[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[PATCH v2 5/5] unistr/u8-chr, unistr/u8-strchr: use Boyer-Moore like alg
From: |
bonzini |
Subject: |
[PATCH v2 5/5] unistr/u8-chr, unistr/u8-strchr: use Boyer-Moore like algorithm. |
Date: |
Fri, 23 Jul 2010 08:53:52 +0200 |
From: Paolo Bonzini <address@hidden>
* lib/unistr/u8-chr.c, lib/unistr/u8-strchr.c: Add Boyer-Moore like operation.
* modules/unistr/u8-chr: Depend on memchr.
---
lib/unistr/u8-chr.c | 181 +++++++++++++++++++++++++++++++++++-------------
lib/unistr/u8-strchr.c | 136 ++++++++++++++++++++++++++++++------
modules/unistr/u8-chr | 1 +
3 files changed, 247 insertions(+), 71 deletions(-)
diff --git a/lib/unistr/u8-chr.c b/lib/unistr/u8-chr.c
index 435d1be..657d190 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 character using multi-byte
+ jumps, and matches back from there.
+
+ Instead of the table, we compare the candidate last character
+ 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 character 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 3ee2465..cb65500 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 character 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 6f5de6c..a337b0f 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
--
1.7.1
- [PATCH v2 0/5] Speed up uNN_chr and uNN_strchr with Boyer-Moore algorithm, bonzini, 2010/07/23
- [PATCH v2 1/5] unistr/u*-chr: prepare for multibyte tests, bonzini, 2010/07/23
- [PATCH v2 2/5] unistr/u*-chr: test multibyte sequences, bonzini, 2010/07/23
- [PATCH v2 3/5] unistr/u*-chr: test multibyte sequences more, bonzini, 2010/07/23
- [PATCH v2 4/5] unistr/u*-strchr: add tests, bonzini, 2010/07/23
- [PATCH v2 5/5] unistr/u8-chr, unistr/u8-strchr: use Boyer-Moore like algorithm.,
bonzini <=
- Re: [PATCH v2 0/5] Speed up uNN_chr and uNN_strchr with Boyer-Moore algorithm, Bruno Haible, 2010/07/23
- Re: [PATCH v2 0/5] Speed up uNN_chr and uNN_strchr with Boyer-Moore algorithm, Paolo Bonzini, 2010/07/23
- Re: [PATCH v2 0/5] Speed up uNN_chr and uNN_strchr with Boyer-Moore algorithm, Pádraig Brady, 2010/07/27
- Re: [PATCH v2 0/5] Speed up uNN_chr and uNN_strchr with Boyer-Moore algorithm, Paolo Bonzini, 2010/07/27
- Re: [PATCH v2 0/5] Speed up uNN_chr and uNN_strchr with Boyer-Moore algorithm, Pádraig Brady, 2010/07/27
- Re: [PATCH v2 0/5] Speed up uNN_chr and uNN_strchr with Boyer-Moore algorithm, Paolo Bonzini, 2010/07/27
- Re: ucs4_t type, Bruno Haible, 2010/07/28
- Re: [PATCH v2 0/5] Speed up uNN_chr and uNN_strchr with Boyer-Moore algorithm, Bruno Haible, 2010/07/28
- Re: [PATCH v2 0/5] Speed up uNN_chr and uNN_strchr with Boyer-Moore algorithm, Pádraig Brady, 2010/07/29
- Re: [PATCH v2 0/5] Speed up uNN_chr and uNN_strchr with Boyer-Moore algorithm, Paolo Bonzini, 2010/07/29