From 89f66cebc5a5d676d2edd676141e03df74d804b7 Mon Sep 17 00:00:00 2001 From: "Steinar H. Gunderson" Date: Thu, 2 Mar 2006 15:21:07 +0000 Subject: [PATCH] Include a fast 2x32 parity routine. --- hamming32.c | 21 ++++++++++++++++++++- 1 file changed, 20 insertions(+), 1 deletion(-) diff --git a/hamming32.c b/hamming32.c index ea66058..827841f 100644 --- a/hamming32.c +++ b/hamming32.c @@ -1,5 +1,8 @@ #include +/* 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) -- 2.39.2