svn commit: r315468 - head/lib/libc/string

[Ed Maste]

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;