diff options
Diffstat (limited to 'lib/unistr/u8-chr.c')
| -rw-r--r-- | lib/unistr/u8-chr.c | 213 |
1 files changed, 50 insertions, 163 deletions
diff --git a/lib/unistr/u8-chr.c b/lib/unistr/u8-chr.c index c7779d2a..435d1be6 100644 --- a/lib/unistr/u8-chr.c +++ b/lib/unistr/u8-chr.c @@ -1,5 +1,5 @@ /* Search character in piece of UTF-8 string. - Copyright (C) 1999, 2002, 2006-2007, 2009-2015 Free Software Foundation, + Copyright (C) 1999, 2002, 2006-2007, 2009-2010 Free Software Foundation, Inc. Written by Bruno Haible <bruno@clisp.org>, 2002. @@ -21,181 +21,68 @@ /* Specification. */ #include "unistr.h" -#include <string.h> - uint8_t * u8_chr (const uint8_t *s, size_t n, ucs4_t uc) { + uint8_t c[6]; + if (uc < 0x80) { uint8_t c0 = uc; - return (uint8_t *) memchr ((const char *) s, c0, n); + for (; n > 0; s++, n--) + { + if (*s == c0) + return (uint8_t *) s; + } } - - { - uint8_t c[6]; - size_t uc_size; - uc_size = u8_uctomb_aux (c, uc, 6); - - if (n < uc_size) - return NULL; - - /* For multibyte character matching we use a Boyer-Moore like - algorithm that searches for the last byte, skipping multi-byte - jumps, and matches back from there. - - Instead of using a table as is usual for Boyer-Moore, we compare - the candidate last byte s[UC_SIZE-1] with each of the possible - bytes in the UTF-8 representation of UC. If the final byte does - not match, we will perform up to UC_SIZE comparisons per memory - load---but each comparison lets us skip one byte in the input! - - If the final byte matches, the "real" Boyer-Moore algorithm - is approximated. Instead, u8_chr just looks for other cN that - are equal to the final byte and uses those to try realigning to - another possible match. For example, when searching for 0xF0 - 0xAA 0xBB 0xAA it will always skip forward by two bytes, even if - the character in the string was for example 0xF1 0xAA 0xBB 0xAA. - The advantage of this scheme is that the skip count after a failed - match can be computed outside the loop, and that it keeps the - complexity low for a pretty rare case. In particular, since c[0] - is never between 0x80 and 0xBF, c[0] is never equal to c[UC_SIZE-1] - and this is optimal for two-byte UTF-8 characters. */ - switch (uc_size) + else + switch (u8_uctomb_aux (c, uc, 6)) { case 2: - { - uint8_t c0 = c[0]; - uint8_t c1 = c[1]; - const uint8_t *end = s + n - 1; - - do - { - /* Here s < end. - Test whether s[0..1] == { c0, c1 }. */ - uint8_t s1 = s[1]; - if (s1 == c1) - { - if (*s == c0) - return (uint8_t *) s; - else - /* Skip the search at s + 1, because s[1] = c1 < c0. */ - s += 2; - } - else - { - if (s1 == c0) - s++; - else - /* Skip the search at s + 1, because s[1] != c0. */ - s += 2; - } - } - while (s < end); - break; - } + if (n > 1) + { + uint8_t c0 = c[0]; + uint8_t c1 = c[1]; + + for (n--; n > 0; s++, n--) + { + if (*s == c0 && s[1] == c1) + return (uint8_t *) s; + } + } + break; case 3: - { - uint8_t c0 = c[0]; - uint8_t c1 = c[1]; - uint8_t c2 = c[2]; - const uint8_t *end = s + n - 2; - size_t skip; - - if (c2 == c1) - skip = 1; - else - skip = 3; - - do - { - /* Here s < end. - Test whether s[0..2] == { c0, c1, c2 }. */ - uint8_t s2 = s[2]; - if (s2 == c2) - { - if (s[1] == c1 && *s == c0) - return (uint8_t *) s; - else - /* If c2 != c1: - Skip the search at s + 1, because s[2] == c2 != c1. - Skip the search at s + 2, because s[2] == c2 < c0. */ - s += skip; - } - else - { - if (s2 == c1) - s++; - else if (s2 == c0) - /* Skip the search at s + 1, because s[2] != c1. */ - s += 2; - else - /* Skip the search at s + 1, because s[2] != c1. - Skip the search at s + 2, because s[2] != c0. */ - s += 3; - } - } - while (s < end); - break; - } + if (n > 2) + { + uint8_t c0 = c[0]; + uint8_t c1 = c[1]; + uint8_t c2 = c[2]; + + for (n -= 2; n > 0; s++, n--) + { + if (*s == c0 && s[1] == c1 && s[2] == c2) + return (uint8_t *) s; + } + } + break; case 4: - { - uint8_t c0 = c[0]; - uint8_t c1 = c[1]; - uint8_t c2 = c[2]; - uint8_t c3 = c[3]; - const uint8_t *end = s + n - 3; - size_t skip; - - if (c3 == c2) - skip = 1; - else if (c3 == c1) - skip = 2; - else - skip = 4; - - do - { - /* Here s < end. - Test whether s[0..3] == { c0, c1, c2, c3 }. */ - uint8_t s3 = s[3]; - if (s3 == c3) - { - if (s[2] == c2 && s[1] == c1 && *s == c0) - return (uint8_t *) s; - else - /* If c3 != c2: - Skip the search at s + 1, because s[3] == c3 != c2. - If c3 != c1: - Skip the search at s + 2, because s[3] == c3 != c1. - Skip the search at s + 3, because s[3] == c3 < c0. */ - s += skip; - } - else - { - if (s3 == c2) - s++; - else if (s3 == c1) - /* Skip the search at s + 1, because s[3] != c2. */ - s += 2; - else if (s3 == c0) - /* Skip the search at s + 1, because s[3] != c2. - Skip the search at s + 2, because s[3] != c1. */ - s += 3; - else - /* Skip the search at s + 1, because s[3] != c2. - Skip the search at s + 2, because s[3] != c1. - Skip the search at s + 3, because s[3] != c0. */ - s += 4; - } - } - while (s < end); - break; - } + if (n > 3) + { + uint8_t c0 = c[0]; + uint8_t c1 = c[1]; + uint8_t c2 = c[2]; + uint8_t c3 = c[3]; + + for (n -= 3; n > 0; s++, n--) + { + if (*s == c0 && s[1] == c1 && s[2] == c2 && s[3] == c3) + return (uint8_t *) s; + } + } + break; } - return NULL; - } + return NULL; } |