Name: tb29552 Date: 01/12/2004


FULL PRODUCT VERSION :
java version "1.4.2_03"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.4.2_03-b02)
Java HotSpot(TM) Server VM (build 1.4.2_03-b02, mixed mode)

ADDITIONAL OS VERSION INFORMATION :
Microsoft Windows XP [Version 5.1.2600]

A DESCRIPTION OF THE PROBLEM :
The attached test case does not work correctly with java using the -server option. It works fine without the -server option.

In particular, when run in -server mode, the test case throws ArrayIndexOutOfBounds exceptions. I have also included a line in the code which demonstrates an inconsistency in the JVM; inside a loop

 while (searchPos != 0x0ffff) {
    ...
 }

I demonstrate searchPos to in fact be equal to 0x0ffff.

The problem appears to be a timing issue. If I run the code in an IDE such as JBuilder and step through, the problem disappears. I can also sometimes get the problem to disappear by adding unrelated code at various points in the program (such as immediately before the while loop)

The problem appears consistently if I run the test repeatedly in a loop. (The main method of the test case invokes the test 200 times.) If I run the test only a single times, the error sometimes appears and sometimes does not.

STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
javac NewDeflater.java
java -server NewDeflater

I used version 1.4.2_03 of the JDK to produce this problem, but also experienced the problem with every other JDK I tried.

Random data is not necessary to produce the problem; I was able to produce the bug using Windows binary files, etc.

EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
The program should terminate without throwing any exceptions or producing any output. This is the behavior seen in client mode.

ACTUAL -
The test case, which was run in a loop, repeatedly threw ArrayIndexOutOfBounds exceptions. Moreover, it printed debugging output to the console, which proved that there was internal inconsistency in the VM.

See error message below; the "0: 65535 65535 true" etc. was generated by System.out.println statements in my code.

ERROR MESSAGES/STACK TRACES THAT OCCUR :
0: 65535 65535 true
java.lang.ArrayIndexOutOfBoundsException: 65535
        at NewDeflater._newhash_FindBestMatch(NewDeflater.java:54)
        at NewDeflater.CompressDataInWindow(NewDeflater.java:73)
        at NewDeflater.main(NewDeflater.java:108)
0: 65535 65535 false
java.lang.ArrayIndexOutOfBoundsException: 65535
        at NewDeflater._newhash_FindBestMatch(NewDeflater.java:54)
        at NewDeflater.CompressDataInWindow(NewDeflater.java:73)
        at NewDeflater.main(NewDeflater.java:108)
0: 65535 65535 false
java.lang.ArrayIndexOutOfBoundsException: 65535
        at NewDeflater._newhash_FindBestMatch(NewDeflater.java:54)
        at NewDeflater.CompressDataInWindow(NewDeflater.java:73)
        at NewDeflater.main(NewDeflater.java:108)
0: 65535 65535 false
java.lang.ArrayIndexOutOfBoundsException: 65535
        at NewDeflater._newhash_FindBestMatch(NewDeflater.java:54)
        at NewDeflater.CompressDataInWindow(NewDeflater.java:73)
        at NewDeflater.main(NewDeflater.java:108)
0: 65535 65535 false
java.lang.ArrayIndexOutOfBoundsException: 65535
        at NewDeflater._newhash_FindBestMatch(NewDeflater.java:54)
        at NewDeflater.CompressDataInWindow(NewDeflater.java:73)
        at NewDeflater.main(NewDeflater.java:108)
0: 65535 65535 false
java.lang.ArrayIndexOutOfBoundsException: 65535
        at NewDeflater._newhash_FindBestMatch(NewDeflater.java:54)
        at NewDeflater.CompressDataInWindow(NewDeflater.java:73)
        at NewDeflater.main(NewDeflater.java:108)
0: 65535 65535 false
java.lang.ArrayIndexOutOfBoundsException: 65535
        at NewDeflater._newhash_FindBestMatch(NewDeflater.java:54)
        at NewDeflater.CompressDataInWindow(NewDeflater.java:73)
        at NewDeflater.main(NewDeflater.java:108)
0: 65535 65535 false
java.lang.ArrayIndexOutOfBoundsException: 65535
        at NewDeflater._newhash_FindBestMatch(NewDeflater.java:54)
        at NewDeflater.CompressDataInWindow(NewDeflater.java:73)
        at NewDeflater.main(NewDeflater.java:108)
0: 65535 65535 false
java.lang.ArrayIndexOutOfBoundsException: 65535
        at NewDeflater._newhash_FindBestMatch(NewDeflater.java:54)
        at NewDeflater.CompressDataInWindow(NewDeflater.java:73)
        at NewDeflater.main(NewDeflater.java:108)

(continues)

REPRODUCIBILITY :
This bug can be reproduced always.

---------- BEGIN SOURCE ----------
// This is stripped source code to do zip compression, stripped as
// much as was possible while still producing the bug.

class NewDeflater {

 private static final int WINDOW_SIZE = 65535; // leaving 0xffff for a null reference.
 private static final short HASH_NULL = -1;

 byte[] window;
 int window_off;
 int window_end;

 /** Hash table functions **/

 public static int HASHTABLE_SIZE = 16384;
 short[] hashHeads;
 short[] hashChains;

 private int HashFunction(int byte1, int byte2, int byte3) {
   return (((byte1 << 6) ^ (byte2 << 3) ^ byte3) & 0x3fff);
 }

 private void HashAdd(int byte1, int byte2, int byte3, int location) {
   int slot = HashFunction(byte1, byte2, byte3);
   short prev = hashHeads[slot];
   hashHeads[slot] = (short) location;
   hashChains[location] = (short) prev;
 }

 int BestMatchLength;
 int BestMatchLocation;

 public NewDeflater() {
   window = new byte[WINDOW_SIZE];
   hashHeads = new short[HASHTABLE_SIZE];
   for (int i = 0; i < HASHTABLE_SIZE; i++)
     hashHeads[i] = HASH_NULL; // a null reference. eventually: -1.
   hashChains = new short[WINDOW_SIZE];
   for (int i = 0; i < WINDOW_SIZE; i++)
     hashChains[i] = HASH_NULL;
   window_off = 1;
   window_end = 1;
 }

 // Parameters:
 // htr: the hash-table root, the first potential match to search.
 private void _newhash_FindBestMatch(int htr) {
   int searchPos = (int) hashHeads[htr] & 0xffff;
   int currpos = window_off;
   while (searchPos != 0x0ffff) {
     // HERE IS PROOF OF THE JVM BUG:
     if (searchPos + BestMatchLength > 65534) {
       System.out.println("" + (searchPos - 0x0ffff) + ": " + searchPos + " " + 0x0ffff + " " + (searchPos == 0x0ffff)); //(searchPos == 0xffff));
     }
     // Determine the length of the match.
     int currlen = 0;
     while (currlen < 258 && (window[searchPos + currlen] == window[currpos + currlen]))
       currlen++;
     if (currlen > BestMatchLength) {
       BestMatchLength = currlen;
       BestMatchLocation = searchPos;
       if (currlen == 258) return;
     }
     searchPos = (int) hashChains[searchPos] & 0xffff;
   }
 }

  private void CompressDataInWindow() {
   int htr;

   while (window_off < window_end - 258) {
     htr = HashFunction(window[window_off], window[window_off+1], window[window_off+2]);
     BestMatchLength = 0;

     if (hashHeads[htr] != HASH_NULL)
       _newhash_FindBestMatch(htr);

     if (BestMatchLength > 2) {

       // now that we are done with the hash table, add the present entry.
       HashAdd(window[window_off], window[window_off+1], window[window_off+2], window_off);

       // add entries to the hash table for the skipped portion.
       int limit = window_off + BestMatchLength;
       window_off++;

       while (window_off < limit) {
         HashAdd(window[window_off], window[window_off+1], window[window_off+2], window_off);
         window_off++;
       }
     }
     else
       HashAdd(window[window_off], window[window_off+1], window[window_off+2], window_off);
   }
 }

 public void setInput(byte[] buf, int off, int len) {
   System.arraycopy(buf, off, window, window_end, len);
   window_end += len;
 }

 public static void main(String[] args) {
  byte[] test = new byte[40000];
  java.util.Random r = new java.util.Random();
  r.nextBytes(test);

  for (int i = 0; i < 200; i++) {
   try {
     NewDeflater def = new NewDeflater();
     def.setInput(test, 0, test.length);
     def.CompressDataInWindow();
   }
   catch (Exception ex) {
     ex.printStackTrace();
   }
   }
 }
}
---------- END SOURCE ----------
(Review ID: 231828)
======================================================================