2 * xxHash - Fast Hash algorithm
3 * Copyright (C) 2012-2020 Yann Collet
4 * Copyright (C) 2019-2020 Devin Hussey (easyaspi314)
6 * BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions are
12 * * Redistributions of source code must retain the above copyright
13 * notice, this list of conditions and the following disclaimer.
14 * * Redistributions in binary form must reproduce the above
15 * copyright notice, this list of conditions and the following disclaimer
16 * in the documentation and/or other materials provided with the
19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
22 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
23 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
24 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
25 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
26 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
27 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
28 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
29 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 * You can contact the author at :
32 * - xxHash homepage: http://www.xxhash.com
33 * - xxHash source repository : https://github.com/Cyan4973/xxHash */
35 /* This is a compact, 100% standalone reference XXH32 single-run implementation.
36 * Instead of focusing on performance hacks, this focuses on cleanliness,
37 * conformance, portability and simplicity.
39 * This file aims to be 100% compatible with C90/C++98, with the additional
40 * requirement of stdint.h. No library functions are used. */
42 #include <stddef.h> /* size_t, NULL */
43 #include <stdint.h> /* uint8_t, uint32_t */
46 static uint32_t const PRIME32_1
= 0x9E3779B1U
; /* 0b10011110001101110111100110110001 */
47 static uint32_t const PRIME32_2
= 0x85EBCA77U
; /* 0b10000101111010111100101001110111 */
48 static uint32_t const PRIME32_3
= 0xC2B2AE3DU
; /* 0b11000010101100101010111000111101 */
49 static uint32_t const PRIME32_4
= 0x27D4EB2FU
; /* 0b00100111110101001110101100101111 */
50 static uint32_t const PRIME32_5
= 0x165667B1U
; /* 0b00010110010101100110011110110001 */
52 /* Rotates value left by amt. */
53 static uint32_t XXH_rotl32(uint32_t const value
, uint32_t const amt
)
55 return (value
<< (amt
% 32)) | (value
>> (32 - (amt
% 32)));
58 /* Portably reads a 32-bit little endian integer from data at the given offset. */
59 static uint32_t XXH_read32(uint8_t const *const data
, size_t const offset
)
61 return (uint32_t) data
[offset
+ 0]
62 | ((uint32_t) data
[offset
+ 1] << 8)
63 | ((uint32_t) data
[offset
+ 2] << 16)
64 | ((uint32_t) data
[offset
+ 3] << 24);
67 /* Mixes input into acc. */
68 static uint32_t XXH32_round(uint32_t acc
, uint32_t const input
)
70 acc
+= input
* PRIME32_2
;
71 acc
= XXH_rotl32(acc
, 13);
76 /* Mixes all bits to finalize the hash. */
77 static uint32_t XXH32_avalanche(uint32_t hash
)
87 /* The XXH32 hash function.
88 * input: The data to hash.
89 * length: The length of input. It is undefined behavior to have length larger than the
91 * seed: A 32-bit value to seed the hash with.
92 * returns: The 32-bit calculated hash value. */
93 uint32_t XXH32(void const *const input
, size_t const length
, uint32_t const seed
)
95 uint8_t const *const data
= (uint8_t const *) input
;
97 size_t remaining
= length
;
100 /* Don't dereference a null pointer. The reference implementation notably doesn't
101 * check for this by default. */
103 return XXH32_avalanche(seed
+ PRIME32_5
);
106 if (remaining
>= 16) {
107 /* Initialize our accumulators */
108 uint32_t acc1
= seed
+ PRIME32_1
+ PRIME32_2
;
109 uint32_t acc2
= seed
+ PRIME32_2
;
110 uint32_t acc3
= seed
+ 0;
111 uint32_t acc4
= seed
- PRIME32_1
;
113 while (remaining
>= 16) {
114 acc1
= XXH32_round(acc1
, XXH_read32(data
, offset
)); offset
+= 4;
115 acc2
= XXH32_round(acc2
, XXH_read32(data
, offset
)); offset
+= 4;
116 acc3
= XXH32_round(acc3
, XXH_read32(data
, offset
)); offset
+= 4;
117 acc4
= XXH32_round(acc4
, XXH_read32(data
, offset
)); offset
+= 4;
121 hash
= XXH_rotl32(acc1
, 1) + XXH_rotl32(acc2
, 7) + XXH_rotl32(acc3
, 12) + XXH_rotl32(acc4
, 18);
123 /* Not enough data for the main loop, put something in there instead. */
124 hash
= seed
+ PRIME32_5
;
127 hash
+= (uint32_t) length
;
129 /* Process the remaining data. */
130 while (remaining
>= 4) {
131 hash
+= XXH_read32(data
, offset
) * PRIME32_3
;
132 hash
= XXH_rotl32(hash
, 17);
138 while (remaining
!= 0) {
139 hash
+= (uint32_t) data
[offset
] * PRIME32_5
;
140 hash
= XXH_rotl32(hash
, 11);
145 return XXH32_avalanche(hash
);