itoa_const/
udiv128.rs

1#[cfg(feature = "no-panic")]
2use 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)]
7const 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
29/// Multiplication”   in Proc. of the SIGPLAN94 Conference on Programming
30/// Language Design and   Implementation, 1994, pp. 61–72
31#[inline]
32#[cfg_attr(feature = "no-panic", no_panic)]
33pub const fn udivmod_1e19(n: u128) -> (u128, u64) {
34    let d = 10_000_000_000_000_000_000_u64; // 10^19
35
36    let quot = if n < 1 << 83 {
37        ((n >> 19) as u64 / (d >> 19)) as u128
38    } else {
39        u128_mulhi(n, 156927543384667019095894735580191660403) >> 62
40    };
41
42    let rem = (n - quot * d as u128) as u64;
43    debug_assert!(quot == n / d as u128);
44    debug_assert!(rem as u128 == n % d as u128);
45
46    (quot, rem)
47}
itoa_const/udiv128.rs

itoa_const/
udiv128.rs
