Jens Axboe | 65f21d6 | 2014-02-20 13:29:42 -0800 | [diff] [blame] | 1 | /* |
| 2 | xxHash - Fast Hash algorithm |
| 3 | Header File |
| 4 | Copyright (C) 2012-2014, Yann Collet. |
| 5 | BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) |
| 6 | |
| 7 | Redistribution and use in source and binary forms, with or without |
| 8 | modification, are permitted provided that the following conditions are |
| 9 | met: |
| 10 | |
| 11 | * Redistributions of source code must retain the above copyright |
| 12 | notice, this list of conditions and the following disclaimer. |
| 13 | * Redistributions in binary form must reproduce the above |
| 14 | copyright notice, this list of conditions and the following disclaimer |
| 15 | in the documentation and/or other materials provided with the |
| 16 | distribution. |
| 17 | |
| 18 | THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
| 19 | "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
| 20 | LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
| 21 | A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
| 22 | OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
| 23 | SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT |
| 24 | LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
| 25 | DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
| 26 | THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| 27 | (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
| 28 | OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| 29 | |
| 30 | You can contact the author at : |
| 31 | - xxHash source repository : http://code.google.com/p/xxhash/ |
| 32 | */ |
| 33 | |
| 34 | /* Notice extracted from xxHash homepage : |
| 35 | |
| 36 | xxHash is an extremely fast Hash algorithm, running at RAM speed limits. |
| 37 | It also successfully passes all tests from the SMHasher suite. |
| 38 | |
| 39 | Comparison (single thread, Windows Seven 32 bits, using SMHasher on a Core 2 Duo @3GHz) |
| 40 | |
| 41 | Name Speed Q.Score Author |
| 42 | xxHash 5.4 GB/s 10 |
| 43 | CrapWow 3.2 GB/s 2 Andrew |
| 44 | MumurHash 3a 2.7 GB/s 10 Austin Appleby |
| 45 | SpookyHash 2.0 GB/s 10 Bob Jenkins |
| 46 | SBox 1.4 GB/s 9 Bret Mulvey |
| 47 | Lookup3 1.2 GB/s 9 Bob Jenkins |
| 48 | SuperFastHash 1.2 GB/s 1 Paul Hsieh |
| 49 | CityHash64 1.05 GB/s 10 Pike & Alakuijala |
| 50 | FNV 0.55 GB/s 5 Fowler, Noll, Vo |
| 51 | CRC32 0.43 GB/s 9 |
| 52 | MD5-32 0.33 GB/s 10 Ronald L. Rivest |
| 53 | SHA1-32 0.28 GB/s 10 |
| 54 | |
| 55 | Q.Score is a measure of quality of the hash function. |
| 56 | It depends on successfully passing SMHasher test set. |
| 57 | 10 is a perfect score. |
| 58 | */ |
| 59 | |
| 60 | #pragma once |
| 61 | |
| 62 | #if defined (__cplusplus) |
| 63 | extern "C" { |
| 64 | #endif |
| 65 | |
| 66 | #include <inttypes.h> |
| 67 | |
| 68 | struct XXH_state32_t |
| 69 | { |
| 70 | uint64_t total_len; |
| 71 | uint32_t seed; |
| 72 | uint32_t v1; |
| 73 | uint32_t v2; |
| 74 | uint32_t v3; |
| 75 | uint32_t v4; |
| 76 | int memsize; |
| 77 | char memory[16]; |
| 78 | }; |
| 79 | |
| 80 | //**************************** |
| 81 | // Type |
| 82 | //**************************** |
| 83 | typedef enum { XXH_OK=0, XXH_ERROR } XXH_errorcode; |
| 84 | |
| 85 | |
| 86 | |
| 87 | //**************************** |
| 88 | // Simple Hash Functions |
| 89 | //**************************** |
| 90 | |
Jens Axboe | ee4ceb7 | 2014-09-26 14:57:41 -0600 | [diff] [blame] | 91 | uint32_t XXH32 (const void* input, uint32_t len, uint32_t seed); |
Jens Axboe | 65f21d6 | 2014-02-20 13:29:42 -0800 | [diff] [blame] | 92 | |
| 93 | /* |
| 94 | XXH32() : |
| 95 | Calculate the 32-bits hash of sequence of length "len" stored at memory address "input". |
| 96 | The memory between input & input+len must be valid (allocated and read-accessible). |
| 97 | "seed" can be used to alter the result predictably. |
| 98 | This function successfully passes all SMHasher tests. |
| 99 | Speed on Core 2 Duo @ 3 GHz (single thread, SMHasher benchmark) : 5.4 GB/s |
| 100 | Note that "len" is type "int", which means it is limited to 2^31-1. |
| 101 | If your data is larger, use the advanced functions below. |
| 102 | */ |
| 103 | |
| 104 | |
| 105 | |
| 106 | //**************************** |
| 107 | // Advanced Hash Functions |
| 108 | //**************************** |
| 109 | |
| 110 | void* XXH32_init (unsigned int seed); |
| 111 | XXH_errorcode XXH32_update (void* state, const void* input, int len); |
| 112 | unsigned int XXH32_digest (void* state); |
| 113 | |
| 114 | /* |
| 115 | These functions calculate the xxhash of an input provided in several small packets, |
| 116 | as opposed to an input provided as a single block. |
| 117 | |
| 118 | It must be started with : |
| 119 | void* XXH32_init() |
| 120 | The function returns a pointer which holds the state of calculation. |
| 121 | |
| 122 | This pointer must be provided as "void* state" parameter for XXH32_update(). |
| 123 | XXH32_update() can be called as many times as necessary. |
| 124 | The user must provide a valid (allocated) input. |
| 125 | The function returns an error code, with 0 meaning OK, and any other value meaning there is an error. |
| 126 | Note that "len" is type "int", which means it is limited to 2^31-1. |
| 127 | If your data is larger, it is recommended to chunk your data into blocks |
| 128 | of size for example 2^30 (1GB) to avoid any "int" overflow issue. |
| 129 | |
| 130 | Finally, you can end the calculation anytime, by using XXH32_digest(). |
| 131 | This function returns the final 32-bits hash. |
| 132 | You must provide the same "void* state" parameter created by XXH32_init(). |
| 133 | Memory will be freed by XXH32_digest(). |
| 134 | */ |
| 135 | |
| 136 | |
Castor Fu | 190b8f0 | 2014-03-20 10:59:29 -0700 | [diff] [blame] | 137 | int XXH32_sizeofState(void); |
Jens Axboe | 65f21d6 | 2014-02-20 13:29:42 -0800 | [diff] [blame] | 138 | XXH_errorcode XXH32_resetState(void* state, unsigned int seed); |
| 139 | |
| 140 | #define XXH32_SIZEOFSTATE 48 |
| 141 | typedef struct { long long ll[(XXH32_SIZEOFSTATE+(sizeof(long long)-1))/sizeof(long long)]; } XXH32_stateSpace_t; |
| 142 | /* |
| 143 | These functions allow user application to make its own allocation for state. |
| 144 | |
| 145 | XXH32_sizeofState() is used to know how much space must be allocated for the xxHash 32-bits state. |
| 146 | Note that the state must be aligned to access 'long long' fields. Memory must be allocated and referenced by a pointer. |
| 147 | This pointer must then be provided as 'state' into XXH32_resetState(), which initializes the state. |
| 148 | |
| 149 | For static allocation purposes (such as allocation on stack, or freestanding systems without malloc()), |
| 150 | use the structure XXH32_stateSpace_t, which will ensure that memory space is large enough and correctly aligned to access 'long long' fields. |
| 151 | */ |
| 152 | |
| 153 | |
| 154 | unsigned int XXH32_intermediateDigest (void* state); |
| 155 | /* |
| 156 | This function does the same as XXH32_digest(), generating a 32-bit hash, |
| 157 | but preserve memory context. |
| 158 | This way, it becomes possible to generate intermediate hashes, and then continue feeding data with XXH32_update(). |
| 159 | To free memory context, use XXH32_digest(), or free(). |
| 160 | */ |
| 161 | |
| 162 | |
| 163 | |
| 164 | //**************************** |
| 165 | // Deprecated function names |
| 166 | //**************************** |
| 167 | // The following translations are provided to ease code transition |
| 168 | // You are encouraged to no longer this function names |
| 169 | #define XXH32_feed XXH32_update |
| 170 | #define XXH32_result XXH32_digest |
| 171 | #define XXH32_getIntermediateResult XXH32_intermediateDigest |
| 172 | |
| 173 | |
| 174 | |
| 175 | #if defined (__cplusplus) |
| 176 | } |
| 177 | #endif |