diff options
-rw-r--r-- | src/hash.h | 23 |
1 files changed, 21 insertions, 2 deletions
@@ -48,6 +48,7 @@ #define HASH_H #include <assert.h> +#include <stdbool.h> #include <stdint.h> #ifdef __LP64__ @@ -59,11 +60,19 @@ static_assert(sizeof(long) == 4, "unsupported data model"); #define hash_long(n, bits) hash_int32(n, bits) #endif +static inline bool +hash_bits_valid(unsigned int bits) +{ + return (bits != 0) && (bits <= HASH_ALLBITS); +} + static inline uint32_t hash_int32(uint32_t n, unsigned int bits) { uint32_t hash; + assert(hash_bits_valid(bits)); + hash = n; hash = ~hash + (hash << 15); hash ^= (hash >> 12); @@ -80,6 +89,8 @@ hash_int64(uint64_t n, unsigned int bits) { uint64_t hash; + assert(hash_bits_valid(bits)); + hash = n; hash = ~hash + (hash << 21); hash ^= (hash >> 24); @@ -105,9 +116,11 @@ hash_ptr(const void *ptr, unsigned int bits) static inline unsigned long hash_str(const char *str, unsigned int bits) { - unsigned long hash; + unsigned long hash, mask; char c; + assert(hash_bits_valid(bits)); + for (hash = 0; /* no condition */; str++) { c = *str; @@ -118,7 +131,13 @@ hash_str(const char *str, unsigned int bits) hash = ((hash << 5) - hash) + c; } - return hash & ((1UL << bits) - 1); + /* + * This mask construction avoids the undefined behavior that would + * result from directly shifting by the number of bits, if that number + * is equal to the width of the hash. + */ + mask = (~0UL >> (HASH_ALLBITS - bits)); + return hash & mask; } #endif /* HASH_H */ |