diff options
Diffstat (limited to 'openjdk/java/util/zip/DeflaterEngine.java')
| -rw-r--r-- | openjdk/java/util/zip/DeflaterEngine.java | 692 |
1 files changed, 0 insertions, 692 deletions
diff --git a/openjdk/java/util/zip/DeflaterEngine.java b/openjdk/java/util/zip/DeflaterEngine.java deleted file mode 100644 index 474e4913..00000000 --- a/openjdk/java/util/zip/DeflaterEngine.java +++ /dev/null @@ -1,692 +0,0 @@ -/* DeflaterEngine.java -- - Copyright (C) 2001, 2004, 2005 Free Software Foundation, Inc. - -This file is part of GNU Classpath. - -GNU Classpath is free software; you can redistribute it and/or modify -it under the terms of the GNU General Public License as published by -the Free Software Foundation; either version 2, or (at your option) -any later version. - -GNU Classpath is distributed in the hope that it will be useful, but -WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU -General Public License for more details. - -You should have received a copy of the GNU General Public License -along with GNU Classpath; see the file COPYING. If not, write to the -Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA -02110-1301 USA. - -Linking this library statically or dynamically with other modules is -making a combined work based on this library. Thus, the terms and -conditions of the GNU General Public License cover the whole -combination. - -As a special exception, the copyright holders of this library give you -permission to link this library with independent modules to produce an -executable, regardless of the license terms of these independent -modules, and to copy and distribute the resulting executable under -terms of your choice, provided that you also meet, for each linked -independent module, the terms and conditions of the license of that -module. An independent module is a module which is not derived from -or based on this library. If you modify this library, you may extend -this exception to your version of the library, but you are not -obligated to do so. If you do not wish to do so, delete this -exception statement from your version. */ - -package java.util.zip; - -final class DeflaterEngine implements DeflaterConstants -{ - private static final int TOO_FAR = 4096; - - private int ins_h; - - /** - * Hashtable, hashing three characters to an index for window, so - * 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. - */ - private short[] head; - - /** - * prev[index & WMASK] points to the previous index that has the - * 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. - */ - private short[] prev; - - private int matchStart, matchLen; - private boolean prevAvailable; - private int blockStart; - - /** - * strstart points to the current character in window. - */ - private int strstart; - - /** - * lookahead is the number of characters starting at strstart in - * window that are valid. - * So window[strstart] until window[strstart+lookahead-1] are valid - * characters. - */ - private int lookahead; - - /** - * This array contains the part of the uncompressed stream that - * is of relevance. The current character is indexed by strstart. - */ - private byte[] window; - - private int strategy, max_chain, max_lazy, niceLength, goodLength; - - /** The current compression function. */ - private int comprFunc; - - /** The input data for compression. */ - private byte[] inputBuf; - - /** The total bytes of input read. */ - private long totalIn; - - /** The offset into inputBuf, where input data starts. */ - private int inputOff; - - /** The end offset of the input data. */ - private int inputEnd; - - private DeflaterPending pending; - private DeflaterHuffman huffman; - - /** The adler checksum */ - private Adler32 adler; - - /* DEFLATE ALGORITHM: - * - * The uncompressed stream is inserted into the window array. When - * the window array is full the first half is thrown away and the - * 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 - * 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. - * - * - */ - - - DeflaterEngine(DeflaterPending pending) { - this.pending = pending; - huffman = new DeflaterHuffman(pending); - adler = new Adler32(); - - window = new byte[2*WSIZE]; - head = new short[HASH_SIZE]; - prev = new short[WSIZE]; - - /* We start at index 1, to avoid a implementation deficiency, that - * we cannot build a repeat pattern at index 0. - */ - blockStart = strstart = 1; - } - - public void reset() - { - huffman.reset(); - adler.reset(); - clearHash(); - totalIn = 0; - } - - final void clearHash() - { - blockStart = strstart = 1; - lookahead = 0; - prevAvailable = false; - matchLen = MIN_MATCH - 1; - for (int i = 0; i < HASH_SIZE; i++) - head[i] = 0; - for (int i = 0; i < WSIZE; i++) - prev[i] = 0; - } - - public final void resetAdler() - { - adler.reset(); - } - - public final int getAdler() - { - int chksum = (int) adler.getValue(); - return chksum; - } - - public final long getTotalIn() - { - return totalIn; - } - - public final void setStrategy(int strat) - { - strategy = strat; - } - - public void setLevel(int lvl) - { - goodLength = DeflaterConstants.GOOD_LENGTH[lvl]; - max_lazy = DeflaterConstants.MAX_LAZY[lvl]; - niceLength = DeflaterConstants.NICE_LENGTH[lvl]; - max_chain = DeflaterConstants.MAX_CHAIN[lvl]; - - 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]; - } - } - - private void updateHash() { - 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 - * value for this hash. - */ - private int insertString() { - short match; - int hash = ((ins_h << HASH_SHIFT) ^ window[strstart + (MIN_MATCH -1)]) - & HASH_MASK; - - 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); - } - - prev[strstart & WMASK] = match = head[hash]; - head[hash] = (short) strstart; - ins_h = hash; - return match & 0xffff; - } - - private void slideWindow() - { - System.arraycopy(window, WSIZE, window, 0, WSIZE); - 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++) - { - int m = head[i] & 0xffff; - head[i] = m >= WSIZE ? (short) (m - WSIZE) : 0; - } - - /* Slide the prev table. - */ - for (int i = 0; i < WSIZE; i++) - { - int m = prev[i] & 0xffff; - prev[i] = m >= WSIZE ? (short) (m - WSIZE) : 0; - } - } - - /** - * Fill the window when the lookahead becomes insufficient. - * Updates strstart and lookahead. - * - * OUT assertions: strstart + lookahead <= 2*WSIZE - * lookahead >= MIN_LOOKAHEAD or inputOff == inputEnd - */ - private void fillWindow() - { - /* If the window is almost full and there is insufficient lookahead, - * move the upper half to the lower one to make room in the upper half. - */ - if (strstart >= WSIZE + MAX_DIST) - slideWindow(); - - /* If there is not enough lookahead, but still some input left, - * read in the input - */ - 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; - } - - if (lookahead >= MIN_MATCH) - updateHash(); - } - - /** - * Find the best (longest) string in the window matching the - * string starting at strstart. - * - * Preconditions: - * strstart + MAX_MATCH <= window.length. - * - * - * @param curMatch - */ - private boolean findLongestMatch(int curMatch) { - int chainLength = this.max_chain; - int niceLength = this.niceLength; - short[] prev = this.prev; - int scan = this.strstart; - 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; - byte scan_end1 = window[best_end - 1]; - byte scan_end = window[best_end]; - - /* Do not waste too much time if we already have a good match: */ - if (best_len >= this.goodLength) - chainLength >>= 2; - - /* Do not look for matches beyond the end of the input. This is necessary - * to make deflate deterministic. - */ - if (niceLength > lookahead) - niceLength = 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"); - 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; - - 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) - ; - - 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]; - } - scan = strstart; - } while ((curMatch = (prev[curMatch & WMASK] & 0xffff)) > limit - && --chainLength != 0); - - matchLen = Math.min(best_len, lookahead); - return matchLen >= MIN_MATCH; - } - - void setDictionary(byte[] buffer, int offset, int length) { - if (DeflaterConstants.DEBUGGING && strstart != 1) - throw new IllegalStateException("strstart not 1"); - adler.update(buffer, offset, length); - if (length < MIN_MATCH) - return; - if (length > MAX_DIST) { - offset += length - MAX_DIST; - length = MAX_DIST; - } - - System.arraycopy(buffer, offset, window, strstart, length); - - updateHash(); - length--; - while (--length > 0) - { - insertString(); - strstart++; - } - strstart += 2; - blockStart = strstart; - } - - private boolean deflateStored(boolean flush, boolean finish) - { - if (!flush && lookahead == 0) - return false; - - strstart += lookahead; - lookahead = 0; - - 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) - { - 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; - } - - private boolean deflateFast(boolean flush, boolean finish) - { - if (lookahead < MIN_LOOKAHEAD && !flush) - return false; - - 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; - } - } - return true; - } - - private boolean deflateSlow(boolean flush, boolean finish) - { - if (lookahead < MIN_LOOKAHEAD && !flush) - return false; - - 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; - } - } - return true; - } - - 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(); - } - } - while (pending.isFlushed() /* repeat while we have no pending output */ - && progress); /* and progress was made */ - - return progress; - } - - void setInput(byte[] buf, int off, int len) - { - // caller has already checked parameters - inputBuf = buf; - inputOff = off; - inputEnd = off + len; - } - - public final boolean needsInput() - { - return inputEnd == inputOff; - } -} |