1use core::{cmp, fmt, ops};
2
3mod narrowing_div;
4pub use narrowing_div::NarrowingDiv;
5
6/// Minimal integer implementations needed on all integer types, including wide integers.
7#[allow(dead_code)] // Some constants are only used with tests
8pub trait MinInt:
9 Copy
10 + fmt::Debug
11 + ops::BitOr<Output = Self>
12 + ops::Not<Output = Self>
13 + ops::Shl<u32, Output = Self>
14{
15 /// Type with the same width but other signedness
16 type OtherSign: MinInt;
17 /// Unsigned version of Self
18 type Unsigned: MinInt;
19
20 /// If `Self` is a signed integer
21 const SIGNED: bool;
22
23 /// The bitwidth of the int type
24 const BITS: u32;
25
26 const ZERO: Self;
27 const ONE: Self;
28 const MIN: Self;
29 const MAX: Self;
30}
31
32/// Access the associated `OtherSign` type from an int (helper to avoid ambiguous associated
33/// types).
34pub type OtherSign<I> = <I as MinInt>::OtherSign;
35
36/// Trait for some basic operations on integers
37#[allow(dead_code)]
38pub trait Int:
39 MinInt
40 + fmt::Display
41 + fmt::Binary
42 + fmt::LowerHex
43 + ops::AddAssign
44 + ops::SubAssign
45 + ops::MulAssign
46 + ops::DivAssign
47 + ops::RemAssign
48 + ops::BitAndAssign
49 + ops::BitOrAssign
50 + ops::BitXorAssign
51 + ops::ShlAssign<i32>
52 + ops::ShlAssign<u32>
53 + ops::ShrAssign<u32>
54 + ops::ShrAssign<i32>
55 + ops::Add<Output = Self>
56 + ops::Sub<Output = Self>
57 + ops::Mul<Output = Self>
58 + ops::Div<Output = Self>
59 + ops::Rem<Output = Self>
60 + ops::Shl<i32, Output = Self>
61 + ops::Shl<u32, Output = Self>
62 + ops::Shr<i32, Output = Self>
63 + ops::Shr<u32, Output = Self>
64 + ops::BitXor<Output = Self>
65 + ops::BitAnd<Output = Self>
66 + cmp::Ord
67 + From<bool>
68 + CastFrom<i32>
69 + CastFrom<u16>
70 + CastFrom<u32>
71 + CastFrom<u8>
72 + CastFrom<usize>
73 + CastInto<i32>
74 + CastInto<u16>
75 + CastInto<u32>
76 + CastInto<u8>
77 + CastInto<usize>
78{
79 fn signed(self) -> OtherSign<Self::Unsigned>;
80 fn unsigned(self) -> Self::Unsigned;
81 fn from_unsigned(unsigned: Self::Unsigned) -> Self;
82 fn abs(self) -> Self;
83 fn unsigned_abs(self) -> Self::Unsigned;
84
85 fn from_bool(b: bool) -> Self;
86
87 /// Prevents the need for excessive conversions between signed and unsigned
88 fn logical_shr(self, other: u32) -> Self;
89
90 /// Absolute difference between two integers.
91 fn abs_diff(self, other: Self) -> Self::Unsigned;
92
93 // copied from primitive integers, but put in a trait
94 fn is_zero(self) -> bool;
95 fn checked_add(self, other: Self) -> Option<Self>;
96 fn checked_sub(self, other: Self) -> Option<Self>;
97 fn wrapping_neg(self) -> Self;
98 fn wrapping_add(self, other: Self) -> Self;
99 fn wrapping_mul(self, other: Self) -> Self;
100 fn wrapping_sub(self, other: Self) -> Self;
101 fn wrapping_shl(self, other: u32) -> Self;
102 fn wrapping_shr(self, other: u32) -> Self;
103 fn rotate_left(self, other: u32) -> Self;
104 fn overflowing_add(self, other: Self) -> (Self, bool);
105 fn overflowing_sub(self, other: Self) -> (Self, bool);
106 fn carrying_add(self, other: Self, carry: bool) -> (Self, bool);
107 fn borrowing_sub(self, other: Self, borrow: bool) -> (Self, bool);
108 fn leading_zeros(self) -> u32;
109 fn trailing_zeros(self) -> u32;
110 fn ilog2(self) -> u32;
111}
112
113macro_rules! int_impl_common {
114 ($ty:ty) => {
115 fn from_bool(b: bool) -> Self {
116 b as $ty
117 }
118
119 fn logical_shr(self, other: u32) -> Self {
120 Self::from_unsigned(self.unsigned().wrapping_shr(other))
121 }
122
123 fn is_zero(self) -> bool {
124 self == Self::ZERO
125 }
126
127 fn checked_add(self, other: Self) -> Option<Self> {
128 self.checked_add(other)
129 }
130
131 fn checked_sub(self, other: Self) -> Option<Self> {
132 self.checked_sub(other)
133 }
134
135 fn wrapping_neg(self) -> Self {
136 <Self>::wrapping_neg(self)
137 }
138
139 fn wrapping_add(self, other: Self) -> Self {
140 <Self>::wrapping_add(self, other)
141 }
142
143 fn wrapping_mul(self, other: Self) -> Self {
144 <Self>::wrapping_mul(self, other)
145 }
146
147 fn wrapping_sub(self, other: Self) -> Self {
148 <Self>::wrapping_sub(self, other)
149 }
150
151 fn wrapping_shl(self, other: u32) -> Self {
152 <Self>::wrapping_shl(self, other)
153 }
154
155 fn wrapping_shr(self, other: u32) -> Self {
156 <Self>::wrapping_shr(self, other)
157 }
158
159 fn rotate_left(self, other: u32) -> Self {
160 <Self>::rotate_left(self, other)
161 }
162
163 fn overflowing_add(self, other: Self) -> (Self, bool) {
164 <Self>::overflowing_add(self, other)
165 }
166
167 fn overflowing_sub(self, other: Self) -> (Self, bool) {
168 <Self>::overflowing_sub(self, other)
169 }
170
171 fn leading_zeros(self) -> u32 {
172 <Self>::leading_zeros(self)
173 }
174
175 fn trailing_zeros(self) -> u32 {
176 <Self>::trailing_zeros(self)
177 }
178
179 fn ilog2(self) -> u32 {
180 // On our older MSRV, this resolves to the trait method. Which won't actually work,
181 // but this is only called behind other gates.
182 #[allow(clippy::incompatible_msrv)]
183 <Self>::ilog2(self)
184 }
185
186 fn carrying_add(self, other: Self, carry: bool) -> (Self, bool) {
187 let (ab, of1) = self.overflowing_add(other);
188 let (abc, of2) = ab.overflowing_add(Self::from_bool(carry));
189 // `of1 && of2` is possible with signed integers if a negative sum
190 // overflows to `MAX` and adding the carry overflows again back to `MIN`
191 (abc, of1 ^ of2)
192 }
193
194 fn borrowing_sub(self, other: Self, borrow: bool) -> (Self, bool) {
195 let (ab, of1) = self.overflowing_sub(other);
196 let (abc, of2) = ab.overflowing_sub(Self::from_bool(borrow));
197 (abc, of1 ^ of2)
198 }
199 };
200}
201
202macro_rules! int_impl {
203 ($ity:ty, $uty:ty) => {
204 impl MinInt for $uty {
205 type OtherSign = $ity;
206 type Unsigned = $uty;
207
208 const BITS: u32 = <Self as MinInt>::ZERO.count_zeros();
209 const SIGNED: bool = Self::MIN != Self::ZERO;
210
211 const ZERO: Self = 0;
212 const ONE: Self = 1;
213 const MIN: Self = <Self>::MIN;
214 const MAX: Self = <Self>::MAX;
215 }
216
217 impl Int for $uty {
218 fn signed(self) -> $ity {
219 self as $ity
220 }
221
222 fn unsigned(self) -> Self {
223 self
224 }
225
226 fn abs(self) -> Self {
227 unimplemented!()
228 }
229
230 fn unsigned_abs(self) -> Self {
231 unimplemented!()
232 }
233
234 // It makes writing macros easier if this is implemented for both signed and unsigned
235 #[allow(clippy::wrong_self_convention)]
236 fn from_unsigned(me: $uty) -> Self {
237 me
238 }
239
240 fn abs_diff(self, other: Self) -> Self {
241 self.abs_diff(other)
242 }
243
244 int_impl_common!($uty);
245 }
246
247 impl MinInt for $ity {
248 type OtherSign = $uty;
249 type Unsigned = $uty;
250
251 const BITS: u32 = <Self as MinInt>::ZERO.count_zeros();
252 const SIGNED: bool = Self::MIN != Self::ZERO;
253
254 const ZERO: Self = 0;
255 const ONE: Self = 1;
256 const MIN: Self = <Self>::MIN;
257 const MAX: Self = <Self>::MAX;
258 }
259
260 impl Int for $ity {
261 fn signed(self) -> Self {
262 self
263 }
264
265 fn unsigned(self) -> $uty {
266 self as $uty
267 }
268
269 fn abs(self) -> Self {
270 self.abs()
271 }
272
273 fn unsigned_abs(self) -> Self::Unsigned {
274 self.unsigned_abs()
275 }
276
277 fn from_unsigned(me: $uty) -> Self {
278 me as $ity
279 }
280
281 fn abs_diff(self, other: Self) -> $uty {
282 self.abs_diff(other)
283 }
284
285 int_impl_common!($ity);
286 }
287 };
288}
289
290int_impl!(isize, usize);
291int_impl!(i8, u8);
292int_impl!(i16, u16);
293int_impl!(i32, u32);
294int_impl!(i64, u64);
295int_impl!(i128, u128);
296
297/// Trait for integers twice the bit width of another integer. This is implemented for all
298/// primitives except for `u8`, because there is not a smaller primitive.
299pub trait DInt: MinInt {
300 /// Integer that is half the bit width of the integer this trait is implemented for
301 type H: HInt<D = Self>;
302
303 /// Returns the low half of `self`
304 fn lo(self) -> Self::H;
305 /// Returns the high half of `self`
306 fn hi(self) -> Self::H;
307 /// Returns the low and high halves of `self` as a tuple
308 fn lo_hi(self) -> (Self::H, Self::H) {
309 (self.lo(), self.hi())
310 }
311 /// Constructs an integer using lower and higher half parts
312 #[allow(unused)]
313 fn from_lo_hi(lo: Self::H, hi: Self::H) -> Self {
314 lo.zero_widen() | hi.widen_hi()
315 }
316}
317
318/// Trait for integers half the bit width of another integer. This is implemented for all
319/// primitives except for `u128`, because it there is not a larger primitive.
320pub trait HInt: Int {
321 /// Integer that is double the bit width of the integer this trait is implemented for
322 type D: DInt<H = Self> + MinInt;
323
324 // NB: some of the below methods could have default implementations (e.g. `widen_hi`), but for
325 // unknown reasons this can cause infinite recursion when optimizations are disabled. See
326 // <https://github.com/rust-lang/compiler-builtins/pull/707> for context.
327
328 /// Widens (using default extension) the integer to have double bit width
329 fn widen(self) -> Self::D;
330 /// Widens (zero extension only) the integer to have double bit width. This is needed to get
331 /// around problems with associated type bounds (such as `Int<Othersign: DInt>`) being unstable
332 fn zero_widen(self) -> Self::D;
333 /// Widens the integer to have double bit width and shifts the integer into the higher bits
334 #[allow(unused)]
335 fn widen_hi(self) -> Self::D;
336 /// Widening multiplication with zero widening. This cannot overflow.
337 fn zero_widen_mul(self, rhs: Self) -> Self::D;
338 /// Widening multiplication. This cannot overflow.
339 fn widen_mul(self, rhs: Self) -> Self::D;
340}
341
342macro_rules! impl_d_int {
343 ($($X:ident $D:ident),*) => {
344 $(
345 impl DInt for $D {
346 type H = $X;
347
348 fn lo(self) -> Self::H {
349 self as $X
350 }
351 fn hi(self) -> Self::H {
352 (self >> <$X as MinInt>::BITS) as $X
353 }
354 }
355 )*
356 };
357}
358
359macro_rules! impl_h_int {
360 ($($H:ident $uH:ident $X:ident),*) => {
361 $(
362 impl HInt for $H {
363 type D = $X;
364
365 fn widen(self) -> Self::D {
366 self as $X
367 }
368 fn zero_widen(self) -> Self::D {
369 (self as $uH) as $X
370 }
371 fn zero_widen_mul(self, rhs: Self) -> Self::D {
372 self.zero_widen().wrapping_mul(rhs.zero_widen())
373 }
374 fn widen_mul(self, rhs: Self) -> Self::D {
375 self.widen().wrapping_mul(rhs.widen())
376 }
377 fn widen_hi(self) -> Self::D {
378 (self as $X) << <Self as MinInt>::BITS
379 }
380 }
381 )*
382 };
383}
384
385impl_d_int!(u8 u16, u16 u32, u32 u64, u64 u128, i8 i16, i16 i32, i32 i64, i64 i128);
386impl_h_int!(
387 u8 u8 u16,
388 u16 u16 u32,
389 u32 u32 u64,
390 u64 u64 u128,
391 i8 u8 i16,
392 i16 u16 i32,
393 i32 u32 i64,
394 i64 u64 i128
395);
396
397/// Trait to express (possibly lossy) casting of integers
398pub trait CastInto<T: Copy>: Copy {
399 /// By default, casts should be exact.
400 #[track_caller]
401 fn cast(self) -> T;
402
403 /// Call for casts that are expected to truncate.
404 ///
405 /// In practice, this is exactly the same as `cast`; the main difference is to document intent
406 /// in code. `cast` may panic in debug mode.
407 fn cast_lossy(self) -> T;
408}
409
410pub trait CastFrom<T: Copy>: Copy {
411 /// By default, casts should be exact.
412 #[track_caller]
413 fn cast_from(value: T) -> Self;
414
415 /// Call for casts that are expected to truncate.
416 fn cast_from_lossy(value: T) -> Self;
417}
418
419impl<T: Copy, U: CastInto<T> + Copy> CastFrom<U> for T {
420 fn cast_from(value: U) -> Self {
421 value.cast()
422 }
423
424 fn cast_from_lossy(value: U) -> Self {
425 value.cast_lossy()
426 }
427}
428
429macro_rules! cast_into {
430 ($ty:ty) => {
431 cast_into!($ty; usize, isize, u8, i8, u16, i16, u32, i32, u64, i64, u128, i128);
432 };
433 ($ty:ty; $($into:ty),*) => {$(
434 impl CastInto<$into> for $ty {
435 fn cast(self) -> $into {
436 // All we can really do to enforce casting rules is check the rules when in
437 // debug mode.
438 #[cfg(not(feature = "compiler-builtins"))]
439 debug_assert!(<$into>::try_from(self).is_ok(), "failed cast from {self}");
440 self as $into
441 }
442
443 fn cast_lossy(self) -> $into {
444 self as $into
445 }
446 }
447 )*};
448}
449
450macro_rules! cast_into_float {
451 ($ty:ty) => {
452 #[cfg(f16_enabled)]
453 cast_into_float!($ty; f16);
454
455 cast_into_float!($ty; f32, f64);
456
457 #[cfg(f128_enabled)]
458 cast_into_float!($ty; f128);
459 };
460 ($ty:ty; $($into:ty),*) => {$(
461 impl CastInto<$into> for $ty {
462 fn cast(self) -> $into {
463 #[cfg(not(feature = "compiler-builtins"))]
464 debug_assert_eq!(self as $into as $ty, self, "inexact float cast");
465 self as $into
466 }
467
468 fn cast_lossy(self) -> $into {
469 self as $into
470 }
471 }
472 )*};
473}
474
475cast_into!(usize);
476cast_into!(isize);
477cast_into!(u8);
478cast_into!(i8);
479cast_into!(u16);
480cast_into!(i16);
481cast_into!(u32);
482cast_into!(i32);
483cast_into!(u64);
484cast_into!(i64);
485cast_into!(u128);
486cast_into!(i128);
487
488cast_into_float!(i8);
489cast_into_float!(i16);
490cast_into_float!(i32);
491cast_into_float!(i64);
492cast_into_float!(i128);
493