1 | //===- llvm/ADT/StableHashing.h - Utilities for stable hashing * C++ *-----===// |
2 | // |
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | // See https://llvm.org/LICENSE.txt for license information. |
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | // |
7 | //===----------------------------------------------------------------------===// |
8 | // |
9 | // This file provides types and functions for computing and combining stable |
10 | // hashes. Stable hashes can be useful for hashing across different modules, |
11 | // processes, or compiler runs. |
12 | // |
13 | //===----------------------------------------------------------------------===// |
14 | |
15 | #ifndef LLVM_ADT_STABLEHASHING_H |
16 | #define LLVM_ADT_STABLEHASHING_H |
17 | |
18 | #include "llvm/ADT/StringRef.h" |
19 | |
20 | namespace llvm { |
21 | |
22 | /// An opaque object representing a stable hash code. It can be serialized, |
23 | /// deserialized, and is stable across processes and executions. |
24 | using stable_hash = uint64_t; |
25 | |
26 | // Implementation details |
27 | namespace hashing { |
28 | namespace detail { |
29 | |
30 | // Stable hashes are based on the 64-bit FNV-1 hash: |
31 | // https://en.wikipedia.org/wiki/Fowler-Noll-Vo_hash_function |
32 | |
33 | const uint64_t FNV_PRIME_64 = 1099511628211u; |
34 | const uint64_t FNV_OFFSET_64 = 14695981039346656037u; |
35 | |
36 | inline void stable_hash_append(stable_hash &Hash, const char Value) { |
37 | Hash = Hash ^ (Value & 0xFF); |
38 | Hash = Hash * FNV_PRIME_64; |
39 | } |
40 | |
41 | inline void stable_hash_append(stable_hash &Hash, stable_hash Value) { |
42 | for (unsigned I = 0; I < 8; ++I) { |
43 | stable_hash_append(Hash, Value: static_cast<char>(Value)); |
44 | Value >>= 8; |
45 | } |
46 | } |
47 | |
48 | } // namespace detail |
49 | } // namespace hashing |
50 | |
51 | inline stable_hash stable_hash_combine(stable_hash A, stable_hash B) { |
52 | stable_hash Hash = hashing::detail::FNV_OFFSET_64; |
53 | hashing::detail::stable_hash_append(Hash, Value: A); |
54 | hashing::detail::stable_hash_append(Hash, Value: B); |
55 | return Hash; |
56 | } |
57 | |
58 | inline stable_hash stable_hash_combine(stable_hash A, stable_hash B, |
59 | stable_hash C) { |
60 | stable_hash Hash = hashing::detail::FNV_OFFSET_64; |
61 | hashing::detail::stable_hash_append(Hash, Value: A); |
62 | hashing::detail::stable_hash_append(Hash, Value: B); |
63 | hashing::detail::stable_hash_append(Hash, Value: C); |
64 | return Hash; |
65 | } |
66 | |
67 | inline stable_hash stable_hash_combine(stable_hash A, stable_hash B, |
68 | stable_hash C, stable_hash D) { |
69 | stable_hash Hash = hashing::detail::FNV_OFFSET_64; |
70 | hashing::detail::stable_hash_append(Hash, Value: A); |
71 | hashing::detail::stable_hash_append(Hash, Value: B); |
72 | hashing::detail::stable_hash_append(Hash, Value: C); |
73 | hashing::detail::stable_hash_append(Hash, Value: D); |
74 | return Hash; |
75 | } |
76 | |
77 | /// Compute a stable_hash for a sequence of values. |
78 | /// |
79 | /// This hashes a sequence of values. It produces the same stable_hash as |
80 | /// 'stable_hash_combine(a, b, c, ...)', but can run over arbitrary sized |
81 | /// sequences and is significantly faster given pointers and types which |
82 | /// can be hashed as a sequence of bytes. |
83 | template <typename InputIteratorT> |
84 | stable_hash stable_hash_combine_range(InputIteratorT First, |
85 | InputIteratorT Last) { |
86 | stable_hash Hash = hashing::detail::FNV_OFFSET_64; |
87 | for (auto I = First; I != Last; ++I) |
88 | hashing::detail::stable_hash_append(Hash, *I); |
89 | return Hash; |
90 | } |
91 | |
92 | inline stable_hash stable_hash_combine_array(const stable_hash *P, size_t C) { |
93 | stable_hash Hash = hashing::detail::FNV_OFFSET_64; |
94 | for (size_t I = 0; I < C; ++I) |
95 | hashing::detail::stable_hash_append(Hash, Value: P[I]); |
96 | return Hash; |
97 | } |
98 | |
99 | inline stable_hash stable_hash_combine_string(const StringRef &S) { |
100 | return stable_hash_combine_range(First: S.begin(), Last: S.end()); |
101 | } |
102 | |
103 | inline stable_hash stable_hash_combine_string(const char *C) { |
104 | stable_hash Hash = hashing::detail::FNV_OFFSET_64; |
105 | while (*C) |
106 | hashing::detail::stable_hash_append(Hash, Value: *(C++)); |
107 | return Hash; |
108 | } |
109 | |
110 | } // namespace llvm |
111 | |
112 | #endif |
113 | |