uint: div_mod_word use intrinsic u128 division(#406)
@@ -1172,43 +1172,9 @@ macro_rules! construct_uint {
#[inline(always)]
fn div_mod_word(hi: u64, lo: u64, y: u64) -> (u64, u64) {
debug_assert!(hi < y);
- // NOTE: this is slow (__udivti3)
- // let x = (u128::from(hi) << 64) + u128::from(lo);
- // let d = u128::from(d);
- // ((x / d) as u64, (x % d) as u64)
- // TODO: look at https://gmplib.org/~tege/division-paper.pdf
- const TWO32: u64 = 1 << 32;
- let s = y.leading_zeros();
- let y = y << s;
- let (yn1, yn0) = Self::split(y);
- let un32 = (hi << s) | lo.checked_shr(64 - s).unwrap_or(0);
- let un10 = lo << s;
- let (un1, un0) = Self::split(un10);
- let mut q1 = un32 / yn1;
- let mut rhat = un32 - q1 * yn1;
-
- while q1 >= TWO32 || q1 * yn0 > TWO32 * rhat + un1 {
- q1 -= 1;
- rhat += yn1;
- if rhat >= TWO32 {
- break;
- }
- }
-
- let un21 = un32.wrapping_mul(TWO32).wrapping_add(un1).wrapping_sub(q1.wrapping_mul(y));
- let mut q0 = un21 / yn1;
- rhat = un21.wrapping_sub(q0.wrapping_mul(yn1));
-
- while q0 >= TWO32 || q0 * yn0 > TWO32 * rhat + un0 {
- q0 -= 1;
- rhat += yn1;
- if rhat >= TWO32 {
- break;
- }
- }
-
- let rem = un21.wrapping_mul(TWO32).wrapping_add(un0).wrapping_sub(y.wrapping_mul(q0));
- (q1 * TWO32 + q0, rem >> s)
+ let x = (u128::from(hi) << 64) + u128::from(lo);
+ let y = u128::from(y);
+ ((x / y) as u64, (x % y) as u64)
}
#[inline(always)]
