1 // Definition of _Hash_bytes. -*- C++ -*-
3 // Copyright (C) 2010-2024 Free Software Foundation, Inc.
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)
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.
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.
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/>.
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/
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.
35 #include <bits/hash_bytes.h>
40 unaligned_load(const char* p
)
43 __builtin_memcpy(&result
, p
, sizeof(result
));
47 #if __SIZEOF_SIZE_T__ == 8
48 // Loads n bytes, where 1 <= n < 8.
50 load_bytes(const char* p
, int n
)
52 std::size_t result
= 0;
55 result
= (result
<< 8) + static_cast<unsigned char>(p
[n
]);
61 shift_mix(std::size_t v
)
62 { return v
^ (v
>> 47);}
68 _GLIBCXX_BEGIN_NAMESPACE_VERSION
70 #if __SIZEOF_SIZE_T__ == 4
72 // Implementation of Murmur hash for 32-bit size_t.
74 _Hash_bytes(const void* ptr
, size_t len
, size_t seed
)
76 const size_t m
= 0x5bd1e995;
77 size_t hash
= seed
^ len
;
78 const char* buf
= static_cast<const char*>(ptr
);
80 // Mix 4 bytes at a time into the hash.
83 size_t k
= unaligned_load(buf
);
94 // Handle the last few bytes of the input array.
98 k
= static_cast<unsigned char>(buf
[2]);
100 [[gnu::fallthrough
]];
102 k
= static_cast<unsigned char>(buf
[1]);
104 [[gnu::fallthrough
]];
106 k
= static_cast<unsigned char>(buf
[0]);
111 // Do a few final mixes of the hash.
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.
123 _Fnv_hash_bytes(const void* ptr
, size_t len
, size_t hash
)
125 const char* cptr
= static_cast<const char*>(ptr
);
128 hash
^= static_cast<size_t>(*cptr
++);
129 hash
*= static_cast<size_t>(16777619UL);
134 #elif __SIZEOF_SIZE_T__ == 8
136 // Implementation of Murmur hash for 64-bit size_t.
138 _Hash_bytes(const void* ptr
, size_t len
, size_t seed
)
140 static const size_t mul
= (((size_t) 0xc6a4a793UL
) << 32UL)
141 + (size_t) 0x5bd1e995UL
;
142 const char* const buf
= static_cast<const char*>(ptr
);
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)
151 const size_t data
= shift_mix(unaligned_load(p
) * mul
) * mul
;
155 if ((len
& 0x7) != 0)
157 const size_t data
= load_bytes(end
, len
& 0x7);
161 hash
= shift_mix(hash
) * mul
;
162 hash
= shift_mix(hash
);
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.
171 _Fnv_hash_bytes(const void* ptr
, size_t len
, size_t hash
)
173 const char* cptr
= static_cast<const char*>(ptr
);
176 hash
^= static_cast<size_t>(*cptr
++);
177 hash
*= static_cast<size_t>(1099511628211ULL);
184 // Dummy hash implementation for unusual sizeof(size_t).
186 _Hash_bytes(const void* ptr
, size_t len
, size_t seed
)
189 const char* cptr
= reinterpret_cast<const char*>(ptr
);
191 hash
= (hash
* 131) + *cptr
++;
196 _Fnv_hash_bytes(const void* ptr
, size_t len
, size_t seed
)
197 { return _Hash_bytes(ptr
, len
, seed
); }
199 #endif /* __SIZEOF_SIZE_T__ */
201 _GLIBCXX_END_NAMESPACE_VERSION