libstdc++-v3/src/hash_bytes.cc

   1 // Definition of _Hash_bytes. -*- C++ -*-
   2
   3 // Copyright (C) 2010 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 <cstring>
  36 #include <bits/functional_hash.h>
  37
  38 namespace
  39 {
  40   inline std::size_t
  41   unaligned_load(const char* p)
  42   {
  43     std::size_t result;
  44     std::memcpy(&result, p, sizeof(result));
  45     return result;
  46   }
  47
  48 #if __SIZEOF_SIZE_T__ == 8
  49   // Loads n bytes, where 1 <= n < 8.
  50   inline std::size_t
  51   load_bytes(const char* p, int n)
  52   {
  53     size_t result = 0;
  54     --n;
  55     do
  56       result = (result << 8) + static_cast<unsigned char>(p[n]);
  57     while (--n >= 0);
  58     return result;
  59   }
  60
  61   inline std::size_t
  62   shift_mix(std::size_t v)
  63   { return v ^ (v >> 47);}
  64 #endif
  65 }
  66
  67 namespace std
  68 {
  69 #if __SIZEOF_SIZE_T__ == 4
  70
  71   // Implementation of Murmur hash for 32-bit size_t.
  72   size_t
  73   _Hash_bytes(const void* ptr, size_t len, size_t seed)
  74   {
  75     const size_t m = 0x5bd1e995;
  76     size_t hash = seed ^ len;
  77     const char* buf = static_cast<const char*>(ptr);
  78
  79     // Mix 4 bytes at a time into the hash.
  80     while(len >= 4)
  81       {
  82         size_t k = unaligned_load(buf);
  83         k *= m;
  84         k ^= k >> 24;
  85         k *= m;
  86         hash *= m;
  87         hash ^= k;
  88         buf += 4;
  89         len -= 4;
  90       }
  91
  92     // Handle the last few bytes of the input array.
  93     switch(len)
  94       {
  95       case 3:
  96         hash ^= static_cast<unsigned char>(buf[2]) << 16;
  97       case 2:
  98         hash ^= static_cast<unsigned char>(buf[1]) << 8;
  99       case 1:
 100         hash ^= static_cast<unsigned char>(buf[0]);
 101         hash *= m;
 102       };
 103
 104     // Do a few final mixes of the hash.
 105     hash ^= hash >> 13;
 106     hash *= m;
 107     hash ^= hash >> 15;
 108     return hash;
 109   }
 110
 111   // Implementation of FNV hash for 32-bit size_t.
 112   size_t
 113   _Fnv_hash_bytes(const void* ptr, size_t len, size_t hash)
 114   {
 115     const char* cptr = static_cast<const char*>(ptr);
 116     for (; len; --len)
 117       {
 118         hash ^= static_cast<size_t>(*cptr++);
 119         hash *= static_cast<size_t>(16777619UL);
 120       }
 121     return hash;
 122   }
 123
 124 #elif __SIZEOF_SIZE_T__ == 8
 125
 126   // Implementation of Murmur hash for 64-bit size_t.
 127   size_t
 128   _Hash_bytes(const void* ptr, size_t len, size_t seed)
 129   {
 130     static const size_t mul = (0xc6a4a793UL << 32UL) + 0x5bd1e995UL;
 131     const char* const buf = static_cast<const char*>(ptr);
 132
 133     // Remove the bytes not divisible by the sizeof(size_t).  This
 134     // allows the main loop to process the data as 64-bit integers.
 135     const int len_aligned = len & ~0x7;
 136     const char* const end = buf + len_aligned;
 137     size_t hash = seed ^ (len * mul);
 138     for (const char* p = buf; p != end; p += 8)
 139       {
 140         const size_t data = shift_mix(unaligned_load(p) * mul) * mul;
 141         hash ^= data;
 142         hash *= mul;
 143       }
 144     if ((len & 0x7) != 0)
 145       {
 146         const size_t data = load_bytes(end, len & 0x7);
 147         hash ^= data;
 148         hash *= mul;
 149       }
 150     hash = shift_mix(hash) * mul;
 151     hash = shift_mix(hash);
 152     return hash;
 153   }
 154
 155   // Implementation of FNV hash for 64-bit size_t.
 156   size_t
 157   _Fnv_hash_bytes(const void* ptr, size_t len, size_t hash)
 158   {
 159     const char* cptr = static_cast<const char*>(ptr);
 160     for (; len; --len)
 161       {
 162         hash ^= static_cast<size_t>(*cptr++);
 163         hash *= static_cast<size_t>(1099511628211ULL);
 164       }
 165     return hash;
 166   }
 167
 168 #else
 169
 170   // Dummy hash implementation for unusual sizeof(size_t).
 171   size_t
 172   _Hash_bytes(const void* ptr, size_t len, size_t seed)
 173   {
 174     size_t hash = seed;
 175     const char* cptr = reinterpret_cast<const char*>(ptr);
 176     for (; clength; --clength)
 177       hash = (hash * 131) + *cptr++;
 178     return hash;
 179   }
 180
 181   size_t
 182   _Fnv_hash_bytes(const void* ptr, size_t len, size_t seed)
 183   { return _Hash_bytes(ptr, len, seed); }
 184
 185 #endif /* __SIZEOF_SIZE_T__ */
 186 }