about summary refs log tree commit diff
path: root/src/string
Commit message (Collapse)AuthorAgeFilesLines
* fix false negatives with periodic needles in strstr, wcsstr, and memmemRich Felker2014-04-183-3/+3
| | | | | | | | 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.
* fix search past the end of haystack in memmemTimo Teräs2014-04-091-0/+1
| | | | | | | | 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.
* include cleanups: remove unused headers and add feature test macrosSzabolcs Nagy2013-12-1222-18/+7
|
* strcmp: Remove unnecessary check for *rMichael Forney2013-11-231-1/+1
| | | | If *l == *r && *l, then by transitivity, *r.
* optimized C memcpyRich Felker2013-08-281-16/+111
| | | | | | | | | | | | | | | | unlike the old C memcpy, this version handles word-at-a-time reads and writes even for misaligned copies. it does not require that the cpu support misaligned accesses; instead, it performs bit shifts to realign the bytes for the destination. essentially, this is the C version of the ARM assembly language memcpy. the ideas are all the same, and it should perform well on any arch with a decent number of general-purpose registers that has a barrel shift operation. since the barrel shifter is an optional cpu feature on microblaze, it may be desirable to provide an alternate asm implementation on microblaze, but otherwise the C code provides a competitive implementation for "generic risc-y" cpu archs that should alleviate the urgent need for arch-specific memcpy asm.
* optimized C memsetRich Felker2013-08-271-12/+77
| | | | | | | | | | | | | | | | this version of memset is optimized both for small and large values of n, and makes no misaligned writes, so it is usable (and near-optimal) on all archs. it is capable of filling up to 52 or 56 bytes without entering a loop and with at most 7 branches, all of which can be fully predicted if memset is called multiple times with the same size. it also uses the attribute extension to inform the compiler that it is violating the aliasing rules, unlike the previous code which simply assumed it was safe to violate the aliasing rules since translation unit boundaries hide the violations from the compiler. for non-GNUC compilers, 100% portable fallback code in the form of a naive loop is provided. I intend to eventually apply this approach to all of the string/memory functions which are doing word-at-a-time accesses.
* add arm-optimized memcpy implementation from bionic libcRich Felker2013-08-143-0/+383
| | | | | | | | | | | | | | | | | | | | the approach of this implementation was heavily investigated prior to adopting it. attempts to obtain similar performance with pure C code were capping out at about 75% of the performance of the asm, with considerably larger code size, and were fragile in that the compiler would sometimes compile part of memcpy into a call to itself. therefore, just using the asm seems to be the best option. this commit is the first to make use of the new subarch-specific asm framework. the new armel directory is the location for arm asm that should not be used for all arm subarchs, only the default one. armhf is the name of the little-endian hardfloat-ABI subarch, which can use the exact same asm. in both cases, the build system finds the asm by following a memcpy.sub file. the other two subarchs, armeb and armebhf, would need a big-endian variant of this code. it would not be hard to adapt the code to big endian, but I will hold off on doing so until there is demand for it.
* optimized memset asm for i386 and x86_64Rich Felker2013-08-012-0/+88
| | | | | | | | | | | | | | | | | | | | the concept of both versions is the same; they differ only in details. for long runs, they use "rep movsl" or "rep movsq", and for small runs, they use a trick, writing from both ends towards the middle, that reduces the number of branches needed. in addition, if memset is called multiple times with the same length, all branches will be predicted; there are no loops. for larger runs, there are likely faster approaches than "rep", at least on some cpu models. for 32-bit, it's unlikely that there is any faster approach that does not require non-baseline instructions; doing anything fancier would require inspecting cpu capabilities. for 64-bit, there may very well be faster versions that work on all models; further optimization could be explored in the future. with these changes, memset is anywhere between 50% faster and 6 times faster, depending on the cpu model and the length and alignment of the destination buffer.
* fix a couple misleading/wrong signal descriptions in strsignalRich Felker2013-07-091-2/+2
| | | | | | | there are still several more that are misleading, but SIGFPE (integer division error misdescribed as floating point) and and SIGCHLD (possibly non-exit status change events described as exiting) were the worst offenders.
* add realtime signals to strsignalRich Felker2013-07-091-3/+19
| | | | | the name format RTnn/RTnnn was chosen to minimized bloat while uniquely identifying the signal.
* fix off-by-one array bound in strsignalRich Felker2013-07-091-1/+1
|
* Add ABI compatability aliases.Isaac Dunham2013-04-051-0/+3
| | | | | | | | GNU used several extensions that were incompatible with C99 and POSIX, so they used alternate names for the standard functions. The result is that we need these to run standards-conformant programs that were linked with glibc.
* fix integer type issue in strverscmpRich Felker2013-02-261-1/+3
| | | | | | | | | lenl-lenr is not a valid expression for a signed int return value from strverscmp, since after implicit conversion from size_t to int this difference could have the wrong sign or might even be zero. using the difference for char values works since they're bounded well within the range of differences representable by int, but it does not work for size_t values.
* implement non-stub strverscmpRich Felker2013-02-261-2/+35
| | | | patch by Isaac Dunham.
* replace stub with working strcasestrRich Felker2013-02-211-2/+4
|
* fix wrong return value from wmemmove on forward copiesRich Felker2013-02-211-1/+2
|
* fix alignment logic in strlcpyRich Felker2012-12-261-1/+1
|
* simplify logic in stpcpy; avoid copying first aligned byte twiceRich Felker2012-10-221-4/+4
| | | | | gcc seems to be generating identical or near-identical code for both versions, but the newer code is more expressive of what it's doing.
* add memmem function (gnu extension)Rich Felker2012-10-151-0/+148
| | | | based on strstr. passes gnulib tests and a few quick checks of my own.
* optimize strchrnul/strcspn not to scan string twice on no-matchRich Felker2012-09-273-25/+29
| | | | | | | | | when strchr fails, and important piece of information already computed, the string length, is thrown away. have strchrnul (with namespace protection) be the underlying function so this information can be kept, and let strchr be a wrapper for it. this also allows strcspn to be considerably faster in the case where the match set has a single element that's not matched.
* slightly cleaner strlen, also seems to compile to better codeRich Felker2012-09-271-6/+4
| | | | | | | testing with gcc 4.6.3 on x86, -Os, the old version does a duplicate null byte check after the first loop. this is purely the compiler being stupid, but the old code was also stupid and unintuitive in how it expressed the check.
* asm for memmove on i386 and x86_64Rich Felker2012-09-102-0/+36
| | | | | | | for the sake of simplicity, I've only used rep movsb rather than breaking up the copy for using rep movsd/q. on all modern cpus, this seems to be fine, but if there are performance problems, there might be a need to go back and add support for rep movsd/q.
* reenable word-at-at-time copying in memmoveRich Felker2012-09-101-4/+27
| | | | | | | | | before restrict was added, memove called memcpy for forward copies and used a byte-at-a-time loop for reverse copies. this was changed to avoid invoking UB now that memcpy has an undefined copying order, making memmove considerably slower. performance is still rather bad, so I'll be adding asm soon.
* use restrict everywhere it's required by c99 and/or posix 2008Rich Felker2012-09-0620-20/+20
| | | | | | | | to deal with the fact that the public headers may be used with pre-c99 compilers, __restrict is used in place of restrict, and defined appropriately for any supported compiler. we also avoid the form [restrict] since older versions of gcc rejected it due to a bug in the original c99 standard, and instead use the form *restrict.
* remove dependency of wmemmove on wmemcpy directionRich Felker2012-09-061-4/+4
| | | | | | unlike the memmove commit, this one should be fine to leave in place. wmemmove is not performance-critical, and even if it were, it's already copying whole 32-bit words at a time instead of bytes.
* remove dependency of memmove on memcpy directionRich Felker2012-09-061-5/+4
| | | | | | | | this commit introduces a performance regression in many uses of memmove, which will need to be addressed before the next release. i'm making it as a temporary measure so that the restrict patch can be committed without invoking undefined behavior when memmove calls memcpy with overlapping regions.
* memcpy asm for i386 and x86_64Rich Felker2012-08-112-0/+51
|
* remove unused but buggy code from strstr.cRich Felker2012-08-111-10/+0
|
* remove buggy short-string wcsstr implementation; always use twowayRich Felker2012-08-111-9/+0
| | | | | | since this interface is rarely used, it's probably best to lean towards keeping code size down anyway. one-character needles will still be found immediately by the initial wcschr call anyway.
* optimize mempcpy to minimize need for data saved across the callRich Felker2012-07-311-2/+1
|
* make strerror_r behave nicer on failureRich Felker2012-06-201-2/+8
| | | | | | | if the buffer is too short, at least return a partial string. this is helpful if the caller is lazy and does not check for failure. care is taken to avoid writing anything if the buffer length is zero, and to always null-terminate when the buffer length is non-zero.
* fix overrun (n essentially ignored) in wcsncmpRich Felker2012-05-261-1/+1
| | | | bug report and solution by Richard Pennington
* fix failure of strrchr(str, 0)Rich Felker2012-05-261-1/+1
| | | | bug report and solution by Richard Pennington
* add all missing wchar functions except floating point parsersRich Felker2012-03-019-0/+71
| | | | | these are mostly untested and adapted directly from corresponding byte string functions and similar.
* add dummied strverscmp (obnoxious GNU function)Rich Felker2011-09-111-0/+7
| | | | | | programs that use this tend to horribly botch international text support, so it's questionable whether we want to support it even in the long term... for now, it's just a dummy that calls strcmp.
* fix wrong type for wcsrchr argument 2Rich Felker2011-06-131-1/+1
|
* fix strncat and wcsncat (double null termination)Rich Felker2011-05-223-3/+3
| | | | also modify wcsncpy to use the same loop logic
* fix wcsncpy writing past end of bufferRich Felker2011-05-221-1/+1
|
* function signature fix: add const qualifier to mempcpy src argRich Felker2011-04-261-1/+1
|
* implement memrchr (nonstandard) and optimize strrchr in terms of itRich Felker2011-04-132-4/+15
|
* fix misplaced *'s in string functions (harmless)Rich Felker2011-04-073-3/+3
|
* fix prototype for strsepRich Felker2011-04-061-0/+1
|
* fix misaligned read on early string termination in strchrRich Felker2011-04-051-1/+2
| | | | | | this could actually cause rare crashes in the case where a short string is located at the end of a page and the following page is not readable, and in fact this was seen in gcc compiling certain files.
* fix serious bug in strchr - char signednessRich Felker2011-04-031-9/+11
| | | | | | search for bytes with high bit set was giving (potentially dangerous) wrong results. i've tested, cleaned up, and hopefully sped up this function now.
* fix all implicit conversion between signed/unsigned pointersRich Felker2011-03-256-20/+16
| | | | | | | sadly the C language does not specify any such implicit conversion, so this is not a matter of just fixing warnings (as gcc treats it) but actual errors. i would like to revisit a number of these changes and possibly revise the types used to reduce the number of casts required.
* fix broken wmemchr (unbounded search)Rich Felker2011-03-171-1/+1
|
* fix missing prototype for strsignalRich Felker2011-02-261-0/+1
|
* add implementation of memccpy functionRich Felker2011-02-241-0/+32
|
* fix backwards conditional in stpncpyRich Felker2011-02-241-1/+1
| | | | | | this only made the function unnecessarily slow on systems with unaligned access, but would of course crash on systems that can't do unaligned accesses (none of which have ports yet).
* more header cleanup and conformance fixes - string.hRich Felker2011-02-141-0/+1
|