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 = ((uint64_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 = ((uint64_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 /* Return a pointer to the string object content, and stores its length 480 * in 'len'. The user is required to pass (likely stack allocated) buffer 481 * 'llbuf' of at least LONG_STR_SIZE bytes. Such a buffer is used in the case 482 * the object is integer encoded in order to provide the representation 483 * without usign heap allocation. 484 * 485 * The function returns the pointer to the object array of bytes representing 486 * the string it contains, that may be a pointer to 'llbuf' or to the 487 * internal object representation. As a side effect 'len' is filled with 488 * the length of such buffer. 489 * 490 * If the source object is NULL the function is guaranteed to return NULL 491 * and set 'len' to 0. */ 492 unsigned char *getObjectReadOnlyString(robj *o, long *len, char *llbuf) { 493 serverAssert(o->type == OBJ_STRING); 494 unsigned char *p = NULL; 495 496 /* Set the 'p' pointer to the string, that can be just a stack allocated 497 * array if our string was integer encoded. */ 498 if (o && o->encoding == OBJ_ENCODING_INT) { 499 p = (unsigned char*) llbuf; 500 if (len) *len = ll2string(llbuf,LONG_STR_SIZE,(long)o->ptr); 501 } else if (o) { 502 p = (unsigned char*) o->ptr; 503 if (len) *len = sdslen(o->ptr); 504 } else { 505 if (len) *len = 0; 506 } 507 return p; 508 } 509 510 /* SETBIT key offset bitvalue */ 511 void setbitCommand(client *c) { 512 robj *o; 513 char *err = "bit is not an integer or out of range"; 514 size_t bitoffset; 515 ssize_t byte, bit; 516 int byteval, bitval; 517 long on; 518 519 if (getBitOffsetFromArgument(c,c->argv[2],&bitoffset,0,0) != C_OK) 520 return; 521 522 if (getLongFromObjectOrReply(c,c->argv[3],&on,err) != C_OK) 523 return; 524 525 /* Bits can only be set or cleared... */ 526 if (on & ~1) { 527 addReplyError(c,err); 528 return; 529 } 530 531 if ((o = lookupStringForBitCommand(c,bitoffset)) == NULL) return; 532 533 /* Get current values */ 534 byte = bitoffset >> 3; 535 byteval = ((uint8_t*)o->ptr)[byte]; 536 bit = 7 - (bitoffset & 0x7); 537 bitval = byteval & (1 << bit); 538 539 /* Update byte with new bit value and return original value */ 540 byteval &= ~(1 << bit); 541 byteval |= ((on & 0x1) << bit); 542 ((uint8_t*)o->ptr)[byte] = byteval; 543 signalModifiedKey(c->db,c->argv[1]); 544 notifyKeyspaceEvent(NOTIFY_STRING,"setbit",c->argv[1],c->db->id); 545 server.dirty++; 546 addReply(c, bitval ? shared.cone : shared.czero); 547 } 548 549 /* GETBIT key offset */ 550 void getbitCommand(client *c) { 551 robj *o; 552 char llbuf[32]; 553 size_t bitoffset; 554 size_t byte, bit; 555 size_t bitval = 0; 556 557 if (getBitOffsetFromArgument(c,c->argv[2],&bitoffset,0,0) != C_OK) 558 return; 559 560 if ((o = lookupKeyReadOrReply(c,c->argv[1],shared.czero)) == NULL || 561 checkType(c,o,OBJ_STRING)) return; 562 563 byte = bitoffset >> 3; 564 bit = 7 - (bitoffset & 0x7); 565 if (sdsEncodedObject(o)) { 566 if (byte < sdslen(o->ptr)) 567 bitval = ((uint8_t*)o->ptr)[byte] & (1 << bit); 568 } else { 569 if (byte < (size_t)ll2string(llbuf,sizeof(llbuf),(long)o->ptr)) 570 bitval = llbuf[byte] & (1 << bit); 571 } 572 573 addReply(c, bitval ? shared.cone : shared.czero); 574 } 575 576 /* BITOP op_name target_key src_key1 src_key2 src_key3 ... src_keyN */ 577 void bitopCommand(client *c) { 578 char *opname = c->argv[1]->ptr; 579 robj *o, *targetkey = c->argv[2]; 580 unsigned long op, j, numkeys; 581 robj **objects; /* Array of source objects. */ 582 unsigned char **src; /* Array of source strings pointers. */ 583 unsigned long *len, maxlen = 0; /* Array of length of src strings, 584 and max len. */ 585 unsigned long minlen = 0; /* Min len among the input keys. */ 586 unsigned char *res = NULL; /* Resulting string. */ 587 588 /* Parse the operation name. */ 589 if ((opname[0] == 'a' || opname[0] == 'A') && !strcasecmp(opname,"and")) 590 op = BITOP_AND; 591 else if((opname[0] == 'o' || opname[0] == 'O') && !strcasecmp(opname,"or")) 592 op = BITOP_OR; 593 else if((opname[0] == 'x' || opname[0] == 'X') && !strcasecmp(opname,"xor")) 594 op = BITOP_XOR; 595 else if((opname[0] == 'n' || opname[0] == 'N') && !strcasecmp(opname,"not")) 596 op = BITOP_NOT; 597 else { 598 addReply(c,shared.syntaxerr); 599 return; 600 } 601 602 /* Sanity check: NOT accepts only a single key argument. */ 603 if (op == BITOP_NOT && c->argc != 4) { 604 addReplyError(c,"BITOP NOT must be called with a single source key."); 605 return; 606 } 607 608 /* Lookup keys, and store pointers to the string objects into an array. */ 609 numkeys = c->argc - 3; 610 src = zmalloc(sizeof(unsigned char*) * numkeys); 611 len = zmalloc(sizeof(long) * numkeys); 612 objects = zmalloc(sizeof(robj*) * numkeys); 613 for (j = 0; j < numkeys; j++) { 614 o = lookupKeyRead(c->db,c->argv[j+3]); 615 /* Handle non-existing keys as empty strings. */ 616 if (o == NULL) { 617 objects[j] = NULL; 618 src[j] = NULL; 619 len[j] = 0; 620 minlen = 0; 621 continue; 622 } 623 /* Return an error if one of the keys is not a string. */ 624 if (checkType(c,o,OBJ_STRING)) { 625 unsigned long i; 626 for (i = 0; i < j; i++) { 627 if (objects[i]) 628 decrRefCount(objects[i]); 629 } 630 zfree(src); 631 zfree(len); 632 zfree(objects); 633 return; 634 } 635 objects[j] = getDecodedObject(o); 636 src[j] = objects[j]->ptr; 637 len[j] = sdslen(objects[j]->ptr); 638 if (len[j] > maxlen) maxlen = len[j]; 639 if (j == 0 || len[j] < minlen) minlen = len[j]; 640 } 641 642 /* Compute the bit operation, if at least one string is not empty. */ 643 if (maxlen) { 644 res = (unsigned char*) sdsnewlen(NULL,maxlen); 645 unsigned char output, byte; 646 unsigned long i; 647 648 /* Fast path: as far as we have data for all the input bitmaps we 649 * can take a fast path that performs much better than the 650 * vanilla algorithm. */ 651 j = 0; 652 if (minlen >= sizeof(unsigned long)*4 && numkeys <= 16) { 653 unsigned long *lp[16]; 654 unsigned long *lres = (unsigned long*) res; 655 656 /* Note: sds pointer is always aligned to 8 byte boundary. */ 657 memcpy(lp,src,sizeof(unsigned long*)*numkeys); 658 memcpy(res,src[0],minlen); 659 660 /* Different branches per different operations for speed (sorry). */ 661 if (op == BITOP_AND) { 662 while(minlen >= sizeof(unsigned long)*4) { 663 for (i = 1; i < numkeys; i++) { 664 lres[0] &= lp[i][0]; 665 lres[1] &= lp[i][1]; 666 lres[2] &= lp[i][2]; 667 lres[3] &= lp[i][3]; 668 lp[i]+=4; 669 } 670 lres+=4; 671 j += sizeof(unsigned long)*4; 672 minlen -= sizeof(unsigned long)*4; 673 } 674 } else if (op == BITOP_OR) { 675 while(minlen >= sizeof(unsigned long)*4) { 676 for (i = 1; i < numkeys; i++) { 677 lres[0] |= lp[i][0]; 678 lres[1] |= lp[i][1]; 679 lres[2] |= lp[i][2]; 680 lres[3] |= lp[i][3]; 681 lp[i]+=4; 682 } 683 lres+=4; 684 j += sizeof(unsigned long)*4; 685 minlen -= sizeof(unsigned long)*4; 686 } 687 } else if (op == BITOP_XOR) { 688 while(minlen >= sizeof(unsigned long)*4) { 689 for (i = 1; i < numkeys; i++) { 690 lres[0] ^= lp[i][0]; 691 lres[1] ^= lp[i][1]; 692 lres[2] ^= lp[i][2]; 693 lres[3] ^= lp[i][3]; 694 lp[i]+=4; 695 } 696 lres+=4; 697 j += sizeof(unsigned long)*4; 698 minlen -= sizeof(unsigned long)*4; 699 } 700 } else if (op == BITOP_NOT) { 701 while(minlen >= sizeof(unsigned long)*4) { 702 lres[0] = ~lres[0]; 703 lres[1] = ~lres[1]; 704 lres[2] = ~lres[2]; 705 lres[3] = ~lres[3]; 706 lres+=4; 707 j += sizeof(unsigned long)*4; 708 minlen -= sizeof(unsigned long)*4; 709 } 710 } 711 } 712 713 /* j is set to the next byte to process by the previous loop. */ 714 for (; j < maxlen; j++) { 715 output = (len[0] <= j) ? 0 : src[0][j]; 716 if (op == BITOP_NOT) output = ~output; 717 for (i = 1; i < numkeys; i++) { 718 byte = (len[i] <= j) ? 0 : src[i][j]; 719 switch(op) { 720 case BITOP_AND: output &= byte; break; 721 case BITOP_OR: output |= byte; break; 722 case BITOP_XOR: output ^= byte; break; 723 } 724 } 725 res[j] = output; 726 } 727 } 728 for (j = 0; j < numkeys; j++) { 729 if (objects[j]) 730 decrRefCount(objects[j]); 731 } 732 zfree(src); 733 zfree(len); 734 zfree(objects); 735 736 /* Store the computed value into the target key */ 737 if (maxlen) { 738 o = createObject(OBJ_STRING,res); 739 setKey(c->db,targetkey,o); 740 notifyKeyspaceEvent(NOTIFY_STRING,"set",targetkey,c->db->id); 741 decrRefCount(o); 742 } else if (dbDelete(c->db,targetkey)) { 743 signalModifiedKey(c->db,targetkey); 744 notifyKeyspaceEvent(NOTIFY_GENERIC,"del",targetkey,c->db->id); 745 } 746 server.dirty++; 747 addReplyLongLong(c,maxlen); /* Return the output string length in bytes. */ 748 } 749 750 /* BITCOUNT key [start end] */ 751 void bitcountCommand(client *c) { 752 robj *o; 753 long start, end, strlen; 754 unsigned char *p; 755 char llbuf[LONG_STR_SIZE]; 756 757 /* Lookup, check for type, and return 0 for non existing keys. */ 758 if ((o = lookupKeyReadOrReply(c,c->argv[1],shared.czero)) == NULL || 759 checkType(c,o,OBJ_STRING)) return; 760 p = getObjectReadOnlyString(o,&strlen,llbuf); 761 762 /* Parse start/end range if any. */ 763 if (c->argc == 4) { 764 if (getLongFromObjectOrReply(c,c->argv[2],&start,NULL) != C_OK) 765 return; 766 if (getLongFromObjectOrReply(c,c->argv[3],&end,NULL) != C_OK) 767 return; 768 /* Convert negative indexes */ 769 if (start < 0) start = strlen+start; 770 if (end < 0) end = strlen+end; 771 if (start < 0) start = 0; 772 if (end < 0) end = 0; 773 if (end >= strlen) end = strlen-1; 774 } else if (c->argc == 2) { 775 /* The whole string. */ 776 start = 0; 777 end = strlen-1; 778 } else { 779 /* Syntax error. */ 780 addReply(c,shared.syntaxerr); 781 return; 782 } 783 784 /* Precondition: end >= 0 && end < strlen, so the only condition where 785 * zero can be returned is: start > end. */ 786 if (start > end) { 787 addReply(c,shared.czero); 788 } else { 789 long bytes = end-start+1; 790 791 addReplyLongLong(c,redisPopcount(p+start,bytes)); 792 } 793 } 794 795 /* BITPOS key bit [start [end]] */ 796 void bitposCommand(client *c) { 797 robj *o; 798 long bit, start, end, strlen; 799 unsigned char *p; 800 char llbuf[LONG_STR_SIZE]; 801 int end_given = 0; 802 803 /* Parse the bit argument to understand what we are looking for, set 804 * or clear bits. */ 805 if (getLongFromObjectOrReply(c,c->argv[2],&bit,NULL) != C_OK) 806 return; 807 if (bit != 0 && bit != 1) { 808 addReplyError(c, "The bit argument must be 1 or 0."); 809 return; 810 } 811 812 /* If the key does not exist, from our point of view it is an infinite 813 * array of 0 bits. If the user is looking for the fist clear bit return 0, 814 * If the user is looking for the first set bit, return -1. */ 815 if ((o = lookupKeyRead(c->db,c->argv[1])) == NULL) { 816 addReplyLongLong(c, bit ? -1 : 0); 817 return; 818 } 819 if (checkType(c,o,OBJ_STRING)) return; 820 p = getObjectReadOnlyString(o,&strlen,llbuf); 821 822 /* Parse start/end range if any. */ 823 if (c->argc == 4 || c->argc == 5) { 824 if (getLongFromObjectOrReply(c,c->argv[3],&start,NULL) != C_OK) 825 return; 826 if (c->argc == 5) { 827 if (getLongFromObjectOrReply(c,c->argv[4],&end,NULL) != C_OK) 828 return; 829 end_given = 1; 830 } else { 831 end = strlen-1; 832 } 833 /* Convert negative indexes */ 834 if (start < 0) start = strlen+start; 835 if (end < 0) end = strlen+end; 836 if (start < 0) start = 0; 837 if (end < 0) end = 0; 838 if (end >= strlen) end = strlen-1; 839 } else if (c->argc == 3) { 840 /* The whole string. */ 841 start = 0; 842 end = strlen-1; 843 } else { 844 /* Syntax error. */ 845 addReply(c,shared.syntaxerr); 846 return; 847 } 848 849 /* For empty ranges (start > end) we return -1 as an empty range does 850 * not contain a 0 nor a 1. */ 851 if (start > end) { 852 addReplyLongLong(c, -1); 853 } else { 854 long bytes = end-start+1; 855 long pos = redisBitpos(p+start,bytes,bit); 856 857 /* If we are looking for clear bits, and the user specified an exact 858 * range with start-end, we can't consider the right of the range as 859 * zero padded (as we do when no explicit end is given). 860 * 861 * So if redisBitpos() returns the first bit outside the range, 862 * we return -1 to the caller, to mean, in the specified range there 863 * is not a single "0" bit. */ 864 if (end_given && bit == 0 && pos == bytes*8) { 865 addReplyLongLong(c,-1); 866 return; 867 } 868 if (pos != -1) pos += start*8; /* Adjust for the bytes we skipped. */ 869 addReplyLongLong(c,pos); 870 } 871 } 872 873 /* BITFIELD key subcommmand-1 arg ... subcommand-2 arg ... subcommand-N ... 874 * 875 * Supported subcommands: 876 * 877 * GET <type> <offset> 878 * SET <type> <offset> <value> 879 * INCRBY <type> <offset> <increment> 880 * OVERFLOW [WRAP|SAT|FAIL] 881 */ 882 883 struct bitfieldOp { 884 uint64_t offset; /* Bitfield offset. */ 885 int64_t i64; /* Increment amount (INCRBY) or SET value */ 886 int opcode; /* Operation id. */ 887 int owtype; /* Overflow type to use. */ 888 int bits; /* Integer bitfield bits width. */ 889 int sign; /* True if signed, otherwise unsigned op. */ 890 }; 891 892 void bitfieldCommand(client *c) { 893 robj *o; 894 size_t bitoffset; 895 int j, numops = 0, changes = 0; 896 struct bitfieldOp *ops = NULL; /* Array of ops to execute at end. */ 897 int owtype = BFOVERFLOW_WRAP; /* Overflow type. */ 898 899 for (j = 2; j < c->argc; j++) { 900 int remargs = c->argc-j-1; /* Remaining args other than current. */ 901 char *subcmd = c->argv[j]->ptr; /* Current command name. */ 902 int opcode; /* Current operation code. */ 903 long long i64 = 0; /* Signed SET value. */ 904 int sign = 0; /* Signed or unsigned type? */ 905 int bits = 0; /* Bitfield width in bits. */ 906 907 if (!strcasecmp(subcmd,"get") && remargs >= 2) 908 opcode = BITFIELDOP_GET; 909 else if (!strcasecmp(subcmd,"set") && remargs >= 3) 910 opcode = BITFIELDOP_SET; 911 else if (!strcasecmp(subcmd,"incrby") && remargs >= 3) 912 opcode = BITFIELDOP_INCRBY; 913 else if (!strcasecmp(subcmd,"overflow") && remargs >= 1) { 914 char *owtypename = c->argv[j+1]->ptr; 915 j++; 916 if (!strcasecmp(owtypename,"wrap")) 917 owtype = BFOVERFLOW_WRAP; 918 else if (!strcasecmp(owtypename,"sat")) 919 owtype = BFOVERFLOW_SAT; 920 else if (!strcasecmp(owtypename,"fail")) 921 owtype = BFOVERFLOW_FAIL; 922 else { 923 addReplyError(c,"Invalid OVERFLOW type specified"); 924 zfree(ops); 925 return; 926 } 927 continue; 928 } else { 929 addReply(c,shared.syntaxerr); 930 zfree(ops); 931 return; 932 } 933 934 /* Get the type and offset arguments, common to all the ops. */ 935 if (getBitfieldTypeFromArgument(c,c->argv[j+1],&sign,&bits) != C_OK) { 936 zfree(ops); 937 return; 938 } 939 940 if (getBitOffsetFromArgument(c,c->argv[j+2],&bitoffset,1,bits) != C_OK){ 941 zfree(ops); 942 return; 943 } 944 945 /* INCRBY and SET require another argument. */ 946 if (opcode != BITFIELDOP_GET) { 947 if (getLongLongFromObjectOrReply(c,c->argv[j+3],&i64,NULL) != C_OK){ 948 zfree(ops); 949 return; 950 } 951 } 952 953 /* Populate the array of operations we'll process. */ 954 ops = zrealloc(ops,sizeof(*ops)*(numops+1)); 955 ops[numops].offset = bitoffset; 956 ops[numops].i64 = i64; 957 ops[numops].opcode = opcode; 958 ops[numops].owtype = owtype; 959 ops[numops].bits = bits; 960 ops[numops].sign = sign; 961 numops++; 962 963 j += 3 - (opcode == BITFIELDOP_GET); 964 } 965 966 addReplyMultiBulkLen(c,numops); 967 968 /* Actually process the operations. */ 969 for (j = 0; j < numops; j++) { 970 struct bitfieldOp *thisop = ops+j; 971 972 /* Execute the operation. */ 973 if (thisop->opcode == BITFIELDOP_SET || 974 thisop->opcode == BITFIELDOP_INCRBY) 975 { 976 /* SET and INCRBY: We handle both with the same code path 977 * for simplicity. SET return value is the previous value so 978 * we need fetch & store as well. */ 979 980 /* Lookup by making room up to the farest bit reached by 981 * this operation. */ 982 if ((o = lookupStringForBitCommand(c, 983 thisop->offset + (thisop->bits-1))) == NULL) return; 984 985 /* We need two different but very similar code paths for signed 986 * and unsigned operations, since the set of functions to get/set 987 * the integers and the used variables types are different. */ 988 if (thisop->sign) { 989 int64_t oldval, newval, wrapped, retval; 990 int overflow; 991 992 oldval = getSignedBitfield(o->ptr,thisop->offset, 993 thisop->bits); 994 995 if (thisop->opcode == BITFIELDOP_INCRBY) { 996 newval = oldval + thisop->i64; 997 overflow = checkSignedBitfieldOverflow(oldval, 998 thisop->i64,thisop->bits,thisop->owtype,&wrapped); 999 if (overflow) newval = wrapped; 1000 retval = newval; 1001 } else { 1002 newval = thisop->i64; 1003 overflow = checkSignedBitfieldOverflow(newval, 1004 0,thisop->bits,thisop->owtype,&wrapped); 1005 if (overflow) newval = wrapped; 1006 retval = oldval; 1007 } 1008 1009 /* On overflow of type is "FAIL", don't write and return 1010 * NULL to signal the condition. */ 1011 if (!(overflow && thisop->owtype == BFOVERFLOW_FAIL)) { 1012 addReplyLongLong(c,retval); 1013 setSignedBitfield(o->ptr,thisop->offset, 1014 thisop->bits,newval); 1015 } else { 1016 addReply(c,shared.nullbulk); 1017 } 1018 } else { 1019 uint64_t oldval, newval, wrapped, retval; 1020 int overflow; 1021 1022 oldval = getUnsignedBitfield(o->ptr,thisop->offset, 1023 thisop->bits); 1024 1025 if (thisop->opcode == BITFIELDOP_INCRBY) { 1026 newval = oldval + thisop->i64; 1027 overflow = checkUnsignedBitfieldOverflow(oldval, 1028 thisop->i64,thisop->bits,thisop->owtype,&wrapped); 1029 if (overflow) newval = wrapped; 1030 retval = newval; 1031 } else { 1032 newval = thisop->i64; 1033 overflow = checkUnsignedBitfieldOverflow(newval, 1034 0,thisop->bits,thisop->owtype,&wrapped); 1035 if (overflow) newval = wrapped; 1036 retval = oldval; 1037 } 1038 /* On overflow of type is "FAIL", don't write and return 1039 * NULL to signal the condition. */ 1040 if (!(overflow && thisop->owtype == BFOVERFLOW_FAIL)) { 1041 addReplyLongLong(c,retval); 1042 setUnsignedBitfield(o->ptr,thisop->offset, 1043 thisop->bits,newval); 1044 } else { 1045 addReply(c,shared.nullbulk); 1046 } 1047 } 1048 changes++; 1049 } else { 1050 /* GET */ 1051 unsigned char buf[9]; 1052 long strlen; 1053 unsigned char *src = NULL; 1054 char llbuf[LONG_STR_SIZE]; 1055 1056 o = lookupKeyRead(c->db,c->argv[1]); 1057 src = getObjectReadOnlyString(o,&strlen,llbuf); 1058 1059 /* For GET we use a trick: before executing the operation 1060 * copy up to 9 bytes to a local buffer, so that we can easily 1061 * execute up to 64 bit operations that are at actual string 1062 * object boundaries. */ 1063 memset(buf,0,9); 1064 int i; 1065 size_t byte = thisop->offset >> 3; 1066 for (i = 0; i < 9; i++) { 1067 if (src == NULL || i+byte >= (size_t)strlen) break; 1068 buf[i] = src[i+byte]; 1069 } 1070 1071 /* Now operate on the copied buffer which is guaranteed 1072 * to be zero-padded. */ 1073 if (thisop->sign) { 1074 int64_t val = getSignedBitfield(buf,thisop->offset-(byte*8), 1075 thisop->bits); 1076 addReplyLongLong(c,val); 1077 } else { 1078 uint64_t val = getUnsignedBitfield(buf,thisop->offset-(byte*8), 1079 thisop->bits); 1080 addReplyLongLong(c,val); 1081 } 1082 } 1083 } 1084 1085 if (changes) { 1086 signalModifiedKey(c->db,c->argv[1]); 1087 notifyKeyspaceEvent(NOTIFY_STRING,"setbit",c->argv[1],c->db->id); 1088 server.dirty += changes; 1089 } 1090 zfree(ops); 1091 } 1092