Re: [PATCH v2] cleanup: fix possible overflow errors in binary search

[Jeff King <peff@peff.net>]

On Sun, Oct 08, 2017 at 02:29:37PM -0400, Derrick Stolee wrote:

> A common mistake when writing binary search is to allow possible
> integer overflow by using the simple average:
> 
> 	mid = (min + max) / 2;
> 
> Instead, use the overflow-safe version:
> 
> 	mid = min + (max - min) / 2;
> 
> This translation is safe since the operation occurs inside a loop
> conditioned on "min < max". The included changes were found using
> the following git grep:
> 
> 	git grep '/ *2;' '*.c'
> 
> Making this cleanup will prevent future review friction when a new
> binary search is contructed based on existing code.

Thanks, this version looks good to me.

> diff --git a/compat/regex/regex_internal.c b/compat/regex/regex_internal.c
> index d4121f2f4..98342b831 100644
> --- a/compat/regex/regex_internal.c
> +++ b/compat/regex/regex_internal.c
> @@ -613,7 +613,7 @@ re_string_reconstruct (re_string_t *pstr, int idx, int eflags)
>  	      int low = 0, high = pstr->valid_len, mid;
>  	      do
>  		{
> -		  mid = (high + low) / 2;
> +		  mid = low + (high - low) / 2;
>  		  if (pstr->offsets[mid] > offset)
>  		    high = mid;
>  		  else if (pstr->offsets[mid] < offset)

This one is a do-while, so it's less obvious that "high" is always more
than "low" when entering the loop. But one assumes it is so, since the
binary search wouldn't work otherwise.

-Peff