src/bitops.c

   1 /* Bit operations.
   2  *
   3  * Copyright (c) 2009-2012, Salvatore Sanfilippo <antirez at gmail dot com>
   4  * All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions are met:
   8  *
   9  *   * Redistributions of source code must retain the above copyright notice,
  10  *     this list of conditions and the following disclaimer.
  11  *   * Redistributions in binary form must reproduce the above copyright
  12  *     notice, this list of conditions and the following disclaimer in the
  13  *     documentation and/or other materials provided with the distribution.
  14  *   * Neither the name of Redis nor the names of its contributors may be used
  15  *     to endorse or promote products derived from this software without
  16  *     specific prior written permission.
  17  *
  18  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  19  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  20  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  21  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
  22  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  23  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  24  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  25  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  26  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  27  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  28  * POSSIBILITY OF SUCH DAMAGE.
  29  */
  30
  31 #include "redis.h"
  32
  33 /* -----------------------------------------------------------------------------
  34  * Helpers and low level bit functions.
  35  * -------------------------------------------------------------------------- */
  36
  37 /* This helper function used by GETBIT / SETBIT parses the bit offset arguemnt
  38  * making sure an error is returned if it is negative or if it overflows
  39  * Redis 512 MB limit for the string value. */
  40 static int getBitOffsetFromArgument(redisClient *c, robj *o, size_t *offset) {
  41     long long loffset;
  42     char *err = "bit offset is not an integer or out of range";
  43
  44     if (getLongLongFromObjectOrReply(c,o,&loffset,err) != REDIS_OK)
  45         return REDIS_ERR;
  46
  47     /* Limit offset to 512MB in bytes */
  48     if ((loffset < 0) || ((unsigned long long)loffset >> 3) >= (512*1024*1024))
  49     {
  50         addReplyError(c,err);
  51         return REDIS_ERR;
  52     }
  53
  54     *offset = (size_t)loffset;
  55     return REDIS_OK;
  56 }
  57
  58 /* Count number of bits set in the binary array pointed by 's' and long
  59  * 'count' bytes. The implementation of this function is required to
  60  * work with a input string length up to 512 MB. */
  61 long popcount(void *s, long count) {
  62     long bits = 0;
  63     unsigned char *p;
  64     uint32_t *p4 = s;
  65     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};
  66
  67     /* Count bits 16 bytes at a time */
  68     while(count>=16) {
  69         uint32_t aux1, aux2, aux3, aux4;
  70
  71         aux1 = *p4++;
  72         aux2 = *p4++;
  73         aux3 = *p4++;
  74         aux4 = *p4++;
  75         count -= 16;
  76
  77         aux1 = aux1 - ((aux1 >> 1) & 0x55555555);
  78         aux1 = (aux1 & 0x33333333) + ((aux1 >> 2) & 0x33333333);
  79         aux2 = aux2 - ((aux2 >> 1) & 0x55555555);
  80         aux2 = (aux2 & 0x33333333) + ((aux2 >> 2) & 0x33333333);
  81         aux3 = aux3 - ((aux3 >> 1) & 0x55555555);
  82         aux3 = (aux3 & 0x33333333) + ((aux3 >> 2) & 0x33333333);
  83         aux4 = aux4 - ((aux4 >> 1) & 0x55555555);
  84         aux4 = (aux4 & 0x33333333) + ((aux4 >> 2) & 0x33333333);
  85         bits += ((((aux1 + (aux1 >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24) +
  86                 ((((aux2 + (aux2 >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24) +
  87                 ((((aux3 + (aux3 >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24) +
  88                 ((((aux4 + (aux4 >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24);
  89     }
  90     /* Count the remaining bytes */
  91     p = (unsigned char*)p4;
  92     while(count--) bits += bitsinbyte[*p++];
  93     return bits;
  94 }
  95
  96 /* -----------------------------------------------------------------------------
  97  * Bits related string commands: GETBIT, SETBIT, BITCOUNT, BITOP.
  98  * -------------------------------------------------------------------------- */
  99
 100 #define BITOP_AND   0
 101 #define BITOP_OR    1
 102 #define BITOP_XOR   2
 103 #define BITOP_NOT   3
 104
 105 /* SETBIT key offset bitvalue */
 106 void setbitCommand(redisClient *c) {
 107     robj *o;
 108     char *err = "bit is not an integer or out of range";
 109     size_t bitoffset;
 110     int byte, bit;
 111     int byteval, bitval;
 112     long on;
 113
 114     if (getBitOffsetFromArgument(c,c->argv[2],&bitoffset) != REDIS_OK)
 115         return;
 116
 117     if (getLongFromObjectOrReply(c,c->argv[3],&on,err) != REDIS_OK)
 118         return;
 119
 120     /* Bits can only be set or cleared... */
 121     if (on & ~1) {
 122         addReplyError(c,err);
 123         return;
 124     }
 125
 126     o = lookupKeyWrite(c->db,c->argv[1]);
 127     if (o == NULL) {
 128         o = createObject(REDIS_STRING,sdsempty());
 129         dbAdd(c->db,c->argv[1],o);
 130     } else {
 131         if (checkType(c,o,REDIS_STRING)) return;
 132
 133         /* Create a copy when the object is shared or encoded. */
 134         if (o->refcount != 1 || o->encoding != REDIS_ENCODING_RAW) {
 135             robj *decoded = getDecodedObject(o);
 136             o = createStringObject(decoded->ptr, sdslen(decoded->ptr));
 137             decrRefCount(decoded);
 138             dbOverwrite(c->db,c->argv[1],o);
 139         }
 140     }
 141
 142     /* Grow sds value to the right length if necessary */
 143     byte = bitoffset >> 3;
 144     o->ptr = sdsgrowzero(o->ptr,byte+1);
 145
 146     /* Get current values */
 147     byteval = ((uint8_t*)o->ptr)[byte];
 148     bit = 7 - (bitoffset & 0x7);
 149     bitval = byteval & (1 << bit);
 150
 151     /* Update byte with new bit value and return original value */
 152     byteval &= ~(1 << bit);
 153     byteval |= ((on & 0x1) << bit);
 154     ((uint8_t*)o->ptr)[byte] = byteval;
 155     signalModifiedKey(c->db,c->argv[1]);
 156     server.dirty++;
 157     addReply(c, bitval ? shared.cone : shared.czero);
 158 }
 159
 160 /* GETBIT key offset */
 161 void getbitCommand(redisClient *c) {
 162     robj *o;
 163     char llbuf[32];
 164     size_t bitoffset;
 165     size_t byte, bit;
 166     size_t bitval = 0;
 167
 168     if (getBitOffsetFromArgument(c,c->argv[2],&bitoffset) != REDIS_OK)
 169         return;
 170
 171     if ((o = lookupKeyReadOrReply(c,c->argv[1],shared.czero)) == NULL ||
 172         checkType(c,o,REDIS_STRING)) return;
 173
 174     byte = bitoffset >> 3;
 175     bit = 7 - (bitoffset & 0x7);
 176     if (o->encoding != REDIS_ENCODING_RAW) {
 177         if (byte < (size_t)ll2string(llbuf,sizeof(llbuf),(long)o->ptr))
 178             bitval = llbuf[byte] & (1 << bit);
 179     } else {
 180         if (byte < sdslen(o->ptr))
 181             bitval = ((uint8_t*)o->ptr)[byte] & (1 << bit);
 182     }
 183
 184     addReply(c, bitval ? shared.cone : shared.czero);
 185 }
 186
 187 /* BITOP op_name target_key src_key1 src_key2 src_key3 ... src_keyN */
 188 void bitopCommand(redisClient *c) {
 189     char *opname = c->argv[1]->ptr;
 190     robj *o, *targetkey = c->argv[2];
 191     long op, j, numkeys;
 192     robj **objects;      /* Array of soruce objects. */
 193     unsigned char **src; /* Array of source strings pointers. */
 194     long *len, maxlen = 0; /* Array of length of src strings, and max len. */
 195     long minlen = 0;    /* Min len among the input keys. */
 196     unsigned char *res = NULL; /* Resulting string. */
 197
 198     /* Parse the operation name. */
 199     if ((opname[0] == 'a' || opname[0] == 'A') && !strcasecmp(opname,"and"))
 200         op = BITOP_AND;
 201     else if((opname[0] == 'o' || opname[0] == 'O') && !strcasecmp(opname,"or"))
 202         op = BITOP_OR;
 203     else if((opname[0] == 'x' || opname[0] == 'X') && !strcasecmp(opname,"xor"))
 204         op = BITOP_XOR;
 205     else if((opname[0] == 'n' || opname[0] == 'N') && !strcasecmp(opname,"not"))
 206         op = BITOP_NOT;
 207     else {
 208         addReply(c,shared.syntaxerr);
 209         return;
 210     }
 211
 212     /* Sanity check: NOT accepts only a single key argument. */
 213     if (op == BITOP_NOT && c->argc != 4) {
 214         addReplyError(c,"BITOP NOT must be called with a single source key.");
 215         return;
 216     }
 217
 218     /* Lookup keys, and store pointers to the string objects into an array. */
 219     numkeys = c->argc - 3;
 220     src = zmalloc(sizeof(unsigned char*) * numkeys);
 221     len = zmalloc(sizeof(long) * numkeys);
 222     objects = zmalloc(sizeof(robj*) * numkeys);
 223     for (j = 0; j < numkeys; j++) {
 224         o = lookupKeyRead(c->db,c->argv[j+3]);
 225         /* Handle non-existing keys as empty strings. */
 226         if (o == NULL) {
 227             objects[j] = NULL;
 228             src[j] = NULL;
 229             len[j] = 0;
 230             minlen = 0;
 231             continue;
 232         }
 233         /* Return an error if one of the keys is not a string. */
 234         if (checkType(c,o,REDIS_STRING)) {
 235             for (j = j-1; j >= 0; j--) {
 236                 if (objects[j])
 237                     decrRefCount(objects[j]);
 238             }
 239             zfree(src);
 240             zfree(len);
 241             zfree(objects);
 242             return;
 243         }
 244         objects[j] = getDecodedObject(o);
 245         src[j] = objects[j]->ptr;
 246         len[j] = sdslen(objects[j]->ptr);
 247         if (len[j] > maxlen) maxlen = len[j];
 248         if (j == 0 || len[j] < minlen) minlen = len[j];
 249     }
 250
 251     /* Compute the bit operation, if at least one string is not empty. */
 252     if (maxlen) {
 253         res = (unsigned char*) sdsnewlen(NULL,maxlen);
 254         unsigned char output, byte;
 255         long i;
 256
 257         /* Fast path: as far as we have data for all the input bitmaps we
 258          * can take a fast path that performs much better than the
 259          * vanilla algorithm. */
 260         j = 0;
 261         if (minlen && numkeys <= 16) {
 262             unsigned long *lp[16];
 263             unsigned long *lres = (unsigned long*) res;
 264
 265             /* Note: sds pointer is always aligned to 8 byte boundary. */
 266             memcpy(lp,src,sizeof(unsigned long*)*numkeys);
 267             memcpy(res,src[0],minlen);
 268
 269             /* Different branches per different operations for speed (sorry). */
 270             if (op == BITOP_AND) {
 271                 while(minlen >= sizeof(unsigned long)*4) {
 272                     for (i = 1; i < numkeys; i++) {
 273                         lres[0] &= lp[i][0];
 274                         lres[1] &= lp[i][1];
 275                         lres[2] &= lp[i][2];
 276                         lres[3] &= lp[i][3];
 277                         lp[i]+=4;
 278                     }
 279                     lres+=4;
 280                     j += sizeof(unsigned long)*4;
 281                     minlen -= sizeof(unsigned long)*4;
 282                 }
 283             } else if (op == BITOP_OR) {
 284                 while(minlen >= sizeof(unsigned long)*4) {
 285                     for (i = 1; i < numkeys; i++) {
 286                         lres[0] |= lp[i][0];
 287                         lres[1] |= lp[i][1];
 288                         lres[2] |= lp[i][2];
 289                         lres[3] |= lp[i][3];
 290                         lp[i]+=4;
 291                     }
 292                     lres+=4;
 293                     j += sizeof(unsigned long)*4;
 294                     minlen -= sizeof(unsigned long)*4;
 295                 }
 296             } else if (op == BITOP_XOR) {
 297                 while(minlen >= sizeof(unsigned long)*4) {
 298                     for (i = 1; i < numkeys; i++) {
 299                         lres[0] ^= lp[i][0];
 300                         lres[1] ^= lp[i][1];
 301                         lres[2] ^= lp[i][2];
 302                         lres[3] ^= lp[i][3];
 303                         lp[i]+=4;
 304                     }
 305                     lres+=4;
 306                     j += sizeof(unsigned long)*4;
 307                     minlen -= sizeof(unsigned long)*4;
 308                 }
 309             } else if (op == BITOP_NOT) {
 310                 while(minlen >= sizeof(unsigned long)*4) {
 311                     lres[0] = ~lres[0];
 312                     lres[1] = ~lres[1];
 313                     lres[2] = ~lres[2];
 314                     lres[3] = ~lres[3];
 315                     lres+=4;
 316                     j += sizeof(unsigned long)*4;
 317                     minlen -= sizeof(unsigned long)*4;
 318                 }
 319             }
 320         }
 321
 322         /* j is set to the next byte to process by the previous loop. */
 323         for (; j < maxlen; j++) {
 324             output = (len[0] <= j) ? 0 : src[0][j];
 325             if (op == BITOP_NOT) output = ~output;
 326             for (i = 1; i < numkeys; i++) {
 327                 byte = (len[i] <= j) ? 0 : src[i][j];
 328                 switch(op) {
 329                 case BITOP_AND: output &= byte; break;
 330                 case BITOP_OR:  output |= byte; break;
 331                 case BITOP_XOR: output ^= byte; break;
 332                 }
 333             }
 334             res[j] = output;
 335         }
 336     }
 337     for (j = 0; j < numkeys; j++) {
 338         if (objects[j])
 339             decrRefCount(objects[j]);
 340     }
 341     zfree(src);
 342     zfree(len);
 343     zfree(objects);
 344
 345     /* Store the computed value into the target key */
 346     if (maxlen) {
 347         o = createObject(REDIS_STRING,res);
 348         setKey(c->db,targetkey,o);
 349         decrRefCount(o);
 350     } else if (dbDelete(c->db,targetkey)) {
 351         signalModifiedKey(c->db,targetkey);
 352     }
 353     server.dirty++;
 354     addReplyLongLong(c,maxlen); /* Return the output string length in bytes. */
 355 }
 356
 357 /* BITCOUNT key [start end] */
 358 void bitcountCommand(redisClient *c) {
 359     robj *o;
 360     long start, end, strlen;
 361     unsigned char *p;
 362     char llbuf[32];
 363
 364     /* Lookup, check for type, and return 0 for non existing keys. */
 365     if ((o = lookupKeyReadOrReply(c,c->argv[1],shared.czero)) == NULL ||
 366         checkType(c,o,REDIS_STRING)) return;
 367
 368     /* Set the 'p' pointer to the string, that can be just a stack allocated
 369      * array if our string was integer encoded. */
 370     if (o->encoding == REDIS_ENCODING_INT) {
 371         p = (unsigned char*) llbuf;
 372         strlen = ll2string(llbuf,sizeof(llbuf),(long)o->ptr);
 373     } else {
 374         p = (unsigned char*) o->ptr;
 375         strlen = sdslen(o->ptr);
 376     }
 377
 378     /* Parse start/end range if any. */
 379     if (c->argc == 4) {
 380         if (getLongFromObjectOrReply(c,c->argv[2],&start,NULL) != REDIS_OK)
 381             return;
 382         if (getLongFromObjectOrReply(c,c->argv[3],&end,NULL) != REDIS_OK)
 383             return;
 384         /* Convert negative indexes */
 385         if (start < 0) start = strlen+start;
 386         if (end < 0) end = strlen+end;
 387         if (start < 0) start = 0;
 388         if (end < 0) end = 0;
 389         if (end >= strlen) end = strlen-1;
 390     } else if (c->argc == 2) {
 391         /* The whole string. */
 392         start = 0;
 393         end = strlen-1;
 394     } else {
 395         /* Syntax error. */
 396         addReply(c,shared.syntaxerr);
 397         return;
 398     }
 399
 400     /* Precondition: end >= 0 && end < strlen, so the only condition where
 401      * zero can be returned is: start > end. */
 402     if (start > end) {
 403         addReply(c,shared.czero);
 404     } else {
 405         long bytes = end-start+1;
 406
 407         addReplyLongLong(c,popcount(p+start,bytes));
 408     }
 409 }