diff options
| author | Derrick Stolee <dstolee@microsoft.com> | 2017-10-08 14:29:37 -0400 |
|---|---|---|
| committer | Junio C Hamano <gitster@pobox.com> | 2017-10-10 08:57:24 +0900 |
| commit | 19716b21a4255ecc7148b54ab2c78039c59f25bf (patch) | |
| tree | 5f1cecbffc543c64e7c4c4f371d204424e1ce1bb /compat | |
| parent | 217f2767cbcb562872437eed4dec62e00846d90c (diff) | |
| download | git-19716b21a4255ecc7148b54ab2c78039c59f25bf.tar.gz | |
cleanup: fix possible overflow errors in binary searchds/avoid-overflow-in-midpoint-computation
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 <dstolee@microsoft.com>
Reviewed-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Diffstat (limited to 'compat')
| -rw-r--r-- | compat/regex/regex_internal.c | 4 | ||||
| -rw-r--r-- | compat/regex/regexec.c | 2 |
2 files changed, 3 insertions, 3 deletions
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 diff --git a/compat/regex/regexec.c b/compat/regex/regexec.c index 0a745d9c3b..6f2b48a78b 100644 --- a/compat/regex/regexec.c +++ b/compat/regex/regexec.c @@ -4284,7 +4284,7 @@ search_cur_bkref_entry (const re_match_context_t *mctx, int str_idx) last = right = mctx->nbkref_ents; for (left = 0; left < right;) { - mid = (left + right) / 2; + mid = left + (right - left) / 2; if (mctx->bkref_ents[mid].str_idx < str_idx) left = mid + 1; else |