ibig/
ubig.rs

1//! Unsigned big integer.
2
3use self::Repr::*;
4use crate::{
5    arch::{ntt, word::Word},
6    buffer::Buffer,
7    math,
8    primitive::WORD_BITS_USIZE,
9};
10use core::slice;
11
12/// Internal representation of UBig.
13#[derive(Debug, Eq, Hash, PartialEq)]
14pub(crate) enum Repr {
15    /// A number that fits in a single Word.
16    Small(Word),
17    /// A number that does not fit in a single Word.
18    ///
19    /// The buffer has:
20    /// * length at least 2
21    /// * no leading zero
22    /// * compact capacity
23    Large(Buffer),
24}
25
26/// Unsigned big integer.
27///
28/// Arbitrarily large unsigned integer.
29///
30/// # Examples
31///
32/// ```
33/// # use ibig::{error::ParseError, ubig, UBig};
34/// let a = ubig!(a2a123bbb127779cccc123123ccc base 32);
35/// let b = ubig!(0x1231abcd4134);
36/// let c = UBig::from_str_radix("a2a123bbb127779cccc123123ccc", 32)?;
37/// let d = UBig::from_str_radix("1231abcd4134", 16)?;
38/// assert_eq!(a, c);
39/// assert_eq!(b, d);
40/// # Ok::<(), ParseError>(())
41/// ```
42#[derive(Eq, Hash, PartialEq)]
43pub struct UBig(Repr);
44
45impl UBig {
46    /// Construct from one word.
47    #[inline]
48    pub(crate) fn from_word(word: Word) -> UBig {
49        UBig(Small(word))
50    }
51
52    /// Get the representation of UBig.
53    #[inline]
54    pub(crate) fn repr(&self) -> &Repr {
55        &self.0
56    }
57
58    /// Convert into representation.
59    #[inline]
60    pub(crate) fn into_repr(self) -> Repr {
61        self.0
62    }
63
64    /// Length in Words.
65    #[inline]
66    pub(crate) fn len(&self) -> usize {
67        match self.repr() {
68            Small(_) => 1,
69            Large(buffer) => buffer.len(),
70        }
71    }
72
73    /// Representation in Words.
74    #[inline]
75    pub(crate) fn as_words(&self) -> &[Word] {
76        match self.repr() {
77            Small(0) => &[],
78            Small(word) => slice::from_ref(word),
79            Large(buffer) => buffer,
80        }
81    }
82
83    /// Maximum length in `Word`s.
84    ///
85    /// Ensures that the number of bits fits in `usize`, which is useful for bit count
86    /// operations, and for radix conversions (even base 2 can be represented).
87    ///
88    /// This also guarantees that up to 16 * length will not overflow.
89    ///
90    /// We also make sure that any multiplication whose result fits in `MAX_LEN` can fit
91    /// within the largest possible number-theoretic transform.
92    ///
93    /// Also make sure this is even, useful for checking whether a square will overflow.
94    pub(crate) const MAX_LEN: usize = math::min_usize(
95        usize::MAX / WORD_BITS_USIZE,
96        match 1usize.checked_shl(ntt::MAX_ORDER) {
97            Some(ntt_len) => ntt_len,
98            None => usize::MAX,
99        },
100    ) & !1usize;
101
102    /// Maximum length in bits.
103    ///
104    /// [UBig]s up to this length are supported. Creating a longer number
105    /// will panic.
106    ///
107    /// This does not guarantee that there is sufficient memory to store numbers
108    /// up to this length. Memory allocation may fail even for smaller numbers.
109    ///
110    /// The fact that this limit fits in `usize` guarantees that all bit
111    /// addressing operations can be performed using `usize`.
112    ///
113    /// It is typically close to `usize::MAX`, but the exact value is platform-dependent.
114    pub const MAX_BIT_LEN: usize = UBig::MAX_LEN * WORD_BITS_USIZE;
115
116    pub(crate) fn panic_number_too_large() -> ! {
117        panic!("number too large, maximum is {} bits", UBig::MAX_BIT_LEN)
118    }
119}
120
121impl Clone for UBig {
122    #[inline]
123    fn clone(&self) -> UBig {
124        match self.repr() {
125            Small(x) => UBig(Small(*x)),
126            Large(buffer) => UBig(Large(buffer.clone())),
127        }
128    }
129
130    #[inline]
131    fn clone_from(&mut self, source: &UBig) {
132        if let Large(buffer) = &mut self.0 {
133            if let Large(source_buffer) = source.repr() {
134                buffer.resizing_clone_from(source_buffer);
135                return;
136            }
137        }
138        *self = source.clone();
139    }
140}
141
142impl From<Buffer> for UBig {
143    /// If the Buffer was allocated with `Buffer::allocate(n)`
144    /// and the normalized length is between `n - 2` and `n + 2`
145    /// (or even approximately between `0.9 * n` and `1.125 * n`),
146    /// there will be no reallocation here.
147    fn from(mut buffer: Buffer) -> UBig {
148        buffer.pop_leading_zeros();
149
150        match buffer.len() {
151            0 => UBig::from_word(0),
152            1 => UBig::from_word(buffer[0]),
153            _ if buffer.len() > UBig::MAX_LEN => UBig::panic_number_too_large(),
154            _ => {
155                buffer.shrink();
156                UBig(Large(buffer))
157            }
158        }
159    }
160}
161
162#[cfg(test)]
163mod tests {
164    use super::*;
165
166    /// Current capacity in Words.
167    fn capacity(x: &UBig) -> usize {
168        match x.repr() {
169            Small(_) => 1,
170            Large(large) => large.capacity(),
171        }
172    }
173
174    #[test]
175    fn test_buffer_to_ubig() {
176        let buf = Buffer::allocate(5);
177        let num: UBig = buf.into();
178        assert_eq!(num, UBig::from_word(0));
179
180        let mut buf = Buffer::allocate(5);
181        buf.push(7);
182        let num: UBig = buf.into();
183        assert_eq!(num, UBig::from_word(7));
184
185        let mut buf = Buffer::allocate(100);
186        buf.push(7);
187        buf.push(0);
188        buf.push(0);
189        let num: UBig = buf.into();
190        assert_eq!(num, UBig::from_word(7));
191
192        let mut buf = Buffer::allocate(5);
193        buf.push(1);
194        buf.push(2);
195        buf.push(3);
196        buf.push(4);
197        let num: UBig = buf.into();
198        assert_eq!(capacity(&num), 7);
199
200        let mut buf = Buffer::allocate(100);
201        buf.push(1);
202        buf.push(2);
203        buf.push(3);
204        buf.push(4);
205        let num: UBig = buf.into();
206        assert_eq!(capacity(&num), 6);
207    }
208
209    #[test]
210    fn test_clone() {
211        let a = UBig::from_word(5);
212        assert_eq!(a.clone(), a);
213
214        let a = gen_ubig(10);
215        let b = a.clone();
216        assert_eq!(a, b);
217        assert_eq!(capacity(&a), capacity(&b));
218    }
219
220    #[test]
221    fn test_clone_from() {
222        let num: UBig = gen_ubig(10);
223
224        let mut a = UBig::from_word(3);
225        a.clone_from(&num);
226        assert_eq!(a, num);
227        let b = UBig::from_word(7);
228        a.clone_from(&b);
229        assert_eq!(a, b);
230        a.clone_from(&b);
231        assert_eq!(a, b);
232
233        let mut a = gen_ubig(9);
234        let prev_cap = capacity(&a);
235        a.clone_from(&num);
236        // The buffer should be reused, 9 is close enough to 10.
237        assert_eq!(capacity(&a), prev_cap);
238        assert_ne!(capacity(&a), capacity(&num));
239
240        let mut a = gen_ubig(2);
241        let prev_cap = capacity(&a);
242        a.clone_from(&num);
243        // The buffer should now be reallocated, it's too small.
244        assert_ne!(capacity(&a), prev_cap);
245        assert_eq!(capacity(&a), capacity(&num));
246
247        let mut a = gen_ubig(100);
248        let prev_cap = capacity(&a);
249        a.clone_from(&num);
250        // The buffer should now be reallocated, it's too large.
251        assert_ne!(capacity(&a), prev_cap);
252        assert_eq!(capacity(&a), capacity(&num));
253    }
254
255    fn gen_ubig(num_words: u16) -> UBig {
256        let mut buf = Buffer::allocate(num_words.into());
257        for i in 0..num_words {
258            buf.push(i.into());
259        }
260        buf.into()
261    }
262}
ibig/ubig.rs

ibig/
ubig.rs
