X-Git-Url: https://git.sesse.net/?a=blobdiff_plain;f=hamming32.c;h=827841f9f380c1bc82d0c077889edb92cec131cf;hb=cf76fbade05b98081e7e547c4d37f2925a0d274c;hp=69619c60737e89ea3b7d1b1b2ddc3ac4304a80ba;hpb=275dd0e908bb13c61095d367362aa60aae153bcb;p=hamming diff --git a/hamming32.c b/hamming32.c index 69619c6..827841f 100644 --- a/hamming32.c +++ b/hamming32.c @@ -1,42 +1,68 @@ #include +/* this is a ~30% win for CPUs with fast 64x64->64 multiplication, but a huge loss otherwise */ +#define PARALLEL_PARITY 1 + #define DATA_BITS 26 #define PARITY_BITS 6 #define EXTRA_BIT_POSITION (PARITY_BITS - 1) #define CODE_BITS (DATA_BITS + PARITY_BITS) #define NUM_DATA_WORDS (1 << DATA_BITS) -unsigned char hamming_parity_lookup[256]; - /* * Needed since we store all the parity at the end of the word, not at the expected - * power-of-two bit positions. This is the inverse of the mapping - * (0..15) -> (0, 8, 4, 2, 1, the rest in ascending order) + * power-of-two bit positions. */ unsigned char permutation_table[CODE_BITS] = { - 0, 4, 3, 5, 2, 6, 7, 8, 1, 9, 10, 11, 12, 13, 14, 15 + 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 }; -/* FIXME: check if the lookup table actually helps us any here */ -unsigned find_parity_32(unsigned data) +unsigned find_parity_32(unsigned x) +{ +#if 0 + /* + * This variant seems to be slightly faster, but depends on + * fast hardware multiplication. + */ + x = x ^ (x >> 1); + x = (x ^ (x >> 2)) & 0x11111111; + x = x * 0x11111111; + return (x >> 28) & 1; +#else + x ^= x >> 16; + x ^= x >> 8; + x ^= x >> 4; + x &= 0xf; + return (0x6996 >> x) & 1; +#endif +} + +/* courtesy of neon/nocturnal :-) */ +unsigned find_parity_32x2(unsigned a, unsigned b) { - return - hamming_parity_lookup[ data & 0xff] ^ - hamming_parity_lookup[(data >> 8) & 0xff] ^ - hamming_parity_lookup[(data >> 16) & 0xff] ^ - hamming_parity_lookup[ data >> 24 ]; + unsigned long long x = (unsigned long long)a | (((unsigned long long)b)<<32); + x = x ^ (x >> 1); + x = (x ^ (x >> 2)) & 0x1111111111111111ULL; + x = x * 0x11111111; + return ((x>>28)&1) | ((x>>(32+28-1))&2); } unsigned generate_parity(unsigned data) { +#if PARALLEL_PARITY + return find_parity_32x2(data & 0x03b4e996, data & 0x00007fff) | + (find_parity_32x2(data & 0x003f80ff, data & 0x01c78f0f) << 2) | + (find_parity_32x2(data & 0x02d9b333, data & 0x036ad555) << 4); +#else unsigned parity1 = find_parity_32(data & 0x036ad555); unsigned parity2 = find_parity_32(data & 0x02d9b333); unsigned parity3 = find_parity_32(data & 0x01c78f0f); unsigned parity4 = find_parity_32(data & 0x003f80ff); unsigned parity5 = find_parity_32(data & 0x00007fff); unsigned parity6 = find_parity_32(data & 0x03b4e996); - + return parity6 | (parity5 << 1) | (parity4 << 2) | (parity3 << 3) | (parity2 << 4) | (parity1 << 5); +#endif } unsigned make_codeword(unsigned data) @@ -44,80 +70,27 @@ unsigned make_codeword(unsigned data) return (data << PARITY_BITS) | generate_parity(data); } -void generate_lookup() -{ - unsigned i; - - printf("Generating lookup table.\n"); - - for (i = 0; i < 256; ++i) { - unsigned parity = (i >> 4) ^ i; - parity = (parity >> 2) ^ parity; - parity = (parity >> 1) ^ parity; - hamming_parity_lookup[i] = parity & 1; - } -} - /* can detect all single or double bit errors */ int has_error(unsigned code) { - unsigned data = code >> PARITY_BITS; unsigned parity = code & ((1 << PARITY_BITS) - 1); - - return (generate_parity(data) != parity); + return (generate_parity(code >> PARITY_BITS) != parity); } int has_double_error(unsigned code) { - unsigned i; - unsigned data = code >> PARITY_BITS; - unsigned parity = code & ((1 << PARITY_BITS) - 1); - unsigned gen_parity = generate_parity(data); - - unsigned hamming_parity = parity >> 1; - unsigned gen_hamming_parity = gen_parity >> 1; - unsigned extra_parity = find_parity_32(code); - - /* no errors at all (user should have used has_error() first; boo, hiss) */ - if (hamming_parity == gen_hamming_parity && extra_parity == 1) - return 0; - - /* both hamming and simple parity errors; this is a single-bit error */ - if (hamming_parity != gen_hamming_parity && extra_parity == 0) - return 0; - - /* hamming says OK, but simple parity indicates an error => simple parity error is wrong */ - if (hamming_parity == gen_hamming_parity && extra_parity == 0) - return 0; - - /* hamming says error, simple parity says OK => DOUBLE ERROR */ - return 1; + unsigned parity_diff = generate_parity(code >> PARITY_BITS) ^ code; + return (parity_diff & ((1 << PARITY_BITS) - 1)) && !find_parity_32(code); } -#if 0 /* Correct any single-bit error -- assumes there are no double-bit errors */ unsigned correct_single_bit_error(unsigned code) { - unsigned bits[CODE_BITS]; - unsigned parity[PARITY_BITS]; - unsigned i, bp = 0; + unsigned parity_diff = generate_parity(code >> PARITY_BITS) ^ code; + unsigned bp = 0, i; - parity[EXTRA_BIT_POSITION] = 0; - - for (i = 0; i < CODE_BITS; ++i) { - bits[i] = (code & (1 << i)) ? 1 : 0; - } - for (i = 1; i < CODE_BITS; ++i) { - parity[EXTRA_BIT_POSITION] ^= bits[i]; - } - - parity[0] = bits[PARITY_BITS+0] ^ bits[PARITY_BITS+1] ^ bits[PARITY_BITS+3] ^ bits[PARITY_BITS+4] ^ bits[PARITY_BITS+6] ^ bits[PARITY_BITS+8] ^ bits[PARITY_BITS+10]; - parity[1] = bits[PARITY_BITS+0] ^ bits[PARITY_BITS+2] ^ bits[PARITY_BITS+3] ^ bits[PARITY_BITS+5] ^ bits[PARITY_BITS+6] ^ bits[PARITY_BITS+9] ^ bits[PARITY_BITS+10]; - parity[2] = bits[PARITY_BITS+1] ^ bits[PARITY_BITS+2] ^ bits[PARITY_BITS+3] ^ bits[PARITY_BITS+7] ^ bits[PARITY_BITS+8] ^ bits[PARITY_BITS+9] ^ bits[PARITY_BITS+10]; - parity[3] = bits[PARITY_BITS+4] ^ bits[PARITY_BITS+5] ^ bits[PARITY_BITS+6] ^ bits[PARITY_BITS+7] ^ bits[PARITY_BITS+8] ^ bits[PARITY_BITS+9] ^ bits[PARITY_BITS+10]; - for (i = 0; i < PARITY_BITS - 1; ++i) { - if (parity[i] != bits[PARITY_BITS - 1 - i]) { + if (parity_diff & (1 << (PARITY_BITS - 1 - i))) { bp |= (1 << i); } } @@ -125,21 +98,26 @@ unsigned correct_single_bit_error(unsigned code) if (bp != 0) { /* flip the wrong bit */ code ^= (1 << permutation_table[bp]); - parity[EXTRA_BIT_POSITION] ^= 1; } /* recompute the lower parity */ - return (code & ~1) | parity[EXTRA_BIT_POSITION]; + return (code & ~1) | find_parity_32(code & ~1); } -#endif void check_zero_bit_detection() { unsigned i; - printf("Checking zero bit detection.\n"); + printf("Checking zero bit detection."); + fflush(stdout); for (i = 0; i < NUM_DATA_WORDS; ++i) { unsigned code = make_codeword(i); + + if ((i & 0xfffff) == 0) { + printf("."); + fflush(stdout); + } + if (has_error(code)) { printf("ERROR: Failed zero-bit test 1 for %x\n", i); } @@ -147,15 +125,24 @@ void check_zero_bit_detection() printf("ERROR: Failed zero-bit test 2 for %x\n", i); } } + + printf("\n"); } void check_single_bit_detection() { unsigned i, j; - printf("Checking single bit detection and correction.\n"); + printf("Checking single bit detection and correction."); + fflush(stdout); for (i = 0; i < NUM_DATA_WORDS; ++i) { unsigned code = make_codeword(i); + + if ((i & 0xfffff) == 0) { + printf("."); + fflush(stdout); + } + for (j = 0; j < CODE_BITS; ++j) { unsigned corrupted_code = code ^ (1 << j); @@ -165,22 +152,29 @@ void check_single_bit_detection() if (has_double_error(corrupted_code)) { printf("ERROR: Failed single-bit test 2 for %x with bit %u flipped\n", i, j); } -#if 0 if (correct_single_bit_error(corrupted_code) != code) { printf("ERROR: Failed single-bit correction test for %x with bit %u flipped\n", i, j); } -#endif } } + + printf("\n"); } void check_double_bit_detection() { unsigned i, j, k; - printf("Checking double bit detection.\n"); + printf("Checking double bit detection."); + fflush(stdout); for (i = 0; i < NUM_DATA_WORDS; ++i) { unsigned code = make_codeword(i); + + if ((i & 0xfffff) == 0) { + printf("."); + fflush(stdout); + } + for (j = 0; j < CODE_BITS; ++j) { for (k = 0; k < CODE_BITS; ++k) { unsigned corrupted_code = code ^ (1 << j) ^ (1 << k); @@ -196,11 +190,12 @@ void check_double_bit_detection() } } } + + printf("\n"); } int main() { - generate_lookup(); check_zero_bit_detection(); check_single_bit_detection(); check_double_bit_detection();