1 | /* |
2 | * xxHash - 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 | * You can contact the author at : |
31 | * - xxHash source repository : https://github.com/Cyan4973/xxHash |
32 | */ |
33 | |
34 | #ifndef QEMU_XXHASH_H |
35 | #define QEMU_XXHASH_H |
36 | |
37 | #include "qemu/bitops.h" |
38 | |
39 | #define PRIME32_1 2654435761U |
40 | #define PRIME32_2 2246822519U |
41 | #define PRIME32_3 3266489917U |
42 | #define PRIME32_4 668265263U |
43 | #define PRIME32_5 374761393U |
44 | |
45 | #define QEMU_XXHASH_SEED 1 |
46 | |
47 | /* |
48 | * xxhash32, customized for input variables that are not guaranteed to be |
49 | * contiguous in memory. |
50 | */ |
51 | static inline uint32_t |
52 | qemu_xxhash7(uint64_t ab, uint64_t cd, uint32_t e, uint32_t f, uint32_t g) |
53 | { |
54 | uint32_t v1 = QEMU_XXHASH_SEED + PRIME32_1 + PRIME32_2; |
55 | uint32_t v2 = QEMU_XXHASH_SEED + PRIME32_2; |
56 | uint32_t v3 = QEMU_XXHASH_SEED + 0; |
57 | uint32_t v4 = QEMU_XXHASH_SEED - PRIME32_1; |
58 | uint32_t a = ab; |
59 | uint32_t b = ab >> 32; |
60 | uint32_t c = cd; |
61 | uint32_t d = cd >> 32; |
62 | uint32_t h32; |
63 | |
64 | v1 += a * PRIME32_2; |
65 | v1 = rol32(v1, 13); |
66 | v1 *= PRIME32_1; |
67 | |
68 | v2 += b * PRIME32_2; |
69 | v2 = rol32(v2, 13); |
70 | v2 *= PRIME32_1; |
71 | |
72 | v3 += c * PRIME32_2; |
73 | v3 = rol32(v3, 13); |
74 | v3 *= PRIME32_1; |
75 | |
76 | v4 += d * PRIME32_2; |
77 | v4 = rol32(v4, 13); |
78 | v4 *= PRIME32_1; |
79 | |
80 | h32 = rol32(v1, 1) + rol32(v2, 7) + rol32(v3, 12) + rol32(v4, 18); |
81 | h32 += 28; |
82 | |
83 | h32 += e * PRIME32_3; |
84 | h32 = rol32(h32, 17) * PRIME32_4; |
85 | |
86 | h32 += f * PRIME32_3; |
87 | h32 = rol32(h32, 17) * PRIME32_4; |
88 | |
89 | h32 += g * PRIME32_3; |
90 | h32 = rol32(h32, 17) * PRIME32_4; |
91 | |
92 | h32 ^= h32 >> 15; |
93 | h32 *= PRIME32_2; |
94 | h32 ^= h32 >> 13; |
95 | h32 *= PRIME32_3; |
96 | h32 ^= h32 >> 16; |
97 | |
98 | return h32; |
99 | } |
100 | |
101 | static inline uint32_t qemu_xxhash2(uint64_t ab) |
102 | { |
103 | return qemu_xxhash7(ab, 0, 0, 0, 0); |
104 | } |
105 | |
106 | static inline uint32_t qemu_xxhash4(uint64_t ab, uint64_t cd) |
107 | { |
108 | return qemu_xxhash7(ab, cd, 0, 0, 0); |
109 | } |
110 | |
111 | static inline uint32_t qemu_xxhash5(uint64_t ab, uint64_t cd, uint32_t e) |
112 | { |
113 | return qemu_xxhash7(ab, cd, e, 0, 0); |
114 | } |
115 | |
116 | static inline uint32_t qemu_xxhash6(uint64_t ab, uint64_t cd, uint32_t e, |
117 | uint32_t f) |
118 | { |
119 | return qemu_xxhash7(ab, cd, e, f, 0); |
120 | } |
121 | |
122 | #endif /* QEMU_XXHASH_H */ |
123 | |