1 /* Incremential hashing for jhash. 2 Copyright (C) 2014-2015 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 #include "config.h" 21 #include "system.h" 22 #include "coretypes.h" 23 #include "hashtab.h" 24 #include "inchash.h" 25 26 /* Borrowed from hashtab.c iterative_hash implementation. */ 27 #define mix(a,b,c) \ 28 { \ 29 a -= b; a -= c; a ^= (c>>13); \ 30 b -= c; b -= a; b ^= (a<< 8); \ 31 c -= a; c -= b; c ^= ((b&0xffffffff)>>13); \ 32 a -= b; a -= c; a ^= ((c&0xffffffff)>>12); \ 33 b -= c; b -= a; b = (b ^ (a<<16)) & 0xffffffff; \ 34 c -= a; c -= b; c = (c ^ (b>> 5)) & 0xffffffff; \ 35 a -= b; a -= c; a = (a ^ (c>> 3)) & 0xffffffff; \ 36 b -= c; b -= a; b = (b ^ (a<<10)) & 0xffffffff; \ 37 c -= a; c -= b; c = (c ^ (b>>15)) & 0xffffffff; \ 38 } 39 40 41 /* Produce good hash value combining VAL and VAL2. */ 42 hashval_t 43 iterative_hash_hashval_t (hashval_t val, hashval_t val2) 44 { 45 /* the golden ratio; an arbitrary value. */ 46 hashval_t a = 0x9e3779b9; 47 48 mix (a, val, val2); 49 return val2; 50 } 51 52 /* Produce good hash value combining VAL and VAL2. */ 53 54 hashval_t 55 iterative_hash_host_wide_int (HOST_WIDE_INT val, hashval_t val2) 56 { 57 if (sizeof (HOST_WIDE_INT) == sizeof (hashval_t)) 58 return iterative_hash_hashval_t (val, val2); 59 else 60 { 61 hashval_t a = (hashval_t) val; 62 /* Avoid warnings about shifting of more than the width of the type on 63 hosts that won't execute this path. */ 64 int zero = 0; 65 hashval_t b = (hashval_t) (val >> (sizeof (hashval_t) * 8 + zero)); 66 mix (a, b, val2); 67 if (sizeof (HOST_WIDE_INT) > 2 * sizeof (hashval_t)) 68 { 69 hashval_t a = (hashval_t) (val >> (sizeof (hashval_t) * 16 + zero)); 70 hashval_t b = (hashval_t) (val >> (sizeof (hashval_t) * 24 + zero)); 71 mix (a, b, val2); 72 } 73 return val2; 74 } 75 } 76