httpd-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Justin Erenkrantz <jerenkra...@ebuilt.com>
Subject Re: [PATCH] Take 3 of mod_include patch...
Date Thu, 06 Sep 2001 02:11:37 GMT
On Wed, Sep 05, 2001 at 06:46:45PM -0700, Brian Pane wrote:
> 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?)

Good point.  I'll make it a while loop instead.  If we start out past
the end of h, we know we don't have a match.  For mod_include, the
edge cases should pick up if that is part of a tag spanning buckets.
-- justin


Mime
View raw message