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

dashu_int/
ubig.rs
