README.md
1xxHash - Extremely fast hash algorithm
2======================================
3
4xxHash is an Extremely fast Hash algorithm, running at RAM speed limits.
5It successfully completes the [SMHasher](http://code.google.com/p/smhasher/wiki/SMHasher) test suite
6which evaluates collision, dispersion and randomness qualities of hash functions.
7Code is highly portable, and hashes are identical on all platforms (little / big endian).
8
9|Branch |Status |
10|------------|---------|
11|master | [](https://travis-ci.org/Cyan4973/xxHash?branch=master) |
12|dev | [](https://travis-ci.org/Cyan4973/xxHash?branch=dev) |
13
14
15
16Benchmarks
17-------------------------
18
19The benchmark uses SMHasher speed test, compiled with Visual 2010 on a Windows Seven 32-bit box.
20The reference system uses a Core 2 Duo @3GHz
21
22
23| Name | Speed | Quality | Author |
24|---------------|-------------|:-------:|-------------------|
25| [xxHash] | 5.4 GB/s | 10 | Y.C. |
26| MurmurHash 3a | 2.7 GB/s | 10 | Austin Appleby |
27| SBox | 1.4 GB/s | 9 | Bret Mulvey |
28| Lookup3 | 1.2 GB/s | 9 | Bob Jenkins |
29| CityHash64 | 1.05 GB/s | 10 | Pike & Alakuijala |
30| FNV | 0.55 GB/s | 5 | Fowler, Noll, Vo |
31| CRC32 | 0.43 GB/s † | 9 | |
32| MD5-32 | 0.33 GB/s | 10 | Ronald L.Rivest |
33| SHA1-32 | 0.28 GB/s | 10 | |
34
35[xxHash]: http://www.xxhash.com
36
37Note †: SMHasher's CRC32 implementation is known to be slow. Faster implementations exist.
38
39Q.Score is a measure of quality of the hash function.
40It depends on successfully passing SMHasher test set.
4110 is a perfect score.
42Algorithms with a score < 5 are not listed on this table.
43
44A more recent version, XXH64, has been created thanks to [Mathias Westerdahl](https://github.com/JCash),
45which offers superior speed and dispersion for 64-bit systems.
46Note however that 32-bit applications will still run faster using the 32-bit version.
47
48SMHasher speed test, compiled using GCC 4.8.2, on Linux Mint 64-bit.
49The reference system uses a Core i5-3340M @2.7GHz
50
51| Version | Speed on 64-bit | Speed on 32-bit |
52|------------|------------------|------------------|
53| XXH64 | 13.8 GB/s | 1.9 GB/s |
54| XXH32 | 6.8 GB/s | 6.0 GB/s |
55
56This project also includes a command line utility, named `xxhsum`, offering similar features as `md5sum`,
57thanks to [Takayuki Matsuoka](https://github.com/t-mat) contributions.
58
59
60### License
61
62The library files `xxhash.c` and `xxhash.h` are BSD licensed.
63The utility `xxhsum` is GPL licensed.
64
65
66### Build modifiers
67
68The following macros can be set at compilation time,
69they modify libxxhash behavior. They are all disabled by default.
70
71- `XXH_INLINE_ALL` : Make all functions `inline`, with bodies directly included within `xxhash.h`.
72 Inlining functions is beneficial for speed on small keys.
73 It's _extremely effective_ when key length is expressed as _a compile time constant_,
74 with performance improvements observed in the +200% range .
75 See [this article](https://fastcompression.blogspot.com/2018/03/xxhash-for-small-keys-impressive-power.html) for details.
76 Note: there is no need for an `xxhash.o` object file in this case.
77- `XXH_REROLL` : reduce size of generated code. Impact on performance vary, depending on platform and algorithm.
78- `XXH_ACCEPT_NULL_INPUT_POINTER` : if set to `1`, when input is a `NULL` pointer,
79 xxhash result is the same as a zero-length input
80 (instead of a dereference segfault).
81 Adds one branch at the beginning of the hash.
82- `XXH_FORCE_MEMORY_ACCESS` : default method `0` uses a portable `memcpy()` notation.
83 Method `1` uses a gcc-specific `packed` attribute, which can provide better performance for some targets.
84 Method `2` forces unaligned reads, which is not standard compliant, but might sometimes be the only way to extract better read performance.
85- `XXH_CPU_LITTLE_ENDIAN` : by default, endianess is determined at compile time.
86 It's possible to skip auto-detection and force format to little-endian, by setting this macro to 1.
87 Setting it to 0 forces big-endian.
88- `XXH_PRIVATE_API` : same impact as `XXH_INLINE_ALL`.
89 Name underlines that XXH_* symbols will not be published.
90- `XXH_NAMESPACE` : prefix all symbols with the value of `XXH_NAMESPACE`.
91 Useful to evade symbol naming collisions,
92 in case of multiple inclusions of xxHash source code.
93 Client applications can still use regular function name,
94 symbols are automatically translated through `xxhash.h`.
95- `XXH_STATIC_LINKING_ONLY` : gives access to state declaration for static allocation.
96 Incompatible with dynamic linking, due to risks of ABI changes.
97- `XXH_NO_LONG_LONG` : removes support for XXH64,
98 for targets without 64-bit support.
99- `XXH_IMPORT` : MSVC specific : should only be defined for dynamic linking, it prevents linkage errors.
100
101
102### Example
103
104Calling xxhash 64-bit variant from a C program :
105
106```C
107#include "xxhash.h"
108
109 (...)
110 XXH64_hash_t hash = XXH64(buffer, size, seed);
111}
112```
113
114Using streaming variant is more involved, but makes it possible to provide data incrementally :
115```C
116#include "stdlib.h" /* abort() */
117#include "xxhash.h"
118
119
120XXH64_hash_t calcul_hash_streaming(FileHandler fh)
121{
122 /* create a hash state */
123 XXH64_state_t* const state = XXH64_createState();
124 if (state==NULL) abort();
125
126 size_t const bufferSize = SOME_SIZE;
127 void* const buffer = malloc(bufferSize);
128 if (buffer==NULL) abort();
129
130 /* Initialize state with selected seed */
131 XXH64_hash_t const seed = 0; /* or any other value */
132 if (XXH64_reset(state, seed) == XXH_ERROR) abort();
133
134 /* Feed the state with input data, any size, any number of times */
135 (...)
136 while ( /* any condition */ ) {
137 size_t const length = get_more_data(buffer, bufferSize, fh);
138 if (XXH64_update(state, buffer, length) == XXH_ERROR) abort();
139 (...)
140 }
141 (...)
142
143 /* Get the hash */
144 XXH64_hash_t const hash = XXH64_digest(state);
145
146 /* State can be re-used; in this example, it is simply freed */
147 free(buffer);
148 XXH64_freeState(state);
149
150 return hash;
151}
152```
153
154### New experimental hash algorithm
155
156Starting with `v0.7.0`, the library includes a new algorithm, named `XXH3`,
157able to generate 64 and 128-bits hashes.
158
159The new algorithm is much faster than its predecessors,
160for both long and small inputs,
161as can be observed in following graphs :
162
163
164
165
166
167The algorithm is currently labeled experimental, its return values can still change in future versions.
168It can already be used for ephemeral data, and for tests, but avoid storing long-term hash values yet.
169
170To access experimental prototypes, one need to unlock their declaration using macro `XXH_STATIC_LINKING_ONLY`.
171`XXH3` will be stabilized in a future version.
172This period is used to collect users' feedback.
173
174
175### Other programming languages
176
177Beyond the C reference version,
178xxHash is also available on many programming languages,
179thanks to great contributors.
180They are [listed here](http://www.xxhash.com/#other-languages).
181
182
183### Branch Policy
184
185> - The "master" branch is considered stable, at all times.
186> - The "dev" branch is the one where all contributions must be merged
187 before being promoted to master.
188> + If you plan to propose a patch, please commit into the "dev" branch,
189 or its own feature branch.
190 Direct commit to "master" are not permitted.
191
){kind=link}
){kind=link}
){kind=link}
){kind=link}