dashu_int/
ubig.rs

1//! Definitions of [UBig].
2//!
3//! Conversion from internal representations including [Buffer][crate::buffer::Buffer], [TypedRepr], [TypedReprRef]
4//! to [UBig] is not implemented, the designed way to construct UBig from them is first convert them
5//! into [Repr], and then directly construct from the [Repr]. This restriction is set to make
6//! the source type explicit.
7
8use crate::repr::{Repr, TypedRepr, TypedReprRef};
9
10/// An unsigned arbitrary precision integer.
11///
12/// `UBig` represents an arbitrarily large non-negative integer. Values that fit in a
13/// [`DoubleWord`](crate::DoubleWord) are inlined (no heap allocation); larger values are stored as a
14/// heap-allocated array of [`Word`](crate::Word)s. The type carries a niche bit, so
15/// [`Option<UBig>`] occupies the same space as [`UBig`].
16///
17/// For the full discussion — construction, parsing, printing, and the memory layout — see the
18/// [user guide](https://zyxin.xyz/dashu/types.html).
19///
20/// # Examples
21///
22/// Parsing and printing (base 2–36 is supported for string/literal parsing):
23///
24/// ```
25/// # use dashu_base::ParseError;
26/// # use dashu_int::{UBig, Word};
27/// // parsing
28/// let a = UBig::from(408580953453092208335085386466371u128);
29/// let b = UBig::from(0x1231abcd4134u64);
30/// let c = UBig::from_str_radix("a2a123bbb127779cccc123", 32)?;
31/// let d = UBig::from_str_radix("1231abcd4134", 16)?;
32/// assert_eq!(a, c);
33/// assert_eq!(b, d);
34///
35/// // printing
36/// assert_eq!(format!("{}", UBig::from(12u8)), "12");
37/// assert_eq!(format!("{:#X}", UBig::from(0xabcdu16)), "0xABCD");
38/// if Word::BITS == 64 {
39///     // number of digits to display depends on the word size
40///     assert_eq!(
41///         format!("{:?}", UBig::ONE << 1000),
42///         "1071508607186267320..4386837205668069376"
43///     );
44/// }
45/// # Ok::<(), ParseError>(())
46/// ```
47///
48/// The niche bit makes `Option<UBig>` free:
49///
50/// ```
51/// # use dashu_int::UBig;
52/// use core::mem::size_of;
53/// assert_eq!(size_of::<UBig>(), size_of::<Option<UBig>>());
54/// ```
55#[derive(Eq, Hash, PartialEq)]
56#[repr(transparent)]
57pub struct UBig(pub(crate) Repr);
58
59impl UBig {
60    /// Get the representation of UBig.
61    #[rustversion::attr(since(1.64), const)]
62    #[inline]
63    pub(crate) fn repr(&self) -> TypedReprRef<'_> {
64        self.0.as_typed()
65    }
66
67    /// Convert into representation.
68    #[inline]
69    pub(crate) fn into_repr(self) -> TypedRepr {
70        self.0.into_typed()
71    }
72
73    /// [UBig] with value 0
74    pub const ZERO: Self = Self(Repr::zero());
75    /// [UBig] with value 1
76    pub const ONE: Self = Self(Repr::one());
77
78    /// Get the raw representation in [Word][crate::Word]s.
79    ///
80    /// If the number is zero, then empty slice will be returned.
81    ///
82    /// # Examples
83    ///
84    /// ```
85    /// # use dashu_int::{UBig, Word};
86    /// assert_eq!(UBig::ZERO.as_words(), &[] as &[Word]);
87    /// assert_eq!(UBig::ONE.as_words(), &[1]);
88    /// ```
89    #[inline]
90    pub fn as_words(&self) -> &[crate::Word] {
91        let (sign, words) = self.0.as_sign_slice();
92        debug_assert!(matches!(sign, crate::Sign::Positive));
93        words
94    }
95
96    /// Create a UBig from a single [Word][crate::Word].
97    ///
98    /// # Examples
99    ///
100    /// ```
101    /// # use dashu_int::UBig;
102    /// const ZERO: UBig = UBig::from_word(0);
103    /// assert_eq!(ZERO, UBig::ZERO);
104    /// const ONE: UBig = UBig::from_word(1);
105    /// assert_eq!(ONE, UBig::ONE);
106    /// ```
107    #[inline]
108    pub const fn from_word(word: crate::Word) -> Self {
109        Self(Repr::from_word(word))
110    }
111
112    /// Create a UBig from a [DoubleWord][crate::DoubleWord].
113    ///
114    /// # Examples
115    ///
116    /// ```
117    /// # use dashu_int::UBig;
118    /// const ZERO: UBig = UBig::from_dword(0);
119    /// assert_eq!(ZERO, UBig::ZERO);
120    /// const ONE: UBig = UBig::from_dword(1);
121    /// assert_eq!(ONE, UBig::ONE);
122    /// ```
123    #[inline]
124    pub const fn from_dword(dword: crate::DoubleWord) -> Self {
125        Self(Repr::from_dword(dword))
126    }
127
128    /// Create a UBig from a u64.
129    ///
130    /// This function is const on 32-bit and 64-bit targets.
131    ///
132    /// # Examples
133    ///
134    /// ```
135    /// # use dashu_int::UBig;
136    /// assert_eq!(UBig::from_u64(42), UBig::from(42u64));
137    /// assert_eq!(UBig::from_u64(10_939_058_860_032_000), UBig::from(10_939_058_860_032_000u64));
138    /// ```
139    #[cfg(not(any(target_pointer_width = "16", force_bits = "16")))]
140    #[inline]
141    pub const fn from_u64(n: u64) -> Self {
142        Self(Repr::from_dword(n as crate::DoubleWord))
143    }
144
145    /// Create a UBig from a u64.
146    ///
147    /// On 16-bit targets `u64` is wider than [`DoubleWord`][crate::DoubleWord], so this delegates
148    /// to `From<u64>` and is not `const`; on 32-bit and 64-bit targets the `const` constructor
149    /// above is used instead.
150    #[cfg(any(target_pointer_width = "16", force_bits = "16"))]
151    #[inline]
152    pub fn from_u64(n: u64) -> Self {
153        Self::from(n)
154    }
155
156    /// Convert a sequence of [Word][crate::Word]s into a UBig
157    ///
158    /// # Examples
159    ///
160    /// ```
161    /// # use dashu_int::{UBig, Word};
162    /// assert_eq!(UBig::from_words(&[] as &[Word]), UBig::ZERO);
163    /// assert_eq!(UBig::from_words(&[1]), UBig::ONE);
164    /// assert_eq!(UBig::from_words(&[1, 1]), (UBig::ONE << Word::BITS as usize) + UBig::ONE);
165    /// ```
166    #[inline]
167    pub fn from_words(words: &[crate::Word]) -> Self {
168        Self(Repr::from_buffer(words.into()))
169    }
170
171    /// Create an UBig from a static sequence of [Word][crate::Word]s. Similar to [from_words][UBig::from_words].
172    ///
173    /// The top word of the input word array must not be zero.
174    ///
175    /// This method is unsafe because it must be carefully handled. The generated instance
176    /// must not be mutated or dropped. Therefore the correct usage is to assign it to an
177    /// immutable static variable. Due to the risk, it's generally not recommended to use this method.
178    /// This method is intended for the use of static creation macros.
179    #[doc(hidden)]
180    #[inline]
181    pub const unsafe fn from_static_words(words: &'static [crate::Word]) -> Self {
182        Self(Repr::from_static_words(words))
183    }
184
185    /// Check whether the value is 0
186    ///
187    /// # Examples
188    ///
189    /// ```
190    /// # use dashu_int::UBig;
191    /// assert!(UBig::ZERO.is_zero());
192    /// assert!(!UBig::ONE.is_zero());
193    /// ```
194    #[inline]
195    pub const fn is_zero(&self) -> bool {
196        self.0.is_zero()
197    }
198
199    /// Check whether the value is 1
200    ///
201    /// # Examples
202    ///
203    /// ```
204    /// # use dashu_int::UBig;
205    /// assert!(!UBig::ZERO.is_one());
206    /// assert!(UBig::ONE.is_one());
207    /// ```
208    #[inline]
209    pub const fn is_one(&self) -> bool {
210        self.0.is_one()
211    }
212
213    /// Create an integer with `n` consecutive one bits (i.e. 2^n - 1).
214    ///
215    /// # Examples
216    ///
217    /// ```
218    /// # use dashu_int::UBig;
219    /// let mut n = UBig::ZERO;
220    /// n.set_bit(20);
221    /// n -= UBig::ONE;
222    /// assert_eq!(UBig::ones(20), n);
223    /// ```
224    #[inline]
225    pub fn ones(n: usize) -> Self {
226        Self(Repr::ones(n))
227    }
228}
229
230// This custom implementation is necessary due to https://github.com/rust-lang/rust/issues/98374
231impl Clone for UBig {
232    #[inline]
233    fn clone(&self) -> UBig {
234        UBig(self.0.clone())
235    }
236    #[inline]
237    fn clone_from(&mut self, source: &UBig) {
238        self.0.clone_from(&source.0)
239    }
240}
241
242#[cfg(test)]
243mod tests {
244    use super::*;
245    use crate::{buffer::Buffer, DoubleWord, Word};
246
247    impl UBig {
248        /// Capacity in Words.
249        #[inline]
250        fn capacity(&self) -> usize {
251            self.0.capacity()
252        }
253    }
254
255    fn gen_ubig(num_words: usize) -> UBig {
256        let mut buf = Buffer::allocate(num_words);
257        for i in 0..num_words {
258            buf.push(i as Word);
259        }
260        UBig(Repr::from_buffer(buf))
261    }
262
263    #[test]
264    fn test_buffer_to_ubig() {
265        let buf = Buffer::allocate(5);
266        let num = UBig(Repr::from_buffer(buf));
267        assert_eq!(num, UBig::ZERO);
268
269        let mut buf = Buffer::allocate(5);
270        buf.push(7);
271        let num = UBig(Repr::from_buffer(buf));
272        assert_eq!(num, UBig::from(7u8));
273
274        let mut buf = Buffer::allocate(100);
275        buf.push(7);
276        buf.push(0);
277        buf.push(0);
278        let num = UBig(Repr::from_buffer(buf));
279        assert_eq!(num, UBig::from(7u8));
280
281        let mut buf = Buffer::allocate(5);
282        buf.push(1);
283        buf.push(2);
284        buf.push(3);
285        buf.push(4);
286        let num = UBig(Repr::from_buffer(buf));
287        assert_eq!(num.capacity(), 7);
288
289        let mut buf = Buffer::allocate(100);
290        buf.push(1);
291        buf.push(2);
292        buf.push(3);
293        buf.push(4);
294        let num = UBig(Repr::from_buffer(buf));
295        assert_eq!(num.capacity(), 6);
296    }
297
298    #[test]
299    fn test_clone() {
300        let a = UBig::from(5u8);
301        assert_eq!(a.clone(), a);
302
303        let a = gen_ubig(10);
304        let b = a.clone();
305        assert_eq!(a, b);
306        assert_eq!(a.capacity(), b.capacity());
307    }
308
309    #[test]
310    fn test_clone_from() {
311        let num: UBig = gen_ubig(10);
312
313        let mut a = UBig::from(3u8);
314        a.clone_from(&num);
315        assert_eq!(a, num);
316        let b = UBig::from(7u8);
317        a.clone_from(&b);
318        assert_eq!(a, b);
319        a.clone_from(&b);
320        assert_eq!(a, b);
321
322        let mut a = gen_ubig(9);
323        let prev_cap = a.capacity();
324        a.clone_from(&num);
325        // the buffer should be reused, 9 is close enough to 10.
326        assert_eq!(a.capacity(), prev_cap);
327        assert_ne!(a.capacity(), num.capacity());
328
329        let mut a = gen_ubig(3);
330        let prev_cap = a.capacity();
331        a.clone_from(&num);
332        // the buffer should now be reallocated, it's too Small.
333        assert_ne!(a.capacity(), prev_cap);
334        assert_eq!(a.capacity(), num.capacity());
335
336        let mut a = gen_ubig(100);
337        let prev_cap = a.capacity();
338        a.clone_from(&num);
339        // the buffer should now be reallocated, it's too large.
340        assert_ne!(a.capacity(), prev_cap);
341        assert_eq!(a.capacity(), num.capacity());
342    }
343
344    #[test]
345    fn test_const_generation() {
346        const ZERO: UBig = UBig::from_word(0);
347        const ONE_SINGLE: UBig = UBig::from_word(1);
348        const ONE_DOUBLE: UBig = UBig::from_dword(1);
349        const DMAX: UBig = UBig::from_dword(DoubleWord::MAX);
350
351        const CDATA: [Word; 3] = [Word::MAX, Word::MAX, Word::MAX];
352        // SAFETY: DATA meets the requirements of from_static_words
353        static CONST_TMAX: UBig = unsafe { UBig::from_static_words(&CDATA) };
354        static DATA: [Word; 3] = [Word::MAX, Word::MAX, Word::MAX];
355        // SAFETY: DATA meets the requirements of from_static_words
356        static STATIC_TMAX: UBig = unsafe { UBig::from_static_words(&DATA) };
357
358        assert_eq!(ZERO, UBig::ZERO);
359        assert_eq!(ONE_SINGLE, UBig::ONE);
360        assert_eq!(ONE_DOUBLE, UBig::ONE);
361        assert_eq!(DMAX.capacity(), 2);
362        assert_eq!(CONST_TMAX.capacity(), 3);
363        assert_eq!(STATIC_TMAX.capacity(), 3);
364    }
365}
dashu_int/ubig.rs

dashu_int/
ubig.rs
