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 pub struct UTerm;
50
51 impl UTerm {
52 /// Instantiates a singleton representing this unsigned integer.
53 #[inline]
new() -> UTerm54 pub fn new() -> UTerm {
55 UTerm
56 }
57 }
58
59 impl 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]
to_u8() -> u877 fn to_u8() -> u8 {
78 0
79 }
80 #[inline]
to_u16() -> u1681 fn to_u16() -> u16 {
82 0
83 }
84 #[inline]
to_u32() -> u3285 fn to_u32() -> u32 {
86 0
87 }
88 #[inline]
to_u64() -> u6489 fn to_u64() -> u64 {
90 0
91 }
92 #[cfg(feature = "i128")]
93 #[inline]
to_u128() -> u12894 fn to_u128() -> u128 {
95 0
96 }
97 #[inline]
to_usize() -> usize98 fn to_usize() -> usize {
99 0
100 }
101
102 #[inline]
to_i8() -> i8103 fn to_i8() -> i8 {
104 0
105 }
106 #[inline]
to_i16() -> i16107 fn to_i16() -> i16 {
108 0
109 }
110 #[inline]
to_i32() -> i32111 fn to_i32() -> i32 {
112 0
113 }
114 #[inline]
to_i64() -> i64115 fn to_i64() -> i64 {
116 0
117 }
118 #[cfg(feature = "i128")]
119 #[inline]
to_i128() -> i128120 fn to_i128() -> i128 {
121 0
122 }
123 #[inline]
to_isize() -> isize124 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)]
146 pub 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
153 impl<U: Unsigned, B: Bit> UInt<U, B> {
154 /// Instantiates a singleton representing this unsigned integer.
155 #[inline]
new() -> UInt<U, B>156 pub fn new() -> UInt<U, B> {
157 UInt::default()
158 }
159 }
160
161 impl<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]
to_u8() -> u8179 fn to_u8() -> u8 {
180 B::to_u8() | U::to_u8() << 1
181 }
182 #[inline]
to_u16() -> u16183 fn to_u16() -> u16 {
184 u16::from(B::to_u8()) | U::to_u16() << 1
185 }
186 #[inline]
to_u32() -> u32187 fn to_u32() -> u32 {
188 u32::from(B::to_u8()) | U::to_u32() << 1
189 }
190 #[inline]
to_u64() -> u64191 fn to_u64() -> u64 {
192 u64::from(B::to_u8()) | U::to_u64() << 1
193 }
194 #[cfg(feature = "i128")]
195 #[inline]
to_u128() -> u128196 fn to_u128() -> u128 {
197 u128::from(B::to_u8()) | U::to_u128() << 1
198 }
199 #[inline]
to_usize() -> usize200 fn to_usize() -> usize {
201 usize::from(B::to_u8()) | U::to_usize() << 1
202 }
203
204 #[inline]
to_i8() -> i8205 fn to_i8() -> i8 {
206 B::to_u8() as i8 | U::to_i8() << 1
207 }
208 #[inline]
to_i16() -> i16209 fn to_i16() -> i16 {
210 i16::from(B::to_u8()) | U::to_i16() << 1
211 }
212 #[inline]
to_i32() -> i32213 fn to_i32() -> i32 {
214 i32::from(B::to_u8()) | U::to_i32() << 1
215 }
216 #[inline]
to_i64() -> i64217 fn to_i64() -> i64 {
218 i64::from(B::to_u8()) | U::to_i64() << 1
219 }
220 #[cfg(feature = "i128")]
221 #[inline]
to_i128() -> i128222 fn to_i128() -> i128 {
223 i128::from(B::to_u8()) | U::to_i128() << 1
224 }
225 #[inline]
to_isize() -> isize226 fn to_isize() -> isize {
227 B::to_u8() as isize | U::to_isize() << 1
228 }
229 }
230
231 impl<U: Unsigned, B: Bit> NonZero for UInt<U, B> {}
232 impl Zero for UTerm {}
233
234 impl PowerOfTwo for UInt<UTerm, B1> {}
235 impl<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
241 impl Len for UTerm {
242 type Output = U0;
243 #[inline]
len(&self) -> Self::Output244 fn len(&self) -> Self::Output {
245 UTerm
246 }
247 }
248
249 /// Length of a bit is 1
250 impl<U: Unsigned, B: Bit> Len for UInt<U, B>
251 where
252 U: Len,
253 Length<U>: Add<B1>,
254 Add1<Length<U>>: Unsigned,
255 {
256 type Output = Add1<Length<U>>;
257 #[inline]
len(&self) -> Self::Output258 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`
267 impl Add<B0> for UTerm {
268 type Output = UTerm;
269 #[inline]
add(self, _: B0) -> Self::Output270 fn add(self, _: B0) -> Self::Output {
271 UTerm
272 }
273 }
274
275 /// `U + B0 = U`
276 impl<U: Unsigned, B: Bit> Add<B0> for UInt<U, B> {
277 type Output = UInt<U, B>;
278 #[inline]
add(self, _: B0) -> Self::Output279 fn add(self, _: B0) -> Self::Output {
280 UInt::new()
281 }
282 }
283
284 /// `UTerm + B1 = UInt<UTerm, B1>`
285 impl Add<B1> for UTerm {
286 type Output = UInt<UTerm, B1>;
287 #[inline]
add(self, _: B1) -> Self::Output288 fn add(self, _: B1) -> Self::Output {
289 UInt::new()
290 }
291 }
292
293 /// `UInt<U, B0> + B1 = UInt<U + B1>`
294 impl<U: Unsigned> Add<B1> for UInt<U, B0> {
295 type Output = UInt<U, B1>;
296 #[inline]
add(self, _: B1) -> Self::Output297 fn add(self, _: B1) -> Self::Output {
298 UInt::new()
299 }
300 }
301
302 /// `UInt<U, B1> + B1 = UInt<U + B1, B0>`
303 impl<U: Unsigned> Add<B1> for UInt<U, B1>
304 where
305 U: Add<B1>,
306 Add1<U>: Unsigned,
307 {
308 type Output = UInt<Add1<U>, B0>;
309 #[inline]
add(self, _: B1) -> Self::Output310 fn add(self, _: B1) -> Self::Output {
311 UInt::new()
312 }
313 }
314
315 // ---------------------------------------------------------------------------------------
316 // Adding unsigned integers
317
318 /// `UTerm + U = U`
319 impl<U: Unsigned> Add<U> for UTerm {
320 type Output = U;
321 #[inline]
add(self, rhs: U) -> Self::Output322 fn add(self, rhs: U) -> Self::Output {
323 rhs
324 }
325 }
326
327 /// `UInt<U, B> + UTerm = UInt<U, B>`
328 impl<U: Unsigned, B: Bit> Add<UTerm> for UInt<U, B> {
329 type Output = UInt<U, B>;
330 #[inline]
add(self, _: UTerm) -> Self::Output331 fn add(self, _: UTerm) -> Self::Output {
332 UInt::new()
333 }
334 }
335
336 /// `UInt<Ul, B0> + UInt<Ur, B0> = UInt<Ul + Ur, B0>`
337 impl<Ul: Unsigned, Ur: Unsigned> Add<UInt<Ur, B0>> for UInt<Ul, B0>
338 where
339 Ul: Add<Ur>,
340 {
341 type Output = UInt<Sum<Ul, Ur>, B0>;
342 #[inline]
add(self, rhs: UInt<Ur, B0>) -> Self::Output343 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>`
352 impl<Ul: Unsigned, Ur: Unsigned> Add<UInt<Ur, B1>> for UInt<Ul, B0>
353 where
354 Ul: Add<Ur>,
355 {
356 type Output = UInt<Sum<Ul, Ur>, B1>;
357 #[inline]
add(self, rhs: UInt<Ur, B1>) -> Self::Output358 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>`
367 impl<Ul: Unsigned, Ur: Unsigned> Add<UInt<Ur, B0>> for UInt<Ul, B1>
368 where
369 Ul: Add<Ur>,
370 {
371 type Output = UInt<Sum<Ul, Ur>, B1>;
372 #[inline]
add(self, rhs: UInt<Ur, B0>) -> Self::Output373 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>`
382 impl<Ul: Unsigned, Ur: Unsigned> Add<UInt<Ur, B1>> for UInt<Ul, B1>
383 where
384 Ul: Add<Ur>,
385 Sum<Ul, Ur>: Add<B1>,
386 {
387 type Output = UInt<Add1<Sum<Ul, Ur>>, B0>;
388 #[inline]
add(self, rhs: UInt<Ur, B1>) -> Self::Output389 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`
401 impl Sub<B0> for UTerm {
402 type Output = UTerm;
403 #[inline]
sub(self, _: B0) -> Self::Output404 fn sub(self, _: B0) -> Self::Output {
405 UTerm
406 }
407 }
408
409 /// `UInt - B0 = UInt`
410 impl<U: Unsigned, B: Bit> Sub<B0> for UInt<U, B> {
411 type Output = UInt<U, B>;
412 #[inline]
sub(self, _: B0) -> Self::Output413 fn sub(self, _: B0) -> Self::Output {
414 UInt::new()
415 }
416 }
417
418 /// `UInt<U, B1> - B1 = UInt<U, B0>`
419 impl<U: Unsigned, B: Bit> Sub<B1> for UInt<UInt<U, B>, B1> {
420 type Output = UInt<UInt<U, B>, B0>;
421 #[inline]
sub(self, _: B1) -> Self::Output422 fn sub(self, _: B1) -> Self::Output {
423 UInt::new()
424 }
425 }
426
427 /// `UInt<UTerm, B1> - B1 = UTerm`
428 impl Sub<B1> for UInt<UTerm, B1> {
429 type Output = UTerm;
430 #[inline]
sub(self, _: B1) -> Self::Output431 fn sub(self, _: B1) -> Self::Output {
432 UTerm
433 }
434 }
435
436 /// `UInt<U, B0> - B1 = UInt<U - B1, B1>`
437 impl<U: Unsigned> Sub<B1> for UInt<U, B0>
438 where
439 U: Sub<B1>,
440 Sub1<U>: Unsigned,
441 {
442 type Output = UInt<Sub1<U>, B1>;
443 #[inline]
sub(self, _: B1) -> Self::Output444 fn sub(self, _: B1) -> Self::Output {
445 UInt::new()
446 }
447 }
448
449 // ---------------------------------------------------------------------------------------
450 // Subtracting unsigned integers
451
452 /// `UTerm - UTerm = UTerm`
453 impl Sub<UTerm> for UTerm {
454 type Output = UTerm;
455 #[inline]
sub(self, _: UTerm) -> Self::Output456 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.
462 impl<Ul: Unsigned, Bl: Bit, Ur: Unsigned> Sub<Ur> for UInt<Ul, Bl>
463 where
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]
sub(self, rhs: Ur) -> Self::Output469 fn sub(self, rhs: Ur) -> Self::Output {
470 self.private_sub(rhs).trim()
471 }
472 }
473
474 /// `U - UTerm = U`
475 impl<U: Unsigned> PrivateSub<UTerm> for U {
476 type Output = U;
477
478 #[inline]
private_sub(self, _: UTerm) -> Self::Output479 fn private_sub(self, _: UTerm) -> Self::Output {
480 self
481 }
482 }
483
484 /// `UInt<Ul, B0> - UInt<Ur, B0> = UInt<Ul - Ur, B0>`
485 impl<Ul: Unsigned, Ur: Unsigned> PrivateSub<UInt<Ur, B0>> for UInt<Ul, B0>
486 where
487 Ul: PrivateSub<Ur>,
488 {
489 type Output = UInt<PrivateSubOut<Ul, Ur>, B0>;
490
491 #[inline]
private_sub(self, rhs: UInt<Ur, B0>) -> Self::Output492 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>`
501 impl<Ul: Unsigned, Ur: Unsigned> PrivateSub<UInt<Ur, B1>> for UInt<Ul, B0>
502 where
503 Ul: PrivateSub<Ur>,
504 PrivateSubOut<Ul, Ur>: Sub<B1>,
505 {
506 type Output = UInt<Sub1<PrivateSubOut<Ul, Ur>>, B1>;
507
508 #[inline]
private_sub(self, rhs: UInt<Ur, B1>) -> Self::Output509 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>`
518 impl<Ul: Unsigned, Ur: Unsigned> PrivateSub<UInt<Ur, B0>> for UInt<Ul, B1>
519 where
520 Ul: PrivateSub<Ur>,
521 {
522 type Output = UInt<PrivateSubOut<Ul, Ur>, B1>;
523
524 #[inline]
private_sub(self, rhs: UInt<Ur, B0>) -> Self::Output525 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>`
534 impl<Ul: Unsigned, Ur: Unsigned> PrivateSub<UInt<Ur, B1>> for UInt<Ul, B1>
535 where
536 Ul: PrivateSub<Ur>,
537 {
538 type Output = UInt<PrivateSubOut<Ul, Ur>, B0>;
539
540 #[inline]
private_sub(self, rhs: UInt<Ur, B1>) -> Self::Output541 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
553 impl<Ur: Unsigned> BitAnd<Ur> for UTerm {
554 type Output = UTerm;
555 #[inline]
bitand(self, _: Ur) -> Self::Output556 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.
563 impl<Ul: Unsigned, Bl: Bit, Ur: Unsigned> BitAnd<Ur> for UInt<Ul, Bl>
564 where
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]
bitand(self, rhs: Ur) -> Self::Output570 fn bitand(self, rhs: Ur) -> Self::Output {
571 self.private_and(rhs).trim()
572 }
573 }
574
575 /// `UTerm & X = UTerm`
576 impl<U: Unsigned> PrivateAnd<U> for UTerm {
577 type Output = UTerm;
578
579 #[inline]
private_and(self, _: U) -> Self::Output580 fn private_and(self, _: U) -> Self::Output {
581 UTerm
582 }
583 }
584
585 /// `X & UTerm = UTerm`
586 impl<B: Bit, U: Unsigned> PrivateAnd<UTerm> for UInt<U, B> {
587 type Output = UTerm;
588
589 #[inline]
private_and(self, _: UTerm) -> Self::Output590 fn private_and(self, _: UTerm) -> Self::Output {
591 UTerm
592 }
593 }
594
595 /// `UInt<Ul, B0> & UInt<Ur, B0> = UInt<Ul & Ur, B0>`
596 impl<Ul: Unsigned, Ur: Unsigned> PrivateAnd<UInt<Ur, B0>> for UInt<Ul, B0>
597 where
598 Ul: PrivateAnd<Ur>,
599 {
600 type Output = UInt<PrivateAndOut<Ul, Ur>, B0>;
601
602 #[inline]
private_and(self, rhs: UInt<Ur, B0>) -> Self::Output603 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>`
612 impl<Ul: Unsigned, Ur: Unsigned> PrivateAnd<UInt<Ur, B1>> for UInt<Ul, B0>
613 where
614 Ul: PrivateAnd<Ur>,
615 {
616 type Output = UInt<PrivateAndOut<Ul, Ur>, B0>;
617
618 #[inline]
private_and(self, rhs: UInt<Ur, B1>) -> Self::Output619 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>`
628 impl<Ul: Unsigned, Ur: Unsigned> PrivateAnd<UInt<Ur, B0>> for UInt<Ul, B1>
629 where
630 Ul: PrivateAnd<Ur>,
631 {
632 type Output = UInt<PrivateAndOut<Ul, Ur>, B0>;
633
634 #[inline]
private_and(self, rhs: UInt<Ur, B0>) -> Self::Output635 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>`
644 impl<Ul: Unsigned, Ur: Unsigned> PrivateAnd<UInt<Ur, B1>> for UInt<Ul, B1>
645 where
646 Ul: PrivateAnd<Ur>,
647 {
648 type Output = UInt<PrivateAndOut<Ul, Ur>, B1>;
649
650 #[inline]
private_and(self, rhs: UInt<Ur, B1>) -> Self::Output651 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`
663 impl<U: Unsigned> BitOr<U> for UTerm {
664 type Output = U;
665 #[inline]
bitor(self, rhs: U) -> Self::Output666 fn bitor(self, rhs: U) -> Self::Output {
667 rhs
668 }
669 }
670
671 /// `X | UTerm = X`
672 impl<B: Bit, U: Unsigned> BitOr<UTerm> for UInt<U, B> {
673 type Output = Self;
674 #[inline]
bitor(self, _: UTerm) -> Self::Output675 fn bitor(self, _: UTerm) -> Self::Output {
676 UInt::new()
677 }
678 }
679
680 /// `UInt<Ul, B0> | UInt<Ur, B0> = UInt<Ul | Ur, B0>`
681 impl<Ul: Unsigned, Ur: Unsigned> BitOr<UInt<Ur, B0>> for UInt<Ul, B0>
682 where
683 Ul: BitOr<Ur>,
684 {
685 type Output = UInt<<Ul as BitOr<Ur>>::Output, B0>;
686 #[inline]
bitor(self, rhs: UInt<Ur, B0>) -> Self::Output687 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>`
696 impl<Ul: Unsigned, Ur: Unsigned> BitOr<UInt<Ur, B1>> for UInt<Ul, B0>
697 where
698 Ul: BitOr<Ur>,
699 {
700 type Output = UInt<Or<Ul, Ur>, B1>;
701 #[inline]
bitor(self, rhs: UInt<Ur, B1>) -> Self::Output702 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>`
711 impl<Ul: Unsigned, Ur: Unsigned> BitOr<UInt<Ur, B0>> for UInt<Ul, B1>
712 where
713 Ul: BitOr<Ur>,
714 {
715 type Output = UInt<Or<Ul, Ur>, B1>;
716 #[inline]
bitor(self, rhs: UInt<Ur, B0>) -> Self::Output717 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>`
726 impl<Ul: Unsigned, Ur: Unsigned> BitOr<UInt<Ur, B1>> for UInt<Ul, B1>
727 where
728 Ul: BitOr<Ur>,
729 {
730 type Output = UInt<Or<Ul, Ur>, B1>;
731 #[inline]
bitor(self, rhs: UInt<Ur, B1>) -> Self::Output732 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
744 impl<Ur: Unsigned> BitXor<Ur> for UTerm {
745 type Output = Ur;
746 #[inline]
bitxor(self, rhs: Ur) -> Self::Output747 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.
754 impl<Ul: Unsigned, Bl: Bit, Ur: Unsigned> BitXor<Ur> for UInt<Ul, Bl>
755 where
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]
bitxor(self, rhs: Ur) -> Self::Output761 fn bitxor(self, rhs: Ur) -> Self::Output {
762 self.private_xor(rhs).trim()
763 }
764 }
765
766 /// `UTerm ^ X = X`
767 impl<U: Unsigned> PrivateXor<U> for UTerm {
768 type Output = U;
769
770 #[inline]
private_xor(self, rhs: U) -> Self::Output771 fn private_xor(self, rhs: U) -> Self::Output {
772 rhs
773 }
774 }
775
776 /// `X ^ UTerm = X`
777 impl<B: Bit, U: Unsigned> PrivateXor<UTerm> for UInt<U, B> {
778 type Output = Self;
779
780 #[inline]
private_xor(self, _: UTerm) -> Self::Output781 fn private_xor(self, _: UTerm) -> Self::Output {
782 self
783 }
784 }
785
786 /// `UInt<Ul, B0> ^ UInt<Ur, B0> = UInt<Ul ^ Ur, B0>`
787 impl<Ul: Unsigned, Ur: Unsigned> PrivateXor<UInt<Ur, B0>> for UInt<Ul, B0>
788 where
789 Ul: PrivateXor<Ur>,
790 {
791 type Output = UInt<PrivateXorOut<Ul, Ur>, B0>;
792
793 #[inline]
private_xor(self, rhs: UInt<Ur, B0>) -> Self::Output794 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>`
803 impl<Ul: Unsigned, Ur: Unsigned> PrivateXor<UInt<Ur, B1>> for UInt<Ul, B0>
804 where
805 Ul: PrivateXor<Ur>,
806 {
807 type Output = UInt<PrivateXorOut<Ul, Ur>, B1>;
808
809 #[inline]
private_xor(self, rhs: UInt<Ur, B1>) -> Self::Output810 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>`
819 impl<Ul: Unsigned, Ur: Unsigned> PrivateXor<UInt<Ur, B0>> for UInt<Ul, B1>
820 where
821 Ul: PrivateXor<Ur>,
822 {
823 type Output = UInt<PrivateXorOut<Ul, Ur>, B1>;
824
825 #[inline]
private_xor(self, rhs: UInt<Ur, B0>) -> Self::Output826 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>`
835 impl<Ul: Unsigned, Ur: Unsigned> PrivateXor<UInt<Ur, B1>> for UInt<Ul, B1>
836 where
837 Ul: PrivateXor<Ur>,
838 {
839 type Output = UInt<PrivateXorOut<Ul, Ur>, B0>;
840
841 #[inline]
private_xor(self, rhs: UInt<Ur, B1>) -> Self::Output842 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`
854 impl Shl<B0> for UTerm {
855 type Output = UTerm;
856 #[inline]
shl(self, _: B0) -> Self::Output857 fn shl(self, _: B0) -> Self::Output {
858 UTerm
859 }
860 }
861
862 /// Shifting `UTerm` by a 1 bit: `UTerm << B1 = UTerm`
863 impl Shl<B1> for UTerm {
864 type Output = UTerm;
865 #[inline]
shl(self, _: B1) -> Self::Output866 fn shl(self, _: B1) -> Self::Output {
867 UTerm
868 }
869 }
870
871 /// Shifting left any unsigned by a zero bit: `U << B0 = U`
872 impl<U: Unsigned, B: Bit> Shl<B0> for UInt<U, B> {
873 type Output = UInt<U, B>;
874 #[inline]
shl(self, _: B0) -> Self::Output875 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>`
881 impl<U: Unsigned, B: Bit> Shl<B1> for UInt<U, B> {
882 type Output = UInt<UInt<U, B>, B0>;
883 #[inline]
shl(self, _: B1) -> Self::Output884 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>`
890 impl<U: Unsigned, B: Bit> Shl<UTerm> for UInt<U, B> {
891 type Output = UInt<U, B>;
892 #[inline]
shl(self, _: UTerm) -> Self::Output893 fn shl(self, _: UTerm) -> Self::Output {
894 UInt::new()
895 }
896 }
897
898 /// Shifting left `UTerm` by an unsigned integer: `UTerm << U = UTerm`
899 impl<U: Unsigned> Shl<U> for UTerm {
900 type Output = UTerm;
901 #[inline]
shl(self, _: U) -> Self::Output902 fn shl(self, _: U) -> Self::Output {
903 UTerm
904 }
905 }
906
907 /// Shifting left `UInt` by `UInt`: `X << Y` = `UInt(X, B0) << (Y - 1)`
908 impl<U: Unsigned, B: Bit, Ur: Unsigned, Br: Bit> Shl<UInt<Ur, Br>> for UInt<U, B>
909 where
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]
shl(self, rhs: UInt<Ur, Br>) -> Self::Output915 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`
924 impl<U: Unsigned> Shr<U> for UTerm {
925 type Output = UTerm;
926 #[inline]
shr(self, _: U) -> Self::Output927 fn shr(self, _: U) -> Self::Output {
928 UTerm
929 }
930 }
931
932 /// Shifting right `UInt` by `UTerm`: `UInt<U, B> >> UTerm = UInt<U, B>`
933 impl<U: Unsigned, B: Bit> Shr<UTerm> for UInt<U, B> {
934 type Output = UInt<U, B>;
935 #[inline]
shr(self, _: UTerm) -> Self::Output936 fn shr(self, _: UTerm) -> Self::Output {
937 UInt::new()
938 }
939 }
940
941 /// Shifting right `UTerm` by a 0 bit: `UTerm >> B0 = UTerm`
942 impl Shr<B0> for UTerm {
943 type Output = UTerm;
944 #[inline]
shr(self, _: B0) -> Self::Output945 fn shr(self, _: B0) -> Self::Output {
946 UTerm
947 }
948 }
949
950 /// Shifting right `UTerm` by a 1 bit: `UTerm >> B1 = UTerm`
951 impl Shr<B1> for UTerm {
952 type Output = UTerm;
953 #[inline]
shr(self, _: B1) -> Self::Output954 fn shr(self, _: B1) -> Self::Output {
955 UTerm
956 }
957 }
958
959 /// Shifting right any unsigned by a zero bit: `U >> B0 = U`
960 impl<U: Unsigned, B: Bit> Shr<B0> for UInt<U, B> {
961 type Output = UInt<U, B>;
962 #[inline]
shr(self, _: B0) -> Self::Output963 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`
969 impl<U: Unsigned, B: Bit> Shr<B1> for UInt<U, B> {
970 type Output = U;
971 #[inline]
shr(self, _: B1) -> Self::Output972 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)`
978 impl<U: Unsigned, B: Bit, Ur: Unsigned, Br: Bit> Shr<UInt<Ur, Br>> for UInt<U, B>
979 where
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]
shr(self, rhs: UInt<Ur, Br>) -> Self::Output985 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`
994 impl<U: Unsigned, B: Bit> Mul<B0> for UInt<U, B> {
995 type Output = UTerm;
996 #[inline]
mul(self, _: B0) -> Self::Output997 fn mul(self, _: B0) -> Self::Output {
998 UTerm
999 }
1000 }
1001
1002 /// `UTerm * B0 = UTerm`
1003 impl Mul<B0> for UTerm {
1004 type Output = UTerm;
1005 #[inline]
mul(self, _: B0) -> Self::Output1006 fn mul(self, _: B0) -> Self::Output {
1007 UTerm
1008 }
1009 }
1010
1011 /// `UTerm * B1 = UTerm`
1012 impl Mul<B1> for UTerm {
1013 type Output = UTerm;
1014 #[inline]
mul(self, _: B1) -> Self::Output1015 fn mul(self, _: B1) -> Self::Output {
1016 UTerm
1017 }
1018 }
1019
1020 /// `UInt * B1 = UInt`
1021 impl<U: Unsigned, B: Bit> Mul<B1> for UInt<U, B> {
1022 type Output = UInt<U, B>;
1023 #[inline]
mul(self, _: B1) -> Self::Output1024 fn mul(self, _: B1) -> Self::Output {
1025 UInt::new()
1026 }
1027 }
1028
1029 /// `UInt<U, B> * UTerm = UTerm`
1030 impl<U: Unsigned, B: Bit> Mul<UTerm> for UInt<U, B> {
1031 type Output = UTerm;
1032 #[inline]
mul(self, _: UTerm) -> Self::Output1033 fn mul(self, _: UTerm) -> Self::Output {
1034 UTerm
1035 }
1036 }
1037
1038 /// `UTerm * U = UTerm`
1039 impl<U: Unsigned> Mul<U> for UTerm {
1040 type Output = UTerm;
1041 #[inline]
mul(self, _: U) -> Self::Output1042 fn mul(self, _: U) -> Self::Output {
1043 UTerm
1044 }
1045 }
1046
1047 /// `UInt<Ul, B0> * UInt<Ur, B> = UInt<(Ul * UInt<Ur, B>), B0>`
1048 impl<Ul: Unsigned, B: Bit, Ur: Unsigned> Mul<UInt<Ur, B>> for UInt<Ul, B0>
1049 where
1050 Ul: Mul<UInt<Ur, B>>,
1051 {
1052 type Output = UInt<Prod<Ul, UInt<Ur, B>>, B0>;
1053 #[inline]
mul(self, rhs: UInt<Ur, B>) -> Self::Output1054 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>`
1063 impl<Ul: Unsigned, B: Bit, Ur: Unsigned> Mul<UInt<Ur, B>> for UInt<Ul, B1>
1064 where
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]
mul(self, rhs: UInt<Ur, B>) -> Self::Output1070 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
1082 impl Cmp<UTerm> for UTerm {
1083 type Output = Equal;
1084
1085 #[inline]
compare<IM: InternalMarker>(&self, _: &UTerm) -> Self::Output1086 fn compare<IM: InternalMarker>(&self, _: &UTerm) -> Self::Output {
1087 Equal
1088 }
1089 }
1090
1091 /// Nonzero > Zero
1092 impl<U: Unsigned, B: Bit> Cmp<UTerm> for UInt<U, B> {
1093 type Output = Greater;
1094
1095 #[inline]
compare<IM: InternalMarker>(&self, _: &UTerm) -> Self::Output1096 fn compare<IM: InternalMarker>(&self, _: &UTerm) -> Self::Output {
1097 Greater
1098 }
1099 }
1100
1101 /// Zero < Nonzero
1102 impl<U: Unsigned, B: Bit> Cmp<UInt<U, B>> for UTerm {
1103 type Output = Less;
1104
1105 #[inline]
compare<IM: InternalMarker>(&self, _: &UInt<U, B>) -> Self::Output1106 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`
1112 impl<Ul: Unsigned, Ur: Unsigned> Cmp<UInt<Ur, B0>> for UInt<Ul, B0>
1113 where
1114 Ul: PrivateCmp<Ur, Equal>,
1115 {
1116 type Output = PrivateCmpOut<Ul, Ur, Equal>;
1117
1118 #[inline]
compare<IM: InternalMarker>(&self, rhs: &UInt<Ur, B0>) -> Self::Output1119 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`
1125 impl<Ul: Unsigned, Ur: Unsigned> Cmp<UInt<Ur, B1>> for UInt<Ul, B1>
1126 where
1127 Ul: PrivateCmp<Ur, Equal>,
1128 {
1129 type Output = PrivateCmpOut<Ul, Ur, Equal>;
1130
1131 #[inline]
compare<IM: InternalMarker>(&self, rhs: &UInt<Ur, B1>) -> Self::Output1132 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`
1138 impl<Ul: Unsigned, Ur: Unsigned> Cmp<UInt<Ur, B1>> for UInt<Ul, B0>
1139 where
1140 Ul: PrivateCmp<Ur, Less>,
1141 {
1142 type Output = PrivateCmpOut<Ul, Ur, Less>;
1143
1144 #[inline]
compare<IM: InternalMarker>(&self, rhs: &UInt<Ur, B1>) -> Self::Output1145 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`
1151 impl<Ul: Unsigned, Ur: Unsigned> Cmp<UInt<Ur, B0>> for UInt<Ul, B1>
1152 where
1153 Ul: PrivateCmp<Ur, Greater>,
1154 {
1155 type Output = PrivateCmpOut<Ul, Ur, Greater>;
1156
1157 #[inline]
compare<IM: InternalMarker>(&self, rhs: &UInt<Ur, B0>) -> Self::Output1158 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`.
1165 impl<Ul, Ur, SoFar> PrivateCmp<UInt<Ur, B0>, SoFar> for UInt<Ul, B0>
1166 where
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]
private_cmp(&self, rhs: &UInt<Ur, B0>, so_far: SoFar) -> Self::Output1175 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`.
1182 impl<Ul, Ur, SoFar> PrivateCmp<UInt<Ur, B1>, SoFar> for UInt<Ul, B1>
1183 where
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]
private_cmp(&self, rhs: &UInt<Ur, B1>, so_far: SoFar) -> Self::Output1192 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`.
1199 impl<Ul, Ur, SoFar> PrivateCmp<UInt<Ur, B1>, SoFar> for UInt<Ul, B0>
1200 where
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]
private_cmp(&self, rhs: &UInt<Ur, B1>, _: SoFar) -> Self::Output1209 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`.
1216 impl<Ul, Ur, SoFar> PrivateCmp<UInt<Ur, B0>, SoFar> for UInt<Ul, B1>
1217 where
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]
private_cmp(&self, rhs: &UInt<Ur, B0>, _: SoFar) -> Self::Output1226 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`.
1232 impl<U: Unsigned, B: Bit, SoFar: Ord> PrivateCmp<UInt<U, B>, SoFar> for UTerm {
1233 type Output = Less;
1234
1235 #[inline]
private_cmp(&self, _: &UInt<U, B>, _: SoFar) -> Self::Output1236 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`.
1242 impl<U: Unsigned, B: Bit, SoFar: Ord> PrivateCmp<UTerm, SoFar> for UInt<U, B> {
1243 type Output = Greater;
1244
1245 #[inline]
private_cmp(&self, _: &UTerm, _: SoFar) -> Self::Output1246 fn private_cmp(&self, _: &UTerm, _: SoFar) -> Self::Output {
1247 Greater
1248 }
1249 }
1250
1251 /// Got to the end of both! Return `SoFar`
1252 impl<SoFar: Ord> PrivateCmp<UTerm, SoFar> for UTerm {
1253 type Output = SoFar;
1254
1255 #[inline]
private_cmp(&self, _: &UTerm, so_far: SoFar) -> Self::Output1256 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
1264 impl<Ul, Bl, Ur, Br> BitDiff<UInt<Ur, Br>> for UInt<Ul, Bl>
1265 where
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
1275 impl<Ul> BitDiff<UTerm> for Ul
1276 where
1277 Ul: Unsigned + Len,
1278 {
1279 type Output = Length<Ul>;
1280 }
1281
1282 // ---------------------------------------------------------------------------------------
1283 // Shifting one number until it's the size of another
1284 use crate::private::ShiftDiff;
1285 impl<Ul: Unsigned, Ur: Unsigned> ShiftDiff<Ur> for Ul
1286 where
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
1297 impl<X: Unsigned, N: Unsigned> Pow<N> for X
1298 where
1299 X: PrivatePow<U1, N>,
1300 {
1301 type Output = PrivatePowOut<X, U1, N>;
1302 #[inline]
powi(self, n: N) -> Self::Output1303 fn powi(self, n: N) -> Self::Output {
1304 self.private_pow(U1::new(), n)
1305 }
1306 }
1307
1308 impl<Y: Unsigned, X: Unsigned> PrivatePow<Y, U0> for X {
1309 type Output = Y;
1310
1311 #[inline]
private_pow(self, y: Y, _: U0) -> Self::Output1312 fn private_pow(self, y: Y, _: U0) -> Self::Output {
1313 y
1314 }
1315 }
1316
1317 impl<Y: Unsigned, X: Unsigned> PrivatePow<Y, U1> for X
1318 where
1319 X: Mul<Y>,
1320 {
1321 type Output = Prod<X, Y>;
1322
1323 #[inline]
private_pow(self, y: Y, _: U1) -> Self::Output1324 fn private_pow(self, y: Y, _: U1) -> Self::Output {
1325 self * y
1326 }
1327 }
1328
1329 /// N is even
1330 impl<Y: Unsigned, U: Unsigned, B: Bit, X: Unsigned> PrivatePow<Y, UInt<UInt<U, B>, B0>> for X
1331 where
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]
private_pow(self, y: Y, n: UInt<UInt<U, B>, B0>) -> Self::Output1338 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
1344 impl<Y: Unsigned, U: Unsigned, B: Bit, X: Unsigned> PrivatePow<Y, UInt<UInt<U, B>, B1>> for X
1345 where
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]
private_pow(self, y: Y, n: UInt<UInt<U, B>, B1>) -> Self::Output1352 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
1362 type Even<N> = UInt<N, B0>;
1363
1364 /// The odd number 2*N + 1
1365 type Odd<N> = UInt<N, B1>;
1366
1367 /// gcd(0, 0) = 0
1368 impl Gcd<U0> for U0 {
1369 type Output = U0;
1370 }
1371
1372 /// gcd(x, 0) = x
1373 impl<X> Gcd<U0> for X
1374 where
1375 X: Unsigned + NonZero,
1376 {
1377 type Output = X;
1378 }
1379
1380 /// gcd(0, y) = y
1381 impl<Y> Gcd<Y> for U0
1382 where
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
1389 impl<Xp, Yp> Gcd<Even<Yp>> for Even<Xp>
1390 where
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
1399 impl<Xp, Yp> Gcd<Even<Yp>> for Odd<Xp>
1400 where
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
1408 impl<Xp, Yp> Gcd<Odd<Yp>> for Even<Xp>
1409 where
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.
1420 impl<Xp, Yp> Gcd<Odd<Yp>> for Odd<Xp>
1421 where
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)]
1432 mod 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]
gcd()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)]
1465 pub trait GetBit<I> {
1466 #[allow(missing_docs)]
1467 type Output;
1468
1469 #[doc(hidden)]
get_bit<IM: InternalMarker>(&self, _: &I) -> Self::Output1470 fn get_bit<IM: InternalMarker>(&self, _: &I) -> Self::Output;
1471 }
1472
1473 #[allow(missing_docs)]
1474 pub type GetBitOut<N, I> = <N as GetBit<I>>::Output;
1475
1476 // Base case
1477 impl<Un, Bn> GetBit<U0> for UInt<Un, Bn>
1478 where
1479 Bn: Copy,
1480 {
1481 type Output = Bn;
1482
1483 #[inline]
get_bit<IM: InternalMarker>(&self, _: &U0) -> Self::Output1484 fn get_bit<IM: InternalMarker>(&self, _: &U0) -> Self::Output {
1485 self.lsb
1486 }
1487 }
1488
1489 // Recursion case
1490 impl<Un, Bn, Ui, Bi> GetBit<UInt<Ui, Bi>> for UInt<Un, Bn>
1491 where
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]
get_bit<IM: InternalMarker>(&self, i: &UInt<Ui, Bi>) -> Self::Output1498 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
1504 impl<I> GetBit<I> for UTerm {
1505 type Output = B0;
1506
1507 #[inline]
get_bit<IM: InternalMarker>(&self, _: &I) -> Self::Output1508 fn get_bit<IM: InternalMarker>(&self, _: &I) -> Self::Output {
1509 B0
1510 }
1511 }
1512
1513 #[test]
test_get_bit()1514 fn 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`.
1531 pub trait SetBit<I, B> {
1532 #[allow(missing_docs)]
1533 type Output;
1534
1535 #[doc(hidden)]
set_bit<IM: InternalMarker>(self, _: I, _: B) -> Self::Output1536 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`.
1539 pub type SetBitOut<N, I, B> = <N as SetBit<I, B>>::Output;
1540
1541 use crate::private::{PrivateSetBit, PrivateSetBitOut};
1542
1543 // Call private one then trim it
1544 impl<N, I, B> SetBit<I, B> for N
1545 where
1546 N: PrivateSetBit<I, B>,
1547 PrivateSetBitOut<N, I, B>: Trim,
1548 {
1549 type Output = TrimOut<PrivateSetBitOut<N, I, B>>;
1550
1551 #[inline]
set_bit<IM: InternalMarker>(self, i: I, b: B) -> Self::Output1552 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
1558 impl<Un, Bn, B> PrivateSetBit<U0, B> for UInt<Un, Bn> {
1559 type Output = UInt<Un, B>;
1560
1561 #[inline]
private_set_bit(self, _: U0, b: B) -> Self::Output1562 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
1571 impl<Un, Bn, Ui, Bi, B> PrivateSetBit<UInt<Ui, Bi>, B> for UInt<Un, Bn>
1572 where
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]
private_set_bit(self, i: UInt<Ui, Bi>, b: B) -> Self::Output1579 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
1588 impl<I> PrivateSetBit<I, B0> for UTerm {
1589 type Output = UTerm;
1590
1591 #[inline]
private_set_bit(self, _: I, _: B0) -> Self::Output1592 fn private_set_bit(self, _: I, _: B0) -> Self::Output {
1593 UTerm
1594 }
1595 }
1596
1597 // Ran out of bits, setting B1
1598 impl<I> PrivateSetBit<I, B1> for UTerm
1599 where
1600 U1: Shl<I>,
1601 {
1602 type Output = Shleft<U1, I>;
1603
1604 #[inline]
private_set_bit(self, i: I, _: B1) -> Self::Output1605 fn private_set_bit(self, i: I, _: B1) -> Self::Output {
1606 <U1 as Shl<I>>::shl(U1::new(), i)
1607 }
1608 }
1609
1610 #[test]
test_set_bit()1611 fn 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)]
1655 mod 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]
test_div()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
1687 use core::ops::Div;
1688
1689 // 0 // N
1690 impl<Ur: Unsigned, Br: Bit> Div<UInt<Ur, Br>> for UTerm {
1691 type Output = UTerm;
1692 #[inline]
div(self, _: UInt<Ur, Br>) -> Self::Output1693 fn div(self, _: UInt<Ur, Br>) -> Self::Output {
1694 UTerm
1695 }
1696 }
1697
1698 // M // N
1699 impl<Ul: Unsigned, Bl: Bit, Ur: Unsigned, Br: Bit> Div<UInt<Ur, Br>> for UInt<Ul, Bl>
1700 where
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))]
div(self, rhs: UInt<Ur, Br>) -> Self::Output1708 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
1715 use core::ops::Rem;
1716
1717 // 0 % N
1718 impl<Ur: Unsigned, Br: Bit> Rem<UInt<Ur, Br>> for UTerm {
1719 type Output = UTerm;
1720 #[inline]
rem(self, _: UInt<Ur, Br>) -> Self::Output1721 fn rem(self, _: UInt<Ur, Br>) -> Self::Output {
1722 UTerm
1723 }
1724 }
1725
1726 // M % N
1727 impl<Ul: Unsigned, Bl: Bit, Ur: Unsigned, Br: Bit> Rem<UInt<Ur, Br>> for UInt<Ul, Bl>
1728 where
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]
rem(self, rhs: UInt<Ur, Br>) -> Self::Output1735 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
1742 use crate::private::{PrivateDiv, PrivateDivQuot, PrivateDivRem};
1743
1744 use crate::Compare;
1745 // R == 0: We set R = UInt<UTerm, N[i]>, then call out to PrivateDivIf for the if statement
1746 impl<N, D, Q, I> PrivateDiv<N, D, Q, U0, I> for ()
1747 where
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]
private_div_quotient(self, n: N, d: D, q: Q, _: U0, i: I) -> Self::Quotient where1778 fn private_div_quotient(self, n: N, d: D, q: Q, _: U0, i: I) -> Self::Quotient
1779 where {
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]
private_div_remainder(self, n: N, d: D, q: Q, _: U0, i: I) -> Self::Remainder1790 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
1802 impl<N, D, Q, Ur, Br, I> PrivateDiv<N, D, Q, UInt<Ur, Br>, I> for ()
1803 where
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]
private_div_quotient(self, n: N, d: D, q: Q, r: UInt<Ur, Br>, i: I) -> Self::Quotient1833 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]
private_div_remainder(self, n: N, d: D, q: Q, r: UInt<Ur, Br>, i: I) -> Self::Remainder1843 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
1856 use crate::private::{PrivateDivIf, PrivateDivIfQuot, PrivateDivIfRem};
1857
1858 // R < D, I > 0, we do nothing and recurse
1859 impl<N, D, Q, R, Ui, Bi> PrivateDivIf<N, D, Q, R, UInt<Ui, Bi>, Less> for ()
1860 where
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]
private_div_if_quotient( self, n: N, d: D, q: Q, r: R, i: UInt<Ui, Bi>, _: Less, ) -> Self::Quotient where1868 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
1877 where {
1878 ().private_div_quotient(n, d, q, r, i - B1)
1879 }
1880
1881 #[inline]
private_div_if_remainder( self, n: N, d: D, q: Q, r: R, i: UInt<Ui, Bi>, _: Less, ) -> Self::Remainder where1882 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
1891 where {
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
1897 impl<N, D, Q, R, Ui, Bi> PrivateDivIf<N, D, Q, R, UInt<Ui, Bi>, Equal> for ()
1898 where
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]
private_div_if_quotient( self, n: N, d: D, q: Q, _: R, i: UInt<Ui, Bi>, _: Equal, ) -> Self::Quotient where1907 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
1916 where {
1917 ().private_div_quotient(n, d, q.set_bit::<Internal>(i, B1), U0::new(), i - B1)
1918 }
1919
1920 #[inline]
private_div_if_remainder( self, n: N, d: D, q: Q, _: R, i: UInt<Ui, Bi>, _: Equal, ) -> Self::Remainder where1921 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
1930 where {
1931 ().private_div_remainder(n, d, q.set_bit::<Internal>(i, B1), U0::new(), i - B1)
1932 }
1933 }
1934
1935 use crate::Diff;
1936 // R > D, I > 0, we set R -= D, Q[I] = 1 and recurse
1937 impl<N, D, Q, R, Ui, Bi> PrivateDivIf<N, D, Q, R, UInt<Ui, Bi>, Greater> for ()
1938 where
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]
private_div_if_quotient( self, n: N, d: D, q: Q, r: R, i: UInt<Ui, Bi>, _: Greater, ) -> Self::Quotient where1951 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
1960 where {
1961 ().private_div_quotient(n, d, q.set_bit::<Internal>(i, B1), r - d, i - B1)
1962 }
1963
1964 #[inline]
private_div_if_remainder( self, n: N, d: D, q: Q, r: R, i: UInt<Ui, Bi>, _: Greater, ) -> Self::Remainder where1965 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
1974 where {
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
1980 impl<N, D, Q, R> PrivateDivIf<N, D, Q, R, U0, Less> for () {
1981 type Quotient = Q;
1982 type Remainder = R;
1983
1984 #[inline]
private_div_if_quotient(self, _: N, _: D, q: Q, _: R, _: U0, _: Less) -> Self::Quotient1985 fn private_div_if_quotient(self, _: N, _: D, q: Q, _: R, _: U0, _: Less) -> Self::Quotient {
1986 q
1987 }
1988
1989 #[inline]
private_div_if_remainder(self, _: N, _: D, _: Q, r: R, _: U0, _: Less) -> Self::Remainder1990 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
1996 impl<N, D, Q, R> PrivateDivIf<N, D, Q, R, U0, Equal> for ()
1997 where
1998 Q: SetBit<U0, B1>,
1999 {
2000 type Quotient = SetBitOut<Q, U0, B1>;
2001 type Remainder = U0;
2002
2003 #[inline]
private_div_if_quotient(self, _: N, _: D, q: Q, _: R, i: U0, _: Equal) -> Self::Quotient2004 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]
private_div_if_remainder(self, _: N, _: D, _: Q, _: R, i: U0, _: Equal) -> Self::Remainder2009 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
2015 impl<N, D, Q, R> PrivateDivIf<N, D, Q, R, U0, Greater> for ()
2016 where
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]
private_div_if_quotient(self, _: N, _: D, q: Q, _: R, i: U0, _: Greater) -> Self::Quotient2024 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]
private_div_if_remainder( self, _: N, d: D, _: Q, r: R, _: U0, _: Greater, ) -> Self::Remainder2029 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
2044 use crate::{PartialDiv, Quot};
2045 impl<Ur: Unsigned, Br: Bit> PartialDiv<UInt<Ur, Br>> for UTerm {
2046 type Output = UTerm;
2047 #[inline]
partial_div(self, _: UInt<Ur, Br>) -> Self::Output2048 fn partial_div(self, _: UInt<Ur, Br>) -> Self::Output {
2049 UTerm
2050 }
2051 }
2052
2053 // M / N
2054 impl<Ul: Unsigned, Bl: Bit, Ur: Unsigned, Br: Bit> PartialDiv<UInt<Ur, Br>> for UInt<Ul, Bl>
2055 where
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]
partial_div(self, rhs: UInt<Ur, Br>) -> Self::Output2060 fn partial_div(self, rhs: UInt<Ur, Br>) -> Self::Output {
2061 self / rhs
2062 }
2063 }
2064
2065 // -----------------------------------------
2066 // PrivateMin
2067 use crate::private::{PrivateMin, PrivateMinOut};
2068
2069 impl<U, B, Ur> PrivateMin<Ur, Equal> for UInt<U, B>
2070 where
2071 Ur: Unsigned,
2072 U: Unsigned,
2073 B: Bit,
2074 {
2075 type Output = UInt<U, B>;
2076 #[inline]
private_min(self, _: Ur) -> Self::Output2077 fn private_min(self, _: Ur) -> Self::Output {
2078 self
2079 }
2080 }
2081
2082 impl<U, B, Ur> PrivateMin<Ur, Less> for UInt<U, B>
2083 where
2084 Ur: Unsigned,
2085 U: Unsigned,
2086 B: Bit,
2087 {
2088 type Output = UInt<U, B>;
2089 #[inline]
private_min(self, _: Ur) -> Self::Output2090 fn private_min(self, _: Ur) -> Self::Output {
2091 self
2092 }
2093 }
2094
2095 impl<U, B, Ur> PrivateMin<Ur, Greater> for UInt<U, B>
2096 where
2097 Ur: Unsigned,
2098 U: Unsigned,
2099 B: Bit,
2100 {
2101 type Output = Ur;
2102 #[inline]
private_min(self, rhs: Ur) -> Self::Output2103 fn private_min(self, rhs: Ur) -> Self::Output {
2104 rhs
2105 }
2106 }
2107
2108 // -----------------------------------------
2109 // Min
2110 use crate::Min;
2111
2112 impl<U> Min<U> for UTerm
2113 where
2114 U: Unsigned,
2115 {
2116 type Output = UTerm;
2117 #[inline]
min(self, _: U) -> Self::Output2118 fn min(self, _: U) -> Self::Output {
2119 self
2120 }
2121 }
2122
2123 impl<U, B, Ur> Min<Ur> for UInt<U, B>
2124 where
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]
min(self, rhs: Ur) -> Self::Output2132 fn min(self, rhs: Ur) -> Self::Output {
2133 self.private_min(rhs)
2134 }
2135 }
2136
2137 // -----------------------------------------
2138 // PrivateMax
2139 use crate::private::{PrivateMax, PrivateMaxOut};
2140
2141 impl<U, B, Ur> PrivateMax<Ur, Equal> for UInt<U, B>
2142 where
2143 Ur: Unsigned,
2144 U: Unsigned,
2145 B: Bit,
2146 {
2147 type Output = UInt<U, B>;
2148 #[inline]
private_max(self, _: Ur) -> Self::Output2149 fn private_max(self, _: Ur) -> Self::Output {
2150 self
2151 }
2152 }
2153
2154 impl<U, B, Ur> PrivateMax<Ur, Less> for UInt<U, B>
2155 where
2156 Ur: Unsigned,
2157 U: Unsigned,
2158 B: Bit,
2159 {
2160 type Output = Ur;
2161 #[inline]
private_max(self, rhs: Ur) -> Self::Output2162 fn private_max(self, rhs: Ur) -> Self::Output {
2163 rhs
2164 }
2165 }
2166
2167 impl<U, B, Ur> PrivateMax<Ur, Greater> for UInt<U, B>
2168 where
2169 Ur: Unsigned,
2170 U: Unsigned,
2171 B: Bit,
2172 {
2173 type Output = UInt<U, B>;
2174 #[inline]
private_max(self, _: Ur) -> Self::Output2175 fn private_max(self, _: Ur) -> Self::Output {
2176 self
2177 }
2178 }
2179
2180 // -----------------------------------------
2181 // Max
2182 use crate::Max;
2183
2184 impl<U> Max<U> for UTerm
2185 where
2186 U: Unsigned,
2187 {
2188 type Output = U;
2189 #[inline]
max(self, rhs: U) -> Self::Output2190 fn max(self, rhs: U) -> Self::Output {
2191 rhs
2192 }
2193 }
2194
2195 impl<U, B, Ur> Max<Ur> for UInt<U, B>
2196 where
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]
max(self, rhs: Ur) -> Self::Output2204 fn max(self, rhs: Ur) -> Self::Output {
2205 self.private_max(rhs)
2206 }
2207 }
2208
2209 // -----------------------------------------
2210 // SquareRoot
2211
2212 impl<N> SquareRoot for N
2213 where
2214 N: PrivateSquareRoot,
2215 {
2216 type Output = <Self as PrivateSquareRoot>::Output;
2217 }
2218
2219 // sqrt(0) = 0.
2220 impl PrivateSquareRoot for UTerm {
2221 type Output = UTerm;
2222 }
2223
2224 // sqrt(1) = 1.
2225 impl 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.
2240 impl<U, Ba, Bb> PrivateSquareRoot for UInt<UInt<U, Ba>, Bb>
2241 where
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]
sqrt_test()2256 fn 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
2297 impl<N> Logarithm2 for N
2298 where
2299 N: PrivateLogarithm2,
2300 {
2301 type Output = <Self as PrivateLogarithm2>::Output;
2302 }
2303
2304 // log2(1) = 0.
2305 impl PrivateLogarithm2 for UInt<UTerm, B1> {
2306 type Output = U0;
2307 }
2308
2309 // General case of log2(Self) where Self >= 2.
2310 impl<U, B> PrivateLogarithm2 for UInt<U, B>
2311 where
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
2322 impl ToInt<i8> for UTerm {
2323 #[inline]
to_int() -> i82324 fn to_int() -> i8 {
2325 Self::I8
2326 }
2327 }
2328
2329 impl ToInt<i16> for UTerm {
2330 #[inline]
to_int() -> i162331 fn to_int() -> i16 {
2332 Self::I16
2333 }
2334 }
2335
2336 impl ToInt<i32> for UTerm {
2337 #[inline]
to_int() -> i322338 fn to_int() -> i32 {
2339 Self::I32
2340 }
2341 }
2342
2343 impl ToInt<i64> for UTerm {
2344 #[inline]
to_int() -> i642345 fn to_int() -> i64 {
2346 Self::I64
2347 }
2348 }
2349
2350 impl ToInt<u8> for UTerm {
2351 #[inline]
to_int() -> u82352 fn to_int() -> u8 {
2353 Self::U8
2354 }
2355 }
2356
2357 impl ToInt<u16> for UTerm {
2358 #[inline]
to_int() -> u162359 fn to_int() -> u16 {
2360 Self::U16
2361 }
2362 }
2363
2364 impl ToInt<u32> for UTerm {
2365 #[inline]
to_int() -> u322366 fn to_int() -> u32 {
2367 Self::U32
2368 }
2369 }
2370
2371 impl ToInt<u64> for UTerm {
2372 #[inline]
to_int() -> u642373 fn to_int() -> u64 {
2374 Self::U64
2375 }
2376 }
2377
2378 impl ToInt<usize> for UTerm {
2379 #[inline]
to_int() -> usize2380 fn to_int() -> usize {
2381 Self::USIZE
2382 }
2383 }
2384
2385 impl<U, B> ToInt<i8> for UInt<U, B>
2386 where
2387 U: Unsigned,
2388 B: Bit,
2389 {
2390 #[inline]
to_int() -> i82391 fn to_int() -> i8 {
2392 Self::I8
2393 }
2394 }
2395
2396 impl<U, B> ToInt<i16> for UInt<U, B>
2397 where
2398 U: Unsigned,
2399 B: Bit,
2400 {
2401 #[inline]
to_int() -> i162402 fn to_int() -> i16 {
2403 Self::I16
2404 }
2405 }
2406
2407 impl<U, B> ToInt<i32> for UInt<U, B>
2408 where
2409 U: Unsigned,
2410 B: Bit,
2411 {
2412 #[inline]
to_int() -> i322413 fn to_int() -> i32 {
2414 Self::I32
2415 }
2416 }
2417
2418 impl<U, B> ToInt<i64> for UInt<U, B>
2419 where
2420 U: Unsigned,
2421 B: Bit,
2422 {
2423 #[inline]
to_int() -> i642424 fn to_int() -> i64 {
2425 Self::I64
2426 }
2427 }
2428
2429 impl<U, B> ToInt<u8> for UInt<U, B>
2430 where
2431 U: Unsigned,
2432 B: Bit,
2433 {
2434 #[inline]
to_int() -> u82435 fn to_int() -> u8 {
2436 Self::U8
2437 }
2438 }
2439
2440 impl<U, B> ToInt<u16> for UInt<U, B>
2441 where
2442 U: Unsigned,
2443 B: Bit,
2444 {
2445 #[inline]
to_int() -> u162446 fn to_int() -> u16 {
2447 Self::U16
2448 }
2449 }
2450
2451 impl<U, B> ToInt<u32> for UInt<U, B>
2452 where
2453 U: Unsigned,
2454 B: Bit,
2455 {
2456 #[inline]
to_int() -> u322457 fn to_int() -> u32 {
2458 Self::U32
2459 }
2460 }
2461
2462 impl<U, B> ToInt<u64> for UInt<U, B>
2463 where
2464 U: Unsigned,
2465 B: Bit,
2466 {
2467 #[inline]
to_int() -> u642468 fn to_int() -> u64 {
2469 Self::U64
2470 }
2471 }
2472
2473 impl<U, B> ToInt<usize> for UInt<U, B>
2474 where
2475 U: Unsigned,
2476 B: Bit,
2477 {
2478 #[inline]
to_int() -> usize2479 fn to_int() -> usize {
2480 Self::USIZE
2481 }
2482 }
2483
2484 #[cfg(test)]
2485 mod tests {
2486 use crate::consts::*;
2487 use crate::{Log2, ToInt, Unsigned};
2488
2489 #[test]
log2_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]
uint_toint_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 }
2599