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