From d34d25c9546ce406afef2c561663db422045f05a Mon Sep 17 00:00:00 2001 From: Tavian Barnes Date: Thu, 13 Feb 2025 12:57:19 -0500 Subject: trie: Make nibble indices big-endian Otherwise the order doesn't match lexicographical order on bytes. --- src/trie.c | 14 +++++++------- tests/trie.c | 4 ++++ 2 files changed, 11 insertions(+), 7 deletions(-) diff --git a/src/trie.c b/src/trie.c index 47a5447..68e3948 100644 --- a/src/trie.c +++ b/src/trie.c @@ -178,11 +178,11 @@ static unsigned char trie_key_nibble(const void *key, size_t length, size_t offs // A branchless version of // if (offset & 1) { - // return bytes[byte] >> 4; - // } else { // return bytes[byte] & 0xF; + // } else { + // return bytes[byte] >> 4; // } - unsigned int shift = (offset & 1) << 2; + unsigned int shift = 4 * ((offset + 1) % 2); return (bytes[byte] >> shift) & 0xF; } @@ -392,9 +392,9 @@ static void trie_node_free(struct trie *trie, struct trie_node *node, size_t siz } #if ENDIAN_NATIVE == ENDIAN_LITTLE -# define TRIE_BSWAP(n) (n) -#elif ENDIAN_NATIVE == ENDIAN_BIG # define TRIE_BSWAP(n) bswap(n) +#elif ENDIAN_NATIVE == ENDIAN_BIG +# define TRIE_BSWAP(n) (n) #endif /** Find the offset of the first nibble that differs between two keys. */ @@ -420,7 +420,7 @@ static size_t trie_mismatch(const struct trie_leaf *rep, const void *key, size_t #ifdef TRIE_BSWAP size_t diff = TRIE_BSWAP(rep_chunk ^ key_chunk); i *= 2; - i += trailing_zeros(diff) / 4; + i += leading_zeros(diff) / 4; return i; #else break; @@ -431,7 +431,7 @@ static size_t trie_mismatch(const struct trie_leaf *rep, const void *key, size_t for (; i < length; ++i) { unsigned char diff = rep_bytes[i] ^ key_bytes[i]; if (diff) { - return 2 * i + !(diff & 0xF); + return 2 * i + !(diff >> 4); } } diff --git a/tests/trie.c b/tests/trie.c index 6e6024a..59bde40 100644 --- a/tests/trie.c +++ b/tests/trie.c @@ -39,6 +39,10 @@ static const char *keys[] = { ">>>>>>", ">>><<<", ">>>", + + "AAAAAAA", + "AAAAAAAB", + "AAAAAAAa", }; static const size_t nkeys = countof(keys); -- cgit v1.2.3