strspn() & strcspn() speed improvements

My versions of strspn() & strcspn() use faster and clear algorithm. Below I provide simple test application, which compares speed and results of old strspn() with new one & unified diff in the bottom. ===============cut================== #include <stdio.h> #include <string.h> #include <time.h> /* for _rdtsc() */ #define S1_LEN 1024 /* length of test string */ #define S2_LEN 256 /* length of mask. Maximum is 265 */ #define PHPAPI PHPAPI size_t php_strspn_new(char *s1, char *s2, char *s1_end, char *s2_end) { unsigned char *p1, *p2; char char_table[256]; if (s1 == s1_end || s2 == s2_end) { /* there is no chars in string [s1] or in the mask [s2] */ return 0; } /* create a char table from mask [s2] */ memset(char_table, 0, 256); p1 = (unsigned char *) s2; p2 = (unsigned char *) s2_end; while (p1 < p2) { char_table[*p1++] = 1; } /* compute the length of the initial segment of string [s1] which consists entirely of characters in mask [s2] */ p1 = (unsigned char *) s1; p2 = (unsigned char *) s1_end; while (p1 < p2 && char_table[*p1++]) { /* empty cycle */ } if (char_table[*(--p1)]) { p1++; } return ((char *)p1 - s1); } PHPAPI size_t php_strspn_old(char *s1, char *s2, char *s1_end, char *s2_end) {

    register const char *p = s1, *spanp;
    register char c = *p;

cont:

    for (spanp = s2; p != s1_end && spanp != s2_end;)
        if (*spanp++ == c) {
            c = *(++p);
            goto cont;
        }
    return (p - s1);

} int main(int argc,char *argv[]) { char s1[S1_LEN], s2[S2_LEN], *s1_end = s1 + S1_LEN, *s2_end = s2 + S2_LEN; size_t n, i; unsigned long long t; memset(s1, S2_LEN - 1, S1_LEN); /* create test string */ for (i = 0; i < S2_LEN; i++) s2[i] = i; /* create test mask */ t = _rdtsc(); n = php_strspn_old(s1, s2, s1_end, s2_end); printf("Old strspn time=%lld, result=%d\n", _rdtsc() - t, n); t = _rdtsc(); n = php_strspn_new(s1, s2, s1_end, s2_end); printf("New strspn time=%lld, result=%d\n", _rdtsc() - t, n);

    return 0;

} ===============cut================== unified diff ==========cut==========

--- string.c    Thu May 13 20:44:32 2004

+++ string_strspn.c Tue Jun 15 15:22:26 2004 @@ -1296,16 +1296,36 @@ */ PHPAPI size_t php_strspn(char *s1, char *s2, char *s1_end, char *s2_end) { - register const char *p = s1, *spanp; - register char c = *p;

+    unsigned char *p1, *p2;
+    char char_table[256];

-cont: - for (spanp = s2; p != s1_end && spanp != s2_end;)

-       if (*spanp++ == c) {
-           c = *(++p);
-           goto cont;
+    /* handling some trivial cases */
+    if (s1 == s1_end || s2 == s2_end) {
+        /* there is no chars in string [s1] or in the mask [s2] */
+        return 0;
+    }

+

+    /* create a char table from mask [s2] */
+    memset(char_table, 0, 256);
+    p1 = (unsigned char *) s2;
+    p2 = (unsigned char *) s2_end;
+    while (p1 < p2) {
+        char_table[*p1++] = 1;
+    }

+

+    /* compute the length of the initial segment of string [s1] which
+       consists entirely of characters in mask [s2]
+    */
+    p1 = (unsigned char *) s1;
+    p2 = (unsigned char *) s1_end;
+    while (p1 < p2 && char_table[*p1++]) {
+        /* empty cycle */
        }

- return (p - s1);

+    if (char_table[*(--p1)]) {
+        p1++;
+    }

+

+    return ((char *)p1 - s1);

} /* }}} */ @@ -1313,18 +1333,40 @@ */ PHPAPI size_t php_strcspn(char *s1, char *s2, char *s1_end, char *s2_end) { - register const char *p, *spanp; - register char c = *s1;

+    unsigned char *p1, *p2;
+    char char_table[256];

- for (p = s1;;) {

-       spanp = s2;
-       do {
-           if (*spanp == c || p == s1_end)
-               return p - s1;
-       } while (spanp++ < s2_end);
-       c = *++p;
+    /* handling some trivial cases */
+    if (s2 == s2_end) {
+        /* empty mask [s2] */
+        return s1_end - s1;
    }

- /* NOTREACHED */

+    if (s1 == s1_end) {
+        /* there is no chars in string [s1] */
+        return 0;
+    }

+

+    /* create a char table from mask [s2] */
+    memset(char_table, 1, 256);
+    p1 = (unsigned char *) s2;
+    p2 = (unsigned char *) s2_end;
+    while (p1 < p2) {
+        char_table[*p1++] = 0;
+    }

+

+    /* compute the length of the initial segment of string [s1] which
+       does NOT contain any of the characters in mask [s2]
+    */
+    p1 = (unsigned char *) s1;
+    p2 = (unsigned char *) s1_end;
+    while (p1 < p2 && char_table[*p1++]) {
+        /* empty cycle */
+    }
+    if (char_table[*(--p1)]) {
+        p1++;
+    }

+

+    return ((char *)p1 - s1);

} /* }}} */ ==========cut========== -- Using Opera's revolutionary e-mail client: http://www.opera.com/m2/