summaryrefslogtreecommitdiff
path: root/src/string
AgeCommit message (Collapse)AuthorLines
2014-04-09fix search past the end of haystack in memmemTimo Teräs-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.
2013-12-12include cleanups: remove unused headers and add feature test macrosSzabolcs Nagy-18/+7
2013-11-23strcmp: Remove unnecessary check for *rMichael Forney-1/+1
If *l == *r && *l, then by transitivity, *r.
2013-08-28optimized C memcpyRich Felker-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.
2013-08-27optimized C memsetRich Felker-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.
2013-08-14add arm-optimized memcpy implementation from bionic libcRich Felker-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.
2013-08-01optimized memset asm for i386 and x86_64Rich Felker-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.
2013-07-09fix a couple misleading/wrong signal descriptions in strsignalRich Felker-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.
2013-07-09add realtime signals to strsignalRich Felker-3/+19
the name format RTnn/RTnnn was chosen to minimized bloat while uniquely identifying the signal.
2013-07-09fix off-by-one array bound in strsignalRich Felker-1/+1
2013-04-05Add ABI compatability aliases.Isaac Dunham-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.
2013-02-26fix integer type issue in strverscmpRich Felker-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.
2013-02-26implement non-stub strverscmpRich Felker-2/+35
patch by Isaac Dunham.
2013-02-21replace stub with working strcasestrRich Felker-2/+4
2013-02-21fix wrong return value from wmemmove on forward copiesRich Felker-1/+2
2012-12-26fix alignment logic in strlcpyRich Felker-1/+1
2012-10-22simplify logic in stpcpy; avoid copying first aligned byte twiceRich Felker-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.
2012-10-15add memmem function (gnu extension)Rich Felker-0/+148
based on strstr. passes gnulib tests and a few quick checks of my own.
2012-09-27optimize strchrnul/strcspn not to scan string twice on no-matchRich Felker-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.
2012-09-27slightly cleaner strlen, also seems to compile to better codeRich Felker-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.
2012-09-10asm for memmove on i386 and x86_64Rich Felker-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.
2012-09-10reenable word-at-at-time copying in memmoveRich Felker-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.
2012-09-06use restrict everywhere it's required by c99 and/or posix 2008Rich Felker-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.
2012-09-06remove dependency of wmemmove on wmemcpy directionRich Felker-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.
2012-09-06remove dependency of memmove on memcpy directionRich Felker-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.
2012-08-11memcpy asm for i386 and x86_64Rich Felker-0/+51
2012-08-11remove unused but buggy code from strstr.cRich Felker-10/+0
2012-08-11remove buggy short-string wcsstr implementation; always use twowayRich Felker-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.
2012-07-31optimize mempcpy to minimize need for data saved across the callRich Felker-2/+1
2012-06-20make strerror_r behave nicer on failureRich Felker-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.
2012-05-26fix overrun (n essentially ignored) in wcsncmpRich Felker-1/+1
bug report and solution by Richard Pennington
2012-05-26fix failure of strrchr(str, 0)Rich Felker-1/+1
bug report and solution by Richard Pennington
2012-03-01add all missing wchar functions except floating point parsersRich Felker-0/+71
these are mostly untested and adapted directly from corresponding byte string functions and similar.
2011-09-11add dummied strverscmp (obnoxious GNU function)Rich Felker-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.
2011-06-13fix wrong type for wcsrchr argument 2Rich Felker-1/+1
2011-05-22fix strncat and wcsncat (double null termination)Rich Felker-3/+3
also modify wcsncpy to use the same loop logic
2011-05-22fix wcsncpy writing past end of bufferRich Felker-1/+1
2011-04-26function signature fix: add const qualifier to mempcpy src argRich Felker-1/+1
2011-04-13implement memrchr (nonstandard) and optimize strrchr in terms of itRich Felker-4/+15
2011-04-07fix misplaced *'s in string functions (harmless)Rich Felker-3/+3
2011-04-06fix prototype for strsepRich Felker-0/+1
2011-04-05fix misaligned read on early string termination in strchrRich Felker-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.
2011-04-03fix serious bug in strchr - char signednessRich Felker-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.
2011-03-25fix all implicit conversion between signed/unsigned pointersRich Felker-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.
2011-03-17fix broken wmemchr (unbounded search)Rich Felker-1/+1
2011-02-26fix missing prototype for strsignalRich Felker-0/+1
2011-02-24add implementation of memccpy functionRich Felker-0/+32
2011-02-24fix backwards conditional in stpncpyRich Felker-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).
2011-02-14more header cleanup and conformance fixes - string.hRich Felker-0/+1
2011-02-12initial check-in, version 0.5.0v0.5.0Rich Felker-0/+1054