xref: /aosp_15_r20/external/cronet/base/third_party/cityhash/city.h (revision 6777b5387eb2ff775bb5750e3f5d96f37fb7352b)
1*6777b538SAndroid Build Coastguard Worker // Copyright (c) 2011 Google, Inc.
2*6777b538SAndroid Build Coastguard Worker //
3*6777b538SAndroid Build Coastguard Worker // Permission is hereby granted, free of charge, to any person obtaining a copy
4*6777b538SAndroid Build Coastguard Worker // of this software and associated documentation files (the "Software"), to deal
5*6777b538SAndroid Build Coastguard Worker // in the Software without restriction, including without limitation the rights
6*6777b538SAndroid Build Coastguard Worker // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
7*6777b538SAndroid Build Coastguard Worker // copies of the Software, and to permit persons to whom the Software is
8*6777b538SAndroid Build Coastguard Worker // furnished to do so, subject to the following conditions:
9*6777b538SAndroid Build Coastguard Worker //
10*6777b538SAndroid Build Coastguard Worker // The above copyright notice and this permission notice shall be included in
11*6777b538SAndroid Build Coastguard Worker // all copies or substantial portions of the Software.
12*6777b538SAndroid Build Coastguard Worker //
13*6777b538SAndroid Build Coastguard Worker // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
14*6777b538SAndroid Build Coastguard Worker // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
15*6777b538SAndroid Build Coastguard Worker // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
16*6777b538SAndroid Build Coastguard Worker // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
17*6777b538SAndroid Build Coastguard Worker // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
18*6777b538SAndroid Build Coastguard Worker // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
19*6777b538SAndroid Build Coastguard Worker // THE SOFTWARE.
20*6777b538SAndroid Build Coastguard Worker //
21*6777b538SAndroid Build Coastguard Worker // CityHash, by Geoff Pike and Jyrki Alakuijala
22*6777b538SAndroid Build Coastguard Worker //
23*6777b538SAndroid Build Coastguard Worker // http://code.google.com/p/cityhash/
24*6777b538SAndroid Build Coastguard Worker //
25*6777b538SAndroid Build Coastguard Worker // This file provides a few functions for hashing strings.  All of them are
26*6777b538SAndroid Build Coastguard Worker // high-quality functions in the sense that they pass standard tests such
27*6777b538SAndroid Build Coastguard Worker // as Austin Appleby's SMHasher.  They are also fast.
28*6777b538SAndroid Build Coastguard Worker //
29*6777b538SAndroid Build Coastguard Worker // For 64-bit x86 code, on short strings, we don't know of anything faster than
30*6777b538SAndroid Build Coastguard Worker // CityHash64 that is of comparable quality.  We believe our nearest competitor
31*6777b538SAndroid Build Coastguard Worker // is Murmur3.  For 64-bit x86 code, CityHash64 is an excellent choice for hash
32*6777b538SAndroid Build Coastguard Worker // tables and most other hashing (excluding cryptography).
33*6777b538SAndroid Build Coastguard Worker //
34*6777b538SAndroid Build Coastguard Worker // For 64-bit x86 code, on long strings, the picture is more complicated.
35*6777b538SAndroid Build Coastguard Worker // On many recent Intel CPUs, such as Nehalem, Westmere, Sandy Bridge, etc.,
36*6777b538SAndroid Build Coastguard Worker // CityHashCrc128 appears to be faster than all competitors of comparable
37*6777b538SAndroid Build Coastguard Worker // quality.  CityHash128 is also good but not quite as fast.  We believe our
38*6777b538SAndroid Build Coastguard Worker // nearest competitor is Bob Jenkins' Spooky.  We don't have great data for
39*6777b538SAndroid Build Coastguard Worker // other 64-bit CPUs, but for long strings we know that Spooky is slightly
40*6777b538SAndroid Build Coastguard Worker // faster than CityHash on some relatively recent AMD x86-64 CPUs, for example.
41*6777b538SAndroid Build Coastguard Worker // Note that CityHashCrc128 is declared in citycrc.h.
42*6777b538SAndroid Build Coastguard Worker //
43*6777b538SAndroid Build Coastguard Worker // For 32-bit x86 code, we don't know of anything faster than CityHash32 that
44*6777b538SAndroid Build Coastguard Worker // is of comparable quality.  We believe our nearest competitor is Murmur3A.
45*6777b538SAndroid Build Coastguard Worker // (On 64-bit CPUs, it is typically faster to use the other CityHash variants.)
46*6777b538SAndroid Build Coastguard Worker //
47*6777b538SAndroid Build Coastguard Worker // Functions in the CityHash family are not suitable for cryptography.
48*6777b538SAndroid Build Coastguard Worker //
49*6777b538SAndroid Build Coastguard Worker // Please see CityHash's README file for more details on our performance
50*6777b538SAndroid Build Coastguard Worker // measurements and so on.
51*6777b538SAndroid Build Coastguard Worker //
52*6777b538SAndroid Build Coastguard Worker // WARNING: This code has been only lightly tested on big-endian platforms!
53*6777b538SAndroid Build Coastguard Worker // It is known to work well on little-endian platforms that have a small penalty
54*6777b538SAndroid Build Coastguard Worker // for unaligned reads, such as current Intel and AMD moderate-to-high-end CPUs.
55*6777b538SAndroid Build Coastguard Worker // It should work on all 32-bit and 64-bit platforms that allow unaligned reads;
56*6777b538SAndroid Build Coastguard Worker // bug reports are welcome.
57*6777b538SAndroid Build Coastguard Worker //
58*6777b538SAndroid Build Coastguard Worker // By the way, for some hash functions, given strings a and b, the hash
59*6777b538SAndroid Build Coastguard Worker // of a+b is easily derived from the hashes of a and b.  This property
60*6777b538SAndroid Build Coastguard Worker // doesn't hold for any hash functions in this file.
61*6777b538SAndroid Build Coastguard Worker 
62*6777b538SAndroid Build Coastguard Worker #ifndef BASE_THIRD_PARTY_CITYHASH_CITY_H_
63*6777b538SAndroid Build Coastguard Worker #define BASE_THIRD_PARTY_CITYHASH_CITY_H_
64*6777b538SAndroid Build Coastguard Worker 
65*6777b538SAndroid Build Coastguard Worker #include <stdint.h>
66*6777b538SAndroid Build Coastguard Worker #include <stdlib.h>  // for size_t.
67*6777b538SAndroid Build Coastguard Worker #include <utility>
68*6777b538SAndroid Build Coastguard Worker 
69*6777b538SAndroid Build Coastguard Worker // XXX(cavalcantii): Declaring it inside of the 'base' namespace allows to
70*6777b538SAndroid Build Coastguard Worker // handle linker symbol clash error with deprecated CityHash from
71*6777b538SAndroid Build Coastguard Worker // third_party/smhasher in a few unit tests.
72*6777b538SAndroid Build Coastguard Worker namespace base {
73*6777b538SAndroid Build Coastguard Worker namespace internal {
74*6777b538SAndroid Build Coastguard Worker namespace cityhash_v111 {
75*6777b538SAndroid Build Coastguard Worker 
76*6777b538SAndroid Build Coastguard Worker typedef uint8_t uint8;
77*6777b538SAndroid Build Coastguard Worker typedef uint32_t uint32;
78*6777b538SAndroid Build Coastguard Worker typedef uint64_t uint64;
79*6777b538SAndroid Build Coastguard Worker typedef std::pair<uint64, uint64> uint128;
80*6777b538SAndroid Build Coastguard Worker 
Uint128Low64(const uint128 & x)81*6777b538SAndroid Build Coastguard Worker inline uint64 Uint128Low64(const uint128& x) {
82*6777b538SAndroid Build Coastguard Worker   return x.first;
83*6777b538SAndroid Build Coastguard Worker }
Uint128High64(const uint128 & x)84*6777b538SAndroid Build Coastguard Worker inline uint64 Uint128High64(const uint128& x) {
85*6777b538SAndroid Build Coastguard Worker   return x.second;
86*6777b538SAndroid Build Coastguard Worker }
87*6777b538SAndroid Build Coastguard Worker 
88*6777b538SAndroid Build Coastguard Worker // Hash function for a byte array.
89*6777b538SAndroid Build Coastguard Worker uint64 CityHash64(const char* buf, size_t len);
90*6777b538SAndroid Build Coastguard Worker 
91*6777b538SAndroid Build Coastguard Worker // Hash function for a byte array.  For convenience, a 64-bit seed is also
92*6777b538SAndroid Build Coastguard Worker // hashed into the result.
93*6777b538SAndroid Build Coastguard Worker uint64 CityHash64WithSeed(const char* buf, size_t len, uint64 seed);
94*6777b538SAndroid Build Coastguard Worker 
95*6777b538SAndroid Build Coastguard Worker // Hash function for a byte array.  For convenience, two seeds are also
96*6777b538SAndroid Build Coastguard Worker // hashed into the result.
97*6777b538SAndroid Build Coastguard Worker uint64 CityHash64WithSeeds(const char* buf,
98*6777b538SAndroid Build Coastguard Worker                            size_t len,
99*6777b538SAndroid Build Coastguard Worker                            uint64 seed0,
100*6777b538SAndroid Build Coastguard Worker                            uint64 seed1);
101*6777b538SAndroid Build Coastguard Worker 
102*6777b538SAndroid Build Coastguard Worker // Hash function for a byte array.
103*6777b538SAndroid Build Coastguard Worker uint128 CityHash128(const char* s, size_t len);
104*6777b538SAndroid Build Coastguard Worker 
105*6777b538SAndroid Build Coastguard Worker // Hash function for a byte array.  For convenience, a 128-bit seed is also
106*6777b538SAndroid Build Coastguard Worker // hashed into the result.
107*6777b538SAndroid Build Coastguard Worker uint128 CityHash128WithSeed(const char* s, size_t len, uint128 seed);
108*6777b538SAndroid Build Coastguard Worker 
109*6777b538SAndroid Build Coastguard Worker // Hash function for a byte array.  Most useful in 32-bit binaries.
110*6777b538SAndroid Build Coastguard Worker uint32 CityHash32(const char* buf, size_t len);
111*6777b538SAndroid Build Coastguard Worker 
112*6777b538SAndroid Build Coastguard Worker // Hash 128 input bits down to 64 bits of output.
113*6777b538SAndroid Build Coastguard Worker // This is intended to be a reasonably good hash function.
Hash128to64(const uint128 & x)114*6777b538SAndroid Build Coastguard Worker inline uint64 Hash128to64(const uint128& x) {
115*6777b538SAndroid Build Coastguard Worker   // Murmur-inspired hashing.
116*6777b538SAndroid Build Coastguard Worker   const uint64 kMul = 0x9ddfea08eb382d69ULL;
117*6777b538SAndroid Build Coastguard Worker   uint64 a = (Uint128Low64(x) ^ Uint128High64(x)) * kMul;
118*6777b538SAndroid Build Coastguard Worker   a ^= (a >> 47);
119*6777b538SAndroid Build Coastguard Worker   uint64 b = (Uint128High64(x) ^ a) * kMul;
120*6777b538SAndroid Build Coastguard Worker   b ^= (b >> 47);
121*6777b538SAndroid Build Coastguard Worker   b *= kMul;
122*6777b538SAndroid Build Coastguard Worker   return b;
123*6777b538SAndroid Build Coastguard Worker }
124*6777b538SAndroid Build Coastguard Worker 
125*6777b538SAndroid Build Coastguard Worker }  // namespace cityhash_v111
126*6777b538SAndroid Build Coastguard Worker }  // namespace internal
127*6777b538SAndroid Build Coastguard Worker }  // namespace base
128*6777b538SAndroid Build Coastguard Worker 
129*6777b538SAndroid Build Coastguard Worker #endif  // CITY_HASH_H_
130