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