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
