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

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