libstdc++-v3/libsupc++/hash_bytes.cc

   1 // Definition of _Hash_bytes. -*- C++ -*-
   2
   3 // Copyright (C) 2010-2023 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 3, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // Under Section 7 of GPL version 3, you are granted additional
  17 // permissions described in the GCC Runtime Library Exception, version
  18 // 3.1, as published by the Free Software Foundation.
  19
  20 // You should have received a copy of the GNU General Public License and
  21 // a copy of the GCC Runtime Library Exception along with this program;
  22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23 // <http://www.gnu.org/licenses/>.
  24
  25 // This file defines Hash_bytes, a primitive used for defining hash
  26 // functions. Based on public domain MurmurHashUnaligned2, by Austin
  27 // Appleby.  http://murmurhash.googlepages.com/
  28
  29 // This file also defines _Fnv_hash_bytes, another primitive with
  30 // exactly the same interface but using a different hash algorithm,
  31 // Fowler / Noll / Vo (FNV) Hash (type FNV-1a). The Murmur hash
  32 // function apears to be better in both speed and hash quality, and
  33 // FNV is provided primarily for backward compatibility.
  34
  35 #include <bits/hash_bytes.h>
  36
  37 namespace
  38 {
  39   inline std::size_t
  40   unaligned_load(const char* p)
  41   {
  42     std::size_t result;
  43     __builtin_memcpy(&result, p, sizeof(result));
  44     return result;
  45   }
  46
  47 #if __SIZEOF_SIZE_T__ == 8
  48   // Loads n bytes, where 1 <= n < 8.
  49   inline std::size_t
  50   load_bytes(const char* p, int n)
  51   {
  52     std::size_t result = 0;
  53     --n;
  54     do
  55       result = (result << 8) + static_cast<unsigned char>(p[n]);
  56     while (--n >= 0);
  57     return result;
  58   }
  59
  60   inline std::size_t
  61   shift_mix(std::size_t v)
  62   { return v ^ (v >> 47);}
  63 #endif
  64 }
  65
  66 namespace std
  67 {
  68 _GLIBCXX_BEGIN_NAMESPACE_VERSION
  69
  70 #if __SIZEOF_SIZE_T__ == 4
  71
  72   // Implementation of Murmur hash for 32-bit size_t.
  73   size_t
  74   _Hash_bytes(const void* ptr, size_t len, size_t seed)
  75   {
  76     const size_t m = 0x5bd1e995;
  77     size_t hash = seed ^ len;
  78     const char* buf = static_cast<const char*>(ptr);
  79
  80     // Mix 4 bytes at a time into the hash.
  81     while(len >= 4)
  82       {
  83         size_t k = unaligned_load(buf);
  84         k *= m;
  85         k ^= k >> 24;
  86         k *= m;
  87         hash *= m;
  88         hash ^= k;
  89         buf += 4;
  90         len -= 4;
  91       }
  92
  93     size_t k;
  94     // Handle the last few bytes of the input array.
  95     switch(len)
  96       {
  97       case 3:
  98         k = static_cast<unsigned char>(buf[2]);
  99         hash ^= k << 16;
 100         [[gnu::fallthrough]];
 101       case 2:
 102         k = static_cast<unsigned char>(buf[1]);
 103         hash ^= k << 8;
 104         [[gnu::fallthrough]];
 105       case 1:
 106         k = static_cast<unsigned char>(buf[0]);
 107         hash ^= k;
 108         hash *= m;
 109       };
 110
 111     // Do a few final mixes of the hash.
 112     hash ^= hash >> 13;
 113     hash *= m;
 114     hash ^= hash >> 15;
 115     return hash;
 116   }
 117
 118   // Implementation of FNV hash for 32-bit size_t.
 119   // N.B. This function should work on unsigned char, otherwise it does not
 120   // correctly implement the FNV-1a algorithm (see PR59406).
 121   // The existing behaviour is retained for backwards compatibility.
 122   size_t
 123   _Fnv_hash_bytes(const void* ptr, size_t len, size_t hash)
 124   {
 125     const char* cptr = static_cast<const char*>(ptr);
 126     for (; len; --len)
 127       {
 128         hash ^= static_cast<size_t>(*cptr++);
 129         hash *= static_cast<size_t>(16777619UL);
 130       }
 131     return hash;
 132   }
 133
 134 #elif __SIZEOF_SIZE_T__ == 8
 135
 136   // Implementation of Murmur hash for 64-bit size_t.
 137   size_t
 138   _Hash_bytes(const void* ptr, size_t len, size_t seed)
 139   {
 140     static const size_t mul = (((size_t) 0xc6a4a793UL) << 32UL)
 141                               + (size_t) 0x5bd1e995UL;
 142     const char* const buf = static_cast<const char*>(ptr);
 143
 144     // Remove the bytes not divisible by the sizeof(size_t).  This
 145     // allows the main loop to process the data as 64-bit integers.
 146     const size_t len_aligned = len & ~(size_t)0x7;
 147     const char* const end = buf + len_aligned;
 148     size_t hash = seed ^ (len * mul);
 149     for (const char* p = buf; p != end; p += 8)
 150       {
 151         const size_t data = shift_mix(unaligned_load(p) * mul) * mul;
 152         hash ^= data;
 153         hash *= mul;
 154       }
 155     if ((len & 0x7) != 0)
 156       {
 157         const size_t data = load_bytes(end, len & 0x7);
 158         hash ^= data;
 159         hash *= mul;
 160       }
 161     hash = shift_mix(hash) * mul;
 162     hash = shift_mix(hash);
 163     return hash;
 164   }
 165
 166   // Implementation of FNV hash for 64-bit size_t.
 167   // N.B. This function should work on unsigned char, otherwise it does not
 168   // correctly implement the FNV-1a algorithm (see PR59406).
 169   // The existing behaviour is retained for backwards compatibility.
 170   size_t
 171   _Fnv_hash_bytes(const void* ptr, size_t len, size_t hash)
 172   {
 173     const char* cptr = static_cast<const char*>(ptr);
 174     for (; len; --len)
 175       {
 176         hash ^= static_cast<size_t>(*cptr++);
 177         hash *= static_cast<size_t>(1099511628211ULL);
 178       }
 179     return hash;
 180   }
 181
 182 #else
 183
 184   // Dummy hash implementation for unusual sizeof(size_t).
 185   size_t
 186   _Hash_bytes(const void* ptr, size_t len, size_t seed)
 187   {
 188     size_t hash = seed;
 189     const char* cptr = reinterpret_cast<const char*>(ptr);
 190     for (; len; --len)
 191       hash = (hash * 131) + *cptr++;
 192     return hash;
 193   }
 194
 195   size_t
 196   _Fnv_hash_bytes(const void* ptr, size_t len, size_t seed)
 197   { return _Hash_bytes(ptr, len, seed); }
 198
 199 #endif /* __SIZEOF_SIZE_T__ */
 200
 201 _GLIBCXX_END_NAMESPACE_VERSION
 202 } // namespace