1use core::ops;
2
3mod specialized_div_rem;
4
5pub mod addsub;
6pub mod leading_zeros;
7pub mod mul;
8pub mod sdiv;
9pub mod shift;
10pub mod udiv;
11
12pub use self::leading_zeros::__clzsi2;
13
14public_test_dep! {
15/// Trait for some basic operations on integers
16pub(crate) trait Int:
17 Copy
18 + core::fmt::Debug
19 + PartialEq
20 + PartialOrd
21 + ops::AddAssign
22 + ops::SubAssign
23 + ops::BitAndAssign
24 + ops::BitOrAssign
25 + ops::BitXorAssign
26 + ops::ShlAssign<i32>
27 + ops::ShrAssign<u32>
28 + ops::Add<Output = Self>
29 + ops::Sub<Output = Self>
30 + ops::Div<Output = Self>
31 + ops::Shl<u32, Output = Self>
32 + ops::Shr<u32, Output = Self>
33 + ops::BitOr<Output = Self>
34 + ops::BitXor<Output = Self>
35 + ops::BitAnd<Output = Self>
36 + ops::Not<Output = Self>
37{
38 /// Type with the same width but other signedness
39 type OtherSign: Int;
40 /// Unsigned version of Self
41 type UnsignedInt: Int;
42
43 /// If `Self` is a signed integer
44 const SIGNED: bool;
45
46 /// The bitwidth of the int type
47 const BITS: u32;
48
49 const ZERO: Self;
50 const ONE: Self;
51 const MIN: Self;
52 const MAX: Self;
53
54 /// LUT used for maximizing the space covered and minimizing the computational cost of fuzzing
55 /// in `testcrate`. For example, Self = u128 produces [0,1,2,7,8,15,16,31,32,63,64,95,96,111,
56 /// 112,119,120,125,126,127].
57 const FUZZ_LENGTHS: [u8; 20];
58 /// The number of entries of `FUZZ_LENGTHS` actually used. The maximum is 20 for u128.
59 const FUZZ_NUM: usize;
60
61 fn unsigned(self) -> Self::UnsignedInt;
62 fn from_unsigned(unsigned: Self::UnsignedInt) -> Self;
63
64 fn from_bool(b: bool) -> Self;
65
66 /// Prevents the need for excessive conversions between signed and unsigned
67 fn logical_shr(self, other: u32) -> Self;
68
69 /// Absolute difference between two integers.
70 fn abs_diff(self, other: Self) -> Self::UnsignedInt;
71
72 // copied from primitive integers, but put in a trait
73 fn is_zero(self) -> bool;
74 fn wrapping_neg(self) -> Self;
75 fn wrapping_add(self, other: Self) -> Self;
76 fn wrapping_mul(self, other: Self) -> Self;
77 fn wrapping_sub(self, other: Self) -> Self;
78 fn wrapping_shl(self, other: u32) -> Self;
79 fn wrapping_shr(self, other: u32) -> Self;
80 fn rotate_left(self, other: u32) -> Self;
81 fn overflowing_add(self, other: Self) -> (Self, bool);
82 fn leading_zeros(self) -> u32;
83}
84}
85
86macro_rules! int_impl_common {
87 ($ty:ty) => {
88 const BITS: u32 = <Self as Int>::ZERO.count_zeros();
89 const SIGNED: bool = Self::MIN != Self::ZERO;
90
91 const ZERO: Self = 0;
92 const ONE: Self = 1;
93 const MIN: Self = <Self>::MIN;
94 const MAX: Self = <Self>::MAX;
95
96 const FUZZ_LENGTHS: [u8; 20] = {
97 let bits = <Self as Int>::BITS;
98 let mut v = [0u8; 20];
99 v[0] = 0;
100 v[1] = 1;
101 v[2] = 2; // important for parity and the iX::MIN case when reversed
102 let mut i = 3;
103 // No need for any more until the byte boundary, because there should be no algorithms
104 // that are sensitive to anything not next to byte boundaries after 2. We also scale
105 // in powers of two, which is important to prevent u128 corner tests from getting too
106 // big.
107 let mut l = 8;
108 loop {
109 if l >= ((bits / 2) as u8) {
110 break;
111 }
112 // get both sides of the byte boundary
113 v[i] = l - 1;
114 i += 1;
115 v[i] = l;
116 i += 1;
117 l *= 2;
118 }
119
120 if bits != 8 {
121 // add the lower side of the middle boundary
122 v[i] = ((bits / 2) - 1) as u8;
123 i += 1;
124 }
125
126 // We do not want to jump directly from the Self::BITS/2 boundary to the Self::BITS
127 // boundary because of algorithms that split the high part up. We reverse the scaling
128 // as we go to Self::BITS.
129 let mid = i;
130 let mut j = 1;
131 loop {
132 v[i] = (bits as u8) - (v[mid - j]) - 1;
133 if j == mid {
134 break;
135 }
136 i += 1;
137 j += 1;
138 }
139 v
140 };
141
142 const FUZZ_NUM: usize = {
143 let log2 = (<Self as Int>::BITS - 1).count_ones() as usize;
144 if log2 == 3 {
145 // case for u8
146 6
147 } else {
148 // 3 entries on each extreme, 2 in the middle, and 4 for each scale of intermediate
149 // boundaries.
150 8 + (4 * (log2 - 4))
151 }
152 };
153
154 fn from_bool(b: bool) -> Self {
155 b as $ty
156 }
157
158 fn logical_shr(self, other: u32) -> Self {
159 Self::from_unsigned(self.unsigned().wrapping_shr(other))
160 }
161
162 fn is_zero(self) -> bool {
163 self == Self::ZERO
164 }
165
166 fn wrapping_neg(self) -> Self {
167 <Self>::wrapping_neg(self)
168 }
169
170 fn wrapping_add(self, other: Self) -> Self {
171 <Self>::wrapping_add(self, other)
172 }
173
174 fn wrapping_mul(self, other: Self) -> Self {
175 <Self>::wrapping_mul(self, other)
176 }
177
178 fn wrapping_sub(self, other: Self) -> Self {
179 <Self>::wrapping_sub(self, other)
180 }
181
182 fn wrapping_shl(self, other: u32) -> Self {
183 <Self>::wrapping_shl(self, other)
184 }
185
186 fn wrapping_shr(self, other: u32) -> Self {
187 <Self>::wrapping_shr(self, other)
188 }
189
190 fn rotate_left(self, other: u32) -> Self {
191 <Self>::rotate_left(self, other)
192 }
193
194 fn overflowing_add(self, other: Self) -> (Self, bool) {
195 <Self>::overflowing_add(self, other)
196 }
197
198 fn leading_zeros(self) -> u32 {
199 <Self>::leading_zeros(self)
200 }
201 };
202}
203
204macro_rules! int_impl {
205 ($ity:ty, $uty:ty) => {
206 impl Int for $uty {
207 type OtherSign = $ity;
208 type UnsignedInt = $uty;
209
210 fn unsigned(self) -> $uty {
211 self
212 }
213
214 // It makes writing macros easier if this is implemented for both signed and unsigned
215 #[allow(clippy::wrong_self_convention)]
216 fn from_unsigned(me: $uty) -> Self {
217 me
218 }
219
220 fn abs_diff(self, other: Self) -> Self {
221 if self < other {
222 other.wrapping_sub(self)
223 } else {
224 self.wrapping_sub(other)
225 }
226 }
227
228 int_impl_common!($uty);
229 }
230
231 impl Int for $ity {
232 type OtherSign = $uty;
233 type UnsignedInt = $uty;
234
235 fn unsigned(self) -> $uty {
236 self as $uty
237 }
238
239 fn from_unsigned(me: $uty) -> Self {
240 me as $ity
241 }
242
243 fn abs_diff(self, other: Self) -> $uty {
244 self.wrapping_sub(other).wrapping_abs() as $uty
245 }
246
247 int_impl_common!($ity);
248 }
249 };
250}
251
252int_impl!(isize, usize);
253int_impl!(i8, u8);
254int_impl!(i16, u16);
255int_impl!(i32, u32);
256int_impl!(i64, u64);
257int_impl!(i128, u128);
258
259public_test_dep! {
260/// Trait for integers twice the bit width of another integer. This is implemented for all
261/// primitives except for `u8`, because there is not a smaller primitive.
262pub(crate) trait DInt: Int {
263 /// Integer that is half the bit width of the integer this trait is implemented for
264 type H: HInt<D = Self> + Int;
265
266 /// Returns the low half of `self`
267 fn lo(self) -> Self::H;
268 /// Returns the high half of `self`
269 fn hi(self) -> Self::H;
270 /// Returns the low and high halves of `self` as a tuple
271 fn lo_hi(self) -> (Self::H, Self::H);
272 /// Constructs an integer using lower and higher half parts
273 fn from_lo_hi(lo: Self::H, hi: Self::H) -> Self;
274}
275}
276
277public_test_dep! {
278/// Trait for integers half the bit width of another integer. This is implemented for all
279/// primitives except for `u128`, because it there is not a larger primitive.
280pub(crate) trait HInt: Int {
281 /// Integer that is double the bit width of the integer this trait is implemented for
282 type D: DInt<H = Self> + Int;
283
284 /// Widens (using default extension) the integer to have double bit width
285 fn widen(self) -> Self::D;
286 /// Widens (zero extension only) the integer to have double bit width. This is needed to get
287 /// around problems with associated type bounds (such as `Int<Othersign: DInt>`) being unstable
288 fn zero_widen(self) -> Self::D;
289 /// Widens the integer to have double bit width and shifts the integer into the higher bits
290 fn widen_hi(self) -> Self::D;
291 /// Widening multiplication with zero widening. This cannot overflow.
292 fn zero_widen_mul(self, rhs: Self) -> Self::D;
293 /// Widening multiplication. This cannot overflow.
294 fn widen_mul(self, rhs: Self) -> Self::D;
295}
296}
297
298macro_rules! impl_d_int {
299 ($($X:ident $D:ident),*) => {
300 $(
301 impl DInt for $D {
302 type H = $X;
303
304 fn lo(self) -> Self::H {
305 self as $X
306 }
307 fn hi(self) -> Self::H {
308 (self >> <$X as Int>::BITS) as $X
309 }
310 fn lo_hi(self) -> (Self::H, Self::H) {
311 (self.lo(), self.hi())
312 }
313 fn from_lo_hi(lo: Self::H, hi: Self::H) -> Self {
314 lo.zero_widen() | hi.widen_hi()
315 }
316 }
317 )*
318 };
319}
320
321macro_rules! impl_h_int {
322 ($($H:ident $uH:ident $X:ident),*) => {
323 $(
324 impl HInt for $H {
325 type D = $X;
326
327 fn widen(self) -> Self::D {
328 self as $X
329 }
330 fn zero_widen(self) -> Self::D {
331 (self as $uH) as $X
332 }
333 fn widen_hi(self) -> Self::D {
334 (self as $X) << <$H as Int>::BITS
335 }
336 fn zero_widen_mul(self, rhs: Self) -> Self::D {
337 self.zero_widen().wrapping_mul(rhs.zero_widen())
338 }
339 fn widen_mul(self, rhs: Self) -> Self::D {
340 self.widen().wrapping_mul(rhs.widen())
341 }
342 }
343 )*
344 };
345}
346
347impl_d_int!(u8 u16, u16 u32, u32 u64, u64 u128, i8 i16, i16 i32, i32 i64, i64 i128);
348impl_h_int!(
349 u8 u8 u16,
350 u16 u16 u32,
351 u32 u32 u64,
352 u64 u64 u128,
353 i8 u8 i16,
354 i16 u16 i32,
355 i32 u32 i64,
356 i64 u64 i128
357);
358
359public_test_dep! {
360/// Trait to express (possibly lossy) casting of integers
361pub(crate) trait CastInto<T: Copy>: Copy {
362 fn cast(self) -> T;
363}
364}
365
366macro_rules! cast_into {
367 ($ty:ty) => {
368 cast_into!($ty; usize, isize, u8, i8, u16, i16, u32, i32, u64, i64, u128, i128);
369 };
370 ($ty:ty; $($into:ty),*) => {$(
371 impl CastInto<$into> for $ty {
372 fn cast(self) -> $into {
373 self as $into
374 }
375 }
376 )*};
377}
378
379cast_into!(usize);
380cast_into!(isize);
381cast_into!(u8);
382cast_into!(i8);
383cast_into!(u16);
384cast_into!(i16);
385cast_into!(u32);
386cast_into!(i32);
387cast_into!(u64);
388cast_into!(i64);
389cast_into!(u128);
390cast_into!(i128);
391