| 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 arguemnt |
| 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 | long popcount(void *s, long count) { |
| 62 | long bits = 0; |
| 63 | unsigned char *p; |
| 64 | uint32_t *p4 = s; |
| 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 bits 16 bytes at a time */ |
| 68 | while(count>=16) { |
| 69 | uint32_t aux1, aux2, aux3, aux4; |
| 70 | |
| 71 | aux1 = *p4++; |
| 72 | aux2 = *p4++; |
| 73 | aux3 = *p4++; |
| 74 | aux4 = *p4++; |
| 75 | count -= 16; |
| 76 | |
| 77 | aux1 = aux1 - ((aux1 >> 1) & 0x55555555); |
| 78 | aux1 = (aux1 & 0x33333333) + ((aux1 >> 2) & 0x33333333); |
| 79 | aux2 = aux2 - ((aux2 >> 1) & 0x55555555); |
| 80 | aux2 = (aux2 & 0x33333333) + ((aux2 >> 2) & 0x33333333); |
| 81 | aux3 = aux3 - ((aux3 >> 1) & 0x55555555); |
| 82 | aux3 = (aux3 & 0x33333333) + ((aux3 >> 2) & 0x33333333); |
| 83 | aux4 = aux4 - ((aux4 >> 1) & 0x55555555); |
| 84 | aux4 = (aux4 & 0x33333333) + ((aux4 >> 2) & 0x33333333); |
| 85 | bits += ((((aux1 + (aux1 >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24) + |
| 86 | ((((aux2 + (aux2 >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24) + |
| 87 | ((((aux3 + (aux3 >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24) + |
| 88 | ((((aux4 + (aux4 >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24); |
| 89 | } |
| 90 | /* Count the remaining bytes */ |
| 91 | p = (unsigned char*)p4; |
| 92 | while(count--) bits += bitsinbyte[*p++]; |
| 93 | return bits; |
| 94 | } |
| 95 | |
| 96 | /* ----------------------------------------------------------------------------- |
| 97 | * Bits related string commands: GETBIT, SETBIT, BITCOUNT, BITOP. |
| 98 | * -------------------------------------------------------------------------- */ |
| 99 | |
| 100 | #define BITOP_AND 0 |
| 101 | #define BITOP_OR 1 |
| 102 | #define BITOP_XOR 2 |
| 103 | #define BITOP_NOT 3 |
| 104 | |
| 105 | /* SETBIT key offset bitvalue */ |
| 106 | void setbitCommand(redisClient *c) { |
| 107 | robj *o; |
| 108 | char *err = "bit is not an integer or out of range"; |
| 109 | size_t bitoffset; |
| 110 | int byte, bit; |
| 111 | int byteval, bitval; |
| 112 | long on; |
| 113 | |
| 114 | if (getBitOffsetFromArgument(c,c->argv[2],&bitoffset) != REDIS_OK) |
| 115 | return; |
| 116 | |
| 117 | if (getLongFromObjectOrReply(c,c->argv[3],&on,err) != REDIS_OK) |
| 118 | return; |
| 119 | |
| 120 | /* Bits can only be set or cleared... */ |
| 121 | if (on & ~1) { |
| 122 | addReplyError(c,err); |
| 123 | return; |
| 124 | } |
| 125 | |
| 126 | o = lookupKeyWrite(c->db,c->argv[1]); |
| 127 | if (o == NULL) { |
| 128 | o = createObject(REDIS_STRING,sdsempty()); |
| 129 | dbAdd(c->db,c->argv[1],o); |
| 130 | } else { |
| 131 | if (checkType(c,o,REDIS_STRING)) return; |
| 132 | |
| 133 | /* Create a copy when the object is shared or encoded. */ |
| 134 | if (o->refcount != 1 || o->encoding != REDIS_ENCODING_RAW) { |
| 135 | robj *decoded = getDecodedObject(o); |
| 136 | o = createStringObject(decoded->ptr, sdslen(decoded->ptr)); |
| 137 | decrRefCount(decoded); |
| 138 | dbOverwrite(c->db,c->argv[1],o); |
| 139 | } |
| 140 | } |
| 141 | |
| 142 | /* Grow sds value to the right length if necessary */ |
| 143 | byte = bitoffset >> 3; |
| 144 | o->ptr = sdsgrowzero(o->ptr,byte+1); |
| 145 | |
| 146 | /* Get current values */ |
| 147 | byteval = ((uint8_t*)o->ptr)[byte]; |
| 148 | bit = 7 - (bitoffset & 0x7); |
| 149 | bitval = byteval & (1 << bit); |
| 150 | |
| 151 | /* Update byte with new bit value and return original value */ |
| 152 | byteval &= ~(1 << bit); |
| 153 | byteval |= ((on & 0x1) << bit); |
| 154 | ((uint8_t*)o->ptr)[byte] = byteval; |
| 155 | signalModifiedKey(c->db,c->argv[1]); |
| 156 | server.dirty++; |
| 157 | addReply(c, bitval ? shared.cone : shared.czero); |
| 158 | } |
| 159 | |
| 160 | /* GETBIT key offset */ |
| 161 | void getbitCommand(redisClient *c) { |
| 162 | robj *o; |
| 163 | char llbuf[32]; |
| 164 | size_t bitoffset; |
| 165 | size_t byte, bit; |
| 166 | size_t bitval = 0; |
| 167 | |
| 168 | if (getBitOffsetFromArgument(c,c->argv[2],&bitoffset) != REDIS_OK) |
| 169 | return; |
| 170 | |
| 171 | if ((o = lookupKeyReadOrReply(c,c->argv[1],shared.czero)) == NULL || |
| 172 | checkType(c,o,REDIS_STRING)) return; |
| 173 | |
| 174 | byte = bitoffset >> 3; |
| 175 | bit = 7 - (bitoffset & 0x7); |
| 176 | if (o->encoding != REDIS_ENCODING_RAW) { |
| 177 | if (byte < (size_t)ll2string(llbuf,sizeof(llbuf),(long)o->ptr)) |
| 178 | bitval = llbuf[byte] & (1 << bit); |
| 179 | } else { |
| 180 | if (byte < sdslen(o->ptr)) |
| 181 | bitval = ((uint8_t*)o->ptr)[byte] & (1 << bit); |
| 182 | } |
| 183 | |
| 184 | addReply(c, bitval ? shared.cone : shared.czero); |
| 185 | } |
| 186 | |
| 187 | /* BITOP op_name target_key src_key1 src_key2 src_key3 ... src_keyN */ |
| 188 | void bitopCommand(redisClient *c) { |
| 189 | char *opname = c->argv[1]->ptr; |
| 190 | robj *o, *targetkey = c->argv[2]; |
| 191 | long op, j, numkeys; |
| 192 | robj **objects; /* Array of soruce objects. */ |
| 193 | unsigned char **src; /* Array of source strings pointers. */ |
| 194 | long *len, maxlen = 0; /* Array of length of src strings, and max len. */ |
| 195 | long minlen = 0; /* Min len among the input keys. */ |
| 196 | unsigned char *res = NULL; /* Resulting string. */ |
| 197 | |
| 198 | /* Parse the operation name. */ |
| 199 | if ((opname[0] == 'a' || opname[0] == 'A') && !strcasecmp(opname,"and")) |
| 200 | op = BITOP_AND; |
| 201 | else if((opname[0] == 'o' || opname[0] == 'O') && !strcasecmp(opname,"or")) |
| 202 | op = BITOP_OR; |
| 203 | else if((opname[0] == 'x' || opname[0] == 'X') && !strcasecmp(opname,"xor")) |
| 204 | op = BITOP_XOR; |
| 205 | else if((opname[0] == 'n' || opname[0] == 'N') && !strcasecmp(opname,"not")) |
| 206 | op = BITOP_NOT; |
| 207 | else { |
| 208 | addReply(c,shared.syntaxerr); |
| 209 | return; |
| 210 | } |
| 211 | |
| 212 | /* Sanity check: NOT accepts only a single key argument. */ |
| 213 | if (op == BITOP_NOT && c->argc != 4) { |
| 214 | addReplyError(c,"BITOP NOT must be called with a single source key."); |
| 215 | return; |
| 216 | } |
| 217 | |
| 218 | /* Lookup keys, and store pointers to the string objects into an array. */ |
| 219 | numkeys = c->argc - 3; |
| 220 | src = zmalloc(sizeof(unsigned char*) * numkeys); |
| 221 | len = zmalloc(sizeof(long) * numkeys); |
| 222 | objects = zmalloc(sizeof(robj*) * numkeys); |
| 223 | for (j = 0; j < numkeys; j++) { |
| 224 | o = lookupKeyRead(c->db,c->argv[j+3]); |
| 225 | /* Handle non-existing keys as empty strings. */ |
| 226 | if (o == NULL) { |
| 227 | objects[j] = NULL; |
| 228 | src[j] = NULL; |
| 229 | len[j] = 0; |
| 230 | minlen = 0; |
| 231 | continue; |
| 232 | } |
| 233 | /* Return an error if one of the keys is not a string. */ |
| 234 | if (checkType(c,o,REDIS_STRING)) { |
| 235 | for (j = j-1; j >= 0; j--) { |
| 236 | if (objects[j]) |
| 237 | decrRefCount(objects[j]); |
| 238 | } |
| 239 | zfree(src); |
| 240 | zfree(len); |
| 241 | zfree(objects); |
| 242 | return; |
| 243 | } |
| 244 | objects[j] = getDecodedObject(o); |
| 245 | src[j] = objects[j]->ptr; |
| 246 | len[j] = sdslen(objects[j]->ptr); |
| 247 | if (len[j] > maxlen) maxlen = len[j]; |
| 248 | if (j == 0 || len[j] < minlen) minlen = len[j]; |
| 249 | } |
| 250 | |
| 251 | /* Compute the bit operation, if at least one string is not empty. */ |
| 252 | if (maxlen) { |
| 253 | res = (unsigned char*) sdsnewlen(NULL,maxlen); |
| 254 | unsigned char output, byte; |
| 255 | long i; |
| 256 | |
| 257 | /* Fast path: as far as we have data for all the input bitmaps we |
| 258 | * can take a fast path that performs much better than the |
| 259 | * vanilla algorithm. */ |
| 260 | j = 0; |
| 261 | if (minlen && numkeys <= 16) { |
| 262 | unsigned long *lp[16]; |
| 263 | unsigned long *lres = (unsigned long*) res; |
| 264 | |
| 265 | /* Note: sds pointer is always aligned to 8 byte boundary. */ |
| 266 | memcpy(lp,src,sizeof(unsigned long*)*numkeys); |
| 267 | memcpy(res,src[0],minlen); |
| 268 | |
| 269 | /* Different branches per different operations for speed (sorry). */ |
| 270 | if (op == BITOP_AND) { |
| 271 | while(minlen >= sizeof(unsigned long)*4) { |
| 272 | for (i = 1; i < numkeys; i++) { |
| 273 | lres[0] &= lp[i][0]; |
| 274 | lres[1] &= lp[i][1]; |
| 275 | lres[2] &= lp[i][2]; |
| 276 | lres[3] &= lp[i][3]; |
| 277 | lp[i]+=4; |
| 278 | } |
| 279 | lres+=4; |
| 280 | j += sizeof(unsigned long)*4; |
| 281 | minlen -= sizeof(unsigned long)*4; |
| 282 | } |
| 283 | } else if (op == BITOP_OR) { |
| 284 | while(minlen >= sizeof(unsigned long)*4) { |
| 285 | for (i = 1; i < numkeys; i++) { |
| 286 | lres[0] |= lp[i][0]; |
| 287 | lres[1] |= lp[i][1]; |
| 288 | lres[2] |= lp[i][2]; |
| 289 | lres[3] |= lp[i][3]; |
| 290 | lp[i]+=4; |
| 291 | } |
| 292 | lres+=4; |
| 293 | j += sizeof(unsigned long)*4; |
| 294 | minlen -= sizeof(unsigned long)*4; |
| 295 | } |
| 296 | } else if (op == BITOP_XOR) { |
| 297 | while(minlen >= sizeof(unsigned long)*4) { |
| 298 | for (i = 1; i < numkeys; i++) { |
| 299 | lres[0] ^= lp[i][0]; |
| 300 | lres[1] ^= lp[i][1]; |
| 301 | lres[2] ^= lp[i][2]; |
| 302 | lres[3] ^= lp[i][3]; |
| 303 | lp[i]+=4; |
| 304 | } |
| 305 | lres+=4; |
| 306 | j += sizeof(unsigned long)*4; |
| 307 | minlen -= sizeof(unsigned long)*4; |
| 308 | } |
| 309 | } else if (op == BITOP_NOT) { |
| 310 | while(minlen >= sizeof(unsigned long)*4) { |
| 311 | lres[0] = ~lres[0]; |
| 312 | lres[1] = ~lres[1]; |
| 313 | lres[2] = ~lres[2]; |
| 314 | lres[3] = ~lres[3]; |
| 315 | lres+=4; |
| 316 | j += sizeof(unsigned long)*4; |
| 317 | minlen -= sizeof(unsigned long)*4; |
| 318 | } |
| 319 | } |
| 320 | } |
| 321 | |
| 322 | /* j is set to the next byte to process by the previous loop. */ |
| 323 | for (; j < maxlen; j++) { |
| 324 | output = (len[0] <= j) ? 0 : src[0][j]; |
| 325 | if (op == BITOP_NOT) output = ~output; |
| 326 | for (i = 1; i < numkeys; i++) { |
| 327 | byte = (len[i] <= j) ? 0 : src[i][j]; |
| 328 | switch(op) { |
| 329 | case BITOP_AND: output &= byte; break; |
| 330 | case BITOP_OR: output |= byte; break; |
| 331 | case BITOP_XOR: output ^= byte; break; |
| 332 | } |
| 333 | } |
| 334 | res[j] = output; |
| 335 | } |
| 336 | } |
| 337 | for (j = 0; j < numkeys; j++) { |
| 338 | if (objects[j]) |
| 339 | decrRefCount(objects[j]); |
| 340 | } |
| 341 | zfree(src); |
| 342 | zfree(len); |
| 343 | zfree(objects); |
| 344 | |
| 345 | /* Store the computed value into the target key */ |
| 346 | if (maxlen) { |
| 347 | o = createObject(REDIS_STRING,res); |
| 348 | setKey(c->db,targetkey,o); |
| 349 | decrRefCount(o); |
| 350 | } else if (dbDelete(c->db,targetkey)) { |
| 351 | signalModifiedKey(c->db,targetkey); |
| 352 | } |
| 353 | server.dirty++; |
| 354 | addReplyLongLong(c,maxlen); /* Return the output string length in bytes. */ |
| 355 | } |
| 356 | |
| 357 | /* BITCOUNT key [start end] */ |
| 358 | void bitcountCommand(redisClient *c) { |
| 359 | robj *o; |
| 360 | long start, end, strlen; |
| 361 | unsigned char *p; |
| 362 | char llbuf[32]; |
| 363 | |
| 364 | /* Lookup, check for type, and return 0 for non existing keys. */ |
| 365 | if ((o = lookupKeyReadOrReply(c,c->argv[1],shared.czero)) == NULL || |
| 366 | checkType(c,o,REDIS_STRING)) return; |
| 367 | |
| 368 | /* Set the 'p' pointer to the string, that can be just a stack allocated |
| 369 | * array if our string was integer encoded. */ |
| 370 | if (o->encoding == REDIS_ENCODING_INT) { |
| 371 | p = (unsigned char*) llbuf; |
| 372 | strlen = ll2string(llbuf,sizeof(llbuf),(long)o->ptr); |
| 373 | } else { |
| 374 | p = (unsigned char*) o->ptr; |
| 375 | strlen = sdslen(o->ptr); |
| 376 | } |
| 377 | |
| 378 | /* Parse start/end range if any. */ |
| 379 | if (c->argc == 4) { |
| 380 | if (getLongFromObjectOrReply(c,c->argv[2],&start,NULL) != REDIS_OK) |
| 381 | return; |
| 382 | if (getLongFromObjectOrReply(c,c->argv[3],&end,NULL) != REDIS_OK) |
| 383 | return; |
| 384 | /* Convert negative indexes */ |
| 385 | if (start < 0) start = strlen+start; |
| 386 | if (end < 0) end = strlen+end; |
| 387 | if (start < 0) start = 0; |
| 388 | if (end < 0) end = 0; |
| 389 | if (end >= strlen) end = strlen-1; |
| 390 | } else if (c->argc == 2) { |
| 391 | /* The whole string. */ |
| 392 | start = 0; |
| 393 | end = strlen-1; |
| 394 | } else { |
| 395 | /* Syntax error. */ |
| 396 | addReply(c,shared.syntaxerr); |
| 397 | return; |
| 398 | } |
| 399 | |
| 400 | /* Precondition: end >= 0 && end < strlen, so the only condition where |
| 401 | * zero can be returned is: start > end. */ |
| 402 | if (start > end) { |
| 403 | addReply(c,shared.czero); |
| 404 | } else { |
| 405 | long bytes = end-start+1; |
| 406 | |
| 407 | addReplyLongLong(c,popcount(p+start,bytes)); |
| 408 | } |
| 409 | } |