lib/unistr/u8-chr.c

   1 /* Search character in piece of UTF-8 string.
   2    Copyright (C) 1999, 2002, 2006-2007, 2009-2021 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 <https://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_chr (const uint8_t *s, size_t n, ucs4_t uc)
  28 {
  29   if (uc < 0x80)
  30     {
  31       uint8_t c0 = uc;
  32
  33       return (uint8_t *) memchr ((const char *) s, c0, n);
  34     }
  35
  36   {
  37     uint8_t c[6];
  38     size_t uc_size;
  39     uc_size = u8_uctomb_aux (c, uc, 6);
  40
  41     if (n < uc_size)
  42       return NULL;
  43
  44     /* For multibyte character matching we use a Boyer-Moore like
  45        algorithm that searches for the last byte, skipping multi-byte
  46        jumps, and matches back from there.
  47
  48        Instead of using a table as is usual for Boyer-Moore, we compare
  49        the candidate last byte s[UC_SIZE-1] with each of the possible
  50        bytes in the UTF-8 representation of UC.  If the final byte does
  51        not match, we will perform up to UC_SIZE comparisons per memory
  52        load---but each comparison lets us skip one byte in the input!
  53
  54        If the final byte matches, the "real" Boyer-Moore algorithm
  55        is approximated.  Instead, u8_chr just looks for other cN that
  56        are equal to the final byte and uses those to try realigning to
  57        another possible match.  For example, when searching for 0xF0
  58        0xAA 0xBB 0xAA it will always skip forward by two bytes, even if
  59        the character in the string was for example 0xF1 0xAA 0xBB 0xAA.
  60        The advantage of this scheme is that the skip count after a failed
  61        match can be computed outside the loop, and that it keeps the
  62        complexity low for a pretty rare case.  In particular, since c[0]
  63        is never between 0x80 and 0xBF, c[0] is never equal to c[UC_SIZE-1]
  64        and this is optimal for two-byte UTF-8 characters.  */
  65     switch (uc_size)
  66       {
  67       case 2:
  68         {
  69           uint8_t c0 = c[0];
  70           uint8_t c1 = c[1];
  71           const uint8_t *end = s + n - 1;
  72
  73           do
  74             {
  75               /* Here s < end.
  76                  Test whether s[0..1] == { c0, c1 }.  */
  77               uint8_t s1 = s[1];
  78               if (s1 == c1)
  79                 {
  80                   if (*s == c0)
  81                     return (uint8_t *) s;
  82                   else
  83                     /* Skip the search at s + 1, because s[1] = c1 < c0.  */
  84                     s += 2;
  85                 }
  86               else
  87                 {
  88                   if (s1 == c0)
  89                     s++;
  90                   else
  91                     /* Skip the search at s + 1, because s[1] != c0.  */
  92                     s += 2;
  93                 }
  94             }
  95           while (s < end);
  96           break;
  97         }
  98
  99       case 3:
 100         {
 101           uint8_t c0 = c[0];
 102           uint8_t c1 = c[1];
 103           uint8_t c2 = c[2];
 104           const uint8_t *end = s + n - 2;
 105           size_t skip;
 106
 107           if (c2 == c1)
 108             skip = 1;
 109           else
 110             skip = 3;
 111
 112           do
 113             {
 114               /* Here s < end.
 115                  Test whether s[0..2] == { c0, c1, c2 }.  */
 116               uint8_t s2 = s[2];
 117               if (s2 == c2)
 118                 {
 119                   if (s[1] == c1 && *s == c0)
 120                     return (uint8_t *) s;
 121                   else
 122                     /* If c2 != c1:
 123                          Skip the search at s + 1, because s[2] == c2 != c1.
 124                        Skip the search at s + 2, because s[2] == c2 < c0.  */
 125                     s += skip;
 126                 }
 127               else
 128                 {
 129                   if (s2 == c1)
 130                     s++;
 131                   else if (s2 == c0)
 132                     /* Skip the search at s + 1, because s[2] != c1.  */
 133                     s += 2;
 134                   else
 135                     /* Skip the search at s + 1, because s[2] != c1.
 136                        Skip the search at s + 2, because s[2] != c0.  */
 137                     s += 3;
 138                 }
 139             }
 140           while (s < end);
 141           break;
 142         }
 143
 144       case 4:
 145         {
 146           uint8_t c0 = c[0];
 147           uint8_t c1 = c[1];
 148           uint8_t c2 = c[2];
 149           uint8_t c3 = c[3];
 150           const uint8_t *end = s + n - 3;
 151           size_t skip;
 152
 153           if (c3 == c2)
 154             skip = 1;
 155           else if (c3 == c1)
 156             skip = 2;
 157           else
 158             skip = 4;
 159
 160           do
 161             {
 162               /* Here s < end.
 163                  Test whether s[0..3] == { c0, c1, c2, c3 }.  */
 164               uint8_t s3 = s[3];
 165               if (s3 == c3)
 166                 {
 167                   if (s[2] == c2 && s[1] == c1 && *s == c0)
 168                     return (uint8_t *) s;
 169                   else
 170                     /* If c3 != c2:
 171                          Skip the search at s + 1, because s[3] == c3 != c2.
 172                        If c3 != c1:
 173                          Skip the search at s + 2, because s[3] == c3 != c1.
 174                        Skip the search at s + 3, because s[3] == c3 < c0.  */
 175                     s += skip;
 176                 }
 177               else
 178                 {
 179                   if (s3 == c2)
 180                     s++;
 181                   else if (s3 == c1)
 182                     /* Skip the search at s + 1, because s[3] != c2.  */
 183                     s += 2;
 184                   else if (s3 == c0)
 185                     /* Skip the search at s + 1, because s[3] != c2.
 186                        Skip the search at s + 2, because s[3] != c1.  */
 187                     s += 3;
 188                   else
 189                     /* Skip the search at s + 1, because s[3] != c2.
 190                        Skip the search at s + 2, because s[3] != c1.
 191                        Skip the search at s + 3, because s[3] != c0.  */
 192                     s += 4;
 193                 }
 194             }
 195           while (s < end);
 196           break;
 197         }
 198       }
 199     return NULL;
 200   }
 201 }