dashu_int/modular/
reducer.rs

1use crate::{
2    add_ops::repr::{sub_large, sub_large_dword, sub_large_ref_val},
3    buffer::Buffer,
4    cmp,
5    div_const::{ConstDivisor, ConstDivisorRepr},
6    helper_macros::debug_assert_zero,
7    math,
8    primitive::shrink_dword,
9    repr::{Repr, TypedRepr, TypedReprRef},
10    shift,
11    ubig::UBig,
12};
13use num_modular::Reducer;
14
15use super::{
16    repr::{ReducedDword, ReducedLarge, ReducedRepr, ReducedWord},
17    Reduced,
18};
19
20impl ConstDivisor {
21    /// If target is larger than the normalized divisor, then subtract it once.
22    fn reduce_once(&self, target: UBig) -> UBig {
23        if !self.check(&target) {
24            match &self.0 {
25                ConstDivisorRepr::Single(d) => target - d.normalized_divisor(),
26                ConstDivisorRepr::Double(d) => target - d.normalized_divisor(),
27                ConstDivisorRepr::Large(d) => {
28                    match target.into_repr() {
29                        TypedRepr::Small(s) => UBig::from_dword(s), // no need to reduce
30                        TypedRepr::Large(s) => UBig(sub_large(s, &d.normalized_divisor)),
31                    }
32                }
33            }
34        } else {
35            target
36        }
37    }
38
39    /// Reduce -target
40    fn reduce_negate(&self, target: UBig) -> UBig {
41        match &self.0 {
42            ConstDivisorRepr::Single(d) => d.normalized_divisor() - target,
43            ConstDivisorRepr::Double(d) => d.normalized_divisor() - target,
44            ConstDivisorRepr::Large(d) => match target.into_repr() {
45                TypedRepr::Small(s) => {
46                    UBig(sub_large_dword(d.normalized_divisor.as_ref().into(), s))
47                }
48                TypedRepr::Large(s) => UBig(sub_large_ref_val(&d.normalized_divisor, s)),
49            },
50        }
51    }
52
53    fn convert_from_normalized(&self, target: &UBig) -> Reduced {
54        match &self.0 {
55            ConstDivisorRepr::Single(d) => {
56                Reduced::from_single(ReducedWord(target.try_into().unwrap()), d)
57            }
58            ConstDivisorRepr::Double(d) => {
59                Reduced::from_double(ReducedDword(target.try_into().unwrap()), d)
60            }
61            ConstDivisorRepr::Large(d) => {
62                let mut buf = Buffer::allocate_exact(d.normalized_divisor.len());
63                let words = target.as_words();
64                buf.push_slice(words);
65                buf.push_zeros(d.normalized_divisor.len() - words.len());
66                Reduced::from_large(ReducedLarge(buf.into_boxed_slice()), d)
67            }
68        }
69    }
70
71    fn convert_to_normalized(&self, target: Reduced) -> UBig {
72        // this function is for internal use only!
73        // it's not checked whether `target` is using `self` as the ring!
74        match target.repr() {
75            ReducedRepr::Single(raw, _) => UBig(Repr::from_word(raw.0)),
76            ReducedRepr::Double(raw, _) => UBig(Repr::from_dword(raw.0)),
77            ReducedRepr::Large(raw, _) => {
78                let mut buf = Buffer::from(raw.0.as_ref());
79                buf.pop_zeros();
80                UBig(Repr::from_buffer(buf))
81            }
82        }
83    }
84}
85
86impl Reducer<UBig> for ConstDivisor {
87    #[inline]
88    fn new(m: &UBig) -> Self {
89        ConstDivisor::new(m.clone())
90    }
91
92    fn transform(&self, target: UBig) -> UBig {
93        UBig(match &self.0 {
94            ConstDivisorRepr::Single(d) => Repr::from_word(ReducedWord::from_ubig(&target, d).0),
95            ConstDivisorRepr::Double(d) => Repr::from_dword(ReducedDword::from_ubig(&target, d).0),
96            ConstDivisorRepr::Large(d) => Repr::from_buffer(d.rem_repr(target.into_repr())),
97        })
98    }
99    fn check(&self, target: &UBig) -> bool {
100        // check whether target < self.divisor()
101        match (&self.0, target.repr()) {
102            (ConstDivisorRepr::Single(d), TypedReprRef::RefSmall(dw)) => match shrink_dword(dw) {
103                Some(w) => d.0.check(&w),
104                None => false,
105            },
106            (ConstDivisorRepr::Single(_), TypedReprRef::RefLarge(_)) => false,
107            (ConstDivisorRepr::Double(d), TypedReprRef::RefSmall(dw)) => d.0.check(&dw),
108            (ConstDivisorRepr::Double(_), TypedReprRef::RefLarge(_)) => false,
109            (ConstDivisorRepr::Large(_), TypedReprRef::RefSmall(_)) => true,
110            (ConstDivisorRepr::Large(d), TypedReprRef::RefLarge(words)) => {
111                cmp::cmp_in_place(words, &d.normalized_divisor).is_le()
112                    && words[0] & math::ones_word(d.shift) == 0 // must be shifted
113            }
114        }
115    }
116
117    #[inline]
118    fn modulus(&self) -> UBig {
119        self.value()
120    }
121
122    fn residue(&self, target: UBig) -> UBig {
123        UBig(match target.into_repr() {
124            TypedRepr::Small(dw) => match &self.0 {
125                ConstDivisorRepr::Single(d) => {
126                    Repr::from_word(shrink_dword(dw).unwrap() >> d.0.shift())
127                }
128                ConstDivisorRepr::Double(d) => Repr::from_dword(dw >> d.0.shift()),
129                ConstDivisorRepr::Large(d) => Repr::from_dword(dw >> d.shift),
130            },
131            TypedRepr::Large(mut buffer) => {
132                if let ConstDivisorRepr::Large(d) = &self.0 {
133                    debug_assert_zero!(shift::shr_in_place(&mut buffer, d.shift));
134                    Repr::from_buffer(buffer)
135                } else {
136                    unreachable!()
137                }
138            }
139        })
140    }
141
142    #[inline(always)]
143    fn is_zero(&self, target: &UBig) -> bool {
144        target.is_zero()
145    }
146
147    #[inline]
148    fn add(&self, lhs: &UBig, rhs: &UBig) -> UBig {
149        self.reduce_once(lhs + rhs)
150    }
151    #[inline]
152    fn dbl(&self, target: UBig) -> UBig {
153        self.reduce_once(target << 1)
154    }
155    #[inline]
156    fn sub(&self, lhs: &UBig, rhs: &UBig) -> UBig {
157        if lhs >= rhs {
158            lhs - rhs
159        } else {
160            self.reduce_negate(rhs - lhs)
161        }
162    }
163    #[inline]
164    fn neg(&self, target: UBig) -> UBig {
165        if target.is_zero() {
166            target
167        } else {
168            self.reduce_negate(target)
169        }
170    }
171
172    // for the following operations, copying is relatively cheap and the implementations of
173    // the `Reduced` type are relied on.
174
175    #[inline]
176    fn mul(&self, lhs: &UBig, rhs: &UBig) -> UBig {
177        let lhs = self.convert_from_normalized(lhs);
178        let rhs = self.convert_from_normalized(rhs);
179        self.convert_to_normalized(lhs * rhs)
180    }
181    #[inline]
182    fn sqr(&self, target: UBig) -> UBig {
183        self.convert_to_normalized(self.convert_from_normalized(&target).sqr())
184    }
185    #[inline]
186    fn inv(&self, target: UBig) -> Option<UBig> {
187        self.convert_from_normalized(&target)
188            .inv()
189            .map(|v| self.convert_to_normalized(v))
190    }
191    #[inline]
192    fn pow(&self, base: UBig, exp: &UBig) -> UBig {
193        self.convert_to_normalized(self.convert_from_normalized(&base).pow(exp))
194    }
195}
dashu_int/modular/reducer.rs

dashu_int/modular/
reducer.rs
