diff options
| author | gatecat <gatecat@ds0.me> | 2022-01-11 16:33:19 +0000 |
|---|---|---|
| committer | GitHub <noreply@github.com> | 2022-01-11 16:33:19 +0000 |
| commit | 2ab08a872d08e6ba64a0b81303889a14941a88f0 (patch) | |
| tree | 9c9ed2147f92c3565a882b6170a2809b5acbae73 | |
| parent | 3d24583b914bac37d9c22931e6fcee2e1408b284 (diff) | |
| parent | ae7c2261befd961a06a7422b8ae79b54c89e03bc (diff) | |
| download | nextpnr-2ab08a872d08e6ba64a0b81303889a14941a88f0.tar.gz nextpnr-2ab08a872d08e6ba64a0b81303889a14941a88f0.tar.bz2 nextpnr-2ab08a872d08e6ba64a0b81303889a14941a88f0.zip | |
Merge pull request #894 from antmicro/integer-hashing
Better hashing function for integer pairs
| -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; |