crypto_bigint/
int.rs

1//! Stack-allocated big signed integers.
2
3mod add;
4mod bit_and;
5mod bit_not;
6mod bit_or;
7mod bit_xor;
8mod cmp;
9mod ct;
10mod div;
11mod div_unsigned;
12mod encoding;
13mod from;
14mod gcd;
15mod invert_mod;
16mod mod_symbol;
17mod mul;
18mod mul_unsigned;
19mod neg;
20mod resize;
21mod shl;
22mod shr;
23mod sign;
24mod sqrt;
25mod sub;
26pub(crate) mod types;
27
28#[cfg(feature = "rand_core")]
29mod rand;
30
31use crate::{
32    Bounded, Choice, ConstOne, ConstZero, Constants, CtEq, CtOption, FixedInteger, Integer, Limb,
33    NonZero, Odd, One, Signed, Uint, Word, Zero, sealed::Sealed,
34};
35use core::fmt;
36
37#[cfg(feature = "serde")]
38use crate::Encoding;
39#[cfg(feature = "serde")]
40use serdect::serde::{Deserialize, Deserializer, Serialize, Serializer};
41
42/// Stack-allocated big _signed_ integer.
43/// See [`Uint`] for _unsigned_ integers.
44///
45/// Created as a [`Uint`] newtype.
46#[allow(clippy::derived_hash_with_manual_eq)]
47#[derive(Copy, Clone, Hash)]
48#[repr(transparent)]
49pub struct Int<const LIMBS: usize>(Uint<LIMBS>);
50
51impl<const LIMBS: usize> Int<LIMBS> {
52    /// The value `0`.
53    pub const ZERO: Self = Self(Uint::ZERO); // Bit sequence (be): 0000....0000
54
55    /// The value `1`.
56    pub const ONE: Self = Self(Uint::ONE); // Bit sequence (be): 0000....0001
57
58    /// The value `-1`
59    pub const MINUS_ONE: Self = Self(Uint::MAX); // Bit sequence (be): 1111....1111
60
61    /// Smallest value this [`Int`] can express.
62    pub const MIN: Self = Self::MAX.not(); // Bit sequence (be): 1000....0000
63
64    /// Maximum value this [`Int`] can express.
65    pub const MAX: Self = Self(Uint::MAX.shr_vartime(1u32)); // Bit sequence (be): 0111....1111
66
67    /// Bit mask for the sign bit of this [`Int`].
68    pub const SIGN_MASK: Self = Self::MIN; // Bit sequence (be): 1000....0000
69
70    /// Total size of the represented integer in bits.
71    pub const BITS: u32 = Uint::<LIMBS>::BITS;
72
73    /// Total size of the represented integer in bytes.
74    pub const BYTES: usize = Uint::<LIMBS>::BYTES;
75
76    /// The number of limbs used on this platform.
77    pub const LIMBS: usize = LIMBS;
78
79    /// Const-friendly [`Int`] constructor.
80    #[must_use]
81    pub const fn new(limbs: [Limb; LIMBS]) -> Self {
82        Self(Uint::new(limbs))
83    }
84
85    /// Const-friendly [`Int`] constructor.
86    ///
87    /// Reinterprets the bits of a value of type [`Uint`] as an [`Int`].
88    /// For a proper conversion, see [`Int::new_from_abs_sign`];
89    /// the public interface of this function is available at [`Uint::as_int`].
90    pub(crate) const fn from_bits(value: Uint<LIMBS>) -> Self {
91        Self(value)
92    }
93
94    /// Create an [`Int`] from an array of [`Word`]s (i.e. word-sized unsigned
95    /// integers).
96    #[inline]
97    #[must_use]
98    pub const fn from_words(arr: [Word; LIMBS]) -> Self {
99        Self(Uint::from_words(arr))
100    }
101
102    /// Create an array of [`Word`]s (i.e. word-sized unsigned integers) from
103    /// an [`Int`].
104    #[inline]
105    #[must_use]
106    pub const fn to_words(self) -> [Word; LIMBS] {
107        self.0.to_words()
108    }
109
110    /// Borrow the inner limbs as an array of [`Word`]s.
111    #[must_use]
112    pub const fn as_words(&self) -> &[Word; LIMBS] {
113        self.0.as_words()
114    }
115
116    /// Borrow the inner limbs as a mutable array of [`Word`]s.
117    pub const fn as_mut_words(&mut self) -> &mut [Word; LIMBS] {
118        self.0.as_mut_words()
119    }
120
121    /// Borrow the inner limbs as a mutable slice of [`Word`]s.
122    #[deprecated(since = "0.7.0", note = "please use `as_mut_words` instead")]
123    pub fn as_words_mut(&mut self) -> &mut [Word] {
124        self.as_mut_words()
125    }
126
127    /// Borrow the limbs of this [`Int`].
128    #[must_use]
129    pub const fn as_limbs(&self) -> &[Limb; LIMBS] {
130        self.0.as_limbs()
131    }
132
133    /// Borrow the limbs of this [`Int`] mutably.
134    pub const fn as_mut_limbs(&mut self) -> &mut [Limb; LIMBS] {
135        self.0.as_mut_limbs()
136    }
137
138    /// Borrow the limbs of this [`Int`] mutably.
139    #[deprecated(since = "0.7.0", note = "please use `as_mut_limbs` instead")]
140    pub const fn as_limbs_mut(&mut self) -> &mut [Limb] {
141        self.as_mut_limbs()
142    }
143
144    /// Convert this [`Int`] into its inner limbs.
145    #[must_use]
146    pub const fn to_limbs(self) -> [Limb; LIMBS] {
147        self.0.to_limbs()
148    }
149
150    /// Convert to a [`NonZero<Int<LIMBS>>`].
151    ///
152    /// Returns some if the original value is non-zero, and false otherwise.
153    #[must_use]
154    pub const fn to_nz(self) -> CtOption<NonZero<Self>> {
155        CtOption::new(NonZero(self), self.0.is_nonzero())
156    }
157
158    /// Convert to a [`Odd<Int<LIMBS>>`].
159    ///
160    /// Returns some if the original value is odd, and false otherwise.
161    #[must_use]
162    pub const fn to_odd(self) -> CtOption<Odd<Self>> {
163        CtOption::new(Odd(self), self.0.is_odd())
164    }
165
166    /// Interpret the data in this object as a [`Uint`] instead.
167    ///
168    /// Note: this is a casting operation. See
169    /// - [`Self::try_into_uint`] for the checked equivalent, and
170    /// - [`Self::abs`] to obtain the absolute value of `self`.
171    #[must_use]
172    pub const fn as_uint(&self) -> &Uint<LIMBS> {
173        &self.0
174    }
175
176    /// Get a [`Uint`] equivalent of this value; returns `None` if `self` is negative.
177    ///
178    /// Note: this is a checked conversion operation. See
179    /// - [`Self::as_uint`] for the unchecked equivalent, and
180    /// - [`Self::abs`] to obtain the absolute value of `self`.
181    #[must_use]
182    pub const fn try_into_uint(self) -> CtOption<Uint<LIMBS>> {
183        CtOption::new(self.0, self.is_negative().not())
184    }
185
186    /// Whether this [`Int`] is equal to `Self::MIN`.
187    #[must_use]
188    pub const fn is_min(&self) -> Choice {
189        Self::eq(self, &Self::MIN)
190    }
191
192    /// Whether this [`Int`] is equal to `Self::MAX`.
193    #[must_use]
194    pub const fn is_max(&self) -> Choice {
195        Self::eq(self, &Self::MAX)
196    }
197
198    /// Is this [`Int`] equal to zero?
199    #[must_use]
200    pub const fn is_zero(&self) -> Choice {
201        self.0.is_zero()
202    }
203
204    /// Invert the most significant bit (msb) of this [`Int`]
205    const fn invert_msb(&self) -> Self {
206        Self(self.0.bitxor(&Self::SIGN_MASK.0))
207    }
208}
209
210impl<const LIMBS: usize> AsRef<[Word; LIMBS]> for Int<LIMBS> {
211    fn as_ref(&self) -> &[Word; LIMBS] {
212        self.as_words()
213    }
214}
215
216impl<const LIMBS: usize> AsMut<[Word; LIMBS]> for Int<LIMBS> {
217    fn as_mut(&mut self) -> &mut [Word; LIMBS] {
218        self.as_mut_words()
219    }
220}
221
222impl<const LIMBS: usize> AsRef<[Limb]> for Int<LIMBS> {
223    fn as_ref(&self) -> &[Limb] {
224        self.as_limbs()
225    }
226}
227
228impl<const LIMBS: usize> AsMut<[Limb]> for Int<LIMBS> {
229    fn as_mut(&mut self) -> &mut [Limb] {
230        self.as_mut_limbs()
231    }
232}
233
234impl<const LIMBS: usize> Bounded for Int<LIMBS> {
235    const BITS: u32 = Self::BITS;
236    const BYTES: usize = Self::BYTES;
237}
238
239impl<const LIMBS: usize> Constants for Int<LIMBS> {
240    const MAX: Self = Self::MAX;
241}
242
243impl<const LIMBS: usize> Default for Int<LIMBS> {
244    fn default() -> Self {
245        Self::ZERO
246    }
247}
248
249impl<const LIMBS: usize> FixedInteger for Int<LIMBS> {
250    const LIMBS: usize = LIMBS;
251}
252
253impl<const LIMBS: usize> Integer for Int<LIMBS> {
254    fn as_limbs(&self) -> &[Limb] {
255        self.0.as_limbs()
256    }
257
258    fn as_mut_limbs(&mut self) -> &mut [Limb] {
259        self.0.as_mut_limbs()
260    }
261
262    fn nlimbs(&self) -> usize {
263        self.0.nlimbs()
264    }
265}
266
267impl<const LIMBS: usize> Sealed for Int<LIMBS> {}
268
269impl<const LIMBS: usize> Signed for Int<LIMBS> {
270    type Unsigned = Uint<LIMBS>;
271
272    fn abs_sign(&self) -> (Uint<LIMBS>, Choice) {
273        self.abs_sign()
274    }
275
276    fn is_negative(&self) -> Choice {
277        self.is_negative()
278    }
279
280    fn is_positive(&self) -> Choice {
281        self.is_positive()
282    }
283}
284
285impl<const LIMBS: usize> ConstZero for Int<LIMBS> {
286    const ZERO: Self = Self::ZERO;
287}
288
289impl<const LIMBS: usize> ConstOne for Int<LIMBS> {
290    const ONE: Self = Self::ONE;
291}
292
293impl<const LIMBS: usize> Zero for Int<LIMBS> {
294    #[inline(always)]
295    fn zero() -> Self {
296        Self::ZERO
297    }
298}
299
300impl<const LIMBS: usize> One for Int<LIMBS> {
301    #[inline(always)]
302    fn one() -> Self {
303        Self::ONE
304    }
305}
306
307impl<const LIMBS: usize> num_traits::Zero for Int<LIMBS> {
308    #[inline(always)]
309    fn zero() -> Self {
310        Self::ZERO
311    }
312
313    fn is_zero(&self) -> bool {
314        self.0.ct_eq(&Self::ZERO.0).into()
315    }
316}
317
318impl<const LIMBS: usize> num_traits::One for Int<LIMBS> {
319    #[inline(always)]
320    fn one() -> Self {
321        Self::ONE
322    }
323
324    fn is_one(&self) -> bool {
325        self.0.ct_eq(&Self::ONE.0).into()
326    }
327}
328
329impl<const LIMBS: usize> fmt::Debug for Int<LIMBS> {
330    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
331        write!(f, "Int(0x{self:X})")
332    }
333}
334
335impl<const LIMBS: usize> fmt::Binary for Int<LIMBS> {
336    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
337        fmt::Binary::fmt(&self.0, f)
338    }
339}
340
341impl<const LIMBS: usize> fmt::Display for Int<LIMBS> {
342    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
343        fmt::UpperHex::fmt(self, f)
344    }
345}
346
347impl<const LIMBS: usize> fmt::LowerHex for Int<LIMBS> {
348    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
349        fmt::LowerHex::fmt(&self.0, f)
350    }
351}
352
353impl<const LIMBS: usize> fmt::UpperHex for Int<LIMBS> {
354    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
355        fmt::UpperHex::fmt(&self.0, f)
356    }
357}
358
359#[cfg(feature = "serde")]
360impl<'de, const LIMBS: usize> Deserialize<'de> for Int<LIMBS>
361where
362    Int<LIMBS>: Encoding,
363{
364    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
365    where
366        D: Deserializer<'de>,
367    {
368        let mut buffer = Self::ZERO.to_le_bytes();
369        serdect::array::deserialize_hex_or_bin(buffer.as_mut(), deserializer)?;
370        Ok(Self::from_le_bytes(buffer))
371    }
372}
373
374#[cfg(feature = "serde")]
375impl<const LIMBS: usize> Serialize for Int<LIMBS>
376where
377    Int<LIMBS>: Encoding,
378{
379    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
380    where
381        S: Serializer,
382    {
383        serdect::array::serialize_hex_lower_or_bin(&Encoding::to_le_bytes(self), serializer)
384    }
385}
386
387#[cfg(test)]
388#[allow(clippy::unwrap_used)]
389mod tests {
390    use crate::{I128, U128};
391
392    cpubits::cpubits! {
393        64 => {
394            #[test]
395            fn as_words() {
396                let n = I128::from_be_hex("AAAAAAAABBBBBBBBCCCCCCCCDDDDDDDD");
397                assert_eq!(n.as_words(), &[0xCCCCCCCCDDDDDDDD, 0xAAAAAAAABBBBBBBB]);
398            }
399
400            #[test]
401            fn as_words_mut() {
402                let mut n = I128::from_be_hex("AAAAAAAABBBBBBBBCCCCCCCCDDDDDDDD");
403                assert_eq!(n.as_mut_words(), &[0xCCCCCCCCDDDDDDDD, 0xAAAAAAAABBBBBBBB]);
404            }
405        }
406    }
407
408    #[cfg(feature = "alloc")]
409    #[test]
410    fn debug() {
411        let n = I128::from_be_hex("AAAAAAAABBBBBBBBCCCCCCCCDDDDDDDD");
412
413        assert_eq!(format!("{n:?}"), "Int(0xAAAAAAAABBBBBBBBCCCCCCCCDDDDDDDD)");
414    }
415
416    #[cfg(feature = "alloc")]
417    #[test]
418    fn display() {
419        let hex = "AAAAAAAABBBBBBBBCCCCCCCCDDDDDDDD";
420        let n = I128::from_be_hex(hex);
421
422        use alloc::string::ToString;
423        assert_eq!(hex, n.to_string());
424
425        let hex = "AAAAAAAABBBBBBBB0000000000000000";
426        let n = I128::from_be_hex(hex);
427        assert_eq!(hex, n.to_string());
428
429        let hex = "AAAAAAAABBBBBBBB00000000DDDDDDDD";
430        let n = I128::from_be_hex(hex);
431        assert_eq!(hex, n.to_string());
432
433        let hex = "AAAAAAAABBBBBBBB0CCCCCCCDDDDDDDD";
434        let n = I128::from_be_hex(hex);
435        assert_eq!(hex, n.to_string());
436    }
437
438    #[cfg(feature = "alloc")]
439    #[test]
440    fn fmt_lower_hex() {
441        let n = I128::from_be_hex("AAAAAAAABBBBBBBBCCCCCCCCDDDDDDDD");
442        assert_eq!(format!("{n:x}"), "aaaaaaaabbbbbbbbccccccccdddddddd");
443        assert_eq!(format!("{n:#x}"), "0xaaaaaaaabbbbbbbbccccccccdddddddd");
444    }
445
446    #[cfg(feature = "alloc")]
447    #[test]
448    fn fmt_upper_hex() {
449        let n = I128::from_be_hex("aaaaaaaabbbbbbbbccccccccdddddddd");
450        assert_eq!(format!("{n:X}"), "AAAAAAAABBBBBBBBCCCCCCCCDDDDDDDD");
451        assert_eq!(format!("{n:#X}"), "0xAAAAAAAABBBBBBBBCCCCCCCCDDDDDDDD");
452    }
453
454    #[cfg(feature = "alloc")]
455    #[test]
456    fn fmt_binary() {
457        let n = I128::from_be_hex("AAAAAAAABBBBBBBBCCCCCCCCDDDDDDDD");
458        assert_eq!(
459            format!("{n:b}"),
460            "10101010101010101010101010101010101110111011101110111011101110111100110011001100110011001100110011011101110111011101110111011101"
461        );
462        assert_eq!(
463            format!("{n:#b}"),
464            "0b10101010101010101010101010101010101110111011101110111011101110111100110011001100110011001100110011011101110111011101110111011101"
465        );
466    }
467
468    #[test]
469    fn is_minimal() {
470        let min = I128::from_be_hex("80000000000000000000000000000000");
471        assert!(min.is_min().to_bool());
472
473        let random = I128::from_be_hex("11113333555577779999BBBBDDDDFFFF");
474        assert!(!random.is_min().to_bool());
475    }
476
477    #[test]
478    fn is_maximal() {
479        let max = I128::from_be_hex("7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF");
480        assert!(max.is_max().to_bool());
481
482        let random = I128::from_be_hex("11113333555577779999BBBBDDDDFFFF");
483        assert!(!random.is_max().to_bool());
484    }
485
486    #[test]
487    fn as_uint() {
488        assert_eq!(*I128::MIN.as_uint(), U128::ONE << 127);
489        assert_eq!(*I128::MINUS_ONE.as_uint(), U128::MAX);
490        assert_eq!(*I128::ZERO.as_uint(), U128::ZERO);
491        assert_eq!(*I128::ONE.as_uint(), U128::ONE);
492        assert_eq!(*I128::MAX.as_uint(), U128::MAX >> 1);
493    }
494
495    #[test]
496    fn to_uint() {
497        assert!(bool::from(I128::MIN.try_into_uint().is_none()));
498        assert!(bool::from(I128::MINUS_ONE.try_into_uint().is_none()));
499        assert_eq!(I128::ZERO.try_into_uint().unwrap(), U128::ZERO);
500        assert_eq!(I128::ONE.try_into_uint().unwrap(), U128::ONE);
501        assert_eq!(I128::MAX.try_into_uint().unwrap(), U128::MAX >> 1);
502    }
503
504    #[test]
505    fn test_signed() {
506        crate::traits::tests::test_signed(I128::MIN, I128::MAX);
507    }
508}
crypto_bigint/int.rs

crypto_bigint/
int.rs
