git.sesse.net Git - hamming/blob - hamming32.c

   1 #include <stdio.h>
   2
   3 #define DATA_BITS    26
   4 #define PARITY_BITS  6
   5 #define EXTRA_BIT_POSITION (PARITY_BITS - 1)
   6 #define CODE_BITS    (DATA_BITS + PARITY_BITS)
   7 #define NUM_DATA_WORDS (1 << DATA_BITS)
   8
   9 unsigned char hamming_parity_lookup[256];
  10
  11 /*
  12  * Needed since we store all the parity at the end of the word, not at the expected
  13  * power-of-two bit positions.
  14  */
  15 unsigned char permutation_table[CODE_BITS] = {
  16         0, 5, 4, 31, 3, 30, 29, 28, 2, 27, 26, 25, 24, 23, 22, 21, 1, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6
  17 };
  18
  19 /* FIXME: check if the lookup table actually helps us any here */
  20 unsigned find_parity_32(unsigned data)
  21 {
  22         return
  23                 hamming_parity_lookup[ data        & 0xff] ^
  24                 hamming_parity_lookup[(data >>  8) & 0xff] ^
  25                 hamming_parity_lookup[(data >> 16) & 0xff] ^
  26                 hamming_parity_lookup[ data >> 24        ];
  27 }
  28
  29 unsigned generate_parity(unsigned data)
  30 {
  31         unsigned parity1 = find_parity_32(data & 0x036ad555);
  32         unsigned parity2 = find_parity_32(data & 0x02d9b333);
  33         unsigned parity3 = find_parity_32(data & 0x01c78f0f);
  34         unsigned parity4 = find_parity_32(data & 0x003f80ff);
  35         unsigned parity5 = find_parity_32(data & 0x00007fff);
  36         unsigned parity6 = find_parity_32(data & 0x03b4e996);
  37
  38         return parity6 | (parity5 << 1) | (parity4 << 2) | (parity3 << 3) | (parity2 << 4) | (parity1 << 5);
  39 }
  40
  41 unsigned make_codeword(unsigned data)
  42 {
  43         return (data << PARITY_BITS) | generate_parity(data);
  44 }
  45
  46 void generate_lookup()
  47 {
  48         unsigned i;
  49
  50         printf("Generating lookup table.\n");
  51
  52         for (i = 0; i < 256; ++i) {
  53                 unsigned parity = (i >> 4) ^ i;
  54                 parity = (parity >> 2) ^ parity;
  55                 parity = (parity >> 1) ^ parity;
  56                 hamming_parity_lookup[i] = parity & 1;
  57         }
  58 }
  59
  60 /* can detect all single or double bit errors */
  61 int has_error(unsigned code)
  62 {
  63         unsigned data = code >> PARITY_BITS;
  64         unsigned parity = code & ((1 << PARITY_BITS) - 1);
  65
  66         return (generate_parity(data) != parity);
  67 }
  68
  69 int has_double_error(unsigned code)
  70 {
  71         unsigned i;
  72         unsigned data = code >> PARITY_BITS;
  73         unsigned parity = code & ((1 << PARITY_BITS) - 1);
  74         unsigned gen_parity = generate_parity(data);
  75
  76         unsigned hamming_parity = parity >> 1;
  77         unsigned gen_hamming_parity = gen_parity >> 1;
  78         unsigned extra_parity = find_parity_32(code);
  79
  80         /* no errors at all (user should have used has_error() first; boo, hiss) */
  81         if (hamming_parity == gen_hamming_parity && extra_parity == 0)
  82                 return 0;
  83
  84         /* both hamming and simple parity errors; this is a single-bit error */
  85         if (hamming_parity != gen_hamming_parity && extra_parity == 1)
  86                 return 0;
  87
  88         /* hamming says OK, but simple parity indicates an error => simple parity error is wrong */
  89         if (hamming_parity == gen_hamming_parity && extra_parity == 1)
  90                 return 0;
  91
  92         /* hamming says error, simple parity says OK => DOUBLE ERROR */
  93         return 1;
  94 }
  95
  96 /* Correct any single-bit error -- assumes there are no double-bit errors */
  97 unsigned correct_single_bit_error(unsigned code)
  98 {
  99         unsigned parity_diff = generate_parity(code >> PARITY_BITS) ^ code;
 100         unsigned bp = 0, i;
 101
 102         for (i = 0; i < PARITY_BITS - 1; ++i) {
 103                 if (parity_diff & (1 << (PARITY_BITS - 1 - i))) {
 104                         bp |= (1 << i);
 105                 }
 106         }
 107
 108         if (bp != 0) {
 109                 /* flip the wrong bit */
 110                 code ^= (1 << permutation_table[bp]);
 111         }
 112
 113         /* recompute the lower parity */
 114         return (code & ~1) | find_parity_32(code & ~1);
 115 }
 116
 117 void check_zero_bit_detection()
 118 {
 119         unsigned i;
 120         printf("Checking zero bit detection.\n");
 121
 122         for (i = 0; i < NUM_DATA_WORDS; ++i) {
 123                 unsigned code = make_codeword(i);
 124                 if (has_error(code)) {
 125                         printf("ERROR: Failed zero-bit test 1 for %x\n", i);
 126                 }
 127                 if (has_double_error(code)) {
 128                         printf("ERROR: Failed zero-bit test 2 for %x\n", i);
 129                 }
 130         }
 131 }
 132
 133 void check_single_bit_detection()
 134 {
 135         unsigned i, j;
 136         printf("Checking single bit detection and correction.\n");
 137
 138         for (i = 0; i < NUM_DATA_WORDS; ++i) {
 139                 unsigned code = make_codeword(i);
 140                 for (j = 0; j < CODE_BITS; ++j) {
 141                         unsigned corrupted_code = code ^ (1 << j);
 142
 143                         if (!has_error(corrupted_code)) {
 144                                 printf("ERROR: Failed single-bit test 1 for %x with bit %u flipped\n", i, j);
 145                         }
 146                         if (has_double_error(corrupted_code)) {
 147                                 printf("ERROR: Failed single-bit test 2 for %x with bit %u flipped\n", i, j);
 148                         }
 149                         if (correct_single_bit_error(corrupted_code) != code) {
 150                                 printf("ERROR: Failed single-bit correction test for %x with bit %u flipped\n", i, j);
 151                         }
 152                 }
 153         }
 154 }
 155
 156 void check_double_bit_detection()
 157 {
 158         unsigned i, j, k;
 159         printf("Checking double bit detection.\n");
 160
 161         for (i = 0; i < NUM_DATA_WORDS; ++i) {
 162                 unsigned code = make_codeword(i);
 163                 for (j = 0; j < CODE_BITS; ++j) {
 164                         for (k = 0; k < CODE_BITS; ++k) {
 165                                 unsigned corrupted_code = code ^ (1 << j) ^ (1 << k);
 166                                 if (j == k)
 167                                         continue;
 168
 169                                 if (!has_error(corrupted_code)) {
 170                                         printf("ERROR: Failed double-bit test 1 for %x with bit %u and %u flipped\n", i, j, k);
 171                                 }
 172                                 if (!has_double_error(corrupted_code)) {
 173                                         printf("ERROR: Failed double-bit test 2 for %x with bit %u and %u flipped\n", i, j, k);
 174                                 }
 175                         }
 176                 }
 177         }
 178 }
 179
 180 int main()
 181 {
 182         generate_lookup();
 183         check_zero_bit_detection();
 184         check_single_bit_detection();
 185         check_double_bit_detection();
 186
 187         return 0;
 188 }