Binary searches

php.internals

john

20 years ago
Attached is a patch which addresses array indices being out of bounds in pcre and libxmlrpc binary searches. John

Antony Dovgal

20 years ago
On 07.06.2006 03:06, john wrote:
> Attached is a patch which addresses array indices being out of bounds in > pcre and libxmlrpc binary searches.
Please elaborate. What exactly are you fixing and how to reproduce it?
> ------------------------------------------------------------------------ > > Index: ext/pcre/pcrelib/pcre_get.c > =================================================================== > RCS file: /repository/php-src/ext/pcre/pcrelib/pcre_get.c,v > retrieving revision 1.2 > diff -u -r1.2 pcre_get.c > --- ext/pcre/pcrelib/pcre_get.c 6 Mar 2006 21:34:07 -0000 1.2 > +++ ext/pcre/pcrelib/pcre_get.c 6 Jun 2006 22:59:42 -0000 > @@ -79,9 +79,10 @@ > return rc; > > bot = 0; > +int mid = 0; > while (top > bot) > { > - int mid = (top + bot) / 2; > + mid = ((unsigned) top + bot) >> 1; > uschar *entry = nametable + entrysize*mid; > int c = strcmp(stringname, (char *)(entry + 2)); > if (c == 0) return (entry[0] << 8) + entry[1]; > Index: ext/xmlrpc/libxmlrpc/queue.c > =================================================================== > RCS file: /repository/php-src/ext/xmlrpc/libxmlrpc/queue.c,v > retrieving revision 1.4 > diff -u -r1.4 queue.c > --- ext/xmlrpc/libxmlrpc/queue.c 5 Jul 2002 04:43:53 -0000 1.4 > +++ ext/xmlrpc/libxmlrpc/queue.c 6 Jun 2006 22:59:44 -0000 > @@ -859,7 +859,7 @@ > hi = q->size - 1; > > while(low <= hi) { > - mid = (low + hi) / 2; > + mid = ((unsigned) (low + high)) >> 1; > val = Comp(key, index[ mid ]); > > if(val < 0) > >
-- Wbr, Antony Dovgal

Sebastian Bergmann

20 years ago
Antony Dovgal wrote:
> Please elaborate. > What exactly are you fixing and how to reproduce it?
http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html
-- Sebastian Bergmann http://www.sebastian-bergmann.de/ GnuPG Key: 0xB85B5D69 / 27A7 2B14 09E4 98CD 6277 0E5B 6867 C514 B85B 5D69

Nuno Lopes

20 years ago
Yesterday some my colleagues were precisely discussing that issue.. I recommend you to submit the patches upstream (to both pcre and libxmlrpc authors) instead, as we prefer not to change bundled libraries (for maintenance sake). Nuno ----- Original Message -----