tommyhash.h

Go to the documentation of this file.

// SPDX-License-Identifier: BSD-2-Clause
// Copyright (C) 2010 Andrea Mazzoleni
 
#ifndef TOMMY_HASH_H
#define TOMMY_HASH_H
 
#include "tommytypes.h"
#include <string.h> /* for strlen */
 
/******************************************************************************/
/* hash */
 
TOMMY_API tommy_uint32_t tommy_hash_u32(tommy_uint32_t init_val, const void* void_key, tommy_size_t key_len);
 
TOMMY_API tommy_uint64_t tommy_hash_u64(tommy_uint64_t init_val, const void* void_key, tommy_size_t key_len);
 
tommy_inline tommy_uint32_t tommy_strhash_u32(tommy_uint32_t init_val, const void* void_key)
{
        return tommy_hash_u32(init_val, void_key, strlen(tommy_cast(const char*, void_key)));
}
 
tommy_inline tommy_uint64_t tommy_strhash_u64(tommy_uint64_t init_val, const void* void_key)
{
        return tommy_hash_u64(init_val, void_key, strlen(tommy_cast(const char*, void_key)));
}
 
tommy_inline tommy_uint32_t tommy_inthash_u32(tommy_uint32_t key)
{
        key -= key << 6;
        key ^= key >> 17;
        key -= key << 9;
        key ^= key << 4;
        key -= key << 3;
        key ^= key << 10;
        key ^= key >> 15;
 
        return key;
}
 
tommy_inline tommy_uint64_t tommy_inthash_u64(tommy_uint64_t key)
{
        key = ~key + (key << 21);
        key = key ^ (key >> 24);
        key = key + (key << 3) + (key << 8);
        key = key ^ (key >> 14);
        key = key + (key << 2) + (key << 4);
        key = key ^ (key >> 28);
        key = key + (key << 31);
 
        return key;
}
 
tommy_inline tommy_uint32_t tommy_mulhash_u32(tommy_uint32_t key)
{
        key ^= key >> 16;
        key *= 0x85ebca6bU;
        key ^= key >> 13;
        key *= 0xc2b2ae35U;
        key ^= key >> 16;
 
        return key;
}
 
tommy_inline tommy_uint64_t tommy_mulhash_u64(tommy_uint64_t key)
{
        key ^= key >> 30;
        key *= 0xbf58476d1ce4e5b9ULL;
        key ^= key >> 27;
        key *= 0x94d049bb133111ebULL;
        key ^= key >> 31;
 
        return key;
}
 
/******************************************************************************/
/* multiplication */
 
#if defined(_MSC_VER) && defined(_M_X64)
/*
 * MSVC x64 does not support inline assembly, so use its full-product intrinsic.
 */
#pragma intrinsic(_umul128)
tommy_inline void tommy_mum(tommy_uint64_t* A, tommy_uint64_t* B)
{
        tommy_uint64_t high;
        tommy_uint64_t low = _umul128(*A, *B, &high);
        *A = low;
        *B = high;
}
#elif defined(_MSC_VER) && defined(_M_ARM64)
#pragma intrinsic(__umulh)
tommy_inline void tommy_mum(tommy_uint64_t* A, tommy_uint64_t* B)
{
        tommy_uint64_t a = *A;
        tommy_uint64_t b = *B;
        *A = a * b;
        *B = __umulh(a, b);
}
#elif defined(__x86_64__) && (defined(__GNUC__) || defined(__clang__))
tommy_inline void tommy_mum(tommy_uint64_t* A, tommy_uint64_t* B)
{
        tommy_uint64_t a = *A;
        tommy_uint64_t b = *B;
        tommy_uint64_t low, high;
 
        /* require a register to avoid Clang spilling the operand before mulq */
        __asm__ (
                "mulq %3"
                : "=a" (low), "=d" (high)
                : "a" (a), "r" (b)
                : "cc"
        );
 
        *A = low;
        *B = high;
}
#elif defined(__SIZEOF_INT128__)
tommy_inline void tommy_mum(tommy_uint64_t* A, tommy_uint64_t* B)
{
        __uint128_t product = (__uint128_t)*A * *B;
        *A = product;
        *B = product >> 64;
}
#elif defined(__aarch64__) && (defined(__GNUC__) || defined(__clang__))
/*
 * Keep this after __SIZEOF_INT128__ because the assembly path failed optimized
 * hash tests on Apple clang 21.0.0. See https://github.com/amadvance/snapraid/issues/43.
 */
tommy_inline void tommy_mum(tommy_uint64_t* A, tommy_uint64_t* B)
{
        tommy_uint64_t a = *A;
        tommy_uint64_t b = *B;
        tommy_uint64_t low = a * b;
        tommy_uint64_t high;
        __asm__ (
                "umulh %0, %1, %2"
                : "=r" (high)
                : "r" (a), "r" (b)
        );
        *A = low;
        *B = high;
}
#else
tommy_inline void tommy_mum(tommy_uint64_t* A, tommy_uint64_t* B)
{
        tommy_uint64_t a = *A;
        tommy_uint64_t b = *B;
        tommy_uint64_t a_lo = (tommy_uint32_t)a;
        tommy_uint64_t a_hi = a >> 32;
        tommy_uint64_t b_lo = (tommy_uint32_t)b;
        tommy_uint64_t b_hi = b >> 32;
        tommy_uint64_t p0 = a_lo * b_lo;
        tommy_uint64_t p1 = a_lo * b_hi;
        tommy_uint64_t p2 = a_hi * b_lo;
        tommy_uint64_t p3 = a_hi * b_hi;
 
        /* retain the carry from the middle words in the high half */
        tommy_uint64_t middle = p1 + (p0 >> 32) + (tommy_uint32_t)p2;
        tommy_uint64_t low = (middle << 32) | (tommy_uint32_t)p0;
        tommy_uint64_t high = p3 + (middle >> 32) + (p2 >> 32);
        *A = low;
        *B = high;
}
#endif
 
#endif