source: trunk/src/core/hash.cpp @ 2183

Last change on this file since 2183 was 2183, checked in by sam, 7 years ago

build: fix the WTFPL site URL in all code comments.

  • Property svn:keywords set to Id
File size: 3.8 KB
Line 
1//
2// Lol Engine
3//
4// Copyright: (c) 2010-2012 Sam Hocevar <sam@hocevar.net>
5//   This program is free software; you can redistribute it and/or
6//   modify it under the terms of the Do What The Fuck You Want To
7//   Public License, Version 2, as published by Sam Hocevar. See
8//   http://www.wtfpl.net/ for more details.
9//
10
11#if defined HAVE_CONFIG_H
12#   include "config.h"
13#endif
14
15#include "core.h"
16
17namespace lol
18{
19
20/*
21 * Hash implementations
22 */
23
24static class HashData
25{
26public:
27    HashData()
28    {
29        /* Initialise CRC32 table */
30        for (int i = 0; i < 256; i++)
31        {
32            uint32_t tmp = i;
33            for (int j = 8; j--; )
34                tmp = (tmp >> 1) ^ ((tmp & 1) ? 0xedb88320 : 0);
35            crc32_table[i] = tmp;
36        }
37    }
38
39    uint32_t crc32_table[256];
40}
41const data;
42
43/*
44 * Helper hash functions
45 */
46
47static inline uint32_t Hash8(uint8_t x)
48{
49    uint32_t ret = 0xffffffffu;
50    ret = data.crc32_table[(uint8_t)(ret ^ x)] ^ (ret >> 8);
51    return ret ^ 0xffffffffu;
52}
53
54static inline uint32_t Hash16(uint16_t x)
55{
56    uint32_t ret = 0xffffffffu;
57    ret = data.crc32_table[(uint8_t)(ret ^ x)] ^ (ret >> 8);
58    ret = data.crc32_table[(uint8_t)(ret ^ (x >> 8))] ^ (ret >> 8);
59    return ret ^ 0xffffffffu;
60}
61
62static inline uint32_t Hash32(uint32_t x)
63{
64    uint32_t ret = 0xffffffffu;
65    ret = data.crc32_table[(uint8_t)(ret ^ x)] ^ (ret >> 8);
66    ret = data.crc32_table[(uint8_t)(ret ^ (x >> 8))] ^ (ret >> 8);
67    ret = data.crc32_table[(uint8_t)(ret ^ (x >> 16))] ^ (ret >> 8);
68    ret = data.crc32_table[(uint8_t)(ret ^ (x >> 24))] ^ (ret >> 8);
69    return ret ^ 0xffffffffu;
70}
71
72static inline uint32_t Hash64(uint64_t x)
73{
74    uint32_t ret = 0xffffffffu;
75    ret = data.crc32_table[(uint8_t)(ret ^ x)] ^ (ret >> 8);
76    ret = data.crc32_table[(uint8_t)(ret ^ (x >> 8))] ^ (ret >> 8);
77    ret = data.crc32_table[(uint8_t)(ret ^ (x >> 16))] ^ (ret >> 8);
78    ret = data.crc32_table[(uint8_t)(ret ^ (x >> 24))] ^ (ret >> 8);
79    ret = data.crc32_table[(uint8_t)(ret ^ (x >> 32))] ^ (ret >> 8);
80    ret = data.crc32_table[(uint8_t)(ret ^ (x >> 40))] ^ (ret >> 8);
81    ret = data.crc32_table[(uint8_t)(ret ^ (x >> 48))] ^ (ret >> 8);
82    ret = data.crc32_table[(uint8_t)(ret ^ (x >> 56))] ^ (ret >> 8);
83    return ret ^ 0xffffffffu;
84}
85
86/*
87 * Integer hash functions
88 */
89
90uint32_t Hash<int8_t>::operator ()(int8_t x) const
91{
92    return Hash8((uint8_t)x);
93}
94
95uint32_t Hash<uint8_t>::operator ()(uint8_t x) const
96{
97    return Hash8(x);
98}
99
100uint32_t Hash<int16_t>::operator ()(int16_t x) const
101{
102    return Hash16((uint16_t)x);
103}
104
105uint32_t Hash<uint16_t>::operator ()(uint16_t x) const
106{
107    return Hash16(x);
108}
109
110uint32_t Hash<int32_t>::operator ()(int32_t x) const
111{
112    return Hash32((uint32_t)x);
113}
114
115uint32_t Hash<uint32_t>::operator ()(uint32_t x) const
116{
117    return Hash32(x);
118}
119
120uint32_t Hash<int64_t>::operator ()(int64_t x) const
121{
122    return Hash64((uint64_t)x);
123}
124
125uint32_t Hash<uint64_t>::operator ()(uint64_t x) const
126{
127    return Hash64(x);
128}
129
130/*
131 * Floating-point hash functions
132 */
133
134uint32_t Hash<half>::operator ()(half f) const
135{
136    return Hash16(f.bits);
137}
138
139uint32_t Hash<float>::operator ()(float f) const
140{
141    union { float tmp; uint32_t x; } u = { f };
142    return Hash32(u.x);
143}
144
145uint32_t Hash<double>::operator ()(double f) const
146{
147    union { double tmp; uint64_t x; } u = { f };
148    return Hash64(u.x);
149}
150
151/*
152 * String and array hash functions
153 */
154
155static uint32_t HashCharString(char const *s)
156{
157    uint32_t ret = 0xffffffffu, ch;
158
159    while ((ch = (uint8_t)*s++))
160        ret = data.crc32_table[(uint8_t)(ret ^ ch)] ^ (ret >> 8);
161
162    return ret ^ 0xffffffffu;
163}
164
165uint32_t Hash<char const *>::operator ()(char const *s) const
166{
167    return HashCharString(s);
168}
169
170uint32_t Hash<String>::operator ()(String const &s) const
171{
172    return HashCharString(&s[0]);
173}
174
175} /* namespace lol */
176
Note: See TracBrowser for help on using the repository browser.