Make strstr and strcasestr O(n), not O(n^2); add memmem.

* libc/string/str-two-way.h: New file.
* libc/string/memmem.c (memmem): New file.
* libc/include/string.h (memmem): Declare for all platforms.
* libc/string/strstr.c (strstr): Provide O(n) implementation when
not optimizing for space.
* libc/string/strcasestr.c (strcasestr): Likewise.
* libc/string/Makefile.am (ELIX_SOURCES): Rename to...
(ELIX_2_SOURCES): ...this.
(ELIX_4_SOURCES): New category, for memmem.
(lib_a_SOURCES, libstring_la_SOURCES): Build new file.
(CHEWOUT_FILES): Build documentation for memmem.
* libc/string/strings.tex: Include new docs.

1 files changed, 102 insertions, 0 deletions

diff --git a/newlib/libc/string/memmem.c b/newlib/libc/string/memmem.c
new file mode 100644
index 000000000..25704e467
--- /dev/null
+++ b/newlib/libc/string/memmem.c
@@ -0,0 +1,102 @@
+/* Byte-wise substring search, using the Two-Way algorithm.
+ * Copyright (C) 2008 Eric Blake
+ * Permission to use, copy, modify, and distribute this software
+ * is freely granted, provided that this notice is preserved.
+ */
+
+/*
+FUNCTION
+	<<memmem>>---find memory segment
+
+INDEX
+	memmem
+
+ANSI_SYNOPSIS
+	#include <string.h>
+	char *memmem(const void *<[s1]>, size_t <[l1]>, const void *<[s2]>,
+		     size_t <[l2]>);
+
+DESCRIPTION
+
+	Locates the first occurrence in the memory region pointed to
+	by <[s1]> with length <[l1]> of the sequence of bytes pointed
+	to by <[s2]> of length <[l2]>.  If you already know the
+	lengths of your haystack and needle, <<memmem>> can be much
+	faster than <<strstr>>.
+
+RETURNS
+	Returns a pointer to the located segment, or a null pointer if
+	<[s2]> is not found. If <[l2]> is 0, <[s1]> is returned.
+
+PORTABILITY
+<<memmem>> is a newlib extension.
+
+<<memmem>> requires no supporting OS subroutines.
+
+QUICKREF
+	memmem pure
+*/
+
+#include <string.h>
+
+#if !defined(PREFER_SIZE_OVER_SPEED) && !defined(__OPTIMIZE_SIZE__)
+# define RETURN_TYPE void *
+# define AVAILABLE(h, h_l, j, n_l) ((j) <= (h_l) - (n_l))
+# include "str-two-way.h"
+#endif
+
+void *
+_DEFUN (memmem, (haystack_start, haystack_len, needle_start, needle_len),
+	const void *haystack_start _AND
+	size_t haystack_len _AND
+	const void *needle_start _AND
+	size_t needle_len)
+{
+  /* Abstract memory is considered to be an array of 'unsigned char' values,
+     not an array of 'char' values.  See ISO C 99 section 6.2.6.1.  */
+  const unsigned char *haystack = (const unsigned char *) haystack_start;
+  const unsigned char *needle = (const unsigned char *) needle_start;
+
+  if (needle_len == 0)
+    /* The first occurrence of the empty string is deemed to occur at
+       the beginning of the string.  */
+    return (void *) haystack;
+
+#if defined(PREFER_SIZE_OVER_SPEED) || defined(__OPTIMIZE_SIZE__)
+
+  /* Less code size, but quadratic performance in the worst case.  */
+  while (needle_len <= haystack_len)
+    {
+      if (!memcmp (haystack, needle, needle_len))
+        return (void *) haystack;
+      haystack++;
+      haystack_len--;
+    }
+  return NULL;
+
+#else /* compilation for speed */
+
+  /* Larger code size, but guaranteed linear performance.  */
+
+  /* Sanity check, otherwise the loop might search through the whole
+     memory.  */
+  if (haystack_len < needle_len)
+    return NULL;
+
+  /* Use optimizations in memchr when possible, to reduce the search
+     size of haystack using a linear algorithm with a smaller
+     coefficient.  However, avoid memchr for long needles, since we
+     can often achieve sublinear performance.  */
+  if (needle_len < LONG_NEEDLE_THRESHOLD)
+    {
+      haystack = memchr (haystack, *needle, haystack_len);
+      if (!haystack || needle_len == 1)
+	return (void *) haystack;
+      haystack_len -= haystack - (const unsigned char *) haystack_start;
+      if (haystack_len < needle_len)
+	return NULL;
+      return two_way_short_needle (haystack, haystack_len, needle, needle_len);
+    }
+  return two_way_long_needle (haystack, haystack_len, needle, needle_len);
+#endif /* compilation for speed */
+}