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