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
16use crate::{
17 modular::{MontyForm, SafeGcdInverter},
18 Bounded, ConstCtOption, ConstZero, Constants, Encoding, FixedInteger, Int, Integer, Limb,
19 NonZero, Odd, PrecomputeInverter, PrecomputeInverterWithAdjuster, Word,
20};
21
22#[macro_use]
23mod macros;
24
25mod add;
26mod add_mod;
27mod bit_and;
28mod bit_not;
29mod bit_or;
30mod bit_xor;
31mod bits;
32mod cmp;
33mod concat;
34mod div;
35pub(crate) mod div_limb;
36pub(crate) mod encoding;
37mod from;
38mod gcd;
39mod inv_mod;
40pub(crate) mod mul;
41mod mul_mod;
42mod neg;
43mod neg_mod;
44mod resize;
45mod shl;
46mod shr;
47mod split;
48mod sqrt;
49mod sub;
50mod sub_mod;
51
52#[cfg(feature = "hybrid-array")]
53mod array;
54#[cfg(feature = "alloc")]
55pub(crate) mod boxed;
56#[cfg(feature = "rand_core")]
57mod rand;
58
59#[allow(clippy::derived_hash_with_manual_eq)]
78#[derive(Copy, Clone, Hash)]
79pub struct Uint<const LIMBS: usize> {
80 pub(crate) limbs: [Limb; LIMBS],
82}
83
84impl<const LIMBS: usize> Uint<LIMBS> {
85 pub const ZERO: Self = Self::from_u8(0);
87
88 pub const ONE: Self = Self::from_u8(1);
90
91 pub const MAX: Self = Self {
93 limbs: [Limb::MAX; LIMBS],
94 };
95
96 pub const BITS: u32 = LIMBS as u32 * Limb::BITS;
98
99 pub(crate) const LOG2_BITS: u32 = u32::BITS - Self::BITS.leading_zeros() - 1;
102
103 pub const BYTES: usize = LIMBS * Limb::BYTES;
105
106 pub const LIMBS: usize = LIMBS;
108
109 pub const fn new(limbs: [Limb; LIMBS]) -> Self {
111 Self { limbs }
112 }
113
114 #[inline]
117 pub const fn from_words(arr: [Word; LIMBS]) -> Self {
118 let mut limbs = [Limb::ZERO; LIMBS];
119 let mut i = 0;
120
121 while i < LIMBS {
122 limbs[i] = Limb(arr[i]);
123 i += 1;
124 }
125
126 Self { limbs }
127 }
128
129 #[inline]
132 pub const fn to_words(self) -> [Word; LIMBS] {
133 let mut arr = [0; LIMBS];
134 let mut i = 0;
135
136 while i < LIMBS {
137 arr[i] = self.limbs[i].0;
138 i += 1;
139 }
140
141 arr
142 }
143
144 pub const fn as_words(&self) -> &[Word; LIMBS] {
146 #[allow(unsafe_code)]
148 unsafe {
149 &*self.limbs.as_ptr().cast()
150 }
151 }
152
153 pub fn as_words_mut(&mut self) -> &mut [Word; LIMBS] {
155 #[allow(unsafe_code)]
157 unsafe {
158 &mut *self.limbs.as_mut_ptr().cast()
159 }
160 }
161
162 pub const fn as_limbs(&self) -> &[Limb; LIMBS] {
164 &self.limbs
165 }
166
167 pub const fn as_limbs_mut(&mut self) -> &mut [Limb; LIMBS] {
169 &mut self.limbs
170 }
171
172 pub const fn to_limbs(self) -> [Limb; LIMBS] {
174 self.limbs
175 }
176
177 pub const fn to_nz(self) -> ConstCtOption<NonZero<Self>> {
181 ConstCtOption::new(NonZero(self), self.is_nonzero())
182 }
183
184 pub const fn to_odd(self) -> ConstCtOption<Odd<Self>> {
188 ConstCtOption::new(Odd(self), self.is_odd())
189 }
190
191 pub const fn as_int(&self) -> Int<LIMBS> {
193 Int::from_bits(*self)
194 }
195}
196
197impl<const LIMBS: usize> AsRef<[Word; LIMBS]> for Uint<LIMBS> {
198 fn as_ref(&self) -> &[Word; LIMBS] {
199 self.as_words()
200 }
201}
202
203impl<const LIMBS: usize> AsMut<[Word; LIMBS]> for Uint<LIMBS> {
204 fn as_mut(&mut self) -> &mut [Word; LIMBS] {
205 self.as_words_mut()
206 }
207}
208
209impl<const LIMBS: usize> AsRef<[Limb]> for Uint<LIMBS> {
210 fn as_ref(&self) -> &[Limb] {
211 self.as_limbs()
212 }
213}
214
215impl<const LIMBS: usize> AsMut<[Limb]> for Uint<LIMBS> {
216 fn as_mut(&mut self) -> &mut [Limb] {
217 self.as_limbs_mut()
218 }
219}
220
221impl<const LIMBS: usize> ConditionallySelectable for Uint<LIMBS> {
222 fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
223 let mut limbs = [Limb::ZERO; LIMBS];
224
225 for i in 0..LIMBS {
226 limbs[i] = Limb::conditional_select(&a.limbs[i], &b.limbs[i], choice);
227 }
228
229 Self { limbs }
230 }
231}
232
233impl<const LIMBS: usize> Bounded for Uint<LIMBS> {
234 const BITS: u32 = Self::BITS;
235 const BYTES: usize = Self::BYTES;
236}
237
238impl<const LIMBS: usize> Constants for Uint<LIMBS> {
239 const ONE: Self = Self::ONE;
240 const MAX: Self = Self::MAX;
241}
242
243impl<const LIMBS: usize> Default for Uint<LIMBS> {
244 fn default() -> Self {
245 Self::ZERO
246 }
247}
248
249impl<const LIMBS: usize> FixedInteger for Uint<LIMBS> {
250 const LIMBS: usize = LIMBS;
251}
252
253impl<const LIMBS: usize> Integer for Uint<LIMBS> {
254 type Monty = MontyForm<LIMBS>;
255
256 fn one() -> Self {
257 Self::ONE
258 }
259
260 fn from_limb_like(limb: Limb, _other: &Self) -> Self {
261 Self::from(limb)
262 }
263
264 fn nlimbs(&self) -> usize {
265 Self::LIMBS
266 }
267}
268
269impl<const LIMBS: usize> num_traits::Num for Uint<LIMBS> {
270 type FromStrRadixErr = crate::DecodeError;
271
272 fn from_str_radix(str: &str, radix: u32) -> Result<Self, Self::FromStrRadixErr> {
274 Self::from_str_radix_vartime(str, radix)
275 }
276}
277
278impl<const LIMBS: usize> ConstZero for Uint<LIMBS> {
279 const ZERO: Self = Self::ZERO;
280}
281
282impl<const LIMBS: usize> num_traits::Zero for Uint<LIMBS> {
283 fn zero() -> Self {
284 Self::ZERO
285 }
286
287 fn is_zero(&self) -> bool {
288 self.ct_eq(&Self::ZERO).into()
289 }
290}
291
292impl<const LIMBS: usize> num_traits::One for Uint<LIMBS> {
293 fn one() -> Self {
294 Self::ONE
295 }
296
297 fn is_one(&self) -> bool {
298 self.ct_eq(&Self::ONE).into()
299 }
300}
301
302impl<const LIMBS: usize> fmt::Debug for Uint<LIMBS> {
303 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
304 write!(f, "Uint(0x{self:X})")
305 }
306}
307
308impl<const LIMBS: usize> fmt::Binary for Uint<LIMBS> {
309 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
310 for limb in self.limbs.iter().rev() {
311 fmt::Binary::fmt(limb, f)?;
312 }
313 Ok(())
314 }
315}
316
317impl<const LIMBS: usize> fmt::Display for Uint<LIMBS> {
318 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
319 fmt::UpperHex::fmt(self, f)
320 }
321}
322
323impl<const LIMBS: usize> fmt::LowerHex for Uint<LIMBS> {
324 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
325 for limb in self.limbs.iter().rev() {
326 fmt::LowerHex::fmt(limb, f)?;
327 }
328 Ok(())
329 }
330}
331
332impl<const LIMBS: usize> fmt::UpperHex for Uint<LIMBS> {
333 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
334 for limb in self.limbs.iter().rev() {
335 fmt::UpperHex::fmt(limb, f)?;
336 }
337 Ok(())
338 }
339}
340
341#[cfg(feature = "serde")]
342impl<'de, const LIMBS: usize> Deserialize<'de> for Uint<LIMBS>
343where
344 Uint<LIMBS>: Encoding,
345{
346 fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
347 where
348 D: Deserializer<'de>,
349 {
350 let mut buffer = Self::ZERO.to_le_bytes();
351 serdect::array::deserialize_hex_or_bin(buffer.as_mut(), deserializer)?;
352
353 Ok(Self::from_le_bytes(buffer))
354 }
355}
356
357#[cfg(feature = "serde")]
358impl<const LIMBS: usize> Serialize for Uint<LIMBS>
359where
360 Uint<LIMBS>: Encoding,
361{
362 fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
363 where
364 S: Serializer,
365 {
366 serdect::array::serialize_hex_lower_or_bin(&Encoding::to_le_bytes(self), serializer)
367 }
368}
369
370#[cfg(feature = "zeroize")]
371impl<const LIMBS: usize> DefaultIsZeroes for Uint<LIMBS> {}
372
373impl_uint_aliases! {
375 (U64, 64, "64-bit"),
376 (U128, 128, "128-bit"),
377 (U192, 192, "192-bit"),
378 (U256, 256, "256-bit"),
379 (U320, 320, "320-bit"),
380 (U384, 384, "384-bit"),
381 (U448, 448, "448-bit"),
382 (U512, 512, "512-bit"),
383 (U576, 576, "576-bit"),
384 (U640, 640, "640-bit"),
385 (U704, 704, "704-bit"),
386 (U768, 768, "768-bit"),
387 (U832, 832, "832-bit"),
388 (U896, 896, "896-bit"),
389 (U960, 960, "960-bit"),
390 (U1024, 1024, "1024-bit"),
391 (U1280, 1280, "1280-bit"),
392 (U1536, 1536, "1536-bit"),
393 (U1792, 1792, "1792-bit"),
394 (U2048, 2048, "2048-bit"),
395 (U3072, 3072, "3072-bit"),
396 (U3584, 3584, "3584-bit"),
397 (U4096, 4096, "4096-bit"),
398 (U4224, 4224, "4224-bit"),
399 (U4352, 4352, "4352-bit"),
400 (U6144, 6144, "6144-bit"),
401 (U8192, 8192, "8192-bit"),
402 (U16384, 16384, "16384-bit"),
403 (U32768, 32768, "32768-bit")
404}
405
406#[cfg(target_pointer_width = "32")]
407impl_uint_aliases! {
408 (U224, 224, "224-bit"), (U544, 544, "544-bit") }
411
412#[cfg(target_pointer_width = "32")]
413impl_uint_concat_split_even! {
414 U64,
415}
416
417impl_uint_concat_split_even! {
420 U128,
421 U256,
422 U384,
423 U512,
424 U640,
425 U768,
426 U896,
427 U1024,
428 U1280,
429 U1536,
430 U1792,
431 U2048,
432 U3072,
433 U3584,
434 U4096,
435 U4224,
436 U4352,
437 U6144,
438 U8192,
439 U16384,
440}
441
442impl_uint_concat_split_mixed! {
448 (U192, [1, 2]),
449 (U256, [1, 3]),
450 (U320, [1, 2, 3, 4]),
451 (U384, [1, 2, 4, 5]),
452 (U448, [1, 2, 3, 4, 5, 6]),
453 (U512, [1, 2, 3, 5, 6, 7]),
454 (U576, [1, 2, 3, 4, 5, 6, 7, 8]),
455 (U640, [1, 2, 3, 4, 6, 7, 8, 9]),
456 (U704, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]),
457 (U768, [1, 2, 3, 4, 5, 7, 8, 9, 10, 11]),
458 (U832, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]),
459 (U896, [1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13]),
460 (U960, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]),
461 (U1024, [1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15]),
462}
463
464#[cfg(feature = "extra-sizes")]
465mod extra_sizes;
466
467#[cfg(test)]
468#[allow(clippy::unwrap_used)]
469mod tests {
470 #[cfg(feature = "alloc")]
471 use alloc::format;
472
473 use subtle::ConditionallySelectable;
474
475 #[cfg(feature = "serde")]
476 use crate::U64;
477 use crate::{Encoding, U128};
478
479 #[cfg(target_pointer_width = "64")]
480 #[test]
481 fn as_words() {
482 let n = U128::from_be_hex("AAAAAAAABBBBBBBBCCCCCCCCDDDDDDDD");
483 assert_eq!(n.as_words(), &[0xCCCCCCCCDDDDDDDD, 0xAAAAAAAABBBBBBBB]);
484 }
485
486 #[cfg(target_pointer_width = "64")]
487 #[test]
488 fn as_words_mut() {
489 let mut n = U128::from_be_hex("AAAAAAAABBBBBBBBCCCCCCCCDDDDDDDD");
490 assert_eq!(n.as_words_mut(), &[0xCCCCCCCCDDDDDDDD, 0xAAAAAAAABBBBBBBB]);
491 }
492
493 #[cfg(feature = "alloc")]
494 #[test]
495 fn debug() {
496 let n = U128::from_be_hex("AAAAAAAABBBBBBBBCCCCCCCCDDDDDDDD");
497
498 assert_eq!(
499 format!("{:?}", n),
500 "Uint(0xAAAAAAAABBBBBBBBCCCCCCCCDDDDDDDD)"
501 );
502 }
503
504 #[cfg(feature = "alloc")]
505 #[test]
506 fn display() {
507 let hex = "AAAAAAAABBBBBBBBCCCCCCCCDDDDDDDD";
508 let n = U128::from_be_hex(hex);
509
510 use alloc::string::ToString;
511 assert_eq!(hex, n.to_string());
512
513 let hex = "AAAAAAAABBBBBBBB0000000000000000";
514 let n = U128::from_be_hex(hex);
515 assert_eq!(hex, n.to_string());
516
517 let hex = "AAAAAAAABBBBBBBB00000000DDDDDDDD";
518 let n = U128::from_be_hex(hex);
519 assert_eq!(hex, n.to_string());
520
521 let hex = "AAAAAAAABBBBBBBB0CCCCCCCDDDDDDDD";
522 let n = U128::from_be_hex(hex);
523 assert_eq!(hex, n.to_string());
524 }
525
526 #[test]
527 fn from_bytes() {
528 let a = U128::from_be_hex("AAAAAAAABBBBBBBB0CCCCCCCDDDDDDDD");
529
530 let be_bytes = a.to_be_bytes();
531 let le_bytes = a.to_le_bytes();
532 for i in 0..16 {
533 assert_eq!(le_bytes[i], be_bytes[15 - i]);
534 }
535
536 let a_from_be = U128::from_be_bytes(be_bytes);
537 let a_from_le = U128::from_le_bytes(le_bytes);
538 assert_eq!(a_from_be, a_from_le);
539 assert_eq!(a_from_be, a);
540 }
541
542 #[test]
543 fn conditional_select() {
544 let a = U128::from_be_hex("00002222444466668888AAAACCCCEEEE");
545 let b = U128::from_be_hex("11113333555577779999BBBBDDDDFFFF");
546
547 let select_0 = U128::conditional_select(&a, &b, 0.into());
548 assert_eq!(a, select_0);
549
550 let select_1 = U128::conditional_select(&a, &b, 1.into());
551 assert_eq!(b, select_1);
552 }
553
554 #[cfg(feature = "serde")]
555 #[test]
556 fn serde() {
557 const TEST: U64 = U64::from_u64(0x0011223344556677);
558
559 let serialized = bincode::serialize(&TEST).unwrap();
560 let deserialized: U64 = bincode::deserialize(&serialized).unwrap();
561
562 assert_eq!(TEST, deserialized);
563 }
564
565 #[cfg(feature = "serde")]
566 #[test]
567 fn serde_owned() {
568 const TEST: U64 = U64::from_u64(0x0011223344556677);
569
570 let serialized = bincode::serialize(&TEST).unwrap();
571 let deserialized: U64 = bincode::deserialize_from(serialized.as_slice()).unwrap();
572
573 assert_eq!(TEST, deserialized);
574 }
575}