From: Bruno Haible Date: Sat, 31 Jul 2010 19:32:47 +0000 (+0200) Subject: unistr/u8-chr, unistr/u8-strchr: Optimize and add comments. X-Git-Tag: v0.1~3965 X-Git-Url: http://erislabs.net/gitweb/?p=gnulib.git;a=commitdiff_plain;h=1027106b1677606f93b8f0f8270a5f0cc15e6fce unistr/u8-chr, unistr/u8-strchr: Optimize and add comments. --- diff --git a/ChangeLog b/ChangeLog index 8c83dff08..dbf336db0 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,5 +1,11 @@ 2010-07-31 Bruno Haible + unistr/u8-chr, unistr/u8-strchr: Optimize and add comments. + * lib/unistr/u8-chr.c (u8_chr): Add comments. Remove a useless test at + the beginning of the loop. + * lib/unistr/u8-strchr.c (u8_strchr): Add comments. Don't fall through + cases in 'switch' statement. + unistr/u8-strchr: Fix several bugs. * lib/unistr/u8-strchr.c (u8_strchr): Don't search beyond the end of the string. When not found, return NULL, not a pointer near the end. diff --git a/lib/unistr/u8-chr.c b/lib/unistr/u8-chr.c index c266fef25..ecdaf6306 100644 --- a/lib/unistr/u8-chr.c +++ b/lib/unistr/u8-chr.c @@ -70,14 +70,17 @@ u8_chr (const uint8_t *s, size_t n, ucs4_t uc) uint8_t c1 = c[1]; const uint8_t *end = s + n - 1; - while (s < end) + 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 @@ -85,9 +88,11 @@ u8_chr (const uint8_t *s, size_t n, ucs4_t uc) if (s1 == c0) s++; else + /* Skip the search at s + 1, because s[1] != c0. */ s += 2; } } + while (s < end); break; } @@ -104,14 +109,19 @@ u8_chr (const uint8_t *s, size_t n, ucs4_t uc) else skip = 3; - while (s < end) + 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 @@ -119,11 +129,15 @@ u8_chr (const uint8_t *s, size_t n, ucs4_t uc) 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; } @@ -143,14 +157,21 @@ u8_chr (const uint8_t *s, size_t n, ucs4_t uc) else skip = 4; - while (s < end) + 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 @@ -158,13 +179,20 @@ u8_chr (const uint8_t *s, size_t n, ucs4_t uc) 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; } } diff --git a/lib/unistr/u8-strchr.c b/lib/unistr/u8-strchr.c index a67b8f322..bcfbb6008 100644 --- a/lib/unistr/u8-strchr.c +++ b/lib/unistr/u8-strchr.c @@ -67,15 +67,19 @@ u8_strchr (const uint8_t *s, ucs4_t uc) { uint8_t c0 = c[0]; uint8_t c1 = c[1]; + /* Search for { c0, c1 }. */ uint8_t s1 = s[1]; for (;;) { + /* Here s[0] != 0, s[1] != 0. + Test whether s[0..1] == { c0, c1 }. */ if (s1 == c1) { if (*s == c0) return (uint8_t *) s; else + /* Skip the search at s + 1, because s[1] = c1 < c0. */ goto case2_skip2; } else @@ -83,6 +87,7 @@ u8_strchr (const uint8_t *s, ucs4_t uc) if (s1 == c0) goto case2_skip1; else + /* Skip the search at s + 1, because s[1] != c0. */ goto case2_skip2; } case2_skip2: @@ -106,26 +111,36 @@ u8_strchr (const uint8_t *s, ucs4_t uc) uint8_t c0 = c[0]; uint8_t c1 = c[1]; uint8_t c2 = c[2]; + /* Search for { c0, c1, c2 }. */ uint8_t s2 = s[2]; for (;;) { + /* Here s[0] != 0, s[1] != 0, s[2] != 0. + Test whether s[0..2] == { c0, c1, c2 }. */ if (s2 == c2) { if (s[1] == c1 && *s == c0) return (uint8_t *) s; - else if (c2 == c1) - goto case3_skip1; else - goto case3_skip3; + /* 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. */ + if (c2 == c1) + goto case3_skip1; + else + goto case3_skip3; } else { if (s2 == c1) goto case3_skip1; else if (s2 == c0) + /* Skip the search at s + 1, because s[2] != c1. */ goto case3_skip2; else + /* Skip the search at s + 1, because s[2] != c1. + Skip the search at s + 2, because s[2] != c0. */ goto case3_skip3; } case3_skip3: @@ -145,6 +160,7 @@ u8_strchr (const uint8_t *s, ucs4_t uc) break; } } + break; case 4: if (*s == 0 || s[1] == 0 || s[2] == 0 || s[3] == 0) @@ -154,30 +170,45 @@ u8_strchr (const uint8_t *s, ucs4_t uc) uint8_t c1 = c[1]; uint8_t c2 = c[2]; uint8_t c3 = c[3]; + /* Search for { c0, c1, c2, c3 }. */ uint8_t s3 = s[3]; for (;;) { + /* Here s[0] != 0, s[1] != 0, s[2] != 0, s[3] != 0. + Test whether s[0..3] == { c0, c1, c2, c3 }. */ 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; + /* 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. */ + 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) + /* Skip the search at s + 1, because s[3] != c2. */ goto case4_skip2; else if (s3 == c0) + /* Skip the search at s + 1, because s[3] != c2. + Skip the search at s + 2, because s[3] != c1. */ goto case4_skip3; 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. */ goto case4_skip4; } case4_skip4: @@ -202,6 +233,7 @@ u8_strchr (const uint8_t *s, ucs4_t uc) break; } } + break; } return NULL;