1 // Definition of _Hash_bytes. -*- C++ -*- 2 3 // Copyright (C) 2010-2018 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 // 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 int len_aligned = len & ~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