Name: rmT116609 Date: 12/09/2003
FULL PRODUCT VERSION :
java version "1.4.2_02"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.4.2_02-b03)
Java HotSpot(TM) Client VM (build 1.4.2_02-b03, mixed mode)
and with -server flag:
java version "1.4.2_02"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.4.2_02-b03)
Java HotSpot(TM) Server VM (build 1.4.2_02-b03, mixed mode)
FULL OS VERSION :
Linux p4laptop.riser 2.4.20-gentoo-r6 #2 Mit Aug 20 22:14:28 CEST 2003 i686 Mobile Intel(R) Pentium(R) 4 - M CPU 2.00GHz GenuineIntel GNU/Linux
EXTRA RELEVANT SYSTEM CONFIGURATION :
Same behavior on other (at least linux) machines.
A DESCRIPTION OF THE PROBLEM :
When run without -server flag the program runs successfully:
$ java GF65536Redundance28
encoding..
but when the -server flag ist added there occurs a sucpicious Exception
$ java -server GF65536Redundance28
encoding..
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 74074
at GF65536.polyeval(GF65536.java:156)
at GF65536Redundance28.encode(GF65536Redundance28.java:95)
at GF65536Redundance28.main(GF65536Redundance28.java:122)
The critical code lines are:
---
int t = (L[(d & 0xffff)] & 0xffff) + (L[(bi & 0xffff)] & 0xffff); // <- t can't be more than 2*0xffff = 2*65535
if (t > 65536-1) t = t - (65536-1); // <- this statement seems to be ignored when running with -server flag
s = (short)(s^E[t]); // <- here occurs the java.lang.ArrayIndexOutOfBoundsException
---
on the last line t can't be more than 65535 because on the first line it gets a value between 0 and 2*65535 and the middle line brings t back in the interval [0,65535]. E however is an array[65546], so OutofBoundsException should not occur -- and also do not if the -server flag is not specified.
To me it looks like the middle line is ignored when -server is used.
STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
$ javac *.java
$ java -server GF65536Redundance28
EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
The program should terminated normally and not through Exceptions.
ACTUAL -
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 74074
at GF65536.polyeval(GF65536.java:156)
at GF65536Redundance28.encode(GF65536Redundance28.java:95)
at GF65536Redundance28.main(GF65536Redundance28.java:122)
ERROR MESSAGES/STACK TRACES THAT OCCUR :
see actual results
REPRODUCIBILITY :
This bug can be reproduced always.
---------- BEGIN SOURCE ----------
/*
* Created on 03.08.2003
* (C) by Micha Riser
*/
/**
* @author micha
*
*/
final public class GF65536 {
private static short[] E = new short[65536];
private static short[] L = new short[65536];
private static short[] inv = new short[65536]; // multiplicative inverse table
private static final String[] dig = {"0","1","2","3","4","5","6","7",
"8","9","a","b","c","d","e","f"};
private static boolean isinitialized = false;
// fast multiply using table lookup
static public short mul(short a, short b){
int t = 0;
if (a == 0 || b == 0) return 0;
t = (L[(a & 0xffff)] & 0xffff) + (L[(b & 0xffff)] & 0xffff);
if (t > 65536-1) t = t - (65536-1);
return E[t];
}
// slow multiply, using shifting
static private short FFMul(short a, short b) {
short aa = a, bb = b, r = 0, t;
while (aa != 0) {
if ((aa & 1) != 0)
r = (short)(r ^ bb);
t = (short)(bb & 0x8000);
bb = (short)(bb << 1);
if (t != 0)
bb = (short)(bb ^ 0x9A0F);
aa = (short)((aa & 0xffff) >> 1);
}
return r;
}
// hex: print a short as two hex digits
static public String hex(short a) {
return dig[(a & 0xffff) >> 12] + dig[(a & 0x0fff) >> 8] + dig[(a & 0x00ff) >> 4] + dig[a & 0x0f];
}
// hex: print a single digit (for tables)
static public String hex(int a) {
return dig[a];
}
// loadE: create and load the E table
static private void loadE() {
short x = (short)0x0001;
int index = 0;
E[index++] = (short)0x0001;
for (int i = 0; i < 65536-1; i++) {
short y = FFMul(x, (short)0x0021);
E[index++] = y;
x = y;
}
}
// loadL: load the L table using the E table
static private void loadL() {
int index;
for (int i = 0; i < 65536-1; i++) {
L[E[i] & 0xffff] = (short)i;
}
}
// loadInv: load in the table inv
static private void loadInv() {
int index;
for (int i = 0; i < 65535; i++)
inv[i] = (short)(inv((short)(i & 0xffff)) & 0xffff);
}
// the multiplicative inverse of a short value
static public short inv(short b) {
short e = L[b & 0xffff];
return E[0xffff - (e & 0xffff)];
}
static public short add(short a, short b) {
return (short)(a^b);
}
static public short sub(short a, short b) {
return (short)(a^b);
}
synchronized static void init() {
if (!isinitialized) {
loadE();
loadL();
loadInv();
isinitialized = true;
}
}
public static void main(String[] args) {
init();
}
static short[][] calculateLix(short[] bases, int rawlength, int deslength) {
short[][] ret = new short[deslength][rawlength];
for(short x=0; x<deslength; x++) {
for(int i=0; i<rawlength; i++) {
//calculate Li(x)
short d = 1;
for(short j=0; j<rawlength; j++)
if (j!=i) {
d = mul(d,sub(bases[i],bases[j]));
}
d = inv(d);
for(short j=0; j<rawlength; j++)
if (j!=i) {
d = mul(d,sub(x,bases[j]));
}
ret[x][i] = d;
}
}
return ret;
}
/**
* This is the time critical code!
*
* @param b
* @param lix
* @param ret
* @return
*/
static short[] polyeval(short[] b, short[][] lix, short[] ret) {
for(int x=0; x<ret.length; x++) {
short s = 0;
for(int i=0; i<b.length; i++) {
// multiply Li[x] with b_i
short d = lix[x][i];
int bi = b[i];
if (d == 0 || bi == 0) continue;
int t = (L[(d & 0xffff)] & 0xffff) + (L[(bi & 0xffff)] & 0xffff); // <- t can't be more than 2*0xffff = 2*65535
if (t > 65536-1) t = t - (65536-1); // <- this statement seems to be ignored when running with -server flag (*)
s = (short)(s^E[t]); // <- here occurs the java.lang.ArrayIndexOutOfBoundsException
}
ret[x] = s;
}
return ret;
}
}
/*
* Created on 03.08.2003
* (C) by Micha Riser, 2003
*/
import java.io.ByteArrayInputStream;
import java.io.ByteArrayOutputStream;
import java.util.Random;
/**
* @author micha
*
*/
public class GF65536Redundance28 {
static public class Data {
public long getSize() {return size;}
public long size;
public byte[][] chunks;
}
public int nofBlocks(Data d) {
int totalrawnofchunks = (int)Math.ceil((double)d.getSize()/(double)chunksize);
return (int)Math.ceil((double)totalrawnofchunks/BLOCKSIZE);
}
public int neededChunks(Data d, int block) {
int totalrawnofchunks = (int)Math.ceil((double)d.getSize()/(double)chunksize);
int blocks = (int)Math.ceil((double)totalrawnofchunks/BLOCKSIZE);
if (block == blocks-1) {
int ret = totalrawnofchunks % BLOCKSIZE;
if (ret==0) return BLOCKSIZE; else return ret;
} else {
return BLOCKSIZE;
}
}
public int nofChunks(int neededchunks) {
return (int)Math.ceil(neededchunks*1.28);
}
public Data encode(java.io.InputStream input, long datalength) {
int totalrawnofchunks = (int)Math.ceil((double)datalength/(double)chunksize);
int totaldesnofchunks = (int)Math.ceil(totalrawnofchunks*1.28);
int blocks = (int)Math.ceil((double)totalrawnofchunks/BLOCKSIZE);
// now encode
try{
Data ret = new Data();
ret.chunks = new byte[totaldesnofchunks][chunksize];
ret.size = datalength;
for(int blocki=0; blocki<blocks; blocki++) {
int rawnofchunks,desnofchunks;
if (blocki==blocks-1) {
rawnofchunks = totalrawnofchunks % BLOCKSIZE;
if (rawnofchunks==0) rawnofchunks = BLOCKSIZE;
desnofchunks = (int)Math.ceil(rawnofchunks*1.28);
} else {
rawnofchunks = BLOCKSIZE;
desnofchunks = (int)Math.ceil(BLOCKSIZE*1.28);
}
short[] idbase = new short[rawnofchunks];
for(short i=0; i<rawnofchunks; i++) idbase[i]=i;
short[][]lix = GF65536.calculateLix(idbase,rawnofchunks,desnofchunks);
short[] in = new short[rawnofchunks];
short[] out = new short[desnofchunks];
long retsize = ret.getSize();
for(int i=0; i<chunksize; i+=2) {
int offset = i*rawnofchunks;
for(int j=0; j<rawnofchunks; j++) {
if (offset+2*j<retsize-1) {
in[j] = (short)( (input.read() & 0xff)+ (input.read() << 8) &0xffff );
} else {
if (offset+2*j == retsize-1) {
in[j] = (short)input.read();
} else {
in[j] = 0;
}
}
}
GF65536.polyeval(in,lix,out);
for(int j=0; j<desnofchunks; j++) {
ret.chunks[BLOCKSIZEENC*blocki+j][i] = (byte)((out[j] & 0xff00)>>8);
ret.chunks[BLOCKSIZEENC*blocki+j][i+1] = (byte)(out[j] & 0xff);
}
}
}
return ret;
} catch (java.io.IOException e) {
return null;
}
}
public static void main(String[] args) throws java.io.IOException {
int SIZE =1630400;
byte[] random = new byte[SIZE];
java.util.Random rnd = new Random(1234);
rnd.nextBytes(random);
GF65536Redundance28 encoder = new GF65536Redundance28();
GF65536.init();
System.out.println("encoding..");
Data enc = encoder.encode(new ByteArrayInputStream(random),SIZE);
}
private final int chunksize = 256*1024;
static private final int BLOCKSIZE = 100;
static private final int BLOCKSIZEENC = 128;
}
---------- END SOURCE ----------
CUSTOMER SUBMITTED WORKAROUND :
- do not use the -server flag
- I got around this by enlarging the array E by a factor 2, copying the lower part to the upper part and removing the if-state (line that is marked by *). Bad side of this is that it needs more memory (and probably is worse for the CPU's cache)
(Incident Review ID: 229675)
======================================================================