1 /* An incremental hash abstract data type. 2 Copyright (C) 2014-2018 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.c. */ 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.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 212