From 8db6403233d2f78e3bb6248bc80255a480aa0df6 Mon Sep 17 00:00:00 2001 From: Federico Angelilli Date: Thu, 30 May 2024 00:22:34 +0200 Subject: Add any_hash --- any_hash.h | 360 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 360 insertions(+) create mode 100644 any_hash.h (limited to 'any_hash.h') diff --git a/any_hash.h b/any_hash.h new file mode 100644 index 0000000..088c444 --- /dev/null +++ b/any_hash.h @@ -0,0 +1,360 @@ +#ifndef ANY_HASH_INCLUDE +#define ANY_HASH_INCLUDE + +#include +#include + +#ifndef ANY_HASH_NO_XXH32 + +typedef uint32_t any_hash32_t; + +any_hash32_t any_hash_xxh32(const uint8_t *data, size_t length, any_hash32_t seed); + +#endif + +#ifndef ANY_HASH_NO_XXH64 + +typedef uint64_t any_hash64_t; + +any_hash64_t any_hash_xxh64(const uint8_t *data, size_t length, any_hash64_t seed); + +#endif + +#endif + +#ifdef ANY_HASH_IMPLEMENT + +#include + +#define ANY_HASH_ALIGNED 0 + +#define ANY_HASH_ROTL1 1 +#define ANY_HASH_ROTL2 7 +#define ANY_HASH_ROTL3 12 +#define ANY_HASH_ROTL4 18 + +#ifndef ANY_HASH_LIKELY +#ifdef __has_builtin +#if __has_builtin(__builtin_expect) +#define ANY_HASH_LIKELY(...) __builtin_expect(!!(__VA_ARGS__), 1) +#endif +#endif + +#ifndef ANY_HASH_LIKELY +#define ANY_HASH_LIKELY(...) +#endif +#endif + +#ifndef ANY_HASH_RUNTIME_ENDIAN +#ifndef ANY_HASH_LE +#if defined(__BYTE_ORDER__) && __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__ || \ + defined(__BIG_ENDIAN__) || defined(__BIG_ENDIAN) || defined(_BIG_ENDIAN) +#define ANY_HASH_LE 0 +#else +#define ANY_HASH_LE 1 +#endif +#endif + +static bool any_hash_little_endian = ANY_HASH_LE; +#else +static int any_hash_test_endian = 1; +static bool any_hash_little_endian = *((char *)&any_hash_test_endian); +#endif + + +#ifndef ANY_HASH_NO_XXH32 + +#define ANY_HASH_BYTES32 sizeof(any_hash32_t) +#define ANY_HASH_DATALEN32 16 + +#define ANY_HASH_ALIGN32 3 +#define ANY_HASH_ROUND32 13 + +#define ANY_HASH_AV32_1 15 +#define ANY_HASH_AV32_2 13 +#define ANY_HASH_AV32_3 16 + +#define ANY_HASH_PROC32_1 17 +#define ANY_HASH_PROC32_2 11 + +#define ANY_HASH_PRIME32_1 2654435761u +#define ANY_HASH_PRIME32_2 2246822519u +#define ANY_HASH_PRIME32_3 3266489917u +#define ANY_HASH_PRIME32_4 668265263u +#define ANY_HASH_PRIME32_5 374761393u + +#ifdef __has_builtin +#if __has_builtin(__builtin_bswap32) +#define ANY_HASH_SWAP32 __builtin_bswap32 +#endif + +#if __has_builtin(__builtin_rotateleft32) +#define ANY_HASH_ROTL32 __builtin_rotateleft32 +#endif +#endif + +#ifndef ANY_HASH_SWAP32 +#define ANY_HASH_SWAP32 any_hash_swap32 + +static inline any_hash32_t any_hash_swap32(any_hash32_t hash) +{ + return ((hash << 24) & 0xff000000) | + ((hash << 8) & 0x00ff0000) | + ((hash << 8) & 0x0000ff00) | + ((hash << 24) & 0x000000ff); +} +#endif + +#ifndef ANY_HASH_ROTL32 +#define ANY_HASH_ROTL32 any_hash_rotl32 + +static inline any_hash32_t any_hash_rotl32(any_hash32_t hash, uint32_t bits) +{ + return (hash << bits) | (hash >> (32 - bits)); +} +#endif + + +static inline any_hash32_t any_hash_fetch32(const uint8_t *data, int_fast32_t align) +{ + if (ANY_HASH_LIKELY(align == ANY_HASH_ALIGNED)) + return any_hash_little_endian + ? *(const any_hash32_t *)data + : ANY_HASH_SWAP32(*(const any_hash32_t *)data); + + any_hash32_t hash; + memcpy(&hash, data, 4); + + return any_hash_little_endian + ? hash + : ANY_HASH_SWAP32(hash); +} + +static inline any_hash32_t any_hash_avalanche32(any_hash32_t hash) +{ + hash ^= hash >> ANY_HASH_AV32_1; + hash *= ANY_HASH_PRIME32_2; + hash ^= hash >> ANY_HASH_AV32_2; + hash *= ANY_HASH_PRIME32_3; + hash ^= hash >> ANY_HASH_AV32_3; + return hash; +} + +static any_hash32_t any_hash_round32(any_hash32_t hash, any_hash32_t next) +{ + hash += next * ANY_HASH_PRIME32_2; + hash = ANY_HASH_ROTL32(hash, ANY_HASH_ROUND32); + hash *= ANY_HASH_PRIME32_1; + return hash; +} + +any_hash32_t any_hash_xxh32(const uint8_t *data, size_t length, any_hash32_t seed) +{ + any_hash32_t hash; + const int_fast32_t align = (uintptr_t)data & ANY_HASH_ALIGN32; + + if (length >= ANY_HASH_DATALEN32) { + const uint8_t *const end = data + length - ANY_HASH_DATALEN32; + + any_hash32_t st1 = seed + ANY_HASH_PRIME32_1 + ANY_HASH_PRIME32_2; + any_hash32_t st2 = seed + ANY_HASH_PRIME32_2; + any_hash32_t st3 = seed; + any_hash32_t st4 = seed - ANY_HASH_PRIME32_1; + + do { + st1 = any_hash_round32(st1, any_hash_fetch32(data, align)); + data += ANY_HASH_BYTES32; + st2 = any_hash_round32(st2, any_hash_fetch32(data, align)); + data += ANY_HASH_BYTES32; + st3 = any_hash_round32(st3, any_hash_fetch32(data, align)); + data += ANY_HASH_BYTES32; + st4 = any_hash_round32(st4, any_hash_fetch32(data, align)); + data += ANY_HASH_BYTES32; + } while (data <= end); + + hash = ANY_HASH_ROTL32(st1, ANY_HASH_ROTL1) + ANY_HASH_ROTL32(st2, ANY_HASH_ROTL2) + + ANY_HASH_ROTL32(st3, ANY_HASH_ROTL3) + ANY_HASH_ROTL32(st4, ANY_HASH_ROTL4); + } else + hash = seed + ANY_HASH_PRIME32_5; + + hash += length; + length &= (ANY_HASH_DATALEN32 - 1); + + while (length >= 4) { + hash += any_hash_fetch32(data, align) * ANY_HASH_PRIME32_3; + hash = ANY_HASH_ROTL32(hash, ANY_HASH_PROC32_1) * ANY_HASH_PRIME32_4; + data += ANY_HASH_BYTES32; + length -= ANY_HASH_BYTES32; + } + + while (length > 0) { + hash += (*data++) * ANY_HASH_PRIME32_5; + hash = ANY_HASH_ROTL32(hash, ANY_HASH_PROC32_2) * ANY_HASH_PRIME32_1; + --length; + } + + return any_hash_avalanche32(hash); +} + +#endif + +#ifndef ANY_HASH_NO_XXH64 + +#define ANY_HASH_BYTES64 sizeof(any_hash64_t) +#define ANY_HASH_DATALEN64 32 + +#define ANY_HASH_ALIGN64 7 +#define ANY_HASH_ROUND64 31 + +#define ANY_HASH_AV64_1 33 +#define ANY_HASH_AV64_2 29 +#define ANY_HASH_AV64_3 32 + +#define ANY_HASH_PROC64_1 27 +#define ANY_HASH_PROC64_2 23 +#define ANY_HASH_PROC64_3 11 + +#define ANY_HASH_PRIME64_1 11400714785074694791ull +#define ANY_HASH_PRIME64_2 14029467366897019727ull +#define ANY_HASH_PRIME64_3 1609587929392839161ull +#define ANY_HASH_PRIME64_4 9650029242287828579ull +#define ANY_HASH_PRIME64_5 2870177450012600261ull + +#ifdef __has_builtin +#if __has_builtin(__builtin_bswap64) +#define ANY_HASH_SWAP64 __builtin_bswap64 +#endif + +#if __has_builtin(__builtin_rotateleft64) +#define ANY_HASH_ROTL64 __builtin_rotateleft64 +#endif +#endif + +#ifndef ANY_HASH_SWAP64 +#define ANY_HASH_SWAP64 any_hash_swap64 + +static inline any_hash64_t any_hash_swap64(any_hash64_t hash) +{ + return ((hash << 56) & 0xff00000000000000ull) | + ((hash << 40) & 0x00ff000000000000ull) | + ((hash << 24) & 0x0000ff0000000000ull) | + ((hash << 8) & 0x000000ff00000000ull) | + ((hash >> 8) & 0x00000000ff000000ull) | + ((hash >> 24) & 0x0000000000ff0000ull) | + ((hash >> 40) & 0x000000000000ff00ull) | + ((hash >> 56) & 0x00000000000000ffull); +} +#endif + +#ifndef ANY_HASH_ROTL64 +#define ANY_HASH_ROTL64 any_hash_rotl64 + +static inline any_hash64_t any_hash_rotl64(any_hash64_t hash, uint32_t bits) +{ + return (hash << bits) | (hash >> (64 - bits)); +} +#endif + +static inline any_hash64_t any_hash_fetch64(const uint8_t *data, int_fast32_t align) +{ + if (ANY_HASH_LIKELY(align == ANY_HASH_ALIGNED)) + return any_hash_little_endian + ? *(const any_hash64_t *)data + : ANY_HASH_SWAP64(*(const any_hash64_t *)data); + + any_hash64_t hash; + memcpy(&hash, data, 8); + + return any_hash_little_endian + ? hash + : ANY_HASH_SWAP64(hash); +} + +static inline any_hash64_t any_hash_avalanche64(any_hash64_t hash) +{ + hash ^= hash >> ANY_HASH_AV64_1; + hash *= ANY_HASH_PRIME64_2; + hash ^= hash >> ANY_HASH_AV64_2; + hash *= ANY_HASH_PRIME64_3; + hash ^= hash >> ANY_HASH_AV64_3; + return hash; +} + +static any_hash64_t any_hash_round64(any_hash64_t hash, any_hash64_t next) +{ + hash += next * ANY_HASH_PRIME64_2; + hash = ANY_HASH_ROTL64(hash, ANY_HASH_ROUND64); + hash *= ANY_HASH_PRIME64_1; + return hash; +} + +static any_hash64_t any_hash_round64_merge(any_hash64_t hash, any_hash64_t next) +{ + hash ^= any_hash_round64(0, next); + hash = hash * ANY_HASH_PRIME64_1 + ANY_HASH_PRIME64_4; + return hash; +} + +any_hash64_t any_hash_xxh64(const uint8_t *data, size_t length, any_hash64_t seed) +{ + any_hash64_t hash; + const int_fast32_t align = (uintptr_t)data & ANY_HASH_ALIGN64; + + if (length >= ANY_HASH_DATALEN64) { + const uint8_t *const end = data + length - ANY_HASH_DATALEN64; + + any_hash64_t st1 = seed + ANY_HASH_PRIME64_1 + ANY_HASH_PRIME64_2; + any_hash64_t st2 = seed + ANY_HASH_PRIME64_2; + any_hash64_t st3 = seed; + any_hash64_t st4 = seed - ANY_HASH_PRIME64_1; + + do { + st1 = any_hash_round64(st1, any_hash_fetch64(data, align)); + data += ANY_HASH_BYTES64; + st2 = any_hash_round64(st2, any_hash_fetch64(data, align)); + data += ANY_HASH_BYTES64; + st3 = any_hash_round64(st3, any_hash_fetch64(data, align)); + data += ANY_HASH_BYTES64; + st4 = any_hash_round64(st4, any_hash_fetch64(data, align)); + data += ANY_HASH_BYTES64; + } while (data <= end); + + hash = ANY_HASH_ROTL64(st1, ANY_HASH_ROTL1) + ANY_HASH_ROTL64(st2, ANY_HASH_ROTL2) + + ANY_HASH_ROTL64(st3, ANY_HASH_ROTL3) + ANY_HASH_ROTL64(st4, ANY_HASH_ROTL4); + + hash = any_hash_round64_merge(hash, st1); + hash = any_hash_round64_merge(hash, st2); + hash = any_hash_round64_merge(hash, st3); + hash = any_hash_round64_merge(hash, st4); + } else + hash = seed + ANY_HASH_PRIME64_5; + + hash += length; + length &= (ANY_HASH_DATALEN64 - 1); + + while (length >= 8) { + hash ^= any_hash_round64(0, any_hash_fetch64(data, align)); + hash = ANY_HASH_ROTL64(hash, ANY_HASH_PROC64_1) * ANY_HASH_PRIME64_1 + ANY_HASH_PRIME64_4; + data += ANY_HASH_BYTES64; + length -= ANY_HASH_BYTES64; + } + + while (length >= 4) { + hash ^= (any_hash64_t)(any_hash_fetch32(data, align)) * ANY_HASH_PRIME64_1; + hash = ANY_HASH_ROTL64(hash, ANY_HASH_PROC64_2) * ANY_HASH_PRIME64_2 + ANY_HASH_PRIME64_3; + data += ANY_HASH_BYTES32; + length -= ANY_HASH_BYTES32; + } + + while (length > 0) { + hash ^= (*data++) * ANY_HASH_PRIME64_5; + hash = ANY_HASH_ROTL64(hash, ANY_HASH_PROC64_3) * ANY_HASH_PRIME64_1; + --length; + } + + return any_hash_avalanche64(hash); +} + +#endif + +#endif -- cgit v1.2.3