BITCOUNT refactoring.

The low level popualtion counting function is now separated from the
BITCOUNT command implementation, so that the low level function can be
further optimized and eventually used in other contexts if needed.

diff --git a/src/bitop.c b/src/bitop.c
index 1eec63ab96116723a354386aadb7240bf9c7f5af..2b26265d7be4860a7b5b2b776571fb1c4b54947e 100644 (file)
--- a/src/bitop.c
+++ b/src/bitop.c
@@ -1,14 +1,9 @@
 #include "redis.h"
 
 /* -----------------------------------------------------------------------------
 #include "redis.h"
 
 /* -----------------------------------------------------------------------------

- * Bits related string commands: GETBIT, SETBIT, BITCOUNT, BITOP.
+ * Helpers and low level bit functions.

  * -------------------------------------------------------------------------- */
 
  * -------------------------------------------------------------------------- */
 

-#define BITOP_AND   0
-#define BITOP_OR    1
-#define BITOP_XOR   2
-#define BITOP_NOT   3
-

 /* This helper function used by GETBIT / SETBIT parses the bit offset arguemnt
  * making sure an error is returned if it is negative or if it overflows
  * Redis 512 MB limit for the string value. */
 /* This helper function used by GETBIT / SETBIT parses the bit offset arguemnt
  * making sure an error is returned if it is negative or if it overflows
  * Redis 512 MB limit for the string value. */


@@ -30,6 +25,28 @@ static int getBitOffsetFromArgument(redisClient *c, robj *o, size_t *offset) {
     return REDIS_OK;
 }
 
     return REDIS_OK;
 }
 

+/* Count number of bits set in the binary array pointed by 's' and long
+ * 'count' bytes. The implementation of this function is required to
+ * work with a input string length up to 512 MB. */
+long popcount(void *s, long count) {
+    long bits = 0;
+    unsigned char *p = 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. */
+    while(count--) bits += bitsinbyte[*p++];
+    return bits;
+}
+
+/* -----------------------------------------------------------------------------
+ * Bits related string commands: GETBIT, SETBIT, BITCOUNT, BITOP.
+ * -------------------------------------------------------------------------- */
+
+#define BITOP_AND   0
+#define BITOP_OR    1
+#define BITOP_XOR   2
+#define BITOP_NOT   3
+

 /* SETBIT key offset bitvalue */
 void setbitCommand(redisClient *c) {
     robj *o;
 /* SETBIT key offset bitvalue */
 void setbitCommand(redisClient *c) {
     robj *o;


@@ -201,7 +218,6 @@ void bitopCommand(redisClient *c) {
 
 /* BITCOUNT key [start end] */
 void bitcountCommand(redisClient *c) {
 
 /* BITCOUNT key [start end] */
 void bitcountCommand(redisClient *c) {

-    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};

     robj *o;
     long start, end;
     unsigned char *p;
     robj *o;
     long start, end;
     unsigned char *p;


@@ -249,11 +265,8 @@ void bitcountCommand(redisClient *c) {
     if (start > end) {
         addReply(c,shared.czero);
     } else {
     if (start > end) {
         addReply(c,shared.czero);
     } else {

-        long bits = 0, bytes = end-start+1;
+        long bytes = end-start+1;

 
 

-        /* We can finally count bits. */
-        p += start;
-        while(bytes--) bits += bitsinbyte[*p++];
-        addReplyLongLong(c,bits);
+        addReplyLongLong(c,popcount(p+start,bytes));

     }
 }
     }
 }