Re: [PATCH] cleanup: fix possible overflow errors in binary search, part 2
On 6/13/2019 1:51 PM, René Scharfe wrote:
Show 22 quoted lines
> Calculating the sum of two array indexes to find the midpoint between
> them can overflow, i.e. code like this is unsafe for big arrays:
>
> mid = (first + last) >> 1;
>
> Make sure the intermediate value stays within the boundaries instead,
> like this:
>
> mid = first + ((last - first) >> 1);
>
> The loop condition of the binary search makes sure that 'last' is
> always greater than 'first', so this is safe as long as 'first' is
> not negative. And that can be verified easily using the pre-context
> of each change, except for name-hash.c, so add an assertion to that
> effect there.
>
> The unsafe calculations were found with:
>
> git grep '(.*+.*) *>> *1'
>
> This is a continuation of 19716b21a4 (cleanup: fix possible overflow
> errors in binary search, 2017-10-08).
Thank you for finding these additional examples!
LGTM. Pretty easy to see this is correct.
-Stolee