--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,13 @@
+2011-01-21  Pádraig Brady  <P@draigBrady.com>
+            Bruno Haible  <bruno@clisp.org>
+
+	Prepare for faster uN_strstr functions.
+	* lib/str-kmp.h: Support definable UNITs.
+	(knuth_morris_pratt): Renamed from knuth_morris_pratt_unibyte. Add
+	needle_len argument.
+	* lib/mbsstr.c (mbsstr): Adjust for the changed str-kmp.h.
+	* lib/mbscasestr.c (mbscasestr): Likewise.
+
 2011-01-21  Pádraig Brady <P@draigBrady.com>
 
 	malloca-tests: make faster by unsetting MALLOC_PERTURB_

--- a/lib/mbscasestr.c
+++ b/lib/mbscasestr.c
@@ -30,6 +30,7 @@
 #define TOLOWER(Ch) (isupper (Ch) ? tolower (Ch) : (Ch))
 
 /* Knuth-Morris-Pratt algorithm.  */
+#define UNIT unsigned char
 #define CANON_ELEMENT(c) TOLOWER (c)
 #include "str-kmp.h"
 
@@ -368,10 +369,12 @@
                   if (needle_last_ccount == NULL)
                     {
                       /* Try the Knuth-Morris-Pratt algorithm.  */
-                      const char *result;
+                      const unsigned char *result;
                       bool success =
-                        knuth_morris_pratt_unibyte (haystack, needle - 1,
-                                                    &result);
+                        knuth_morris_pratt ((const unsigned char *) haystack,
+                                            (const unsigned char *) (needle - 1),
+                                            strlen (needle - 1),
+                                            &result);
                       if (success)
                         return (char *) result;
                       try_kmp = false;

--- a/lib/mbsstr.c
+++ b/lib/mbsstr.c
@@ -27,6 +27,7 @@
 #include "mbuiter.h"
 
 /* Knuth-Morris-Pratt algorithm.  */
+#define UNIT unsigned char
 #define CANON_ELEMENT(c) c
 #include "str-kmp.h"
 
@@ -339,10 +340,12 @@
                   if (needle_last_ccount == NULL)
                     {
                       /* Try the Knuth-Morris-Pratt algorithm.  */
-                      const char *result;
+                      const unsigned char *result;
                       bool success =
-                        knuth_morris_pratt_unibyte (haystack, needle - 1,
-                                                    &result);
+                        knuth_morris_pratt ((const unsigned char *) haystack,
+                                            (const unsigned char *) (needle - 1),
+                                            strlen (needle - 1),
+                                            &result);
                       if (success)
                         return (char *) result;
                       try_kmp = false;

--- a/lib/str-kmp.h
+++ b/lib/str-kmp.h
@@ -1,4 +1,4 @@
-/* Substring search in a NUL terminated string of 'char' elements,
+/* Substring search in a NUL terminated string of UNIT elements,
    using the Knuth-Morris-Pratt algorithm.
    Copyright (C) 2005-2011 Free Software Foundation, Inc.
    Written by Bruno Haible <bruno@clisp.org>, 2005.
@@ -18,21 +18,26 @@
    Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
 
 /* Before including this file, you need to define:
+     UNIT                    The element type of the needle and haystack.
      CANON_ELEMENT(c)        A macro that canonicalizes an element right after
-                             it has been fetched from one of the two strings.
-                             The argument is an 'unsigned char'; the result
-                             must be an 'unsigned char' as well.  */
+                             it has been fetched from needle or haystack.
+                             The argument is of type UNIT; the result must be
+                             of type UNIT as well.  */
 
 /* Knuth-Morris-Pratt algorithm.
    See http://en.wikipedia.org/wiki/Knuth-Morris-Pratt_algorithm
+   HAYSTACK is the NUL terminated string in which to search for.
+   NEEDLE is the string to search for in HAYSTACK, consisting of NEEDLE_LEN
+   units.
    Return a boolean indicating success:
    Return true and set *RESULTP if the search was completed.
    Return false if it was aborted because not enough memory was available.  */
 static bool
-knuth_morris_pratt_unibyte (const char *haystack, const char *needle,
-                            const char **resultp)
+knuth_morris_pratt (const UNIT *haystack,
+                    const UNIT *needle, size_t needle_len,
+                    const UNIT **resultp)
 {
-  size_t m = strlen (needle);
+  size_t m = needle_len;
 
   /* Allocate the table.  */
   size_t *table = (size_t *) nmalloca (m, sizeof (size_t));
@@ -66,14 +71,14 @@
            The inequality needle[x..i-1] != needle[0..i-1-x] is known to hold
            for x < table[i-1], by induction.
            Furthermore, if j>0: needle[i-1-j..i-2] = needle[0..j-1].  */
-        unsigned char b = CANON_ELEMENT ((unsigned char) needle[i - 1]);
+        UNIT b = CANON_ELEMENT (needle[i - 1]);
 
         for (;;)
           {
             /* Invariants: The inequality needle[x..i-1] != needle[0..i-1-x]
                is known to hold for x < i-1-j.
                Furthermore, if j>0: needle[i-1-j..i-2] = needle[0..j-1].  */
-            if (b == CANON_ELEMENT ((unsigned char) needle[j]))
+            if (b == CANON_ELEMENT (needle[j]))
               {
                 /* Set table[i] := i-1-j.  */
                 table[i] = i - ++j;
@@ -108,17 +113,16 @@
   /* Search, using the table to accelerate the processing.  */
   {
     size_t j;
-    const char *rhaystack;
-    const char *phaystack;
+    const UNIT *rhaystack;
+    const UNIT *phaystack;
 
     *resultp = NULL;
     j = 0;
     rhaystack = haystack;
     phaystack = haystack;
     /* Invariant: phaystack = rhaystack + j.  */
-    while (*phaystack != '\0')
-      if (CANON_ELEMENT ((unsigned char) needle[j])
-          == CANON_ELEMENT ((unsigned char) *phaystack))
+    while (*phaystack != 0)
+      if (CANON_ELEMENT (needle[j]) == CANON_ELEMENT (*phaystack))
         {
           j++;
           phaystack++;