1// Definition of _Hash_bytes. -*- C++ -*-
2
3// Copyright (C) 2010-2020 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
37namespace
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
66namespace 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    // Handle the last few bytes of the input array.
94    switch(len)
95      {
96      case 3:
97	hash ^= static_cast<unsigned char>(buf[2]) << 16;
98	[[gnu::fallthrough]];
99      case 2:
100	hash ^= static_cast<unsigned char>(buf[1]) << 8;
101	[[gnu::fallthrough]];
102      case 1:
103	hash ^= static_cast<unsigned char>(buf[0]);
104	hash *= m;
105      };
106
107    // Do a few final mixes of the hash.
108    hash ^= hash >> 13;
109    hash *= m;
110    hash ^= hash >> 15;
111    return hash;
112  }
113
114  // Implementation of FNV hash for 32-bit size_t.
115  // N.B. This function should work on unsigned char, otherwise it does not
116  // correctly implement the FNV-1a algorithm (see PR59406).
117  // The existing behaviour is retained for backwards compatibility.
118  size_t
119  _Fnv_hash_bytes(const void* ptr, size_t len, size_t hash)
120  {
121    const char* cptr = static_cast<const char*>(ptr);
122    for (; len; --len)
123      {
124	hash ^= static_cast<size_t>(*cptr++);
125	hash *= static_cast<size_t>(16777619UL);
126      }
127    return hash;
128  }
129
130#elif __SIZEOF_SIZE_T__ == 8
131
132  // Implementation of Murmur hash for 64-bit size_t.
133  size_t
134  _Hash_bytes(const void* ptr, size_t len, size_t seed)
135  {
136    static const size_t mul = (((size_t) 0xc6a4a793UL) << 32UL)
137			      + (size_t) 0x5bd1e995UL;
138    const char* const buf = static_cast<const char*>(ptr);
139
140    // Remove the bytes not divisible by the sizeof(size_t).  This
141    // allows the main loop to process the data as 64-bit integers.
142    const size_t len_aligned = len & ~(size_t)0x7;
143    const char* const end = buf + len_aligned;
144    size_t hash = seed ^ (len * mul);
145    for (const char* p = buf; p != end; p += 8)
146      {
147	const size_t data = shift_mix(unaligned_load(p) * mul) * mul;
148	hash ^= data;
149	hash *= mul;
150      }
151    if ((len & 0x7) != 0)
152      {
153	const size_t data = load_bytes(end, len & 0x7);
154	hash ^= data;
155	hash *= mul;
156      }
157    hash = shift_mix(hash) * mul;
158    hash = shift_mix(hash);
159    return hash;
160  }
161
162  // Implementation of FNV hash for 64-bit size_t.
163  // N.B. This function should work on unsigned char, otherwise it does not
164  // correctly implement the FNV-1a algorithm (see PR59406).
165  // The existing behaviour is retained for backwards compatibility.
166  size_t
167  _Fnv_hash_bytes(const void* ptr, size_t len, size_t hash)
168  {
169    const char* cptr = static_cast<const char*>(ptr);
170    for (; len; --len)
171      {
172	hash ^= static_cast<size_t>(*cptr++);
173	hash *= static_cast<size_t>(1099511628211ULL);
174      }
175    return hash;
176  }
177
178#else
179
180  // Dummy hash implementation for unusual sizeof(size_t).
181  size_t
182  _Hash_bytes(const void* ptr, size_t len, size_t seed)
183  {
184    size_t hash = seed;
185    const char* cptr = reinterpret_cast<const char*>(ptr);
186    for (; len; --len)
187      hash = (hash * 131) + *cptr++;
188    return hash;
189  }
190
191  size_t
192  _Fnv_hash_bytes(const void* ptr, size_t len, size_t seed)
193  { return _Hash_bytes(ptr, len, seed); }
194
195#endif /* __SIZEOF_SIZE_T__ */
196
197_GLIBCXX_END_NAMESPACE_VERSION
198} // namespace
199