From ccab349c99167f6a3e18d43bc616aeccdfbb009c Mon Sep 17 00:00:00 2001 From: Ran Benita Date: Sat, 9 Nov 2019 12:43:04 +0200 Subject: [PATCH] atom: use a better hash function FNV-1a instead of the djb2-like one from before. Keep the unrolling since it seems quite beneficial, even though it loses one byte if the length is odd... Signed-off-by: Ran Benita --- src/atom.c | 20 +++++++++++++++----- 1 file changed, 15 insertions(+), 5 deletions(-) diff --git a/src/atom.c b/src/atom.c index cebc2e7..09f6e6a 100644 --- a/src/atom.c +++ b/src/atom.c @@ -73,6 +73,20 @@ #include "utils.h" #include "atom.h" +/* FNV-1a (http://www.isthe.com/chongo/tech/comp/fnv/). */ +static inline uint32_t +hash_buf(const char *string, size_t len) +{ + uint32_t hash = 2166136261u; + for (size_t i = 0; i < len / 2; i++) { + hash ^= (uint8_t) string[i]; + hash *= 0x01000193; + hash ^= (uint8_t) string[len - 1 - i]; + hash *= 0x01000193; + } + return hash; +} + struct atom_node { xkb_atom_t left, right; uint32_t fingerprint; @@ -122,11 +136,7 @@ static bool find_atom_pointer(struct atom_table *table, const char *string, size_t len, xkb_atom_t **atomp_out, uint32_t *fingerprint_out) { - uint32_t fingerprint = 0; - for (size_t i = 0; i < (len + 1) / 2; i++) { - fingerprint = fingerprint * 27 + string[i]; - fingerprint = fingerprint * 27 + string[len - 1 - i]; - } + uint32_t fingerprint = hash_buf(string, len); xkb_atom_t *atomp = &table->root; while (*atomp != XKB_ATOM_NONE) { -- 2.7.4