/*
 * Copyright 2006 Bob Jenkins
 *
 * Derived from public domain source, see
 *     <http://burtleburtle.net/bob/c/lookup3.c>:
 *
 * "lookup3.c, by Bob Jenkins, May 2006, Public Domain.
 *
 *  These are functions for producing 32-bit hashes for hash table lookup...
 *  ...You can use this free for any purpose.  It's in the public domain.
 *  It has no warranty."
 *
 * Copyright (c) 2014-2015 Solarflare Communications Inc.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 * 1. Redistributions of source code must retain the above copyright notice,
 *    this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright notice,
 *    this list of conditions and the following disclaimer in the documentation
 *    and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
 * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * The views and conclusions contained in the software and documentation are
 * those of the authors and should not be interpreted as representing official
 * policies, either expressed or implied, of the FreeBSD Project.
 */

#include "efx.h"
#include "efx_impl.h"

/* Hash initial value */
#define EFX_HASH_INITIAL_VALUE  0xdeadbeef

/*
 * Rotate a 32-bit value left
 *
 * Allow platform to provide an intrinsic or optimised routine and
 * fall-back to a simple shift based implementation.
 */
#if EFSYS_HAS_ROTL_DWORD

#define EFX_HASH_ROTATE(_value, _shift)                                 \
        EFSYS_ROTL_DWORD(_value, _shift)

#else

#define EFX_HASH_ROTATE(_value, _shift)                                 \
        (((_value) << (_shift)) | ((_value) >> (32 - (_shift))))

#endif

/* Mix three 32-bit values reversibly */
#define EFX_HASH_MIX(_a, _b, _c)                                        \
        do {                                                            \
                _a -= _c;                                               \
                _a ^= EFX_HASH_ROTATE(_c, 4);                           \
                _c += _b;                                               \
                _b -= _a;                                               \
                _b ^= EFX_HASH_ROTATE(_a, 6);                           \
                _a += _c;                                               \
                _c -= _b;                                               \
                _c ^= EFX_HASH_ROTATE(_b, 8);                           \
                _b += _a;                                               \
                _a -= _c;                                               \
                _a ^= EFX_HASH_ROTATE(_c, 16);                          \
                _c += _b;                                               \
                _b -= _a;                                               \
                _b ^= EFX_HASH_ROTATE(_a, 19);                          \
                _a += _c;                                               \
                _c -= _b;                                               \
                _c ^= EFX_HASH_ROTATE(_b, 4);                           \
                _b += _a;                                               \
        _NOTE(CONSTANTCONDITION)                                        \
        } while (B_FALSE)

/* Final mixing of three 32-bit values into one (_c) */
#define EFX_HASH_FINALISE(_a, _b, _c)                                   \
        do {                                                            \
                _c ^= _b;                                               \
                _c -= EFX_HASH_ROTATE(_b, 14);                          \
                _a ^= _c;                                               \
                _a -= EFX_HASH_ROTATE(_c, 11);                          \
                _b ^= _a;                                               \
                _b -= EFX_HASH_ROTATE(_a, 25);                          \
                _c ^= _b;                                               \
                _c -= EFX_HASH_ROTATE(_b, 16);                          \
                _a ^= _c;                                               \
                _a -= EFX_HASH_ROTATE(_c, 4);                           \
                _b ^= _a;                                               \
                _b -= EFX_HASH_ROTATE(_a, 14);                          \
                _c ^= _b;                                               \
                _c -= EFX_HASH_ROTATE(_b, 24);                          \
        _NOTE(CONSTANTCONDITION)                                        \
        } while (B_FALSE)


/* Produce a 32-bit hash from 32-bit aligned input */
        __checkReturn           uint32_t
efx_hash_dwords(
        __in_ecount(count)      uint32_t const *input,
        __in                    size_t count,
        __in                    uint32_t init)
{
        uint32_t a;
        uint32_t b;
        uint32_t c;

        /* Set up the initial internal state */
        a = b = c = EFX_HASH_INITIAL_VALUE +
                (((uint32_t)count) * sizeof (uint32_t)) + init;

        /* Handle all but the last three dwords of the input */
        while (count > 3) {
                a += input[0];
                b += input[1];
                c += input[2];
                EFX_HASH_MIX(a, b, c);

                count -= 3;
                input += 3;
        }

        /* Handle the left-overs */
        switch (count) {
        case 3:
                c += input[2];
                /* FALLTHROUGH */
        case 2:
                b += input[1];
                /* FALLTHROUGH */
        case 1:
                a += input[0];
                EFX_HASH_FINALISE(a, b, c);
                break;

        case 0:
                /* Should only get here if count parameter was zero */
                break;
        }

        return (c);
}

#if EFSYS_IS_BIG_ENDIAN

/* Produce a 32-bit hash from arbitrarily aligned input */
        __checkReturn           uint32_t
efx_hash_bytes(
        __in_ecount(length)     uint8_t const *input,
        __in                    size_t length,
        __in                    uint32_t init)
{
        uint32_t a;
        uint32_t b;
        uint32_t c;

        /* Set up the initial internal state */
        a = b = c = EFX_HASH_INITIAL_VALUE + (uint32_t)length + init;

        /* Handle all but the last twelve bytes of the input */
        while (length > 12) {
                a += ((uint32_t)input[0]) << 24;
                a += ((uint32_t)input[1]) << 16;
                a += ((uint32_t)input[2]) << 8;
                a += ((uint32_t)input[3]);
                b += ((uint32_t)input[4]) << 24;
                b += ((uint32_t)input[5]) << 16;
                b += ((uint32_t)input[6]) << 8;
                b += ((uint32_t)input[7]);
                c += ((uint32_t)input[8]) << 24;
                c += ((uint32_t)input[9]) << 16;
                c += ((uint32_t)input[10]) << 8;
                c += ((uint32_t)input[11]);
                EFX_HASH_MIX(a, b, c);
                length -= 12;
                input += 12;
        }

        /* Handle the left-overs */
        switch (length) {
        case 12:
                c += ((uint32_t)input[11]);
                /* Fall-through */
        case 11:
                c += ((uint32_t)input[10]) << 8;
                /* Fall-through */
        case 10:
                c += ((uint32_t)input[9]) << 16;
                /* Fall-through */
        case 9:
                c += ((uint32_t)input[8]) << 24;
                /* Fall-through */
        case 8:
                b += ((uint32_t)input[7]);
                /* Fall-through */
        case 7:
                b += ((uint32_t)input[6]) << 8;
                /* Fall-through */
        case 6:
                b += ((uint32_t)input[5]) << 16;
                /* Fall-through */
        case 5:
                b += ((uint32_t)input[4]) << 24;
                /* Fall-through */
        case 4:
                a += ((uint32_t)input[3]);
                /* Fall-through */
        case 3:
                a += ((uint32_t)input[2]) << 8;
                /* Fall-through */
        case 2:
                a += ((uint32_t)input[1]) << 16;
                /* Fall-through */
        case 1:
                a += ((uint32_t)input[0]) << 24;
                EFX_HASH_FINALISE(a, b, c);
                break;

        case 0:
                /* Should only get here if length parameter was zero */
                break;
        }

        return (c);
}

#elif EFSYS_IS_LITTLE_ENDIAN

/* Produce a 32-bit hash from arbitrarily aligned input */
        __checkReturn           uint32_t
efx_hash_bytes(
        __in_ecount(length)     uint8_t const *input,
        __in                    size_t length,
        __in                    uint32_t init)
{
        uint32_t a;
        uint32_t b;
        uint32_t c;

        /* Set up the initial internal state */
        a = b = c = EFX_HASH_INITIAL_VALUE + (uint32_t)length + init;

        /* Handle all but the last twelve bytes of the input */
        while (length > 12) {
                a += ((uint32_t)input[0]);
                a += ((uint32_t)input[1]) << 8;
                a += ((uint32_t)input[2]) << 16;
                a += ((uint32_t)input[3]) << 24;
                b += ((uint32_t)input[4]);
                b += ((uint32_t)input[5]) << 8;
                b += ((uint32_t)input[6]) << 16;
                b += ((uint32_t)input[7]) << 24;
                c += ((uint32_t)input[8]);
                c += ((uint32_t)input[9]) << 8;
                c += ((uint32_t)input[10]) << 16;
                c += ((uint32_t)input[11]) << 24;
                EFX_HASH_MIX(a, b, c);
                length -= 12;
                input += 12;
        }

        /* Handle the left-overs */
        switch (length) {
        case 12:
                c += ((uint32_t)input[11]) << 24;
                /* FALLTHROUGH */
        case 11:
                c += ((uint32_t)input[10]) << 16;
                /* FALLTHROUGH */
        case 10:
                c += ((uint32_t)input[9]) << 8;
                /* FALLTHROUGH */
        case 9:
                c += ((uint32_t)input[8]);
                /* FALLTHROUGH */
        case 8:
                b += ((uint32_t)input[7]) << 24;
                /* FALLTHROUGH */
        case 7:
                b += ((uint32_t)input[6]) << 16;
                /* FALLTHROUGH */
        case 6:
                b += ((uint32_t)input[5]) << 8;
                /* FALLTHROUGH */
        case 5:
                b += ((uint32_t)input[4]);
                /* FALLTHROUGH */
        case 4:
                a += ((uint32_t)input[3]) << 24;
                /* FALLTHROUGH */
        case 3:
                a += ((uint32_t)input[2]) << 16;
                /* FALLTHROUGH */
        case 2:
                a += ((uint32_t)input[1]) << 8;
                /* FALLTHROUGH */
        case 1:
                a += ((uint32_t)input[0]);
                EFX_HASH_FINALISE(a, b, c);
                break;

        case 0:
                /* Should only get here if length parameter was zero */
                break;
        }

        return (c);
}

#else

#error "Neither of EFSYS_IS_{BIG,LITTLE}_ENDIAN is set"

#endif