lib/unistr/u8-strchr.c

   1 /* Search character in UTF-8 string.
   2    Copyright (C) 1999, 2002, 2006-2007, 2009-2014 Free Software Foundation,
   3    Inc.
   4    Written by Bruno Haible <bruno@clisp.org>, 2002.
   5
   6    This program is free software: you can redistribute it and/or modify it
   7    under the terms of the GNU Lesser General Public License as published
   8    by the Free Software Foundation; either version 3 of the License, or
   9    (at your option) any later version.
  10
  11    This program is distributed in the hope that it will be useful,
  12    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14    Lesser General Public License for more details.
  15
  16    You should have received a copy of the GNU Lesser General Public License
  17    along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
  18
  19 #include <config.h>
  20
  21 /* Specification.  */
  22 #include "unistr.h"
  23
  24 #include <string.h>
  25
  26 uint8_t *
  27 u8_strchr (const uint8_t *s, ucs4_t uc)
  28 {
  29   uint8_t c[6];
  30
  31   if (uc < 0x80)
  32     {
  33       uint8_t c0 = uc;
  34
  35       if (false)
  36         {
  37           /* Unoptimized code.  */
  38           for (;;)
  39             {
  40               uint8_t s0 = *s;
  41               if (s0 == c0)
  42                 return (uint8_t *) s;
  43               s++;
  44               if (s0 == 0)
  45                 break;
  46             }
  47         }
  48       else
  49         {
  50           /* Optimized code.
  51              strchr() is often so well optimized, that it's worth the
  52              added function call.  */
  53           return (uint8_t *) strchr ((const char *) s, c0);
  54         }
  55     }
  56   else
  57       /* Loops equivalent to strstr, optimized for a specific length (2, 3, 4)
  58          of the needle.  We use an algorithm similar to Boyer-Moore which
  59          is documented in lib/unistr/u8-chr.c.  There is additional
  60          complication because we need to check after every byte for
  61          a NUL byte, but the idea is the same. */
  62     switch (u8_uctomb_aux (c, uc, 6))
  63       {
  64       case 2:
  65         if (*s == 0 || s[1] == 0)
  66           break;
  67         {
  68           uint8_t c0 = c[0];
  69           uint8_t c1 = c[1];
  70           /* Search for { c0, c1 }.  */
  71           uint8_t s1 = s[1];
  72
  73           for (;;)
  74             {
  75               /* Here s[0] != 0, s[1] != 0.
  76                  Test whether s[0..1] == { c0, c1 }.  */
  77               if (s1 == c1)
  78                 {
  79                   if (*s == c0)
  80                     return (uint8_t *) s;
  81                   else
  82                     /* Skip the search at s + 1, because s[1] = c1 < c0.  */
  83                     goto case2_skip2;
  84                 }
  85               else
  86                 {
  87                   if (s1 == c0)
  88                     goto case2_skip1;
  89                   else
  90                     /* Skip the search at s + 1, because s[1] != c0.  */
  91                     goto case2_skip2;
  92                 }
  93              case2_skip2:
  94               s++;
  95               s1 = s[1];
  96               if (s[1] == 0)
  97                 break;
  98              case2_skip1:
  99               s++;
 100               s1 = s[1];
 101               if (s[1] == 0)
 102                 break;
 103             }
 104         }
 105         break;
 106
 107       case 3:
 108         if (*s == 0 || s[1] == 0 || s[2] == 0)
 109           break;
 110         {
 111           uint8_t c0 = c[0];
 112           uint8_t c1 = c[1];
 113           uint8_t c2 = c[2];
 114           /* Search for { c0, c1, c2 }.  */
 115           uint8_t s2 = s[2];
 116
 117           for (;;)
 118             {
 119               /* Here s[0] != 0, s[1] != 0, s[2] != 0.
 120                  Test whether s[0..2] == { c0, c1, c2 }.  */
 121               if (s2 == c2)
 122                 {
 123                   if (s[1] == c1 && *s == c0)
 124                     return (uint8_t *) s;
 125                   else
 126                     /* If c2 != c1:
 127                          Skip the search at s + 1, because s[2] == c2 != c1.
 128                        Skip the search at s + 2, because s[2] == c2 < c0.  */
 129                     if (c2 == c1)
 130                       goto case3_skip1;
 131                     else
 132                       goto case3_skip3;
 133                 }
 134               else
 135                 {
 136                   if (s2 == c1)
 137                     goto case3_skip1;
 138                   else if (s2 == c0)
 139                     /* Skip the search at s + 1, because s[2] != c1.  */
 140                     goto case3_skip2;
 141                   else
 142                     /* Skip the search at s + 1, because s[2] != c1.
 143                        Skip the search at s + 2, because s[2] != c0.  */
 144                     goto case3_skip3;
 145                 }
 146              case3_skip3:
 147               s++;
 148               s2 = s[2];
 149               if (s[2] == 0)
 150                 break;
 151              case3_skip2:
 152               s++;
 153               s2 = s[2];
 154               if (s[2] == 0)
 155                 break;
 156              case3_skip1:
 157               s++;
 158               s2 = s[2];
 159               if (s[2] == 0)
 160                 break;
 161             }
 162         }
 163         break;
 164
 165       case 4:
 166         if (*s == 0 || s[1] == 0 || s[2] == 0 || s[3] == 0)
 167           break;
 168         {
 169           uint8_t c0 = c[0];
 170           uint8_t c1 = c[1];
 171           uint8_t c2 = c[2];
 172           uint8_t c3 = c[3];
 173           /* Search for { c0, c1, c2, c3 }.  */
 174           uint8_t s3 = s[3];
 175
 176           for (;;)
 177             {
 178               /* Here s[0] != 0, s[1] != 0, s[2] != 0, s[3] != 0.
 179                  Test whether s[0..3] == { c0, c1, c2, c3 }.  */
 180               if (s3 == c3)
 181                 {
 182                   if (s[2] == c2 && s[1] == c1 && *s == c0)
 183                     return (uint8_t *) s;
 184                   else
 185                     /* If c3 != c2:
 186                          Skip the search at s + 1, because s[3] == c3 != c2.
 187                        If c3 != c1:
 188                          Skip the search at s + 2, because s[3] == c3 != c1.
 189                        Skip the search at s + 3, because s[3] == c3 < c0.  */
 190                     if (c3 == c2)
 191                       goto case4_skip1;
 192                     else if (c3 == c1)
 193                       goto case4_skip2;
 194                     else
 195                       goto case4_skip4;
 196                 }
 197               else
 198                 {
 199                   if (s3 == c2)
 200                     goto case4_skip1;
 201                   else if (s3 == c1)
 202                     /* Skip the search at s + 1, because s[3] != c2.  */
 203                     goto case4_skip2;
 204                   else if (s3 == c0)
 205                     /* Skip the search at s + 1, because s[3] != c2.
 206                        Skip the search at s + 2, because s[3] != c1.  */
 207                     goto case4_skip3;
 208                   else
 209                     /* Skip the search at s + 1, because s[3] != c2.
 210                        Skip the search at s + 2, because s[3] != c1.
 211                        Skip the search at s + 3, because s[3] != c0.  */
 212                     goto case4_skip4;
 213                 }
 214              case4_skip4:
 215               s++;
 216               s3 = s[3];
 217               if (s[3] == 0)
 218                 break;
 219              case4_skip3:
 220               s++;
 221               s3 = s[3];
 222               if (s[3] == 0)
 223                 break;
 224              case4_skip2:
 225               s++;
 226               s3 = s[3];
 227               if (s[3] == 0)
 228                 break;
 229              case4_skip1:
 230               s++;
 231               s3 = s[3];
 232               if (s[3] == 0)
 233                 break;
 234             }
 235         }
 236         break;
 237       }
 238
 239   return NULL;
 240 }