[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[PATCH 5/5] unistr/u8-chr: use Boyer-Moore like algorithm.
From: |
bonzini |
Subject: |
[PATCH 5/5] unistr/u8-chr: use Boyer-Moore like algorithm. |
Date: |
Tue, 20 Jul 2010 17:26:29 +0200 |
From: Paolo Bonzini <address@hidden>
* lib/unistr/u8-chr.c: Add Boyer-Moore like optimization.
---
lib/unistr/u8-chr.c | 129 ++++++++++++++++++++++++++++++++---------------
1 files changed, 88 insertions(+), 41 deletions(-)
diff --git a/lib/unistr/u8-chr.c b/lib/unistr/u8-chr.c
index 435d1be..6ad6fdb 100644
--- a/lib/unistr/u8-chr.c
+++ b/lib/unistr/u8-chr.c
@@ -30,59 +30,106 @@ u8_chr (const uint8_t *s, size_t n, ucs4_t uc)
{
uint8_t c0 = uc;
- for (; n > 0; s++, n--)
- {
- if (*s == c0)
- return (uint8_t *) s;
- }
+ return memchr (s, c0, n);
}
else
switch (u8_uctomb_aux (c, uc, 6))
{
case 2:
- if (n > 1)
- {
- uint8_t c0 = c[0];
- uint8_t c1 = c[1];
+ {
+ uint8_t c0 = c[0];
+ uint8_t c1 = c[1];
+ const uint8_t *end = s + n - 1;
- for (n--; n > 0; s++, n--)
- {
- if (*s == c0 && s[1] == c1)
- return (uint8_t *) s;
- }
- }
- break;
+ 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];
+ {
+ uint8_t c0 = c[0];
+ uint8_t c1 = c[1];
+ uint8_t c2 = c[2];
+ const uint8_t *end = s + n - 2;
- for (n -= 2; n > 0; s++, n--)
- {
- if (*s == c0 && s[1] == c1 && s[2] == c2)
- return (uint8_t *) s;
- }
- }
- break;
+ while (s < end)
+ {
+ uint8_t s2 = s[2];
+ if (s2 == c2)
+ {
+ if (s[1] == c1 && *s == c0)
+ return (uint8_t *) s;
+ else if (s2 == c1)
+ s++;
+ else
+ s += 3;
+ }
+ 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];
+ {
+ 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;
- for (n -= 3; n > 0; s++, n--)
- {
- if (*s == c0 && s[1] == c1 && s[2] == c2 && s[3] == c3)
- return (uint8_t *) s;
- }
- }
- break;
+ 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 if (s3 == c2)
+ s++;
+ else if (s3 == c1)
+ s += 2;
+ else
+ s += 4;
+ }
+ else
+ {
+ if (s3 == c2)
+ s++;
+ else if (s3 == c1)
+ s += 2;
+ else if (s3 == c0)
+ s += 3;
+ else
+ s += 4;
+ }
+ }
+ break;
+ }
}
return NULL;
}
--
1.7.1
- [PATCH 0/5] unistr/u*-chr, unistr/u*-strchr: improve test coverage, optimize, bonzini, 2010/07/20
- [PATCH 1/5] unistr/u*-strchr: add tests, bonzini, 2010/07/20
- [PATCH 2/5] unistr/u*-chr, unistr/u*-strchr: prepare for multibyte tests, bonzini, 2010/07/20
- [PATCH 4/5] unistr/u*-chr, unistr/u*-strchr: test multibyte sequences more, bonzini, 2010/07/20
- [PATCH 3/5] unistr/u*-chr, unistr/u*-strchr: test multibyte sequences, bonzini, 2010/07/20
- [PATCH 5/5] unistr/u8-chr: use Boyer-Moore like algorithm.,
bonzini <=
- Re: [PATCH 0/5] unistr/u*-chr, unistr/u*-strchr: improve test coverage, optimize, Bruno Haible, 2010/07/20