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