aboutsummaryrefslogtreecommitdiff
path: root/newlib/libc/string
AgeCommit message (Collapse)AuthorFilesLines
2019-01-13update to Unicode 11.0Thomas Wolff2-57/+62
2019-01-01Improve performance of memmemWilco Dijkstra2-51/+137
This patch significantly improves performance of memmem using a novel modified Horspool algorithm.  Needles up to size 256 use a bad-character table indexed by hashed pairs of characters to quickly skip past mismatches. Long needles use a self-adapting filtering step to avoid comparing the whole needle repeatedly. By limiting the needle length to 256, the shift table only requires 8 bits per entry, lowering preprocessing overhead and minimizing cache effects. This limit also implies worst-case performance is linear. Small needles up to size 2 use a dedicated linear search.  Very long needles use the Two-Way algorithm (to avoid increasing stack size inlining is now disabled). The performance gain is 6.6 times on English text on AArch64 using random needles with average size 8 (this is even faster than the recently improved strstr algorithm, so I'll update that in the near future). The size-optimized memmem has also been rewritten from scratch to get a 2.7x performance gain. Tested against GLIBC testsuite and randomized tests. Message-Id: <DB5PR08MB1030649D051FA8532A4512C883B20@DB5PR08MB1030.eurprd08.prod.outlook.com>
2018-10-18Improve performance of strstrWilco Dijkstra1-96/+127
v3: Add support for read ahead using strnlen, giving an additional 25% speedup on large inputs (both short and long needles). This patch significantly improves performance of strstr by using Sunday's Quick-Search algorithm. Due to its simplicity it has the best average performance of string matching algorithms on almost all inputs. It uses a bad-character shift table to skip past mismatches. The needle length is limited to 254 - this reduces the shift table memory 4 to 8 times, lowering preprocessing overhead and minimizing cache effects. The limit also implies its worst-case performance is linear. Larger needles are processed by the Two-Way algorithm. The macro AVAILABLE has been improved to use strnlen to read the input in chunks. This results in a 2.5 times speedup for large needles, reducing the performance drop when the Quick-Search algorithm can't be used. The code for 1-4 byte needles has been simplified and now uses unsigned char. Since the optimized code relies on 8-bit chars, we defer to the size-optimized implementation if CHAR_BIT > 8. The performance gain of finding a set of randomly chosen words of size 8 in 256 bytes of English text is 14 times on AArch64. For longer haystacks the gain is well over 20 times. The size-optimized strstr has also been rewritten from scratch to improve performance. On the same test the performance gain is 69%. Tested against GLIBC testsuite, randomized tests and the GNULIB strstr test (https://git.savannah.gnu.org/cgit/gnulib.git/tree/tests/test-strstr.c). --
2018-09-05Improve strstr performance of short needlesWilco Dijkstra1-10/+65
Improve strstr performance for the common case of short needles. For a single character strchr is best, for 2-4 characters a small loop is fastest. For these the speedup over the Two-Way algorithm is ~10 times on large strings. Newlib builds, the new code passes GLIBC testsuite. OK for commit?
2018-08-29Use __inhibit_loop_to_libcall in all memset/memcpy implementationsKeith Packard1-0/+2
This macro selects a compiler option that disables recognition of common memset/memcpy patterns and converting those to direct memset/memcpy calls. Signed-off-by: Keith Packard <keithp@keithp.com>
2018-03-14fix/enhance Unicode table generation scriptsThomas Wolff1-10/+27
Scripts do not try to acquire Unicode data by best-effort magic anymore. Options supported: -h for help -i to copy Unicode data from /usr/share/unicode/ucd first -u to download Unicode data from unicode.org first If (despite of -i or -u if given) the necessary Unicode files are not available locally, table generation is skipped, but no error code is returned, so not to obstruct the build process if called from a Makefile.
2018-03-12width data generationThomas Wolff5-0/+1388
2018-03-12use generated width dataThomas Wolff1-126/+24
2018-03-12generated width data, Unicode 10.0Thomas Wolff3-0/+201
These tables provide character width properties for use by the wcwidth/wcswidth functions. They are generated from Unicode.
2018-01-17ansification: remove _EXFUN, _EXFUN_NOTHROWYaakov Selkowitz1-1/+1
Signed-off-by: Yaakov Selkowitz <yselkowi@redhat.com>
2018-01-17ansification: remove _DEFUNYaakov Selkowitz85-175/+88
Signed-off-by: Yaakov Selkowitz <yselkowi@redhat.com>
2018-01-17ansification: remove _CAST_VOIDYaakov Selkowitz1-3/+3
Signed-off-by: Yaakov Selkowitz <yselkowi@redhat.com>
2018-01-17ansification: remove _PTRYaakov Selkowitz9-25/+25
Signed-off-by: Yaakov Selkowitz <yselkowi@redhat.com>
2018-01-17ansification: remove _PARAMSYaakov Selkowitz1-1/+1
Signed-off-by: Yaakov Selkowitz <yselkowi@redhat.com>
2018-01-17ansification: remove _CONSTYaakov Selkowitz70-144/+144
Signed-off-by: Yaakov Selkowitz <yselkowi@redhat.com>
2018-01-17ansification: remove _ANDYaakov Selkowitz77-124/+124
Signed-off-by: Yaakov Selkowitz <yselkowi@redhat.com>
2017-12-07makedoc: make errors visibleJon Turney1-3/+3
Discard QUICKREF sections, rather than writing them to stderr Discard MATHREF sections, rather than discarding as an error Pass NOTES sections through to texinfo, rather than discarding as an error Don't redirect makedoc stderr to .ref file Remove makedoc output on error Remove .ref files from CLEANFILES Regenerate Makefile.ins Signed-off-by: Jon Turney <jon.turney@dronecode.org.uk>
2017-12-01string: remove TRAD_SYNOPSISYaakov Selkowitz85-546/+85
Signed-off-by: Yaakov Selkowitz <yselkowi@redhat.com>
2017-11-30string: add wmempcpyYaakov Selkowitz4-38/+81
Signed-off-by: Yaakov Selkowitz <yselkowi@redhat.com>
2017-09-19Fix warnings and documentation in strnstr.cSebastian Huber1-4/+3
Signed-off-by: Sebastian Huber <sebastian.huber@embedded-brains.de>
2017-08-30newlib: string/Makefile.am (CHEWOUT_FILES): Add strnstr.defCorinna Vinschen2-2/+2
Regenerate strings/Makefile.in Signed-off-by: Corinna Vinschen <corinna@vinschen.de>
2017-08-30newlib: strnstr: drop traditional synopisisCorinna Vinschen1-7/+0
Signed-off-by: Corinna Vinschen <corinna@vinschen.de>
2017-08-30Add man page entry for strnstr.c.Sichen Zhao2-0/+43
2017-08-30Modify strnstr.c.Sichen Zhao1-55/+10
2017-08-25newlib: rebuild string/Makefile.inCorinna Vinschen1-27/+49
Signed-off-by: Corinna Vinschen <corinna@vinschen.de>
2017-08-25Port strnstr.c to newlib.Sichen Zhao1-0/+1
2017-08-25Import strnstr.c from FreeBSD.Sichen Zhao1-0/+65
2017-07-05Add ffsl(), ffsll(), fls(), flsl(), flsll()Sebastian Huber7-13/+238
Use compiler builtin for ffs(). Remove duplicate implementation from Cygwin. Signed-off-by: Sebastian Huber <sebastian.huber@embedded-brains.de>
2017-07-05Implement bzero() via memset()Sebastian Huber1-8/+5
Use memset() to implement bzero() to profit from machine-specific memset() optimizations. Signed-off-by: Sebastian Huber <sebastian.huber@embedded-brains.de>
2017-06-19string: fix strverscmp doc inclusionYaakov Selkowitz1-0/+3
Signed-off-by: Yaakov Selkowitz <yselkowi@redhat.com>
2017-06-19string: add strverscmpYaakov Selkowitz4-2/+114
The actual implementation is from musl (MIT license). Signed-off-by: Yaakov Selkowitz <yselkowi@redhat.com>
2017-03-15libc/string/strsignal.c: Use of || not && lead to dead code.Joel Sherrill1-4/+2
Coverity Id: 175333
2017-01-16Add missing headers to fix implicit function defnsPat Pannuto2-0/+2
A few files were missing headers for memset/malloc, likely missed because the files don't directly call the functions, rather they come in via macros in libc/include/sys/reent.h: #define _REENT_CHECK(var, what, type, size, init) do { \ struct _reent *_r = (var); \ if (_r->what == NULL) { \ _r->what = (type)malloc(size); \ #define _REENT_CHECK_ASCTIME_BUF(var) \ _REENT_CHECK(var, _asctime_buf, char *, _REENT_ASCTIME_SIZE, \ memset((var)->_asctime_buf, 0, _REENT_ASCTIME_SIZE)) Without these fixes, implicit function signatures are provided, which gcc warns could cause aliasing issues down the line: ../../../../../../../newlib-2.5.0/newlib/libc/time/asctime.c:62:3: warning: type of 'memset' does not match original declaration [-Wlto-type-mismatch] /Volumes/code/external/newlib-cygwin/newlib/libc/include/string.h:29:7: note: return value type mismatch _PTR _EXFUN(memset,(_PTR, int, size_t)); ^ /Volumes/code/external/newlib-cygwin/newlib/libc/include/string.h:29:7: note: 'memset' was previously declared here /Volumes/code/external/newlib-cygwin/newlib/libc/include/string.h:29:7: note: code may be misoptimized unless -fno-strict-aliasing is used ../../../../../../../newlib-2.5.0/newlib/libc/time/asctime.c:62:3: warning: type of 'malloc' does not match original declaration [-Wlto-type-mismatch] /Volumes/code/external/newlib-cygwin/newlib/libc/include/malloc.h:37:13: note: return value type mismatch extern _PTR malloc _PARAMS ((size_t)); ^ /Volumes/code/external/newlib-cygwin/newlib/libc/include/malloc.h:37:13: note: 'malloc' was previously declared here /Volumes/code/external/newlib-cygwin/newlib/libc/include/malloc.h:37:13: note: code may be misoptimized unless -fno-strict-aliasing is used ../../../../../../../newlib-2.5.0/newlib/libc/time/lcltime.c:58:3: warning: type of 'malloc' does not match original declaration [-Wlto-type-mismatch] /Volumes/code/external/newlib-cygwin/newlib/libc/include/malloc.h:37:13: note: return value type mismatch extern _PTR malloc _PARAMS ((size_t)); ^ /Volumes/code/external/newlib-cygwin/newlib/libc/include/malloc.h:37:13: note: 'malloc' was previously declared here /Volumes/code/external/newlib-cygwin/newlib/libc/include/malloc.h:37:13: note: code may be misoptimized unless -fno-strict-aliasing is used ../../../../../../../newlib-2.5.0/newlib/libc/string/strsignal.c:70:3: warning: type of 'malloc' does not match original declaration [-Wlto-type-mismatch] /Volumes/code/external/newlib-cygwin/newlib/libc/include/malloc.h:37:13: note: return value type mismatch extern _PTR malloc _PARAMS ((size_t)); ^ /Volumes/code/external/newlib-cygwin/newlib/libc/include/malloc.h:37:13: note: 'malloc' was previously declared here /Volumes/code/external/newlib-cygwin/newlib/libc/include/malloc.h:37:13: note: code may be misoptimized unless -fno-strict-aliasing is used Including the proper headers elminates the implicit function signatures and these warnings.
2016-12-22Bump release to 2.5.0 for yearly snapshot.newlib-2_5_0Jeff Johnston1-32/+18
2016-08-31Fix typo in strerror doccygwin-2_6_0-releaseCorinna Vinschen1-1/+1
Signed-off-by: Corinna Vinschen <corinna@vinschen.de>
2016-08-23strerror_l: Fix copy-and-paste typoEric Blake1-1/+1
Signed-off-by: Eric Blake <eblake@redhat.com>
2016-08-23Mention strerror_l in libc/string/strings.texCorinna Vinschen1-1/+1
Signed-off-by: Corinna Vinschen <corinna@vinschen.de>
2016-08-23Implement missing POSIX-1.2008 function strerror_lCorinna Vinschen1-1/+18
Signed-off-by: Corinna Vinschen <corinna@vinschen.de>
2016-08-21Remove extern declaration of __locale_cjk_lang in string/local.hCorinna Vinschen1-4/+0
Now that __locale_cjk_lang is an inline function in setlocale.h and setlocale.h is included, the declaration doesn't make sense. Signed-off-by: Corinna Vinschen <corinna@vinschen.de>
2016-08-15Implement per-locale string functionsCorinna Vinschen18-52/+576
strcasecmp_l, strcoll_l, strncasecmp_l, strxfrm_l, wcscasecmp_l, wcscoll_l, wcstrncasecmp_l, wcstrxfrm_l, strftime_l. Add missing CHEWOUT_FILES from previous patch. TODO: strfmon_l. Signed-off by: Corinna Vinschen <corinna@vinschen.de>
2016-07-04Regenerate newlib MakefilesJon Turney1-3/+16
2016-03-18Add timingsafe_memcmp()Sebastian Huber3-18/+73
This function is used by LibreSSL and OpenSSH and is provided by the OpenBSD libc. * libc/include/string.h (timingsafe_memcmp): Declare. * libc/string/timingsafe_memcmp.c: New file. * libc/string/Makefile.am: Add new file. * libc/string/Makefile.in: Regenerate.
2016-03-18Add timingsafe_bcmp()Sebastian Huber3-21/+58
This function is used by LibreSSL and OpenSSH and is provided by the OpenBSD libc. * libc/include/string.h (timingsafe_bcmp): Declare. * libc/string/timingsafe_bcmp.c: New file. * libc/string/Makefile.am: Add new file. * libc/string/Makefile.in: Regenerate.
2016-03-18Add explicit_bzero()Sebastian Huber3-46/+72
This function is used by LibreSSL and OpenSSH and is provided by the OpenBSD libc. * libc/include/string.h (explicit_bzero): Declare. * libc/string/explicit_bzero.c: New file. * libc/string/Makefile.am: Add new file. * libc/string/Makefile.in: Regenerate.
2016-02-12Fix compile with GCC 5 -WerrorYaakov Selkowitz1-1/+1
newlib/libc/ * stdio64/freopen64.c: Include <string.h> for memset(). * stdlib/quick_exit.c: Include <unistd.h> for _exit(). * string/gnu_basename.c (__gnu_basename): Fix discarded const qualifier warning. * stdlib/strtold.c: Include "mprec.h" for _strtorx_r(). Signed-off-by: Yaakov Selkowitz <yselkowi@redhat.com>
2015-11-02Move duplicated documentation rules to Makefile.sharedJeff Johnston2-21/+15
- Also, harmonize libm to use CHEWOUT_FILES like libc, rather than chobj. Update documentation appropriately. * HOWTO: Update. * Makefile.shared: Move documentation rules to here... * libc/argz/Makefile.am: ... from here ... * libc/ctype/Makefile.am: ... and here. * libc/errno/Makefile.am: Ditto. * libc/iconv/Makefile.am: Ditto. * libc/iconv/ccs/Makefile.am : Ditto. * libc/iconv/ces/Makefile.am: Ditto. * libc/iconv/lib/Makefile.am: Ditto. * libc/locale/Makefile.am: Ditto. * libc/misc/Makefile.am: Ditto. * libc/posix/Makefile.am: Ditto. * libc/reent/Makefile.am: Ditto. * libc/search/Makefile.am: Ditto. * libc/stdio/Makefile.am: Ditto. * libc/stdio64/Makefile.am: Ditto. * libc/stdlib/Makefile.am : Ditto. * libc/string/Makefile.am: Ditto. * libc/syscalls/Makefile.am: Ditto. * libc/time/Makefile.am : Ditto. * libc/unix/Makefile.am: Ditto. * libc/xdr/Makefile.am: Ditto. * libm/common/Makefile.am: Ditto. * libm/complex/Makefile.am: Ditto. * libm/math/Makefile.am: Ditto. * libm/mathfp/Makefile.am: Ditto.
2015-11-02Add missing semicolons to prototypes.Jeff Johnston2-8/+8
* libc/stdio/fseek.c: Add missing semicolons to prototypes in SYNOPSIS. * libc/stdio/fwide.c: Ditto. * libc/stdio64/fseeko64.c: Ditto. * libc/string/strtok.c: Ditto. * libc/string/wcstok.c: Ditto. * libm/math/w_cosh.c: Ditto. * libm/math/w_fmod.c: Ditto. * libm/mathfp/s_cosh.c: Ditto. * libm/mathfp/s_fmod.c: Ditto.
2015-06-29Regenerate Makefile.inJon TURNEY1-1/+1
Regenerate Makefile.in with changes in commits 153385d8 and 433aad91 2015-06-29 Jon Turney <jon.turney@dronecode.org.uk> * libc/ctype/Makefile.in: Regenerate. * libc/posix/Makefile.in: Ditto. * libc/stdio/Makefile.in: Ditto. * libc/stdio64/Makefile.in: Ditto. * libc/stdlib/Makefile.in: Ditto. * libc/string/Makefile.in: Ditto. Signed-off-by: Jon TURNEY <jon.turney@dronecode.org.uk>
2015-06-24Use source files which have makedoc markup, but aren't processed or included.newlib-snapshot-20150623Jon TURNEY2-1/+5
These source files have makedoc markup, but aren't listed to be chewed by makedoc. I am assuming that is accidental. Future work: Note that stdio/fseeko.c, stdio/ftello.c and common/s_isnand.c have makedoc markup, but duplicate stdio/fseek.c, stdio/ftell.c and common/s_isnan.c respectively. 2015-06-23 Jon Turney <jon.turney@dronecode.org.uk> * libc/ctype/Makefile.am (CHEWOUT_FILES): Add isblank.def. * libc/ctype/ctype.tex: Include isblank and add to menu. * libc/posix/Makefile.am (CHEWOUT_FILES): Add posix_spawn.def. * libc/posix/posix.tex: Include posix_spawn and add to menu. * libc/stdio64/Makefile.am (CHEWOUT_FILES): Add fdopen.def. * libc/stdio64/stdio64.tex: Include fdopen64 and add to menu. * libc/stdio64/fdopen64.c: Improve one-line description. * libc/string/Makefile.am (CHEWOUT_FILES): Add strchrnul.def. * libc/string/strings.tex: Include strchrnul and add to menu. Signed-off-by: Jon TURNEY <jon.turney@dronecode.org.uk>
2015-06-24Use makedoc output files which are generated but aren't includedJon TURNEY1-0/+8
I think these are accidental omissions, as these source files are listed to be chewed by makedoc, but the result is not included by any texinfo source file. Future work: Nothing in libc/reent/ which is processed by makedoc is included by reent.tex 2015-06-23 Jon Turney <jon.turney@dronecode.org.uk> * libc/stdlib/stdlib.tex: Include itoa and utoa, and add to menu. * libc/string/strings.tex: Include memrchr and rawmemchr, and add to menu. * libm/math/math.tex: Include exp10 and pow10, and add to menu. * libm/common/s_exp10.c: Improve one-line description. * libm/common/s_exp10.c: Ditto. Signed-off-by: Jon TURNEY <jon.turney@dronecode.org.uk>
generated by cgit v1.1 at 2026-02-06 00:44:12 +0000