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
stable_hash_append(stable_hash & Hash,const char Value)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
stable_hash_append(stable_hash & Hash,stable_hash Value)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, static_cast<char>(Value));
44 Value >>= 8;
45 }
46 }
47
48 } // namespace detail
49 } // namespace hashing
50
stable_hash_combine(stable_hash A,stable_hash B)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, A);
54 hashing::detail::stable_hash_append(Hash, B);
55 return Hash;
56 }
57
stable_hash_combine(stable_hash A,stable_hash B,stable_hash C)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, A);
62 hashing::detail::stable_hash_append(Hash, B);
63 hashing::detail::stable_hash_append(Hash, C);
64 return Hash;
65 }
66
stable_hash_combine(stable_hash A,stable_hash B,stable_hash C,stable_hash D)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, A);
71 hashing::detail::stable_hash_append(Hash, B);
72 hashing::detail::stable_hash_append(Hash, C);
73 hashing::detail::stable_hash_append(Hash, 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>
stable_hash_combine_range(InputIteratorT First,InputIteratorT Last)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
stable_hash_combine_array(const stable_hash * P,size_t C)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, P[I]);
96 return Hash;
97 }
98
stable_hash_combine_string(const StringRef & S)99 inline stable_hash stable_hash_combine_string(const StringRef &S) {
100 return stable_hash_combine_range(S.begin(), S.end());
101 }
102
stable_hash_combine_string(const char * C)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, *(C++));
107 return Hash;
108 }
109
110 } // namespace llvm
111
112 #endif
113