/* 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 "server.h"

/* -----------------------------------------------------------------------------
 * Helpers and low level bit functions.
 * -------------------------------------------------------------------------- */

/* 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. */
size_t redisPopcount(void *s, PORT_LONG count) {
 size_t bits = 0;
 unsigned char *p = s;
 uint32_t *p4;
 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 initial bytes not aligned to 32 bit. */
 while((PORT_ULONG)p & 3 && count) {
 bits += bitsinbyte[*p++];
 count--;
 }

 /* Count bits 28 bytes at a time */
 p4 = (uint32_t*)p;
 while(count>=28) {
 uint32_t aux1, aux2, aux3, aux4, aux5, aux6, aux7;

 aux1 = *p4++;
 aux2 = *p4++;
 aux3 = *p4++;
 aux4 = *p4++;
 aux5 = *p4++;
 aux6 = *p4++;
 aux7 = *p4++;
 count -= 28;

 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);
 aux5 = aux5 - ((aux5 >> 1) & 0x55555555);
 aux5 = (aux5 & 0x33333333) + ((aux5 >> 2) & 0x33333333);
 aux6 = aux6 - ((aux6 >> 1) & 0x55555555);
 aux6 = (aux6 & 0x33333333) + ((aux6 >> 2) & 0x33333333);
 aux7 = aux7 - ((aux7 >> 1) & 0x55555555);
 aux7 = (aux7 & 0x33333333) + ((aux7 >> 2) & 0x33333333);
 bits += ((((aux1 + (aux1 >> 4)) & 0x0F0F0F0F) +
 ((aux2 + (aux2 >> 4)) & 0x0F0F0F0F) +
 ((aux3 + (aux3 >> 4)) & 0x0F0F0F0F) +
 ((aux4 + (aux4 >> 4)) & 0x0F0F0F0F) +
 ((aux5 + (aux5 >> 4)) & 0x0F0F0F0F) +
 ((aux6 + (aux6 >> 4)) & 0x0F0F0F0F) +
 ((aux7 + (aux7 >> 4)) & 0x0F0F0F0F))* 0x01010101) >> 24;
 }
 /* Count the remaining bytes. */
 p = (unsigned char*)p4;
 while(count--) bits += bitsinbyte[*p++];
 return bits;
}

/* Return the position of the first bit set to one (if 'bit' is 1) or
 * zero (if 'bit' is 0) in the bitmap starting at 's' and long 'count' bytes.
 *
 * The function is guaranteed to return a value >= 0 if 'bit' is 0 since if
 * no zero bit is found, it returns count*8 assuming the string is zero
 * padded on the right. However if 'bit' is 1 it is possible that there is
 * not a single set bit in the bitmap. In this special case -1 is returned. */
PORT_LONG redisBitpos(void *s, PORT_ULONG count, int bit) {
 PORT_ULONG *l;
 unsigned char *c;
 PORT_ULONG skipval, word = 0, one;
 PORT_LONG pos = 0; /* Position of bit, to return to the caller. */
 PORT_ULONG j;
 int found;

 /* Process whole words first, seeking for first word that is not
 * all ones or all zeros respectively if we are lookig for zeros
 * or ones. This is much faster with large strings having contiguous
 * blocks of 1 or 0 bits compared to the vanilla bit per bit processing.
 *
 * Note that if we start from an address that is not aligned
 * to sizeof(unsigned long) we consume it byte by byte until it is
 * aligned. */

 /* Skip initial bits not aligned to sizeof(unsigned long) byte by byte. */
 skipval = bit ? 0 : UCHAR_MAX;
 c = (unsigned char*) s;
 found = 0;
 while((PORT_ULONG)c & (sizeof(*l)-1) && count) {
 if (*c != skipval) {
 found = 1;
 break;
 }
 c++;
 count--;
 pos += 8;
 }

 /* Skip bits with full word step. */
 l = (PORT_ULONG*) c;
 if (!found) {
 skipval = bit ? 0 : PORT_ULONG_MAX;
 while (count >= sizeof(*l)) {
 if (*l != skipval) break;
 l++;
 count -= sizeof(*l);
 pos += sizeof(*l)*8;
 }
 }

 /* Load bytes into "word" considering the first byte as the most significant
 * (we basically consider it as written in big endian, since we consider the
 * string as a set of bits from left to right, with the first bit at position
 * zero.
 *
 * Note that the loading is designed to work even when the bytes left
 * (count) are less than a full word. We pad it with zero on the right. */
 c = (unsigned char*)l;
 for (j = 0; j < sizeof(*l); j++) {
 word <<= 8;
 if (count) {
 word |= *c;
 c++;
 count--;
 }
 }

 /* Special case:
 * If bits in the string are all zero and we are looking for one,
 * return -1 to signal that there is not a single "1" in the whole
 * string. This can't happen when we are looking for "0" as we assume
 * that the right of the string is zero padded. */
 if (bit == 1 && word == 0) return -1;

 /* Last word left, scan bit by bit. The first thing we need is to
 * have a single "1" set in the most significant position in an
 * unsigned long. We don't know the size of the long so we use a
 * simple trick. */
 one = PORT_ULONG_MAX; /* All bits set to 1.*/
 one >>= 1; /* All bits set to 1 but the MSB. */
 one = ~one; /* All bits set to 0 but the MSB. */

 while(one) {
 if (((one & word) != 0) == bit) return pos;
 pos++;
 one >>= 1;
 }

 /* If we reached this point, there is a bug in the algorithm, since
 * the case of no match is handled as a special case before. */
 serverPanic("End of redisBitpos() reached.");
 return 0; /* Just to avoid warnings. */
}

/* The following set.*Bitfield and get.*Bitfield functions implement setting
 * and getting arbitrary size (up to 64 bits) signed and unsigned integers
 * at arbitrary positions into a bitmap.
 *
 * The representation considers the bitmap as having the bit number 0 to be
 * the most significant bit of the first byte, and so forth, so for example
 * setting a 5 bits unsigned integer to value 23 at offset 7 into a bitmap
 * previously set to all zeroes, will produce the following representation:
 *
 * +--------+--------+
 * |00000001|01110000|
 * +--------+--------+
 *
 * When offsets and integer sizes are aligned to bytes boundaries, this is the
 * same as big endian, however when such alignment does not exist, its important
 * to also understand how the bits inside a byte are ordered.
 *
 * Note that this format follows the same convention as SETBIT and related
 * commands.
 */

void setUnsignedBitfield(unsigned char *p, uint64_t offset, uint64_t bits, uint64_t value) {
 uint64_t byte, bit, byteval, bitval, j;

 for (j = 0; j < bits; j++) {
 bitval = (value & ((uint64_t)1<<(bits-1-j))) != 0;
 byte = offset >> 3;
 bit = 7 - (offset & 0x7);
 byteval = p[byte];
 byteval &= ~(1 << bit);
 byteval |= bitval << bit;
 p[byte] = byteval & 0xff;
 offset++;
 }
}

void setSignedBitfield(unsigned char *p, uint64_t offset, uint64_t bits, int64_t value) {
 uint64_t uv = value; /* Casting will add UINT64_MAX + 1 if v is negative. */
 setUnsignedBitfield(p,offset,bits,uv);
}

uint64_t getUnsignedBitfield(unsigned char *p, uint64_t offset, uint64_t bits) {
 uint64_t byte, bit, byteval, bitval, j, value = 0;

 for (j = 0; j < bits; j++) {
 byte = offset >> 3;
 bit = 7 - (offset & 0x7);
 byteval = p[byte];
 bitval = (byteval >> bit) & 1;
 value = (value<<1) | bitval;
 offset++;
 }
 return value;
}

int64_t getSignedBitfield(unsigned char *p, uint64_t offset, uint64_t bits) {
 int64_t value;
 union {uint64_t u; int64_t i;} conv;

 /* Converting from unsigned to signed is undefined when the value does
 * not fit, however here we assume two's complement and the original value
 * was obtained from signed -> unsigned conversion, so we'll find the
 * most significant bit set if the original value was negative.
 *
 * Note that two's complement is mandatory for exact-width types
 * according to the C99 standard. */
 conv.u = getUnsignedBitfield(p,offset,bits);
 value = conv.i;

 /* If the top significant bit is 1, propagate it to all the
 * higher bits for two's complement representation of signed
 * integers. */
 if (value & ((uint64_t)1 << (bits-1)))
 value |= ((uint64_t)-1) << bits;
 return value;
}

/* The following two functions detect overflow of a value in the context
 * of storing it as an unsigned or signed integer with the specified
 * number of bits. The functions both take the value and a possible increment.
 * If no overflow could happen and the value+increment fit inside the limits,
 * then zero is returned, otherwise in case of overflow, 1 is returned,
 * otherwise in case of underflow, -1 is returned.
 *
 * When non-zero is returned (oferflow or underflow), if not NULL, *limit is
 * set to the value the operation should result when an overflow happens,
 * depending on the specified overflow semantics:
 *
 * For BFOVERFLOW_SAT if 1 is returned, *limit it is set maximum value that
 * you can store in that integer. when -1 is returned, *limit is set to the
 * minimum value that an integer of that size can represent.
 *
 * For BFOVERFLOW_WRAP *limit is set by performing the operation in order to
 * "wrap" around towards zero for unsigned integers, or towards the most
 * negative number that is possible to represent for signed integers. */

#define BFOVERFLOW_WRAP 0
#define BFOVERFLOW_SAT 1
#define BFOVERFLOW_FAIL 2 /* Used by the BITFIELD command implementation. */

int checkUnsignedBitfieldOverflow(uint64_t value, int64_t incr, uint64_t bits, int owtype, uint64_t *limit) {
 uint64_t max = (bits == 64) ? UINT64_MAX : (((uint64_t)1<<bits)-1);
 int64_t maxincr = max-value;
 int64_t minincr = -value;

 if (value > max || (incr > 0 && incr > maxincr)) {
 if (limit) {
 if (owtype == BFOVERFLOW_WRAP) {
 goto handle_wrap;
 } else if (owtype == BFOVERFLOW_SAT) {
 *limit = max;
 }
 }
 return 1;
 } else if (incr < 0 && incr < minincr) {
 if (limit) {
 if (owtype == BFOVERFLOW_WRAP) {
 goto handle_wrap;
 } else if (owtype == BFOVERFLOW_SAT) {
 *limit = 0;
 }
 }
 return -1;
 }
 return 0;

handle_wrap:
 {
 uint64_t mask = ((uint64_t)-1) << bits;
 uint64_t res = value+incr;

 res &= ~mask;
 *limit = res;
 }
 return 1;
}

int checkSignedBitfieldOverflow(int64_t value, int64_t incr, uint64_t bits, int owtype, int64_t *limit) {
 int64_t max = (bits == 64) ? INT64_MAX : (((int64_t)1<<(bits-1))-1);
 int64_t min = (-max)-1;

 /* Note that maxincr and minincr could overflow, but we use the values
 * only after checking 'value' range, so when we use it no overflow
 * happens. */
 int64_t maxincr = max-value;
 int64_t minincr = min-value;

 if (value > max || (bits != 64 && incr > maxincr) || (value >= 0 && incr > 0 && incr > maxincr))
 {
 if (limit) {
 if (owtype == BFOVERFLOW_WRAP) {
 goto handle_wrap;
 } else if (owtype == BFOVERFLOW_SAT) {
 *limit = max;
 }
 }
 return 1;
 } else if (value < min || (bits != 64 && incr < minincr) || (value < 0 && incr < 0 && incr < minincr)) {
 if (limit) {
 if (owtype == BFOVERFLOW_WRAP) {
 goto handle_wrap;
 } else if (owtype == BFOVERFLOW_SAT) {
 *limit = min;
 }
 }
 return -1;
 }
 return 0;

handle_wrap:
 {
 uint64_t mask = ((uint64_t)-1) << bits;
 uint64_t msb = (uint64_t)1 << (bits-1);
 uint64_t a = value, b = incr, c;
 c = a+b; /* Perform addition as unsigned so that's defined. */

 /* If the sign bit is set, propagate to all the higher order
 * bits, to cap the negative value. If it's clear, mask to
 * the positive integer limit. */
 if (c & msb) {
 c |= mask;
 } else {
 c &= ~mask;
 }
 *limit = c;
 }
 return 1;
}

/* Debugging function. Just show bits in the specified bitmap. Not used
 * but here for not having to rewrite it when debugging is needed. */
void printBits(unsigned char *p, PORT_ULONG count) {
 PORT_ULONG j, i, byte;

 for (j = 0; j < count; j++) {
 byte = p[j];
 for (i = 0x80; i > 0; i /= 2)
 printf("%c", (byte & i) ? '1' : '0');
 printf("|");
 }
 printf("\n");
}

/* -----------------------------------------------------------------------------
 * Bits related string commands: GETBIT, SETBIT, BITCOUNT, BITOP.
 * -------------------------------------------------------------------------- */

#define BITOP_AND 0
#define BITOP_OR 1
#define BITOP_XOR 2
#define BITOP_NOT 3

#define BITFIELDOP_GET 0
#define BITFIELDOP_SET 1
#define BITFIELDOP_INCRBY 2

/* This helper function used by GETBIT / SETBIT parses the bit offset argument
 * making sure an error is returned if it is negative or if it overflows
 * Redis 512 MB limit for the string value.
 *
 * If the 'hash' argument is true, and 'bits is positive, then the command
 * will also parse bit offsets prefixed by "#". In such a case the offset
 * is multiplied by 'bits'. This is useful for the BITFIELD command. */
int getBitOffsetFromArgument(client *c, robj *o, size_t *offset, int hash, int bits) {
 PORT_LONGLONG loffset;
 char *err = "bit offset is not an integer or out of range";
 char *p = o->ptr;
 size_t plen = sdslen(p);
 int usehash = 0;

 /* Handle #<offset> form. */
 if (p[0] == '#' && hash && bits > 0) usehash = 1;

 if (string2ll(p+usehash,plen-usehash,&loffset) == 0) {
 addReplyError(c,err);
 return C_ERR;
 }

 /* Adjust the offset by 'bits' for #<offset> form. */
 if (usehash) loffset *= bits;

 /* Limit offset to 512MB in bytes */
 if ((loffset < 0) || ((PORT_ULONGLONG)loffset >> 3) >= (512*1024*1024))
 {
 addReplyError(c,err);
 return C_ERR;
 }

 *offset = (size_t)loffset;
 return C_OK;
}

/* This helper function for BITFIELD parses a bitfield type in the form
 * <sign><bits> where sign is 'u' or 'i' for unsigned and signed, and
 * the bits is a value between 1 and 64. However 64 bits unsigned integers
 * are reported as an error because of current limitations of Redis protocol
 * to return unsigned integer values greater than INT64_MAX.
 *
 * On error C_ERR is returned and an error is sent to the client. */
int getBitfieldTypeFromArgument(client *c, robj *o, int *sign, int *bits) {
 char *p = o->ptr;
 char *err = "Invalid bitfield type. Use something like i16 u8. Note that u64 is not supported but i64 is.";
 PORT_LONGLONG llbits;

 if (p[0] == 'i') {
 *sign = 1;
 } else if (p[0] == 'u') {
 *sign = 0;
 } else {
 addReplyError(c,err);
 return C_ERR;
 }

 if ((string2ll(p+1,strlen(p+1),&llbits)) == 0 ||
 llbits < 1 ||
 (*sign == 1 && llbits > 64) ||
 (*sign == 0 && llbits > 63))
 {
 addReplyError(c,err);
 return C_ERR;
 }
 *bits = llbits;
 return C_OK;
}

/* This is an helper function for commands implementations that need to write
 * bits to a string object. The command creates or pad with zeroes the string
 * so that the 'maxbit' bit can be addressed. The object is finally
 * returned. Otherwise if the key holds a wrong type NULL is returned and
 * an error is sent to the client. */
robj *lookupStringForBitCommand(client *c, size_t maxbit) {
 size_t byte = maxbit >> 3;
 robj *o = lookupKeyWrite(c->db,c->argv[1]);

 if (o == NULL) {
 o = createObject(OBJ_STRING,sdsnewlen(NULL, byte+1));
 dbAdd(c->db,c->argv[1],o);
 } else {
 if (checkType(c,o,OBJ_STRING)) return NULL;
 o = dbUnshareStringValue(c->db,c->argv[1],o);
 o->ptr = sdsgrowzero(o->ptr,byte+1);
 }
 return o;
}

/* Return a pointer to the string object content, and stores its length
 * in 'len'. The user is required to pass (likely stack allocated) buffer
 * 'llbuf' of at least LONG_STR_SIZE bytes. Such a buffer is used in the case
 * the object is integer encoded in order to provide the representation
 * without usign heap allocation.
 *
 * The function returns the pointer to the object array of bytes representing
 * the string it contains, that may be a pointer to 'llbuf' or to the
 * internal object representation. As a side effect 'len' is filled with
 * the length of such buffer.
 *
 * If the source object is NULL the function is guaranteed to return NULL
 * and set 'len' to 0. */
unsigned char *getObjectReadOnlyString(robj *o, PORT_LONG *len, char *llbuf) {
 serverAssert(o->type == OBJ_STRING);
 unsigned char *p = NULL;

 /* Set the 'p' pointer to the string, that can be just a stack allocated
 * array if our string was integer encoded. */
 if (o && o->encoding == OBJ_ENCODING_INT) {
 p = (unsigned char*) llbuf;
 if (len) *len = ll2string(llbuf,LONG_STR_SIZE,(PORT_LONG)o->ptr);
 } else if (o) {
 p = (unsigned char*) o->ptr;
 if (len) *len = sdslen(o->ptr);
 } else {
 if (len) *len = 0;
 }
 return p;
}

/* SETBIT key offset bitvalue */
void setbitCommand(client *c) {
 robj *o;
 char *err = "bit is not an integer or out of range";
 size_t bitoffset;
 ssize_t byte, bit;
 int byteval, bitval;
 PORT_LONG on;

 if (getBitOffsetFromArgument(c,c->argv[2],&bitoffset,0,0) != C_OK)
 return;

 if (getLongFromObjectOrReply(c,c->argv[3],&on,err) != C_OK)
 return;

 /* Bits can only be set or cleared... */
 if (on & ~1) {
 addReplyError(c,err);
 return;
 }

 if ((o = lookupStringForBitCommand(c,bitoffset)) == NULL) return;

 /* Get current values */
 byte = bitoffset >> 3;
 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]);
 notifyKeyspaceEvent(NOTIFY_STRING,"setbit",c->argv[1],c->db->id);
 server.dirty++;
 addReply(c, bitval ? shared.cone : shared.czero);
}

/* GETBIT key offset */
void getbitCommand(client *c) {
 robj *o;
 char llbuf[32];
 size_t bitoffset;
 size_t byte, bit;
 size_t bitval = 0;

 if (getBitOffsetFromArgument(c,c->argv[2],&bitoffset,0,0) != C_OK)
 return;

 if ((o = lookupKeyReadOrReply(c,c->argv[1],shared.czero)) == NULL ||
 checkType(c,o,OBJ_STRING)) return;

 byte = bitoffset >> 3;
 bit = 7 - (bitoffset & 0x7);
 if (sdsEncodedObject(o)) {
 if (byte < sdslen(o->ptr))
 bitval = ((uint8_t*)o->ptr)[byte] & (1 << bit);
 } else {
 if (byte < (size_t)ll2string(llbuf,sizeof(llbuf),(PORT_LONG)o->ptr))
 bitval = llbuf[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(client *c) {
 char *opname = c->argv[1]->ptr;
 robj *o, *targetkey = c->argv[2];
 PORT_ULONG op, j, numkeys;
 robj **objects; /* Array of source objects. */
 unsigned char **src; /* Array of source strings pointers. */
 PORT_ULONG *len, maxlen = 0; /* Array of length of src strings,
 and max len. */
 PORT_ULONG 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(PORT_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,OBJ_STRING)) {
 PORT_ULONG i;
 for (i = 0; i < j; i++) {
 if (objects[i])
 decrRefCount(objects[i]);
 }
 zfree(src);
 zfree(len);
 zfree(objects);
 return;
 }
 objects[j] = getDecodedObject(o);
 src[j] = objects[j]->ptr;
 len[j] = (PORT_LONG) sdslen(objects[j]->ptr); WIN_PORT_FIX /* cast (PORT_LONG) */
 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;
 PORT_ULONG 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. On ARM we skip the fast path since it will
 * result in GCC compiling the code using multiple-words load/store
 * operations that are not supported even in ARM >= v6. */
 j = 0;
 #ifndef USE_ALIGNED_ACCESS
 if (minlen >= sizeof(PORT_ULONG)*4 && numkeys <= 16) {
 PORT_ULONG *lp[16];
 PORT_ULONG *lres = (PORT_ULONG*) res;

 /* Note: sds pointer is always aligned to 8 byte boundary. */
 memcpy(lp,src,sizeof(PORT_ULONG*)*numkeys);
 memcpy(res,src[0],minlen);

 /* Different branches per different operations for speed (sorry). */
 if (op == BITOP_AND) {
 while(minlen >= sizeof(PORT_ULONG)*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(PORT_ULONG)*4;
 minlen -= sizeof(PORT_ULONG)*4;
 }
 } else if (op == BITOP_OR) {
 while(minlen >= sizeof(PORT_ULONG)*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(PORT_ULONG)*4;
 minlen -= sizeof(PORT_ULONG)*4;
 }
 } else if (op == BITOP_XOR) {
 while(minlen >= sizeof(PORT_ULONG)*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(PORT_ULONG)*4;
 minlen -= sizeof(PORT_ULONG)*4;
 }
 } else if (op == BITOP_NOT) {
 while(minlen >= sizeof(PORT_ULONG)*4) {
 lres[0] = ~lres[0];
 lres[1] = ~lres[1];
 lres[2] = ~lres[2];
 lres[3] = ~lres[3];
 lres+=4;
 j += sizeof(PORT_ULONG)*4;
 minlen -= sizeof(PORT_ULONG)*4;
 }
 }
 }
 #endif

 /* 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(OBJ_STRING,res);
 setKey(c->db,targetkey,o);
 notifyKeyspaceEvent(NOTIFY_STRING,"set",targetkey,c->db->id);
 decrRefCount(o);
 } else if (dbDelete(c->db,targetkey)) {
 signalModifiedKey(c->db,targetkey);
 notifyKeyspaceEvent(NOTIFY_GENERIC,"del",targetkey,c->db->id);
 }
 server.dirty++;
 addReplyLongLong(c,maxlen); /* Return the output string length in bytes. */
}

/* BITCOUNT key [start end] */
void bitcountCommand(client *c) {
 robj *o;
 PORT_LONG start, end, strlen;
 unsigned char *p;
 char llbuf[LONG_STR_SIZE];

 /* Lookup, check for type, and return 0 for non existing keys. */
 if ((o = lookupKeyReadOrReply(c,c->argv[1],shared.czero)) == NULL ||
 checkType(c,o,OBJ_STRING)) return;
 p = getObjectReadOnlyString(o,&strlen,llbuf);

 /* Parse start/end range if any. */
 if (c->argc == 4) {
 if (getLongFromObjectOrReply(c,c->argv[2],&start,NULL) != C_OK)
 return;
 if (getLongFromObjectOrReply(c,c->argv[3],&end,NULL) != C_OK)
 return;
 /* Convert negative indexes */
 if (start < 0 && end < 0 && start > end) {
 addReply(c,shared.czero);
 return;
 }
 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 {
 PORT_LONG bytes = end-start+1;

 addReplyLongLong(c,redisPopcount(p+start,bytes));
 }
}

/* BITPOS key bit [start [end]] */
void bitposCommand(client *c) {
 robj *o;
 PORT_LONG bit, start, end, strlen;
 unsigned char *p;
 char llbuf[LONG_STR_SIZE];
 int end_given = 0;

 /* Parse the bit argument to understand what we are looking for, set
 * or clear bits. */
 if (getLongFromObjectOrReply(c,c->argv[2],&bit,NULL) != C_OK)
 return;
 if (bit != 0 && bit != 1) {
 addReplyError(c, "The bit argument must be 1 or 0.");
 return;
 }

 /* If the key does not exist, from our point of view it is an infinite
 * array of 0 bits. If the user is looking for the fist clear bit return 0,
 * If the user is looking for the first set bit, return -1. */
 if ((o = lookupKeyRead(c->db,c->argv[1])) == NULL) {
 addReplyLongLong(c, bit ? -1 : 0);
 return;
 }
 if (checkType(c,o,OBJ_STRING)) return;
 p = getObjectReadOnlyString(o,&strlen,llbuf);

 /* Parse start/end range if any. */
 if (c->argc == 4 || c->argc == 5) {
 if (getLongFromObjectOrReply(c,c->argv[3],&start,NULL) != C_OK)
 return;
 if (c->argc == 5) {
 if (getLongFromObjectOrReply(c,c->argv[4],&end,NULL) != C_OK)
 return;
 end_given = 1;
 } else {
 end = strlen-1;
 }
 /* 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 == 3) {
 /* The whole string. */
 start = 0;
 end = strlen-1;
 } else {
 /* Syntax error. */
 addReply(c,shared.syntaxerr);
 return;
 }

 /* For empty ranges (start > end) we return -1 as an empty range does
 * not contain a 0 nor a 1. */
 if (start > end) {
 addReplyLongLong(c, -1);
 } else {
 PORT_LONG bytes = end-start+1;
 PORT_LONG pos = redisBitpos(p+start,(PORT_ULONG)bytes,(int)bit); WIN_PORT_FIX /* cast (PORT_ULONG), cast (int) */

 /* If we are looking for clear bits, and the user specified an exact
 * range with start-end, we can't consider the right of the range as
 * zero padded (as we do when no explicit end is given).
 *
 * So if redisBitpos() returns the first bit outside the range,
 * we return -1 to the caller, to mean, in the specified range there
 * is not a single "0" bit. */
 if (end_given && bit == 0 && pos == bytes*8) {
 addReplyLongLong(c,-1);
 return;
 }
 if (pos != -1) pos += start*8; /* Adjust for the bytes we skipped. */
 addReplyLongLong(c,pos);
 }
}

/* BITFIELD key subcommmand-1 arg ... subcommand-2 arg ... subcommand-N ...
 *
 * Supported subcommands:
 *
 * GET <type> <offset>
 * SET <type> <offset> <value>
 * INCRBY <type> <offset> <increment>
 * OVERFLOW [WRAP|SAT|FAIL]
 */

struct bitfieldOp {
 uint64_t offset; /* Bitfield offset. */
 int64_t i64; /* Increment amount (INCRBY) or SET value */
 int opcode; /* Operation id. */
 int owtype; /* Overflow type to use. */
 int bits; /* Integer bitfield bits width. */
 int sign; /* True if signed, otherwise unsigned op. */
};

void bitfieldCommand(client *c) {
 robj *o;
 size_t bitoffset;
 int j, numops = 0, changes = 0;
 struct bitfieldOp *ops = NULL; /* Array of ops to execute at end. */
 int owtype = BFOVERFLOW_WRAP; /* Overflow type. */
 int readonly = 1;
 size_t highest_write_offset = 0;

 for (j = 2; j < c->argc; j++) {
 int remargs = c->argc-j-1; /* Remaining args other than current. */
 char *subcmd = c->argv[j]->ptr; /* Current command name. */
 int opcode; /* Current operation code. */
 PORT_LONGLONG i64 = 0; /* Signed SET value. */
 int sign = 0; /* Signed or unsigned type? */
 int bits = 0; /* Bitfield width in bits. */

 if (!strcasecmp(subcmd,"get") && remargs >= 2)
 opcode = BITFIELDOP_GET;
 else if (!strcasecmp(subcmd,"set") && remargs >= 3)
 opcode = BITFIELDOP_SET;
 else if (!strcasecmp(subcmd,"incrby") && remargs >= 3)
 opcode = BITFIELDOP_INCRBY;
 else if (!strcasecmp(subcmd,"overflow") && remargs >= 1) {
 char *owtypename = c->argv[j+1]->ptr;
 j++;
 if (!strcasecmp(owtypename,"wrap"))
 owtype = BFOVERFLOW_WRAP;
 else if (!strcasecmp(owtypename,"sat"))
 owtype = BFOVERFLOW_SAT;
 else if (!strcasecmp(owtypename,"fail"))
 owtype = BFOVERFLOW_FAIL;
 else {
 addReplyError(c,"Invalid OVERFLOW type specified");
 zfree(ops);
 return;
 }
 continue;
 } else {
 addReply(c,shared.syntaxerr);
 zfree(ops);
 return;
 }

 /* Get the type and offset arguments, common to all the ops. */
 if (getBitfieldTypeFromArgument(c,c->argv[j+1],&sign,&bits) != C_OK) {
 zfree(ops);
 return;
 }

 if (getBitOffsetFromArgument(c,c->argv[j+2],&bitoffset,1,bits) != C_OK){
 zfree(ops);
 return;
 }

 if (opcode != BITFIELDOP_GET) {
 readonly = 0;
 if (highest_write_offset < bitoffset + bits - 1)
 highest_write_offset = bitoffset + bits - 1;
 /* INCRBY and SET require another argument. */
 if (getLongLongFromObjectOrReply(c,c->argv[j+3],&i64,NULL) != C_OK){
 zfree(ops);
 return;
 }
 }

 /* Populate the array of operations we'll process. */
 ops = zrealloc(ops,sizeof(*ops)*(numops+1));
 ops[numops].offset = bitoffset;
 ops[numops].i64 = i64;
 ops[numops].opcode = opcode;
 ops[numops].owtype = owtype;
 ops[numops].bits = bits;
 ops[numops].sign = sign;
 numops++;

 j += 3 - (opcode == BITFIELDOP_GET);
 }

 if (readonly) {
 /* Lookup for read is ok if key doesn't exit, but errors
 * if it's not a string. */
 o = lookupKeyRead(c->db,c->argv[1]);
 if (o != NULL && checkType(c,o,OBJ_STRING)) {
 zfree(ops);
 return;
 }
 } else {
 /* Lookup by making room up to the farest bit reached by
 * this operation. */
 if ((o = lookupStringForBitCommand(c,
 highest_write_offset)) == NULL) {
 zfree(ops);
 return;
 }
 }

 addReplyMultiBulkLen(c,numops);

 /* Actually process the operations. */
 for (j = 0; j < numops; j++) {
 struct bitfieldOp *thisop = ops+j;

 /* Execute the operation. */
 if (thisop->opcode == BITFIELDOP_SET ||
 thisop->opcode == BITFIELDOP_INCRBY)
 {
 /* SET and INCRBY: We handle both with the same code path
 * for simplicity. SET return value is the previous value so
 * we need fetch & store as well. */

 /* We need two different but very similar code paths for signed
 * and unsigned operations, since the set of functions to get/set
 * the integers and the used variables types are different. */
 if (thisop->sign) {
 int64_t oldval, newval, wrapped, retval;
 int overflow;

 oldval = getSignedBitfield(o->ptr,thisop->offset,
 thisop->bits);

 if (thisop->opcode == BITFIELDOP_INCRBY) {
 newval = oldval + thisop->i64;
 overflow = checkSignedBitfieldOverflow(oldval,
 thisop->i64,thisop->bits,thisop->owtype,&wrapped);
 if (overflow) newval = wrapped;
 retval = newval;
 } else {
 newval = thisop->i64;
 overflow = checkSignedBitfieldOverflow(newval,
 0,thisop->bits,thisop->owtype,&wrapped);
 if (overflow) newval = wrapped;
 retval = oldval;
 }

 /* On overflow of type is "FAIL", don't write and return
 * NULL to signal the condition. */
 if (!(overflow && thisop->owtype == BFOVERFLOW_FAIL)) {
 addReplyLongLong(c,retval);
 setSignedBitfield(o->ptr,thisop->offset,
 thisop->bits,newval);
 } else {
 addReply(c,shared.nullbulk);
 }
 } else {
 uint64_t oldval, newval, wrapped, retval;
 int overflow;

 oldval = getUnsignedBitfield(o->ptr,thisop->offset,
 thisop->bits);

 if (thisop->opcode == BITFIELDOP_INCRBY) {
 newval = oldval + thisop->i64;
 overflow = checkUnsignedBitfieldOverflow(oldval,
 thisop->i64,thisop->bits,thisop->owtype,&wrapped);
 if (overflow) newval = wrapped;
 retval = newval;
 } else {
 newval = thisop->i64;
 overflow = checkUnsignedBitfieldOverflow(newval,
 0,thisop->bits,thisop->owtype,&wrapped);
 if (overflow) newval = wrapped;
 retval = oldval;
 }
 /* On overflow of type is "FAIL", don't write and return
 * NULL to signal the condition. */
 if (!(overflow && thisop->owtype == BFOVERFLOW_FAIL)) {
 addReplyLongLong(c,retval);
 setUnsignedBitfield(o->ptr,thisop->offset,
 thisop->bits,newval);
 } else {
 addReply(c,shared.nullbulk);
 }
 }
 changes++;
 } else {
 /* GET */
 unsigned char buf[9];
 PORT_LONG strlen = 0;
 unsigned char *src = NULL;
 char llbuf[LONG_STR_SIZE];

 if (o != NULL)
 src = getObjectReadOnlyString(o,&strlen,llbuf);

 /* For GET we use a trick: before executing the operation
 * copy up to 9 bytes to a local buffer, so that we can easily
 * execute up to 64 bit operations that are at actual string
 * object boundaries. */
 memset(buf,0,9);
 int i;
 size_t byte = thisop->offset >> 3;
 for (i = 0; i < 9; i++) {
 if (src == NULL || i+byte >= (size_t)strlen) break;
 buf[i] = src[i+byte];
 }

 /* Now operate on the copied buffer which is guaranteed
 * to be zero-padded. */
 if (thisop->sign) {
 int64_t val = getSignedBitfield(buf,thisop->offset-(byte*8),
 thisop->bits);
 addReplyLongLong(c,val);
 } else {
 uint64_t val = getUnsignedBitfield(buf,thisop->offset-(byte*8),
 thisop->bits);
 addReplyLongLong(c,val);
 }
 }
 }

 if (changes) {
 signalModifiedKey(c->db,c->argv[1]);
 notifyKeyspaceEvent(NOTIFY_STRING,"setbit",c->argv[1],c->db->id);
 server.dirty += changes;
 }
 zfree(ops);
}