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

[Paolo Bonzini <pbonzini@redhat.com>]

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