From ae7c2261befd961a06a7422b8ae79b54c89e03bc Mon Sep 17 00:00:00 2001 From: Maciej Kurc Date: Tue, 11 Jan 2022 15:28:13 +0100 Subject: Switched integer pair hashing function from DJB2 to Cantor Signed-off-by: Maciej Kurc --- common/hashlib.h | 7 +++++-- 1 file changed, 5 insertions(+), 2 deletions(-) diff --git a/common/hashlib.h b/common/hashlib.h index b71f0129..70de8c91 100644 --- a/common/hashlib.h +++ b/common/hashlib.h @@ -26,8 +26,11 @@ NEXTPNR_NAMESPACE_BEGIN const int hashtable_size_trigger = 2; const int hashtable_size_factor = 3; -// The XOR version of DJB2 -inline unsigned int mkhash(unsigned int a, unsigned int b) { return ((a << 5) + a) ^ b; } +// Cantor pairing function for two non-negative integers +// https://en.wikipedia.org/wiki/Pairing_function +inline unsigned int mkhash(unsigned int a, unsigned int b) { + return (a*a + 3*a + 2*a*b + b + b*b) / 2; +} // traditionally 5381 is used as starting value for the djb2 hash const unsigned int mkhash_init = 5381; -- cgit v1.2.3