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

[hamming] / hamming32.c

diff --git a/hamming32.c b/hamming32.c
index ea6605850680708b124120ddcf05bc4a57c248ff..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)
@@ -34,16 +37,32 @@ unsigned find_parity_32(unsigned x)
 #endif
 }
 
+/* courtesy of neon/nocturnal :-) */
+unsigned find_parity_32x2(unsigned a, unsigned b)
+{
+       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)