subversion/libsvn_subr/fnv1a.c

/*
 * 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__context_reset(svn_fnv1a_32__context_t *context)
{
  context->hash = FNV1_BASE_32;
}

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__context_reset(svn_fnv1a_32x4__context_t *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;
}

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);
}