From owner-svn-src-head@freebsd.org Sat Mar 18 00:53:25 2017 Return-Path: Delivered-To: svn-src-head@mailman.ysv.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:1900:2254:206a::19:1]) by mailman.ysv.freebsd.org (Postfix) with ESMTP id EC7C9D1011B; Sat, 18 Mar 2017 00:53:25 +0000 (UTC) (envelope-from emaste@FreeBSD.org) Received: from repo.freebsd.org (repo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:0]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client did not present a certificate) by mx1.freebsd.org (Postfix) with ESMTPS id A0E4819E8; Sat, 18 Mar 2017 00:53:25 +0000 (UTC) (envelope-from emaste@FreeBSD.org) Received: from repo.freebsd.org ([127.0.1.37]) by repo.freebsd.org (8.15.2/8.15.2) with ESMTP id v2I0rOhF030730; Sat, 18 Mar 2017 00:53:24 GMT (envelope-from emaste@FreeBSD.org) Received: (from emaste@localhost) by repo.freebsd.org (8.15.2/8.15.2/Submit) id v2I0rOCt030727; Sat, 18 Mar 2017 00:53:24 GMT (envelope-from emaste@FreeBSD.org) Message-Id: <201703180053.v2I0rOCt030727@repo.freebsd.org> X-Authentication-Warning: repo.freebsd.org: emaste set sender to emaste@FreeBSD.org using -f From: Ed Maste Date: Sat, 18 Mar 2017 00:53:24 +0000 (UTC) To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r315468 - head/lib/libc/string X-SVN-Group: head MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-BeenThere: svn-src-head@freebsd.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: SVN commit messages for the src tree for head/-current List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 18 Mar 2017 00:53:26 -0000 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;