[PATCH v2 5/5] unistr/u8-chr, unistr/u8-strchr: use Boyer-Moore like algorithm.

[bonzini]

From: Paolo Bonzini <address@hidden>

* lib/unistr/u8-chr.c, lib/unistr/u8-strchr.c: Add Boyer-Moore like operation.
* modules/unistr/u8-chr: Depend on memchr.
---
 lib/unistr/u8-chr.c    |  181 +++++++++++++++++++++++++++++++++++-------------
 lib/unistr/u8-strchr.c |  136 ++++++++++++++++++++++++++++++------
 modules/unistr/u8-chr  |    1 +
 3 files changed, 247 insertions(+), 71 deletions(-)

diff --git a/lib/unistr/u8-chr.c b/lib/unistr/u8-chr.c
index 435d1be..657d190 100644
--- a/lib/unistr/u8-chr.c
+++ b/lib/unistr/u8-chr.c
@@ -24,65 +24,148 @@
 uint8_t *
 u8_chr (const uint8_t *s, size_t n, ucs4_t uc)
 {
-  uint8_t c[6];
-
   if (uc < 0x80)
     {
       uint8_t c0 = uc;
 
-      for (; n > 0; s++, n--)
-        {
-          if (*s == c0)
-            return (uint8_t *) s;
-        }
+      return (uint8_t *) memchr ((const char *) s, c0, n);
     }
-  else
-    switch (u8_uctomb_aux (c, uc, 6))
+
+  {
+    uint8_t c[6];
+    size_t uc_size;
+    uc_size = u8_uctomb_aux (c, uc, 6);
+
+    if (n < uc_size)
+      return NULL;
+
+    /* For multibyte character matching we use a Boyer-Moore like
+       algorithm that searches for the last character using multi-byte
+       jumps, and matches back from there.
+
+       Instead of the table, we compare the candidate last character
+       s[UC_SIZE-1] with each of the possible bytes in the UTF-8
+       representation of UC.  If the final byte does not match, we will
+       perform up to UC_SIZE comparisons per memory load---but each
+       comparison lets us skip one byte in the input!
+
+       If the final byte matches, the "real" Boyer-Moore algorithm is
+       approximated.  Instead, u8_chr just looks for other cN that are
+       equal to the final character and uses those to try realigning
+       to another possible match.  For example, when searching for 0xF0
+       0xAA 0xBB 0xAA it will always skip forward by two bytes, even if
+       the character in the string was for example 0xF1 0xAA 0xBB 0xAA.
+       The advantage of this scheme is that the skip count after a failed
+       match can be computed outside the loop, and that it keeps the
+       complexity low for a pretty rare case.  In particular, since c[0]
+       is never between 0x80 and 0xBF, c[0] is never equal to c[UC_SIZE-1]
+       and this is optimal for two-byte UTF-8 characters.  */
+    switch (uc_size)
       {
       case 2:
-        if (n > 1)
-          {
-            uint8_t c0 = c[0];
-            uint8_t c1 = c[1];
-
-            for (n--; n > 0; s++, n--)
-              {
-                if (*s == c0 && s[1] == c1)
-                  return (uint8_t *) s;
-              }
-          }
-        break;
+        {
+          uint8_t c0 = c[0];
+          uint8_t c1 = c[1];
+          const uint8_t *end = s + n - 1;
+
+          while (s < end)
+            {
+              uint8_t s1 = s[1];
+              if (s1 == c1)
+                {
+                  if (*s == c0)
+                    return (uint8_t *) s;
+                  else
+                    s += 2;
+                }
+              else
+                {
+                  if (s1 == c0)
+                    s++;
+                  else
+                    s += 2;
+                }
+            }
+          break;
+        }
 
       case 3:
-        if (n > 2)
-          {
-            uint8_t c0 = c[0];
-            uint8_t c1 = c[1];
-            uint8_t c2 = c[2];
-
-            for (n -= 2; n > 0; s++, n--)
-              {
-                if (*s == c0 && s[1] == c1 && s[2] == c2)
-                  return (uint8_t *) s;
-              }
-          }
-        break;
+        {
+          uint8_t c0 = c[0];
+          uint8_t c1 = c[1];
+          uint8_t c2 = c[2];
+          const uint8_t *end = s + n - 2;
+         size_t skip;
+
+         if (c2 == c1)
+            skip = 1;
+          else
+            skip = 3;
+
+          while (s < end)
+            {
+              uint8_t s2 = s[2];
+              if (s2 == c2)
+                {
+                  if (s[1] == c1 && *s == c0)
+                    return (uint8_t *) s;
+                  else
+                    s += skip;
+                }
+              else
+                {
+                  if (s2 == c1)
+                    s++;
+                  else if (s2 == c0)
+                    s += 2;
+                  else
+                    s += 3;
+                }
+            }
+          break;
+        }
 
       case 4:
-        if (n > 3)
-          {
-            uint8_t c0 = c[0];
-            uint8_t c1 = c[1];
-            uint8_t c2 = c[2];
-            uint8_t c3 = c[3];
-
-            for (n -= 3; n > 0; s++, n--)
-              {
-                if (*s == c0 && s[1] == c1 && s[2] == c2 && s[3] == c3)
-                  return (uint8_t *) s;
-              }
-          }
-        break;
+        {
+          uint8_t c0 = c[0];
+          uint8_t c1 = c[1];
+          uint8_t c2 = c[2];
+          uint8_t c3 = c[3];
+          const uint8_t *end = s + n - 3;
+          size_t skip;
+
+         if (c3 == c2)
+            skip = 1;
+          else if (c3 == c1)
+            skip = 2;
+          else
+            skip = 4;
+
+          while (s < end)
+            {
+              uint8_t s3 = s[3];
+              if (s3 == c3)
+                {
+                  if (s[2] == c2 && s[1] == c1 && *s == c0)
+                    return (uint8_t *) s;
+                  else
+                    s += skip;
+                }
+              else
+                {
+                  if (s3 == c2)
+                    s++;
+                  else if (s3 == c1)
+                    s += 2;
+                  else if (s3 == c0)
+                    s += 3;
+                  else
+                    s += 4;
+                }
+            }
+          break;
+        }
       }
-  return NULL;
+    return NULL;
+  }
 }
diff --git a/lib/unistr/u8-strchr.c b/lib/unistr/u8-strchr.c
index 3ee2465..cb65500 100644
--- a/lib/unistr/u8-strchr.c
+++ b/lib/unistr/u8-strchr.c
@@ -35,14 +35,15 @@ u8_strchr (const uint8_t *s, ucs4_t uc)
       if (false)
         {
           /* Unoptimized code.  */
-          for (;; s++)
+         for (;;)
             {
-              if (*s == c0)
+              uint8_t s0 = *s;
+              if (s0 == c0)
+               return (uint8_t *) s;
+             s++;
+              if (s0 == 0)
                 break;
-              if (*s == 0)
-                goto notfound;
             }
-          return (uint8_t *) s;
         }
       else
         {
@@ -53,22 +54,46 @@ u8_strchr (const uint8_t *s, ucs4_t uc)
         }
     }
   else
+      /* Loops equivalent to strstr, optimized for a specific length (2, 3, 4)
+         of the needle.  We use an algorithm similar to Boyer-Moore which
+        is documented in lib/unistr/u8-chr.c.  There is additional
+        complication because we need to check after every character for
+        a NUL byte, but the idea is the same. */
     switch (u8_uctomb_aux (c, uc, 6))
       {
-      /* Loops equivalent to strstr, optimized for a specific length (2, 3, 4)
-         of the needle.  */
       case 2:
         if (*s == 0)
-          goto notfound;
+          break;
         {
           uint8_t c0 = c[0];
           uint8_t c1 = c[1];
+          uint8_t s1 = s[1];
 
-          for (;; s++)
+          for (;;)
             {
+              if (s1 == c1)
+                {
+                  if (*s == c0)
+                    return (uint8_t *) s;
+                  else
+                    goto case2_skip2;
+                }
+              else
+                {
+                  if (s1 == c0)
+                    goto case2_skip1;
+                  else
+                    goto case2_skip2;
+                }
+             case2_skip2:
+              s++; 
+              s1 = s[1];
+              if (s[1] == 0)
+                break;
+             case2_skip1:
+              s++;
+              s1 = s[1];
               if (s[1] == 0)
-                goto notfound;
-              if (s[1] == c1 && *s == c0)
                 break;
             }
           return (uint8_t *) s;
@@ -76,41 +101,108 @@ u8_strchr (const uint8_t *s, ucs4_t uc)
 
       case 3:
         if (*s == 0 || s[1] == 0)
-          goto notfound;
+          break;
         {
           uint8_t c0 = c[0];
           uint8_t c1 = c[1];
           uint8_t c2 = c[2];
+          uint8_t s2 = s[2];
 
-          for (;; s++)
+          for (;;)
             {
+              if (s2 == c2)
+                {
+                  if (s[1] == c1 && *s == c0)
+                    return (uint8_t *) s;
+                  else if (c2 == c1)
+                    goto case3_skip1;
+                  else
+                    goto case3_skip3;
+                }
+              else
+                {
+                  if (s2 == c1)
+                    goto case3_skip1;
+                  else if (s2 == c0)
+                    goto case3_skip2;
+                  else
+                    goto case3_skip3;
+                }
+             case3_skip3:
+              s++; 
+              s2 = s[2];
+              if (s[2] == 0)
+                break;
+             case3_skip2:
+              s++; 
+              s2 = s[2];
+              if (s[2] == 0)
+                break;
+             case3_skip1:
+              s++;
+              s2 = s[2];
               if (s[2] == 0)
-                goto notfound;
-              if (s[2] == c2 && s[1] == c1 && *s == c0)
                 break;
             }
-          return (uint8_t *) s;
         }
 
       case 4:
         if (*s == 0 || s[1] == 0 || s[2] == 0)
-          goto notfound;
+          break;
         {
           uint8_t c0 = c[0];
           uint8_t c1 = c[1];
           uint8_t c2 = c[2];
           uint8_t c3 = c[3];
+          uint8_t s3 = s[3];
 
-          for (;; s++)
+          for (;;)
             {
+              if (s3 == c3)
+                {
+                  if (s[2] == c2 && s[1] == c1 && *s == c0)
+                    return (uint8_t *) s;
+                  else if (c3 == c2)
+                    goto case4_skip1;
+                  else if (c3 == c1)
+                    goto case4_skip2;
+                  else
+                    goto case4_skip4;
+                }
+              else
+                {
+                  if (s3 == c2)
+                    goto case4_skip1;
+                  else if (s3 == c1)
+                    goto case4_skip2;
+                  else if (s3 == c0)
+                    goto case4_skip3;
+                  else
+                    goto case4_skip4;
+                }
+             case4_skip4:
+              s++; 
+              s3 = s[3];
+              if (s[3] == 0)
+                break;
+             case4_skip3:
+              s++; 
+              s3 = s[3];
+              if (s[3] == 0)
+                break;
+             case4_skip2:
+              s++; 
+              s3 = s[3];
+              if (s[3] == 0)
+                break;
+             case4_skip1:
+              s++;
+              s3 = s[3];
               if (s[3] == 0)
-                goto notfound;
-              if (s[3] == c3 && s[2] == c2 && s[1] == c1 && *s == c0)
                 break;
             }
-          return (uint8_t *) s;
         }
       }
-notfound:
+
   return NULL;
 }
diff --git a/modules/unistr/u8-chr b/modules/unistr/u8-chr
index 6f5de6c..a337b0f 100644
--- a/modules/unistr/u8-chr
+++ b/modules/unistr/u8-chr
@@ -5,6 +5,7 @@ Files:
 lib/unistr/u8-chr.c
 
 Depends-on:
+memchr
 unistr/base
 unistr/u8-uctomb
 
-- 
1.7.1