X-Git-Url: https://git.sesse.net/?a=blobdiff_plain;f=hamming32.c;h=827841f9f380c1bc82d0c077889edb92cec131cf;hb=HEAD;hp=9b8576b2a04631be46e8ca29600209f3ccbedd89;hpb=30ef48a829b34154438763e3bcfe9e2a9352c48b;p=hamming

diff --git a/hamming32.c b/hamming32.c
index 9b8576b..827841f 100644
--- 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 */