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
31#include "server.h"
32
33/* -----------------------------------------------------------------------------
34 * Helpers and low level bit functions.
35 * -------------------------------------------------------------------------- */
36
37/* Count number of bits set in the binary array pointed by 's' and long
38 * 'count' bytes. The implementation of this function is required to
39 * work with an input string length up to 512 MB or more (server.proto_max_bulk_len) */
40long long redisPopcount(void *s, long count) {
41 long long bits = 0;
42 unsigned char *p = s;
43 uint32_t *p4;
44 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};
45
46 /* Count initial bytes not aligned to 32 bit. */
47 while((unsigned long)p & 3 && count) {
48 bits += bitsinbyte[*p++];
49 count--;
50 }
51
52 /* Count bits 28 bytes at a time */
53 p4 = (uint32_t*)p;
54 while(count>=28) {
55 uint32_t aux1, aux2, aux3, aux4, aux5, aux6, aux7;
56
57 aux1 = *p4++;
58 aux2 = *p4++;
59 aux3 = *p4++;
60 aux4 = *p4++;
61 aux5 = *p4++;
62 aux6 = *p4++;
63 aux7 = *p4++;
64 count -= 28;
65
66 aux1 = aux1 - ((aux1 >> 1) & 0x55555555);
67 aux1 = (aux1 & 0x33333333) + ((aux1 >> 2) & 0x33333333);
68 aux2 = aux2 - ((aux2 >> 1) & 0x55555555);
69 aux2 = (aux2 & 0x33333333) + ((aux2 >> 2) & 0x33333333);
70 aux3 = aux3 - ((aux3 >> 1) & 0x55555555);
71 aux3 = (aux3 & 0x33333333) + ((aux3 >> 2) & 0x33333333);
72 aux4 = aux4 - ((aux4 >> 1) & 0x55555555);
73 aux4 = (aux4 & 0x33333333) + ((aux4 >> 2) & 0x33333333);
74 aux5 = aux5 - ((aux5 >> 1) & 0x55555555);
75 aux5 = (aux5 & 0x33333333) + ((aux5 >> 2) & 0x33333333);
76 aux6 = aux6 - ((aux6 >> 1) & 0x55555555);
77 aux6 = (aux6 & 0x33333333) + ((aux6 >> 2) & 0x33333333);
78 aux7 = aux7 - ((aux7 >> 1) & 0x55555555);
79 aux7 = (aux7 & 0x33333333) + ((aux7 >> 2) & 0x33333333);
80 bits += ((((aux1 + (aux1 >> 4)) & 0x0F0F0F0F) +
81 ((aux2 + (aux2 >> 4)) & 0x0F0F0F0F) +
82 ((aux3 + (aux3 >> 4)) & 0x0F0F0F0F) +
83 ((aux4 + (aux4 >> 4)) & 0x0F0F0F0F) +
84 ((aux5 + (aux5 >> 4)) & 0x0F0F0F0F) +
85 ((aux6 + (aux6 >> 4)) & 0x0F0F0F0F) +
86 ((aux7 + (aux7 >> 4)) & 0x0F0F0F0F))* 0x01010101) >> 24;
87 }
88 /* Count the remaining bytes. */
89 p = (unsigned char*)p4;
90 while(count--) bits += bitsinbyte[*p++];
91 return bits;
92}
93
94/* Return the position of the first bit set to one (if 'bit' is 1) or
95 * zero (if 'bit' is 0) in the bitmap starting at 's' and long 'count' bytes.
96 *
97 * The function is guaranteed to return a value >= 0 if 'bit' is 0 since if
98 * no zero bit is found, it returns count*8 assuming the string is zero
99 * padded on the right. However if 'bit' is 1 it is possible that there is
100 * not a single set bit in the bitmap. In this special case -1 is returned. */
101long long redisBitpos(void *s, unsigned long count, int bit) {
102 unsigned long *l;
103 unsigned char *c;
104 unsigned long skipval, word = 0, one;
105 long long pos = 0; /* Position of bit, to return to the caller. */
106 unsigned long j;
107 int found;
108
109 /* Process whole words first, seeking for first word that is not
110 * all ones or all zeros respectively if we are looking for zeros
111 * or ones. This is much faster with large strings having contiguous
112 * blocks of 1 or 0 bits compared to the vanilla bit per bit processing.
113 *
114 * Note that if we start from an address that is not aligned
115 * to sizeof(unsigned long) we consume it byte by byte until it is
116 * aligned. */
117
118 /* Skip initial bits not aligned to sizeof(unsigned long) byte by byte. */
119 skipval = bit ? 0 : UCHAR_MAX;
120 c = (unsigned char*) s;
121 found = 0;
122 while((unsigned long)c & (sizeof(*l)-1) && count) {
123 if (*c != skipval) {
124 found = 1;
125 break;
126 }
127 c++;
128 count--;
129 pos += 8;
130 }
131
132 /* Skip bits with full word step. */
133 l = (unsigned long*) c;
134 if (!found) {
135 skipval = bit ? 0 : ULONG_MAX;
136 while (count >= sizeof(*l)) {
137 if (*l != skipval) break;
138 l++;
139 count -= sizeof(*l);
140 pos += sizeof(*l)*8;
141 }
142 }
143
144 /* Load bytes into "word" considering the first byte as the most significant
145 * (we basically consider it as written in big endian, since we consider the
146 * string as a set of bits from left to right, with the first bit at position
147 * zero.
148 *
149 * Note that the loading is designed to work even when the bytes left
150 * (count) are less than a full word. We pad it with zero on the right. */
151 c = (unsigned char*)l;
152 for (j = 0; j < sizeof(*l); j++) {
153 word <<= 8;
154 if (count) {
155 word |= *c;
156 c++;
157 count--;
158 }
159 }
160
161 /* Special case:
162 * If bits in the string are all zero and we are looking for one,
163 * return -1 to signal that there is not a single "1" in the whole
164 * string. This can't happen when we are looking for "0" as we assume
165 * that the right of the string is zero padded. */
166 if (bit == 1 && word == 0) return -1;
167
168 /* Last word left, scan bit by bit. The first thing we need is to
169 * have a single "1" set in the most significant position in an
170 * unsigned long. We don't know the size of the long so we use a
171 * simple trick. */
172 one = ULONG_MAX; /* All bits set to 1.*/
173 one >>= 1; /* All bits set to 1 but the MSB. */
174 one = ~one; /* All bits set to 0 but the MSB. */
175
176 while(one) {
177 if (((one & word) != 0) == bit) return pos;
178 pos++;
179 one >>= 1;
180 }
181
182 /* If we reached this point, there is a bug in the algorithm, since
183 * the case of no match is handled as a special case before. */
184 serverPanic("End of redisBitpos() reached.");
185 return 0; /* Just to avoid warnings. */
186}
187
188/* The following set.*Bitfield and get.*Bitfield functions implement setting
189 * and getting arbitrary size (up to 64 bits) signed and unsigned integers
190 * at arbitrary positions into a bitmap.
191 *
192 * The representation considers the bitmap as having the bit number 0 to be
193 * the most significant bit of the first byte, and so forth, so for example
194 * setting a 5 bits unsigned integer to value 23 at offset 7 into a bitmap
195 * previously set to all zeroes, will produce the following representation:
196 *
197 * +--------+--------+
198 * |00000001|01110000|
199 * +--------+--------+
200 *
201 * When offsets and integer sizes are aligned to bytes boundaries, this is the
202 * same as big endian, however when such alignment does not exist, its important
203 * to also understand how the bits inside a byte are ordered.
204 *
205 * Note that this format follows the same convention as SETBIT and related
206 * commands.
207 */
208
209void setUnsignedBitfield(unsigned char *p, uint64_t offset, uint64_t bits, uint64_t value) {
210 uint64_t byte, bit, byteval, bitval, j;
211
212 for (j = 0; j < bits; j++) {
213 bitval = (value & ((uint64_t)1<<(bits-1-j))) != 0;
214 byte = offset >> 3;
215 bit = 7 - (offset & 0x7);
216 byteval = p[byte];
217 byteval &= ~(1 << bit);
218 byteval |= bitval << bit;
219 p[byte] = byteval & 0xff;
220 offset++;
221 }
222}
223
224void setSignedBitfield(unsigned char *p, uint64_t offset, uint64_t bits, int64_t value) {
225 uint64_t uv = value; /* Casting will add UINT64_MAX + 1 if v is negative. */
226 setUnsignedBitfield(p,offset,bits,uv);
227}
228
229uint64_t getUnsignedBitfield(unsigned char *p, uint64_t offset, uint64_t bits) {
230 uint64_t byte, bit, byteval, bitval, j, value = 0;
231
232 for (j = 0; j < bits; j++) {
233 byte = offset >> 3;
234 bit = 7 - (offset & 0x7);
235 byteval = p[byte];
236 bitval = (byteval >> bit) & 1;
237 value = (value<<1) | bitval;
238 offset++;
239 }
240 return value;
241}
242
243int64_t getSignedBitfield(unsigned char *p, uint64_t offset, uint64_t bits) {
244 int64_t value;
245 union {uint64_t u; int64_t i;} conv;
246
247 /* Converting from unsigned to signed is undefined when the value does
248 * not fit, however here we assume two's complement and the original value
249 * was obtained from signed -> unsigned conversion, so we'll find the
250 * most significant bit set if the original value was negative.
251 *
252 * Note that two's complement is mandatory for exact-width types
253 * according to the C99 standard. */
254 conv.u = getUnsignedBitfield(p,offset,bits);
255 value = conv.i;
256
257 /* If the top significant bit is 1, propagate it to all the
258 * higher bits for two's complement representation of signed
259 * integers. */
260 if (bits < 64 && (value & ((uint64_t)1 << (bits-1))))
261 value |= ((uint64_t)-1) << bits;
262 return value;
263}
264
265/* The following two functions detect overflow of a value in the context
266 * of storing it as an unsigned or signed integer with the specified
267 * number of bits. The functions both take the value and a possible increment.
268 * If no overflow could happen and the value+increment fit inside the limits,
269 * then zero is returned, otherwise in case of overflow, 1 is returned,
270 * otherwise in case of underflow, -1 is returned.
271 *
272 * When non-zero is returned (overflow or underflow), if not NULL, *limit is
273 * set to the value the operation should result when an overflow happens,
274 * depending on the specified overflow semantics:
275 *
276 * For BFOVERFLOW_SAT if 1 is returned, *limit it is set maximum value that
277 * you can store in that integer. when -1 is returned, *limit is set to the
278 * minimum value that an integer of that size can represent.
279 *
280 * For BFOVERFLOW_WRAP *limit is set by performing the operation in order to
281 * "wrap" around towards zero for unsigned integers, or towards the most
282 * negative number that is possible to represent for signed integers. */
283
284#define BFOVERFLOW_WRAP 0
285#define BFOVERFLOW_SAT 1
286#define BFOVERFLOW_FAIL 2 /* Used by the BITFIELD command implementation. */
287
288int checkUnsignedBitfieldOverflow(uint64_t value, int64_t incr, uint64_t bits, int owtype, uint64_t *limit) {
289 uint64_t max = (bits == 64) ? UINT64_MAX : (((uint64_t)1<<bits)-1);
290 int64_t maxincr = max-value;
291 int64_t minincr = -value;
292
293 if (value > max || (incr > 0 && incr > maxincr)) {
294 if (limit) {
295 if (owtype == BFOVERFLOW_WRAP) {
296 goto handle_wrap;
297 } else if (owtype == BFOVERFLOW_SAT) {
298 *limit = max;
299 }
300 }
301 return 1;
302 } else if (incr < 0 && incr < minincr) {
303 if (limit) {
304 if (owtype == BFOVERFLOW_WRAP) {
305 goto handle_wrap;
306 } else if (owtype == BFOVERFLOW_SAT) {
307 *limit = 0;
308 }
309 }
310 return -1;
311 }
312 return 0;
313
314handle_wrap:
315 {
316 uint64_t mask = ((uint64_t)-1) << bits;
317 uint64_t res = value+incr;
318
319 res &= ~mask;
320 *limit = res;
321 }
322 return 1;
323}
324
325int checkSignedBitfieldOverflow(int64_t value, int64_t incr, uint64_t bits, int owtype, int64_t *limit) {
326 int64_t max = (bits == 64) ? INT64_MAX : (((int64_t)1<<(bits-1))-1);
327 int64_t min = (-max)-1;
328
329 /* Note that maxincr and minincr could overflow, but we use the values
330 * only after checking 'value' range, so when we use it no overflow
331 * happens. 'uint64_t' cast is there just to prevent undefined behavior on
332 * overflow */
333 int64_t maxincr = (uint64_t)max-value;
334 int64_t minincr = min-value;
335
336 if (value > max || (bits != 64 && incr > maxincr) || (value >= 0 && incr > 0 && incr > maxincr))
337 {
338 if (limit) {
339 if (owtype == BFOVERFLOW_WRAP) {
340 goto handle_wrap;
341 } else if (owtype == BFOVERFLOW_SAT) {
342 *limit = max;
343 }
344 }
345 return 1;
346 } else if (value < min || (bits != 64 && incr < minincr) || (value < 0 && incr < 0 && incr < minincr)) {
347 if (limit) {
348 if (owtype == BFOVERFLOW_WRAP) {
349 goto handle_wrap;
350 } else if (owtype == BFOVERFLOW_SAT) {
351 *limit = min;
352 }
353 }
354 return -1;
355 }
356 return 0;
357
358handle_wrap:
359 {
360 uint64_t msb = (uint64_t)1 << (bits-1);
361 uint64_t a = value, b = incr, c;
362 c = a+b; /* Perform addition as unsigned so that's defined. */
363
364 /* If the sign bit is set, propagate to all the higher order
365 * bits, to cap the negative value. If it's clear, mask to
366 * the positive integer limit. */
367 if (bits < 64) {
368 uint64_t mask = ((uint64_t)-1) << bits;
369 if (c & msb) {
370 c |= mask;
371 } else {
372 c &= ~mask;
373 }
374 }
375 *limit = c;
376 }
377 return 1;
378}
379
380/* Debugging function. Just show bits in the specified bitmap. Not used
381 * but here for not having to rewrite it when debugging is needed. */
382void printBits(unsigned char *p, unsigned long count) {
383 unsigned long j, i, byte;
384
385 for (j = 0; j < count; j++) {
386 byte = p[j];
387 for (i = 0x80; i > 0; i /= 2)
388 printf("%c", (byte & i) ? '1' : '0');
389 printf("|");
390 }
391 printf("\n");
392}
393
394/* -----------------------------------------------------------------------------
395 * Bits related string commands: GETBIT, SETBIT, BITCOUNT, BITOP.
396 * -------------------------------------------------------------------------- */
397
398#define BITOP_AND 0
399#define BITOP_OR 1
400#define BITOP_XOR 2
401#define BITOP_NOT 3
402
403#define BITFIELDOP_GET 0
404#define BITFIELDOP_SET 1
405#define BITFIELDOP_INCRBY 2
406
407/* This helper function used by GETBIT / SETBIT parses the bit offset argument
408 * making sure an error is returned if it is negative or if it overflows
409 * Redis 512 MB limit for the string value or more (server.proto_max_bulk_len).
410 *
411 * If the 'hash' argument is true, and 'bits is positive, then the command
412 * will also parse bit offsets prefixed by "#". In such a case the offset
413 * is multiplied by 'bits'. This is useful for the BITFIELD command. */
414int getBitOffsetFromArgument(client *c, robj *o, uint64_t *offset, int hash, int bits) {
415 long long loffset;
416 char *err = "bit offset is not an integer or out of range";
417 char *p = o->ptr;
418 size_t plen = sdslen(p);
419 int usehash = 0;
420
421 /* Handle #<offset> form. */
422 if (p[0] == '#' && hash && bits > 0) usehash = 1;
423
424 if (string2ll(p+usehash,plen-usehash,&loffset) == 0) {
425 addReplyError(c,err);
426 return C_ERR;
427 }
428
429 /* Adjust the offset by 'bits' for #<offset> form. */
430 if (usehash) loffset *= bits;
431
432 /* Limit offset to server.proto_max_bulk_len (512MB in bytes by default) */
433 if (loffset < 0 || (!mustObeyClient(c) && (loffset >> 3) >= server.proto_max_bulk_len))
434 {
435 addReplyError(c,err);
436 return C_ERR;
437 }
438
439 *offset = loffset;
440 return C_OK;
441}
442
443/* This helper function for BITFIELD parses a bitfield type in the form
444 * <sign><bits> where sign is 'u' or 'i' for unsigned and signed, and
445 * the bits is a value between 1 and 64. However 64 bits unsigned integers
446 * are reported as an error because of current limitations of Redis protocol
447 * to return unsigned integer values greater than INT64_MAX.
448 *
449 * On error C_ERR is returned and an error is sent to the client. */
450int getBitfieldTypeFromArgument(client *c, robj *o, int *sign, int *bits) {
451 char *p = o->ptr;
452 char *err = "Invalid bitfield type. Use something like i16 u8. Note that u64 is not supported but i64 is.";
453 long long llbits;
454
455 if (p[0] == 'i') {
456 *sign = 1;
457 } else if (p[0] == 'u') {
458 *sign = 0;
459 } else {
460 addReplyError(c,err);
461 return C_ERR;
462 }
463
464 if ((string2ll(p+1,strlen(p+1),&llbits)) == 0 ||
465 llbits < 1 ||
466 (*sign == 1 && llbits > 64) ||
467 (*sign == 0 && llbits > 63))
468 {
469 addReplyError(c,err);
470 return C_ERR;
471 }
472 *bits = llbits;
473 return C_OK;
474}
475
476/* This is a helper function for commands implementations that need to write
477 * bits to a string object. The command creates or pad with zeroes the string
478 * so that the 'maxbit' bit can be addressed. The object is finally
479 * returned. Otherwise if the key holds a wrong type NULL is returned and
480 * an error is sent to the client. */
481robj *lookupStringForBitCommand(client *c, uint64_t maxbit, int *dirty) {
482 size_t byte = maxbit >> 3;
483 robj *o = lookupKeyWrite(c->db,c->argv[1]);
484 if (checkType(c,o,OBJ_STRING)) return NULL;
485 if (dirty) *dirty = 0;
486
487 if (o == NULL) {
488 o = createObject(OBJ_STRING,sdsnewlen(NULL, byte+1));
489 dbAdd(c->db,c->argv[1],o);
490 if (dirty) *dirty = 1;
491 } else {
492 o = dbUnshareStringValue(c->db,c->argv[1],o);
493 size_t oldlen = sdslen(o->ptr);
494 o->ptr = sdsgrowzero(o->ptr,byte+1);
495 if (dirty && oldlen != sdslen(o->ptr)) *dirty = 1;
496 }
497 return o;
498}
499
500/* Return a pointer to the string object content, and stores its length
501 * in 'len'. The user is required to pass (likely stack allocated) buffer
502 * 'llbuf' of at least LONG_STR_SIZE bytes. Such a buffer is used in the case
503 * the object is integer encoded in order to provide the representation
504 * without using heap allocation.
505 *
506 * The function returns the pointer to the object array of bytes representing
507 * the string it contains, that may be a pointer to 'llbuf' or to the
508 * internal object representation. As a side effect 'len' is filled with
509 * the length of such buffer.
510 *
511 * If the source object is NULL the function is guaranteed to return NULL
512 * and set 'len' to 0. */
513unsigned char *getObjectReadOnlyString(robj *o, long *len, char *llbuf) {
514 serverAssert(!o || o->type == OBJ_STRING);
515 unsigned char *p = NULL;
516
517 /* Set the 'p' pointer to the string, that can be just a stack allocated
518 * array if our string was integer encoded. */
519 if (o && o->encoding == OBJ_ENCODING_INT) {
520 p = (unsigned char*) llbuf;
521 if (len) *len = ll2string(llbuf,LONG_STR_SIZE,(long)o->ptr);
522 } else if (o) {
523 p = (unsigned char*) o->ptr;
524 if (len) *len = sdslen(o->ptr);
525 } else {
526 if (len) *len = 0;
527 }
528 return p;
529}
530
531/* SETBIT key offset bitvalue */
532void setbitCommand(client *c) {
533 robj *o;
534 char *err = "bit is not an integer or out of range";
535 uint64_t bitoffset;
536 ssize_t byte, bit;
537 int byteval, bitval;
538 long on;
539
540 if (getBitOffsetFromArgument(c,c->argv[2],&bitoffset,0,0) != C_OK)
541 return;
542
543 if (getLongFromObjectOrReply(c,c->argv[3],&on,err) != C_OK)
544 return;
545
546 /* Bits can only be set or cleared... */
547 if (on & ~1) {
548 addReplyError(c,err);
549 return;
550 }
551
552 int dirty;
553 if ((o = lookupStringForBitCommand(c,bitoffset,&dirty)) == NULL) return;
554
555 /* Get current values */
556 byte = bitoffset >> 3;
557 byteval = ((uint8_t*)o->ptr)[byte];
558 bit = 7 - (bitoffset & 0x7);
559 bitval = byteval & (1 << bit);
560
561 /* Either it is newly created, changed length, or the bit changes before and after.
562 * Note that the bitval here is actually a decimal number.
563 * So we need to use `!!` to convert it to 0 or 1 for comparison. */
564 if (dirty || (!!bitval != on)) {
565 /* Update byte with new bit value. */
566 byteval &= ~(1 << bit);
567 byteval |= ((on & 0x1) << bit);
568 ((uint8_t*)o->ptr)[byte] = byteval;
569 signalModifiedKey(c,c->db,c->argv[1]);
570 notifyKeyspaceEvent(NOTIFY_STRING,"setbit",c->argv[1],c->db->id);
571 server.dirty++;
572 }
573
574 /* Return original value. */
575 addReply(c, bitval ? shared.cone : shared.czero);
576}
577
578/* GETBIT key offset */
579void getbitCommand(client *c) {
580 robj *o;
581 char llbuf[32];
582 uint64_t bitoffset;
583 size_t byte, bit;
584 size_t bitval = 0;
585
586 if (getBitOffsetFromArgument(c,c->argv[2],&bitoffset,0,0) != C_OK)
587 return;
588
589 if ((o = lookupKeyReadOrReply(c,c->argv[1],shared.czero)) == NULL ||
590 checkType(c,o,OBJ_STRING)) return;
591
592 byte = bitoffset >> 3;
593 bit = 7 - (bitoffset & 0x7);
594 if (sdsEncodedObject(o)) {
595 if (byte < sdslen(o->ptr))
596 bitval = ((uint8_t*)o->ptr)[byte] & (1 << bit);
597 } else {
598 if (byte < (size_t)ll2string(llbuf,sizeof(llbuf),(long)o->ptr))
599 bitval = llbuf[byte] & (1 << bit);
600 }
601
602 addReply(c, bitval ? shared.cone : shared.czero);
603}
604
605/* BITOP op_name target_key src_key1 src_key2 src_key3 ... src_keyN */
606REDIS_NO_SANITIZE("alignment")
607void bitopCommand(client *c) {
608 char *opname = c->argv[1]->ptr;
609 robj *o, *targetkey = c->argv[2];
610 unsigned long op, j, numkeys;
611 robj **objects; /* Array of source objects. */
612 unsigned char **src; /* Array of source strings pointers. */
613 unsigned long *len, maxlen = 0; /* Array of length of src strings,
614 and max len. */
615 unsigned long minlen = 0; /* Min len among the input keys. */
616 unsigned char *res = NULL; /* Resulting string. */
617
618 /* Parse the operation name. */
619 if ((opname[0] == 'a' || opname[0] == 'A') && !strcasecmp(opname,"and"))
620 op = BITOP_AND;
621 else if((opname[0] == 'o' || opname[0] == 'O') && !strcasecmp(opname,"or"))
622 op = BITOP_OR;
623 else if((opname[0] == 'x' || opname[0] == 'X') && !strcasecmp(opname,"xor"))
624 op = BITOP_XOR;
625 else if((opname[0] == 'n' || opname[0] == 'N') && !strcasecmp(opname,"not"))
626 op = BITOP_NOT;
627 else {
628 addReplyErrorObject(c,shared.syntaxerr);
629 return;
630 }
631
632 /* Sanity check: NOT accepts only a single key argument. */
633 if (op == BITOP_NOT && c->argc != 4) {
634 addReplyError(c,"BITOP NOT must be called with a single source key.");
635 return;
636 }
637
638 /* Lookup keys, and store pointers to the string objects into an array. */
639 numkeys = c->argc - 3;
640 src = zmalloc(sizeof(unsigned char*) * numkeys);
641 len = zmalloc(sizeof(long) * numkeys);
642 objects = zmalloc(sizeof(robj*) * numkeys);
643 for (j = 0; j < numkeys; j++) {
644 o = lookupKeyRead(c->db,c->argv[j+3]);
645 /* Handle non-existing keys as empty strings. */
646 if (o == NULL) {
647 objects[j] = NULL;
648 src[j] = NULL;
649 len[j] = 0;
650 minlen = 0;
651 continue;
652 }
653 /* Return an error if one of the keys is not a string. */
654 if (checkType(c,o,OBJ_STRING)) {
655 unsigned long i;
656 for (i = 0; i < j; i++) {
657 if (objects[i])
658 decrRefCount(objects[i]);
659 }
660 zfree(src);
661 zfree(len);
662 zfree(objects);
663 return;
664 }
665 objects[j] = getDecodedObject(o);
666 src[j] = objects[j]->ptr;
667 len[j] = sdslen(objects[j]->ptr);
668 if (len[j] > maxlen) maxlen = len[j];
669 if (j == 0 || len[j] < minlen) minlen = len[j];
670 }
671
672 /* Compute the bit operation, if at least one string is not empty. */
673 if (maxlen) {
674 res = (unsigned char*) sdsnewlen(NULL,maxlen);
675 unsigned char output, byte;
676 unsigned long i;
677
678 /* Fast path: as far as we have data for all the input bitmaps we
679 * can take a fast path that performs much better than the
680 * vanilla algorithm. On ARM we skip the fast path since it will
681 * result in GCC compiling the code using multiple-words load/store
682 * operations that are not supported even in ARM >= v6. */
683 j = 0;
684 #ifndef USE_ALIGNED_ACCESS
685 if (minlen >= sizeof(unsigned long)*4 && numkeys <= 16) {
686 unsigned long *lp[16];
687 unsigned long *lres = (unsigned long*) res;
688
689 memcpy(lp,src,sizeof(unsigned long*)*numkeys);
690 memcpy(res,src[0],minlen);
691
692 /* Different branches per different operations for speed (sorry). */
693 if (op == BITOP_AND) {
694 while(minlen >= sizeof(unsigned long)*4) {
695 for (i = 1; i < numkeys; i++) {
696 lres[0] &= lp[i][0];
697 lres[1] &= lp[i][1];
698 lres[2] &= lp[i][2];
699 lres[3] &= lp[i][3];
700 lp[i]+=4;
701 }
702 lres+=4;
703 j += sizeof(unsigned long)*4;
704 minlen -= sizeof(unsigned long)*4;
705 }
706 } else if (op == BITOP_OR) {
707 while(minlen >= sizeof(unsigned long)*4) {
708 for (i = 1; i < numkeys; i++) {
709 lres[0] |= lp[i][0];
710 lres[1] |= lp[i][1];
711 lres[2] |= lp[i][2];
712 lres[3] |= lp[i][3];
713 lp[i]+=4;
714 }
715 lres+=4;
716 j += sizeof(unsigned long)*4;
717 minlen -= sizeof(unsigned long)*4;
718 }
719 } else if (op == BITOP_XOR) {
720 while(minlen >= sizeof(unsigned long)*4) {
721 for (i = 1; i < numkeys; i++) {
722 lres[0] ^= lp[i][0];
723 lres[1] ^= lp[i][1];
724 lres[2] ^= lp[i][2];
725 lres[3] ^= lp[i][3];
726 lp[i]+=4;
727 }
728 lres+=4;
729 j += sizeof(unsigned long)*4;
730 minlen -= sizeof(unsigned long)*4;
731 }
732 } else if (op == BITOP_NOT) {
733 while(minlen >= sizeof(unsigned long)*4) {
734 lres[0] = ~lres[0];
735 lres[1] = ~lres[1];
736 lres[2] = ~lres[2];
737 lres[3] = ~lres[3];
738 lres+=4;
739 j += sizeof(unsigned long)*4;
740 minlen -= sizeof(unsigned long)*4;
741 }
742 }
743 }
744 #endif
745
746 /* j is set to the next byte to process by the previous loop. */
747 for (; j < maxlen; j++) {
748 output = (len[0] <= j) ? 0 : src[0][j];
749 if (op == BITOP_NOT) output = ~output;
750 for (i = 1; i < numkeys; i++) {
751 int skip = 0;
752 byte = (len[i] <= j) ? 0 : src[i][j];
753 switch(op) {
754 case BITOP_AND:
755 output &= byte;
756 skip = (output == 0);
757 break;
758 case BITOP_OR:
759 output |= byte;
760 skip = (output == 0xff);
761 break;
762 case BITOP_XOR: output ^= byte; break;
763 }
764
765 if (skip) {
766 break;
767 }
768 }
769 res[j] = output;
770 }
771 }
772 for (j = 0; j < numkeys; j++) {
773 if (objects[j])
774 decrRefCount(objects[j]);
775 }
776 zfree(src);
777 zfree(len);
778 zfree(objects);
779
780 /* Store the computed value into the target key */
781 if (maxlen) {
782 o = createObject(OBJ_STRING,res);
783 setKey(c,c->db,targetkey,o,0);
784 notifyKeyspaceEvent(NOTIFY_STRING,"set",targetkey,c->db->id);
785 decrRefCount(o);
786 server.dirty++;
787 } else if (dbDelete(c->db,targetkey)) {
788 signalModifiedKey(c,c->db,targetkey);
789 notifyKeyspaceEvent(NOTIFY_GENERIC,"del",targetkey,c->db->id);
790 server.dirty++;
791 }
792 addReplyLongLong(c,maxlen); /* Return the output string length in bytes. */
793}
794
795/* BITCOUNT key [start end [BIT|BYTE]] */
796void bitcountCommand(client *c) {
797 robj *o;
798 long long start, end;
799 long strlen;
800 unsigned char *p;
801 char llbuf[LONG_STR_SIZE];
802 int isbit = 0;
803 unsigned char first_byte_neg_mask = 0, last_byte_neg_mask = 0;
804
805 /* Lookup, check for type, and return 0 for non existing keys. */
806 if ((o = lookupKeyReadOrReply(c,c->argv[1],shared.czero)) == NULL ||
807 checkType(c,o,OBJ_STRING)) return;
808 p = getObjectReadOnlyString(o,&strlen,llbuf);
809
810 /* Parse start/end range if any. */
811 if (c->argc == 4 || c->argc == 5) {
812 long long totlen = strlen;
813 /* Make sure we will not overflow */
814 serverAssert(totlen <= LLONG_MAX >> 3);
815 if (getLongLongFromObjectOrReply(c,c->argv[2],&start,NULL) != C_OK)
816 return;
817 if (getLongLongFromObjectOrReply(c,c->argv[3],&end,NULL) != C_OK)
818 return;
819 /* Convert negative indexes */
820 if (start < 0 && end < 0 && start > end) {
821 addReply(c,shared.czero);
822 return;
823 }
824 if (c->argc == 5) {
825 if (!strcasecmp(c->argv[4]->ptr,"bit")) isbit = 1;
826 else if (!strcasecmp(c->argv[4]->ptr,"byte")) isbit = 0;
827 else {
828 addReplyErrorObject(c,shared.syntaxerr);
829 return;
830 }
831 }
832 if (isbit) totlen <<= 3;
833 if (start < 0) start = totlen+start;
834 if (end < 0) end = totlen+end;
835 if (start < 0) start = 0;
836 if (end < 0) end = 0;
837 if (end >= totlen) end = totlen-1;
838 if (isbit && start <= end) {
839 /* Before converting bit offset to byte offset, create negative masks
840 * for the edges. */
841 first_byte_neg_mask = ~((1<<(8-(start&7)))-1) & 0xFF;
842 last_byte_neg_mask = (1<<(7-(end&7)))-1;
843 start >>= 3;
844 end >>= 3;
845 }
846 } else if (c->argc == 2) {
847 /* The whole string. */
848 start = 0;
849 end = strlen-1;
850 } else {
851 /* Syntax error. */
852 addReplyErrorObject(c,shared.syntaxerr);
853 return;
854 }
855
856 /* Precondition: end >= 0 && end < strlen, so the only condition where
857 * zero can be returned is: start > end. */
858 if (start > end) {
859 addReply(c,shared.czero);
860 } else {
861 long bytes = (long)(end-start+1);
862 long long count = redisPopcount(p+start,bytes);
863 if (first_byte_neg_mask != 0 || last_byte_neg_mask != 0) {
864 unsigned char firstlast[2] = {0, 0};
865 /* We may count bits of first byte and last byte which are out of
866 * range. So we need to subtract them. Here we use a trick. We set
867 * bits in the range to zero. So these bit will not be excluded. */
868 if (first_byte_neg_mask != 0) firstlast[0] = p[start] & first_byte_neg_mask;
869 if (last_byte_neg_mask != 0) firstlast[1] = p[end] & last_byte_neg_mask;
870 count -= redisPopcount(firstlast,2);
871 }
872 addReplyLongLong(c,count);
873 }
874}
875
876/* BITPOS key bit [start [end [BIT|BYTE]]] */
877void bitposCommand(client *c) {
878 robj *o;
879 long long start, end;
880 long bit, strlen;
881 unsigned char *p;
882 char llbuf[LONG_STR_SIZE];
883 int isbit = 0, end_given = 0;
884 unsigned char first_byte_neg_mask = 0, last_byte_neg_mask = 0;
885
886 /* Parse the bit argument to understand what we are looking for, set
887 * or clear bits. */
888 if (getLongFromObjectOrReply(c,c->argv[2],&bit,NULL) != C_OK)
889 return;
890 if (bit != 0 && bit != 1) {
891 addReplyError(c, "The bit argument must be 1 or 0.");
892 return;
893 }
894
895 /* If the key does not exist, from our point of view it is an infinite
896 * array of 0 bits. If the user is looking for the first clear bit return 0,
897 * If the user is looking for the first set bit, return -1. */
898 if ((o = lookupKeyRead(c->db,c->argv[1])) == NULL) {
899 addReplyLongLong(c, bit ? -1 : 0);
900 return;
901 }
902 if (checkType(c,o,OBJ_STRING)) return;
903 p = getObjectReadOnlyString(o,&strlen,llbuf);
904
905 /* Parse start/end range if any. */
906 if (c->argc == 4 || c->argc == 5 || c->argc == 6) {
907 long long totlen = strlen;
908 /* Make sure we will not overflow */
909 serverAssert(totlen <= LLONG_MAX >> 3);
910 if (getLongLongFromObjectOrReply(c,c->argv[3],&start,NULL) != C_OK)
911 return;
912 if (c->argc == 6) {
913 if (!strcasecmp(c->argv[5]->ptr,"bit")) isbit = 1;
914 else if (!strcasecmp(c->argv[5]->ptr,"byte")) isbit = 0;
915 else {
916 addReplyErrorObject(c,shared.syntaxerr);
917 return;
918 }
919 }
920 if (c->argc >= 5) {
921 if (getLongLongFromObjectOrReply(c,c->argv[4],&end,NULL) != C_OK)
922 return;
923 end_given = 1;
924 } else {
925 if (isbit) end = (totlen<<3) + 7;
926 else end = totlen-1;
927 }
928 if (isbit) totlen <<= 3;
929 /* Convert negative indexes */
930 if (start < 0) start = totlen+start;
931 if (end < 0) end = totlen+end;
932 if (start < 0) start = 0;
933 if (end < 0) end = 0;
934 if (end >= totlen) end = totlen-1;
935 if (isbit && start <= end) {
936 /* Before converting bit offset to byte offset, create negative masks
937 * for the edges. */
938 first_byte_neg_mask = ~((1<<(8-(start&7)))-1) & 0xFF;
939 last_byte_neg_mask = (1<<(7-(end&7)))-1;
940 start >>= 3;
941 end >>= 3;
942 }
943 } else if (c->argc == 3) {
944 /* The whole string. */
945 start = 0;
946 end = strlen-1;
947 } else {
948 /* Syntax error. */
949 addReplyErrorObject(c,shared.syntaxerr);
950 return;
951 }
952
953 /* For empty ranges (start > end) we return -1 as an empty range does
954 * not contain a 0 nor a 1. */
955 if (start > end) {
956 addReplyLongLong(c, -1);
957 } else {
958 long bytes = end-start+1;
959 long long pos;
960 unsigned char tmpchar;
961 if (first_byte_neg_mask) {
962 if (bit) tmpchar = p[start] & ~first_byte_neg_mask;
963 else tmpchar = p[start] | first_byte_neg_mask;
964 /* Special case, there is only one byte */
965 if (last_byte_neg_mask && bytes == 1) {
966 if (bit) tmpchar = tmpchar & ~last_byte_neg_mask;
967 else tmpchar = tmpchar | last_byte_neg_mask;
968 }
969 pos = redisBitpos(&tmpchar,1,bit);
970 /* If there are no more bytes or we get valid pos, we can exit early */
971 if (bytes == 1 || (pos != -1 && pos != 8)) goto result;
972 start++;
973 bytes--;
974 }
975 /* If the last byte has not bits in the range, we should exclude it */
976 long curbytes = bytes - (last_byte_neg_mask ? 1 : 0);
977 if (curbytes > 0) {
978 pos = redisBitpos(p+start,curbytes,bit);
979 /* If there is no more bytes or we get valid pos, we can exit early */
980 if (bytes == curbytes || (pos != -1 && pos != (long long)curbytes<<3)) goto result;
981 start += curbytes;
982 bytes -= curbytes;
983 }
984 if (bit) tmpchar = p[end] & ~last_byte_neg_mask;
985 else tmpchar = p[end] | last_byte_neg_mask;
986 pos = redisBitpos(&tmpchar,1,bit);
987
988 result:
989 /* If we are looking for clear bits, and the user specified an exact
990 * range with start-end, we can't consider the right of the range as
991 * zero padded (as we do when no explicit end is given).
992 *
993 * So if redisBitpos() returns the first bit outside the range,
994 * we return -1 to the caller, to mean, in the specified range there
995 * is not a single "0" bit. */
996 if (end_given && bit == 0 && pos == (long long)bytes<<3) {
997 addReplyLongLong(c,-1);
998 return;
999 }
1000 if (pos != -1) pos += (long long)start<<3; /* Adjust for the bytes we skipped. */
1001 addReplyLongLong(c,pos);
1002 }
1003}
1004
1005/* BITFIELD key subcommand-1 arg ... subcommand-2 arg ... subcommand-N ...
1006 *
1007 * Supported subcommands:
1008 *
1009 * GET <type> <offset>
1010 * SET <type> <offset> <value>
1011 * INCRBY <type> <offset> <increment>
1012 * OVERFLOW [WRAP|SAT|FAIL]
1013 */
1014
1015#define BITFIELD_FLAG_NONE 0
1016#define BITFIELD_FLAG_READONLY (1<<0)
1017
1018struct bitfieldOp {
1019 uint64_t offset; /* Bitfield offset. */
1020 int64_t i64; /* Increment amount (INCRBY) or SET value */
1021 int opcode; /* Operation id. */
1022 int owtype; /* Overflow type to use. */
1023 int bits; /* Integer bitfield bits width. */
1024 int sign; /* True if signed, otherwise unsigned op. */
1025};
1026
1027/* This implements both the BITFIELD command and the BITFIELD_RO command
1028 * when flags is set to BITFIELD_FLAG_READONLY: in this case only the
1029 * GET subcommand is allowed, other subcommands will return an error. */
1030void bitfieldGeneric(client *c, int flags) {
1031 robj *o;
1032 uint64_t bitoffset;
1033 int j, numops = 0, changes = 0, dirty = 0;
1034 struct bitfieldOp *ops = NULL; /* Array of ops to execute at end. */
1035 int owtype = BFOVERFLOW_WRAP; /* Overflow type. */
1036 int readonly = 1;
1037 uint64_t highest_write_offset = 0;
1038
1039 for (j = 2; j < c->argc; j++) {
1040 int remargs = c->argc-j-1; /* Remaining args other than current. */
1041 char *subcmd = c->argv[j]->ptr; /* Current command name. */
1042 int opcode; /* Current operation code. */
1043 long long i64 = 0; /* Signed SET value. */
1044 int sign = 0; /* Signed or unsigned type? */
1045 int bits = 0; /* Bitfield width in bits. */
1046
1047 if (!strcasecmp(subcmd,"get") && remargs >= 2)
1048 opcode = BITFIELDOP_GET;
1049 else if (!strcasecmp(subcmd,"set") && remargs >= 3)
1050 opcode = BITFIELDOP_SET;
1051 else if (!strcasecmp(subcmd,"incrby") && remargs >= 3)
1052 opcode = BITFIELDOP_INCRBY;
1053 else if (!strcasecmp(subcmd,"overflow") && remargs >= 1) {
1054 char *owtypename = c->argv[j+1]->ptr;
1055 j++;
1056 if (!strcasecmp(owtypename,"wrap"))
1057 owtype = BFOVERFLOW_WRAP;
1058 else if (!strcasecmp(owtypename,"sat"))
1059 owtype = BFOVERFLOW_SAT;
1060 else if (!strcasecmp(owtypename,"fail"))
1061 owtype = BFOVERFLOW_FAIL;
1062 else {
1063 addReplyError(c,"Invalid OVERFLOW type specified");
1064 zfree(ops);
1065 return;
1066 }
1067 continue;
1068 } else {
1069 addReplyErrorObject(c,shared.syntaxerr);
1070 zfree(ops);
1071 return;
1072 }
1073
1074 /* Get the type and offset arguments, common to all the ops. */
1075 if (getBitfieldTypeFromArgument(c,c->argv[j+1],&sign,&bits) != C_OK) {
1076 zfree(ops);
1077 return;
1078 }
1079
1080 if (getBitOffsetFromArgument(c,c->argv[j+2],&bitoffset,1,bits) != C_OK){
1081 zfree(ops);
1082 return;
1083 }
1084
1085 if (opcode != BITFIELDOP_GET) {
1086 readonly = 0;
1087 if (highest_write_offset < bitoffset + bits - 1)
1088 highest_write_offset = bitoffset + bits - 1;
1089 /* INCRBY and SET require another argument. */
1090 if (getLongLongFromObjectOrReply(c,c->argv[j+3],&i64,NULL) != C_OK){
1091 zfree(ops);
1092 return;
1093 }
1094 }
1095
1096 /* Populate the array of operations we'll process. */
1097 ops = zrealloc(ops,sizeof(*ops)*(numops+1));
1098 ops[numops].offset = bitoffset;
1099 ops[numops].i64 = i64;
1100 ops[numops].opcode = opcode;
1101 ops[numops].owtype = owtype;
1102 ops[numops].bits = bits;
1103 ops[numops].sign = sign;
1104 numops++;
1105
1106 j += 3 - (opcode == BITFIELDOP_GET);
1107 }
1108
1109 if (readonly) {
1110 /* Lookup for read is ok if key doesn't exit, but errors
1111 * if it's not a string. */
1112 o = lookupKeyRead(c->db,c->argv[1]);
1113 if (o != NULL && checkType(c,o,OBJ_STRING)) {
1114 zfree(ops);
1115 return;
1116 }
1117 } else {
1118 if (flags & BITFIELD_FLAG_READONLY) {
1119 zfree(ops);
1120 addReplyError(c, "BITFIELD_RO only supports the GET subcommand");
1121 return;
1122 }
1123
1124 /* Lookup by making room up to the farthest bit reached by
1125 * this operation. */
1126 if ((o = lookupStringForBitCommand(c,
1127 highest_write_offset,&dirty)) == NULL) {
1128 zfree(ops);
1129 return;
1130 }
1131 }
1132
1133 addReplyArrayLen(c,numops);
1134
1135 /* Actually process the operations. */
1136 for (j = 0; j < numops; j++) {
1137 struct bitfieldOp *thisop = ops+j;
1138
1139 /* Execute the operation. */
1140 if (thisop->opcode == BITFIELDOP_SET ||
1141 thisop->opcode == BITFIELDOP_INCRBY)
1142 {
1143 /* SET and INCRBY: We handle both with the same code path
1144 * for simplicity. SET return value is the previous value so
1145 * we need fetch & store as well. */
1146
1147 /* We need two different but very similar code paths for signed
1148 * and unsigned operations, since the set of functions to get/set
1149 * the integers and the used variables types are different. */
1150 if (thisop->sign) {
1151 int64_t oldval, newval, wrapped, retval;
1152 int overflow;
1153
1154 oldval = getSignedBitfield(o->ptr,thisop->offset,
1155 thisop->bits);
1156
1157 if (thisop->opcode == BITFIELDOP_INCRBY) {
1158 overflow = checkSignedBitfieldOverflow(oldval,
1159 thisop->i64,thisop->bits,thisop->owtype,&wrapped);
1160 newval = overflow ? wrapped : oldval + thisop->i64;
1161 retval = newval;
1162 } else {
1163 newval = thisop->i64;
1164 overflow = checkSignedBitfieldOverflow(newval,
1165 0,thisop->bits,thisop->owtype,&wrapped);
1166 if (overflow) newval = wrapped;
1167 retval = oldval;
1168 }
1169
1170 /* On overflow of type is "FAIL", don't write and return
1171 * NULL to signal the condition. */
1172 if (!(overflow && thisop->owtype == BFOVERFLOW_FAIL)) {
1173 addReplyLongLong(c,retval);
1174 setSignedBitfield(o->ptr,thisop->offset,
1175 thisop->bits,newval);
1176
1177 if (dirty || (oldval != newval))
1178 changes++;
1179 } else {
1180 addReplyNull(c);
1181 }
1182 } else {
1183 uint64_t oldval, newval, wrapped, retval;
1184 int overflow;
1185
1186 oldval = getUnsignedBitfield(o->ptr,thisop->offset,
1187 thisop->bits);
1188
1189 if (thisop->opcode == BITFIELDOP_INCRBY) {
1190 newval = oldval + thisop->i64;
1191 overflow = checkUnsignedBitfieldOverflow(oldval,
1192 thisop->i64,thisop->bits,thisop->owtype,&wrapped);
1193 if (overflow) newval = wrapped;
1194 retval = newval;
1195 } else {
1196 newval = thisop->i64;
1197 overflow = checkUnsignedBitfieldOverflow(newval,
1198 0,thisop->bits,thisop->owtype,&wrapped);
1199 if (overflow) newval = wrapped;
1200 retval = oldval;
1201 }
1202 /* On overflow of type is "FAIL", don't write and return
1203 * NULL to signal the condition. */
1204 if (!(overflow && thisop->owtype == BFOVERFLOW_FAIL)) {
1205 addReplyLongLong(c,retval);
1206 setUnsignedBitfield(o->ptr,thisop->offset,
1207 thisop->bits,newval);
1208
1209 if (dirty || (oldval != newval))
1210 changes++;
1211 } else {
1212 addReplyNull(c);
1213 }
1214 }
1215 } else {
1216 /* GET */
1217 unsigned char buf[9];
1218 long strlen = 0;
1219 unsigned char *src = NULL;
1220 char llbuf[LONG_STR_SIZE];
1221
1222 if (o != NULL)
1223 src = getObjectReadOnlyString(o,&strlen,llbuf);
1224
1225 /* For GET we use a trick: before executing the operation
1226 * copy up to 9 bytes to a local buffer, so that we can easily
1227 * execute up to 64 bit operations that are at actual string
1228 * object boundaries. */
1229 memset(buf,0,9);
1230 int i;
1231 uint64_t byte = thisop->offset >> 3;
1232 for (i = 0; i < 9; i++) {
1233 if (src == NULL || i+byte >= (uint64_t)strlen) break;
1234 buf[i] = src[i+byte];
1235 }
1236
1237 /* Now operate on the copied buffer which is guaranteed
1238 * to be zero-padded. */
1239 if (thisop->sign) {
1240 int64_t val = getSignedBitfield(buf,thisop->offset-(byte*8),
1241 thisop->bits);
1242 addReplyLongLong(c,val);
1243 } else {
1244 uint64_t val = getUnsignedBitfield(buf,thisop->offset-(byte*8),
1245 thisop->bits);
1246 addReplyLongLong(c,val);
1247 }
1248 }
1249 }
1250
1251 if (changes) {
1252 signalModifiedKey(c,c->db,c->argv[1]);
1253 notifyKeyspaceEvent(NOTIFY_STRING,"setbit",c->argv[1],c->db->id);
1254 server.dirty += changes;
1255 }
1256 zfree(ops);
1257}
1258
1259void bitfieldCommand(client *c) {
1260 bitfieldGeneric(c, BITFIELD_FLAG_NONE);
1261}
1262
1263void bitfieldroCommand(client *c) {
1264 bitfieldGeneric(c, BITFIELD_FLAG_READONLY);
1265}
1266