bnum/bint/
mod.rs

1macro_rules! ilog {
2    ($method: ident $(, $base: ident : $ty: ty)?) => {
3        #[doc = doc::$method!(I)]
4        #[must_use = doc::must_use_op!()]
5        #[inline]
6        pub const fn $method(self, $($base : $ty),*) -> ExpType {
7            $(
8                if $base.le(&<$ty>::ONE) {
9                    panic!(errors::err_msg!(errors::invalid_log_base!()))
10                }
11            ), *
12            if self.is_negative() {
13                panic!(errors::err_msg!(errors::non_positive_log_message!()))
14            } else {
15                self.bits.$method($($base.bits)?)
16            }
17        }
18    }
19}
20
21use crate::digit;
22use crate::ExpType;
23use crate::{doc, errors};
24
25#[cfg(feature = "serde")]
26use serde::{Deserialize, Serialize};
27
28#[cfg(feature = "borsh")]
29use ::{
30    alloc::string::ToString,
31    borsh::{BorshDeserialize, BorshSchema, BorshSerialize},
32};
33
34use core::default::Default;
35
36use core::iter::{Iterator, Product, Sum};
37
38macro_rules! mod_impl {
39    ($BUint: ident, $BInt: ident, $Digit: ident) => {
40        /// Big signed integer type, of fixed size which must be known at compile time. Stored as a
41        #[doc = concat!(" [`", stringify!($BUint), "`].")]
42        ///
43        /// Digits of the underlying
44        #[doc = concat!("[`", stringify!($BUint), "`](crate::", stringify!($BUint), ")")]
45        /// are stored in little endian (least significant digit first). This integer type aims to exactly replicate the behaviours of Rust's built-in signed integer types: [`i8`], [`i16`], [`i32`], [`i64`], [`i128`] and [`isize`]. The const generic parameter `N` is the number of digits that are stored in the underlying
46        #[doc = concat!("[`", stringify!($BUint), "`].")]
47        ///
48        #[doc = doc::arithmetic_doc!($BInt)]
49
50        #[derive(Clone, Copy, Hash, PartialEq, Eq)]
51        #[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
52        #[cfg_attr(feature = "borsh", derive(BorshSerialize, BorshDeserialize, BorshSchema))]                
53        #[cfg_attr(feature = "arbitrary", derive(arbitrary::Arbitrary))]
54        #[cfg_attr(feature = "valuable", derive(valuable::Valuable))]
55        #[repr(transparent)]
56        pub struct $BInt<const N: usize> {
57            pub(crate) bits: $BUint<N>,
58        }
59
60        #[cfg(feature = "zeroize")]
61        impl<const N: usize> zeroize::DefaultIsZeroes for $BInt<N> {}
62
63        impl<const N: usize> $BInt<N> {
64            #[doc = doc::count_ones!(I 256)]
65            #[must_use = doc::must_use_op!()]
66            #[inline]
67            pub const fn count_ones(self) -> ExpType {
68                self.bits.count_ones()
69            }
70
71            #[doc = doc::count_zeros!(I 256)]
72            #[must_use = doc::must_use_op!()]
73            #[inline]
74            pub const fn count_zeros(self) -> ExpType {
75                self.bits.count_zeros()
76            }
77
78            #[doc = doc::leading_zeros!(I 256)]
79            #[must_use = doc::must_use_op!()]
80            #[inline]
81            pub const fn leading_zeros(self) -> ExpType {
82                self.bits.leading_zeros()
83            }
84
85            #[doc = doc::trailing_zeros!(I 256)]
86            #[must_use = doc::must_use_op!()]
87            #[inline]
88            pub const fn trailing_zeros(self) -> ExpType {
89                self.bits.trailing_zeros()
90            }
91
92            #[doc = doc::leading_ones!(I 256, NEG_ONE)]
93            #[must_use = doc::must_use_op!()]
94            #[inline]
95            pub const fn leading_ones(self) -> ExpType {
96                self.bits.leading_ones()
97            }
98
99            #[doc = doc::trailing_ones!(I 256)]
100            #[must_use = doc::must_use_op!()]
101            #[inline]
102            pub const fn trailing_ones(self) -> ExpType {
103                self.bits.trailing_ones()
104            }
105
106            #[doc = doc::cast_unsigned!(I)]
107            #[must_use = doc::must_use_op!()]
108            #[inline]
109            pub const fn cast_unsigned(self) -> $BUint<N> {
110                self.to_bits()
111            }
112
113            #[doc = doc::rotate_left!(I 256, "i")]
114            #[must_use = doc::must_use_op!()]
115            #[inline]
116            pub const fn rotate_left(self, n: ExpType) -> Self {
117                Self::from_bits(self.bits.rotate_left(n))
118            }
119
120            #[doc = doc::rotate_right!(I 256, "i")]
121            #[must_use = doc::must_use_op!()]
122            #[inline]
123            pub const fn rotate_right(self, n: ExpType) -> Self {
124                Self::from_bits(self.bits.rotate_right(n))
125            }
126
127            #[doc = doc::swap_bytes!(I 256, "i")]
128            #[must_use = doc::must_use_op!()]
129            #[inline]
130            pub const fn swap_bytes(self) -> Self {
131                Self::from_bits(self.bits.swap_bytes())
132            }
133
134            #[doc = doc::reverse_bits!(I 256, "i")]
135            #[must_use = doc::must_use_op!()]
136            #[inline]
137            pub const fn reverse_bits(self) -> Self {
138                Self::from_bits(self.bits.reverse_bits())
139            }
140
141            #[doc = doc::unsigned_abs!(I)]
142            #[must_use = doc::must_use_op!()]
143            #[inline]
144            pub const fn unsigned_abs(self) -> $BUint<N> {
145                if self.is_negative() {
146                    self.wrapping_neg().bits
147                } else {
148                    self.bits
149                }
150            }
151
152            #[doc = doc::pow!(I 256)]
153            #[must_use = doc::must_use_op!()]
154            #[inline]
155            pub const fn pow(self, exp: ExpType) -> Self {
156                #[cfg(debug_assertions)]
157                return self.strict_pow(exp);
158
159                #[cfg(not(debug_assertions))]
160                self.wrapping_pow(exp)
161            }
162
163            #[doc = doc::div_euclid!(I)]
164            #[must_use = doc::must_use_op!()]
165            #[inline]
166            pub const fn div_euclid(self, rhs: Self) -> Self {
167                assert!(self.ne(&Self::MIN) || rhs.ne(&Self::NEG_ONE), errors::err_msg!("attempt to divide with overflow"));
168                self.wrapping_div_euclid(rhs)
169            }
170
171            #[doc = doc::rem_euclid!(I)]
172            #[must_use = doc::must_use_op!()]
173            #[inline]
174            pub const fn rem_euclid(self, rhs: Self) -> Self {
175                assert!(self.ne(&Self::MIN) || rhs.ne(&Self::NEG_ONE), errors::err_msg!("attempt to calculate remainder with overflow"));
176                self.wrapping_rem_euclid(rhs)
177            }
178
179            #[doc = doc::abs!(I)]
180            #[must_use = doc::must_use_op!()]
181            #[inline]
182            pub const fn abs(self) -> Self {
183                #[cfg(debug_assertions)]
184                return self.strict_abs();
185
186                #[cfg(not(debug_assertions))]
187                match self.checked_abs() {
188                    Some(int) => int,
189                    None => Self::MIN,
190                }
191            }
192
193            #[doc = doc::signum!(I)]
194            #[must_use = doc::must_use_op!()]
195            #[inline]
196            pub const fn signum(self) -> Self {
197                if self.is_negative() {
198                    Self::NEG_ONE
199                } else if self.is_zero() {
200                    Self::ZERO
201                } else {
202                    Self::ONE
203                }
204            }
205
206            #[doc = doc::is_positive!(I)]
207            #[must_use = doc::must_use_op!()]
208            #[inline]
209            pub const fn is_positive(self) -> bool {
210                let signed_digit = self.signed_digit();
211                signed_digit.is_positive() || (signed_digit == 0 && !self.bits.is_zero())
212            }
213
214            #[doc = doc::is_negative!(I)]
215            #[must_use = doc::must_use_op!()]
216            #[inline]
217            pub const fn is_negative(self) -> bool {
218                self.signed_digit().is_negative()
219            }
220
221            #[doc = doc::doc_comment! {
222                I 256,
223                "Returns `true` if and only if `self == 2^k` for some integer `k`.",
224
225                "let n = " stringify!(I256) "::from(1i16 << 12);\n"
226                "assert!(n.is_power_of_two());\n"
227                "let m = " stringify!(I256) "::from(90i8);\n"
228                "assert!(!m.is_power_of_two());\n"
229                "assert!(!((-n).is_power_of_two()));"
230            }]
231            #[must_use]
232            #[inline]
233            pub const fn is_power_of_two(self) -> bool {
234                !self.is_negative() &&self.bits.is_power_of_two()
235            }
236
237            #[doc = doc::midpoint!(I)]
238            #[must_use = doc::must_use_op!()]
239            #[inline]
240            pub const fn midpoint(self, rhs: Self) -> Self {
241                // see section 2.5: Average of Two Integers in Hacker's Delight
242                let x = self.bitxor(rhs);
243                let t = self.bitand(rhs).add(x.shr(1));
244                if t.is_negative() && x.bits.digits[0] & 1 == 1 { // t is negative and 
245                    t.add($BInt::ONE)
246                } else {
247                    t
248                }
249            }
250
251            ilog!(ilog, base: Self);
252            ilog!(ilog2);
253            ilog!(ilog10);
254
255            #[doc = doc::abs_diff!(I)]
256            #[must_use = doc::must_use_op!()]
257            #[inline]
258            pub const fn abs_diff(self, other: Self) -> $BUint<N> {
259                if self.lt(&other) {
260                    other.wrapping_sub(self).to_bits()
261                } else {
262                    self.wrapping_sub(other).to_bits()
263                }
264            }
265
266            #[doc = doc::next_multiple_of!(I)]
267            #[must_use = doc::must_use_op!()]
268            #[inline]
269            pub const fn next_multiple_of(self, rhs: Self) -> Self {
270                let rem = self.wrapping_rem_euclid(rhs);
271                if rem.is_zero() {
272                    return self;
273                }
274                if rem.is_negative() == rhs.is_negative() {
275                    self.add(rhs.sub(rem))
276                } else {
277                    self.sub(rem)
278                }
279            }
280
281            #[doc = doc::div_floor!(I)]
282            #[must_use = doc::must_use_op!()]
283            #[inline]
284            pub const fn div_floor(self, rhs: Self) -> Self {
285                if rhs.is_zero() {
286                    errors::div_zero!();
287                }
288                let (div, rem) = self.div_rem_unchecked(rhs);
289                if rem.is_zero() || self.is_negative() == rhs.is_negative() {
290                    div
291                } else {
292                    div.sub(Self::ONE)
293                }
294            }
295
296            #[doc = doc::div_ceil!(I)]
297            #[must_use = doc::must_use_op!()]
298            #[inline]
299            pub const fn div_ceil(self, rhs: Self) -> Self {
300                if rhs.is_zero() {
301                    errors::div_zero!();
302                }
303                let (div, rem) = self.div_rem_unchecked(rhs);
304                if rem.is_zero() || self.is_negative() != rhs.is_negative() {
305                    div
306                } else {
307                    div.add(Self::ONE)
308                }
309            }
310        }
311
312        impl<const N: usize> $BInt<N> {
313            #[doc = doc::bits!(I 256)]
314            #[must_use]
315            #[inline]
316            pub const fn bits(&self) -> ExpType {
317                self.bits.bits()
318            }
319
320            #[doc = doc::bit!(I 256)]
321            #[must_use]
322            #[inline]
323            pub const fn bit(&self, b: ExpType) -> bool {
324                self.bits.bit(b)
325            }
326
327            #[inline(always)]
328            pub(crate) const fn signed_digit(&self) -> digit::$Digit::SignedDigit {
329                self.bits.digits[N - 1] as _
330            }
331
332            #[doc = doc::is_zero!(I 256)]
333            #[must_use]
334            #[inline]
335            pub const fn is_zero(&self) -> bool {
336                self.bits.is_zero()
337            }
338
339            #[doc = doc::is_one!(I 256)]
340            #[must_use]
341            #[inline]
342            pub const fn is_one(&self) -> bool {
343                self.bits.is_one()
344            }
345
346            /// Creates a signed integer with `bits` as its underlying representation in two's complement.
347            ///
348            /// This method is faster for casting from a
349            #[doc = concat!("[`", stringify!($BUint), "`]")]
350            /// to a
351            #[doc = concat!("[`", stringify!($BInt), "`]")]
352            /// of the same size than using the `As` trait.
353            #[must_use]
354            #[inline(always)]
355            pub const fn from_bits(bits: $BUint<N>) -> Self {
356                Self { bits }
357            }
358
359            /// This simply returns the underlying representation of the integer in two's complement, as an unsigned integer.
360            ///
361            /// This method is faster for casting from a
362            #[doc = concat!("[`", stringify!($BInt), "`]")]
363            /// to a
364            #[doc = concat!("[`", stringify!($BUint), "`]")]
365            /// of the same size than using the `As` trait.
366            #[must_use]
367            #[inline(always)]
368            pub const fn to_bits(self) -> $BUint<N> {
369                self.bits
370            }
371        }
372
373        impl<const N: usize> Default for $BInt<N> {
374            #[doc = doc::default!()]
375            #[inline]
376            fn default() -> Self {
377                Self::ZERO
378            }
379        }
380
381        impl<const N: usize> Product<Self> for $BInt<N> {
382            #[inline]
383            fn product<I: Iterator<Item = Self>>(iter: I) -> Self {
384                iter.fold(Self::ONE, |a, b| a * b)
385            }
386        }
387
388        impl<'a, const N: usize> Product<&'a Self> for $BInt<N> {
389            #[inline]
390            fn product<I: Iterator<Item = &'a Self>>(iter: I) -> Self {
391                iter.fold(Self::ONE, |a, b| a * b)
392            }
393        }
394
395        impl<const N: usize> Sum<Self> for $BInt<N> {
396            #[inline]
397            fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
398                iter.fold(Self::ZERO, |a, b| a + b)
399            }
400        }
401
402        impl<'a, const N: usize> Sum<&'a Self> for $BInt<N> {
403            #[inline]
404            fn sum<I: Iterator<Item = &'a Self>>(iter: I) -> Self {
405                iter.fold(Self::ZERO, |a, b| a + b)
406            }
407        }
408
409        #[cfg(any(test, feature = "quickcheck"))]
410        impl<const N: usize> quickcheck::Arbitrary for $BInt<N> {
411            #[inline]
412            fn arbitrary(g: &mut quickcheck::Gen) -> Self {
413                Self::from_bits(<$BUint::<N> as quickcheck::Arbitrary>::arbitrary(g))
414            }
415        }
416    };
417}
418
419#[cfg(test)]
420crate::test::all_digit_tests! {
421    use crate::test::{
422        debug_skip, test_bignum,
423        types::itest,
424    };
425    // use crate::test::types::big_types::$Digit::*;
426
427    crate::int::tests!(itest);
428
429    test_bignum! {
430        function: <itest>::unsigned_abs(a: itest),
431        cases: [
432            (itest::MIN),
433            (0 as itest)
434        ]
435    }
436    test_bignum! {
437        function: <itest>::abs(a: itest),
438        skip: debug_skip!(a == itest::MIN)
439    }
440    test_bignum! {
441        function: <itest>::signum(a: itest)
442    }
443    test_bignum! {
444        function: <itest>::is_positive(a: itest)
445    }
446    test_bignum! {
447        function: <itest>::is_negative(a: itest)
448    }
449    test_bignum! {
450        function: <itest>::cast_unsigned(a: itest)
451    }
452
453    #[test]
454    fn bit() {
455        let i = ITEST::from(0b10100101010101i16);
456        assert!(i.bit(2));
457        assert!(!i.bit(3));
458        assert!(i.bit(8));
459        assert!(!i.bit(9));
460        assert!(i.bit(i.bits() - 1));
461    }
462
463    #[test]
464    fn is_zero() {
465        assert!(ITEST::ZERO.is_zero());
466        assert!(!ITEST::MAX.is_zero());
467        assert!(!ITEST::ONE.is_zero());
468    }
469
470    #[test]
471    fn is_one() {
472        assert!(ITEST::ONE.is_one());
473        assert!(!ITEST::MAX.is_one());
474        assert!(!ITEST::ZERO.is_one());
475    }
476
477    #[test]
478    fn bits() {
479        let u = ITEST::from(0b10100101010101i16);
480        assert_eq!(u.bits(), 14);
481    }
482
483    #[test]
484    fn default() {
485        assert_eq!(ITEST::default(), itest::default().into());
486    }
487
488    #[test]
489    fn is_power_of_two() {
490        assert!(!ITEST::from(-1273i16).is_power_of_two());
491        assert!(!ITEST::from(8945i16).is_power_of_two());
492        assert!(ITEST::from(1i16 << 14).is_power_of_two());
493    }
494
495    #[test]
496    fn sum() {
497        let v = vec![&ITEST::ZERO, &ITEST::ONE, &ITEST::TWO, &ITEST::THREE, &ITEST::FOUR];
498        assert_eq!(ITEST::TEN, v.iter().copied().sum());
499        assert_eq!(ITEST::TEN, v.into_iter().sum());
500    }
501
502    #[test]
503    fn product() {
504        let v = vec![&ITEST::ONE, &ITEST::TWO, &ITEST::THREE];
505        assert_eq!(ITEST::SIX, v.iter().copied().sum());
506        assert_eq!(ITEST::SIX, v.into_iter().sum());
507    }
508}
509
510crate::macro_impl!(mod_impl);
511
512mod bigint_helpers;
513pub mod cast;
514mod checked;
515mod cmp;
516mod const_trait_fillers;
517mod consts;
518mod convert;
519mod endian;
520mod fmt;
521#[cfg(feature = "numtraits")]
522mod numtraits;
523mod ops;
524mod overflowing;
525mod radix;
526mod saturating;
527mod strict;
528mod unchecked;
529mod wrapping;
bnum/bint/mod.rs

bnum/bint/
mod.rs
