dashu_int/modular/
convert.rs

1//! Conversion between Modulo, UBig and IBig.
2
3use crate::{
4    arch::word::{DoubleWord, Word},
5    buffer::Buffer,
6    div_const::{ConstDivisorRepr, ConstDoubleDivisor, ConstLargeDivisor, ConstSingleDivisor},
7    fast_div::ConstDivisor,
8    helper_macros::debug_assert_zero,
9    ibig::IBig,
10    primitive::shrink_dword,
11    repr::{Repr, TypedReprRef::*},
12    shift,
13    ubig::UBig,
14    Sign::*,
15};
16use dashu_base::UnsignedAbs;
17
18use super::repr::{Reduced, ReducedDword, ReducedLarge, ReducedRepr, ReducedWord};
19
20impl Reduced<'_> {
21    /// Get the residue in range `0..n` in an n-element ring.
22    ///
23    /// # Examples
24    ///
25    /// ```
26    /// # use dashu_int::{fast_div::ConstDivisor, UBig};
27    /// let ring = ConstDivisor::new(UBig::from(100u8));
28    /// let x = ring.reduce(-1234);
29    /// assert_eq!(x.residue(), UBig::from(66u8));
30    /// ```
31    #[inline]
32    pub fn residue(&self) -> UBig {
33        let repr = match self.repr() {
34            ReducedRepr::Single(raw, ring) => Repr::from_word(raw.residue(ring)),
35            ReducedRepr::Double(raw, ring) => Repr::from_dword(raw.residue(ring)),
36            ReducedRepr::Large(raw, ring) => Repr::from_buffer(raw.residue(ring)),
37        };
38        UBig(repr)
39    }
40
41    /// Get the modulus of the ring that this element belongs to.
42    pub fn modulus(&self) -> UBig {
43        let repr = match self.repr() {
44            ReducedRepr::Single(_, ring) => Repr::from_word(ring.divisor()),
45            ReducedRepr::Double(_, ring) => Repr::from_dword(ring.divisor()),
46            ReducedRepr::Large(_, ring) => Repr::from_buffer(ring.divisor()),
47        };
48        UBig(repr)
49    }
50}
51
52impl ReducedWord {
53    #[inline]
54    pub fn from_ubig(x: &UBig, ring: &ConstSingleDivisor) -> Self {
55        Self(match x.repr() {
56            RefSmall(dword) => {
57                if let Some(word) = shrink_dword(dword) {
58                    ring.rem_word(word)
59                } else {
60                    ring.rem_dword(dword)
61                }
62            }
63            RefLarge(words) => ring.rem_large(words),
64        })
65    }
66
67    #[inline]
68    pub fn residue(self, ring: &ConstSingleDivisor) -> Word {
69        debug_assert!(self.is_valid(ring));
70        self.0 >> ring.shift()
71    }
72}
73
74impl ReducedDword {
75    #[inline]
76    pub fn from_ubig(x: &UBig, ring: &ConstDoubleDivisor) -> Self {
77        Self(match x.repr() {
78            RefSmall(dword) => ring.rem_dword(dword),
79            RefLarge(words) => ring.rem_large(words),
80        })
81    }
82
83    #[inline]
84    pub fn residue(self, ring: &ConstDoubleDivisor) -> DoubleWord {
85        debug_assert!(self.is_valid(ring));
86        self.0 >> ring.shift()
87    }
88}
89
90impl ReducedLarge {
91    pub fn from_ubig(x: UBig, ring: &ConstLargeDivisor) -> ReducedLarge {
92        let mut buffer = ring.rem_repr(x.into_repr());
93        let modulus_len = ring.normalized_divisor.len();
94        buffer.ensure_capacity_exact(modulus_len);
95        buffer.push_zeros(modulus_len - buffer.len());
96        Self(buffer.into_boxed_slice())
97    }
98
99    pub fn residue(&self, ring: &ConstLargeDivisor) -> Buffer {
100        let mut buffer: Buffer = self.0.as_ref().into();
101        debug_assert_zero!(shift::shr_in_place(&mut buffer, ring.shift));
102        buffer
103    }
104}
105
106/// Trait for types that can be converted into an [IntoRing::RingElement] by a `RingReducer`.
107pub trait IntoRing<'a, RingReducer> {
108    type RingElement: 'a;
109    fn into_ring(self, reducer: &'a RingReducer) -> Self::RingElement;
110}
111
112impl<'a> IntoRing<'a, ConstDivisor> for UBig {
113    type RingElement = Reduced<'a>;
114    #[inline]
115    fn into_ring(self, ring: &ConstDivisor) -> Reduced {
116        match &ring.0 {
117            ConstDivisorRepr::Single(ring) => {
118                Reduced::from_single(ReducedWord::from_ubig(&self, ring), ring)
119            }
120            ConstDivisorRepr::Double(ring) => {
121                Reduced::from_double(ReducedDword::from_ubig(&self, ring), ring)
122            }
123            ConstDivisorRepr::Large(ring) => {
124                Reduced::from_large(ReducedLarge::from_ubig(self, ring), ring)
125            }
126        }
127    }
128}
129
130impl<'a> IntoRing<'a, ConstDivisor> for IBig {
131    type RingElement = Reduced<'a>;
132
133    #[inline]
134    fn into_ring(self, ring: &ConstDivisor) -> Reduced {
135        let sign = self.sign();
136        let modulo = self.unsigned_abs().into_ring(ring);
137        match sign {
138            Positive => modulo,
139            Negative => -modulo,
140        }
141    }
142}
143
144/// Implement `IntoModulo` for unsigned primitives.
145macro_rules! impl_into_ring_for_unsigned {
146    ($t:ty) => {
147        impl<'a> IntoRing<'a, ConstDivisor> for $t {
148            type RingElement = Reduced<'a>;
149            #[inline]
150            fn into_ring(self, ring: &'a ConstDivisor) -> Reduced<'a> {
151                UBig::from(self).into_ring(ring)
152            }
153        }
154    };
155}
156
157/// Implement `IntoModulo` for signed primitives.
158macro_rules! impl_into_modulo_for_signed {
159    ($t:ty) => {
160        impl<'a> IntoRing<'a, ConstDivisor> for $t {
161            type RingElement = Reduced<'a>;
162            #[inline]
163            fn into_ring(self, ring: &'a ConstDivisor) -> Reduced<'a> {
164                IBig::from(self).into_ring(ring)
165            }
166        }
167    };
168}
169
170impl_into_ring_for_unsigned!(bool);
171impl_into_ring_for_unsigned!(u8);
172impl_into_ring_for_unsigned!(u16);
173impl_into_ring_for_unsigned!(u32);
174impl_into_ring_for_unsigned!(u64);
175impl_into_ring_for_unsigned!(u128);
176impl_into_ring_for_unsigned!(usize);
177impl_into_modulo_for_signed!(i8);
178impl_into_modulo_for_signed!(i16);
179impl_into_modulo_for_signed!(i32);
180impl_into_modulo_for_signed!(i64);
181impl_into_modulo_for_signed!(i128);
182impl_into_modulo_for_signed!(isize);
183
184impl ConstDivisor {
185    /// Create an element of the modulo ring from another type.
186    ///
187    /// # Examples
188    ///
189    /// ```
190    /// # use dashu_int::{fast_div::ConstDivisor, UBig, IBig};
191    /// let ring = ConstDivisor::new(UBig::from(100u8));
192    /// let x = ring.reduce(-1234);
193    /// let y = ring.reduce(IBig::from(3366));
194    /// assert!(x == y);
195    /// ```
196    pub fn reduce<'a, T: IntoRing<'a, ConstDivisor, RingElement = Reduced<'a>>>(
197        &'a self,
198        x: T,
199    ) -> Reduced {
200        x.into_ring(self)
201    }
202}
dashu_int/modular/convert.rs

dashu_int/modular/
convert.rs
