httpd-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Brian Pane <bp...@pacbell.net>
Subject Re: [PATCH] Take 3 of mod_include patch...
Date Thu, 06 Sep 2001 01:46:45 GMT
Justin Erenkrantz wrote:
[...]

>+/* Implements the BNDM search algorithm (as described above).
>+ *
>+ * n  - the pattern to search for
>+ * nl - length of the pattern to search for
>+ * h  - the string to look in
>+ * hl - length of the string to look for
>+ * t  - precompiled bndm structure against the pattern 
>+ *
>+ * Returns the count of character that is the first match or hl if no
>+ * match is found.
>+ */
>+static int bndm(const char *n, apr_size_t nl, const char *h, apr_size_t hl, 
>+                bndm_t *t)
>+{
>+    apr_size_t skip;
>+    const char *he, *p, *pi;
>+    unsigned int *T, x, d;
>+
>+    he = h + hl;
>+
>+    T = t->T;
>+    x = t->x << 1;
>+
>+    pi = h - 1; /* pi: p initial */
>+    p = pi + nl; /* compare window right to left. point to the first char */
>+
>+    do {
>+        skip = nl;
>+        d = x;
>+        do {
>+            d = (d >> 1) & T[(unsigned char) *p--];
>+            if ((d & 1)) {
>+                if (p != pi)
>+                    skip = p - pi;
>+                else
>+                    return p - h + 1;
>+            }
>+        } while (d > 1);
>+        p = (pi += skip) + nl; 
>+    } while (p < he);
>
If nl > hl (e.g., if the caller tries to search for a 5-byte pattern in
a 3-byte string), the first loop iteration will look at memory beyond
the end of the string.  Should this be a while loop instead of do-while?
(Or is the caller responsible for avoiding this case?)

--Brian




Mime
View raw message