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

[hamming] / hamming32.c

diff --git a/hamming32.c b/hamming32.c
index 6cbd153732d3516e9af67ca1a29e53cee0b4d6e4..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,10 +73,8 @@ 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)