[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: infinite loop in boyer_moore()

From: Chong Yidong
Subject: Re: infinite loop in boyer_moore()
Date: Thu, 16 Apr 2009 00:51:45 -0400
User-agent: Gnus/5.13 (Gnus v5.13) Emacs/23.0.91 (gnu/linux)

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?

reply via email to

[Prev in Thread] Current Thread [Next in Thread]