Mailing-List: contact dev-help@httpd.apache.org; run by ezmlm
Precedence: bulk
Reply-To: dev@httpd.apache.org
Subject: Re: [PATCH] Take 3 of mod_include patch...
From: Ian Holsman <ianh@cnet.com>
To: dev@httpd.apache.org
In-Reply-To: <20010905191137.B2007@ebuilt.com>
References: <20010905164453.N10838@ebuilt.com>
	<3B96D585.3010201@pacbell.net>  <20010905191137.B2007@ebuilt.com>
Content-Type: text/plain
Content-Transfer-Encoding: 7bit
Date: 06 Sep 2001 10:25:28 -0700
Message-Id: <999797128.28555.118.camel@griffon.cnet.com>
Mime-Version: 1.0

On Wed, 2001-09-05 at 19:11, Justin Erenkrantz wrote:
> On Wed, Sep 05, 2001 at 06:46:45PM -0700, Brian Pane wrote:
> > Justin Erenkrantz wrote:
> > [...]

getting back to the original patch
to find_start_sequence.

does anyone have any comments on this?
I'm seeing lower CPU utilization when using this.
and the edge cases are handled by the old 'slower' method
..Ian
> > 
> > >+/* 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
-- 
Ian Holsman          IanH@cnet.com
Performance Measurement & Analysis
CNET Networks   -   (415) 364-8608