[PATCH JGIT] Computation of average could overflow
- From
Sohn, Matthias <matthias.sohn@sap.com>
- Date
- Apr 27, 2009, 23:02 UTC
- Message-ID
- <366BBB1215D0AB4B8A153AF047A2878002FCE7E7@dewdfe18.wdf.sap.corp>
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 that 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-i t-nearly.html).
Signed-off-by: Matthias Sohn <matthias.sohn@sap.com> --- .../src/org/spearce/jgit/dircache/DirCache.java | 2 +- .../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 58da014..fa906fa 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 @@ int findEntry(final byte[] p, final int pLen) { 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 0ecd04d..ff9e666 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 @@ private static final int binarySearch(final TreeEntry[] entries, 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)
-- 1.6.2.2.1669.g7eaf8