From: Paolo Bonzini Date: Tue, 20 Jul 2010 13:47:47 +0000 (+0200) Subject: unistr/u8-chr, unistr/u8-strchr: use Boyer-Moore like algorithm. X-Git-Tag: v0.1~4012 X-Git-Url: http://erislabs.net/gitweb/?p=gnulib.git;a=commitdiff_plain;h=b48afd89ec9be56156d6e2bebfdf457c778fe5c3 unistr/u8-chr, unistr/u8-strchr: use Boyer-Moore like algorithm. * lib/unistr/u8-chr.c, lib/unistr/u8-strchr.c: Add Boyer-Moore like operation. * modules/unistr/u8-chr: Depend on memchr. --- diff --git a/lib/unistr/u8-chr.c b/lib/unistr/u8-chr.c index 435d1be61..46a3bd205 100644 --- a/lib/unistr/u8-chr.c +++ b/lib/unistr/u8-chr.c @@ -24,65 +24,148 @@ 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; - for (; n > 0; s++, n--) - { - if (*s == c0) - return (uint8_t *) s; - } + return (uint8_t *) memchr ((const char *) s, c0, n); } - else - switch (u8_uctomb_aux (c, uc, 6)) + + { + 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) { case 2: - 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; + { + uint8_t c0 = c[0]; + uint8_t c1 = c[1]; + const uint8_t *end = s + n - 1; + + while (s < end) + { + uint8_t s1 = s[1]; + if (s1 == c1) + { + if (*s == c0) + return (uint8_t *) s; + else + s += 2; + } + else + { + if (s1 == c0) + s++; + else + s += 2; + } + } + break; + } case 3: - 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; + { + 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; + + while (s < end) + { + uint8_t s2 = s[2]; + if (s2 == c2) + { + if (s[1] == c1 && *s == c0) + return (uint8_t *) s; + else + s += skip; + } + else + { + if (s2 == c1) + s++; + else if (s2 == c0) + s += 2; + else + s += 3; + } + } + break; + } case 4: - 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; + { + 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; + + while (s < end) + { + uint8_t s3 = s[3]; + if (s3 == c3) + { + if (s[2] == c2 && s[1] == c1 && *s == c0) + return (uint8_t *) s; + else + s += skip; + } + else + { + if (s3 == c2) + s++; + else if (s3 == c1) + s += 2; + else if (s3 == c0) + s += 3; + else + s += 4; + } + } + break; + } } - return NULL; + return NULL; + } } diff --git a/lib/unistr/u8-strchr.c b/lib/unistr/u8-strchr.c index 3ee246521..8ff49ef21 100644 --- a/lib/unistr/u8-strchr.c +++ b/lib/unistr/u8-strchr.c @@ -35,14 +35,15 @@ u8_strchr (const uint8_t *s, ucs4_t uc) if (false) { /* Unoptimized code. */ - for (;; s++) + for (;;) { - if (*s == c0) + uint8_t s0 = *s; + if (s0 == c0) + return (uint8_t *) s; + s++; + if (s0 == 0) break; - if (*s == 0) - goto notfound; } - return (uint8_t *) s; } else { @@ -53,22 +54,46 @@ u8_strchr (const uint8_t *s, ucs4_t uc) } } else + /* Loops equivalent to strstr, optimized for a specific length (2, 3, 4) + of the needle. We use an algorithm similar to Boyer-Moore which + is documented in lib/unistr/u8-chr.c. There is additional + complication because we need to check after every byte for + a NUL byte, but the idea is the same. */ switch (u8_uctomb_aux (c, uc, 6)) { - /* Loops equivalent to strstr, optimized for a specific length (2, 3, 4) - of the needle. */ case 2: if (*s == 0) - goto notfound; + break; { uint8_t c0 = c[0]; uint8_t c1 = c[1]; + uint8_t s1 = s[1]; - for (;; s++) + for (;;) { + if (s1 == c1) + { + if (*s == c0) + return (uint8_t *) s; + else + goto case2_skip2; + } + else + { + if (s1 == c0) + goto case2_skip1; + else + goto case2_skip2; + } + case2_skip2: + s++; + s1 = s[1]; + if (s[1] == 0) + break; + case2_skip1: + s++; + s1 = s[1]; if (s[1] == 0) - goto notfound; - if (s[1] == c1 && *s == c0) break; } return (uint8_t *) s; @@ -76,41 +101,108 @@ u8_strchr (const uint8_t *s, ucs4_t uc) case 3: if (*s == 0 || s[1] == 0) - goto notfound; + break; { uint8_t c0 = c[0]; uint8_t c1 = c[1]; uint8_t c2 = c[2]; + uint8_t s2 = s[2]; - for (;; s++) + for (;;) { + if (s2 == c2) + { + if (s[1] == c1 && *s == c0) + return (uint8_t *) s; + else if (c2 == c1) + goto case3_skip1; + else + goto case3_skip3; + } + else + { + if (s2 == c1) + goto case3_skip1; + else if (s2 == c0) + goto case3_skip2; + else + goto case3_skip3; + } + case3_skip3: + s++; + s2 = s[2]; + if (s[2] == 0) + break; + case3_skip2: + s++; + s2 = s[2]; + if (s[2] == 0) + break; + case3_skip1: + s++; + s2 = s[2]; if (s[2] == 0) - goto notfound; - if (s[2] == c2 && s[1] == c1 && *s == c0) break; } - return (uint8_t *) s; } case 4: if (*s == 0 || s[1] == 0 || s[2] == 0) - goto notfound; + break; { uint8_t c0 = c[0]; uint8_t c1 = c[1]; uint8_t c2 = c[2]; uint8_t c3 = c[3]; + uint8_t s3 = s[3]; - for (;; s++) + for (;;) { + if (s3 == c3) + { + if (s[2] == c2 && s[1] == c1 && *s == c0) + return (uint8_t *) s; + else if (c3 == c2) + goto case4_skip1; + else if (c3 == c1) + goto case4_skip2; + else + goto case4_skip4; + } + else + { + if (s3 == c2) + goto case4_skip1; + else if (s3 == c1) + goto case4_skip2; + else if (s3 == c0) + goto case4_skip3; + else + goto case4_skip4; + } + case4_skip4: + s++; + s3 = s[3]; + if (s[3] == 0) + break; + case4_skip3: + s++; + s3 = s[3]; + if (s[3] == 0) + break; + case4_skip2: + s++; + s3 = s[3]; + if (s[3] == 0) + break; + case4_skip1: + s++; + s3 = s[3]; if (s[3] == 0) - goto notfound; - if (s[3] == c3 && s[2] == c2 && s[1] == c1 && *s == c0) break; } - return (uint8_t *) s; } } -notfound: + return NULL; } diff --git a/modules/unistr/u8-chr b/modules/unistr/u8-chr index 6f5de6c72..a337b0f16 100644 --- a/modules/unistr/u8-chr +++ b/modules/unistr/u8-chr @@ -5,6 +5,7 @@ Files: lib/unistr/u8-chr.c Depends-on: +memchr unistr/base unistr/u8-uctomb