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