Add table version of popcount and popcount8

    * Adds an alternative version of popcount using a static table for
    8 bits patterns. Disabled by default.

git-svn-id: svn+ssh://idea.nguyen.vg/svn/sxsi/trunk/bp@1217 3cdefd35-fc62-479d-8e8d-bae585ffb9ca

diff --git a/Makefile b/Makefile
index 542525a..23cd4f6 100644 (file)
--- a/Makefile
+++ b/Makefile
@@ -3,6 +3,7 @@ POPCOUNT=$(shell grep -q popcnt /proc/cpuinfo && echo 1)
 ifeq ($(POPCOUNT), 1)
        POPCOUNT_FLAG=-DHAS_NATIVE_POPCOUNT
 else
+       #POPCOUNT_FLAG=-DHAS_POPCOUNT_TABLE
        POPCOUNT_FLAG=
 endif
 

diff --git a/bp-utils.c b/bp-utils.c
index b1d68ce..0fc7a42 100644 (file)
--- a/bp-utils.c
+++ b/bp-utils.c
@@ -1,6 +1,27 @@
 #include <stdio.h>
 #include "bp-utils.h"
 
+unsigned char popCount[] = {
+  0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,
+  1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
+  1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
+  2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
+  1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
+  2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
+  2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
+  3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
+  1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
+  2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
+  2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
+  3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
+  2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
+  3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
+  3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
+  4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8
+};
+
+
+
 static size_t allocated = 0;
 
 void * bp_malloc(size_t n)

diff --git a/bp-utils.h b/bp-utils.h
index b548688..6ead4fa 100644 (file)
--- a/bp-utils.h
+++ b/bp-utils.h
@@ -36,7 +36,25 @@ static inline unsigned int popcount8(unsigned int n) {
 }
 
 #else
+#ifdef HAS_POPCOUNT_TABLE
+
+extern unsigned char popCount[256];
 
+static unsigned int popcount8(unsigned int x)
+{
+  return (unsigned int) popCount[x & 0xff];
+}
+
+static unsigned int popcount(unsigned int x)
+{
+  return popcount8(x) +
+    popcount8((x >> 8)) +
+    popcount8((x >> 16)) +
+    popcount8((x >> 24));
+}
+
+
+#else
 static unsigned int popcount8(unsigned int x)
 {
   unsigned int r;
@@ -58,6 +76,7 @@ static inline unsigned int popcount(unsigned int x)
 }
 
 #endif
+#endif
 
 
 void * bp_malloc(size_t);