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