ruint/algorithms/
mod.rs

Help
1//! ⚠️ Collection of bignum algorithms.
2//!
3//! **Warning.** Most functions in this module are currently not considered part
4//! of the stable API and may be changed or removed in future minor releases.
5
6#![allow(missing_docs)] // TODO: document algorithms
7
8use core::cmp::Ordering;
9
10mod add;
11pub mod div;
12mod gcd;
13mod mul;
14mod mul_redc;
15mod ops;
16mod shift;
17
18pub use self::{
19    add::{adc_n, sbb_n},
20    div::div,
21    gcd::{gcd, gcd_extended, inv_mod, LehmerMatrix},
22    mul::{add_nx1, addmul, addmul_n, addmul_nx1, mul_nx1, submul_nx1},
23    mul_redc::{mul_redc, square_redc},
24    ops::{adc, sbb},
25    shift::{shift_left_small, shift_right_small},
26};
27
28trait DoubleWord<T>: Sized + Copy {
29    fn join(high: T, low: T) -> Self;
30    fn add(a: T, b: T) -> Self;
31    fn mul(a: T, b: T) -> Self;
32    fn muladd(a: T, b: T, c: T) -> Self;
33    fn muladd2(a: T, b: T, c: T, d: T) -> Self;
34
35    fn high(self) -> T;
36    fn low(self) -> T;
37    fn split(self) -> (T, T);
38}
39
40impl DoubleWord<u64> for u128 {
41    #[inline(always)]
42    fn join(high: u64, low: u64) -> Self {
43        (Self::from(high) << 64) | Self::from(low)
44    }
45
46    /// Computes `a + b` as a 128-bit value.
47    #[inline(always)]
48    fn add(a: u64, b: u64) -> Self {
49        Self::from(a) + Self::from(b)
50    }
51
52    /// Computes `a * b` as a 128-bit value.
53    #[inline(always)]
54    fn mul(a: u64, b: u64) -> Self {
55        Self::from(a) * Self::from(b)
56    }
57
58    /// Computes `a * b + c` as a 128-bit value. Note that this can not
59    /// overflow.
60    #[inline(always)]
61    fn muladd(a: u64, b: u64, c: u64) -> Self {
62        Self::from(a) * Self::from(b) + Self::from(c)
63    }
64
65    /// Computes `a * b + c + d` as a 128-bit value. Note that this can not
66    /// overflow.
67    #[inline(always)]
68    fn muladd2(a: u64, b: u64, c: u64, d: u64) -> Self {
69        Self::from(a) * Self::from(b) + Self::from(c) + Self::from(d)
70    }
71
72    #[inline(always)]
73    fn high(self) -> u64 {
74        (self >> 64) as u64
75    }
76
77    #[inline(always)]
78    #[allow(clippy::cast_possible_truncation)]
79    fn low(self) -> u64 {
80        self as u64
81    }
82
83    #[inline(always)]
84    fn split(self) -> (u64, u64) {
85        (self.low(), self.high())
86    }
87}
88
89/// Compare two `u64` slices in reverse order.
90#[inline(always)]
91#[must_use]
92pub fn cmp(left: &[u64], right: &[u64]) -> Ordering {
93    let l = core::cmp::min(left.len(), right.len());
94
95    // Slice to the loop iteration range to enable bound check
96    // elimination in the compiler
97    let lhs = &left[..l];
98    let rhs = &right[..l];
99
100    for i in (0..l).rev() {
101        match i8::from(lhs[i] > rhs[i]) - i8::from(lhs[i] < rhs[i]) {
102            -1 => return Ordering::Less,
103            0 => {}
104            1 => return Ordering::Greater,
105            _ => unsafe { core::hint::unreachable_unchecked() },
106        }
107
108        // Equivalent to:
109        // match lhs[i].cmp(&rhs[i]) {
110        //     Ordering::Equal => {}
111        //     non_eq => return non_eq,
112        // }
113    }
114
115    left.len().cmp(&right.len())
116}
117
118// Helper while [Rust#85532](https://github.com/rust-lang/rust/issues/85532) stabilizes.
119#[inline]
120#[must_use]
121pub const fn carrying_add(lhs: u64, rhs: u64, carry: bool) -> (u64, bool) {
122    let (result, carry_1) = lhs.overflowing_add(rhs);
123    let (result, carry_2) = result.overflowing_add(carry as u64);
124    (result, carry_1 | carry_2)
125}
126
127// Helper while [Rust#85532](https://github.com/rust-lang/rust/issues/85532) stabilizes.
128#[inline]
129#[must_use]
130pub const fn borrowing_sub(lhs: u64, rhs: u64, borrow: bool) -> (u64, bool) {
131    let (result, borrow_1) = lhs.overflowing_sub(rhs);
132    let (result, borrow_2) = result.overflowing_sub(borrow as u64);
133    (result, borrow_1 | borrow_2)
134}
ruint/algorithms/mod.rs

ruint/algorithms/
mod.rs
