From b844718a1687424b2748608cbb52fb4012417fe5 Mon Sep 17 00:00:00 2001 From: steven-na Date: Fri, 21 Aug 2026 16:01:34 -0700 Subject: Hashmap usable i think, now with proper 3rd party algorithm --- README.md | 2 +- include/a5hash.h | 874 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/map.c | 118 ++++---- src/map.h | 4 +- 4 files changed, 929 insertions(+), 69 deletions(-) create mode 100644 include/a5hash.h diff --git a/README.md b/README.md index 1010836..831e3ac 100644 --- a/README.md +++ b/README.md @@ -20,4 +20,4 @@ - [ ] strng_view_t - [ ] thread_pool - [ ] vec2sw - - [ ] version.c + - [ ] hashmap diff --git a/include/a5hash.h b/include/a5hash.h new file mode 100644 index 0000000..3fcceb6 --- /dev/null +++ b/include/a5hash.h @@ -0,0 +1,874 @@ +/** + * @file a5hash.h + * + * @version 5.25 + * + * @brief The header file for the "a5hash" 64-bit hash function, "a5hash32" + * 32-bit hash function, "a5hash128" 128-bit hash function, and "a5rand" + * 64-bit PRNG. + * + * The source code is written in ISO C99, with full C++ compliance enabled + * conditionally and automatically when compiled with a C++ compiler. + * + * Description is available at https://github.com/avaneev/a5hash + * + * Email: aleksey.vaneev@gmail.com or info@voxengo.com + * + * LICENSE: + * + * Copyright (c) 2025 Aleksey Vaneev + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + */ + +#ifndef A5HASH_INCLUDED +#define A5HASH_INCLUDED + +#define A5HASH_VER_STR "5.25" ///< A5HASH source code version string. + +/** + * @def A5HASH_NS_CUSTOM + * @brief If this macro is defined externally, all symbols will be placed into + * the C++ namespace specified by this macro and will not be exported to the + * global namespace. WARNING: if the macro's value is empty, the symbols will + * be placed into the global namespace anyway. + */ + +/** + * @def A5HASH_U64_C( x ) + * @brief Macro that defines a numeric value as unsigned 64-bit value. + * + * @param x Value. + */ + +/** + * @def A5HASH_NOEX + * @brief Macro that defines the "noexcept" function specifier for C++ + * environment. + */ + +/** + * @def A5HASH_NULL + * @brief Macro that defines "nullptr" value, for C++ guidelines compliance. + */ + +/** + * @def A5HASH_NS + * @brief Macro that defines the actual implementation namespace in C++ + * environment, with export of relevant symbols to the global namespace + * (if @ref A5HASH_NS_CUSTOM is undefined). + */ + +#if defined( __cplusplus ) + + #include + + #if __cplusplus >= 201103L + + #include + + #define A5HASH_U64_C( x ) UINT64_C( x ) + #define A5HASH_NOEX noexcept + #define A5HASH_NULL nullptr + + #else // __cplusplus >= 201103L + + #include + + #define A5HASH_U64_C( x ) (uint64_t) x + #define A5HASH_NOEX throw() + #define A5HASH_NULL NULL + + #endif // __cplusplus >= 201103L + + #if defined( A5HASH_NS_CUSTOM ) + #define A5HASH_NS A5HASH_NS_CUSTOM + #else // defined( A5HASH_NS_CUSTOM ) + #define A5HASH_NS a5hash_impl + #endif // defined( A5HASH_NS_CUSTOM ) + +#else // defined( __cplusplus ) + + #include + #include + + #define A5HASH_U64_C( x ) (uint64_t) x + #define A5HASH_NOEX + #define A5HASH_NULL NULL + +#endif // defined( __cplusplus ) + +#if defined( _MSC_VER ) + #include +#endif // defined( _MSC_VER ) + +#define A5HASH_VAL10 A5HASH_U64_C( 0xAAAAAAAAAAAAAAAA ) ///< `10` bit-pairs. +#define A5HASH_VAL01 A5HASH_U64_C( 0x5555555555555555 ) ///< `01` bit-pairs. + +/** + * @def A5HASH_ICC_GCC + * @brief Macro that denotes the use of ICC classic compiler with GCC-style + * built-in functions. + */ + +#if defined( __INTEL_COMPILER ) && __INTEL_COMPILER >= 1300 && \ + !defined( _MSC_VER ) + + #define A5HASH_ICC_GCC + +#endif // ICC check + +/** + * @def A5HASH_GCC_BUILTINS + * @brief Macro that denotes availability of GCC-style built-in functions. + */ + +#if defined( __GNUC__ ) || defined( __clang__ ) || \ + defined( __IBMC__ ) || defined( __IBMCPP__ ) || defined( A5HASH_ICC_GCC ) + + #define A5HASH_GCC_BUILTINS + +#endif // GCC built-ins check + +/** + * @def A5HASH_BMI2 + * @brief Macro that denotes availability of the `mulx` intrinsic + * (MSVC-compatible compilers only). + */ + +#if defined( _MSC_VER ) + #if defined( __BMI2__ ) || ( !defined( A5HASH_GCC_BUILTINS ) && \ + defined( _M_AMD64 ) && defined( __AVX2__ ) && \ + ( defined( __INTEL_COMPILER ) || _MSC_VER >= 1900 )) + + #include + #define A5HASH_BMI2 + + #else // BMI2 + + #include + + #endif // BMI2 +#endif // defined( _MSC_VER ) + +/** + * @def A5HASH_STATIC + * @brief Macro that defines a function as "static". + */ + +#if ( defined( __cplusplus ) && __cplusplus >= 201703L ) || \ + ( defined( __STDC_VERSION__ ) && __STDC_VERSION__ >= 202311L ) + + #define A5HASH_STATIC [[maybe_unused]] static + +#elif defined( A5HASH_GCC_BUILTINS ) + + #define A5HASH_STATIC static __attribute__((unused)) + +#else // defined( A5HASH_GCC_BUILTINS ) + + #define A5HASH_STATIC static + +#endif // defined( A5HASH_GCC_BUILTINS ) + +/** + * @def A5HASH_INLINE + * @brief Macro that defines a function as inlinable at the compiler's + * discretion. + */ + +#define A5HASH_INLINE A5HASH_STATIC inline + +/** + * @def A5HASH_INLINE_F + * @brief Macro to force code inlining. + */ + +#if defined( __LP64__ ) || defined( _LP64 ) || \ + !( SIZE_MAX <= 0xFFFFFFFFU ) || ( defined( UINTPTR_MAX ) && \ + !( UINTPTR_MAX <= 0xFFFFFFFFU )) || defined( __x86_64__ ) || \ + defined( __aarch64__ ) || defined( _M_AMD64 ) || defined( _M_ARM64 ) + + #if defined( A5HASH_GCC_BUILTINS ) + + #define A5HASH_INLINE_F A5HASH_INLINE __attribute__((always_inline)) + + #elif defined( _MSC_VER ) + + #define A5HASH_INLINE_F A5HASH_STATIC __forceinline + + #endif // defined( _MSC_VER ) + +#endif // 64-bit platform check + +#if !defined( A5HASH_INLINE_F ) + #define A5HASH_INLINE_F A5HASH_INLINE +#endif // !defined( A5HASH_INLINE_F ) + +#if defined( A5HASH_NS ) + +namespace A5HASH_NS { + +using std :: memcpy; +using std :: size_t; + +#if __cplusplus >= 201103L + + using std :: uint32_t; + using std :: uint64_t; + using uint8_t = unsigned char; ///< For C++ type aliasing compliance. + +#endif // __cplusplus >= 201103L + +#endif // defined( A5HASH_NS ) + +/** + * @{ + * @brief Load unsigned value of the specific bit size from memory. + * + * @param p Load address. + */ + +A5HASH_INLINE_F uint32_t a5hash_lu32( const uint8_t* const p ) A5HASH_NOEX +{ + uint32_t v; + memcpy( &v, p, 4 ); + + return( v ); +} + +A5HASH_INLINE_F uint64_t a5hash_lu64( const uint8_t* const p ) A5HASH_NOEX +{ + uint64_t v; + memcpy( &v, p, 8 ); + + return( v ); +} + +/** @} */ + +/** + * @brief 64-bit by 64-bit unsigned multiplication producing a 128-bit result. + * + * @param u Multiplier 1. + * @param v Multiplier 2. + * @param[out] rl The lower half of the 128-bit result. + * @param[out] rh The upper half of the 128-bit result. + */ + +A5HASH_INLINE_F void a5hash_umul128( const uint64_t u, const uint64_t v, + uint64_t* const rl, uint64_t* const rh ) A5HASH_NOEX +{ +#if defined( A5HASH_BMI2 ) + + *rl = _mulx_u64( u, v, rh ); + +#elif defined( _MSC_VER ) && ( defined( _M_ARM64 ) || defined( _M_ARM64EC ) || \ + ( defined( __INTEL_COMPILER ) && defined( _M_AMD64 ))) + + *rl = u * v; + *rh = __umulh( u, v ); + +#elif defined( _MSC_VER ) && ( defined( _M_AMD64 ) || defined( _M_IA64 )) + + *rl = _umul128( u, v, rh ); + +#elif defined( __SIZEOF_INT128__ ) || \ + ( defined( A5HASH_ICC_GCC ) && defined( __x86_64__ )) + + __uint128_t r = u; + r *= v; + + *rl = (uint64_t) r; + *rh = (uint64_t) ( r >> 64 ); + +#elif ( defined( __IBMC__ ) || defined( __IBMCPP__ )) && defined( __LP64__ ) + + *rl = u * v; + *rh = __mulhdu( u, v ); + +#else // defined( __IBMC__ ) + + // _umul128() code for 32-bit systems, adapted from Hacker's Delight, + // Henry S. Warren, Jr. + + *rl = u * v; + + const uint32_t u0 = (uint32_t) u; + const uint32_t v0 = (uint32_t) v; + const uint64_t w0 = (uint64_t) u0 * v0; + const uint32_t u1 = (uint32_t) ( u >> 32 ); + const uint32_t v1 = (uint32_t) ( v >> 32 ); + const uint64_t t = (uint64_t) u1 * v0 + (uint32_t) ( w0 >> 32 ); + const uint64_t w1 = (uint64_t) u0 * v1 + (uint32_t) t; + + *rh = (uint64_t) u1 * v1 + (uint32_t) ( w1 >> 32 ) + + (uint32_t) ( t >> 32 ); + +#endif // defined( __IBMC__ ) +} + +/** + * @brief A5HASH 64-bit hash function. + * + * Produces and returns a 64-bit hash value (digest) of the specified message, + * string, or binary data block. Designed for string/small key data hash-map + * and hash-table uses. + * + * @param Msg0 The message to produce a hash from. The alignment of this + * pointer is unimportant. It is valid to pass 0 when `MsgLen` equals 0. + * @param MsgLen Message length, in bytes, can be zero. + * @param UseSeed An optional value to use instead of the default seed (0). + * This value can have any number of significant bits and any statistical + * quality. + * @return 64-bit hash of the input data. + */ + +A5HASH_INLINE_F uint64_t a5hash( const void* const Msg0, size_t MsgLen, + const uint64_t UseSeed ) A5HASH_NOEX +{ + const uint8_t* Msg = (const uint8_t*) Msg0; + + uint64_t val01 = A5HASH_VAL01; + uint64_t val10 = A5HASH_VAL10; + + // The seeds are initialized to mantissa bits of PI. + + uint64_t Seed1 = A5HASH_U64_C( 0x243F6A8885A308D3 ) ^ MsgLen; + uint64_t Seed2 = A5HASH_U64_C( 0x452821E638D01377 ) ^ MsgLen; + + a5hash_umul128( Seed2 ^ ( UseSeed & val10 ), + Seed1 ^ ( UseSeed & val01 ), &Seed1, &Seed2 ); + + if( MsgLen > 16 ) + { + val01 ^= Seed1; + val10 ^= Seed2; + + do + { + a5hash_umul128( (uint64_t) a5hash_lu32( Msg ) << 32 ^ + a5hash_lu32( Msg + 4 ) ^ Seed1, + (uint64_t) a5hash_lu32( Msg + 8 ) << 32 ^ + a5hash_lu32( Msg + 12 ) ^ Seed2, &Seed1, &Seed2 ); + + MsgLen -= 16; + Msg += 16; + + Seed1 += val01; + Seed2 += val10; + + } while( MsgLen > 16 ); + } + + if( MsgLen == 0 ) + { + goto _fin; + } + + if( MsgLen > 3 ) + { + const uint8_t* Msg4; + size_t mo; + + Msg4 = Msg + MsgLen - 4; + mo = MsgLen >> 3; + + Seed1 ^= (uint64_t) a5hash_lu32( Msg ) << 32 | a5hash_lu32( Msg4 ); + + Seed2 ^= (uint64_t) a5hash_lu32( Msg + mo * 4 ) << 32 | + a5hash_lu32( Msg4 - mo * 4 ); + + _fin: + a5hash_umul128( Seed1, Seed2, &Seed1, &Seed2 ); + + a5hash_umul128( val01 ^ Seed1, Seed2, &Seed1, &Seed2 ); + + return( Seed1 ^ Seed2 ); + } + else + { + Seed1 ^= Msg[ 0 ]; + + if( --MsgLen != 0 ) + { + Seed1 ^= (uint64_t) Msg[ 1 ] << 8; + + if( --MsgLen != 0 ) + { + Seed1 ^= (uint64_t) Msg[ 2 ] << 16; + } + } + + goto _fin; + } +} + +/** + * @brief 32-bit by 32-bit unsigned multiplication producing a 64-bit result. + * + * @param u Multiplier 1. + * @param v Multiplier 2. + * @param[out] rl The lower half of the 64-bit result. + * @param[out] rh The upper half of the 64-bit result. + */ + +A5HASH_INLINE_F void a5hash_umul64( const uint32_t u, const uint32_t v, + uint32_t* const rl, uint32_t* const rh ) A5HASH_NOEX +{ + const uint64_t r = (uint64_t) u * v; + + *rl = (uint32_t) r; + *rh = (uint32_t) ( r >> 32 ); +} + +/** + * @brief A5HASH 32-bit hash function. + * + * Produces and returns a 32-bit hash value (digest) of the specified message, + * string, or binary data block. Designed for string/small key data hash-map + * and hash-table uses. + * + * This function works natively on 32-bit platforms and avoids the performance + * penalty of 64-bit arithmetic. + * + * @param Msg0 The message to produce a hash from. The alignment of this + * pointer is unimportant. It is valid to pass 0 when `MsgLen` equals 0. + * @param MsgLen Message length, in bytes, can be zero. + * @param UseSeed An optional value to use instead of the default seed (0). + * This value can have any number of significant bits and any statistical + * quality. + * @return 32-bit hash of the input data. + */ + +A5HASH_INLINE_F uint32_t a5hash32( const void* const Msg0, size_t MsgLen, + const uint32_t UseSeed ) A5HASH_NOEX +{ + const uint8_t* Msg = (const uint8_t*) Msg0; + + uint32_t val01 = (uint32_t) A5HASH_VAL01; + uint32_t val10 = (uint32_t) A5HASH_VAL10; + + // The seeds are initialized to mantissa bits of PI. + + uint32_t Seed1 = 0x243F6A88 ^ (uint32_t) MsgLen; + uint32_t Seed2 = 0x85A308D3 ^ (uint32_t) MsgLen; + uint32_t Seed3, Seed4; + uint32_t a, b, c, d; + + #if SIZE_MAX <= 0xFFFFFFFFU + + Seed3 = 0xFB0BD3EA; + Seed4 = 0x0F58FD47; + + #else // SIZE_MAX <= 0xFFFFFFFFU + + a5hash_umul64( (uint32_t) ( MsgLen >> 32 ) ^ 0x452821E6, + (uint32_t) ( MsgLen >> 32 ) ^ 0x38D01377, &Seed3, &Seed4 ); + + #endif // SIZE_MAX <= 0xFFFFFFFFU + + a5hash_umul64( Seed2 ^ ( UseSeed & val10 ), + Seed1 ^ ( UseSeed & val01 ), &Seed1, &Seed2 ); + + if( MsgLen < 17 ) + { + if( MsgLen > 3 ) + { + const uint8_t* const Msg4 = Msg + MsgLen - 4; + size_t mo; + + a = a5hash_lu32( Msg ); + b = a5hash_lu32( Msg4 ); + + if( MsgLen < 9 ) + { + goto _fin; + } + + mo = MsgLen >> 3; + + c = a5hash_lu32( Msg + mo * 4 ); + d = a5hash_lu32( Msg4 - mo * 4 ); + } + else + { + a = 0; + b = 0; + + if( MsgLen != 0 ) + { + a = Msg[ 0 ]; + + if( MsgLen != 1 ) + { + a |= (uint32_t) Msg[ 1 ] << 8; + + if( MsgLen != 2 ) + { + a |= (uint32_t) Msg[ 2 ] << 16; + } + } + } + + goto _fin; + } + } + else + { + val01 ^= Seed1; + val10 ^= Seed2; + + do + { + const uint32_t s1 = Seed1; + const uint32_t s4 = Seed4; + + a5hash_umul64( a5hash_lu32( Msg ) + Seed1, + a5hash_lu32( Msg + 4 ) + Seed2, &Seed1, &Seed2 ); + + a5hash_umul64( a5hash_lu32( Msg + 8 ) + Seed3, + a5hash_lu32( Msg + 12 ) + Seed4, &Seed3, &Seed4 ); + + MsgLen -= 16; + Msg += 16; + + Seed1 += val01; + Seed2 += s4; + Seed3 += s1; + Seed4 += val10; + + } while( MsgLen > 16 ); + + a = a5hash_lu32( Msg + MsgLen - 8 ); + b = a5hash_lu32( Msg + MsgLen - 4 ); + + if( MsgLen < 9 ) + { + goto _fin; + } + + c = a5hash_lu32( Msg + MsgLen - 16 ); + d = a5hash_lu32( Msg + MsgLen - 12 ); + } + + a5hash_umul64( c + Seed3, d + Seed4, &Seed3, &Seed4 ); + +_fin: + Seed1 ^= Seed3; + Seed2 ^= Seed4; + + a5hash_umul64( a + Seed1, b + Seed2, &Seed1, &Seed2 ); + + a5hash_umul64( val01 ^ Seed1, Seed2, &a, &b ); + + return( a ^ b ); +} + +/** + * @brief A5HASH 128-bit hash function. + * + * Produces and returns a 128-bit hash value (digest) of the specified + * message, string, or binary data block. Designed for string/small key data + * hash-map and hash-table uses. + * + * @param Msg0 The message to produce a hash from. The alignment of this + * pointer is unimportant. It is valid to pass 0 when `MsgLen` equals 0. + * @param MsgLen Message length, in bytes, can be zero. + * @param UseSeed An optional value to use instead of the default seed (0). + * This value can have any number of significant bits and any statistical + * quality. + * @param[out] rh Pointer to 64-bit variable that receives upper 64 bits of + * 128-bit hash. The alignment of this pointer is unimportant. Can be 0. + * @return Lower 64 bits of 128-bit hash of the input data. + */ + +A5HASH_INLINE uint64_t a5hash128( const void* const Msg0, size_t MsgLen, + const uint64_t UseSeed, void* const rh ) A5HASH_NOEX +{ + const uint8_t* Msg = (const uint8_t*) Msg0; + + uint64_t val01 = A5HASH_VAL01; + uint64_t val10 = A5HASH_VAL10; + + // The seeds are initialized to mantissa bits of PI. + + uint64_t Seed1 = A5HASH_U64_C( 0x243F6A8885A308D3 ) ^ MsgLen; + uint64_t Seed2 = A5HASH_U64_C( 0x452821E638D01377 ) ^ MsgLen; + uint64_t Seed3 = A5HASH_U64_C( 0xA4093822299F31D0 ); + uint64_t Seed4 = A5HASH_U64_C( 0xC0AC29B7C97C50DD ); + uint64_t a, b, c, d; + + a5hash_umul128( Seed2 ^ ( UseSeed & val10 ), + Seed1 ^ ( UseSeed & val01 ), &Seed1, &Seed2 ); + + if( MsgLen < 17 ) + { + if( MsgLen > 3 ) + { + const uint8_t* Msg4; + size_t mo; + + Msg4 = Msg + MsgLen - 4; + mo = MsgLen >> 3; + + a = (uint64_t) a5hash_lu32( Msg ) << 32 | a5hash_lu32( Msg4 ); + + b = (uint64_t) a5hash_lu32( Msg + mo * 4 ) << 32 | + a5hash_lu32( Msg4 - mo * 4 ); + + _fin16: + a5hash_umul128( a + Seed1, b + Seed2, &Seed1, &Seed2 ); + + a5hash_umul128( val01 ^ Seed1, Seed2, &a, &b ); + + a ^= b; + + if( rh != A5HASH_NULL ) + { + a5hash_umul128( Seed1 ^ Seed3, Seed2 ^ Seed4, &Seed3, &Seed4 ); + + Seed3 ^= Seed4; + memcpy( rh, &Seed3, 8 ); + } + + return( a ); + } + else + { + a = 0; + b = 0; + + if( MsgLen != 0 ) + { + a = Msg[ 0 ]; + + if( --MsgLen != 0 ) + { + a |= (uint64_t) Msg[ 1 ] << 8; + + if( --MsgLen != 0 ) + { + a |= (uint64_t) Msg[ 2 ] << 16; + } + } + } + + goto _fin16; + } + } + + if( MsgLen < 33 ) + { + a = (uint64_t) a5hash_lu32( Msg ) << 32 | a5hash_lu32( Msg + 4 ); + b = (uint64_t) a5hash_lu32( Msg + 8 ) << 32 | a5hash_lu32( Msg + 12 ); + c = (uint64_t) a5hash_lu32( Msg + MsgLen - 16 ) << 32 | + a5hash_lu32( Msg + MsgLen - 12 ); + + d = (uint64_t) a5hash_lu32( Msg + MsgLen - 8 ) << 32 | + a5hash_lu32( Msg + MsgLen - 4 ); + + _fin_m: + a5hash_umul128( c + Seed3, d + Seed4, &Seed3, &Seed4 ); + + _fin: + Seed1 ^= Seed3; + Seed2 ^= Seed4; + + a5hash_umul128( a + Seed1, b + Seed2, &Seed1, &Seed2 ); + + a5hash_umul128( val01 ^ Seed1, Seed2, &a, &b ); + + a ^= b; + + if( rh != A5HASH_NULL ) + { + a5hash_umul128( Seed1 ^ Seed3, Seed2 ^ Seed4, &Seed3, &Seed4 ); + + Seed3 ^= Seed4; + memcpy( rh, &Seed3, 8 ); + } + + return( a ); + } + else + { + val01 ^= Seed1; + val10 ^= Seed2; + + if( MsgLen > 64 ) + { + uint64_t Seed5 = A5HASH_U64_C( 0x082EFA98EC4E6C89 ); + uint64_t Seed6 = A5HASH_U64_C( 0x3F84D5B5B5470917 ); + uint64_t Seed7 = A5HASH_U64_C( 0x13198A2E03707344 ); + uint64_t Seed8 = A5HASH_U64_C( 0xBE5466CF34E90C6C ); + + do + { + const uint64_t s1 = Seed1; + const uint64_t s3 = Seed3; + const uint64_t s5 = Seed5; + + a5hash_umul128( a5hash_lu64( Msg ) + Seed1, + a5hash_lu64( Msg + 32 ) + Seed2, &Seed1, &Seed2 ); + + Seed1 += val01; + Seed2 += Seed8; + + a5hash_umul128( a5hash_lu64( Msg + 8 ) + Seed3, + a5hash_lu64( Msg + 40 ) + Seed4, &Seed3, &Seed4 ); + + Seed3 += s1; + Seed4 += val10; + + a5hash_umul128( a5hash_lu64( Msg + 16 ) + Seed5, + a5hash_lu64( Msg + 48 ) + Seed6, &Seed5, &Seed6 ); + + a5hash_umul128( a5hash_lu64( Msg + 24 ) + Seed7, + a5hash_lu64( Msg + 56 ) + Seed8, &Seed7, &Seed8 ); + + MsgLen -= 64; + Msg += 64; + + Seed5 += s3; + Seed6 += val10; + Seed7 += s5; + Seed8 += val10; + + } while( MsgLen > 64 ); + + Seed1 ^= Seed5; + Seed2 ^= Seed6; + Seed3 ^= Seed7; + Seed4 ^= Seed8; + + if( MsgLen > 32 ) + { + goto _tail32; + } + } + else + { + uint64_t s1; + + _tail32: + s1 = Seed1; + + a5hash_umul128( a5hash_lu64( Msg ) + Seed1, + a5hash_lu64( Msg + 8 ) + Seed2, &Seed1, &Seed2 ); + + Seed1 += val01; + Seed2 += Seed4; + + a5hash_umul128( a5hash_lu64( Msg + 16 ) + Seed3, + a5hash_lu64( Msg + 24 ) + Seed4, &Seed3, &Seed4 ); + + MsgLen -= 32; + Msg += 32; + + Seed3 += s1; + Seed4 += val10; + } + + a = a5hash_lu64( Msg + MsgLen - 16 ); + b = a5hash_lu64( Msg + MsgLen - 8 ); + + if( MsgLen < 17 ) + { + goto _fin; + } + + c = a5hash_lu64( Msg + MsgLen - 32 ); + d = a5hash_lu64( Msg + MsgLen - 24 ); + + goto _fin_m; + } +} + +/** + * @brief A5RAND 64-bit pseudo-random number generator. + * + * A simple, reliable, self-starting, yet efficient PRNG with a 2^64 period. + * 0.50 cycles/byte performance. It self-starts in 4 iterations, which is the + * suggested "warm-up" period before using its output when seeds are + * initialized with an arbitrary value. If initialized with high-quality, + * uniformly random value (e.g., from the operating system's entropy or a + * hash function's output), the PRNG output is valid from the start. + * + * @param[in,out] Seed1 Seed value 1. Can be initialized to any value + * (even 0). Should not be used as the PRNG value. + * @param[in,out] Seed2 Seed value 2. Must be initialized to the same value as + * `Seed1`. Should not be used as the PRNG value. + * @return The next uniformly random 64-bit value. + */ + +A5HASH_INLINE_F uint64_t a5rand( uint64_t* const Seed1, + uint64_t* const Seed2 ) A5HASH_NOEX +{ + uint64_t s1 = *Seed1; + uint64_t s2 = *Seed2; + + a5hash_umul128( s1 + A5HASH_VAL01, s2 + A5HASH_VAL10, &s1, &s2 ); + + *Seed1 = s1; + *Seed2 = s2; + + return( s1 ^ s2 ); +} + +#if defined( A5HASH_NS ) + +} // namespace A5HASH_NS + +#if !defined( A5HASH_NS_CUSTOM ) + +namespace { + +using A5HASH_NS :: a5hash_umul128; +using A5HASH_NS :: a5hash; +using A5HASH_NS :: a5hash32; +using A5HASH_NS :: a5hash128; +using A5HASH_NS :: a5rand; + +} // namespace + +#endif // !defined( A5HASH_NS_CUSTOM ) + +#endif // defined( A5HASH_NS ) + +// Defines for Doxygen. + +#if !defined( A5HASH_NS_CUSTOM ) + #define A5HASH_NS_CUSTOM +#endif // !defined( A5HASH_NS_CUSTOM ) + +#undef A5HASH_NS_CUSTOM +#undef A5HASH_U64_C +#undef A5HASH_NOEX +#undef A5HASH_NULL +#undef A5HASH_VAL10 +#undef A5HASH_VAL01 +#undef A5HASH_ICC_GCC +#undef A5HASH_GCC_BUILTINS +#undef A5HASH_BMI2 +#undef A5HASH_STATIC +#undef A5HASH_INLINE +#undef A5HASH_INLINE_F + +#endif // A5HASH_INCLUDED diff --git a/src/map.c b/src/map.c index 00b56b8..788095f 100644 --- a/src/map.c +++ b/src/map.c @@ -2,12 +2,15 @@ #include "common.h" #include "smrt_arena.h" +#include "../include/a5hash.h" + +#include #include -#include #include -#define ENTRY_TOMBSTONE 0b0000000000000000000000000000000000000000000000000000000000000001 -#define ENTRY_MASK 0b1111111111111111111111111111111111111111111111111111111111111110 +#define ENTRY_TOMBSTONE 0b00000001 +#define ENTRY_EMPTY 0b00000000 +#define ENTRY_MASK 0b11111110 typedef struct { void const *key; @@ -16,24 +19,17 @@ typedef struct { typedef struct _map_t { u64 table_size; + u8 *hashlookup; u64 *hashes; map_key_entry_t *keys; void **values; } _map_t; -u32 hash(u8 const *input, u64 inputlen) { - // Make this batched + SIMD eventually - u32 sum = UINT32_MAX / 2; - for (u64 i = 0; i < inputlen; i++) { - sum += input[i]; - } - return sum; -} - map_t map_create(smrt_arena_t *arena, u64 capacity) { map_t map = smrt_arena_push(arena, sizeof(_map_t), true); map->hashes = SMRTA_ALLOC_ARRAY(arena, u64, capacity); + map->hashlookup = SMRTA_ALLOC_ARRAY(arena, u8, capacity); map->keys = SMRTA_ALLOC_ARRAY(arena, map_key_entry_t, capacity); map->values = SMRTA_ALLOC_ARRAY(arena, void*, capacity); map->table_size = capacity; @@ -42,96 +38,84 @@ map_t map_create(smrt_arena_t *arena, u64 capacity) { } i32 map_insert(map_t const map, u8 const *key, u64 keylen, void *value) { - u64 h = hash(key, keylen) & ENTRY_MASK; + u64 h = a5hash128(key, keylen, 0, NULL); + u8 h_lookup = h >> (64-8) & ENTRY_MASK; u64 start = h % map->table_size; i64 first_tombstone = -1; u64 tsize = map->table_size; - for (u64 i = start; i != start - 1; i = (i+1)%tsize) { - // If didnt find match, insert at first tombstone or current i - if (map->keys[i].key == NULL) { + for (u64 i = start; i != start - 1; i=(i+1)%tsize) { + u8 h_lookupcmp = map->hashlookup[i]; + if (h_lookupcmp == ENTRY_EMPTY) { if (first_tombstone != -1) i = first_tombstone; + map->hashes[i] = h; - map->keys[i] = (map_key_entry_t){.key=key, .keylen=keylen, }; + map->hashlookup[i] = h_lookup; + map->keys[i] = (map_key_entry_t){ .key=key, .keylen=keylen }; map->values[i] = value; return 0; } - u64 h_cmp = map->hashes[i]; - - // if tombstone, update first tombstone - if (first_tombstone != -1 && (h_cmp & ENTRY_TOMBSTONE) == ENTRY_TOMBSTONE) { + if (first_tombstone == -1 && + h_lookupcmp == ENTRY_TOMBSTONE) { first_tombstone = i; continue; } - map_key_entry_t k = map->keys[i]; - if ((k.keylen == keylen) && - (h == h_cmp ) && - (memcmp(key, k.key, keylen) == 0)) - { - map->keys[i].key = key; - map->values[i] = value; - return 0; + if ( + h_lookupcmp == h_lookup && + keylen == map->keys[i].keylen && + h == map->hashes[i] && + (memcmp(key, map->keys[i].key, keylen) == 0) + ) { + map->keys[i].key=key; + map->values[i]=value; } - } + } return -1; } i32 map_delete(map_t const map, u8 const *key, u64 keylen) { - u64 h = hash(key, keylen) & ENTRY_MASK; + u64 h = a5hash128(key, keylen, 0, NULL); + u8 h_lookup = h >> (64-8) & ENTRY_MASK; u64 start = h % map->table_size; u64 tsize = map->table_size; - for (u64 i = start; i != start - 1; i = (i+1)%tsize) { - if (map->keys[i].key == NULL) { - return -1; - } - - u64 h_cmp = map->hashes[i]; - - if ((h_cmp & ENTRY_TOMBSTONE) == ENTRY_TOMBSTONE) { - continue; - } - - map_key_entry_t k = map->keys[i]; - if (k.keylen == keylen && - h == h_cmp && - memcmp(key, k.key, keylen) == 0) - { - map->keys[i].keylen = 0; - map->hashes[i] = ENTRY_TOMBSTONE; - return 0; - } + for (u64 i = start; i != start - 1; i=(i+1)%tsize) { + u8 h_lookupcmp = map->hashlookup[i]; + if (h_lookupcmp == ENTRY_EMPTY) return -1; + if (h_lookupcmp == ENTRY_TOMBSTONE) continue; + + if (h_lookupcmp == h_lookup && + h == map->hashes[i] && + keylen == map->keys[i].keylen && + (memcmp(key, map->keys[i].key, keylen) == 0)) + { map->keys[i].keylen=0; + map->hashlookup[i]=ENTRY_TOMBSTONE; + return 0; } } return -1; } void *map_lookup(map_t const map, u8 const *key, u64 keylen) { - u64 h = hash(key, keylen) & ENTRY_MASK; + u64 h = a5hash128(key, keylen, 0, NULL); + u8 h_lookup = h >> (64-8) & ENTRY_MASK; u64 start = h % map->table_size; u64 tsize = map->table_size; for (u64 i = start; i != start - 1; i = (i+1)%tsize) { - if (map->keys[i].key == NULL) { - return NULL; - } - - u64 h_cmp = map->hashes[i]; - - if ((h_cmp & ENTRY_TOMBSTONE) == ENTRY_TOMBSTONE) { - continue; - } + u8 h_lookupcmp = map->hashlookup[i]; + if (h_lookupcmp == ENTRY_EMPTY) return NULL; + if (h_lookupcmp == ENTRY_TOMBSTONE) continue; map_key_entry_t k = map->keys[i]; - if (k.keylen == keylen && - h == h_cmp && - memcmp(key, k.key, keylen) == 0) - { - return map->values[i]; - } + if (h_lookupcmp == h_lookup && + h == map->hashes[i] && + k.keylen == keylen && + (memcmp(key, k.key, keylen) == 0)) + { return map->values[i]; } } return NULL; diff --git a/src/map.h b/src/map.h index b99a306..6678ddd 100644 --- a/src/map.h +++ b/src/map.h @@ -4,7 +4,9 @@ #include "smrt_arena.h" // Hashmap structure that stores u8* keys and void* values. -// API: map_create, map_insert, map_delete, map_lookoop +// API: map_create, map_insert, map_delete, map_lookup +// There is no map_destroy. It is allocated on the arena +// Uses a5hash to hash keys. typedef struct _map_t* map_t; map_t map_create(smrt_arena_t *arena, u64 table_size); -- cgit v1.2.3