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

dashu_int/
ubig.rs
