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) */ |
40 | long 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. */ |
101 | long 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 | |
209 | void 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 | |
224 | void 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 | |
229 | uint64_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 | |
243 | int64_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 | |
288 | int 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 | |
314 | handle_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 | |
325 | int 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 | |
358 | handle_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. */ |
382 | void 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. */ |
414 | int 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. */ |
450 | int 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. */ |
481 | robj *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. */ |
513 | unsigned 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 */ |
532 | void 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 */ |
579 | void 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 */ |
606 | REDIS_NO_SANITIZE("alignment" ) |
607 | void 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]] */ |
796 | void 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]]] */ |
877 | void 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 | |
1018 | struct 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. */ |
1030 | void 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 | |
1259 | void bitfieldCommand(client *c) { |
1260 | bitfieldGeneric(c, BITFIELD_FLAG_NONE); |
1261 | } |
1262 | |
1263 | void bitfieldroCommand(client *c) { |
1264 | bitfieldGeneric(c, BITFIELD_FLAG_READONLY); |
1265 | } |
1266 | |