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