[PATCH] rawmemchr: modernize and simplify

[Paul Eggert]

* lib/rawmemchr.c (HAVE_RAWMEMCHR): Assume it’s not defined;
otherwise this file would not be compiled.  Include limits.h,
stdalign.h, stdint.h, verify.h.
(rawmemchr): Prefer uintptr_t to unsigned long and to size_t when
it’s the better type.  Verify that longword lacks padding.  Use
alignof rather than sizeof when checking alignment.  Simplify by
assuming C99 decl-after-statement, and by using multiplication
rather than repeated shifting and OR (modern compilers can
optimize the multiplication if needed).  Avoid unnecessary casts.
Don’t assume CHAR_WIDTH is 8.  Convert back and forth between void *
to suppress bogus GCC warnings about alignment.  Omit a
duplicate assignment to char_ptr.
* modules/rawmemchr (Depends-on): Add stdalign, stdint, verify.
---
 ChangeLog         | 17 ++++++++++
 lib/rawmemchr.c   | 79 +++++++++++++++++------------------------------
 modules/rawmemchr |  3 ++
 3 files changed, 49 insertions(+), 50 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index d42551ce1..bf6c9d66b 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,20 @@
+2021-08-20  Paul Eggert  <eggert@cs.ucla.edu>
+
+       rawmemchr: modernize and simplify
+       * lib/rawmemchr.c (HAVE_RAWMEMCHR): Assume it’s not defined;
+       otherwise this file would not be compiled.  Include limits.h,
+       stdalign.h, stdint.h, verify.h.
+       (rawmemchr): Prefer uintptr_t to unsigned long and to size_t when
+       it’s the better type.  Verify that longword lacks padding.  Use
+       alignof rather than sizeof when checking alignment.  Simplify by
+       assuming C99 decl-after-statement, and by using multiplication
+       rather than repeated shifting and OR (modern compilers can
+       optimize the multiplication if needed).  Avoid unnecessary casts.
+       Don’t assume CHAR_WIDTH is 8.  Convert back and forth between void *
+       to suppress bogus GCC warnings about alignment.  Omit a
+       duplicate assignment to char_ptr.
+       * modules/rawmemchr (Depends-on): Add stdalign, stdint, verify.
+
 2021-08-17  Paul Eggert  <eggert@cs.ucla.edu>
 
        c-stack: fix libsigsegv dependency
diff --git a/lib/rawmemchr.c b/lib/rawmemchr.c
index 896d435af..469bfa3cd 100644
--- a/lib/rawmemchr.c
+++ b/lib/rawmemchr.c
@@ -19,71 +19,54 @@
 /* Specification.  */
 #include <string.h>
 
-/* A function definition is only needed if HAVE_RAWMEMCHR is not defined.  */
-#if !HAVE_RAWMEMCHR
+#include <limits.h>
+#include <stdalign.h>
+#include <stdint.h>
+
+#include "verify.h"
 
 /* Find the first occurrence of C in S.  */
 void *
 rawmemchr (const void *s, int c_in)
 {
-  /* 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;
+  /* Change this typedef to experiment with performance.  */
+  typedef uintptr_t longword;
+  /* If you change the "uintptr_t", you should change UINTPTR_WIDTH to match.
+     This verifies that the type does not have padding bits.  */
+  verify (UINTPTR_WIDTH == UCHAR_WIDTH * sizeof (longword));
 
   const unsigned char *char_ptr;
-  const longword *longword_ptr;
-  longword repeated_one;
-  longword repeated_c;
-  unsigned char c;
-
-  c = (unsigned char) c_in;
+  unsigned char c = c_in;
 
   /* Handle the first 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;
-       (size_t) char_ptr % sizeof (longword) != 0;
+       (uintptr_t) char_ptr % alignof (longword) != 0;
        ++char_ptr)
     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.  */
+  longword const *longword_ptr = s = char_ptr;
 
   /* 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;
-            }
-        }
-    }
+  longword repeated_one = (longword) -1 / UCHAR_MAX;
+  longword repeated_c = repeated_one * c;
+  longword repeated_hibit = repeated_one * (UCHAR_MAX / 2 + 1);
 
   /* 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 NUL or
+     test a longword at a time.  The tricky part is testing if any of
+     the 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.
+     to testing whether any of the bytes in longword1 is zero.
+
+     (The following comments assume 8-bit bytes, as POSIX requires;
+     the code's use of UCHAR_MAX should work even if bytes have more
+     than 8 bits.)
 
      We compute tmp =
-       ((longword1 - repeated_one) & ~longword1) & (repeated_one << 7).
+       ((longword1 - repeated_one) & ~longword1) & (repeated_one * 0x80).
      That is, we perform the following operations:
        1. Subtract repeated_one.
        2. & ~longword1.
@@ -117,25 +100,21 @@ rawmemchr (const void *s, int c_in)
     {
       longword longword1 = *longword_ptr ^ repeated_c;
 
-      if ((((longword1 - repeated_one) & ~longword1)
-           & (repeated_one << 7)) != 0)
+      if ((((longword1 - repeated_one) & ~longword1) & repeated_hibit) != 0)
         break;
       longword_ptr++;
     }
 
-  char_ptr = (const unsigned char *) longword_ptr;
+  char_ptr = s = longword_ptr;
 
   /* At this point, we know that one of the sizeof (longword) bytes
-     starting at char_ptr is == c.  On little-endian machines, we
+     starting at char_ptr is == c.  If we knew endianness, 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.  */
+     iteration.  However, the following simple and portable code does
+     not attempt this potential optimization.  */
 
-  char_ptr = (unsigned char *) longword_ptr;
   while (*char_ptr != c)
     char_ptr++;
   return (void *) char_ptr;
 }
-
-#endif
diff --git a/modules/rawmemchr b/modules/rawmemchr
index 32320568c..d30065e74 100644
--- a/modules/rawmemchr
+++ b/modules/rawmemchr
@@ -8,7 +8,10 @@ m4/rawmemchr.m4
 
 Depends-on:
 extensions
+stdalign
+stdint
 string
+verify
 
 configure.ac:
 gl_FUNC_RAWMEMCHR
-- 
2.30.2