gcc/rust/util/fnv-hash.h

   1 // Copyright (C) 2020-2023 Free Software Foundation, Inc.
   2
   3 // This file is part of GCC.
   4
   5 // GCC is free software; you can redistribute it and/or modify it under
   6 // the terms of the GNU General Public License as published by the Free
   7 // Software Foundation; either version 3, or (at your option) any later
   8 // version.
   9
  10 // GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  11 // WARRANTY; without even the implied warranty of MERCHANTABILITY or
  12 // FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  13 // for more details.
  14
  15 // You should have received a copy of the GNU General Public License
  16 // along with GCC; see the file COPYING3.  If not see
  17 // <http://www.gnu.org/licenses/>.
  18
  19 #ifndef RUST_FNV_HASH_H
  20 #define RUST_FNV_HASH_H
  21
  22 namespace Rust {
  23 namespace Hash {
  24
  25 const uint64_t offset128Lower = 0x62b821756295c58d;
  26 const uint64_t offset128Higher = 0x6c62272e07bb0142;
  27 const uint64_t prime128Lower = 0x13b;
  28 const uint64_t prime128Shift = 24;
  29
  30 // ported from https://github.com/golang/go/blob/master/src/hash/fnv/fnv.go
  31 class FNV128
  32 {
  33 public:
  34   FNV128 () { reset (); }
  35
  36   void reset ()
  37   {
  38     buf[0] = offset128Higher;
  39     buf[1] = offset128Lower;
  40   }
  41
  42   void write (const unsigned char *in, size_t len)
  43   {
  44     for (size_t i = 0; i < len; i++)
  45       {
  46         unsigned char c = in[i];
  47
  48         // https://stackoverflow.com/questions/28868367/getting-the-high-part-of-64-bit-integer-multiplication
  49         uint64_t a = prime128Lower;
  50         uint64_t b = buf[1];
  51
  52         uint64_t a_lo = (uint32_t) a;
  53         uint64_t a_hi = a >> 32;
  54         uint64_t b_lo = (uint32_t) b;
  55         uint64_t b_hi = b >> 32;
  56
  57         uint64_t a_x_b_hi = a_hi * b_hi;
  58         uint64_t a_x_b_mid = a_hi * b_lo;
  59         uint64_t b_x_a_mid = b_hi * a_lo;
  60         uint64_t a_x_b_lo = a_lo * b_lo;
  61
  62         uint64_t carry_bit
  63           = ((uint64_t) (uint32_t) a_x_b_mid + (uint64_t) (uint32_t) b_x_a_mid
  64              + (a_x_b_lo >> 32))
  65             >> 32;
  66
  67         uint64_t multhi
  68           = a_x_b_hi + (a_x_b_mid >> 32) + (b_x_a_mid >> 32) + carry_bit;
  69
  70         uint64_t s0 = multhi;                 // high
  71         uint64_t s1 = prime128Lower * buf[1]; // low
  72
  73         s0 += buf[1] << (prime128Shift + prime128Lower * buf[0]);
  74
  75         // Update the values
  76         buf[1] = s1;
  77         buf[0] = s0;
  78         buf[1] ^= (uint64_t) c;
  79       }
  80   }
  81
  82   void sum (uint64_t *hi, uint64_t *lo) const
  83   {
  84     *hi = buf[0];
  85     *lo = buf[1];
  86   }
  87
  88 private:
  89   uint64_t buf[2];
  90 };
  91
  92 } // namespace Hash
  93 } // namespace Rust
  94
  95 #endif // RUST_FNV_HASH_H