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
