bitops.c

Bug Summary

File:	src/bitops.c
Warning:	line 316, column 40 The result of the left shift is undefined due to shifting by '64', which is greater or equal to the width of type 'uint64_t'
Annotated Source Code

Press '?' to see keyboard shortcuts
Show analyzer invocation
clang -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name bitops.c -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -mrelocation-model static -mthread-model posix -mframe-pointer=none -fmath-errno -fno-rounding-math -masm-verbose -mconstructor-aliases -munwind-tables -target-cpu x86-64 -dwarf-column-info -fno-split-dwarf-inlining -debugger-tuning=gdb -resource-dir /usr/lib/llvm-10/lib/clang/10.0.0 -D REDIS_STATIC= -I ../deps/hiredis -I ../deps/linenoise -I ../deps/lua/src -I ../deps/hdr_histogram -D USE_JEMALLOC -I ../deps/jemalloc/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-10/lib/clang/10.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-c11-extensions -Wno-missing-field-initializers -std=c11 -fdebug-compilation-dir /home/netto/Desktop/redis-6.2.1/src -ferror-limit 19 -fmessage-length 0 -fgnuc-version=4.2.1 -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -faddrsig -o /tmp/scan-build-2021-03-14-133648-8817-1 -x c bitops.c
1/* 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.
*/

31#include "server.h"

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

37/* 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 an input string length up to 512 MB or more (server.proto_max_bulk_len) */
40size_t redisPopcount(void *s, 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((unsigned long)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;
92}

94/* 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. */
101long redisBitpos(void *s, unsigned long count, int bit) {
  unsigned long *l;
  unsigned char *c;
  unsigned long skipval, word = 0, one;
  long pos = 0; /* Position of bit, to return to the caller. */
  unsigned long j;
  int found;

  /* Process whole words first, seeking for first word that is not
   * all ones or all zeros respectively if we are looking 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(127*2 +1);
  c = (unsigned char*) s;
  found = 0;
  while((unsigned long)c & (sizeof(*l)-1) && count) {
      if (*c != skipval) {
          found = 1;
          break;
      }
      c++;
      count--;
      pos += 8;
  }

  /* Skip bits with full word step. */
  l = (unsigned long*) c;
  if (!found) {
      skipval = bit ? 0 : ULONG_MAX(9223372036854775807L *2UL+1UL);
      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 = ULONG_MAX(9223372036854775807L *2UL+1UL); /* 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.")_serverPanic("bitops.c",184,"End of redisBitpos() reached."),
__builtin_unreachable();
  return 0; /* Just to avoid warnings. */
186}

188/* 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.
*/

209void 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++;
  }
222}

224void 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);
227}

229uint64_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;
241}

243int64_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 (bits < 64 && (value & ((uint64_t)1 << (bits-1))))
      value |= ((uint64_t)-1) << bits;
  return value;
263}

265/* 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 (overflow 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. */

284#define BFOVERFLOW_WRAP0 0
285#define BFOVERFLOW_SAT1 1
286#define BFOVERFLOW_FAIL2 2 /* Used by the BITFIELD command implementation. */

288int checkUnsignedBitfieldOverflow(uint64_t value, int64_t incr, uint64_t bits, int owtype, uint64_t *limit) {
  uint64_t max = (bits == 64) ? UINT64_MAX(18446744073709551615UL) : (((uint64_t)1<<bits)-1);
1
Assuming 'bits' is equal to 64→
2
←
'?' condition is true→
  int64_t maxincr = max-value;
  int64_t minincr = -value;

  if (value2.1
'value' is <= 'max'
 > max || (incr > 0 && incr > maxincr)) {
3
←
Assuming 'incr' is > 0→
4
←
Assuming 'incr' is > 'maxincr'→
5
←
Taking true branch→
      if (limit) {
6
←
Assuming 'limit' is non-null→
7
←
Taking true branch→
          if (owtype == BFOVERFLOW_WRAP0) {
8
←
Assuming 'owtype' is equal to BFOVERFLOW_WRAP→
9
←
Taking true branch→
              goto handle_wrap;
10
←
Control jumps to line 316→
          } else if (owtype == BFOVERFLOW_SAT1) {
              *limit = max;
          }
      }
      return 1;
  } else if (incr < 0 && incr < minincr) {
      if (limit) {
          if (owtype == BFOVERFLOW_WRAP0) {
              goto handle_wrap;
          } else if (owtype == BFOVERFLOW_SAT1) {
              *limit = 0;
          }
      }
      return -1;
  }
  return 0;

314handle_wrap:
  {
      uint64_t mask = ((uint64_t)-1) << bits;
11
←
The result of the left shift is undefined due to shifting by '64', which is greater or equal to the width of type 'uint64_t'
      uint64_t res = value+incr;

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

325int checkSignedBitfieldOverflow(int64_t value, int64_t incr, uint64_t bits, int owtype, int64_t *limit) {
  int64_t max = (bits == 64) ? INT64_MAX(9223372036854775807L) : (((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_WRAP0) {
              goto handle_wrap;
          } else if (owtype == BFOVERFLOW_SAT1) {
              *limit = max;
          }
      }
      return 1;
  } else if (value < min || (bits != 64 && incr < minincr) || (value < 0 && incr < 0 && incr < minincr)) {
      if (limit) {
          if (owtype == BFOVERFLOW_WRAP0) {
              goto handle_wrap;
          } else if (owtype == BFOVERFLOW_SAT1) {
              *limit = min;
          }
      }
      return -1;
  }
  return 0;

357handle_wrap:
  {
      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 (bits < 64) {
          uint64_t mask = ((uint64_t)-1) << bits;
          if (c & msb) {
              c |= mask;
          } else {
              c &= ~mask;
          }
      }
      *limit = c;
  }
  return 1;
377}

379/* Debugging function. Just show bits in the specified bitmap. Not used
* but here for not having to rewrite it when debugging is needed. */
381void printBits(unsigned char *p, unsigned long count) {
  unsigned long 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");
391}

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

397#define BITOP_AND0   0
398#define BITOP_OR1    1
399#define BITOP_XOR2   2
400#define BITOP_NOT3   3

402#define BITFIELDOP_GET0 0
403#define BITFIELDOP_SET1 1
404#define BITFIELDOP_INCRBY2 2

406/* 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 or more (server.proto_max_bulk_len).
*
* 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. */
413int getBitOffsetFromArgument(client *c, robj *o, size_t *offset, int hash, int bits) {
  long long 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-1;
  }

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

  /* Limit offset to server.proto_max_bulk_len (512MB in bytes by default) */
  if ((loffset < 0) || (loffset >> 3) >= server.proto_max_bulk_len)
  {
      addReplyError(c,err);
      return C_ERR-1;
  }

  *offset = (size_t)loffset;
  return C_OK0;
440}

442/* 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. */
449int 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.";
  long long llbits;

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

  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-1;
  }
  *bits = llbits;
  return C_OK0;
473}

475/* 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. */
480robj *lookupStringForBitCommand(client *c, size_t maxbit) {
  size_t byte = maxbit >> 3;
  robj *o = lookupKeyWrite(c->db,c->argv[1]);
  if (checkType(c,o,OBJ_STRING0)) return NULL((void*)0);

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

495/* 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 using 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. */
508unsigned char *getObjectReadOnlyString(robj *o, long *len, char *llbuf) {
  serverAssert(o->type == OBJ_STRING)((o->type == 0)?(void)0 : (_serverAssert("o->type == OBJ_STRING"
,"bitops.c",509),__builtin_unreachable()));
  unsigned char *p = NULL((void*)0);

  /* 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_INT1) {
      p = (unsigned char*) llbuf;
      if (len) *len = ll2string(llbuf,LONG_STR_SIZE21,(long)o->ptr);
  } else if (o) {
      p = (unsigned char*) o->ptr;
      if (len) *len = sdslen(o->ptr);
  } else {
      if (len) *len = 0;
  }
  return p;
524}

526/* SETBIT key offset bitvalue */
527void 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;
  long on;

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

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

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

  if ((o = lookupStringForBitCommand(c,bitoffset)) == NULL((void*)0)) 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,c->db,c->argv[1]);
  notifyKeyspaceEvent(NOTIFY_STRING(1<<3),"setbit",c->argv[1],c->db->id);
  server.dirty++;
  addReply(c, bitval ? shared.cone : shared.czero);
563}

565/* GETBIT key offset */
566void 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_OK0)
      return;

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

  byte = bitoffset >> 3;
  bit = 7 - (bitoffset & 0x7);
  if (sdsEncodedObject(o)(o->encoding == 0 || o->encoding == 8)) {
      if (byte < sdslen(o->ptr))
          bitval = ((uint8_t*)o->ptr)[byte] & (1 << bit);
  } else {
      if (byte < (size_t)ll2string(llbuf,sizeof(llbuf),(long)o->ptr))
          bitval = llbuf[byte] & (1 << bit);
  }

  addReply(c, bitval ? shared.cone : shared.czero);
590}

592/* BITOP op_name target_key src_key1 src_key2 src_key3 ... src_keyN */
593void bitopCommand(client *c) {
  char *opname = c->argv[1]->ptr;
  robj *o, *targetkey = c->argv[2];
  unsigned long op, j, numkeys;
  robj **objects;      /* Array of source objects. */
  unsigned char **src; /* Array of source strings pointers. */
  unsigned long *len, maxlen = 0; /* Array of length of src strings,
                                     and max len. */
  unsigned long minlen = 0;    /* Min len among the input keys. */
  unsigned char *res = NULL((void*)0); /* Resulting string. */

  /* Parse the operation name. */
  if ((opname[0] == 'a' || opname[0] == 'A') && !strcasecmp(opname,"and"))
      op = BITOP_AND0;
  else if((opname[0] == 'o' || opname[0] == 'O') && !strcasecmp(opname,"or"))
      op = BITOP_OR1;
  else if((opname[0] == 'x' || opname[0] == 'X') && !strcasecmp(opname,"xor"))
      op = BITOP_XOR2;
  else if((opname[0] == 'n' || opname[0] == 'N') && !strcasecmp(opname,"not"))
      op = BITOP_NOT3;
  else {
      addReplyErrorObject(c,shared.syntaxerr);
      return;
  }

  /* Sanity check: NOT accepts only a single key argument. */
  if (op == BITOP_NOT3 && 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((void*)0)) {
          objects[j] = NULL((void*)0);
          src[j] = NULL((void*)0);
          len[j] = 0;
          minlen = 0;
          continue;
      }
      /* Return an error if one of the keys is not a string. */
      if (checkType(c,o,OBJ_STRING0)) {
          unsigned long 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] = 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((void*)0),maxlen);
      unsigned char output, byte;
      unsigned 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. 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(unsigned long)*4 && 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_AND0) {
              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_OR1) {
              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_XOR2) {
              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_NOT3) {
              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;
              }
          }
      }
      #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_NOT3) output = ~output;
          for (i = 1; i < numkeys; i++) {
              int skip = 0;
              byte = (len[i] <= j) ? 0 : src[i][j];
              switch(op) {
              case BITOP_AND0:
                  output &= byte;
                  skip = (output == 0);
                  break;
              case BITOP_OR1:
                  output |= byte;
                  skip = (output == 0xff);
                  break;
              case BITOP_XOR2: output ^= byte; break;
              }

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

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

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

  /* Parse start/end range if any. */
  if (c->argc == 4) {
      if (getLongFromObjectOrReply(c,c->argv[2],&start,NULL((void*)0)) != C_OK0)
          return;
      if (getLongFromObjectOrReply(c,c->argv[3],&end,NULL((void*)0)) != C_OK0)
          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. */
      addReplyErrorObject(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,redisPopcount(p+start,bytes));
  }
829}

831/* BITPOS key bit [start [end]] */
832void bitposCommand(client *c) {
  robj *o;
  long bit, start, end, strlen;
  unsigned char *p;
  char llbuf[LONG_STR_SIZE21];
  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((void*)0)) != C_OK0)
      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((void*)0)) {
      addReplyLongLong(c, bit ? -1 : 0);
      return;
  }
  if (checkType(c,o,OBJ_STRING0)) 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((void*)0)) != C_OK0)
          return;
      if (c->argc == 5) {
          if (getLongFromObjectOrReply(c,c->argv[4],&end,NULL((void*)0)) != C_OK0)
              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. */
      addReplyErrorObject(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 {
      long bytes = end-start+1;
      long pos = redisBitpos(p+start,bytes,bit);

      /* 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);
  }
907}

909/* 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]
*/

919#define BITFIELD_FLAG_NONE0      0
920#define BITFIELD_FLAG_READONLY(1<<0)  (1<<0)

922struct 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. */
929};

931/* This implements both the BITFIELD command and the BITFIELD_RO command
* when flags is set to BITFIELD_FLAG_READONLY: in this case only the
* GET subcommand is allowed, other subcommands will return an error. */
934void bitfieldGeneric(client *c, int flags) {
  robj *o;
  size_t bitoffset;
  int j, numops = 0, changes = 0;
  struct bitfieldOp *ops = NULL((void*)0); /* Array of ops to execute at end. */
  int owtype = BFOVERFLOW_WRAP0; /* 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. */
      long long 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_GET0;
      else if (!strcasecmp(subcmd,"set") && remargs >= 3)
          opcode = BITFIELDOP_SET1;
      else if (!strcasecmp(subcmd,"incrby") && remargs >= 3)
          opcode = BITFIELDOP_INCRBY2;
      else if (!strcasecmp(subcmd,"overflow") && remargs >= 1) {
          char *owtypename = c->argv[j+1]->ptr;
          j++;
          if (!strcasecmp(owtypename,"wrap"))
              owtype = BFOVERFLOW_WRAP0;
          else if (!strcasecmp(owtypename,"sat"))
              owtype = BFOVERFLOW_SAT1;
          else if (!strcasecmp(owtypename,"fail"))
              owtype = BFOVERFLOW_FAIL2;
          else {
              addReplyError(c,"Invalid OVERFLOW type specified");
              zfree(ops);
              return;
          }
          continue;
      } else {
          addReplyErrorObject(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_OK0) {
          zfree(ops);
          return;
      }

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

      if (opcode != BITFIELDOP_GET0) {
          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((void*)0)) != C_OK0){
              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_GET0);
  }

  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((void*)0) && checkType(c,o,OBJ_STRING0)) {
          zfree(ops);
          return;
      }
  } else {
      if (flags & BITFIELD_FLAG_READONLY(1<<0)) {
          zfree(ops);
          addReplyError(c, "BITFIELD_RO only supports the GET subcommand");
          return;
      }

      /* Lookup by making room up to the farest bit reached by
       * this operation. */
      if ((o = lookupStringForBitCommand(c,
          highest_write_offset)) == NULL((void*)0)) {
          zfree(ops);
          return;
      }
  }

  addReplyArrayLen(c,numops);

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

      /* Execute the operation. */
      if (thisop->opcode == BITFIELDOP_SET1 ||
          thisop->opcode == BITFIELDOP_INCRBY2)
      {
          /* 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_INCRBY2) {
                  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_FAIL2)) {
                  addReplyLongLong(c,retval);
                  setSignedBitfield(o->ptr,thisop->offset,
                                    thisop->bits,newval);
              } else {
                  addReplyNull(c);
              }
          } else {
              uint64_t oldval, newval, wrapped, retval;
              int overflow;

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

              if (thisop->opcode == BITFIELDOP_INCRBY2) {
                  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_FAIL2)) {
                  addReplyLongLong(c,retval);
                  setUnsignedBitfield(o->ptr,thisop->offset,
                                      thisop->bits,newval);
              } else {
                  addReplyNull(c);
              }
          }
          changes++;
      } else {
          /* GET */
          unsigned char buf[9];
          long strlen = 0;
          unsigned char *src = NULL((void*)0);
          char llbuf[LONG_STR_SIZE21];

          if (o != NULL((void*)0))
              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((void*)0) || 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,c->db,c->argv[1]);
      notifyKeyspaceEvent(NOTIFY_STRING(1<<3),"setbit",c->argv[1],c->db->id);
      server.dirty += changes;
  }
  zfree(ops);
1157}

1159void bitfieldCommand(client *c) {
  bitfieldGeneric(c, BITFIELD_FLAG_NONE0);
1161}

1163void bitfieldroCommand(client *c) {
  bitfieldGeneric(c, BITFIELD_FLAG_READONLY(1<<0));
1165}