Back to home page

Redis cross reference

 
 

    


0001 /* Bit operations.
0002  *
0003  * Copyright (c) 2009-2012, Salvatore Sanfilippo <antirez at gmail dot com>
0004  * All rights reserved.
0005  *
0006  * Redistribution and use in source and binary forms, with or without
0007  * modification, are permitted provided that the following conditions are met:
0008  *
0009  *   * Redistributions of source code must retain the above copyright notice,
0010  *     this list of conditions and the following disclaimer.
0011  *   * Redistributions in binary form must reproduce the above copyright
0012  *     notice, this list of conditions and the following disclaimer in the
0013  *     documentation and/or other materials provided with the distribution.
0014  *   * Neither the name of Redis nor the names of its contributors may be used
0015  *     to endorse or promote products derived from this software without
0016  *     specific prior written permission.
0017  *
0018  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
0019  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
0020  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
0021  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
0022  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
0023  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
0024  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
0025  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
0026  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
0027  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
0028  * POSSIBILITY OF SUCH DAMAGE.
0029  */
0030 
0031 #include "redis.h"
0032 
0033 /* -----------------------------------------------------------------------------
0034  * Helpers and low level bit functions.
0035  * -------------------------------------------------------------------------- */
0036 
0037 /* This helper function used by GETBIT / SETBIT parses the bit offset argument
0038  * making sure an error is returned if it is negative or if it overflows
0039  * Redis 512 MB limit for the string value. */
0040 static int getBitOffsetFromArgument(redisClient *c, robj *o, size_t *offset) {
0041     long long loffset;
0042     char *err = "bit offset is not an integer or out of range";
0043 
0044     if (getLongLongFromObjectOrReply(c,o,&loffset,err) != REDIS_OK)
0045         return REDIS_ERR;
0046 
0047     /* Limit offset to 512MB in bytes */
0048     if ((loffset < 0) || ((unsigned long long)loffset >> 3) >= (512*1024*1024))
0049     {
0050         addReplyError(c,err);
0051         return REDIS_ERR;
0052     }
0053 
0054     *offset = (size_t)loffset;
0055     return REDIS_OK;
0056 }
0057 
0058 /* Count number of bits set in the binary array pointed by 's' and long
0059  * 'count' bytes. The implementation of this function is required to
0060  * work with a input string length up to 512 MB. */
0061 long popcount(void *s, long count) {
0062     long bits = 0;
0063     unsigned char *p;
0064     uint32_t *p4 = s;
0065     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};
0066 
0067     /* Count bits 16 bytes at a time */
0068     while(count>=16) {
0069         uint32_t aux1, aux2, aux3, aux4;
0070 
0071         aux1 = *p4++;
0072         aux2 = *p4++;
0073         aux3 = *p4++;
0074         aux4 = *p4++;
0075         count -= 16;
0076 
0077         aux1 = aux1 - ((aux1 >> 1) & 0x55555555);
0078         aux1 = (aux1 & 0x33333333) + ((aux1 >> 2) & 0x33333333);
0079         aux2 = aux2 - ((aux2 >> 1) & 0x55555555);
0080         aux2 = (aux2 & 0x33333333) + ((aux2 >> 2) & 0x33333333);
0081         aux3 = aux3 - ((aux3 >> 1) & 0x55555555);
0082         aux3 = (aux3 & 0x33333333) + ((aux3 >> 2) & 0x33333333);
0083         aux4 = aux4 - ((aux4 >> 1) & 0x55555555);
0084         aux4 = (aux4 & 0x33333333) + ((aux4 >> 2) & 0x33333333);
0085         bits += ((((aux1 + (aux1 >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24) +
0086                 ((((aux2 + (aux2 >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24) +
0087                 ((((aux3 + (aux3 >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24) +
0088                 ((((aux4 + (aux4 >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24);
0089     }
0090     /* Count the remaining bytes */
0091     p = (unsigned char*)p4;
0092     while(count--) bits += bitsinbyte[*p++];
0093     return bits;
0094 }
0095 
0096 /* -----------------------------------------------------------------------------
0097  * Bits related string commands: GETBIT, SETBIT, BITCOUNT, BITOP.
0098  * -------------------------------------------------------------------------- */
0099 
0100 #define BITOP_AND   0
0101 #define BITOP_OR    1
0102 #define BITOP_XOR   2
0103 #define BITOP_NOT   3
0104 
0105 /* SETBIT key offset bitvalue */
0106 void setbitCommand(redisClient *c) {
0107     robj *o;
0108     char *err = "bit is not an integer or out of range";
0109     size_t bitoffset;
0110     int byte, bit;
0111     int byteval, bitval;
0112     long on;
0113 
0114     if (getBitOffsetFromArgument(c,c->argv[2],&bitoffset) != REDIS_OK)
0115         return;
0116 
0117     if (getLongFromObjectOrReply(c,c->argv[3],&on,err) != REDIS_OK)
0118         return;
0119 
0120     /* Bits can only be set or cleared... */
0121     if (on & ~1) {
0122         addReplyError(c,err);
0123         return;
0124     }
0125 
0126     o = lookupKeyWrite(c->db,c->argv[1]);
0127     if (o == NULL) {
0128         o = createObject(REDIS_STRING,sdsempty());
0129         dbAdd(c->db,c->argv[1],o);
0130     } else {
0131         if (checkType(c,o,REDIS_STRING)) return;
0132 
0133         /* Create a copy when the object is shared or encoded. */
0134         if (o->refcount != 1 || o->encoding != REDIS_ENCODING_RAW) {
0135             robj *decoded = getDecodedObject(o);
0136             o = createStringObject(decoded->ptr, sdslen(decoded->ptr));
0137             decrRefCount(decoded);
0138             dbOverwrite(c->db,c->argv[1],o);
0139         }
0140     }
0141 
0142     /* Grow sds value to the right length if necessary */
0143     byte = bitoffset >> 3;
0144     o->ptr = sdsgrowzero(o->ptr,byte+1);
0145 
0146     /* Get current values */
0147     byteval = ((uint8_t*)o->ptr)[byte];
0148     bit = 7 - (bitoffset & 0x7);
0149     bitval = byteval & (1 << bit);
0150 
0151     /* Update byte with new bit value and return original value */
0152     byteval &= ~(1 << bit);
0153     byteval |= ((on & 0x1) << bit);
0154     ((uint8_t*)o->ptr)[byte] = byteval;
0155     signalModifiedKey(c->db,c->argv[1]);
0156     server.dirty++;
0157     addReply(c, bitval ? shared.cone : shared.czero);
0158 }
0159 
0160 /* GETBIT key offset */
0161 void getbitCommand(redisClient *c) {
0162     robj *o;
0163     char llbuf[32];
0164     size_t bitoffset;
0165     size_t byte, bit;
0166     size_t bitval = 0;
0167 
0168     if (getBitOffsetFromArgument(c,c->argv[2],&bitoffset) != REDIS_OK)
0169         return;
0170 
0171     if ((o = lookupKeyReadOrReply(c,c->argv[1],shared.czero)) == NULL ||
0172         checkType(c,o,REDIS_STRING)) return;
0173 
0174     byte = bitoffset >> 3;
0175     bit = 7 - (bitoffset & 0x7);
0176     if (o->encoding != REDIS_ENCODING_RAW) {
0177         if (byte < (size_t)ll2string(llbuf,sizeof(llbuf),(long)o->ptr))
0178             bitval = llbuf[byte] & (1 << bit);
0179     } else {
0180         if (byte < sdslen(o->ptr))
0181             bitval = ((uint8_t*)o->ptr)[byte] & (1 << bit);
0182     }
0183 
0184     addReply(c, bitval ? shared.cone : shared.czero);
0185 }
0186 
0187 /* BITOP op_name target_key src_key1 src_key2 src_key3 ... src_keyN */
0188 void bitopCommand(redisClient *c) {
0189     char *opname = c->argv[1]->ptr;
0190     robj *o, *targetkey = c->argv[2];
0191     long op, j, numkeys;
0192     robj **objects;      /* Array of source objects. */
0193     unsigned char **src; /* Array of source strings pointers. */
0194     long *len, maxlen = 0; /* Array of length of src strings, and max len. */
0195     long minlen = 0;    /* Min len among the input keys. */
0196     unsigned char *res = NULL; /* Resulting string. */
0197 
0198     /* Parse the operation name. */
0199     if ((opname[0] == 'a' || opname[0] == 'A') && !strcasecmp(opname,"and"))
0200         op = BITOP_AND;
0201     else if((opname[0] == 'o' || opname[0] == 'O') && !strcasecmp(opname,"or"))
0202         op = BITOP_OR;
0203     else if((opname[0] == 'x' || opname[0] == 'X') && !strcasecmp(opname,"xor"))
0204         op = BITOP_XOR;
0205     else if((opname[0] == 'n' || opname[0] == 'N') && !strcasecmp(opname,"not"))
0206         op = BITOP_NOT;
0207     else {
0208         addReply(c,shared.syntaxerr);
0209         return;
0210     }
0211 
0212     /* Sanity check: NOT accepts only a single key argument. */
0213     if (op == BITOP_NOT && c->argc != 4) {
0214         addReplyError(c,"BITOP NOT must be called with a single source key.");
0215         return;
0216     }
0217 
0218     /* Lookup keys, and store pointers to the string objects into an array. */
0219     numkeys = c->argc - 3;
0220     src = zmalloc(sizeof(unsigned char*) * numkeys);
0221     len = zmalloc(sizeof(long) * numkeys);
0222     objects = zmalloc(sizeof(robj*) * numkeys);
0223     for (j = 0; j < numkeys; j++) {
0224         o = lookupKeyRead(c->db,c->argv[j+3]);
0225         /* Handle non-existing keys as empty strings. */
0226         if (o == NULL) {
0227             objects[j] = NULL;
0228             src[j] = NULL;
0229             len[j] = 0;
0230             minlen = 0;
0231             continue;
0232         }
0233         /* Return an error if one of the keys is not a string. */
0234         if (checkType(c,o,REDIS_STRING)) {
0235             for (j = j-1; j >= 0; j--) {
0236                 if (objects[j])
0237                     decrRefCount(objects[j]);
0238             }
0239             zfree(src);
0240             zfree(len);
0241             zfree(objects);
0242             return;
0243         }
0244         objects[j] = getDecodedObject(o);
0245         src[j] = objects[j]->ptr;
0246         len[j] = sdslen(objects[j]->ptr);
0247         if (len[j] > maxlen) maxlen = len[j];
0248         if (j == 0 || len[j] < minlen) minlen = len[j];
0249     }
0250 
0251     /* Compute the bit operation, if at least one string is not empty. */
0252     if (maxlen) {
0253         res = (unsigned char*) sdsnewlen(NULL,maxlen);
0254         unsigned char output, byte;
0255         long i;
0256 
0257         /* Fast path: as far as we have data for all the input bitmaps we
0258          * can take a fast path that performs much better than the
0259          * vanilla algorithm. */
0260         j = 0;
0261         if (minlen && numkeys <= 16) {
0262             unsigned long *lp[16];
0263             unsigned long *lres = (unsigned long*) res;
0264 
0265             /* Note: sds pointer is always aligned to 8 byte boundary. */
0266             memcpy(lp,src,sizeof(unsigned long*)*numkeys);
0267             memcpy(res,src[0],minlen);
0268 
0269             /* Different branches per different operations for speed (sorry). */
0270             if (op == BITOP_AND) {
0271                 while(minlen >= sizeof(unsigned long)*4) {
0272                     for (i = 1; i < numkeys; i++) {
0273                         lres[0] &= lp[i][0];
0274                         lres[1] &= lp[i][1];
0275                         lres[2] &= lp[i][2];
0276                         lres[3] &= lp[i][3];
0277                         lp[i]+=4;
0278                     }
0279                     lres+=4;
0280                     j += sizeof(unsigned long)*4;
0281                     minlen -= sizeof(unsigned long)*4;
0282                 }
0283             } else if (op == BITOP_OR) {
0284                 while(minlen >= sizeof(unsigned long)*4) {
0285                     for (i = 1; i < numkeys; i++) {
0286                         lres[0] |= lp[i][0];
0287                         lres[1] |= lp[i][1];
0288                         lres[2] |= lp[i][2];
0289                         lres[3] |= lp[i][3];
0290                         lp[i]+=4;
0291                     }
0292                     lres+=4;
0293                     j += sizeof(unsigned long)*4;
0294                     minlen -= sizeof(unsigned long)*4;
0295                 }
0296             } else if (op == BITOP_XOR) {
0297                 while(minlen >= sizeof(unsigned long)*4) {
0298                     for (i = 1; i < numkeys; i++) {
0299                         lres[0] ^= lp[i][0];
0300                         lres[1] ^= lp[i][1];
0301                         lres[2] ^= lp[i][2];
0302                         lres[3] ^= lp[i][3];
0303                         lp[i]+=4;
0304                     }
0305                     lres+=4;
0306                     j += sizeof(unsigned long)*4;
0307                     minlen -= sizeof(unsigned long)*4;
0308                 }
0309             } else if (op == BITOP_NOT) {
0310                 while(minlen >= sizeof(unsigned long)*4) {
0311                     lres[0] = ~lres[0];
0312                     lres[1] = ~lres[1];
0313                     lres[2] = ~lres[2];
0314                     lres[3] = ~lres[3];
0315                     lres+=4;
0316                     j += sizeof(unsigned long)*4;
0317                     minlen -= sizeof(unsigned long)*4;
0318                 }
0319             }
0320         }
0321 
0322         /* j is set to the next byte to process by the previous loop. */
0323         for (; j < maxlen; j++) {
0324             output = (len[0] <= j) ? 0 : src[0][j];
0325             if (op == BITOP_NOT) output = ~output;
0326             for (i = 1; i < numkeys; i++) {
0327                 byte = (len[i] <= j) ? 0 : src[i][j];
0328                 switch(op) {
0329                 case BITOP_AND: output &= byte; break;
0330                 case BITOP_OR:  output |= byte; break;
0331                 case BITOP_XOR: output ^= byte; break;
0332                 }
0333             }
0334             res[j] = output;
0335         }
0336     }
0337     for (j = 0; j < numkeys; j++) {
0338         if (objects[j])
0339             decrRefCount(objects[j]);
0340     }
0341     zfree(src);
0342     zfree(len);
0343     zfree(objects);
0344 
0345     /* Store the computed value into the target key */
0346     if (maxlen) {
0347         o = createObject(REDIS_STRING,res);
0348         setKey(c->db,targetkey,o);
0349         decrRefCount(o);
0350     } else if (dbDelete(c->db,targetkey)) {
0351         signalModifiedKey(c->db,targetkey);
0352     }
0353     server.dirty++;
0354     addReplyLongLong(c,maxlen); /* Return the output string length in bytes. */
0355 }
0356 
0357 /* BITCOUNT key [start end] */
0358 void bitcountCommand(redisClient *c) {
0359     robj *o;
0360     long start, end, strlen;
0361     unsigned char *p;
0362     char llbuf[32];
0363 
0364     /* Lookup, check for type, and return 0 for non existing keys. */
0365     if ((o = lookupKeyReadOrReply(c,c->argv[1],shared.czero)) == NULL ||
0366         checkType(c,o,REDIS_STRING)) return;
0367 
0368     /* Set the 'p' pointer to the string, that can be just a stack allocated
0369      * array if our string was integer encoded. */
0370     if (o->encoding == REDIS_ENCODING_INT) {
0371         p = (unsigned char*) llbuf;
0372         strlen = ll2string(llbuf,sizeof(llbuf),(long)o->ptr);
0373     } else {
0374         p = (unsigned char*) o->ptr;
0375         strlen = sdslen(o->ptr);
0376     }
0377 
0378     /* Parse start/end range if any. */
0379     if (c->argc == 4) {
0380         if (getLongFromObjectOrReply(c,c->argv[2],&start,NULL) != REDIS_OK)
0381             return;
0382         if (getLongFromObjectOrReply(c,c->argv[3],&end,NULL) != REDIS_OK)
0383             return;
0384         /* Convert negative indexes */
0385         if (start < 0) start = strlen+start;
0386         if (end < 0) end = strlen+end;
0387         if (start < 0) start = 0;
0388         if (end < 0) end = 0;
0389         if (end >= strlen) end = strlen-1;
0390     } else if (c->argc == 2) {
0391         /* The whole string. */
0392         start = 0;
0393         end = strlen-1;
0394     } else {
0395         /* Syntax error. */
0396         addReply(c,shared.syntaxerr);
0397         return;
0398     }
0399 
0400     /* Precondition: end >= 0 && end < strlen, so the only condition where
0401      * zero can be returned is: start > end. */
0402     if (start > end) {
0403         addReply(c,shared.czero);
0404     } else {
0405         long bytes = end-start+1;
0406 
0407         addReplyLongLong(c,popcount(p+start,bytes));
0408     }
0409 }