1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
// ---------------- [ File: bitcoin-serialize/src/map_into_range.rs ]
crate::ix!();
/**
| 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/
*/
pub fn map_into_range(x: u64, n: u64) -> u64 {
#[cfg(__SIZEOF_INT128__)]
{
return (x as u128 * n as u128) >> 64;
}
// To perform the calculation on 64-bit
// numbers without losing the result to
// overflow, split the numbers into the
// most significant and least significant
// 32 bits and perform multiplication
// piece-wise.
//
// See:
// https://stackoverflow.com/a/26855440
let x_hi: u64 = x >> 32;
let x_lo: u64 = x & 0xFFFFFFFF;
let n_hi: u64 = n >> 32;
let n_lo: u64 = n & 0xFFFFFFFF;
let ac: u64 = x_hi * n_hi;
let ad: u64 = x_hi * n_lo;
let bc: u64 = x_lo * n_hi;
let bd: u64 = x_lo * n_lo;
let mid34: u64 = (bd >> 32) + (bc & 0xFFFFFFFF) + (ad & 0xFFFFFFFF);
let upper64: u64 = ac + (bc >> 32) + (ad >> 32) + (mid34 >> 32);
upper64
}
#[cfg(test)]
mod map_into_range_tests {
use super::*;
fn reference(x: u64, n: u64) -> u64 {
(((x as u128) * (n as u128)) >> 64) as u64
}
#[traced_test]
fn matches_reference() {
const N: u64 = 1_000_003; // arbitrary odd prime
for x in [
0u64,
1,
2,
3,
42,
1 << 20,
u64::MAX / 2,
u64::MAX,
] {
assert_eq!(map_into_range(x, N), reference(x, N));
}
}
#[traced_test]
fn result_always_less_than_n() {
const N: u64 = 123_456_789;
for x in [0, 1, u64::MAX / 3, u64::MAX] {
let y = map_into_range(x, N);
assert!(y < N, "map_into_range({x}, {N}) = {y} ≥ {N}");
}
}
#[traced_test]
fn n_equal_one_maps_to_zero() {
for x in [0u64, 1, 2, 3, u64::MAX] {
assert_eq!(map_into_range(x, 1), 0);
}
}
}