bigdecimal/bigdigit/
endian.rs

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

bigdecimal/bigdigit/
endian.rs
