Out-of-bounds read and write in the glibc's qsort()

Re:Out-of-bounds read and write in the glibc's qsort() by skitter on Monday February 05, 2024 @01:54PM (#39265290)

They already mention the issue of using substraction for comparison; here's another different accidentally intransitive comparison function:

    int cmp(const float *a, const float *b) {
        if (*a < *b) {
            return 1;
        } else if (*a == *b) {
            return 0;
        } else {
            return -1;
        }
    }

[ Parent | on HN ]

Re:Out-of-bounds read and write in the glibc's qsort() by jstimpfle on Monday February 05, 2024 @01:59PM (#39265378)

Is it intransitive? Can you give a, b, c s.t. a < b and b < c, but not a < c?

[ Parent | on HN ]

Re:Out-of-bounds read and write in the glibc's qsort() by rrauenza on Monday February 05, 2024 @02:05PM (#39265476)

Maybe inf or nan?

https://stackoverflow.com/a/42723797/2077386

[ Parent | on HN ]

Re:Out-of-bounds read and write in the glibc's qsort() by rightbyte on Monday February 05, 2024 @02:11PM (#39265561)

No, but you need a nan check in the above code. And a negative zero check if you are picky for sorting maybe.

[ Parent | on HN ]

Re:Out-of-bounds read and write in the glibc's qsort() by ufo on Monday February 05, 2024 @02:07PM (#39265500)

Maybe theyre talking about NaN?Comparing against NaN return false. That doesn't violate transitivity, but it can confuse many sorting algorithms.

[ Parent | on HN ]

Re:Out-of-bounds read and write in the glibc's qsort() by scythe on Monday February 05, 2024 @02:06PM (#39265490)

Trivially, NaN != NaN, so this function is not even properly reflexive (i.e. for a = b = NaN we find cmp(&a,&b) = cmp(&b,&a) = 1).

[ Parent | on HN ]

Re:Out-of-bounds read and write in the glibc's qsort() by jstimpfle on Monday February 05, 2024 @02:44PM (#39266054)

I mean, yeah. It's not like there is a lot of meaning to NaN. For most applications, trying to sort NaNs is probably a bug in itself. So I think this is likely a perfectly valid comparison function.

To make a point, here is a sorting function I'm using.

    static int cmp_seqnos(const void *a, const void *b)
    {
        uint64_t x = (const uint64_t *) a;
        uint64_t y = (const uint64_t *) b;
        if (y - x < ((uint64_t) 1 << 63))
            return -1;
        return x != y;
    }

I think this should work if there are uint64_t a, b: b - a < ((uint64_t) 1 << 63) and all values x from the set to be sorted are in the range a..b. Note that a < b isn't a requirement here.

Sorting such numbers can be useful when dealing with sliding windows.

[ Parent | on HN ]