Re: Boyer Moore overflow patch

[Charles Levert]

* On Saturday 2005-07-16 at 14:43:10 +0100, Julian Foad wrote:
> Charles Levert wrote:
> >I think the only pending patch that's affected
> >is one you were working on to fix a bug.
> 
> Sorry to be so forgetful, but could you post the URL or tracker number of 
> the particular bug that you are talking about?

Boyer Moore overflow patch:
   <http://lists.gnu.org/archive/html/bug-grep/2005-06/msg00039.html>
   <http://lists.gnu.org/archive/html/bug-grep/2005-06/msg00040.html>
   <http://lists.gnu.org/archive/html/bug-grep/2005-06/msg00048.html>

The following patch is all that remains to be
done in this file.  Other issues mentioned in the
first message above have already been dealt with.


> >--- src/kwset.c      2005-07-04 01:14:37 -0400
> >+++ src/kwset.c      2005-07-04 04:50:38 -0400
> >@@ -404,7 +404,13 @@ kwsprep (kwset_t kws)
> >     }
> >       /* Build the Boyer Moore delta.  Boy that's easy compared to CW. */
> >       for (i = 0; i < kwset->mind; ++i)
> >-    delta[U(kwset->target[i])] = kwset->mind - (i + 1);
> >+    {
> >+      int d = kwset->mind - (i + 1);
> >+
> >+      if (UCHAR_MAX < d)
> >+        d = UCHAR_MAX;
> >+      delta[U(kwset->target[i])] = d;
> >+    }
> >       /* Find the minimal delta2 shift that we might make after
> >      a backwards match has failed. */
> >       c = kwset->target[kwset->mind - 1];

Computing d first, as opposed to using a MIN()
macro straight out, avoids relying on the
compiler's optimizer to recognize and not compute
"kwset->mind - (i + 1)" twice.


> >along with tests that would be surrounded by a
> >
> >   for mode in F G E
> >
> >loop in "tests/foad1.sh".
> 
> Please could you write those tests?

# Test for Boyer-Moore bugs.  Thanks to Steve Summit for reporting the bug
# and providing a test case which inspired these.
b17='bbbbbbbbbbbbbbbbb'
b85="$b17$b17$b17$b17$b17"
b255="$b85$b85$b85"
x16='xxxxxxxxxxxxxxxx'
x64="$x16$x16$x16$x16"
x256="$x64$x64$x64$x64"
bm="cbbba${b255}c"
bt="${x256}${bm}${x16}xx/"
for mode in F G E; do
  grep_test "a${b255}a/"  ''     "a${b255}b"  -$mode
  grep_test "$bt"         "$bt"  "$bm"        -$mode
done


> In another email you wrote:
> >(I still don't understand the second test case,

Here are the original tests (which differ by
their terminating slash).

First test:
   grep_test "a${b255}a" "" "a${b255}b"
Second test:
   grep_test "${x256}${bm}${x16}xx" "${x256}${bm}${x16}xx/" "$bm"

It's just that I haven't figured out for myself
what's the buggy behavior that the second test
is after (and that the first one isn't already
covering).