On Sat, 19 Feb 2022 20:07:58 +0700
John Naylor <john.nay...@enterprisedb.com> wrote:
> We've accumulated a few bit-twiddling hacks to get the compiler to
> emit a rotate instruction. Since we have a macro for that, let's use
> it, as in the attached. I thought the new call sites would look better
> with a "left" version, so I added a new macro for that. That's not
> necessary, however.
>
> Some comments now look a bit too obvious to keep around, but maybe
> they should be replaced with a "why", instead of a "what":
>
> /* rotate hashkey left 1 bit at each step */
> - hashkey = (hashkey << 1) | ((hashkey &
> 0x80000000) ? 1 : 0);
> + hashkey = pg_rotate_left32(hashkey, 1);
I think we can use this macro also in hash_multirange, hash_range,
and JsonbHashScalarValue as in the attached patch. How about replacing
them with the macro, too.
For avoiding undefined behaviours, maybe it is better to use unsigned
int and bit mask as a following code in Linux does[1][2], though it
would be unnecessary if they are used properly as in the current
PostgreSQL code.
static inline __u32 rol32(__u32 word, unsigned int shift)
{
return (word << (shift & 31)) | (word >> ((-shift) & 31));
}
[1] https://github.com/torvalds/linux/blob/master/include/linux/bitops.h
[2] https://lore.kernel.org/lkml/20190609164129.126354...@linuxfoundation.org/
Regards,
Yugo Nagata
>
>
> --
> John Naylor
> EDB: http://www.enterprisedb.com
--
Yugo NAGATA <nag...@sraoss.co.jp>
diff --git a/src/backend/executor/execGrouping.c b/src/backend/executor/execGrouping.c
index af6e9c42d8..ce8f6cd047 100644
--- a/src/backend/executor/execGrouping.c
+++ b/src/backend/executor/execGrouping.c
@@ -460,7 +460,7 @@ TupleHashTableHash_internal(struct tuplehash_hash *tb,
bool isNull;
/* rotate hashkey left 1 bit at each step */
- hashkey = (hashkey << 1) | ((hashkey & 0x80000000) ? 1 : 0);
+ hashkey = pg_rotate_left32(hashkey, 1);
attr = slot_getattr(slot, att, &isNull);
diff --git a/src/backend/executor/nodeHash.c b/src/backend/executor/nodeHash.c
index 4d68a8b97b..6f9d0f9487 100644
--- a/src/backend/executor/nodeHash.c
+++ b/src/backend/executor/nodeHash.c
@@ -1841,7 +1841,7 @@ ExecHashGetHashValue(HashJoinTable hashtable,
bool isNull;
/* rotate hashkey left 1 bit at each step */
- hashkey = (hashkey << 1) | ((hashkey & 0x80000000) ? 1 : 0);
+ hashkey = pg_rotate_left32(hashkey, 1);
/*
* Get the join attribute value of the tuple
diff --git a/src/backend/executor/nodeMemoize.c b/src/backend/executor/nodeMemoize.c
index 55cdd5c4d9..e32e4c04e6 100644
--- a/src/backend/executor/nodeMemoize.c
+++ b/src/backend/executor/nodeMemoize.c
@@ -167,7 +167,7 @@ MemoizeHash_hash(struct memoize_hash *tb, const MemoizeKey *key)
for (int i = 0; i < numkeys; i++)
{
/* rotate hashkey left 1 bit at each step */
- hashkey = (hashkey << 1) | ((hashkey & 0x80000000) ? 1 : 0);
+ hashkey = pg_rotate_left32(hashkey, 1);
if (!pslot->tts_isnull[i]) /* treat nulls as having hash key 0 */
{
@@ -190,7 +190,7 @@ MemoizeHash_hash(struct memoize_hash *tb, const MemoizeKey *key)
for (int i = 0; i < numkeys; i++)
{
/* rotate hashkey left 1 bit at each step */
- hashkey = (hashkey << 1) | ((hashkey & 0x80000000) ? 1 : 0);
+ hashkey = pg_rotate_left32(hashkey, 1);
if (!pslot->tts_isnull[i]) /* treat nulls as having hash key 0 */
{
diff --git a/src/backend/utils/adt/jsonb_util.c b/src/backend/utils/adt/jsonb_util.c
index 291fb722e2..60442758b3 100644
--- a/src/backend/utils/adt/jsonb_util.c
+++ b/src/backend/utils/adt/jsonb_util.c
@@ -18,6 +18,7 @@
#include "common/hashfn.h"
#include "common/jsonapi.h"
#include "miscadmin.h"
+#include "port/pg_bitutils.h"
#include "utils/builtins.h"
#include "utils/datetime.h"
#include "utils/json.h"
@@ -1342,7 +1343,7 @@ JsonbHashScalarValue(const JsonbValue *scalarVal, uint32 *hash)
* the previous value left 1 bit, then XOR'ing in the new
* key/value/element's hash value.
*/
- *hash = (*hash << 1) | (*hash >> 31);
+ *hash = pg_rotate_left32(*hash, 1);
*hash ^= tmp;
}
diff --git a/src/backend/utils/adt/multirangetypes.c b/src/backend/utils/adt/multirangetypes.c
index 7b86421465..c8c1ee8fe9 100644
--- a/src/backend/utils/adt/multirangetypes.c
+++ b/src/backend/utils/adt/multirangetypes.c
@@ -2772,7 +2772,7 @@ hash_multirange(PG_FUNCTION_ARGS)
/* Merge hashes of flags and bounds */
range_hash = hash_uint32((uint32) flags);
range_hash ^= lower_hash;
- range_hash = (range_hash << 1) | (range_hash >> 31);
+ range_hash = pg_rotate_left32(range_hash, 1);
range_hash ^= upper_hash;
/*
diff --git a/src/backend/utils/adt/rangetypes.c b/src/backend/utils/adt/rangetypes.c
index c3e6c721e6..cbff4e93d5 100644
--- a/src/backend/utils/adt/rangetypes.c
+++ b/src/backend/utils/adt/rangetypes.c
@@ -35,6 +35,7 @@
#include "lib/stringinfo.h"
#include "libpq/pqformat.h"
#include "miscadmin.h"
+#include "port/pg_bitutils.h"
#include "utils/builtins.h"
#include "utils/date.h"
#include "utils/lsyscache.h"
@@ -1363,7 +1364,7 @@ hash_range(PG_FUNCTION_ARGS)
/* Merge hashes of flags and bounds */
result = hash_uint32((uint32) flags);
result ^= lower_hash;
- result = (result << 1) | (result >> 31);
+ result = pg_rotate_left32(result, 1);
result ^= upper_hash;
PG_RETURN_INT32(result);
diff --git a/src/backend/utils/cache/catcache.c b/src/backend/utils/cache/catcache.c
index eb83088089..ec073e1ed0 100644
--- a/src/backend/utils/cache/catcache.c
+++ b/src/backend/utils/cache/catcache.c
@@ -26,6 +26,7 @@
#include "catalog/pg_type.h"
#include "common/hashfn.h"
#include "miscadmin.h"
+#include "port/pg_bitutils.h"
#ifdef CATCACHE_STATS
#include "storage/ipc.h" /* for on_proc_exit */
#endif
@@ -281,25 +282,18 @@ CatalogCacheComputeHashValue(CatCache *cache, int nkeys,
{
case 4:
oneHash = (cc_hashfunc[3]) (v4);
-
- hashValue ^= oneHash << 24;
- hashValue ^= oneHash >> 8;
+ hashValue ^= pg_rotate_left32(oneHash, 24);
/* FALLTHROUGH */
case 3:
oneHash = (cc_hashfunc[2]) (v3);
-
- hashValue ^= oneHash << 16;
- hashValue ^= oneHash >> 16;
+ hashValue ^= pg_rotate_left32(oneHash, 16);
/* FALLTHROUGH */
case 2:
oneHash = (cc_hashfunc[1]) (v2);
-
- hashValue ^= oneHash << 8;
- hashValue ^= oneHash >> 24;
+ hashValue ^= pg_rotate_left32(oneHash, 8);
/* FALLTHROUGH */
case 1:
oneHash = (cc_hashfunc[0]) (v1);
-
hashValue ^= oneHash;
break;
default:
diff --git a/src/include/port/pg_bitutils.h b/src/include/port/pg_bitutils.h
index 44c74fb974..65aa5ec29d 100644
--- a/src/include/port/pg_bitutils.h
+++ b/src/include/port/pg_bitutils.h
@@ -285,12 +285,18 @@ extern int pg_popcount64(uint64 word);
extern uint64 pg_popcount(const char *buf, int bytes);
/*
- * Rotate the bits of "word" to the right by n bits.
+ * Rotate the bits of word to the right/left by n bits.
*/
static inline uint32
pg_rotate_right32(uint32 word, int n)
{
- return (word >> n) | (word << (sizeof(word) * BITS_PER_BYTE - n));
+ return (word >> n) | (word << (32 - n));
+}
+
+static inline uint32
+pg_rotate_left32(uint32 word, int n)
+{
+ return (word << n) | (word >> (32 - n));
}
#endif /* PG_BITUTILS_H */
