mbutrovich commented on code in PR #12232:
URL: https://github.com/apache/arrow-rs/pull/12232#discussion_r4588583614


##########
arrow-buffer/src/divisor.rs:
##########
@@ -470,20 +513,389 @@ 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, so the `i256` variants branch on the divisor, 
unlike the other
+/// divisor types. The shift is the same for every value, so the branch is 
predicted. A

Review Comment:
   Done. The explanation lives in the `DivisorI256` docs, and `shr` points 
there.



##########
arrow-buffer/src/divisor.rs:
##########
@@ -470,20 +513,389 @@ 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 {

Review Comment:
   > Since `i256` is already hand-written, would writing 
`AddIndicatorDivisorI128` by hand (or passing just a multiplier fn and a mulsh 
fn) let the existing macros stay as they were?
   
   The `i128` divisor differs from the 32-bit and 64-bit ones only in how it 
computes the multiplier and `MULSH`. The macro takes those two as arguments, so 
the `signed_divisor!` call for `DivisorI128` shows only what's new, and the 
rest is code that #11467 already reviewed.
   
   Writing `AddIndicatorDivisorI128` by hand wouldn't leave the existing macros 
as they were. `signed_divisor!` generates `AddIndicator` along with the enum 
and `PowerOfTwo`, so the macro would have to stop generating it for `i32` and 
`i64` too, and those would move into another macro. Writing all of 
`DivisorI128` by hand would copy about 180 lines of the macro body, including a 
`PowerOfTwo` that is the same for every width.
   
   The `|magnitude, l| ...` arguments follow the form 
[`n_bit_divisor!`](https://github.com/apache/arrow-rs/blob/d1efb23dc1fbb0046d61fc9ab816a50f8ee0bba9/arrow-buffer/src/divisor.rs#L68-L73)
 already uses for `Up` and `Down`, because a `const fn` can't call a closure. 
Passing named `const fn`s instead would work, but it would add two helper 
functions per width, so I'd keep the expressions.
   
   The `divisor_enum!` arm that takes the examples and `$branch_doc` is there 
for `DivisorI256`, which needs `i256` examples and branches on the shift. It 
would stay either way.
   



-- 
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]

Reply via email to