Re: [PATCH] libgcc: Fix up __divmodbitint4 [PR114755]

[Christophe Lyon <christophe.lyon@linaro.org>]

On Thu, 18 Apr 2024 at 09:37, Jakub Jelinek <jakub@redhat.com> wrote:
>
> Hi!
>
> The following testcase aborts on aarch64-linux but does not on x86_64-linux.
> In both cases there is UB in the __divmodbitint4 implemenetation.
> When the divisor is negative with most significant limb (even when partial)
> all ones, has at least 2 limbs and the second most significant limb has the
> most significant bit clear, when this number is negated, it will have 0
> in the most significant limb.
> Already in the PR114397 r14-9592 fix I was dealing with such divisors, but
> thought the problem is only if because of that un < vn doesn't imply the
> quotient is 0 and remainder u.
> But as this testcase shows, the problem is with such divisors always.
> What happens is that we use __builtin_clz* on the most significant limb,
> and assume it will not be 0 because that is UB for the builtins.
> Normally the most significant limb of the divisor shouldn't be 0, as
> guaranteed by the bitint_reduce_prec e.g. for the positive numbers, unless
> the divisor is just 0 (but for vn == 1 we have special cases).

Just curious: could this have been caught by ubsan? (I don't know if
it knows about clz)

Thanks,

Christophe

>
> The following patch moves the handling of this corner case a few lines
> earlier before the un < vn check, because adjusting the vn later is harder.
>
> Bootstrapped/regtested on x86_64-linux and i686-linux, plus tested with
> make check-gcc -j32 -k GCC_TEST_RUN_EXPENSIVE=1 RUNTESTFLAGS="GCC_TEST_RUN_EXPENSIVE=1 dg.exp='*bitint* pr112673.c builtin-stdc-bit-*.c pr112566-2.c pr112511.c' dg-torture.exp=*bitint* dfp.exp=*bitint*"
> on aarch64-linux, ok for trunk?
>
> 2024-04-18  Jakub Jelinek  <jakub@redhat.com>
>
>         PR libgcc/114755
>         * libgcc2.c (__divmodbitint4): Perform the decrement on negative
>         v with most significant limb all ones and the second least
>         significant limb with most significant bit clear always, regardless of
>         un < vn.
>
>         * gcc.dg/torture/bitint-69.c: New test.
>
> --- libgcc/libgcc2.c.jj 2024-03-21 13:07:43.629886730 +0100
> +++ libgcc/libgcc2.c    2024-04-17 19:00:55.453691368 +0200
> @@ -1705,69 +1705,62 @@ __divmodbitint4 (UBILtype *q, SItype qpr
>    USItype rn = ((USItype) rprec + W_TYPE_SIZE - 1) / W_TYPE_SIZE;
>    USItype up = auprec % W_TYPE_SIZE;
>    USItype vp = avprec % W_TYPE_SIZE;
> +  /* If vprec < 0 and the top limb of v is all ones and the second most
> +     significant limb has most significant bit clear, then just decrease
> +     vn/avprec/vp, because after negation otherwise v2 would have most
> +     significant limb clear.  */
> +  if (vprec < 0
> +      && ((v[BITINT_END (0, vn - 1)] | (vp ? ((UWtype) -1 << vp) : 0))
> +         == (UWtype) -1)
> +      && vn > 1
> +      && (Wtype) v[BITINT_END (1, vn - 2)] >= 0)
> +    {
> +      vp = 0;
> +      --vn;
> +#if __LIBGCC_BITINT_ORDER__ == __ORDER_BIG_ENDIAN__
> +      ++v;
> +#endif
> +    }
>    if (__builtin_expect (un < vn, 0))
>      {
> -      /* If abs(v) > abs(u), then q is 0 and r is u.
> -        Unfortunately un < vn doesn't always mean abs(v) > abs(u).
> -        If uprec > 0 and vprec < 0 and vn == un + 1, if the
> -        top limb of v is all ones and the second most significant
> -        limb has most significant bit clear, then just decrease
> -        vn/avprec/vp and continue, after negation both numbers
> -        will have the same number of limbs.  */
> -      if (un + 1 == vn
> -         && uprec >= 0
> -         && vprec < 0
> -         && ((v[BITINT_END (0, vn - 1)] | (vp ? ((UWtype) -1 << vp) : 0))
> -             == (UWtype) -1)
> -         && (Wtype) v[BITINT_END (1, vn - 2)] >= 0)
> -       {
> -         vp = 0;
> -         --vn;
> +      /* q is 0 and r is u.  */
> +      if (q)
> +       __builtin_memset (q, 0, qn * sizeof (UWtype));
> +      if (r == NULL)
> +       return;
>  #if __LIBGCC_BITINT_ORDER__ == __ORDER_BIG_ENDIAN__
> -         ++v;
> +      r += rn - 1;
> +      u += un - 1;
>  #endif
> +      if (up)
> +       --un;
> +      if (rn < un)
> +       un = rn;
> +      for (rn -= un; un; --un)
> +       {
> +         *r = *u;
> +         r += BITINT_INC;
> +         u += BITINT_INC;
>         }
> -      else
> +      if (!rn)
> +       return;
> +      if (up)
>         {
> -         /* q is 0 and r is u.  */
> -         if (q)
> -           __builtin_memset (q, 0, qn * sizeof (UWtype));
> -         if (r == NULL)
> +         if (uprec > 0)
> +           *r = *u & (((UWtype) 1 << up) - 1);
> +         else
> +           *r = *u | ((UWtype) -1 << up);
> +         r += BITINT_INC;
> +         if (!--rn)
>             return;
> -#if __LIBGCC_BITINT_ORDER__ == __ORDER_BIG_ENDIAN__
> -         r += rn - 1;
> -         u += un - 1;
> -#endif
> -         if (up)
> -           --un;
> -         if (rn < un)
> -           un = rn;
> -         for (rn -= un; un; --un)
> -           {
> -             *r = *u;
> -             r += BITINT_INC;
> -             u += BITINT_INC;
> -           }
> -         if (!rn)
> -           return;
> -         if (up)
> -           {
> -             if (uprec > 0)
> -               *r = *u & (((UWtype) 1 << up) - 1);
> -             else
> -               *r = *u | ((UWtype) -1 << up);
> -             r += BITINT_INC;
> -             if (!--rn)
> -               return;
> -           }
> -         UWtype c = uprec < 0 ? (UWtype) -1 : (UWtype) 0;
> -         for (; rn; --rn)
> -           {
> -             *r = c;
> -             r += BITINT_INC;
> -           }
> -         return;
>         }
> +      UWtype c = uprec < 0 ? (UWtype) -1 : (UWtype) 0;
> +      for (; rn; --rn)
> +       {
> +         *r = c;
> +         r += BITINT_INC;
> +       }
> +      return;
>      }
>    USItype qn2 = un - vn + 1;
>    if (qn >= qn2)
> --- gcc/testsuite/gcc.dg/torture/bitint-69.c.jj 2024-04-17 19:09:34.165521448 +0200
> +++ gcc/testsuite/gcc.dg/torture/bitint-69.c    2024-04-17 19:10:25.343814139 +0200
> @@ -0,0 +1,26 @@
> +/* PR libgcc/114755 */
> +/* { dg-do run { target bitint } } */
> +/* { dg-options "-std=c23" } */
> +/* { dg-skip-if "" { ! run_expensive_tests }  { "*" } { "-O0" "-O2" } } */
> +/* { dg-skip-if "" { ! run_expensive_tests } { "-flto" } { "" } } */
> +
> +#if __BITINT_MAXWIDTH__ >= 255
> +_BitInt(65)
> +foo (void)
> +{
> +  _BitInt(255) a = 0x040404040404040404040404wb;
> +  _BitInt(65) b = -0xffffffffffffffffwb;
> +  _BitInt(65) r = a % b;
> +  return r;
> +}
> +#endif
> +
> +int
> +main ()
> +{
> +#if __BITINT_MAXWIDTH__ >= 255
> +  _BitInt(65) x = foo ();
> +  if (x != 0x0404040408080808wb)
> +    __builtin_abort ();
> +#endif
> +}
>
>         Jakub
>