gcc/inchash.c

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