Re: [PATCH] globsort: handle int overflow in cmp functions

[Grisha Levit]

On Fri, May 17, 2024 at 3:06 PM Chet Ramey <chet.ramey@case.edu> wrote:
>
> On 5/17/24 12:57 PM, Grisha Levit wrote:
> > The current cmp implementation for size and blocks subtracts the two
> > values and returns the difference as an int. This subtraction can
> > overflow, and the returned int can end up having the wrong sign.
> >
> > This also makes the qsort comparison function non-transitive. (Some
> > interesting discussion on that at [1]).
>
> Thanks for the report. If overflow is a concern, then a guaranteed
> transitive comparison function is the right thing. Your solution is clever,
> but a little obscure; I think I'll make it look more like the other
> comparison functions.

FWIW, I was copying the approach from coreutils[1] and gnulib[2]:

/* _GL_CMP (n1, n2) performs a three-valued comparison on n1 vs. n2, where
   n1 and n2 are expressions without side effects, that evaluate to real
   numbers (excluding NaN).
   It returns
     1  if n1 > n2
     0  if n1 == n2
     -1 if n1 < n2
   The naïve code   (n1 > n2 ? 1 : n1 < n2 ? -1 : 0)  produces a conditional
   jump with nearly all GCC versions up to GCC 10.
   This variant     (n1 < n2 ? -1 : n1 > n2)  produces a conditional with many
   GCC versions up to GCC 9.
   The better code  (n1 > n2) - (n1 < n2)  from Hacker's Delight § 2-9
   avoids conditional jumps in all GCC versions >= 3.4.  */
#define _GL_CMP(n1, n2) (((n1) > (n2)) - ((n1) < (n2)))


[1]: https://git.gnu.org/cgit/coreutils.git/tree/src/ls.c?h=v9.5#n3899
[2]: https://git.gnu.org/cgit/gnulib.git/tree/m4/gnulib-common.m4?h=v1.0#n622