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

typenum/
uint.rs
