From 1d36515bc7ae02633e1ad2b423d2b0a63793ffd0 Mon Sep 17 00:00:00 2001 From: "Steinar H. Gunderson" Date: Thu, 2 Mar 2006 13:44:51 +0000 Subject: [PATCH] Implement single-bit correction for hamming32. --- hamming.txt | 4 ++-- hamming32.c | 33 ++++++--------------------------- 2 files changed, 8 insertions(+), 29 deletions(-) diff --git a/hamming.txt b/hamming.txt index a3747e3..8391ba3 100644 --- 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 cbfb447..24f818c 100644 --- 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 } } } -- 2.39.2