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 */
45static apr_uint32_t
46fnv1a_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 */
63enum { 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 */
69static apr_size_t
70fnv1a_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 */
94static apr_uint32_t
95finalize_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
117apr_uint32_t
118svn__fnv1a_32(const void *input, apr_size_t len)
119{
120  return fnv1a_32(FNV1_BASE_32, input, len);
121}
122
123apr_uint32_t
124svn__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
135void
136svn__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
154struct svn_fnv1a_32__context_t
155{
156  apr_uint32_t hash;
157};
158
159svn_fnv1a_32__context_t *
160svn_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
168void
169svn_fnv1a_32__context_reset(svn_fnv1a_32__context_t *context)
170{
171  context->hash = FNV1_BASE_32;
172}
173
174void
175svn_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
182apr_uint32_t
183svn_fnv1a_32__finalize(svn_fnv1a_32__context_t *context)
184{
185  return context->hash;
186}
187
188
189struct svn_fnv1a_32x4__context_t
190{
191  apr_uint32_t hashes[SCALING];
192  apr_size_t buffered;
193  char buffer[SCALING];
194};
195
196svn_fnv1a_32x4__context_t *
197svn_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
211void
212svn_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
222void
223svn_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
257apr_uint32_t
258svn_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