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

relp_num/integer/big/
io.rs
