1 /* An incremental hash abstract data type.
2 Copyright (C) 2014-2023 Free Software Foundation, Inc.
3
4 This file is part of GCC.
5
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
9 version.
10
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
19
20 #ifndef INCHASH_H
21 #define INCHASH_H 1
22
23
24 /* This file implements an incremential hash function ADT, to be used
25 by code that incrementially hashes a lot of unrelated data
26 (not in a single memory block) into a single value. The goal
27 is to make it easy to plug in efficient hash algorithms.
28 Currently it just implements the plain old jhash based
29 incremental hash from gcc's tree.cc. */
30
31 hashval_t iterative_hash_host_wide_int (HOST_WIDE_INT, hashval_t);
32 hashval_t iterative_hash_hashval_t (hashval_t, hashval_t);
33
34 namespace inchash
35 {
36
37 class hash
38 {
39 public:
40
41 /* Start incremential hashing, optionally with SEED. */
42 hash (hashval_t seed = 0)
43 {
44 val = seed;
45 bits = 0;
46 }
47
48 /* End incremential hashing and provide the final value. */
49 hashval_t end ()
50 {
51 return val;
52 }
53
54 /* Add unsigned value V. */
55 void add_int (unsigned v)
56 {
57 val = iterative_hash_hashval_t (v, val);
58 }
59
60 /* Add polynomial value V, treating each element as an unsigned int. */
61 template<unsigned int N, typename T>
62 void add_poly_int (const poly_int_pod<N, T> &v)
63 {
64 for (unsigned int i = 0; i < N; ++i)
65 add_int (v.coeffs[i]);
66 }
67
68 /* Add HOST_WIDE_INT value V. */
69 void add_hwi (HOST_WIDE_INT v)
70 {
71 val = iterative_hash_host_wide_int (v, val);
72 }
73
74 /* Add polynomial value V, treating each element as a HOST_WIDE_INT. */
75 template<unsigned int N, typename T>
76 void add_poly_hwi (const poly_int_pod<N, T> &v)
77 {
78 for (unsigned int i = 0; i < N; ++i)
79 add_hwi (v.coeffs[i]);
80 }
81
82 /* Add wide_int-based value V. */
83 template<typename T>
84 void add_wide_int (const generic_wide_int<T> &x)
85 {
86 add_int (x.get_len ());
87 for (unsigned i = 0; i < x.get_len (); i++)
88 add_hwi (x.sext_elt (i));
89 }
90
91 /* Hash in pointer PTR. */
92 void add_ptr (const void *ptr)
93 {
94 add (&ptr, sizeof (ptr));
95 }
96
97 /* Add a memory block DATA with size LEN. */
98 void add (const void *data, size_t len)
99 {
100 val = iterative_hash (data, len, val);
101 }
102
103 /* Merge hash value OTHER. */
104 void merge_hash (hashval_t other)
105 {
106 val = iterative_hash_hashval_t (other, val);
107 }
108
109 /* Hash in state from other inchash OTHER. */
110 void merge (hash &other)
111 {
112 merge_hash (other.val);
113 }
114
115 template<class T> void add_object(T &obj)
116 {
117 add (&obj, sizeof(T));
118 }
119
120 /* Support for accumulating boolean flags */
121
122 void add_flag (bool flag)
123 {
124 bits = (bits << 1) | flag;
125 }
126
127 void commit_flag ()
128 {
129 add_int (bits);
130 bits = 0;
131 }
132
133 /* Support for commutative hashing. Add A and B in a defined order
134 based on their value. This is useful for hashing commutative
135 expressions, so that A+B and B+A get the same hash. */
136
137 void add_commutative (hash &a, hash &b)
138 {
139 if (a.end() > b.end())
140 {
141 merge (b);
142 merge (a);
143 }
144 else
145 {
146 merge (a);
147 merge (b);
148 }
149 }
150
151 private:
152 hashval_t val;
153 unsigned bits;
154 };
155
156 }
157
158 /* Borrowed from hashtab.c iterative_hash implementation. */
159 #define mix(a,b,c) \
160 { \
161 a -= b; a -= c; a ^= (c>>13); \
162 b -= c; b -= a; b ^= (a<< 8); \
163 c -= a; c -= b; c ^= ((b&0xffffffff)>>13); \
164 a -= b; a -= c; a ^= ((c&0xffffffff)>>12); \
165 b -= c; b -= a; b = (b ^ (a<<16)) & 0xffffffff; \
166 c -= a; c -= b; c = (c ^ (b>> 5)) & 0xffffffff; \
167 a -= b; a -= c; a = (a ^ (c>> 3)) & 0xffffffff; \
168 b -= c; b -= a; b = (b ^ (a<<10)) & 0xffffffff; \
169 c -= a; c -= b; c = (c ^ (b>>15)) & 0xffffffff; \
170 }
171
172
173 /* Produce good hash value combining VAL and VAL2. */
174 inline
175 hashval_t
176 iterative_hash_hashval_t (hashval_t val, hashval_t val2)
177 {
178 /* the golden ratio; an arbitrary value. */
179 hashval_t a = 0x9e3779b9;
180
181 mix (a, val, val2);
182 return val2;
183 }
184
185 /* Produce good hash value combining VAL and VAL2. */
186
187 inline
188 hashval_t
189 iterative_hash_host_wide_int (HOST_WIDE_INT val, hashval_t val2)
190 {
191 if (sizeof (HOST_WIDE_INT) == sizeof (hashval_t))
192 return iterative_hash_hashval_t (val, val2);
193 else
194 {
195 hashval_t a = (hashval_t) val;
196 /* Avoid warnings about shifting of more than the width of the type on
197 hosts that won't execute this path. */
198 int zero = 0;
199 hashval_t b = (hashval_t) (val >> (sizeof (hashval_t) * 8 + zero));
200 mix (a, b, val2);
201 if (sizeof (HOST_WIDE_INT) > 2 * sizeof (hashval_t))
202 {
203 hashval_t a = (hashval_t) (val >> (sizeof (hashval_t) * 16 + zero));
204 hashval_t b = (hashval_t) (val >> (sizeof (hashval_t) * 24 + zero));
205 mix (a, b, val2);
206 }
207 return val2;
208 }
209 }
210
211 #endif