Cleanup: comments (long lines) in blenlib
[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
19  * \ingroup bli
20  *
21  *  Functions to compute Murmur2A hash key.
22  *
23  * A very fast hash generating int32 result, with few collisions and good repartition.
24  *
25  * See also:
26  * reference implementation:
27  * - https://smhasher.googlecode.com/svn-history/r130/trunk/MurmurHash2.cpp
28  * - http://programmers.stackexchange.com/questions/49550/which-hashing-algorithm-is-best-for-uniqueness-and-speed
29  *
30  * \warning Do not store that hash in files or such, it is not endian-agnostic,
31  * so you should only use it for temporary data.
32  */
33
34 #include "BLI_compiler_attrs.h"
35
36 #include "BLI_hash_mm2a.h" /* own include */
37
38 /* Helpers. */
39 #define MM2A_M 0x5bd1e995
40
41 #define MM2A_MIX(h, k) \
42   { \
43     (k) *= MM2A_M; \
44     (k) ^= (k) >> 24; \
45     (k) *= MM2A_M; \
46     (h) = ((h)*MM2A_M) ^ (k); \
47   } \
48   (void)0
49
50 #define MM2A_MIX_FINALIZE(h) \
51   { \
52     (h) ^= (h) >> 13; \
53     (h) *= MM2A_M; \
54     (h) ^= (h) >> 15; \
55   } \
56   (void)0
57
58 static void mm2a_mix_tail(BLI_HashMurmur2A *mm2, const unsigned char **data, size_t *len)
59 {
60   while (*len && ((*len < 4) || mm2->count)) {
61     mm2->tail |= (uint32_t)(**data) << (mm2->count * 8);
62
63     mm2->count++;
64     (*len)--;
65     (*data)++;
66
67     if (mm2->count == 4) {
68       MM2A_MIX(mm2->hash, mm2->tail);
69       mm2->tail = 0;
70       mm2->count = 0;
71     }
72   }
73 }
74
75 void BLI_hash_mm2a_init(BLI_HashMurmur2A *mm2, uint32_t seed)
76 {
77   mm2->hash = seed;
78   mm2->tail = 0;
79   mm2->count = 0;
80   mm2->size = 0;
81 }
82
83 void BLI_hash_mm2a_add(BLI_HashMurmur2A *mm2, const unsigned char *data, size_t len)
84 {
85   mm2->size += (uint32_t)len;
86
87   mm2a_mix_tail(mm2, &data, &len);
88
89   for (; len >= 4; data += 4, len -= 4) {
90     uint32_t k = *(const uint32_t *)data;
91
92     MM2A_MIX(mm2->hash, k);
93   }
94
95   mm2a_mix_tail(mm2, &data, &len);
96 }
97
98 void BLI_hash_mm2a_add_int(BLI_HashMurmur2A *mm2, int data)
99 {
100   BLI_hash_mm2a_add(mm2, (const unsigned char *)&data, sizeof(data));
101 }
102
103 uint32_t BLI_hash_mm2a_end(BLI_HashMurmur2A *mm2)
104 {
105   MM2A_MIX(mm2->hash, mm2->tail);
106   MM2A_MIX(mm2->hash, mm2->size);
107
108   MM2A_MIX_FINALIZE(mm2->hash);
109
110   return mm2->hash;
111 }
112
113 /* Non-incremental version, quicker for small keys. */
114 uint32_t BLI_hash_mm2(const unsigned char *data, size_t len, uint32_t seed)
115 {
116   /* Initialize the hash to a 'random' value */
117   uint32_t h = seed ^ len;
118
119   /* Mix 4 bytes at a time into the hash */
120   for (; len >= 4; data += 4, len -= 4) {
121     uint32_t k = *(uint32_t *)data;
122
123     MM2A_MIX(h, k);
124   }
125
126   /* Handle the last few bytes of the input array */
127   switch (len) {
128     case 3:
129       h ^= data[2] << 16;
130       ATTR_FALLTHROUGH;
131     case 2:
132       h ^= data[1] << 8;
133       ATTR_FALLTHROUGH;
134     case 1:
135       h ^= data[0];
136       h *= MM2A_M;
137   }
138
139   /* Do a few final mixes of the hash to ensure the last few bytes are well-incorporated. */
140   MM2A_MIX_FINALIZE(h);
141
142   return h;
143 }