num_bigint/
big_digit.rs

1use alloc::vec::Vec;
2
3// A [`BigDigit`] is a [`BigUint`]'s composing element.
4cfg_digit!(
5    pub(crate) type BigDigit = u32;
6    pub(crate) type BigDigit = u64;
7);
8
9// A [`DoubleBigDigit`] is the internal type used to do the computations.  Its
10// size is the double of the size of [`BigDigit`].
11cfg_digit!(
12    pub(crate) type DoubleBigDigit = u64;
13    pub(crate) type DoubleBigDigit = u128;
14);
15
16pub(crate) const BITS: u8 = BigDigit::BITS as u8;
17pub(crate) const HALF_BITS: u8 = BITS / 2;
18pub(crate) const HALF: BigDigit = (1 << HALF_BITS) - 1;
19
20pub(crate) const MAX: BigDigit = BigDigit::MAX;
21const LO_MASK: DoubleBigDigit = MAX as DoubleBigDigit;
22
23#[inline]
24fn get_hi(n: DoubleBigDigit) -> BigDigit {
25    (n >> BITS) as BigDigit
26}
27#[inline]
28fn get_lo(n: DoubleBigDigit) -> BigDigit {
29    (n & LO_MASK) as BigDigit
30}
31
32/// Split one [`DoubleBigDigit`] into two [`BigDigit`]s.
33#[inline]
34pub(crate) fn from_doublebigdigit(n: DoubleBigDigit) -> (BigDigit, BigDigit) {
35    (get_hi(n), get_lo(n))
36}
37
38/// Join two [`BigDigit`]s into one [`DoubleBigDigit`].
39#[inline]
40pub(crate) fn to_doublebigdigit(hi: BigDigit, lo: BigDigit) -> DoubleBigDigit {
41    DoubleBigDigit::from(lo) | (DoubleBigDigit::from(hi) << BITS)
42}
43
44pub(crate) enum BigDigits {
45    Inline(Option<BigDigit>),
46    Heap(Vec<BigDigit>),
47}
48
49impl BigDigits {
50    pub(crate) const ZERO: Self = BigDigits::Inline(None);
51    pub(crate) const ONE: Self = BigDigits::Inline(Some(1));
52
53    #[inline]
54    pub(crate) const fn from_digit(x: BigDigit) -> Self {
55        if x == 0 {
56            BigDigits::ZERO
57        } else {
58            BigDigits::Inline(Some(x))
59        }
60    }
61
62    #[inline]
63    pub(crate) fn from_slice(slice: &[BigDigit]) -> Self {
64        match slice {
65            &[] => BigDigits::ZERO,
66            &[x] => BigDigits::Inline(Some(x)),
67            xs => BigDigits::Heap(xs.to_vec()),
68        }
69    }
70
71    #[inline]
72    pub(crate) fn from_vec(xs: Vec<BigDigit>) -> Self {
73        BigDigits::Heap(xs)
74    }
75
76    #[inline]
77    pub(crate) fn clear(&mut self) {
78        match self {
79            BigDigits::Inline(x) => *x = None,
80            BigDigits::Heap(xs) => xs.clear(),
81        }
82    }
83
84    #[inline]
85    pub(crate) fn push(&mut self, y: BigDigit) {
86        match &mut *self {
87            BigDigits::Inline(x @ None) => *x = Some(y),
88            BigDigits::Inline(Some(x)) => *self = BigDigits::Heap([*x, y].to_vec()),
89            BigDigits::Heap(xs) => xs.push(y),
90        }
91    }
92
93    #[inline]
94    pub(crate) fn pop(&mut self) -> Option<BigDigit> {
95        match self {
96            BigDigits::Inline(x) => x.take(),
97            BigDigits::Heap(xs) => xs.pop(),
98        }
99    }
100
101    #[inline]
102    pub(crate) fn last(&self) -> Option<&BigDigit> {
103        match self {
104            BigDigits::Inline(x) => x.as_ref(),
105            BigDigits::Heap(xs) => xs.last(),
106        }
107    }
108
109    #[inline]
110    pub(crate) fn len(&self) -> usize {
111        match self {
112            BigDigits::Inline(None) => 0,
113            BigDigits::Inline(Some(_)) => 1,
114            BigDigits::Heap(xs) => xs.len(),
115        }
116    }
117
118    #[inline]
119    pub(crate) fn is_empty(&self) -> bool {
120        match self {
121            BigDigits::Inline(None) => true,
122            BigDigits::Inline(Some(_)) => false,
123            BigDigits::Heap(xs) => xs.is_empty(),
124        }
125    }
126
127    #[inline]
128    pub(crate) fn capacity(&self) -> usize {
129        match self {
130            BigDigits::Inline(_) => 1,
131            BigDigits::Heap(xs) => xs.capacity(),
132        }
133    }
134
135    #[inline]
136    pub(crate) fn shrink(&mut self) {
137        if let BigDigits::Heap(xs) = self {
138            if xs.len() < xs.capacity() / 2 {
139                match **xs {
140                    [] => *self = BigDigits::ZERO,
141                    [x] => *self = BigDigits::Inline(Some(x)),
142                    _ => xs.shrink_to(xs.len() + 1),
143                }
144            }
145        }
146    }
147
148    /// Returns `true` if the most-significant digit (if any) is nonzero.
149    #[inline]
150    pub(crate) fn is_normal(&self) -> bool {
151        match self {
152            BigDigits::Inline(Some(0)) => false,
153            BigDigits::Inline(_) => true,
154            BigDigits::Heap(xs) => !matches!(**xs, [.., 0]),
155        }
156    }
157
158    /// Strips off trailing zero bigdigits - most algorithms require
159    /// the most significant digit in the number to be nonzero.
160    #[inline]
161    pub(crate) fn normalize(&mut self) {
162        match self {
163            BigDigits::Inline(x) => {
164                if let Some(0) = *x {
165                    *x = None;
166                }
167            }
168            BigDigits::Heap(xs) => {
169                if let [.., 0] = **xs {
170                    let len = xs.iter().rposition(|&d| d != 0).map_or(0, |i| i + 1);
171                    xs.truncate(len);
172                }
173                if xs.len() < xs.capacity() / 2 {
174                    match **xs {
175                        [] => *self = BigDigits::ZERO,
176                        [x] => *self = BigDigits::Inline(Some(x)),
177                        _ => xs.shrink_to(xs.len() + 1),
178                    }
179                }
180            }
181        }
182    }
183
184    #[inline]
185    pub(crate) fn truncate(&mut self, len: usize) {
186        match self {
187            BigDigits::Inline(x) => {
188                if len == 0 {
189                    *x = None;
190                }
191            }
192            BigDigits::Heap(xs) => xs.truncate(len),
193        }
194    }
195
196    #[inline]
197    pub(crate) fn drain_front(&mut self, len: usize) {
198        match self {
199            BigDigits::Inline(x) => {
200                assert!(len <= 1);
201                if len == 1 {
202                    *x = None;
203                }
204            }
205            BigDigits::Heap(xs) => {
206                xs.drain(..len);
207            }
208        }
209    }
210
211    pub(crate) fn reserve(&mut self, additional: usize) {
212        match &mut *self {
213            BigDigits::Inline(opt_x) => {
214                let capacity = usize::from(opt_x.is_some()) + additional;
215                if capacity > 1 {
216                    let mut vec = Vec::with_capacity(capacity);
217                    if let Some(x) = *opt_x {
218                        vec.push(x);
219                    }
220                    *self = BigDigits::Heap(vec);
221                }
222            }
223            BigDigits::Heap(xs) => xs.reserve(additional),
224        }
225    }
226
227    pub(crate) fn resize(&mut self, len: usize, value: BigDigit) {
228        match &mut *self {
229            BigDigits::Inline(x) => match len {
230                0 => *x = None,
231                1 => {
232                    if x.is_none() {
233                        *x = Some(value);
234                    }
235                }
236                _ => {
237                    let mut xs = Vec::with_capacity(len);
238                    if let Some(x) = *x {
239                        xs.push(x);
240                    }
241                    xs.resize(len, value);
242                    *self = BigDigits::Heap(xs);
243                }
244            },
245            BigDigits::Heap(xs) => xs.resize(len, value),
246        }
247    }
248
249    pub(crate) fn extend_from_slice(&mut self, ys: &[BigDigit]) {
250        match &mut *self {
251            BigDigits::Inline(None) => *self = BigDigits::from_slice(ys),
252            BigDigits::Inline(Some(x)) => {
253                let len = ys.len() + 1;
254                if len > 1 {
255                    let mut xs = Vec::with_capacity(len);
256                    xs.push(*x);
257                    xs.extend_from_slice(ys);
258                    *self = BigDigits::Heap(xs);
259                }
260            }
261            BigDigits::Heap(xs) => xs.extend_from_slice(ys),
262        }
263    }
264
265    pub(crate) fn extend<I>(&mut self, mut iter: I)
266    where
267        I: ExactSizeIterator<Item = BigDigit>,
268    {
269        match &mut *self {
270            BigDigits::Inline(x) => {
271                if x.is_none() {
272                    match iter.next() {
273                        Some(y) => *x = Some(y),
274                        None => return,
275                    }
276                }
277                if let Some(y) = iter.next() {
278                    let len = iter.len().saturating_add(2);
279                    let mut xs = Vec::with_capacity(len);
280                    xs.push(x.unwrap());
281                    xs.push(y);
282                    xs.extend(iter);
283                    *self = BigDigits::Heap(xs);
284                }
285            }
286            BigDigits::Heap(xs) => xs.extend(iter),
287        }
288    }
289}
290
291impl Clone for BigDigits {
292    #[inline]
293    fn clone(&self) -> Self {
294        match self {
295            BigDigits::Inline(x) => BigDigits::Inline(*x),
296            BigDigits::Heap(xs) => BigDigits::from_slice(xs),
297        }
298    }
299
300    #[inline]
301    fn clone_from(&mut self, source: &Self) {
302        match &mut *self {
303            // Reuse the existing heap allocation if we have one.
304            BigDigits::Heap(xs) if xs.capacity() != 0 => {
305                xs.clear();
306                xs.extend_from_slice(source);
307            }
308            #[allow(clippy::assigning_clones)]
309            _ => *self = source.clone(),
310        }
311    }
312}
313
314impl core::ops::Deref for BigDigits {
315    type Target = [BigDigit];
316
317    #[inline]
318    fn deref(&self) -> &Self::Target {
319        match self {
320            BigDigits::Inline(None) => &[],
321            BigDigits::Inline(Some(x)) => core::slice::from_ref(x),
322            BigDigits::Heap(xs) => xs,
323        }
324    }
325}
326
327impl core::ops::DerefMut for BigDigits {
328    #[inline]
329    fn deref_mut(&mut self) -> &mut Self::Target {
330        match self {
331            BigDigits::Inline(None) => &mut [],
332            BigDigits::Inline(Some(x)) => core::slice::from_mut(x),
333            BigDigits::Heap(xs) => xs,
334        }
335    }
336}
num_bigint/big_digit.rs

num_bigint/
big_digit.rs
