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<N, T> &v) |
63 | { |
64 | for (unsigned int i = 0; i < N; ++i) |
65 | add_int (v: 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<N, T> &v) |
77 | { |
78 | for (unsigned int i = 0; i < N; ++i) |
79 | add_hwi (v: 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 (v: x.get_len ()); |
87 | for (unsigned i = 0; i < x.get_len (); i++) |
88 | add_hwi (v: x.sext_elt (i)); |
89 | } |
90 | |
91 | void add_real_value (const class real_value &v); |
92 | |
93 | /* Hash in pointer PTR. */ |
94 | void add_ptr (const void *ptr) |
95 | { |
96 | add (data: &ptr, len: sizeof (ptr)); |
97 | } |
98 | |
99 | /* Add a memory block DATA with size LEN. */ |
100 | void add (const void *data, size_t len) |
101 | { |
102 | val = iterative_hash (data, len, val); |
103 | } |
104 | |
105 | /* Merge hash value OTHER. */ |
106 | void merge_hash (hashval_t other) |
107 | { |
108 | val = iterative_hash_hashval_t (other, val); |
109 | } |
110 | |
111 | /* Hash in state from other inchash OTHER. */ |
112 | void merge (hash &other) |
113 | { |
114 | merge_hash (other: other.val); |
115 | } |
116 | |
117 | template<class T> void add_object(T &obj) |
118 | { |
119 | add (data: &obj, len: sizeof(T)); |
120 | } |
121 | |
122 | /* Support for accumulating boolean flags */ |
123 | |
124 | void add_flag (bool flag) |
125 | { |
126 | bits = (bits << 1) | flag; |
127 | } |
128 | |
129 | void commit_flag () |
130 | { |
131 | add_int (v: bits); |
132 | bits = 0; |
133 | } |
134 | |
135 | /* Support for commutative hashing. Add A and B in a defined order |
136 | based on their value. This is useful for hashing commutative |
137 | expressions, so that A+B and B+A get the same hash. */ |
138 | |
139 | void add_commutative (hash &a, hash &b) |
140 | { |
141 | if (a.end() > b.end()) |
142 | { |
143 | merge (other&: b); |
144 | merge (other&: a); |
145 | } |
146 | else |
147 | { |
148 | merge (other&: a); |
149 | merge (other&: b); |
150 | } |
151 | } |
152 | |
153 | private: |
154 | hashval_t val; |
155 | unsigned bits; |
156 | }; |
157 | |
158 | } |
159 | |
160 | /* Borrowed from hashtab.c iterative_hash implementation. */ |
161 | #define mix(a,b,c) \ |
162 | { \ |
163 | a -= b; a -= c; a ^= (c>>13); \ |
164 | b -= c; b -= a; b ^= (a<< 8); \ |
165 | c -= a; c -= b; c ^= ((b&0xffffffff)>>13); \ |
166 | a -= b; a -= c; a ^= ((c&0xffffffff)>>12); \ |
167 | b -= c; b -= a; b = (b ^ (a<<16)) & 0xffffffff; \ |
168 | c -= a; c -= b; c = (c ^ (b>> 5)) & 0xffffffff; \ |
169 | a -= b; a -= c; a = (a ^ (c>> 3)) & 0xffffffff; \ |
170 | b -= c; b -= a; b = (b ^ (a<<10)) & 0xffffffff; \ |
171 | c -= a; c -= b; c = (c ^ (b>>15)) & 0xffffffff; \ |
172 | } |
173 | |
174 | |
175 | /* Produce good hash value combining VAL and VAL2. */ |
176 | inline |
177 | hashval_t |
178 | iterative_hash_hashval_t (hashval_t val, hashval_t val2) |
179 | { |
180 | /* the golden ratio; an arbitrary value. */ |
181 | hashval_t a = 0x9e3779b9; |
182 | |
183 | mix (a, val, val2); |
184 | return val2; |
185 | } |
186 | |
187 | /* Produce good hash value combining VAL and VAL2. */ |
188 | |
189 | inline |
190 | hashval_t |
191 | iterative_hash_host_wide_int (HOST_WIDE_INT val, hashval_t val2) |
192 | { |
193 | if (sizeof (HOST_WIDE_INT) == sizeof (hashval_t)) |
194 | return iterative_hash_hashval_t (val, val2); |
195 | else |
196 | { |
197 | hashval_t a = (hashval_t) val; |
198 | /* Avoid warnings about shifting of more than the width of the type on |
199 | hosts that won't execute this path. */ |
200 | int zero = 0; |
201 | hashval_t b = (hashval_t) (val >> (sizeof (hashval_t) * 8 + zero)); |
202 | mix (a, b, val2); |
203 | if (sizeof (HOST_WIDE_INT) > 2 * sizeof (hashval_t)) |
204 | { |
205 | hashval_t a = (hashval_t) (val >> (sizeof (hashval_t) * 16 + zero)); |
206 | hashval_t b = (hashval_t) (val >> (sizeof (hashval_t) * 24 + zero)); |
207 | mix (a, b, val2); |
208 | } |
209 | return val2; |
210 | } |
211 | } |
212 | |
213 | #endif |
214 | |