Merge branch 'rs/avoid-overflow-in-midpoint-computation'

Code clean-up to avoid signed integer overlaps during binary search.

* rs/avoid-overflow-in-midpoint-computation:
cleanup: fix possible overflow errors in binary search, part 2

diff --git a/builtin/ls-files.c b/builtin/ls-files.c
index 7f83c9a6f26bd92e5e3832a8ea8d6ec44d5a5f5a..670e8fb93c9320686410cabb8938a106be8e8158 100644 (file)
--- a/builtin/ls-files.c
+++ b/builtin/ls-files.c
@@ -373,7 +373,7 @@ static void prune_index(struct index_state *istate,
        first = pos;
        last = istate->cache_nr;
        while (last > first) {
-               int next = (last + first) >> 1;
+               int next = first + ((last - first) >> 1);
                const struct cache_entry *ce = istate->cache[next];
                if (!strncmp(ce->name, prefix, prefixlen)) {
                        first = next+1;

diff --git a/diffcore-rename.c b/diffcore-rename.c
index 07bd34b63145e1dc179afebcc7af351c34c2ab07..6af92d5eba6584416d331c2f6e63bd7d403ca773 100644 (file)
--- a/diffcore-rename.c
+++ b/diffcore-rename.c
@@ -23,7 +23,7 @@ static int find_rename_dst(struct diff_filespec *two)
        first = 0;
        last = rename_dst_nr;
        while (last > first) {
-               int next = (last + first) >> 1;
+               int next = first + ((last - first) >> 1);
                struct diff_rename_dst *dst = &(rename_dst[next]);
                int cmp = strcmp(two->path, dst->two->path);
                if (!cmp)
@@ -83,7 +83,7 @@ static struct diff_rename_src *register_rename_src(struct diff_filepair *p)
        first = 0;
        last = rename_src_nr;
        while (last > first) {
-               int next = (last + first) >> 1;
+               int next = first + ((last - first) >> 1);
                struct diff_rename_src *src = &(rename_src[next]);
                int cmp = strcmp(one->path, src->p->one->path);
                if (!cmp)

diff --git a/dir.c b/dir.c
index ba4a51c296efcad9861ebfb4b318fbd5cb3025a4..d021c908e5d162cfd4d961ab11d16b1b9eb7124a 100644 (file)
--- a/dir.c
+++ b/dir.c
@@ -701,7 +701,7 @@ static struct untracked_cache_dir *lookup_untracked(struct untracked_cache *uc,
        first = 0;
        last = dir->dirs_nr;
        while (last > first) {
-               int cmp, next = (last + first) >> 1;
+               int cmp, next = first + ((last - first) >> 1);
                d = dir->dirs[next];
                cmp = strncmp(name, d->name, len);
                if (!cmp && strlen(d->name) > len)

diff --git a/name-hash.c b/name-hash.c
index b4861bc7b02a93bd5f3659098764f535bb1f51c1..695908609f40f9cbb3960162a311af5d452610e2 100644 (file)
--- a/name-hash.c
+++ b/name-hash.c
@@ -345,8 +345,9 @@ static int handle_range_dir(
        else {
                int begin = k_start;
                int end = k_end;
+               assert(begin >= 0);
                while (begin < end) {
-                       int mid = (begin + end) >> 1;
+                       int mid = begin + ((end - begin) >> 1);
                        int cmp = strncmp(istate->cache[mid]->name, prefix->buf, prefix->len);
                        if (cmp == 0) /* mid has same prefix; look in second part */
                                begin = mid + 1;

diff --git a/read-cache.c b/read-cache.c
index 4dd22f4f6eb60ffa8f7c31a535a14b16fb403e53..c701f7f8b81378104e2732e8bb132144ff82e8f5 100644 (file)
--- a/read-cache.c
+++ b/read-cache.c
@@ -549,7 +549,7 @@ static int index_name_stage_pos(const struct index_state *istate, const char *na
        first = 0;
        last = istate->cache_nr;
        while (last > first) {
-               int next = (last + first) >> 1;
+               int next = first + ((last - first) >> 1);
                struct cache_entry *ce = istate->cache[next];
                int cmp = cache_name_stage_compare(name, namelen, stage, ce->name, ce_namelen(ce), ce_stage(ce));
                if (!cmp)

diff --git a/sh-i18n--envsubst.c b/sh-i18n--envsubst.c
index cecfdd36c7e696dce6188aea3398fbe8857d798b..e7430b9aa8ecf136a7d625ee059822e1e1a74b26 100644 (file)
--- a/sh-i18n--envsubst.c
+++ b/sh-i18n--envsubst.c
@@ -249,7 +249,7 @@ sorted_string_list_member (const string_list_ty *slp, const char *s)
        {
          /* Here we know that if s is in the list, it is at an index j
             with j1 <= j < j2.  */
-         size_t j = (j1 + j2) >> 1;
+         size_t j = j1 + ((j2 - j1) >> 1);
          int result = strcmp (slp->item[j], s);
 
          if (result > 0)