xref: /PHP-8.1/ext/hash/hash_fnv.c (revision 01b3fc03)
1 /*
2   +----------------------------------------------------------------------+
3   | Copyright (c) The PHP Group                                          |
4   +----------------------------------------------------------------------+
5   | This source file is subject to version 3.01 of the PHP license,      |
6   | that is bundled with this package in the file LICENSE, and is        |
7   | available through the world-wide-web at the following url:           |
8   | https://www.php.net/license/3_01.txt                                 |
9   | If you did not receive a copy of the PHP license and are unable to   |
10   | obtain it through the world-wide-web, please send a note to          |
11   | license@php.net so we can mail you a copy immediately.               |
12   +----------------------------------------------------------------------+
13   | Author: Michael Maclean <mgdm@php.net>                               |
14   +----------------------------------------------------------------------+
15 */
16 
17 /*  Based on the public domain algorithm found at
18 	http://www.isthe.com/chongo/tech/comp/fnv/index.html */
19 
20 #include "php_hash.h"
21 #include "php_hash_fnv.h"
22 
23 const php_hash_ops php_hash_fnv132_ops = {
24 	"fnv132",
25 	(php_hash_init_func_t) PHP_FNV132Init,
26 	(php_hash_update_func_t) PHP_FNV132Update,
27 	(php_hash_final_func_t) PHP_FNV132Final,
28 	php_hash_copy,
29 	php_hash_serialize,
30 	php_hash_unserialize,
31 	PHP_FNV132_SPEC,
32 	4,
33 	4,
34 	sizeof(PHP_FNV132_CTX),
35 	0
36 };
37 
38 const php_hash_ops php_hash_fnv1a32_ops = {
39 	"fnv1a32",
40 	(php_hash_init_func_t) PHP_FNV132Init,
41 	(php_hash_update_func_t) PHP_FNV1a32Update,
42 	(php_hash_final_func_t) PHP_FNV132Final,
43 	php_hash_copy,
44 	php_hash_serialize,
45 	php_hash_unserialize,
46 	PHP_FNV132_SPEC,
47 	4,
48 	4,
49 	sizeof(PHP_FNV132_CTX),
50 	0
51 };
52 
53 const php_hash_ops php_hash_fnv164_ops = {
54 	"fnv164",
55 	(php_hash_init_func_t) PHP_FNV164Init,
56 	(php_hash_update_func_t) PHP_FNV164Update,
57 	(php_hash_final_func_t) PHP_FNV164Final,
58 	php_hash_copy,
59 	php_hash_serialize,
60 	php_hash_unserialize,
61 	PHP_FNV164_SPEC,
62 	8,
63 	4,
64 	sizeof(PHP_FNV164_CTX),
65 	0
66 };
67 
68 const php_hash_ops php_hash_fnv1a64_ops = {
69 	"fnv1a64",
70 	(php_hash_init_func_t) PHP_FNV164Init,
71 	(php_hash_update_func_t) PHP_FNV1a64Update,
72 	(php_hash_final_func_t) PHP_FNV164Final,
73 	php_hash_copy,
74 	php_hash_serialize,
75 	php_hash_unserialize,
76 	PHP_FNV164_SPEC,
77 	8,
78 	4,
79 	sizeof(PHP_FNV164_CTX),
80 	0
81 };
82 
83 /* {{{ PHP_FNV132Init
84  * 32-bit FNV-1 hash initialisation
85  */
PHP_FNV132Init(PHP_FNV132_CTX * context,ZEND_ATTRIBUTE_UNUSED HashTable * args)86 PHP_HASH_API void PHP_FNV132Init(PHP_FNV132_CTX *context, ZEND_ATTRIBUTE_UNUSED HashTable *args)
87 {
88 	context->state = PHP_FNV1_32_INIT;
89 }
90 /* }}} */
91 
PHP_FNV132Update(PHP_FNV132_CTX * context,const unsigned char * input,size_t inputLen)92 PHP_HASH_API void PHP_FNV132Update(PHP_FNV132_CTX *context, const unsigned char *input,
93 		size_t inputLen)
94 {
95 	context->state = fnv_32_buf((void *)input, inputLen, context->state, 0);
96 }
97 
PHP_FNV1a32Update(PHP_FNV132_CTX * context,const unsigned char * input,size_t inputLen)98 PHP_HASH_API void PHP_FNV1a32Update(PHP_FNV132_CTX *context, const unsigned char *input,
99 		size_t inputLen)
100 {
101 	context->state = fnv_32_buf((void *)input, inputLen, context->state, 1);
102 }
103 
PHP_FNV132Final(unsigned char digest[4],PHP_FNV132_CTX * context)104 PHP_HASH_API void PHP_FNV132Final(unsigned char digest[4], PHP_FNV132_CTX * context)
105 {
106 #ifdef WORDS_BIGENDIAN
107 	memcpy(digest, &context->state, 4);
108 #else
109 	int i = 0;
110 	unsigned char *c = (unsigned char *) &context->state;
111 
112 	for (i = 0; i < 4; i++) {
113 		digest[i] = c[3 - i];
114 	}
115 #endif
116 }
117 
118 /* {{{ PHP_FNV164Init
119  * 64-bit FNV-1 hash initialisation
120  */
PHP_FNV164Init(PHP_FNV164_CTX * context,ZEND_ATTRIBUTE_UNUSED HashTable * args)121 PHP_HASH_API void PHP_FNV164Init(PHP_FNV164_CTX *context, ZEND_ATTRIBUTE_UNUSED HashTable *args)
122 {
123 	context->state = PHP_FNV1_64_INIT;
124 }
125 /* }}} */
126 
PHP_FNV164Update(PHP_FNV164_CTX * context,const unsigned char * input,size_t inputLen)127 PHP_HASH_API void PHP_FNV164Update(PHP_FNV164_CTX *context, const unsigned char *input,
128 		size_t inputLen)
129 {
130 	context->state = fnv_64_buf((void *)input, inputLen, context->state, 0);
131 }
132 
PHP_FNV1a64Update(PHP_FNV164_CTX * context,const unsigned char * input,size_t inputLen)133 PHP_HASH_API void PHP_FNV1a64Update(PHP_FNV164_CTX *context, const unsigned char *input,
134 		size_t inputLen)
135 {
136 	context->state = fnv_64_buf((void *)input, inputLen, context->state, 1);
137 }
138 
PHP_FNV164Final(unsigned char digest[8],PHP_FNV164_CTX * context)139 PHP_HASH_API void PHP_FNV164Final(unsigned char digest[8], PHP_FNV164_CTX * context)
140 {
141 #ifdef WORDS_BIGENDIAN
142 	memcpy(digest, &context->state, 8);
143 #else
144 	int i = 0;
145 	unsigned char *c = (unsigned char *) &context->state;
146 
147 	for (i = 0; i < 8; i++) {
148 		digest[i] = c[7 - i];
149 	}
150 #endif
151 }
152 
153 
154 /*
155  * fnv_32_buf - perform a 32 bit Fowler/Noll/Vo hash on a buffer
156  *
157  * input:
158  *  buf - start of buffer to hash
159  *  len - length of buffer in octets
160  *  hval	- previous hash value or 0 if first call
161  *  alternate - if > 0 use the alternate version
162  *
163  * returns:
164  *  32 bit hash as a static hash type
165  */
166 static uint32_t
fnv_32_buf(void * buf,size_t len,uint32_t hval,int alternate)167 fnv_32_buf(void *buf, size_t len, uint32_t hval, int alternate)
168 {
169 	unsigned char *bp = (unsigned char *)buf;   /* start of buffer */
170 	unsigned char *be = bp + len;	   /* beyond end of buffer */
171 
172 	/*
173 	 * FNV-1 hash each octet in the buffer
174 	 */
175 	if (alternate == 0) {
176 		while (bp < be) {
177 			/* multiply by the 32 bit FNV magic prime mod 2^32 */
178 			hval *= PHP_FNV_32_PRIME;
179 
180 			/* xor the bottom with the current octet */
181 			hval ^= (uint32_t)*bp++;
182 		}
183 	} else {
184 		while (bp < be) {
185 			/* xor the bottom with the current octet */
186 			hval ^= (uint32_t)*bp++;
187 
188 			/* multiply by the 32 bit FNV magic prime mod 2^32 */
189 			hval *= PHP_FNV_32_PRIME;
190 		}
191 	}
192 
193 	/* return our new hash value */
194 	return hval;
195 }
196 
197 /*
198  * fnv_64_buf - perform a 64 bit Fowler/Noll/Vo hash on a buffer
199  *
200  * input:
201  *  buf - start of buffer to hash
202  *  len - length of buffer in octets
203  *  hval	- previous hash value or 0 if first call
204  *  alternate - if > 0 use the alternate version
205  *
206  * returns:
207  *  64 bit hash as a static hash type
208  */
209 static uint64_t
fnv_64_buf(void * buf,size_t len,uint64_t hval,int alternate)210 fnv_64_buf(void *buf, size_t len, uint64_t hval, int alternate)
211 {
212 	unsigned char *bp = (unsigned char *)buf;   /* start of buffer */
213 	unsigned char *be = bp + len;	   /* beyond end of buffer */
214 
215 	/*
216 	 * FNV-1 hash each octet of the buffer
217 	 */
218 
219 	if (alternate == 0) {
220 		while (bp < be) {
221 			/* multiply by the 64 bit FNV magic prime mod 2^64 */
222 			hval *= PHP_FNV_64_PRIME;
223 
224 			/* xor the bottom with the current octet */
225 			hval ^= (uint64_t)*bp++;
226 		}
227 	 } else {
228 		while (bp < be) {
229 			/* xor the bottom with the current octet */
230 			hval ^= (uint64_t)*bp++;
231 
232 			/* multiply by the 64 bit FNV magic prime mod 2^64 */
233 			hval *= PHP_FNV_64_PRIME;
234 		 }
235 	}
236 
237 	/* return our new hash value */
238 	return hval;
239 }
240