0,0 → 1,190 |
// Definition of _Hash_bytes. -*- C++ -*- |
|
// Copyright (C) 2010-2015 Free Software Foundation, Inc. |
// |
// This file is part of the GNU ISO C++ Library. This library is free |
// software; you can redistribute it and/or modify it under the |
// terms of the GNU General Public License as published by the |
// Free Software Foundation; either version 3, or (at your option) |
// any later version. |
|
// This library is distributed in the hope that it will be useful, |
// but WITHOUT ANY WARRANTY; without even the implied warranty of |
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
// GNU General Public License for more details. |
|
// Under Section 7 of GPL version 3, you are granted additional |
// permissions described in the GCC Runtime Library Exception, version |
// 3.1, as published by the Free Software Foundation. |
|
// You should have received a copy of the GNU General Public License and |
// a copy of the GCC Runtime Library Exception along with this program; |
// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see |
// <http://www.gnu.org/licenses/>. |
|
// This file defines Hash_bytes, a primitive used for defining hash |
// functions. Based on public domain MurmurHashUnaligned2, by Austin |
// Appleby. http://murmurhash.googlepages.com/ |
|
// This file also defines _Fnv_hash_bytes, another primitive with |
// exactly the same interface but using a different hash algorithm, |
// Fowler / Noll / Vo (FNV) Hash (type FNV-1a). The Murmur hash |
// function apears to be better in both speed and hash quality, and |
// FNV is provided primarily for backward compatibility. |
|
#include <bits/hash_bytes.h> |
|
namespace |
{ |
inline std::size_t |
unaligned_load(const char* p) |
{ |
std::size_t result; |
__builtin_memcpy(&result, p, sizeof(result)); |
return result; |
} |
|
#if __SIZEOF_SIZE_T__ == 8 |
// Loads n bytes, where 1 <= n < 8. |
inline std::size_t |
load_bytes(const char* p, int n) |
{ |
std::size_t result = 0; |
--n; |
do |
result = (result << 8) + static_cast<unsigned char>(p[n]); |
while (--n >= 0); |
return result; |
} |
|
inline std::size_t |
shift_mix(std::size_t v) |
{ return v ^ (v >> 47);} |
#endif |
} |
|
namespace std |
{ |
_GLIBCXX_BEGIN_NAMESPACE_VERSION |
|
#if __SIZEOF_SIZE_T__ == 4 |
|
// Implementation of Murmur hash for 32-bit size_t. |
size_t |
_Hash_bytes(const void* ptr, size_t len, size_t seed) |
{ |
const size_t m = 0x5bd1e995; |
size_t hash = seed ^ len; |
const char* buf = static_cast<const char*>(ptr); |
|
// Mix 4 bytes at a time into the hash. |
while(len >= 4) |
{ |
size_t k = unaligned_load(buf); |
k *= m; |
k ^= k >> 24; |
k *= m; |
hash *= m; |
hash ^= k; |
buf += 4; |
len -= 4; |
} |
|
// Handle the last few bytes of the input array. |
switch(len) |
{ |
case 3: |
hash ^= static_cast<unsigned char>(buf[2]) << 16; |
case 2: |
hash ^= static_cast<unsigned char>(buf[1]) << 8; |
case 1: |
hash ^= static_cast<unsigned char>(buf[0]); |
hash *= m; |
}; |
|
// Do a few final mixes of the hash. |
hash ^= hash >> 13; |
hash *= m; |
hash ^= hash >> 15; |
return hash; |
} |
|
// Implementation of FNV hash for 32-bit size_t. |
size_t |
_Fnv_hash_bytes(const void* ptr, size_t len, size_t hash) |
{ |
const char* cptr = static_cast<const char*>(ptr); |
for (; len; --len) |
{ |
hash ^= static_cast<size_t>(*cptr++); |
hash *= static_cast<size_t>(16777619UL); |
} |
return hash; |
} |
|
#elif __SIZEOF_SIZE_T__ == 8 |
|
// Implementation of Murmur hash for 64-bit size_t. |
size_t |
_Hash_bytes(const void* ptr, size_t len, size_t seed) |
{ |
static const size_t mul = (((size_t) 0xc6a4a793UL) << 32UL) |
+ (size_t) 0x5bd1e995UL; |
const char* const buf = static_cast<const char*>(ptr); |
|
// Remove the bytes not divisible by the sizeof(size_t). This |
// allows the main loop to process the data as 64-bit integers. |
const int len_aligned = len & ~0x7; |
const char* const end = buf + len_aligned; |
size_t hash = seed ^ (len * mul); |
for (const char* p = buf; p != end; p += 8) |
{ |
const size_t data = shift_mix(unaligned_load(p) * mul) * mul; |
hash ^= data; |
hash *= mul; |
} |
if ((len & 0x7) != 0) |
{ |
const size_t data = load_bytes(end, len & 0x7); |
hash ^= data; |
hash *= mul; |
} |
hash = shift_mix(hash) * mul; |
hash = shift_mix(hash); |
return hash; |
} |
|
// Implementation of FNV hash for 64-bit size_t. |
size_t |
_Fnv_hash_bytes(const void* ptr, size_t len, size_t hash) |
{ |
const char* cptr = static_cast<const char*>(ptr); |
for (; len; --len) |
{ |
hash ^= static_cast<size_t>(*cptr++); |
hash *= static_cast<size_t>(1099511628211ULL); |
} |
return hash; |
} |
|
#else |
|
// Dummy hash implementation for unusual sizeof(size_t). |
size_t |
_Hash_bytes(const void* ptr, size_t len, size_t seed) |
{ |
size_t hash = seed; |
const char* cptr = reinterpret_cast<const char*>(ptr); |
for (; len; --len) |
hash = (hash * 131) + *cptr++; |
return hash; |
} |
|
size_t |
_Fnv_hash_bytes(const void* ptr, size_t len, size_t seed) |
{ return _Hash_bytes(ptr, len, seed); } |
|
#endif /* __SIZEOF_SIZE_T__ */ |
|
_GLIBCXX_END_NAMESPACE_VERSION |
} // namespace |