From 19716b21a4255ecc7148b54ab2c78039c59f25bf Mon Sep 17 00:00:00 2001 From: Derrick Stolee Date: Sun, 8 Oct 2017 14:29:37 -0400 Subject: cleanup: fix possible overflow errors in binary search 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. Signed-off-by: Derrick Stolee Reviewed-by: Jeff King Signed-off-by: Junio C Hamano --- compat/regex/regex_internal.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'compat/regex/regex_internal.c') diff --git a/compat/regex/regex_internal.c b/compat/regex/regex_internal.c index d4121f2f4f..98342b8316 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) @@ -1394,7 +1394,7 @@ re_node_set_contains (const re_node_set *set, int elem) right = set->nelem - 1; while (idx < right) { - mid = (idx + right) / 2; + mid = idx + (right - idx) / 2; if (set->elems[mid] < elem) idx = mid + 1; else -- cgit 1.2.3-korg