1 //  Copyright (c) 2011-present, Facebook, Inc.  All rights reserved.
2 //  This source code is licensed under both the GPLv2 (found in the
3 //  COPYING file in the root directory) and Apache 2.0 License
4 //  (found in the LICENSE.Apache file in the root directory).
5 //
6 // Copyright (c) 2012 The LevelDB Authors. All rights reserved.
7 // Use of this source code is governed by a BSD-style license that can be
8 // found in the LICENSE file. See the AUTHORS file for names of contributors.
9 
10 #include <cstring>
11 #include <vector>
12 
13 #include "test_util/testharness.h"
14 #include "util/coding.h"
15 #include "util/hash.h"
16 
17 using ROCKSDB_NAMESPACE::EncodeFixed32;
18 using ROCKSDB_NAMESPACE::GetSliceHash64;
19 using ROCKSDB_NAMESPACE::Hash;
20 using ROCKSDB_NAMESPACE::Hash64;
21 using ROCKSDB_NAMESPACE::Lower32of64;
22 using ROCKSDB_NAMESPACE::Slice;
23 using ROCKSDB_NAMESPACE::Upper32of64;
24 
25 // The hash algorithm is part of the file format, for example for the Bloom
26 // filters. Test that the hash values are stable for a set of random strings of
27 // varying lengths.
TEST(HashTest,Values)28 TEST(HashTest, Values) {
29   constexpr uint32_t kSeed = 0xbc9f1d34;  // Same as BloomHash.
30 
31   EXPECT_EQ(Hash("", 0, kSeed), 3164544308u);
32   EXPECT_EQ(Hash("\x08", 1, kSeed), 422599524u);
33   EXPECT_EQ(Hash("\x17", 1, kSeed), 3168152998u);
34   EXPECT_EQ(Hash("\x9a", 1, kSeed), 3195034349u);
35   EXPECT_EQ(Hash("\x1c", 1, kSeed), 2651681383u);
36   EXPECT_EQ(Hash("\x4d\x76", 2, kSeed), 2447836956u);
37   EXPECT_EQ(Hash("\x52\xd5", 2, kSeed), 3854228105u);
38   EXPECT_EQ(Hash("\x91\xf7", 2, kSeed), 31066776u);
39   EXPECT_EQ(Hash("\xd6\x27", 2, kSeed), 1806091603u);
40   EXPECT_EQ(Hash("\x30\x46\x0b", 3, kSeed), 3808221797u);
41   EXPECT_EQ(Hash("\x56\xdc\xd6", 3, kSeed), 2157698265u);
42   EXPECT_EQ(Hash("\xd4\x52\x33", 3, kSeed), 1721992661u);
43   EXPECT_EQ(Hash("\x6a\xb5\xf4", 3, kSeed), 2469105222u);
44   EXPECT_EQ(Hash("\x67\x53\x81\x1c", 4, kSeed), 118283265u);
45   EXPECT_EQ(Hash("\x69\xb8\xc0\x88", 4, kSeed), 3416318611u);
46   EXPECT_EQ(Hash("\x1e\x84\xaf\x2d", 4, kSeed), 3315003572u);
47   EXPECT_EQ(Hash("\x46\xdc\x54\xbe", 4, kSeed), 447346355u);
48   EXPECT_EQ(Hash("\xd0\x7a\x6e\xea\x56", 5, kSeed), 4255445370u);
49   EXPECT_EQ(Hash("\x86\x83\xd5\xa4\xd8", 5, kSeed), 2390603402u);
50   EXPECT_EQ(Hash("\xb7\x46\xbb\x77\xce", 5, kSeed), 2048907743u);
51   EXPECT_EQ(Hash("\x6c\xa8\xbc\xe5\x99", 5, kSeed), 2177978500u);
52   EXPECT_EQ(Hash("\x5c\x5e\xe1\xa0\x73\x81", 6, kSeed), 1036846008u);
53   EXPECT_EQ(Hash("\x08\x5d\x73\x1c\xe5\x2e", 6, kSeed), 229980482u);
54   EXPECT_EQ(Hash("\x42\xfb\xf2\x52\xb4\x10", 6, kSeed), 3655585422u);
55   EXPECT_EQ(Hash("\x73\xe1\xff\x56\x9c\xce", 6, kSeed), 3502708029u);
56   EXPECT_EQ(Hash("\x5c\xbe\x97\x75\x54\x9a\x52", 7, kSeed), 815120748u);
57   EXPECT_EQ(Hash("\x16\x82\x39\x49\x88\x2b\x36", 7, kSeed), 3056033698u);
58   EXPECT_EQ(Hash("\x59\x77\xf0\xa7\x24\xf4\x78", 7, kSeed), 587205227u);
59   EXPECT_EQ(Hash("\xd3\xa5\x7c\x0e\xc0\x02\x07", 7, kSeed), 2030937252u);
60   EXPECT_EQ(Hash("\x31\x1b\x98\x75\x96\x22\xd3\x9a", 8, kSeed), 469635402u);
61   EXPECT_EQ(Hash("\x38\xd6\xf7\x28\x20\xb4\x8a\xe9", 8, kSeed), 3530274698u);
62   EXPECT_EQ(Hash("\xbb\x18\x5d\xf4\x12\x03\xf7\x99", 8, kSeed), 1974545809u);
63   EXPECT_EQ(Hash("\x80\xd4\x3b\x3b\xae\x22\xa2\x78", 8, kSeed), 3563570120u);
64   EXPECT_EQ(Hash("\x1a\xb5\xd0\xfe\xab\xc3\x61\xb2\x99", 9, kSeed),
65             2706087434u);
66   EXPECT_EQ(Hash("\x8e\x4a\xc3\x18\x20\x2f\x06\xe6\x3c", 9, kSeed),
67             1534654151u);
68   EXPECT_EQ(Hash("\xb6\xc0\xdd\x05\x3f\xc4\x86\x4c\xef", 9, kSeed),
69             2355554696u);
70   EXPECT_EQ(Hash("\x9a\x5f\x78\x0d\xaf\x50\xe1\x1f\x55", 9, kSeed),
71             1400800912u);
72   EXPECT_EQ(Hash("\x22\x6f\x39\x1f\xf8\xdd\x4f\x52\x17\x94", 10, kSeed),
73             3420325137u);
74   EXPECT_EQ(Hash("\x32\x89\x2a\x75\x48\x3a\x4a\x02\x69\xdd", 10, kSeed),
75             3427803584u);
76   EXPECT_EQ(Hash("\x06\x92\x5c\xf4\x88\x0e\x7e\x68\x38\x3e", 10, kSeed),
77             1152407945u);
78   EXPECT_EQ(Hash("\xbd\x2c\x63\x38\xbf\xe9\x78\xb7\xbf\x15", 10, kSeed),
79             3382479516u);
80 }
81 
82 // The hash algorithm is part of the file format, for example for the Bloom
83 // filters.
TEST(HashTest,Hash64Misc)84 TEST(HashTest, Hash64Misc) {
85   constexpr uint32_t kSeed = 0;  // Same as GetSliceHash64
86 
87   for (char fill : {'\0', 'a', '1', '\xff'}) {
88     const size_t max_size = 1000;
89     const std::string str(max_size, fill);
90 
91     for (size_t size = 0; size <= max_size; ++size) {
92       uint64_t here = Hash64(str.data(), size, kSeed);
93 
94       // Must be same as GetSliceHash64
95       EXPECT_EQ(here, GetSliceHash64(Slice(str.data(), size)));
96 
97       // Upper and Lower must reconstruct hash
98       EXPECT_EQ(here, (uint64_t{Upper32of64(here)} << 32) | Lower32of64(here));
99       EXPECT_EQ(here, (uint64_t{Upper32of64(here)} << 32) + Lower32of64(here));
100       EXPECT_EQ(here, (uint64_t{Upper32of64(here)} << 32) ^ Lower32of64(here));
101 
102       // Seed changes hash value (with high probability)
103       for (uint64_t var_seed = 1; var_seed != 0; var_seed <<= 1) {
104         EXPECT_NE(here, Hash64(str.data(), size, var_seed));
105       }
106 
107       // Size changes hash value (with high probability)
108       size_t max_smaller_by = std::min(size_t{30}, size);
109       for (size_t smaller_by = 1; smaller_by <= max_smaller_by; ++smaller_by) {
110         EXPECT_NE(here, Hash64(str.data(), size - smaller_by, kSeed));
111       }
112     }
113   }
114 }
115 
116 // Test that hash values are "non-trivial" for "trivial" inputs
TEST(HashTest,Hash64Trivial)117 TEST(HashTest, Hash64Trivial) {
118   // Thorough test too slow for regression testing
119   constexpr bool thorough = false;
120 
121   // For various seeds, make sure hash of empty string is not zero.
122   constexpr uint64_t max_seed = thorough ? 0x1000000 : 0x10000;
123   for (uint64_t seed = 0; seed < max_seed; ++seed) {
124     uint64_t here = Hash64("", 0, seed);
125     EXPECT_NE(Lower32of64(here), 0u);
126     EXPECT_NE(Upper32of64(here), 0u);
127   }
128 
129   // For standard seed, make sure hash of small strings are not zero
130   constexpr uint32_t kSeed = 0;  // Same as GetSliceHash64
131   char input[4];
132   constexpr int max_len = thorough ? 3 : 2;
133   for (int len = 1; len <= max_len; ++len) {
134     for (uint32_t i = 0; (i >> (len * 8)) == 0; ++i) {
135       EncodeFixed32(input, i);
136       uint64_t here = Hash64(input, len, kSeed);
137       EXPECT_NE(Lower32of64(here), 0u);
138       EXPECT_NE(Upper32of64(here), 0u);
139     }
140   }
141 }
142 
143 // Test that the hash values are stable for a set of random strings of
144 // varying small lengths.
TEST(HashTest,Hash64SmallValueSchema)145 TEST(HashTest, Hash64SmallValueSchema) {
146   constexpr uint32_t kSeed = 0;  // Same as GetSliceHash64
147 
148   EXPECT_EQ(Hash64("", 0, kSeed), uint64_t{5999572062939766020u});
149   EXPECT_EQ(Hash64("\x08", 1, kSeed), uint64_t{583283813901344696u});
150   EXPECT_EQ(Hash64("\x17", 1, kSeed), uint64_t{16175549975585474943u});
151   EXPECT_EQ(Hash64("\x9a", 1, kSeed), uint64_t{16322991629225003903u});
152   EXPECT_EQ(Hash64("\x1c", 1, kSeed), uint64_t{13269285487706833447u});
153   EXPECT_EQ(Hash64("\x4d\x76", 2, kSeed), uint64_t{6859542833406258115u});
154   EXPECT_EQ(Hash64("\x52\xd5", 2, kSeed), uint64_t{4919611532550636959u});
155   EXPECT_EQ(Hash64("\x91\xf7", 2, kSeed), uint64_t{14199427467559720719u});
156   EXPECT_EQ(Hash64("\xd6\x27", 2, kSeed), uint64_t{12292689282614532691u});
157   EXPECT_EQ(Hash64("\x30\x46\x0b", 3, kSeed), uint64_t{11404699285340020889u});
158   EXPECT_EQ(Hash64("\x56\xdc\xd6", 3, kSeed), uint64_t{12404347133785524237u});
159   EXPECT_EQ(Hash64("\xd4\x52\x33", 3, kSeed), uint64_t{15853805298481534034u});
160   EXPECT_EQ(Hash64("\x6a\xb5\xf4", 3, kSeed), uint64_t{16863488758399383382u});
161   EXPECT_EQ(Hash64("\x67\x53\x81\x1c", 4, kSeed),
162             uint64_t{9010661983527562386u});
163   EXPECT_EQ(Hash64("\x69\xb8\xc0\x88", 4, kSeed),
164             uint64_t{6611781377647041447u});
165   EXPECT_EQ(Hash64("\x1e\x84\xaf\x2d", 4, kSeed),
166             uint64_t{15290969111616346501u});
167   EXPECT_EQ(Hash64("\x46\xdc\x54\xbe", 4, kSeed),
168             uint64_t{7063754590279313623u});
169   EXPECT_EQ(Hash64("\xd0\x7a\x6e\xea\x56", 5, kSeed),
170             uint64_t{6384167718754869899u});
171   EXPECT_EQ(Hash64("\x86\x83\xd5\xa4\xd8", 5, kSeed),
172             uint64_t{16874407254108011067u});
173   EXPECT_EQ(Hash64("\xb7\x46\xbb\x77\xce", 5, kSeed),
174             uint64_t{16809880630149135206u});
175   EXPECT_EQ(Hash64("\x6c\xa8\xbc\xe5\x99", 5, kSeed),
176             uint64_t{1249038833153141148u});
177   EXPECT_EQ(Hash64("\x5c\x5e\xe1\xa0\x73\x81", 6, kSeed),
178             uint64_t{17358142495308219330u});
179   EXPECT_EQ(Hash64("\x08\x5d\x73\x1c\xe5\x2e", 6, kSeed),
180             uint64_t{4237646583134806322u});
181   EXPECT_EQ(Hash64("\x42\xfb\xf2\x52\xb4\x10", 6, kSeed),
182             uint64_t{4373664924115234051u});
183   EXPECT_EQ(Hash64("\x73\xe1\xff\x56\x9c\xce", 6, kSeed),
184             uint64_t{12012981210634596029u});
185   EXPECT_EQ(Hash64("\x5c\xbe\x97\x75\x54\x9a\x52", 7, kSeed),
186             uint64_t{5716522398211028826u});
187   EXPECT_EQ(Hash64("\x16\x82\x39\x49\x88\x2b\x36", 7, kSeed),
188             uint64_t{15604531309862565013u});
189   EXPECT_EQ(Hash64("\x59\x77\xf0\xa7\x24\xf4\x78", 7, kSeed),
190             uint64_t{8601330687345614172u});
191   EXPECT_EQ(Hash64("\xd3\xa5\x7c\x0e\xc0\x02\x07", 7, kSeed),
192             uint64_t{8088079329364056942u});
193   EXPECT_EQ(Hash64("\x31\x1b\x98\x75\x96\x22\xd3\x9a", 8, kSeed),
194             uint64_t{9844314944338447628u});
195   EXPECT_EQ(Hash64("\x38\xd6\xf7\x28\x20\xb4\x8a\xe9", 8, kSeed),
196             uint64_t{10973293517982163143u});
197   EXPECT_EQ(Hash64("\xbb\x18\x5d\xf4\x12\x03\xf7\x99", 8, kSeed),
198             uint64_t{9986007080564743219u});
199   EXPECT_EQ(Hash64("\x80\xd4\x3b\x3b\xae\x22\xa2\x78", 8, kSeed),
200             uint64_t{1729303145008254458u});
201   EXPECT_EQ(Hash64("\x1a\xb5\xd0\xfe\xab\xc3\x61\xb2\x99", 9, kSeed),
202             uint64_t{13253403748084181481u});
203   EXPECT_EQ(Hash64("\x8e\x4a\xc3\x18\x20\x2f\x06\xe6\x3c", 9, kSeed),
204             uint64_t{7768754303876232188u});
205   EXPECT_EQ(Hash64("\xb6\xc0\xdd\x05\x3f\xc4\x86\x4c\xef", 9, kSeed),
206             uint64_t{12439346786701492u});
207   EXPECT_EQ(Hash64("\x9a\x5f\x78\x0d\xaf\x50\xe1\x1f\x55", 9, kSeed),
208             uint64_t{10841838338450144690u});
209   EXPECT_EQ(Hash64("\x22\x6f\x39\x1f\xf8\xdd\x4f\x52\x17\x94", 10, kSeed),
210             uint64_t{12883919702069153152u});
211   EXPECT_EQ(Hash64("\x32\x89\x2a\x75\x48\x3a\x4a\x02\x69\xdd", 10, kSeed),
212             uint64_t{12692903507676842188u});
213   EXPECT_EQ(Hash64("\x06\x92\x5c\xf4\x88\x0e\x7e\x68\x38\x3e", 10, kSeed),
214             uint64_t{6540985900674032620u});
215   EXPECT_EQ(Hash64("\xbd\x2c\x63\x38\xbf\xe9\x78\xb7\xbf\x15", 10, kSeed),
216             uint64_t{10551812464348219044u});
217 }
218 
Hash64TestDescriptor(const char * repeat,size_t limit)219 std::string Hash64TestDescriptor(const char *repeat, size_t limit) {
220   const char *mod61_encode =
221       "abcdefghijklmnopqrstuvwxyz123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
222 
223   std::string input;
224   while (input.size() < limit) {
225     input.append(repeat);
226   }
227   std::string rv;
228   for (size_t i = 0; i < limit; ++i) {
229     uint64_t h = GetSliceHash64(Slice(input.data(), i));
230     rv.append(1, mod61_encode[static_cast<size_t>(h % 61)]);
231   }
232   return rv;
233 }
234 
235 // XXH3p changes its algorithm for various sizes up through 250 bytes, so
236 // we need to check the stability of larger sizes also.
TEST(HashTest,Hash64LargeValueSchema)237 TEST(HashTest, Hash64LargeValueSchema) {
238   // Each of these derives a "descriptor" from the hash values for all
239   // lengths up to 430.
240   // Note that "c" is common for the zero-length string.
241   EXPECT_EQ(
242       Hash64TestDescriptor("foo", 430),
243       "cRhyWsY67B6klRA1udmOuiYuX7IthyGBKqbeosz2hzVglWCmQx8nEdnpkvPfYX56Up2OWOTV"
244       "lTzfAoYwvtqKzjD8E9xttR2unelbXbIV67NUe6bOO23BxaSFRcA3njGu5cUWfgwOqNoTsszp"
245       "uPvKRP6qaUR5VdoBkJUCFIefd7edlNK5mv6JYWaGdwxehg65hTkTmjZoPKxTZo4PLyzbL9U4"
246       "xt12ITSfeP2MfBHuLI2z2pDlBb44UQKVMx27LEoAHsdLp3WfWfgH3sdRBRCHm33UxCM4QmE2"
247       "xJ7gqSvNwTeH7v9GlC8zWbGroyD3UVNeShMLx29O7tH1biemLULwAHyIw8zdtLMDpEJ8m2ic"
248       "l6Lb4fDuuFNAs1GCVUthjK8CV8SWI8Rsz5THSwn5CGhpqUwSZcFknjwWIl5rNCvDxXJqYr");
249   // Note that "1EeRk" is common for "Rocks"
250   EXPECT_EQ(
251       Hash64TestDescriptor("Rocks", 430),
252       "c1EeRkrzgOYWLA8PuhJrwTePJewoB44WdXYDfhbk3ZxTqqg25WlPExDl7IKIQLJvnA6gJxxn"
253       "9TCSLkFGfJeXehaSS1GBqWSzfhEH4VXiXIUCuxJXxtKXcSC6FrNIQGTZbYDiUOLD6Y5inzrF"
254       "9etwQhXUBanw55xAUdNMFQAm2GjJ6UDWp2mISLiMMkLjANWMKLaZMqaFLX37qB4MRO1ooVRv"
255       "zSvaNRSCLxlggQCasQq8icWjzf3HjBlZtU6pd4rkaUxSzHqmo9oM5MghbU5Rtxg8wEfO7lVN"
256       "5wdMONYecslQTwjZUpO1K3LDf3K3XK6sUXM6ShQQ3RHmMn2acB4YtTZ3QQcHYJSOHn2DuWpa"
257       "Q8RqzX5lab92YmOLaCdOHq1BPsM7SIBzMdLgePNsJ1vvMALxAaoDUHPxoFLO2wx18IXnyX");
258   EXPECT_EQ(
259       Hash64TestDescriptor("RocksDB", 430),
260       "c1EeRkukbkb28wLTahwD2sfUhZzaBEnF8SVrxnPVB6A7b8CaAl3UKsDZISF92GSq2wDCukOq"
261       "Jgrsp7A3KZhDiLW8dFXp8UPqPxMCRlMdZeVeJ2dJxrmA6cyt99zkQFj7ELbut6jAeVqARFnw"
262       "fnWVXOsaLrq7bDCbMcns2DKvTaaqTCLMYxI7nhtLpFN1jR755FRQFcOzrrDbh7QhypjdvlYw"
263       "cdAMSZgp9JMHxbM23wPSuH6BOFgxejz35PScZfhDPvTOxIy1jc3MZsWrMC3P324zNolO7JdW"
264       "CX2I5UDKjjaEJfxbgVgJIXxtQGlmj2xkO5sPpjULQV4X2HlY7FQleJ4QRaJIB4buhCA4vUTF"
265       "eMFlxCIYUpTCsal2qsmnGOWa8WCcefrohMjDj1fjzSvSaQwlpyR1GZHF2uPOoQagiCpHpm");
266 }
267 
TEST(Fastrange32Test,Values)268 TEST(Fastrange32Test, Values) {
269   using ROCKSDB_NAMESPACE::fastrange32;
270   // Zero range
271   EXPECT_EQ(fastrange32(0, 0), 0U);
272   EXPECT_EQ(fastrange32(123, 0), 0U);
273   EXPECT_EQ(fastrange32(0xffffffff, 0), 0U);
274 
275   // One range
276   EXPECT_EQ(fastrange32(0, 1), 0U);
277   EXPECT_EQ(fastrange32(123, 1), 0U);
278   EXPECT_EQ(fastrange32(0xffffffff, 1), 0U);
279 
280   // Two range
281   EXPECT_EQ(fastrange32(0, 2), 0U);
282   EXPECT_EQ(fastrange32(123, 2), 0U);
283   EXPECT_EQ(fastrange32(0x7fffffff, 2), 0U);
284   EXPECT_EQ(fastrange32(0x80000000, 2), 1U);
285   EXPECT_EQ(fastrange32(0xffffffff, 2), 1U);
286 
287   // Seven range
288   EXPECT_EQ(fastrange32(0, 7), 0U);
289   EXPECT_EQ(fastrange32(123, 7), 0U);
290   EXPECT_EQ(fastrange32(613566756, 7), 0U);
291   EXPECT_EQ(fastrange32(613566757, 7), 1U);
292   EXPECT_EQ(fastrange32(1227133513, 7), 1U);
293   EXPECT_EQ(fastrange32(1227133514, 7), 2U);
294   // etc.
295   EXPECT_EQ(fastrange32(0xffffffff, 7), 6U);
296 
297   // Big
298   EXPECT_EQ(fastrange32(1, 0x80000000), 0U);
299   EXPECT_EQ(fastrange32(2, 0x80000000), 1U);
300   EXPECT_EQ(fastrange32(4, 0x7fffffff), 1U);
301   EXPECT_EQ(fastrange32(4, 0x80000000), 2U);
302   EXPECT_EQ(fastrange32(0xffffffff, 0x7fffffff), 0x7ffffffeU);
303   EXPECT_EQ(fastrange32(0xffffffff, 0x80000000), 0x7fffffffU);
304 }
305 
TEST(Fastrange64Test,Values)306 TEST(Fastrange64Test, Values) {
307   using ROCKSDB_NAMESPACE::fastrange64;
308   // Zero range
309   EXPECT_EQ(fastrange64(0, 0), 0U);
310   EXPECT_EQ(fastrange64(123, 0), 0U);
311   EXPECT_EQ(fastrange64(0xffffFFFF, 0), 0U);
312   EXPECT_EQ(fastrange64(0xffffFFFFffffFFFF, 0), 0U);
313 
314   // One range
315   EXPECT_EQ(fastrange64(0, 1), 0U);
316   EXPECT_EQ(fastrange64(123, 1), 0U);
317   EXPECT_EQ(fastrange64(0xffffFFFF, 1), 0U);
318   EXPECT_EQ(fastrange64(0xffffFFFFffffFFFF, 1), 0U);
319 
320   // Two range
321   EXPECT_EQ(fastrange64(0, 2), 0U);
322   EXPECT_EQ(fastrange64(123, 2), 0U);
323   EXPECT_EQ(fastrange64(0xffffFFFF, 2), 0U);
324   EXPECT_EQ(fastrange64(0x7fffFFFFffffFFFF, 2), 0U);
325   EXPECT_EQ(fastrange64(0x8000000000000000, 2), 1U);
326   EXPECT_EQ(fastrange64(0xffffFFFFffffFFFF, 2), 1U);
327 
328   // Seven range
329   EXPECT_EQ(fastrange64(0, 7), 0U);
330   EXPECT_EQ(fastrange64(123, 7), 0U);
331   EXPECT_EQ(fastrange64(0xffffFFFF, 7), 0U);
332   EXPECT_EQ(fastrange64(2635249153387078802, 7), 0U);
333   EXPECT_EQ(fastrange64(2635249153387078803, 7), 1U);
334   EXPECT_EQ(fastrange64(5270498306774157604, 7), 1U);
335   EXPECT_EQ(fastrange64(5270498306774157605, 7), 2U);
336   EXPECT_EQ(fastrange64(0x7fffFFFFffffFFFF, 7), 3U);
337   EXPECT_EQ(fastrange64(0x8000000000000000, 7), 3U);
338   EXPECT_EQ(fastrange64(0xffffFFFFffffFFFF, 7), 6U);
339 
340   // Big but 32-bit range
341   EXPECT_EQ(fastrange64(0x100000000, 0x80000000), 0U);
342   EXPECT_EQ(fastrange64(0x200000000, 0x80000000), 1U);
343   EXPECT_EQ(fastrange64(0x400000000, 0x7fffFFFF), 1U);
344   EXPECT_EQ(fastrange64(0x400000000, 0x80000000), 2U);
345   EXPECT_EQ(fastrange64(0xffffFFFFffffFFFF, 0x7fffFFFF), 0x7fffFFFEU);
346   EXPECT_EQ(fastrange64(0xffffFFFFffffFFFF, 0x80000000), 0x7fffFFFFU);
347 
348   // Big, > 32-bit range
349 #if SIZE_MAX == UINT64_MAX
350   EXPECT_EQ(fastrange64(0x7fffFFFFffffFFFF, 0x4200000002), 0x2100000000U);
351   EXPECT_EQ(fastrange64(0x8000000000000000, 0x4200000002), 0x2100000001U);
352 
353   EXPECT_EQ(fastrange64(0x0000000000000000, 420000000002), 0U);
354   EXPECT_EQ(fastrange64(0x7fffFFFFffffFFFF, 420000000002), 210000000000U);
355   EXPECT_EQ(fastrange64(0x8000000000000000, 420000000002), 210000000001U);
356   EXPECT_EQ(fastrange64(0xffffFFFFffffFFFF, 420000000002), 420000000001U);
357 
358   EXPECT_EQ(fastrange64(0xffffFFFFffffFFFF, 0xffffFFFFffffFFFF),
359             0xffffFFFFffffFFFEU);
360 #endif
361 }
362 
363 // for inspection of disassembly
fastrange32(uint32_t hash,uint32_t range)364 uint32_t fastrange32(uint32_t hash, uint32_t range) {
365   return ROCKSDB_NAMESPACE::fastrange32(hash, range);
366 }
367 
368 // for inspection of disassembly
fastrange64(uint64_t hash,size_t range)369 size_t fastrange64(uint64_t hash, size_t range) {
370   return ROCKSDB_NAMESPACE::fastrange64(hash, range);
371 }
372 
main(int argc,char ** argv)373 int main(int argc, char** argv) {
374   ::testing::InitGoogleTest(&argc, argv);
375 
376   return RUN_ALL_TESTS();
377 }
378