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

   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.cpp
  28 // See Paul Hsieh's page at: http://www.azillionmonkeys.com/qed/hash.html
  29 // Also see http://www.concentric.net/~Ttwang/tech/inthash.htm,
  30 // http://burtleburtle.net/bob/hash/integer.html
  31 #include "vogl_core.h"
  32
  33 #undef get16bits
  34 #if (defined(__GNUC__) && defined(__i386__)) || defined(__WATCOMC__) || defined(_MSC_VER) || defined(__BORLANDC__) || defined(__TURBOC__)
  35 #define get16bits(d) (*((const uint16 *)(d)))
  36 #endif
  37
  38 #if !defined(get16bits)
  39 #define get16bits(d) ((((uint32)(((const uint8 *)(d))[1])) << 8) + (uint32)(((const uint8 *)(d))[0]))
  40 #endif
  41
  42 namespace vogl
  43 {
  44     struct well_known_hash_t
  45     {
  46         const char *m_pStr;
  47         string_hash m_hash;
  48     };
  49
  50 #define DEFINE_WELL_KNOWN_STRING_HASH(x) \
  51     {                                    \
  52         x, string_hash(x)                \
  53     }                                    \
  54     ,
  55     well_known_hash_t g_well_known_string_hashes[] =
  56         {
  57             DEFINE_WELL_KNOWN_STRING_HASH("width")
  58             DEFINE_WELL_KNOWN_STRING_HASH("height")
  59             DEFINE_WELL_KNOWN_STRING_HASH("indices")
  60             DEFINE_WELL_KNOWN_STRING_HASH("win_width")
  61             DEFINE_WELL_KNOWN_STRING_HASH("win_height")
  62             DEFINE_WELL_KNOWN_STRING_HASH("active_attributes")
  63             DEFINE_WELL_KNOWN_STRING_HASH("active_uniforms")
  64             DEFINE_WELL_KNOWN_STRING_HASH("active_uniform_blocks")
  65             DEFINE_WELL_KNOWN_STRING_HASH("link_status")
  66             DEFINE_WELL_KNOWN_STRING_HASH("map_access")
  67             DEFINE_WELL_KNOWN_STRING_HASH("map_range")
  68             DEFINE_WELL_KNOWN_STRING_HASH("data")
  69             DEFINE_WELL_KNOWN_STRING_HASH("flushed_ranges")
  70             DEFINE_WELL_KNOWN_STRING_HASH("explicit_flush")
  71             DEFINE_WELL_KNOWN_STRING_HASH("writable_map")
  72             DEFINE_WELL_KNOWN_STRING_HASH("start")
  73             DEFINE_WELL_KNOWN_STRING_HASH("end")
  74             DEFINE_WELL_KNOWN_STRING_HASH("first_vertex_ofs")
  75             DEFINE_WELL_KNOWN_STRING_HASH("viewport_x")
  76             DEFINE_WELL_KNOWN_STRING_HASH("viewport_y")
  77             DEFINE_WELL_KNOWN_STRING_HASH("viewport_width")
  78             DEFINE_WELL_KNOWN_STRING_HASH("viewport_height")
  79             DEFINE_WELL_KNOWN_STRING_HASH("func_id")
  80         };
  81
  82     const uint g_num_well_known_string_hashes = VOGL_ARRAY_SIZE(g_well_known_string_hashes);
  83
  84     const char *find_well_known_string_hash(const string_hash &hash)
  85     {
  86         for (uint i = 0; i < g_num_well_known_string_hashes; i++)
  87             if (g_well_known_string_hashes[i].m_hash == hash)
  88                 return g_well_known_string_hashes[i].m_pStr;
  89         return NULL;
  90     }
  91
  92     uint32 fast_hash(const void *p, int len)
  93     {
  94         const char *data = static_cast<const char *>(p);
  95
  96         uint32 hash = len, tmp;
  97         int rem;
  98
  99         if (len <= 0 || data == NULL)
 100             return 0;
 101
 102         rem = len & 3;
 103         len >>= 2;
 104
 105         /* Main loop */
 106         for (; len > 0; len--)
 107         {
 108             hash += get16bits(data);
 109             tmp = (get16bits(data + 2) << 11) ^ hash;
 110             hash = (hash << 16) ^ tmp;
 111             data += 2 * sizeof(uint16);
 112             hash += hash >> 11;
 113         }
 114
 115         /* Handle end cases */
 116         switch (rem)
 117         {
 118             case 3:
 119                 hash += get16bits(data);
 120                 hash ^= hash << 16;
 121                 hash ^= data[sizeof(uint16)] << 18;
 122                 hash += hash >> 11;
 123                 break;
 124             case 2:
 125                 hash += get16bits(data);
 126                 hash ^= hash << 11;
 127                 hash += hash >> 17;
 128                 break;
 129             case 1:
 130                 hash += *data;
 131                 hash ^= hash << 10;
 132                 hash += hash >> 1;
 133         }
 134
 135         /* Force "avalanching" of final 127 bits */
 136         hash ^= hash << 3;
 137         hash += hash >> 5;
 138         hash ^= hash << 4;
 139         hash += hash >> 17;
 140         hash ^= hash << 25;
 141         hash += hash >> 6;
 142
 143         return hash;
 144     }
 145
 146     // Public domain code originally from http://svn.r-project.org/R/trunk/src/extra/xz/check/crc64_small.c
 147     uint64_t g_crc64_table[256];
 148
 149     void crc64_init()
 150     {
 151         static const uint64_t poly64 = 0xC96C5795D7870F42ULL;
 152
 153         for (size_t b = 0; b < 256; ++b)
 154         {
 155             uint64_t r = b;
 156             for (size_t i = 0; i < 8; ++i)
 157             {
 158                 if (r & 1)
 159                     r = (r >> 1) ^ poly64;
 160                 else
 161                     r >>= 1;
 162             }
 163
 164             g_crc64_table[b] = r;
 165         }
 166
 167         return;
 168     }
 169
 170     uint64_t calc_crc64(uint64_t crc, const uint8 *buf, size_t size)
 171     {
 172         if (!g_crc64_table[0])
 173             crc64_init();
 174
 175         crc = ~crc;
 176
 177         while (size != 0)
 178         {
 179             crc = g_crc64_table[*buf++ ^ (crc & 0xFF)] ^ (crc >> 8);
 180             --size;
 181         }
 182
 183         return ~crc;
 184     }
 185
 186     uint64_t calc_sum64(const uint8 *buf, size_t size, uint shift_amount)
 187     {
 188         uint64_t sum = 0;
 189
 190         while (size != 0)
 191         {
 192             uint c = *buf++;
 193             c >>= shift_amount;
 194             sum += c;
 195             --size;
 196         }
 197
 198         return sum;
 199     }
 200
 201 } // namespace vogl