Re: [PATCH] cleanup: fix possible overflow errors in binary search, part 2

["Martin Ågren" <martin.agren@gmail.com>]

On Thu, 13 Jun 2019 at 19:54, René Scharfe <l.s.r@web.de> wrote:
>
> 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.

Right, with "safe", one might mean something like "no undefined behavior
due to shifting a signed value with the high bit set". Especially since
we're worrying about overflows, we're obviously having large values in
mind, so we're right to consider the sign bit. But, we're fine as you
note.  Because we subtract, and `last` doesn't have its sign bit set,
and `first` is non-negative and not greater than `last`, the sign bit of
`(last - first)` is always zero.

So all is well. But maybe we should write `(last - first) / 2` anyway.
We could then drop the extra parenthesis, and we would keep future
readers (and static analysis?) from wondering whether we might ever be
shifting a signed value with the sign bit set. A few spots fewer to
audit in the future...

Martin