X-Git-Url: https://git.saurik.com/redis.git/blobdiff_plain/7c34643f154f543e1eef7c9855fb8d657146c646..c8852ebf191387779275a70b5540f30976b9ef1f:/src/bitops.c diff --git a/src/bitops.c b/src/bitops.c index 0b9c7b02..3ef0a8f3 100644 --- a/src/bitops.c +++ b/src/bitops.c @@ -1,3 +1,33 @@ +/* Bit operations. + * + * Copyright (c) 2009-2012, Salvatore Sanfilippo + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * * Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * * Neither the name of Redis nor the names of its contributors may be used + * to endorse or promote products derived from this software without + * specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + #include "redis.h" /* ----------------------------------------------------------------------------- @@ -114,14 +144,14 @@ void setbitCommand(redisClient *c) { o->ptr = sdsgrowzero(o->ptr,byte+1); /* Get current values */ - byteval = ((char*)o->ptr)[byte]; + byteval = ((uint8_t*)o->ptr)[byte]; bit = 7 - (bitoffset & 0x7); bitval = byteval & (1 << bit); /* Update byte with new bit value and return original value */ byteval &= ~(1 << bit); byteval |= ((on & 0x1) << bit); - ((char*)o->ptr)[byte] = byteval; + ((uint8_t*)o->ptr)[byte] = byteval; signalModifiedKey(c->db,c->argv[1]); server.dirty++; addReply(c, bitval ? shared.cone : shared.czero); @@ -148,7 +178,7 @@ void getbitCommand(redisClient *c) { bitval = llbuf[byte] & (1 << bit); } else { if (byte < sdslen(o->ptr)) - bitval = ((char*)o->ptr)[byte] & (1 << bit); + bitval = ((uint8_t*)o->ptr)[byte] & (1 << bit); } addReply(c, bitval ? shared.cone : shared.czero); @@ -159,8 +189,10 @@ void bitopCommand(redisClient *c) { char *opname = c->argv[1]->ptr; robj *o, *targetkey = c->argv[2]; long op, j, numkeys; + robj **objects; /* Array of soruce objects. */ unsigned char **src; /* Array of source strings pointers. */ long *len, maxlen = 0; /* Array of length of src strings, and max len. */ + long minlen = 0; /* Min len among the input keys. */ unsigned char *res = NULL; /* Resulting string. */ /* Parse the operation name. */ @@ -187,23 +219,33 @@ void bitopCommand(redisClient *c) { numkeys = c->argc - 3; src = zmalloc(sizeof(unsigned char*) * numkeys); len = zmalloc(sizeof(long) * numkeys); + objects = zmalloc(sizeof(robj*) * numkeys); for (j = 0; j < numkeys; j++) { o = lookupKeyRead(c->db,c->argv[j+3]); /* Handle non-existing keys as empty strings. */ if (o == NULL) { + objects[j] = NULL; src[j] = NULL; len[j] = 0; + minlen = 0; continue; } /* Return an error if one of the keys is not a string. */ if (checkType(c,o,REDIS_STRING)) { + for (j = j-1; j >= 0; j--) { + if (objects[j]) + decrRefCount(objects[j]); + } zfree(src); zfree(len); + zfree(objects); return; } - src[j] = o->ptr; - len[j] = sdslen(o->ptr); + objects[j] = getDecodedObject(o); + src[j] = objects[j]->ptr; + len[j] = sdslen(objects[j]->ptr); if (len[j] > maxlen) maxlen = len[j]; + if (j == 0 || len[j] < minlen) minlen = len[j]; } /* Compute the bit operation, if at least one string is not empty. */ @@ -212,7 +254,73 @@ void bitopCommand(redisClient *c) { unsigned char output, byte; long i; - for (j = 0; j < maxlen; j++) { + /* Fast path: as far as we have data for all the input bitmaps we + * can take a fast path that performs much better than the + * vanilla algorithm. */ + j = 0; + if (minlen && numkeys <= 16) { + unsigned long *lp[16]; + unsigned long *lres = (unsigned long*) res; + + /* Note: sds pointer is always aligned to 8 byte boundary. */ + memcpy(lp,src,sizeof(unsigned long*)*numkeys); + memcpy(res,src[0],minlen); + + /* Different branches per different operations for speed (sorry). */ + if (op == BITOP_AND) { + while(minlen >= sizeof(unsigned long)*4) { + for (i = 1; i < numkeys; i++) { + lres[0] &= lp[i][0]; + lres[1] &= lp[i][1]; + lres[2] &= lp[i][2]; + lres[3] &= lp[i][3]; + lp[i]+=4; + } + lres+=4; + j += sizeof(unsigned long)*4; + minlen -= sizeof(unsigned long)*4; + } + } else if (op == BITOP_OR) { + while(minlen >= sizeof(unsigned long)*4) { + for (i = 1; i < numkeys; i++) { + lres[0] |= lp[i][0]; + lres[1] |= lp[i][1]; + lres[2] |= lp[i][2]; + lres[3] |= lp[i][3]; + lp[i]+=4; + } + lres+=4; + j += sizeof(unsigned long)*4; + minlen -= sizeof(unsigned long)*4; + } + } else if (op == BITOP_XOR) { + while(minlen >= sizeof(unsigned long)*4) { + for (i = 1; i < numkeys; i++) { + lres[0] ^= lp[i][0]; + lres[1] ^= lp[i][1]; + lres[2] ^= lp[i][2]; + lres[3] ^= lp[i][3]; + lp[i]+=4; + } + lres+=4; + j += sizeof(unsigned long)*4; + minlen -= sizeof(unsigned long)*4; + } + } else if (op == BITOP_NOT) { + while(minlen >= sizeof(unsigned long)*4) { + lres[0] = ~lres[0]; + lres[1] = ~lres[1]; + lres[2] = ~lres[2]; + lres[3] = ~lres[3]; + lres+=4; + j += sizeof(unsigned long)*4; + minlen -= sizeof(unsigned long)*4; + } + } + } + + /* j is set to the next byte to process by the previous loop. */ + for (; j < maxlen; j++) { output = (len[0] <= j) ? 0 : src[0][j]; if (op == BITOP_NOT) output = ~output; for (i = 1; i < numkeys; i++) { @@ -226,8 +334,13 @@ void bitopCommand(redisClient *c) { res[j] = output; } } + for (j = 0; j < numkeys; j++) { + if (objects[j]) + decrRefCount(objects[j]); + } zfree(src); zfree(len); + zfree(objects); /* Store the computed value into the target key */ if (maxlen) { @@ -244,10 +357,9 @@ void bitopCommand(redisClient *c) { /* BITCOUNT key [start end] */ void bitcountCommand(redisClient *c) { robj *o; - long start, end; + long start, end, strlen; unsigned char *p; char llbuf[32]; - size_t strlen; /* Lookup, check for type, and return 0 for non existing keys. */ if ((o = lookupKeyReadOrReply(c,c->argv[1],shared.czero)) == NULL || @@ -274,7 +386,7 @@ void bitcountCommand(redisClient *c) { if (end < 0) end = strlen+end; if (start < 0) start = 0; if (end < 0) end = 0; - if ((unsigned)end >= strlen) end = strlen-1; + if (end >= strlen) end = strlen-1; } else if (c->argc == 2) { /* The whole string. */ start = 0;