From: Derrick Stolee Date: Fri, 06 Oct 2017 14:41:12 GMT Subject: Re: [PATCH] cleanup: fix possible overflow errors in binary search Message-ID: In-Reply-To: <20171006141820.6vd3qt6iosxcgebm@sigill.intra.peff.net> 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: >> >> mid = min + (max - min) / 2; > Great, thank you for picking this up! > >> The included changes were found using the following two greps: >> >> grep "/ 2;" *.c >> grep "/ 2;" */*.c >> grep "/2;" */*.c > You can use[1]: > > git grep '/ 2;' '*.c' > > to have Git expand the wildcard. That catches a few extra cases in > compat/regex/*.c. Even though it's imported code, it might be > nice to cover those, too (since it's a possible bug, and also as a good > example). > > [1] I'd actually write: > > git grep '/ *2;' '*.c' > > to do it all in one grep. :) Thanks for the grep lesson! I knew there would be a simpler way to do what I wanted. >> --- >> builtin/index-pack.c | 4 ++-- >> builtin/pack-objects.c | 2 +- >> builtin/unpack-objects.c | 2 +- >> cache-tree.c | 2 +- >> packfile.c | 2 +- >> sha1-lookup.c | 2 +- >> sha1_name.c | 2 +- >> string-list.c | 2 +- >> utf8.c | 2 +- >> xdiff/xpatience.c | 2 +- >> 10 files changed, 11 insertions(+), 11 deletions(-) > These all look good to me (really the only way the conversion could be > bad is if "min" was higher than "max", and each case is just inside a > loop condition which makes sure that is not the case). > > -Peff I thought this should be simple enough. When we are all happy with the idea of this cleanup, I'll re-roll with the missed examples. Thanks, -Stolee