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 "server.h" 32 33 /* ----------------------------------------------------------------------------- 34 * Helpers and low level bit functions. 35 * -------------------------------------------------------------------------- */ 36 37 /* Count number of bits set in the binary array pointed by 's' and long 38 * 'count' bytes. The implementation of this function is required to 39 * work with a input string length up to 512 MB. */ 40 size_t redisPopcount(void *s, long count) { 41 size_t bits = 0; 42 unsigned char *p = s; 43 uint32_t *p4; 44 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}; 45 46 /* Count initial bytes not aligned to 32 bit. */ 47 while((unsigned long)p & 3 && count) { 48 bits += bitsinbyte[*p++]; 49 count--; 50 } 51 52 /* Count bits 28 bytes at a time */ 53 p4 = (uint32_t*)p; 54 while(count>=28) { 55 uint32_t aux1, aux2, aux3, aux4, aux5, aux6, aux7; 56 57 aux1 = *p4++; 58 aux2 = *p4++; 59 aux3 = *p4++; 60 aux4 = *p4++; 61 aux5 = *p4++; 62 aux6 = *p4++; 63 aux7 = *p4++; 64 count -= 28; 65 66 aux1 = aux1 - ((aux1 >> 1) & 0x55555555); 67 aux1 = (aux1 & 0x33333333) + ((aux1 >> 2) & 0x33333333); 68 aux2 = aux2 - ((aux2 >> 1) & 0x55555555); 69 aux2 = (aux2 & 0x33333333) + ((aux2 >> 2) & 0x33333333); 70 aux3 = aux3 - ((aux3 >> 1) & 0x55555555); 71 aux3 = (aux3 & 0x33333333) + ((aux3 >> 2) & 0x33333333); 72 aux4 = aux4 - ((aux4 >> 1) & 0x55555555); 73 aux4 = (aux4 & 0x33333333) + ((aux4 >> 2) & 0x33333333); 74 aux5 = aux5 - ((aux5 >> 1) & 0x55555555); 75 aux5 = (aux5 & 0x33333333) + ((aux5 >> 2) & 0x33333333); 76 aux6 = aux6 - ((aux6 >> 1) & 0x55555555); 77 aux6 = (aux6 & 0x33333333) + ((aux6 >> 2) & 0x33333333); 78 aux7 = aux7 - ((aux7 >> 1) & 0x55555555); 79 aux7 = (aux7 & 0x33333333) + ((aux7 >> 2) & 0x33333333); 80 bits += ((((aux1 + (aux1 >> 4)) & 0x0F0F0F0F) + 81 ((aux2 + (aux2 >> 4)) & 0x0F0F0F0F) + 82 ((aux3 + (aux3 >> 4)) & 0x0F0F0F0F) + 83 ((aux4 + (aux4 >> 4)) & 0x0F0F0F0F) + 84 ((aux5 + (aux5 >> 4)) & 0x0F0F0F0F) + 85 ((aux6 + (aux6 >> 4)) & 0x0F0F0F0F) + 86 ((aux7 + (aux7 >> 4)) & 0x0F0F0F0F))* 0x01010101) >> 24; 87 } 88 /* Count the remaining bytes. */ 89 p = (unsigned char*)p4; 90 while(count--) bits += bitsinbyte[*p++]; 91 return bits; 92 } 93 94 /* Return the position of the first bit set to one (if 'bit' is 1) or 95 * zero (if 'bit' is 0) in the bitmap starting at 's' and long 'count' bytes. 96 * 97 * The function is guaranteed to return a value >= 0 if 'bit' is 0 since if 98 * no zero bit is found, it returns count*8 assuming the string is zero 99 * padded on the right. However if 'bit' is 1 it is possible that there is 100 * not a single set bit in the bitmap. In this special case -1 is returned. */ 101 long redisBitpos(void *s, unsigned long count, int bit) { 102 unsigned long *l; 103 unsigned char *c; 104 unsigned long skipval, word = 0, one; 105 long pos = 0; /* Position of bit, to return to the caller. */ 106 unsigned long j; 107 108 /* Process whole words first, seeking for first word that is not 109 * all ones or all zeros respectively if we are lookig for zeros 110 * or ones. This is much faster with large strings having contiguous 111 * blocks of 1 or 0 bits compared to the vanilla bit per bit processing. 112 * 113 * Note that if we start from an address that is not aligned 114 * to sizeof(unsigned long) we consume it byte by byte until it is 115 * aligned. */ 116 117 /* Skip initial bits not aligned to sizeof(unsigned long) byte by byte. */ 118 skipval = bit ? 0 : UCHAR_MAX; 119 c = (unsigned char*) s; 120 while((unsigned long)c & (sizeof(*l)-1) && count) { 121 if (*c != skipval) break; 122 c++; 123 count--; 124 pos += 8; 125 } 126 127 /* Skip bits with full word step. */ 128 skipval = bit ? 0 : ULONG_MAX; 129 l = (unsigned long*) c; 130 while (count >= sizeof(*l)) { 131 if (*l != skipval) break; 132 l++; 133 count -= sizeof(*l); 134 pos += sizeof(*l)*8; 135 } 136 137 /* Load bytes into "word" considering the first byte as the most significant 138 * (we basically consider it as written in big endian, since we consider the 139 * string as a set of bits from left to right, with the first bit at position 140 * zero. 141 * 142 * Note that the loading is designed to work even when the bytes left 143 * (count) are less than a full word. We pad it with zero on the right. */ 144 c = (unsigned char*)l; 145 for (j = 0; j < sizeof(*l); j++) { 146 word <<= 8; 147 if (count) { 148 word |= *c; 149 c++; 150 count--; 151 } 152 } 153 154 /* Special case: 155 * If bits in the string are all zero and we are looking for one, 156 * return -1 to signal that there is not a single "1" in the whole 157 * string. This can't happen when we are looking for "0" as we assume 158 * that the right of the string is zero padded. */ 159 if (bit == 1 && word == 0) return -1; 160 161 /* Last word left, scan bit by bit. The first thing we need is to 162 * have a single "1" set in the most significant position in an 163 * unsigned long. We don't know the size of the long so we use a 164 * simple trick. */ 165 one = ULONG_MAX; /* All bits set to 1.*/ 166 one >>= 1; /* All bits set to 1 but the MSB. */ 167 one = ~one; /* All bits set to 0 but the MSB. */ 168 169 while(one) { 170 if (((one & word) != 0) == bit) return pos; 171 pos++; 172 one >>= 1; 173 } 174 175 /* If we reached this point, there is a bug in the algorithm, since 176 * the case of no match is handled as a special case before. */ 177 serverPanic("End of redisBitpos() reached."); 178 return 0; /* Just to avoid warnings. */ 179 } 180 181 /* The following set.*Bitfield and get.*Bitfield functions implement setting 182 * and getting arbitrary size (up to 64 bits) signed and unsigned integers 183 * at arbitrary positions into a bitmap. 184 * 185 * The representation considers the bitmap as having the bit number 0 to be 186 * the most significant bit of the first byte, and so forth, so for example 187 * setting a 5 bits unsigned integer to value 23 at offset 7 into a bitmap 188 * previously set to all zeroes, will produce the following representation: 189 * 190 * +--------+--------+ 191 * |00000001|01110000| 192 * +--------+--------+ 193 * 194 * When offsets and integer sizes are aligned to bytes boundaries, this is the 195 * same as big endian, however when such alignment does not exist, its important 196 * to also understand how the bits inside a byte are ordered. 197 * 198 * Note that this format follows the same convention as SETBIT and related 199 * commands. 200 */ 201 202 void setUnsignedBitfield(unsigned char *p, uint64_t offset, uint64_t bits, uint64_t value) { 203 uint64_t byte, bit, byteval, bitval, j; 204 205 for (j = 0; j < bits; j++) { 206 bitval = (value & ((uint64_t)1<<(bits-1-j))) != 0; 207 byte = offset >> 3; 208 bit = 7 - (offset & 0x7); 209 byteval = p[byte]; 210 byteval &= ~(1 << bit); 211 byteval |= bitval << bit; 212 p[byte] = byteval & 0xff; 213 offset++; 214 } 215 } 216 217 void setSignedBitfield(unsigned char *p, uint64_t offset, uint64_t bits, int64_t value) { 218 uint64_t uv; 219 220 if (value >= 0) 221 uv = value; 222 else 223 uv = UINT64_MAX + value + 1; 224 setUnsignedBitfield(p,offset,bits,uv); 225 } 226 227 uint64_t getUnsignedBitfield(unsigned char *p, uint64_t offset, uint64_t bits) { 228 uint64_t byte, bit, byteval, bitval, j, value = 0; 229 230 for (j = 0; j < bits; j++) { 231 byte = offset >> 3; 232 bit = 7 - (offset & 0x7); 233 byteval = p[byte]; 234 bitval = (byteval >> bit) & 1; 235 value = (value<<1) | bitval; 236 offset++; 237 } 238 return value; 239 } 240 241 int64_t getSignedBitfield(unsigned char *p, uint64_t offset, uint64_t bits) { 242 int64_t value = getUnsignedBitfield(p,offset,bits); 243 /* If the top significant bit is 1, propagate it to all the 244 * higher bits for two complement representation of signed 245 * integers. */ 246 if (value & ((uint64_t)1 << (bits-1))) 247 value |= ((uint64_t)-1) << bits; 248 return value; 249 } 250 251 /* The following two functions detect overflow of a value in the context 252 * of storing it as an unsigned or signed integer with the specified 253 * number of bits. The functions both take the value and a possible increment. 254 * If no overflow could happen and the value+increment fit inside the limits, 255 * then zero is returned, otherwise in case of overflow, 1 is returned, 256 * otherwise in case of underflow, -1 is returned. 257 * 258 * When non-zero is returned (oferflow or underflow), if not NULL, *limit is 259 * set to the value the operation should result when an overflow happens, 260 * depending on the specified overflow semantics: 261 * 262 * For BFOVERFLOW_SAT if 1 is returned, *limit it is set maximum value that 263 * you can store in that integer. when -1 is returned, *limit is set to the 264 * minimum value that an integer of that size can represent. 265 * 266 * For BFOVERFLOW_WRAP *limit is set by performing the operation in order to 267 * "wrap" around towards zero for unsigned integers, or towards the most 268 * negative number that is possible to represent for signed integers. */ 269 270 #define BFOVERFLOW_WRAP 0 271 #define BFOVERFLOW_SAT 1 272 #define BFOVERFLOW_FAIL 2 /* Used by the BITFIELD command implementation. */ 273 274 int checkUnsignedBitfieldOverflow(uint64_t value, int64_t incr, uint64_t bits, int owtype, uint64_t *limit) { 275 uint64_t max = (bits == 64) ? UINT64_MAX : (((uint64_t)1<<bits)-1); 276 int64_t maxincr = max-value; 277 int64_t minincr = -value; 278 279 if (value > max || (incr > 0 && incr > maxincr)) { 280 if (limit) { 281 if (owtype == BFOVERFLOW_WRAP) { 282 goto handle_wrap; 283 } else if (owtype == BFOVERFLOW_SAT) { 284 *limit = max; 285 } 286 } 287 return 1; 288 } else if (incr < 0 && incr < minincr) { 289 if (limit) { 290 if (owtype == BFOVERFLOW_WRAP) { 291 goto handle_wrap; 292 } else if (owtype == BFOVERFLOW_SAT) { 293 *limit = 0; 294 } 295 } 296 return -1; 297 } 298 return 0; 299 300 handle_wrap: 301 { 302 uint64_t mask = ((int64_t)-1) << bits; 303 uint64_t res = value+incr; 304 305 res &= ~mask; 306 *limit = res; 307 } 308 return 1; 309 } 310 311 int checkSignedBitfieldOverflow(int64_t value, int64_t incr, uint64_t bits, int owtype, int64_t *limit) { 312 int64_t max = (bits == 64) ? INT64_MAX : (((int64_t)1<<(bits-1))-1); 313 int64_t min = (-max)-1; 314 315 /* Note that maxincr and minincr could overflow, but we use the values 316 * only after checking 'value' range, so when we use it no overflow 317 * happens. */ 318 int64_t maxincr = max-value; 319 int64_t minincr = min-value; 320 321 if (value > max || (bits != 64 && incr > maxincr) || (value >= 0 && incr > 0 && incr > maxincr)) 322 { 323 if (limit) { 324 if (owtype == BFOVERFLOW_WRAP) { 325 goto handle_wrap; 326 } else if (owtype == BFOVERFLOW_SAT) { 327 *limit = max; 328 } 329 } 330 return 1; 331 } else if (value < min || (bits != 64 && incr < minincr) || (value < 0 && incr < 0 && incr < minincr)) { 332 if (limit) { 333 if (owtype == BFOVERFLOW_WRAP) { 334 goto handle_wrap; 335 } else if (owtype == BFOVERFLOW_SAT) { 336 *limit = min; 337 } 338 } 339 return -1; 340 } 341 return 0; 342 343 handle_wrap: 344 { 345 uint64_t mask = ((int64_t)-1) << bits; 346 uint64_t msb = (uint64_t)1 << (bits-1); 347 uint64_t a = value, b = incr, c; 348 c = a+b; /* Perform addition as unsigned so that's defined. */ 349 350 /* If the sign bit is set, propagate to all the higher order 351 * bits, to cap the negative value. If it's clear, mask to 352 * the positive integer limit. */ 353 if (c & msb) { 354 c |= mask; 355 } else { 356 c &= ~mask; 357 } 358 *limit = c; 359 } 360 return 1; 361 } 362 363 /* Debugging function. Just show bits in the specified bitmap. Not used 364 * but here for not having to rewrite it when debugging is needed. */ 365 void printBits(unsigned char *p, unsigned long count) { 366 unsigned long j, i, byte; 367 368 for (j = 0; j < count; j++) { 369 byte = p[j]; 370 for (i = 0x80; i > 0; i /= 2) 371 printf("%c", (byte & i) ? '1' : '0'); 372 printf("|"); 373 } 374 printf("\n"); 375 } 376 377 /* ----------------------------------------------------------------------------- 378 * Bits related string commands: GETBIT, SETBIT, BITCOUNT, BITOP. 379 * -------------------------------------------------------------------------- */ 380 381 #define BITOP_AND 0 382 #define BITOP_OR 1 383 #define BITOP_XOR 2 384 #define BITOP_NOT 3 385 386 #define BITFIELDOP_GET 0 387 #define BITFIELDOP_SET 1 388 #define BITFIELDOP_INCRBY 2 389 390 /* This helper function used by GETBIT / SETBIT parses the bit offset argument 391 * making sure an error is returned if it is negative or if it overflows 392 * Redis 512 MB limit for the string value. 393 * 394 * If the 'hash' argument is true, and 'bits is positive, then the command 395 * will also parse bit offsets prefixed by "#". In such a case the offset 396 * is multiplied by 'bits'. This is useful for the BITFIELD command. */ 397 int getBitOffsetFromArgument(client *c, robj *o, size_t *offset, int hash, int bits) { 398 long long loffset; 399 char *err = "bit offset is not an integer or out of range"; 400 char *p = o->ptr; 401 size_t plen = sdslen(p); 402 int usehash = 0; 403 404 /* Handle #<offset> form. */ 405 if (p[0] == '#' && hash && bits > 0) usehash = 1; 406 407 if (string2ll(p+usehash,plen-usehash,&loffset) == 0) { 408 addReplyError(c,err); 409 return C_ERR; 410 } 411 412 /* Adjust the offset by 'bits' for #<offset> form. */ 413 if (usehash) loffset *= bits; 414 415 /* Limit offset to 512MB in bytes */ 416 if ((loffset < 0) || ((unsigned long long)loffset >> 3) >= (512*1024*1024)) 417 { 418 addReplyError(c,err); 419 return C_ERR; 420 } 421 422 *offset = (size_t)loffset; 423 return C_OK; 424 } 425 426 /* This helper function for BITFIELD parses a bitfield type in the form 427 * <sign><bits> where sign is 'u' or 'i' for unsigned and signed, and 428 * the bits is a value between 1 and 64. However 64 bits unsigned integers 429 * are reported as an error because of current limitations of Redis protocol 430 * to return unsigned integer values greater than INT64_MAX. 431 * 432 * On error C_ERR is returned and an error is sent to the client. */ 433 int getBitfieldTypeFromArgument(client *c, robj *o, int *sign, int *bits) { 434 char *p = o->ptr; 435 char *err = "Invalid bitfield type. Use something like i16 u8. Note that u64 is not supported but i64 is."; 436 long long llbits; 437 438 if (p[0] == 'i') { 439 *sign = 1; 440 } else if (p[0] == 'u') { 441 *sign = 0; 442 } else { 443 addReplyError(c,err); 444 return C_ERR; 445 } 446 447 if ((string2ll(p+1,strlen(p+1),&llbits)) == 0 || 448 llbits < 1 || 449 (*sign == 1 && llbits > 64) || 450 (*sign == 0 && llbits > 63)) 451 { 452 addReplyError(c,err); 453 return C_ERR; 454 } 455 *bits = llbits; 456 return C_OK; 457 } 458 459 /* This is an helper function for commands implementations that need to write 460 * bits to a string object. The command creates or pad with zeroes the string 461 * so that the 'maxbit' bit can be addressed. The object is finally 462 * returned. Otherwise if the key holds a wrong type NULL is returned and 463 * an error is sent to the client. */ 464 robj *lookupStringForBitCommand(client *c, size_t maxbit) { 465 size_t byte = maxbit >> 3; 466 robj *o = lookupKeyWrite(c->db,c->argv[1]); 467 468 if (o == NULL) { 469 o = createObject(OBJ_STRING,sdsnewlen(NULL, byte+1)); 470 dbAdd(c->db,c->argv[1],o); 471 } else { 472 if (checkType(c,o,OBJ_STRING)) return NULL; 473 o = dbUnshareStringValue(c->db,c->argv[1],o); 474 o->ptr = sdsgrowzero(o->ptr,byte+1); 475 } 476 return o; 477 } 478 479 /* SETBIT key offset bitvalue */ 480 void setbitCommand(client *c) { 481 robj *o; 482 char *err = "bit is not an integer or out of range"; 483 size_t bitoffset; 484 ssize_t byte, bit; 485 int byteval, bitval; 486 long on; 487 488 if (getBitOffsetFromArgument(c,c->argv[2],&bitoffset,0,0) != C_OK) 489 return; 490 491 if (getLongFromObjectOrReply(c,c->argv[3],&on,err) != C_OK) 492 return; 493 494 /* Bits can only be set or cleared... */ 495 if (on & ~1) { 496 addReplyError(c,err); 497 return; 498 } 499 500 if ((o = lookupStringForBitCommand(c,bitoffset)) == NULL) return; 501 502 /* Get current values */ 503 byte = bitoffset >> 3; 504 byteval = ((uint8_t*)o->ptr)[byte]; 505 bit = 7 - (bitoffset & 0x7); 506 bitval = byteval & (1 << bit); 507 508 /* Update byte with new bit value and return original value */ 509 byteval &= ~(1 << bit); 510 byteval |= ((on & 0x1) << bit); 511 ((uint8_t*)o->ptr)[byte] = byteval; 512 signalModifiedKey(c->db,c->argv[1]); 513 notifyKeyspaceEvent(NOTIFY_STRING,"setbit",c->argv[1],c->db->id); 514 server.dirty++; 515 addReply(c, bitval ? shared.cone : shared.czero); 516 } 517 518 /* GETBIT key offset */ 519 void getbitCommand(client *c) { 520 robj *o; 521 char llbuf[32]; 522 size_t bitoffset; 523 size_t byte, bit; 524 size_t bitval = 0; 525 526 if (getBitOffsetFromArgument(c,c->argv[2],&bitoffset,0,0) != C_OK) 527 return; 528 529 if ((o = lookupKeyReadOrReply(c,c->argv[1],shared.czero)) == NULL || 530 checkType(c,o,OBJ_STRING)) return; 531 532 byte = bitoffset >> 3; 533 bit = 7 - (bitoffset & 0x7); 534 if (sdsEncodedObject(o)) { 535 if (byte < sdslen(o->ptr)) 536 bitval = ((uint8_t*)o->ptr)[byte] & (1 << bit); 537 } else { 538 if (byte < (size_t)ll2string(llbuf,sizeof(llbuf),(long)o->ptr)) 539 bitval = llbuf[byte] & (1 << bit); 540 } 541 542 addReply(c, bitval ? shared.cone : shared.czero); 543 } 544 545 /* BITOP op_name target_key src_key1 src_key2 src_key3 ... src_keyN */ 546 void bitopCommand(client *c) { 547 char *opname = c->argv[1]->ptr; 548 robj *o, *targetkey = c->argv[2]; 549 unsigned long op, j, numkeys; 550 robj **objects; /* Array of source objects. */ 551 unsigned char **src; /* Array of source strings pointers. */ 552 unsigned long *len, maxlen = 0; /* Array of length of src strings, 553 and max len. */ 554 unsigned long minlen = 0; /* Min len among the input keys. */ 555 unsigned char *res = NULL; /* Resulting string. */ 556 557 /* Parse the operation name. */ 558 if ((opname[0] == 'a' || opname[0] == 'A') && !strcasecmp(opname,"and")) 559 op = BITOP_AND; 560 else if((opname[0] == 'o' || opname[0] == 'O') && !strcasecmp(opname,"or")) 561 op = BITOP_OR; 562 else if((opname[0] == 'x' || opname[0] == 'X') && !strcasecmp(opname,"xor")) 563 op = BITOP_XOR; 564 else if((opname[0] == 'n' || opname[0] == 'N') && !strcasecmp(opname,"not")) 565 op = BITOP_NOT; 566 else { 567 addReply(c,shared.syntaxerr); 568 return; 569 } 570 571 /* Sanity check: NOT accepts only a single key argument. */ 572 if (op == BITOP_NOT && c->argc != 4) { 573 addReplyError(c,"BITOP NOT must be called with a single source key."); 574 return; 575 } 576 577 /* Lookup keys, and store pointers to the string objects into an array. */ 578 numkeys = c->argc - 3; 579 src = zmalloc(sizeof(unsigned char*) * numkeys); 580 len = zmalloc(sizeof(long) * numkeys); 581 objects = zmalloc(sizeof(robj*) * numkeys); 582 for (j = 0; j < numkeys; j++) { 583 o = lookupKeyRead(c->db,c->argv[j+3]); 584 /* Handle non-existing keys as empty strings. */ 585 if (o == NULL) { 586 objects[j] = NULL; 587 src[j] = NULL; 588 len[j] = 0; 589 minlen = 0; 590 continue; 591 } 592 /* Return an error if one of the keys is not a string. */ 593 if (checkType(c,o,OBJ_STRING)) { 594 unsigned long i; 595 for (i = 0; i < j; i++) { 596 if (objects[i]) 597 decrRefCount(objects[i]); 598 } 599 zfree(src); 600 zfree(len); 601 zfree(objects); 602 return; 603 } 604 objects[j] = getDecodedObject(o); 605 src[j] = objects[j]->ptr; 606 len[j] = sdslen(objects[j]->ptr); 607 if (len[j] > maxlen) maxlen = len[j]; 608 if (j == 0 || len[j] < minlen) minlen = len[j]; 609 } 610 611 /* Compute the bit operation, if at least one string is not empty. */ 612 if (maxlen) { 613 res = (unsigned char*) sdsnewlen(NULL,maxlen); 614 unsigned char output, byte; 615 unsigned long i; 616 617 /* Fast path: as far as we have data for all the input bitmaps we 618 * can take a fast path that performs much better than the 619 * vanilla algorithm. */ 620 j = 0; 621 if (minlen >= sizeof(unsigned long)*4 && numkeys <= 16) { 622 unsigned long *lp[16]; 623 unsigned long *lres = (unsigned long*) res; 624 625 /* Note: sds pointer is always aligned to 8 byte boundary. */ 626 memcpy(lp,src,sizeof(unsigned long*)*numkeys); 627 memcpy(res,src[0],minlen); 628 629 /* Different branches per different operations for speed (sorry). */ 630 if (op == BITOP_AND) { 631 while(minlen >= sizeof(unsigned long)*4) { 632 for (i = 1; i < numkeys; i++) { 633 lres[0] &= lp[i][0]; 634 lres[1] &= lp[i][1]; 635 lres[2] &= lp[i][2]; 636 lres[3] &= lp[i][3]; 637 lp[i]+=4; 638 } 639 lres+=4; 640 j += sizeof(unsigned long)*4; 641 minlen -= sizeof(unsigned long)*4; 642 } 643 } else if (op == BITOP_OR) { 644 while(minlen >= sizeof(unsigned long)*4) { 645 for (i = 1; i < numkeys; i++) { 646 lres[0] |= lp[i][0]; 647 lres[1] |= lp[i][1]; 648 lres[2] |= lp[i][2]; 649 lres[3] |= lp[i][3]; 650 lp[i]+=4; 651 } 652 lres+=4; 653 j += sizeof(unsigned long)*4; 654 minlen -= sizeof(unsigned long)*4; 655 } 656 } else if (op == BITOP_XOR) { 657 while(minlen >= sizeof(unsigned long)*4) { 658 for (i = 1; i < numkeys; i++) { 659 lres[0] ^= lp[i][0]; 660 lres[1] ^= lp[i][1]; 661 lres[2] ^= lp[i][2]; 662 lres[3] ^= lp[i][3]; 663 lp[i]+=4; 664 } 665 lres+=4; 666 j += sizeof(unsigned long)*4; 667 minlen -= sizeof(unsigned long)*4; 668 } 669 } else if (op == BITOP_NOT) { 670 while(minlen >= sizeof(unsigned long)*4) { 671 lres[0] = ~lres[0]; 672 lres[1] = ~lres[1]; 673 lres[2] = ~lres[2]; 674 lres[3] = ~lres[3]; 675 lres+=4; 676 j += sizeof(unsigned long)*4; 677 minlen -= sizeof(unsigned long)*4; 678 } 679 } 680 } 681 682 /* j is set to the next byte to process by the previous loop. */ 683 for (; j < maxlen; j++) { 684 output = (len[0] <= j) ? 0 : src[0][j]; 685 if (op == BITOP_NOT) output = ~output; 686 for (i = 1; i < numkeys; i++) { 687 byte = (len[i] <= j) ? 0 : src[i][j]; 688 switch(op) { 689 case BITOP_AND: output &= byte; break; 690 case BITOP_OR: output |= byte; break; 691 case BITOP_XOR: output ^= byte; break; 692 } 693 } 694 res[j] = output; 695 } 696 } 697 for (j = 0; j < numkeys; j++) { 698 if (objects[j]) 699 decrRefCount(objects[j]); 700 } 701 zfree(src); 702 zfree(len); 703 zfree(objects); 704 705 /* Store the computed value into the target key */ 706 if (maxlen) { 707 o = createObject(OBJ_STRING,res); 708 setKey(c->db,targetkey,o); 709 notifyKeyspaceEvent(NOTIFY_STRING,"set",targetkey,c->db->id); 710 decrRefCount(o); 711 } else if (dbDelete(c->db,targetkey)) { 712 signalModifiedKey(c->db,targetkey); 713 notifyKeyspaceEvent(NOTIFY_GENERIC,"del",targetkey,c->db->id); 714 } 715 server.dirty++; 716 addReplyLongLong(c,maxlen); /* Return the output string length in bytes. */ 717 } 718 719 /* BITCOUNT key [start end] */ 720 void bitcountCommand(client *c) { 721 robj *o; 722 long start, end, strlen; 723 unsigned char *p; 724 char llbuf[32]; 725 726 /* Lookup, check for type, and return 0 for non existing keys. */ 727 if ((o = lookupKeyReadOrReply(c,c->argv[1],shared.czero)) == NULL || 728 checkType(c,o,OBJ_STRING)) return; 729 730 /* Set the 'p' pointer to the string, that can be just a stack allocated 731 * array if our string was integer encoded. */ 732 if (o->encoding == OBJ_ENCODING_INT) { 733 p = (unsigned char*) llbuf; 734 strlen = ll2string(llbuf,sizeof(llbuf),(long)o->ptr); 735 } else { 736 p = (unsigned char*) o->ptr; 737 strlen = sdslen(o->ptr); 738 } 739 740 /* Parse start/end range if any. */ 741 if (c->argc == 4) { 742 if (getLongFromObjectOrReply(c,c->argv[2],&start,NULL) != C_OK) 743 return; 744 if (getLongFromObjectOrReply(c,c->argv[3],&end,NULL) != C_OK) 745 return; 746 /* Convert negative indexes */ 747 if (start < 0) start = strlen+start; 748 if (end < 0) end = strlen+end; 749 if (start < 0) start = 0; 750 if (end < 0) end = 0; 751 if (end >= strlen) end = strlen-1; 752 } else if (c->argc == 2) { 753 /* The whole string. */ 754 start = 0; 755 end = strlen-1; 756 } else { 757 /* Syntax error. */ 758 addReply(c,shared.syntaxerr); 759 return; 760 } 761 762 /* Precondition: end >= 0 && end < strlen, so the only condition where 763 * zero can be returned is: start > end. */ 764 if (start > end) { 765 addReply(c,shared.czero); 766 } else { 767 long bytes = end-start+1; 768 769 addReplyLongLong(c,redisPopcount(p+start,bytes)); 770 } 771 } 772 773 /* BITPOS key bit [start [end]] */ 774 void bitposCommand(client *c) { 775 robj *o; 776 long bit, start, end, strlen; 777 unsigned char *p; 778 char llbuf[32]; 779 int end_given = 0; 780 781 /* Parse the bit argument to understand what we are looking for, set 782 * or clear bits. */ 783 if (getLongFromObjectOrReply(c,c->argv[2],&bit,NULL) != C_OK) 784 return; 785 if (bit != 0 && bit != 1) { 786 addReplyError(c, "The bit argument must be 1 or 0."); 787 return; 788 } 789 790 /* If the key does not exist, from our point of view it is an infinite 791 * array of 0 bits. If the user is looking for the fist clear bit return 0, 792 * If the user is looking for the first set bit, return -1. */ 793 if ((o = lookupKeyRead(c->db,c->argv[1])) == NULL) { 794 addReplyLongLong(c, bit ? -1 : 0); 795 return; 796 } 797 if (checkType(c,o,OBJ_STRING)) return; 798 799 /* Set the 'p' pointer to the string, that can be just a stack allocated 800 * array if our string was integer encoded. */ 801 if (o->encoding == OBJ_ENCODING_INT) { 802 p = (unsigned char*) llbuf; 803 strlen = ll2string(llbuf,sizeof(llbuf),(long)o->ptr); 804 } else { 805 p = (unsigned char*) o->ptr; 806 strlen = sdslen(o->ptr); 807 } 808 809 /* Parse start/end range if any. */ 810 if (c->argc == 4 || c->argc == 5) { 811 if (getLongFromObjectOrReply(c,c->argv[3],&start,NULL) != C_OK) 812 return; 813 if (c->argc == 5) { 814 if (getLongFromObjectOrReply(c,c->argv[4],&end,NULL) != C_OK) 815 return; 816 end_given = 1; 817 } else { 818 end = strlen-1; 819 } 820 /* Convert negative indexes */ 821 if (start < 0) start = strlen+start; 822 if (end < 0) end = strlen+end; 823 if (start < 0) start = 0; 824 if (end < 0) end = 0; 825 if (end >= strlen) end = strlen-1; 826 } else if (c->argc == 3) { 827 /* The whole string. */ 828 start = 0; 829 end = strlen-1; 830 } else { 831 /* Syntax error. */ 832 addReply(c,shared.syntaxerr); 833 return; 834 } 835 836 /* For empty ranges (start > end) we return -1 as an empty range does 837 * not contain a 0 nor a 1. */ 838 if (start > end) { 839 addReplyLongLong(c, -1); 840 } else { 841 long bytes = end-start+1; 842 long pos = redisBitpos(p+start,bytes,bit); 843 844 /* If we are looking for clear bits, and the user specified an exact 845 * range with start-end, we can't consider the right of the range as 846 * zero padded (as we do when no explicit end is given). 847 * 848 * So if redisBitpos() returns the first bit outside the range, 849 * we return -1 to the caller, to mean, in the specified range there 850 * is not a single "0" bit. */ 851 if (end_given && bit == 0 && pos == bytes*8) { 852 addReplyLongLong(c,-1); 853 return; 854 } 855 if (pos != -1) pos += start*8; /* Adjust for the bytes we skipped. */ 856 addReplyLongLong(c,pos); 857 } 858 } 859 860 /* BITFIELD key subcommmand-1 arg ... subcommand-2 arg ... subcommand-N ... 861 * 862 * Supported subcommands: 863 * 864 * GET <type> <offset> 865 * SET <type> <offset> <value> 866 * INCRBY <type> <offset> <increment> 867 * OVERFLOW [WRAP|SAT|FAIL] 868 */ 869 870 struct bitfieldOp { 871 uint64_t offset; /* Bitfield offset. */ 872 int64_t i64; /* Increment amount (INCRBY) or SET value */ 873 int opcode; /* Operation id. */ 874 int owtype; /* Overflow type to use. */ 875 int bits; /* Integer bitfield bits width. */ 876 int sign; /* True if signed, otherwise unsigned op. */ 877 }; 878 879 void bitfieldCommand(client *c) { 880 robj *o; 881 size_t bitoffset; 882 int j, numops = 0, changes = 0; 883 struct bitfieldOp *ops = NULL; /* Array of ops to execute at end. */ 884 int owtype = BFOVERFLOW_WRAP; /* Overflow type. */ 885 886 for (j = 2; j < c->argc; j++) { 887 int remargs = c->argc-j-1; /* Remaining args other than current. */ 888 char *subcmd = c->argv[j]->ptr; /* Current command name. */ 889 int opcode; /* Current operation code. */ 890 long long i64 = 0; /* Signed SET value. */ 891 int sign = 0; /* Signed or unsigned type? */ 892 int bits = 0; /* Bitfield width in bits. */ 893 894 if (!strcasecmp(subcmd,"get") && remargs >= 2) 895 opcode = BITFIELDOP_GET; 896 else if (!strcasecmp(subcmd,"set") && remargs >= 3) 897 opcode = BITFIELDOP_SET; 898 else if (!strcasecmp(subcmd,"incrby") && remargs >= 3) 899 opcode = BITFIELDOP_INCRBY; 900 else if (!strcasecmp(subcmd,"overflow") && remargs >= 1) { 901 char *owtypename = c->argv[j+1]->ptr; 902 j++; 903 if (!strcasecmp(owtypename,"wrap")) 904 owtype = BFOVERFLOW_WRAP; 905 else if (!strcasecmp(owtypename,"sat")) 906 owtype = BFOVERFLOW_SAT; 907 else if (!strcasecmp(owtypename,"fail")) 908 owtype = BFOVERFLOW_FAIL; 909 else { 910 addReplyError(c,"Invalid OVERFLOW type specified"); 911 zfree(ops); 912 return; 913 } 914 continue; 915 } else { 916 addReply(c,shared.syntaxerr); 917 zfree(ops); 918 return; 919 } 920 921 /* Get the type and offset arguments, common to all the ops. */ 922 if (getBitfieldTypeFromArgument(c,c->argv[j+1],&sign,&bits) != C_OK) { 923 zfree(ops); 924 return; 925 } 926 927 if (getBitOffsetFromArgument(c,c->argv[j+2],&bitoffset,1,bits) != C_OK){ 928 zfree(ops); 929 return; 930 } 931 932 /* INCRBY and SET require another argument. */ 933 if (opcode != BITFIELDOP_GET) { 934 if (getLongLongFromObjectOrReply(c,c->argv[j+3],&i64,NULL) != C_OK){ 935 zfree(ops); 936 return; 937 } 938 } 939 940 /* Populate the array of operations we'll process. */ 941 ops = zrealloc(ops,sizeof(*ops)*(numops+1)); 942 ops[numops].offset = bitoffset; 943 ops[numops].i64 = i64; 944 ops[numops].opcode = opcode; 945 ops[numops].owtype = owtype; 946 ops[numops].bits = bits; 947 ops[numops].sign = sign; 948 numops++; 949 950 j += 3 - (opcode == BITFIELDOP_GET); 951 } 952 953 addReplyMultiBulkLen(c,numops); 954 955 /* Actually process the operations. */ 956 for (j = 0; j < numops; j++) { 957 struct bitfieldOp *thisop = ops+j; 958 959 /* Execute the operation. */ 960 if (thisop->opcode == BITFIELDOP_SET || 961 thisop->opcode == BITFIELDOP_INCRBY) 962 { 963 /* SET and INCRBY: We handle both with the same code path 964 * for simplicity. SET return value is the previous value so 965 * we need fetch & store as well. */ 966 967 /* Lookup by making room up to the farest bit reached by 968 * this operation. */ 969 if ((o = lookupStringForBitCommand(c, 970 thisop->offset + (thisop->bits-1))) == NULL) return; 971 972 /* We need two different but very similar code paths for signed 973 * and unsigned operations, since the set of functions to get/set 974 * the integers and the used variables types are different. */ 975 if (thisop->sign) { 976 int64_t oldval, newval, wrapped, retval; 977 int overflow; 978 979 oldval = getSignedBitfield(o->ptr,thisop->offset, 980 thisop->bits); 981 982 if (thisop->opcode == BITFIELDOP_INCRBY) { 983 newval = oldval + thisop->i64; 984 overflow = checkSignedBitfieldOverflow(oldval, 985 thisop->i64,thisop->bits,thisop->owtype,&wrapped); 986 if (overflow) newval = wrapped; 987 retval = newval; 988 } else { 989 newval = thisop->i64; 990 overflow = checkSignedBitfieldOverflow(newval, 991 0,thisop->bits,thisop->owtype,&wrapped); 992 if (overflow) newval = wrapped; 993 retval = oldval; 994 } 995 996 /* On overflow of type is "FAIL", don't write and return 997 * NULL to signal the condition. */ 998 if (!(overflow && thisop->owtype == BFOVERFLOW_FAIL)) { 999 addReplyLongLong(c,retval); 1000 setSignedBitfield(o->ptr,thisop->offset, 1001 thisop->bits,newval); 1002 } else { 1003 addReply(c,shared.nullbulk); 1004 } 1005 } else { 1006 uint64_t oldval, newval, wrapped, retval; 1007 int overflow; 1008 1009 oldval = getUnsignedBitfield(o->ptr,thisop->offset, 1010 thisop->bits); 1011 1012 if (thisop->opcode == BITFIELDOP_INCRBY) { 1013 newval = oldval + thisop->i64; 1014 overflow = checkUnsignedBitfieldOverflow(oldval, 1015 thisop->i64,thisop->bits,thisop->owtype,&wrapped); 1016 if (overflow) newval = wrapped; 1017 retval = newval; 1018 } else { 1019 newval = thisop->i64; 1020 overflow = checkUnsignedBitfieldOverflow(newval, 1021 0,thisop->bits,thisop->owtype,&wrapped); 1022 if (overflow) newval = wrapped; 1023 retval = oldval; 1024 } 1025 /* On overflow of type is "FAIL", don't write and return 1026 * NULL to signal the condition. */ 1027 if (!(overflow && thisop->owtype == BFOVERFLOW_FAIL)) { 1028 addReplyLongLong(c,retval); 1029 setUnsignedBitfield(o->ptr,thisop->offset, 1030 thisop->bits,newval); 1031 } else { 1032 addReply(c,shared.nullbulk); 1033 } 1034 } 1035 changes++; 1036 } else { 1037 /* GET */ 1038 o = lookupKeyRead(c->db,c->argv[1]); 1039 size_t olen = (o == NULL) ? 0 : sdslen(o->ptr); 1040 unsigned char buf[9]; 1041 1042 /* For GET we use a trick: before executing the operation 1043 * copy up to 9 bytes to a local buffer, so that we can easily 1044 * execute up to 64 bit operations that are at actual string 1045 * object boundaries. */ 1046 memset(buf,0,9); 1047 unsigned char *src = o ? o->ptr : NULL; 1048 int i; 1049 size_t byte = thisop->offset >> 3; 1050 for (i = 0; i < 9; i++) { 1051 if (src == NULL || i+byte >= olen) break; 1052 buf[i] = src[i+byte]; 1053 } 1054 1055 /* Now operate on the copied buffer which is guaranteed 1056 * to be zero-padded. */ 1057 if (thisop->sign) { 1058 int64_t val = getSignedBitfield(buf,thisop->offset-(byte*8), 1059 thisop->bits); 1060 addReplyLongLong(c,val); 1061 } else { 1062 uint64_t val = getUnsignedBitfield(buf,thisop->offset-(byte*8), 1063 thisop->bits); 1064 addReplyLongLong(c,val); 1065 } 1066 } 1067 } 1068 1069 if (changes) { 1070 signalModifiedKey(c->db,c->argv[1]); 1071 notifyKeyspaceEvent(NOTIFY_STRING,"setbit",c->argv[1],c->db->id); 1072 server.dirty += changes; 1073 } 1074 zfree(ops); 1075 } 1076