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 + len;
64
65 switch (len)
66 {
67 case 11: c = c + ((zbx_hash_t)p[10] << 24);
68 case 10: c = c + ((zbx_hash_t)p[9] << 16);
69 case 9: c = c + ((zbx_hash_t)p[8] << 8);
70 case 8: b = b + ((zbx_hash_t)p[7] << 24);
71 case 7: b = b + ((zbx_hash_t)p[6] << 16);
72 case 6: b = b + ((zbx_hash_t)p[5] << 8);
73 case 5: b = b + p[4];
74 case 4: a = a + ((zbx_hash_t)p[3] << 24);
75 case 3: a = a + ((zbx_hash_t)p[2] << 16);
76 case 2: a = a + ((zbx_hash_t)p[1] << 8);
77 case 1: a = a + p[0];
78 }
79
80 mix(a, b, c);
81
82 return c;
83 }
84
85 /*
86 * modified FNV hash function (see http://home.comcast.net/~bretm/hash/6.html)
87 */
zbx_hash_modfnv(const void * data,size_t len,zbx_hash_t seed)88 zbx_hash_t zbx_hash_modfnv(const void *data, size_t len, zbx_hash_t seed)
89 {
90 const uchar *p = (const uchar *)data;
91
92 zbx_hash_t hash;
93
94 hash = 2166136261u ^ seed;
95
96 while (len-- >= 1)
97 {
98 hash = (hash ^ *(p++)) * 16777619u;
99 }
100
101 hash += hash << 13;
102 hash ^= hash >> 7;
103 hash += hash << 3;
104 hash ^= hash >> 17;
105 hash += hash << 5;
106
107 return hash;
108 }
109
110 /*
111 * Murmur (see http://sites.google.com/site/murmurhash/)
112 */
zbx_hash_murmur2(const void * data,size_t len,zbx_hash_t seed)113 zbx_hash_t zbx_hash_murmur2(const void *data, size_t len, zbx_hash_t seed)
114 {
115 const uchar *p = (const uchar *)data;
116
117 zbx_hash_t hash;
118
119 const zbx_hash_t m = 0x5bd1e995u;
120 const zbx_hash_t r = 24;
121
122 hash = seed ^ len;
123
124 while (len >= 4)
125 {
126 zbx_hash_t k;
127
128 k = p[0];
129 k |= p[1] << 8;
130 k |= p[2] << 16;
131 k |= p[3] << 24;
132
133 k *= m;
134 k ^= k >> r;
135 k *= m;
136
137 hash *= m;
138 hash ^= k;
139
140 p += 4;
141 len -= 4;
142 }
143
144 switch (len)
145 {
146 case 3: hash ^= p[2] << 16;
147 case 2: hash ^= p[1] << 8;
148 case 1: hash ^= p[0];
149 hash *= m;
150 }
151
152 hash ^= hash >> 13;
153 hash *= m;
154 hash ^= hash >> 15;
155
156 return hash;
157 }
158
159 /*
160 * sdbm (see http://www.cse.yorku.ca/~oz/hash.html)
161 */
zbx_hash_sdbm(const void * data,size_t len,zbx_hash_t seed)162 zbx_hash_t zbx_hash_sdbm(const void *data, size_t len, zbx_hash_t seed)
163 {
164 const uchar *p = (const uchar *)data;
165
166 zbx_hash_t hash = seed;
167
168 #if 1
169
170 while (len-- >= 1)
171 {
172 /* hash = *(p++) + hash * 65599; */
173
174 hash = *(p++) + (hash << 6) + (hash << 16) - hash;
175 }
176
177 #else /* Duff's device */
178
179 #define HASH_STEP len--; \
180 hash = *(p++) + (hash << 6) + (hash << 16) - hash
181
182 switch (len & 7)
183 {
184 do
185 {
186 HASH_STEP;
187 case 7: HASH_STEP;
188 case 6: HASH_STEP;
189 case 5: HASH_STEP;
190 case 4: HASH_STEP;
191 case 3: HASH_STEP;
192 case 2: HASH_STEP;
193 case 1: HASH_STEP;
194 case 0: ;
195 }
196 while (len >= 8);
197 }
198
199 #endif
200
201 return hash;
202 }
203
204 /*
205 * djb2 (see http://www.cse.yorku.ca/~oz/hash.html)
206 */
zbx_hash_djb2(const void * data,size_t len,zbx_hash_t seed)207 zbx_hash_t zbx_hash_djb2(const void *data, size_t len, zbx_hash_t seed)
208 {
209 const uchar *p = (const uchar *)data;
210
211 zbx_hash_t hash;
212
213 hash = 5381u ^ seed;
214
215 while (len-- >= 1)
216 {
217 /* hash = hash * 33 + *(p++); */
218
219 hash = ((hash << 5) + hash) + *(p++);
220 }
221
222 return hash;
223 }
224
225 /* default hash functions */
226
zbx_default_ptr_hash_func(const void * data)227 zbx_hash_t zbx_default_ptr_hash_func(const void *data)
228 {
229 return ZBX_DEFAULT_PTR_HASH_ALGO(data, ZBX_PTR_SIZE, ZBX_DEFAULT_HASH_SEED);
230 }
231
zbx_default_uint64_hash_func(const void * data)232 zbx_hash_t zbx_default_uint64_hash_func(const void *data)
233 {
234 return ZBX_DEFAULT_UINT64_HASH_ALGO(data, sizeof(zbx_uint64_t), ZBX_DEFAULT_HASH_SEED);
235 }
236
zbx_default_string_hash_func(const void * data)237 zbx_hash_t zbx_default_string_hash_func(const void *data)
238 {
239 return ZBX_DEFAULT_STRING_HASH_ALGO(data, strlen((const char *)data), ZBX_DEFAULT_HASH_SEED);
240 }
241
242 /* default comparison functions */
243
zbx_default_int_compare_func(const void * d1,const void * d2)244 int zbx_default_int_compare_func(const void *d1, const void *d2)
245 {
246 const int *i1 = (const int *)d1;
247 const int *i2 = (const int *)d2;
248
249 ZBX_RETURN_IF_NOT_EQUAL(*i1, *i2);
250
251 return 0;
252 }
253
zbx_default_uint64_compare_func(const void * d1,const void * d2)254 int zbx_default_uint64_compare_func(const void *d1, const void *d2)
255 {
256 const zbx_uint64_t *i1 = (const zbx_uint64_t *)d1;
257 const zbx_uint64_t *i2 = (const zbx_uint64_t *)d2;
258
259 ZBX_RETURN_IF_NOT_EQUAL(*i1, *i2);
260
261 return 0;
262 }
263
zbx_default_uint64_ptr_compare_func(const void * d1,const void * d2)264 int zbx_default_uint64_ptr_compare_func(const void *d1, const void *d2)
265 {
266 const zbx_uint64_t *p1 = *(const zbx_uint64_t **)d1;
267 const zbx_uint64_t *p2 = *(const zbx_uint64_t **)d2;
268
269 return zbx_default_uint64_compare_func(p1, p2);
270 }
271
zbx_default_str_compare_func(const void * d1,const void * d2)272 int zbx_default_str_compare_func(const void *d1, const void *d2)
273 {
274 return strcmp(*(const char **)d1, *(const char **)d2);
275 }
276
zbx_default_ptr_compare_func(const void * d1,const void * d2)277 int zbx_default_ptr_compare_func(const void *d1, const void *d2)
278 {
279 const void *p1 = *(const void **)d1;
280 const void *p2 = *(const void **)d2;
281
282 ZBX_RETURN_IF_NOT_EQUAL(p1, p2);
283
284 return 0;
285 }
286
287 /* default memory management functions */
288
zbx_default_mem_malloc_func(void * old,size_t size)289 void *zbx_default_mem_malloc_func(void *old, size_t size)
290 {
291 return zbx_malloc(old, size);
292 }
293
zbx_default_mem_realloc_func(void * old,size_t size)294 void *zbx_default_mem_realloc_func(void *old, size_t size)
295 {
296 return zbx_realloc(old, size);
297 }
298
zbx_default_mem_free_func(void * ptr)299 void zbx_default_mem_free_func(void *ptr)
300 {
301 zbx_free(ptr);
302 }
303
304 /* numeric functions */
305
is_prime(int n)306 int is_prime(int n)
307 {
308 int i;
309
310 if (n <= 1)
311 return 0;
312 if (n == 2)
313 return 1;
314 if (n % 2 == 0)
315 return 0;
316
317 for (i = 3; i * i <= n; i+=2)
318 if (n % i == 0)
319 return 0;
320
321 return 1;
322 }
323
next_prime(int n)324 int next_prime(int n)
325 {
326 while (!is_prime(n))
327 n++;
328
329 return n;
330 }
331
332 /******************************************************************************
333 * *
334 * Function: zbx_isqrt32 *
335 * *
336 * Purpose: calculate integer part of square root of a 32 bit integer value *
337 * *
338 * Parameters: value - [IN] the value to calculate square root for *
339 * *
340 * Return value: the integer part of square root *
341 * *
342 * Comments: Uses basic digit by digit square root calculation algorithm with *
343 * binary base. *
344 * *
345 ******************************************************************************/
zbx_isqrt32(unsigned int value)346 unsigned int zbx_isqrt32(unsigned int value)
347 {
348 unsigned int i, remainder = 0, result = 0, p;
349
350 for (i = 0; i < 16; i++)
351 {
352 result <<= 1;
353 remainder = (remainder << 2) + (value >> 30);
354 value <<= 2;
355
356 p = (result << 1) | 1;
357 if (p <= remainder)
358 {
359 remainder -= p;
360 result |= 1;
361 }
362 }
363
364 return result;
365 }
366