summaryrefslogtreecommitdiff
path: root/src/bitops.c
Commit message (Collapse)AuthorAgeFilesLines
* Minor aesthetic fixes to PR #3264.antirez2016-06-161-5/+5
| | | | | | | Comment format fixed + local var modified from camel case to underscore separators as Redis code base normally does (camel case is mostly used for global symbols like structure names, function names, global vars, ...).
* Merge pull request #3264 from oranagra/bitfield_fix2Salvatore Sanfilippo2016-06-161-9/+20
|\ | | | | fix crash in BITFIELD GET on non existing key or wrong type see #3259
| * check WRONGTYPE in BITFIELD before looping on the operations.oranagra2016-05-241-9/+18
| | | | | | | | | | optimization: lookup key only once, and grow at once to the max need fixes #3259 and #3221, and also an early return if wrongtype is discovered by SET
| * fix crash in BITFIELD GET on non existing key or wrong type see #3259oranagra2016-05-241-3/+5
| | | | | | | | this was a bug in the recent refactoring: bee963c4459223d874e3294a0d8638a588d33c8e
* | GETRANGE: return empty string with negative, inverted start/end.antirez2016-06-151-2/+2
| |
* | Remove additional round brackets from fix for #3282.antirez2016-06-151-1/+1
| |
* | Merge pull request #3282 from wenduo/unstableSalvatore Sanfilippo2016-06-151-0/+4
|\ \ | | | | | | bitcount bug:return non-zero value when start > end (both negative)
| * | bitcount bug:return non-zero value when start > end (both negative)wenduo2016-05-301-0/+4
| |/
* | fix some compiler warningsPierre Chapuis2016-06-051-2/+2
| |
* | Avoid undefined behavior in BITFIELD implementation.antirez2016-05-311-8/+15
|/ | | | | | | | Probably there is no compiler that will actaully break the code or raise a signal for unsigned -> signed overflowing conversion, still it was apparently possible to write it in a more correct way. All tests passing.
* Code to access object string bytes repeated 3x refactored into 1 function.antirez2016-05-181-35/+39
|
* fix crash in BITFIELD GET when key is integer encodedoranagra2016-05-101-3/+15
|
* BITFIELD: Farest bit set is offset+bits-1. Off by one error fixed.antirez2016-03-021-2/+4
|
* More BITFIELD fixes. Overflow conditional simplified.antirez2016-03-021-9/+8
| | | | See issue #3114.
* bitops/bitfield: fix length, overflow condition and *signSun He2016-03-021-5/+8
|
* BITFIELD: refactoring & fix of retval on FAIL.antirez2016-02-291-8/+24
|
* BITFIELD: Fix #<index> form parsing.antirez2016-02-261-6/+4
|
* BITFIELD: Support #<index> offsets form.antirez2016-02-261-6/+23
|
* BITFIELD command initial implementation.antirez2016-02-261-32/+474
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | The new bitfield command is an extension to the Redis bit operations, where not just single bit operations are performed, but the array of bits composing a string, can be addressed at random, not aligned offsets, with any width unsigned and signed integers like u8, s5, u10 (up to 64 bit signed integers and 63 bit unsigned integers). The BITFIELD command supports subcommands that can SET, GET, or INCRBY those arbitrary bit counters, with multiple overflow semantics. Trivial and credits: A similar command was imagined a few times in the past, but for some reason looked a bit far fetched or not well specified. Finally the command was proposed again in a clear form by Yoav Steinberg from Redis Labs, that proposed a set of commands on arbitrary sized integers stored at bit offsets. Starting from this proposal I wrote an initial specification of a single command with sub-commands similar to what Yoav envisioned, using short names for types definitions, and adding control on the overflow. This commit is the resulting implementation. Examples: BITFIELD mykey OVERFLOW wrap INCRBY i2 10 -1 GET i2 10
* RDMF: More consistent define names.antirez2015-07-271-4/+4
|
* RDMF: REDIS_OK REDIS_ERR -> C_OK C_ERR.antirez2015-07-261-12/+12
|
* RDMF: OBJ_ macros for object related stuff.antirez2015-07-261-9/+9
|
* RDMF: use client instead of redisClient, like Disque.antirez2015-07-261-6/+6
|
* RDMF (Redis/Disque merge friendlyness) refactoring WIP 1.antirez2015-07-261-1/+1
|
* Bitops: Stop overallocating storage space on setMatt Stancliff2014-12-111-5/+3
| | | | | | | | | | | | | | Previously the string was created empty then re-sized to fit the offset, but sds resize causes the sds to over-allocate by at least 1 MB (which is a lot when you are operating at bit-level access). This also improves the speed of initial sets by 2% to 6% based on quick testing. Patch logic provided by @oranagra Fixes #1918
* bitops.c/bitopCommand: skip short minlen for FAST PATHSun He2014-12-031-1/+1
|
* bitops.c/redisPopcount: little optimization in loopSun He2014-12-021-8/+20
|
* Remove warnings and improve integer sign correctness.antirez2014-08-131-9/+11
|
* String value unsharing refactored into proper function.antirez2014-03-301-8/+1
| | | | | | | | | | | All the Redis functions that need to modify the string value of a key in a destructive way (APPEND, SETBIT, SETRANGE, ...) require to make the object unshared (if refcount > 1) and encoded in raw format (if encoding is not already REDIS_ENCODING_RAW). This was cut & pasted many times in multiple places of the code. This commit puts the small logic needed into a function called dbUnshareStringValue().
* warnigns -> warnings in redisBitpos().antirez2014-02-271-1/+1
|
* More consistent BITPOS behavior with bit=0 and ranges.antirez2014-02-271-9/+15
| | | | | | | | | | | | | | | | | | | | | | | | | | | With the new behavior it is possible to specify just the start in the range (the end will be assumed to be the first byte), or it is possible to specify both start and end. This is useful to change the behavior of the command when looking for zeros inside a string. 1) If the user specifies both start and end, and no 0 is found inside the range, the command returns -1. 2) If instead no range is specified, or just the start is given, even if in the actual string no 0 bit is found, the command returns the first bit on the right after the end of the string. So for example if the string stored at key foo is "\xff\xff": BITPOS foo (returns 16) BITPOS foo 0 -1 (returns -1) BITPOS foo 0 (returns 16) The idea is that when no end is given the user is just looking for the first bit that is zero and can be set to 1 with SETBIT, as it is "available". Instead when a specific range is given, we just look for a zero within the boundaries of the range.
* Initial implementation of BITPOS.antirez2014-02-271-1/+169
| | | | | It appears to work but more stress testing, and both unit tests and fuzzy testing, is needed in order to ensure the implementation is sane.
* Fix misaligned word access in redisPopcount().antirez2014-02-271-2/+9
|
* Introduction of a new string encoding: EMBSTRantirez2013-07-221-5/+5
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Previously two string encodings were used for string objects: 1) REDIS_ENCODING_RAW: a string object with obj->ptr pointing to an sds stirng. 2) REDIS_ENCODING_INT: a string object where the obj->ptr void pointer is casted to a long. This commit introduces a experimental new encoding called REDIS_ENCODING_EMBSTR that implements an object represented by an sds string that is not modifiable but allocated in the same memory chunk as the robj structure itself. The chunk looks like the following: +--------------+-----------+------------+--------+----+ | robj data... | robj->ptr | sds header | string | \0 | +--------------+-----+-----+------------+--------+----+ | ^ +-----------------------+ The robj->ptr points to the contiguous sds string data, so the object can be manipulated with the same functions used to manipulate plan string objects, however we need just on malloc and one free in order to allocate or release this kind of objects. Moreover it has better cache locality. This new allocation strategy should benefit both the memory usage and the performances. A performance gain between 60 and 70% was observed during micro-benchmarks, however there is more work to do to evaluate the performance impact and the memory usage behavior.
* function renamed: popcount_binary -> redisPopcount.antirez2013-06-261-2/+2
|
* rename popcount to popcount_binary to avoid a conflict with NetBSD libcYAMAMOTO Takashi2013-05-171-2/+2
| | | | | | | NetBSD-current's libc has a function named popcount. hiding these extensions using feature macros is not possible because redis uses other extensions covered by the same feature macro. eg. inet_aton
* Revert "use long long instead of size_t make it more safe"antirez2013-05-081-2/+2
| | | | | | | | | | | | This reverts commit 2c75f2cf1aa0d9cc8256517bd6f3d8a82088ee1a. After further analysis, it is very unlikely that we'll raise the string size limit to > 512MB, and at the same time such big strings will be used in 32 bit systems. Better to revert to size_t so that 32 bit processors will not be forced to use a 64 bit counter in normal operations, that is currently completely useless.
* use long long instead of size_t make it more safeJiahao Huang2013-05-071-2/+2
|
* in 32bit machine, popcount don't work with a input string length up to 512 MB,Jiahao Huang2013-05-071-2/+2
| | | | bitcount commant may return negtive integer with string length more than 256 MB
* Keyspace events: it is now possible to select subclasses of events.antirez2013-01-281-3/+3
| | | | | | | | | When keyspace events are enabled, the overhead is not sever but noticeable, so this commit introduces the ability to select subclasses of events in order to avoid to generate events the user is not interested in. The events can be selected using redis.conf or CONFIG SET / GET.
* Keyspace events added for more commands.antirez2013-01-281-0/+3
|
* Fixed many typos.guiquanz2013-01-191-2/+2
|
* BSD license added to every C source and header file.antirez2012-11-081-0/+30
|
* BITCOUNT: fix segmentation fault.Haruto Otake2012-09-051-3/+2
| | | | | | | | | | | | | | | | | remove unsafe and unnecessary cast. until now, this cast may lead segmentation fault when end > UINT_MAX setbit foo 0 1 bitcount 0 4294967295 => ok bitcount 0 4294967296 => cause segmentation fault. Note by @antirez: the commit was modified a bit to also change the string length type to long, since it's guaranteed to be at max 512 MB in size, so we can work with the same type across all the code path. A regression test was also added.
* Don't assume that "char" is signed.antirez2012-07-181-3/+3
| | | | | | | | | | | | For the C standard char can be either signed or unsigned, it's up to the compiler, but Redis assumed that it was signed in a few places. The practical effect of this patch is that now Redis 2.6 will run correctly in every system where char is unsigned, notably the RaspBerry PI and other ARM systems with GCC. Thanks to Georgi Marinov (@eesn on twitter) that reported the problem and allowed me to use his RaspBerry via SSH to trace and fix the issue!
* BITOP bug when called against non existing keys fixed.antirez2012-05-311-0/+1
| | | | | | | | | | | | | | | | | | | | In the issue #529 an user reported a bug that can be triggered with the following code: flushdb set a "\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00" bitop or x a b The bug was introduced with the speed optimization in commit 8bbc076 that specializes every BITOP operation loop up to the minimum length of the input strings. However the computation of the minimum length contained an error when a non existing key was present in the input, after a key that was non zero length. This commit fixes the bug and adds a regression test for it.
* BITOP command 10x speed improvement.antirez2012-05-241-1/+69
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This commit adds a fast-path to the BITOP that can be used for all the bytes from 0 to the minimal length of the string, and if there are at max 16 input keys. Often the intersected bitmaps are roughly the same size, so this optimization can provide a 10x speed boost to most real world usages of the command. Bytes are processed four full words at a time, in loops specialized for the specific BITOP sub-command, without the need to check for length issues with the inputs (since we run this algorithm only as far as there is data from all the keys at the same time). The remaining part of the string is intersected in the usual way using the slow but generic algorith. It is possible to do better than this with inputs that are not roughly the same size, sorting the input keys by length, by initializing the result string in a smarter way, and noticing that the final part of the output string composed of only data from the longest string does not need any proecessing since AND, OR and XOR against an empty string does not alter the output (zero in the first case, and the original string in the other two cases). More implementations will be implemented later likely, but this should be enough to release Redis 2.6-RC4 with bitops merged in. Note: this commit also adds better testing for BITOP NOT command, that is currently the faster and hard to optimize further since it just flips the bits of a single input string.
* BITOP: handle integer encoded objects correctly.antirez2012-05-241-2/+16
| | | | | | | | | | | A bug in the implementation caused BITOP to crash the server if at least one one of the source objects was integer encoded. The new implementation takes an additional array of Redis objects pointers and calls getDecodedObject() to get a reference to a string encoded object, and then uses decrRefCount() to release the object. Tests modified to cover the regression and improve coverage.
* BITCOUNT performance improved.antirez2012-05-241-13/+22
| | | | | | | | | | | | | At Redis's default optimization level the command is now much faster, always using a constant-time bit manipualtion technique to count bits instead of GCC builtin popcount, and unrolling the loop. The current implementation performance is 1.5GB/s in a MBA 11" (1.8 Ghz i7) compiled with both GCC and clang. The algorithm used is described here: http://graphics.stanford.edu/~seander/bithacks.html
* bitop.c renamed bitops.cantirez2012-05-241-0/+288
bitop.c contains the "Bit related string operations" so it seems more logical to call it bitops instead of bitop. This also makes it matching the name of the test (unit/bitops.tcl).
View Lorry Controller Status