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, 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, A); 54 hashing::detail::stable_hash_append(Hash, 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, A); 62 hashing::detail::stable_hash_append(Hash, B); 63 hashing::detail::stable_hash_append(Hash, 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, 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> 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, P[I]); 96 return Hash; 97 } 98 99 inline stable_hash stable_hash_combine_string(const StringRef &S) { 100 return stable_hash_combine_range(S.begin(), 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, *(C++)); 107 return Hash; 108 } 109 110 } // namespace llvm 111 112 #endif 113