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__update(svn_fnv1a_32__context_t *context,
 170                      const void *data,
 171                      apr_size_t len)
 172 {
 173   context->hash = fnv1a_32(context->hash, data, len);
 174 }
 175
 176 apr_uint32_t
 177 svn_fnv1a_32__finalize(svn_fnv1a_32__context_t *context)
 178 {
 179   return context->hash;
 180 }
 181
 182
 183 struct svn_fnv1a_32x4__context_t
 184 {
 185   apr_uint32_t hashes[SCALING];
 186   apr_size_t buffered;
 187   char buffer[SCALING];
 188 };
 189
 190 svn_fnv1a_32x4__context_t *
 191 svn_fnv1a_32x4__context_create(apr_pool_t *pool)
 192 {
 193   svn_fnv1a_32x4__context_t *context = apr_palloc(pool, sizeof(*context));
 194
 195   context->hashes[0] = FNV1_BASE_32;
 196   context->hashes[1] = FNV1_BASE_32;
 197   context->hashes[2] = FNV1_BASE_32;
 198   context->hashes[3] = FNV1_BASE_32;
 199
 200   context->buffered = 0;
 201
 202   return context;
 203 }
 204
 205 void
 206 svn_fnv1a_32x4__update(svn_fnv1a_32x4__context_t *context,
 207                        const void *data,
 208                        apr_size_t len)
 209 {
 210   apr_size_t processed;
 211
 212   if (context->buffered)
 213     {
 214       apr_size_t to_copy = SCALING - context->buffered;
 215       if (to_copy > len)
 216         {
 217           memcpy(context->buffer + context->buffered, data, len);
 218           context->buffered += len;
 219           return;
 220         }
 221
 222       memcpy(context->buffer + context->buffered, data, to_copy);
 223       data = (const char *)data + to_copy;
 224       len -= to_copy;
 225
 226       fnv1a_32x4(context->hashes, context->buffer, SCALING);
 227       context->buffered = 0;
 228     }
 229
 230   processed = fnv1a_32x4(context->hashes, data, len);
 231   if (processed != len)
 232     {
 233       context->buffered = len - processed;
 234       memcpy(context->buffer,
 235              (const char*)data + processed,
 236              len - processed);
 237     }
 238 }
 239
 240 apr_uint32_t
 241 svn_fnv1a_32x4__finalize(svn_fnv1a_32x4__context_t *context)
 242 {
 243   return finalize_fnv1a_32x4(context->hashes,
 244                              context->buffer,
 245                              context->buffered);
 246 }