pub use self::leading_zeros::__clzsi2;
/// Trait for some basic operations on integers
-pub(crate) trait Int:
+#[doc(hidden)]
+pub trait Int:
Copy
+ PartialEq
+ PartialOrd
+ ops::AddAssign
+ ops::BitAndAssign
+ ops::BitOrAssign
+ + ops::BitXorAssign
+ ops::ShlAssign<i32>
+ ops::ShrAssign<u32>
+ ops::Add<Output = Self>
const ZERO: Self;
const ONE: Self;
+ const MIN: Self;
+
+ /// LUT used for maximizing the space covered and minimizing the computational cost of fuzzing
+ /// in `testcrate`. For example, Self = u128 produces [0,1,2,7,8,15,16,31,32,63,64,95,96,111,
+ /// 112,119,120,125,126,127].
+ const FUZZ_LENGTHS: [u8; 20];
+ /// The number of entries of `FUZZ_LENGTHS` actually used. The maximum is 20 for u128.
+ const FUZZ_NUM: usize;
/// Extracts the sign from self and returns a tuple.
///
fn from_bool(b: bool) -> Self;
+ /// Prevents the need for excessive conversions between signed and unsigned
+ fn logical_shr(self, other: u32) -> Self;
+
+ /// Absolute difference between two integers.
+ fn abs_diff(self, other: Self) -> Self::UnsignedInt;
+
// copied from primitive integers, but put in a trait
+ fn is_zero(self) -> bool;
fn max_value() -> Self;
fn min_value() -> Self;
+ fn wrapping_neg(self) -> Self;
fn wrapping_add(self, other: Self) -> Self;
fn wrapping_mul(self, other: Self) -> Self;
fn wrapping_sub(self, other: Self) -> Self;
fn wrapping_shl(self, other: u32) -> Self;
+ fn wrapping_shr(self, other: u32) -> Self;
+ fn rotate_left(self, other: u32) -> Self;
fn overflowing_add(self, other: Self) -> (Self, bool);
fn aborting_div(self, other: Self) -> Self;
fn aborting_rem(self, other: Self) -> Self;
const ZERO: Self = 0;
const ONE: Self = 1;
+ const MIN: Self = <Self>::MIN;
+
+ const FUZZ_LENGTHS: [u8; 20] = {
+ let bits = <Self as Int>::BITS;
+ let mut v = [0u8; 20];
+ v[0] = 0;
+ v[1] = 1;
+ v[2] = 2; // important for parity and the iX::MIN case when reversed
+ let mut i = 3;
+ // No need for any more until the byte boundary, because there should be no algorithms
+ // that are sensitive to anything not next to byte boundaries after 2. We also scale
+ // in powers of two, which is important to prevent u128 corner tests from getting too
+ // big.
+ let mut l = 8;
+ loop {
+ if l >= ((bits / 2) as u8) {
+ break;
+ }
+ // get both sides of the byte boundary
+ v[i] = l - 1;
+ i += 1;
+ v[i] = l;
+ i += 1;
+ l *= 2;
+ }
+
+ if bits != 8 {
+ // add the lower side of the middle boundary
+ v[i] = ((bits / 2) - 1) as u8;
+ i += 1;
+ }
+
+ // We do not want to jump directly from the Self::BITS/2 boundary to the Self::BITS
+ // boundary because of algorithms that split the high part up. We reverse the scaling
+ // as we go to Self::BITS.
+ let mid = i;
+ let mut j = 1;
+ loop {
+ v[i] = (bits as u8) - (v[mid - j]) - 1;
+ if j == mid {
+ break;
+ }
+ i += 1;
+ j += 1;
+ }
+ v
+ };
+
+ const FUZZ_NUM: usize = {
+ let log2 = (<Self as Int>::BITS - 1).count_ones() as usize;
+ if log2 == 3 {
+ // case for u8
+ 6
+ } else {
+ // 3 entries on each extreme, 2 in the middle, and 4 for each scale of intermediate
+ // boundaries.
+ 8 + (4 * (log2 - 4))
+ }
+ };
fn from_bool(b: bool) -> Self {
b as $ty
}
+ fn logical_shr(self, other: u32) -> Self {
+ Self::from_unsigned(self.unsigned().wrapping_shr(other))
+ }
+
+ fn is_zero(self) -> bool {
+ self == Self::ZERO
+ }
+
fn max_value() -> Self {
<Self>::max_value()
}
<Self>::min_value()
}
+ fn wrapping_neg(self) -> Self {
+ <Self>::wrapping_neg(self)
+ }
+
fn wrapping_add(self, other: Self) -> Self {
<Self>::wrapping_add(self, other)
}
<Self>::wrapping_shl(self, other)
}
+ fn wrapping_shr(self, other: u32) -> Self {
+ <Self>::wrapping_shr(self, other)
+ }
+
+ fn rotate_left(self, other: u32) -> Self {
+ <Self>::rotate_left(self, other)
+ }
+
fn overflowing_add(self, other: Self) -> (Self, bool) {
<Self>::overflowing_add(self, other)
}
me
}
+ fn abs_diff(self, other: Self) -> Self {
+ (self.wrapping_sub(other) as $ity).wrapping_abs() as $uty
+ }
+
int_impl_common!($uty, $bits);
}
me as $ity
}
+ fn abs_diff(self, other: Self) -> $uty {
+ self.wrapping_sub(other).wrapping_abs() as $uty
+ }
+
int_impl_common!($ity, $bits);
}
};
}
+int_impl!(isize, usize, usize::MAX.count_ones());
+int_impl!(i8, u8, 8);
int_impl!(i16, u16, 16);
int_impl!(i32, u32, 32);
int_impl!(i64, u64, 64);
int_impl!(i128, u128, 128);
-/// Trait to convert an integer to/from smaller parts
-pub(crate) trait LargeInt: Int {
- type LowHalf: Int;
- type HighHalf: Int;
+/// Trait for integers twice the bit width of another integer. This is implemented for all
+/// primitives except for `u8`, because there is not a smaller primitive.
+#[doc(hidden)]
+pub trait DInt: Int {
+ /// Integer that is half the bit width of the integer this trait is implemented for
+ type H: HInt<D = Self> + Int;
+
+ /// Returns the low half of `self`
+ fn lo(self) -> Self::H;
+ /// Returns the high half of `self`
+ fn hi(self) -> Self::H;
+ /// Returns the low and high halves of `self` as a tuple
+ fn lo_hi(self) -> (Self::H, Self::H);
+ /// Constructs an integer using lower and higher half parts
+ fn from_lo_hi(lo: Self::H, hi: Self::H) -> Self;
+}
- fn low(self) -> Self::LowHalf;
- fn low_as_high(low: Self::LowHalf) -> Self::HighHalf;
- fn high(self) -> Self::HighHalf;
- fn high_as_low(low: Self::HighHalf) -> Self::LowHalf;
- fn from_parts(low: Self::LowHalf, high: Self::HighHalf) -> Self;
+/// Trait for integers half the bit width of another integer. This is implemented for all
+/// primitives except for `u128`, because it there is not a larger primitive.
+#[doc(hidden)]
+pub trait HInt: Int {
+ /// Integer that is double the bit width of the integer this trait is implemented for
+ type D: DInt<H = Self> + Int;
+
+ /// Widens (using default extension) the integer to have double bit width
+ fn widen(self) -> Self::D;
+ /// Widens (zero extension only) the integer to have double bit width. This is needed to get
+ /// around problems with associated type bounds (such as `Int<Othersign: DInt>`) being unstable
+ fn zero_widen(self) -> Self::D;
+ /// Widens the integer to have double bit width and shifts the integer into the higher bits
+ fn widen_hi(self) -> Self::D;
+ /// Widening multiplication with zero widening. This cannot overflow.
+ fn zero_widen_mul(self, rhs: Self) -> Self::D;
+ /// Widening multiplication. This cannot overflow.
+ fn widen_mul(self, rhs: Self) -> Self::D;
}
-macro_rules! large_int {
- ($ty:ty, $tylow:ty, $tyhigh:ty, $halfbits:expr) => {
- impl LargeInt for $ty {
- type LowHalf = $tylow;
- type HighHalf = $tyhigh;
+macro_rules! impl_d_int {
+ ($($X:ident $D:ident),*) => {
+ $(
+ impl DInt for $D {
+ type H = $X;
- fn low(self) -> $tylow {
- self as $tylow
- }
- fn low_as_high(low: $tylow) -> $tyhigh {
- low as $tyhigh
- }
- fn high(self) -> $tyhigh {
- (self >> $halfbits) as $tyhigh
- }
- fn high_as_low(high: $tyhigh) -> $tylow {
- high as $tylow
+ fn lo(self) -> Self::H {
+ self as $X
+ }
+ fn hi(self) -> Self::H {
+ (self >> <$X as Int>::BITS) as $X
+ }
+ fn lo_hi(self) -> (Self::H, Self::H) {
+ (self.lo(), self.hi())
+ }
+ fn from_lo_hi(lo: Self::H, hi: Self::H) -> Self {
+ lo.zero_widen() | hi.widen_hi()
+ }
}
- fn from_parts(low: $tylow, high: $tyhigh) -> $ty {
- low as $ty | ((high as $ty) << $halfbits)
+ )*
+ };
+}
+
+macro_rules! impl_h_int {
+ ($($H:ident $uH:ident $X:ident),*) => {
+ $(
+ impl HInt for $H {
+ type D = $X;
+
+ fn widen(self) -> Self::D {
+ self as $X
+ }
+ fn zero_widen(self) -> Self::D {
+ (self as $uH) as $X
+ }
+ fn widen_hi(self) -> Self::D {
+ (self as $X) << <$H as Int>::BITS
+ }
+ fn zero_widen_mul(self, rhs: Self) -> Self::D {
+ self.zero_widen().wrapping_mul(rhs.zero_widen())
+ }
+ fn widen_mul(self, rhs: Self) -> Self::D {
+ self.widen().wrapping_mul(rhs.widen())
+ }
}
- }
+ )*
};
}
-large_int!(u32, u16, u16, 16);
-large_int!(i32, u16, i16, 16);
-large_int!(u64, u32, u32, 32);
-large_int!(i64, u32, i32, 32);
-large_int!(u128, u64, u64, 64);
-large_int!(i128, u64, i64, 64);
+impl_d_int!(u8 u16, u16 u32, u32 u64, u64 u128, i8 i16, i16 i32, i32 i64, i64 i128);
+impl_h_int!(
+ u8 u8 u16,
+ u16 u16 u32,
+ u32 u32 u64,
+ u64 u64 u128,
+ i8 u8 i16,
+ i16 u16 i32,
+ i32 u32 i64,
+ i64 u64 i128
+);
/// Trait to express (possibly lossy) casting of integers
pub(crate) trait CastInto<T: Copy>: Copy {
cast_into!(i64);
cast_into!(u128);
cast_into!(i128);
-
-pub(crate) trait WideInt: Int {
- type Output: Int;
-
- fn wide_mul(self, other: Self) -> (Self, Self);
- fn wide_shift_left(&mut self, low: &mut Self, count: i32);
- fn wide_shift_right_with_sticky(&mut self, low: &mut Self, count: i32);
-}
-
-macro_rules! impl_wide_int {
- ($ty:ty, $tywide:ty, $bits:expr) => {
- impl WideInt for $ty {
- type Output = $ty;
-
- fn wide_mul(self, other: Self) -> (Self, Self) {
- let product = (self as $tywide).wrapping_mul(other as $tywide);
- ((product >> ($bits as $ty)) as $ty, product as $ty)
- }
-
- fn wide_shift_left(&mut self, low: &mut Self, count: i32) {
- *self = (*self << count) | (*low >> ($bits - count));
- *low = *low << count;
- }
-
- fn wide_shift_right_with_sticky(&mut self, low: &mut Self, count: i32) {
- if count < $bits {
- let sticky = *low << ($bits - count);
- *low = *self << ($bits - count) | *low >> count | sticky;
- *self = *self >> count;
- } else if count < 2 * $bits {
- let sticky = *self << (2 * $bits - count) | *low;
- *low = *self >> (count - $bits) | sticky;
- *self = 0;
- } else {
- let sticky = *self | *low;
- *self = sticky;
- *self = 0;
- }
- }
- }
- };
-}
-
-impl_wide_int!(u32, u64, 32);
-impl_wide_int!(u64, u128, 64);
projects / rustc.git / blobdiff