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

[bonzini]

From: Paolo Bonzini <address@hidden>

* lib/unistr/u8-chr.c: Add Boyer-Moore like optimization.
---
 lib/unistr/u8-chr.c    |  129 ++++++++++++++++++++++++++++++++---------------
 1 files changed, 88 insertions(+), 41 deletions(-)

diff --git a/lib/unistr/u8-chr.c b/lib/unistr/u8-chr.c
index 435d1be..6ad6fdb 100644
--- a/lib/unistr/u8-chr.c
+++ b/lib/unistr/u8-chr.c
@@ -30,59 +30,106 @@ u8_chr (const uint8_t *s, size_t n, ucs4_t uc)
     {
       uint8_t c0 = uc;
 
-      for (; n > 0; s++, n--)
-        {
-          if (*s == c0)
-            return (uint8_t *) s;
-        }
+      return memchr (s, c0, n);
     }
   else
     switch (u8_uctomb_aux (c, uc, 6))
       {
       case 2:
-        if (n > 1)
-          {
-            uint8_t c0 = c[0];
-            uint8_t c1 = c[1];
+        {
+          uint8_t c0 = c[0];
+          uint8_t c1 = c[1];
+          const uint8_t *end = s + n - 1;
 
-            for (n--; n > 0; s++, n--)
-              {
-                if (*s == c0 && s[1] == c1)
-                  return (uint8_t *) s;
-              }
-          }
-        break;
+          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];
+        {
+          uint8_t c0 = c[0];
+          uint8_t c1 = c[1];
+          uint8_t c2 = c[2];
+          const uint8_t *end = s + n - 2;
 
-            for (n -= 2; n > 0; s++, n--)
-              {
-                if (*s == c0 && s[1] == c1 && s[2] == c2)
-                  return (uint8_t *) s;
-              }
-          }
-        break;
+          while (s < end)
+            {
+              uint8_t s2 = s[2];
+              if (s2 == c2)
+                {
+                  if (s[1] == c1 && *s == c0)
+                    return (uint8_t *) s;
+                  else if (s2 == c1)
+                    s++;
+                  else
+                    s += 3;
+                }
+              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];
+        {
+          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;
 
-            for (n -= 3; n > 0; s++, n--)
-              {
-                if (*s == c0 && s[1] == c1 && s[2] == c2 && s[3] == c3)
-                  return (uint8_t *) s;
-              }
-          }
-        break;
+          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 if (s3 == c2)
+                    s++;
+                  else if (s3 == c1)
+                    s += 2;
+                  else
+                    s += 4;
+                }
+              else
+                {
+                  if (s3 == c2)
+                    s++;
+                  else if (s3 == c1)
+                    s += 2;
+                  else if (s3 == c0)
+                    s += 3;
+                  else
+                    s += 4;
+                }
+            }
+          break;
+        }
       }
   return NULL;
 }
-- 
1.7.1