Add an implementation of the (72,64) Hamming codes.

[hamming] / hamming32.c

diff --git a/hamming32.c b/hamming32.c
index 9b8576b2a04631be46e8ca29600209f3ccbedd89..827841f9f380c1bc82d0c077889edb92cec131cf 100644 (file)
--- a/hamming32.c
+++ b/hamming32.c
@@ -1,5 +1,8 @@
 #include <stdio.h>
 
+/* 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)
@@ -14,26 +17,52 @@ unsigned char permutation_table[CODE_BITS] = {
        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
 };
 
-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)
 {
-       data = (data >> 16) ^ data;
-       data = (data >> 8) ^ data;
-       data = (data >> 4) ^ data;
-       data = (data >> 2) ^ data;
-       data = (data >> 1) ^ data;
-       return (data & 1);
+       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,36 +73,14 @@ unsigned make_codeword(unsigned data)
 /* 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 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 == 0)
-               return 0;
-
-       /* both hamming and simple parity errors; this is a single-bit error */
-       if (hamming_parity != gen_hamming_parity && extra_parity == 1)
-               return 0;
-
-       /* hamming says OK, but simple parity indicates an error => simple parity error is wrong */
-       if (hamming_parity == gen_hamming_parity && extra_parity == 1)
-               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);
 }
 
 /* Correct any single-bit error -- assumes there are no double-bit errors */