#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.
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)
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)
{
int has_double_error(unsigned code)
{
- unsigned i;
- unsigned data = code >> PARITY_BITS;
- unsigned parity = code & ((1 << PARITY_BITS) - 1);
- unsigned gen_parity = generate_parity(data);
-
- unsigned hamming_parity = parity >> 1;
- unsigned gen_hamming_parity = gen_parity >> 1;
- unsigned extra_parity = find_parity_32(code);
-
- /* no errors at all (user should have used has_error() first; boo, hiss) */
- if (hamming_parity == gen_hamming_parity && extra_parity == 0)
- return 0;
-
- /* both hamming and simple parity errors; this is a single-bit error */
- if (hamming_parity != gen_hamming_parity && extra_parity == 1)
- return 0;
-
- /* hamming says OK, but simple parity indicates an error => simple parity error is wrong */
- if (hamming_parity == gen_hamming_parity && extra_parity == 1)
- return 0;
-
- /* hamming says error, simple parity says OK => DOUBLE ERROR */
- return 1;
+ unsigned parity_diff = generate_parity(code >> PARITY_BITS) ^ code;
+ return (parity_diff & ((1 << PARITY_BITS) - 1)) && !find_parity_32(code);
}
/* Correct any single-bit error -- assumes there are no double-bit errors */
void check_zero_bit_detection()
{
unsigned i;
- printf("Checking zero bit detection.\n");
+ printf("Checking zero bit detection.");
+ fflush(stdout);
for (i = 0; i < NUM_DATA_WORDS; ++i) {
unsigned code = make_codeword(i);
+
+ if ((i & 0xfffff) == 0) {
+ printf(".");
+ fflush(stdout);
+ }
+
if (has_error(code)) {
printf("ERROR: Failed zero-bit test 1 for %x\n", i);
}
printf("ERROR: Failed zero-bit test 2 for %x\n", i);
}
}
+
+ printf("\n");
}
void check_single_bit_detection()
{
unsigned i, j;
- printf("Checking single bit detection and correction.\n");
+ printf("Checking single bit detection and correction.");
+ fflush(stdout);
for (i = 0; i < NUM_DATA_WORDS; ++i) {
unsigned code = make_codeword(i);
+
+ if ((i & 0xfffff) == 0) {
+ printf(".");
+ fflush(stdout);
+ }
+
for (j = 0; j < CODE_BITS; ++j) {
unsigned corrupted_code = code ^ (1 << j);
}
}
}
+
+ printf("\n");
}
void check_double_bit_detection()
{
unsigned i, j, k;
- printf("Checking double bit detection.\n");
+ printf("Checking double bit detection.");
+ fflush(stdout);
for (i = 0; i < NUM_DATA_WORDS; ++i) {
unsigned code = make_codeword(i);
+
+ if ((i & 0xfffff) == 0) {
+ printf(".");
+ fflush(stdout);
+ }
+
for (j = 0; j < CODE_BITS; ++j) {
for (k = 0; k < CODE_BITS; ++k) {
unsigned corrupted_code = code ^ (1 << j) ^ (1 << k);
}
}
}
+
+ printf("\n");
}
int main()
{
- generate_lookup();
check_zero_bit_detection();
check_single_bit_detection();
check_double_bit_detection();