blob: df53eb526d4feefed6945bf5f52d13fd3707060a (
plain)
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
|
/// Multiply unsigned 128 bit integers, return upper 128 bits of the result
#[inline]
fn u128_mulhi(x: u128, y: u128) -> u128 {
let x_lo = x as u64;
let x_hi = (x >> 64) as u64;
let y_lo = y as u64;
let y_hi = (y >> 64) as u64;
// handle possibility of overflow
let carry = (x_lo as u128 * y_lo as u128) >> 64;
let m = x_lo as u128 * y_hi as u128 + carry;
let high1 = m >> 64;
let m_lo = m as u64;
let high2 = (x_hi as u128 * y_lo as u128 + m_lo as u128) >> 64;
x_hi as u128 * y_hi as u128 + high1 + high2
}
/// Divide `n` by 1e19 and return quotient and remainder
///
/// Integer division algorithm is based on the following paper:
///
/// T. Granlund and P. Montgomery, “Division by Invariant Integers Using Multiplication”
/// in Proc. of the SIGPLAN94 Conference on Programming Language Design and
/// Implementation, 1994, pp. 61–72
///
#[inline]
pub fn udivmod_1e19(n: u128) -> (u128, u64) {
let d = 10_000_000_000_000_000_000_u64; // 10^19
let quot = if n < 1 << 83 {
((n >> 19) as u64 / (d >> 19)) as u128
} else {
u128_mulhi(n, 156927543384667019095894735580191660403) >> 62
};
let rem = (n - quot * d as u128) as u64;
debug_assert_eq!(quot, n / d as u128);
debug_assert_eq!(rem as u128, n % d as u128);
(quot, rem)
}
|
