bigdecimal/bigdigit/
endian.rs

1//! Structs and traits for generic operations on big or little endian ints
2
3use crate::*;
4
5use crate::stdlib;
6use crate::stdlib::fmt;
7use crate::stdlib::Vec;
8
9#[cfg(not(rustc_1_75))]
10use stdlib::Box;
11
12use num_traits::{Zero, PrimInt};
13
14use super::radix::RadixType;
15
16/// Trait to allow generic parameterization of significant digit ordering
17#[allow(dead_code)]
18pub(crate) trait Endianness: Copy + Clone + Default + fmt::Debug {
19    /// Name to use for debugging
20    const NAME: &'static str;
21
22    /// Iterate over digits in vec from least to most significance
23    #[cfg(rustc_1_75)]
24    fn into_iter<'a, D: 'a>(digits: Vec<D>) -> impl LeBigDigitIterator<'a, D>;
25
26    /// Iterate in slice from least to most significance
27    #[cfg(rustc_1_75)]
28    fn iter_slice<D>(digits: &[D]) -> impl LeBigDigitIterator<'_, &D>;
29
30    /// Iterate over mut digits in slice from least to most significance
31    #[cfg(rustc_1_75)]
32    fn iter_slice_mut<D>(digits: &mut [D]) -> impl LeBigDigitIterator<'_, &mut D>;
33
34    #[cfg(not(rustc_1_75))]
35    fn into_iter<'a, D: 'a>(digits: Vec<D>) -> LittleEndianBigDigitIter<'a, D>;
36
37    #[cfg(not(rustc_1_75))]
38    fn iter_slice<D>(digits: &[D]) -> LittleEndianBigDigitIter<'_, &D>;
39
40    #[cfg(not(rustc_1_75))]
41    fn iter_slice_mut<D>(digits: &mut [D]) -> LittleEndianBigDigitIter<'_, &mut D>;
42
43    #[cfg(rustc_1_75)]
44    fn addassign_carry_into_slice_at<R: RadixType>(
45        digits: &mut [R::Base],
46        carry: &mut R::Base,
47        idx: usize,
48    ) {
49        for dest in Self::iter_slice_mut(digits).skip(idx) {
50            R::addassign_carry(dest, carry);
51            if carry.is_zero() {
52                return;
53            }
54        }
55    }
56
57    #[cfg(not(rustc_1_75))]
58    fn addassign_carry_into_slice_at<R: RadixType>(
59        digits: &mut [R::Base],
60        carry: &mut R::Base,
61        idx: usize,
62    );
63
64    /// Place given digit at the most-significant end of the vecor
65    fn push_significant_digit<D>(digits: &mut Vec<D>, d: D);
66
67    /// Split slice into most-significant digit and 'the rest'
68    ///
69    /// If slice is empty zero and empty-slice is returned
70    fn split_most_significant_digit<D: Zero + PrimInt>(digits: &[D]) -> (D, &[D]);
71
72    /// Split significant zeros from digits returning pair (digits, zeros)
73    fn split_significant_zeros<D: Zero>(digits: &[D]) -> (&[D], &[D]);
74
75    /// Split slice into 'count' low-significant digits, and remaining
76    /// significant digits
77    fn split_least_significant<D>(digits: &[D], count: usize) -> (&[D], &[D]);
78
79    /// Split mutable slice into 'count' low-significant digits, and
80    /// remaining significant digits
81    fn split_least_significant_mut<D>(digits: &mut [D], count: usize) -> (&mut [D], &mut [D]);
82
83    /// Remove any zeros at the location of highest significance, if all zeros
84    /// the vector will be cleared
85    fn strip_significant_zeros<D: Copy + Zero>(digits: &mut Vec<D>);
86
87    /// return number of consecutive zeros starting at significant
88    fn count_significant_zeros<D: Zero>(digits: &[D]) -> usize {
89        Self::iter_slice(digits).rev().position(|d| !d.is_zero()).unwrap_or(digits.len())
90    }
91
92    /// Remove 'n' insignificant digits from the vector, and MAY remove leading significant zeros
93    fn remove_insignificant_digits<D: Zero + Copy>(digits: &mut Vec<D>, n: usize);
94
95    /// Correctly order a slice of little endian digits
96    ///
97    /// Reverses for BigEndian, no-op for LittleEndian
98    fn reorder_le_digits<D: Copy>(digits: &mut [D]);
99
100    /// Reorder vector of big-endian digits to this endianness
101    ///
102    /// Removes trailing zeros
103    fn reorder_be_vec<D: Zero + Copy>(digits: &mut Vec<D>);
104
105    /// Consider digits in slice past 'idx' to be little-endian digits
106    /// of higher significance than those below; move them to correct
107    /// position in the slice
108    ///
109    /// This will be a no-op for LittleEndian, and a rotate and reverse for BigEndian
110    ///
111    fn rotate_trailing_le_digits_at<D: Copy>(digits: &mut [D], idx: usize);
112
113    /// Extract digits in correct order from bigiuint
114    fn bigint_to_digits(n: &num_bigint::BigUint) -> Vec<u8>;
115
116    /// Build BigUint from base-10 digits in slice
117    fn biguint_from_digits(n: &[u8]) -> Option<num_bigint::BigUint>;
118
119    /// Split u128 and store in vector
120    fn fill_vec_with_u128<R: RadixType>(vec: &mut Vec<R::Base>, n: u128);
121}
122
123
124/// Empty struct indicating most-significant bigdigit first
125#[derive(#[automatically_derived]
impl ::core::marker::Copy for BigEndian { }Copy, #[automatically_derived]
impl ::core::clone::Clone for BigEndian {
    #[inline]
    fn clone(&self) -> BigEndian { *self }
}Clone, #[automatically_derived]
impl ::core::fmt::Debug for BigEndian {
    #[inline]
    fn fmt(&self, f: &mut ::core::fmt::Formatter) -> ::core::fmt::Result {
        ::core::fmt::Formatter::write_str(f, "BigEndian")
    }
}Debug, #[automatically_derived]
impl ::core::default::Default for BigEndian {
    #[inline]
    fn default() -> BigEndian { BigEndian {} }
}Default)]
126pub(crate) struct BigEndian {}
127
128/// Empty struct indicating least-significant bigdigit first
129#[derive(#[automatically_derived]
impl ::core::marker::Copy for LittleEndian { }Copy, #[automatically_derived]
impl ::core::clone::Clone for LittleEndian {
    #[inline]
    fn clone(&self) -> LittleEndian { *self }
}Clone, #[automatically_derived]
impl ::core::fmt::Debug for LittleEndian {
    #[inline]
    fn fmt(&self, f: &mut ::core::fmt::Formatter) -> ::core::fmt::Result {
        ::core::fmt::Formatter::write_str(f, "LittleEndian")
    }
}Debug, #[automatically_derived]
impl ::core::default::Default for LittleEndian {
    #[inline]
    fn default() -> LittleEndian { LittleEndian {} }
}Default)]
130pub(crate) struct LittleEndian {}
131
132impl Endianness for BigEndian {
133    const NAME: &'static str = "BE";
134
135    #[cfg(rustc_1_75)]
136    fn into_iter<'a, D: 'a>(digits: Vec<D>) -> impl LeBigDigitIterator<'a, D> {
137        digits.into_iter().rev()
138    }
139
140    #[cfg(rustc_1_75)]
141    fn iter_slice<D>(digits: &[D]) -> impl LeBigDigitIterator<'_, &D> {
142        digits.iter().rev()
143    }
144
145    #[cfg(rustc_1_75)]
146    fn iter_slice_mut<D>(digits: &mut [D]) -> impl LeBigDigitIterator<'_, &mut D> {
147        digits.iter_mut().rev()
148    }
149
150    #[cfg(not(rustc_1_75))]
151    fn into_iter<'a, D: 'a>(digits: Vec<D>) -> LittleEndianBigDigitIter<'a, D> {
152        LittleEndianBigDigitIter {
153            digits: Box::new(digits.into_iter().rev()),
154        }
155    }
156
157    #[cfg(not(rustc_1_75))]
158    fn iter_slice<D>(digits: &[D]) -> LittleEndianBigDigitIter<'_, &D> {
159        LittleEndianBigDigitIter {
160            digits: Box::new(digits.iter().rev()),
161        }
162    }
163
164    #[cfg(not(rustc_1_75))]
165    fn iter_slice_mut<D>(digits: &mut [D]) -> LittleEndianBigDigitIter<'_, &mut D> {
166        LittleEndianBigDigitIter {
167            digits: Box::new(digits.iter_mut().rev()),
168        }
169    }
170
171    #[cfg(not(rustc_1_75))]
172    fn addassign_carry_into_slice_at<R: RadixType>(
173        digits: &mut [R::Base],
174        carry: &mut R::Base,
175        idx: usize,
176    ) {
177        for dest in digits.iter_mut().rev().skip(idx) {
178            R::addassign_carry(dest, carry);
179            if carry.is_zero() {
180                return;
181            }
182        }
183    }
184
185    fn push_significant_digit<D>(digits: &mut Vec<D>, d: D) {
186        digits.insert(0, d);
187    }
188
189    fn split_least_significant<D>(digits: &[D], count: usize) -> (&[D], &[D]) {
190        let (hi, lo) = digits.split_at(digits.len() - count);
191        (lo, hi)
192    }
193
194    fn split_least_significant_mut<D>(digits: &mut [D], count: usize) -> (&mut [D], &mut [D]) {
195        let (hi, lo) = digits.split_at_mut(digits.len() - count);
196        (lo, hi)
197    }
198
199    fn split_most_significant_digit<D: Copy + Zero>(digits: &[D]) -> (D, &[D]) {
200        digits.split_first().map(|(&d, r)| (d, r)).unwrap_or((Zero::zero(), &[]))
201    }
202
203    fn strip_significant_zeros<D: Copy + Zero>(digits: &mut Vec<D>) {
204        if let Some(idx) = digits.iter().position(|d| !d.is_zero()) {
205            digits.copy_within(idx.., 0);
206            digits.truncate(digits.len() - idx);
207        } else {
208            digits.clear();
209        }
210    }
211
212    fn split_significant_zeros<D: Zero>(digits: &[D]) -> (&[D], &[D]) {
213        if let Some(idx) = digits.iter().position(|d| !d.is_zero()) {
214            let (sig_zeros, digits) = digits.split_at(idx);
215            (digits, sig_zeros)
216        } else {
217            (&[], digits)
218        }
219    }
220
221    fn remove_insignificant_digits<D: Zero + Copy>(digits: &mut Vec<D>, n: usize) {
222        // TODO: Does truncate need - 1?
223        digits.truncate(digits.len() - n);
224    }
225
226    fn reorder_le_digits<D: Copy>(digits: &mut [D]) {
227        digits.reverse()
228    }
229
230    fn reorder_be_vec<D: Zero + Copy>(digits: &mut Vec<D>) {
231        match digits.iter().position(|&d| !d.is_zero()) {
232            Some(0) => {}
233            Some(idx) => {
234                digits.copy_within(idx.., 0);
235                digits.truncate(digits.len() - idx);
236            }
237            None => digits.clear(),
238        }
239    }
240
241    fn rotate_trailing_le_digits_at<D: Copy>(digits: &mut [D], idx: usize) {
242        Self::reorder_le_digits(&mut digits[idx..]);
243        digits.rotate_left(idx);
244    }
245
246    fn bigint_to_digits(n: &num_bigint::BigUint) -> Vec<u8> {
247        n.to_radix_be(10)
248    }
249
250    fn biguint_from_digits(n: &[u8]) -> Option<num_bigint::BigUint> {
251        num_bigint::BigUint::from_radix_be(n, 10)
252    }
253
254    fn fill_vec_with_u128<R: RadixType>(vec: &mut Vec<R::Base>, n: u128) {
255        LittleEndian::fill_vec_with_u128::<R>(vec, n);
256        vec.reverse();
257    }
258}
259
260
261impl Endianness for LittleEndian {
262    const NAME: &'static str = "LE";
263
264    #[cfg(rustc_1_75)]
265    fn into_iter<'a, D: 'a>(digits: Vec<D>) -> impl LeBigDigitIterator<'a, D> {
266        digits.into_iter()
267    }
268
269    #[cfg(rustc_1_75)]
270    fn iter_slice<D>(digits: &[D]) -> impl LeBigDigitIterator<'_, &D> {
271        digits.iter()
272    }
273
274    #[cfg(rustc_1_75)]
275    fn iter_slice_mut<D>(digits: &mut [D]) -> impl LeBigDigitIterator<'_, &mut D> {
276        digits.iter_mut()
277    }
278
279    #[cfg(not(rustc_1_75))]
280    fn into_iter<'a, D: 'a>(digits: Vec<D>) -> LittleEndianBigDigitIter<'a, D> {
281        LittleEndianBigDigitIter {
282            digits: Box::new(digits.into_iter()),
283        }
284    }
285
286    #[cfg(not(rustc_1_75))]
287    fn iter_slice<D>(digits: &[D]) -> LittleEndianBigDigitIter<'_, &D> {
288        LittleEndianBigDigitIter {
289            digits: Box::new(digits.iter()),
290        }
291    }
292
293    #[cfg(not(rustc_1_75))]
294    fn iter_slice_mut<D>(digits: &mut [D]) -> LittleEndianBigDigitIter<'_, &mut D> {
295        LittleEndianBigDigitIter {
296            digits: Box::new(digits.into_iter()),
297        }
298    }
299
300    #[cfg(not(rustc_1_75))]
301    fn addassign_carry_into_slice_at<R: RadixType>(
302        digits: &mut [R::Base],
303        carry: &mut R::Base,
304        idx: usize,
305    ) {
306        for dest in digits.iter_mut().skip(idx) {
307            R::addassign_carry(dest, carry);
308            if carry.is_zero() {
309                return;
310            }
311        }
312    }
313
314    fn push_significant_digit<D>(digits: &mut Vec<D>, d: D) {
315        digits.push(d);
316    }
317
318    fn split_least_significant<D>(digits: &[D], count: usize) -> (&[D], &[D]) {
319        digits.split_at(count)
320    }
321
322    fn split_least_significant_mut<D>(digits: &mut [D], count: usize) -> (&mut [D], &mut [D]) {
323        digits.split_at_mut(count)
324    }
325
326    fn split_most_significant_digit<D: Copy + Zero>(digits: &[D]) -> (D, &[D]) {
327        digits.split_last().map(|(&d, r)| (d, r)).unwrap_or((Zero::zero(), &[]))
328    }
329
330    fn strip_significant_zeros<D: Zero>(digits: &mut Vec<D>) {
331        if let Some(idx) = digits.iter().rposition(|d| !d.is_zero()) {
332            digits.truncate(idx + 1);
333        } else {
334            digits.clear();
335        }
336    }
337
338    fn split_significant_zeros<D: Zero>(digits: &[D]) -> (&[D], &[D]) {
339        if let Some(idx) = digits.iter().rposition(|d| !d.is_zero()) {
340            let (digits, sig_zeros) = digits.split_at(idx);
341            (digits, sig_zeros)
342        } else {
343            (&[], digits)
344        }
345    }
346
347    fn remove_insignificant_digits<D: Zero + Copy>(digits: &mut Vec<D>, n: usize) {
348        let last_nonzero_idx = digits.iter().rposition(|&d| !d.is_zero());
349
350        match (last_nonzero_idx, n > digits.len()) {
351            (Some(idx), false) => {
352                digits.copy_within(n..=idx, 0);
353                digits.truncate(idx - n + 1);
354            }
355            _ => {
356                digits.clear();
357            }
358        }
359    }
360
361    fn reorder_be_vec<D: Zero + Copy>(digits: &mut Vec<D>) {
362        match digits.iter().position(|&d| !d.is_zero()) {
363            None => digits.clear(),
364            Some(idx) => {
365                digits.copy_within(idx.., 0);
366                digits.truncate(digits.len() - idx);
367                digits.reverse();
368            }
369        }
370    }
371
372    #[allow(unused_variables)]
373    fn reorder_le_digits<D: Copy>(digits: &mut [D]) {
374        //no-op
375    }
376
377    #[allow(unused_variables)]
378    fn rotate_trailing_le_digits_at<D: Copy>(digits: &mut [D], idx: usize) {
379        //no-op
380    }
381
382    fn bigint_to_digits(n: &num_bigint::BigUint) -> Vec<u8> {
383        n.to_radix_le(10)
384    }
385
386    fn biguint_from_digits(n: &[u8]) -> Option<num_bigint::BigUint> {
387        num_bigint::BigUint::from_radix_le(n, 10)
388    }
389
390    fn fill_vec_with_u128<R: RadixType>(vec: &mut Vec<R::Base>, mut n: u128) {
391        let base = R::RADIX.to_u128().unwrap();
392        vec.clear();
393
394        while !n.is_zero() {
395            let (hi, lo) = num_integer::div_rem(n, base);
396            let lo = R::Base::from_u128(lo).unwrap();
397            vec.push(lo);
398            n = hi;
399        }
400    }
401}
402
403/// Abstraction over fixed-size little-endian bigdigit iterators
404///
405/// Can be applied to slice, vecs, and num_bigint::{U32Digits, U64Digits}
406/// allowing "easy" access to the digits.
407pub(crate) trait LeBigDigitIterator<'a, D>
408                    : Iterator<Item = D>
409                    + ExactSizeIterator
410                    + DoubleEndedIterator
411{
412}
413
414/// Thin wrapper around boxed big-digit-iterator trait object
415///
416/// Used to implement generic endian iterators for versions of Rust before
417/// Return Position Impl Trait In Trait (RPITIT) were implemented.
418///
419#[cfg(not(rustc_1_75))]
420pub(crate) struct LittleEndianBigDigitIter<'a, D> {
421    digits: Box<dyn LeBigDigitIterator<'a, D> + 'a>,
422}
423
424#[cfg(not(rustc_1_75))]
425impl<D> Iterator for LittleEndianBigDigitIter<'_, D> {
426    type Item = D;
427
428    fn next(&mut self) -> Option<Self::Item> {
429        self.digits.next()
430    }
431
432    fn size_hint(&self) -> (usize, Option<usize>) {
433        self.digits.size_hint()
434    }
435}
436
437#[cfg(not(rustc_1_75))]
438impl<D> DoubleEndedIterator for LittleEndianBigDigitIter<'_, D> {
439    fn next_back(&mut self) -> Option<Self::Item> {
440        self.digits.next_back()
441    }
442}
443
444#[cfg(not(rustc_1_75))]
445impl<D> ExactSizeIterator for LittleEndianBigDigitIter<'_, D> {
446    fn len(&self) -> usize {
447        self.digits.len()
448    }
449}
450
451
452impl<'a> LeBigDigitIterator<'a, u64> for num_bigint::U64Digits<'a> {}
453impl<'a> LeBigDigitIterator<'a, u32> for num_bigint::U32Digits<'a> {}
454
455impl<'a, D> LeBigDigitIterator<'a, &'a D> for stdlib::slice::Iter<'a, D> {}
456impl<'a, D> LeBigDigitIterator<'a, &'a D> for stdlib::iter::Rev<stdlib::slice::Iter<'a, D>> {}
457impl<'a, D> LeBigDigitIterator<'a, &'a mut D> for stdlib::slice::IterMut<'a, D> {}
458impl<'a, D> LeBigDigitIterator<'a, &'a mut D> for stdlib::iter::Rev<stdlib::slice::IterMut<'a, D>> {}
459
460impl<D> LeBigDigitIterator<'_, D> for stdlib::vec::IntoIter<D> {}
461impl<D> LeBigDigitIterator<'_, D> for stdlib::iter::Rev<stdlib::vec::IntoIter<D>> {}
bigdecimal/bigdigit/endian.rs

bigdecimal/bigdigit/
endian.rs
