--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,16 @@
+2008-01-09  Simon Josefsson  <simon@josefsson.org>
+	and Eric Blake  <ebb9@byu.net>
+
+	Add memmem-simple module.
+	* m4/memmem.m4 (gl_FUNC_MEMMEM_SIMPLE): New macro.
+	(gl_FUNC_MEMMEM): Separate performance from presence checks.
+	* modules/memmem-simple: New file.
+	* modules/memmem (Description): Tweak.
+	* MODULES.html.sh (string handling): Mention new module.
+	* doc/functions/memmem.texi (memmem): Distinguish which flaws are
+	addressed by memmem-simple.
+	* NEWS: Document the difference.
+
 2008-01-09  Eric Blake  <ebb9@byu.net>
 
 	Give gcc some memmem optimization hints.
@@ -12,7 +25,7 @@
 	* build-aux/config.rpath: Likewise.
 
 2008-01-08  Jim Meyering  <meyering@redhat.com>
-            Bruno Haible  <bruno@clisp.org>
+	    Bruno Haible  <bruno@clisp.org>
 
 	* lib/printf-parse.c (PRINTF_PARSE): Handle a size specifier "q"
 	on MacOS X and a size specifier "I64" on mingw. Needed for PRIdMAX.

--- a/MODULES.html.sh
+++ b/MODULES.html.sh
@@ -1,6 +1,6 @@
 #!/bin/sh
 #
-# Copyright (C) 2002-2007 Free Software Foundation, Inc.
+# Copyright (C) 2002-2008 Free Software Foundation, Inc.
 #
 # This program is free software: you can redistribute it and/or modify
 # it under the terms of the GNU General Public License as published by
@@ -1654,6 +1654,7 @@
   func_begin_table
   func_module bcopy
   func_module memmem
+  func_module memmem-simple
   func_module mempcpy
   func_module memrchr
   func_module stpcpy

--- a/NEWS
+++ b/NEWS
@@ -6,6 +6,12 @@
 
 Date        Modules         Changes
 
+2008-01-08  memmem          This module now replaces worst-case inefficient
+                            implementations; clients that use controlled
+                            needles and thus do not care about worst-case
+                            efficiency should use the new memmem-simple
+                            module instead for smaller code size.
+
 2007-12-24  setenv          The include file is changed from "setenv.h" to
                             <stdlib.h>. Also, the unsetenv function is no
                             longer declared in this module; use the 'unsetenv'

--- a/doc/functions/memmem.texi
+++ b/doc/functions/memmem.texi
@@ -4,7 +4,7 @@
 
 Unspecified by POSIX, but comparable to @code{strstr}.
 
-Gnulib module: memmem
+Gnulib module: memmem, memmem-simple
 
 Portability problems fixed by Gnulib:
 @itemize
@@ -14,12 +14,12 @@
 
 @item
 This function returns incorrect values in some cases, such as when
-given an empty needle:
+given an empty needle (not fixed in memmem-simple):
 glibc <= 2.0, cygwin 1.5.x
 
 @item
 This function has quadratic instead of linear complexity on some
-platforms:
+platforms (not fixed in memmem-simple):
 glibc <= 2.6.1, cygwin 1.5.x
 
 @item

--- a/m4/memmem.m4
+++ b/m4/memmem.m4
@@ -1,10 +1,11 @@
-# memmem.m4 serial 7
+# memmem.m4 serial 8
 dnl Copyright (C) 2002, 2003, 2004, 2007, 2008 Free Software Foundation, Inc.
 dnl This file is free software; the Free Software Foundation
 dnl gives unlimited permission to copy and/or distribute it,
 dnl with or without modifications, as long as this notice is preserved.
 
-AC_DEFUN([gl_FUNC_MEMMEM],
+dnl Check that memmem is present.
+AC_DEFUN([gl_FUNC_MEMMEM_SIMPLE],
 [
   dnl Persuade glibc <string.h> to declare memmem().
   AC_REQUIRE([AC_USE_SYSTEM_EXTENSIONS])
@@ -14,7 +15,15 @@
   AC_CHECK_DECLS_ONCE(memmem)
   if test $ac_cv_have_decl_memmem = no; then
     HAVE_DECL_MEMMEM=0
-  else
+  fi
+  gl_PREREQ_MEMMEM
+]) # gl_FUNC_MEMMEM_SIMPLE
+
+dnl Additionally, check that memmem is efficient and handles empty needles.
+AC_DEFUN([gl_FUNC_MEMMEM],
+[
+  AC_REQUIRE([gl_FUNC_MEMMEM_SIMPLE])
+  if test $ac_cv_have_decl_memmem = yes; then
     AC_CACHE_CHECK([whether memmem works in linear time],
       [gl_cv_func_memmem_works],
       [AC_RUN_IFELSE([AC_LANG_PROGRAM([
@@ -28,6 +37,7 @@
     /* Failure to compile this test due to missing alarm is okay,
        since all such platforms (mingw) also lack memmem.  */
     alarm (5);
+    /* Check for quadratic performance.  */
     if (haystack && needle)
       {
 	memset (haystack, 'A', 2 * m);
@@ -36,6 +46,7 @@
 	needle[m] = 'B';
 	result = memmem (haystack, 2 * m + 1, needle, m + 1);
       }
+    /* Check for empty needle behavior.  */
     return !result || !memmem ("a", 1, 0, 0);]])],
 	[gl_cv_func_memmem_works=yes], [gl_cv_func_memmem_works=no],
 	[dnl pessimistically assume the worst, since even glibc 2.6.1
@@ -46,8 +57,7 @@
       AC_LIBOBJ([memmem])
     fi
   fi
-  gl_PREREQ_MEMMEM
-])
+]) # gl_FUNC_MEMMEM
 
 # Prerequisites of lib/memmem.c.
 AC_DEFUN([gl_PREREQ_MEMMEM], [:])

--- a/modules/memmem
+++ b/modules/memmem
@@ -1,5 +1,5 @@
 Description:
-memmem() function: locate first substring in a buffer.
+memmem() function: efficiently locate first substring in a buffer.
 
 Files:
 lib/memmem.c

new file mode 100644
--- /dev/null
+++ b/modules/memmem-simple
@@ -0,0 +1,28 @@
+Description:
+memmem() function: locate first substring in a buffer.
+
+Files:
+lib/memmem.c
+m4/memmem.m4
+
+Depends-on:
+extensions
+string
+stdint
+memchr
+memcmp
+
+configure.ac:
+gl_FUNC_MEMMEM_SIMPLE
+gl_STRING_MODULE_INDICATOR([memmem])
+
+Makefile.am:
+
+Include:
+<string.h>
+
+License:
+LGPLv2+
+
+Maintainer:
+libc, Eric Blake, Simon Josefsson