Embedded Template Library 1.0
murmur3.h
Go to the documentation of this file.
1
2
3/******************************************************************************
4The MIT License(MIT)
5
6Embedded Template Library.
7https://github.com/ETLCPP/etl
8https://www.etlcpp.com
9
10Copyright(c) 2014 John Wellbelove
11
12Permission is hereby granted, free of charge, to any person obtaining a copy
13of this software and associated documentation files(the "Software"), to deal
14in the Software without restriction, including without limitation the rights
15to use, copy, modify, merge, publish, distribute, sublicense, and / or sell
16copies of the Software, and to permit persons to whom the Software is
17furnished to do so, subject to the following conditions :
18
19The above copyright notice and this permission notice shall be included in all
20copies or substantial portions of the Software.
21
22THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
23IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
24FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.IN NO EVENT SHALL THE
25AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
26LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
27OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
28SOFTWARE.
29******************************************************************************/
30
31#ifndef ETL_MURMUR3_INCLUDED
32#define ETL_MURMUR3_INCLUDED
33
34#include "platform.h"
35#include "ihash.h"
36#include "binary.h"
37#include "error_handler.h"
38
39#include <stdint.h>
40
41#if defined(ETL_COMPILER_KEIL)
42#pragma diag_suppress 1300
43#endif
44
47
48namespace etl
49{
50 //***************************************************************************
54 //***************************************************************************
55 template <typename THash>
56 class murmur3
57 {
58 public:
59
60#if ETL_NOT_USING_64BIT_TYPES
61 ETL_STATIC_ASSERT((etl::is_same<THash, uint32_t>::value), "Only 32 bit types supported");
62#else
63 ETL_STATIC_ASSERT((etl::is_same<THash, uint32_t>::value || etl::is_same<THash, uint64_t>::value), "Only 32 & 64 bit types supported");
64#endif
65
66 typedef THash value_type;
67
68 //*************************************************************************
71 //*************************************************************************
72 murmur3(value_type seed_ = 0)
73 : seed(seed_)
74 {
75 reset();
76 }
77
78 //*************************************************************************
83 //*************************************************************************
84 template<typename TIterator>
85 murmur3(TIterator begin, const TIterator end, value_type seed_ = 0)
86 : seed(seed_)
87 {
88 ETL_STATIC_ASSERT(sizeof(typename etl::iterator_traits<TIterator>::value_type) == 1, "Incompatible type");
89
90 reset();
91 while (begin != end)
92 {
93 block |= (*begin) << (block_fill_count * 8U);
94 ++begin;
95
96 if (++block_fill_count == FULL_BLOCK)
97 {
98 add_block();
99 block_fill_count = 0;
100 block = 0;
101 }
102
103 ++char_count;
104 }
105 }
106
107 //*************************************************************************
109 //*************************************************************************
110 void reset()
111 {
112 hash = seed;
113 char_count = 0;
114 block = 0;
115 block_fill_count = 0;
116 is_finalised = false;
117 }
118
119 //*************************************************************************
123 //*************************************************************************
124 template<typename TIterator>
125 void add(TIterator begin, const TIterator end)
126 {
127 ETL_STATIC_ASSERT(sizeof(typename etl::iterator_traits<TIterator>::value_type) == 1, "Incompatible type");
128 ETL_ASSERT(!is_finalised, ETL_ERROR(hash_finalised));
129
130 while (begin != end)
131 {
132 block |= (*begin) << (block_fill_count * 8U);
133 ++begin;
134
135 if (++block_fill_count == FULL_BLOCK)
136 {
137 add_block();
138 block_fill_count = 0;
139 block = 0;
140 }
141
142 ++char_count;
143 }
144 }
145
146 //*************************************************************************
150 //*************************************************************************
151 void add(uint8_t value_)
152 {
153 // We can't add to a finalised hash!
154 ETL_ASSERT(!is_finalised, ETL_ERROR(hash_finalised));
155
156 block |= value_ << (block_fill_count * 8U);
157
158 if (++block_fill_count == FULL_BLOCK)
159 {
160 add_block();
161 block_fill_count = 0;
162 block = 0;
163 }
164
165 ++char_count;
166 }
167
168 //*************************************************************************
170 //*************************************************************************
171 value_type value()
172 {
173 finalise();
174 return hash;
175 }
176
177 //*************************************************************************
179 //*************************************************************************
180 operator value_type ()
181 {
182 return value();
183 }
184
185 private:
186
187 //*************************************************************************
189 //*************************************************************************
190 void add_block()
191 {
192 block *= CONSTANT1;
193 block = rotate_left(block, SHIFT1);
194 block *= CONSTANT2;
195
196 hash ^= block;
197 hash = rotate_left(hash, SHIFT2);
198 hash = (hash * MULTIPLY) + ADD;
199 }
200
201 //*************************************************************************
203 //*************************************************************************
204 void finalise()
205 {
206 if (!is_finalised)
207 {
208 block *= CONSTANT1;
209 block = rotate_left(block, SHIFT1);
210 block *= CONSTANT2;
211
212 hash ^= block;
213 hash ^= char_count;
214 hash ^= (hash >> 16U);
215 hash *= 0x85EBCA6BUL;
216 hash ^= (hash >> 13U);
217 hash *= 0xC2B2AE35UL;
218 hash ^= (hash >> 16U);
219
220 is_finalised = true;
221 }
222 }
223
224 bool is_finalised;
225 uint8_t block_fill_count;
226 size_t char_count;
227 value_type block;
228 value_type hash;
229 value_type seed;
230
231 static ETL_CONSTANT uint8_t FULL_BLOCK = 4U;
232 static ETL_CONSTANT value_type CONSTANT1 = 0xCC9E2D51UL;
233 static ETL_CONSTANT value_type CONSTANT2 = 0x1B873593UL;
234 static ETL_CONSTANT value_type SHIFT1 = 15;
235 static ETL_CONSTANT value_type SHIFT2 = 13;
236 static ETL_CONSTANT value_type MULTIPLY = 5;
237 static ETL_CONSTANT value_type ADD = 0xE6546B64UL;
238 };
239}
240
241#endif
ETL_CONSTEXPR14 T rotate_left(T value)
Definition: binary.h:116
#define ETL_ASSERT(b, e)
Definition: error_handler.h:316
void reset()
Resets the hash to the initial state.
Definition: murmur3.h:110
murmur3(value_type seed_=0)
Definition: murmur3.h:72
murmur3(TIterator begin, const TIterator end, value_type seed_=0)
Definition: murmur3.h:85
void add(TIterator begin, const TIterator end)
Definition: murmur3.h:125
value_type value()
Gets the hash value.
Definition: murmur3.h:171
void add(uint8_t value_)
Definition: murmur3.h:151
Definition: murmur3.h:57
is_same
Definition: type_traits_generator.h:1041
Definition: ihash.h:64
bitset_ext
Definition: absolute.h:38
ETL_CONSTEXPR TContainer::iterator begin(TContainer &container)
Definition: iterator.h:931
ETL_CONSTEXPR TContainer::iterator end(TContainer &container)
Definition: iterator.h:961