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

}