From d12a68d4158ba308b3e153158a0affa80c5fa9eb Mon Sep 17 00:00:00 2001
From: antirez <antirez@gmail.com>
Date: Sun, 20 May 2012 00:49:35 +0200
Subject: [PATCH] popcount() optimization for speed.

We run the array by 32 bit words instead of processing it byte per byte.
If the code is compiled using GCC __builtin_popcount() builtin function
is used instead.
---
 src/bitop.c | 20 ++++++++++++++++++--
 1 file changed, 18 insertions(+), 2 deletions(-)

diff --git a/src/bitop.c b/src/bitop.c
index 2b26265d..053db02b 100644
--- a/src/bitop.c
+++ b/src/bitop.c
@@ -30,10 +30,26 @@ static int getBitOffsetFromArgument(redisClient *c, robj *o, size_t *offset) {
  * work with a input string length up to 512 MB. */
 long popcount(void *s, long count) {
     long bits = 0;
-    unsigned char *p = s;
+    unsigned char *p;
+    uint32_t *p4 = s;
     static const unsigned char bitsinbyte[256] = {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};
 
-    /* We can finally count bits. */
+    /* Count bits four bytes at a time */
+    while(count>=4) {
+        uint32_t aux = *p4++;
+        count -= 4;
+#ifdef __GNUC__
+        /* Unsigned int is always >= 4 bytes if compiler is GCC */
+        bits += __builtin_popcount(aux);
+#else
+        bits += bitsinbyte[aux&0xff] +
+                bitsinbyte[(aux>>8)&0xff] +
+                bitsinbyte[(aux>>16)&0xff] +
+                bitsinbyte[(aux>>24)&0xff];
+#endif
+    }
+    /* Count the remaining bytes */
+    p = (unsigned char*)p4;
     while(count--) bits += bitsinbyte[*p++];
     return bits;
 }
-- 
2.45.2