1 /* Bit operations. 2 * 3 * Copyright (c) 2009-2012, Salvatore Sanfilippo <antirez at gmail dot com> 4 * All rights reserved. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions are met: 8 * 9 * * Redistributions of source code must retain the above copyright notice, 10 * this list of conditions and the following disclaimer. 11 * * Redistributions in binary form must reproduce the above copyright 12 * notice, this list of conditions and the following disclaimer in the 13 * documentation and/or other materials provided with the distribution. 14 * * Neither the name of Redis nor the names of its contributors may be used 15 * to endorse or promote products derived from this software without 16 * specific prior written permission. 17 * 18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 19 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 20 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 21 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 22 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 23 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 24 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 25 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 26 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 27 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 28 * POSSIBILITY OF SUCH DAMAGE. 29 */ 30 31 #include "redis.h" 32 33 /* ----------------------------------------------------------------------------- 34 * Helpers and low level bit functions. 35 * -------------------------------------------------------------------------- */ 36 37 /* This helper function used by GETBIT / SETBIT parses the bit offset argument 38 * making sure an error is returned if it is negative or if it overflows 39 * Redis 512 MB limit for the string value. */ 40 static int getBitOffsetFromArgument(redisClient *c, robj *o, size_t *offset) { 41 long long loffset; 42 char *err = "bit offset is not an integer or out of range"; 43 44 if (getLongLongFromObjectOrReply(c,o,&loffset,err) != REDIS_OK) 45 return REDIS_ERR; 46 47 /* Limit offset to 512MB in bytes */ 48 if ((loffset < 0) || ((unsigned long long)loffset >> 3) >= (512*1024*1024)) 49 { 50 addReplyError(c,err); 51 return REDIS_ERR; 52 } 53 54 *offset = (size_t)loffset; 55 return REDIS_OK; 56 } 57 58 /* Count number of bits set in the binary array pointed by 's' and long 59 * 'count' bytes. The implementation of this function is required to 60 * work with a input string length up to 512 MB. */ 61 size_t redisPopcount(void *s, long count) { 62 size_t bits = 0; 63 unsigned char *p = s; 64 uint32_t *p4; 65 static const unsigned char bitsinbyte[256] = {0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8}; 66 67 /* Count initial bytes not aligned to 32 bit. */ 68 while((unsigned long)p & 3 && count) { 69 bits += bitsinbyte[*p++]; 70 count--; 71 } 72 73 /* Count bits 28 bytes at a time */ 74 p4 = (uint32_t*)p; 75 while(count>=28) { 76 uint32_t aux1, aux2, aux3, aux4, aux5, aux6, aux7; 77 78 aux1 = *p4++; 79 aux2 = *p4++; 80 aux3 = *p4++; 81 aux4 = *p4++; 82 aux5 = *p4++; 83 aux6 = *p4++; 84 aux7 = *p4++; 85 count -= 28; 86 87 aux1 = aux1 - ((aux1 >> 1) & 0x55555555); 88 aux1 = (aux1 & 0x33333333) + ((aux1 >> 2) & 0x33333333); 89 aux2 = aux2 - ((aux2 >> 1) & 0x55555555); 90 aux2 = (aux2 & 0x33333333) + ((aux2 >> 2) & 0x33333333); 91 aux3 = aux3 - ((aux3 >> 1) & 0x55555555); 92 aux3 = (aux3 & 0x33333333) + ((aux3 >> 2) & 0x33333333); 93 aux4 = aux4 - ((aux4 >> 1) & 0x55555555); 94 aux4 = (aux4 & 0x33333333) + ((aux4 >> 2) & 0x33333333); 95 aux5 = aux5 - ((aux5 >> 1) & 0x55555555); 96 aux5 = (aux5 & 0x33333333) + ((aux5 >> 2) & 0x33333333); 97 aux6 = aux6 - ((aux6 >> 1) & 0x55555555); 98 aux6 = (aux6 & 0x33333333) + ((aux6 >> 2) & 0x33333333); 99 aux7 = aux7 - ((aux7 >> 1) & 0x55555555); 100 aux7 = (aux7 & 0x33333333) + ((aux7 >> 2) & 0x33333333); 101 bits += ((((aux1 + (aux1 >> 4)) & 0x0F0F0F0F) + 102 ((aux2 + (aux2 >> 4)) & 0x0F0F0F0F) + 103 ((aux3 + (aux3 >> 4)) & 0x0F0F0F0F) + 104 ((aux4 + (aux4 >> 4)) & 0x0F0F0F0F) + 105 ((aux5 + (aux5 >> 4)) & 0x0F0F0F0F) + 106 ((aux6 + (aux6 >> 4)) & 0x0F0F0F0F) + 107 ((aux7 + (aux7 >> 4)) & 0x0F0F0F0F))* 0x01010101) >> 24; 108 } 109 /* Count the remaining bytes. */ 110 p = (unsigned char*)p4; 111 while(count--) bits += bitsinbyte[*p++]; 112 return bits; 113 } 114 115 /* Return the position of the first bit set to one (if 'bit' is 1) or 116 * zero (if 'bit' is 0) in the bitmap starting at 's' and long 'count' bytes. 117 * 118 * The function is guaranteed to return a value >= 0 if 'bit' is 0 since if 119 * no zero bit is found, it returns count*8 assuming the string is zero 120 * padded on the right. However if 'bit' is 1 it is possible that there is 121 * not a single set bit in the bitmap. In this special case -1 is returned. */ 122 long redisBitpos(void *s, unsigned long count, int bit) { 123 unsigned long *l; 124 unsigned char *c; 125 unsigned long skipval, word = 0, one; 126 long pos = 0; /* Position of bit, to return to the caller. */ 127 unsigned long j; 128 129 /* Process whole words first, seeking for first word that is not 130 * all ones or all zeros respectively if we are lookig for zeros 131 * or ones. This is much faster with large strings having contiguous 132 * blocks of 1 or 0 bits compared to the vanilla bit per bit processing. 133 * 134 * Note that if we start from an address that is not aligned 135 * to sizeof(unsigned long) we consume it byte by byte until it is 136 * aligned. */ 137 138 /* Skip initial bits not aligned to sizeof(unsigned long) byte by byte. */ 139 skipval = bit ? 0 : UCHAR_MAX; 140 c = (unsigned char*) s; 141 while((unsigned long)c & (sizeof(*l)-1) && count) { 142 if (*c != skipval) break; 143 c++; 144 count--; 145 pos += 8; 146 } 147 148 /* Skip bits with full word step. */ 149 skipval = bit ? 0 : ULONG_MAX; 150 l = (unsigned long*) c; 151 while (count >= sizeof(*l)) { 152 if (*l != skipval) break; 153 l++; 154 count -= sizeof(*l); 155 pos += sizeof(*l)*8; 156 } 157 158 /* Load bytes into "word" considering the first byte as the most significant 159 * (we basically consider it as written in big endian, since we consider the 160 * string as a set of bits from left to right, with the first bit at position 161 * zero. 162 * 163 * Note that the loading is designed to work even when the bytes left 164 * (count) are less than a full word. We pad it with zero on the right. */ 165 c = (unsigned char*)l; 166 for (j = 0; j < sizeof(*l); j++) { 167 word <<= 8; 168 if (count) { 169 word |= *c; 170 c++; 171 count--; 172 } 173 } 174 175 /* Special case: 176 * If bits in the string are all zero and we are looking for one, 177 * return -1 to signal that there is not a single "1" in the whole 178 * string. This can't happen when we are looking for "0" as we assume 179 * that the right of the string is zero padded. */ 180 if (bit == 1 && word == 0) return -1; 181 182 /* Last word left, scan bit by bit. The first thing we need is to 183 * have a single "1" set in the most significant position in an 184 * unsigned long. We don't know the size of the long so we use a 185 * simple trick. */ 186 one = ULONG_MAX; /* All bits set to 1.*/ 187 one >>= 1; /* All bits set to 1 but the MSB. */ 188 one = ~one; /* All bits set to 0 but the MSB. */ 189 190 while(one) { 191 if (((one & word) != 0) == bit) return pos; 192 pos++; 193 one >>= 1; 194 } 195 196 /* If we reached this point, there is a bug in the algorithm, since 197 * the case of no match is handled as a special case before. */ 198 redisPanic("End of redisBitpos() reached."); 199 return 0; /* Just to avoid warnings. */ 200 } 201 202 /* ----------------------------------------------------------------------------- 203 * Bits related string commands: GETBIT, SETBIT, BITCOUNT, BITOP. 204 * -------------------------------------------------------------------------- */ 205 206 #define BITOP_AND 0 207 #define BITOP_OR 1 208 #define BITOP_XOR 2 209 #define BITOP_NOT 3 210 211 /* SETBIT key offset bitvalue */ 212 void setbitCommand(redisClient *c) { 213 robj *o; 214 char *err = "bit is not an integer or out of range"; 215 size_t bitoffset; 216 int byte, bit; 217 int byteval, bitval; 218 long on; 219 220 if (getBitOffsetFromArgument(c,c->argv[2],&bitoffset) != REDIS_OK) 221 return; 222 223 if (getLongFromObjectOrReply(c,c->argv[3],&on,err) != REDIS_OK) 224 return; 225 226 /* Bits can only be set or cleared... */ 227 if (on & ~1) { 228 addReplyError(c,err); 229 return; 230 } 231 232 o = lookupKeyWrite(c->db,c->argv[1]); 233 if (o == NULL) { 234 o = createObject(REDIS_STRING,sdsempty()); 235 dbAdd(c->db,c->argv[1],o); 236 } else { 237 if (checkType(c,o,REDIS_STRING)) return; 238 o = dbUnshareStringValue(c->db,c->argv[1],o); 239 } 240 241 /* Grow sds value to the right length if necessary */ 242 byte = bitoffset >> 3; 243 o->ptr = sdsgrowzero(o->ptr,byte+1); 244 245 /* Get current values */ 246 byteval = ((uint8_t*)o->ptr)[byte]; 247 bit = 7 - (bitoffset & 0x7); 248 bitval = byteval & (1 << bit); 249 250 /* Update byte with new bit value and return original value */ 251 byteval &= ~(1 << bit); 252 byteval |= ((on & 0x1) << bit); 253 ((uint8_t*)o->ptr)[byte] = byteval; 254 signalModifiedKey(c->db,c->argv[1]); 255 notifyKeyspaceEvent(REDIS_NOTIFY_STRING,"setbit",c->argv[1],c->db->id); 256 server.dirty++; 257 addReply(c, bitval ? shared.cone : shared.czero); 258 } 259 260 /* GETBIT key offset */ 261 void getbitCommand(redisClient *c) { 262 robj *o; 263 char llbuf[32]; 264 size_t bitoffset; 265 size_t byte, bit; 266 size_t bitval = 0; 267 268 if (getBitOffsetFromArgument(c,c->argv[2],&bitoffset) != REDIS_OK) 269 return; 270 271 if ((o = lookupKeyReadOrReply(c,c->argv[1],shared.czero)) == NULL || 272 checkType(c,o,REDIS_STRING)) return; 273 274 byte = bitoffset >> 3; 275 bit = 7 - (bitoffset & 0x7); 276 if (sdsEncodedObject(o)) { 277 if (byte < sdslen(o->ptr)) 278 bitval = ((uint8_t*)o->ptr)[byte] & (1 << bit); 279 } else { 280 if (byte < (size_t)ll2string(llbuf,sizeof(llbuf),(long)o->ptr)) 281 bitval = llbuf[byte] & (1 << bit); 282 } 283 284 addReply(c, bitval ? shared.cone : shared.czero); 285 } 286 287 /* BITOP op_name target_key src_key1 src_key2 src_key3 ... src_keyN */ 288 void bitopCommand(redisClient *c) { 289 char *opname = c->argv[1]->ptr; 290 robj *o, *targetkey = c->argv[2]; 291 unsigned long op, j, numkeys; 292 robj **objects; /* Array of source objects. */ 293 unsigned char **src; /* Array of source strings pointers. */ 294 unsigned long *len, maxlen = 0; /* Array of length of src strings, 295 and max len. */ 296 unsigned long minlen = 0; /* Min len among the input keys. */ 297 unsigned char *res = NULL; /* Resulting string. */ 298 299 /* Parse the operation name. */ 300 if ((opname[0] == 'a' || opname[0] == 'A') && !strcasecmp(opname,"and")) 301 op = BITOP_AND; 302 else if((opname[0] == 'o' || opname[0] == 'O') && !strcasecmp(opname,"or")) 303 op = BITOP_OR; 304 else if((opname[0] == 'x' || opname[0] == 'X') && !strcasecmp(opname,"xor")) 305 op = BITOP_XOR; 306 else if((opname[0] == 'n' || opname[0] == 'N') && !strcasecmp(opname,"not")) 307 op = BITOP_NOT; 308 else { 309 addReply(c,shared.syntaxerr); 310 return; 311 } 312 313 /* Sanity check: NOT accepts only a single key argument. */ 314 if (op == BITOP_NOT && c->argc != 4) { 315 addReplyError(c,"BITOP NOT must be called with a single source key."); 316 return; 317 } 318 319 /* Lookup keys, and store pointers to the string objects into an array. */ 320 numkeys = c->argc - 3; 321 src = zmalloc(sizeof(unsigned char*) * numkeys); 322 len = zmalloc(sizeof(long) * numkeys); 323 objects = zmalloc(sizeof(robj*) * numkeys); 324 for (j = 0; j < numkeys; j++) { 325 o = lookupKeyRead(c->db,c->argv[j+3]); 326 /* Handle non-existing keys as empty strings. */ 327 if (o == NULL) { 328 objects[j] = NULL; 329 src[j] = NULL; 330 len[j] = 0; 331 minlen = 0; 332 continue; 333 } 334 /* Return an error if one of the keys is not a string. */ 335 if (checkType(c,o,REDIS_STRING)) { 336 unsigned long i; 337 for (i = 0; i < j; i++) { 338 if (objects[i]) 339 decrRefCount(objects[i]); 340 } 341 zfree(src); 342 zfree(len); 343 zfree(objects); 344 return; 345 } 346 objects[j] = getDecodedObject(o); 347 src[j] = objects[j]->ptr; 348 len[j] = sdslen(objects[j]->ptr); 349 if (len[j] > maxlen) maxlen = len[j]; 350 if (j == 0 || len[j] < minlen) minlen = len[j]; 351 } 352 353 /* Compute the bit operation, if at least one string is not empty. */ 354 if (maxlen) { 355 res = (unsigned char*) sdsnewlen(NULL,maxlen); 356 unsigned char output, byte; 357 unsigned long i; 358 359 /* Fast path: as far as we have data for all the input bitmaps we 360 * can take a fast path that performs much better than the 361 * vanilla algorithm. */ 362 j = 0; 363 if (minlen >= sizeof(unsigned long)*4 && numkeys <= 16) { 364 unsigned long *lp[16]; 365 unsigned long *lres = (unsigned long*) res; 366 367 /* Note: sds pointer is always aligned to 8 byte boundary. */ 368 memcpy(lp,src,sizeof(unsigned long*)*numkeys); 369 memcpy(res,src[0],minlen); 370 371 /* Different branches per different operations for speed (sorry). */ 372 if (op == BITOP_AND) { 373 while(minlen >= sizeof(unsigned long)*4) { 374 for (i = 1; i < numkeys; i++) { 375 lres[0] &= lp[i][0]; 376 lres[1] &= lp[i][1]; 377 lres[2] &= lp[i][2]; 378 lres[3] &= lp[i][3]; 379 lp[i]+=4; 380 } 381 lres+=4; 382 j += sizeof(unsigned long)*4; 383 minlen -= sizeof(unsigned long)*4; 384 } 385 } else if (op == BITOP_OR) { 386 while(minlen >= sizeof(unsigned long)*4) { 387 for (i = 1; i < numkeys; i++) { 388 lres[0] |= lp[i][0]; 389 lres[1] |= lp[i][1]; 390 lres[2] |= lp[i][2]; 391 lres[3] |= lp[i][3]; 392 lp[i]+=4; 393 } 394 lres+=4; 395 j += sizeof(unsigned long)*4; 396 minlen -= sizeof(unsigned long)*4; 397 } 398 } else if (op == BITOP_XOR) { 399 while(minlen >= sizeof(unsigned long)*4) { 400 for (i = 1; i < numkeys; i++) { 401 lres[0] ^= lp[i][0]; 402 lres[1] ^= lp[i][1]; 403 lres[2] ^= lp[i][2]; 404 lres[3] ^= lp[i][3]; 405 lp[i]+=4; 406 } 407 lres+=4; 408 j += sizeof(unsigned long)*4; 409 minlen -= sizeof(unsigned long)*4; 410 } 411 } else if (op == BITOP_NOT) { 412 while(minlen >= sizeof(unsigned long)*4) { 413 lres[0] = ~lres[0]; 414 lres[1] = ~lres[1]; 415 lres[2] = ~lres[2]; 416 lres[3] = ~lres[3]; 417 lres+=4; 418 j += sizeof(unsigned long)*4; 419 minlen -= sizeof(unsigned long)*4; 420 } 421 } 422 } 423 424 /* j is set to the next byte to process by the previous loop. */ 425 for (; j < maxlen; j++) { 426 output = (len[0] <= j) ? 0 : src[0][j]; 427 if (op == BITOP_NOT) output = ~output; 428 for (i = 1; i < numkeys; i++) { 429 byte = (len[i] <= j) ? 0 : src[i][j]; 430 switch(op) { 431 case BITOP_AND: output &= byte; break; 432 case BITOP_OR: output |= byte; break; 433 case BITOP_XOR: output ^= byte; break; 434 } 435 } 436 res[j] = output; 437 } 438 } 439 for (j = 0; j < numkeys; j++) { 440 if (objects[j]) 441 decrRefCount(objects[j]); 442 } 443 zfree(src); 444 zfree(len); 445 zfree(objects); 446 447 /* Store the computed value into the target key */ 448 if (maxlen) { 449 o = createObject(REDIS_STRING,res); 450 setKey(c->db,targetkey,o); 451 notifyKeyspaceEvent(REDIS_NOTIFY_STRING,"set",targetkey,c->db->id); 452 decrRefCount(o); 453 } else if (dbDelete(c->db,targetkey)) { 454 signalModifiedKey(c->db,targetkey); 455 notifyKeyspaceEvent(REDIS_NOTIFY_GENERIC,"del",targetkey,c->db->id); 456 } 457 server.dirty++; 458 addReplyLongLong(c,maxlen); /* Return the output string length in bytes. */ 459 } 460 461 /* BITCOUNT key [start end] */ 462 void bitcountCommand(redisClient *c) { 463 robj *o; 464 long start, end, strlen; 465 unsigned char *p; 466 char llbuf[32]; 467 468 /* Lookup, check for type, and return 0 for non existing keys. */ 469 if ((o = lookupKeyReadOrReply(c,c->argv[1],shared.czero)) == NULL || 470 checkType(c,o,REDIS_STRING)) return; 471 472 /* Set the 'p' pointer to the string, that can be just a stack allocated 473 * array if our string was integer encoded. */ 474 if (o->encoding == REDIS_ENCODING_INT) { 475 p = (unsigned char*) llbuf; 476 strlen = ll2string(llbuf,sizeof(llbuf),(long)o->ptr); 477 } else { 478 p = (unsigned char*) o->ptr; 479 strlen = sdslen(o->ptr); 480 } 481 482 /* Parse start/end range if any. */ 483 if (c->argc == 4) { 484 if (getLongFromObjectOrReply(c,c->argv[2],&start,NULL) != REDIS_OK) 485 return; 486 if (getLongFromObjectOrReply(c,c->argv[3],&end,NULL) != REDIS_OK) 487 return; 488 /* Convert negative indexes */ 489 if (start < 0) start = strlen+start; 490 if (end < 0) end = strlen+end; 491 if (start < 0) start = 0; 492 if (end < 0) end = 0; 493 if (end >= strlen) end = strlen-1; 494 } else if (c->argc == 2) { 495 /* The whole string. */ 496 start = 0; 497 end = strlen-1; 498 } else { 499 /* Syntax error. */ 500 addReply(c,shared.syntaxerr); 501 return; 502 } 503 504 /* Precondition: end >= 0 && end < strlen, so the only condition where 505 * zero can be returned is: start > end. */ 506 if (start > end) { 507 addReply(c,shared.czero); 508 } else { 509 long bytes = end-start+1; 510 511 addReplyLongLong(c,redisPopcount(p+start,bytes)); 512 } 513 } 514 515 /* BITPOS key bit [start [end]] */ 516 void bitposCommand(redisClient *c) { 517 robj *o; 518 long bit, start, end, strlen; 519 unsigned char *p; 520 char llbuf[32]; 521 int end_given = 0; 522 523 /* Parse the bit argument to understand what we are looking for, set 524 * or clear bits. */ 525 if (getLongFromObjectOrReply(c,c->argv[2],&bit,NULL) != REDIS_OK) 526 return; 527 if (bit != 0 && bit != 1) { 528 addReplyError(c, "The bit argument must be 1 or 0."); 529 return; 530 } 531 532 /* If the key does not exist, from our point of view it is an infinite 533 * array of 0 bits. If the user is looking for the fist clear bit return 0, 534 * If the user is looking for the first set bit, return -1. */ 535 if ((o = lookupKeyRead(c->db,c->argv[1])) == NULL) { 536 addReplyLongLong(c, bit ? -1 : 0); 537 return; 538 } 539 if (checkType(c,o,REDIS_STRING)) return; 540 541 /* Set the 'p' pointer to the string, that can be just a stack allocated 542 * array if our string was integer encoded. */ 543 if (o->encoding == REDIS_ENCODING_INT) { 544 p = (unsigned char*) llbuf; 545 strlen = ll2string(llbuf,sizeof(llbuf),(long)o->ptr); 546 } else { 547 p = (unsigned char*) o->ptr; 548 strlen = sdslen(o->ptr); 549 } 550 551 /* Parse start/end range if any. */ 552 if (c->argc == 4 || c->argc == 5) { 553 if (getLongFromObjectOrReply(c,c->argv[3],&start,NULL) != REDIS_OK) 554 return; 555 if (c->argc == 5) { 556 if (getLongFromObjectOrReply(c,c->argv[4],&end,NULL) != REDIS_OK) 557 return; 558 end_given = 1; 559 } else { 560 end = strlen-1; 561 } 562 /* Convert negative indexes */ 563 if (start < 0) start = strlen+start; 564 if (end < 0) end = strlen+end; 565 if (start < 0) start = 0; 566 if (end < 0) end = 0; 567 if (end >= strlen) end = strlen-1; 568 } else if (c->argc == 3) { 569 /* The whole string. */ 570 start = 0; 571 end = strlen-1; 572 } else { 573 /* Syntax error. */ 574 addReply(c,shared.syntaxerr); 575 return; 576 } 577 578 /* For empty ranges (start > end) we return -1 as an empty range does 579 * not contain a 0 nor a 1. */ 580 if (start > end) { 581 addReplyLongLong(c, -1); 582 } else { 583 long bytes = end-start+1; 584 long pos = redisBitpos(p+start,bytes,bit); 585 586 /* If we are looking for clear bits, and the user specified an exact 587 * range with start-end, we can't consider the right of the range as 588 * zero padded (as we do when no explicit end is given). 589 * 590 * So if redisBitpos() returns the first bit outside the range, 591 * we return -1 to the caller, to mean, in the specified range there 592 * is not a single "0" bit. */ 593 if (end_given && bit == 0 && pos == bytes*8) { 594 addReplyLongLong(c,-1); 595 return; 596 } 597 if (pos != -1) pos += start*8; /* Adjust for the bytes we skipped. */ 598 addReplyLongLong(c,pos); 599 } 600 } 601