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 = value; /* Casting will add UINT64_MAX + 1 if v is negative. */ 219 setUnsignedBitfield(p,offset,bits,uv); 220 } 221 222 uint64_t getUnsignedBitfield(unsigned char *p, uint64_t offset, uint64_t bits) { 223 uint64_t byte, bit, byteval, bitval, j, value = 0; 224 225 for (j = 0; j < bits; j++) { 226 byte = offset >> 3; 227 bit = 7 - (offset & 0x7); 228 byteval = p[byte]; 229 bitval = (byteval >> bit) & 1; 230 value = (value<<1) | bitval; 231 offset++; 232 } 233 return value; 234 } 235 236 int64_t getSignedBitfield(unsigned char *p, uint64_t offset, uint64_t bits) { 237 int64_t value; 238 union {uint64_t u; int64_t i;} conv; 239 240 /* Converting from unsigned to signed is undefined when the value does 241 * not fit, however here we assume two's complement and the original value 242 * was obtained from signed -> unsigned conversion, so we'll find the 243 * most significant bit set if the original value was negative. 244 * 245 * Note that two's complement is mandatory for exact-width types 246 * according to the C99 standard. */ 247 conv.u = getUnsignedBitfield(p,offset,bits); 248 value = conv.i; 249 250 /* If the top significant bit is 1, propagate it to all the 251 * higher bits for two's complement representation of signed 252 * integers. */ 253 if (value & ((uint64_t)1 << (bits-1))) 254 value |= ((uint64_t)-1) << bits; 255 return value; 256 } 257 258 /* The following two functions detect overflow of a value in the context 259 * of storing it as an unsigned or signed integer with the specified 260 * number of bits. The functions both take the value and a possible increment. 261 * If no overflow could happen and the value+increment fit inside the limits, 262 * then zero is returned, otherwise in case of overflow, 1 is returned, 263 * otherwise in case of underflow, -1 is returned. 264 * 265 * When non-zero is returned (oferflow or underflow), if not NULL, *limit is 266 * set to the value the operation should result when an overflow happens, 267 * depending on the specified overflow semantics: 268 * 269 * For BFOVERFLOW_SAT if 1 is returned, *limit it is set maximum value that 270 * you can store in that integer. when -1 is returned, *limit is set to the 271 * minimum value that an integer of that size can represent. 272 * 273 * For BFOVERFLOW_WRAP *limit is set by performing the operation in order to 274 * "wrap" around towards zero for unsigned integers, or towards the most 275 * negative number that is possible to represent for signed integers. */ 276 277 #define BFOVERFLOW_WRAP 0 278 #define BFOVERFLOW_SAT 1 279 #define BFOVERFLOW_FAIL 2 /* Used by the BITFIELD command implementation. */ 280 281 int checkUnsignedBitfieldOverflow(uint64_t value, int64_t incr, uint64_t bits, int owtype, uint64_t *limit) { 282 uint64_t max = (bits == 64) ? UINT64_MAX : (((uint64_t)1<<bits)-1); 283 int64_t maxincr = max-value; 284 int64_t minincr = -value; 285 286 if (value > max || (incr > 0 && incr > maxincr)) { 287 if (limit) { 288 if (owtype == BFOVERFLOW_WRAP) { 289 goto handle_wrap; 290 } else if (owtype == BFOVERFLOW_SAT) { 291 *limit = max; 292 } 293 } 294 return 1; 295 } else if (incr < 0 && incr < minincr) { 296 if (limit) { 297 if (owtype == BFOVERFLOW_WRAP) { 298 goto handle_wrap; 299 } else if (owtype == BFOVERFLOW_SAT) { 300 *limit = 0; 301 } 302 } 303 return -1; 304 } 305 return 0; 306 307 handle_wrap: 308 { 309 uint64_t mask = ((uint64_t)-1) << bits; 310 uint64_t res = value+incr; 311 312 res &= ~mask; 313 *limit = res; 314 } 315 return 1; 316 } 317 318 int checkSignedBitfieldOverflow(int64_t value, int64_t incr, uint64_t bits, int owtype, int64_t *limit) { 319 int64_t max = (bits == 64) ? INT64_MAX : (((int64_t)1<<(bits-1))-1); 320 int64_t min = (-max)-1; 321 322 /* Note that maxincr and minincr could overflow, but we use the values 323 * only after checking 'value' range, so when we use it no overflow 324 * happens. */ 325 int64_t maxincr = max-value; 326 int64_t minincr = min-value; 327 328 if (value > max || (bits != 64 && incr > maxincr) || (value >= 0 && incr > 0 && incr > maxincr)) 329 { 330 if (limit) { 331 if (owtype == BFOVERFLOW_WRAP) { 332 goto handle_wrap; 333 } else if (owtype == BFOVERFLOW_SAT) { 334 *limit = max; 335 } 336 } 337 return 1; 338 } else if (value < min || (bits != 64 && incr < minincr) || (value < 0 && incr < 0 && incr < minincr)) { 339 if (limit) { 340 if (owtype == BFOVERFLOW_WRAP) { 341 goto handle_wrap; 342 } else if (owtype == BFOVERFLOW_SAT) { 343 *limit = min; 344 } 345 } 346 return -1; 347 } 348 return 0; 349 350 handle_wrap: 351 { 352 uint64_t mask = ((uint64_t)-1) << bits; 353 uint64_t msb = (uint64_t)1 << (bits-1); 354 uint64_t a = value, b = incr, c; 355 c = a+b; /* Perform addition as unsigned so that's defined. */ 356 357 /* If the sign bit is set, propagate to all the higher order 358 * bits, to cap the negative value. If it's clear, mask to 359 * the positive integer limit. */ 360 if (c & msb) { 361 c |= mask; 362 } else { 363 c &= ~mask; 364 } 365 *limit = c; 366 } 367 return 1; 368 } 369 370 /* Debugging function. Just show bits in the specified bitmap. Not used 371 * but here for not having to rewrite it when debugging is needed. */ 372 void printBits(unsigned char *p, unsigned long count) { 373 unsigned long j, i, byte; 374 375 for (j = 0; j < count; j++) { 376 byte = p[j]; 377 for (i = 0x80; i > 0; i /= 2) 378 printf("%c", (byte & i) ? '1' : '0'); 379 printf("|"); 380 } 381 printf("\n"); 382 } 383 384 /* ----------------------------------------------------------------------------- 385 * Bits related string commands: GETBIT, SETBIT, BITCOUNT, BITOP. 386 * -------------------------------------------------------------------------- */ 387 388 #define BITOP_AND 0 389 #define BITOP_OR 1 390 #define BITOP_XOR 2 391 #define BITOP_NOT 3 392 393 #define BITFIELDOP_GET 0 394 #define BITFIELDOP_SET 1 395 #define BITFIELDOP_INCRBY 2 396 397 /* This helper function used by GETBIT / SETBIT parses the bit offset argument 398 * making sure an error is returned if it is negative or if it overflows 399 * Redis 512 MB limit for the string value. 400 * 401 * If the 'hash' argument is true, and 'bits is positive, then the command 402 * will also parse bit offsets prefixed by "#". In such a case the offset 403 * is multiplied by 'bits'. This is useful for the BITFIELD command. */ 404 int getBitOffsetFromArgument(client *c, robj *o, size_t *offset, int hash, int bits) { 405 long long loffset; 406 char *err = "bit offset is not an integer or out of range"; 407 char *p = o->ptr; 408 size_t plen = sdslen(p); 409 int usehash = 0; 410 411 /* Handle #<offset> form. */ 412 if (p[0] == '#' && hash && bits > 0) usehash = 1; 413 414 if (string2ll(p+usehash,plen-usehash,&loffset) == 0) { 415 addReplyError(c,err); 416 return C_ERR; 417 } 418 419 /* Adjust the offset by 'bits' for #<offset> form. */ 420 if (usehash) loffset *= bits; 421 422 /* Limit offset to 512MB in bytes */ 423 if ((loffset < 0) || ((unsigned long long)loffset >> 3) >= (512*1024*1024)) 424 { 425 addReplyError(c,err); 426 return C_ERR; 427 } 428 429 *offset = (size_t)loffset; 430 return C_OK; 431 } 432 433 /* This helper function for BITFIELD parses a bitfield type in the form 434 * <sign><bits> where sign is 'u' or 'i' for unsigned and signed, and 435 * the bits is a value between 1 and 64. However 64 bits unsigned integers 436 * are reported as an error because of current limitations of Redis protocol 437 * to return unsigned integer values greater than INT64_MAX. 438 * 439 * On error C_ERR is returned and an error is sent to the client. */ 440 int getBitfieldTypeFromArgument(client *c, robj *o, int *sign, int *bits) { 441 char *p = o->ptr; 442 char *err = "Invalid bitfield type. Use something like i16 u8. Note that u64 is not supported but i64 is."; 443 long long llbits; 444 445 if (p[0] == 'i') { 446 *sign = 1; 447 } else if (p[0] == 'u') { 448 *sign = 0; 449 } else { 450 addReplyError(c,err); 451 return C_ERR; 452 } 453 454 if ((string2ll(p+1,strlen(p+1),&llbits)) == 0 || 455 llbits < 1 || 456 (*sign == 1 && llbits > 64) || 457 (*sign == 0 && llbits > 63)) 458 { 459 addReplyError(c,err); 460 return C_ERR; 461 } 462 *bits = llbits; 463 return C_OK; 464 } 465 466 /* This is an helper function for commands implementations that need to write 467 * bits to a string object. The command creates or pad with zeroes the string 468 * so that the 'maxbit' bit can be addressed. The object is finally 469 * returned. Otherwise if the key holds a wrong type NULL is returned and 470 * an error is sent to the client. */ 471 robj *lookupStringForBitCommand(client *c, size_t maxbit) { 472 size_t byte = maxbit >> 3; 473 robj *o = lookupKeyWrite(c->db,c->argv[1]); 474 475 if (o == NULL) { 476 o = createObject(OBJ_STRING,sdsnewlen(NULL, byte+1)); 477 dbAdd(c->db,c->argv[1],o); 478 } else { 479 if (checkType(c,o,OBJ_STRING)) return NULL; 480 o = dbUnshareStringValue(c->db,c->argv[1],o); 481 o->ptr = sdsgrowzero(o->ptr,byte+1); 482 } 483 return o; 484 } 485 486 /* Return a pointer to the string object content, and stores its length 487 * in 'len'. The user is required to pass (likely stack allocated) buffer 488 * 'llbuf' of at least LONG_STR_SIZE bytes. Such a buffer is used in the case 489 * the object is integer encoded in order to provide the representation 490 * without usign heap allocation. 491 * 492 * The function returns the pointer to the object array of bytes representing 493 * the string it contains, that may be a pointer to 'llbuf' or to the 494 * internal object representation. As a side effect 'len' is filled with 495 * the length of such buffer. 496 * 497 * If the source object is NULL the function is guaranteed to return NULL 498 * and set 'len' to 0. */ 499 unsigned char *getObjectReadOnlyString(robj *o, long *len, char *llbuf) { 500 serverAssert(o->type == OBJ_STRING); 501 unsigned char *p = NULL; 502 503 /* Set the 'p' pointer to the string, that can be just a stack allocated 504 * array if our string was integer encoded. */ 505 if (o && o->encoding == OBJ_ENCODING_INT) { 506 p = (unsigned char*) llbuf; 507 if (len) *len = ll2string(llbuf,LONG_STR_SIZE,(long)o->ptr); 508 } else if (o) { 509 p = (unsigned char*) o->ptr; 510 if (len) *len = sdslen(o->ptr); 511 } else { 512 if (len) *len = 0; 513 } 514 return p; 515 } 516 517 /* SETBIT key offset bitvalue */ 518 void setbitCommand(client *c) { 519 robj *o; 520 char *err = "bit is not an integer or out of range"; 521 size_t bitoffset; 522 ssize_t byte, bit; 523 int byteval, bitval; 524 long on; 525 526 if (getBitOffsetFromArgument(c,c->argv[2],&bitoffset,0,0) != C_OK) 527 return; 528 529 if (getLongFromObjectOrReply(c,c->argv[3],&on,err) != C_OK) 530 return; 531 532 /* Bits can only be set or cleared... */ 533 if (on & ~1) { 534 addReplyError(c,err); 535 return; 536 } 537 538 if ((o = lookupStringForBitCommand(c,bitoffset)) == NULL) return; 539 540 /* Get current values */ 541 byte = bitoffset >> 3; 542 byteval = ((uint8_t*)o->ptr)[byte]; 543 bit = 7 - (bitoffset & 0x7); 544 bitval = byteval & (1 << bit); 545 546 /* Update byte with new bit value and return original value */ 547 byteval &= ~(1 << bit); 548 byteval |= ((on & 0x1) << bit); 549 ((uint8_t*)o->ptr)[byte] = byteval; 550 signalModifiedKey(c->db,c->argv[1]); 551 notifyKeyspaceEvent(NOTIFY_STRING,"setbit",c->argv[1],c->db->id); 552 server.dirty++; 553 addReply(c, bitval ? shared.cone : shared.czero); 554 } 555 556 /* GETBIT key offset */ 557 void getbitCommand(client *c) { 558 robj *o; 559 char llbuf[32]; 560 size_t bitoffset; 561 size_t byte, bit; 562 size_t bitval = 0; 563 564 if (getBitOffsetFromArgument(c,c->argv[2],&bitoffset,0,0) != C_OK) 565 return; 566 567 if ((o = lookupKeyReadOrReply(c,c->argv[1],shared.czero)) == NULL || 568 checkType(c,o,OBJ_STRING)) return; 569 570 byte = bitoffset >> 3; 571 bit = 7 - (bitoffset & 0x7); 572 if (sdsEncodedObject(o)) { 573 if (byte < sdslen(o->ptr)) 574 bitval = ((uint8_t*)o->ptr)[byte] & (1 << bit); 575 } else { 576 if (byte < (size_t)ll2string(llbuf,sizeof(llbuf),(long)o->ptr)) 577 bitval = llbuf[byte] & (1 << bit); 578 } 579 580 addReply(c, bitval ? shared.cone : shared.czero); 581 } 582 583 /* BITOP op_name target_key src_key1 src_key2 src_key3 ... src_keyN */ 584 void bitopCommand(client *c) { 585 char *opname = c->argv[1]->ptr; 586 robj *o, *targetkey = c->argv[2]; 587 unsigned long op, j, numkeys; 588 robj **objects; /* Array of source objects. */ 589 unsigned char **src; /* Array of source strings pointers. */ 590 unsigned long *len, maxlen = 0; /* Array of length of src strings, 591 and max len. */ 592 unsigned long minlen = 0; /* Min len among the input keys. */ 593 unsigned char *res = NULL; /* Resulting string. */ 594 595 /* Parse the operation name. */ 596 if ((opname[0] == 'a' || opname[0] == 'A') && !strcasecmp(opname,"and")) 597 op = BITOP_AND; 598 else if((opname[0] == 'o' || opname[0] == 'O') && !strcasecmp(opname,"or")) 599 op = BITOP_OR; 600 else if((opname[0] == 'x' || opname[0] == 'X') && !strcasecmp(opname,"xor")) 601 op = BITOP_XOR; 602 else if((opname[0] == 'n' || opname[0] == 'N') && !strcasecmp(opname,"not")) 603 op = BITOP_NOT; 604 else { 605 addReply(c,shared.syntaxerr); 606 return; 607 } 608 609 /* Sanity check: NOT accepts only a single key argument. */ 610 if (op == BITOP_NOT && c->argc != 4) { 611 addReplyError(c,"BITOP NOT must be called with a single source key."); 612 return; 613 } 614 615 /* Lookup keys, and store pointers to the string objects into an array. */ 616 numkeys = c->argc - 3; 617 src = zmalloc(sizeof(unsigned char*) * numkeys); 618 len = zmalloc(sizeof(long) * numkeys); 619 objects = zmalloc(sizeof(robj*) * numkeys); 620 for (j = 0; j < numkeys; j++) { 621 o = lookupKeyRead(c->db,c->argv[j+3]); 622 /* Handle non-existing keys as empty strings. */ 623 if (o == NULL) { 624 objects[j] = NULL; 625 src[j] = NULL; 626 len[j] = 0; 627 minlen = 0; 628 continue; 629 } 630 /* Return an error if one of the keys is not a string. */ 631 if (checkType(c,o,OBJ_STRING)) { 632 unsigned long i; 633 for (i = 0; i < j; i++) { 634 if (objects[i]) 635 decrRefCount(objects[i]); 636 } 637 zfree(src); 638 zfree(len); 639 zfree(objects); 640 return; 641 } 642 objects[j] = getDecodedObject(o); 643 src[j] = objects[j]->ptr; 644 len[j] = sdslen(objects[j]->ptr); 645 if (len[j] > maxlen) maxlen = len[j]; 646 if (j == 0 || len[j] < minlen) minlen = len[j]; 647 } 648 649 /* Compute the bit operation, if at least one string is not empty. */ 650 if (maxlen) { 651 res = (unsigned char*) sdsnewlen(NULL,maxlen); 652 unsigned char output, byte; 653 unsigned long i; 654 655 /* Fast path: as far as we have data for all the input bitmaps we 656 * can take a fast path that performs much better than the 657 * vanilla algorithm. */ 658 j = 0; 659 if (minlen >= sizeof(unsigned long)*4 && numkeys <= 16) { 660 unsigned long *lp[16]; 661 unsigned long *lres = (unsigned long*) res; 662 663 /* Note: sds pointer is always aligned to 8 byte boundary. */ 664 memcpy(lp,src,sizeof(unsigned long*)*numkeys); 665 memcpy(res,src[0],minlen); 666 667 /* Different branches per different operations for speed (sorry). */ 668 if (op == BITOP_AND) { 669 while(minlen >= sizeof(unsigned long)*4) { 670 for (i = 1; i < numkeys; i++) { 671 lres[0] &= lp[i][0]; 672 lres[1] &= lp[i][1]; 673 lres[2] &= lp[i][2]; 674 lres[3] &= lp[i][3]; 675 lp[i]+=4; 676 } 677 lres+=4; 678 j += sizeof(unsigned long)*4; 679 minlen -= sizeof(unsigned long)*4; 680 } 681 } else if (op == BITOP_OR) { 682 while(minlen >= sizeof(unsigned long)*4) { 683 for (i = 1; i < numkeys; i++) { 684 lres[0] |= lp[i][0]; 685 lres[1] |= lp[i][1]; 686 lres[2] |= lp[i][2]; 687 lres[3] |= lp[i][3]; 688 lp[i]+=4; 689 } 690 lres+=4; 691 j += sizeof(unsigned long)*4; 692 minlen -= sizeof(unsigned long)*4; 693 } 694 } else if (op == BITOP_XOR) { 695 while(minlen >= sizeof(unsigned long)*4) { 696 for (i = 1; i < numkeys; i++) { 697 lres[0] ^= lp[i][0]; 698 lres[1] ^= lp[i][1]; 699 lres[2] ^= lp[i][2]; 700 lres[3] ^= lp[i][3]; 701 lp[i]+=4; 702 } 703 lres+=4; 704 j += sizeof(unsigned long)*4; 705 minlen -= sizeof(unsigned long)*4; 706 } 707 } else if (op == BITOP_NOT) { 708 while(minlen >= sizeof(unsigned long)*4) { 709 lres[0] = ~lres[0]; 710 lres[1] = ~lres[1]; 711 lres[2] = ~lres[2]; 712 lres[3] = ~lres[3]; 713 lres+=4; 714 j += sizeof(unsigned long)*4; 715 minlen -= sizeof(unsigned long)*4; 716 } 717 } 718 } 719 720 /* j is set to the next byte to process by the previous loop. */ 721 for (; j < maxlen; j++) { 722 output = (len[0] <= j) ? 0 : src[0][j]; 723 if (op == BITOP_NOT) output = ~output; 724 for (i = 1; i < numkeys; i++) { 725 byte = (len[i] <= j) ? 0 : src[i][j]; 726 switch(op) { 727 case BITOP_AND: output &= byte; break; 728 case BITOP_OR: output |= byte; break; 729 case BITOP_XOR: output ^= byte; break; 730 } 731 } 732 res[j] = output; 733 } 734 } 735 for (j = 0; j < numkeys; j++) { 736 if (objects[j]) 737 decrRefCount(objects[j]); 738 } 739 zfree(src); 740 zfree(len); 741 zfree(objects); 742 743 /* Store the computed value into the target key */ 744 if (maxlen) { 745 o = createObject(OBJ_STRING,res); 746 setKey(c->db,targetkey,o); 747 notifyKeyspaceEvent(NOTIFY_STRING,"set",targetkey,c->db->id); 748 decrRefCount(o); 749 } else if (dbDelete(c->db,targetkey)) { 750 signalModifiedKey(c->db,targetkey); 751 notifyKeyspaceEvent(NOTIFY_GENERIC,"del",targetkey,c->db->id); 752 } 753 server.dirty++; 754 addReplyLongLong(c,maxlen); /* Return the output string length in bytes. */ 755 } 756 757 /* BITCOUNT key [start end] */ 758 void bitcountCommand(client *c) { 759 robj *o; 760 long start, end, strlen; 761 unsigned char *p; 762 char llbuf[LONG_STR_SIZE]; 763 764 /* Lookup, check for type, and return 0 for non existing keys. */ 765 if ((o = lookupKeyReadOrReply(c,c->argv[1],shared.czero)) == NULL || 766 checkType(c,o,OBJ_STRING)) return; 767 p = getObjectReadOnlyString(o,&strlen,llbuf); 768 769 /* Parse start/end range if any. */ 770 if (c->argc == 4) { 771 if (getLongFromObjectOrReply(c,c->argv[2],&start,NULL) != C_OK) 772 return; 773 if (getLongFromObjectOrReply(c,c->argv[3],&end,NULL) != C_OK) 774 return; 775 /* Convert negative indexes */ 776 if (start < 0 && end < 0 && start > end) { 777 addReply(c,shared.czero); 778 return; 779 } 780 if (start < 0) start = strlen+start; 781 if (end < 0) end = strlen+end; 782 if (start < 0) start = 0; 783 if (end < 0) end = 0; 784 if (end >= strlen) end = strlen-1; 785 } else if (c->argc == 2) { 786 /* The whole string. */ 787 start = 0; 788 end = strlen-1; 789 } else { 790 /* Syntax error. */ 791 addReply(c,shared.syntaxerr); 792 return; 793 } 794 795 /* Precondition: end >= 0 && end < strlen, so the only condition where 796 * zero can be returned is: start > end. */ 797 if (start > end) { 798 addReply(c,shared.czero); 799 } else { 800 long bytes = end-start+1; 801 802 addReplyLongLong(c,redisPopcount(p+start,bytes)); 803 } 804 } 805 806 /* BITPOS key bit [start [end]] */ 807 void bitposCommand(client *c) { 808 robj *o; 809 long bit, start, end, strlen; 810 unsigned char *p; 811 char llbuf[LONG_STR_SIZE]; 812 int end_given = 0; 813 814 /* Parse the bit argument to understand what we are looking for, set 815 * or clear bits. */ 816 if (getLongFromObjectOrReply(c,c->argv[2],&bit,NULL) != C_OK) 817 return; 818 if (bit != 0 && bit != 1) { 819 addReplyError(c, "The bit argument must be 1 or 0."); 820 return; 821 } 822 823 /* If the key does not exist, from our point of view it is an infinite 824 * array of 0 bits. If the user is looking for the fist clear bit return 0, 825 * If the user is looking for the first set bit, return -1. */ 826 if ((o = lookupKeyRead(c->db,c->argv[1])) == NULL) { 827 addReplyLongLong(c, bit ? -1 : 0); 828 return; 829 } 830 if (checkType(c,o,OBJ_STRING)) return; 831 p = getObjectReadOnlyString(o,&strlen,llbuf); 832 833 /* Parse start/end range if any. */ 834 if (c->argc == 4 || c->argc == 5) { 835 if (getLongFromObjectOrReply(c,c->argv[3],&start,NULL) != C_OK) 836 return; 837 if (c->argc == 5) { 838 if (getLongFromObjectOrReply(c,c->argv[4],&end,NULL) != C_OK) 839 return; 840 end_given = 1; 841 } else { 842 end = strlen-1; 843 } 844 /* Convert negative indexes */ 845 if (start < 0) start = strlen+start; 846 if (end < 0) end = strlen+end; 847 if (start < 0) start = 0; 848 if (end < 0) end = 0; 849 if (end >= strlen) end = strlen-1; 850 } else if (c->argc == 3) { 851 /* The whole string. */ 852 start = 0; 853 end = strlen-1; 854 } else { 855 /* Syntax error. */ 856 addReply(c,shared.syntaxerr); 857 return; 858 } 859 860 /* For empty ranges (start > end) we return -1 as an empty range does 861 * not contain a 0 nor a 1. */ 862 if (start > end) { 863 addReplyLongLong(c, -1); 864 } else { 865 long bytes = end-start+1; 866 long pos = redisBitpos(p+start,bytes,bit); 867 868 /* If we are looking for clear bits, and the user specified an exact 869 * range with start-end, we can't consider the right of the range as 870 * zero padded (as we do when no explicit end is given). 871 * 872 * So if redisBitpos() returns the first bit outside the range, 873 * we return -1 to the caller, to mean, in the specified range there 874 * is not a single "0" bit. */ 875 if (end_given && bit == 0 && pos == bytes*8) { 876 addReplyLongLong(c,-1); 877 return; 878 } 879 if (pos != -1) pos += start*8; /* Adjust for the bytes we skipped. */ 880 addReplyLongLong(c,pos); 881 } 882 } 883 884 /* BITFIELD key subcommmand-1 arg ... subcommand-2 arg ... subcommand-N ... 885 * 886 * Supported subcommands: 887 * 888 * GET <type> <offset> 889 * SET <type> <offset> <value> 890 * INCRBY <type> <offset> <increment> 891 * OVERFLOW [WRAP|SAT|FAIL] 892 */ 893 894 struct bitfieldOp { 895 uint64_t offset; /* Bitfield offset. */ 896 int64_t i64; /* Increment amount (INCRBY) or SET value */ 897 int opcode; /* Operation id. */ 898 int owtype; /* Overflow type to use. */ 899 int bits; /* Integer bitfield bits width. */ 900 int sign; /* True if signed, otherwise unsigned op. */ 901 }; 902 903 void bitfieldCommand(client *c) { 904 robj *o; 905 size_t bitoffset; 906 int j, numops = 0, changes = 0; 907 struct bitfieldOp *ops = NULL; /* Array of ops to execute at end. */ 908 int owtype = BFOVERFLOW_WRAP; /* Overflow type. */ 909 int readonly = 1; 910 long higest_write_offset = 0; 911 912 for (j = 2; j < c->argc; j++) { 913 int remargs = c->argc-j-1; /* Remaining args other than current. */ 914 char *subcmd = c->argv[j]->ptr; /* Current command name. */ 915 int opcode; /* Current operation code. */ 916 long long i64 = 0; /* Signed SET value. */ 917 int sign = 0; /* Signed or unsigned type? */ 918 int bits = 0; /* Bitfield width in bits. */ 919 920 if (!strcasecmp(subcmd,"get") && remargs >= 2) 921 opcode = BITFIELDOP_GET; 922 else if (!strcasecmp(subcmd,"set") && remargs >= 3) 923 opcode = BITFIELDOP_SET; 924 else if (!strcasecmp(subcmd,"incrby") && remargs >= 3) 925 opcode = BITFIELDOP_INCRBY; 926 else if (!strcasecmp(subcmd,"overflow") && remargs >= 1) { 927 char *owtypename = c->argv[j+1]->ptr; 928 j++; 929 if (!strcasecmp(owtypename,"wrap")) 930 owtype = BFOVERFLOW_WRAP; 931 else if (!strcasecmp(owtypename,"sat")) 932 owtype = BFOVERFLOW_SAT; 933 else if (!strcasecmp(owtypename,"fail")) 934 owtype = BFOVERFLOW_FAIL; 935 else { 936 addReplyError(c,"Invalid OVERFLOW type specified"); 937 zfree(ops); 938 return; 939 } 940 continue; 941 } else { 942 addReply(c,shared.syntaxerr); 943 zfree(ops); 944 return; 945 } 946 947 /* Get the type and offset arguments, common to all the ops. */ 948 if (getBitfieldTypeFromArgument(c,c->argv[j+1],&sign,&bits) != C_OK) { 949 zfree(ops); 950 return; 951 } 952 953 if (getBitOffsetFromArgument(c,c->argv[j+2],&bitoffset,1,bits) != C_OK){ 954 zfree(ops); 955 return; 956 } 957 958 if (opcode != BITFIELDOP_GET) { 959 readonly = 0; 960 higest_write_offset = bitoffset + bits - 1; 961 /* INCRBY and SET require another argument. */ 962 if (getLongLongFromObjectOrReply(c,c->argv[j+3],&i64,NULL) != C_OK){ 963 zfree(ops); 964 return; 965 } 966 } 967 968 /* Populate the array of operations we'll process. */ 969 ops = zrealloc(ops,sizeof(*ops)*(numops+1)); 970 ops[numops].offset = bitoffset; 971 ops[numops].i64 = i64; 972 ops[numops].opcode = opcode; 973 ops[numops].owtype = owtype; 974 ops[numops].bits = bits; 975 ops[numops].sign = sign; 976 numops++; 977 978 j += 3 - (opcode == BITFIELDOP_GET); 979 } 980 981 if (readonly) { 982 /* Lookup for read is ok if key doesn't exit, but errors 983 * if it's not a string. */ 984 o = lookupKeyRead(c->db,c->argv[1]); 985 if (o != NULL && checkType(c,o,OBJ_STRING)) return; 986 } else { 987 /* Lookup by making room up to the farest bit reached by 988 * this operation. */ 989 if ((o = lookupStringForBitCommand(c, 990 higest_write_offset)) == NULL) return; 991 } 992 993 addReplyMultiBulkLen(c,numops); 994 995 /* Actually process the operations. */ 996 for (j = 0; j < numops; j++) { 997 struct bitfieldOp *thisop = ops+j; 998 999 /* Execute the operation. */ 1000 if (thisop->opcode == BITFIELDOP_SET || 1001 thisop->opcode == BITFIELDOP_INCRBY) 1002 { 1003 /* SET and INCRBY: We handle both with the same code path 1004 * for simplicity. SET return value is the previous value so 1005 * we need fetch & store as well. */ 1006 1007 /* We need two different but very similar code paths for signed 1008 * and unsigned operations, since the set of functions to get/set 1009 * the integers and the used variables types are different. */ 1010 if (thisop->sign) { 1011 int64_t oldval, newval, wrapped, retval; 1012 int overflow; 1013 1014 oldval = getSignedBitfield(o->ptr,thisop->offset, 1015 thisop->bits); 1016 1017 if (thisop->opcode == BITFIELDOP_INCRBY) { 1018 newval = oldval + thisop->i64; 1019 overflow = checkSignedBitfieldOverflow(oldval, 1020 thisop->i64,thisop->bits,thisop->owtype,&wrapped); 1021 if (overflow) newval = wrapped; 1022 retval = newval; 1023 } else { 1024 newval = thisop->i64; 1025 overflow = checkSignedBitfieldOverflow(newval, 1026 0,thisop->bits,thisop->owtype,&wrapped); 1027 if (overflow) newval = wrapped; 1028 retval = oldval; 1029 } 1030 1031 /* On overflow of type is "FAIL", don't write and return 1032 * NULL to signal the condition. */ 1033 if (!(overflow && thisop->owtype == BFOVERFLOW_FAIL)) { 1034 addReplyLongLong(c,retval); 1035 setSignedBitfield(o->ptr,thisop->offset, 1036 thisop->bits,newval); 1037 } else { 1038 addReply(c,shared.nullbulk); 1039 } 1040 } else { 1041 uint64_t oldval, newval, wrapped, retval; 1042 int overflow; 1043 1044 oldval = getUnsignedBitfield(o->ptr,thisop->offset, 1045 thisop->bits); 1046 1047 if (thisop->opcode == BITFIELDOP_INCRBY) { 1048 newval = oldval + thisop->i64; 1049 overflow = checkUnsignedBitfieldOverflow(oldval, 1050 thisop->i64,thisop->bits,thisop->owtype,&wrapped); 1051 if (overflow) newval = wrapped; 1052 retval = newval; 1053 } else { 1054 newval = thisop->i64; 1055 overflow = checkUnsignedBitfieldOverflow(newval, 1056 0,thisop->bits,thisop->owtype,&wrapped); 1057 if (overflow) newval = wrapped; 1058 retval = oldval; 1059 } 1060 /* On overflow of type is "FAIL", don't write and return 1061 * NULL to signal the condition. */ 1062 if (!(overflow && thisop->owtype == BFOVERFLOW_FAIL)) { 1063 addReplyLongLong(c,retval); 1064 setUnsignedBitfield(o->ptr,thisop->offset, 1065 thisop->bits,newval); 1066 } else { 1067 addReply(c,shared.nullbulk); 1068 } 1069 } 1070 changes++; 1071 } else { 1072 /* GET */ 1073 unsigned char buf[9]; 1074 long strlen = 0; 1075 unsigned char *src = NULL; 1076 char llbuf[LONG_STR_SIZE]; 1077 1078 if (o != NULL) 1079 src = getObjectReadOnlyString(o,&strlen,llbuf); 1080 1081 /* For GET we use a trick: before executing the operation 1082 * copy up to 9 bytes to a local buffer, so that we can easily 1083 * execute up to 64 bit operations that are at actual string 1084 * object boundaries. */ 1085 memset(buf,0,9); 1086 int i; 1087 size_t byte = thisop->offset >> 3; 1088 for (i = 0; i < 9; i++) { 1089 if (src == NULL || i+byte >= (size_t)strlen) break; 1090 buf[i] = src[i+byte]; 1091 } 1092 1093 /* Now operate on the copied buffer which is guaranteed 1094 * to be zero-padded. */ 1095 if (thisop->sign) { 1096 int64_t val = getSignedBitfield(buf,thisop->offset-(byte*8), 1097 thisop->bits); 1098 addReplyLongLong(c,val); 1099 } else { 1100 uint64_t val = getUnsignedBitfield(buf,thisop->offset-(byte*8), 1101 thisop->bits); 1102 addReplyLongLong(c,val); 1103 } 1104 } 1105 } 1106 1107 if (changes) { 1108 signalModifiedKey(c->db,c->argv[1]); 1109 notifyKeyspaceEvent(NOTIFY_STRING,"setbit",c->argv[1],c->db->id); 1110 server.dirty += changes; 1111 } 1112 zfree(ops); 1113 } 1114