Revision control
Copy as Markdown
// 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);
}