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
