GNU bug report logs - #2844
infinite loop in boyer_moore()

Previous Next

Full log

Message #22 received at 2844 <at> emacsbugs.donarmstrong.com (full text, mbox):

From: Chong Yidong <cyd <at> stupidchicken.com>
To: emacs-devel <at> gnu.org
Cc: 2844 <at> debbugs.gnu.org
Subject: Re: infinite loop in boyer_moore()
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?

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.