diff options
| -rw-r--r-- | lib/birdlib.h | 27 | ||||
| -rw-r--r-- | lib/ip.h | 31 | ||||
| -rw-r--r-- | lib/net.h | 34 |
3 files changed, 75 insertions, 17 deletions
diff --git a/lib/birdlib.h b/lib/birdlib.h index e03bd0b2..b7226411 100644 --- a/lib/birdlib.h +++ b/lib/birdlib.h @@ -162,6 +162,7 @@ void bug(const char *msg, ...) NORET; void debug(const char *msg, ...); /* Printf to debug output */ void debug_safe(const char *msg); /* Printf to debug output, async-safe */ + /* Debugging */ #if defined(LOCAL_DEBUG) || defined(GLOBAL_DEBUG) @@ -196,10 +197,36 @@ asm( ); #endif + /* Pseudorandom numbers */ u32 random_u32(void); void random_init(void); void random_bytes(void *buf, size_t size); + +/* Hashing */ + +/* Constant parameter for non-parametrized hashes */ +#define HASH_PARAM 2902958171u + +/* Precomputed powers of HASH_PARAM */ +#define HASH_PARAM1 ((u64) HASH_PARAM) +#define HASH_PARAM2 (HASH_PARAM1 * HASH_PARAM) +#define HASH_PARAM3 (HASH_PARAM2 * HASH_PARAM) +#define HASH_PARAM4 (HASH_PARAM3 * HASH_PARAM) + +/* Reduce intermediate 64-bit value to final 32-bit value */ +static inline u32 hash_value(u64 a) +{ return ((u32) a) ^ ((u32) (a >> 32)); } + +static inline u64 u32_hash0(u32 v, u32 p, u64 acc) +{ return (acc + v) * p; } + +static inline u64 u64_hash0(u64 v, u32 p, u64 acc) +{ return u32_hash0(v >> 32, p, u32_hash0(v, p, acc)); } + +static inline u32 u64_hash(u64 v) +{ return hash_value(u64_hash0(v, HASH_PARAM, 0)); } + #endif @@ -194,14 +194,37 @@ static inline int ipa_nonzero2(ip_addr a) * Hash and compare functions */ +static inline u64 ip4_hash0(ip4_addr a, u32 p, u64 acc) +{ return (acc + _I(a)) * p; } + static inline u32 ip4_hash(ip4_addr a) -{ return u32_hash(_I(a)); } +{ + // return hash_value(ip4_hash0(a, HASH_PARAM, 0)); + + /* For some reason, the old hash works slightly better */ + return u32_hash(_I(a)); +} + +static inline u64 ip6_hash0(ip6_addr a, u32 p, u64 acc) +{ + acc += _I0(a); acc *= p; + acc += _I1(a); acc *= p; + acc += _I2(a); acc *= p; + acc += _I3(a); acc *= p; + return acc; +} static inline u32 ip6_hash(ip6_addr a) { - /* Returns a 32-bit hash key, although low-order bits are not mixed */ - u32 x = _I0(a) ^ _I1(a) ^ _I2(a) ^ _I3(a); - return x ^ (x << 16) ^ (x << 24); + // return hash_value(ip6_hash0(a, HASH_PARAM, 0)); + + /* Just use the expanded form */ + u64 acc = + _I0(a) * HASH_PARAM4 + + _I1(a) * HASH_PARAM3 + + _I2(a) * HASH_PARAM2 + + _I3(a) * HASH_PARAM1; + return hash_value(acc); } static inline int ip4_compare(ip4_addr a, ip4_addr b) @@ -479,39 +479,47 @@ static inline void net_copy_mpls(net_addr_mpls *dst, const net_addr_mpls *src) { memcpy(dst, src, sizeof(net_addr_mpls)); } -/* XXXX */ -static inline u32 u64_hash(u64 a) -{ return u32_hash(a); } +static inline u32 px4_hash(ip4_addr prefix, u32 pxlen) +{ return ip4_hash(prefix) ^ (pxlen << 26); } + +static inline u32 px6_hash(ip6_addr prefix, u32 pxlen) +{ return ip6_hash(prefix) ^ (pxlen << 26); } static inline u32 net_hash_ip4(const net_addr_ip4 *n) -{ return ip4_hash(n->prefix) ^ ((u32) n->pxlen << 26); } +{ return px4_hash(n->prefix, n->pxlen); } static inline u32 net_hash_ip6(const net_addr_ip6 *n) -{ return ip6_hash(n->prefix) ^ ((u32) n->pxlen << 26); } +{ return px6_hash(n->prefix, n->pxlen); } static inline u32 net_hash_vpn4(const net_addr_vpn4 *n) -{ return ip4_hash(n->prefix) ^ ((u32) n->pxlen << 26) ^ u64_hash(n->rd); } +{ + u64 acc = ip4_hash0(n->prefix, HASH_PARAM, 0) ^ (n->pxlen << 26); + return hash_value(u64_hash0(n->rd, HASH_PARAM, acc)); +} static inline u32 net_hash_vpn6(const net_addr_vpn6 *n) -{ return ip6_hash(n->prefix) ^ ((u32) n->pxlen << 26) ^ u64_hash(n->rd); } +{ + u64 acc = ip6_hash0(n->prefix, HASH_PARAM, 0) ^ (n->pxlen << 26); + return hash_value(u64_hash0(n->rd, HASH_PARAM, acc)); +} static inline u32 net_hash_roa4(const net_addr_roa4 *n) -{ return ip4_hash(n->prefix) ^ ((u32) n->pxlen << 26); } +{ return px4_hash(n->prefix, n->pxlen); } static inline u32 net_hash_roa6(const net_addr_roa6 *n) -{ return ip6_hash(n->prefix) ^ ((u32) n->pxlen << 26); } +{ return px6_hash(n->prefix, n->pxlen); } static inline u32 net_hash_flow4(const net_addr_flow4 *n) -{ return ip4_hash(n->prefix) ^ ((u32) n->pxlen << 26); } +{ return px4_hash(n->prefix, n->pxlen); } static inline u32 net_hash_flow6(const net_addr_flow6 *n) -{ return ip6_hash(n->prefix) ^ ((u32) n->pxlen << 26); } +{ return px6_hash(n->prefix, n->pxlen); } static inline u32 net_hash_ip6_sadr(const net_addr_ip6_sadr *n) -{ return net_hash_ip6((net_addr_ip6 *) n); } +{ return px6_hash(n->dst_prefix, n->dst_pxlen); } static inline u32 net_hash_mpls(const net_addr_mpls *n) -{ return n->label; } +{ return u32_hash(n->label); } u32 net_hash(const net_addr *a); |