src/vendor/itoa/src/udiv128.rs

   1 // Copyright 2009-2016 compiler-builtins Developers
   2 //
   3 // The compiler-builtins crate is dual licensed under both the University of
   4 // Illinois "BSD-Like" license and the MIT license.  As a user of this code you may
   5 // choose to use it under either license. As a contributor, you agree to allow
   6 // your code to be used under both.
   7 //
   8 // Full text of the relevant licenses is found here:
   9 // https://github.com/rust-lang-nursery/compiler-builtins/blob/master/LICENSE.TXT
  10 //
  11 //
  12 //
  13 // The following code is based on Rust’s [compiler-builtins crate]
  14 // (https://github.com/rust-lang-nursery/compiler-builtins) which
  15 // provides runtime functions for the Rust programs. The Rust
  16 // compiler will automatically link your programs against this crate.
  17 //
  18 // We copied the implementation of '__udivmodti4()' which is an intrinsic
  19 // implementing division with remainder for architectures without 128-bit integer support.
  20 // We have done this two reasons, to work around [bad optimization by LLVM]
  21 // (https://github.com/rust-lang/rust/issues/44545) and to allow function
  22 // inlining which doesn’t happen with the intrinsic.
  23
  24 #[inline]
  25 pub fn udivmod_1e19(n: u128) -> (u128, u64) {
  26     let d = 10_000_000_000_000_000_000_u64; // 10^19
  27
  28     let high = (n >> 64) as u64;
  29     if high == 0 {
  30         let low = n as u64;
  31         return ((low / d) as u128, low % d);
  32     }
  33
  34     let sr = 65 - high.leading_zeros();
  35
  36     // 2 <= sr <= 65
  37     let mut q: u128 = n << (128 - sr);
  38     let mut r: u128 = n >> sr;
  39     let mut carry: u64 = 0;
  40
  41     // Don't use a range because they may generate references to memcpy in unoptimized code
  42     //
  43     // Loop invariants:  r < d; carry is 0 or 1
  44     let mut i = 0;
  45     while i < sr {
  46         i += 1;
  47
  48         // r:q = ((r:q) << 1) | carry
  49         r = (r << 1) | (q >> 127);
  50         q = (q << 1) | carry as u128;
  51
  52         // carry = 0
  53         // if r >= d {
  54         //     r -= d;
  55         //     carry = 1;
  56         // }
  57         let s = (d as u128).wrapping_sub(r).wrapping_sub(1) as i128 >> 127;
  58         carry = (s & 1) as u64;
  59         r -= (d as u128) & s as u128;
  60     }
  61
  62     ((q << 1) | carry as u128, r as u64)
  63 }