substrate_typenum/
uint.rs

1//! Type-level unsigned integers.
2//!
3//!
4//! **Type operators** implemented:
5//!
6//! From `::core::ops`: `BitAnd`, `BitOr`, `BitXor`, `Shl`, `Shr`, `Add`, `Sub`,
7//!                 `Mul`, `Div`, and `Rem`.
8//! From `typenum`: `Same`, `Cmp`, and `Pow`.
9//!
10//! Rather than directly using the structs defined in this module, it is recommended that
11//! you import and use the relevant aliases from the [consts](../consts/index.html) module.
12//!
13//! # Example
14//! ```rust
15//! use std::ops::{Add, BitAnd, BitOr, BitXor, Div, Mul, Rem, Shl, Shr, Sub};
16//! use typenum::{Unsigned, U1, U2, U3, U4};
17//!
18//! assert_eq!(<U3 as BitAnd<U2>>::Output::to_u32(), 2);
19//! assert_eq!(<U3 as BitOr<U4>>::Output::to_u32(), 7);
20//! assert_eq!(<U3 as BitXor<U2>>::Output::to_u32(), 1);
21//! assert_eq!(<U3 as Shl<U1>>::Output::to_u32(), 6);
22//! assert_eq!(<U3 as Shr<U1>>::Output::to_u32(), 1);
23//! assert_eq!(<U3 as Add<U2>>::Output::to_u32(), 5);
24//! assert_eq!(<U3 as Sub<U2>>::Output::to_u32(), 1);
25//! assert_eq!(<U3 as Mul<U2>>::Output::to_u32(), 6);
26//! assert_eq!(<U3 as Div<U2>>::Output::to_u32(), 1);
27//! assert_eq!(<U3 as Rem<U2>>::Output::to_u32(), 1);
28//! ```
29
30use crate::{
31    bit::{Bit, B0, B1},
32    consts::{U0, U1},
33    private::{
34        BitDiff, BitDiffOut, Internal, InternalMarker, PrivateAnd, PrivateAndOut, PrivateCmp,
35        PrivateCmpOut, PrivateLogarithm2, PrivatePow, PrivatePowOut, PrivateSquareRoot, PrivateSub,
36        PrivateSubOut, PrivateXor, PrivateXorOut, Trim, TrimOut,
37    },
38    Add1, Cmp, Double, Equal, Gcd, Gcf, GrEq, Greater, IsGreaterOrEqual, Len, Length, Less, Log2,
39    Logarithm2, Maximum, Minimum, NonZero, Or, Ord, Pow, Prod, Shleft, Shright, Sqrt, Square,
40    SquareRoot, Sub1, Sum, ToInt, Zero,
41};
42use core::ops::{Add, BitAnd, BitOr, BitXor, Mul, Shl, Shr, Sub};
43#[cfg(feature = "derive_scale")]
44use parity_scale_codec::{Decode, DecodeWithMemTracking, Encode, MaxEncodedLen};
45
46pub use crate::marker_traits::{PowerOfTwo, Unsigned};
47
48/// The terminating type for `UInt`; it always comes after the most significant
49/// bit. `UTerm` by itself represents zero, which is aliased to `U0`.
50#[cfg_attr(
51    feature = "derive_scale",
52    derive(scale_info::TypeInfo, Decode, DecodeWithMemTracking, Encode, MaxEncodedLen)
53)]
54#[derive(Eq, PartialEq, Ord, PartialOrd, Clone, Copy, Hash, Debug, Default)]
55pub struct UTerm;
56
57impl UTerm {
58    /// Instantiates a singleton representing this unsigned integer.
59    #[inline]
60    pub fn new() -> UTerm {
61        UTerm
62    }
63}
64
65impl Unsigned for UTerm {
66    const U8: u8 = 0;
67    const U16: u16 = 0;
68    const U32: u32 = 0;
69    const U64: u64 = 0;
70    #[cfg(feature = "i128")]
71    const U128: u128 = 0;
72    const USIZE: usize = 0;
73
74    const I8: i8 = 0;
75    const I16: i16 = 0;
76    const I32: i32 = 0;
77    const I64: i64 = 0;
78    #[cfg(feature = "i128")]
79    const I128: i128 = 0;
80    const ISIZE: isize = 0;
81
82    #[inline]
83    fn to_u8() -> u8 {
84        0
85    }
86    #[inline]
87    fn to_u16() -> u16 {
88        0
89    }
90    #[inline]
91    fn to_u32() -> u32 {
92        0
93    }
94    #[inline]
95    fn to_u64() -> u64 {
96        0
97    }
98    #[cfg(feature = "i128")]
99    #[inline]
100    fn to_u128() -> u128 {
101        0
102    }
103    #[inline]
104    fn to_usize() -> usize {
105        0
106    }
107
108    #[inline]
109    fn to_i8() -> i8 {
110        0
111    }
112    #[inline]
113    fn to_i16() -> i16 {
114        0
115    }
116    #[inline]
117    fn to_i32() -> i32 {
118        0
119    }
120    #[inline]
121    fn to_i64() -> i64 {
122        0
123    }
124    #[cfg(feature = "i128")]
125    #[inline]
126    fn to_i128() -> i128 {
127        0
128    }
129    #[inline]
130    fn to_isize() -> isize {
131        0
132    }
133}
134
135/// `UInt` is defined recursively, where `B` is the least significant bit and `U` is the rest
136/// of the number. Conceptually, `U` should be bound by the trait `Unsigned` and `B` should
137/// be bound by the trait `Bit`, but enforcing these bounds causes linear instead of
138/// logrithmic scaling in some places, so they are left off for now. They may be enforced in
139/// future.
140///
141/// In order to keep numbers unique, leading zeros are not allowed, so `UInt<UTerm, B0>` is
142/// forbidden.
143///
144/// # Example
145/// ```rust
146/// use typenum::{UInt, UTerm, B0, B1};
147///
148/// # #[allow(dead_code)]
149/// type U6 = UInt<UInt<UInt<UTerm, B1>, B1>, B0>;
150/// ```
151#[cfg_attr(
152    feature = "derive_scale",
153    derive(scale_info::TypeInfo, Decode, DecodeWithMemTracking, Encode, MaxEncodedLen)
154)]
155#[derive(Eq, PartialEq, Ord, PartialOrd, Clone, Copy, Hash, Debug, Default)]
156pub struct UInt<U, B> {
157    /// The more significant bits of `Self`.
158    pub(crate) msb: U,
159    /// The least significant bit of `Self`.
160    pub(crate) lsb: B,
161}
162
163impl<U: Unsigned, B: Bit> UInt<U, B> {
164    /// Instantiates a singleton representing this unsigned integer.
165    #[inline]
166    pub fn new() -> UInt<U, B> {
167        UInt::default()
168    }
169}
170
171impl<U: Unsigned, B: Bit> Unsigned for UInt<U, B> {
172    const U8: u8 = B::U8 | U::U8 << 1;
173    const U16: u16 = B::U8 as u16 | U::U16 << 1;
174    const U32: u32 = B::U8 as u32 | U::U32 << 1;
175    const U64: u64 = B::U8 as u64 | U::U64 << 1;
176    #[cfg(feature = "i128")]
177    const U128: u128 = B::U8 as u128 | U::U128 << 1;
178    const USIZE: usize = B::U8 as usize | U::USIZE << 1;
179
180    const I8: i8 = B::U8 as i8 | U::I8 << 1;
181    const I16: i16 = B::U8 as i16 | U::I16 << 1;
182    const I32: i32 = B::U8 as i32 | U::I32 << 1;
183    const I64: i64 = B::U8 as i64 | U::I64 << 1;
184    #[cfg(feature = "i128")]
185    const I128: i128 = B::U8 as i128 | U::I128 << 1;
186    const ISIZE: isize = B::U8 as isize | U::ISIZE << 1;
187
188    #[inline]
189    fn to_u8() -> u8 {
190        B::to_u8() | U::to_u8() << 1
191    }
192    #[inline]
193    fn to_u16() -> u16 {
194        u16::from(B::to_u8()) | U::to_u16() << 1
195    }
196    #[inline]
197    fn to_u32() -> u32 {
198        u32::from(B::to_u8()) | U::to_u32() << 1
199    }
200    #[inline]
201    fn to_u64() -> u64 {
202        u64::from(B::to_u8()) | U::to_u64() << 1
203    }
204    #[cfg(feature = "i128")]
205    #[inline]
206    fn to_u128() -> u128 {
207        u128::from(B::to_u8()) | U::to_u128() << 1
208    }
209    #[inline]
210    fn to_usize() -> usize {
211        usize::from(B::to_u8()) | U::to_usize() << 1
212    }
213
214    #[inline]
215    fn to_i8() -> i8 {
216        B::to_u8() as i8 | U::to_i8() << 1
217    }
218    #[inline]
219    fn to_i16() -> i16 {
220        i16::from(B::to_u8()) | U::to_i16() << 1
221    }
222    #[inline]
223    fn to_i32() -> i32 {
224        i32::from(B::to_u8()) | U::to_i32() << 1
225    }
226    #[inline]
227    fn to_i64() -> i64 {
228        i64::from(B::to_u8()) | U::to_i64() << 1
229    }
230    #[cfg(feature = "i128")]
231    #[inline]
232    fn to_i128() -> i128 {
233        i128::from(B::to_u8()) | U::to_i128() << 1
234    }
235    #[inline]
236    fn to_isize() -> isize {
237        B::to_u8() as isize | U::to_isize() << 1
238    }
239}
240
241impl<U: Unsigned, B: Bit> NonZero for UInt<U, B> {}
242impl Zero for UTerm {}
243
244impl PowerOfTwo for UInt<UTerm, B1> {}
245impl<U: Unsigned + PowerOfTwo> PowerOfTwo for UInt<U, B0> {}
246
247// ---------------------------------------------------------------------------------------
248// Getting length of unsigned integers, which is defined as the number of bits before `UTerm`
249
250/// Length of `UTerm` by itself is 0
251impl Len for UTerm {
252    type Output = U0;
253    #[inline]
254    fn len(&self) -> Self::Output {
255        UTerm
256    }
257}
258
259/// Length of a bit is 1
260impl<U: Unsigned, B: Bit> Len for UInt<U, B>
261where
262    U: Len,
263    Length<U>: Add<B1>,
264    Add1<Length<U>>: Unsigned,
265{
266    type Output = Add1<Length<U>>;
267    #[inline]
268    fn len(&self) -> Self::Output {
269        self.msb.len() + B1
270    }
271}
272
273// ---------------------------------------------------------------------------------------
274// Adding bits to unsigned integers
275
276/// `UTerm + B0 = UTerm`
277impl Add<B0> for UTerm {
278    type Output = UTerm;
279    #[inline]
280    fn add(self, _: B0) -> Self::Output {
281        UTerm
282    }
283}
284
285/// `U + B0 = U`
286impl<U: Unsigned, B: Bit> Add<B0> for UInt<U, B> {
287    type Output = UInt<U, B>;
288    #[inline]
289    fn add(self, _: B0) -> Self::Output {
290        UInt::new()
291    }
292}
293
294/// `UTerm + B1 = UInt<UTerm, B1>`
295impl Add<B1> for UTerm {
296    type Output = UInt<UTerm, B1>;
297    #[inline]
298    fn add(self, _: B1) -> Self::Output {
299        UInt::new()
300    }
301}
302
303/// `UInt<U, B0> + B1 = UInt<U + B1>`
304impl<U: Unsigned> Add<B1> for UInt<U, B0> {
305    type Output = UInt<U, B1>;
306    #[inline]
307    fn add(self, _: B1) -> Self::Output {
308        UInt::new()
309    }
310}
311
312/// `UInt<U, B1> + B1 = UInt<U + B1, B0>`
313impl<U: Unsigned> Add<B1> for UInt<U, B1>
314where
315    U: Add<B1>,
316    Add1<U>: Unsigned,
317{
318    type Output = UInt<Add1<U>, B0>;
319    #[inline]
320    fn add(self, _: B1) -> Self::Output {
321        UInt::new()
322    }
323}
324
325// ---------------------------------------------------------------------------------------
326// Adding unsigned integers
327
328/// `UTerm + U = U`
329impl<U: Unsigned> Add<U> for UTerm {
330    type Output = U;
331    #[inline]
332    fn add(self, rhs: U) -> Self::Output {
333        rhs
334    }
335}
336
337/// `UInt<U, B> + UTerm = UInt<U, B>`
338impl<U: Unsigned, B: Bit> Add<UTerm> for UInt<U, B> {
339    type Output = UInt<U, B>;
340    #[inline]
341    fn add(self, _: UTerm) -> Self::Output {
342        UInt::new()
343    }
344}
345
346/// `UInt<Ul, B0> + UInt<Ur, B0> = UInt<Ul + Ur, B0>`
347impl<Ul: Unsigned, Ur: Unsigned> Add<UInt<Ur, B0>> for UInt<Ul, B0>
348where
349    Ul: Add<Ur>,
350{
351    type Output = UInt<Sum<Ul, Ur>, B0>;
352    #[inline]
353    fn add(self, rhs: UInt<Ur, B0>) -> Self::Output {
354        UInt {
355            msb: self.msb + rhs.msb,
356            lsb: B0,
357        }
358    }
359}
360
361/// `UInt<Ul, B0> + UInt<Ur, B1> = UInt<Ul + Ur, B1>`
362impl<Ul: Unsigned, Ur: Unsigned> Add<UInt<Ur, B1>> for UInt<Ul, B0>
363where
364    Ul: Add<Ur>,
365{
366    type Output = UInt<Sum<Ul, Ur>, B1>;
367    #[inline]
368    fn add(self, rhs: UInt<Ur, B1>) -> Self::Output {
369        UInt {
370            msb: self.msb + rhs.msb,
371            lsb: B1,
372        }
373    }
374}
375
376/// `UInt<Ul, B1> + UInt<Ur, B0> = UInt<Ul + Ur, B1>`
377impl<Ul: Unsigned, Ur: Unsigned> Add<UInt<Ur, B0>> for UInt<Ul, B1>
378where
379    Ul: Add<Ur>,
380{
381    type Output = UInt<Sum<Ul, Ur>, B1>;
382    #[inline]
383    fn add(self, rhs: UInt<Ur, B0>) -> Self::Output {
384        UInt {
385            msb: self.msb + rhs.msb,
386            lsb: B1,
387        }
388    }
389}
390
391/// `UInt<Ul, B1> + UInt<Ur, B1> = UInt<(Ul + Ur) + B1, B0>`
392impl<Ul: Unsigned, Ur: Unsigned> Add<UInt<Ur, B1>> for UInt<Ul, B1>
393where
394    Ul: Add<Ur>,
395    Sum<Ul, Ur>: Add<B1>,
396{
397    type Output = UInt<Add1<Sum<Ul, Ur>>, B0>;
398    #[inline]
399    fn add(self, rhs: UInt<Ur, B1>) -> Self::Output {
400        UInt {
401            msb: self.msb + rhs.msb + B1,
402            lsb: B0,
403        }
404    }
405}
406
407// ---------------------------------------------------------------------------------------
408// Subtracting bits from unsigned integers
409
410/// `UTerm - B0 = Term`
411impl Sub<B0> for UTerm {
412    type Output = UTerm;
413    #[inline]
414    fn sub(self, _: B0) -> Self::Output {
415        UTerm
416    }
417}
418
419/// `UInt - B0 = UInt`
420impl<U: Unsigned, B: Bit> Sub<B0> for UInt<U, B> {
421    type Output = UInt<U, B>;
422    #[inline]
423    fn sub(self, _: B0) -> Self::Output {
424        UInt::new()
425    }
426}
427
428/// `UInt<U, B1> - B1 = UInt<U, B0>`
429impl<U: Unsigned, B: Bit> Sub<B1> for UInt<UInt<U, B>, B1> {
430    type Output = UInt<UInt<U, B>, B0>;
431    #[inline]
432    fn sub(self, _: B1) -> Self::Output {
433        UInt::new()
434    }
435}
436
437/// `UInt<UTerm, B1> - B1 = UTerm`
438impl Sub<B1> for UInt<UTerm, B1> {
439    type Output = UTerm;
440    #[inline]
441    fn sub(self, _: B1) -> Self::Output {
442        UTerm
443    }
444}
445
446/// `UInt<U, B0> - B1 = UInt<U - B1, B1>`
447impl<U: Unsigned> Sub<B1> for UInt<U, B0>
448where
449    U: Sub<B1>,
450    Sub1<U>: Unsigned,
451{
452    type Output = UInt<Sub1<U>, B1>;
453    #[inline]
454    fn sub(self, _: B1) -> Self::Output {
455        UInt::new()
456    }
457}
458
459// ---------------------------------------------------------------------------------------
460// Subtracting unsigned integers
461
462/// `UTerm - UTerm = UTerm`
463impl Sub<UTerm> for UTerm {
464    type Output = UTerm;
465    #[inline]
466    fn sub(self, _: UTerm) -> Self::Output {
467        UTerm
468    }
469}
470
471/// Subtracting unsigned integers. We just do our `PrivateSub` and then `Trim` the output.
472impl<Ul: Unsigned, Bl: Bit, Ur: Unsigned> Sub<Ur> for UInt<Ul, Bl>
473where
474    UInt<Ul, Bl>: PrivateSub<Ur>,
475    PrivateSubOut<UInt<Ul, Bl>, Ur>: Trim,
476{
477    type Output = TrimOut<PrivateSubOut<UInt<Ul, Bl>, Ur>>;
478    #[inline]
479    fn sub(self, rhs: Ur) -> Self::Output {
480        self.private_sub(rhs).trim()
481    }
482}
483
484/// `U - UTerm = U`
485impl<U: Unsigned> PrivateSub<UTerm> for U {
486    type Output = U;
487
488    #[inline]
489    fn private_sub(self, _: UTerm) -> Self::Output {
490        self
491    }
492}
493
494/// `UInt<Ul, B0> - UInt<Ur, B0> = UInt<Ul - Ur, B0>`
495impl<Ul: Unsigned, Ur: Unsigned> PrivateSub<UInt<Ur, B0>> for UInt<Ul, B0>
496where
497    Ul: PrivateSub<Ur>,
498{
499    type Output = UInt<PrivateSubOut<Ul, Ur>, B0>;
500
501    #[inline]
502    fn private_sub(self, rhs: UInt<Ur, B0>) -> Self::Output {
503        UInt {
504            msb: self.msb.private_sub(rhs.msb),
505            lsb: B0,
506        }
507    }
508}
509
510/// `UInt<Ul, B0> - UInt<Ur, B1> = UInt<(Ul - Ur) - B1, B1>`
511impl<Ul: Unsigned, Ur: Unsigned> PrivateSub<UInt<Ur, B1>> for UInt<Ul, B0>
512where
513    Ul: PrivateSub<Ur>,
514    PrivateSubOut<Ul, Ur>: Sub<B1>,
515{
516    type Output = UInt<Sub1<PrivateSubOut<Ul, Ur>>, B1>;
517
518    #[inline]
519    fn private_sub(self, rhs: UInt<Ur, B1>) -> Self::Output {
520        UInt {
521            msb: self.msb.private_sub(rhs.msb) - B1,
522            lsb: B1,
523        }
524    }
525}
526
527/// `UInt<Ul, B1> - UInt<Ur, B0> = UInt<Ul - Ur, B1>`
528impl<Ul: Unsigned, Ur: Unsigned> PrivateSub<UInt<Ur, B0>> for UInt<Ul, B1>
529where
530    Ul: PrivateSub<Ur>,
531{
532    type Output = UInt<PrivateSubOut<Ul, Ur>, B1>;
533
534    #[inline]
535    fn private_sub(self, rhs: UInt<Ur, B0>) -> Self::Output {
536        UInt {
537            msb: self.msb.private_sub(rhs.msb),
538            lsb: B1,
539        }
540    }
541}
542
543/// `UInt<Ul, B1> - UInt<Ur, B1> = UInt<Ul - Ur, B0>`
544impl<Ul: Unsigned, Ur: Unsigned> PrivateSub<UInt<Ur, B1>> for UInt<Ul, B1>
545where
546    Ul: PrivateSub<Ur>,
547{
548    type Output = UInt<PrivateSubOut<Ul, Ur>, B0>;
549
550    #[inline]
551    fn private_sub(self, rhs: UInt<Ur, B1>) -> Self::Output {
552        UInt {
553            msb: self.msb.private_sub(rhs.msb),
554            lsb: B0,
555        }
556    }
557}
558
559// ---------------------------------------------------------------------------------------
560// And unsigned integers
561
562/// 0 & X = 0
563impl<Ur: Unsigned> BitAnd<Ur> for UTerm {
564    type Output = UTerm;
565    #[inline]
566    fn bitand(self, _: Ur) -> Self::Output {
567        UTerm
568    }
569}
570
571/// Anding unsigned integers.
572/// We use our `PrivateAnd` operator and then `Trim` the output.
573impl<Ul: Unsigned, Bl: Bit, Ur: Unsigned> BitAnd<Ur> for UInt<Ul, Bl>
574where
575    UInt<Ul, Bl>: PrivateAnd<Ur>,
576    PrivateAndOut<UInt<Ul, Bl>, Ur>: Trim,
577{
578    type Output = TrimOut<PrivateAndOut<UInt<Ul, Bl>, Ur>>;
579    #[inline]
580    fn bitand(self, rhs: Ur) -> Self::Output {
581        self.private_and(rhs).trim()
582    }
583}
584
585/// `UTerm & X = UTerm`
586impl<U: Unsigned> PrivateAnd<U> for UTerm {
587    type Output = UTerm;
588
589    #[inline]
590    fn private_and(self, _: U) -> Self::Output {
591        UTerm
592    }
593}
594
595/// `X & UTerm = UTerm`
596impl<B: Bit, U: Unsigned> PrivateAnd<UTerm> for UInt<U, B> {
597    type Output = UTerm;
598
599    #[inline]
600    fn private_and(self, _: UTerm) -> Self::Output {
601        UTerm
602    }
603}
604
605/// `UInt<Ul, B0> & UInt<Ur, B0> = UInt<Ul & Ur, B0>`
606impl<Ul: Unsigned, Ur: Unsigned> PrivateAnd<UInt<Ur, B0>> for UInt<Ul, B0>
607where
608    Ul: PrivateAnd<Ur>,
609{
610    type Output = UInt<PrivateAndOut<Ul, Ur>, B0>;
611
612    #[inline]
613    fn private_and(self, rhs: UInt<Ur, B0>) -> Self::Output {
614        UInt {
615            msb: self.msb.private_and(rhs.msb),
616            lsb: B0,
617        }
618    }
619}
620
621/// `UInt<Ul, B0> & UInt<Ur, B1> = UInt<Ul & Ur, B0>`
622impl<Ul: Unsigned, Ur: Unsigned> PrivateAnd<UInt<Ur, B1>> for UInt<Ul, B0>
623where
624    Ul: PrivateAnd<Ur>,
625{
626    type Output = UInt<PrivateAndOut<Ul, Ur>, B0>;
627
628    #[inline]
629    fn private_and(self, rhs: UInt<Ur, B1>) -> Self::Output {
630        UInt {
631            msb: self.msb.private_and(rhs.msb),
632            lsb: B0,
633        }
634    }
635}
636
637/// `UInt<Ul, B1> & UInt<Ur, B0> = UInt<Ul & Ur, B0>`
638impl<Ul: Unsigned, Ur: Unsigned> PrivateAnd<UInt<Ur, B0>> for UInt<Ul, B1>
639where
640    Ul: PrivateAnd<Ur>,
641{
642    type Output = UInt<PrivateAndOut<Ul, Ur>, B0>;
643
644    #[inline]
645    fn private_and(self, rhs: UInt<Ur, B0>) -> Self::Output {
646        UInt {
647            msb: self.msb.private_and(rhs.msb),
648            lsb: B0,
649        }
650    }
651}
652
653/// `UInt<Ul, B1> & UInt<Ur, B1> = UInt<Ul & Ur, B1>`
654impl<Ul: Unsigned, Ur: Unsigned> PrivateAnd<UInt<Ur, B1>> for UInt<Ul, B1>
655where
656    Ul: PrivateAnd<Ur>,
657{
658    type Output = UInt<PrivateAndOut<Ul, Ur>, B1>;
659
660    #[inline]
661    fn private_and(self, rhs: UInt<Ur, B1>) -> Self::Output {
662        UInt {
663            msb: self.msb.private_and(rhs.msb),
664            lsb: B1,
665        }
666    }
667}
668
669// ---------------------------------------------------------------------------------------
670// Or unsigned integers
671
672/// `UTerm | X = X`
673impl<U: Unsigned> BitOr<U> for UTerm {
674    type Output = U;
675    #[inline]
676    fn bitor(self, rhs: U) -> Self::Output {
677        rhs
678    }
679}
680
681///  `X | UTerm = X`
682impl<B: Bit, U: Unsigned> BitOr<UTerm> for UInt<U, B> {
683    type Output = Self;
684    #[inline]
685    fn bitor(self, _: UTerm) -> Self::Output {
686        UInt::new()
687    }
688}
689
690/// `UInt<Ul, B0> | UInt<Ur, B0> = UInt<Ul | Ur, B0>`
691impl<Ul: Unsigned, Ur: Unsigned> BitOr<UInt<Ur, B0>> for UInt<Ul, B0>
692where
693    Ul: BitOr<Ur>,
694{
695    type Output = UInt<<Ul as BitOr<Ur>>::Output, B0>;
696    #[inline]
697    fn bitor(self, rhs: UInt<Ur, B0>) -> Self::Output {
698        UInt {
699            msb: self.msb.bitor(rhs.msb),
700            lsb: B0,
701        }
702    }
703}
704
705/// `UInt<Ul, B0> | UInt<Ur, B1> = UInt<Ul | Ur, B1>`
706impl<Ul: Unsigned, Ur: Unsigned> BitOr<UInt<Ur, B1>> for UInt<Ul, B0>
707where
708    Ul: BitOr<Ur>,
709{
710    type Output = UInt<Or<Ul, Ur>, B1>;
711    #[inline]
712    fn bitor(self, rhs: UInt<Ur, B1>) -> Self::Output {
713        UInt {
714            msb: self.msb.bitor(rhs.msb),
715            lsb: self.lsb.bitor(rhs.lsb),
716        }
717    }
718}
719
720/// `UInt<Ul, B1> | UInt<Ur, B0> = UInt<Ul | Ur, B1>`
721impl<Ul: Unsigned, Ur: Unsigned> BitOr<UInt<Ur, B0>> for UInt<Ul, B1>
722where
723    Ul: BitOr<Ur>,
724{
725    type Output = UInt<Or<Ul, Ur>, B1>;
726    #[inline]
727    fn bitor(self, rhs: UInt<Ur, B0>) -> Self::Output {
728        UInt {
729            msb: self.msb.bitor(rhs.msb),
730            lsb: self.lsb.bitor(rhs.lsb),
731        }
732    }
733}
734
735/// `UInt<Ul, B1> | UInt<Ur, B1> = UInt<Ul | Ur, B1>`
736impl<Ul: Unsigned, Ur: Unsigned> BitOr<UInt<Ur, B1>> for UInt<Ul, B1>
737where
738    Ul: BitOr<Ur>,
739{
740    type Output = UInt<Or<Ul, Ur>, B1>;
741    #[inline]
742    fn bitor(self, rhs: UInt<Ur, B1>) -> Self::Output {
743        UInt {
744            msb: self.msb.bitor(rhs.msb),
745            lsb: self.lsb.bitor(rhs.lsb),
746        }
747    }
748}
749
750// ---------------------------------------------------------------------------------------
751// Xor unsigned integers
752
753/// 0 ^ X = X
754impl<Ur: Unsigned> BitXor<Ur> for UTerm {
755    type Output = Ur;
756    #[inline]
757    fn bitxor(self, rhs: Ur) -> Self::Output {
758        rhs
759    }
760}
761
762/// Xoring unsigned integers.
763/// We use our `PrivateXor` operator and then `Trim` the output.
764impl<Ul: Unsigned, Bl: Bit, Ur: Unsigned> BitXor<Ur> for UInt<Ul, Bl>
765where
766    UInt<Ul, Bl>: PrivateXor<Ur>,
767    PrivateXorOut<UInt<Ul, Bl>, Ur>: Trim,
768{
769    type Output = TrimOut<PrivateXorOut<UInt<Ul, Bl>, Ur>>;
770    #[inline]
771    fn bitxor(self, rhs: Ur) -> Self::Output {
772        self.private_xor(rhs).trim()
773    }
774}
775
776/// `UTerm ^ X = X`
777impl<U: Unsigned> PrivateXor<U> for UTerm {
778    type Output = U;
779
780    #[inline]
781    fn private_xor(self, rhs: U) -> Self::Output {
782        rhs
783    }
784}
785
786/// `X ^ UTerm = X`
787impl<B: Bit, U: Unsigned> PrivateXor<UTerm> for UInt<U, B> {
788    type Output = Self;
789
790    #[inline]
791    fn private_xor(self, _: UTerm) -> Self::Output {
792        self
793    }
794}
795
796/// `UInt<Ul, B0> ^ UInt<Ur, B0> = UInt<Ul ^ Ur, B0>`
797impl<Ul: Unsigned, Ur: Unsigned> PrivateXor<UInt<Ur, B0>> for UInt<Ul, B0>
798where
799    Ul: PrivateXor<Ur>,
800{
801    type Output = UInt<PrivateXorOut<Ul, Ur>, B0>;
802
803    #[inline]
804    fn private_xor(self, rhs: UInt<Ur, B0>) -> Self::Output {
805        UInt {
806            msb: self.msb.private_xor(rhs.msb),
807            lsb: B0,
808        }
809    }
810}
811
812/// `UInt<Ul, B0> ^ UInt<Ur, B1> = UInt<Ul ^ Ur, B1>`
813impl<Ul: Unsigned, Ur: Unsigned> PrivateXor<UInt<Ur, B1>> for UInt<Ul, B0>
814where
815    Ul: PrivateXor<Ur>,
816{
817    type Output = UInt<PrivateXorOut<Ul, Ur>, B1>;
818
819    #[inline]
820    fn private_xor(self, rhs: UInt<Ur, B1>) -> Self::Output {
821        UInt {
822            msb: self.msb.private_xor(rhs.msb),
823            lsb: B1,
824        }
825    }
826}
827
828/// `UInt<Ul, B1> ^ UInt<Ur, B0> = UInt<Ul ^ Ur, B1>`
829impl<Ul: Unsigned, Ur: Unsigned> PrivateXor<UInt<Ur, B0>> for UInt<Ul, B1>
830where
831    Ul: PrivateXor<Ur>,
832{
833    type Output = UInt<PrivateXorOut<Ul, Ur>, B1>;
834
835    #[inline]
836    fn private_xor(self, rhs: UInt<Ur, B0>) -> Self::Output {
837        UInt {
838            msb: self.msb.private_xor(rhs.msb),
839            lsb: B1,
840        }
841    }
842}
843
844/// `UInt<Ul, B1> ^ UInt<Ur, B1> = UInt<Ul ^ Ur, B0>`
845impl<Ul: Unsigned, Ur: Unsigned> PrivateXor<UInt<Ur, B1>> for UInt<Ul, B1>
846where
847    Ul: PrivateXor<Ur>,
848{
849    type Output = UInt<PrivateXorOut<Ul, Ur>, B0>;
850
851    #[inline]
852    fn private_xor(self, rhs: UInt<Ur, B1>) -> Self::Output {
853        UInt {
854            msb: self.msb.private_xor(rhs.msb),
855            lsb: B0,
856        }
857    }
858}
859
860// ---------------------------------------------------------------------------------------
861// Shl unsigned integers
862
863/// Shifting `UTerm` by a 0 bit: `UTerm << B0 = UTerm`
864impl Shl<B0> for UTerm {
865    type Output = UTerm;
866    #[inline]
867    fn shl(self, _: B0) -> Self::Output {
868        UTerm
869    }
870}
871
872/// Shifting `UTerm` by a 1 bit: `UTerm << B1 = UTerm`
873impl Shl<B1> for UTerm {
874    type Output = UTerm;
875    #[inline]
876    fn shl(self, _: B1) -> Self::Output {
877        UTerm
878    }
879}
880
881/// Shifting left any unsigned by a zero bit: `U << B0 = U`
882impl<U: Unsigned, B: Bit> Shl<B0> for UInt<U, B> {
883    type Output = UInt<U, B>;
884    #[inline]
885    fn shl(self, _: B0) -> Self::Output {
886        UInt::new()
887    }
888}
889
890/// Shifting left a `UInt` by a one bit: `UInt<U, B> << B1 = UInt<UInt<U, B>, B0>`
891impl<U: Unsigned, B: Bit> Shl<B1> for UInt<U, B> {
892    type Output = UInt<UInt<U, B>, B0>;
893    #[inline]
894    fn shl(self, _: B1) -> Self::Output {
895        UInt::new()
896    }
897}
898
899/// Shifting left `UInt` by `UTerm`: `UInt<U, B> << UTerm = UInt<U, B>`
900impl<U: Unsigned, B: Bit> Shl<UTerm> for UInt<U, B> {
901    type Output = UInt<U, B>;
902    #[inline]
903    fn shl(self, _: UTerm) -> Self::Output {
904        UInt::new()
905    }
906}
907
908/// Shifting left `UTerm` by an unsigned integer: `UTerm << U = UTerm`
909impl<U: Unsigned> Shl<U> for UTerm {
910    type Output = UTerm;
911    #[inline]
912    fn shl(self, _: U) -> Self::Output {
913        UTerm
914    }
915}
916
917/// Shifting left `UInt` by `UInt`: `X << Y` = `UInt(X, B0) << (Y - 1)`
918impl<U: Unsigned, B: Bit, Ur: Unsigned, Br: Bit> Shl<UInt<Ur, Br>> for UInt<U, B>
919where
920    UInt<Ur, Br>: Sub<B1>,
921    UInt<UInt<U, B>, B0>: Shl<Sub1<UInt<Ur, Br>>>,
922{
923    type Output = Shleft<UInt<UInt<U, B>, B0>, Sub1<UInt<Ur, Br>>>;
924    #[inline]
925    fn shl(self, rhs: UInt<Ur, Br>) -> Self::Output {
926        (UInt { msb: self, lsb: B0 }).shl(rhs - B1)
927    }
928}
929
930// ---------------------------------------------------------------------------------------
931// Shr unsigned integers
932
933/// Shifting right a `UTerm` by an unsigned integer: `UTerm >> U = UTerm`
934impl<U: Unsigned> Shr<U> for UTerm {
935    type Output = UTerm;
936    #[inline]
937    fn shr(self, _: U) -> Self::Output {
938        UTerm
939    }
940}
941
942/// Shifting right `UInt` by `UTerm`: `UInt<U, B> >> UTerm = UInt<U, B>`
943impl<U: Unsigned, B: Bit> Shr<UTerm> for UInt<U, B> {
944    type Output = UInt<U, B>;
945    #[inline]
946    fn shr(self, _: UTerm) -> Self::Output {
947        UInt::new()
948    }
949}
950
951/// Shifting right `UTerm` by a 0 bit: `UTerm >> B0 = UTerm`
952impl Shr<B0> for UTerm {
953    type Output = UTerm;
954    #[inline]
955    fn shr(self, _: B0) -> Self::Output {
956        UTerm
957    }
958}
959
960/// Shifting right `UTerm` by a 1 bit: `UTerm >> B1 = UTerm`
961impl Shr<B1> for UTerm {
962    type Output = UTerm;
963    #[inline]
964    fn shr(self, _: B1) -> Self::Output {
965        UTerm
966    }
967}
968
969/// Shifting right any unsigned by a zero bit: `U >> B0 = U`
970impl<U: Unsigned, B: Bit> Shr<B0> for UInt<U, B> {
971    type Output = UInt<U, B>;
972    #[inline]
973    fn shr(self, _: B0) -> Self::Output {
974        UInt::new()
975    }
976}
977
978/// Shifting right a `UInt` by a 1 bit: `UInt<U, B> >> B1 = U`
979impl<U: Unsigned, B: Bit> Shr<B1> for UInt<U, B> {
980    type Output = U;
981    #[inline]
982    fn shr(self, _: B1) -> Self::Output {
983        self.msb
984    }
985}
986
987/// Shifting right `UInt` by `UInt`: `UInt(U, B) >> Y` = `U >> (Y - 1)`
988impl<U: Unsigned, B: Bit, Ur: Unsigned, Br: Bit> Shr<UInt<Ur, Br>> for UInt<U, B>
989where
990    UInt<Ur, Br>: Sub<B1>,
991    U: Shr<Sub1<UInt<Ur, Br>>>,
992{
993    type Output = Shright<U, Sub1<UInt<Ur, Br>>>;
994    #[inline]
995    fn shr(self, rhs: UInt<Ur, Br>) -> Self::Output {
996        self.msb.shr(rhs - B1)
997    }
998}
999
1000// ---------------------------------------------------------------------------------------
1001// Multiply unsigned integers
1002
1003/// `UInt * B0 = UTerm`
1004impl<U: Unsigned, B: Bit> Mul<B0> for UInt<U, B> {
1005    type Output = UTerm;
1006    #[inline]
1007    fn mul(self, _: B0) -> Self::Output {
1008        UTerm
1009    }
1010}
1011
1012/// `UTerm * B0 = UTerm`
1013impl Mul<B0> for UTerm {
1014    type Output = UTerm;
1015    #[inline]
1016    fn mul(self, _: B0) -> Self::Output {
1017        UTerm
1018    }
1019}
1020
1021/// `UTerm * B1 = UTerm`
1022impl Mul<B1> for UTerm {
1023    type Output = UTerm;
1024    #[inline]
1025    fn mul(self, _: B1) -> Self::Output {
1026        UTerm
1027    }
1028}
1029
1030/// `UInt * B1 = UInt`
1031impl<U: Unsigned, B: Bit> Mul<B1> for UInt<U, B> {
1032    type Output = UInt<U, B>;
1033    #[inline]
1034    fn mul(self, _: B1) -> Self::Output {
1035        UInt::new()
1036    }
1037}
1038
1039/// `UInt<U, B> * UTerm = UTerm`
1040impl<U: Unsigned, B: Bit> Mul<UTerm> for UInt<U, B> {
1041    type Output = UTerm;
1042    #[inline]
1043    fn mul(self, _: UTerm) -> Self::Output {
1044        UTerm
1045    }
1046}
1047
1048/// `UTerm * U = UTerm`
1049impl<U: Unsigned> Mul<U> for UTerm {
1050    type Output = UTerm;
1051    #[inline]
1052    fn mul(self, _: U) -> Self::Output {
1053        UTerm
1054    }
1055}
1056
1057/// `UInt<Ul, B0> * UInt<Ur, B> = UInt<(Ul * UInt<Ur, B>), B0>`
1058impl<Ul: Unsigned, B: Bit, Ur: Unsigned> Mul<UInt<Ur, B>> for UInt<Ul, B0>
1059where
1060    Ul: Mul<UInt<Ur, B>>,
1061{
1062    type Output = UInt<Prod<Ul, UInt<Ur, B>>, B0>;
1063    #[inline]
1064    fn mul(self, rhs: UInt<Ur, B>) -> Self::Output {
1065        UInt {
1066            msb: self.msb * rhs,
1067            lsb: B0,
1068        }
1069    }
1070}
1071
1072/// `UInt<Ul, B1> * UInt<Ur, B> = UInt<(Ul * UInt<Ur, B>), B0> + UInt<Ur, B>`
1073impl<Ul: Unsigned, B: Bit, Ur: Unsigned> Mul<UInt<Ur, B>> for UInt<Ul, B1>
1074where
1075    Ul: Mul<UInt<Ur, B>>,
1076    UInt<Prod<Ul, UInt<Ur, B>>, B0>: Add<UInt<Ur, B>>,
1077{
1078    type Output = Sum<UInt<Prod<Ul, UInt<Ur, B>>, B0>, UInt<Ur, B>>;
1079    #[inline]
1080    fn mul(self, rhs: UInt<Ur, B>) -> Self::Output {
1081        UInt {
1082            msb: self.msb * rhs,
1083            lsb: B0,
1084        } + rhs
1085    }
1086}
1087
1088// ---------------------------------------------------------------------------------------
1089// Compare unsigned integers
1090
1091/// Zero == Zero
1092impl Cmp<UTerm> for UTerm {
1093    type Output = Equal;
1094
1095    #[inline]
1096    fn compare<IM: InternalMarker>(&self, _: &UTerm) -> Self::Output {
1097        Equal
1098    }
1099}
1100
1101/// Nonzero > Zero
1102impl<U: Unsigned, B: Bit> Cmp<UTerm> for UInt<U, B> {
1103    type Output = Greater;
1104
1105    #[inline]
1106    fn compare<IM: InternalMarker>(&self, _: &UTerm) -> Self::Output {
1107        Greater
1108    }
1109}
1110
1111/// Zero < Nonzero
1112impl<U: Unsigned, B: Bit> Cmp<UInt<U, B>> for UTerm {
1113    type Output = Less;
1114
1115    #[inline]
1116    fn compare<IM: InternalMarker>(&self, _: &UInt<U, B>) -> Self::Output {
1117        Less
1118    }
1119}
1120
1121/// `UInt<Ul, B0>` cmp with `UInt<Ur, B0>`: `SoFar` is `Equal`
1122impl<Ul: Unsigned, Ur: Unsigned> Cmp<UInt<Ur, B0>> for UInt<Ul, B0>
1123where
1124    Ul: PrivateCmp<Ur, Equal>,
1125{
1126    type Output = PrivateCmpOut<Ul, Ur, Equal>;
1127
1128    #[inline]
1129    fn compare<IM: InternalMarker>(&self, rhs: &UInt<Ur, B0>) -> Self::Output {
1130        self.msb.private_cmp(&rhs.msb, Equal)
1131    }
1132}
1133
1134/// `UInt<Ul, B1>` cmp with `UInt<Ur, B1>`: `SoFar` is `Equal`
1135impl<Ul: Unsigned, Ur: Unsigned> Cmp<UInt<Ur, B1>> for UInt<Ul, B1>
1136where
1137    Ul: PrivateCmp<Ur, Equal>,
1138{
1139    type Output = PrivateCmpOut<Ul, Ur, Equal>;
1140
1141    #[inline]
1142    fn compare<IM: InternalMarker>(&self, rhs: &UInt<Ur, B1>) -> Self::Output {
1143        self.msb.private_cmp(&rhs.msb, Equal)
1144    }
1145}
1146
1147/// `UInt<Ul, B0>` cmp with `UInt<Ur, B1>`: `SoFar` is `Less`
1148impl<Ul: Unsigned, Ur: Unsigned> Cmp<UInt<Ur, B1>> for UInt<Ul, B0>
1149where
1150    Ul: PrivateCmp<Ur, Less>,
1151{
1152    type Output = PrivateCmpOut<Ul, Ur, Less>;
1153
1154    #[inline]
1155    fn compare<IM: InternalMarker>(&self, rhs: &UInt<Ur, B1>) -> Self::Output {
1156        self.msb.private_cmp(&rhs.msb, Less)
1157    }
1158}
1159
1160/// `UInt<Ul, B1>` cmp with `UInt<Ur, B0>`: `SoFar` is `Greater`
1161impl<Ul: Unsigned, Ur: Unsigned> Cmp<UInt<Ur, B0>> for UInt<Ul, B1>
1162where
1163    Ul: PrivateCmp<Ur, Greater>,
1164{
1165    type Output = PrivateCmpOut<Ul, Ur, Greater>;
1166
1167    #[inline]
1168    fn compare<IM: InternalMarker>(&self, rhs: &UInt<Ur, B0>) -> Self::Output {
1169        self.msb.private_cmp(&rhs.msb, Greater)
1170    }
1171}
1172
1173/// Comparing non-terimal bits, with both having bit `B0`.
1174/// These are `Equal`, so we propogate `SoFar`.
1175impl<Ul, Ur, SoFar> PrivateCmp<UInt<Ur, B0>, SoFar> for UInt<Ul, B0>
1176where
1177    Ul: Unsigned,
1178    Ur: Unsigned,
1179    SoFar: Ord,
1180    Ul: PrivateCmp<Ur, SoFar>,
1181{
1182    type Output = PrivateCmpOut<Ul, Ur, SoFar>;
1183
1184    #[inline]
1185    fn private_cmp(&self, rhs: &UInt<Ur, B0>, so_far: SoFar) -> Self::Output {
1186        self.msb.private_cmp(&rhs.msb, so_far)
1187    }
1188}
1189
1190/// Comparing non-terimal bits, with both having bit `B1`.
1191/// These are `Equal`, so we propogate `SoFar`.
1192impl<Ul, Ur, SoFar> PrivateCmp<UInt<Ur, B1>, SoFar> for UInt<Ul, B1>
1193where
1194    Ul: Unsigned,
1195    Ur: Unsigned,
1196    SoFar: Ord,
1197    Ul: PrivateCmp<Ur, SoFar>,
1198{
1199    type Output = PrivateCmpOut<Ul, Ur, SoFar>;
1200
1201    #[inline]
1202    fn private_cmp(&self, rhs: &UInt<Ur, B1>, so_far: SoFar) -> Self::Output {
1203        self.msb.private_cmp(&rhs.msb, so_far)
1204    }
1205}
1206
1207/// Comparing non-terimal bits, with `Lhs` having bit `B0` and `Rhs` having bit `B1`.
1208/// `SoFar`, Lhs is `Less`.
1209impl<Ul, Ur, SoFar> PrivateCmp<UInt<Ur, B1>, SoFar> for UInt<Ul, B0>
1210where
1211    Ul: Unsigned,
1212    Ur: Unsigned,
1213    SoFar: Ord,
1214    Ul: PrivateCmp<Ur, Less>,
1215{
1216    type Output = PrivateCmpOut<Ul, Ur, Less>;
1217
1218    #[inline]
1219    fn private_cmp(&self, rhs: &UInt<Ur, B1>, _: SoFar) -> Self::Output {
1220        self.msb.private_cmp(&rhs.msb, Less)
1221    }
1222}
1223
1224/// Comparing non-terimal bits, with `Lhs` having bit `B1` and `Rhs` having bit `B0`.
1225/// `SoFar`, Lhs is `Greater`.
1226impl<Ul, Ur, SoFar> PrivateCmp<UInt<Ur, B0>, SoFar> for UInt<Ul, B1>
1227where
1228    Ul: Unsigned,
1229    Ur: Unsigned,
1230    SoFar: Ord,
1231    Ul: PrivateCmp<Ur, Greater>,
1232{
1233    type Output = PrivateCmpOut<Ul, Ur, Greater>;
1234
1235    #[inline]
1236    fn private_cmp(&self, rhs: &UInt<Ur, B0>, _: SoFar) -> Self::Output {
1237        self.msb.private_cmp(&rhs.msb, Greater)
1238    }
1239}
1240
1241/// Got to the end of just the `Lhs`. It's `Less`.
1242impl<U: Unsigned, B: Bit, SoFar: Ord> PrivateCmp<UInt<U, B>, SoFar> for UTerm {
1243    type Output = Less;
1244
1245    #[inline]
1246    fn private_cmp(&self, _: &UInt<U, B>, _: SoFar) -> Self::Output {
1247        Less
1248    }
1249}
1250
1251/// Got to the end of just the `Rhs`. `Lhs` is `Greater`.
1252impl<U: Unsigned, B: Bit, SoFar: Ord> PrivateCmp<UTerm, SoFar> for UInt<U, B> {
1253    type Output = Greater;
1254
1255    #[inline]
1256    fn private_cmp(&self, _: &UTerm, _: SoFar) -> Self::Output {
1257        Greater
1258    }
1259}
1260
1261/// Got to the end of both! Return `SoFar`
1262impl<SoFar: Ord> PrivateCmp<UTerm, SoFar> for UTerm {
1263    type Output = SoFar;
1264
1265    #[inline]
1266    fn private_cmp(&self, _: &UTerm, so_far: SoFar) -> Self::Output {
1267        so_far
1268    }
1269}
1270
1271// ---------------------------------------------------------------------------------------
1272// Getting difference in number of bits
1273
1274impl<Ul, Bl, Ur, Br> BitDiff<UInt<Ur, Br>> for UInt<Ul, Bl>
1275where
1276    Ul: Unsigned,
1277    Bl: Bit,
1278    Ur: Unsigned,
1279    Br: Bit,
1280    Ul: BitDiff<Ur>,
1281{
1282    type Output = BitDiffOut<Ul, Ur>;
1283}
1284
1285impl<Ul> BitDiff<UTerm> for Ul
1286where
1287    Ul: Unsigned + Len,
1288{
1289    type Output = Length<Ul>;
1290}
1291
1292// ---------------------------------------------------------------------------------------
1293// Shifting one number until it's the size of another
1294use crate::private::ShiftDiff;
1295impl<Ul: Unsigned, Ur: Unsigned> ShiftDiff<Ur> for Ul
1296where
1297    Ur: BitDiff<Ul>,
1298    Ul: Shl<BitDiffOut<Ur, Ul>>,
1299{
1300    type Output = Shleft<Ul, BitDiffOut<Ur, Ul>>;
1301}
1302
1303// ---------------------------------------------------------------------------------------
1304// Powers of unsigned integers
1305
1306/// X^N
1307impl<X: Unsigned, N: Unsigned> Pow<N> for X
1308where
1309    X: PrivatePow<U1, N>,
1310{
1311    type Output = PrivatePowOut<X, U1, N>;
1312    #[inline]
1313    fn powi(self, n: N) -> Self::Output {
1314        self.private_pow(U1::new(), n)
1315    }
1316}
1317
1318impl<Y: Unsigned, X: Unsigned> PrivatePow<Y, U0> for X {
1319    type Output = Y;
1320
1321    #[inline]
1322    fn private_pow(self, y: Y, _: U0) -> Self::Output {
1323        y
1324    }
1325}
1326
1327impl<Y: Unsigned, X: Unsigned> PrivatePow<Y, U1> for X
1328where
1329    X: Mul<Y>,
1330{
1331    type Output = Prod<X, Y>;
1332
1333    #[inline]
1334    fn private_pow(self, y: Y, _: U1) -> Self::Output {
1335        self * y
1336    }
1337}
1338
1339/// N is even
1340impl<Y: Unsigned, U: Unsigned, B: Bit, X: Unsigned> PrivatePow<Y, UInt<UInt<U, B>, B0>> for X
1341where
1342    X: Mul,
1343    Square<X>: PrivatePow<Y, UInt<U, B>>,
1344{
1345    type Output = PrivatePowOut<Square<X>, Y, UInt<U, B>>;
1346
1347    #[inline]
1348    fn private_pow(self, y: Y, n: UInt<UInt<U, B>, B0>) -> Self::Output {
1349        (self * self).private_pow(y, n.msb)
1350    }
1351}
1352
1353/// N is odd
1354impl<Y: Unsigned, U: Unsigned, B: Bit, X: Unsigned> PrivatePow<Y, UInt<UInt<U, B>, B1>> for X
1355where
1356    X: Mul + Mul<Y>,
1357    Square<X>: PrivatePow<Prod<X, Y>, UInt<U, B>>,
1358{
1359    type Output = PrivatePowOut<Square<X>, Prod<X, Y>, UInt<U, B>>;
1360
1361    #[inline]
1362    fn private_pow(self, y: Y, n: UInt<UInt<U, B>, B1>) -> Self::Output {
1363        (self * self).private_pow(self * y, n.msb)
1364    }
1365}
1366
1367//------------------------------------------
1368// Greatest Common Divisor
1369
1370/// The even number 2*N
1371#[allow(unused)] // Silence spurious warning on older versions of rust
1372type Even<N> = UInt<N, B0>;
1373
1374/// The odd number 2*N + 1
1375type Odd<N> = UInt<N, B1>;
1376
1377/// gcd(0, 0) = 0
1378impl Gcd<U0> for U0 {
1379    type Output = U0;
1380}
1381
1382/// gcd(x, 0) = x
1383impl<X> Gcd<U0> for X
1384where
1385    X: Unsigned + NonZero,
1386{
1387    type Output = X;
1388}
1389
1390/// gcd(0, y) = y
1391impl<Y> Gcd<Y> for U0
1392where
1393    Y: Unsigned + NonZero,
1394{
1395    type Output = Y;
1396}
1397
1398/// gcd(x, y) = 2*gcd(x/2, y/2) if both x and y even
1399impl<Xp, Yp> Gcd<Even<Yp>> for Even<Xp>
1400where
1401    Xp: Gcd<Yp>,
1402    Even<Xp>: NonZero,
1403    Even<Yp>: NonZero,
1404{
1405    type Output = UInt<Gcf<Xp, Yp>, B0>;
1406}
1407
1408/// gcd(x, y) = gcd(x, y/2) if x odd and y even
1409impl<Xp, Yp> Gcd<Even<Yp>> for Odd<Xp>
1410where
1411    Odd<Xp>: Gcd<Yp>,
1412    Even<Yp>: NonZero,
1413{
1414    type Output = Gcf<Odd<Xp>, Yp>;
1415}
1416
1417/// gcd(x, y) = gcd(x/2, y) if x even and y odd
1418impl<Xp, Yp> Gcd<Odd<Yp>> for Even<Xp>
1419where
1420    Xp: Gcd<Odd<Yp>>,
1421    Even<Xp>: NonZero,
1422{
1423    type Output = Gcf<Xp, Odd<Yp>>;
1424}
1425
1426/// gcd(x, y) = gcd([max(x, y) - min(x, y)], min(x, y)) if both x and y odd
1427///
1428/// This will immediately invoke the case for x even and y odd because the difference of two odd
1429/// numbers is an even number.
1430impl<Xp, Yp> Gcd<Odd<Yp>> for Odd<Xp>
1431where
1432    Odd<Xp>: Max<Odd<Yp>> + Min<Odd<Yp>>,
1433    Odd<Yp>: Max<Odd<Xp>> + Min<Odd<Xp>>,
1434    Maximum<Odd<Xp>, Odd<Yp>>: Sub<Minimum<Odd<Xp>, Odd<Yp>>>,
1435    Diff<Maximum<Odd<Xp>, Odd<Yp>>, Minimum<Odd<Xp>, Odd<Yp>>>: Gcd<Minimum<Odd<Xp>, Odd<Yp>>>,
1436{
1437    type Output =
1438        Gcf<Diff<Maximum<Odd<Xp>, Odd<Yp>>, Minimum<Odd<Xp>, Odd<Yp>>>, Minimum<Odd<Xp>, Odd<Yp>>>;
1439}
1440
1441#[cfg(test)]
1442mod gcd_tests {
1443    use super::*;
1444    use crate::consts::*;
1445
1446    macro_rules! gcd_test {
1447        (
1448            $( $a:ident, $b:ident => $c:ident ),* $(,)*
1449        ) => {
1450            $(
1451                assert_eq!(<Gcf<$a, $b> as Unsigned>::to_usize(), $c::to_usize());
1452                assert_eq!(<Gcf<$b, $a> as Unsigned>::to_usize(), $c::to_usize());
1453             )*
1454        }
1455    }
1456
1457    #[test]
1458    fn gcd() {
1459        gcd_test! {
1460            U0,   U0    => U0,
1461            U0,   U42   => U42,
1462            U12,  U8    => U4,
1463            U13,  U1013 => U1,  // Two primes
1464            U9,   U26   => U1,  // Not prime but coprime
1465            U143, U273  => U13,
1466            U117, U273  => U39,
1467        }
1468    }
1469}
1470
1471// -----------------------------------------
1472// GetBit
1473
1474#[allow(missing_docs)]
1475pub trait GetBit<I> {
1476    #[allow(missing_docs)]
1477    type Output;
1478
1479    #[doc(hidden)]
1480    fn get_bit<IM: InternalMarker>(&self, _: &I) -> Self::Output;
1481}
1482
1483#[allow(missing_docs)]
1484pub type GetBitOut<N, I> = <N as GetBit<I>>::Output;
1485
1486// Base case
1487impl<Un, Bn> GetBit<U0> for UInt<Un, Bn>
1488where
1489    Bn: Copy,
1490{
1491    type Output = Bn;
1492
1493    #[inline]
1494    fn get_bit<IM: InternalMarker>(&self, _: &U0) -> Self::Output {
1495        self.lsb
1496    }
1497}
1498
1499// Recursion case
1500impl<Un, Bn, Ui, Bi> GetBit<UInt<Ui, Bi>> for UInt<Un, Bn>
1501where
1502    UInt<Ui, Bi>: Copy + Sub<B1>,
1503    Un: GetBit<Sub1<UInt<Ui, Bi>>>,
1504{
1505    type Output = GetBitOut<Un, Sub1<UInt<Ui, Bi>>>;
1506
1507    #[inline]
1508    fn get_bit<IM: InternalMarker>(&self, i: &UInt<Ui, Bi>) -> Self::Output {
1509        self.msb.get_bit::<Internal>(&(*i - B1))
1510    }
1511}
1512
1513// Ran out of bits
1514impl<I> GetBit<I> for UTerm {
1515    type Output = B0;
1516
1517    #[inline]
1518    fn get_bit<IM: InternalMarker>(&self, _: &I) -> Self::Output {
1519        B0
1520    }
1521}
1522
1523#[test]
1524fn test_get_bit() {
1525    use crate::consts::*;
1526    use crate::Same;
1527    type T1 = <GetBitOut<U2, U0> as Same<B0>>::Output;
1528    type T2 = <GetBitOut<U2, U1> as Same<B1>>::Output;
1529    type T3 = <GetBitOut<U2, U2> as Same<B0>>::Output;
1530
1531    <T1 as Bit>::to_bool();
1532    <T2 as Bit>::to_bool();
1533    <T3 as Bit>::to_bool();
1534}
1535
1536// -----------------------------------------
1537// SetBit
1538
1539/// A **type operator** that, when implemented for unsigned integer `N`, sets the bit at position
1540/// `I` to `B`.
1541pub trait SetBit<I, B> {
1542    #[allow(missing_docs)]
1543    type Output;
1544
1545    #[doc(hidden)]
1546    fn set_bit<IM: InternalMarker>(self, _: I, _: B) -> Self::Output;
1547}
1548/// Alias for the result of calling `SetBit`: `SetBitOut<N, I, B> = <N as SetBit<I, B>>::Output`.
1549pub type SetBitOut<N, I, B> = <N as SetBit<I, B>>::Output;
1550
1551use crate::private::{PrivateSetBit, PrivateSetBitOut};
1552
1553// Call private one then trim it
1554impl<N, I, B> SetBit<I, B> for N
1555where
1556    N: PrivateSetBit<I, B>,
1557    PrivateSetBitOut<N, I, B>: Trim,
1558{
1559    type Output = TrimOut<PrivateSetBitOut<N, I, B>>;
1560
1561    #[inline]
1562    fn set_bit<IM: InternalMarker>(self, i: I, b: B) -> Self::Output {
1563        self.private_set_bit(i, b).trim()
1564    }
1565}
1566
1567// Base case
1568impl<Un, Bn, B> PrivateSetBit<U0, B> for UInt<Un, Bn> {
1569    type Output = UInt<Un, B>;
1570
1571    #[inline]
1572    fn private_set_bit(self, _: U0, b: B) -> Self::Output {
1573        UInt {
1574            msb: self.msb,
1575            lsb: b,
1576        }
1577    }
1578}
1579
1580// Recursion case
1581impl<Un, Bn, Ui, Bi, B> PrivateSetBit<UInt<Ui, Bi>, B> for UInt<Un, Bn>
1582where
1583    UInt<Ui, Bi>: Sub<B1>,
1584    Un: PrivateSetBit<Sub1<UInt<Ui, Bi>>, B>,
1585{
1586    type Output = UInt<PrivateSetBitOut<Un, Sub1<UInt<Ui, Bi>>, B>, Bn>;
1587
1588    #[inline]
1589    fn private_set_bit(self, i: UInt<Ui, Bi>, b: B) -> Self::Output {
1590        UInt {
1591            msb: self.msb.private_set_bit(i - B1, b),
1592            lsb: self.lsb,
1593        }
1594    }
1595}
1596
1597// Ran out of bits, setting B0
1598impl<I> PrivateSetBit<I, B0> for UTerm {
1599    type Output = UTerm;
1600
1601    #[inline]
1602    fn private_set_bit(self, _: I, _: B0) -> Self::Output {
1603        UTerm
1604    }
1605}
1606
1607// Ran out of bits, setting B1
1608impl<I> PrivateSetBit<I, B1> for UTerm
1609where
1610    U1: Shl<I>,
1611{
1612    type Output = Shleft<U1, I>;
1613
1614    #[inline]
1615    fn private_set_bit(self, i: I, _: B1) -> Self::Output {
1616        <U1 as Shl<I>>::shl(U1::new(), i)
1617    }
1618}
1619
1620#[test]
1621fn test_set_bit() {
1622    use crate::consts::*;
1623    use crate::Same;
1624    type T1 = <SetBitOut<U2, U0, B0> as Same<U2>>::Output;
1625    type T2 = <SetBitOut<U2, U0, B1> as Same<U3>>::Output;
1626    type T3 = <SetBitOut<U2, U1, B0> as Same<U0>>::Output;
1627    type T4 = <SetBitOut<U2, U1, B1> as Same<U2>>::Output;
1628    type T5 = <SetBitOut<U2, U2, B0> as Same<U2>>::Output;
1629    type T6 = <SetBitOut<U2, U2, B1> as Same<U6>>::Output;
1630    type T7 = <SetBitOut<U2, U3, B0> as Same<U2>>::Output;
1631    type T8 = <SetBitOut<U2, U3, B1> as Same<U10>>::Output;
1632    type T9 = <SetBitOut<U2, U4, B0> as Same<U2>>::Output;
1633    type T10 = <SetBitOut<U2, U4, B1> as Same<U18>>::Output;
1634
1635    type T11 = <SetBitOut<U3, U0, B0> as Same<U2>>::Output;
1636
1637    <T1 as Unsigned>::to_u32();
1638    <T2 as Unsigned>::to_u32();
1639    <T3 as Unsigned>::to_u32();
1640    <T4 as Unsigned>::to_u32();
1641    <T5 as Unsigned>::to_u32();
1642    <T6 as Unsigned>::to_u32();
1643    <T7 as Unsigned>::to_u32();
1644    <T8 as Unsigned>::to_u32();
1645    <T9 as Unsigned>::to_u32();
1646    <T10 as Unsigned>::to_u32();
1647    <T11 as Unsigned>::to_u32();
1648}
1649
1650// -----------------------------------------
1651
1652// Division algorithm:
1653// We have N / D:
1654// let Q = 0, R = 0
1655// NBits = len(N)
1656// for I in NBits-1..0:
1657//   R <<=1
1658//   R[0] = N[i]
1659//   let C = R.cmp(D)
1660//   if C == Equal or Greater:
1661//     R -= D
1662//     Q[i] = 1
1663
1664#[cfg(tests)]
1665mod tests {
1666    macro_rules! test_div {
1667        ($a:ident / $b:ident = $c:ident) => {{
1668            type R = Quot<$a, $b>;
1669            assert_eq!(<R as Unsigned>::to_usize(), $c::to_usize());
1670        }};
1671    }
1672    #[test]
1673    fn test_div() {
1674        use crate::consts::*;
1675        use crate::{Quot, Same};
1676
1677        test_div!(U0 / U1 = U0);
1678        test_div!(U1 / U1 = U1);
1679        test_div!(U2 / U1 = U2);
1680        test_div!(U3 / U1 = U3);
1681        test_div!(U4 / U1 = U4);
1682
1683        test_div!(U0 / U2 = U0);
1684        test_div!(U1 / U2 = U0);
1685        test_div!(U2 / U2 = U1);
1686        test_div!(U3 / U2 = U1);
1687        test_div!(U4 / U2 = U2);
1688        test_div!(U6 / U2 = U3);
1689        test_div!(U7 / U2 = U3);
1690
1691        type T = <SetBitOut<U0, U1, B1> as Same<U2>>::Output;
1692        <T as Unsigned>::to_u32();
1693    }
1694}
1695// -----------------------------------------
1696// Div
1697use core::ops::Div;
1698
1699// 0 // N
1700impl<Ur: Unsigned, Br: Bit> Div<UInt<Ur, Br>> for UTerm {
1701    type Output = UTerm;
1702    #[inline]
1703    fn div(self, _: UInt<Ur, Br>) -> Self::Output {
1704        UTerm
1705    }
1706}
1707
1708// M // N
1709impl<Ul: Unsigned, Bl: Bit, Ur: Unsigned, Br: Bit> Div<UInt<Ur, Br>> for UInt<Ul, Bl>
1710where
1711    UInt<Ul, Bl>: Len,
1712    Length<UInt<Ul, Bl>>: Sub<B1>,
1713    (): PrivateDiv<UInt<Ul, Bl>, UInt<Ur, Br>, U0, U0, Sub1<Length<UInt<Ul, Bl>>>>,
1714{
1715    type Output = PrivateDivQuot<UInt<Ul, Bl>, UInt<Ur, Br>, U0, U0, Sub1<Length<UInt<Ul, Bl>>>>;
1716    #[inline]
1717    #[cfg_attr(feature = "cargo-clippy", allow(clippy::suspicious_arithmetic_impl))]
1718    fn div(self, rhs: UInt<Ur, Br>) -> Self::Output {
1719        ().private_div_quotient(self, rhs, U0::new(), U0::new(), self.len() - B1)
1720    }
1721}
1722
1723// -----------------------------------------
1724// Rem
1725use core::ops::Rem;
1726
1727// 0 % N
1728impl<Ur: Unsigned, Br: Bit> Rem<UInt<Ur, Br>> for UTerm {
1729    type Output = UTerm;
1730    #[inline]
1731    fn rem(self, _: UInt<Ur, Br>) -> Self::Output {
1732        UTerm
1733    }
1734}
1735
1736// M % N
1737impl<Ul: Unsigned, Bl: Bit, Ur: Unsigned, Br: Bit> Rem<UInt<Ur, Br>> for UInt<Ul, Bl>
1738where
1739    UInt<Ul, Bl>: Len,
1740    Length<UInt<Ul, Bl>>: Sub<B1>,
1741    (): PrivateDiv<UInt<Ul, Bl>, UInt<Ur, Br>, U0, U0, Sub1<Length<UInt<Ul, Bl>>>>,
1742{
1743    type Output = PrivateDivRem<UInt<Ul, Bl>, UInt<Ur, Br>, U0, U0, Sub1<Length<UInt<Ul, Bl>>>>;
1744    #[inline]
1745    fn rem(self, rhs: UInt<Ur, Br>) -> Self::Output {
1746        ().private_div_remainder(self, rhs, UTerm, UTerm, self.len() - B1)
1747    }
1748}
1749
1750// -----------------------------------------
1751// PrivateDiv
1752use crate::private::{PrivateDiv, PrivateDivQuot, PrivateDivRem};
1753
1754use crate::Compare;
1755// R == 0: We set R = UInt<UTerm, N[i]>, then call out to PrivateDivIf for the if statement
1756impl<N, D, Q, I> PrivateDiv<N, D, Q, U0, I> for ()
1757where
1758    N: GetBit<I>,
1759    UInt<UTerm, GetBitOut<N, I>>: Trim,
1760    TrimOut<UInt<UTerm, GetBitOut<N, I>>>: Cmp<D>,
1761    (): PrivateDivIf<
1762        N,
1763        D,
1764        Q,
1765        TrimOut<UInt<UTerm, GetBitOut<N, I>>>,
1766        I,
1767        Compare<TrimOut<UInt<UTerm, GetBitOut<N, I>>>, D>,
1768    >,
1769{
1770    type Quotient = PrivateDivIfQuot<
1771        N,
1772        D,
1773        Q,
1774        TrimOut<UInt<UTerm, GetBitOut<N, I>>>,
1775        I,
1776        Compare<TrimOut<UInt<UTerm, GetBitOut<N, I>>>, D>,
1777    >;
1778    type Remainder = PrivateDivIfRem<
1779        N,
1780        D,
1781        Q,
1782        TrimOut<UInt<UTerm, GetBitOut<N, I>>>,
1783        I,
1784        Compare<TrimOut<UInt<UTerm, GetBitOut<N, I>>>, D>,
1785    >;
1786
1787    #[inline]
1788    fn private_div_quotient(self, n: N, d: D, q: Q, _: U0, i: I) -> Self::Quotient
1789where {
1790        let r = (UInt {
1791            msb: UTerm,
1792            lsb: n.get_bit::<Internal>(&i),
1793        })
1794        .trim();
1795        let r_cmp_d = r.compare::<Internal>(&d);
1796        ().private_div_if_quotient(n, d, q, r, i, r_cmp_d)
1797    }
1798
1799    #[inline]
1800    fn private_div_remainder(self, n: N, d: D, q: Q, _: U0, i: I) -> Self::Remainder {
1801        let r = (UInt {
1802            msb: UTerm,
1803            lsb: n.get_bit::<Internal>(&i),
1804        })
1805        .trim();
1806        let r_cmp_d = r.compare::<Internal>(&d);
1807        ().private_div_if_remainder(n, d, q, r, i, r_cmp_d)
1808    }
1809}
1810
1811// R > 0: We perform R <<= 1 and R[0] = N[i], then call out to PrivateDivIf for the if statement
1812impl<N, D, Q, Ur, Br, I> PrivateDiv<N, D, Q, UInt<Ur, Br>, I> for ()
1813where
1814    N: GetBit<I>,
1815    UInt<UInt<Ur, Br>, GetBitOut<N, I>>: Cmp<D>,
1816    (): PrivateDivIf<
1817        N,
1818        D,
1819        Q,
1820        UInt<UInt<Ur, Br>, GetBitOut<N, I>>,
1821        I,
1822        Compare<UInt<UInt<Ur, Br>, GetBitOut<N, I>>, D>,
1823    >,
1824{
1825    type Quotient = PrivateDivIfQuot<
1826        N,
1827        D,
1828        Q,
1829        UInt<UInt<Ur, Br>, GetBitOut<N, I>>,
1830        I,
1831        Compare<UInt<UInt<Ur, Br>, GetBitOut<N, I>>, D>,
1832    >;
1833    type Remainder = PrivateDivIfRem<
1834        N,
1835        D,
1836        Q,
1837        UInt<UInt<Ur, Br>, GetBitOut<N, I>>,
1838        I,
1839        Compare<UInt<UInt<Ur, Br>, GetBitOut<N, I>>, D>,
1840    >;
1841
1842    #[inline]
1843    fn private_div_quotient(self, n: N, d: D, q: Q, r: UInt<Ur, Br>, i: I) -> Self::Quotient {
1844        let r = UInt {
1845            msb: r,
1846            lsb: n.get_bit::<Internal>(&i),
1847        };
1848        let r_cmp_d = r.compare::<Internal>(&d);
1849        ().private_div_if_quotient(n, d, q, r, i, r_cmp_d)
1850    }
1851
1852    #[inline]
1853    fn private_div_remainder(self, n: N, d: D, q: Q, r: UInt<Ur, Br>, i: I) -> Self::Remainder {
1854        let r = UInt {
1855            msb: r,
1856            lsb: n.get_bit::<Internal>(&i),
1857        };
1858        let r_cmp_d = r.compare::<Internal>(&d);
1859        ().private_div_if_remainder(n, d, q, r, i, r_cmp_d)
1860    }
1861}
1862
1863// -----------------------------------------
1864// PrivateDivIf
1865
1866use crate::private::{PrivateDivIf, PrivateDivIfQuot, PrivateDivIfRem};
1867
1868// R < D, I > 0, we do nothing and recurse
1869impl<N, D, Q, R, Ui, Bi> PrivateDivIf<N, D, Q, R, UInt<Ui, Bi>, Less> for ()
1870where
1871    UInt<Ui, Bi>: Sub<B1>,
1872    (): PrivateDiv<N, D, Q, R, Sub1<UInt<Ui, Bi>>>,
1873{
1874    type Quotient = PrivateDivQuot<N, D, Q, R, Sub1<UInt<Ui, Bi>>>;
1875    type Remainder = PrivateDivRem<N, D, Q, R, Sub1<UInt<Ui, Bi>>>;
1876
1877    #[inline]
1878    fn private_div_if_quotient(
1879        self,
1880        n: N,
1881        d: D,
1882        q: Q,
1883        r: R,
1884        i: UInt<Ui, Bi>,
1885        _: Less,
1886    ) -> Self::Quotient
1887where {
1888        ().private_div_quotient(n, d, q, r, i - B1)
1889    }
1890
1891    #[inline]
1892    fn private_div_if_remainder(
1893        self,
1894        n: N,
1895        d: D,
1896        q: Q,
1897        r: R,
1898        i: UInt<Ui, Bi>,
1899        _: Less,
1900    ) -> Self::Remainder
1901where {
1902        ().private_div_remainder(n, d, q, r, i - B1)
1903    }
1904}
1905
1906// R == D, I > 0, we set R = 0, Q[I] = 1 and recurse
1907impl<N, D, Q, R, Ui, Bi> PrivateDivIf<N, D, Q, R, UInt<Ui, Bi>, Equal> for ()
1908where
1909    UInt<Ui, Bi>: Copy + Sub<B1>,
1910    Q: SetBit<UInt<Ui, Bi>, B1>,
1911    (): PrivateDiv<N, D, SetBitOut<Q, UInt<Ui, Bi>, B1>, U0, Sub1<UInt<Ui, Bi>>>,
1912{
1913    type Quotient = PrivateDivQuot<N, D, SetBitOut<Q, UInt<Ui, Bi>, B1>, U0, Sub1<UInt<Ui, Bi>>>;
1914    type Remainder = PrivateDivRem<N, D, SetBitOut<Q, UInt<Ui, Bi>, B1>, U0, Sub1<UInt<Ui, Bi>>>;
1915
1916    #[inline]
1917    fn private_div_if_quotient(
1918        self,
1919        n: N,
1920        d: D,
1921        q: Q,
1922        _: R,
1923        i: UInt<Ui, Bi>,
1924        _: Equal,
1925    ) -> Self::Quotient
1926where {
1927        ().private_div_quotient(n, d, q.set_bit::<Internal>(i, B1), U0::new(), i - B1)
1928    }
1929
1930    #[inline]
1931    fn private_div_if_remainder(
1932        self,
1933        n: N,
1934        d: D,
1935        q: Q,
1936        _: R,
1937        i: UInt<Ui, Bi>,
1938        _: Equal,
1939    ) -> Self::Remainder
1940where {
1941        ().private_div_remainder(n, d, q.set_bit::<Internal>(i, B1), U0::new(), i - B1)
1942    }
1943}
1944
1945use crate::Diff;
1946// R > D, I > 0, we set R -= D, Q[I] = 1 and recurse
1947impl<N, D, Q, R, Ui, Bi> PrivateDivIf<N, D, Q, R, UInt<Ui, Bi>, Greater> for ()
1948where
1949    D: Copy,
1950    UInt<Ui, Bi>: Copy + Sub<B1>,
1951    R: Sub<D>,
1952    Q: SetBit<UInt<Ui, Bi>, B1>,
1953    (): PrivateDiv<N, D, SetBitOut<Q, UInt<Ui, Bi>, B1>, Diff<R, D>, Sub1<UInt<Ui, Bi>>>,
1954{
1955    type Quotient =
1956        PrivateDivQuot<N, D, SetBitOut<Q, UInt<Ui, Bi>, B1>, Diff<R, D>, Sub1<UInt<Ui, Bi>>>;
1957    type Remainder =
1958        PrivateDivRem<N, D, SetBitOut<Q, UInt<Ui, Bi>, B1>, Diff<R, D>, Sub1<UInt<Ui, Bi>>>;
1959
1960    #[inline]
1961    fn private_div_if_quotient(
1962        self,
1963        n: N,
1964        d: D,
1965        q: Q,
1966        r: R,
1967        i: UInt<Ui, Bi>,
1968        _: Greater,
1969    ) -> Self::Quotient
1970where {
1971        ().private_div_quotient(n, d, q.set_bit::<Internal>(i, B1), r - d, i - B1)
1972    }
1973
1974    #[inline]
1975    fn private_div_if_remainder(
1976        self,
1977        n: N,
1978        d: D,
1979        q: Q,
1980        r: R,
1981        i: UInt<Ui, Bi>,
1982        _: Greater,
1983    ) -> Self::Remainder
1984where {
1985        ().private_div_remainder(n, d, q.set_bit::<Internal>(i, B1), r - d, i - B1)
1986    }
1987}
1988
1989// R < D, I == 0: we do nothing, and return
1990impl<N, D, Q, R> PrivateDivIf<N, D, Q, R, U0, Less> for () {
1991    type Quotient = Q;
1992    type Remainder = R;
1993
1994    #[inline]
1995    fn private_div_if_quotient(self, _: N, _: D, q: Q, _: R, _: U0, _: Less) -> Self::Quotient {
1996        q
1997    }
1998
1999    #[inline]
2000    fn private_div_if_remainder(self, _: N, _: D, _: Q, r: R, _: U0, _: Less) -> Self::Remainder {
2001        r
2002    }
2003}
2004
2005// R == D, I == 0: we set R = 0, Q[I] = 1, and return
2006impl<N, D, Q, R> PrivateDivIf<N, D, Q, R, U0, Equal> for ()
2007where
2008    Q: SetBit<U0, B1>,
2009{
2010    type Quotient = SetBitOut<Q, U0, B1>;
2011    type Remainder = U0;
2012
2013    #[inline]
2014    fn private_div_if_quotient(self, _: N, _: D, q: Q, _: R, i: U0, _: Equal) -> Self::Quotient {
2015        q.set_bit::<Internal>(i, B1)
2016    }
2017
2018    #[inline]
2019    fn private_div_if_remainder(self, _: N, _: D, _: Q, _: R, i: U0, _: Equal) -> Self::Remainder {
2020        i
2021    }
2022}
2023
2024// R > D, I == 0: We set R -= D, Q[I] = 1, and return
2025impl<N, D, Q, R> PrivateDivIf<N, D, Q, R, U0, Greater> for ()
2026where
2027    R: Sub<D>,
2028    Q: SetBit<U0, B1>,
2029{
2030    type Quotient = SetBitOut<Q, U0, B1>;
2031    type Remainder = Diff<R, D>;
2032
2033    #[inline]
2034    fn private_div_if_quotient(self, _: N, _: D, q: Q, _: R, i: U0, _: Greater) -> Self::Quotient {
2035        q.set_bit::<Internal>(i, B1)
2036    }
2037
2038    #[inline]
2039    fn private_div_if_remainder(
2040        self,
2041        _: N,
2042        d: D,
2043        _: Q,
2044        r: R,
2045        _: U0,
2046        _: Greater,
2047    ) -> Self::Remainder {
2048        r - d
2049    }
2050}
2051
2052// -----------------------------------------
2053// PartialDiv
2054use crate::{PartialDiv, Quot};
2055impl<Ur: Unsigned, Br: Bit> PartialDiv<UInt<Ur, Br>> for UTerm {
2056    type Output = UTerm;
2057    #[inline]
2058    fn partial_div(self, _: UInt<Ur, Br>) -> Self::Output {
2059        UTerm
2060    }
2061}
2062
2063// M / N
2064impl<Ul: Unsigned, Bl: Bit, Ur: Unsigned, Br: Bit> PartialDiv<UInt<Ur, Br>> for UInt<Ul, Bl>
2065where
2066    UInt<Ul, Bl>: Div<UInt<Ur, Br>> + Rem<UInt<Ur, Br>, Output = U0>,
2067{
2068    type Output = Quot<UInt<Ul, Bl>, UInt<Ur, Br>>;
2069    #[inline]
2070    fn partial_div(self, rhs: UInt<Ur, Br>) -> Self::Output {
2071        self / rhs
2072    }
2073}
2074
2075// -----------------------------------------
2076// PrivateMin
2077use crate::private::{PrivateMin, PrivateMinOut};
2078
2079impl<U, B, Ur> PrivateMin<Ur, Equal> for UInt<U, B>
2080where
2081    Ur: Unsigned,
2082    U: Unsigned,
2083    B: Bit,
2084{
2085    type Output = UInt<U, B>;
2086    #[inline]
2087    fn private_min(self, _: Ur) -> Self::Output {
2088        self
2089    }
2090}
2091
2092impl<U, B, Ur> PrivateMin<Ur, Less> for UInt<U, B>
2093where
2094    Ur: Unsigned,
2095    U: Unsigned,
2096    B: Bit,
2097{
2098    type Output = UInt<U, B>;
2099    #[inline]
2100    fn private_min(self, _: Ur) -> Self::Output {
2101        self
2102    }
2103}
2104
2105impl<U, B, Ur> PrivateMin<Ur, Greater> for UInt<U, B>
2106where
2107    Ur: Unsigned,
2108    U: Unsigned,
2109    B: Bit,
2110{
2111    type Output = Ur;
2112    #[inline]
2113    fn private_min(self, rhs: Ur) -> Self::Output {
2114        rhs
2115    }
2116}
2117
2118// -----------------------------------------
2119// Min
2120use crate::Min;
2121
2122impl<U> Min<U> for UTerm
2123where
2124    U: Unsigned,
2125{
2126    type Output = UTerm;
2127    #[inline]
2128    fn min(self, _: U) -> Self::Output {
2129        self
2130    }
2131}
2132
2133impl<U, B, Ur> Min<Ur> for UInt<U, B>
2134where
2135    U: Unsigned,
2136    B: Bit,
2137    Ur: Unsigned,
2138    UInt<U, B>: Cmp<Ur> + PrivateMin<Ur, Compare<UInt<U, B>, Ur>>,
2139{
2140    type Output = PrivateMinOut<UInt<U, B>, Ur, Compare<UInt<U, B>, Ur>>;
2141    #[inline]
2142    fn min(self, rhs: Ur) -> Self::Output {
2143        self.private_min(rhs)
2144    }
2145}
2146
2147// -----------------------------------------
2148// PrivateMax
2149use crate::private::{PrivateMax, PrivateMaxOut};
2150
2151impl<U, B, Ur> PrivateMax<Ur, Equal> for UInt<U, B>
2152where
2153    Ur: Unsigned,
2154    U: Unsigned,
2155    B: Bit,
2156{
2157    type Output = UInt<U, B>;
2158    #[inline]
2159    fn private_max(self, _: Ur) -> Self::Output {
2160        self
2161    }
2162}
2163
2164impl<U, B, Ur> PrivateMax<Ur, Less> for UInt<U, B>
2165where
2166    Ur: Unsigned,
2167    U: Unsigned,
2168    B: Bit,
2169{
2170    type Output = Ur;
2171    #[inline]
2172    fn private_max(self, rhs: Ur) -> Self::Output {
2173        rhs
2174    }
2175}
2176
2177impl<U, B, Ur> PrivateMax<Ur, Greater> for UInt<U, B>
2178where
2179    Ur: Unsigned,
2180    U: Unsigned,
2181    B: Bit,
2182{
2183    type Output = UInt<U, B>;
2184    #[inline]
2185    fn private_max(self, _: Ur) -> Self::Output {
2186        self
2187    }
2188}
2189
2190// -----------------------------------------
2191// Max
2192use crate::Max;
2193
2194impl<U> Max<U> for UTerm
2195where
2196    U: Unsigned,
2197{
2198    type Output = U;
2199    #[inline]
2200    fn max(self, rhs: U) -> Self::Output {
2201        rhs
2202    }
2203}
2204
2205impl<U, B, Ur> Max<Ur> for UInt<U, B>
2206where
2207    U: Unsigned,
2208    B: Bit,
2209    Ur: Unsigned,
2210    UInt<U, B>: Cmp<Ur> + PrivateMax<Ur, Compare<UInt<U, B>, Ur>>,
2211{
2212    type Output = PrivateMaxOut<UInt<U, B>, Ur, Compare<UInt<U, B>, Ur>>;
2213    #[inline]
2214    fn max(self, rhs: Ur) -> Self::Output {
2215        self.private_max(rhs)
2216    }
2217}
2218
2219// -----------------------------------------
2220// SquareRoot
2221
2222impl<N> SquareRoot for N
2223where
2224    N: PrivateSquareRoot,
2225{
2226    type Output = <Self as PrivateSquareRoot>::Output;
2227}
2228
2229// sqrt(0) = 0.
2230impl PrivateSquareRoot for UTerm {
2231    type Output = UTerm;
2232}
2233
2234// sqrt(1) = 1.
2235impl PrivateSquareRoot for UInt<UTerm, B1> {
2236    type Output = UInt<UTerm, B1>;
2237}
2238
2239// General case of sqrt(Self) where Self >= 2. If a and b are
2240// bit-valued and Self = 4*u + 2*a + b, then the integer-valued
2241// (fractional part truncated) square root of Self is either 2*sqrt(u)
2242// or 2*sqrt(u)+1. Guess and check by comparing (2*sqrt(u)+1)^2
2243// against Self. Since the `typenum` result of that comparison is a
2244// bit, directly add that bit to 2*sqrt(u).
2245//
2246// Use `Sum<Double<Sqrt<U>>, GrEq<...>>` instead of `UInt<Sqrt<U>,
2247// GrEq<...>>` because `Sqrt<U>` can turn out to be `UTerm` and
2248// `GrEq<...>` can turn out to be `B0`, which would not be a valid
2249// UInt as leading zeros are disallowed.
2250impl<U, Ba, Bb> PrivateSquareRoot for UInt<UInt<U, Ba>, Bb>
2251where
2252    U: Unsigned,
2253    Ba: Bit,
2254    Bb: Bit,
2255    U: SquareRoot,
2256    Sqrt<U>: Shl<B1>,
2257    Double<Sqrt<U>>: Add<B1>,
2258    Add1<Double<Sqrt<U>>>: Mul,
2259    Self: IsGreaterOrEqual<Square<Add1<Double<Sqrt<U>>>>>,
2260    Double<Sqrt<U>>: Add<GrEq<Self, Square<Add1<Double<Sqrt<U>>>>>>,
2261{
2262    type Output = Sum<Double<Sqrt<U>>, GrEq<Self, Square<Add1<Double<Sqrt<U>>>>>>;
2263}
2264
2265#[test]
2266fn sqrt_test() {
2267    use crate::consts::*;
2268
2269    assert_eq!(0, <Sqrt<U0>>::to_u32());
2270
2271    assert_eq!(1, <Sqrt<U1>>::to_u32());
2272    assert_eq!(1, <Sqrt<U2>>::to_u32());
2273    assert_eq!(1, <Sqrt<U3>>::to_u32());
2274
2275    assert_eq!(2, <Sqrt<U4>>::to_u32());
2276    assert_eq!(2, <Sqrt<U5>>::to_u32());
2277    assert_eq!(2, <Sqrt<U6>>::to_u32());
2278    assert_eq!(2, <Sqrt<U7>>::to_u32());
2279    assert_eq!(2, <Sqrt<U8>>::to_u32());
2280
2281    assert_eq!(3, <Sqrt<U9>>::to_u32());
2282    assert_eq!(3, <Sqrt<U10>>::to_u32());
2283    assert_eq!(3, <Sqrt<U11>>::to_u32());
2284    assert_eq!(3, <Sqrt<U12>>::to_u32());
2285    assert_eq!(3, <Sqrt<U13>>::to_u32());
2286    assert_eq!(3, <Sqrt<U14>>::to_u32());
2287    assert_eq!(3, <Sqrt<U15>>::to_u32());
2288
2289    assert_eq!(4, <Sqrt<U16>>::to_u32());
2290    assert_eq!(4, <Sqrt<U17>>::to_u32());
2291    assert_eq!(4, <Sqrt<U18>>::to_u32());
2292    assert_eq!(4, <Sqrt<U19>>::to_u32());
2293    assert_eq!(4, <Sqrt<U20>>::to_u32());
2294    assert_eq!(4, <Sqrt<U21>>::to_u32());
2295    assert_eq!(4, <Sqrt<U22>>::to_u32());
2296    assert_eq!(4, <Sqrt<U23>>::to_u32());
2297    assert_eq!(4, <Sqrt<U24>>::to_u32());
2298
2299    assert_eq!(5, <Sqrt<U25>>::to_u32());
2300    assert_eq!(5, <Sqrt<U26>>::to_u32());
2301    // ...
2302}
2303
2304// -----------------------------------------
2305// Logarithm2
2306
2307impl<N> Logarithm2 for N
2308where
2309    N: PrivateLogarithm2,
2310{
2311    type Output = <Self as PrivateLogarithm2>::Output;
2312}
2313
2314// log2(1) = 0.
2315impl PrivateLogarithm2 for UInt<UTerm, B1> {
2316    type Output = U0;
2317}
2318
2319// General case of log2(Self) where Self >= 2.
2320impl<U, B> PrivateLogarithm2 for UInt<U, B>
2321where
2322    U: Unsigned + Logarithm2,
2323    B: Bit,
2324    Log2<U>: Add<B1>,
2325{
2326    type Output = Add1<Log2<U>>;
2327}
2328
2329// -----------------------------------------
2330// ToInt
2331
2332impl ToInt<i8> for UTerm {
2333    #[inline]
2334    fn to_int() -> i8 {
2335        Self::I8
2336    }
2337}
2338
2339impl ToInt<i16> for UTerm {
2340    #[inline]
2341    fn to_int() -> i16 {
2342        Self::I16
2343    }
2344}
2345
2346impl ToInt<i32> for UTerm {
2347    #[inline]
2348    fn to_int() -> i32 {
2349        Self::I32
2350    }
2351}
2352
2353impl ToInt<i64> for UTerm {
2354    #[inline]
2355    fn to_int() -> i64 {
2356        Self::I64
2357    }
2358}
2359
2360impl ToInt<u8> for UTerm {
2361    #[inline]
2362    fn to_int() -> u8 {
2363        Self::U8
2364    }
2365}
2366
2367impl ToInt<u16> for UTerm {
2368    #[inline]
2369    fn to_int() -> u16 {
2370        Self::U16
2371    }
2372}
2373
2374impl ToInt<u32> for UTerm {
2375    #[inline]
2376    fn to_int() -> u32 {
2377        Self::U32
2378    }
2379}
2380
2381impl ToInt<u64> for UTerm {
2382    #[inline]
2383    fn to_int() -> u64 {
2384        Self::U64
2385    }
2386}
2387
2388impl ToInt<usize> for UTerm {
2389    #[inline]
2390    fn to_int() -> usize {
2391        Self::USIZE
2392    }
2393}
2394
2395impl<U, B> ToInt<i8> for UInt<U, B>
2396where
2397    U: Unsigned,
2398    B: Bit,
2399{
2400    #[inline]
2401    fn to_int() -> i8 {
2402        Self::I8
2403    }
2404}
2405
2406impl<U, B> ToInt<i16> for UInt<U, B>
2407where
2408    U: Unsigned,
2409    B: Bit,
2410{
2411    #[inline]
2412    fn to_int() -> i16 {
2413        Self::I16
2414    }
2415}
2416
2417impl<U, B> ToInt<i32> for UInt<U, B>
2418where
2419    U: Unsigned,
2420    B: Bit,
2421{
2422    #[inline]
2423    fn to_int() -> i32 {
2424        Self::I32
2425    }
2426}
2427
2428impl<U, B> ToInt<i64> for UInt<U, B>
2429where
2430    U: Unsigned,
2431    B: Bit,
2432{
2433    #[inline]
2434    fn to_int() -> i64 {
2435        Self::I64
2436    }
2437}
2438
2439impl<U, B> ToInt<u8> for UInt<U, B>
2440where
2441    U: Unsigned,
2442    B: Bit,
2443{
2444    #[inline]
2445    fn to_int() -> u8 {
2446        Self::U8
2447    }
2448}
2449
2450impl<U, B> ToInt<u16> for UInt<U, B>
2451where
2452    U: Unsigned,
2453    B: Bit,
2454{
2455    #[inline]
2456    fn to_int() -> u16 {
2457        Self::U16
2458    }
2459}
2460
2461impl<U, B> ToInt<u32> for UInt<U, B>
2462where
2463    U: Unsigned,
2464    B: Bit,
2465{
2466    #[inline]
2467    fn to_int() -> u32 {
2468        Self::U32
2469    }
2470}
2471
2472impl<U, B> ToInt<u64> for UInt<U, B>
2473where
2474    U: Unsigned,
2475    B: Bit,
2476{
2477    #[inline]
2478    fn to_int() -> u64 {
2479        Self::U64
2480    }
2481}
2482
2483impl<U, B> ToInt<usize> for UInt<U, B>
2484where
2485    U: Unsigned,
2486    B: Bit,
2487{
2488    #[inline]
2489    fn to_int() -> usize {
2490        Self::USIZE
2491    }
2492}
2493
2494#[cfg(test)]
2495mod tests {
2496    use crate::consts::*;
2497    use crate::{Log2, ToInt, Unsigned};
2498
2499    #[test]
2500    fn log2_test() {
2501        assert_eq!(0, <Log2<U1>>::to_u32());
2502
2503        assert_eq!(1, <Log2<U2>>::to_u32());
2504        assert_eq!(1, <Log2<U3>>::to_u32());
2505
2506        assert_eq!(2, <Log2<U4>>::to_u32());
2507        assert_eq!(2, <Log2<U5>>::to_u32());
2508        assert_eq!(2, <Log2<U6>>::to_u32());
2509        assert_eq!(2, <Log2<U7>>::to_u32());
2510
2511        assert_eq!(3, <Log2<U8>>::to_u32());
2512        assert_eq!(3, <Log2<U9>>::to_u32());
2513        assert_eq!(3, <Log2<U10>>::to_u32());
2514        assert_eq!(3, <Log2<U11>>::to_u32());
2515        assert_eq!(3, <Log2<U12>>::to_u32());
2516        assert_eq!(3, <Log2<U13>>::to_u32());
2517        assert_eq!(3, <Log2<U14>>::to_u32());
2518        assert_eq!(3, <Log2<U15>>::to_u32());
2519
2520        assert_eq!(4, <Log2<U16>>::to_u32());
2521        assert_eq!(4, <Log2<U17>>::to_u32());
2522        assert_eq!(4, <Log2<U18>>::to_u32());
2523        assert_eq!(4, <Log2<U19>>::to_u32());
2524        assert_eq!(4, <Log2<U20>>::to_u32());
2525        assert_eq!(4, <Log2<U21>>::to_u32());
2526        assert_eq!(4, <Log2<U22>>::to_u32());
2527        assert_eq!(4, <Log2<U23>>::to_u32());
2528        assert_eq!(4, <Log2<U24>>::to_u32());
2529        assert_eq!(4, <Log2<U25>>::to_u32());
2530        assert_eq!(4, <Log2<U26>>::to_u32());
2531        assert_eq!(4, <Log2<U27>>::to_u32());
2532        assert_eq!(4, <Log2<U28>>::to_u32());
2533        assert_eq!(4, <Log2<U29>>::to_u32());
2534        assert_eq!(4, <Log2<U30>>::to_u32());
2535        assert_eq!(4, <Log2<U31>>::to_u32());
2536
2537        assert_eq!(5, <Log2<U32>>::to_u32());
2538        assert_eq!(5, <Log2<U33>>::to_u32());
2539
2540        // ...
2541    }
2542
2543    #[test]
2544    fn uint_toint_test() {
2545        // i8
2546        assert_eq!(0_i8, U0::to_int());
2547        assert_eq!(1_i8, U1::to_int());
2548        assert_eq!(2_i8, U2::to_int());
2549        assert_eq!(3_i8, U3::to_int());
2550        assert_eq!(4_i8, U4::to_int());
2551
2552        // i16
2553        assert_eq!(0_i16, U0::to_int());
2554        assert_eq!(1_i16, U1::to_int());
2555        assert_eq!(2_i16, U2::to_int());
2556        assert_eq!(3_i16, U3::to_int());
2557        assert_eq!(4_i16, U4::to_int());
2558
2559        // i32
2560        assert_eq!(0_i32, U0::to_int());
2561        assert_eq!(1_i32, U1::to_int());
2562        assert_eq!(2_i32, U2::to_int());
2563        assert_eq!(3_i32, U3::to_int());
2564        assert_eq!(4_i32, U4::to_int());
2565
2566        // i64
2567        assert_eq!(0_i64, U0::to_int());
2568        assert_eq!(1_i64, U1::to_int());
2569        assert_eq!(2_i64, U2::to_int());
2570        assert_eq!(3_i64, U3::to_int());
2571        assert_eq!(4_i64, U4::to_int());
2572
2573        // u8
2574        assert_eq!(0_u8, U0::to_int());
2575        assert_eq!(1_u8, U1::to_int());
2576        assert_eq!(2_u8, U2::to_int());
2577        assert_eq!(3_u8, U3::to_int());
2578        assert_eq!(4_u8, U4::to_int());
2579
2580        // u16
2581        assert_eq!(0_u16, U0::to_int());
2582        assert_eq!(1_u16, U1::to_int());
2583        assert_eq!(2_u16, U2::to_int());
2584        assert_eq!(3_u16, U3::to_int());
2585        assert_eq!(4_u16, U4::to_int());
2586
2587        // u32
2588        assert_eq!(0_u32, U0::to_int());
2589        assert_eq!(1_u32, U1::to_int());
2590        assert_eq!(2_u32, U2::to_int());
2591        assert_eq!(3_u32, U3::to_int());
2592        assert_eq!(4_u32, U4::to_int());
2593
2594        // u64
2595        assert_eq!(0_u64, U0::to_int());
2596        assert_eq!(1_u64, U1::to_int());
2597        assert_eq!(2_u64, U2::to_int());
2598        assert_eq!(3_u64, U3::to_int());
2599        assert_eq!(4_u64, U4::to_int());
2600
2601        // usize
2602        assert_eq!(0_usize, U0::to_int());
2603        assert_eq!(1_usize, U1::to_int());
2604        assert_eq!(2_usize, U2::to_int());
2605        assert_eq!(3_usize, U3::to_int());
2606        assert_eq!(4_usize, U4::to_int());
2607    }
2608}
substrate_typenum/uint.rs

substrate_typenum/
uint.rs
