5 #define EXTRA_BIT_POSITION (PARITY_BITS - 1)
6 #define CODE_BITS (DATA_BITS + PARITY_BITS)
7 #define NUM_DATA_WORDS (1 << DATA_BITS)
9 unsigned char hamming_parity_lookup[256];
12 * Needed since we store all the parity at the end of the word, not at the expected
13 * power-of-two bit positions.
15 unsigned char permutation_table[CODE_BITS] = {
16 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
19 /* FIXME: check if the lookup table actually helps us any here */
20 unsigned find_parity_32(unsigned data)
23 hamming_parity_lookup[ data & 0xff] ^
24 hamming_parity_lookup[(data >> 8) & 0xff] ^
25 hamming_parity_lookup[(data >> 16) & 0xff] ^
26 hamming_parity_lookup[ data >> 24 ];
29 unsigned generate_parity(unsigned data)
31 unsigned parity1 = find_parity_32(data & 0x036ad555);
32 unsigned parity2 = find_parity_32(data & 0x02d9b333);
33 unsigned parity3 = find_parity_32(data & 0x01c78f0f);
34 unsigned parity4 = find_parity_32(data & 0x003f80ff);
35 unsigned parity5 = find_parity_32(data & 0x00007fff);
36 unsigned parity6 = find_parity_32(data & 0x03b4e996);
38 return parity6 | (parity5 << 1) | (parity4 << 2) | (parity3 << 3) | (parity2 << 4) | (parity1 << 5);
41 unsigned make_codeword(unsigned data)
43 return (data << PARITY_BITS) | generate_parity(data);
46 void generate_lookup()
50 printf("Generating lookup table.\n");
52 for (i = 0; i < 256; ++i) {
53 unsigned parity = (i >> 4) ^ i;
54 parity = (parity >> 2) ^ parity;
55 parity = (parity >> 1) ^ parity;
56 hamming_parity_lookup[i] = parity & 1;
60 /* can detect all single or double bit errors */
61 int has_error(unsigned code)
63 unsigned data = code >> PARITY_BITS;
64 unsigned parity = code & ((1 << PARITY_BITS) - 1);
66 return (generate_parity(data) != parity);
69 int has_double_error(unsigned code)
72 unsigned data = code >> PARITY_BITS;
73 unsigned parity = code & ((1 << PARITY_BITS) - 1);
74 unsigned gen_parity = generate_parity(data);
76 unsigned hamming_parity = parity >> 1;
77 unsigned gen_hamming_parity = gen_parity >> 1;
78 unsigned extra_parity = find_parity_32(code);
80 /* no errors at all (user should have used has_error() first; boo, hiss) */
81 if (hamming_parity == gen_hamming_parity && extra_parity == 0)
84 /* both hamming and simple parity errors; this is a single-bit error */
85 if (hamming_parity != gen_hamming_parity && extra_parity == 1)
88 /* hamming says OK, but simple parity indicates an error => simple parity error is wrong */
89 if (hamming_parity == gen_hamming_parity && extra_parity == 1)
92 /* hamming says error, simple parity says OK => DOUBLE ERROR */
96 /* Correct any single-bit error -- assumes there are no double-bit errors */
97 unsigned correct_single_bit_error(unsigned code)
99 unsigned parity_diff = generate_parity(code >> PARITY_BITS) ^ code;
102 for (i = 0; i < PARITY_BITS - 1; ++i) {
103 if (parity_diff & (1 << (PARITY_BITS - 1 - i))) {
109 /* flip the wrong bit */
110 code ^= (1 << permutation_table[bp]);
113 /* recompute the lower parity */
114 return (code & ~1) | find_parity_32(code & ~1);
117 void check_zero_bit_detection()
120 printf("Checking zero bit detection.\n");
122 for (i = 0; i < NUM_DATA_WORDS; ++i) {
123 unsigned code = make_codeword(i);
124 if (has_error(code)) {
125 printf("ERROR: Failed zero-bit test 1 for %x\n", i);
127 if (has_double_error(code)) {
128 printf("ERROR: Failed zero-bit test 2 for %x\n", i);
133 void check_single_bit_detection()
136 printf("Checking single bit detection and correction.\n");
138 for (i = 0; i < NUM_DATA_WORDS; ++i) {
139 unsigned code = make_codeword(i);
140 for (j = 0; j < CODE_BITS; ++j) {
141 unsigned corrupted_code = code ^ (1 << j);
143 if (!has_error(corrupted_code)) {
144 printf("ERROR: Failed single-bit test 1 for %x with bit %u flipped\n", i, j);
146 if (has_double_error(corrupted_code)) {
147 printf("ERROR: Failed single-bit test 2 for %x with bit %u flipped\n", i, j);
149 if (correct_single_bit_error(corrupted_code) != code) {
150 printf("ERROR: Failed single-bit correction test for %x with bit %u flipped\n", i, j);
156 void check_double_bit_detection()
159 printf("Checking double bit detection.\n");
161 for (i = 0; i < NUM_DATA_WORDS; ++i) {
162 unsigned code = make_codeword(i);
163 for (j = 0; j < CODE_BITS; ++j) {
164 for (k = 0; k < CODE_BITS; ++k) {
165 unsigned corrupted_code = code ^ (1 << j) ^ (1 << k);
169 if (!has_error(corrupted_code)) {
170 printf("ERROR: Failed double-bit test 1 for %x with bit %u and %u flipped\n", i, j, k);
172 if (!has_double_error(corrupted_code)) {
173 printf("ERROR: Failed double-bit test 2 for %x with bit %u and %u flipped\n", i, j, k);
183 check_zero_bit_detection();
184 check_single_bit_detection();
185 check_double_bit_detection();