1 /*
2  * Copyright (c) 2006-2022, RT-Thread Development Team
3  *
4  * SPDX-License-Identifier: Apache-2.0
5  *
6  * Change Logs:
7  * Date           Author       Notes
8  * 2022-08-01     GuEe-GUI     first version
9  */
10 
11 #ifndef __UTIL_HASHMAP_H__
12 #define __UTIL_HASHMAP_H__
13 
14 #include <rtdef.h>
15 
16 /*
17  * http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf
18  *
19  * GoldenRatio = ~(Math.pow(2, 32) / ((Math.sqrt(5) - 1) / 2)) + 1
20  */
21 #define RT_HASHMAP_GOLDEN_RATIO_32  0x61C88647
22 #define RT_HASHMAP_GOLDEN_RATIO_64  0X61C8864680B583EBULL
23 
rt_hashmap_32(rt_uint32_t val,rt_uint32_t bits)24 rt_inline rt_uint32_t rt_hashmap_32(rt_uint32_t val, rt_uint32_t bits)
25 {
26     /* High bits are more random, so use them. */
27     return (val * RT_HASHMAP_GOLDEN_RATIO_32) >> (32 - bits);
28 }
29 
rt_hashmap_64(rt_uint64_t val,rt_uint32_t bits)30 rt_inline rt_uint32_t rt_hashmap_64(rt_uint64_t val, rt_uint32_t bits)
31 {
32 #ifdef ARCH_CPU_64BIT
33     /* 64x64-bit multiply is efficient on all 64-bit processors */
34     return val * RT_HASHMAP_GOLDEN_RATIO_64 >> (64 - bits);
35 #else
36     /* Hash 64 bits using only 32x32-bit multiply. */
37     return rt_hashmap_32((rt_uint32_t)val ^ ((val >> 32) * RT_HASHMAP_GOLDEN_RATIO_32), bits);
38 #endif
39 }
40 
41 #endif /* __UTIL_HASHMAP_H__ */
42