1#![allow(clippy::needless_range_loop, clippy::many_single_char_names)]
4
5use core::fmt;
6
7#[cfg(feature = "serde")]
8use serdect::serde::{Deserialize, Deserializer, Serialize, Serializer};
9use subtle::{Choice, ConditionallySelectable, ConstantTimeEq};
10#[cfg(feature = "zeroize")]
11use zeroize::DefaultIsZeroes;
12
13#[cfg(feature = "extra-sizes")]
14pub use extra_sizes::*;
15
16pub(crate) use ref_type::UintRef;
17
18use crate::{
19 Bounded, ConstCtOption, ConstZero, Constants, Encoding, FixedInteger, Int, Integer, Limb,
20 NonZero, Odd, PrecomputeInverter, PrecomputeInverterWithAdjuster, Word,
21 modular::{MontyForm, SafeGcdInverter},
22};
23
24#[macro_use]
25mod macros;
26
27mod add;
28mod add_mod;
29mod bit_and;
30mod bit_not;
31mod bit_or;
32mod bit_xor;
33mod bits;
34mod cmp;
35mod concat;
36mod div;
37pub(crate) mod div_limb;
38pub(crate) mod encoding;
39mod from;
40mod gcd;
41mod invert_mod;
42pub(crate) mod mul;
43mod mul_mod;
44mod neg;
45mod neg_mod;
46mod resize;
47mod shl;
48mod shr;
49mod split;
50mod sqrt;
51mod sub;
52mod sub_mod;
53
54#[cfg(feature = "hybrid-array")]
55mod array;
56#[cfg(feature = "alloc")]
57pub(crate) mod boxed;
58#[cfg(feature = "rand_core")]
59mod rand;
60
61#[allow(clippy::derived_hash_with_manual_eq)]
80#[derive(Copy, Clone, Hash)]
81pub struct Uint<const LIMBS: usize> {
82 pub(crate) limbs: [Limb; LIMBS],
84}
85
86impl<const LIMBS: usize> Uint<LIMBS> {
87 pub const ZERO: Self = Self::from_u8(0);
89
90 pub const ONE: Self = Self::from_u8(1);
92
93 pub const MAX: Self = Self {
95 limbs: [Limb::MAX; LIMBS],
96 };
97
98 pub const BITS: u32 = LIMBS as u32 * Limb::BITS;
100
101 pub(crate) const LOG2_BITS: u32 = u32::BITS - Self::BITS.leading_zeros() - 1;
104
105 pub const BYTES: usize = LIMBS * Limb::BYTES;
107
108 pub const LIMBS: usize = LIMBS;
110
111 pub const fn new(limbs: [Limb; LIMBS]) -> Self {
113 Self { limbs }
114 }
115
116 #[inline]
119 pub const fn from_words(arr: [Word; LIMBS]) -> Self {
120 let mut limbs = [Limb::ZERO; LIMBS];
121 let mut i = 0;
122
123 while i < LIMBS {
124 limbs[i] = Limb(arr[i]);
125 i += 1;
126 }
127
128 Self { limbs }
129 }
130
131 #[inline]
134 pub const fn to_words(self) -> [Word; LIMBS] {
135 let mut arr = [0; LIMBS];
136 let mut i = 0;
137
138 while i < LIMBS {
139 arr[i] = self.limbs[i].0;
140 i += 1;
141 }
142
143 arr
144 }
145
146 pub const fn as_words(&self) -> &[Word; LIMBS] {
148 #[allow(unsafe_code)]
150 unsafe {
151 &*self.limbs.as_ptr().cast()
152 }
153 }
154
155 pub const fn as_mut_words(&mut self) -> &mut [Word; LIMBS] {
157 #[allow(unsafe_code)]
159 unsafe {
160 &mut *self.limbs.as_mut_ptr().cast()
161 }
162 }
163
164 #[deprecated(since = "0.7.0", note = "please use `as_mut_words` instead")]
166 pub const fn as_words_mut(&mut self) -> &mut [Word] {
167 self.as_mut_words()
168 }
169
170 pub const fn as_limbs(&self) -> &[Limb; LIMBS] {
172 &self.limbs
173 }
174
175 pub const fn as_mut_limbs(&mut self) -> &mut [Limb; LIMBS] {
177 &mut self.limbs
178 }
179
180 #[deprecated(since = "0.7.0", note = "please use `as_mut_limbs` instead")]
182 pub const fn as_limbs_mut(&mut self) -> &mut [Limb] {
183 self.as_mut_limbs()
184 }
185
186 pub const fn to_limbs(self) -> [Limb; LIMBS] {
188 self.limbs
189 }
190
191 pub(crate) const fn as_uint_ref(&self) -> &UintRef {
193 UintRef::new(&self.limbs)
194 }
195
196 pub(crate) const fn as_mut_uint_ref(&mut self) -> &mut UintRef {
198 UintRef::new_mut(&mut self.limbs)
199 }
200
201 pub const fn to_nz(self) -> ConstCtOption<NonZero<Self>> {
205 ConstCtOption::new(NonZero(self), self.is_nonzero())
206 }
207
208 pub const fn to_odd(self) -> ConstCtOption<Odd<Self>> {
212 ConstCtOption::new(Odd(self), self.is_odd())
213 }
214
215 pub const fn as_int(&self) -> Int<LIMBS> {
217 Int::from_bits(*self)
218 }
219}
220
221impl<const LIMBS: usize> AsRef<[Word; LIMBS]> for Uint<LIMBS> {
222 fn as_ref(&self) -> &[Word; LIMBS] {
223 self.as_words()
224 }
225}
226
227impl<const LIMBS: usize> AsMut<[Word; LIMBS]> for Uint<LIMBS> {
228 fn as_mut(&mut self) -> &mut [Word; LIMBS] {
229 self.as_mut_words()
230 }
231}
232
233impl<const LIMBS: usize> AsRef<[Limb]> for Uint<LIMBS> {
234 fn as_ref(&self) -> &[Limb] {
235 self.as_limbs()
236 }
237}
238
239impl<const LIMBS: usize> AsMut<[Limb]> for Uint<LIMBS> {
240 fn as_mut(&mut self) -> &mut [Limb] {
241 self.as_mut_limbs()
242 }
243}
244
245impl<const LIMBS: usize> AsRef<UintRef> for Uint<LIMBS> {
246 fn as_ref(&self) -> &UintRef {
247 self.as_uint_ref()
248 }
249}
250
251impl<const LIMBS: usize> AsMut<UintRef> for Uint<LIMBS> {
252 fn as_mut(&mut self) -> &mut UintRef {
253 self.as_mut_uint_ref()
254 }
255}
256
257impl<const LIMBS: usize> ConditionallySelectable for Uint<LIMBS> {
258 fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
259 let mut limbs = [Limb::ZERO; LIMBS];
260
261 for i in 0..LIMBS {
262 limbs[i] = Limb::conditional_select(&a.limbs[i], &b.limbs[i], choice);
263 }
264
265 Self { limbs }
266 }
267}
268
269impl<const LIMBS: usize> Bounded for Uint<LIMBS> {
270 const BITS: u32 = Self::BITS;
271 const BYTES: usize = Self::BYTES;
272}
273
274impl<const LIMBS: usize> Constants for Uint<LIMBS> {
275 const ONE: Self = Self::ONE;
276 const MAX: Self = Self::MAX;
277}
278
279impl<const LIMBS: usize> Default for Uint<LIMBS> {
280 fn default() -> Self {
281 Self::ZERO
282 }
283}
284
285impl<const LIMBS: usize> FixedInteger for Uint<LIMBS> {
286 const LIMBS: usize = LIMBS;
287}
288
289impl<const LIMBS: usize> Integer for Uint<LIMBS> {
290 type Monty = MontyForm<LIMBS>;
291
292 fn one() -> Self {
293 Self::ONE
294 }
295
296 fn from_limb_like(limb: Limb, _other: &Self) -> Self {
297 Self::from(limb)
298 }
299
300 fn nlimbs(&self) -> usize {
301 Self::LIMBS
302 }
303}
304
305impl<const LIMBS: usize> num_traits::Num for Uint<LIMBS> {
306 type FromStrRadixErr = crate::DecodeError;
307
308 fn from_str_radix(str: &str, radix: u32) -> Result<Self, Self::FromStrRadixErr> {
310 Self::from_str_radix_vartime(str, radix)
311 }
312}
313
314impl<const LIMBS: usize> ConstZero for Uint<LIMBS> {
315 const ZERO: Self = Self::ZERO;
316}
317
318impl<const LIMBS: usize> num_traits::Zero for Uint<LIMBS> {
319 fn zero() -> Self {
320 Self::ZERO
321 }
322
323 fn is_zero(&self) -> bool {
324 self.ct_eq(&Self::ZERO).into()
325 }
326}
327
328impl<const LIMBS: usize> num_traits::One for Uint<LIMBS> {
329 fn one() -> Self {
330 Self::ONE
331 }
332
333 fn is_one(&self) -> bool {
334 self.ct_eq(&Self::ONE).into()
335 }
336}
337
338impl<const LIMBS: usize> fmt::Debug for Uint<LIMBS> {
339 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
340 write!(f, "Uint(0x{:X})", self.as_uint_ref())
341 }
342}
343
344impl<const LIMBS: usize> fmt::Binary for Uint<LIMBS> {
345 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
346 fmt::Binary::fmt(self.as_uint_ref(), f)
347 }
348}
349
350impl<const LIMBS: usize> fmt::Display for Uint<LIMBS> {
351 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
352 fmt::UpperHex::fmt(self, f)
353 }
354}
355
356impl<const LIMBS: usize> fmt::LowerHex for Uint<LIMBS> {
357 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
358 fmt::LowerHex::fmt(self.as_uint_ref(), f)
359 }
360}
361
362impl<const LIMBS: usize> fmt::UpperHex for Uint<LIMBS> {
363 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
364 fmt::UpperHex::fmt(self.as_uint_ref(), f)
365 }
366}
367
368#[cfg(feature = "serde")]
369impl<'de, const LIMBS: usize> Deserialize<'de> for Uint<LIMBS>
370where
371 Uint<LIMBS>: Encoding,
372{
373 fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
374 where
375 D: Deserializer<'de>,
376 {
377 let mut buffer = Self::ZERO.to_le_bytes();
378 serdect::array::deserialize_hex_or_bin(buffer.as_mut(), deserializer)?;
379
380 Ok(Self::from_le_bytes(buffer))
381 }
382}
383
384#[cfg(feature = "serde")]
385impl<const LIMBS: usize> Serialize for Uint<LIMBS>
386where
387 Uint<LIMBS>: Encoding,
388{
389 fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
390 where
391 S: Serializer,
392 {
393 serdect::array::serialize_hex_lower_or_bin(&Encoding::to_le_bytes(self), serializer)
394 }
395}
396
397#[cfg(feature = "zeroize")]
398impl<const LIMBS: usize> DefaultIsZeroes for Uint<LIMBS> {}
399
400impl_uint_aliases! {
402 (U64, 64, "64-bit"),
403 (U128, 128, "128-bit"),
404 (U192, 192, "192-bit"),
405 (U256, 256, "256-bit"),
406 (U320, 320, "320-bit"),
407 (U384, 384, "384-bit"),
408 (U448, 448, "448-bit"),
409 (U512, 512, "512-bit"),
410 (U576, 576, "576-bit"),
411 (U640, 640, "640-bit"),
412 (U704, 704, "704-bit"),
413 (U768, 768, "768-bit"),
414 (U832, 832, "832-bit"),
415 (U896, 896, "896-bit"),
416 (U960, 960, "960-bit"),
417 (U1024, 1024, "1024-bit"),
418 (U1280, 1280, "1280-bit"),
419 (U1536, 1536, "1536-bit"),
420 (U1792, 1792, "1792-bit"),
421 (U2048, 2048, "2048-bit"),
422 (U3072, 3072, "3072-bit"),
423 (U3584, 3584, "3584-bit"),
424 (U4096, 4096, "4096-bit"),
425 (U4224, 4224, "4224-bit"),
426 (U4352, 4352, "4352-bit"),
427 (U6144, 6144, "6144-bit"),
428 (U8192, 8192, "8192-bit"),
429 (U16384, 16384, "16384-bit"),
430 (U32768, 32768, "32768-bit")
431}
432
433#[cfg(target_pointer_width = "32")]
434impl_uint_aliases! {
435 (U224, 224, "224-bit"), (U544, 544, "544-bit") }
438
439#[cfg(target_pointer_width = "32")]
440impl_uint_concat_split_even! {
441 U64,
442}
443
444impl_uint_concat_split_even! {
447 U128,
448 U256,
449 U384,
450 U512,
451 U640,
452 U768,
453 U896,
454 U1024,
455 U1280,
456 U1536,
457 U1792,
458 U2048,
459 U3072,
460 U3584,
461 U4096,
462 U4224,
463 U4352,
464 U6144,
465 U8192,
466 U16384,
467}
468
469impl_uint_concat_split_mixed! {
475 (U192, [1, 2]),
476 (U256, [1, 3]),
477 (U320, [1, 2, 3, 4]),
478 (U384, [1, 2, 4, 5]),
479 (U448, [1, 2, 3, 4, 5, 6]),
480 (U512, [1, 2, 3, 5, 6, 7]),
481 (U576, [1, 2, 3, 4, 5, 6, 7, 8]),
482 (U640, [1, 2, 3, 4, 6, 7, 8, 9]),
483 (U704, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]),
484 (U768, [1, 2, 3, 4, 5, 7, 8, 9, 10, 11]),
485 (U832, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]),
486 (U896, [1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13]),
487 (U960, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]),
488 (U1024, [1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15]),
489}
490
491#[cfg(feature = "extra-sizes")]
492mod extra_sizes;
493mod ref_type;
494
495#[cfg(test)]
496#[allow(clippy::unwrap_used)]
497mod tests {
498 #[cfg(feature = "alloc")]
499 use alloc::format;
500
501 use subtle::ConditionallySelectable;
502
503 #[cfg(feature = "serde")]
504 use crate::U64;
505 use crate::{Encoding, U128};
506
507 #[cfg(target_pointer_width = "64")]
508 #[test]
509 fn as_words() {
510 let n = U128::from_be_hex("AAAAAAAABBBBBBBBCCCCCCCCDDDDDDDD");
511 assert_eq!(n.as_words(), &[0xCCCCCCCCDDDDDDDD, 0xAAAAAAAABBBBBBBB]);
512 }
513
514 #[cfg(target_pointer_width = "64")]
515 #[test]
516 fn as_words_mut() {
517 let mut n = U128::from_be_hex("AAAAAAAABBBBBBBBCCCCCCCCDDDDDDDD");
518 assert_eq!(n.as_mut_words(), &[0xCCCCCCCCDDDDDDDD, 0xAAAAAAAABBBBBBBB]);
519 }
520
521 #[cfg(feature = "alloc")]
522 #[test]
523 fn debug() {
524 let n = U128::from_be_hex("AAAAAAAABBBBBBBBCCCCCCCCDDDDDDDD");
525
526 assert_eq!(
527 format!("{:?}", n),
528 "Uint(0xAAAAAAAABBBBBBBBCCCCCCCCDDDDDDDD)"
529 );
530 }
531
532 #[cfg(feature = "alloc")]
533 #[test]
534 fn display() {
535 let hex = "AAAAAAAABBBBBBBBCCCCCCCCDDDDDDDD";
536 let n = U128::from_be_hex(hex);
537
538 use alloc::string::ToString;
539 assert_eq!(hex, n.to_string());
540
541 let hex = "AAAAAAAABBBBBBBB0000000000000000";
542 let n = U128::from_be_hex(hex);
543 assert_eq!(hex, n.to_string());
544
545 let hex = "AAAAAAAABBBBBBBB00000000DDDDDDDD";
546 let n = U128::from_be_hex(hex);
547 assert_eq!(hex, n.to_string());
548
549 let hex = "AAAAAAAABBBBBBBB0CCCCCCCDDDDDDDD";
550 let n = U128::from_be_hex(hex);
551 assert_eq!(hex, n.to_string());
552 }
553
554 #[cfg(feature = "alloc")]
555 #[test]
556 fn fmt_lower_hex() {
557 let n = U128::from_be_hex("AAAAAAAABBBBBBBBCCCCCCCCDDDDDDDD");
558 assert_eq!(format!("{n:x}"), "aaaaaaaabbbbbbbbccccccccdddddddd");
559 assert_eq!(format!("{n:#x}"), "0xaaaaaaaabbbbbbbbccccccccdddddddd");
560 }
561
562 #[cfg(feature = "alloc")]
563 #[test]
564 fn fmt_lower_hex_from_trait() {
565 fn format_int<T: crate::Integer>(n: T) -> alloc::string::String {
566 format!("{n:x}")
567 }
568 let n = U128::from_be_hex("AAAAAAAABBBBBBBBCCCCCCCCDDDDDDDD");
569 assert_eq!(format_int(n), "aaaaaaaabbbbbbbbccccccccdddddddd");
570 }
571
572 #[cfg(feature = "alloc")]
573 #[test]
574 fn fmt_upper_hex() {
575 let n = U128::from_be_hex("aaaaaaaabbbbbbbbccccccccdddddddd");
576 assert_eq!(format!("{n:X}"), "AAAAAAAABBBBBBBBCCCCCCCCDDDDDDDD");
577 assert_eq!(format!("{n:#X}"), "0xAAAAAAAABBBBBBBBCCCCCCCCDDDDDDDD");
578 }
579
580 #[cfg(feature = "alloc")]
581 #[test]
582 fn fmt_upper_hex_from_trait() {
583 fn format_int<T: crate::Integer>(n: T) -> alloc::string::String {
584 format!("{n:X}")
585 }
586 let n = U128::from_be_hex("aaaaaaaabbbbbbbbccccccccdddddddd");
587 assert_eq!(format_int(n), "AAAAAAAABBBBBBBBCCCCCCCCDDDDDDDD");
588 }
589
590 #[cfg(feature = "alloc")]
591 #[test]
592 fn fmt_binary() {
593 let n = U128::from_be_hex("AAAAAAAABBBBBBBBCCCCCCCCDDDDDDDD");
594 assert_eq!(
595 format!("{n:b}"),
596 "10101010101010101010101010101010101110111011101110111011101110111100110011001100110011001100110011011101110111011101110111011101"
597 );
598 assert_eq!(
599 format!("{n:#b}"),
600 "0b10101010101010101010101010101010101110111011101110111011101110111100110011001100110011001100110011011101110111011101110111011101"
601 );
602 }
603
604 #[cfg(feature = "alloc")]
605 #[test]
606 fn fmt_binary_from_trait() {
607 fn format_int<T: crate::Integer>(n: T) -> alloc::string::String {
608 format!("{n:b}")
609 }
610 let n = U128::from_be_hex("aaaaaaaabbbbbbbbccccccccdddddddd");
611 assert_eq!(
612 format_int(n),
613 "10101010101010101010101010101010101110111011101110111011101110111100110011001100110011001100110011011101110111011101110111011101"
614 );
615 }
616
617 #[test]
618 fn from_bytes() {
619 let a = U128::from_be_hex("AAAAAAAABBBBBBBB0CCCCCCCDDDDDDDD");
620
621 let be_bytes = a.to_be_bytes();
622 let le_bytes = a.to_le_bytes();
623 for i in 0..16 {
624 assert_eq!(le_bytes[i], be_bytes[15 - i]);
625 }
626
627 let a_from_be = U128::from_be_bytes(be_bytes);
628 let a_from_le = U128::from_le_bytes(le_bytes);
629 assert_eq!(a_from_be, a_from_le);
630 assert_eq!(a_from_be, a);
631 }
632
633 #[test]
634 fn conditional_select() {
635 let a = U128::from_be_hex("00002222444466668888AAAACCCCEEEE");
636 let b = U128::from_be_hex("11113333555577779999BBBBDDDDFFFF");
637
638 let select_0 = U128::conditional_select(&a, &b, 0.into());
639 assert_eq!(a, select_0);
640
641 let select_1 = U128::conditional_select(&a, &b, 1.into());
642 assert_eq!(b, select_1);
643 }
644
645 #[cfg(feature = "serde")]
646 #[test]
647 fn serde() {
648 const TEST: U64 = U64::from_u64(0x0011223344556677);
649
650 let serialized = bincode::serialize(&TEST).unwrap();
651 let deserialized: U64 = bincode::deserialize(&serialized).unwrap();
652
653 assert_eq!(TEST, deserialized);
654 }
655
656 #[cfg(feature = "serde")]
657 #[test]
658 fn serde_owned() {
659 const TEST: U64 = U64::from_u64(0x0011223344556677);
660
661 let serialized = bincode::serialize(&TEST).unwrap();
662 let deserialized: U64 = bincode::deserialize_from(serialized.as_slice()).unwrap();
663
664 assert_eq!(TEST, deserialized);
665 }
666}