> + * 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-bitmultiplication has to do backflips to get that working on multiple platforms. But I'm not sure it's necessary --
ifthe max block number is UINT32_MAX and max block size is UINT16_MAX, can't we just use 64-bit multiplication?
I was definitely hand-waving additional implementation here for
non-native 128 bit support; the modulus algorithm as presented
requires 4 times the space as the divisor, so a uint16 implementation
should work for all 64-bit machines. Certainly open to other ideas or
implementations, this was the one I was able to find initially. If
the 16bit approach is all that is needed in practice we can also see
about narrowing the domain and not worry about making this a
general-purpose function.
Best,
David