1 /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 /* This Source Code Form is subject to the terms of the Mozilla Public
3 * License, v. 2.0. If a copy of the MPL was not distributed with this file,
4 * You can obtain one at http://mozilla.org/MPL/2.0/. */
6 /* Utilities for hashing. */
9 * This file exports functions for hashing data down to a 32-bit value,
12 * - HashString Hash a char* or uint16_t/wchar_t* of known or unknown
15 * - HashBytes Hash a byte array of known length.
17 * - HashGeneric Hash one or more values. Currently, we support uint32_t,
18 * types which can be implicitly cast to uint32_t, data
19 * pointers, and function pointers.
21 * - AddToHash Add one or more values to the given hash. This supports the
22 * same list of types as HashGeneric.
25 * You can chain these functions together to hash complex objects. For example:
30 * uint32_t uint1, uint2;
31 * void (*callbackFn)();
35 * uint32_t hash = HashString(str);
36 * hash = AddToHash(hash, uint1, uint2);
37 * return AddToHash(hash, callbackFn);
41 * If you want to hash an nsAString or nsACString, use the HashString functions
45 #ifndef mozilla_HashFunctions_h_
46 #define mozilla_HashFunctions_h_
48 #include "mozilla/Assertions.h"
49 #include "mozilla/Attributes.h"
50 #include "mozilla/StandardInteger.h"
51 #include "mozilla/Types.h"
57 * The golden ratio as a 32-bit fixed-point value.
59 static const uint32_t GoldenRatioU32
= 0x9E3779B9U
;
62 RotateBitsLeft32(uint32_t value
, uint8_t bits
)
64 MOZ_ASSERT(bits
< 32);
65 return (value
<< bits
) | (value
>> (32 - bits
));
71 AddU32ToHash(uint32_t hash
, uint32_t value
)
74 * This is the meat of all our hash routines. This hash function is not
75 * particularly sophisticated, but it seems to work well for our mostly
76 * plain-text inputs. Implementation notes follow.
78 * Our use of the golden ratio here is arbitrary; we could pick almost any
81 * * is odd (because otherwise, all our hash values will be even)
83 * * has a reasonably-even mix of 1's and 0's (consider the extreme case
84 * where we multiply by 0x3 or 0xeffffff -- this will not produce good
85 * mixing across all bits of the hash).
87 * The rotation length of 5 is also arbitrary, although an odd number is again
88 * preferable so our hash explores the whole universe of possible rotations.
90 * Finally, we multiply by the golden ratio *after* xor'ing, not before.
91 * Otherwise, if |hash| is 0 (as it often is for the beginning of a message),
94 * (GoldenRatioU32 * RotateBitsLeft(hash, 5)) |xor| value
96 * evaluates to |value|.
98 * (Number-theoretic aside: Because any odd number |m| is relatively prime to
99 * our modulus (2^32), the list
101 * [x * m (mod 2^32) for 0 <= x < 2^32]
103 * has no duplicate elements. This means that multiplying by |m| does not
104 * cause us to skip any possible hash values.
106 * It's also nice if |m| has large-ish order mod 2^32 -- that is, if the
107 * smallest k such that m^k == 1 (mod 2^32) is large -- so we can safely
108 * multiply our hash value by |m| a few times without negating the
109 * multiplicative effect. Our golden ratio constant has order 2^29, which is
110 * more than enough for our purposes.)
112 return GoldenRatioU32
* (RotateBitsLeft32(hash
, 5) ^ value
);
116 * AddUintptrToHash takes sizeof(uintptr_t) as a template parameter.
118 template<size_t PtrSize
>
120 AddUintptrToHash(uint32_t hash
, uintptr_t value
);
124 AddUintptrToHash
<4>(uint32_t hash
, uintptr_t value
)
126 return AddU32ToHash(hash
, static_cast<uint32_t>(value
));
131 AddUintptrToHash
<8>(uint32_t hash
, uintptr_t value
)
134 * The static cast to uint64_t below is necessary because this function
135 * sometimes gets compiled on 32-bit platforms (yes, even though it's a
136 * template and we never call this particular override in a 32-bit build). If
137 * we do value >> 32 on a 32-bit machine, we're shifting a 32-bit uintptr_t
138 * right 32 bits, and the compiler throws an error.
140 uint32_t v1
= static_cast<uint32_t>(value
);
141 uint32_t v2
= static_cast<uint32_t>(static_cast<uint64_t>(value
) >> 32);
142 return AddU32ToHash(AddU32ToHash(hash
, v1
), v2
);
145 } /* namespace detail */
148 * AddToHash takes a hash and some values and returns a new hash based on the
151 * Currently, we support hashing uint32_t's, values which we can implicitly
152 * convert to uint32_t, data pointers, and function pointers.
155 MOZ_WARN_UNUSED_RESULT
157 AddToHash(uint32_t hash
, A a
)
160 * Try to convert |A| to uint32_t implicitly. If this works, great. If not,
163 return detail::AddU32ToHash(hash
, a
);
167 MOZ_WARN_UNUSED_RESULT
169 AddToHash(uint32_t hash
, A
* a
)
172 * You might think this function should just take a void*. But then we'd only
173 * catch data pointers and couldn't handle function pointers.
176 MOZ_STATIC_ASSERT(sizeof(a
) == sizeof(uintptr_t),
179 return detail::AddUintptrToHash
<sizeof(uintptr_t)>(hash
, uintptr_t(a
));
183 MOZ_WARN_UNUSED_RESULT
185 AddToHash(uint32_t hash
, uintptr_t a
)
187 return detail::AddUintptrToHash
<sizeof(uintptr_t)>(hash
, a
);
190 template<typename A
, typename B
>
191 MOZ_WARN_UNUSED_RESULT
193 AddToHash(uint32_t hash
, A a
, B b
)
195 return AddToHash(AddToHash(hash
, a
), b
);
198 template<typename A
, typename B
, typename C
>
199 MOZ_WARN_UNUSED_RESULT
201 AddToHash(uint32_t hash
, A a
, B b
, C c
)
203 return AddToHash(AddToHash(hash
, a
, b
), c
);
206 template<typename A
, typename B
, typename C
, typename D
>
207 MOZ_WARN_UNUSED_RESULT
209 AddToHash(uint32_t hash
, A a
, B b
, C c
, D d
)
211 return AddToHash(AddToHash(hash
, a
, b
, c
), d
);
214 template<typename A
, typename B
, typename C
, typename D
, typename E
>
215 MOZ_WARN_UNUSED_RESULT
217 AddToHash(uint32_t hash
, A a
, B b
, C c
, D d
, E e
)
219 return AddToHash(AddToHash(hash
, a
, b
, c
, d
), e
);
223 * The HashGeneric class of functions let you hash one or more values.
225 * If you want to hash together two values x and y, calling HashGeneric(x, y) is
226 * much better than calling AddToHash(x, y), because AddToHash(x, y) assumes
227 * that x has already been hashed.
230 MOZ_WARN_UNUSED_RESULT
234 return AddToHash(0, a
);
237 template<typename A
, typename B
>
238 MOZ_WARN_UNUSED_RESULT
240 HashGeneric(A a
, B b
)
242 return AddToHash(0, a
, b
);
245 template<typename A
, typename B
, typename C
>
246 MOZ_WARN_UNUSED_RESULT
248 HashGeneric(A a
, B b
, C c
)
250 return AddToHash(0, a
, b
, c
);
253 template<typename A
, typename B
, typename C
, typename D
>
254 MOZ_WARN_UNUSED_RESULT
256 HashGeneric(A a
, B b
, C c
, D d
)
258 return AddToHash(0, a
, b
, c
, d
);
261 template<typename A
, typename B
, typename C
, typename D
, typename E
>
262 MOZ_WARN_UNUSED_RESULT
264 HashGeneric(A a
, B b
, C c
, D d
, E e
)
266 return AddToHash(0, a
, b
, c
, d
, e
);
273 HashUntilZero(const T
* str
)
276 for (T c
; (c
= *str
); str
++)
277 hash
= AddToHash(hash
, c
);
283 HashKnownLength(const T
* str
, size_t length
)
286 for (size_t i
= 0; i
< length
; i
++)
287 hash
= AddToHash(hash
, str
[i
]);
291 } /* namespace detail */
294 * The HashString overloads below do just what you'd expect.
296 * If you have the string's length, you might as well call the overload which
297 * includes the length. It may be marginally faster.
299 MOZ_WARN_UNUSED_RESULT
301 HashString(const char* str
)
303 return detail::HashUntilZero(str
);
306 MOZ_WARN_UNUSED_RESULT
308 HashString(const char* str
, size_t length
)
310 return detail::HashKnownLength(str
, length
);
313 MOZ_WARN_UNUSED_RESULT
315 HashString(const uint16_t* str
)
317 return detail::HashUntilZero(str
);
320 MOZ_WARN_UNUSED_RESULT
322 HashString(const uint16_t* str
, size_t length
)
324 return detail::HashKnownLength(str
, length
);
328 * On Windows, wchar_t (PRUnichar) is not the same as uint16_t, even though it's
332 MOZ_WARN_UNUSED_RESULT
334 HashString(const wchar_t* str
)
336 return detail::HashUntilZero(str
);
339 MOZ_WARN_UNUSED_RESULT
341 HashString(const wchar_t* str
, size_t length
)
343 return detail::HashKnownLength(str
, length
);
348 * Hash some number of bytes.
350 * This hash walks word-by-word, rather than byte-by-byte, so you won't get the
351 * same result out of HashBytes as you would out of HashString.
353 MOZ_WARN_UNUSED_RESULT
354 extern MFBT_API(uint32_t)
355 HashBytes(const void* bytes
, size_t length
);
357 } /* namespace mozilla */
358 #endif /* __cplusplus */
359 #endif /* mozilla_HashFunctions_h_ */