X-Git-Url: http://erislabs.net/gitweb/?a=blobdiff_plain;f=lib%2Funistr%2Fu8-strchr.c;h=ea931a9153072c415981dc6fb23dd137060e5cde;hb=d462d9f08cc8fd534ccae14c878f9c7c18112237;hp=cce594cb4441aca2842c1aa39764836277e7c9ad;hpb=c02c2a767745cd9ae29179e5d9c788bd31d361c8;p=gnulib.git diff --git a/lib/unistr/u8-strchr.c b/lib/unistr/u8-strchr.c index cce594cb4..ea931a915 100644 --- a/lib/unistr/u8-strchr.c +++ b/lib/unistr/u8-strchr.c @@ -1,28 +1,27 @@ /* Search character in UTF-8 string. - Copyright (C) 1999, 2002, 2006 Free Software Foundation, Inc. + Copyright (C) 1999, 2002, 2006-2007, 2009-2012 Free Software Foundation, + Inc. Written by Bruno Haible , 2002. - This program is free software; you can redistribute it and/or modify it - under the terms of the GNU Library General Public License as published - by the Free Software Foundation; either version 2, or (at your option) - any later version. + This program is free software: you can redistribute it and/or modify it + under the terms of the GNU Lesser General Public License as published + by the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU - Library General Public License for more details. + Lesser General Public License for more details. - You should have received a copy of the GNU Library General Public - License along with this program; if not, write to the Free Software - Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, - USA. */ + You should have received a copy of the GNU Lesser General Public License + along with this program. If not, see . */ #include /* Specification. */ #include "unistr.h" -#include "ucs4-utf8.h" +#include uint8_t * u8_strchr (const uint8_t *s, ucs4_t uc) @@ -33,72 +32,209 @@ u8_strchr (const uint8_t *s, ucs4_t uc) { uint8_t c0 = uc; - for (;; s++) - { - if (*s == c0) - break; - if (*s == 0) - goto notfound; - } - return (uint8_t *) s; + if (false) + { + /* Unoptimized code. */ + for (;;) + { + uint8_t s0 = *s; + if (s0 == c0) + return (uint8_t *) s; + s++; + if (s0 == 0) + break; + } + } + else + { + /* Optimized code. + strchr() is often so well optimized, that it's worth the + added function call. */ + return (uint8_t *) strchr ((const char *) s, c0); + } } 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)) { case 2: - if (*s == 0) - goto notfound; - { - uint8_t c0 = c[0]; - uint8_t c1 = c[1]; + if (*s == 0 || s[1] == 0) + break; + { + uint8_t c0 = c[0]; + uint8_t c1 = c[1]; + /* Search for { c0, c1 }. */ + uint8_t s1 = s[1]; - for (;; s++) - { - if (s[1] == 0) - goto notfound; - if (*s == c0 && s[1] == c1) - break; - } - return (uint8_t *) s; - } + 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 + { + if (s1 == c0) + goto case2_skip1; + else + /* Skip the search at s + 1, because s[1] != c0. */ + goto case2_skip2; + } + case2_skip2: + s++; + s1 = s[1]; + if (s[1] == 0) + break; + case2_skip1: + s++; + s1 = s[1]; + if (s[1] == 0) + break; + } + } + break; case 3: - if (*s == 0 || s[1] == 0) - goto notfound; - { - uint8_t c0 = c[0]; - uint8_t c1 = c[1]; - uint8_t c2 = c[2]; + if (*s == 0 || s[1] == 0 || s[2] == 0) + break; + { + 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 (;; s++) - { - if (s[2] == 0) - goto notfound; - if (*s == c0 && s[1] == c1 && s[2] == c2) - break; - } - return (uint8_t *) s; - } + 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: + 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: + 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) + break; + } + } + break; case 4: - if (*s == 0 || s[1] == 0 || s[2] == 0) - goto notfound; - { - uint8_t c0 = c[0]; - uint8_t c1 = c[1]; - uint8_t c2 = c[2]; - uint8_t c3 = c[3]; + if (*s == 0 || s[1] == 0 || s[2] == 0 || s[3] == 0) + break; + { + uint8_t c0 = c[0]; + 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 (;; s++) - { - if (s[3] == 0) - goto notfound; - if (*s == c0 && s[1] == c1 && s[2] == c2 && s[3] == c3) - break; - } - return (uint8_t *) s; - } + 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: + 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: + 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) + break; + } + } + break; } -notfound: + return NULL; }