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