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    #[inline]
62    pub(crate) const fn repr(&self) -> TypedReprRef<'_> {
63        self.0.as_typed()
64    }
65
66    /// Convert into representation.
67    #[inline]
68    pub(crate) fn into_repr(self) -> TypedRepr {
69        self.0.into_typed()
70    }
71
72    /// [UBig] with value 0
73    pub const ZERO: Self = Self(Repr::zero());
74    /// [UBig] with value 1
75    pub const ONE: Self = Self(Repr::one());
76
77    /// Get the raw representation in [Word][crate::Word]s.
78    ///
79    /// If the number is zero, then empty slice will be returned.
80    ///
81    /// # Examples
82    ///
83    /// ```
84    /// # use dashu_int::{UBig, Word};
85    /// assert_eq!(UBig::ZERO.as_words(), &[] as &[Word]);
86    /// assert_eq!(UBig::ONE.as_words(), &[1]);
87    /// ```
88    #[inline]
89    pub fn as_words(&self) -> &[crate::Word] {
90        let (sign, words) = self.0.as_sign_slice();
91        debug_assert!(matches!(sign, crate::Sign::Positive));
92        words
93    }
94
95    /// Create a UBig from a single [Word][crate::Word].
96    ///
97    /// # Examples
98    ///
99    /// ```
100    /// # use dashu_int::UBig;
101    /// const ZERO: UBig = UBig::from_word(0);
102    /// assert_eq!(ZERO, UBig::ZERO);
103    /// const ONE: UBig = UBig::from_word(1);
104    /// assert_eq!(ONE, UBig::ONE);
105    /// ```
106    #[inline]
107    pub const fn from_word(word: crate::Word) -> Self {
108        Self(Repr::from_word(word))
109    }
110
111    /// Create a UBig from a [DoubleWord][crate::DoubleWord].
112    ///
113    /// # Examples
114    ///
115    /// ```
116    /// # use dashu_int::UBig;
117    /// const ZERO: UBig = UBig::from_dword(0);
118    /// assert_eq!(ZERO, UBig::ZERO);
119    /// const ONE: UBig = UBig::from_dword(1);
120    /// assert_eq!(ONE, UBig::ONE);
121    /// ```
122    #[inline]
123    pub const fn from_dword(dword: crate::DoubleWord) -> Self {
124        Self(Repr::from_dword(dword))
125    }
126
127    /// Create a UBig from a u64.
128    ///
129    /// This function is const on 32-bit and 64-bit targets.
130    ///
131    /// # Examples
132    ///
133    /// ```
134    /// # use dashu_int::UBig;
135    /// assert_eq!(UBig::from_u64(42), UBig::from(42u64));
136    /// assert_eq!(UBig::from_u64(10_939_058_860_032_000), UBig::from(10_939_058_860_032_000u64));
137    /// ```
138    #[cfg(not(any(target_pointer_width = "16", force_bits = "16")))]
139    #[inline]
140    pub const fn from_u64(n: u64) -> Self {
141        Self(Repr::from_dword(n as crate::DoubleWord))
142    }
143
144    /// Create a UBig from a u64.
145    ///
146    /// On 16-bit targets `u64` is wider than [`DoubleWord`][crate::DoubleWord], so this delegates
147    /// to `From<u64>` and is not `const`; on 32-bit and 64-bit targets the `const` constructor
148    /// above is used instead.
149    #[cfg(any(target_pointer_width = "16", force_bits = "16"))]
150    #[inline]
151    pub fn from_u64(n: u64) -> Self {
152        Self::from(n)
153    }
154
155    /// Convert a sequence of [Word][crate::Word]s into a UBig
156    ///
157    /// # Examples
158    ///
159    /// ```
160    /// # use dashu_int::{UBig, Word};
161    /// assert_eq!(UBig::from_words(&[] as &[Word]), UBig::ZERO);
162    /// assert_eq!(UBig::from_words(&[1]), UBig::ONE);
163    /// assert_eq!(UBig::from_words(&[1, 1]), (UBig::ONE << Word::BITS as usize) + UBig::ONE);
164    /// ```
165    #[inline]
166    pub fn from_words(words: &[crate::Word]) -> Self {
167        Self(Repr::from_buffer(words.into()))
168    }
169
170    /// Create an UBig from a static sequence of [Word][crate::Word]s. Similar to [from_words][UBig::from_words].
171    ///
172    /// The top word of the input word array must not be zero.
173    ///
174    /// This method is unsafe because it must be carefully handled. The generated instance
175    /// must not be mutated or dropped. Therefore the correct usage is to assign it to an
176    /// immutable static variable. Due to the risk, it's generally not recommended to use this method.
177    /// This method is intended for the use of static creation macros.
178    #[doc(hidden)]
179    #[inline]
180    pub const unsafe fn from_static_words(words: &'static [crate::Word]) -> Self {
181        Self(Repr::from_static_words(words))
182    }
183
184    /// Check whether the value is 0
185    ///
186    /// # Examples
187    ///
188    /// ```
189    /// # use dashu_int::UBig;
190    /// assert!(UBig::ZERO.is_zero());
191    /// assert!(!UBig::ONE.is_zero());
192    /// ```
193    #[inline]
194    pub const fn is_zero(&self) -> bool {
195        self.0.is_zero()
196    }
197
198    /// Check whether the value is 1
199    ///
200    /// # Examples
201    ///
202    /// ```
203    /// # use dashu_int::UBig;
204    /// assert!(!UBig::ZERO.is_one());
205    /// assert!(UBig::ONE.is_one());
206    /// ```
207    #[inline]
208    pub const fn is_one(&self) -> bool {
209        self.0.is_one()
210    }
211
212    /// Create an integer with `n` consecutive one bits (i.e. 2^n - 1).
213    ///
214    /// # Examples
215    ///
216    /// ```
217    /// # use dashu_int::UBig;
218    /// let mut n = UBig::ZERO;
219    /// n.set_bit(20);
220    /// n -= UBig::ONE;
221    /// assert_eq!(UBig::ones(20), n);
222    /// ```
223    #[inline]
224    pub fn ones(n: usize) -> Self {
225        Self(Repr::ones(n))
226    }
227}
228
229// This custom implementation is necessary due to https://github.com/rust-lang/rust/issues/98374
230impl Clone for UBig {
231    #[inline]
232    fn clone(&self) -> UBig {
233        UBig(self.0.clone())
234    }
235    #[inline]
236    fn clone_from(&mut self, source: &UBig) {
237        self.0.clone_from(&source.0)
238    }
239}
240
241#[cfg(test)]
242mod tests {
243    use super::*;
244    use crate::{buffer::Buffer, DoubleWord, Word};
245
246    impl UBig {
247        /// Capacity in Words.
248        #[inline]
249        fn capacity(&self) -> usize {
250            self.0.capacity()
251        }
252    }
253
254    fn gen_ubig(num_words: usize) -> UBig {
255        let mut buf = Buffer::allocate(num_words);
256        for i in 0..num_words {
257            buf.push(i as Word);
258        }
259        UBig(Repr::from_buffer(buf))
260    }
261
262    #[test]
263    fn test_buffer_to_ubig() {
264        let buf = Buffer::allocate(5);
265        let num = UBig(Repr::from_buffer(buf));
266        assert_eq!(num, UBig::ZERO);
267
268        let mut buf = Buffer::allocate(5);
269        buf.push(7);
270        let num = UBig(Repr::from_buffer(buf));
271        assert_eq!(num, UBig::from(7u8));
272
273        let mut buf = Buffer::allocate(100);
274        buf.push(7);
275        buf.push(0);
276        buf.push(0);
277        let num = UBig(Repr::from_buffer(buf));
278        assert_eq!(num, UBig::from(7u8));
279
280        let mut buf = Buffer::allocate(5);
281        buf.push(1);
282        buf.push(2);
283        buf.push(3);
284        buf.push(4);
285        let num = UBig(Repr::from_buffer(buf));
286        assert_eq!(num.capacity(), 7);
287
288        let mut buf = Buffer::allocate(100);
289        buf.push(1);
290        buf.push(2);
291        buf.push(3);
292        buf.push(4);
293        let num = UBig(Repr::from_buffer(buf));
294        assert_eq!(num.capacity(), 6);
295    }
296
297    #[test]
298    fn test_clone() {
299        let a = UBig::from(5u8);
300        assert_eq!(a.clone(), a);
301
302        let a = gen_ubig(10);
303        let b = a.clone();
304        assert_eq!(a, b);
305        assert_eq!(a.capacity(), b.capacity());
306    }
307
308    #[test]
309    fn test_clone_from() {
310        let num: UBig = gen_ubig(10);
311
312        let mut a = UBig::from(3u8);
313        a.clone_from(&num);
314        assert_eq!(a, num);
315        let b = UBig::from(7u8);
316        a.clone_from(&b);
317        assert_eq!(a, b);
318        a.clone_from(&b);
319        assert_eq!(a, b);
320
321        let mut a = gen_ubig(9);
322        let prev_cap = a.capacity();
323        a.clone_from(&num);
324        // the buffer should be reused, 9 is close enough to 10.
325        assert_eq!(a.capacity(), prev_cap);
326        assert_ne!(a.capacity(), num.capacity());
327
328        let mut a = gen_ubig(3);
329        let prev_cap = a.capacity();
330        a.clone_from(&num);
331        // the buffer should now be reallocated, it's too Small.
332        assert_ne!(a.capacity(), prev_cap);
333        assert_eq!(a.capacity(), num.capacity());
334
335        let mut a = gen_ubig(100);
336        let prev_cap = a.capacity();
337        a.clone_from(&num);
338        // the buffer should now be reallocated, it's too large.
339        assert_ne!(a.capacity(), prev_cap);
340        assert_eq!(a.capacity(), num.capacity());
341    }
342
343    #[test]
344    fn test_const_generation() {
345        const ZERO: UBig = UBig::from_word(0);
346        const ONE_SINGLE: UBig = UBig::from_word(1);
347        const ONE_DOUBLE: UBig = UBig::from_dword(1);
348        const DMAX: UBig = UBig::from_dword(DoubleWord::MAX);
349
350        const CDATA: [Word; 3] = [Word::MAX, Word::MAX, Word::MAX];
351        // SAFETY: DATA meets the requirements of from_static_words
352        static CONST_TMAX: UBig = unsafe { UBig::from_static_words(&CDATA) };
353        static DATA: [Word; 3] = [Word::MAX, Word::MAX, Word::MAX];
354        // SAFETY: DATA meets the requirements of from_static_words
355        static STATIC_TMAX: UBig = unsafe { UBig::from_static_words(&DATA) };
356
357        assert_eq!(ZERO, UBig::ZERO);
358        assert_eq!(ONE_SINGLE, UBig::ONE);
359        assert_eq!(ONE_DOUBLE, UBig::ONE);
360        assert_eq!(DMAX.capacity(), 2);
361        assert_eq!(CONST_TMAX.capacity(), 3);
362        assert_eq!(STATIC_TMAX.capacity(), 3);
363    }
364}
dashu_int/ubig.rs

dashu_int/
ubig.rs
