From 1d99aaab8e364c6ad722437e43c77fd54e13b071 Mon Sep 17 00:00:00 2001 From: Matthias Sohn Date: Tue, 28 Apr 2009 01:02:55 +0200 Subject: [PATCH] Computation of average could overflow The code computes the average of two integers using either division or signed right shift, and then uses the result as the index of an array. If the values being averaged are very large, this can overflow (resulting in the computation of a negative average). Assuming that the result is intended to be nonnegative, you can use an unsigned right shift instead. In other words, rather than using (low+high)/2, use (low+high) >>> 1. This bug exists in many earlier implementations of binary search and merge sort. Martin Buchholz found and fixed it (http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6412541) in the JDK libraries, and Joshua Bloch widely publicized the bug pattern (http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html). Signed-off-by: Matthias Sohn Signed-off-by: Shawn O. Pearce --- org.spearce.jgit/src/org/spearce/jgit/dircache/DirCache.java | 2 +- org.spearce.jgit/src/org/spearce/jgit/lib/Tree.java | 2 +- 2 files changed, 2 insertions(+), 2 deletions(-) diff --git a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCache.java b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCache.java index 58da0142..fa906fa4 100644 --- a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCache.java +++ b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCache.java @@ -593,7 +593,7 @@ public class DirCache { int low = 0; int high = entryCnt; do { - int mid = (low + high) >> 1; + int mid = (low + high) >>> 1; final int cmp = cmp(p, pLen, sortedEntries[mid]); if (cmp < 0) high = mid; diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/Tree.java b/org.spearce.jgit/src/org/spearce/jgit/lib/Tree.java index 0ecd04d2..ff9e6661 100644 --- a/org.spearce.jgit/src/org/spearce/jgit/lib/Tree.java +++ b/org.spearce.jgit/src/org/spearce/jgit/lib/Tree.java @@ -136,7 +136,7 @@ public class Tree extends TreeEntry implements Treeish { int high = entries.length; int low = 0; do { - final int mid = (low + high) / 2; + final int mid = (low + high) >>> 1; final int cmp = compareNames(entries[mid].getNameUTF8(), nameUTF8, nameStart, nameEnd, TreeEntry.lastChar(entries[mid]), nameUTF8last); if (cmp < 0) -- 2.11.4.GIT