5 #define EXTRA_BIT_POSITION (PARITY_BITS - 1)
6 #define CODE_BITS (DATA_BITS + PARITY_BITS)
7 #define NUM_DATA_WORDS (1 << DATA_BITS)
10 * Needed since we store all the parity at the end of the word, not at the expected
11 * power-of-two bit positions.
13 unsigned char permutation_table[CODE_BITS] = {
14 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
17 unsigned find_parity_32(unsigned data)
19 data = (data >> 16) ^ data;
20 data = (data >> 8) ^ data;
21 data = (data >> 4) ^ data;
22 data = (data >> 2) ^ data;
23 data = (data >> 1) ^ data;
27 unsigned generate_parity(unsigned data)
29 unsigned parity1 = find_parity_32(data & 0x036ad555);
30 unsigned parity2 = find_parity_32(data & 0x02d9b333);
31 unsigned parity3 = find_parity_32(data & 0x01c78f0f);
32 unsigned parity4 = find_parity_32(data & 0x003f80ff);
33 unsigned parity5 = find_parity_32(data & 0x00007fff);
34 unsigned parity6 = find_parity_32(data & 0x03b4e996);
36 return parity6 | (parity5 << 1) | (parity4 << 2) | (parity3 << 3) | (parity2 << 4) | (parity1 << 5);
39 unsigned make_codeword(unsigned data)
41 return (data << PARITY_BITS) | generate_parity(data);
44 /* can detect all single or double bit errors */
45 int has_error(unsigned code)
47 unsigned data = code >> PARITY_BITS;
48 unsigned parity = code & ((1 << PARITY_BITS) - 1);
50 return (generate_parity(data) != parity);
53 int has_double_error(unsigned code)
55 unsigned parity_diff = generate_parity(code >> PARITY_BITS) ^ code;
56 return (parity_diff & ((1 << PARITY_BITS) - 1)) && !find_parity_32(code);
59 /* Correct any single-bit error -- assumes there are no double-bit errors */
60 unsigned correct_single_bit_error(unsigned code)
62 unsigned parity_diff = generate_parity(code >> PARITY_BITS) ^ code;
65 for (i = 0; i < PARITY_BITS - 1; ++i) {
66 if (parity_diff & (1 << (PARITY_BITS - 1 - i))) {
72 /* flip the wrong bit */
73 code ^= (1 << permutation_table[bp]);
76 /* recompute the lower parity */
77 return (code & ~1) | find_parity_32(code & ~1);
80 void check_zero_bit_detection()
83 printf("Checking zero bit detection.");
86 for (i = 0; i < NUM_DATA_WORDS; ++i) {
87 unsigned code = make_codeword(i);
89 if ((i & 0xfffff) == 0) {
94 if (has_error(code)) {
95 printf("ERROR: Failed zero-bit test 1 for %x\n", i);
97 if (has_double_error(code)) {
98 printf("ERROR: Failed zero-bit test 2 for %x\n", i);
105 void check_single_bit_detection()
108 printf("Checking single bit detection and correction.");
111 for (i = 0; i < NUM_DATA_WORDS; ++i) {
112 unsigned code = make_codeword(i);
114 if ((i & 0xfffff) == 0) {
119 for (j = 0; j < CODE_BITS; ++j) {
120 unsigned corrupted_code = code ^ (1 << j);
122 if (!has_error(corrupted_code)) {
123 printf("ERROR: Failed single-bit test 1 for %x with bit %u flipped\n", i, j);
125 if (has_double_error(corrupted_code)) {
126 printf("ERROR: Failed single-bit test 2 for %x with bit %u flipped\n", i, j);
128 if (correct_single_bit_error(corrupted_code) != code) {
129 printf("ERROR: Failed single-bit correction test for %x with bit %u flipped\n", i, j);
137 void check_double_bit_detection()
140 printf("Checking double bit detection.");
143 for (i = 0; i < NUM_DATA_WORDS; ++i) {
144 unsigned code = make_codeword(i);
146 if ((i & 0xfffff) == 0) {
151 for (j = 0; j < CODE_BITS; ++j) {
152 for (k = 0; k < CODE_BITS; ++k) {
153 unsigned corrupted_code = code ^ (1 << j) ^ (1 << k);
157 if (!has_error(corrupted_code)) {
158 printf("ERROR: Failed double-bit test 1 for %x with bit %u and %u flipped\n", i, j, k);
160 if (!has_double_error(corrupted_code)) {
161 printf("ERROR: Failed double-bit test 2 for %x with bit %u and %u flipped\n", i, j, k);
172 check_zero_bit_detection();
173 check_single_bit_detection();
174 check_double_bit_detection();