diff options
author | Richard Braun <rbraun@sceen.net> | 2018-03-28 00:28:34 +0200 |
---|---|---|
committer | Richard Braun <rbraun@sceen.net> | 2018-03-28 00:38:08 +0200 |
commit | 6fb44164ecdb2227be73344724be10eb9b50a6e1 (patch) | |
tree | 64567bf93abaa36373a19bd50e2aa85d1e484af9 /src | |
parent | a6a6d504f930311a2279a1ef6773bd436b945a79 (diff) |
hash: fix undefined behavior in hash_str
Reported by Laurent Dufresne.
Diffstat (limited to 'src')
-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 */ |