// Copyright (C) 2012-2014 Jean-Philippe Aumasson
// Copyright (C) 2012-2014 Daniel J. Bernstein <djb@cr.yp.to>
// Copyright (C) 2016 Intel Corporation.
// SPDX-License-Identifier: CC0-1.0

#include <QtCore/qassert.h>
#include <QtCore/qcompilerdetection.h>
#include <QtCore/qendian.h>

#ifdef Q_CC_GNU
#  define DECL_HOT_FUNCTION       __attribute__((hot))
#else
#  define DECL_HOT_FUNCTION
#endif

#include <cstdint>

QT_USE_NAMESPACE

namespace {

// This is an inlined version of the SipHash implementation that is
// trying to avoid some memcpy's from uint64 to uint8[] and back.

#define ROTL(x, b) (((x) << (b)) | ((x) >> (sizeof(x) * 8 - (b))))

#define SIPROUND                                                                       \
do {                                                                                   \
            v0 += v1;                                                                  \
            v1 = ROTL(v1, 13);                                                         \
            v1 ^= v0;                                                                  \
            v0 = ROTL(v0, 32);                                                         \
            v2 += v3;                                                                  \
            v3 = ROTL(v3, 16);                                                         \
            v3 ^= v2;                                                                  \
            v0 += v3;                                                                  \
            v3 = ROTL(v3, 21);                                                         \
            v3 ^= v0;                                                                  \
            v2 += v1;                                                                  \
            v1 = ROTL(v1, 17);                                                         \
            v1 ^= v2;                                                                  \
            v2 = ROTL(v2, 32);                                                         \
} while (0)

template <int cROUNDS = 2, int dROUNDS = 4> struct SipHash64
{
    /* "somepseudorandomlygeneratedbytes" */
    uint64_t v0 = 0x736f6d6570736575ULL;
    uint64_t v1 = 0x646f72616e646f6dULL;
    uint64_t v2 = 0x6c7967656e657261ULL;
    uint64_t v3 = 0x7465646279746573ULL;
    uint64_t b;
    uint64_t k0;
    uint64_t k1;

    inline SipHash64(uint64_t fulllen, uint64_t seed, uint64_t seed2);
    inline void addBlock(const uint8_t *in, size_t inlen);
    inline uint64_t finalize(const uint8_t *in, size_t left);
};

template <int cROUNDS, int dROUNDS>
SipHash64<cROUNDS, dROUNDS>::SipHash64(uint64_t inlen, uint64_t seed, uint64_t seed2)
{
    b = inlen << 56;
    k0 = seed;
    k1 = seed2;
    v3 ^= k1;
    v2 ^= k0;
    v1 ^= k1;
    v0 ^= k0;
}

template <int cROUNDS, int dROUNDS> DECL_HOT_FUNCTION void
SipHash64<cROUNDS, dROUNDS>::addBlock(const uint8_t *in, size_t inlen)
{
    Q_ASSERT((inlen & 7ULL) == 0);
    int i;
    const uint8_t *end = in + inlen;
    for (; in != end; in += 8) {
        uint64_t m = qFromUnaligned<uint64_t>(in);
        v3 ^= m;

        for (i = 0; i < cROUNDS; ++i)
            SIPROUND;

        v0 ^= m;
    }
}

template <int cROUNDS, int dROUNDS> DECL_HOT_FUNCTION uint64_t
SipHash64<cROUNDS, dROUNDS>::finalize(const uint8_t *in, size_t left)
{
    int i;
    switch (left) {
    case 7:
        b |= ((uint64_t)in[6]) << 48;
        Q_FALLTHROUGH();
    case 6:
        b |= ((uint64_t)in[5]) << 40;
        Q_FALLTHROUGH();
    case 5:
        b |= ((uint64_t)in[4]) << 32;
        Q_FALLTHROUGH();
    case 4:
        b |= ((uint64_t)in[3]) << 24;
        Q_FALLTHROUGH();
    case 3:
        b |= ((uint64_t)in[2]) << 16;
        Q_FALLTHROUGH();
    case 2:
        b |= ((uint64_t)in[1]) << 8;
        Q_FALLTHROUGH();
    case 1:
        b |= ((uint64_t)in[0]);
        break;
    case 0:
        break;
    }

    v3 ^= b;

    for (i = 0; i < cROUNDS; ++i)
        SIPROUND;

    v0 ^= b;

    v2 ^= 0xff;

    for (i = 0; i < dROUNDS; ++i)
        SIPROUND;

    b = v0 ^ v1 ^ v2 ^ v3;
    return b;
}
#undef SIPROUND

// This is a "SipHash" implementation adopted for 32bit platforms. It performs
// basically the same operations as the 64bit version using 4 byte at a time
// instead of 8.
//
// To make this work, we also need to change the constants for the mixing
// rotations in ROTL. We're simply using half of the 64bit constants, rounded up
// for odd numbers.
//
// For the v0-v4 constants, simply use the first four bytes of the 64 bit versions.
//

#define SIPROUND                                                                       \
do {                                                                                   \
            v0 += v1;                                                                  \
            v1 = ROTL(v1, 7);                                                          \
            v1 ^= v0;                                                                  \
            v0 = ROTL(v0, 16);                                                         \
            v2 += v3;                                                                  \
            v3 = ROTL(v3, 8);                                                          \
            v3 ^= v2;                                                                  \
            v0 += v3;                                                                  \
            v3 = ROTL(v3, 11);                                                         \
            v3 ^= v0;                                                                  \
            v2 += v1;                                                                  \
            v1 = ROTL(v1, 9);                                                          \
            v1 ^= v2;                                                                  \
            v2 = ROTL(v2, 16);                                                         \
} while (0)

template <int cROUNDS = 2, int dROUNDS = 4> struct SipHash32
{
    /* "somepseudorandomlygeneratedbytes" */
    uint v0 = 0x736f6d65U;
    uint v1 = 0x646f7261U;
    uint v2 = 0x6c796765U;
    uint v3 = 0x74656462U;
    uint b;
    uint k0;
    uint k1;

    inline SipHash32(size_t fulllen, uint seed, uint seed2);
    inline void addBlock(const uint8_t *in, size_t inlen);
    inline uint finalize(const uint8_t *in, size_t left);
};

template <int cROUNDS, int dROUNDS> inline
        SipHash32<cROUNDS, dROUNDS>::SipHash32(size_t inlen, uint seed, uint seed2)
{
    uint k0 = seed;
    uint k1 = seed2;
    b = inlen << 24;
    v3 ^= k1;
    v2 ^= k0;
    v1 ^= k1;
    v0 ^= k0;
}

template <int cROUNDS, int dROUNDS> inline DECL_HOT_FUNCTION void
SipHash32<cROUNDS, dROUNDS>::addBlock(const uint8_t *in, size_t inlen)
{
    Q_ASSERT((inlen & 3ULL) == 0);
    int i;
    const uint8_t *end = in + inlen;
    for (; in != end; in += 4) {
        uint m = qFromUnaligned<uint>(in);
        v3 ^= m;

        for (i = 0; i < cROUNDS; ++i)
            SIPROUND;

        v0 ^= m;
    }
}

template <int cROUNDS, int dROUNDS> inline DECL_HOT_FUNCTION uint
SipHash32<cROUNDS, dROUNDS>::finalize(const uint8_t *in, size_t left)
{
    int i;
    switch (left) {
    case 3:
        b |= ((uint)in[2]) << 16;
        Q_FALLTHROUGH();
    case 2:
        b |= ((uint)in[1]) << 8;
        Q_FALLTHROUGH();
    case 1:
        b |= ((uint)in[0]);
        break;
    case 0:
        break;
    }

    v3 ^= b;

    for (i = 0; i < cROUNDS; ++i)
        SIPROUND;

    v0 ^= b;

    v2 ^= 0xff;

    for (i = 0; i < dROUNDS; ++i)
        SIPROUND;

    b = v0 ^ v1 ^ v2 ^ v3;
    return b;
}
#undef SIPROUND
#undef ROTL

// Use SipHash-1-2, which has similar performance characteristics as
// Qt 4's hash implementation, instead of the SipHash-2-4 default
template <int cROUNDS = 1, int dROUNDS = 2>
using SipHash = std::conditional_t<sizeof(void *) == 8,
                                   SipHash64<cROUNDS, dROUNDS>, SipHash32<cROUNDS, dROUNDS>>;

} // unnamed namespace

Q_NEVER_INLINE DECL_HOT_FUNCTION
static size_t siphash(const uint8_t *in, size_t inlen, size_t seed, size_t seed2)
{
    constexpr size_t TailSizeMask = sizeof(void *) - 1;
    SipHash<> hasher(inlen, seed, seed2);
    hasher.addBlock(in, inlen & ~TailSizeMask);
    return hasher.finalize(in + (inlen & ~TailSizeMask), inlen & TailSizeMask);
}