Re: infinite loop in boyer_moore()

Re: infinite loop in boyer_moore()

[Chong Yidong]

> 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?

Re: infinite loop in boyer_moore()

[Chong Yidong]

Ping.  Anyone have an opinion?

>> 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?

Re: infinite loop in boyer_moore()

[Andreas Schwab]

Chong Yidong <cyd@stupidchicken.com> writes:

> Ping.  Anyone have an opinion?

I've now checked in a fix.

Andreas.

-- 
Andreas Schwab, schwab@linux-m68k.org
GPG Key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
"And now for something completely different."

Re: infinite loop in boyer_moore()

[Chong Yidong]

Andreas Schwab <schwab@linux-m68k.org> writes:

>> Ping.  Anyone have an opinion?
>
> I've now checked in a fix.
>
> Andreas.

Thanks.