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