Am 13.06.19 um 21:42 schrieb Martin Ågren: > On Thu, 13 Jun 2019 at 19:54, René Scharfe <l.s.r@xxxxxx> 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... Yes, thought about that. When I saw Clang 8 emitting extra opcodes for handling the sign for the version with division I decided to restrict the patch to just do overflow prevention and leave the right shifts in place.. René
