From 4dae774893615c1d78f7ddc46a2b20ab548b302a Mon Sep 17 00:00:00 2001 From: Alexandre Julliard Date: Sun, 23 May 2010 22:25:06 +0200 Subject: [PATCH] ntdll: Reimplement bsearch to avoid redundant and possibly out of bounds comparisons. --- dlls/ntdll/misc.c | 25 +++++++++---------------- 1 file changed, 9 insertions(+), 16 deletions(-) diff --git a/dlls/ntdll/misc.c b/dlls/ntdll/misc.c index eedef6543c9..621848ee021 100644 --- a/dlls/ntdll/misc.c +++ b/dlls/ntdll/misc.c @@ -302,27 +302,20 @@ void * __cdecl NTDLL_bsearch( const void *key, const void *base, size_t nmemb, size_t size, int (__cdecl *compar)(const void *, const void *) ) { - int begin, end, cursor; - - begin = 0; - end = nmemb-1; - while (1) { - int ret; - cursor = (end-begin)/2+begin; - ret = compar(key,(char*)base+(cursor*size)); + ssize_t min = 0; + ssize_t max = nmemb - 1; + + while (min <= max) + { + ssize_t cursor = (min + max) / 2; + int ret = compar(key,(const char *)base+(cursor*size)); if (!ret) return (char*)base+(cursor*size); if (ret < 0) - end = cursor; + max = cursor - 1; else - begin = cursor; - if ((end-begin)<=1) - break; + min = cursor + 1; } - if (!compar(key,(char*)base+(begin*size))) - return (char*)base+(begin*size); - if (!compar(key,(char*)base+(end*size))) - return (char*)base+(end*size); return NULL; } -- 2.11.4.GIT