From d8893a077c3e87605f7d1630d35688b734cc86d2 Mon Sep 17 00:00:00 2001 From: Paul Eggert Date: Sun, 19 May 2024 08:42:57 -0700 Subject: [PATCH] Port knuth_hash to odd platforms MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit * src/lisp.h (hash_hash_t, knuth_hash): Use unsigned int and unsigned long long int rather than uint32_t and uint64_t, as POSIX does not guarantee the presence of uint64_t, and uint32_t and uint64_t both in theory have problems with undefined behavior on integer overflow. This doesn’t affect behavior (or even machine code) on typical platforms. (cherry picked from commit 9bcd644408367b1d57e62a7f73b4ef4a3cd366b4) --- src/lisp.h | 14 +++++++++----- 1 file changed, 9 insertions(+), 5 deletions(-) diff --git a/src/lisp.h b/src/lisp.h index d61a4d5c982..4b4ff2a2c60 100644 --- a/src/lisp.h +++ b/src/lisp.h @@ -2534,7 +2534,7 @@ struct Lisp_Hash_Table; /* The type of a hash value stored in the table. It's unsigned and a subtype of EMACS_UINT. */ -typedef uint32_t hash_hash_t; +typedef unsigned int hash_hash_t; typedef enum { Test_eql, @@ -2818,10 +2818,14 @@ INLINE ptrdiff_t knuth_hash (hash_hash_t hash, unsigned bits) { /* Knuth multiplicative hashing, tailored for 32-bit indices - (avoiding a 64-bit multiply). */ - uint32_t alpha = 2654435769; /* 2**32/phi */ - /* Note the cast to uint64_t, to make it work for bits=0. */ - return (uint64_t)((uint32_t)hash * alpha) >> (32 - bits); + (avoiding a 64-bit multiply on typical platforms). */ + unsigned int h = hash; + unsigned int alpha = 2654435769; /* 2**32/phi */ + /* Multiply with unsigned int, ANDing in case UINT_WIDTH exceeds 32. */ + unsigned int product = (h * alpha) & 0xffffffffu; + /* Convert to a wider type, so that the shift works when BITS == 0. */ + unsigned long long int wide_product = product; + return wide_product >> (32 - bits); } -- 2.39.5