1 /*
2 * fnv1a.c : routines to create checksums derived from FNV-1a
3 *
4 * ====================================================================
5 * Licensed to the Apache Software Foundation (ASF) under one
6 * or more contributor license agreements. See the NOTICE file
7 * distributed with this work for additional information
8 * regarding copyright ownership. The ASF licenses this file
9 * to you under the Apache License, Version 2.0 (the
10 * "License"); you may not use this file except in compliance
11 * with the License. You may obtain a copy of the License at
12 *
13 * http://www.apache.org/licenses/LICENSE-2.0
14 *
15 * Unless required by applicable law or agreed to in writing,
16 * software distributed under the License is distributed on an
17 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
18 * KIND, either express or implied. See the License for the
19 * specific language governing permissions and limitations
20 * under the License.
21 * ====================================================================
22 */
23
24 #define APR_WANT_BYTEFUNC
25
26 #include <assert.h>
27 #include <apr.h>
28
29 #include "private/svn_subr_private.h"
30 #include "fnv1a.h"
31
32 /**
33 * See http://www.isthe.com/chongo/tech/comp/fnv/ for more info on FNV-1
34 */
35
36 /* FNV-1 32 bit constants taken from
37 * http://www.isthe.com/chongo/tech/comp/fnv/
38 */
39 #define FNV1_PRIME_32 0x01000193
40 #define FNV1_BASE_32 2166136261U
41
42 /* FNV-1a core implementation returning a 32 bit checksum over the first
43 * LEN bytes in INPUT. HASH is the checksum over preceding data (if any).
44 */
45 static apr_uint32_t
fnv1a_32(apr_uint32_t hash,const void * input,apr_size_t len)46 fnv1a_32(apr_uint32_t hash, const void *input, apr_size_t len)
47 {
48 const unsigned char *data = input;
49 const unsigned char *end = data + len;
50
51 for (; data != end; ++data)
52 {
53 hash ^= *data;
54 hash *= FNV1_PRIME_32;
55 }
56
57 return hash;
58 }
59
60 /* Number of interleaved FVN-1a checksums we calculate for the modified
61 * checksum algorithm.
62 */
63 enum { SCALING = 4 };
64
65 /* FNV-1a core implementation updating 4 interleaved checksums in HASHES
66 * over the first LEN bytes in INPUT. This will only process multiples
67 * of 4 and return the number of bytes processed. LEN - ReturnValue < 4.
68 */
69 static apr_size_t
fnv1a_32x4(apr_uint32_t hashes[SCALING],const void * input,apr_size_t len)70 fnv1a_32x4(apr_uint32_t hashes[SCALING], const void *input, apr_size_t len)
71 {
72 /* calculate SCALING interleaved FNV-1a hashes while the input
73 is large enough */
74 const unsigned char *data = input;
75 const unsigned char *end = data + len;
76 for (; data + SCALING <= end; data += SCALING)
77 {
78 hashes[0] ^= data[0];
79 hashes[0] *= FNV1_PRIME_32;
80 hashes[1] ^= data[1];
81 hashes[1] *= FNV1_PRIME_32;
82 hashes[2] ^= data[2];
83 hashes[2] *= FNV1_PRIME_32;
84 hashes[3] ^= data[3];
85 hashes[3] *= FNV1_PRIME_32;
86 }
87
88 return data - (const unsigned char *)input;
89 }
90
91 /* Combine interleaved HASHES plus LEN bytes from INPUT into a single
92 * 32 bit hash value and return that. LEN must be < 4.
93 */
94 static apr_uint32_t
finalize_fnv1a_32x4(apr_uint32_t hashes[SCALING],const void * input,apr_size_t len)95 finalize_fnv1a_32x4(apr_uint32_t hashes[SCALING],
96 const void *input,
97 apr_size_t len)
98 {
99 char final_data[sizeof(apr_uint32_t) * SCALING + SCALING - 1];
100 apr_size_t i;
101 assert(len < SCALING);
102
103 for (i = 0; i < SCALING; ++i)
104 hashes[i] = htonl(hashes[i]);
105
106 /* run FNV-1a over the interleaved checksums plus the remaining
107 (odd-lotted) input data */
108 memcpy(final_data, hashes, sizeof(apr_uint32_t) * SCALING);
109 if (len)
110 memcpy(final_data + sizeof(apr_uint32_t) * SCALING, input, len);
111
112 return fnv1a_32(FNV1_BASE_32,
113 final_data,
114 sizeof(apr_uint32_t) * SCALING + len);
115 }
116
117 apr_uint32_t
svn__fnv1a_32(const void * input,apr_size_t len)118 svn__fnv1a_32(const void *input, apr_size_t len)
119 {
120 return fnv1a_32(FNV1_BASE_32, input, len);
121 }
122
123 apr_uint32_t
svn__fnv1a_32x4(const void * input,apr_size_t len)124 svn__fnv1a_32x4(const void *input, apr_size_t len)
125 {
126 apr_uint32_t hashes[SCALING]
127 = { FNV1_BASE_32, FNV1_BASE_32, FNV1_BASE_32, FNV1_BASE_32 };
128 apr_size_t processed = fnv1a_32x4(hashes, input, len);
129
130 return finalize_fnv1a_32x4(hashes,
131 (const char *)input + processed,
132 len - processed);
133 }
134
135 void
svn__fnv1a_32x4_raw(apr_uint32_t hashes[4],const void * input,apr_size_t len)136 svn__fnv1a_32x4_raw(apr_uint32_t hashes[4],
137 const void *input,
138 apr_size_t len)
139 {
140 apr_size_t processed;
141
142 apr_size_t i;
143 for (i = 0; i < SCALING; ++i)
144 hashes[i] = FNV1_BASE_32;
145
146 /* Process full 16 byte chunks. */
147 processed = fnv1a_32x4(hashes, input, len);
148
149 /* Fold the remainder (if any) into the first hash. */
150 hashes[0] = fnv1a_32(hashes[0], (const char *)input + processed,
151 len - processed);
152 }
153
154 struct svn_fnv1a_32__context_t
155 {
156 apr_uint32_t hash;
157 };
158
159 svn_fnv1a_32__context_t *
svn_fnv1a_32__context_create(apr_pool_t * pool)160 svn_fnv1a_32__context_create(apr_pool_t *pool)
161 {
162 svn_fnv1a_32__context_t *context = apr_palloc(pool, sizeof(*context));
163 context->hash = FNV1_BASE_32;
164
165 return context;
166 }
167
168 void
svn_fnv1a_32__context_reset(svn_fnv1a_32__context_t * context)169 svn_fnv1a_32__context_reset(svn_fnv1a_32__context_t *context)
170 {
171 context->hash = FNV1_BASE_32;
172 }
173
174 void
svn_fnv1a_32__update(svn_fnv1a_32__context_t * context,const void * data,apr_size_t len)175 svn_fnv1a_32__update(svn_fnv1a_32__context_t *context,
176 const void *data,
177 apr_size_t len)
178 {
179 context->hash = fnv1a_32(context->hash, data, len);
180 }
181
182 apr_uint32_t
svn_fnv1a_32__finalize(svn_fnv1a_32__context_t * context)183 svn_fnv1a_32__finalize(svn_fnv1a_32__context_t *context)
184 {
185 return context->hash;
186 }
187
188
189 struct svn_fnv1a_32x4__context_t
190 {
191 apr_uint32_t hashes[SCALING];
192 apr_size_t buffered;
193 char buffer[SCALING];
194 };
195
196 svn_fnv1a_32x4__context_t *
svn_fnv1a_32x4__context_create(apr_pool_t * pool)197 svn_fnv1a_32x4__context_create(apr_pool_t *pool)
198 {
199 svn_fnv1a_32x4__context_t *context = apr_palloc(pool, sizeof(*context));
200
201 context->hashes[0] = FNV1_BASE_32;
202 context->hashes[1] = FNV1_BASE_32;
203 context->hashes[2] = FNV1_BASE_32;
204 context->hashes[3] = FNV1_BASE_32;
205
206 context->buffered = 0;
207
208 return context;
209 }
210
211 void
svn_fnv1a_32x4__context_reset(svn_fnv1a_32x4__context_t * context)212 svn_fnv1a_32x4__context_reset(svn_fnv1a_32x4__context_t *context)
213 {
214 context->hashes[0] = FNV1_BASE_32;
215 context->hashes[1] = FNV1_BASE_32;
216 context->hashes[2] = FNV1_BASE_32;
217 context->hashes[3] = FNV1_BASE_32;
218
219 context->buffered = 0;
220 }
221
222 void
svn_fnv1a_32x4__update(svn_fnv1a_32x4__context_t * context,const void * data,apr_size_t len)223 svn_fnv1a_32x4__update(svn_fnv1a_32x4__context_t *context,
224 const void *data,
225 apr_size_t len)
226 {
227 apr_size_t processed;
228
229 if (context->buffered)
230 {
231 apr_size_t to_copy = SCALING - context->buffered;
232 if (to_copy > len)
233 {
234 memcpy(context->buffer + context->buffered, data, len);
235 context->buffered += len;
236 return;
237 }
238
239 memcpy(context->buffer + context->buffered, data, to_copy);
240 data = (const char *)data + to_copy;
241 len -= to_copy;
242
243 fnv1a_32x4(context->hashes, context->buffer, SCALING);
244 context->buffered = 0;
245 }
246
247 processed = fnv1a_32x4(context->hashes, data, len);
248 if (processed != len)
249 {
250 context->buffered = len - processed;
251 memcpy(context->buffer,
252 (const char*)data + processed,
253 len - processed);
254 }
255 }
256
257 apr_uint32_t
svn_fnv1a_32x4__finalize(svn_fnv1a_32x4__context_t * context)258 svn_fnv1a_32x4__finalize(svn_fnv1a_32x4__context_t *context)
259 {
260 return finalize_fnv1a_32x4(context->hashes,
261 context->buffer,
262 context->buffered);
263 }
264