Name: rmT116609 Date: 05/11/2004


FULL PRODUCT VERSION :
java version "1.5.0-beta"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.5.0-beta-b32c)
Java HotSpot(TM) Client VM (build 1.5.0-beta-b32c, mixed mode)


ADDITIONAL OS VERSION INFORMATION :
Linux freeway 2.4.21-4-686 #1 Sat Aug 2 23:27:25 EST 2003 i686 GNU/Linux


A DESCRIPTION OF THE PROBLEM :
java.util.Arrays.binarySearch() will throw an ArrayIndexOutOfBoundsException if the array
is large. This is caused by overflow in the calculation:

           int mid = (low + high) >> 1;

The correct calculation uses unsigned shift:

           int mid = (low + high) >>> 1;

There are similar problems in Collections, and TreeMap also includes the faulty calculation

           int mid = (lo + hi) / 2;

There may be others.


STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
Run the included code example.

EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
The code should print

index = 1099999999

ACTUAL -
The code printed

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1064671149
        at java.util.Arrays.binarySearch(Arrays.java:1509)
        at infinitum.tom.Search.main(Search.java:7)


ERROR MESSAGES/STACK TRACES THAT OCCUR :
$ /jdk/j2sdk1.5.0/bin/java -Xmx1200m -server Search
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1064671149
        at java.util.Arrays.binarySearch(Arrays.java:1509)
        at infinitum.tom.Search.main(Search.java:7)


REPRODUCIBILITY :
This bug can be reproduced rarely.

---------- BEGIN SOURCE ----------
class Search {
    public static void main (String[] args) {
        byte[] b = new byte[1100000000];
        b[b.length - 1] = 1;
        int index = java.util.Arrays.binarySearch(b, (byte)1);
        System.out.println("index = " + index);
    }
}
---------- END SOURCE ----------
(Incident Review ID: 261136)
======================================================================