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