From: antirez Date: Sun, 20 May 2012 09:06:29 +0000 (+0200) Subject: bitop.c renamed bitops.c X-Git-Url: https://git.saurik.com/redis.git/commitdiff_plain/80f8028e3c0d9948c3f1e1eb56cda1dbbf891d02 bitop.c renamed bitops.c bitop.c contains the "Bit related string operations" so it seems more logical to call it bitops instead of bitop. This also makes it matching the name of the test (unit/bitops.tcl). --- diff --git a/src/Makefile b/src/Makefile index f1d9c49d..bffdb30e 100644 --- a/src/Makefile +++ b/src/Makefile @@ -96,7 +96,7 @@ QUIET_LINK = @printf ' %b %b\n' $(LINKCOLOR)LINK$(ENDCOLOR) $(BINCOLOR)$@$(EN endif REDIS_SERVER_NAME= redis-server -REDIS_SERVER_OBJ= adlist.o ae.o anet.o dict.o redis.o sds.o zmalloc.o lzf_c.o lzf_d.o pqsort.o zipmap.o sha1.o ziplist.o release.o networking.o util.o object.o db.o replication.o rdb.o t_string.o t_list.o t_set.o t_zset.o t_hash.o config.o aof.o pubsub.o multi.o debug.o sort.o intset.o syncio.o cluster.o crc16.o endianconv.o slowlog.o scripting.o bio.o rio.o rand.o memtest.o crc64.o bitop.o +REDIS_SERVER_OBJ= adlist.o ae.o anet.o dict.o redis.o sds.o zmalloc.o lzf_c.o lzf_d.o pqsort.o zipmap.o sha1.o ziplist.o release.o networking.o util.o object.o db.o replication.o rdb.o t_string.o t_list.o t_set.o t_zset.o t_hash.o config.o aof.o pubsub.o multi.o debug.o sort.o intset.o syncio.o cluster.o crc16.o endianconv.o slowlog.o scripting.o bio.o rio.o rand.o memtest.o crc64.o bitops.o REDIS_CLI_NAME= redis-cli REDIS_CLI_OBJ= anet.o sds.o adlist.o redis-cli.o zmalloc.o release.o anet.o ae.o REDIS_BENCHMARK_NAME= redis-benchmark diff --git a/src/bitop.c b/src/bitop.c deleted file mode 100644 index 053db02b..00000000 --- a/src/bitop.c +++ /dev/null @@ -1,288 +0,0 @@ -#include "redis.h" - -/* ----------------------------------------------------------------------------- - * Helpers and low level bit functions. - * -------------------------------------------------------------------------- */ - -/* This helper function used by GETBIT / SETBIT parses the bit offset arguemnt - * making sure an error is returned if it is negative or if it overflows - * Redis 512 MB limit for the string value. */ -static int getBitOffsetFromArgument(redisClient *c, robj *o, size_t *offset) { - long long loffset; - char *err = "bit offset is not an integer or out of range"; - - if (getLongLongFromObjectOrReply(c,o,&loffset,err) != REDIS_OK) - return REDIS_ERR; - - /* Limit offset to 512MB in bytes */ - if ((loffset < 0) || ((unsigned long long)loffset >> 3) >= (512*1024*1024)) - { - addReplyError(c,err); - return REDIS_ERR; - } - - *offset = (size_t)loffset; - return REDIS_OK; -} - -/* Count number of bits set in the binary array pointed by 's' and long - * 'count' bytes. The implementation of this function is required to - * work with a input string length up to 512 MB. */ -long popcount(void *s, long count) { - long bits = 0; - unsigned char *p; - uint32_t *p4 = s; - 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}; - - /* Count bits four bytes at a time */ - while(count>=4) { - uint32_t aux = *p4++; - count -= 4; -#ifdef __GNUC__ - /* Unsigned int is always >= 4 bytes if compiler is GCC */ - bits += __builtin_popcount(aux); -#else - bits += bitsinbyte[aux&0xff] + - bitsinbyte[(aux>>8)&0xff] + - bitsinbyte[(aux>>16)&0xff] + - bitsinbyte[(aux>>24)&0xff]; -#endif - } - /* Count the remaining bytes */ - p = (unsigned char*)p4; - while(count--) bits += bitsinbyte[*p++]; - return bits; -} - -/* ----------------------------------------------------------------------------- - * Bits related string commands: GETBIT, SETBIT, BITCOUNT, BITOP. - * -------------------------------------------------------------------------- */ - -#define BITOP_AND 0 -#define BITOP_OR 1 -#define BITOP_XOR 2 -#define BITOP_NOT 3 - -/* SETBIT key offset bitvalue */ -void setbitCommand(redisClient *c) { - robj *o; - char *err = "bit is not an integer or out of range"; - size_t bitoffset; - int byte, bit; - int byteval, bitval; - long on; - - if (getBitOffsetFromArgument(c,c->argv[2],&bitoffset) != REDIS_OK) - return; - - if (getLongFromObjectOrReply(c,c->argv[3],&on,err) != REDIS_OK) - return; - - /* Bits can only be set or cleared... */ - if (on & ~1) { - addReplyError(c,err); - return; - } - - o = lookupKeyWrite(c->db,c->argv[1]); - if (o == NULL) { - o = createObject(REDIS_STRING,sdsempty()); - dbAdd(c->db,c->argv[1],o); - } else { - if (checkType(c,o,REDIS_STRING)) return; - - /* Create a copy when the object is shared or encoded. */ - if (o->refcount != 1 || o->encoding != REDIS_ENCODING_RAW) { - robj *decoded = getDecodedObject(o); - o = createStringObject(decoded->ptr, sdslen(decoded->ptr)); - decrRefCount(decoded); - dbOverwrite(c->db,c->argv[1],o); - } - } - - /* Grow sds value to the right length if necessary */ - byte = bitoffset >> 3; - o->ptr = sdsgrowzero(o->ptr,byte+1); - - /* Get current values */ - byteval = ((char*)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; - signalModifiedKey(c->db,c->argv[1]); - server.dirty++; - addReply(c, bitval ? shared.cone : shared.czero); -} - -/* GETBIT key offset */ -void getbitCommand(redisClient *c) { - robj *o; - char llbuf[32]; - size_t bitoffset; - size_t byte, bit; - size_t bitval = 0; - - if (getBitOffsetFromArgument(c,c->argv[2],&bitoffset) != REDIS_OK) - return; - - if ((o = lookupKeyReadOrReply(c,c->argv[1],shared.czero)) == NULL || - checkType(c,o,REDIS_STRING)) return; - - byte = bitoffset >> 3; - bit = 7 - (bitoffset & 0x7); - if (o->encoding != REDIS_ENCODING_RAW) { - if (byte < (size_t)ll2string(llbuf,sizeof(llbuf),(long)o->ptr)) - bitval = llbuf[byte] & (1 << bit); - } else { - if (byte < sdslen(o->ptr)) - bitval = ((char*)o->ptr)[byte] & (1 << bit); - } - - addReply(c, bitval ? shared.cone : shared.czero); -} - -/* BITOP op_name target_key src_key1 src_key2 src_key3 ... src_keyN */ -void bitopCommand(redisClient *c) { - char *opname = c->argv[1]->ptr; - robj *o, *targetkey = c->argv[2]; - long op, j, numkeys; - unsigned char **src; /* Array of source strings pointers. */ - long *len, maxlen = 0; /* Array of length of src strings, and max len. */ - unsigned char *res = NULL; /* Resulting string. */ - - /* Parse the operation name. */ - if ((opname[0] == 'a' || opname[0] == 'A') && !strcasecmp(opname,"and")) - op = BITOP_AND; - else if((opname[0] == 'o' || opname[0] == 'O') && !strcasecmp(opname,"or")) - op = BITOP_OR; - else if((opname[0] == 'x' || opname[0] == 'X') && !strcasecmp(opname,"xor")) - op = BITOP_XOR; - else if((opname[0] == 'n' || opname[0] == 'N') && !strcasecmp(opname,"not")) - op = BITOP_NOT; - else { - addReply(c,shared.syntaxerr); - return; - } - - /* Sanity check: NOT accepts only a single key argument. */ - if (op == BITOP_NOT && c->argc != 4) { - addReplyError(c,"BITOP NOT must be called with a single source key."); - return; - } - - /* Lookup keys, and store pointers to the string objects into an array. */ - numkeys = c->argc - 3; - src = zmalloc(sizeof(unsigned char*) * numkeys); - len = zmalloc(sizeof(long) * 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) { - src[j] = NULL; - len[j] = 0; - continue; - } - /* Return an error if one of the keys is not a string. */ - if (checkType(c,o,REDIS_STRING)) { - zfree(src); - zfree(len); - return; - } - src[j] = o->ptr; - len[j] = sdslen(o->ptr); - if (len[j] > maxlen) maxlen = len[j]; - } - - /* Compute the bit operation, if at least one string is not empty. */ - if (maxlen) { - res = (unsigned char*) sdsnewlen(NULL,maxlen); - unsigned char output, byte; - long i; - - for (j = 0; j < maxlen; j++) { - output = (len[0] <= j) ? 0 : src[0][j]; - if (op == BITOP_NOT) output = ~output; - for (i = 1; i < numkeys; i++) { - byte = (len[i] <= j) ? 0 : src[i][j]; - switch(op) { - case BITOP_AND: output &= byte; break; - case BITOP_OR: output |= byte; break; - case BITOP_XOR: output ^= byte; break; - } - } - res[j] = output; - } - } - zfree(src); - zfree(len); - - /* Store the computed value into the target key */ - if (maxlen) { - o = createObject(REDIS_STRING,res); - setKey(c->db,targetkey,o); - decrRefCount(o); - } else if (dbDelete(c->db,targetkey)) { - signalModifiedKey(c->db,targetkey); - } - server.dirty++; - addReplyLongLong(c,maxlen); /* Return the output string length in bytes. */ -} - -/* BITCOUNT key [start end] */ -void bitcountCommand(redisClient *c) { - robj *o; - long start, end; - 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 || - checkType(c,o,REDIS_STRING)) return; - - /* Set the 'p' pointer to the string, that can be just a stack allocated - * array if our string was integer encoded. */ - if (o->encoding == REDIS_ENCODING_INT) { - p = (unsigned char*) llbuf; - strlen = ll2string(llbuf,sizeof(llbuf),(long)o->ptr); - } else { - p = (unsigned char*) o->ptr; - strlen = sdslen(o->ptr); - } - - /* Parse start/end range if any. */ - if (c->argc == 4) { - if (getLongFromObjectOrReply(c,c->argv[2],&start,NULL) != REDIS_OK) - return; - if (getLongFromObjectOrReply(c,c->argv[3],&end,NULL) != REDIS_OK) - return; - /* Convert negative indexes */ - if (start < 0) start = strlen+start; - if (end < 0) end = strlen+end; - if (start < 0) start = 0; - if (end < 0) end = 0; - if ((unsigned)end >= strlen) end = strlen-1; - } else if (c->argc == 2) { - /* The whole string. */ - start = 0; - end = strlen-1; - } else { - /* Syntax error. */ - addReply(c,shared.syntaxerr); - return; - } - - /* Precondition: end >= 0 && end < strlen, so the only condition where - * zero can be returned is: start > end. */ - if (start > end) { - addReply(c,shared.czero); - } else { - long bytes = end-start+1; - - addReplyLongLong(c,popcount(p+start,bytes)); - } -} diff --git a/src/bitops.c b/src/bitops.c new file mode 100644 index 00000000..053db02b --- /dev/null +++ b/src/bitops.c @@ -0,0 +1,288 @@ +#include "redis.h" + +/* ----------------------------------------------------------------------------- + * Helpers and low level bit functions. + * -------------------------------------------------------------------------- */ + +/* This helper function used by GETBIT / SETBIT parses the bit offset arguemnt + * making sure an error is returned if it is negative or if it overflows + * Redis 512 MB limit for the string value. */ +static int getBitOffsetFromArgument(redisClient *c, robj *o, size_t *offset) { + long long loffset; + char *err = "bit offset is not an integer or out of range"; + + if (getLongLongFromObjectOrReply(c,o,&loffset,err) != REDIS_OK) + return REDIS_ERR; + + /* Limit offset to 512MB in bytes */ + if ((loffset < 0) || ((unsigned long long)loffset >> 3) >= (512*1024*1024)) + { + addReplyError(c,err); + return REDIS_ERR; + } + + *offset = (size_t)loffset; + return REDIS_OK; +} + +/* Count number of bits set in the binary array pointed by 's' and long + * 'count' bytes. The implementation of this function is required to + * work with a input string length up to 512 MB. */ +long popcount(void *s, long count) { + long bits = 0; + unsigned char *p; + uint32_t *p4 = s; + 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}; + + /* Count bits four bytes at a time */ + while(count>=4) { + uint32_t aux = *p4++; + count -= 4; +#ifdef __GNUC__ + /* Unsigned int is always >= 4 bytes if compiler is GCC */ + bits += __builtin_popcount(aux); +#else + bits += bitsinbyte[aux&0xff] + + bitsinbyte[(aux>>8)&0xff] + + bitsinbyte[(aux>>16)&0xff] + + bitsinbyte[(aux>>24)&0xff]; +#endif + } + /* Count the remaining bytes */ + p = (unsigned char*)p4; + while(count--) bits += bitsinbyte[*p++]; + return bits; +} + +/* ----------------------------------------------------------------------------- + * Bits related string commands: GETBIT, SETBIT, BITCOUNT, BITOP. + * -------------------------------------------------------------------------- */ + +#define BITOP_AND 0 +#define BITOP_OR 1 +#define BITOP_XOR 2 +#define BITOP_NOT 3 + +/* SETBIT key offset bitvalue */ +void setbitCommand(redisClient *c) { + robj *o; + char *err = "bit is not an integer or out of range"; + size_t bitoffset; + int byte, bit; + int byteval, bitval; + long on; + + if (getBitOffsetFromArgument(c,c->argv[2],&bitoffset) != REDIS_OK) + return; + + if (getLongFromObjectOrReply(c,c->argv[3],&on,err) != REDIS_OK) + return; + + /* Bits can only be set or cleared... */ + if (on & ~1) { + addReplyError(c,err); + return; + } + + o = lookupKeyWrite(c->db,c->argv[1]); + if (o == NULL) { + o = createObject(REDIS_STRING,sdsempty()); + dbAdd(c->db,c->argv[1],o); + } else { + if (checkType(c,o,REDIS_STRING)) return; + + /* Create a copy when the object is shared or encoded. */ + if (o->refcount != 1 || o->encoding != REDIS_ENCODING_RAW) { + robj *decoded = getDecodedObject(o); + o = createStringObject(decoded->ptr, sdslen(decoded->ptr)); + decrRefCount(decoded); + dbOverwrite(c->db,c->argv[1],o); + } + } + + /* Grow sds value to the right length if necessary */ + byte = bitoffset >> 3; + o->ptr = sdsgrowzero(o->ptr,byte+1); + + /* Get current values */ + byteval = ((char*)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; + signalModifiedKey(c->db,c->argv[1]); + server.dirty++; + addReply(c, bitval ? shared.cone : shared.czero); +} + +/* GETBIT key offset */ +void getbitCommand(redisClient *c) { + robj *o; + char llbuf[32]; + size_t bitoffset; + size_t byte, bit; + size_t bitval = 0; + + if (getBitOffsetFromArgument(c,c->argv[2],&bitoffset) != REDIS_OK) + return; + + if ((o = lookupKeyReadOrReply(c,c->argv[1],shared.czero)) == NULL || + checkType(c,o,REDIS_STRING)) return; + + byte = bitoffset >> 3; + bit = 7 - (bitoffset & 0x7); + if (o->encoding != REDIS_ENCODING_RAW) { + if (byte < (size_t)ll2string(llbuf,sizeof(llbuf),(long)o->ptr)) + bitval = llbuf[byte] & (1 << bit); + } else { + if (byte < sdslen(o->ptr)) + bitval = ((char*)o->ptr)[byte] & (1 << bit); + } + + addReply(c, bitval ? shared.cone : shared.czero); +} + +/* BITOP op_name target_key src_key1 src_key2 src_key3 ... src_keyN */ +void bitopCommand(redisClient *c) { + char *opname = c->argv[1]->ptr; + robj *o, *targetkey = c->argv[2]; + long op, j, numkeys; + unsigned char **src; /* Array of source strings pointers. */ + long *len, maxlen = 0; /* Array of length of src strings, and max len. */ + unsigned char *res = NULL; /* Resulting string. */ + + /* Parse the operation name. */ + if ((opname[0] == 'a' || opname[0] == 'A') && !strcasecmp(opname,"and")) + op = BITOP_AND; + else if((opname[0] == 'o' || opname[0] == 'O') && !strcasecmp(opname,"or")) + op = BITOP_OR; + else if((opname[0] == 'x' || opname[0] == 'X') && !strcasecmp(opname,"xor")) + op = BITOP_XOR; + else if((opname[0] == 'n' || opname[0] == 'N') && !strcasecmp(opname,"not")) + op = BITOP_NOT; + else { + addReply(c,shared.syntaxerr); + return; + } + + /* Sanity check: NOT accepts only a single key argument. */ + if (op == BITOP_NOT && c->argc != 4) { + addReplyError(c,"BITOP NOT must be called with a single source key."); + return; + } + + /* Lookup keys, and store pointers to the string objects into an array. */ + numkeys = c->argc - 3; + src = zmalloc(sizeof(unsigned char*) * numkeys); + len = zmalloc(sizeof(long) * 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) { + src[j] = NULL; + len[j] = 0; + continue; + } + /* Return an error if one of the keys is not a string. */ + if (checkType(c,o,REDIS_STRING)) { + zfree(src); + zfree(len); + return; + } + src[j] = o->ptr; + len[j] = sdslen(o->ptr); + if (len[j] > maxlen) maxlen = len[j]; + } + + /* Compute the bit operation, if at least one string is not empty. */ + if (maxlen) { + res = (unsigned char*) sdsnewlen(NULL,maxlen); + unsigned char output, byte; + long i; + + for (j = 0; j < maxlen; j++) { + output = (len[0] <= j) ? 0 : src[0][j]; + if (op == BITOP_NOT) output = ~output; + for (i = 1; i < numkeys; i++) { + byte = (len[i] <= j) ? 0 : src[i][j]; + switch(op) { + case BITOP_AND: output &= byte; break; + case BITOP_OR: output |= byte; break; + case BITOP_XOR: output ^= byte; break; + } + } + res[j] = output; + } + } + zfree(src); + zfree(len); + + /* Store the computed value into the target key */ + if (maxlen) { + o = createObject(REDIS_STRING,res); + setKey(c->db,targetkey,o); + decrRefCount(o); + } else if (dbDelete(c->db,targetkey)) { + signalModifiedKey(c->db,targetkey); + } + server.dirty++; + addReplyLongLong(c,maxlen); /* Return the output string length in bytes. */ +} + +/* BITCOUNT key [start end] */ +void bitcountCommand(redisClient *c) { + robj *o; + long start, end; + 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 || + checkType(c,o,REDIS_STRING)) return; + + /* Set the 'p' pointer to the string, that can be just a stack allocated + * array if our string was integer encoded. */ + if (o->encoding == REDIS_ENCODING_INT) { + p = (unsigned char*) llbuf; + strlen = ll2string(llbuf,sizeof(llbuf),(long)o->ptr); + } else { + p = (unsigned char*) o->ptr; + strlen = sdslen(o->ptr); + } + + /* Parse start/end range if any. */ + if (c->argc == 4) { + if (getLongFromObjectOrReply(c,c->argv[2],&start,NULL) != REDIS_OK) + return; + if (getLongFromObjectOrReply(c,c->argv[3],&end,NULL) != REDIS_OK) + return; + /* Convert negative indexes */ + if (start < 0) start = strlen+start; + if (end < 0) end = strlen+end; + if (start < 0) start = 0; + if (end < 0) end = 0; + if ((unsigned)end >= strlen) end = strlen-1; + } else if (c->argc == 2) { + /* The whole string. */ + start = 0; + end = strlen-1; + } else { + /* Syntax error. */ + addReply(c,shared.syntaxerr); + return; + } + + /* Precondition: end >= 0 && end < strlen, so the only condition where + * zero can be returned is: start > end. */ + if (start > end) { + addReply(c,shared.czero); + } else { + long bytes = end-start+1; + + addReplyLongLong(c,popcount(p+start,bytes)); + } +}