ruint/algorithms/
mod.rs

1//! ⚠️ Collection of bignum algorithms.
2//!
3//! <div class="warning">
4//! Functions in this module are currently not considered part of the stable API
5//! and may be changed or removed in future minor releases, without prior
6//! notice.
7//! </div>
8
9#![allow(missing_docs)] // TODO: document algorithms
10
11macro_rules! unstable_warning {
12    () => {
13        "\n\n<div class=\"warning\">⚠️ This function is not part of the stable API.</div>\n\n"
14    };
15}
16pub(crate) use unstable_warning;
17
18use core::cmp::Ordering;
19
20mod add;
21pub mod div;
22mod gcd;
23mod mul;
24mod mul_redc;
25mod shift;
26
27pub use self::{
28    add::{borrowing_sub, borrowing_sub_n, carrying_add, carrying_add_n},
29    div::div,
30    gcd::{gcd, gcd_extended, inv_mod, LehmerMatrix},
31    mul::{add_nx1, addmul, addmul_n, addmul_nx1, mul_nx1, submul_nx1},
32    mul_redc::{mul_redc, square_redc},
33    shift::{shift_left_small, shift_right_small},
34};
35
36pub(crate) trait DoubleWord<T: Default>: Sized + Copy {
37    /// `high << 64 | low`
38    fn join(high: T, low: T) -> Self;
39    /// `(low, high)`
40    fn split(self) -> (T, T);
41
42    /// `a * b + c + d`
43    fn muladd2(a: T, b: T, c: T, d: T) -> Self;
44
45    /// `a + b`
46    #[inline(always)]
47    fn add(a: T, b: T) -> Self {
48        Self::muladd2(T::default(), T::default(), a, b)
49    }
50    /// `a * b`
51    #[inline(always)]
52    fn mul(a: T, b: T) -> Self {
53        Self::muladd2(a, b, T::default(), T::default())
54    }
55    /// `a * b + c`
56    #[inline(always)]
57    fn muladd(a: T, b: T, c: T) -> Self {
58        Self::muladd2(a, b, c, T::default())
59    }
60
61    #[inline(always)]
62    fn high(self) -> T {
63        self.split().1
64    }
65    #[inline(always)]
66    fn low(self) -> T {
67        self.split().0
68    }
69}
70
71#[allow(clippy::cast_possible_truncation)]
72impl DoubleWord<u64> for u128 {
73    #[inline(always)]
74    fn join(high: u64, low: u64) -> Self {
75        (Self::from(high) << 64) | Self::from(low)
76    }
77
78    #[inline(always)]
79    fn split(self) -> (u64, u64) {
80        (self as u64, (self >> 64) as u64)
81    }
82
83    #[inline(always)]
84    fn muladd2(a: u64, b: u64, c: u64, d: u64) -> Self {
85        #[cfg(feature = "nightly")]
86        {
87            let (low, high) = u64::carrying_mul_add(a, b, c, d);
88            Self::join(high, low)
89        }
90        #[cfg(not(feature = "nightly"))]
91        {
92            Self::from(a) * Self::from(b) + Self::from(c) + Self::from(d)
93        }
94    }
95}
96
97/// ⚠️ Compare two limb slices in reverse order.
98#[doc = crate::algorithms::unstable_warning!()]
99/// Assumes that if the slices are of different length, the longer slice is
100/// always greater than the shorter slice.
101#[inline(always)]
102#[must_use]
103pub fn cmp(a: &[u64], b: &[u64]) -> Ordering {
104    match a.len().cmp(&b.len()) {
105        Ordering::Equal => {}
106        non_eq => return non_eq,
107    }
108    for i in (0..a.len()).rev() {
109        match i8::from(a[i] > b[i]) - i8::from(a[i] < b[i]) {
110            -1 => return Ordering::Less,
111            0 => {}
112            1 => return Ordering::Greater,
113            _ => unsafe { core::hint::unreachable_unchecked() },
114        }
115
116        // Equivalent to the following code, but on older rustc versions
117        // performs better:
118        // match a[i].cmp(&b[i]) {
119        //     Ordering::Equal => {}
120        //     non_eq => return non_eq,
121        // }
122    }
123    Ordering::Equal
124}
125
126#[inline]
127pub(crate) const fn trim_end_zeros(mut x: &[u64]) -> &[u64] {
128    while let [rest @ .., 0] = x {
129        x = rest;
130    }
131    x
132}
133
134#[inline]
135pub(crate) fn trim_end_zeros_mut(mut x: &mut [u64]) -> &mut [u64] {
136    while let [rest @ .., 0] = x {
137        x = rest;
138    }
139    x
140}
ruint/algorithms/mod.rs

ruint/algorithms/
mod.rs
