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

From: Martin Ågren <martin.agren@gmail.com>
Date: Jun 13, 2019, 19:42 UTC
Message-ID: <CAN0heSriaQV7zd4h8gfazi0dY_Dc5qLBWfJBtZGxOtm1+cgZqw@mail.gmail.com>
In-Reply-To: <f0059613-d3e4-a1e2-2c01-727579e069d2@web.de>

On Thu, 13 Jun 2019 at 19:54, René Scharfe <l.s.r@web.de> wrote:

Show 16 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.

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