diff options
Diffstat (limited to 'libjava/classpath/java/util/zip/DeflaterEngine.java')
| -rw-r--r-- | libjava/classpath/java/util/zip/DeflaterEngine.java | 618 |
1 files changed, 309 insertions, 309 deletions
diff --git a/libjava/classpath/java/util/zip/DeflaterEngine.java b/libjava/classpath/java/util/zip/DeflaterEngine.java index 38a82d8..287558e 100644 --- a/libjava/classpath/java/util/zip/DeflaterEngine.java +++ b/libjava/classpath/java/util/zip/DeflaterEngine.java @@ -45,7 +45,7 @@ class DeflaterEngine implements DeflaterConstants /** * Hashtable, hashing three characters to an index for window, so - * that window[index]..window[index+2] have this hash code. + * that window[index]..window[index+2] have this hash code. * Note that the array should really be unsigned short, so you need * to and the values with 0xffff. */ @@ -53,7 +53,7 @@ class DeflaterEngine implements DeflaterConstants /** * prev[index & WMASK] points to the previous index that has the - * same hash code as the string starting at index. This way + * same hash code as the string starting at index. This way * entries with the same hash code are in a linked list. * Note that the array should really be unsigned short, so you need * to and the values with 0xffff. @@ -78,7 +78,7 @@ class DeflaterEngine implements DeflaterConstants private int lookahead; /** - * This array contains the part of the uncompressed stream that + * This array contains the part of the uncompressed stream that * is of relevance. The current character is indexed by strstart. */ private byte[] window; @@ -113,12 +113,12 @@ class DeflaterEngine implements DeflaterConstants * second half is copied to the beginning. * * The head array is a hash table. Three characters build a hash value - * and they the value points to the corresponding index in window of + * and they the value points to the corresponding index in window of * the last string with this hash. The prev array implements a * linked list of matches with the same hash: prev[index & WMASK] points * to the previous index with the same hash. - * - * + * + * */ @@ -180,44 +180,44 @@ class DeflaterEngine implements DeflaterConstants niceLength = DeflaterConstants.NICE_LENGTH[lvl]; max_chain = DeflaterConstants.MAX_CHAIN[lvl]; - if (DeflaterConstants.COMPR_FUNC[lvl] != comprFunc) + if (DeflaterConstants.COMPR_FUNC[lvl] != comprFunc) { - if (DeflaterConstants.DEBUGGING) - System.err.println("Change from "+comprFunc +" to " - + DeflaterConstants.COMPR_FUNC[lvl]); - switch (comprFunc) - { - case DEFLATE_STORED: - if (strstart > blockStart) - { - huffman.flushStoredBlock(window, blockStart, - strstart - blockStart, false); - blockStart = strstart; - } - updateHash(); - break; - case DEFLATE_FAST: - if (strstart > blockStart) - { - huffman.flushBlock(window, blockStart, strstart - blockStart, - false); - blockStart = strstart; - } - break; - case DEFLATE_SLOW: - if (prevAvailable) - huffman.tallyLit(window[strstart-1] & 0xff); - if (strstart > blockStart) - { - huffman.flushBlock(window, blockStart, strstart - blockStart, - false); - blockStart = strstart; - } - prevAvailable = false; - matchLen = MIN_MATCH - 1; - break; - } - comprFunc = COMPR_FUNC[lvl]; + if (DeflaterConstants.DEBUGGING) + System.err.println("Change from "+comprFunc +" to " + + DeflaterConstants.COMPR_FUNC[lvl]); + switch (comprFunc) + { + case DEFLATE_STORED: + if (strstart > blockStart) + { + huffman.flushStoredBlock(window, blockStart, + strstart - blockStart, false); + blockStart = strstart; + } + updateHash(); + break; + case DEFLATE_FAST: + if (strstart > blockStart) + { + huffman.flushBlock(window, blockStart, strstart - blockStart, + false); + blockStart = strstart; + } + break; + case DEFLATE_SLOW: + if (prevAvailable) + huffman.tallyLit(window[strstart-1] & 0xff); + if (strstart > blockStart) + { + huffman.flushBlock(window, blockStart, strstart - blockStart, + false); + blockStart = strstart; + } + prevAvailable = false; + matchLen = MIN_MATCH - 1; + break; + } + comprFunc = COMPR_FUNC[lvl]; } } @@ -225,7 +225,7 @@ class DeflaterEngine implements DeflaterConstants if (DEBUGGING) System.err.println("updateHash: "+strstart); ins_h = (window[strstart] << HASH_SHIFT) ^ window[strstart + 1]; - } + } /** * Inserts the current string in the head hash and returns the previous @@ -238,13 +238,13 @@ class DeflaterEngine implements DeflaterConstants if (DEBUGGING) { - if (hash != (((window[strstart] << (2*HASH_SHIFT)) - ^ (window[strstart + 1] << HASH_SHIFT) - ^ (window[strstart + 2])) & HASH_MASK)) - throw new InternalError("hash inconsistent: "+hash+"/" - +window[strstart]+"," - +window[strstart+1]+"," - +window[strstart+2]+","+HASH_SHIFT); + if (hash != (((window[strstart] << (2*HASH_SHIFT)) + ^ (window[strstart + 1] << HASH_SHIFT) + ^ (window[strstart + 2])) & HASH_MASK)) + throw new InternalError("hash inconsistent: "+hash+"/" + +window[strstart]+"," + +window[strstart+1]+"," + +window[strstart+2]+","+HASH_SHIFT); } prev[strstart & WMASK] = match = head[hash]; @@ -259,22 +259,22 @@ class DeflaterEngine implements DeflaterConstants matchStart -= WSIZE; strstart -= WSIZE; blockStart -= WSIZE; - + /* Slide the hash table (could be avoided with 32 bit values * at the expense of memory usage). */ - for (int i = 0; i < HASH_SIZE; i++) + for (int i = 0; i < HASH_SIZE; i++) { - int m = head[i] & 0xffff; - head[i] = m >= WSIZE ? (short) (m - WSIZE) : 0; + int m = head[i] & 0xffff; + head[i] = m >= WSIZE ? (short) (m - WSIZE) : 0; } /* Slide the prev table. */ - for (int i = 0; i < WSIZE; i++) + for (int i = 0; i < WSIZE; i++) { - int m = prev[i] & 0xffff; - prev[i] = m >= WSIZE ? (short) (m - WSIZE) : 0; + int m = prev[i] & 0xffff; + prev[i] = m >= WSIZE ? (short) (m - WSIZE) : 0; } } @@ -298,30 +298,30 @@ class DeflaterEngine implements DeflaterConstants */ while (lookahead < DeflaterConstants.MIN_LOOKAHEAD && inputOff < inputEnd) { - int more = 2*WSIZE - lookahead - strstart; - - if (more > inputEnd - inputOff) - more = inputEnd - inputOff; - - System.arraycopy(inputBuf, inputOff, - window, strstart + lookahead, more); - adler.update(inputBuf, inputOff, more); - inputOff += more; - totalIn += more; - lookahead += more; + int more = 2*WSIZE - lookahead - strstart; + + if (more > inputEnd - inputOff) + more = inputEnd - inputOff; + + System.arraycopy(inputBuf, inputOff, + window, strstart + lookahead, more); + adler.update(inputBuf, inputOff, more); + inputOff += more; + totalIn += more; + lookahead += more; } - if (lookahead >= MIN_MATCH) + if (lookahead >= MIN_MATCH) updateHash(); } /** - * Find the best (longest) string in the window matching the + * Find the best (longest) string in the window matching the * string starting at strstart. * * Preconditions: * strstart + MAX_MATCH <= window.length. - * + * * * @param curMatch */ @@ -333,7 +333,7 @@ class DeflaterEngine implements DeflaterConstants int match; int best_end = this.strstart + matchLen; int best_len = Math.max(matchLen, MIN_MATCH - 1); - + int limit = Math.max(strstart - MAX_DIST, 0); int strend = scan + MAX_MATCH - 1; @@ -350,51 +350,51 @@ class DeflaterEngine implements DeflaterConstants if (niceLength > lookahead) niceLength = lookahead; - if (DeflaterConstants.DEBUGGING - && strstart > 2*WSIZE - MIN_LOOKAHEAD) + if (DeflaterConstants.DEBUGGING + && strstart > 2*WSIZE - MIN_LOOKAHEAD) throw new InternalError("need lookahead"); - + do { if (DeflaterConstants.DEBUGGING && curMatch >= strstart) - throw new InternalError("future match"); + throw new InternalError("future match"); if (window[curMatch + best_len] != scan_end - || window[curMatch + best_len - 1] != scan_end1 - || window[curMatch] != window[scan] - || window[curMatch+1] != window[scan + 1]) - continue; + || window[curMatch + best_len - 1] != scan_end1 + || window[curMatch] != window[scan] + || window[curMatch+1] != window[scan + 1]) + continue; - match = curMatch + 2; + match = curMatch + 2; scan += 2; /* We check for insufficient lookahead only every 8th comparison; * the 256th check will be made at strstart+258. */ while (window[++scan] == window[++match] - && window[++scan] == window[++match] - && window[++scan] == window[++match] - && window[++scan] == window[++match] - && window[++scan] == window[++match] - && window[++scan] == window[++match] - && window[++scan] == window[++match] - && window[++scan] == window[++match] - && scan < strend) + && window[++scan] == window[++match] + && window[++scan] == window[++match] + && window[++scan] == window[++match] + && window[++scan] == window[++match] + && window[++scan] == window[++match] + && window[++scan] == window[++match] + && window[++scan] == window[++match] + && scan < strend) ; if (scan > best_end) { -// if (DeflaterConstants.DEBUGGING && ins_h == 0) -// System.err.println("Found match: "+curMatch+"-"+(scan-strstart)); - matchStart = curMatch; - best_end = scan; - best_len = scan - strstart; - if (best_len >= niceLength) - break; - - scan_end1 = window[best_end-1]; - scan_end = window[best_end]; +// if (DeflaterConstants.DEBUGGING && ins_h == 0) +// System.err.println("Found match: "+curMatch+"-"+(scan-strstart)); + matchStart = curMatch; + best_end = scan; + best_len = scan - strstart; + if (best_len >= niceLength) + break; + + scan_end1 = window[best_end-1]; + scan_end = window[best_end]; } scan = strstart; } while ((curMatch = (prev[curMatch & WMASK] & 0xffff)) > limit - && --chainLength != 0); + && --chainLength != 0); matchLen = Math.min(best_len, lookahead); return matchLen >= MIN_MATCH; @@ -417,13 +417,13 @@ class DeflaterEngine implements DeflaterConstants length--; while (--length > 0) { - insertString(); - strstart++; + insertString(); + strstart++; } strstart += 2; blockStart = strstart; - } - + } + private boolean deflateStored(boolean flush, boolean finish) { if (!flush && lookahead == 0) @@ -434,25 +434,25 @@ class DeflaterEngine implements DeflaterConstants int storedLen = strstart - blockStart; - if ((storedLen >= DeflaterConstants.MAX_BLOCK_SIZE) - /* Block is full */ - || (blockStart < WSIZE && storedLen >= MAX_DIST) - /* Block may move out of window */ - || flush) + if ((storedLen >= DeflaterConstants.MAX_BLOCK_SIZE) + /* Block is full */ + || (blockStart < WSIZE && storedLen >= MAX_DIST) + /* Block may move out of window */ + || flush) { - boolean lastBlock = finish; - if (storedLen > DeflaterConstants.MAX_BLOCK_SIZE) - { - storedLen = DeflaterConstants.MAX_BLOCK_SIZE; - lastBlock = false; - } - - if (DeflaterConstants.DEBUGGING) - System.err.println("storedBlock["+storedLen+","+lastBlock+"]"); - - huffman.flushStoredBlock(window, blockStart, storedLen, lastBlock); - blockStart += storedLen; - return !lastBlock; + boolean lastBlock = finish; + if (storedLen > DeflaterConstants.MAX_BLOCK_SIZE) + { + storedLen = DeflaterConstants.MAX_BLOCK_SIZE; + lastBlock = false; + } + + if (DeflaterConstants.DEBUGGING) + System.err.println("storedBlock["+storedLen+","+lastBlock+"]"); + + huffman.flushStoredBlock(window, blockStart, storedLen, lastBlock); + blockStart += storedLen; + return !lastBlock; } return true; } @@ -464,78 +464,78 @@ class DeflaterEngine implements DeflaterConstants while (lookahead >= MIN_LOOKAHEAD || flush) { - if (lookahead == 0) - { - /* We are flushing everything */ - huffman.flushBlock(window, blockStart, strstart - blockStart, - finish); - blockStart = strstart; - return false; - } - - if (strstart > 2 * WSIZE - MIN_LOOKAHEAD) - { - /* slide window, as findLongestMatch need this. - * This should only happen when flushing and the window - * is almost full. - */ - slideWindow(); - } - - int hashHead; - if (lookahead >= MIN_MATCH - && (hashHead = insertString()) != 0 - && strategy != Deflater.HUFFMAN_ONLY - && strstart - hashHead <= MAX_DIST - && findLongestMatch(hashHead)) - { - /* longestMatch sets matchStart and matchLen */ - if (DeflaterConstants.DEBUGGING) - { - for (int i = 0 ; i < matchLen; i++) - { - if (window[strstart+i] != window[matchStart + i]) - throw new InternalError(); - } - } - boolean full = huffman.tallyDist(strstart - matchStart, matchLen); - - lookahead -= matchLen; - if (matchLen <= max_lazy && lookahead >= MIN_MATCH) - { - while (--matchLen > 0) - { - strstart++; - insertString(); - } - strstart++; - } - else - { - strstart += matchLen; - if (lookahead >= MIN_MATCH - 1) - updateHash(); - } - matchLen = MIN_MATCH - 1; - if (!full) - continue; - } - else - { - /* No match found */ - huffman.tallyLit(window[strstart] & 0xff); - strstart++; - lookahead--; - } - - if (huffman.isFull()) - { - boolean lastBlock = finish && lookahead == 0; - huffman.flushBlock(window, blockStart, strstart - blockStart, - lastBlock); - blockStart = strstart; - return !lastBlock; - } + if (lookahead == 0) + { + /* We are flushing everything */ + huffman.flushBlock(window, blockStart, strstart - blockStart, + finish); + blockStart = strstart; + return false; + } + + if (strstart > 2 * WSIZE - MIN_LOOKAHEAD) + { + /* slide window, as findLongestMatch need this. + * This should only happen when flushing and the window + * is almost full. + */ + slideWindow(); + } + + int hashHead; + if (lookahead >= MIN_MATCH + && (hashHead = insertString()) != 0 + && strategy != Deflater.HUFFMAN_ONLY + && strstart - hashHead <= MAX_DIST + && findLongestMatch(hashHead)) + { + /* longestMatch sets matchStart and matchLen */ + if (DeflaterConstants.DEBUGGING) + { + for (int i = 0 ; i < matchLen; i++) + { + if (window[strstart+i] != window[matchStart + i]) + throw new InternalError(); + } + } + boolean full = huffman.tallyDist(strstart - matchStart, matchLen); + + lookahead -= matchLen; + if (matchLen <= max_lazy && lookahead >= MIN_MATCH) + { + while (--matchLen > 0) + { + strstart++; + insertString(); + } + strstart++; + } + else + { + strstart += matchLen; + if (lookahead >= MIN_MATCH - 1) + updateHash(); + } + matchLen = MIN_MATCH - 1; + if (!full) + continue; + } + else + { + /* No match found */ + huffman.tallyLit(window[strstart] & 0xff); + strstart++; + lookahead--; + } + + if (huffman.isFull()) + { + boolean lastBlock = finish && lookahead == 0; + huffman.flushBlock(window, blockStart, strstart - blockStart, + lastBlock); + blockStart = strstart; + return !lastBlock; + } } return true; } @@ -547,127 +547,127 @@ class DeflaterEngine implements DeflaterConstants while (lookahead >= MIN_LOOKAHEAD || flush) { - if (lookahead == 0) - { - if (prevAvailable) - huffman.tallyLit(window[strstart-1] & 0xff); - prevAvailable = false; - - /* We are flushing everything */ - if (DeflaterConstants.DEBUGGING && !flush) - throw new InternalError("Not flushing, but no lookahead"); - huffman.flushBlock(window, blockStart, strstart - blockStart, - finish); - blockStart = strstart; - return false; - } - - if (strstart >= 2 * WSIZE - MIN_LOOKAHEAD) - { - /* slide window, as findLongestMatch need this. - * This should only happen when flushing and the window - * is almost full. - */ - slideWindow(); - } - - int prevMatch = matchStart; - int prevLen = matchLen; - if (lookahead >= MIN_MATCH) - { - int hashHead = insertString(); - if (strategy != Deflater.HUFFMAN_ONLY - && hashHead != 0 && strstart - hashHead <= MAX_DIST - && findLongestMatch(hashHead)) - { - /* longestMatch sets matchStart and matchLen */ - - /* Discard match if too small and too far away */ - if (matchLen <= 5 - && (strategy == Deflater.FILTERED - || (matchLen == MIN_MATCH - && strstart - matchStart > TOO_FAR))) { - matchLen = MIN_MATCH - 1; - } - } - } - - /* previous match was better */ - if (prevLen >= MIN_MATCH && matchLen <= prevLen) - { - if (DeflaterConstants.DEBUGGING) - { - for (int i = 0 ; i < matchLen; i++) - { - if (window[strstart-1+i] != window[prevMatch + i]) - throw new InternalError(); - } - } - huffman.tallyDist(strstart - 1 - prevMatch, prevLen); - prevLen -= 2; - do - { - strstart++; - lookahead--; - if (lookahead >= MIN_MATCH) - insertString(); - } - while (--prevLen > 0); - strstart ++; - lookahead--; - prevAvailable = false; - matchLen = MIN_MATCH - 1; - } - else - { - if (prevAvailable) - huffman.tallyLit(window[strstart-1] & 0xff); - prevAvailable = true; - strstart++; - lookahead--; - } - - if (huffman.isFull()) - { - int len = strstart - blockStart; - if (prevAvailable) - len--; - boolean lastBlock = (finish && lookahead == 0 && !prevAvailable); - huffman.flushBlock(window, blockStart, len, lastBlock); - blockStart += len; - return !lastBlock; - } + if (lookahead == 0) + { + if (prevAvailable) + huffman.tallyLit(window[strstart-1] & 0xff); + prevAvailable = false; + + /* We are flushing everything */ + if (DeflaterConstants.DEBUGGING && !flush) + throw new InternalError("Not flushing, but no lookahead"); + huffman.flushBlock(window, blockStart, strstart - blockStart, + finish); + blockStart = strstart; + return false; + } + + if (strstart >= 2 * WSIZE - MIN_LOOKAHEAD) + { + /* slide window, as findLongestMatch need this. + * This should only happen when flushing and the window + * is almost full. + */ + slideWindow(); + } + + int prevMatch = matchStart; + int prevLen = matchLen; + if (lookahead >= MIN_MATCH) + { + int hashHead = insertString(); + if (strategy != Deflater.HUFFMAN_ONLY + && hashHead != 0 && strstart - hashHead <= MAX_DIST + && findLongestMatch(hashHead)) + { + /* longestMatch sets matchStart and matchLen */ + + /* Discard match if too small and too far away */ + if (matchLen <= 5 + && (strategy == Deflater.FILTERED + || (matchLen == MIN_MATCH + && strstart - matchStart > TOO_FAR))) { + matchLen = MIN_MATCH - 1; + } + } + } + + /* previous match was better */ + if (prevLen >= MIN_MATCH && matchLen <= prevLen) + { + if (DeflaterConstants.DEBUGGING) + { + for (int i = 0 ; i < matchLen; i++) + { + if (window[strstart-1+i] != window[prevMatch + i]) + throw new InternalError(); + } + } + huffman.tallyDist(strstart - 1 - prevMatch, prevLen); + prevLen -= 2; + do + { + strstart++; + lookahead--; + if (lookahead >= MIN_MATCH) + insertString(); + } + while (--prevLen > 0); + strstart ++; + lookahead--; + prevAvailable = false; + matchLen = MIN_MATCH - 1; + } + else + { + if (prevAvailable) + huffman.tallyLit(window[strstart-1] & 0xff); + prevAvailable = true; + strstart++; + lookahead--; + } + + if (huffman.isFull()) + { + int len = strstart - blockStart; + if (prevAvailable) + len--; + boolean lastBlock = (finish && lookahead == 0 && !prevAvailable); + huffman.flushBlock(window, blockStart, len, lastBlock); + blockStart += len; + return !lastBlock; + } } return true; - } + } - public boolean deflate(boolean flush, boolean finish) + public boolean deflate(boolean flush, boolean finish) { boolean progress; do { - fillWindow(); - boolean canFlush = flush && inputOff == inputEnd; - if (DeflaterConstants.DEBUGGING) - System.err.println("window: ["+blockStart+","+strstart+"," - +lookahead+"], "+comprFunc+","+canFlush); - switch (comprFunc) - { - case DEFLATE_STORED: - progress = deflateStored(canFlush, finish); - break; - case DEFLATE_FAST: - progress = deflateFast(canFlush, finish); - break; - case DEFLATE_SLOW: - progress = deflateSlow(canFlush, finish); - break; - default: - throw new InternalError(); - } + fillWindow(); + boolean canFlush = flush && inputOff == inputEnd; + if (DeflaterConstants.DEBUGGING) + System.err.println("window: ["+blockStart+","+strstart+"," + +lookahead+"], "+comprFunc+","+canFlush); + switch (comprFunc) + { + case DEFLATE_STORED: + progress = deflateStored(canFlush, finish); + break; + case DEFLATE_FAST: + progress = deflateFast(canFlush, finish); + break; + case DEFLATE_SLOW: + progress = deflateSlow(canFlush, finish); + break; + default: + throw new InternalError(); + } } while (pending.isFlushed() /* repeat while we have no pending output */ - && progress); /* and progress was made */ + && progress); /* and progress was made */ return progress; } @@ -676,12 +676,12 @@ class DeflaterEngine implements DeflaterConstants { if (inputOff < inputEnd) throw new IllegalStateException - ("Old input was not completely processed"); + ("Old input was not completely processed"); int end = off + len; /* We want to throw an ArrayIndexOutOfBoundsException early. The - * check is very tricky: it also handles integer wrap around. + * check is very tricky: it also handles integer wrap around. */ if (0 > off || off > end || end > buf.length) throw new ArrayIndexOutOfBoundsException(); |