Re: `u64` by `u64` div/mod in DRM QR for arm32

[Paolo Bonzini]

On 4/15/25 11:14, Jocelyn Falempe wrote:
For this case, the u64 divisor "pow" is a power of 10, so can have only 
a limited number of values. (17, and 9 of them can be used as u32).
Normally when the divisor is known at build time the compiler can 
replace the division by a multiplication and some bit shift.

so for 32bits machine, the match can be rewritten with constants, a bit 
like this:

If you add bindings to mul_u64_u64_shr from include/linux/math64.h, you 
can include the constants yourself:

pub struct MagicMul {
    mult: u64,
    shift: u32,
}

// Computed using the algorithm from Hacker's Delight, 2nd ed.
const DIV10: [MagicMul; 19] = [
    MagicMul { mult: 0x1, shift: 0 },
    MagicMul { mult: 0x6666666666666667u64, shift: 66 },
    MagicMul { mult: 0xA3D70A3D70A3D70Bu64, shift: 70 },
    MagicMul { mult: 0x20C49BA5E353F7CFu64, shift: 71 },
    MagicMul { mult: 0x346DC5D63886594Bu64, shift: 75 },
    MagicMul { mult: 0x29F16B11C6D1E109u64, shift: 78 },
    MagicMul { mult: 0x431BDE82D7B634DBu64, shift: 82 },
    MagicMul { mult: 0xD6BF94D5E57A42BDu64, shift: 87 },
    MagicMul { mult: 0x55E63B88C230E77Fu64, shift: 89 },
    MagicMul { mult: 0x112E0BE826D694B3u64, shift: 90 },
    MagicMul { mult: 0x036F9BFB3AF7B757u64, shift: 91 },
    MagicMul { mult: 0x00AFEBFF0BCB24ABu64, shift: 92 },
    MagicMul { mult: 0x232F33025BD42233u64, shift: 101 },
    MagicMul { mult: 0x384B84D092ED0385u64, shift: 105 },
    MagicMul { mult: 0x0B424DC35095CD81u64, shift: 106 },
    MagicMul { mult: 0x480EBE7B9D58566Du64, shift: 112 },
    MagicMul { mult: 0x39A5652FB1137857u64, shift: 115 },
    MagicMul { mult: 0x5C3BD5191B525A25u64, shift: 119 },
    MagicMul { mult: 0x12725DD1D243ABA1u64, shift: 120 },
];

const fn div10(val: u64, exp: u32) -> u64 {
    let MagicMul { mult, shift } = DIV10[exp as usize];
    mul_u64_u64_shr(val, mult, shift)
}

#[test]
fn test_div10() {
    assert_eq!(div10(12345678, 0), 12345678);
    assert_eq!(div10(12345678, 1), 1234567);
    assert_eq!(div10(12345678, 2), 123456);
    assert_eq!(div10(12345678, 3), 12345);
    assert_eq!(div10(12345678, 4), 1234);
    assert_eq!(div10(12345678, 5), 123);
    assert_eq!(div10(12345678, 6), 12);
    assert_eq!(div10(12345678, 7), 1);

    assert_eq!(div10(9876543298765432, 8), 98765432);
    assert_eq!(div10(9876543298765432, 9), 9876543);
    assert_eq!(div10(9876543298765432, 10), 987654);
    assert_eq!(div10(9876543298765432, 11), 98765);
    assert_eq!(div10(9876543298765432, 12), 9876);
    assert_eq!(div10(9876543298765432, 13), 987);
    assert_eq!(div10(9876543298765432, 14), 98);
    assert_eq!(div10(9876543298765432, 15), 9);

    assert_eq!(div10(12349876543298765432, 16), 1234);
    assert_eq!(div10(12349876543298765432, 17), 123);
    assert_eq!(div10(12349876543298765432, 18), 12);
}


I tried the test in userspace with this implementation of the
function:

#![feature(bigint_helper_methods)]
const fn mul_u64_u64_shr(m: u64, n: u64, s: u32) -> u64 {
    let (a, b) = m.widening_mul(n);
    if s == 0 {
        a
    } else if s < 64 {
        (a >> s) | (b << 64 - s)
    } else {
        b >> (s - 64)
    }
}


HTH,

Paolo