| Age | Commit message (Collapse) | Author | Lines |
|---|
|
the pntz function, implementing a "count trailing zeros" variant for a
bit vector consisting of two size_t words, erroneously returned zero
rather than the number of bits in the low word when the first bit set
was the low bit of the high word.
as a result, a loop in the trinkle function which should have a
guaranteed small bound on the number of iterations, could run
unboundedly, thereby overflowing a stack-based working-space array
which was sized for the bound.
CVE-2026-40200 has been assigned for this issue.
|
|
|
|
we make qsort a wrapper by providing a wrapper_cmp function that uses
the extra argument as a function pointer. should be optimized to a tail
call on most architectures, as long as it's built with
-fomit-frame-pointer, so the performance impact should be minimal.
to keep the git history clean, for now qsort_r is implemented in qsort.c
and qsort is implemented in qsort_nr.c. qsort.c also received a few
trivial cleanups, including replacing (*cmp)() calls with cmp().
qsort_nr.c contains only wrapper_cmp and qsort as a qsort_r wrapper
itself.
|
|
|
|
|
|
Smoothsort is an adaptive variant of heapsort. This version was
written by Valentin Ochs (apo) specifically for inclusion in musl. I
worked with him to get it working in O(1) memory usage even with giant
array element widths, and to optimize it heavily for size and speed.
It's still roughly 4 times as large as the old heap sort
implementation, but roughly 20 times faster given an almost-sorted
array of 1M elements (20 being the base-2 log of 1M), i.e. it really
does reduce O(n log n) to O(n) in the mostly-sorted case. It's still
somewhat slower than glibc's Introsort for random input, but now
considerably faster than glibc when the input is already sorted, or
mostly sorted.
|
|
this is actually a workaround for a bug in gcc, whereby it asserts
inequality of the keys being compared...
|
|
|
