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