contrib/subversion/subversion/libsvn_subr/fnv1a.c

   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
  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
  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
  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
 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
 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
 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 *
 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
 169 svn_fnv1a_32__context_reset(svn_fnv1a_32__context_t *context)
 170 {
 171   context->hash = FNV1_BASE_32;
 172 }
 173
 174 void
 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
 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 *
 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
 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
 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
 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 }