7 #define CODE_BITS (DATA_BITS + PARITY_BITS)
8 #define SAMPLE_SIZE 1000000
9 #define SAMPLE_PROGRESS 100000
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 int permutation_table[CODE_BITS + 1] = {
16 -1, -1, -1, 63, -1, 62, 61, 60, -1, 59, 58, 57, 56, 55, 54, 53, -1, 52, 51, 50, 49, 48, 47, 46, 45, 44, 43, 42, 41, 40, 39, 38, -1, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, -1, 6, 5, 4, 3, 2, 1, 0
19 unsigned find_parity_8(unsigned x)
23 return (0x6996 >> x) & 1;
26 unsigned find_parity_64(unsigned long long x)
28 unsigned y = (x ^ (x >> 32)) & 0xFFFFFFFFULL;
31 return find_parity_8(y);
34 unsigned generate_parity(unsigned long long data)
36 unsigned parity1 = find_parity_64(data & 0xDAB5556AAAAAAAD5ULL);
37 unsigned parity2 = find_parity_64(data & 0xB66CCCD9999999B3ULL);
38 unsigned parity3 = find_parity_64(data & 0x71E3C3C78787878FULL);
39 unsigned parity4 = find_parity_64(data & 0x0FE03FC07F807F80ULL);
40 unsigned parity5 = find_parity_64(data & 0x001FFFC0007FFF80ULL);
41 unsigned parity6 = find_parity_64(data & 0x0000003FFFFFFF80ULL);
42 unsigned parity7 = find_parity_64(data & 0x000000000000007FULL);
43 unsigned parity8 = find_parity_64(data & 0xED3A65B4CB4B34E9ULL);
45 return parity8 | (parity7 << 1) | (parity6 << 2) | (parity5 << 3) | (parity4 << 4) | (parity3 << 5) | (parity2 << 6) | (parity1 << 7);
48 /* can detect all single or double bit errors */
49 int has_error(unsigned long long data, unsigned parity)
51 return (generate_parity(data) != parity);
54 int has_double_error(unsigned long long data, unsigned parity)
56 return (generate_parity(data) != parity) && (find_parity_64(data) == find_parity_8(parity));
59 /* Correct any single-bit error -- assumes there are no double-bit errors */
60 unsigned long long correct_single_bit_error(unsigned long long data, unsigned parity)
62 unsigned parity_diff = generate_parity(data) ^ parity;
65 for (i = 0; i < PARITY_BITS - 1; ++i) {
66 if (parity_diff & (1 << (PARITY_BITS - 1 - i))) {
71 /* flip the wrong bit, if it's in the data */
72 if (permutation_table[bp] != -1) {
73 data ^= (1ULL << permutation_table[bp]);
79 void check_zero_bit_detection()
82 printf("Checking zero bit detection.");
85 for (i = 0; i < SAMPLE_SIZE; ++i) {
86 unsigned long long data =
87 ((unsigned long long)(rand()) << 40) ^
88 ((unsigned long long)(rand()) << 20) ^
89 ((unsigned long long)(rand()));
90 unsigned long long parity =
91 generate_parity(data);
93 if ((i % SAMPLE_PROGRESS) == 0) {
98 if (has_error(data, parity)) {
99 printf("ERROR: Failed zero-bit test 1 for %llx\n", data);
101 if (has_double_error(data, parity)) {
102 printf("ERROR: Failed zero-bit test 2 for %llx\n", data);
109 void check_single_bit_detection()
112 printf("Checking single bit detection and correction.");
115 for (i = 0; i < SAMPLE_SIZE; ++i) {
116 unsigned long long data =
117 ((unsigned long long)(rand()) << 40) ^
118 ((unsigned long long)(rand()) << 20) ^
119 ((unsigned long long)(rand()));
120 unsigned long long parity =
121 generate_parity(data);
123 if ((i % SAMPLE_PROGRESS) == 0) {
128 for (j = 0; j < CODE_BITS; ++j) {
129 unsigned long long corrupted_data = data;
130 unsigned corrupted_parity = parity;
133 corrupted_data ^= (1ULL << j);
135 corrupted_parity ^= (1 << (j - DATA_BITS));
138 if (!has_error(corrupted_data, corrupted_parity)) {
139 printf("ERROR: Failed single-bit test 1 for %llx with bit %u flipped\n", data, j);
141 if (has_double_error(corrupted_data, corrupted_parity)) {
142 printf("ERROR: Failed single-bit test 2 for %llx with bit %u flipped\n", data, j);
144 if (correct_single_bit_error(corrupted_data, corrupted_parity) != data) {
145 printf("ERROR: Failed single-bit correction test for %llx with bit %u flipped\n", data, j);
153 void check_double_bit_detection()
156 printf("Checking double bit detection.");
159 for (i = 0; i < SAMPLE_SIZE; ++i) {
160 unsigned long long data =
161 ((unsigned long long)(rand()) << 40) ^
162 ((unsigned long long)(rand()) << 20) ^
163 ((unsigned long long)(rand()));
164 unsigned long long parity =
165 generate_parity(data);
167 if ((i % SAMPLE_PROGRESS) == 0) {
172 for (j = 0; j < CODE_BITS; ++j) {
173 for (k = j + 1; k < CODE_BITS; ++k) {
174 unsigned long long corrupted_data = data;
175 unsigned corrupted_parity = parity;
177 corrupted_data ^= (1ULL << j);
179 corrupted_parity ^= (1 << (j - DATA_BITS));
182 corrupted_data ^= (1ULL << k);
184 corrupted_parity ^= (1 << (k - DATA_BITS));
187 if (!has_error(corrupted_data, corrupted_parity)) {
188 printf("ERROR: Failed double-bit test 1 for %llx with bit %u and %u flipped\n", data, j, k);
190 if (!has_double_error(corrupted_data, corrupted_parity)) {
191 printf("ERROR: Failed double-bit test 2 for %llx with bit %u and %u flipped\n", data, j, k);
203 check_zero_bit_detection();
204 check_single_bit_detection();
205 check_double_bit_detection();