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