1 // SPDX-License-Identifier: BSD-2-Clause OR GPL-2.0-only
2 /*
3 * The xxhash is copied from the linux kernel at:
4 * https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/lib/xxhash.c
5 *
6 * The original copyright is:
7 *
8 * xxHash - Extremely Fast Hash algorithm
9 * Copyright (C) 2012-2016, Yann Collet.
10 *
11 * BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
12 *
13 * Redistribution and use in source and binary forms, with or without
14 * modification, are permitted provided that the following conditions are
15 * met:
16 *
17 * * Redistributions of source code must retain the above copyright
18 * notice, this list of conditions and the following disclaimer.
19 * * Redistributions in binary form must reproduce the above
20 * copyright notice, this list of conditions and the following disclaimer
21 * in the documentation and/or other materials provided with the
22 * distribution.
23 *
24 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
25 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
26 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
27 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
28 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
29 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
30 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
31 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
32 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
33 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
34 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
35 *
36 * This program is free software; you can redistribute it and/or modify it under
37 * the terms of the GNU General Public License version 2 as published by the
38 * Free Software Foundation. This program is dual-licensed; you may select
39 * either version 2 of the GNU General Public License ("GPL") or BSD license
40 * ("BSD").
41 *
42 * You can contact the author at:
43 * - xxHash homepage: https://cyan4973.github.io/xxHash/
44 * - xxHash source repository: https://github.com/Cyan4973/xxHash
45 */
46
47 #include "erofs/defs.h"
48 #include "erofs/xxhash.h"
49
50 /*-*************************************
51 * Macros
52 **************************************/
53 #define xxh_rotl32(x, r) ((x << r) | (x >> (32 - r)))
54
55 /*-*************************************
56 * Constants
57 **************************************/
58 static const uint32_t PRIME32_1 = 2654435761U;
59 static const uint32_t PRIME32_2 = 2246822519U;
60 static const uint32_t PRIME32_3 = 3266489917U;
61 static const uint32_t PRIME32_4 = 668265263U;
62 static const uint32_t PRIME32_5 = 374761393U;
63
64 /*-***************************
65 * Simple Hash Functions
66 ****************************/
xxh32_round(uint32_t seed,const uint32_t input)67 static uint32_t xxh32_round(uint32_t seed, const uint32_t input)
68 {
69 seed += input * PRIME32_2;
70 seed = xxh_rotl32(seed, 13);
71 seed *= PRIME32_1;
72 return seed;
73 }
74
xxh32(const void * input,const size_t len,const uint32_t seed)75 uint32_t xxh32(const void *input, const size_t len, const uint32_t seed)
76 {
77 const uint8_t *p = (const uint8_t *)input;
78 const uint8_t *b_end = p + len;
79 uint32_t h32;
80
81 if (len >= 16) {
82 const uint8_t *const limit = b_end - 16;
83 uint32_t v1 = seed + PRIME32_1 + PRIME32_2;
84 uint32_t v2 = seed + PRIME32_2;
85 uint32_t v3 = seed + 0;
86 uint32_t v4 = seed - PRIME32_1;
87
88 do {
89 v1 = xxh32_round(v1, get_unaligned_le32(p));
90 p += 4;
91 v2 = xxh32_round(v2, get_unaligned_le32(p));
92 p += 4;
93 v3 = xxh32_round(v3, get_unaligned_le32(p));
94 p += 4;
95 v4 = xxh32_round(v4, get_unaligned_le32(p));
96 p += 4;
97 } while (p <= limit);
98
99 h32 = xxh_rotl32(v1, 1) + xxh_rotl32(v2, 7) +
100 xxh_rotl32(v3, 12) + xxh_rotl32(v4, 18);
101 } else {
102 h32 = seed + PRIME32_5;
103 }
104
105 h32 += (uint32_t)len;
106
107 while (p + 4 <= b_end) {
108 h32 += get_unaligned_le32(p) * PRIME32_3;
109 h32 = xxh_rotl32(h32, 17) * PRIME32_4;
110 p += 4;
111 }
112
113 while (p < b_end) {
114 h32 += (*p) * PRIME32_5;
115 h32 = xxh_rotl32(h32, 11) * PRIME32_1;
116 p++;
117 }
118
119 h32 ^= h32 >> 15;
120 h32 *= PRIME32_2;
121 h32 ^= h32 >> 13;
122 h32 *= PRIME32_3;
123 h32 ^= h32 >> 16;
124
125 return h32;
126 }
127