git.cworth.org Git - vogl/blob - src/voglcore/vogl_hash.h

   1 /**************************************************************************
   2  *
   3  * Copyright 2013-2014 RAD Game Tools and Valve Software
   4  * Copyright 2010-2014 Rich Geldreich and Tenacious Software LLC
   5  * All Rights Reserved.
   6  *
   7  * Permission is hereby granted, free of charge, to any person obtaining a copy
   8  * of this software and associated documentation files (the "Software"), to deal
   9  * in the Software without restriction, including without limitation the rights
  10  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  11  * copies of the Software, and to permit persons to whom the Software is
  12  * furnished to do so, subject to the following conditions:
  13  *
  14  * The above copyright notice and this permission notice shall be included in
  15  * all copies or substantial portions of the Software.
  16  *
  17  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  18  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  19  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  20  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  21  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  22  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  23  * THE SOFTWARE.
  24  *
  25  **************************************************************************/
  26
  27 // File: vogl_hash.h
  28 #pragma once
  29
  30 #include "vogl_core.h"
  31
  32 namespace vogl
  33 {
  34     extern uint64_t g_crc64_table[256];
  35
  36     const uint64_t CRC64_INIT = 0;
  37     void crc64_init();
  38     uint64_t calc_crc64(uint64_t crc, const uint8 *buf, size_t size);
  39
  40     uint64_t calc_sum64(const uint8 *buf, size_t size, uint shift_amount = 0);
  41
  42     uint32 fast_hash(const void *p, int len);
  43
  44     template <typename T>
  45     inline uint32 fast_hash_obj(const T &obj)
  46     {
  47         return fast_hash(&obj, sizeof(obj));
  48     }
  49
  50     // 4-byte integer hash, full avalanche
  51     inline uint32 bitmix32c(uint32 a)
  52     {
  53         a = (a + 0x7ed55d16) + (a << 12);
  54         a = (a ^ 0xc761c23c) ^ (a >> 19);
  55         a = (a + 0x165667b1) + (a << 5);
  56         a = (a + 0xd3a2646c) ^ (a << 9);
  57         a = (a + 0xfd7046c5) + (a << 3);
  58         a = (a ^ 0xb55a4f09) ^ (a >> 16);
  59         return a;
  60     }
  61
  62     // 4-byte integer hash, full avalanche, no constants
  63     inline uint32 bitmix32(uint32 a)
  64     {
  65         a -= (a << 6);
  66         a ^= (a >> 17);
  67         a -= (a << 9);
  68         a ^= (a << 4);
  69         a -= (a << 3);
  70         a ^= (a << 10);
  71         a ^= (a >> 15);
  72         return a;
  73     }
  74
  75     // Derived from: http://www.altdevblogaday.com/2011/10/27/quasi-compile-time-string-hashing/
  76     // Also see: http://www.isthe.com/chongo/tech/comp/fnv/#xor-fold
  77     class string_hash
  78     {
  79     public:
  80         inline string_hash()
  81             : m_hash(0)
  82         {
  83         }
  84         inline string_hash(uint hash)
  85             : m_hash(hash)
  86         {
  87         }
  88         inline string_hash(const string_hash &other)
  89             : m_hash(other.m_hash)
  90         {
  91         }
  92         inline string_hash &operator=(const string_hash &rhs)
  93         {
  94             m_hash = rhs.m_hash;
  95             return *this;
  96         }
  97
  98         template <uint N>
  99         inline string_hash(const char (&str)[N])
 100             : m_hash(fnv_hash<N, N>::hash(str))
 101         {
 102         }
 103
 104         template <uint N>
 105         inline bool operator==(const char (&str)[N]) const
 106         {
 107             return m_hash == fnv_hash<N, N>::hash(str);
 108         }
 109
 110         template <uint N>
 111         inline bool operator!=(const char (&str)[N]) const
 112         {
 113             return m_hash != fnv_hash<N, N>::hash(str);
 114         }
 115
 116         inline bool operator==(const string_hash &other) const
 117         {
 118             return m_hash == other.m_hash;
 119         }
 120         inline bool operator!=(const string_hash &other) const
 121         {
 122             return m_hash != other.m_hash;
 123         }
 124
 125         struct const_char_ptr
 126         {
 127             inline const_char_ptr(const char *pStr)
 128                 : m_pStr(pStr)
 129             {
 130             }
 131             const char *m_pStr;
 132         };
 133         inline string_hash(const const_char_ptr &str)
 134         {
 135             init();
 136             finalize(str.m_pStr);
 137         }
 138         inline string_hash(const const_char_ptr &str, size_t len)
 139         {
 140             init();
 141             finalize(str.m_pStr, len);
 142         }
 143
 144         inline string_hash(char *pStr)
 145         {
 146             init();
 147             finalize((const char *)pStr);
 148         }
 149         inline string_hash(char *pStr, size_t len)
 150         {
 151             init();
 152             finalize((const char *)pStr, len);
 153         }
 154
 155         inline uint get_hash() const
 156         {
 157             return m_hash;
 158         }
 159         inline void set_hash(uint hash)
 160         {
 161             m_hash = hash;
 162         }
 163
 164         inline operator size_t() const
 165         {
 166             return get_hash();
 167         }
 168
 169         inline uint set(const char *pStr, size_t len)
 170         {
 171             init();
 172             return finalize(pStr, len);
 173         }
 174
 175         inline uint set(const char *pStr)
 176         {
 177             init();
 178             return finalize(pStr);
 179         }
 180
 181         inline void init()
 182         {
 183             m_hash = 2166136261U;
 184         }
 185
 186         inline uint finalize(const char *pStr, size_t len)
 187         {
 188             update(pStr, len);
 189             m_hash *= 16777619u;
 190             return m_hash;
 191         }
 192
 193         inline uint finalize(const char *pStr)
 194         {
 195             return finalize(pStr, strlen(pStr));
 196         }
 197
 198         inline uint update(const char *pStr, size_t len)
 199         {
 200             uint hash = m_hash;
 201             for (const char *pEnd = pStr + len; pStr != pEnd; ++pStr)
 202             {
 203                 hash ^= *pStr;
 204                 hash *= 16777619u;
 205             }
 206             m_hash = hash;
 207             return hash;
 208         }
 209
 210         inline uint update(const char *pStr)
 211         {
 212             return update(pStr, strlen(pStr));
 213         }
 214
 215     private:
 216         uint m_hash;
 217
 218         template <uint N, uint I>
 219         struct fnv_hash
 220         {
 221             inline static uint hash(const char (&str)[N])
 222             {
 223                 return (fnv_hash<N, I - 1>::hash(str) ^ str[I - 1]) * 16777619U;
 224             }
 225         };
 226
 227         template <uint N>
 228         struct fnv_hash<N, 1>
 229         {
 230             inline static uint hash(const char (&str)[N])
 231             {
 232                 return (2166136261U ^ str[0]) * 16777619U;
 233             }
 234         };
 235     };
 236
 237     const char *find_well_known_string_hash(const string_hash &hash);
 238
 239 } // namespace vogl