From: Steinar H. Gunderson <sgunderson@bigfoot.com>
Date: Thu, 2 Mar 2006 15:05:16 +0000 (+0000)
Subject: Optimize the parity generation.
X-Git-Url: https://git.sesse.net/?p=hamming;a=commitdiff_plain;h=51647a36325cf86792dc667ca836459c066b2f5a

Optimize the parity generation.
---

diff --git a/hamming32.c b/hamming32.c
index fb53e3b..ea66058 100644
--- a/hamming32.c
+++ b/hamming32.c
@@ -14,14 +14,24 @@ 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)
 {
-	data = (data >> 16) ^ data;
-	data = (data >> 8) ^ data;
-	data = (data >> 4) ^ data;
-	data = (data >> 2) ^ data;
-	data = (data >> 1) ^ data;
-	return (data & 1);
+#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
 }
 
 unsigned generate_parity(unsigned data)