Re: [PATCH v2] cleanup: fix possible overflow errors in binary search
From: Jeff King <hidden>
Date: 2017-10-09 13:33:26
On Sun, Oct 08, 2017 at 02:29:37PM -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; This translation is safe since the operation occurs inside a loop conditioned on "min < max". The included changes were found using the following git grep: git grep '/ *2;' '*.c' Making this cleanup will prevent future review friction when a new binary search is contructed based on existing code.
Thanks, this version looks good to me.
quoted hunk ↗ jump to hunk
diff --git a/compat/regex/regex_internal.c b/compat/regex/regex_internal.c index d4121f2f4..98342b831 100644 --- a/compat/regex/regex_internal.c +++ b/compat/regex/regex_internal.c@@ -613,7 +613,7 @@ re_string_reconstruct (re_string_t *pstr, int idx, int eflags) int low = 0, high = pstr->valid_len, mid; do { - mid = (high + low) / 2; + mid = low + (high - low) / 2; if (pstr->offsets[mid] > offset) high = mid; else if (pstr->offsets[mid] < offset)
This one is a do-while, so it's less obvious that "high" is always more than "low" when entering the loop. But one assumes it is so, since the binary search wouldn't work otherwise. -Peff