1 files changed, 246 insertions, 0 deletions
diff --git a/subversion/libsvn_subr/fnv1a.c b/subversion/libsvn_subr/fnv1a.c
new file mode 100644
index 0000000..458bdd2
--- /dev/null
+++ b/subversion/libsvn_subr/fnv1a.c
@@ -0,0 +1,246 @@
+/*
+ * fnv1a.c :  routines to create checksums derived from FNV-1a
+ *
+ * ====================================================================
+ *    Licensed to the Apache Software Foundation (ASF) under one
+ *    or more contributor license agreements.  See the NOTICE file
+ *    distributed with this work for additional information
+ *    regarding copyright ownership.  The ASF licenses this file
+ *    to you under the Apache License, Version 2.0 (the
+ *    "License"); you may not use this file except in compliance
+ *    with the License.  You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *    Unless required by applicable law or agreed to in writing,
+ *    software distributed under the License is distributed on an
+ *    "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ *    KIND, either express or implied.  See the License for the
+ *    specific language governing permissions and limitations
+ *    under the License.
+ * ====================================================================
+ */
+
+#define APR_WANT_BYTEFUNC
+
+#include <assert.h>
+#include <apr.h>
+
+#include "private/svn_subr_private.h"
+#include "fnv1a.h"
+
+/**
+ * See http://www.isthe.com/chongo/tech/comp/fnv/ for more info on FNV-1
+ */
+
+/* FNV-1 32 bit constants taken from
+ * http://www.isthe.com/chongo/tech/comp/fnv/
+ */
+#define FNV1_PRIME_32 0x01000193
+#define FNV1_BASE_32 2166136261U
+
+/* FNV-1a core implementation returning a 32 bit checksum over the first
+ * LEN bytes in INPUT.  HASH is the checksum over preceding data (if any).
+ */
+static apr_uint32_t
+fnv1a_32(apr_uint32_t hash, const void *input, apr_size_t len)
+{
+  const unsigned char *data = input;
+  const unsigned char *end = data + len;
+
+  for (; data != end; ++data)
+    {
+      hash ^= *data;
+      hash *= FNV1_PRIME_32;
+    }
+
+  return hash;
+}
+
+/* Number of interleaved FVN-1a checksums we calculate for the modified
+ * checksum algorithm.
+ */
+enum { SCALING = 4 };
+
+/* FNV-1a core implementation updating 4 interleaved checksums in HASHES
+ * over the first LEN bytes in INPUT.  This will only process multiples
+ * of 4 and return the number of bytes processed.  LEN - ReturnValue < 4.
+ */
+static apr_size_t
+fnv1a_32x4(apr_uint32_t hashes[SCALING], const void *input, apr_size_t len)
+{
+  /* calculate SCALING interleaved FNV-1a hashes while the input
+     is large enough */
+  const unsigned char *data = input;
+  const unsigned char *end = data + len;
+  for (; data + SCALING <= end; data += SCALING)
+    {
+      hashes[0] ^= data[0];
+      hashes[0] *= FNV1_PRIME_32;
+      hashes[1] ^= data[1];
+      hashes[1] *= FNV1_PRIME_32;
+      hashes[2] ^= data[2];
+      hashes[2] *= FNV1_PRIME_32;
+      hashes[3] ^= data[3];
+      hashes[3] *= FNV1_PRIME_32;
+    }
+
+  return data - (const unsigned char *)input;
+}
+
+/* Combine interleaved HASHES plus LEN bytes from INPUT into a single
+ * 32 bit hash value and return that.  LEN must be < 4.
+ */
+static apr_uint32_t
+finalize_fnv1a_32x4(apr_uint32_t hashes[SCALING],
+                    const void *input,
+                    apr_size_t len)
+{
+  char final_data[sizeof(apr_uint32_t) * SCALING + SCALING - 1];
+  apr_size_t i;
+  assert(len < SCALING);
+
+  for (i = 0; i < SCALING; ++i)
+    hashes[i] = htonl(hashes[i]);
+
+  /* run FNV-1a over the interleaved checksums plus the remaining
+     (odd-lotted) input data */
+  memcpy(final_data, hashes, sizeof(apr_uint32_t) * SCALING);
+  if (len)
+    memcpy(final_data + sizeof(apr_uint32_t) * SCALING, input, len);
+
+  return fnv1a_32(FNV1_BASE_32,
+                  final_data,
+                  sizeof(apr_uint32_t) * SCALING + len);
+}
+
+apr_uint32_t
+svn__fnv1a_32(const void *input, apr_size_t len)
+{
+  return fnv1a_32(FNV1_BASE_32, input, len);
+}
+
+apr_uint32_t
+svn__fnv1a_32x4(const void *input, apr_size_t len)
+{
+  apr_uint32_t hashes[SCALING]
+    = { FNV1_BASE_32, FNV1_BASE_32, FNV1_BASE_32, FNV1_BASE_32 };
+  apr_size_t processed = fnv1a_32x4(hashes, input, len);
+
+  return finalize_fnv1a_32x4(hashes,
+                             (const char *)input + processed,
+                             len - processed);
+}
+
+void
+svn__fnv1a_32x4_raw(apr_uint32_t hashes[4],
+                    const void *input,
+                    apr_size_t len)
+{
+  apr_size_t processed;
+
+  apr_size_t i;
+  for (i = 0; i < SCALING; ++i)
+    hashes[i] = FNV1_BASE_32;
+
+  /* Process full 16 byte chunks. */
+  processed = fnv1a_32x4(hashes, input, len);
+
+  /* Fold the remainder (if any) into the first hash. */
+  hashes[0] = fnv1a_32(hashes[0], (const char *)input + processed,
+                       len - processed);
+}
+
+struct svn_fnv1a_32__context_t
+{
+  apr_uint32_t hash;
+};
+
+svn_fnv1a_32__context_t *
+svn_fnv1a_32__context_create(apr_pool_t *pool)
+{
+  svn_fnv1a_32__context_t *context = apr_palloc(pool, sizeof(*context));
+  context->hash = FNV1_BASE_32;
+
+  return context;
+}
+
+void
+svn_fnv1a_32__update(svn_fnv1a_32__context_t *context,
+                     const void *data,
+                     apr_size_t len)
+{
+  context->hash = fnv1a_32(context->hash, data, len);
+}
+
+apr_uint32_t
+svn_fnv1a_32__finalize(svn_fnv1a_32__context_t *context)
+{
+  return context->hash;
+}
+
+
+struct svn_fnv1a_32x4__context_t
+{
+  apr_uint32_t hashes[SCALING];
+  apr_size_t buffered;
+  char buffer[SCALING];
+};
+
+svn_fnv1a_32x4__context_t *
+svn_fnv1a_32x4__context_create(apr_pool_t *pool)
+{
+  svn_fnv1a_32x4__context_t *context = apr_palloc(pool, sizeof(*context));
+
+  context->hashes[0] = FNV1_BASE_32;
+  context->hashes[1] = FNV1_BASE_32;
+  context->hashes[2] = FNV1_BASE_32;
+  context->hashes[3] = FNV1_BASE_32;
+
+  context->buffered = 0;
+
+  return context;
+}
+
+void
+svn_fnv1a_32x4__update(svn_fnv1a_32x4__context_t *context,
+                       const void *data,
+                       apr_size_t len)
+{
+  apr_size_t processed;
+
+  if (context->buffered)
+    {
+      apr_size_t to_copy = SCALING - context->buffered;
+      if (to_copy > len)
+        {
+          memcpy(context->buffer + context->buffered, data, len);
+          context->buffered += len;
+          return;
+        }
+
+      memcpy(context->buffer + context->buffered, data, to_copy);
+      data = (const char *)data + to_copy;
+      len -= to_copy;
+
+      fnv1a_32x4(context->hashes, context->buffer, SCALING);
+      context->buffered = 0;
+    }
+
+  processed = fnv1a_32x4(context->hashes, data, len);
+  if (processed != len)
+    {
+      context->buffered = len - processed;
+      memcpy(context->buffer,
+             (const char*)data + processed,
+             len - processed);
+    }
+}
+
+apr_uint32_t
+svn_fnv1a_32x4__finalize(svn_fnv1a_32x4__context_t *context)
+{
+  return finalize_fnv1a_32x4(context->hashes,
+                             context->buffer,
+                             context->buffered);
+}