Tune by using memchr and memrchr.

* .bzrignore: Add string.h.
* admin/merge-gnulib (GNULIB_MODULES): Add memrchr.
* lib/gnulib.mk, m4/gnulib-comp.m4: Regenerate.
* lib/memrchr.c, lib/string.in.h, m4/memrchr.m4, m4/string_h.m4:
New files, from gnulib.
* src/doc.c (Fsnarf_documentation):
* src/fileio.c (Fsubstitute_in_file_name):
* src/search.c (find_newline, scan_newline):
* src/xdisp.c (pos_visible_p, display_count_lines):
Use memchr and memrchr rather than scanning byte-by-byte.
* src/search.c (find_newline): Rename from scan_buffer.
Omit first arg TARGET, as it's always '\n'.  All callers changed.

17 files changed, 1619 insertions, 160 deletions

diff --git a/ChangeLog b/ChangeLog
index d5ca6c17b5..0da3969fa1 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,11 @@
 2013-02-11  Paul Eggert  <[email protected]>
 
+	Tune by using memchr and memrchr.
+	* .bzrignore: Add string.h.
+	* lib/gnulib.mk, m4/gnulib-comp.m4: Regenerate.
+	* lib/memrchr.c, lib/string.in.h, m4/memrchr.m4, m4/string_h.m4:
+	New files, from gnulib.
+
 	Merge from gnulib, incorporating:
 	2013-02-11 unsetenv etc.: port to Solaris 11 + GNU Emacs
 	2013-02-09 secure_getenv: fix C++ declaration typo
diff --git a/admin/ChangeLog b/admin/ChangeLog
index 76ac11446a..7e72e10cd9 100644
--- a/admin/ChangeLog
+++ b/admin/ChangeLog
@@ -1,3 +1,8 @@
+2013-02-11  Paul Eggert  <[email protected]>
+
+	Tune by using memchr and memrchr.
+	* merge-gnulib (GNULIB_MODULES): Add memrchr.
+
 2013-02-01  Paul Eggert  <[email protected]>
 
 	Use fdopendir, fstatat and readlinkat, for efficiency (Bug#13539).
diff --git a/admin/merge-gnulib b/admin/merge-gnulib
index e90e2e23b2..b43f2bd9bb 100755
--- a/admin/merge-gnulib
+++ b/admin/merge-gnulib
@@ -31,7 +31,8 @@ GNULIB_MODULES='
   dtoastr dtotimespec dup2 environ execinfo faccessat
   fcntl-h fdopendir filemode fstatat getloadavg getopt-gnu gettime gettimeofday
   ignore-value intprops largefile lstat
-  manywarnings mktime pselect pthread_sigmask putenv readlink readlinkat
+  manywarnings memrchr mktime
+  pselect pthread_sigmask putenv readlink readlinkat
   sig2str socklen stat-time stdalign stdarg stdbool stdio
   strftime strtoimax strtoumax symlink sys_stat
   sys_time time timer-time timespec-add timespec-sub unsetenv utimens
diff --git a/lib/gnulib.mk b/lib/gnulib.mk
index 8103eec88a..c130cbc65b 100644
--- a/lib/gnulib.mk
+++ b/lib/gnulib.mk
@@ -21,7 +21,7 @@
 # the same distribution terms as the rest of that program.
 #
 # Generated by gnulib-tool.
-# Reproduce by: gnulib-tool --import --dir=. --lib=libgnu --source-base=lib --m4-base=m4 --doc-base=doc --tests-base=tests --aux-dir=build-aux --avoid=dup --avoid=errno --avoid=fchdir --avoid=fcntl --avoid=fstat --avoid=malloc-posix --avoid=msvc-inval --avoid=msvc-nothrow --avoid=open --avoid=openat-die --avoid=opendir --avoid=raise --avoid=save-cwd --avoid=select --avoid=sigprocmask --avoid=sys_types --avoid=threadlib --makefile-name=gnulib.mk --conditional-dependencies --no-libtool --macro-prefix=gl --no-vc-files alloca-opt c-ctype c-strcase careadlinkat close-stream crypto/md5 crypto/sha1 crypto/sha256 crypto/sha512 dtoastr dtotimespec dup2 environ execinfo faccessat fcntl-h fdopendir filemode fstatat getloadavg getopt-gnu gettime gettimeofday ignore-value intprops largefile lstat manywarnings mktime pselect pthread_sigmask putenv readlink readlinkat sig2str socklen stat-time stdalign stdarg stdbool stdio strftime strtoimax strtoumax symlink sys_stat sys_time time timer-time timespec-add timespec-sub unsetenv utimens warnings
+# Reproduce by: gnulib-tool --import --dir=. --lib=libgnu --source-base=lib --m4-base=m4 --doc-base=doc --tests-base=tests --aux-dir=build-aux --avoid=dup --avoid=errno --avoid=fchdir --avoid=fcntl --avoid=fstat --avoid=malloc-posix --avoid=msvc-inval --avoid=msvc-nothrow --avoid=open --avoid=openat-die --avoid=opendir --avoid=raise --avoid=save-cwd --avoid=select --avoid=sigprocmask --avoid=sys_types --avoid=threadlib --makefile-name=gnulib.mk --conditional-dependencies --no-libtool --macro-prefix=gl --no-vc-files alloca-opt c-ctype c-strcase careadlinkat close-stream crypto/md5 crypto/sha1 crypto/sha256 crypto/sha512 dtoastr dtotimespec dup2 environ execinfo faccessat fcntl-h fdopendir filemode fstatat getloadavg getopt-gnu gettime gettimeofday ignore-value intprops largefile lstat manywarnings memrchr mktime pselect pthread_sigmask putenv readlink readlinkat sig2str socklen stat-time stdalign stdarg stdbool stdio strftime strtoimax strtoumax symlink sys_stat sys_time time timer-time timespec-add timespec-sub unsetenv utimens warnings
 
 
 MOSTLYCLEANFILES += core *.stackdump
@@ -480,6 +480,15 @@ EXTRA_libgnu_a_SOURCES += lstat.c
 
 ## end   gnulib module lstat
 
+## begin gnulib module memrchr
+
+
+EXTRA_DIST += memrchr.c
+
+EXTRA_libgnu_a_SOURCES += memrchr.c
+
+## end   gnulib module memrchr
+
 ## begin gnulib module mktime
 
 
@@ -1105,6 +1114,106 @@ EXTRA_DIST += strftime.h
 
 ## end   gnulib module strftime
 
+## begin gnulib module string
+
+BUILT_SOURCES += string.h
+
+# We need the following in order to create <string.h> when the system
+# doesn't have one that works with the given compiler.
+string.h: string.in.h $(top_builddir)/config.status $(CXXDEFS_H) $(ARG_NONNULL_H) $(WARN_ON_USE_H)
+	$(AM_V_GEN)rm -f $@-t $@ && \
+	{ echo '/* DO NOT EDIT! GENERATED AUTOMATICALLY! */' && \
+	  sed -e 's|@''GUARD_PREFIX''@|GL|g' \
+	      -e 's|@''INCLUDE_NEXT''@|$(INCLUDE_NEXT)|g' \
+	      -e 's|@''PRAGMA_SYSTEM_HEADER''@|@PRAGMA_SYSTEM_HEADER@|g' \
+	      -e 's|@''PRAGMA_COLUMNS''@|@PRAGMA_COLUMNS@|g' \
+	      -e 's|@''NEXT_STRING_H''@|$(NEXT_STRING_H)|g' \
+	      -e 's/@''GNULIB_FFSL''@/$(GNULIB_FFSL)/g' \
+	      -e 's/@''GNULIB_FFSLL''@/$(GNULIB_FFSLL)/g' \
+	      -e 's/@''GNULIB_MBSLEN''@/$(GNULIB_MBSLEN)/g' \
+	      -e 's/@''GNULIB_MBSNLEN''@/$(GNULIB_MBSNLEN)/g' \
+	      -e 's/@''GNULIB_MBSCHR''@/$(GNULIB_MBSCHR)/g' \
+	      -e 's/@''GNULIB_MBSRCHR''@/$(GNULIB_MBSRCHR)/g' \
+	      -e 's/@''GNULIB_MBSSTR''@/$(GNULIB_MBSSTR)/g' \
+	      -e 's/@''GNULIB_MBSCASECMP''@/$(GNULIB_MBSCASECMP)/g' \
+	      -e 's/@''GNULIB_MBSNCASECMP''@/$(GNULIB_MBSNCASECMP)/g' \
+	      -e 's/@''GNULIB_MBSPCASECMP''@/$(GNULIB_MBSPCASECMP)/g' \
+	      -e 's/@''GNULIB_MBSCASESTR''@/$(GNULIB_MBSCASESTR)/g' \
+	      -e 's/@''GNULIB_MBSCSPN''@/$(GNULIB_MBSCSPN)/g' \
+	      -e 's/@''GNULIB_MBSPBRK''@/$(GNULIB_MBSPBRK)/g' \
+	      -e 's/@''GNULIB_MBSSPN''@/$(GNULIB_MBSSPN)/g' \
+	      -e 's/@''GNULIB_MBSSEP''@/$(GNULIB_MBSSEP)/g' \
+	      -e 's/@''GNULIB_MBSTOK_R''@/$(GNULIB_MBSTOK_R)/g' \
+	      -e 's/@''GNULIB_MEMCHR''@/$(GNULIB_MEMCHR)/g' \
+	      -e 's/@''GNULIB_MEMMEM''@/$(GNULIB_MEMMEM)/g' \
+	      -e 's/@''GNULIB_MEMPCPY''@/$(GNULIB_MEMPCPY)/g' \
+	      -e 's/@''GNULIB_MEMRCHR''@/$(GNULIB_MEMRCHR)/g' \
+	      -e 's/@''GNULIB_RAWMEMCHR''@/$(GNULIB_RAWMEMCHR)/g' \
+	      -e 's/@''GNULIB_STPCPY''@/$(GNULIB_STPCPY)/g' \
+	      -e 's/@''GNULIB_STPNCPY''@/$(GNULIB_STPNCPY)/g' \
+	      -e 's/@''GNULIB_STRCHRNUL''@/$(GNULIB_STRCHRNUL)/g' \
+	      -e 's/@''GNULIB_STRDUP''@/$(GNULIB_STRDUP)/g' \
+	      -e 's/@''GNULIB_STRNCAT''@/$(GNULIB_STRNCAT)/g' \
+	      -e 's/@''GNULIB_STRNDUP''@/$(GNULIB_STRNDUP)/g' \
+	      -e 's/@''GNULIB_STRNLEN''@/$(GNULIB_STRNLEN)/g' \
+	      -e 's/@''GNULIB_STRPBRK''@/$(GNULIB_STRPBRK)/g' \
+	      -e 's/@''GNULIB_STRSEP''@/$(GNULIB_STRSEP)/g' \
+	      -e 's/@''GNULIB_STRSTR''@/$(GNULIB_STRSTR)/g' \
+	      -e 's/@''GNULIB_STRCASESTR''@/$(GNULIB_STRCASESTR)/g' \
+	      -e 's/@''GNULIB_STRTOK_R''@/$(GNULIB_STRTOK_R)/g' \
+	      -e 's/@''GNULIB_STRERROR''@/$(GNULIB_STRERROR)/g' \
+	      -e 's/@''GNULIB_STRERROR_R''@/$(GNULIB_STRERROR_R)/g' \
+	      -e 's/@''GNULIB_STRSIGNAL''@/$(GNULIB_STRSIGNAL)/g' \
+	      -e 's/@''GNULIB_STRVERSCMP''@/$(GNULIB_STRVERSCMP)/g' \
+	      < $(srcdir)/string.in.h | \
+	  sed -e 's|@''HAVE_FFSL''@|$(HAVE_FFSL)|g' \
+	      -e 's|@''HAVE_FFSLL''@|$(HAVE_FFSLL)|g' \
+	      -e 's|@''HAVE_MBSLEN''@|$(HAVE_MBSLEN)|g' \
+	      -e 's|@''HAVE_MEMCHR''@|$(HAVE_MEMCHR)|g' \
+	      -e 's|@''HAVE_DECL_MEMMEM''@|$(HAVE_DECL_MEMMEM)|g' \
+	      -e 's|@''HAVE_MEMPCPY''@|$(HAVE_MEMPCPY)|g' \
+	      -e 's|@''HAVE_DECL_MEMRCHR''@|$(HAVE_DECL_MEMRCHR)|g' \
+	      -e 's|@''HAVE_RAWMEMCHR''@|$(HAVE_RAWMEMCHR)|g' \
+	      -e 's|@''HAVE_STPCPY''@|$(HAVE_STPCPY)|g' \
+	      -e 's|@''HAVE_STPNCPY''@|$(HAVE_STPNCPY)|g' \
+	      -e 's|@''HAVE_STRCHRNUL''@|$(HAVE_STRCHRNUL)|g' \
+	      -e 's|@''HAVE_DECL_STRDUP''@|$(HAVE_DECL_STRDUP)|g' \
+	      -e 's|@''HAVE_DECL_STRNDUP''@|$(HAVE_DECL_STRNDUP)|g' \
+	      -e 's|@''HAVE_DECL_STRNLEN''@|$(HAVE_DECL_STRNLEN)|g' \
+	      -e 's|@''HAVE_STRPBRK''@|$(HAVE_STRPBRK)|g' \
+	      -e 's|@''HAVE_STRSEP''@|$(HAVE_STRSEP)|g' \
+	      -e 's|@''HAVE_STRCASESTR''@|$(HAVE_STRCASESTR)|g' \
+	      -e 's|@''HAVE_DECL_STRTOK_R''@|$(HAVE_DECL_STRTOK_R)|g' \
+	      -e 's|@''HAVE_DECL_STRERROR_R''@|$(HAVE_DECL_STRERROR_R)|g' \
+	      -e 's|@''HAVE_DECL_STRSIGNAL''@|$(HAVE_DECL_STRSIGNAL)|g' \
+	      -e 's|@''HAVE_STRVERSCMP''@|$(HAVE_STRVERSCMP)|g' \
+	      -e 's|@''REPLACE_STPNCPY''@|$(REPLACE_STPNCPY)|g' \
+	      -e 's|@''REPLACE_MEMCHR''@|$(REPLACE_MEMCHR)|g' \
+	      -e 's|@''REPLACE_MEMMEM''@|$(REPLACE_MEMMEM)|g' \
+	      -e 's|@''REPLACE_STRCASESTR''@|$(REPLACE_STRCASESTR)|g' \
+	      -e 's|@''REPLACE_STRCHRNUL''@|$(REPLACE_STRCHRNUL)|g' \
+	      -e 's|@''REPLACE_STRDUP''@|$(REPLACE_STRDUP)|g' \
+	      -e 's|@''REPLACE_STRSTR''@|$(REPLACE_STRSTR)|g' \
+	      -e 's|@''REPLACE_STRERROR''@|$(REPLACE_STRERROR)|g' \
+	      -e 's|@''REPLACE_STRERROR_R''@|$(REPLACE_STRERROR_R)|g' \
+	      -e 's|@''REPLACE_STRNCAT''@|$(REPLACE_STRNCAT)|g' \
+	      -e 's|@''REPLACE_STRNDUP''@|$(REPLACE_STRNDUP)|g' \
+	      -e 's|@''REPLACE_STRNLEN''@|$(REPLACE_STRNLEN)|g' \
+	      -e 's|@''REPLACE_STRSIGNAL''@|$(REPLACE_STRSIGNAL)|g' \
+	      -e 's|@''REPLACE_STRTOK_R''@|$(REPLACE_STRTOK_R)|g' \
+	      -e 's|@''UNDEFINE_STRTOK_R''@|$(UNDEFINE_STRTOK_R)|g' \
+	      -e '/definitions of _GL_FUNCDECL_RPL/r $(CXXDEFS_H)' \
+	      -e '/definition of _GL_ARG_NONNULL/r $(ARG_NONNULL_H)' \
+	      -e '/definition of _GL_WARN_ON_USE/r $(WARN_ON_USE_H)'; \
+	      < $(srcdir)/string.in.h; \
+	} > $@-t && \
+	mv $@-t $@
+MOSTLYCLEANFILES += string.h string.h-t
+
+EXTRA_DIST += string.in.h
+
+## end   gnulib module string
+
 ## begin gnulib module strtoimax
 
 
diff --git a/lib/memrchr.c b/lib/memrchr.c
new file mode 100644
index 0000000000..5a023e0638
--- /dev/null
+++ b/lib/memrchr.c
@@ -0,0 +1,161 @@
+/* memrchr -- find the last occurrence of a byte in a memory block
+
+   Copyright (C) 1991, 1993, 1996-1997, 1999-2000, 2003-2013 Free Software
+   Foundation, Inc.
+
+   Based on strlen implementation by Torbjorn Granlund ([email protected]),
+   with help from Dan Sahlin ([email protected]) and
+   commentary by Jim Blandy ([email protected]);
+   adaptation to memchr suggested by Dick Karpinski ([email protected]),
+   and implemented by Roland McGrath ([email protected]).
+
+   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
+   the Free Software Foundation; either version 3 of the License, or
+   (at your option) any later version.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
+
+#if defined _LIBC
+# include <memcopy.h>
+#else
+# include <config.h>
+# define reg_char char
+#endif
+
+#include <string.h>
+#include <limits.h>
+
+#undef __memrchr
+#ifdef _LIBC
+# undef memrchr
+#endif
+
+#ifndef weak_alias
+# define __memrchr memrchr
+#endif
+
+/* Search no more than N bytes of S for C.  */
+void *
+__memrchr (void const *s, int c_in, size_t n)
+{
+  /* On 32-bit hardware, choosing longword to be a 32-bit unsigned
+     long instead of a 64-bit uintmax_t tends to give better
+     performance.  On 64-bit hardware, unsigned long is generally 64
+     bits already.  Change this typedef to experiment with
+     performance.  */
+  typedef unsigned long int longword;
+
+  const unsigned char *char_ptr;
+  const longword *longword_ptr;
+  longword repeated_one;
+  longword repeated_c;
+  unsigned reg_char c;
+
+  c = (unsigned char) c_in;
+
+  /* Handle the last few bytes by reading one byte at a time.
+     Do this until CHAR_PTR is aligned on a longword boundary.  */
+  for (char_ptr = (const unsigned char *) s + n;
+       n > 0 && (size_t) char_ptr % sizeof (longword) != 0;
+       --n)
+    if (*--char_ptr == c)
+      return (void *) char_ptr;
+
+  longword_ptr = (const longword *) char_ptr;
+
+  /* All these elucidatory comments refer to 4-byte longwords,
+     but the theory applies equally well to any size longwords.  */
+
+  /* Compute auxiliary longword values:
+     repeated_one is a value which has a 1 in every byte.
+     repeated_c has c in every byte.  */
+  repeated_one = 0x01010101;
+  repeated_c = c | (c << 8);
+  repeated_c |= repeated_c << 16;
+  if (0xffffffffU < (longword) -1)
+    {
+      repeated_one |= repeated_one << 31 << 1;
+      repeated_c |= repeated_c << 31 << 1;
+      if (8 < sizeof (longword))
+        {
+          size_t i;
+
+          for (i = 64; i < sizeof (longword) * 8; i *= 2)
+            {
+              repeated_one |= repeated_one << i;
+              repeated_c |= repeated_c << i;
+            }
+        }
+    }
+
+  /* Instead of the traditional loop which tests each byte, we will test a
+     longword at a time.  The tricky part is testing if *any of the four*
+     bytes in the longword in question are equal to c.  We first use an xor
+     with repeated_c.  This reduces the task to testing whether *any of the
+     four* bytes in longword1 is zero.
+
+     We compute tmp =
+       ((longword1 - repeated_one) & ~longword1) & (repeated_one << 7).
+     That is, we perform the following operations:
+       1. Subtract repeated_one.
+       2. & ~longword1.
+       3. & a mask consisting of 0x80 in every byte.
+     Consider what happens in each byte:
+       - If a byte of longword1 is zero, step 1 and 2 transform it into 0xff,
+         and step 3 transforms it into 0x80.  A carry can also be propagated
+         to more significant bytes.
+       - If a byte of longword1 is nonzero, let its lowest 1 bit be at
+         position k (0 <= k <= 7); so the lowest k bits are 0.  After step 1,
+         the byte ends in a single bit of value 0 and k bits of value 1.
+         After step 2, the result is just k bits of value 1: 2^k - 1.  After
+         step 3, the result is 0.  And no carry is produced.
+     So, if longword1 has only non-zero bytes, tmp is zero.
+     Whereas if longword1 has a zero byte, call j the position of the least
+     significant zero byte.  Then the result has a zero at positions 0, ...,
+     j-1 and a 0x80 at position j.  We cannot predict the result at the more
+     significant bytes (positions j+1..3), but it does not matter since we
+     already have a non-zero bit at position 8*j+7.
+
+     So, the test whether any byte in longword1 is zero is equivalent to
+     testing whether tmp is nonzero.  */
+
+  while (n >= sizeof (longword))
+    {
+      longword longword1 = *--longword_ptr ^ repeated_c;
+
+      if ((((longword1 - repeated_one) & ~longword1)
+           & (repeated_one << 7)) != 0)
+        {
+          longword_ptr++;
+          break;
+        }
+      n -= sizeof (longword);
+    }
+
+  char_ptr = (const unsigned char *) longword_ptr;
+
+  /* At this point, we know that either n < sizeof (longword), or one of the
+     sizeof (longword) bytes starting at char_ptr is == c.  On little-endian
+     machines, we could determine the first such byte without any further
+     memory accesses, just by looking at the tmp result from the last loop
+     iteration.  But this does not work on big-endian machines.  Choose code
+     that works in both cases.  */
+
+  while (n-- > 0)
+    {
+      if (*--char_ptr == c)
+        return (void *) char_ptr;
+    }
+
+  return NULL;
+}
+#ifdef weak_alias
+weak_alias (__memrchr, memrchr)
+#endif
diff --git a/lib/string.in.h b/lib/string.in.h
new file mode 100644
index 0000000000..d7a6c9c923
--- /dev/null
+++ b/lib/string.in.h
@@ -0,0 +1,1029 @@
+/* A GNU-like <string.h>.
+
+   Copyright (C) 1995-1996, 2001-2013 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
+   the Free Software Foundation; either version 3, or (at your option)
+   any later version.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, see <http://www.gnu.org/licenses/>.  */
+
+#ifndef _@GUARD_PREFIX@_STRING_H
+
+#if __GNUC__ >= 3
+@PRAGMA_SYSTEM_HEADER@
+#endif
+@PRAGMA_COLUMNS@
+
+/* The include_next requires a split double-inclusion guard.  */
+#@INCLUDE_NEXT@ @NEXT_STRING_H@
+
+#ifndef _@GUARD_PREFIX@_STRING_H
+#define _@GUARD_PREFIX@_STRING_H
+
+/* NetBSD 5.0 mis-defines NULL.  */
+#include <stddef.h>
+
+/* MirBSD defines mbslen as a macro.  */
+#if @GNULIB_MBSLEN@ && defined __MirBSD__
+# include <wchar.h>
+#endif
+
+/* The __attribute__ feature is available in gcc versions 2.5 and later.
+   The attribute __pure__ was added in gcc 2.96.  */
+#if __GNUC__ > 2 || (__GNUC__ == 2 && __GNUC_MINOR__ >= 96)
+# define _GL_ATTRIBUTE_PURE __attribute__ ((__pure__))
+#else
+# define _GL_ATTRIBUTE_PURE /* empty */
+#endif
+
+/* NetBSD 5.0 declares strsignal in <unistd.h>, not in <string.h>.  */
+/* But in any case avoid namespace pollution on glibc systems.  */
+#if (@GNULIB_STRSIGNAL@ || defined GNULIB_POSIXCHECK) && defined __NetBSD__ \
+    && ! defined __GLIBC__
+# include <unistd.h>
+#endif
+
+/* The definitions of _GL_FUNCDECL_RPL etc. are copied here.  */
+
+/* The definition of _GL_ARG_NONNULL is copied here.  */
+
+/* The definition of _GL_WARN_ON_USE is copied here.  */
+
+
+/* Find the index of the least-significant set bit.  */
+#if @GNULIB_FFSL@
+# if !@HAVE_FFSL@
+_GL_FUNCDECL_SYS (ffsl, int, (long int i));
+# endif
+_GL_CXXALIAS_SYS (ffsl, int, (long int i));
+_GL_CXXALIASWARN (ffsl);
+#elif defined GNULIB_POSIXCHECK
+# undef ffsl
+# if HAVE_RAW_DECL_FFSL
+_GL_WARN_ON_USE (ffsl, "ffsl is not portable - use the ffsl module");
+# endif
+#endif
+
+
+/* Find the index of the least-significant set bit.  */
+#if @GNULIB_FFSLL@
+# if !@HAVE_FFSLL@
+_GL_FUNCDECL_SYS (ffsll, int, (long long int i));
+# endif
+_GL_CXXALIAS_SYS (ffsll, int, (long long int i));
+_GL_CXXALIASWARN (ffsll);
+#elif defined GNULIB_POSIXCHECK
+# undef ffsll
+# if HAVE_RAW_DECL_FFSLL
+_GL_WARN_ON_USE (ffsll, "ffsll is not portable - use the ffsll module");
+# endif
+#endif
+
+
+/* Return the first instance of C within N bytes of S, or NULL.  */
+#if @GNULIB_MEMCHR@
+# if @REPLACE_MEMCHR@
+#  if !(defined __cplusplus && defined GNULIB_NAMESPACE)
+#   define memchr rpl_memchr
+#  endif
+_GL_FUNCDECL_RPL (memchr, void *, (void const *__s, int __c, size_t __n)
+                                  _GL_ATTRIBUTE_PURE
+                                  _GL_ARG_NONNULL ((1)));
+_GL_CXXALIAS_RPL (memchr, void *, (void const *__s, int __c, size_t __n));
+# else
+#  if ! @HAVE_MEMCHR@
+_GL_FUNCDECL_SYS (memchr, void *, (void const *__s, int __c, size_t __n)
+                                  _GL_ATTRIBUTE_PURE
+                                  _GL_ARG_NONNULL ((1)));
+#  endif
+  /* On some systems, this function is defined as an overloaded function:
+       extern "C" { const void * std::memchr (const void *, int, size_t); }
+       extern "C++" { void * std::memchr (void *, int, size_t); }  */
+_GL_CXXALIAS_SYS_CAST2 (memchr,
+                        void *, (void const *__s, int __c, size_t __n),
+                        void const *, (void const *__s, int __c, size_t __n));
+# endif
+# if ((__GLIBC__ == 2 && __GLIBC_MINOR__ >= 10) && !defined __UCLIBC__) \
+     && (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 4))
+_GL_CXXALIASWARN1 (memchr, void *, (void *__s, int __c, size_t __n));
+_GL_CXXALIASWARN1 (memchr, void const *,
+                   (void const *__s, int __c, size_t __n));
+# else
+_GL_CXXALIASWARN (memchr);
+# endif
+#elif defined GNULIB_POSIXCHECK
+# undef memchr
+/* Assume memchr is always declared.  */
+_GL_WARN_ON_USE (memchr, "memchr has platform-specific bugs - "
+                 "use gnulib module memchr for portability" );
+#endif
+
+/* Return the first occurrence of NEEDLE in HAYSTACK.  */
+#if @GNULIB_MEMMEM@
+# if @REPLACE_MEMMEM@
+#  if !(defined __cplusplus && defined GNULIB_NAMESPACE)
+#   define memmem rpl_memmem
+#  endif
+_GL_FUNCDECL_RPL (memmem, void *,
+                  (void const *__haystack, size_t __haystack_len,
+                   void const *__needle, size_t __needle_len)
+                  _GL_ATTRIBUTE_PURE
+                  _GL_ARG_NONNULL ((1, 3)));
+_GL_CXXALIAS_RPL (memmem, void *,
+                  (void const *__haystack, size_t __haystack_len,
+                   void const *__needle, size_t __needle_len));
+# else
+#  if ! @HAVE_DECL_MEMMEM@
+_GL_FUNCDECL_SYS (memmem, void *,
+                  (void const *__haystack, size_t __haystack_len,
+                   void const *__needle, size_t __needle_len)
+                  _GL_ATTRIBUTE_PURE
+                  _GL_ARG_NONNULL ((1, 3)));
+#  endif
+_GL_CXXALIAS_SYS (memmem, void *,
+                  (void const *__haystack, size_t __haystack_len,
+                   void const *__needle, size_t __needle_len));
+# endif
+_GL_CXXALIASWARN (memmem);
+#elif defined GNULIB_POSIXCHECK
+# undef memmem
+# if HAVE_RAW_DECL_MEMMEM
+_GL_WARN_ON_USE (memmem, "memmem is unportable and often quadratic - "
+                 "use gnulib module memmem-simple for portability, "
+                 "and module memmem for speed" );
+# endif
+#endif
+
+/* Copy N bytes of SRC to DEST, return pointer to bytes after the
+   last written byte.  */
+#if @GNULIB_MEMPCPY@
+# if ! @HAVE_MEMPCPY@
+_GL_FUNCDECL_SYS (mempcpy, void *,
+                  (void *restrict __dest, void const *restrict __src,
+                   size_t __n)
+                  _GL_ARG_NONNULL ((1, 2)));
+# endif
+_GL_CXXALIAS_SYS (mempcpy, void *,
+                  (void *restrict __dest, void const *restrict __src,
+                   size_t __n));
+_GL_CXXALIASWARN (mempcpy);
+#elif defined GNULIB_POSIXCHECK
+# undef mempcpy
+# if HAVE_RAW_DECL_MEMPCPY
+_GL_WARN_ON_USE (mempcpy, "mempcpy is unportable - "
+                 "use gnulib module mempcpy for portability");
+# endif
+#endif
+
+/* Search backwards through a block for a byte (specified as an int).  */
+#if @GNULIB_MEMRCHR@
+# if ! @HAVE_DECL_MEMRCHR@
+_GL_FUNCDECL_SYS (memrchr, void *, (void const *, int, size_t)
+                                   _GL_ATTRIBUTE_PURE
+                                   _GL_ARG_NONNULL ((1)));
+# endif
+  /* On some systems, this function is defined as an overloaded function:
+       extern "C++" { const void * std::memrchr (const void *, int, size_t); }
+       extern "C++" { void * std::memrchr (void *, int, size_t); }  */
+_GL_CXXALIAS_SYS_CAST2 (memrchr,
+                        void *, (void const *, int, size_t),
+                        void const *, (void const *, int, size_t));
+# if ((__GLIBC__ == 2 && __GLIBC_MINOR__ >= 10) && !defined __UCLIBC__) \
+     && (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 4))
+_GL_CXXALIASWARN1 (memrchr, void *, (void *, int, size_t));
+_GL_CXXALIASWARN1 (memrchr, void const *, (void const *, int, size_t));
+# else
+_GL_CXXALIASWARN (memrchr);
+# endif
+#elif defined GNULIB_POSIXCHECK
+# undef memrchr
+# if HAVE_RAW_DECL_MEMRCHR
+_GL_WARN_ON_USE (memrchr, "memrchr is unportable - "
+                 "use gnulib module memrchr for portability");
+# endif
+#endif
+
+/* Find the first occurrence of C in S.  More efficient than
+   memchr(S,C,N), at the expense of undefined behavior if C does not
+   occur within N bytes.  */
+#if @GNULIB_RAWMEMCHR@
+# if ! @HAVE_RAWMEMCHR@
+_GL_FUNCDECL_SYS (rawmemchr, void *, (void const *__s, int __c_in)
+                                     _GL_ATTRIBUTE_PURE
+                                     _GL_ARG_NONNULL ((1)));
+# endif
+  /* On some systems, this function is defined as an overloaded function:
+       extern "C++" { const void * std::rawmemchr (const void *, int); }
+       extern "C++" { void * std::rawmemchr (void *, int); }  */
+_GL_CXXALIAS_SYS_CAST2 (rawmemchr,
+                        void *, (void const *__s, int __c_in),
+                        void const *, (void const *__s, int __c_in));
+# if ((__GLIBC__ == 2 && __GLIBC_MINOR__ >= 10) && !defined __UCLIBC__) \
+     && (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 4))
+_GL_CXXALIASWARN1 (rawmemchr, void *, (void *__s, int __c_in));
+_GL_CXXALIASWARN1 (rawmemchr, void const *, (void const *__s, int __c_in));
+# else
+_GL_CXXALIASWARN (rawmemchr);
+# endif
+#elif defined GNULIB_POSIXCHECK
+# undef rawmemchr
+# if HAVE_RAW_DECL_RAWMEMCHR
+_GL_WARN_ON_USE (rawmemchr, "rawmemchr is unportable - "
+                 "use gnulib module rawmemchr for portability");
+# endif
+#endif
+
+/* Copy SRC to DST, returning the address of the terminating '\0' in DST.  */
+#if @GNULIB_STPCPY@
+# if ! @HAVE_STPCPY@
+_GL_FUNCDECL_SYS (stpcpy, char *,
+                  (char *restrict __dst, char const *restrict __src)
+                  _GL_ARG_NONNULL ((1, 2)));
+# endif
+_GL_CXXALIAS_SYS (stpcpy, char *,
+                  (char *restrict __dst, char const *restrict __src));
+_GL_CXXALIASWARN (stpcpy);
+#elif defined GNULIB_POSIXCHECK
+# undef stpcpy
+# if HAVE_RAW_DECL_STPCPY
+_GL_WARN_ON_USE (stpcpy, "stpcpy is unportable - "
+                 "use gnulib module stpcpy for portability");
+# endif
+#endif
+
+/* Copy no more than N bytes of SRC to DST, returning a pointer past the
+   last non-NUL byte written into DST.  */
+#if @GNULIB_STPNCPY@
+# if @REPLACE_STPNCPY@
+#  if !(defined __cplusplus && defined GNULIB_NAMESPACE)
+#   undef stpncpy
+#   define stpncpy rpl_stpncpy
+#  endif
+_GL_FUNCDECL_RPL (stpncpy, char *,
+                  (char *restrict __dst, char const *restrict __src,
+                   size_t __n)
+                  _GL_ARG_NONNULL ((1, 2)));
+_GL_CXXALIAS_RPL (stpncpy, char *,
+                  (char *restrict __dst, char const *restrict __src,
+                   size_t __n));
+# else
+#  if ! @HAVE_STPNCPY@
+_GL_FUNCDECL_SYS (stpncpy, char *,
+                  (char *restrict __dst, char const *restrict __src,
+                   size_t __n)
+                  _GL_ARG_NONNULL ((1, 2)));
+#  endif
+_GL_CXXALIAS_SYS (stpncpy, char *,
+                  (char *restrict __dst, char const *restrict __src,
+                   size_t __n));
+# endif
+_GL_CXXALIASWARN (stpncpy);
+#elif defined GNULIB_POSIXCHECK
+# undef stpncpy
+# if HAVE_RAW_DECL_STPNCPY
+_GL_WARN_ON_USE (stpncpy, "stpncpy is unportable - "
+                 "use gnulib module stpncpy for portability");
+# endif
+#endif
+
+#if defined GNULIB_POSIXCHECK
+/* strchr() does not work with multibyte strings if the locale encoding is
+   GB18030 and the character to be searched is a digit.  */
+# undef strchr
+/* Assume strchr is always declared.  */
+_GL_WARN_ON_USE (strchr, "strchr cannot work correctly on character strings "
+                 "in some multibyte locales - "
+                 "use mbschr if you care about internationalization");
+#endif
+
+/* Find the first occurrence of C in S or the final NUL byte.  */
+#if @GNULIB_STRCHRNUL@
+# if @REPLACE_STRCHRNUL@
+#  if !(defined __cplusplus && defined GNULIB_NAMESPACE)
+#   define strchrnul rpl_strchrnul
+#  endif
+_GL_FUNCDECL_RPL (strchrnul, char *, (const char *__s, int __c_in)
+                                     _GL_ATTRIBUTE_PURE
+                                     _GL_ARG_NONNULL ((1)));
+_GL_CXXALIAS_RPL (strchrnul, char *,
+                  (const char *str, int ch));
+# else
+#  if ! @HAVE_STRCHRNUL@
+_GL_FUNCDECL_SYS (strchrnul, char *, (char const *__s, int __c_in)
+                                     _GL_ATTRIBUTE_PURE
+                                     _GL_ARG_NONNULL ((1)));
+#  endif
+  /* On some systems, this function is defined as an overloaded function:
+       extern "C++" { const char * std::strchrnul (const char *, int); }
+       extern "C++" { char * std::strchrnul (char *, int); }  */
+_GL_CXXALIAS_SYS_CAST2 (strchrnul,
+                        char *, (char const *__s, int __c_in),
+                        char const *, (char const *__s, int __c_in));
+# endif
+# if ((__GLIBC__ == 2 && __GLIBC_MINOR__ >= 10) && !defined __UCLIBC__) \
+     && (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 4))
+_GL_CXXALIASWARN1 (strchrnul, char *, (char *__s, int __c_in));
+_GL_CXXALIASWARN1 (strchrnul, char const *, (char const *__s, int __c_in));
+# else
+_GL_CXXALIASWARN (strchrnul);
+# endif
+#elif defined GNULIB_POSIXCHECK
+# undef strchrnul
+# if HAVE_RAW_DECL_STRCHRNUL
+_GL_WARN_ON_USE (strchrnul, "strchrnul is unportable - "
+                 "use gnulib module strchrnul for portability");
+# endif
+#endif
+
+/* Duplicate S, returning an identical malloc'd string.  */
+#if @GNULIB_STRDUP@
+# if @REPLACE_STRDUP@
+#  if !(defined __cplusplus && defined GNULIB_NAMESPACE)
+#   undef strdup
+#   define strdup rpl_strdup
+#  endif
+_GL_FUNCDECL_RPL (strdup, char *, (char const *__s) _GL_ARG_NONNULL ((1)));
+_GL_CXXALIAS_RPL (strdup, char *, (char const *__s));
+# else
+#  if defined __cplusplus && defined GNULIB_NAMESPACE && defined strdup
+    /* strdup exists as a function and as a macro.  Get rid of the macro.  */
+#   undef strdup
+#  endif
+#  if !(@HAVE_DECL_STRDUP@ || defined strdup)
+_GL_FUNCDECL_SYS (strdup, char *, (char const *__s) _GL_ARG_NONNULL ((1)));
+#  endif
+_GL_CXXALIAS_SYS (strdup, char *, (char const *__s));
+# endif
+_GL_CXXALIASWARN (strdup);
+#elif defined GNULIB_POSIXCHECK
+# undef strdup
+# if HAVE_RAW_DECL_STRDUP
+_GL_WARN_ON_USE (strdup, "strdup is unportable - "
+                 "use gnulib module strdup for portability");
+# endif
+#endif
+
+/* Append no more than N characters from SRC onto DEST.  */
+#if @GNULIB_STRNCAT@
+# if @REPLACE_STRNCAT@
+#  if !(defined __cplusplus && defined GNULIB_NAMESPACE)
+#   undef strncat
+#   define strncat rpl_strncat
+#  endif
+_GL_FUNCDECL_RPL (strncat, char *, (char *dest, const char *src, size_t n)
+                                   _GL_ARG_NONNULL ((1, 2)));
+_GL_CXXALIAS_RPL (strncat, char *, (char *dest, const char *src, size_t n));
+# else
+_GL_CXXALIAS_SYS (strncat, char *, (char *dest, const char *src, size_t n));
+# endif
+_GL_CXXALIASWARN (strncat);
+#elif defined GNULIB_POSIXCHECK
+# undef strncat
+# if HAVE_RAW_DECL_STRNCAT
+_GL_WARN_ON_USE (strncat, "strncat is unportable - "
+                 "use gnulib module strncat for portability");
+# endif
+#endif
+
+/* Return a newly allocated copy of at most N bytes of STRING.  */
+#if @GNULIB_STRNDUP@
+# if @REPLACE_STRNDUP@
+#  if !(defined __cplusplus && defined GNULIB_NAMESPACE)
+#   undef strndup
+#   define strndup rpl_strndup
+#  endif
+_GL_FUNCDECL_RPL (strndup, char *, (char const *__string, size_t __n)
+                                   _GL_ARG_NONNULL ((1)));
+_GL_CXXALIAS_RPL (strndup, char *, (char const *__string, size_t __n));
+# else
+#  if ! @HAVE_DECL_STRNDUP@
+_GL_FUNCDECL_SYS (strndup, char *, (char const *__string, size_t __n)
+                                   _GL_ARG_NONNULL ((1)));
+#  endif
+_GL_CXXALIAS_SYS (strndup, char *, (char const *__string, size_t __n));
+# endif
+_GL_CXXALIASWARN (strndup);
+#elif defined GNULIB_POSIXCHECK
+# undef strndup
+# if HAVE_RAW_DECL_STRNDUP
+_GL_WARN_ON_USE (strndup, "strndup is unportable - "
+                 "use gnulib module strndup for portability");
+# endif
+#endif
+
+/* Find the length (number of bytes) of STRING, but scan at most
+   MAXLEN bytes.  If no '\0' terminator is found in that many bytes,
+   return MAXLEN.  */
+#if @GNULIB_STRNLEN@
+# if @REPLACE_STRNLEN@
+#  if !(defined __cplusplus && defined GNULIB_NAMESPACE)
+#   undef strnlen
+#   define strnlen rpl_strnlen
+#  endif
+_GL_FUNCDECL_RPL (strnlen, size_t, (char const *__string, size_t __maxlen)
+                                   _GL_ATTRIBUTE_PURE
+                                   _GL_ARG_NONNULL ((1)));
+_GL_CXXALIAS_RPL (strnlen, size_t, (char const *__string, size_t __maxlen));
+# else
+#  if ! @HAVE_DECL_STRNLEN@
+_GL_FUNCDECL_SYS (strnlen, size_t, (char const *__string, size_t __maxlen)
+                                   _GL_ATTRIBUTE_PURE
+                                   _GL_ARG_NONNULL ((1)));
+#  endif
+_GL_CXXALIAS_SYS (strnlen, size_t, (char const *__string, size_t __maxlen));
+# endif
+_GL_CXXALIASWARN (strnlen);
+#elif defined GNULIB_POSIXCHECK
+# undef strnlen
+# if HAVE_RAW_DECL_STRNLEN
+_GL_WARN_ON_USE (strnlen, "strnlen is unportable - "
+                 "use gnulib module strnlen for portability");
+# endif
+#endif
+
+#if defined GNULIB_POSIXCHECK
+/* strcspn() assumes the second argument is a list of single-byte characters.
+   Even in this simple case, it does not work with multibyte strings if the
+   locale encoding is GB18030 and one of the characters to be searched is a
+   digit.  */
+# undef strcspn
+/* Assume strcspn is always declared.  */
+_GL_WARN_ON_USE (strcspn, "strcspn cannot work correctly on character strings "
+                 "in multibyte locales - "
+                 "use mbscspn if you care about internationalization");
+#endif
+
+/* Find the first occurrence in S of any character in ACCEPT.  */
+#if @GNULIB_STRPBRK@
+# if ! @HAVE_STRPBRK@
+_GL_FUNCDECL_SYS (strpbrk, char *, (char const *__s, char const *__accept)
+                                   _GL_ATTRIBUTE_PURE
+                                   _GL_ARG_NONNULL ((1, 2)));
+# endif
+  /* On some systems, this function is defined as an overloaded function:
+       extern "C" { const char * strpbrk (const char *, const char *); }
+       extern "C++" { char * strpbrk (char *, const char *); }  */
+_GL_CXXALIAS_SYS_CAST2 (strpbrk,
+                        char *, (char const *__s, char const *__accept),
+                        const char *, (char const *__s, char const *__accept));
+# if ((__GLIBC__ == 2 && __GLIBC_MINOR__ >= 10) && !defined __UCLIBC__) \
+     && (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 4))
+_GL_CXXALIASWARN1 (strpbrk, char *, (char *__s, char const *__accept));
+_GL_CXXALIASWARN1 (strpbrk, char const *,
+                   (char const *__s, char const *__accept));
+# else
+_GL_CXXALIASWARN (strpbrk);
+# endif
+# if defined GNULIB_POSIXCHECK
+/* strpbrk() assumes the second argument is a list of single-byte characters.
+   Even in this simple case, it does not work with multibyte strings if the
+   locale encoding is GB18030 and one of the characters to be searched is a
+   digit.  */
+#  undef strpbrk
+_GL_WARN_ON_USE (strpbrk, "strpbrk cannot work correctly on character strings "
+                 "in multibyte locales - "
+                 "use mbspbrk if you care about internationalization");
+# endif
+#elif defined GNULIB_POSIXCHECK
+# undef strpbrk
+# if HAVE_RAW_DECL_STRPBRK
+_GL_WARN_ON_USE (strpbrk, "strpbrk is unportable - "
+                 "use gnulib module strpbrk for portability");
+# endif
+#endif
+
+#if defined GNULIB_POSIXCHECK
+/* strspn() assumes the second argument is a list of single-byte characters.
+   Even in this simple case, it cannot work with multibyte strings.  */
+# undef strspn
+/* Assume strspn is always declared.  */
+_GL_WARN_ON_USE (strspn, "strspn cannot work correctly on character strings "
+                 "in multibyte locales - "
+                 "use mbsspn if you care about internationalization");
+#endif
+
+#if defined GNULIB_POSIXCHECK
+/* strrchr() does not work with multibyte strings if the locale encoding is
+   GB18030 and the character to be searched is a digit.  */
+# undef strrchr
+/* Assume strrchr is always declared.  */
+_GL_WARN_ON_USE (strrchr, "strrchr cannot work correctly on character strings "
+                 "in some multibyte locales - "
+                 "use mbsrchr if you care about internationalization");
+#endif
+
+/* Search the next delimiter (char listed in DELIM) starting at *STRINGP.
+   If one is found, overwrite it with a NUL, and advance *STRINGP
+   to point to the next char after it.  Otherwise, set *STRINGP to NULL.
+   If *STRINGP was already NULL, nothing happens.
+   Return the old value of *STRINGP.
+
+   This is a variant of strtok() that is multithread-safe and supports
+   empty fields.
+
+   Caveat: It modifies the original string.
+   Caveat: These functions cannot be used on constant strings.
+   Caveat: The identity of the delimiting character is lost.
+   Caveat: It doesn't work with multibyte strings unless all of the delimiter
+           characters are ASCII characters < 0x30.
+
+   See also strtok_r().  */
+#if @GNULIB_STRSEP@
+# if ! @HAVE_STRSEP@
+_GL_FUNCDECL_SYS (strsep, char *,
+                  (char **restrict __stringp, char const *restrict __delim)
+                  _GL_ARG_NONNULL ((1, 2)));
+# endif
+_GL_CXXALIAS_SYS (strsep, char *,
+                  (char **restrict __stringp, char const *restrict __delim));
+_GL_CXXALIASWARN (strsep);
+# if defined GNULIB_POSIXCHECK
+#  undef strsep
+_GL_WARN_ON_USE (strsep, "strsep cannot work correctly on character strings "
+                 "in multibyte locales - "
+                 "use mbssep if you care about internationalization");
+# endif
+#elif defined GNULIB_POSIXCHECK
+# undef strsep
+# if HAVE_RAW_DECL_STRSEP
+_GL_WARN_ON_USE (strsep, "strsep is unportable - "
+                 "use gnulib module strsep for portability");
+# endif
+#endif
+
+#if @GNULIB_STRSTR@
+# if @REPLACE_STRSTR@
+#  if !(defined __cplusplus && defined GNULIB_NAMESPACE)
+#   define strstr rpl_strstr
+#  endif
+_GL_FUNCDECL_RPL (strstr, char *, (const char *haystack, const char *needle)
+                                  _GL_ATTRIBUTE_PURE
+                                  _GL_ARG_NONNULL ((1, 2)));
+_GL_CXXALIAS_RPL (strstr, char *, (const char *haystack, const char *needle));
+# else
+  /* On some systems, this function is defined as an overloaded function:
+       extern "C++" { const char * strstr (const char *, const char *); }
+       extern "C++" { char * strstr (char *, const char *); }  */
+_GL_CXXALIAS_SYS_CAST2 (strstr,
+                        char *, (const char *haystack, const char *needle),
+                        const char *, (const char *haystack, const char *needle));
+# endif
+# if ((__GLIBC__ == 2 && __GLIBC_MINOR__ >= 10) && !defined __UCLIBC__) \
+     && (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 4))
+_GL_CXXALIASWARN1 (strstr, char *, (char *haystack, const char *needle));
+_GL_CXXALIASWARN1 (strstr, const char *,
+                   (const char *haystack, const char *needle));
+# else
+_GL_CXXALIASWARN (strstr);
+# endif
+#elif defined GNULIB_POSIXCHECK
+/* strstr() does not work with multibyte strings if the locale encoding is
+   different from UTF-8:
+   POSIX says that it operates on "strings", and "string" in POSIX is defined
+   as a sequence of bytes, not of characters.  */
+# undef strstr
+/* Assume strstr is always declared.  */
+_GL_WARN_ON_USE (strstr, "strstr is quadratic on many systems, and cannot "
+                 "work correctly on character strings in most "
+                 "multibyte locales - "
+                 "use mbsstr if you care about internationalization, "
+                 "or use strstr if you care about speed");
+#endif
+
+/* Find the first occurrence of NEEDLE in HAYSTACK, using case-insensitive
+   comparison.  */
+#if @GNULIB_STRCASESTR@
+# if @REPLACE_STRCASESTR@
+#  if !(defined __cplusplus && defined GNULIB_NAMESPACE)
+#   define strcasestr rpl_strcasestr
+#  endif
+_GL_FUNCDECL_RPL (strcasestr, char *,
+                  (const char *haystack, const char *needle)
+                  _GL_ATTRIBUTE_PURE
+                  _GL_ARG_NONNULL ((1, 2)));
+_GL_CXXALIAS_RPL (strcasestr, char *,
+                  (const char *haystack, const char *needle));
+# else
+#  if ! @HAVE_STRCASESTR@
+_GL_FUNCDECL_SYS (strcasestr, char *,
+                  (const char *haystack, const char *needle)
+                  _GL_ATTRIBUTE_PURE
+                  _GL_ARG_NONNULL ((1, 2)));
+#  endif
+  /* On some systems, this function is defined as an overloaded function:
+       extern "C++" { const char * strcasestr (const char *, const char *); }
+       extern "C++" { char * strcasestr (char *, const char *); }  */
+_GL_CXXALIAS_SYS_CAST2 (strcasestr,
+                        char *, (const char *haystack, const char *needle),
+                        const char *, (const char *haystack, const char *needle));
+# endif
+# if ((__GLIBC__ == 2 && __GLIBC_MINOR__ >= 10) && !defined __UCLIBC__) \
+     && (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 4))
+_GL_CXXALIASWARN1 (strcasestr, char *, (char *haystack, const char *needle));
+_GL_CXXALIASWARN1 (strcasestr, const char *,
+                   (const char *haystack, const char *needle));
+# else
+_GL_CXXALIASWARN (strcasestr);
+# endif
+#elif defined GNULIB_POSIXCHECK
+/* strcasestr() does not work with multibyte strings:
+   It is a glibc extension, and glibc implements it only for unibyte
+   locales.  */
+# undef strcasestr
+# if HAVE_RAW_DECL_STRCASESTR
+_GL_WARN_ON_USE (strcasestr, "strcasestr does work correctly on character "
+                 "strings in multibyte locales - "
+                 "use mbscasestr if you care about "
+                 "internationalization, or use c-strcasestr if you want "
+                 "a locale independent function");
+# endif
+#endif
+
+/* Parse S into tokens separated by characters in DELIM.
+   If S is NULL, the saved pointer in SAVE_PTR is used as
+   the next starting point.  For example:
+        char s[] = "-abc-=-def";
+        char *sp;
+        x = strtok_r(s, "-", &sp);      // x = "abc", sp = "=-def"
+        x = strtok_r(NULL, "-=", &sp);  // x = "def", sp = NULL
+        x = strtok_r(NULL, "=", &sp);   // x = NULL
+                // s = "abc\0-def\0"
+
+   This is a variant of strtok() that is multithread-safe.
+
+   For the POSIX documentation for this function, see:
+   http://www.opengroup.org/susv3xsh/strtok.html
+
+   Caveat: It modifies the original string.
+   Caveat: These functions cannot be used on constant strings.
+   Caveat: The identity of the delimiting character is lost.
+   Caveat: It doesn't work with multibyte strings unless all of the delimiter
+           characters are ASCII characters < 0x30.
+
+   See also strsep().  */
+#if @GNULIB_STRTOK_R@
+# if @REPLACE_STRTOK_R@
+#  if !(defined __cplusplus && defined GNULIB_NAMESPACE)
+#   undef strtok_r
+#   define strtok_r rpl_strtok_r
+#  endif
+_GL_FUNCDECL_RPL (strtok_r, char *,
+                  (char *restrict s, char const *restrict delim,
+                   char **restrict save_ptr)
+                  _GL_ARG_NONNULL ((2, 3)));
+_GL_CXXALIAS_RPL (strtok_r, char *,
+                  (char *restrict s, char const *restrict delim,
+                   char **restrict save_ptr));
+# else
+#  if @UNDEFINE_STRTOK_R@ || defined GNULIB_POSIXCHECK
+#   undef strtok_r
+#  endif
+#  if ! @HAVE_DECL_STRTOK_R@
+_GL_FUNCDECL_SYS (strtok_r, char *,
+                  (char *restrict s, char const *restrict delim,
+                   char **restrict save_ptr)
+                  _GL_ARG_NONNULL ((2, 3)));
+#  endif
+_GL_CXXALIAS_SYS (strtok_r, char *,
+                  (char *restrict s, char const *restrict delim,
+                   char **restrict save_ptr));
+# endif
+_GL_CXXALIASWARN (strtok_r);
+# if defined GNULIB_POSIXCHECK
+_GL_WARN_ON_USE (strtok_r, "strtok_r cannot work correctly on character "
+                 "strings in multibyte locales - "
+                 "use mbstok_r if you care about internationalization");
+# endif
+#elif defined GNULIB_POSIXCHECK
+# undef strtok_r
+# if HAVE_RAW_DECL_STRTOK_R
+_GL_WARN_ON_USE (strtok_r, "strtok_r is unportable - "
+                 "use gnulib module strtok_r for portability");
+# endif
+#endif
+
+
+/* The following functions are not specified by POSIX.  They are gnulib
+   extensions.  */
+
+#if @GNULIB_MBSLEN@
+/* Return the number of multibyte characters in the character string STRING.
+   This considers multibyte characters, unlike strlen, which counts bytes.  */
+# ifdef __MirBSD__  /* MirBSD defines mbslen as a macro.  Override it.  */
+#  undef mbslen
+# endif
+# if @HAVE_MBSLEN@  /* AIX, OSF/1, MirBSD define mbslen already in libc.  */
+#  if !(defined __cplusplus && defined GNULIB_NAMESPACE)
+#   define mbslen rpl_mbslen
+#  endif
+_GL_FUNCDECL_RPL (mbslen, size_t, (const char *string)
+                                  _GL_ATTRIBUTE_PURE
+                                  _GL_ARG_NONNULL ((1)));
+_GL_CXXALIAS_RPL (mbslen, size_t, (const char *string));
+# else
+_GL_FUNCDECL_SYS (mbslen, size_t, (const char *string)
+                                  _GL_ATTRIBUTE_PURE
+                                  _GL_ARG_NONNULL ((1)));
+_GL_CXXALIAS_SYS (mbslen, size_t, (const char *string));
+# endif
+_GL_CXXALIASWARN (mbslen);
+#endif
+
+#if @GNULIB_MBSNLEN@
+/* Return the number of multibyte characters in the character string starting
+   at STRING and ending at STRING + LEN.  */
+_GL_EXTERN_C size_t mbsnlen (const char *string, size_t len)
+     _GL_ATTRIBUTE_PURE
+     _GL_ARG_NONNULL ((1));
+#endif
+
+#if @GNULIB_MBSCHR@
+/* Locate the first single-byte character C in the character string STRING,
+   and return a pointer to it.  Return NULL if C is not found in STRING.
+   Unlike strchr(), this function works correctly in multibyte locales with
+   encodings such as GB18030.  */
+# if defined __hpux
+#  if !(defined __cplusplus && defined GNULIB_NAMESPACE)
+#   define mbschr rpl_mbschr /* avoid collision with HP-UX function */
+#  endif
+_GL_FUNCDECL_RPL (mbschr, char *, (const char *string, int c)
+                                  _GL_ATTRIBUTE_PURE
+                                  _GL_ARG_NONNULL ((1)));
+_GL_CXXALIAS_RPL (mbschr, char *, (const char *string, int c));
+# else
+_GL_FUNCDECL_SYS (mbschr, char *, (const char *string, int c)
+                                  _GL_ATTRIBUTE_PURE
+                                  _GL_ARG_NONNULL ((1)));
+_GL_CXXALIAS_SYS (mbschr, char *, (const char *string, int c));
+# endif
+_GL_CXXALIASWARN (mbschr);
+#endif
+
+#if @GNULIB_MBSRCHR@
+/* Locate the last single-byte character C in the character string STRING,
+   and return a pointer to it.  Return NULL if C is not found in STRING.
+   Unlike strrchr(), this function works correctly in multibyte locales with
+   encodings such as GB18030.  */
+# if defined __hpux || defined __INTERIX
+#  if !(defined __cplusplus && defined GNULIB_NAMESPACE)
+#   define mbsrchr rpl_mbsrchr /* avoid collision with system function */
+#  endif
+_GL_FUNCDECL_RPL (mbsrchr, char *, (const char *string, int c)
+                                   _GL_ATTRIBUTE_PURE
+                                   _GL_ARG_NONNULL ((1)));
+_GL_CXXALIAS_RPL (mbsrchr, char *, (const char *string, int c));
+# else
+_GL_FUNCDECL_SYS (mbsrchr, char *, (const char *string, int c)
+                                   _GL_ATTRIBUTE_PURE
+                                   _GL_ARG_NONNULL ((1)));
+_GL_CXXALIAS_SYS (mbsrchr, char *, (const char *string, int c));
+# endif
+_GL_CXXALIASWARN (mbsrchr);
+#endif
+
+#if @GNULIB_MBSSTR@
+/* Find the first occurrence of the character string NEEDLE in the character
+   string HAYSTACK.  Return NULL if NEEDLE is not found in HAYSTACK.
+   Unlike strstr(), this function works correctly in multibyte locales with
+   encodings different from UTF-8.  */
+_GL_EXTERN_C char * mbsstr (const char *haystack, const char *needle)
+     _GL_ATTRIBUTE_PURE
+     _GL_ARG_NONNULL ((1, 2));
+#endif
+
+#if @GNULIB_MBSCASECMP@
+/* Compare the character strings S1 and S2, ignoring case, returning less than,
+   equal to or greater than zero if S1 is lexicographically less than, equal to
+   or greater than S2.
+   Note: This function may, in multibyte locales, return 0 for strings of
+   different lengths!
+   Unlike strcasecmp(), this function works correctly in multibyte locales.  */
+_GL_EXTERN_C int mbscasecmp (const char *s1, const char *s2)
+     _GL_ATTRIBUTE_PURE
+     _GL_ARG_NONNULL ((1, 2));
+#endif
+
+#if @GNULIB_MBSNCASECMP@
+/* Compare the initial segment of the character string S1 consisting of at most
+   N characters with the initial segment of the character string S2 consisting
+   of at most N characters, ignoring case, returning less than, equal to or
+   greater than zero if the initial segment of S1 is lexicographically less
+   than, equal to or greater than the initial segment of S2.
+   Note: This function may, in multibyte locales, return 0 for initial segments
+   of different lengths!
+   Unlike strncasecmp(), this function works correctly in multibyte locales.
+   But beware that N is not a byte count but a character count!  */
+_GL_EXTERN_C int mbsncasecmp (const char *s1, const char *s2, size_t n)
+     _GL_ATTRIBUTE_PURE
+     _GL_ARG_NONNULL ((1, 2));
+#endif
+
+#if @GNULIB_MBSPCASECMP@
+/* Compare the initial segment of the character string STRING consisting of
+   at most mbslen (PREFIX) characters with the character string PREFIX,
+   ignoring case.  If the two match, return a pointer to the first byte
+   after this prefix in STRING.  Otherwise, return NULL.
+   Note: This function may, in multibyte locales, return non-NULL if STRING
+   is of smaller length than PREFIX!
+   Unlike strncasecmp(), this function works correctly in multibyte
+   locales.  */
+_GL_EXTERN_C char * mbspcasecmp (const char *string, const char *prefix)
+     _GL_ATTRIBUTE_PURE
+     _GL_ARG_NONNULL ((1, 2));
+#endif
+
+#if @GNULIB_MBSCASESTR@
+/* Find the first occurrence of the character string NEEDLE in the character
+   string HAYSTACK, using case-insensitive comparison.
+   Note: This function may, in multibyte locales, return success even if
+   strlen (haystack) < strlen (needle) !
+   Unlike strcasestr(), this function works correctly in multibyte locales.  */
+_GL_EXTERN_C char * mbscasestr (const char *haystack, const char *needle)
+     _GL_ATTRIBUTE_PURE
+     _GL_ARG_NONNULL ((1, 2));
+#endif
+
+#if @GNULIB_MBSCSPN@
+/* Find the first occurrence in the character string STRING of any character
+   in the character string ACCEPT.  Return the number of bytes from the
+   beginning of the string to this occurrence, or to the end of the string
+   if none exists.
+   Unlike strcspn(), this function works correctly in multibyte locales.  */
+_GL_EXTERN_C size_t mbscspn (const char *string, const char *accept)
+     _GL_ATTRIBUTE_PURE
+     _GL_ARG_NONNULL ((1, 2));
+#endif
+
+#if @GNULIB_MBSPBRK@
+/* Find the first occurrence in the character string STRING of any character
+   in the character string ACCEPT.  Return the pointer to it, or NULL if none
+   exists.
+   Unlike strpbrk(), this function works correctly in multibyte locales.  */
+# if defined __hpux
+#  if !(defined __cplusplus && defined GNULIB_NAMESPACE)
+#   define mbspbrk rpl_mbspbrk /* avoid collision with HP-UX function */
+#  endif
+_GL_FUNCDECL_RPL (mbspbrk, char *, (const char *string, const char *accept)
+                                   _GL_ATTRIBUTE_PURE
+                                   _GL_ARG_NONNULL ((1, 2)));
+_GL_CXXALIAS_RPL (mbspbrk, char *, (const char *string, const char *accept));
+# else
+_GL_FUNCDECL_SYS (mbspbrk, char *, (const char *string, const char *accept)
+                                   _GL_ATTRIBUTE_PURE
+                                   _GL_ARG_NONNULL ((1, 2)));
+_GL_CXXALIAS_SYS (mbspbrk, char *, (const char *string, const char *accept));
+# endif
+_GL_CXXALIASWARN (mbspbrk);
+#endif
+
+#if @GNULIB_MBSSPN@
+/* Find the first occurrence in the character string STRING of any character
+   not in the character string REJECT.  Return the number of bytes from the
+   beginning of the string to this occurrence, or to the end of the string
+   if none exists.
+   Unlike strspn(), this function works correctly in multibyte locales.  */
+_GL_EXTERN_C size_t mbsspn (const char *string, const char *reject)
+     _GL_ATTRIBUTE_PURE
+     _GL_ARG_NONNULL ((1, 2));
+#endif
+
+#if @GNULIB_MBSSEP@
+/* Search the next delimiter (multibyte character listed in the character
+   string DELIM) starting at the character string *STRINGP.
+   If one is found, overwrite it with a NUL, and advance *STRINGP to point
+   to the next multibyte character after it.  Otherwise, set *STRINGP to NULL.
+   If *STRINGP was already NULL, nothing happens.
+   Return the old value of *STRINGP.
+
+   This is a variant of mbstok_r() that supports empty fields.
+
+   Caveat: It modifies the original string.
+   Caveat: These functions cannot be used on constant strings.
+   Caveat: The identity of the delimiting character is lost.
+
+   See also mbstok_r().  */
+_GL_EXTERN_C char * mbssep (char **stringp, const char *delim)
+     _GL_ARG_NONNULL ((1, 2));
+#endif
+
+#if @GNULIB_MBSTOK_R@
+/* Parse the character string STRING into tokens separated by characters in
+   the character string DELIM.
+   If STRING is NULL, the saved pointer in SAVE_PTR is used as
+   the next starting point.  For example:
+        char s[] = "-abc-=-def";
+        char *sp;
+        x = mbstok_r(s, "-", &sp);      // x = "abc", sp = "=-def"
+        x = mbstok_r(NULL, "-=", &sp);  // x = "def", sp = NULL
+        x = mbstok_r(NULL, "=", &sp);   // x = NULL
+                // s = "abc\0-def\0"
+
+   Caveat: It modifies the original string.
+   Caveat: These functions cannot be used on constant strings.
+   Caveat: The identity of the delimiting character is lost.
+
+   See also mbssep().  */
+_GL_EXTERN_C char * mbstok_r (char *string, const char *delim, char **save_ptr)
+     _GL_ARG_NONNULL ((2, 3));
+#endif
+
+/* Map any int, typically from errno, into an error message.  */
+#if @GNULIB_STRERROR@
+# if @REPLACE_STRERROR@
+#  if !(defined __cplusplus && defined GNULIB_NAMESPACE)
+#   undef strerror
+#   define strerror rpl_strerror
+#  endif
+_GL_FUNCDECL_RPL (strerror, char *, (int));
+_GL_CXXALIAS_RPL (strerror, char *, (int));
+# else
+_GL_CXXALIAS_SYS (strerror, char *, (int));
+# endif
+_GL_CXXALIASWARN (strerror);
+#elif defined GNULIB_POSIXCHECK
+# undef strerror
+/* Assume strerror is always declared.  */
+_GL_WARN_ON_USE (strerror, "strerror is unportable - "
+                 "use gnulib module strerror to guarantee non-NULL result");
+#endif
+
+/* Map any int, typically from errno, into an error message.  Multithread-safe.
+   Uses the POSIX declaration, not the glibc declaration.  */
+#if @GNULIB_STRERROR_R@
+# if @REPLACE_STRERROR_R@
+#  if !(defined __cplusplus && defined GNULIB_NAMESPACE)
+#   undef strerror_r
+#   define strerror_r rpl_strerror_r
+#  endif
+_GL_FUNCDECL_RPL (strerror_r, int, (int errnum, char *buf, size_t buflen)
+                                   _GL_ARG_NONNULL ((2)));
+_GL_CXXALIAS_RPL (strerror_r, int, (int errnum, char *buf, size_t buflen));
+# else
+#  if !@HAVE_DECL_STRERROR_R@
+_GL_FUNCDECL_SYS (strerror_r, int, (int errnum, char *buf, size_t buflen)
+                                   _GL_ARG_NONNULL ((2)));
+#  endif
+_GL_CXXALIAS_SYS (strerror_r, int, (int errnum, char *buf, size_t buflen));
+# endif
+# if @HAVE_DECL_STRERROR_R@
+_GL_CXXALIASWARN (strerror_r);
+# endif
+#elif defined GNULIB_POSIXCHECK
+# undef strerror_r
+# if HAVE_RAW_DECL_STRERROR_R
+_GL_WARN_ON_USE (strerror_r, "strerror_r is unportable - "
+                 "use gnulib module strerror_r-posix for portability");
+# endif
+#endif
+
+#if @GNULIB_STRSIGNAL@
+# if @REPLACE_STRSIGNAL@
+#  if !(defined __cplusplus && defined GNULIB_NAMESPACE)
+#   define strsignal rpl_strsignal
+#  endif
+_GL_FUNCDECL_RPL (strsignal, char *, (int __sig));
+_GL_CXXALIAS_RPL (strsignal, char *, (int __sig));
+# else
+#  if ! @HAVE_DECL_STRSIGNAL@
+_GL_FUNCDECL_SYS (strsignal, char *, (int __sig));
+#  endif
+/* Need to cast, because on Cygwin 1.5.x systems, the return type is
+   'const char *'.  */
+_GL_CXXALIAS_SYS_CAST (strsignal, char *, (int __sig));
+# endif
+_GL_CXXALIASWARN (strsignal);
+#elif defined GNULIB_POSIXCHECK
+# undef strsignal
+# if HAVE_RAW_DECL_STRSIGNAL
+_GL_WARN_ON_USE (strsignal, "strsignal is unportable - "
+                 "use gnulib module strsignal for portability");
+# endif
+#endif
+
+#if @GNULIB_STRVERSCMP@
+# if !@HAVE_STRVERSCMP@
+_GL_FUNCDECL_SYS (strverscmp, int, (const char *, const char *)
+                                   _GL_ATTRIBUTE_PURE
+                                   _GL_ARG_NONNULL ((1, 2)));
+# endif
+_GL_CXXALIAS_SYS (strverscmp, int, (const char *, const char *));
+_GL_CXXALIASWARN (strverscmp);
+#elif defined GNULIB_POSIXCHECK
+# undef strverscmp
+# if HAVE_RAW_DECL_STRVERSCMP
+_GL_WARN_ON_USE (strverscmp, "strverscmp is unportable - "
+                 "use gnulib module strverscmp for portability");
+# endif
+#endif
+
+
+#endif /* _@GUARD_PREFIX@_STRING_H */
+#endif /* _@GUARD_PREFIX@_STRING_H */
diff --git a/m4/gnulib-comp.m4 b/m4/gnulib-comp.m4
index 8098a52e50..a7987120c5 100644
--- a/m4/gnulib-comp.m4
+++ b/m4/gnulib-comp.m4
@@ -83,6 +83,7 @@ AC_DEFUN([gl_EARLY],
   AC_REQUIRE([AC_SYS_LARGEFILE])
   # Code from module lstat:
   # Code from module manywarnings:
+  # Code from module memrchr:
   # Code from module mktime:
   # Code from module multiarch:
   # Code from module nocrash:
@@ -117,6 +118,7 @@ AC_DEFUN([gl_EARLY],
   # Code from module stdio:
   # Code from module stdlib:
   # Code from module strftime:
+  # Code from module string:
   # Code from module strtoimax:
   # Code from module strtoll:
   # Code from module strtoull:
@@ -242,6 +244,12 @@ AC_DEFUN([gl_INIT],
     gl_PREREQ_LSTAT
   fi
   gl_SYS_STAT_MODULE_INDICATOR([lstat])
+  gl_FUNC_MEMRCHR
+  if test $ac_cv_func_memrchr = no; then
+    AC_LIBOBJ([memrchr])
+    gl_PREREQ_MEMRCHR
+  fi
+  gl_STRING_MODULE_INDICATOR([memrchr])
   gl_FUNC_MKTIME
   if test $REPLACE_MKTIME = 1; then
     AC_LIBOBJ([mktime])
@@ -294,6 +302,7 @@ AC_DEFUN([gl_INIT],
   gl_STDIO_H
   gl_STDLIB_H
   gl_FUNC_GNU_STRFTIME
+  gl_HEADER_STRING_H
   gl_FUNC_STRTOIMAX
   if test $HAVE_STRTOIMAX = 0 || test $REPLACE_STRTOIMAX = 1; then
     AC_LIBOBJ([strtoimax])
@@ -757,6 +766,7 @@ AC_DEFUN([gl_FILE_LIST], [
   lib/lstat.c
   lib/md5.c
   lib/md5.h
+  lib/memrchr.c
   lib/mktime-internal.h
   lib/mktime.c
   lib/openat-priv.h
@@ -790,6 +800,7 @@ AC_DEFUN([gl_FILE_LIST], [
   lib/stdlib.in.h
   lib/strftime.c
   lib/strftime.h
+  lib/string.in.h
   lib/strtoimax.c
   lib/strtol.c
   lib/strtoll.c
@@ -848,6 +859,7 @@ AC_DEFUN([gl_FILE_LIST], [
   m4/lstat.m4
   m4/manywarnings.m4
   m4/md5.m4
+  m4/memrchr.m4
   m4/mktime.m4
   m4/multiarch.m4
   m4/nocrash.m4
@@ -877,6 +889,7 @@ AC_DEFUN([gl_FILE_LIST], [
   m4/stdio_h.m4
   m4/stdlib_h.m4
   m4/strftime.m4
+  m4/string_h.m4
   m4/strtoimax.m4
   m4/strtoll.m4
   m4/strtoull.m4
diff --git a/m4/memrchr.m4 b/m4/memrchr.m4
new file mode 100644
index 0000000000..5920f5747b
--- /dev/null
+++ b/m4/memrchr.m4
@@ -0,0 +1,23 @@
+# memrchr.m4 serial 10
+dnl Copyright (C) 2002-2003, 2005-2007, 2009-2013 Free Software Foundation,
+dnl 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_MEMRCHR],
+[
+  dnl Persuade glibc <string.h> to declare memrchr().
+  AC_REQUIRE([AC_USE_SYSTEM_EXTENSIONS])
+
+  AC_REQUIRE([gl_HEADER_STRING_H_DEFAULTS])
+  AC_CHECK_DECLS_ONCE([memrchr])
+  if test $ac_cv_have_decl_memrchr = no; then
+    HAVE_DECL_MEMRCHR=0
+  fi
+
+  AC_CHECK_FUNCS([memrchr])
+])
+
+# Prerequisites of lib/memrchr.c.
+AC_DEFUN([gl_PREREQ_MEMRCHR], [:])
diff --git a/m4/string_h.m4 b/m4/string_h.m4
new file mode 100644
index 0000000000..cc5fbbb32f
--- /dev/null
+++ b/m4/string_h.m4
@@ -0,0 +1,120 @@
+# Configure a GNU-like replacement for <string.h>.
+
+# Copyright (C) 2007-2013 Free Software Foundation, Inc.
+# This file is free software; the Free Software Foundation
+# gives unlimited permission to copy and/or distribute it,
+# with or without modifications, as long as this notice is preserved.
+
+# serial 21
+
+# Written by Paul Eggert.
+
+AC_DEFUN([gl_HEADER_STRING_H],
+[
+  dnl Use AC_REQUIRE here, so that the default behavior below is expanded
+  dnl once only, before all statements that occur in other macros.
+  AC_REQUIRE([gl_HEADER_STRING_H_BODY])
+])
+
+AC_DEFUN([gl_HEADER_STRING_H_BODY],
+[
+  AC_REQUIRE([AC_C_RESTRICT])
+  AC_REQUIRE([gl_HEADER_STRING_H_DEFAULTS])
+  gl_NEXT_HEADERS([string.h])
+
+  dnl Check for declarations of anything we want to poison if the
+  dnl corresponding gnulib module is not in use, and which is not
+  dnl guaranteed by C89.
+  gl_WARN_ON_USE_PREPARE([[#include <string.h>
+    ]],
+    [ffsl ffsll memmem mempcpy memrchr rawmemchr stpcpy stpncpy strchrnul
+     strdup strncat strndup strnlen strpbrk strsep strcasestr strtok_r
+     strerror_r strsignal strverscmp])
+])
+
+AC_DEFUN([gl_STRING_MODULE_INDICATOR],
+[
+  dnl Use AC_REQUIRE here, so that the default settings are expanded once only.
+  AC_REQUIRE([gl_HEADER_STRING_H_DEFAULTS])
+  gl_MODULE_INDICATOR_SET_VARIABLE([$1])
+  dnl Define it also as a C macro, for the benefit of the unit tests.
+  gl_MODULE_INDICATOR_FOR_TESTS([$1])
+])
+
+AC_DEFUN([gl_HEADER_STRING_H_DEFAULTS],
+[
+  GNULIB_FFSL=0;        AC_SUBST([GNULIB_FFSL])
+  GNULIB_FFSLL=0;       AC_SUBST([GNULIB_FFSLL])
+  GNULIB_MEMCHR=0;      AC_SUBST([GNULIB_MEMCHR])
+  GNULIB_MEMMEM=0;      AC_SUBST([GNULIB_MEMMEM])
+  GNULIB_MEMPCPY=0;     AC_SUBST([GNULIB_MEMPCPY])
+  GNULIB_MEMRCHR=0;     AC_SUBST([GNULIB_MEMRCHR])
+  GNULIB_RAWMEMCHR=0;   AC_SUBST([GNULIB_RAWMEMCHR])
+  GNULIB_STPCPY=0;      AC_SUBST([GNULIB_STPCPY])
+  GNULIB_STPNCPY=0;     AC_SUBST([GNULIB_STPNCPY])
+  GNULIB_STRCHRNUL=0;   AC_SUBST([GNULIB_STRCHRNUL])
+  GNULIB_STRDUP=0;      AC_SUBST([GNULIB_STRDUP])
+  GNULIB_STRNCAT=0;     AC_SUBST([GNULIB_STRNCAT])
+  GNULIB_STRNDUP=0;     AC_SUBST([GNULIB_STRNDUP])
+  GNULIB_STRNLEN=0;     AC_SUBST([GNULIB_STRNLEN])
+  GNULIB_STRPBRK=0;     AC_SUBST([GNULIB_STRPBRK])
+  GNULIB_STRSEP=0;      AC_SUBST([GNULIB_STRSEP])
+  GNULIB_STRSTR=0;      AC_SUBST([GNULIB_STRSTR])
+  GNULIB_STRCASESTR=0;  AC_SUBST([GNULIB_STRCASESTR])
+  GNULIB_STRTOK_R=0;    AC_SUBST([GNULIB_STRTOK_R])
+  GNULIB_MBSLEN=0;      AC_SUBST([GNULIB_MBSLEN])
+  GNULIB_MBSNLEN=0;     AC_SUBST([GNULIB_MBSNLEN])
+  GNULIB_MBSCHR=0;      AC_SUBST([GNULIB_MBSCHR])
+  GNULIB_MBSRCHR=0;     AC_SUBST([GNULIB_MBSRCHR])
+  GNULIB_MBSSTR=0;      AC_SUBST([GNULIB_MBSSTR])
+  GNULIB_MBSCASECMP=0;  AC_SUBST([GNULIB_MBSCASECMP])
+  GNULIB_MBSNCASECMP=0; AC_SUBST([GNULIB_MBSNCASECMP])
+  GNULIB_MBSPCASECMP=0; AC_SUBST([GNULIB_MBSPCASECMP])
+  GNULIB_MBSCASESTR=0;  AC_SUBST([GNULIB_MBSCASESTR])
+  GNULIB_MBSCSPN=0;     AC_SUBST([GNULIB_MBSCSPN])
+  GNULIB_MBSPBRK=0;     AC_SUBST([GNULIB_MBSPBRK])
+  GNULIB_MBSSPN=0;      AC_SUBST([GNULIB_MBSSPN])
+  GNULIB_MBSSEP=0;      AC_SUBST([GNULIB_MBSSEP])
+  GNULIB_MBSTOK_R=0;    AC_SUBST([GNULIB_MBSTOK_R])
+  GNULIB_STRERROR=0;    AC_SUBST([GNULIB_STRERROR])
+  GNULIB_STRERROR_R=0;  AC_SUBST([GNULIB_STRERROR_R])
+  GNULIB_STRSIGNAL=0;   AC_SUBST([GNULIB_STRSIGNAL])
+  GNULIB_STRVERSCMP=0;  AC_SUBST([GNULIB_STRVERSCMP])
+  HAVE_MBSLEN=0;        AC_SUBST([HAVE_MBSLEN])
+  dnl Assume proper GNU behavior unless another module says otherwise.
+  HAVE_FFSL=1;                  AC_SUBST([HAVE_FFSL])
+  HAVE_FFSLL=1;                 AC_SUBST([HAVE_FFSLL])
+  HAVE_MEMCHR=1;                AC_SUBST([HAVE_MEMCHR])
+  HAVE_DECL_MEMMEM=1;           AC_SUBST([HAVE_DECL_MEMMEM])
+  HAVE_MEMPCPY=1;               AC_SUBST([HAVE_MEMPCPY])
+  HAVE_DECL_MEMRCHR=1;          AC_SUBST([HAVE_DECL_MEMRCHR])
+  HAVE_RAWMEMCHR=1;             AC_SUBST([HAVE_RAWMEMCHR])
+  HAVE_STPCPY=1;                AC_SUBST([HAVE_STPCPY])
+  HAVE_STPNCPY=1;               AC_SUBST([HAVE_STPNCPY])
+  HAVE_STRCHRNUL=1;             AC_SUBST([HAVE_STRCHRNUL])
+  HAVE_DECL_STRDUP=1;           AC_SUBST([HAVE_DECL_STRDUP])
+  HAVE_DECL_STRNDUP=1;          AC_SUBST([HAVE_DECL_STRNDUP])
+  HAVE_DECL_STRNLEN=1;          AC_SUBST([HAVE_DECL_STRNLEN])
+  HAVE_STRPBRK=1;               AC_SUBST([HAVE_STRPBRK])
+  HAVE_STRSEP=1;                AC_SUBST([HAVE_STRSEP])
+  HAVE_STRCASESTR=1;            AC_SUBST([HAVE_STRCASESTR])
+  HAVE_DECL_STRTOK_R=1;         AC_SUBST([HAVE_DECL_STRTOK_R])
+  HAVE_DECL_STRERROR_R=1;       AC_SUBST([HAVE_DECL_STRERROR_R])
+  HAVE_DECL_STRSIGNAL=1;        AC_SUBST([HAVE_DECL_STRSIGNAL])
+  HAVE_STRVERSCMP=1;            AC_SUBST([HAVE_STRVERSCMP])
+  REPLACE_MEMCHR=0;             AC_SUBST([REPLACE_MEMCHR])
+  REPLACE_MEMMEM=0;             AC_SUBST([REPLACE_MEMMEM])
+  REPLACE_STPNCPY=0;            AC_SUBST([REPLACE_STPNCPY])
+  REPLACE_STRDUP=0;             AC_SUBST([REPLACE_STRDUP])
+  REPLACE_STRSTR=0;             AC_SUBST([REPLACE_STRSTR])
+  REPLACE_STRCASESTR=0;         AC_SUBST([REPLACE_STRCASESTR])
+  REPLACE_STRCHRNUL=0;          AC_SUBST([REPLACE_STRCHRNUL])
+  REPLACE_STRERROR=0;           AC_SUBST([REPLACE_STRERROR])
+  REPLACE_STRERROR_R=0;         AC_SUBST([REPLACE_STRERROR_R])
+  REPLACE_STRNCAT=0;            AC_SUBST([REPLACE_STRNCAT])
+  REPLACE_STRNDUP=0;            AC_SUBST([REPLACE_STRNDUP])
+  REPLACE_STRNLEN=0;            AC_SUBST([REPLACE_STRNLEN])
+  REPLACE_STRSIGNAL=0;          AC_SUBST([REPLACE_STRSIGNAL])
+  REPLACE_STRTOK_R=0;           AC_SUBST([REPLACE_STRTOK_R])
+  UNDEFINE_STRTOK_R=0;          AC_SUBST([UNDEFINE_STRTOK_R])
+])
diff --git a/src/ChangeLog b/src/ChangeLog
index b3d3958853..30470f5730 100644
--- a/src/ChangeLog
+++ b/src/ChangeLog
@@ -1,5 +1,14 @@
 2013-02-11  Paul Eggert  <[email protected]>
 
+	Tune by using memchr and memrchr.
+	* doc.c (Fsnarf_documentation):
+	* fileio.c (Fsubstitute_in_file_name):
+	* search.c (find_newline, scan_newline):
+	* xdisp.c (pos_visible_p, display_count_lines):
+	Use memchr and memrchr rather than scanning byte-by-byte.
+	* search.c (find_newline): Rename from scan_buffer.
+	Omit first arg TARGET, as it's always '\n'.  All callers changed.
+
 	Clean up read_key_sequence a tiny bit more.
 	* keyboard.c (read_char_x_menu_prompt) [HAVE_MENUS]:
 	(read_key_sequence): Remove unused locals.
diff --git a/src/doc.c b/src/doc.c
index fa2eca66a1..7234fb38bf 100644
--- a/src/doc.c
+++ b/src/doc.c
@@ -630,11 +630,10 @@ the same file name is found in the `doc-directory'.  */)
 	break;
 
       buf[filled] = 0;
-      p = buf;
       end = buf + (filled < 512 ? filled : filled - 128);
-      while (p != end && *p != '\037') p++;
+      p = memchr (buf, '\037', end - buf);
       /* p points to ^_Ffunctionname\n or ^_Vvarname\n or ^_Sfilename\n.  */
-      if (p != end)
+      if (p)
 	{
 	  end = strchr (p, '\n');
 
diff --git a/src/editfns.c b/src/editfns.c
index 0f88a781b8..c5cd8b0b72 100644
--- a/src/editfns.c
+++ b/src/editfns.c
@@ -735,9 +735,8 @@ Field boundaries are not noticed if `inhibit-field-text-motion' is non-nil.  */)
 	      /* This is the ONLY_IN_LINE case, check that NEW_POS and
 		 FIELD_BOUND are on the same line by seeing whether
 		 there's an intervening newline or not.  */
-	      || (scan_buffer ('\n',
-			       XFASTINT (new_pos), XFASTINT (field_bound),
-			       fwd ? -1 : 1, &shortage, 1),
+	      || (find_newline (XFASTINT (new_pos), XFASTINT (field_bound),
+				fwd ? -1 : 1, &shortage, 1),
 		  shortage != 0)))
 	/* Constrain NEW_POS to FIELD_BOUND.  */
 	new_pos = field_bound;
diff --git a/src/fileio.c b/src/fileio.c
index 98a9b32ea9..89ad339646 100644
--- a/src/fileio.c
+++ b/src/fileio.c
@@ -1710,8 +1710,9 @@ those `/' is discarded.  */)
 	else if (*p == '{')
 	  {
 	    o = ++p;
-	    while (p != endp && *p != '}') p++;
-	    if (*p != '}') goto missingclose;
+	    p = memchr (p, '}', endp - p);
+	    if (! p)
+	      goto missingclose;
 	    s = p;
 	  }
 	else
@@ -1779,8 +1780,9 @@ those `/' is discarded.  */)
 	else if (*p == '{')
 	  {
 	    o = ++p;
-	    while (p != endp && *p != '}') p++;
-	    if (*p != '}') goto missingclose;
+	    p = memchr (p, '}', endp - p);
+	    if (! p)
+	      goto missingclose;
 	    s = p++;
 	  }
 	else
diff --git a/src/lisp.h b/src/lisp.h
index 14db66c679..37d2b45e85 100644
--- a/src/lisp.h
+++ b/src/lisp.h
@@ -3346,8 +3346,8 @@ extern ptrdiff_t fast_c_string_match_ignore_case (Lisp_Object, const char *,
 extern ptrdiff_t fast_string_match_ignore_case (Lisp_Object, Lisp_Object);
 extern ptrdiff_t fast_looking_at (Lisp_Object, ptrdiff_t, ptrdiff_t,
                                   ptrdiff_t, ptrdiff_t, Lisp_Object);
-extern ptrdiff_t scan_buffer (int, ptrdiff_t, ptrdiff_t, ptrdiff_t,
-			      ptrdiff_t *, bool);
+extern ptrdiff_t find_newline (ptrdiff_t, ptrdiff_t, ptrdiff_t,
+			       ptrdiff_t *, bool);
 extern EMACS_INT scan_newline (ptrdiff_t, ptrdiff_t, ptrdiff_t, ptrdiff_t,
 			       EMACS_INT, bool);
 extern ptrdiff_t find_next_newline (ptrdiff_t, int);
diff --git a/src/region-cache.h b/src/region-cache.h
index 697ae1c791..e4c6b59ee9 100644
--- a/src/region-cache.h
+++ b/src/region-cache.h
@@ -40,7 +40,7 @@ along with GNU Emacs.  If not, see <http://www.gnu.org/licenses/>.  */
    existing data structure, and disturb as little of the existing code
    as possible.
 
-   So here's the tack.  We add some caching to the scan_buffer
+   So here's the tack.  We add some caching to the find_newline
    function, so that when it searches for a newline, it notes that the
    region between the start and end of the search contained no
    newlines; then, the next time around, it consults this cache to see
diff --git a/src/search.c b/src/search.c
index c4ccf6c257..c25d244101 100644
--- a/src/search.c
+++ b/src/search.c
@@ -619,7 +619,7 @@ newline_cache_on_off (struct buffer *buf)
 }
 
 
-/* Search for COUNT instances of the character TARGET between START and END.
+/* Search for COUNT newlines between START and END.
 
    If COUNT is positive, search forwards; END must be >= START.
    If COUNT is negative, search backwards for the -COUNTth instance;
@@ -634,14 +634,14 @@ newline_cache_on_off (struct buffer *buf)
    this is not the same as the usual convention for Emacs motion commands.
 
    If we don't find COUNT instances before reaching END, set *SHORTAGE
-   to the number of TARGETs left unfound, and return END.
+   to the number of newlines left unfound, and return END.
 
    If ALLOW_QUIT, set immediate_quit.  That's good to do
    except when inside redisplay.  */
 
 ptrdiff_t
-scan_buffer (int target, ptrdiff_t start, ptrdiff_t end,
-	     ptrdiff_t count, ptrdiff_t *shortage, bool allow_quit)
+find_newline (ptrdiff_t start, ptrdiff_t end,
+	      ptrdiff_t count, ptrdiff_t *shortage, bool allow_quit)
 {
   struct region_cache *newline_cache;
   ptrdiff_t end_byte = -1;
@@ -656,7 +656,7 @@ scan_buffer (int target, ptrdiff_t start, ptrdiff_t end,
   else
     {
       direction = -1;
-      if (!end) 
+      if (!end)
 	end = BEGV, end_byte = BEGV_BYTE;
     }
   if (end_byte == -1)
@@ -684,7 +684,7 @@ scan_buffer (int target, ptrdiff_t start, ptrdiff_t end,
 
         /* If we're looking for a newline, consult the newline cache
            to see where we can avoid some scanning.  */
-        if (target == '\n' && newline_cache)
+        if (newline_cache)
           {
             ptrdiff_t next_change;
             immediate_quit = 0;
@@ -723,32 +723,32 @@ scan_buffer (int target, ptrdiff_t start, ptrdiff_t end,
 
           while (cursor < ceiling_addr)
             {
-              unsigned char *scan_start = cursor;
-
               /* The dumb loop.  */
-              while (*cursor != target && ++cursor < ceiling_addr)
-                ;
+	      unsigned char *nl = memchr (cursor, '\n', ceiling_addr - cursor);
 
               /* If we're looking for newlines, cache the fact that
                  the region from start to cursor is free of them. */
-              if (target == '\n' && newline_cache)
-                know_region_cache (current_buffer, newline_cache,
-                                   BYTE_TO_CHAR (start_byte + scan_start - base),
-                                   BYTE_TO_CHAR (start_byte + cursor - base));
-
-              /* Did we find the target character?  */
-              if (cursor < ceiling_addr)
-                {
-                  if (--count == 0)
-                    {
-                      immediate_quit = 0;
-                      return BYTE_TO_CHAR (start_byte + cursor - base + 1);
-                    }
-                  cursor++;
-                }
+              if (newline_cache)
+		{
+		  unsigned char *low = cursor;
+		  unsigned char *lim = nl ? nl : ceiling_addr;
+		  know_region_cache (current_buffer, newline_cache,
+				     BYTE_TO_CHAR (low - base + start_byte),
+				     BYTE_TO_CHAR (lim - base + start_byte));
+		}
+
+              if (! nl)
+		break;
+
+	      if (--count == 0)
+		{
+		  immediate_quit = 0;
+		  return BYTE_TO_CHAR (nl + 1 - base + start_byte);
+		}
+	      cursor = nl + 1;
             }
 
-          start = BYTE_TO_CHAR (start_byte + cursor - base);
+          start = BYTE_TO_CHAR (ceiling_addr - base + start_byte);
         }
       }
   else
@@ -760,7 +760,7 @@ scan_buffer (int target, ptrdiff_t start, ptrdiff_t end,
 	ptrdiff_t tem;
 
         /* Consult the newline cache, if appropriate.  */
-        if (target == '\n' && newline_cache)
+        if (newline_cache)
           {
             ptrdiff_t next_change;
             immediate_quit = 0;
@@ -794,31 +794,32 @@ scan_buffer (int target, ptrdiff_t start, ptrdiff_t end,
 
           while (cursor >= ceiling_addr)
             {
-              unsigned char *scan_start = cursor;
-
-              while (*cursor != target && --cursor >= ceiling_addr)
-                ;
+	      unsigned char *nl = memrchr (ceiling_addr, '\n',
+					   cursor + 1 - ceiling_addr);
 
               /* If we're looking for newlines, cache the fact that
                  the region from after the cursor to start is free of them.  */
-              if (target == '\n' && newline_cache)
-                know_region_cache (current_buffer, newline_cache,
-                                   BYTE_TO_CHAR (start_byte + cursor - base),
-                                   BYTE_TO_CHAR (start_byte + scan_start - base));
-
-              /* Did we find the target character?  */
-              if (cursor >= ceiling_addr)
-                {
-                  if (++count >= 0)
-                    {
-                      immediate_quit = 0;
-                      return BYTE_TO_CHAR (start_byte + cursor - base);
-                    }
-                  cursor--;
-                }
+              if (newline_cache)
+		{
+		  unsigned char *low = nl ? nl : ceiling_addr - 1;
+		  unsigned char *lim = cursor;
+		  know_region_cache (current_buffer, newline_cache,
+				     BYTE_TO_CHAR (low - base + start_byte),
+				     BYTE_TO_CHAR (lim - base + start_byte));
+		}
+
+              if (! nl)
+		break;
+
+	      if (++count >= 0)
+		{
+		  immediate_quit = 0;
+		  return BYTE_TO_CHAR (nl - base + start_byte);
+		}
+	      cursor = nl - 1;
             }
 
-	  start = BYTE_TO_CHAR (start_byte + cursor - base);
+	  start = BYTE_TO_CHAR (ceiling_addr - 1 - base + start_byte);
         }
       }
 
@@ -828,8 +829,7 @@ scan_buffer (int target, ptrdiff_t start, ptrdiff_t end,
   return start;
 }
 
-/* Search for COUNT instances of a line boundary, which means either a
-   newline or (if selective display enabled) a carriage return.
+/* Search for COUNT instances of a line boundary.
    Start at START.  If COUNT is negative, search backwards.
 
    We report the resulting position by calling TEMP_SET_PT_BOTH.
@@ -860,9 +860,6 @@ scan_newline (ptrdiff_t start, ptrdiff_t start_byte,
 
   bool old_immediate_quit = immediate_quit;
 
-  /* The code that follows is like scan_buffer
-     but checks for either newline or carriage return.  */
-
   if (allow_quit)
     immediate_quit++;
 
@@ -874,29 +871,25 @@ scan_newline (ptrdiff_t start, ptrdiff_t start_byte,
 	  ceiling = min (limit_byte - 1, ceiling);
 	  ceiling_addr = BYTE_POS_ADDR (ceiling) + 1;
 	  base = (cursor = BYTE_POS_ADDR (start_byte));
-	  while (1)
-	    {
-	      while (*cursor != '\n' && ++cursor != ceiling_addr)
-		;
 
-	      if (cursor != ceiling_addr)
+	  do
+	    {
+	      unsigned char *nl = memchr (cursor, '\n', ceiling_addr - cursor);
+	      if (! nl)
+		break;
+	      if (--count == 0)
 		{
-		  if (--count == 0)
-		    {
-		      immediate_quit = old_immediate_quit;
-		      start_byte = start_byte + cursor - base + 1;
-		      start = BYTE_TO_CHAR (start_byte);
-		      TEMP_SET_PT_BOTH (start, start_byte);
-		      return 0;
-		    }
-		  else
-		    if (++cursor == ceiling_addr)
-		      break;
+		  immediate_quit = old_immediate_quit;
+		  start_byte += nl - base + 1;
+		  start = BYTE_TO_CHAR (start_byte);
+		  TEMP_SET_PT_BOTH (start, start_byte);
+		  return 0;
 		}
-	      else
-		break;
+	      cursor = nl + 1;
 	    }
-	  start_byte += cursor - base;
+	  while (cursor < ceiling_addr);
+
+	  start_byte += ceiling_addr - base;
 	}
     }
   else
@@ -905,31 +898,28 @@ scan_newline (ptrdiff_t start, ptrdiff_t start_byte,
 	{
 	  ceiling = BUFFER_FLOOR_OF (start_byte - 1);
 	  ceiling = max (limit_byte, ceiling);
-	  ceiling_addr = BYTE_POS_ADDR (ceiling) - 1;
+	  ceiling_addr = BYTE_POS_ADDR (ceiling);
 	  base = (cursor = BYTE_POS_ADDR (start_byte - 1) + 1);
 	  while (1)
 	    {
-	      while (--cursor != ceiling_addr && *cursor != '\n')
-		;
+	      unsigned char *nl = memrchr (ceiling_addr, '\n',
+					   cursor - ceiling_addr);
+	      if (! nl)
+		break;
 
-	      if (cursor != ceiling_addr)
+	      if (++count == 0)
 		{
-		  if (++count == 0)
-		    {
-		      immediate_quit = old_immediate_quit;
-		      /* Return the position AFTER the match we found.  */
-		      start_byte = start_byte + cursor - base + 1;
-		      start = BYTE_TO_CHAR (start_byte);
-		      TEMP_SET_PT_BOTH (start, start_byte);
-		      return 0;
-		    }
+		  immediate_quit = old_immediate_quit;
+		  /* Return the position AFTER the match we found.  */
+		  start_byte += nl - base + 1;
+		  start = BYTE_TO_CHAR (start_byte);
+		  TEMP_SET_PT_BOTH (start, start_byte);
+		  return 0;
 		}
-	      else
-		break;
+
+	      cursor = nl;
 	    }
-	  /* Here we add 1 to compensate for the last decrement
-	     of CURSOR, which took it past the valid range.  */
-	  start_byte += cursor - base + 1;
+	  start_byte += ceiling_addr - base;
 	}
     }
 
@@ -942,7 +932,7 @@ scan_newline (ptrdiff_t start, ptrdiff_t start_byte,
 ptrdiff_t
 find_next_newline_no_quit (ptrdiff_t from, ptrdiff_t cnt)
 {
-  return scan_buffer ('\n', from, 0, cnt, (ptrdiff_t *) 0, 0);
+  return find_newline (from, 0, cnt, (ptrdiff_t *) 0, 0);
 }
 
 /* Like find_next_newline, but returns position before the newline,
@@ -953,7 +943,7 @@ ptrdiff_t
 find_before_next_newline (ptrdiff_t from, ptrdiff_t to, ptrdiff_t cnt)
 {
   ptrdiff_t shortage;
-  ptrdiff_t pos = scan_buffer ('\n', from, to, cnt, &shortage, 1);
+  ptrdiff_t pos = find_newline (from, to, cnt, &shortage, 1);
 
   if (shortage == 0)
     pos--;
diff --git a/src/xdisp.c b/src/xdisp.c
index 3b82de9432..463f4f9ef0 100644
--- a/src/xdisp.c
+++ b/src/xdisp.c
@@ -1392,21 +1392,9 @@ pos_visible_p (struct window *w, ptrdiff_t charpos, int *x, int *y,
 	      Lisp_Object cpos = make_number (charpos);
 	      Lisp_Object spec = Fget_char_property (cpos, Qdisplay, Qnil);
 	      Lisp_Object string = string_from_display_spec (spec);
-	      int newline_in_string = 0;
-
-	      if (STRINGP (string))
-		{
-		  const char *s = SSDATA (string);
-		  const char *e = s + SBYTES (string);
-		  while (s < e)
-		    {
-		      if (*s++ == '\n')
-			{
-			  newline_in_string = 1;
-			  break;
-			}
-		    }
-		}
+	      bool newline_in_string
+		= (STRINGP (string)
+		   && memchr (SDATA (string), '\n', SBYTES (string)));
 	      /* The tricky code below is needed because there's a
 		 discrepancy between move_it_to and how we set cursor
 		 when the display line ends in a newline from a
@@ -14759,7 +14747,7 @@ compute_window_start_on_continuation_line (struct window *w)
 	SET_TEXT_POS (start_pos, ZV, ZV_BYTE);
 
       /* Find the start of the continued line.  This should be fast
-	 because scan_buffer is fast (newline cache).  */
+	 because find_newline is fast (newline cache).  */
       row = w->desired_matrix->rows + (WINDOW_WANTS_HEADER_LINE_P (w) ? 1 : 0);
       init_iterator (&it, w, CHARPOS (start_pos), BYTEPOS (start_pos),
 		     row, DEFAULT_FACE_ID);
@@ -21626,31 +21614,36 @@ display_count_lines (ptrdiff_t start_byte,
 	  ceiling = min (limit_byte - 1, ceiling);
 	  ceiling_addr = BYTE_POS_ADDR (ceiling) + 1;
 	  base = (cursor = BYTE_POS_ADDR (start_byte));
-	  while (1)
+
+	  do
 	    {
 	      if (selective_display)
-		while (*cursor != '\n' && *cursor != 015 && ++cursor != ceiling_addr)
-		  ;
+		{
+		  while (*cursor != '\n' && *cursor != 015
+			 && ++cursor != ceiling_addr)
+		    continue;
+		  if (cursor == ceiling_addr)
+		    break;
+		}
 	      else
-		while (*cursor != '\n' && ++cursor != ceiling_addr)
-		  ;
+		{
+		  cursor = memchr (cursor, '\n', ceiling_addr - cursor);
+		  if (! cursor)
+		    break;
+		}
+
+	      cursor++;
 
-	      if (cursor != ceiling_addr)
+	      if (--count == 0)
 		{
-		  if (--count == 0)
-		    {
-		      start_byte += cursor - base + 1;
-		      *byte_pos_ptr = start_byte;
-		      return orig_count;
-		    }
-		  else
-		    if (++cursor == ceiling_addr)
-		      break;
+		  start_byte += cursor - base;
+		  *byte_pos_ptr = start_byte;
+		  return orig_count;
 		}
-	      else
-		break;
 	    }
-	  start_byte += cursor - base;
+	  while (cursor < ceiling_addr);
+
+	  start_byte += ceiling_addr - base;
 	}
     }
   else
@@ -21659,35 +21652,35 @@ display_count_lines (ptrdiff_t start_byte,
 	{
 	  ceiling = BUFFER_FLOOR_OF (start_byte - 1);
 	  ceiling = max (limit_byte, ceiling);
-	  ceiling_addr = BYTE_POS_ADDR (ceiling) - 1;
+	  ceiling_addr = BYTE_POS_ADDR (ceiling);
 	  base = (cursor = BYTE_POS_ADDR (start_byte - 1) + 1);
 	  while (1)
 	    {
 	      if (selective_display)
-		while (--cursor != ceiling_addr
-		       && *cursor != '\n' && *cursor != 015)
-		  ;
+		{
+		  while (--cursor >= ceiling_addr
+			 && *cursor != '\n' && *cursor != 015)
+		    continue;
+		  if (cursor < ceiling_addr)
+		    break;
+		}
 	      else
-		while (--cursor != ceiling_addr && *cursor != '\n')
-		  ;
+		{
+		  cursor = memrchr (ceiling_addr, '\n', cursor - ceiling_addr);
+		  if (! cursor)
+		    break;
+		}
 
-	      if (cursor != ceiling_addr)
+	      if (++count == 0)
 		{
-		  if (++count == 0)
-		    {
-		      start_byte += cursor - base + 1;
-		      *byte_pos_ptr = start_byte;
-		      /* When scanning backwards, we should
-			 not count the newline posterior to which we stop.  */
-		      return - orig_count - 1;
-		    }
+		  start_byte += cursor - base + 1;
+		  *byte_pos_ptr = start_byte;
+		  /* When scanning backwards, we should
+		     not count the newline posterior to which we stop.  */
+		  return - orig_count - 1;
 		}
-	      else
-		break;
 	    }
-	  /* Here we add 1 to compensate for the last decrement
-	     of CURSOR, which took it past the valid range.  */
-	  start_byte += cursor - base + 1;
+	  start_byte += ceiling_addr - base;
 	}
     }