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