From efab28b06bfaa50c41337e84136cb58437e7ba00 Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Thu, 6 Jan 2022 11:46:50 -0500 Subject: Add FastRange32 function and use it throughout the codebase --- src/util/fastrange.h | 20 +++++++++++++++----- 1 file changed, 15 insertions(+), 5 deletions(-) (limited to 'src/util/fastrange.h') diff --git a/src/util/fastrange.h b/src/util/fastrange.h index 963d21c03a..77cb883ce0 100644 --- a/src/util/fastrange.h +++ b/src/util/fastrange.h @@ -7,11 +7,21 @@ #include -// Map a value x that is uniformly distributed in the range [0, 2^64) to a -// value uniformly distributed in [0, n) by returning the upper 64 bits of -// x * n. -// -// See: https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/ +/* This file offers implementations of the fast range reduction technique described + * in https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/ + * + * In short, they take an integer x and a range n, and return the upper bits of + * (x * n). If x is uniformly distributed over its domain, the result is as close to + * uniformly distributed over [0, n) as (x mod n) would be, but significantly faster. + */ + +/** Fast range reduction with 32-bit input and 32-bit range. */ +static inline uint32_t FastRange32(uint32_t x, uint32_t n) +{ + return (uint64_t{x} * n) >> 32; +} + +/** Fast range reduction with 64-bit input and 64-bit range. */ static inline uint64_t FastRange64(uint64_t x, uint64_t n) { #ifdef __SIZEOF_INT128__ -- cgit v1.2.3