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 | } |

49 | |