Re: Binary searches

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