[redis.git] / src / bitops.c

/* Bit operations.
 *
 * Copyright (c) 2009-2012, Salvatore Sanfilippo <antirez at gmail dot com>
 * 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"

/* -----------------------------------------------------------------------------
 * 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 16 bytes at a time */
    while(count>=16) {
        uint32_t aux1, aux2, aux3, aux4;

        aux1 = *p4++;
        aux2 = *p4++;
        aux3 = *p4++;
        aux4 = *p4++;
        count -= 16;

        aux1 = aux1 - ((aux1 >> 1) & 0x55555555);
        aux1 = (aux1 & 0x33333333) + ((aux1 >> 2) & 0x33333333);
        aux2 = aux2 - ((aux2 >> 1) & 0x55555555);
        aux2 = (aux2 & 0x33333333) + ((aux2 >> 2) & 0x33333333);
        aux3 = aux3 - ((aux3 >> 1) & 0x55555555);
        aux3 = (aux3 & 0x33333333) + ((aux3 >> 2) & 0x33333333);
        aux4 = aux4 - ((aux4 >> 1) & 0x55555555);
        aux4 = (aux4 & 0x33333333) + ((aux4 >> 2) & 0x33333333);
        bits += ((((aux1 + (aux1 >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24) +
                ((((aux2 + (aux2 >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24) +
                ((((aux3 + (aux3 >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24) +
                ((((aux4 + (aux4 >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24);
    }
    /* 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 = ((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);
    ((uint8_t*)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 = ((uint8_t*)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;
    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. */
    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);
    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;
        }
        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. */
    if (maxlen) {
        res = (unsigned char*) sdsnewlen(NULL,maxlen);
        unsigned char output, byte;
        long i;

        /* 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++) {
                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;
        }
    }
    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) {
        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, strlen;
    unsigned char *p;
    char llbuf[32];

    /* 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 (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));
    }
}
Commit	Line	Data
d288ee65	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
84ec6706	31	#include "redis.h"
	32
	33	/* -----------------------------------------------------------------------------
7ffa248c	34	* Helpers and low level bit functions.
84ec6706	35	* -------------------------------------------------------------------------- */
84ec6706	36
84ec6706	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) >= (51210241024))
	49	{
	50	addReplyError(c,err);
	51	return REDIS_ERR;
	52	}
	53
	54	*offset = (size_t)loffset;
	55	return REDIS_OK;
	56	}
	57
7ffa248c	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;
d12a68d4	63	unsigned char *p;
d12a68d4	64	uint32_t *p4 = s;
7ffa248c	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};
7ffa248c	66
c19bfe9f	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);
d12a68d4	89	}
	90	/* Count the remaining bytes */
	91	p = (unsigned char*)p4;
7ffa248c	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
84ec6706	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 */
82675c86	147	byteval = ((uint8_t*)o->ptr)[byte];
84ec6706	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);
82675c86	154	((uint8_t*)o->ptr)[byte] = byteval;
84ec6706	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))
82675c86	181	bitval = ((uint8_t*)o->ptr)[byte] & (1 << bit);
84ec6706	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;
f0d962c0	192	robj *objects; / Array of soruce objects. */
84ec6706	193	unsigned char *src; / Array of source strings pointers. */
84ec6706	194	long len, maxlen = 0; / Array of length of src strings, and max len. */
8bbc0768	195	long minlen = 0; /* Min len among the input keys. */
84ec6706	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);
f0d962c0	222	objects = zmalloc(sizeof(robj) numkeys);
84ec6706	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) {
f0d962c0	227	objects[j] = NULL;
84ec6706	228	src[j] = NULL;
84ec6706	229	len[j] = 0;
8f0658cd	230	minlen = 0;
84ec6706	231	continue;
	232	}
	233	/* Return an error if one of the keys is not a string. */
	234	if (checkType(c,o,REDIS_STRING)) {
f0d962c0	235	for (j = j-1; j >= 0; j--) {
	236	if (objects[j])
	237	decrRefCount(objects[j]);
	238	}
84ec6706	239	zfree(src);
84ec6706	240	zfree(len);
f0d962c0	241	zfree(objects);
84ec6706	242	return;
84ec6706	243	}
f0d962c0	244	objects[j] = getDecodedObject(o);
	245	src[j] = objects[j]->ptr;
	246	len[j] = sdslen(objects[j]->ptr);
84ec6706	247	if (len[j] > maxlen) maxlen = len[j];
8bbc0768	248	if (j == 0 \|\| len[j] < minlen) minlen = len[j];
84ec6706	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
8bbc0768	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++) {
84ec6706	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	}
f0d962c0	337	for (j = 0; j < numkeys; j++) {
	338	if (objects[j])
	339	decrRefCount(objects[j]);
	340	}
84ec6706	341	zfree(src);
84ec6706	342	zfree(len);
f0d962c0	343	zfree(objects);
84ec6706	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) {
84ec6706	359	robj *o;
4c3d4190	360	long start, end, strlen;
84ec6706	361	unsigned char *p;
84ec6706	362	char llbuf[32];
84ec6706	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;
4c3d4190	389	if (end >= strlen) end = strlen-1;
84ec6706	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 {
7ffa248c	405	long bytes = end-start+1;
84ec6706	406
7ffa248c	407	addReplyLongLong(c,popcount(p+start,bytes));
84ec6706	408	}
84ec6706	409	}