ruint/algorithms/
mod.rs

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;
14#[cfg(feature = "alloc")] // TODO: Make mul_redc alloc-free
15mod mul_redc;
16mod ops;
17mod shift;
18
19pub use self::{
20    add::{adc_n, sbb_n},
21    div::div,
22    gcd::{gcd, gcd_extended, inv_mod, LehmerMatrix},
23    mul::{add_nx1, addmul, addmul_n, addmul_nx1, addmul_ref, mul_nx1, submul_nx1},
24    ops::{adc, sbb},
25    shift::{shift_left_small, shift_right_small},
26};
27#[cfg(feature = "alloc")]
28pub use mul_redc::mul_redc;
29
30trait DoubleWord<T>: Sized + Copy {
31    fn join(high: T, low: T) -> Self;
32    fn add(a: T, b: T) -> Self;
33    fn mul(a: T, b: T) -> Self;
34    fn muladd(a: T, b: T, c: T) -> Self;
35    fn muladd2(a: T, b: T, c: T, d: T) -> Self;
36
37    fn high(self) -> T;
38    fn low(self) -> T;
39    fn split(self) -> (T, T);
40}
41
42impl DoubleWord<u64> for u128 {
43    #[inline(always)]
44    fn join(high: u64, low: u64) -> Self {
45        (Self::from(high) << 64) | Self::from(low)
46    }
47
48    /// Computes `a + b` as a 128-bit value.
49    #[inline(always)]
50    fn add(a: u64, b: u64) -> Self {
51        Self::from(a) + Self::from(b)
52    }
53
54    /// Computes `a * b` as a 128-bit value.
55    #[inline(always)]
56    fn mul(a: u64, b: u64) -> Self {
57        Self::from(a) * Self::from(b)
58    }
59
60    /// Computes `a * b + c` as a 128-bit value. Note that this can not
61    /// overflow.
62    #[inline(always)]
63    fn muladd(a: u64, b: u64, c: u64) -> Self {
64        Self::from(a) * Self::from(b) + Self::from(c)
65    }
66
67    /// Computes `a * b + c + d` as a 128-bit value. Note that this can not
68    /// overflow.
69    #[inline(always)]
70    fn muladd2(a: u64, b: u64, c: u64, d: u64) -> Self {
71        Self::from(a) * Self::from(b) + Self::from(c) + Self::from(d)
72    }
73
74    #[inline(always)]
75    fn high(self) -> u64 {
76        (self >> 64) as u64
77    }
78
79    #[inline(always)]
80    #[allow(clippy::cast_possible_truncation)]
81    fn low(self) -> u64 {
82        self as u64
83    }
84
85    #[inline(always)]
86    fn split(self) -> (u64, u64) {
87        (self.low(), self.high())
88    }
89}
90
91/// Compare two `u64` slices in reverse order.
92#[inline(always)]
93#[must_use]
94pub fn cmp(left: &[u64], right: &[u64]) -> Ordering {
95    let l = core::cmp::min(left.len(), right.len());
96
97    // Slice to the loop iteration range to enable bound check
98    // elimination in the compiler
99    let lhs = &left[..l];
100    let rhs = &right[..l];
101
102    for i in (0..l).rev() {
103        match i8::from(lhs[i] > rhs[i]) - i8::from(lhs[i] < rhs[i]) {
104            -1 => return Ordering::Less,
105            0 => {}
106            1 => return Ordering::Greater,
107            _ => unsafe { core::hint::unreachable_unchecked() },
108        }
109
110        // Equivalent to:
111        // match lhs[i].cmp(&rhs[i]) {
112        //     Ordering::Equal => {}
113        //     non_eq => return non_eq,
114        // }
115    }
116
117    left.len().cmp(&right.len())
118}
ruint/algorithms/mod.rs

ruint/algorithms/
mod.rs
