unistr/u8-chr, unistr/u8-strchr: use Boyer-Moore like algorithm.

[pspp] / lib / unistr / u8-strchr.c

diff --git a/lib/unistr/u8-strchr.c b/lib/unistr/u8-strchr.c
index 5ab3f8061b13e498af48527b633ffc624bb59b60..8ff49ef21356bc1c3b9f3e2fba9e5e8b50d9a35f 100644 (file)
--- a/lib/unistr/u8-strchr.c
+++ b/lib/unistr/u8-strchr.c
@@ -1,5 +1,6 @@
 /* Search character in UTF-8 string.
-   Copyright (C) 1999, 2002, 2006-2007, 2009 Free Software Foundation, Inc.
+   Copyright (C) 1999, 2002, 2006-2007, 2009-2010 Free Software Foundation,
+   Inc.
    Written by Bruno Haible <bruno@clisp.org>, 2002.
 
    This program is free software: you can redistribute it and/or modify it
@@ -20,6 +21,8 @@
 /* Specification.  */
 #include "unistr.h"
 
+#include <string.h>
+
 uint8_t *
 u8_strchr (const uint8_t *s, ucs4_t uc)
 {
@@ -29,30 +32,68 @@ u8_strchr (const uint8_t *s, ucs4_t uc)
     {
       uint8_t c0 = uc;
 
-      for (;; s++)
+      if (false)
+        {
+          /* Unoptimized code.  */
+         for (;;)
+            {
+              uint8_t s0 = *s;
+              if (s0 == c0)
+               return (uint8_t *) s;
+             s++;
+              if (s0 == 0)
+                break;
+            }
+        }
+      else
         {
-          if (*s == c0)
-            break;
-          if (*s == 0)
-            goto notfound;
+          /* Optimized code.
+             strchr() is often so well optimized, that it's worth the
+             added function call.  */
+          return (uint8_t *) strchr ((const char *) s, c0);
         }
-      return (uint8_t *) s;
     }
   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 byte for
+        a NUL byte, but the idea is the same. */
     switch (u8_uctomb_aux (c, uc, 6))
       {
       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 == c0 && s[1] == c1)
                 break;
             }
           return (uint8_t *) s;
@@ -60,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 == c0 && s[1] == c1 && s[2] == c2)
                 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 == c0 && s[1] == c1 && s[2] == c2 && s[3] == c3)
                 break;
             }
-          return (uint8_t *) s;
         }
       }
-notfound:
+
   return NULL;
 }