comphead commented on code in PR #12232:
URL: https://github.com/apache/arrow-rs/pull/12232#discussion_r4634463571
##########
arrow-buffer/src/divisor.rs:
##########
@@ -470,20 +513,367 @@ unsigned_divisor!(
u64,
u128
);
-signed_divisor!(
+/// Expands to the arguments of `signed_divisor!` that compute with `$wide`, a
type twice as wide
+/// as `$t`
+macro_rules! signed_divisor_wide {
+ ($name:ident, $power_of_two:ident, $add:ident, $t:ty, $wide:ty) => {
+ signed_divisor!(
+ $name,
+ $power_of_two,
+ $add,
+ $t,
+ [const],
+ // m = 1 + floor(2^(N + l - 1) / |divisor|) is between 2^(N - 1)
and 2^N, so m - 2^N
+ // fits in the narrow type
+ |magnitude, l| {
+ let m = 1 + (1 << (<$t>::BITS + l - 1)) / magnitude as $wide;
+ (m - (1 << <$t>::BITS)) as $t
+ },
+ // `n + MULSH(m', n)` in figure 5.1
+ |m, n| n + ((m as $wide * n as $wide) >> <$t>::BITS) as $t,
+ []
+ );
+ };
+}
+
+signed_divisor_wide!(
DivisorI32,
PowerOfTwoDivisorI32,
AddIndicatorDivisorI32,
i32,
i64
);
-signed_divisor!(
+signed_divisor_wide!(
DivisorI64,
PowerOfTwoDivisorI64,
AddIndicatorDivisorI64,
i64,
i128
);
+signed_divisor!(
+ DivisorI128,
+ PowerOfTwoDivisorI128,
+ AddIndicatorDivisorI128,
+ i128,
+ [],
+ // m = 1 + floor(2^(127 + l) / |divisor|), as for the narrower types.
2^(127 + l) is at most
+ // 2^254, so `i256` holds it, and the quotient is below 2^128
+ |magnitude, l| {
+ let pow = i256::ONE << (127 + l) as u8;
+ let (q, _) = pow.wrapping_div(i256::from_parts(magnitude,
0)).to_parts();
+ q.wrapping_add(1) as i128
+ },
+ // Figure 5.1 computes `n + MULSH(m', n)`, and `i128` has no wider type to
compute `MULSH`
+ // in. Section 3 of the paper gives `MULSH(x, y) = MULUH(x, y) - AND(x,
XSIGN(y))
+ // - AND(y, XSIGN(x))`, which is program (1) in section 8-3 of Warren,
"Hacker's Delight", 2nd
+ // edition. `m'` is negative for every divisor but 1 and -1, which are
powers of two, so
+ // `AND(n, XSIGN(m'))` is `n` and cancels the add, leaving `MULUH(m', n) -
AND(m', XSIGN(n))`
+ |m, n| (mulx(m as u128, n as u128).1 as i128).wrapping_sub((n >> 127) & m),
+ [
+ ///
+ /// When every value of a batch fits in `i64`, dividing in `i64` with
[`DivisorI64`] gives
+ /// the same results, except for a divisor of -1, because `i64::MIN /
-1` overflows in
+ /// `i64` but not in `i128`. A divisor that doesn't fit in `i64` gives
a quotient of 0 and
+ /// leaves the value as the remainder, except that `i64::MIN / 2^63`
is -1 with a
+ /// remainder of 0.
+ ///
+ /// ```
+ /// # use arrow_buffer::{DivisorI128, DivisorI64};
+ /// let values: Vec<i128> = vec![-12_345, 678, i64::MIN as i128];
+ /// let divisor: i128 = 100;
+ /// let narrow = values.iter().all(|n| i64::try_from(*n).is_ok());
+ /// let quotients: Vec<i128> = match i64::try_from(divisor) {
+ /// Ok(d) if narrow && d != -1 => {
+ /// let d = DivisorI64::new(d).unwrap();
+ /// values.iter().map(|n| d.wrapping_div_rem(*n as i64).0 as
i128).collect()
+ /// }
+ /// _ => {
+ /// let d = DivisorI128::new(divisor).unwrap();
+ /// values.iter().map(|n| d.wrapping_div_rem(*n).0).collect()
+ /// }
+ /// };
+ /// assert_eq!(quotients, [-123, 6, -92233720368547758]);
+ /// ```
+ ]
+);
+
+// `signed_divisor!` can't build `DivisorI256`, because `i256` has no `BITS`
or `unsigned_abs` and
+// its operators can't be called in a `const fn`. Its variants compute on the
parts of the values
+// with the helpers below `impl DivisorI256` instead
+divisor_enum!(
+ DivisorI256,
+ i256,
+ concat!(
+ "# use arrow_buffer::{i256, DivisorI256};\n",
+ "let values: Vec<i256> = [100, 7,
64].map(i256::from_i128).to_vec();\n",
+ "let quotients: Vec<_> = match
DivisorI256::new(i256::from_i128(7)).unwrap() {\n",
+ " DivisorI256::PowerOfTwo(d) => values.iter().map(move |n|
d.wrapping_div_rem(*n).0).collect(),\n",
+ " DivisorI256::AddIndicator(d) => values.iter().map(move |n|
d.wrapping_div_rem(*n).0).collect(),\n",
+ " d => values.iter().map(move |n|
d.wrapping_div_rem(*n).0).collect(),\n",
+ "};\n",
+ "assert_eq!(quotients, [14, 1, 9].map(i256::from_i128));",
+ ),
+ concat!(
+ "# use arrow_buffer::{i256, DivisorI256};\n",
+ "let divisor = DivisorI256::new(i256::from_i128(7)).unwrap();\n",
+ "let (q, r) = divisor.wrapping_div_rem(i256::from_i128(100));\n",
+ "assert_eq!((q, r), (i256::from_i128(14), i256::from_i128(2)));",
+ ),
+ "Unlike those of the other divisor types, they branch on the divisor's
shift. The shift is the same for every value, so the branch is predicted, and a
form without it was slower.",
+ [
+ ///
+ /// When every value of a batch fits in `i128`, dividing in `i128`
with [`DivisorI128`]
+ /// gives the same results, except for a divisor of -1, because
`i128::MIN / -1` overflows
+ /// in `i128` but not in `i256`. A divisor that doesn't fit in `i128`
gives a quotient of 0
+ /// and leaves the value as the remainder, except that `i128::MIN /
2^127` is -1 with a
+ /// remainder of 0.
+ ],
+ /// A divisor whose magnitude is a power of two
+ PowerOfTwo(PowerOfTwoDivisorI256),
+ /// Any other divisor
+ AddIndicator(AddIndicatorDivisorI256),
+);
+
+impl DivisorI256 {
+ /// Returns a divisor for `divisor`, or `None` if `divisor` is zero
+ ///
+ /// # Example
+ /// ```
+ /// # use arrow_buffer::{i256, DivisorI256};
+ /// assert!(DivisorI256::new(i256::ZERO).is_none());
+ /// ```
+ pub fn new(divisor: i256) -> Option<Self> {
+ if divisor == i256::ZERO {
+ return None;
+ }
+ Some(match PowerOfTwoDivisorI256::new(divisor) {
+ Some(d) => Self::PowerOfTwo(d),
+ None => Self::AddIndicator(AddIndicatorDivisorI256::new(divisor)),
+ })
+ }
+
+ /// Returns `(n / divisor, n % divisor)`, or `None` for `i256::MIN / -1`
+ ///
+ /// It matches on the variant on each call. Only [`Self::PowerOfTwo`] can
return `None`.
+ ///
+ /// # Example
+ /// ```
+ /// # use arrow_buffer::{i256, DivisorI256};
+ /// let divisor = DivisorI256::new(i256::from_i128(-7)).unwrap();
+ /// let qr = divisor.checked_div_rem(i256::from_i128(-100));
+ /// assert_eq!(qr, Some((i256::from_i128(14), i256::from_i128(-2))));
+ ///
+ /// let minus_one = DivisorI256::new(i256::MINUS_ONE).unwrap();
+ /// assert_eq!(minus_one.checked_div_rem(i256::MIN), None);
+ /// ```
+ #[inline]
+ pub const fn checked_div_rem(self, n: i256) -> Option<(i256, i256)> {
+ match self {
+ Self::PowerOfTwo(d) => d.checked_div_rem(n),
+ Self::AddIndicator(d) => Some(d.wrapping_div_rem(n)),
+ }
+ }
+}
+
+/// `i256` operations that a `const fn` can call, on the parts of the values.
`shr` is `SRA` from
+/// table 3.1 of Granlund and Montgomery for `0..=255` bits
+///
+/// It branches on the shift, see [`DivisorI256`]
+const fn shr(x: i256, shift: u32) -> i256 {
Review Comment:
`shr` is the same code as `impl Shr<u8> for i256` in `bigint/mod.rs`, branch
for branch, and `and`, `xor` and `not` are `&`, `^` and `!`. They exist so that
the `i256` `wrapping_div_rem` and `checked_div_rem` can be `const fn`, which
`divisor_enum!` requires. But `DivisorI256::new` isn't `const` and the variants
have private fields, so no caller can get a `DivisorI256` in a const context.
The `const` only commits the public API, and removing it later would be a
breaking change, while adding it later wouldn't be. The same holds for
`DivisorI128`. Could `divisor_enum!` take the optional `[const]` that
`signed_divisor!` already takes for `new`? Then the `i256` types could use the
operators and these four helpers could go.
##########
arrow-buffer/src/divisor.rs:
##########
@@ -586,6 +976,18 @@ mod tests {
divisors.retain(|d| *d != 0);
let mut values: Vec<$t> = vec![0, 1, -1, <$t>::MIN, <$t>::MAX,
<$t>::MIN + 1];
+ // Each side of every power of two, which includes the 64-bit
limbs of the
+ // multiply and the edges of the narrower types a kernel may
divide in instead,
+ // and the largest values of each decimal precision
+ for k in 0..bits - 1 {
Review Comment:
These loops over powers of two and ten build the same edges as the
`magnitudes` loops above (lines 961 to 969). Collecting the edges once, then
extending `magnitudes` with `[p - 1, p, p + 1]` and `values` with the six
signed neighbors, would compute them once. `test_divisor_i256` does the same
thing twice, in `magnitudes` (line 1044) and `edges` (line 1069), and could
share one `edges` list.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]