On Thu, Aug 31, 2023 at 8:51 AM David Christensen <
david.christensen@crunchydata.com> wrote:
> 0005 - utility functions for fast div/mod operations; basically
> montgomery multiplication
+/*
+ * pg_fastmod - calculates the modulus of a 32-bit number against a constant
+ * divisor without using the division operator
+ */
+static inline uint32 pg_fastmod(uint32 n, uint32 divisor, uint64 fastinv)
+{
+#ifdef HAVE_INT128
+ uint64_t lowbits = fastinv * n;
+ return ((uint128)lowbits * divisor) >> 64;
+#else
+ return n % divisor;
+#endif
+}
Requiring 128-bit arithmetic to avoid serious regression is a non-starter as written. Software that relies on fast 128-bit multiplication has to do backflips to get that working on multiple platforms. But I'm not sure it's necessary -- if the max block number is UINT32_MAX and max block size is UINT16_MAX, can't we just use 64-bit multiplication?