src/bitops.c

   1 #include "redis.h"
   2
   3 /* -----------------------------------------------------------------------------
   4  * Helpers and low level bit functions.
   5  * -------------------------------------------------------------------------- */
   6
   7 /* This helper function used by GETBIT / SETBIT parses the bit offset arguemnt
   8  * making sure an error is returned if it is negative or if it overflows
   9  * Redis 512 MB limit for the string value. */
  10 static int getBitOffsetFromArgument(redisClient *c, robj *o, size_t *offset) {
  11     long long loffset;
  12     char *err = "bit offset is not an integer or out of range";
  13
  14     if (getLongLongFromObjectOrReply(c,o,&loffset,err) != REDIS_OK)
  15         return REDIS_ERR;
  16
  17     /* Limit offset to 512MB in bytes */
  18     if ((loffset < 0) || ((unsigned long long)loffset >> 3) >= (512*1024*1024))
  19     {
  20         addReplyError(c,err);
  21         return REDIS_ERR;
  22     }
  23
  24     *offset = (size_t)loffset;
  25     return REDIS_OK;
  26 }
  27
  28 /* Count number of bits set in the binary array pointed by 's' and long
  29  * 'count' bytes. The implementation of this function is required to
  30  * work with a input string length up to 512 MB. */
  31 long popcount(void *s, long count) {
  32     long bits = 0;
  33     unsigned char *p;
  34     uint32_t *p4 = s;
  35     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};
  36
  37     /* Count bits four bytes at a time */
  38     while(count>=4) {
  39         uint32_t aux = *p4++;
  40         count -= 4;
  41 #ifdef __GNUC__
  42         /* Unsigned int is always >= 4 bytes if compiler is GCC */
  43         bits += __builtin_popcount(aux);
  44 #else
  45         bits += bitsinbyte[aux&0xff] +
  46                 bitsinbyte[(aux>>8)&0xff] +
  47                 bitsinbyte[(aux>>16)&0xff] +
  48                 bitsinbyte[(aux>>24)&0xff];
  49 #endif
  50     }
  51     /* Count the remaining bytes */
  52     p = (unsigned char*)p4;
  53     while(count--) bits += bitsinbyte[*p++];
  54     return bits;
  55 }
  56
  57 /* -----------------------------------------------------------------------------
  58  * Bits related string commands: GETBIT, SETBIT, BITCOUNT, BITOP.
  59  * -------------------------------------------------------------------------- */
  60
  61 #define BITOP_AND   0
  62 #define BITOP_OR    1
  63 #define BITOP_XOR   2
  64 #define BITOP_NOT   3
  65
  66 /* SETBIT key offset bitvalue */
  67 void setbitCommand(redisClient *c) {
  68     robj *o;
  69     char *err = "bit is not an integer or out of range";
  70     size_t bitoffset;
  71     int byte, bit;
  72     int byteval, bitval;
  73     long on;
  74
  75     if (getBitOffsetFromArgument(c,c->argv[2],&bitoffset) != REDIS_OK)
  76         return;
  77
  78     if (getLongFromObjectOrReply(c,c->argv[3],&on,err) != REDIS_OK)
  79         return;
  80
  81     /* Bits can only be set or cleared... */
  82     if (on & ~1) {
  83         addReplyError(c,err);
  84         return;
  85     }
  86
  87     o = lookupKeyWrite(c->db,c->argv[1]);
  88     if (o == NULL) {
  89         o = createObject(REDIS_STRING,sdsempty());
  90         dbAdd(c->db,c->argv[1],o);
  91     } else {
  92         if (checkType(c,o,REDIS_STRING)) return;
  93
  94         /* Create a copy when the object is shared or encoded. */
  95         if (o->refcount != 1 || o->encoding != REDIS_ENCODING_RAW) {
  96             robj *decoded = getDecodedObject(o);
  97             o = createStringObject(decoded->ptr, sdslen(decoded->ptr));
  98             decrRefCount(decoded);
  99             dbOverwrite(c->db,c->argv[1],o);
 100         }
 101     }
 102
 103     /* Grow sds value to the right length if necessary */
 104     byte = bitoffset >> 3;
 105     o->ptr = sdsgrowzero(o->ptr,byte+1);
 106
 107     /* Get current values */
 108     byteval = ((char*)o->ptr)[byte];
 109     bit = 7 - (bitoffset & 0x7);
 110     bitval = byteval & (1 << bit);
 111
 112     /* Update byte with new bit value and return original value */
 113     byteval &= ~(1 << bit);
 114     byteval |= ((on & 0x1) << bit);
 115     ((char*)o->ptr)[byte] = byteval;
 116     signalModifiedKey(c->db,c->argv[1]);
 117     server.dirty++;
 118     addReply(c, bitval ? shared.cone : shared.czero);
 119 }
 120
 121 /* GETBIT key offset */
 122 void getbitCommand(redisClient *c) {
 123     robj *o;
 124     char llbuf[32];
 125     size_t bitoffset;
 126     size_t byte, bit;
 127     size_t bitval = 0;
 128
 129     if (getBitOffsetFromArgument(c,c->argv[2],&bitoffset) != REDIS_OK)
 130         return;
 131
 132     if ((o = lookupKeyReadOrReply(c,c->argv[1],shared.czero)) == NULL ||
 133         checkType(c,o,REDIS_STRING)) return;
 134
 135     byte = bitoffset >> 3;
 136     bit = 7 - (bitoffset & 0x7);
 137     if (o->encoding != REDIS_ENCODING_RAW) {
 138         if (byte < (size_t)ll2string(llbuf,sizeof(llbuf),(long)o->ptr))
 139             bitval = llbuf[byte] & (1 << bit);
 140     } else {
 141         if (byte < sdslen(o->ptr))
 142             bitval = ((char*)o->ptr)[byte] & (1 << bit);
 143     }
 144
 145     addReply(c, bitval ? shared.cone : shared.czero);
 146 }
 147
 148 /* BITOP op_name target_key src_key1 src_key2 src_key3 ... src_keyN */
 149 void bitopCommand(redisClient *c) {
 150     char *opname = c->argv[1]->ptr;
 151     robj *o, *targetkey = c->argv[2];
 152     long op, j, numkeys;
 153     unsigned char **src; /* Array of source strings pointers. */
 154     long *len, maxlen = 0; /* Array of length of src strings, and max len. */
 155     unsigned char *res = NULL; /* Resulting string. */
 156
 157     /* Parse the operation name. */
 158     if ((opname[0] == 'a' || opname[0] == 'A') && !strcasecmp(opname,"and"))
 159         op = BITOP_AND;
 160     else if((opname[0] == 'o' || opname[0] == 'O') && !strcasecmp(opname,"or"))
 161         op = BITOP_OR;
 162     else if((opname[0] == 'x' || opname[0] == 'X') && !strcasecmp(opname,"xor"))
 163         op = BITOP_XOR;
 164     else if((opname[0] == 'n' || opname[0] == 'N') && !strcasecmp(opname,"not"))
 165         op = BITOP_NOT;
 166     else {
 167         addReply(c,shared.syntaxerr);
 168         return;
 169     }
 170
 171     /* Sanity check: NOT accepts only a single key argument. */
 172     if (op == BITOP_NOT && c->argc != 4) {
 173         addReplyError(c,"BITOP NOT must be called with a single source key.");
 174         return;
 175     }
 176
 177     /* Lookup keys, and store pointers to the string objects into an array. */
 178     numkeys = c->argc - 3;
 179     src = zmalloc(sizeof(unsigned char*) * numkeys);
 180     len = zmalloc(sizeof(long) * numkeys);
 181     for (j = 0; j < numkeys; j++) {
 182         o = lookupKeyRead(c->db,c->argv[j+3]);
 183         /* Handle non-existing keys as empty strings. */
 184         if (o == NULL) {
 185             src[j] = NULL;
 186             len[j] = 0;
 187             continue;
 188         }
 189         /* Return an error if one of the keys is not a string. */
 190         if (checkType(c,o,REDIS_STRING)) {
 191             zfree(src);
 192             zfree(len);
 193             return;
 194         }
 195         src[j] = o->ptr;
 196         len[j] = sdslen(o->ptr);
 197         if (len[j] > maxlen) maxlen = len[j];
 198     }
 199
 200     /* Compute the bit operation, if at least one string is not empty. */
 201     if (maxlen) {
 202         res = (unsigned char*) sdsnewlen(NULL,maxlen);
 203         unsigned char output, byte;
 204         long i;
 205
 206         for (j = 0; j < maxlen; j++) {
 207             output = (len[0] <= j) ? 0 : src[0][j];
 208             if (op == BITOP_NOT) output = ~output;
 209             for (i = 1; i < numkeys; i++) {
 210                 byte = (len[i] <= j) ? 0 : src[i][j];
 211                 switch(op) {
 212                 case BITOP_AND: output &= byte; break;
 213                 case BITOP_OR:  output |= byte; break;
 214                 case BITOP_XOR: output ^= byte; break;
 215                 }
 216             }
 217             res[j] = output;
 218         }
 219     }
 220     zfree(src);
 221     zfree(len);
 222
 223     /* Store the computed value into the target key */
 224     if (maxlen) {
 225         o = createObject(REDIS_STRING,res);
 226         setKey(c->db,targetkey,o);
 227         decrRefCount(o);
 228     } else if (dbDelete(c->db,targetkey)) {
 229         signalModifiedKey(c->db,targetkey);
 230     }
 231     server.dirty++;
 232     addReplyLongLong(c,maxlen); /* Return the output string length in bytes. */
 233 }
 234
 235 /* BITCOUNT key [start end] */
 236 void bitcountCommand(redisClient *c) {
 237     robj *o;
 238     long start, end;
 239     unsigned char *p;
 240     char llbuf[32];
 241     size_t strlen;
 242
 243     /* Lookup, check for type, and return 0 for non existing keys. */
 244     if ((o = lookupKeyReadOrReply(c,c->argv[1],shared.czero)) == NULL ||
 245         checkType(c,o,REDIS_STRING)) return;
 246
 247     /* Set the 'p' pointer to the string, that can be just a stack allocated
 248      * array if our string was integer encoded. */
 249     if (o->encoding == REDIS_ENCODING_INT) {
 250         p = (unsigned char*) llbuf;
 251         strlen = ll2string(llbuf,sizeof(llbuf),(long)o->ptr);
 252     } else {
 253         p = (unsigned char*) o->ptr;
 254         strlen = sdslen(o->ptr);
 255     }
 256
 257     /* Parse start/end range if any. */
 258     if (c->argc == 4) {
 259         if (getLongFromObjectOrReply(c,c->argv[2],&start,NULL) != REDIS_OK)
 260             return;
 261         if (getLongFromObjectOrReply(c,c->argv[3],&end,NULL) != REDIS_OK)
 262             return;
 263         /* Convert negative indexes */
 264         if (start < 0) start = strlen+start;
 265         if (end < 0) end = strlen+end;
 266         if (start < 0) start = 0;
 267         if (end < 0) end = 0;
 268         if ((unsigned)end >= strlen) end = strlen-1;
 269     } else if (c->argc == 2) {
 270         /* The whole string. */
 271         start = 0;
 272         end = strlen-1;
 273     } else {
 274         /* Syntax error. */
 275         addReply(c,shared.syntaxerr);
 276         return;
 277     }
 278
 279     /* Precondition: end >= 0 && end < strlen, so the only condition where
 280      * zero can be returned is: start > end. */
 281     if (start > end) {
 282         addReply(c,shared.czero);
 283     } else {
 284         long bytes = end-start+1;
 285
 286         addReplyLongLong(c,popcount(p+start,bytes));
 287     }
 288 }