1 files changed, 69 insertions, 0 deletions
diff --git a/vendor/compiler_builtins/src/int/specialized_div_rem/asymmetric.rs b/vendor/compiler_builtins/src/int/specialized_div_rem/asymmetric.rs
new file mode 100644
index 000000000..56ce188a3
--- /dev/null
+++ b/vendor/compiler_builtins/src/int/specialized_div_rem/asymmetric.rs
@@ -0,0 +1,69 @@
+/// Creates an unsigned division function optimized for dividing integers with the same
+/// bitwidth as the largest operand in an asymmetrically sized division. For example, x86-64 has an
+/// assembly instruction that can divide a 128 bit integer by a 64 bit integer if the quotient fits
+/// in 64 bits. The 128 bit version of this algorithm would use that fast hardware division to
+/// construct a full 128 bit by 128 bit division.
+#[allow(unused_macros)]
+macro_rules! impl_asymmetric {
+    (
+        $fn:ident, // name of the unsigned division function
+        $zero_div_fn:ident, // function called when division by zero is attempted
+        $half_division:ident, // function for division of a $uX by a $uX
+        $asymmetric_division:ident, // function for division of a $uD by a $uX
+        $n_h:expr, // the number of bits in a $iH or $uH
+        $uH:ident, // unsigned integer with half the bit width of $uX
+        $uX:ident, // unsigned integer with half the bit width of $uD
+        $uD:ident // unsigned integer type for the inputs and outputs of `$fn`
+    ) => {
+        /// Computes the quotient and remainder of `duo` divided by `div` and returns them as a
+        /// tuple.
+        pub fn $fn(duo: $uD, div: $uD) -> ($uD, $uD) {
+            let n: u32 = $n_h * 2;
+
+            let duo_lo = duo as $uX;
+            let duo_hi = (duo >> n) as $uX;
+            let div_lo = div as $uX;
+            let div_hi = (div >> n) as $uX;
+            if div_hi == 0 {
+                if div_lo == 0 {
+                    $zero_div_fn()
+                }
+                if duo_hi < div_lo {
+                    // `$uD` by `$uX` division with a quotient that will fit into a `$uX`
+                    let (quo, rem) = unsafe { $asymmetric_division(duo, div_lo) };
+                    return (quo as $uD, rem as $uD);
+                } else {
+                    // Short division using the $uD by $uX division
+                    let (quo_hi, rem_hi) = $half_division(duo_hi, div_lo);
+                    let tmp = unsafe {
+                        $asymmetric_division((duo_lo as $uD) | ((rem_hi as $uD) << n), div_lo)
+                    };
+                    return ((tmp.0 as $uD) | ((quo_hi as $uD) << n), tmp.1 as $uD);
+                }
+            }
+
+            // This has been adapted from
+            // https://www.codeproject.com/tips/785014/uint-division-modulus which was in turn
+            // adapted from Hacker's Delight. This is similar to the two possibility algorithm
+            // in that it uses only more significant parts of `duo` and `div` to divide a large
+            // integer with a smaller division instruction.
+            let div_lz = div_hi.leading_zeros();
+            let div_extra = n - div_lz;
+            let div_sig_n = (div >> div_extra) as $uX;
+            let tmp = unsafe { $asymmetric_division(duo >> 1, div_sig_n) };
+
+            let mut quo = tmp.0 >> ((n - 1) - div_lz);
+            if quo != 0 {
+                quo -= 1;
+            }
+
+            // Note that this is a full `$uD` multiplication being used here
+            let mut rem = duo - (quo as $uD).wrapping_mul(div);
+            if div <= rem {
+                quo += 1;
+                rem -= div;
+            }
+            return (quo as $uD, rem);
+        }
+    };
+}