[PATCH] cleanup: fix possible overflow errors in binary search

2017-10-06 Thread Derrick Stolee
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; The included changes were found using the following two greps: grep

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

2017-10-06 Thread Jeff King
On Fri, Oct 06, 2017 at 09:52:31AM -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;

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

2017-10-06 Thread Derrick Stolee
On 10/6/2017 10:18 AM, Jeff King wrote: On Fri, Oct 06, 2017 at 09:52:31AM -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:

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

2019-06-13 Thread René Scharfe
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);

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

2019-06-13 Thread Derrick Stolee
On 6/13/2019 1:51 PM, René Scharfe 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, > lik

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

2019-06-13 Thread Martin Ågren
On Thu, 13 Jun 2019 at 19:54, René Scharfe 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 ins

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

2019-06-13 Thread René Scharfe
Am 13.06.19 um 21:42 schrieb Martin Ågren: > On Thu, 13 Jun 2019 at 19:54, René Scharfe 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 th

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

2019-06-13 Thread Martin Ågren
On Thu, 13 Jun 2019 at 23:33, René Scharfe wrote: > > Am 13.06.19 um 21:42 schrieb Martin Ågren: > > On Thu, 13 Jun 2019 at 19:54, René Scharfe wrote: > >> Make sure the intermediate value stays within the boundaries instead, > >> like this: > >> > >> mid = first + ((last - first) >> 1);