GHash - code reorganization, performance enhancements, add a few missing utils to...
[blender.git] / source / blender / blenlib / intern / hash_mm2a.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * ***** END GPL LICENSE BLOCK *****
19  *
20  * Copyright (C) 2014 Blender Foundation.
21  *
22  */
23
24 /** \file blender/blenlib/intern/hash_mm2a.c
25  *  \ingroup bli
26  *
27  *  Functions to compute Murmur2A hash key.
28  *
29  * A very fast hash generating int32 result, with few collisions and good repartition.
30  *
31  * See also:
32  *     reference implementation: https://smhasher.googlecode.com/svn-history/r130/trunk/MurmurHash2.cpp
33  *     and http://programmers.stackexchange.com/questions/49550/which-hashing-algorithm-is-best-for-uniqueness-and-speed
34  *
35  * \warning Do not store that hash in files or such, it is not endian-agnostic, so you should only use it
36  *          for temporary data.
37  */
38
39 #include "BLI_hash_mm2a.h"  /* own include */
40
41 /* Helpers. */
42 #define MM2A_M 0x5bd1e995
43
44 #define MM2A_MIX(h, k)           \
45 {                                \
46         (k) *= MM2A_M;               \
47         (k) ^= (k) >> 24;            \
48         (k) *= MM2A_M;               \
49         (h) = ((h) * MM2A_M) ^ (k);  \
50 } (void)0
51
52 #define MM2A_MIX_FINALIZE(h)     \
53 {                                \
54         (h) ^= (h) >> 13;            \
55         (h) *= MM2A_M;               \
56         (h) ^= (h) >> 15;            \
57 } (void)0
58
59 static void mm2a_mix_tail(BLI_HashMurmur2A *mm2, const unsigned char **data, size_t *len)
60 {
61         while (*len && ((*len < 4) || mm2->count)) {
62                 mm2->tail |= (uint32_t)(**data) << (mm2->count * 8);
63
64                 mm2->count++;
65                 (*len)--;
66                 (*data)++;
67
68                 if (mm2->count == 4) {
69                         MM2A_MIX(mm2->hash, mm2->tail);
70                         mm2->tail = 0;
71                         mm2->count = 0;
72                 }
73         }
74 }
75
76 void BLI_hash_mm2a_init(BLI_HashMurmur2A *mm2, uint32_t seed)
77 {
78         mm2->hash  = seed;
79         mm2->tail  = 0;
80         mm2->count = 0;
81         mm2->size  = 0;
82 }
83
84 void BLI_hash_mm2a_add(BLI_HashMurmur2A *mm2, const unsigned char *data, size_t len)
85 {
86         mm2->size += (uint32_t)len;
87
88         mm2a_mix_tail(mm2, &data, &len);
89
90         for (; len >= 4; data += 4, len -= 4) {
91                 uint32_t k = *(const uint32_t *)data;
92
93                 MM2A_MIX(mm2->hash, k);
94         }
95
96         mm2a_mix_tail(mm2, &data, &len);
97 }
98
99 void BLI_hash_mm2a_add_int(BLI_HashMurmur2A *mm2, int data)
100 {
101         BLI_hash_mm2a_add(mm2, (const unsigned char *)&data, sizeof(data));
102 }
103
104 uint32_t BLI_hash_mm2a_end(BLI_HashMurmur2A *mm2)
105 {
106         MM2A_MIX(mm2->hash, mm2->tail);
107         MM2A_MIX(mm2->hash, mm2->size);
108
109         MM2A_MIX_FINALIZE(mm2->hash);
110
111         return mm2->hash;
112 }
113
114 /* Non-incremental version, quicker for small keys. */
115 uint32_t BLI_hash_mm2(const unsigned char *data, size_t len, uint32_t seed)
116 {
117         /* Initialize the hash to a 'random' value */
118         uint32_t h = seed ^ len;
119
120         /* Mix 4 bytes at a time into the hash */
121         for (; len >= 4; data += 4, len -= 4) {
122                 uint32_t k = *(uint32_t *)data;
123
124                 MM2A_MIX(h, k);
125         }
126
127         /* Handle the last few bytes of the input array */
128         switch (len) {
129                 case 3:
130                         h ^= data[2] << 16;
131                         /* fall through */
132                 case 2:
133                         h ^= data[1] << 8;
134                         /* fall through */
135                 case 1:
136                         h ^= data[0];
137                         h *= MM2A_M;
138         };
139
140         /* Do a few final mixes of the hash to ensure the last few bytes are well-incorporated. */
141         MM2A_MIX_FINALIZE(h);
142
143         return h;
144 }
145