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

2024-05-20 Thread Andreas Schwab
On Mai 17 2024, 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.

In the case of globsort_sizecmp, since off_t is wider than int, it can
return a wrong value even if the subtraction doesn't overflow.

-- 
Andreas Schwab, sch...@linux-m68k.org
GPG Key fingerprint = 7578 EB47 D4E5 4D69 2510  2552 DF73 E780 A9DA AEC1
"And now for something completely different."



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

2024-05-20 Thread Chet Ramey

On 5/20/24 10:07 AM, alex xmb sw ratchev wrote:


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

Sure. I'm going to stick with code clarity and uniformity over micro
optimizations here. Maybe I could hide it in a macro.


an if overflow sounds like an important thing to code , an overall one


We're talking about different ways to avoid it.

--
``The lyf so short, the craft so long to lerne.'' - Chaucer
 ``Ars longa, vita brevis'' - Hippocrates
Chet Ramey, UTech, CWRUc...@case.eduhttp://tiswww.cwru.edu/~chet/



OpenPGP_signature.asc
Description: OpenPGP digital signature


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

2024-05-20 Thread alex xmb sw ratchev
On Mon, May 20, 2024, 15:58 Chet Ramey  wrote:

> On 5/17/24 5:56 PM, Grisha Levit wrote:
> > On Fri, May 17, 2024 at 3:06 PM Chet Ramey  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]:
>
> Sure. I'm going to stick with code clarity and uniformity over micro
> optimizations here. Maybe I could hide it in a macro.
>

an if overflow sounds like an important thing to code , an overall one

-- 
> ``The lyf so short, the craft so long to lerne.'' - Chaucer
>  ``Ars longa, vita brevis'' - Hippocrates
> Chet Ramey, UTech, CWRUc...@case.eduhttp://tiswww.cwru.edu/~chet/
>
>


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

2024-05-20 Thread Chet Ramey

On 5/17/24 5:56 PM, Grisha Levit wrote:

On Fri, May 17, 2024 at 3:06 PM Chet Ramey  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]:


Sure. I'm going to stick with code clarity and uniformity over micro
optimizations here. Maybe I could hide it in a macro.

--
``The lyf so short, the craft so long to lerne.'' - Chaucer
 ``Ars longa, vita brevis'' - Hippocrates
Chet Ramey, UTech, CWRUc...@case.eduhttp://tiswww.cwru.edu/~chet/



OpenPGP_signature.asc
Description: OpenPGP digital signature


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

2024-05-17 Thread Grisha Levit
On Fri, May 17, 2024 at 3:06 PM Chet Ramey  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



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

2024-05-17 Thread Chet Ramey

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.

Chet

--
``The lyf so short, the craft so long to lerne.'' - Chaucer
 ``Ars longa, vita brevis'' - Hippocrates
Chet Ramey, UTech, CWRUc...@case.eduhttp://tiswww.cwru.edu/~chet/



OpenPGP_signature.asc
Description: OpenPGP digital signature


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

2024-05-17 Thread Robert Elz
Date:Fri, 17 May 2024 12:57:25 -0400
From:Grisha Levit 
Message-ID:  <20240517165738.8896-1-grishale...@gmail.com>

  | 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 message provides enough info about the implementation to
answer the "what order if we get equality" question in my previous
message ... just "whatever qsort decides to do" - which is almost
always the wrong thing.


  | -  return ((glob_sorttype < SORT_REVERSE) ? g1->st.size - g2->st.size : 
g2->st.size - g1->st.size);
  | +  return (glob_sorttype < SORT_REVERSE)
  | +? (g1->st.size > g2->st.size) - (g1->st.size < g2->st.size)
  | +: (g2->st.size > g1->st.size) - (g1->st.size < g2->st.size);

Shouldn't the 2nd half of the : case have the g1 & g2 swapped as well?
(and the same for the blocks comparison).

kre

ps: you're likely to get finger wagging by those people who believe
that booleans in C should be a real type of their own, and performing
arithmetic on bool results is naughty.   That's not me - I don't
believe bool should exist in C, things were fine without it.