Subject: bug#2844: infinite loop in boyer_moore()

From: Chong Yidong <[email-masked]>
Date: Thu, 02 Apr 2009 18:26:38 -0400

> Gnus has been entering infinite loops for me while splitting mail.
> Today I got a chance to look into it.  The problem is in
> boyer_moore(), in search.c:

>     /* Use signed comparison if appropriate
>        to make cursor+infinity sure to be > p_limit.
>        Assuming that the buffer lies in a range of addresses
>        that are all "positive" (as ints) or all "negative",
>        either kind of comparison will work as long
>        as we don't step by infinity.  So pick the kind
>        that works when we do step by infinity.  */
>     if ((EMACS_INT) (p_limit + infinity) > (EMACS_INT) p_limit)
>       while ((EMACS_INT) cursor <= (EMACS_INT) p_limit)
>         cursor += BM_tab[*cursor];
>     else
>       while ((EMACS_UINT) cursor <= (EMACS_UINT) p_limit)
>         cursor += BM_tab[*cursor];

> it takes the signed (EMACS_INT) loop, but that fails because cursor is
> (unsigned char *) 0x7fffc440, whereas p_limit is (unsigned char *)
> 0x80001260.

> infinity, computed earlier in that function, is 0x37dac21, but I don't
> see how a positive value would have helped.  It seems to me that we
> have to check that we won't be crossing this boundary starting at
> cursor rather than p_limit, or maybe both.  I haven't thought much
> about it.

Checking with cursor as well as p_limit sounds about right to be, but I
am far from familiar with this part of the code.  Does anyone one this
list have an opinion?