diff options
author | Maciej Kurc <mkurc@antmicro.com> | 2022-01-11 15:28:13 +0100 |
---|---|---|
committer | Maciej Kurc <mkurc@antmicro.com> | 2022-01-11 15:28:13 +0100 |
commit | ae7c2261befd961a06a7422b8ae79b54c89e03bc (patch) | |
tree | 9c9ed2147f92c3565a882b6170a2809b5acbae73 | |
parent | 3d24583b914bac37d9c22931e6fcee2e1408b284 (diff) | |
download | nextpnr-ae7c2261befd961a06a7422b8ae79b54c89e03bc.tar.gz nextpnr-ae7c2261befd961a06a7422b8ae79b54c89e03bc.tar.bz2 nextpnr-ae7c2261befd961a06a7422b8ae79b54c89e03bc.zip |
Switched integer pair hashing function from DJB2 to Cantor
Signed-off-by: Maciej Kurc <mkurc@antmicro.com>
-rw-r--r-- | common/hashlib.h | 7 |
1 files 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; |