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 argument 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 notifyKeyspaceEvent(REDIS_NOTIFY_STRING,"setbit",c->argv[1],c->db->id); 157 server.dirty++; 158 addReply(c, bitval ? shared.cone : shared.czero); 159 } 160 161 /* GETBIT key offset */ 162 void getbitCommand(redisClient *c) { 163 robj *o; 164 char llbuf[32]; 165 size_t bitoffset; 166 size_t byte, bit; 167 size_t bitval = 0; 168 169 if (getBitOffsetFromArgument(c,c->argv[2],&bitoffset) != REDIS_OK) 170 return; 171 172 if ((o = lookupKeyReadOrReply(c,c->argv[1],shared.czero)) == NULL || 173 checkType(c,o,REDIS_STRING)) return; 174 175 byte = bitoffset >> 3; 176 bit = 7 - (bitoffset & 0x7); 177 if (o->encoding != REDIS_ENCODING_RAW) { 178 if (byte < (size_t)ll2string(llbuf,sizeof(llbuf),(long)o->ptr)) 179 bitval = llbuf[byte] & (1 << bit); 180 } else { 181 if (byte < sdslen(o->ptr)) 182 bitval = ((uint8_t*)o->ptr)[byte] & (1 << bit); 183 } 184 185 addReply(c, bitval ? shared.cone : shared.czero); 186 } 187 188 /* BITOP op_name target_key src_key1 src_key2 src_key3 ... src_keyN */ 189 void bitopCommand(redisClient *c) { 190 char *opname = c->argv[1]->ptr; 191 robj *o, *targetkey = c->argv[2]; 192 long op, j, numkeys; 193 robj **objects; /* Array of source objects. */ 194 unsigned char **src; /* Array of source strings pointers. */ 195 long *len, maxlen = 0; /* Array of length of src strings, and max len. */ 196 long minlen = 0; /* Min len among the input keys. */ 197 unsigned char *res = NULL; /* Resulting string. */ 198 199 /* Parse the operation name. */ 200 if ((opname[0] == 'a' || opname[0] == 'A') && !strcasecmp(opname,"and")) 201 op = BITOP_AND; 202 else if((opname[0] == 'o' || opname[0] == 'O') && !strcasecmp(opname,"or")) 203 op = BITOP_OR; 204 else if((opname[0] == 'x' || opname[0] == 'X') && !strcasecmp(opname,"xor")) 205 op = BITOP_XOR; 206 else if((opname[0] == 'n' || opname[0] == 'N') && !strcasecmp(opname,"not")) 207 op = BITOP_NOT; 208 else { 209 addReply(c,shared.syntaxerr); 210 return; 211 } 212 213 /* Sanity check: NOT accepts only a single key argument. */ 214 if (op == BITOP_NOT && c->argc != 4) { 215 addReplyError(c,"BITOP NOT must be called with a single source key."); 216 return; 217 } 218 219 /* Lookup keys, and store pointers to the string objects into an array. */ 220 numkeys = c->argc - 3; 221 src = zmalloc(sizeof(unsigned char*) * numkeys); 222 len = zmalloc(sizeof(long) * numkeys); 223 objects = zmalloc(sizeof(robj*) * numkeys); 224 for (j = 0; j < numkeys; j++) { 225 o = lookupKeyRead(c->db,c->argv[j+3]); 226 /* Handle non-existing keys as empty strings. */ 227 if (o == NULL) { 228 objects[j] = NULL; 229 src[j] = NULL; 230 len[j] = 0; 231 minlen = 0; 232 continue; 233 } 234 /* Return an error if one of the keys is not a string. */ 235 if (checkType(c,o,REDIS_STRING)) { 236 for (j = j-1; j >= 0; j--) { 237 if (objects[j]) 238 decrRefCount(objects[j]); 239 } 240 zfree(src); 241 zfree(len); 242 zfree(objects); 243 return; 244 } 245 objects[j] = getDecodedObject(o); 246 src[j] = objects[j]->ptr; 247 len[j] = sdslen(objects[j]->ptr); 248 if (len[j] > maxlen) maxlen = len[j]; 249 if (j == 0 || len[j] < minlen) minlen = len[j]; 250 } 251 252 /* Compute the bit operation, if at least one string is not empty. */ 253 if (maxlen) { 254 res = (unsigned char*) sdsnewlen(NULL,maxlen); 255 unsigned char output, byte; 256 long i; 257 258 /* Fast path: as far as we have data for all the input bitmaps we 259 * can take a fast path that performs much better than the 260 * vanilla algorithm. */ 261 j = 0; 262 if (minlen && numkeys <= 16) { 263 unsigned long *lp[16]; 264 unsigned long *lres = (unsigned long*) res; 265 266 /* Note: sds pointer is always aligned to 8 byte boundary. */ 267 memcpy(lp,src,sizeof(unsigned long*)*numkeys); 268 memcpy(res,src[0],minlen); 269 270 /* Different branches per different operations for speed (sorry). */ 271 if (op == BITOP_AND) { 272 while(minlen >= sizeof(unsigned long)*4) { 273 for (i = 1; i < numkeys; i++) { 274 lres[0] &= lp[i][0]; 275 lres[1] &= lp[i][1]; 276 lres[2] &= lp[i][2]; 277 lres[3] &= lp[i][3]; 278 lp[i]+=4; 279 } 280 lres+=4; 281 j += sizeof(unsigned long)*4; 282 minlen -= sizeof(unsigned long)*4; 283 } 284 } else if (op == BITOP_OR) { 285 while(minlen >= sizeof(unsigned long)*4) { 286 for (i = 1; i < numkeys; i++) { 287 lres[0] |= lp[i][0]; 288 lres[1] |= lp[i][1]; 289 lres[2] |= lp[i][2]; 290 lres[3] |= lp[i][3]; 291 lp[i]+=4; 292 } 293 lres+=4; 294 j += sizeof(unsigned long)*4; 295 minlen -= sizeof(unsigned long)*4; 296 } 297 } else if (op == BITOP_XOR) { 298 while(minlen >= sizeof(unsigned long)*4) { 299 for (i = 1; i < numkeys; i++) { 300 lres[0] ^= lp[i][0]; 301 lres[1] ^= lp[i][1]; 302 lres[2] ^= lp[i][2]; 303 lres[3] ^= lp[i][3]; 304 lp[i]+=4; 305 } 306 lres+=4; 307 j += sizeof(unsigned long)*4; 308 minlen -= sizeof(unsigned long)*4; 309 } 310 } else if (op == BITOP_NOT) { 311 while(minlen >= sizeof(unsigned long)*4) { 312 lres[0] = ~lres[0]; 313 lres[1] = ~lres[1]; 314 lres[2] = ~lres[2]; 315 lres[3] = ~lres[3]; 316 lres+=4; 317 j += sizeof(unsigned long)*4; 318 minlen -= sizeof(unsigned long)*4; 319 } 320 } 321 } 322 323 /* j is set to the next byte to process by the previous loop. */ 324 for (; j < maxlen; j++) { 325 output = (len[0] <= j) ? 0 : src[0][j]; 326 if (op == BITOP_NOT) output = ~output; 327 for (i = 1; i < numkeys; i++) { 328 byte = (len[i] <= j) ? 0 : src[i][j]; 329 switch(op) { 330 case BITOP_AND: output &= byte; break; 331 case BITOP_OR: output |= byte; break; 332 case BITOP_XOR: output ^= byte; break; 333 } 334 } 335 res[j] = output; 336 } 337 } 338 for (j = 0; j < numkeys; j++) { 339 if (objects[j]) 340 decrRefCount(objects[j]); 341 } 342 zfree(src); 343 zfree(len); 344 zfree(objects); 345 346 /* Store the computed value into the target key */ 347 if (maxlen) { 348 o = createObject(REDIS_STRING,res); 349 setKey(c->db,targetkey,o); 350 notifyKeyspaceEvent(REDIS_NOTIFY_STRING,"set",targetkey,c->db->id); 351 decrRefCount(o); 352 } else if (dbDelete(c->db,targetkey)) { 353 signalModifiedKey(c->db,targetkey); 354 notifyKeyspaceEvent(REDIS_NOTIFY_GENERIC,"del",targetkey,c->db->id); 355 } 356 server.dirty++; 357 addReplyLongLong(c,maxlen); /* Return the output string length in bytes. */ 358 } 359 360 /* BITCOUNT key [start end] */ 361 void bitcountCommand(redisClient *c) { 362 robj *o; 363 long start, end, strlen; 364 unsigned char *p; 365 char llbuf[32]; 366 367 /* Lookup, check for type, and return 0 for non existing keys. */ 368 if ((o = lookupKeyReadOrReply(c,c->argv[1],shared.czero)) == NULL || 369 checkType(c,o,REDIS_STRING)) return; 370 371 /* Set the 'p' pointer to the string, that can be just a stack allocated 372 * array if our string was integer encoded. */ 373 if (o->encoding == REDIS_ENCODING_INT) { 374 p = (unsigned char*) llbuf; 375 strlen = ll2string(llbuf,sizeof(llbuf),(long)o->ptr); 376 } else { 377 p = (unsigned char*) o->ptr; 378 strlen = sdslen(o->ptr); 379 } 380 381 /* Parse start/end range if any. */ 382 if (c->argc == 4) { 383 if (getLongFromObjectOrReply(c,c->argv[2],&start,NULL) != REDIS_OK) 384 return; 385 if (getLongFromObjectOrReply(c,c->argv[3],&end,NULL) != REDIS_OK) 386 return; 387 /* Convert negative indexes */ 388 if (start < 0) start = strlen+start; 389 if (end < 0) end = strlen+end; 390 if (start < 0) start = 0; 391 if (end < 0) end = 0; 392 if (end >= strlen) end = strlen-1; 393 } else if (c->argc == 2) { 394 /* The whole string. */ 395 start = 0; 396 end = strlen-1; 397 } else { 398 /* Syntax error. */ 399 addReply(c,shared.syntaxerr); 400 return; 401 } 402 403 /* Precondition: end >= 0 && end < strlen, so the only condition where 404 * zero can be returned is: start > end. */ 405 if (start > end) { 406 addReply(c,shared.czero); 407 } else { 408 long bytes = end-start+1; 409 410 addReplyLongLong(c,popcount(p+start,bytes)); 411 } 412 } 413