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