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