From dd30f5c701609a8c6dc09b9b48967df54767b7ed Mon Sep 17 00:00:00 2001
From: tylo <tylo@norceresearch.no>
Date: Mon, 9 Mar 2020 19:28:43 +0100
Subject: fast_reduce

---
 cmap.h | 7 +++++++
 1 file changed, 7 insertions(+)

diff --git a/cmap.h b/cmap.h
index 1bc8a615..fb3845a4 100644
--- a/cmap.h
+++ b/cmap.h
@@ -207,4 +207,11 @@ typedef Value cmap_##tag##_value_t
 #define FIBONACCI_DECL  size_t fib1 = 0, fib2 = 1, fibx
 #define FIBONACCI_NEXT  (fibx = fib1 + fib2, fib1 = fib2, fib2 = fibx)
 
+// https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/
+// 
+static inline uint32_t fast_reduce(uint32_t x, uint32_t N) {
+    return ((uint64_t) x * (uint64_t) N) >> 32;
+}
+#define cmap_reduce(x, N) ((uint32_t)(((uint64_t) (x) * (uint64_t) (N)) >> 32))
+
 #endif
-- 
cgit v1.2.3