1 /* 2 * xxHash - Extremely Fast Hash algorithm 3 * Copyright (C) 2012-2016, Yann Collet. 4 * 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 * This program is free software; you can redistribute it and/or modify it under 31 * the terms of the GNU General Public License version 2 as published by the 32 * Free Software Foundation. This program is dual-licensed; you may select 33 * either version 2 of the GNU General Public License ("GPL") or BSD license 34 * ("BSD"). 35 * 36 * You can contact the author at: 37 * - xxHash homepage: https://cyan4973.github.io/xxHash/ 38 * - xxHash source repository: https://github.com/Cyan4973/xxHash 39 */ 40 41 /* 42 * Notice extracted from xxHash homepage: 43 * 44 * xxHash is an extremely fast Hash algorithm, running at RAM speed limits. 45 * It also successfully passes all tests from the SMHasher suite. 46 * 47 * Comparison (single thread, Windows Seven 32 bits, using SMHasher on a Core 2 48 * Duo @3GHz) 49 * 50 * Name Speed Q.Score Author 51 * xxHash 5.4 GB/s 10 52 * CrapWow 3.2 GB/s 2 Andrew 53 * MumurHash 3a 2.7 GB/s 10 Austin Appleby 54 * SpookyHash 2.0 GB/s 10 Bob Jenkins 55 * SBox 1.4 GB/s 9 Bret Mulvey 56 * Lookup3 1.2 GB/s 9 Bob Jenkins 57 * SuperFastHash 1.2 GB/s 1 Paul Hsieh 58 * CityHash64 1.05 GB/s 10 Pike & Alakuijala 59 * FNV 0.55 GB/s 5 Fowler, Noll, Vo 60 * CRC32 0.43 GB/s 9 61 * MD5-32 0.33 GB/s 10 Ronald L. Rivest 62 * SHA1-32 0.28 GB/s 10 63 * 64 * Q.Score is a measure of quality of the hash function. 65 * It depends on successfully passing SMHasher test set. 66 * 10 is a perfect score. 67 * 68 * A 64-bits version, named xxh64 offers much better speed, 69 * but for 64-bits applications only. 70 * Name Speed on 64 bits Speed on 32 bits 71 * xxh64 13.8 GB/s 1.9 GB/s 72 * xxh32 6.8 GB/s 6.0 GB/s 73 */ 74 75 #ifndef XXHASH_H 76 #define XXHASH_H 77 78 #include <linux/types.h> 79 80 /*-**************************** 81 * Simple Hash Functions 82 *****************************/ 83 84 /** 85 * xxh32() - calculate the 32-bit hash of the input with a given seed. 86 * 87 * @input: The data to hash. 88 * @length: The length of the data to hash. 89 * @seed: The seed can be used to alter the result predictably. 90 * 91 * Speed on Core 2 Duo @ 3 GHz (single thread, SMHasher benchmark) : 5.4 GB/s 92 * 93 * Return: The 32-bit hash of the data. 94 */ 95 uint32_t xxh32(const void *input, size_t length, uint32_t seed); 96 97 /** 98 * xxh64() - calculate the 64-bit hash of the input with a given seed. 99 * 100 * @input: The data to hash. 101 * @length: The length of the data to hash. 102 * @seed: The seed can be used to alter the result predictably. 103 * 104 * This function runs 2x faster on 64-bit systems, but slower on 32-bit systems. 105 * 106 * Return: The 64-bit hash of the data. 107 */ 108 uint64_t xxh64(const void *input, size_t length, uint64_t seed); 109 110 /** 111 * xxhash() - calculate wordsize hash of the input with a given seed 112 * @input: The data to hash. 113 * @length: The length of the data to hash. 114 * @seed: The seed can be used to alter the result predictably. 115 * 116 * If the hash does not need to be comparable between machines with 117 * different word sizes, this function will call whichever of xxh32() 118 * or xxh64() is faster. 119 * 120 * Return: wordsize hash of the data. 121 */ 122 xxhash(const void * input,size_t length,uint64_t seed)123 static inline unsigned long xxhash(const void *input, size_t length, 124 uint64_t seed) 125 { 126 #if BITS_PER_LONG == 64 127 return xxh64(input, length, seed); 128 #else 129 return xxh32(input, length, seed); 130 #endif 131 } 132 133 /*-**************************** 134 * Streaming Hash Functions 135 *****************************/ 136 137 /* 138 * These definitions are only meant to allow allocation of XXH state 139 * statically, on stack, or in a struct for example. 140 * Do not use members directly. 141 */ 142 143 /** 144 * struct xxh32_state - private xxh32 state, do not use members directly 145 */ 146 struct xxh32_state { 147 uint32_t total_len_32; 148 uint32_t large_len; 149 uint32_t v1; 150 uint32_t v2; 151 uint32_t v3; 152 uint32_t v4; 153 uint32_t mem32[4]; 154 uint32_t memsize; 155 }; 156 157 /** 158 * struct xxh32_state - private xxh64 state, do not use members directly 159 */ 160 struct xxh64_state { 161 uint64_t total_len; 162 uint64_t v1; 163 uint64_t v2; 164 uint64_t v3; 165 uint64_t v4; 166 uint64_t mem64[4]; 167 uint32_t memsize; 168 }; 169 170 /** 171 * xxh32_reset() - reset the xxh32 state to start a new hashing operation 172 * 173 * @state: The xxh32 state to reset. 174 * @seed: Initialize the hash state with this seed. 175 * 176 * Call this function on any xxh32_state to prepare for a new hashing operation. 177 */ 178 void xxh32_reset(struct xxh32_state *state, uint32_t seed); 179 180 /** 181 * xxh32_update() - hash the data given and update the xxh32 state 182 * 183 * @state: The xxh32 state to update. 184 * @input: The data to hash. 185 * @length: The length of the data to hash. 186 * 187 * After calling xxh32_reset() call xxh32_update() as many times as necessary. 188 * 189 * Return: Zero on success, otherwise an error code. 190 */ 191 int xxh32_update(struct xxh32_state *state, const void *input, size_t length); 192 193 /** 194 * xxh32_digest() - produce the current xxh32 hash 195 * 196 * @state: Produce the current xxh32 hash of this state. 197 * 198 * A hash value can be produced at any time. It is still possible to continue 199 * inserting input into the hash state after a call to xxh32_digest(), and 200 * generate new hashes later on, by calling xxh32_digest() again. 201 * 202 * Return: The xxh32 hash stored in the state. 203 */ 204 uint32_t xxh32_digest(const struct xxh32_state *state); 205 206 /** 207 * xxh64_reset() - reset the xxh64 state to start a new hashing operation 208 * 209 * @state: The xxh64 state to reset. 210 * @seed: Initialize the hash state with this seed. 211 */ 212 void xxh64_reset(struct xxh64_state *state, uint64_t seed); 213 214 /** 215 * xxh64_update() - hash the data given and update the xxh64 state 216 * @state: The xxh64 state to update. 217 * @input: The data to hash. 218 * @length: The length of the data to hash. 219 * 220 * After calling xxh64_reset() call xxh64_update() as many times as necessary. 221 * 222 * Return: Zero on success, otherwise an error code. 223 */ 224 int xxh64_update(struct xxh64_state *state, const void *input, size_t length); 225 226 /** 227 * xxh64_digest() - produce the current xxh64 hash 228 * 229 * @state: Produce the current xxh64 hash of this state. 230 * 231 * A hash value can be produced at any time. It is still possible to continue 232 * inserting input into the hash state after a call to xxh64_digest(), and 233 * generate new hashes later on, by calling xxh64_digest() again. 234 * 235 * Return: The xxh64 hash stored in the state. 236 */ 237 uint64_t xxh64_digest(const struct xxh64_state *state); 238 239 /*-************************** 240 * Utils 241 ***************************/ 242 243 /** 244 * xxh32_copy_state() - copy the source state into the destination state 245 * 246 * @src: The source xxh32 state. 247 * @dst: The destination xxh32 state. 248 */ 249 void xxh32_copy_state(struct xxh32_state *dst, const struct xxh32_state *src); 250 251 /** 252 * xxh64_copy_state() - copy the source state into the destination state 253 * 254 * @src: The source xxh64 state. 255 * @dst: The destination xxh64 state. 256 */ 257 void xxh64_copy_state(struct xxh64_state *dst, const struct xxh64_state *src); 258 259 #endif /* XXHASH_H */ 260