3 /* this is a ~30% win for CPUs with fast 64x64->64 multiplication, but a huge loss otherwise */
4 #define PARALLEL_PARITY 1
8 #define EXTRA_BIT_POSITION (PARITY_BITS - 1)
9 #define CODE_BITS (DATA_BITS + PARITY_BITS)
10 #define NUM_DATA_WORDS (1 << DATA_BITS)
13 * Needed since we store all the parity at the end of the word, not at the expected
14 * power-of-two bit positions.
16 unsigned char permutation_table[CODE_BITS] = {
17 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
20 unsigned find_parity_32(unsigned x)
24 * This variant seems to be slightly faster, but depends on
25 * fast hardware multiplication.
28 x = (x ^ (x >> 2)) & 0x11111111;
36 return (0x6996 >> x) & 1;
40 /* courtesy of neon/nocturnal :-) */
41 unsigned find_parity_32x2(unsigned a, unsigned b)
43 unsigned long long x = (unsigned long long)a | (((unsigned long long)b)<<32);
45 x = (x ^ (x >> 2)) & 0x1111111111111111ULL;
47 return ((x>>28)&1) | ((x>>(32+28-1))&2);
50 unsigned generate_parity(unsigned data)
53 return find_parity_32x2(data & 0x03b4e996, data & 0x00007fff) |
54 (find_parity_32x2(data & 0x003f80ff, data & 0x01c78f0f) << 2) |
55 (find_parity_32x2(data & 0x02d9b333, data & 0x036ad555) << 4);
57 unsigned parity1 = find_parity_32(data & 0x036ad555);
58 unsigned parity2 = find_parity_32(data & 0x02d9b333);
59 unsigned parity3 = find_parity_32(data & 0x01c78f0f);
60 unsigned parity4 = find_parity_32(data & 0x003f80ff);
61 unsigned parity5 = find_parity_32(data & 0x00007fff);
62 unsigned parity6 = find_parity_32(data & 0x03b4e996);
64 return parity6 | (parity5 << 1) | (parity4 << 2) | (parity3 << 3) | (parity2 << 4) | (parity1 << 5);
68 unsigned make_codeword(unsigned data)
70 return (data << PARITY_BITS) | generate_parity(data);
73 /* can detect all single or double bit errors */
74 int has_error(unsigned code)
76 unsigned parity = code & ((1 << PARITY_BITS) - 1);
77 return (generate_parity(code >> PARITY_BITS) != parity);
80 int has_double_error(unsigned code)
82 unsigned parity_diff = generate_parity(code >> PARITY_BITS) ^ code;
83 return (parity_diff & ((1 << PARITY_BITS) - 1)) && !find_parity_32(code);
86 /* Correct any single-bit error -- assumes there are no double-bit errors */
87 unsigned correct_single_bit_error(unsigned code)
89 unsigned parity_diff = generate_parity(code >> PARITY_BITS) ^ code;
92 for (i = 0; i < PARITY_BITS - 1; ++i) {
93 if (parity_diff & (1 << (PARITY_BITS - 1 - i))) {
99 /* flip the wrong bit */
100 code ^= (1 << permutation_table[bp]);
103 /* recompute the lower parity */
104 return (code & ~1) | find_parity_32(code & ~1);
107 void check_zero_bit_detection()
110 printf("Checking zero bit detection.");
113 for (i = 0; i < NUM_DATA_WORDS; ++i) {
114 unsigned code = make_codeword(i);
116 if ((i & 0xfffff) == 0) {
121 if (has_error(code)) {
122 printf("ERROR: Failed zero-bit test 1 for %x\n", i);
124 if (has_double_error(code)) {
125 printf("ERROR: Failed zero-bit test 2 for %x\n", i);
132 void check_single_bit_detection()
135 printf("Checking single bit detection and correction.");
138 for (i = 0; i < NUM_DATA_WORDS; ++i) {
139 unsigned code = make_codeword(i);
141 if ((i & 0xfffff) == 0) {
146 for (j = 0; j < CODE_BITS; ++j) {
147 unsigned corrupted_code = code ^ (1 << j);
149 if (!has_error(corrupted_code)) {
150 printf("ERROR: Failed single-bit test 1 for %x with bit %u flipped\n", i, j);
152 if (has_double_error(corrupted_code)) {
153 printf("ERROR: Failed single-bit test 2 for %x with bit %u flipped\n", i, j);
155 if (correct_single_bit_error(corrupted_code) != code) {
156 printf("ERROR: Failed single-bit correction test for %x with bit %u flipped\n", i, j);
164 void check_double_bit_detection()
167 printf("Checking double bit detection.");
170 for (i = 0; i < NUM_DATA_WORDS; ++i) {
171 unsigned code = make_codeword(i);
173 if ((i & 0xfffff) == 0) {
178 for (j = 0; j < CODE_BITS; ++j) {
179 for (k = 0; k < CODE_BITS; ++k) {
180 unsigned corrupted_code = code ^ (1 << j) ^ (1 << k);
184 if (!has_error(corrupted_code)) {
185 printf("ERROR: Failed double-bit test 1 for %x with bit %u and %u flipped\n", i, j, k);
187 if (!has_double_error(corrupted_code)) {
188 printf("ERROR: Failed double-bit test 2 for %x with bit %u and %u flipped\n", i, j, k);
199 check_zero_bit_detection();
200 check_single_bit_detection();
201 check_double_bit_detection();