1 /// Multiply unsigned 128 bit integers, return upper 128 bits of the result
2 #[inline]
u128_mulhi(x: u128, y: u128) -> u1283 fn u128_mulhi(x: u128, y: u128) -> u128 {
4 let x_lo = x as u64;
5 let x_hi = (x >> 64) as u64;
6 let y_lo = y as u64;
7 let y_hi = (y >> 64) as u64;
8
9 // handle possibility of overflow
10 let carry = (x_lo as u128 * y_lo as u128) >> 64;
11 let m = x_lo as u128 * y_hi as u128 + carry;
12 let high1 = m >> 64;
13
14 let m_lo = m as u64;
15 let high2 = (x_hi as u128 * y_lo as u128 + m_lo as u128) >> 64;
16
17 x_hi as u128 * y_hi as u128 + high1 + high2
18 }
19
20 /// Divide `n` by 1e19 and return quotient and remainder
21 ///
22 /// Integer division algorithm is based on the following paper:
23 ///
24 /// T. Granlund and P. Montgomery, “Division by Invariant Integers Using Multiplication”
25 /// in Proc. of the SIGPLAN94 Conference on Programming Language Design and
26 /// Implementation, 1994, pp. 61–72
27 ///
28 #[inline]
udivmod_1e19(n: u128) -> (u128, u64)29 pub fn udivmod_1e19(n: u128) -> (u128, u64) {
30 let d = 10_000_000_000_000_000_000_u64; // 10^19
31
32 let quot = if n < 1 << 83 {
33 ((n >> 19) as u64 / (d >> 19)) as u128
34 } else {
35 u128_mulhi(n, 156927543384667019095894735580191660403) >> 62
36 };
37
38 let rem = (n - quot * d as u128) as u64;
39 debug_assert_eq!(quot, n / d as u128);
40 debug_assert_eq!(rem as u128, n % d as u128);
41
42 (quot, rem)
43 }
44