relp_num/integer/big/
io.rs

1#![allow(unused_unsafe)]
2
3use core::mem;
4use std::cmp::Ordering;
5use std::convert::TryFrom;
6use std::convert::TryInto;
7use std::fmt;
8use std::num::NonZeroUsize;
9use std::str::FromStr;
10
11use num_traits::{FromPrimitive, One, ToPrimitive, Zero};
12use smallvec::SmallVec;
13use smallvec::smallvec;
14
15use crate::integer::big::{BITS_PER_WORD, NonZeroUbig, Ubig};
16use crate::integer::big::ops::building_blocks::is_well_formed;
17use crate::integer::big::ops::non_zero::{add_assign_single_non_zero, mul_assign_single_non_zero, shr, shr_mut};
18use crate::rational::{f32_kind, f64_kind};
19use crate::rational::big::io::FloatKind;
20
21impl<const S: usize> Ubig<S> {
22    /// Creates a new unsigned integer with the small specified value.
23    #[must_use]
24    #[inline]
25    pub fn new(value: usize) -> Self {
26        Ubig(if value > 0 { smallvec![value] } else { smallvec![] })
27    }
28    #[must_use]
29    #[inline]
30    pub(crate) unsafe fn from_inner_unchecked(values: SmallVec<[usize; S]>) -> Self {
31        debug_assert!(is_well_formed(&values));
32
33        Self(values)
34    }
35}
36
37impl<const S: usize> NonZeroUbig<S> {
38    /// Creates a new unsigned integer with the small specified value.
39    ///
40    /// If the specified value is non zero, this succeeds, otherwise, returns `None`.
41    #[must_use]
42    pub fn new(n: usize) -> Option<Self> {
43        if n != 0 {
44            Some(unsafe { Self(smallvec![n]) })
45        } else {
46            None
47        }
48    }
49    #[must_use]
50    #[inline]
51    pub(crate) unsafe fn new_unchecked(value: usize) -> Self {
52        NonZeroUbig(smallvec![value])
53    }
54    #[must_use]
55    #[inline]
56    pub(crate) unsafe fn from_inner_unchecked(values: SmallVec<[usize; S]>) -> Self {
57        debug_assert!(is_well_formed(&values));
58
59        Self(values)
60    }
61}
62
63impl<const S: usize> Default for Ubig<S> {
64    fn default() -> Self {
65        Self::zero()
66    }
67}
68
69impl<const S: usize> From<NonZeroUsize> for Ubig<S> {
70    fn from(value: NonZeroUsize) -> Self {
71        Self(smallvec![value.get()])
72    }
73}
74
75impl<const S: usize> From<NonZeroUsize> for NonZeroUbig<S> {
76    fn from(value: NonZeroUsize) -> Self {
77        Self(smallvec![value.get()])
78    }
79}
80
81impl<const S: usize, const I: usize> TryFrom<[usize; I]> for Ubig<S> {
82    // TODO
83    type Error = ();
84
85    fn try_from(value: [usize; I]) -> Result<Self, Self::Error> {
86        if is_well_formed(&value) {
87            Ok(Self(SmallVec::from_slice(&value)))
88        } else {
89            Err(())
90        }
91    }
92}
93
94impl<const S: usize, const I: usize> TryFrom<[usize; I]> for NonZeroUbig<S> {
95    // TODO
96    type Error = ();
97
98    fn try_from(value: [usize; I]) -> Result<Self, Self::Error> {
99        if is_well_formed(&value) && !value.is_empty() {
100            Ok(Self(SmallVec::from_slice(&value)))
101        } else {
102            Err(())
103        }
104    }
105}
106
107impl<const S: usize> Zero for Ubig<S> {
108    #[must_use]
109    #[inline]
110    fn zero() -> Self {
111        Self(smallvec![])
112    }
113
114    #[inline]
115    fn set_zero(&mut self) {
116        self.0.clear();
117    }
118
119    #[must_use]
120    #[inline]
121    fn is_zero(&self) -> bool {
122        self.0.is_empty()
123    }
124}
125
126impl<const S: usize> One for Ubig<S> {
127    #[must_use]
128    #[inline]
129    fn one() -> Self {
130        Self(smallvec![1])
131    }
132
133    #[inline]
134    fn set_one(&mut self) {
135        self.0.clear();
136        self.0.push(1);
137    }
138
139    #[must_use]
140    #[inline]
141    fn is_one(&self) -> bool {
142        self.0.len() == 1 && self.0[0] == 1
143    }
144}
145
146impl<const S: usize> One for NonZeroUbig<S> {
147    #[must_use]
148    #[inline]
149    fn one() -> Self {
150        Self(smallvec![1])
151    }
152
153    #[inline]
154    fn set_one(&mut self) {
155        self.0.truncate(1);
156        *unsafe { self.0.get_unchecked_mut(0) } = 1;
157    }
158
159    #[must_use]
160    #[inline]
161    fn is_one(&self) -> bool {
162        *unsafe { self.0.get_unchecked(0) } == 1 && self.0.len() == 1
163    }
164}
165
166
167impl<const S: usize> From<usize> for Ubig<S> {
168    fn from(value: usize) -> Self {
169        Self(if value > 0 { smallvec![value] } else { smallvec![] })
170    }
171}
172
173impl<const S: usize> FromStr for Ubig<S> {
174    // TODO(ARCHITECTURE): Better error handling
175    type Err = &'static str;
176
177    fn from_str(s: &str) -> Result<Self, Self::Err> {
178        from_str_radix::<10, S>(s).map(Self)
179    }
180}
181
182impl<const S: usize> FromStr for NonZeroUbig<S> {
183    // TODO(ARCHITECTURE): Better error handling
184    type Err = &'static str;
185
186    fn from_str(s: &str) -> Result<Self, Self::Err> {
187        from_str_radix::<10, S>(s)
188            .map(|inner| {
189                if !inner.is_empty() {
190                    Ok(unsafe { Self(inner) })
191                } else {
192                    Err("Zero value")
193                }
194            })
195            .flatten()
196    }
197}
198
199impl<const S: usize> fmt::Display for Ubig<S> {
200    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
201        f.write_str(&to_str_radix::<10>(self))
202    }
203}
204
205impl<const S: usize> fmt::Display for NonZeroUbig<S> {
206    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
207        // TODO(PERFORMANCE): Skip zero case
208        f.write_str(&to_str_radix::<10>(self))
209    }
210}
211
212#[inline]
213pub fn from_str_radix<const RADIX: u32, const S: usize>(s: &str) -> Result<SmallVec<[usize; S]>, &'static str> {
214    debug_assert!(RADIX <= 36);
215
216    match s.len() {
217        0 => Err("Empty string"),
218        _ => {
219            let mut char_iterator = s
220                .trim()
221                .chars()
222                .skip_while(|&c| c == '0');
223            match char_iterator.next() {
224                None => Ok(smallvec![]),
225                Some(value) => {
226                    match value.to_digit(RADIX) {
227                        None => Err("Character is not a digit"),
228                        Some(value) => {
229                            let mut non_zero_total = unsafe { smallvec![value as usize] };
230
231                            for character in char_iterator {
232                                match character.to_digit(RADIX) {
233                                    None => return Err("Character is not a digit"),
234                                    Some(value) => {
235                                        mul_assign_single_non_zero(&mut non_zero_total, RADIX as usize);
236                                        add_assign_single_non_zero(&mut non_zero_total, value as usize);
237                                    }
238                                }
239                            }
240
241                            Ok(non_zero_total)
242                        }
243                    }
244                }
245            }
246        }
247    }
248}
249
250fn to_str_radix<const RADIX: u32>(value: &[usize]) -> String {
251    assert!(RADIX > 1 && RADIX <= 36);
252
253    match value.len() {
254        0 => "0".to_string(),
255        _ => {
256            let mut digits = vec![0];
257
258            // Set highest word to the lowest index, and reverse the bits
259            let mut leading_zero_words = 0;
260            while value[leading_zero_words] == 0 {
261                // At least the last value is not allowed to be zero, so we don't have to check bounds
262                leading_zero_words += 1;
263            }
264            let leading_zero_bits = value.last().unwrap().leading_zeros();
265
266            // Set highest word to the lowest index, and reverse the bits
267            let mut value = value.iter()
268                .skip(leading_zero_words)
269                .map(|word| word.reverse_bits())
270                .rev()
271                .collect::<SmallVec<[usize; 8]>>();
272            let len_before_shift = value.len() as u32;
273            shr_mut(&mut value, 0, leading_zero_bits);
274
275            let bit_count = len_before_shift * BITS_PER_WORD - leading_zero_bits;
276            debug_assert_eq!(value[0] % 2, 1);
277            for bit_index in 0..bit_count {
278                update_digits::<RADIX>(&mut digits, value[0] % 2 == 1);
279                shr_mut(&mut value, 0, 1);
280
281                if value.is_empty() {
282                    // Had this many bits remaining
283                    for _ in (bit_index + 1)..(leading_zero_words as u32 * BITS_PER_WORD + bit_count) {
284                        update_digits::<RADIX>(&mut digits, false);
285                    }
286                    break;
287                }
288            }
289
290            digits.into_iter()
291                .rev()
292                .map(|digit| {
293                    if digit < 10 {
294                        digit.to_string()
295                    } else {
296                        ASCII_LOWER[(digit - 10) as usize].to_string()
297                    }
298                })
299                .collect()
300        }
301    }
302}
303
304static ASCII_LOWER: [char; 26] = [
305    'a', 'b', 'c', 'd', 'e',
306    'f', 'g', 'h', 'i', 'j',
307    'k', 'l', 'm', 'n', 'o',
308    'p', 'q', 'r', 's', 't',
309    'u', 'v', 'w', 'x', 'y',
310    'z',
311];
312
313fn update_digits<const RADIX: u32>(digits: &mut Vec<u32>, mut carry: bool) {
314    for digit in digits.iter_mut() {
315        *digit *= 2; // binary, each bit multiplies by 2
316        if carry {
317            *digit += 1;
318            carry = false;
319        }
320        if *digit >= RADIX {
321            *digit %= RADIX;
322            carry = true;
323        }
324    }
325    if carry {
326        digits.push(1);
327    }
328}
329
330impl<const S: usize> FromPrimitive for Ubig<S> {
331    fn from_isize(n: isize) -> Option<Self> {
332        if n >= 0 {
333            Some(Self::new(n.unsigned_abs()))
334        } else {
335            None
336        }
337    }
338
339    fn from_i8(n: i8) -> Option<Self> {
340        if n >= 0 {
341            Some(Self::new(n.unsigned_abs() as usize))
342        } else {
343            None
344        }
345    }
346
347    fn from_i16(n: i16) -> Option<Self> {
348        if n >= 0 {
349            Some(Self::new(n.unsigned_abs() as usize))
350        } else {
351            None
352        }
353    }
354
355    fn from_i32(n: i32) -> Option<Self> {
356        if n >= 0 {
357            Some(Self::new(n.unsigned_abs() as usize))
358        } else {
359            None
360        }
361    }
362
363    fn from_i64(n: i64) -> Option<Self> {
364        if n >= 0 {
365            Some(Self::new(n.unsigned_abs() as usize))
366        } else {
367            None
368        }
369    }
370
371    fn from_i128(n: i128) -> Option<Self> {
372        if n >= 0 {
373            Self::from_u128(n.unsigned_abs())
374        } else {
375            None
376        }
377    }
378
379    fn from_usize(n: usize) -> Option<Self> {
380        Some(Self::new(n))
381    }
382
383    fn from_u8(n: u8) -> Option<Self> {
384        Some(Self::new(n as usize))
385    }
386
387    fn from_u16(n: u16) -> Option<Self> {
388        Some(Self::new(n as usize))
389    }
390
391    fn from_u32(n: u32) -> Option<Self> {
392        Some(Self::new(n as usize))
393    }
394
395    fn from_u64(n: u64) -> Option<Self> {
396        Some(Self::new(n as usize))
397    }
398
399    fn from_u128(n: u128) -> Option<Self> {
400        let bits = mem::size_of::<u32>() * 8;
401        let groups = 128 / bits;
402
403        let mut data = (0..groups)
404            .map(|i| (n >> (i * bits)) as usize)
405            .collect::<SmallVec<_>>();
406        while let Some(0) = data.last() {
407            data.pop();
408        }
409
410        debug_assert!(is_well_formed(&data));
411
412        Some(unsafe {
413            // SAFETY: data does not end in a zero value.
414            Self::from_inner_unchecked(data)
415        })
416    }
417
418    fn from_f32(n: f32) -> Option<Self> {
419        Self::from_float_kind(f32_kind(n))
420    }
421
422    fn from_f64(n: f64) -> Option<Self> {
423        Self::from_float_kind(f64_kind(n))
424    }
425}
426
427impl<const S: usize> Ubig<S> {
428    fn from_float_kind(kind: FloatKind) -> Option<Self> {
429        match kind  {
430            FloatKind::Subnormal(as_ratio) | FloatKind::Normal(as_ratio) => {
431                if as_ratio.sign == 0 {
432                    let result = match as_ratio.exponent.cmp(&0) {
433                        Ordering::Less => {
434                            let result = as_ratio.fraction.get() >> as_ratio.exponent.unsigned_abs();
435                            Self::from(result as usize)
436                        }
437                        Ordering::Equal => Self::from(as_ratio.fraction.get() as usize),
438                        Ordering::Greater => {
439                            let exponent = as_ratio.exponent.unsigned_abs();
440                            let (words, bits) = (exponent / BITS_PER_WORD, exponent % BITS_PER_WORD);
441                            let values = [as_ratio.fraction.get() as usize];
442                            let result = shr(&values, words as usize, bits);
443
444                            unsafe {
445                                Self::from_inner_unchecked(result)
446                            }
447                        }
448                    };
449
450                    Some(result)
451                } else {
452                    None
453                }
454            },
455            FloatKind::Zero => Some(Self::zero()),
456            _ => None,
457        }
458    }
459}
460
461
462macro_rules! small {
463    ($value:expr) => {
464        {
465            match $value.len() {
466                0 => Some(0),
467                1 => $value[0].try_into().ok(),
468                _ => None,
469            }
470        }
471    }
472}
473
474macro_rules! to_primitive_impl {
475    ($name:ty) => {
476        impl<const S: usize> ToPrimitive for $name {
477            fn to_isize(&self) -> Option<isize> {
478                small!(self)
479            }
480
481            fn to_i8(&self) -> Option<i8> {
482                small!(self)
483            }
484
485            fn to_i16(&self) -> Option<i16> {
486                small!(self)
487            }
488
489            fn to_i32(&self) -> Option<i32> {
490                small!(self)
491            }
492
493            fn to_i64(&self) -> Option<i64> {
494                small!(self)
495            }
496
497            fn to_i128(&self) -> Option<i128> {
498                todo!()
499            }
500
501            fn to_usize(&self) -> Option<usize> {
502                small!(self)
503            }
504
505            fn to_u8(&self) -> Option<u8> {
506                small!(self)
507            }
508
509            fn to_u16(&self) -> Option<u16> {
510                small!(self)
511            }
512
513            fn to_u32(&self) -> Option<u32> {
514                small!(self)
515            }
516
517            fn to_u64(&self) -> Option<u64> {
518                small!(self)
519            }
520
521            fn to_u128(&self) -> Option<u128> {
522                todo!()
523            }
524
525            fn to_f32(&self) -> Option<f32> {
526                Some(make_float_32::<S>(self))
527            }
528
529            fn to_f64(&self) -> Option<f64> {
530                Some(make_float_64::<S>(self))
531            }
532        }
533    }
534}
535
536to_primitive_impl!(Ubig<S>);
537to_primitive_impl!(NonZeroUbig<S>);
538
539macro_rules! define_float_maker {
540    ($name:ident, $target:ty, $bit_array:ty, $bits_in_exponent:expr, $bits_in_fraction:expr) => {
541        fn $name<const S: usize>(values: &[usize]) -> $target {
542            let sign = 0;
543
544            match values.last() {
545                None => <$target>::zero(),
546                Some(last_value) => {
547                    debug_assert_ne!(*last_value, 0);
548                    let bits_in_highest = BITS_PER_WORD - last_value.leading_zeros();
549                    debug_assert!(bits_in_highest > 0);
550                    let bits = (values.len() - 1) as u32 * BITS_PER_WORD + bits_in_highest;
551                    debug_assert!(bits > 0);
552
553                    let exponent = (bits as $bit_array + ((2 as $bit_array).pow($bits_in_exponent - 1) - 1 - 1)) << $bits_in_fraction;
554
555                    let mut copy = SmallVec::<[usize; S]>::from_slice(values);
556                    *copy.last_mut().unwrap() -= 1 << (bits_in_highest - 1);
557
558                    let remaining_bits = bits - 1;
559                    let fraction = match remaining_bits.cmp(&$bits_in_fraction) {
560                        Ordering::Less => copy[0] << ($bits_in_fraction - remaining_bits),
561                        Ordering::Equal => copy[0],
562                        Ordering::Greater => {
563                            let to_shift = remaining_bits - $bits_in_fraction;
564                            let (highest_bit_lost_set, any_other_set) = {
565                                let index = to_shift - 1;
566
567                                let (words, bits) = ((index / BITS_PER_WORD) as usize, index % BITS_PER_WORD);
568                                let highest_bit_lost = copy[words] & (1 << bits) > 0;
569
570                                let any_other = copy[..words].iter().any(|&w| w != 0)
571                                    || {
572                                        if bits == 0 {
573                                            false
574                                        } else {
575                                            let mask = !0 >> (BITS_PER_WORD - bits);
576                                            mask & copy[words] > 0
577                                        }
578                                    };
579
580                                (highest_bit_lost, any_other)
581                            };
582
583                            let (mut words, bits) = (to_shift / BITS_PER_WORD, to_shift % BITS_PER_WORD);
584
585                            let unrounded = 'scope: {
586                                // Satisfy the assumptions of `shr_mut`
587                                while let Some(0) = copy.last() {
588                                    if copy.len() == 1 {
589                                        // This is the last value. We must be dealing with a power of 2.
590                                        break 'scope 0;
591                                    }
592                                    copy.pop();
593                                    words -= 1;
594                                }
595                                shr_mut(&mut copy, words as usize, bits);
596
597                                match copy.last() {
598                                    Some(&value) => value,
599                                    None => 0,
600                                }
601                            };
602
603                            if highest_bit_lost_set {
604                                if any_other_set {
605                                    unrounded + 1
606                                } else {
607                                    // Tie to even
608                                    if unrounded % 2 == 1 {
609                                        unrounded + 1
610                                    } else {
611                                        unrounded
612                                    }
613                                }
614                            } else {
615                                unrounded
616                            }
617                        },
618                    };
619
620                    <$target>::from_bits(sign | exponent | fraction as $bit_array)
621                }
622            }
623        }
624    }
625}
626
627define_float_maker!(make_float_32, f32, u32, 8, 23);
628define_float_maker!(make_float_64, f64, u64, 11, 52);
629
630#[cfg(test)]
631mod test {
632    use num_traits::FromPrimitive;
633    use num_traits::ToPrimitive;
634
635    use crate::Ubig;
636
637    #[test]
638    fn test_from_primitive() {
639        assert_eq!(Ubig::<1>::from_i16(-4), None);
640        assert_eq!(Ubig::<1>::from_u16(4), Some(Ubig::from(4)));
641        assert_eq!(Ubig::<1>::from_i128(0), Some(Ubig::from(0)));
642        assert_eq!(Ubig::<1>::from_i128(1), Some(Ubig::from(1)));
643        assert_eq!(Ubig::<1>::from_i128(-1), None);
644
645        assert_eq!(Ubig::<1>::from_f32(1.5_f32), Some(Ubig::from(1)));
646        assert_eq!(Ubig::<1>::from_f32(1_f32), Some(Ubig::from(1)));
647        assert_eq!(Ubig::<1>::from_f32(0.5_f32), Some(Ubig::from(0)));
648        assert_eq!(Ubig::<1>::from_f32(0.75_f32), Some(Ubig::from(0)));
649        assert_eq!(Ubig::<1>::from_f32(0_f32), Some(Ubig::from(0)));
650
651        assert_eq!(Ubig::<1>::from_f32(-1.5_f32), None);
652        assert_eq!(Ubig::<1>::from_f32(-0_f32), Some(Ubig::from(0)));
653    }
654
655    #[test]
656    fn test_to_primitive() {
657        assert_eq!(Ubig::<1>::from(4).to_i16(), Some(4));
658
659        assert_eq!(Ubig::<1>::from(0).to_f32(), Some(0_f32));
660        assert_eq!(Ubig::<1>::from(1).to_f32(), Some(1_f32));
661        assert_eq!(Ubig::<1>::from(2).to_f32(), Some(2_f32));
662        assert_eq!(Ubig::<1>::from(3).to_f32(), Some(3_f32));
663        assert_eq!(Ubig::<1>::from(4).to_f32(), Some(4_f32));
664        assert_eq!(Ubig::<1>::from(5).to_f32(), Some(5_f32));
665        assert_eq!(Ubig::<1>::from(6).to_f32(), Some(6_f32));
666        assert_eq!(Ubig::<1>::from(7).to_f32(), Some(7_f32));
667
668        assert_eq!(Ubig::<1>::from(0).to_f64(), Some(0_f64));
669        assert_eq!(Ubig::<1>::from(1).to_f64(), Some(1_f64));
670        assert_eq!(Ubig::<1>::from(2).to_f64(), Some(2_f64));
671        assert_eq!(Ubig::<1>::from(3).to_f64(), Some(3_f64));
672        assert_eq!(Ubig::<1>::from(4).to_f64(), Some(4_f64));
673        assert_eq!(Ubig::<1>::from(5).to_f64(), Some(5_f64));
674        assert_eq!(Ubig::<1>::from(6).to_f64(), Some(6_f64));
675        assert_eq!(Ubig::<1>::from(7).to_f64(), Some(7_f64));
676        assert_eq!(Ubig::<1>::from(123456789).to_f64(), Some(123456789_f64));
677    }
678
679    #[test]
680    fn test_to_primitive_rounding() {
681        assert_eq!(Ubig::<1>::from(16777216).to_f32(), Some(16777216_f32));
682        assert_eq!(Ubig::<1>::from(16777217).to_f32(), Some(16777217_f32));
683        assert_eq!(Ubig::<1>::from(16777218).to_f32(), Some(16777218_f32));
684        assert_eq!(Ubig::<1>::from(16777219).to_f32(), Some(16777219_f32));
685
686        assert_eq!(Ubig::<1>::from(123_456_789).to_f32(), Some(123456790_f32));
687
688        for i in 0..100 {
689            let x = 2_usize.pow(25) + i;
690            assert_eq!(Ubig::<1>::from(x).to_f32(), Some(x as f32));
691        }
692
693        assert_eq!(Ubig::<1>::from(9_007_199_254_740_992).to_f32(), Some(9007199000000000_f32));
694        assert_eq!(Ubig::<1>::from(9_007_199_254_740_993).to_f32(), Some(9007199000000000_f32));
695        assert_eq!(Ubig::<1>::from(9_007_199_254_740_994).to_f32(), Some(9007199000000000_f32));
696
697        assert_eq!(Ubig::<1>::from(9_007_199_254_740_992).to_f64(), Some(9_007_199_254_740_992_f64));
698        assert_eq!(Ubig::<1>::from(9_007_199_254_740_993).to_f64(), Some(9_007_199_254_740_992_f64));
699        assert_eq!(Ubig::<1>::from(9_007_199_254_740_994).to_f64(), Some(9_007_199_254_740_994_f64));
700
701        for i in 0..100 {
702            let x = 2_usize.pow(54) + i;
703            assert_eq!(Ubig::<1>::from(x).to_f64(), Some(x as f64));
704        }
705    }
706}
relp_num/integer/big/io.rs

relp_num/integer/big/
io.rs
