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

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

[Miguel Ojeda]

Hi Jocelyn, Christian,

I started build-testing arm 32-bit within my other usual routine
tests, and I hit:

    ld.lld: error: undefined symbol: __aeabi_uldivmod
    >>> referenced by drm_panic_qr.rs:417 (drivers/gpu/drm/drm_panic_qr.rs:417)
    >>> drivers/gpu/drm/drm_panic_qr.o:(<drm_panic_qr::SegmentIterator
as core::iter::traits::iterator::Iterator>::next) in archive vmlinux.a

which comes from both these `u64` by `u64`:

    let out = (self.carry / pow) as u16;
    self.carry = self.carry % pow;

Christian: I guess we can offer a set of `div64` functions using the C
ones, at least for the time being, and eventually wire the actual
operator with some support from upstream Rust. Or do you have
something else in mind? (i.e. I think you have been discussing
intrinsics lately)

Thanks!

Cheers,
Miguel

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

[Christian Schrefl]

Hi Miguel,

On 14.04.25 8:14 PM, Miguel Ojeda wrote:
> Hi Jocelyn, Christian,
> 
> I started build-testing arm 32-bit within my other usual routine
> tests, and I hit:
> 
>     ld.lld: error: undefined symbol: __aeabi_uldivmod
>     >>> referenced by drm_panic_qr.rs:417 (drivers/gpu/drm/drm_panic_qr.rs:417)
>     >>> drivers/gpu/drm/drm_panic_qr.o:(<drm_panic_qr::SegmentIterator
> as core::iter::traits::iterator::Iterator>::next) in archive vmlinux.a
> 
> which comes from both these `u64` by `u64`:
> 
>     let out = (self.carry / pow) as u16;
>     self.carry = self.carry % pow;
> 
> Christian: I guess we can offer a set of `div64` functions using the C
> ones, at least for the time being, and eventually wire the actual
> operator with some support from upstream Rust. Or do you have
> something else in mind? (i.e. I think you have been discussing
> intrinsics lately)

I think using the C implementations is fine. Not sure how much the
FFI is going to matter for performance, but it should be rare enough
that is shouldn't matter (and hopefully we will get cross lang LTO 
or something similar at some point).

We could also just implement the intrinsic(s) ourselves, but then 
the u64 divisions would be implicit which is probably undesired.
We could also rename the intrinsics so they are only usable from 
specific crates. 

I think we need the opinion of the some arm people here.

CC Russell King and Linus Walleij.


I'm not sure what could be done in upstream rust to help here
and that would probably need be a very specific features for the
kernel.


Cheers
Chrisitan

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

[Russell King (Oracle)]

On Mon, Apr 14, 2025 at 09:21:42PM +0200, Christian Schrefl wrote:
> Hi Miguel,
> 
> On 14.04.25 8:14 PM, Miguel Ojeda wrote:
> > Hi Jocelyn, Christian,
> > 
> > I started build-testing arm 32-bit within my other usual routine
> > tests, and I hit:
> > 
> >     ld.lld: error: undefined symbol: __aeabi_uldivmod
> >     >>> referenced by drm_panic_qr.rs:417 (drivers/gpu/drm/drm_panic_qr.rs:417)
> >     >>> drivers/gpu/drm/drm_panic_qr.o:(<drm_panic_qr::SegmentIterator
> > as core::iter::traits::iterator::Iterator>::next) in archive vmlinux.a
> > 
> > which comes from both these `u64` by `u64`:
> > 
> >     let out = (self.carry / pow) as u16;
> >     self.carry = self.carry % pow;
> > 
> > Christian: I guess we can offer a set of `div64` functions using the C
> > ones, at least for the time being, and eventually wire the actual
> > operator with some support from upstream Rust. Or do you have
> > something else in mind? (i.e. I think you have been discussing
> > intrinsics lately)
> 
> I think using the C implementations is fine. Not sure how much the
> FFI is going to matter for performance, but it should be rare enough
> that is shouldn't matter (and hopefully we will get cross lang LTO 
> or something similar at some point).
> 
> We could also just implement the intrinsic(s) ourselves, but then 
> the u64 divisions would be implicit which is probably undesired.
> We could also rename the intrinsics so they are only usable from 
> specific crates. 
> 
> I think we need the opinion of the some arm people here.
> 
> CC Russell King and Linus Walleij.

The kernel has had the general position that u64 by u64 division is
silly and isn't supported. Several 32-bit architectures including
32-bit ARM don't support it.

-- 
RMK's Patch system: https://www.armlinux.org.uk/developer/patches/
FTTP is here! 80Mbps down 10Mbps up. Decent connectivity at last!

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

[Jocelyn Falempe]

On 14/04/2025 21:46, Russell King (Oracle) wrote:
> On Mon, Apr 14, 2025 at 09:21:42PM +0200, Christian Schrefl wrote:
>> Hi Miguel,
>>
>> On 14.04.25 8:14 PM, Miguel Ojeda wrote:
>>> Hi Jocelyn, Christian,
>>>
>>> I started build-testing arm 32-bit within my other usual routine
>>> tests, and I hit:
>>>
>>>      ld.lld: error: undefined symbol: __aeabi_uldivmod
>>>      >>> referenced by drm_panic_qr.rs:417 (drivers/gpu/drm/drm_panic_qr.rs:417)
>>>      >>> drivers/gpu/drm/drm_panic_qr.o:(<drm_panic_qr::SegmentIterator
>>> as core::iter::traits::iterator::Iterator>::next) in archive vmlinux.a
>>>
>>> which comes from both these `u64` by `u64`:
>>>
>>>      let out = (self.carry / pow) as u16;
>>>      self.carry = self.carry % pow;
>>>
>>> Christian: I guess we can offer a set of `div64` functions using the C
>>> ones, at least for the time being, and eventually wire the actual
>>> operator with some support from upstream Rust. Or do you have
>>> something else in mind? (i.e. I think you have been discussing
>>> intrinsics lately)
>>
>> I think using the C implementations is fine. Not sure how much the
>> FFI is going to matter for performance, but it should be rare enough
>> that is shouldn't matter (and hopefully we will get cross lang LTO
>> or something similar at some point).
>>
>> We could also just implement the intrinsic(s) ourselves, but then
>> the u64 divisions would be implicit which is probably undesired.
>> We could also rename the intrinsics so they are only usable from
>> specific crates.
>>
>> I think we need the opinion of the some arm people here.
>>
>> CC Russell King and Linus Walleij.
> 
> The kernel has had the general position that u64 by u64 division is
> silly and isn't supported. Several 32-bit architectures including
> 32-bit ARM don't support it.
> 

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:

1..9 => {
      let out = (self.carry / u32::pow(10, self.carry_len));

10 => {
      let out = (self.carry / 10_000_000_000);
       ...
}

11 => {
      let out = (self.carry / 100_000_000_000);
     ...
}

Would that fix this problem?

Best Regards,

-- 

Jocelyn

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

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

[Geert Uytterhoeven]

 	Hi Russell,

On Mon, 14 Apr 2025, Russell King (Oracle) wrote:
> On Mon, Apr 14, 2025 at 09:21:42PM +0200, Christian Schrefl wrote:
>> Hi Miguel,
>>
>> On 14.04.25 8:14 PM, Miguel Ojeda wrote:
>>> Hi Jocelyn, Christian,
>>>
>>> I started build-testing arm 32-bit within my other usual routine
>>> tests, and I hit:
>>>
>>>     ld.lld: error: undefined symbol: __aeabi_uldivmod
>>>    >>> referenced by drm_panic_qr.rs:417 (drivers/gpu/drm/drm_panic_qr.rs:417)
>>>    >>> drivers/gpu/drm/drm_panic_qr.o:(<drm_panic_qr::SegmentIterator
>>> as core::iter::traits::iterator::Iterator>::next) in archive vmlinux.a
>>>
>>> which comes from both these `u64` by `u64`:
>>>
>>>     let out = (self.carry / pow) as u16;
>>>     self.carry = self.carry % pow;
>>>
>>> Christian: I guess we can offer a set of `div64` functions using the C
>>> ones, at least for the time being, and eventually wire the actual
>>> operator with some support from upstream Rust. Or do you have
>>> something else in mind? (i.e. I think you have been discussing
>>> intrinsics lately)
>>
>> I think using the C implementations is fine. Not sure how much the
>> FFI is going to matter for performance, but it should be rare enough
>> that is shouldn't matter (and hopefully we will get cross lang LTO
>> or something similar at some point).
>>
>> We could also just implement the intrinsic(s) ourselves, but then
>> the u64 divisions would be implicit which is probably undesired.
>> We could also rename the intrinsics so they are only usable from
>> specific crates.
>>
>> I think we need the opinion of the some arm people here.
>>
>> CC Russell King and Linus Walleij.
>
> The kernel has had the general position that u64 by u64 division is
> silly and isn't supported. Several 32-bit architectures including

s/isn't supported/isn't supported implicitly/

> 32-bit ARM don't support it.

It is supported when called explicitly through div64_u64()
https://elixir.bootlin.com/linux/v6.14.5/source/include/linux/math64.h#L60
But you better think twice before using it, especially in
performance-critical code.

Gr{oetje,eeting}s,

 						Geert

--
Geert Uytterhoeven -- There's lots of Linux beyond ia32 -- geert@linux-m68k.org

In personal conversations with technical people, I call myself a hacker. But
when I'm talking to journalists I just say "programmer" or something like that.
 							    -- Linus Torvalds

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

[Miguel Ojeda]

On Mon, Apr 14, 2025 at 8:14 PM Miguel Ojeda
<miguel.ojeda.sandonis@gmail.com> wrote:
>
> operator with some support from upstream Rust. Or do you have

Or, probably something that makes more sense: just forbidding its use.

Cheers,
Miguel