1 /*
2 ** Zabbix
3 ** Copyright (C) 2001-2021 Zabbix SIA
4 **
5 ** This program is free software; you can redistribute it and/or modify
6 ** it under the terms of the GNU General Public License as published by
7 ** the Free Software Foundation; either version 2 of the License, or
8 ** (at your option) any later version.
9 **
10 ** This program is distributed in the hope that it will be useful,
11 ** but WITHOUT ANY WARRANTY; without even the implied warranty of
12 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 ** GNU General Public License for more details.
14 **
15 ** You should have received a copy of the GNU General Public License
16 ** along with this program; if not, write to the Free Software
17 ** Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
18 **/
19
20 #include "common.h"
21
22 #include "zbxalgo.h"
23
24 typedef unsigned char uchar;
25
26 /*
27 * Bob Jenkins hash function (see http://burtleburtle.net/bob/hash/evahash.html)
28 */
zbx_hash_lookup2(const void * data,size_t len,zbx_hash_t seed)29 zbx_hash_t zbx_hash_lookup2(const void *data, size_t len, zbx_hash_t seed)
30 {
31 const uchar *p = (const uchar *)data;
32
33 zbx_hash_t a, b, c;
34
35 #define mix(a, b, c) \
36 { \
37 a = a - b; a = a - c; a = a ^ (c >> 13); \
38 b = b - c; b = b - a; b = b ^ (a << 8); \
39 c = c - a; c = c - b; c = c ^ (b >> 13); \
40 a = a - b; a = a - c; a = a ^ (c >> 12); \
41 b = b - c; b = b - a; b = b ^ (a << 16); \
42 c = c - a; c = c - b; c = c ^ (b >> 5); \
43 a = a - b; a = a - c; a = a ^ (c >> 3); \
44 b = b - c; b = b - a; b = b ^ (a << 10); \
45 c = c - a; c = c - b; c = c ^ (b >> 15); \
46 }
47
48 a = b = 0x9e3779b9u;
49 c = seed;
50
51 while (len >= 12)
52 {
53 a = a + (p[0] + ((zbx_hash_t)p[1] << 8) + ((zbx_hash_t)p[2] << 16) + ((zbx_hash_t)p[3] << 24));
54 b = b + (p[4] + ((zbx_hash_t)p[5] << 8) + ((zbx_hash_t)p[6] << 16) + ((zbx_hash_t)p[7] << 24));
55 c = c + (p[8] + ((zbx_hash_t)p[9] << 8) + ((zbx_hash_t)p[10] << 16) + ((zbx_hash_t)p[11] << 24));
56
57 mix(a, b, c);
58
59 p += 12;
60 len -= 12;
61 }
62
63 c = c + (zbx_hash_t)len;
64
65 switch (len)
66 {
67 case 11: c = c + ((zbx_hash_t)p[10] << 24);
68 ZBX_FALLTHROUGH;
69 case 10: c = c + ((zbx_hash_t)p[9] << 16);
70 ZBX_FALLTHROUGH;
71 case 9: c = c + ((zbx_hash_t)p[8] << 8);
72 ZBX_FALLTHROUGH;
73 case 8: b = b + ((zbx_hash_t)p[7] << 24);
74 ZBX_FALLTHROUGH;
75 case 7: b = b + ((zbx_hash_t)p[6] << 16);
76 ZBX_FALLTHROUGH;
77 case 6: b = b + ((zbx_hash_t)p[5] << 8);
78 ZBX_FALLTHROUGH;
79 case 5: b = b + p[4];
80 ZBX_FALLTHROUGH;
81 case 4: a = a + ((zbx_hash_t)p[3] << 24);
82 ZBX_FALLTHROUGH;
83 case 3: a = a + ((zbx_hash_t)p[2] << 16);
84 ZBX_FALLTHROUGH;
85 case 2: a = a + ((zbx_hash_t)p[1] << 8);
86 ZBX_FALLTHROUGH;
87 case 1: a = a + p[0];
88 }
89
90 mix(a, b, c);
91
92 return c;
93 }
94
95 /*
96 * modified FNV hash function (see http://www.isthe.com/chongo/tech/comp/fnv/)
97 */
zbx_hash_modfnv(const void * data,size_t len,zbx_hash_t seed)98 zbx_hash_t zbx_hash_modfnv(const void *data, size_t len, zbx_hash_t seed)
99 {
100 const uchar *p = (const uchar *)data;
101
102 zbx_hash_t hash;
103
104 hash = 2166136261u ^ seed;
105
106 while (len-- >= 1)
107 {
108 hash = (hash ^ *(p++)) * 16777619u;
109 }
110
111 hash += hash << 13;
112 hash ^= hash >> 7;
113 hash += hash << 3;
114 hash ^= hash >> 17;
115 hash += hash << 5;
116
117 return hash;
118 }
119
120 /*
121 * Murmur (see http://sites.google.com/site/murmurhash/)
122 */
zbx_hash_murmur2(const void * data,size_t len,zbx_hash_t seed)123 zbx_hash_t zbx_hash_murmur2(const void *data, size_t len, zbx_hash_t seed)
124 {
125 const uchar *p = (const uchar *)data;
126
127 zbx_hash_t hash;
128
129 const zbx_hash_t m = 0x5bd1e995u;
130 const zbx_hash_t r = 24;
131
132 hash = seed ^ (zbx_hash_t)len;
133
134 while (len >= 4)
135 {
136 zbx_hash_t k;
137
138 k = p[0];
139 k |= p[1] << 8;
140 k |= p[2] << 16;
141 k |= p[3] << 24;
142
143 k *= m;
144 k ^= k >> r;
145 k *= m;
146
147 hash *= m;
148 hash ^= k;
149
150 p += 4;
151 len -= 4;
152 }
153
154 switch (len)
155 {
156 case 3: hash ^= p[2] << 16;
157 ZBX_FALLTHROUGH;
158 case 2: hash ^= p[1] << 8;
159 ZBX_FALLTHROUGH;
160 case 1: hash ^= p[0];
161 hash *= m;
162 }
163
164 hash ^= hash >> 13;
165 hash *= m;
166 hash ^= hash >> 15;
167
168 return hash;
169 }
170
171 /*
172 * sdbm (see http://www.cse.yorku.ca/~oz/hash.html)
173 */
zbx_hash_sdbm(const void * data,size_t len,zbx_hash_t seed)174 zbx_hash_t zbx_hash_sdbm(const void *data, size_t len, zbx_hash_t seed)
175 {
176 const uchar *p = (const uchar *)data;
177
178 zbx_hash_t hash = seed;
179
180 #if 1
181
182 while (len-- >= 1)
183 {
184 /* hash = *(p++) + hash * 65599; */
185
186 hash = *(p++) + (hash << 6) + (hash << 16) - hash;
187 }
188
189 #else /* Duff's device */
190
191 #define HASH_STEP len--; \
192 hash = *(p++) + (hash << 6) + (hash << 16) - hash
193
194 switch (len & 7)
195 {
196 do
197 {
198 HASH_STEP;
199 case 7: HASH_STEP;
200 case 6: HASH_STEP;
201 case 5: HASH_STEP;
202 case 4: HASH_STEP;
203 case 3: HASH_STEP;
204 case 2: HASH_STEP;
205 case 1: HASH_STEP;
206 case 0: ;
207 }
208 while (len >= 8);
209 }
210
211 #endif
212
213 return hash;
214 }
215
216 /*
217 * djb2 (see http://www.cse.yorku.ca/~oz/hash.html)
218 */
zbx_hash_djb2(const void * data,size_t len,zbx_hash_t seed)219 zbx_hash_t zbx_hash_djb2(const void *data, size_t len, zbx_hash_t seed)
220 {
221 const uchar *p = (const uchar *)data;
222
223 zbx_hash_t hash;
224
225 hash = 5381u ^ seed;
226
227 while (len-- >= 1)
228 {
229 /* hash = hash * 33 + *(p++); */
230
231 hash = ((hash << 5) + hash) + *(p++);
232 }
233
234 return hash;
235 }
236
237 /*
238 * see http://xoshiro.di.unimi.it/splitmix64.c
239 */
zbx_hash_splittable64(const void * data)240 zbx_hash_t zbx_hash_splittable64(const void *data)
241 {
242 zbx_uint64_t value = *(const zbx_uint64_t *)data;
243
244 value ^= value >> 30;
245 value *= __UINT64_C(0xbf58476d1ce4e5b9);
246 value ^= value >> 27;
247 value *= __UINT64_C(0x94d049bb133111eb);
248 value ^= value >> 31;
249
250 return (zbx_hash_t)value ^ (value >> 32);
251 }
252
253 /* default hash functions */
254
zbx_default_ptr_hash_func(const void * data)255 zbx_hash_t zbx_default_ptr_hash_func(const void *data)
256 {
257 return ZBX_DEFAULT_PTR_HASH_ALGO(data, ZBX_PTR_SIZE, ZBX_DEFAULT_HASH_SEED);
258 }
259
zbx_default_string_hash_func(const void * data)260 zbx_hash_t zbx_default_string_hash_func(const void *data)
261 {
262 return ZBX_DEFAULT_STRING_HASH_ALGO(data, strlen((const char *)data), ZBX_DEFAULT_HASH_SEED);
263 }
264
zbx_default_uint64_pair_hash_func(const void * data)265 zbx_hash_t zbx_default_uint64_pair_hash_func(const void *data)
266 {
267 const zbx_uint64_pair_t *pair = (const zbx_uint64_pair_t *)data;
268
269 zbx_hash_t hash;
270
271 hash = ZBX_DEFAULT_UINT64_HASH_FUNC(&pair->first);
272 hash = ZBX_DEFAULT_UINT64_HASH_ALGO(&pair->second, sizeof(pair->second), hash);
273
274 return hash;
275 }
276
277 /* default comparison functions */
278
zbx_default_int_compare_func(const void * d1,const void * d2)279 int zbx_default_int_compare_func(const void *d1, const void *d2)
280 {
281 const int *i1 = (const int *)d1;
282 const int *i2 = (const int *)d2;
283
284 ZBX_RETURN_IF_NOT_EQUAL(*i1, *i2);
285
286 return 0;
287 }
288
zbx_default_uint64_compare_func(const void * d1,const void * d2)289 int zbx_default_uint64_compare_func(const void *d1, const void *d2)
290 {
291 const zbx_uint64_t *i1 = (const zbx_uint64_t *)d1;
292 const zbx_uint64_t *i2 = (const zbx_uint64_t *)d2;
293
294 ZBX_RETURN_IF_NOT_EQUAL(*i1, *i2);
295
296 return 0;
297 }
298
zbx_default_uint64_ptr_compare_func(const void * d1,const void * d2)299 int zbx_default_uint64_ptr_compare_func(const void *d1, const void *d2)
300 {
301 const zbx_uint64_t *p1 = *(const zbx_uint64_t **)d1;
302 const zbx_uint64_t *p2 = *(const zbx_uint64_t **)d2;
303
304 return zbx_default_uint64_compare_func(p1, p2);
305 }
306
zbx_default_str_compare_func(const void * d1,const void * d2)307 int zbx_default_str_compare_func(const void *d1, const void *d2)
308 {
309 return strcmp(*(const char **)d1, *(const char **)d2);
310 }
311
zbx_default_ptr_compare_func(const void * d1,const void * d2)312 int zbx_default_ptr_compare_func(const void *d1, const void *d2)
313 {
314 const void *p1 = *(const void **)d1;
315 const void *p2 = *(const void **)d2;
316
317 ZBX_RETURN_IF_NOT_EQUAL(p1, p2);
318
319 return 0;
320 }
321
zbx_default_uint64_pair_compare_func(const void * d1,const void * d2)322 int zbx_default_uint64_pair_compare_func(const void *d1, const void *d2)
323 {
324 const zbx_uint64_pair_t *p1 = (const zbx_uint64_pair_t *)d1;
325 const zbx_uint64_pair_t *p2 = (const zbx_uint64_pair_t *)d2;
326
327 ZBX_RETURN_IF_NOT_EQUAL(p1->first, p2->first);
328 ZBX_RETURN_IF_NOT_EQUAL(p1->second, p2->second);
329
330 return 0;
331 }
332
333 /* default memory management functions */
334
zbx_default_mem_malloc_func(void * old,size_t size)335 void *zbx_default_mem_malloc_func(void *old, size_t size)
336 {
337 return zbx_malloc(old, size);
338 }
339
zbx_default_mem_realloc_func(void * old,size_t size)340 void *zbx_default_mem_realloc_func(void *old, size_t size)
341 {
342 return zbx_realloc(old, size);
343 }
344
zbx_default_mem_free_func(void * ptr)345 void zbx_default_mem_free_func(void *ptr)
346 {
347 zbx_free(ptr);
348 }
349
350 /* numeric functions */
351
is_prime(int n)352 int is_prime(int n)
353 {
354 int i;
355
356 if (n <= 1)
357 return 0;
358 if (n == 2)
359 return 1;
360 if (n % 2 == 0)
361 return 0;
362
363 for (i = 3; i * i <= n; i+=2)
364 if (n % i == 0)
365 return 0;
366
367 return 1;
368 }
369
next_prime(int n)370 int next_prime(int n)
371 {
372 while (!is_prime(n))
373 n++;
374
375 return n;
376 }
377
378 /******************************************************************************
379 * *
380 * Function: zbx_isqrt32 *
381 * *
382 * Purpose: calculate integer part of square root of a 32 bit integer value *
383 * *
384 * Parameters: value - [IN] the value to calculate square root for *
385 * *
386 * Return value: the integer part of square root *
387 * *
388 * Comments: Uses basic digit by digit square root calculation algorithm with *
389 * binary base. *
390 * *
391 ******************************************************************************/
zbx_isqrt32(unsigned int value)392 unsigned int zbx_isqrt32(unsigned int value)
393 {
394 unsigned int i, remainder = 0, result = 0, p;
395
396 for (i = 0; i < 16; i++)
397 {
398 result <<= 1;
399 remainder = (remainder << 2) + (value >> 30);
400 value <<= 2;
401
402 p = (result << 1) | 1;
403 if (p <= remainder)
404 {
405 remainder -= p;
406 result |= 1;
407 }
408 }
409
410 return result;
411 }
412