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