Switched integer pair hashing function from DJB2 to Cantor

Signed-off-by: Maciej Kurc <mkurc@antmicro.com>

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;