src/bitop.c

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