Implement single-bit correction for hamming32.

diff --git a/hamming.txt b/hamming.txt
index a3747e33cec09fca6a158f54a503460e8e485457..8391ba386f33160049cec135b8cafa746e487d38 100644 (file)
--- a/hamming.txt
+++ b/hamming.txt
@@ -49,7 +49,7 @@ p5                                    xx xx xx xx xx xx xx  xx xx xx xx xx xx xx
 Last bit is the parity of all the data bits _and_ the parity bits, which means it gets
 counted as follows (?):
 
-p6 xx xx  xx    xx xx    xx        xx xx xx    xx       xx  xx             xx xx
+p6 xx xx  xx    xx xx    xx        xx xx xx    xx       xx  xx       xx    xx xx
 
 Converted to bitmasks:
 
@@ -58,4 +58,4 @@ p2: 02 d9 b3 33
 p3: 01 c7 8f 0f
 p4: 00 3f 80 ff
 p5: 00 00 7f ff
-p6: 03 b4 e9 86
+p6: 03 b4 e9 96

diff --git a/hamming32.c b/hamming32.c
index cbfb447fbb841ddb5e675b42c3cf9d354dc25c0c..24f818c1e55596db2003f02f68812dcce6e7fccf 100644 (file)
--- a/hamming32.c
+++ b/hamming32.c
@@ -10,11 +10,10 @@ unsigned char hamming_parity_lookup[256];
 
 /* 
  * Needed since we store all the parity at the end of the word, not at the expected
- * power-of-two bit positions. This is the inverse of the mapping
- * (0..31) -> (0, 16, 8, 4, 2, 1, the rest in ascending order)
+ * power-of-two bit positions.
  */
 unsigned char permutation_table[CODE_BITS] = {
-       0, 5, 4, 6, 3, 7, 8, 9, 2, 10, 11, 12, 13, 14, 15, 16, 1, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31
+       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
 };
 
 /* FIXME: check if the lookup table actually helps us any here */
@@ -94,30 +93,14 @@ int has_double_error(unsigned code)
        return 1;
 }
 
-#if 0
 /* Correct any single-bit error -- assumes there are no double-bit errors */
 unsigned correct_single_bit_error(unsigned code)
 {
-       unsigned bits[CODE_BITS];
-       unsigned parity[PARITY_BITS];
-       unsigned i, bp = 0;
+       unsigned parity_diff = generate_parity(code >> PARITY_BITS) ^ code;
+       unsigned bp = 0, i;
 
-       parity[EXTRA_BIT_POSITION] = 0;
-
-       for (i = 0; i < CODE_BITS; ++i) {
-               bits[i] = (code & (1 << i)) ? 1 : 0;
-       }
-       for (i = 1; i < CODE_BITS; ++i) {
-               parity[EXTRA_BIT_POSITION] ^= bits[i];
-       }
-
-       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];
-       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];
-       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];
-       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];
-       
        for (i = 0; i < PARITY_BITS - 1; ++i) {
-               if (parity[i] != bits[PARITY_BITS - 1 - i]) {
+               if (parity_diff & (1 << (PARITY_BITS - 1 - i))) {
                        bp |= (1 << i);
                }
        }
@@ -125,13 +108,11 @@ unsigned correct_single_bit_error(unsigned code)
        if (bp != 0) {
                /* flip the wrong bit */
                code ^= (1 << permutation_table[bp]);
-               parity[EXTRA_BIT_POSITION] ^= 1;
        }
 
        /* recompute the lower parity */
-       return (code & ~1) | parity[EXTRA_BIT_POSITION];
+       return (code & ~1) | find_parity_32(code & ~1);
 }
-#endif
 
 void check_zero_bit_detection()
 {
@@ -165,11 +146,9 @@ void check_single_bit_detection()
                        if (has_double_error(corrupted_code)) {
                                printf("ERROR: Failed single-bit test 2 for %x with bit %u flipped\n", i, j);
                        }
-#if 0                  
                        if (correct_single_bit_error(corrupted_code) != code) {
                                printf("ERROR: Failed single-bit correction test for %x with bit %u flipped\n", i, j);
                        }
-#endif
                }
        }
 }