cleanup: style
[blender-staging.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 static void mm2a_mix_tail(BLI_HashMurmur2A *mm2, const unsigned char **data, size_t *len)
53 {
54         while (*len && ((*len < 4) || mm2->count)) {
55                 mm2->tail |= (uint32_t)(**data) << (mm2->count * 8);
56
57                 mm2->count++;
58                 (*len)--;
59                 (*data)++;
60
61                 if (mm2->count == 4) {
62                         MM2A_MIX(mm2->hash, mm2->tail);
63                         mm2->tail = 0;
64                         mm2->count = 0;
65                 }
66         }
67 }
68
69 void BLI_hash_mm2a_init(BLI_HashMurmur2A *mm2, uint32_t seed)
70 {
71         mm2->hash  = seed;
72         mm2->tail  = 0;
73         mm2->count = 0;
74         mm2->size  = 0;
75 }
76
77 void BLI_hash_mm2a_add(BLI_HashMurmur2A *mm2, const unsigned char *data, size_t len)
78 {
79         mm2->size += (uint32_t)len;
80
81         mm2a_mix_tail(mm2, &data, &len);
82
83         for (; len >= 4; data += 4, len -= 4) {
84                 uint32_t k = *(const uint32_t *)data;
85
86                 MM2A_MIX(mm2->hash, k);
87         }
88
89         mm2a_mix_tail(mm2, &data, &len);
90 }
91
92 void BLI_hash_mm2a_add_int(BLI_HashMurmur2A *mm2, int data)
93 {
94         BLI_hash_mm2a_add(mm2, (const unsigned char *)&data, sizeof(data));
95 }
96
97 uint32_t BLI_hash_mm2a_end(BLI_HashMurmur2A *mm2)
98 {
99         MM2A_MIX(mm2->hash, mm2->tail);
100         MM2A_MIX(mm2->hash, mm2->size);
101
102         mm2->hash ^= mm2->hash >> 13;
103         mm2->hash *= MM2A_M;
104         mm2->hash ^= mm2->hash >> 15;
105
106         return mm2->hash;
107 }