X-Git-Url: https://git.sesse.net/?a=blobdiff_plain;f=hamming32.c;h=2d8b882c7fdefeb8b6adb13ced7ce9918a02b150;hb=7ad344802d7f2865832ac37ab032365a5fbeaab9;hp=cbfb447fbb841ddb5e675b42c3cf9d354dc25c0c;hpb=cee238a7744c1a111804a96062a133813d8d42b2;p=hamming

diff --git a/hamming32.c b/hamming32.c
index cbfb447..2d8b882 100644
--- a/hamming32.c
+++ b/hamming32.c
@@ -6,25 +6,22 @@
 #define CODE_BITS    (DATA_BITS + PARITY_BITS)
 #define NUM_DATA_WORDS (1 << DATA_BITS)
 
-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 */
 unsigned find_parity_32(unsigned data)
 {
-	return
-		hamming_parity_lookup[ data        & 0xff] ^
-		hamming_parity_lookup[(data >>  8) & 0xff] ^
-		hamming_parity_lookup[(data >> 16) & 0xff] ^
-		hamming_parity_lookup[ data >> 24        ];
+	data = (data >> 16) ^ data;
+	data = (data >> 8) ^ data;
+	data = (data >> 4) ^ data;
+	data = (data >> 2) ^ data;
+	data = (data >> 1) ^ data;
+	return (data & 1);
 }
 
 unsigned generate_parity(unsigned data)
@@ -44,20 +41,6 @@ unsigned make_codeword(unsigned data)
 	return (data << PARITY_BITS) | generate_parity(data);
 }
 
-void generate_lookup()
-{
-	unsigned i;
-
-	printf("Generating lookup table.\n");
-	
-	for (i = 0; i < 256; ++i) {
-		unsigned parity = (i >> 4) ^ i;
-		parity = (parity >> 2) ^ parity;
-		parity = (parity >> 1) ^ parity;
-		hamming_parity_lookup[i] = parity & 1;
-	}
-}
-
 /* can detect all single or double bit errors */
 int has_error(unsigned code)
 {
@@ -94,30 +77,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;
-
-	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];
-	}
+	unsigned parity_diff = generate_parity(code >> PARITY_BITS) ^ code;
+	unsigned bp = 0, 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 +92,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 +130,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
 		}
 	}
 }
@@ -200,7 +163,6 @@ void check_double_bit_detection()
 
 int main()
 {
-	generate_lookup();
 	check_zero_bit_detection();
 	check_single_bit_detection();
 	check_double_bit_detection();