Date: Sat, 18 Mar 2017 00:53:24 +0000 (UTC) From: Ed Maste <emaste@FreeBSD.org> To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r315468 - head/lib/libc/string Message-ID: <201703180053.v2I0rOCt030727@repo.freebsd.org>
next in thread | raw e-mail | index | archive | help
Author: emaste Date: Sat Mar 18 00:53:24 2017 New Revision: 315468 URL: https://svnweb.freebsd.org/changeset/base/315468 Log: libc: add reference to two-way algorithm and bad shift table in memmem/strstr Requested by: ed Modified: head/lib/libc/string/memmem.c head/lib/libc/string/strstr.c Modified: head/lib/libc/string/memmem.c ============================================================================== --- head/lib/libc/string/memmem.c Sat Mar 18 00:51:39 2017 (r315467) +++ head/lib/libc/string/memmem.c Sat Mar 18 00:53:24 2017 (r315468) @@ -58,6 +58,14 @@ static char *fourbyte_memmem(const unsig #define BITOP(a,b,op) \ ((a)[(size_t)(b)/(8*sizeof *(a))] op (size_t)1<<((size_t)(b)%(8*sizeof *(a)))) +/* + * Two Way string search algorithm, with a bad shift table applied to the last + * byte of the window. A bit array marks which entries in the shift table are + * initialized to avoid fully initializing a 1kb/2kb table. + * + * Reference: CROCHEMORE M., PERRIN D., 1991, Two-way string-matching, + * Journal of the ACM 38(3):651-675 + */ static char *twoway_memmem(const unsigned char *h, const unsigned char *z, const unsigned char *n, size_t l) { size_t i, ip, jp, k, p, ms, p0, mem, mem0; Modified: head/lib/libc/string/strstr.c ============================================================================== --- head/lib/libc/string/strstr.c Sat Mar 18 00:51:39 2017 (r315467) +++ head/lib/libc/string/strstr.c Sat Mar 18 00:53:24 2017 (r315468) @@ -55,6 +55,14 @@ static char *fourbyte_strstr(const unsig #define BITOP(a,b,op) \ ((a)[(size_t)(b)/(8*sizeof *(a))] op (size_t)1<<((size_t)(b)%(8*sizeof *(a)))) +/* + * Two Way string search algorithm, with a bad shift table applied to the last + * byte of the window. A bit array marks which entries in the shift table are + * initialized to avoid fully initializing a 1kb/2kb table. + * + * Reference: CROCHEMORE M., PERRIN D., 1991, Two-way string-matching, + * Journal of the ACM 38(3):651-675 + */ static char *twoway_strstr(const unsigned char *h, const unsigned char *n) { const unsigned char *z;
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201703180053.v2I0rOCt030727>