1 /* Search character in piece of UTF-8 string.
2 Copyright (C) 1999, 2002, 2006-2007, 2009-2012 Free Software Foundation,
4 Written by Bruno Haible <bruno@clisp.org>, 2002.
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.
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.
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/>. */
27 u8_chr (const uint8_t *s, size_t n, ucs4_t uc)
33 return (uint8_t *) memchr ((const char *) s, c0, n);
39 uc_size = u8_uctomb_aux (c, uc, 6);
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.
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!
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. */
71 const uint8_t *end = s + n - 1;
76 Test whether s[0..1] == { c0, c1 }. */
83 /* Skip the search at s + 1, because s[1] = c1 < c0. */
91 /* Skip the search at s + 1, because s[1] != c0. */
104 const uint8_t *end = s + n - 2;
115 Test whether s[0..2] == { c0, c1, c2 }. */
119 if (s[1] == c1 && *s == c0)
120 return (uint8_t *) s;
123 Skip the search at s + 1, because s[2] == c2 != c1.
124 Skip the search at s + 2, because s[2] == c2 < c0. */
132 /* Skip the search at s + 1, because s[2] != c1. */
135 /* Skip the search at s + 1, because s[2] != c1.
136 Skip the search at s + 2, because s[2] != c0. */
150 const uint8_t *end = s + n - 3;
163 Test whether s[0..3] == { c0, c1, c2, c3 }. */
167 if (s[2] == c2 && s[1] == c1 && *s == c0)
168 return (uint8_t *) s;
171 Skip the search at s + 1, because s[3] == c3 != c2.
173 Skip the search at s + 2, because s[3] == c3 != c1.
174 Skip the search at s + 3, because s[3] == c3 < c0. */
182 /* Skip the search at s + 1, because s[3] != c2. */
185 /* Skip the search at s + 1, because s[3] != c2.
186 Skip the search at s + 2, because s[3] != c1. */
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. */