a752c7ab
 elopes
add first test an...
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
|
/*
* Copyright (C) 2013 Freie Universität Berlin
*
* This file is subject to the terms and conditions of the GNU Lesser
* General Public License v2.1. See the file LICENSE in the top level
* directory for more details.
*/
/**
* @ingroup sys_hashes
* @{
*
* @file
* @brief Hash function API
*
* @author Jason Linehan <patientulysses@gmail.com>
* @author Christian Mehlis <mehlis@inf.fu-berlin.de>
*/
#ifndef HASHES_H
#define HASHES_H
#include <stddef.h>
#include <inttypes.h>
#ifdef __cplusplus
extern "C" {
#endif
/**
* @brief djb2
*
* HISTORY
* This algorithm (k=33) was first reported by Dan Bernstein many years
* ago in comp.lang.c. Another version of this algorithm (now favored by
* bernstein) uses XOR:
*
* hash(i) = hash(i - 1) * 33 ^ str[i];
*
* The magic of number 33 (why it works better than many other constants,
* prime or not) has never been adequately explained.
*
* @param buf input buffer to hash
* @param len length of buffer
* @return 32 bit sized hash
*/
uint32_t djb2_hash(const uint8_t *buf, size_t len);
/**
* @brief sdbm
*
* HISTORY
* This algorithm was created for sdbm (a public-domain reimplementation
* of ndbm) database library. It was found to do well in scrambling bits,
* causing better distribution of the keys and fewer splits. it also
* happens to be a good general hashing function with good distribution.
*
* The actual function is
*
* hash(i) = hash(i - 1) * 65599 + str[i];
*
* What is included below is the faster version used in gawk. [there is
* even a faster, duff-device version] the magic constant 65599 was picked
* out of thin air while experimenting with different constants, and turns
* out to be a prime. this is one of the algorithms used in berkeley db
* (see sleepycat) and elsewhere.
*
* @param buf input buffer to hash
* @param len length of buffer
* @return 32 bit sized hash
*/
uint32_t sdbm_hash(const uint8_t *buf, size_t len);
/**
* @brief Kernighan and Ritchie
*
* HISTORY
* This hash function appeared in K&R (1st ed) but at least the reader
* was warned:
*
* "This is not the best possible algorithm, but it has the merit
* of extreme simplicity."
*
* This is an understatement. It is a terrible hashing algorithm, and it
* could have been much better without sacrificing its "extreme simplicity."
* [see the second edition!]
*
* Many C programmers use this function without actually testing it, or
* checking something like Knuth's Sorting and Searching, so it stuck.
* It is now found mixed with otherwise respectable code, eg. cnews. sigh.
* [see also: tpop]
*
* @param buf input buffer to hash
* @param len length of buffer
* @return 32 bit sized hash
*/
uint32_t kr_hash(const uint8_t *buf, size_t len);
/**
* @brief Shift, Add, XOR
*
* @param buf input buffer to hash
* @param len length of buffer
* @return 32 bit sized hash
*/
uint32_t sax_hash(const uint8_t *buf, size_t len);
/**
* @brief Donald E. Knuth
*
* HISTORY
* Proposed by Donald E. Knuth in The Art Of Computer Programming Vol. 3,
* under the topic of "Sorting and Search", Chapter 6.4.
*
* @param buf input buffer to hash
* @param len length of buffer
* @return 32 bit sized hash
*/
uint32_t dek_hash(const uint8_t *buf, size_t len);
/**
* @brief Fowler–Noll–Vo
*
* NOTE
* For a more fully featured and modern version of this hash, see fnv32.c
*
* @param buf input buffer to hash
* @param len length of buffer
* @return 32 bit sized hash
*/
uint32_t fnv_hash(const uint8_t *buf, size_t len);
/**
* @brief Rotating
*
* found on
* http://burtleburtle.net/bob/hash/doobs.html
*
* @param buf input buffer to hash
* @param len length of buffer
* @return 32 bit sized hash
*/
uint32_t rotating_hash(const uint8_t *buf, size_t len);
/**
* @brief One at a time
*
* found on
* http://burtleburtle.net/bob/hash/doobs.html
*
* @param buf input buffer to hash
* @param len length of buffer
* @return 32 bit sized hash
*/
uint32_t one_at_a_time_hash(const uint8_t *buf, size_t len);
#ifdef __cplusplus
}
#endif
/** @} */
#endif /* HASHES_H */
|