| Commit message (Expand) | Author | Age | Files | Lines |
|---|
| * | optimize two-way strstr and memmem bad character shift•••first, the condition (mem && k < p) is redundant, because mem being
nonzero implies the needle is periodic with period exactly p, in which
case any byte that appears in the needle must appear in the last p
bytes of the needle, bounding the shift (k) by p.
second, the whole point of replacing the shift k by mem (=l-p) is to
prevent shifting by less than mem when discarding the memory on shift,
in which case linear time could not be guaranteed. but as written, the
check also replaced shifts greater than mem by mem, reducing the
benefit of the shift. there is no possible benefit to this reduction of
the shift; since mem is being cleared, the full shift is valid and
more optimal. so only replace the shift by mem when it would be less
than mem.
| Rich Felker | 2018-11-08 | 1 | -1/+1 |
| * | fix spuriously slow check in twoway strstr/memmem cores•••mem0 && mem && ... is redundant since mem can only be nonzero when
mem0 is nonzero.
| Rich Felker | 2018-11-02 | 1 | -1/+1 |
| * | fix OOB reads in Xbyte_memmem•••Reported by Leah Neukirchen.
| Alexander Monakov | 2017-09-04 | 1 | -9/+9 |
| * | fix read past end of haystack buffer for short needles in memmem•••the two/three/four byte memmem specializations are not prepared to
handle haystacks shorter than the needle; they unconditionally read at
least up to the needle length and subtract from the haystack length.
if the haystack is shorter, the remaining haystack length underflows
and produces an unbounded search which will eventually either crash or
find a spurious match.
the top-level memmem function attempted to avoid this case already by
checking for haystack shorter than needle, but it failed to re-check
after using memchr to remove the maximal prefix not containing the
first byte of the needle.
| Rich Felker | 2016-04-01 | 1 | -0/+1 |
| * | fix incorrect comparison loop condition in memmem•••the logic for this loop was copied from null-terminated-string logic
in strstr without properly adapting it to work with explicit lengths.
presumably this error could result in false negatives (wrongly
comparing past the end of the needle/haystack), false positives
(stopping comparison early when the needle contains null bytes), and
crashes (from runaway reads past the end of mapped memory).
| Rich Felker | 2014-06-19 | 1 | -2/+2 |
| * | fix false negatives with periodic needles in strstr, wcsstr, and memmem•••in cases where the memorized match range from the right factor
exceeded the length of the left factor, it was wrongly treated as a
mismatch rather than a match.
issue reported by Yves Bastide.
| Rich Felker | 2014-04-18 | 1 | -1/+1 |
| * | fix search past the end of haystack in memmem•••to optimize the search, memchr is used to find the first occurrence of
the first character of the needle in the haystack before switching to
a search for the full needle. however, the number of characters
skipped by this first step were not subtracted from the haystack
length, causing memmem to search past the end of the haystack.
| Timo Teräs | 2014-04-09 | 1 | -0/+1 |
| * | include cleanups: remove unused headers and add feature test macros | Szabolcs Nagy | 2013-12-12 | 1 | -1/+0 |
| * | add memmem function (gnu extension)•••based on strstr. passes gnulib tests and a few quick checks of my own.
| Rich Felker | 2012-10-15 | 1 | -0/+148 |
