1/* Incremential hashing for jhash.
2   Copyright (C) 2014-2015 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify it under
7the terms of the GNU General Public License as published by the Free
8Software Foundation; either version 3, or (at your option) any later
9version.
10
11GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12WARRANTY; without even the implied warranty of MERCHANTABILITY or
13FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14for more details.
15
16You should have received a copy of the GNU General Public License
17along 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.  */
42hashval_t
43iterative_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
54hashval_t
55iterative_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