Skip to main content

arrow_buffer/bigint/
div.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: See the NOTICE file distributed with this work for additional information regarding copyright ownership
3// SPDX-FileContributor: Licensed to the Apache Software Foundation (ASF) under one or more contributor license agreements
4
5//! N-digit division
6//!
7//! Implementation heavily inspired by [uint]
8//!
9//! [uint]: https://github.com/paritytech/parity-common/blob/d3a9327124a66e52ca1114bb8640c02c18c134b8/uint/src/uint.rs#L844
10
11/// Unsigned, little-endian, n-digit division with remainder
12///
13/// # Panics
14///
15/// Panics if divisor is zero
16pub fn div_rem<const N: usize>(numerator: &[u64; N], divisor: &[u64; N]) -> ([u64; N], [u64; N]) {
17    let numerator_bits = bits(numerator);
18    let divisor_bits = bits(divisor);
19    assert_ne!(divisor_bits, 0, "division by zero");
20
21    if numerator_bits < divisor_bits {
22        return ([0; N], *numerator);
23    }
24
25    if divisor_bits <= 64 {
26        return div_rem_small(numerator, divisor[0]);
27    }
28
29    let numerator_words = numerator_bits.div_ceil(64);
30    let divisor_words = divisor_bits.div_ceil(64);
31    let n = divisor_words;
32    let m = numerator_words - divisor_words;
33
34    div_rem_knuth(numerator, divisor, n, m)
35}
36
37/// Return the least number of bits needed to represent the number
38fn bits(arr: &[u64]) -> usize {
39    for (idx, v) in arr.iter().enumerate().rev() {
40        if *v > 0 {
41            return 64 - v.leading_zeros() as usize + 64 * idx;
42        }
43    }
44    0
45}
46
47/// Division of numerator by a u64 divisor
48fn div_rem_small<const N: usize>(numerator: &[u64; N], divisor: u64) -> ([u64; N], [u64; N]) {
49    // `div_rem_word` uses the `div` instruction only on x86_64 outside Miri, which can't run
50    // inline assembly. On every other 64-bit target it is a `u128` division, which calls
51    // `__udivti3` for every digit, so those targets divide with a reciprocal instead
52    #[cfg(all(target_pointer_width = "64", any(not(target_arch = "x86_64"), miri)))]
53    {
54        div_rem_small_reciprocal(numerator, divisor)
55    }
56
57    // x86_64 outside Miri keeps `div`. On 32-bit targets, including wasm32, each
58    // 64x64-to-128-bit product in the reciprocal path would call `__multi3`
59    #[cfg(not(all(target_pointer_width = "64", any(not(target_arch = "x86_64"), miri))))]
60    {
61        div_rem_small_word(numerator, divisor)
62    }
63}
64
65#[cfg(any(
66    test,
67    not(all(target_pointer_width = "64", any(not(target_arch = "x86_64"), miri)))
68))]
69fn div_rem_small_word<const N: usize>(numerator: &[u64; N], divisor: u64) -> ([u64; N], [u64; N]) {
70    let mut rem = 0u64;
71    let mut numerator = *numerator;
72    numerator.iter_mut().rev().for_each(|d| {
73        let (q, r) = div_rem_word(rem, *d, divisor);
74        *d = q;
75        rem = r;
76    });
77
78    let mut rem_padded = [0; N];
79    rem_padded[0] = rem;
80    (numerator, rem_padded)
81}
82
83/// Like [`div_rem_small_word`], but divides each digit by multiplying with a
84/// reciprocal of the divisor, computed once
85#[cfg(any(
86    test,
87    all(target_pointer_width = "64", any(not(target_arch = "x86_64"), miri))
88))]
89fn div_rem_small_reciprocal<const N: usize>(
90    numerator: &[u64; N],
91    divisor: u64,
92) -> ([u64; N], [u64; N]) {
93    // Shifting both operands so the divisor's top bit is set leaves the quotient unchanged
94    let shift = divisor.leading_zeros();
95    let divisor = divisor << shift;
96    let reciprocal = reciprocal_word(divisor);
97    let numerator = full_shl(numerator, shift);
98
99    // The top digit is below 2^shift, and so below the divisor
100    let mut rem = numerator[N];
101    let mut quotient = [0; N];
102    for i in (0..N).rev() {
103        let (q, r) = div_rem_word_reciprocal(rem, numerator[i], divisor, reciprocal);
104        quotient[i] = q;
105        rem = r;
106    }
107
108    let mut rem_padded = [0; N];
109    rem_padded[0] = rem >> shift;
110    (quotient, rem_padded)
111}
112
113/// Returns `floor((2^128 - 1) / divisor) - 2^64` for a divisor with its top bit set
114///
115/// This is algorithm 2 of [Möller and Granlund, "Improved division by invariant integers" (2011)](https://gmplib.org/~tege/division-paper.pdf),
116/// which avoids a `u128` division. It looks up an 11-bit approximation of `2^74 / divisor`,
117/// refines it with Newton iterations to 21, 34 and 65 bits, and then corrects the last bit.
118///
119/// The names follow the paper, where `vK` is the `K`th approximation
120#[cfg(any(
121    test,
122    all(target_pointer_width = "64", any(not(target_arch = "x86_64"), miri))
123))]
124fn reciprocal_word(divisor: u64) -> u64 {
125    debug_assert_eq!(divisor >> 63, 1);
126
127    // `floor((2^19 - 3 * 2^8) / d9)` for each value of the top 9 bits `d9`. The paper subtracts
128    // `3 * 2^8` to make the error bound of `v0` symmetric around zero
129    const TABLE: [u16; 256] = {
130        let mut table = [0; 256];
131        let mut i = 0;
132        while i < 256 {
133            table[i] = (((1 << 19) - 3 * (1 << 8)) / (i as u32 + 256)) as u16;
134            i += 1;
135        }
136        table
137    };
138
139    let d0 = divisor & 1; // Least significant bit
140    let d9 = divisor >> 55; // Most significant 9 bits
141    // `d40` and `d63` are rounded up, so they can equal 2^40 and 2^63
142    let d40 = (divisor >> 24) + 1; // Most significant 40 bits
143    let d63 = (divisor >> 1) + d0; // Most significant 63 bits
144
145    // `d9` is in 256..512, so masking gives `d9 - 256` without a bounds check
146    let v0 = u64::from(TABLE[(d9 & 0xff) as usize]);
147    // Each Newton iteration `x + x * (1 - x * d)` about doubles the bits of precision. The
148    // shifts scale `v1` to about `2^84 / divisor` and `v2` to about `2^97 / divisor`, and keep
149    // every product within a `u64`. The `- 1` makes `v1` an underestimate, so the next line's
150    // `2^60 - v1 * d40`, the error of `v1`, can't underflow
151    let v1 = (v0 << 11) - ((v0 * v0 * d40) >> 40) - 1;
152    let v2 = (v1 << 13) + ((v1 * ((1 << 60) - v1 * d40)) >> 47);
153    // The error of `v2`, `2^97 - v2 * divisor`, can take 65 bits, so this computes half of it
154    // as `2^96 - v2 * d63 + floor(v2 / 2) * d0`, which fits in 64 bits. The `2^96` term is
155    // zero modulo 2^64
156    let e = ((v2 >> 1) & d0.wrapping_neg()).wrapping_sub(v2.wrapping_mul(d63));
157    // `2^64 + v3` is about `2^128 / divisor`. The `2^64` bit is always set, so it isn't stored
158    let v3 = (v2 << 31).wrapping_add(((u128::from(v2) * u128::from(e)) >> 65) as u64);
159    // `v3` is the result or one less. `floor((v3 + 2^64 + 1) * divisor / 2^64)` is 2^64 in the
160    // first case and `2^64 - 1` in the second, so subtracting it modulo 2^64 adds the missing
161    // one. Adding `2^64 * divisor` as `divisor` after the shift keeps the product in a `u128`
162    let p = (((u128::from(v3) + 1) * u128::from(divisor)) >> 64) as u64;
163    v3.wrapping_sub(p.wrapping_add(divisor))
164}
165
166/// Divides `hi:lo` by a divisor with its top bit set, given its [`reciprocal_word`]
167///
168/// This is algorithm 4 of [Möller and Granlund, "Improved division by invariant integers" (2011)](https://gmplib.org/~tege/division-paper.pdf)
169#[cfg(any(
170    test,
171    all(target_pointer_width = "64", any(not(target_arch = "x86_64"), miri))
172))]
173#[inline]
174fn div_rem_word_reciprocal(hi: u64, lo: u64, divisor: u64, reciprocal: u64) -> (u64, u64) {
175    debug_assert!(hi < divisor);
176    debug_assert_eq!(divisor >> 63, 1);
177
178    // `(2^64 + reciprocal) * hi + lo` is below 2^128 because `hi < divisor`
179    let p = u128::from(reciprocal) * u128::from(hi) + ((u128::from(hi) << 64) | u128::from(lo));
180    // `q` is the quotient, one more, or one less
181    let mut q = ((p >> 64) as u64).wrapping_add(1);
182    let mut r = lo.wrapping_sub(q.wrapping_mul(divisor));
183    // The low word of `p` tells whether `q` was one too large
184    if r > p as u64 {
185        q = q.wrapping_sub(1);
186        r = r.wrapping_add(divisor);
187    }
188    // `q` was one too small, which is rare
189    if r >= divisor {
190        q += 1;
191        r -= divisor;
192    }
193    (q, r)
194}
195
196/// Use Knuth Algorithm D to compute `numerator / divisor` returning the
197/// quotient and remainder
198///
199/// `n` is the number of non-zero 64-bit words in `divisor`
200/// `m` is the number of non-zero 64-bit words present in `numerator` beyond `divisor`, and
201/// therefore the number of words in the quotient
202///
203/// A good explanation of the algorithm can be found [here](https://ridiculousfish.com/blog/posts/labor-of-division-episode-iv.html)
204fn div_rem_knuth<const N: usize>(
205    numerator: &[u64; N],
206    divisor: &[u64; N],
207    n: usize,
208    m: usize,
209) -> ([u64; N], [u64; N]) {
210    assert!(n + m <= N);
211
212    // The algorithm works by incrementally generating guesses `q_hat`, for the next digit
213    // of the quotient, starting from the most significant digit.
214    //
215    // This relies on the property that for any `q_hat` where
216    //
217    //      (q_hat << (j * 64)) * divisor <= numerator`
218    //
219    // We can set
220    //
221    //      q += q_hat << (j * 64)
222    //      numerator -= (q_hat << (j * 64)) * divisor
223    //
224    // And then iterate until `numerator < divisor`
225
226    // We normalize the divisor so that the highest bit in the highest digit of the
227    // divisor is set, this ensures our initial guess of `q_hat` is at most 2 off from
228    // the correct value for q[j]
229    let shift = divisor[n - 1].leading_zeros();
230    // As the shift is computed based on leading zeros, don't need to perform full_shl
231    let divisor = shl_word(divisor, shift);
232    // numerator may have fewer leading zeros than divisor, so must add another digit
233    let mut numerator = full_shl(numerator, shift);
234
235    // The two most significant digits of the divisor
236    let b0 = divisor[n - 1];
237    let b1 = divisor[n - 2];
238
239    let mut q = [0; N];
240
241    for j in (0..=m).rev() {
242        let a0 = numerator[j + n];
243        let a1 = numerator[j + n - 1];
244
245        let mut q_hat = if a0 < b0 {
246            // The first estimate is [a1, a0] / b0, it may be too large by at most 2
247            let (mut q_hat, mut r_hat) = div_rem_word(a0, a1, b0);
248
249            // r_hat = [a1, a0] - q_hat * b0
250            //
251            // Now we want to compute a more precise estimate [a2,a1,a0] / [b1,b0]
252            // which can only be less or equal to the current q_hat
253            //
254            // q_hat is too large if:
255            // [a2,a1,a0] < q_hat * [b1,b0]
256            // [a2,r_hat] < q_hat * b1
257            let a2 = numerator[j + n - 2];
258            loop {
259                let r = u128::from(q_hat) * u128::from(b1);
260                let (lo, hi) = (r as u64, (r >> 64) as u64);
261                if (hi, lo) <= (r_hat, a2) {
262                    break;
263                }
264
265                q_hat -= 1;
266                let (new_r_hat, overflow) = r_hat.overflowing_add(b0);
267                r_hat = new_r_hat;
268
269                if overflow {
270                    break;
271                }
272            }
273            q_hat
274        } else {
275            u64::MAX
276        };
277
278        // q_hat is now either the correct quotient digit, or in rare cases 1 too large
279
280        // Compute numerator -= (q_hat * divisor) << (j * 64)
281        let q_hat_v = full_mul_u64(&divisor, q_hat);
282        let c = sub_assign(&mut numerator[j..], &q_hat_v[..n + 1]);
283
284        // If underflow, q_hat was too large by 1
285        if c {
286            // Reduce q_hat by 1
287            q_hat -= 1;
288
289            // Add back one multiple of divisor
290            let c = add_assign(&mut numerator[j..], &divisor[..n]);
291            numerator[j + n] = numerator[j + n].wrapping_add(u64::from(c));
292        }
293
294        // q_hat is the correct value for q[j]
295        q[j] = q_hat;
296    }
297
298    // The remainder is what is left in numerator, with the initial normalization shl reversed
299    let remainder = full_shr(&numerator, shift);
300    (q, remainder)
301}
302
303/// Perform narrowing division of a u128 by a u64 divisor, returning the quotient and remainder
304///
305/// This method may trap or panic if hi >= divisor, i.e. the quotient would not fit
306/// into a 64-bit integer
307fn div_rem_word(hi: u64, lo: u64, divisor: u64) -> (u64, u64) {
308    debug_assert!(hi < divisor);
309    debug_assert_ne!(divisor, 0);
310
311    // LLVM fails to use the div instruction as it is not able to prove
312    // that hi < divisor, and therefore the result will fit into 64-bits
313    #[cfg(all(target_arch = "x86_64", not(miri)))]
314    unsafe {
315        let mut quot = lo;
316        let mut rem = hi;
317        std::arch::asm!(
318            "div {divisor}",
319            divisor = in(reg) divisor,
320            inout("rax") quot,
321            inout("rdx") rem,
322            options(pure, nomem, nostack)
323        );
324        (quot, rem)
325    }
326    #[cfg(any(not(target_arch = "x86_64"), miri))]
327    {
328        let x = (u128::from(hi) << 64) + u128::from(lo);
329        let y = u128::from(divisor);
330        ((x / y) as u64, (x % y) as u64)
331    }
332}
333
334/// Perform `a += b`
335fn add_assign(a: &mut [u64], b: &[u64]) -> bool {
336    binop_slice(a, b, u64::overflowing_add)
337}
338
339/// Perform `a -= b`
340fn sub_assign(a: &mut [u64], b: &[u64]) -> bool {
341    binop_slice(a, b, u64::overflowing_sub)
342}
343
344/// Converts an overflowing binary operation on scalars to one on slices
345fn binop_slice(a: &mut [u64], b: &[u64], binop: impl Fn(u64, u64) -> (u64, bool) + Copy) -> bool {
346    let mut c = false;
347    a.iter_mut().zip(b.iter()).for_each(|(x, y)| {
348        let (res1, overflow1) = y.overflowing_add(u64::from(c));
349        let (res2, overflow2) = binop(*x, res1);
350        *x = res2;
351        c = overflow1 || overflow2;
352    });
353    c
354}
355
356/// Widening multiplication of an N-digit array with a u64
357fn full_mul_u64<const N: usize>(a: &[u64; N], b: u64) -> ArrayPlusOne<u64, N> {
358    let mut carry = 0;
359    let mut out = [0; N];
360    out.iter_mut().zip(a).for_each(|(o, v)| {
361        let r = *v as u128 * b as u128 + carry as u128;
362        *o = r as u64;
363        carry = (r >> 64) as u64;
364    });
365    ArrayPlusOne(out, carry)
366}
367
368/// Left shift of an N-digit array by at most 63 bits
369fn shl_word<const N: usize>(v: &[u64; N], shift: u32) -> [u64; N] {
370    full_shl(v, shift).0
371}
372
373/// Widening left shift of an N-digit array by at most 63 bits
374fn full_shl<const N: usize>(v: &[u64; N], shift: u32) -> ArrayPlusOne<u64, N> {
375    debug_assert!(shift < 64);
376    if shift == 0 {
377        return ArrayPlusOne(*v, 0);
378    }
379    let mut out = [0u64; N];
380    out[0] = v[0] << shift;
381    for i in 1..N {
382        out[i] = (v[i - 1] >> (64 - shift)) | (v[i] << shift)
383    }
384    let carry = v[N - 1] >> (64 - shift);
385    ArrayPlusOne(out, carry)
386}
387
388/// Narrowing right shift of an (N+1)-digit array by at most 63 bits
389fn full_shr<const N: usize>(a: &ArrayPlusOne<u64, N>, shift: u32) -> [u64; N] {
390    debug_assert!(shift < 64);
391    if shift == 0 {
392        return a.0;
393    }
394    let mut out = [0; N];
395    for i in 0..N - 1 {
396        out[i] = (a[i] >> shift) | (a[i + 1] << (64 - shift))
397    }
398    out[N - 1] = a[N - 1] >> shift;
399    out
400}
401
402/// An array of N + 1 elements
403///
404/// This is a hack around lack of support for const arithmetic
405#[repr(C)]
406struct ArrayPlusOne<T, const N: usize>([T; N], T);
407
408impl<T, const N: usize> std::ops::Deref for ArrayPlusOne<T, N> {
409    type Target = [T];
410
411    #[inline]
412    fn deref(&self) -> &Self::Target {
413        let x = std::ptr::from_ref::<Self>(self);
414        unsafe { std::slice::from_raw_parts(x.cast::<T>(), N + 1) }
415    }
416}
417
418impl<T, const N: usize> std::ops::DerefMut for ArrayPlusOne<T, N> {
419    fn deref_mut(&mut self) -> &mut Self::Target {
420        let x = std::ptr::from_mut::<Self>(self);
421        unsafe { std::slice::from_raw_parts_mut(x.cast::<T>(), N + 1) }
422    }
423}
424
425#[cfg(test)]
426mod tests {
427    use super::*;
428    use rand::{RngExt, SeedableRng, rngs::StdRng};
429
430    fn check_div_rem_small<const N: usize>(numerator: [u64; N], divisor: u64) {
431        let expected = div_rem_small_word(&numerator, divisor);
432        assert_eq!(
433            div_rem_small_reciprocal(&numerator, divisor),
434            expected,
435            "{numerator:?} / {divisor}"
436        );
437    }
438
439    #[test]
440    fn test_reciprocal_word() {
441        let mut divisors = vec![1 << 63, (1 << 63) + 1, u64::MAX - 1, u64::MAX];
442        // Each boundary between entries of the lookup table
443        for i in 257..512u64 {
444            divisors.extend([(i << 55) - 1, i << 55, (i << 55) + 1]);
445        }
446        let mut rng = StdRng::seed_from_u64(42);
447        divisors.extend((0..100_000).map(|_| rng.random::<u64>() | (1 << 63)));
448        for divisor in divisors {
449            let n = (u128::from(!divisor) << 64) | u128::from(u64::MAX);
450            let expected = (n / u128::from(divisor)) as u64;
451            assert_eq!(reciprocal_word(divisor), expected, "{divisor}");
452        }
453    }
454
455    #[test]
456    fn test_div_rem_word_reciprocal() {
457        // The reciprocal of 2^63 + 2 is 2^64 - 8, so the estimate for
458        // (2^127 + 2^64 - 1) / (2^63 + 2) is 2^64 - 3. That is one below the quotient
459        // 2^64 - 2, so the second correction runs. Random inputs rarely reach it.
460        let (hi, lo, divisor) = (1 << 63, u64::MAX, (1 << 63) + 2);
461        assert_eq!(reciprocal_word(divisor), u64::MAX - 7);
462        let n = (u128::from(hi) << 64) | u128::from(lo);
463        let d = u128::from(divisor);
464        assert_eq!(
465            div_rem_word_reciprocal(hi, lo, divisor, reciprocal_word(divisor)),
466            ((n / d) as u64, (n % d) as u64)
467        );
468
469        let mut rng = StdRng::seed_from_u64(42);
470        let mut divisors = vec![1 << 63, (1 << 63) + 1, u64::MAX - 1, u64::MAX];
471        divisors.extend((0..100).map(|_| rng.random::<u64>() | (1 << 63)));
472        for divisor in divisors {
473            let reciprocal = reciprocal_word(divisor);
474            let mut his = vec![0, 1, divisor / 2, divisor - 1];
475            his.extend((0..20).map(|_| rng.random_range(0..divisor)));
476            for hi in his {
477                let mut los = vec![0, 1, divisor - 1, divisor, u64::MAX];
478                los.extend((0..20).map(|_| rng.random::<u64>()));
479                for lo in los {
480                    let n = (u128::from(hi) << 64) | u128::from(lo);
481                    let d = u128::from(divisor);
482                    let expected = ((n / d) as u64, (n % d) as u64);
483                    assert_eq!(
484                        div_rem_word_reciprocal(hi, lo, divisor, reciprocal),
485                        expected,
486                        "{n} / {divisor}"
487                    );
488                }
489            }
490        }
491    }
492
493    #[test]
494    fn test_div_rem_small_reciprocal() {
495        let mut rng = StdRng::seed_from_u64(42);
496        let numerators = [
497            [0; 4],
498            [1, 0, 0, 0],
499            [0, 0, 0, 1],
500            [u64::MAX; 4],
501            [0, 0, 0, u64::MAX],
502            [u64::MAX, 0, 0, 0],
503            rng.random(),
504        ];
505        // Every normalization shift, with divisors at and next to each power of two
506        for shift in 0..64 {
507            let p = 1u64 << shift;
508            let mut divisors = vec![p, p.wrapping_mul(2).wrapping_sub(1)];
509            divisors.extend(p.checked_add(1));
510            divisors.extend(p.checked_sub(1).filter(|d| *d != 0));
511            for divisor in divisors {
512                for numerator in numerators {
513                    check_div_rem_small(numerator, divisor);
514                    check_div_rem_small([numerator[0], numerator[1]], divisor);
515                    check_div_rem_small([numerator[0]], divisor);
516                }
517            }
518        }
519        // Powers of ten, as used when rescaling decimals
520        for k in 0..=19 {
521            let p = 10u64.pow(k);
522            for divisor in [p - 1, p, p + 1].into_iter().filter(|d| *d != 0) {
523                for numerator in numerators {
524                    check_div_rem_small(numerator, divisor);
525                }
526            }
527        }
528        for _ in 0..1000 {
529            let divisor = rng.random::<u64>() >> rng.random_range(0..64);
530            if divisor != 0 {
531                check_div_rem_small(rng.random::<[u64; 4]>(), divisor);
532            }
533        }
534    }
535}