uint.rs source code [crates/typenum/src/uint.rs]

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