From 2d2d570df6321333be129d1d4b1d80b118f9ae0a Mon Sep 17 00:00:00 2001 From: "sgunderson@bigfoot.com" <> Date: Wed, 16 Jan 2008 01:42:39 +0100 Subject: [PATCH] Add an implementation of the (72,64) Hamming codes. --- hamming64.c | 208 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 208 insertions(+) create mode 100644 hamming64.c diff --git a/hamming64.c b/hamming64.c new file mode 100644 index 0000000..1f0acfb --- /dev/null +++ b/hamming64.c @@ -0,0 +1,208 @@ +#include +#include +#include + +#define DATA_BITS 64 +#define PARITY_BITS 8 +#define CODE_BITS (DATA_BITS + PARITY_BITS) +#define SAMPLE_SIZE 1000000 +#define SAMPLE_PROGRESS 100000 + +/* + * Needed since we store all the parity at the end of the word, not at the expected + * power-of-two bit positions. + */ +int permutation_table[CODE_BITS + 1] = { + -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 +}; + +unsigned find_parity_8(unsigned x) +{ + x ^= x >> 4; + x &= 0xf; + return (0x6996 >> x) & 1; +} + +unsigned find_parity_64(unsigned long long x) +{ + unsigned y = (x ^ (x >> 32)) & 0xFFFFFFFFULL; + y ^= y >> 16; + y ^= y >> 8; + return find_parity_8(y); +} + +unsigned generate_parity(unsigned long long data) +{ + unsigned parity1 = find_parity_64(data & 0xDAB5556AAAAAAAD5ULL); + unsigned parity2 = find_parity_64(data & 0xB66CCCD9999999B3ULL); + unsigned parity3 = find_parity_64(data & 0x71E3C3C78787878FULL); + unsigned parity4 = find_parity_64(data & 0x0FE03FC07F807F80ULL); + unsigned parity5 = find_parity_64(data & 0x001FFFC0007FFF80ULL); + unsigned parity6 = find_parity_64(data & 0x0000003FFFFFFF80ULL); + unsigned parity7 = find_parity_64(data & 0x000000000000007FULL); + unsigned parity8 = find_parity_64(data & 0xED3A65B4CB4B34E9ULL); + + return parity8 | (parity7 << 1) | (parity6 << 2) | (parity5 << 3) | (parity4 << 4) | (parity3 << 5) | (parity2 << 6) | (parity1 << 7); +} + +/* can detect all single or double bit errors */ +int has_error(unsigned long long data, unsigned parity) +{ + return (generate_parity(data) != parity); +} + +int has_double_error(unsigned long long data, unsigned parity) +{ + return (generate_parity(data) != parity) && (find_parity_64(data) == find_parity_8(parity)); +} + +/* Correct any single-bit error -- assumes there are no double-bit errors */ +unsigned long long correct_single_bit_error(unsigned long long data, unsigned parity) +{ + unsigned parity_diff = generate_parity(data) ^ parity; + unsigned bp = 0, i; + + for (i = 0; i < PARITY_BITS - 1; ++i) { + if (parity_diff & (1 << (PARITY_BITS - 1 - i))) { + bp |= (1 << i); + } + } + + /* flip the wrong bit, if it's in the data */ + if (permutation_table[bp] != -1) { + data ^= (1ULL << permutation_table[bp]); + } + + return data; +} + +void check_zero_bit_detection() +{ + unsigned i; + printf("Checking zero bit detection."); + fflush(stdout); + + for (i = 0; i < SAMPLE_SIZE; ++i) { + unsigned long long data = + ((unsigned long long)(rand()) << 40) ^ + ((unsigned long long)(rand()) << 20) ^ + ((unsigned long long)(rand())); + unsigned long long parity = + generate_parity(data); + + if ((i % SAMPLE_PROGRESS) == 0) { + printf("."); + fflush(stdout); + } + + if (has_error(data, parity)) { + printf("ERROR: Failed zero-bit test 1 for %llx\n", data); + } + if (has_double_error(data, parity)) { + printf("ERROR: Failed zero-bit test 2 for %llx\n", data); + } + } + + printf("\n"); +} + +void check_single_bit_detection() +{ + unsigned i, j; + printf("Checking single bit detection and correction."); + fflush(stdout); + + for (i = 0; i < SAMPLE_SIZE; ++i) { + unsigned long long data = + ((unsigned long long)(rand()) << 40) ^ + ((unsigned long long)(rand()) << 20) ^ + ((unsigned long long)(rand())); + unsigned long long parity = + generate_parity(data); + + if ((i % SAMPLE_PROGRESS) == 0) { + printf("."); + fflush(stdout); + } + + for (j = 0; j < CODE_BITS; ++j) { + unsigned long long corrupted_data = data; + unsigned corrupted_parity = parity; + + if (j < DATA_BITS) { + corrupted_data ^= (1ULL << j); + } else { + corrupted_parity ^= (1 << (j - DATA_BITS)); + } + + if (!has_error(corrupted_data, corrupted_parity)) { + printf("ERROR: Failed single-bit test 1 for %llx with bit %u flipped\n", data, j); + } + if (has_double_error(corrupted_data, corrupted_parity)) { + printf("ERROR: Failed single-bit test 2 for %llx with bit %u flipped\n", data, j); + } + if (correct_single_bit_error(corrupted_data, corrupted_parity) != data) { + printf("ERROR: Failed single-bit correction test for %llx with bit %u flipped\n", data, j); + } + } + } + + printf("\n"); +} + +void check_double_bit_detection() +{ + unsigned i, j, k; + printf("Checking double bit detection."); + fflush(stdout); + + for (i = 0; i < SAMPLE_SIZE; ++i) { + unsigned long long data = + ((unsigned long long)(rand()) << 40) ^ + ((unsigned long long)(rand()) << 20) ^ + ((unsigned long long)(rand())); + unsigned long long parity = + generate_parity(data); + + if ((i % SAMPLE_PROGRESS) == 0) { + printf("."); + fflush(stdout); + } + + for (j = 0; j < CODE_BITS; ++j) { + for (k = j + 1; k < CODE_BITS; ++k) { + unsigned long long corrupted_data = data; + unsigned corrupted_parity = parity; + if (j < DATA_BITS) { + corrupted_data ^= (1ULL << j); + } else { + corrupted_parity ^= (1 << (j - DATA_BITS)); + } + if (k < DATA_BITS) { + corrupted_data ^= (1ULL << k); + } else { + corrupted_parity ^= (1 << (k - DATA_BITS)); + } + + if (!has_error(corrupted_data, corrupted_parity)) { + printf("ERROR: Failed double-bit test 1 for %llx with bit %u and %u flipped\n", data, j, k); + } + if (!has_double_error(corrupted_data, corrupted_parity)) { + printf("ERROR: Failed double-bit test 2 for %llx with bit %u and %u flipped\n", data, j, k); + } + } + } + } + + printf("\n"); +} + +int main() +{ + srand(time(NULL)); + check_zero_bit_detection(); + check_single_bit_detection(); + check_double_bit_detection(); + + return 0; +} -- 2.39.2