1 /**************************************************************************
3 * Copyright 2013-2014 RAD Game Tools and Valve Software
4 * Copyright 2010-2014 Rich Geldreich and Tenacious Software LLC
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:
14 * The above copyright notice and this permission notice shall be included in
15 * all copies or substantial portions of the Software.
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
25 **************************************************************************/
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"
34 #if (defined(__GNUC__) && defined(__i386__)) || defined(__WATCOMC__) || defined(_MSC_VER) || defined(__BORLANDC__) || defined(__TURBOC__)
35 #define get16bits(d) (*((const uint16 *)(d)))
38 #if !defined(get16bits)
39 #define get16bits(d) ((((uint32)(((const uint8 *)(d))[1])) << 8) + (uint32)(((const uint8 *)(d))[0]))
44 struct well_known_hash_t
50 #define DEFINE_WELL_KNOWN_STRING_HASH(x) \
55 well_known_hash_t g_well_known_string_hashes[] =
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")
82 const uint g_num_well_known_string_hashes = VOGL_ARRAY_SIZE(g_well_known_string_hashes);
84 const char *find_well_known_string_hash(const string_hash &hash)
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;
92 uint32 fast_hash(const void *p, int len)
94 const char *data = static_cast<const char *>(p);
96 uint32 hash = len, tmp;
99 if (len <= 0 || data == NULL)
106 for (; len > 0; len--)
108 hash += get16bits(data);
109 tmp = (get16bits(data + 2) << 11) ^ hash;
110 hash = (hash << 16) ^ tmp;
111 data += 2 * sizeof(uint16);
115 /* Handle end cases */
119 hash += get16bits(data);
121 hash ^= data[sizeof(uint16)] << 18;
125 hash += get16bits(data);
135 /* Force "avalanching" of final 127 bits */
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];
151 static const uint64_t poly64 = 0xC96C5795D7870F42ULL;
153 for (size_t b = 0; b < 256; ++b)
156 for (size_t i = 0; i < 8; ++i)
159 r = (r >> 1) ^ poly64;
164 g_crc64_table[b] = r;
170 uint64_t calc_crc64(uint64_t crc, const uint8 *buf, size_t size)
172 if (!g_crc64_table[0])
179 crc = g_crc64_table[*buf++ ^ (crc & 0xFF)] ^ (crc >> 8);
186 uint64_t calc_sum64(const uint8 *buf, size_t size, uint shift_amount)