lib/unistr/u8-chr.c

   1 /* Search character in piece of UTF-8 string.
   2    Copyright (C) 1999, 2002, 2006-2007, 2009-2010 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_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           while (s < end)
  74             {
  75               uint8_t s1 = s[1];
  76               if (s1 == c1)
  77                 {
  78                   if (*s == c0)
  79                     return (uint8_t *) s;
  80                   else
  81                     s += 2;
  82                 }
  83               else
  84                 {
  85                   if (s1 == c0)
  86                     s++;
  87                   else
  88                     s += 2;
  89                 }
  90             }
  91           break;
  92         }
  93
  94       case 3:
  95         {
  96           uint8_t c0 = c[0];
  97           uint8_t c1 = c[1];
  98           uint8_t c2 = c[2];
  99           const uint8_t *end = s + n - 2;
 100           size_t skip;
 101
 102           if (c2 == c1)
 103             skip = 1;
 104           else
 105             skip = 3;
 106
 107           while (s < end)
 108             {
 109               uint8_t s2 = s[2];
 110               if (s2 == c2)
 111                 {
 112                   if (s[1] == c1 && *s == c0)
 113                     return (uint8_t *) s;
 114                   else
 115                     s += skip;
 116                 }
 117               else
 118                 {
 119                   if (s2 == c1)
 120                     s++;
 121                   else if (s2 == c0)
 122                     s += 2;
 123                   else
 124                     s += 3;
 125                 }
 126             }
 127           break;
 128         }
 129
 130       case 4:
 131         {
 132           uint8_t c0 = c[0];
 133           uint8_t c1 = c[1];
 134           uint8_t c2 = c[2];
 135           uint8_t c3 = c[3];
 136           const uint8_t *end = s + n - 3;
 137           size_t skip;
 138
 139           if (c3 == c2)
 140             skip = 1;
 141           else if (c3 == c1)
 142             skip = 2;
 143           else
 144             skip = 4;
 145
 146           while (s < end)
 147             {
 148               uint8_t s3 = s[3];
 149               if (s3 == c3)
 150                 {
 151                   if (s[2] == c2 && s[1] == c1 && *s == c0)
 152                     return (uint8_t *) s;
 153                   else
 154                     s += skip;
 155                 }
 156               else
 157                 {
 158                   if (s3 == c2)
 159                     s++;
 160                   else if (s3 == c1)
 161                     s += 2;
 162                   else if (s3 == c0)
 163                     s += 3;
 164                   else
 165                     s += 4;
 166                 }
 167             }
 168           break;
 169         }
 170       }
 171     return NULL;
 172   }
 173 }