diff options
Diffstat (limited to 'libjava/classpath/java/util/zip/DeflaterHuffman.java')
| -rw-r--r-- | libjava/classpath/java/util/zip/DeflaterHuffman.java | 776 |
1 files changed, 776 insertions, 0 deletions
diff --git a/libjava/classpath/java/util/zip/DeflaterHuffman.java b/libjava/classpath/java/util/zip/DeflaterHuffman.java new file mode 100644 index 0000000..d040dde --- /dev/null +++ b/libjava/classpath/java/util/zip/DeflaterHuffman.java @@ -0,0 +1,776 @@ +/* DeflaterHuffman.java -- + Copyright (C) 2001, 2004 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; + +/** + * This is the DeflaterHuffman class. + * + * This class is <i>not</i> thread safe. This is inherent in the API, due + * to the split of deflate and setInput. + * + * @author Jochen Hoenicke + * @date Jan 6, 2000 + */ +class DeflaterHuffman +{ + private static final int BUFSIZE = 1 << (DeflaterConstants.DEFAULT_MEM_LEVEL + 6); + private static final int LITERAL_NUM = 286; + private static final int DIST_NUM = 30; + private static final int BITLEN_NUM = 19; + private static final int REP_3_6 = 16; + private static final int REP_3_10 = 17; + private static final int REP_11_138 = 18; + private static final int EOF_SYMBOL = 256; + private static final int[] BL_ORDER = + { 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 }; + + private static String bit4Reverse = + "\000\010\004\014\002\012\006\016\001\011\005\015\003\013\007\017"; + + class Tree { + short[] freqs; + short[] codes; + byte[] length; + int[] bl_counts; + int minNumCodes, numCodes; + int maxLength; + + Tree(int elems, int minCodes, int maxLength) { + this.minNumCodes = minCodes; + this.maxLength = maxLength; + freqs = new short[elems]; + bl_counts = new int[maxLength]; + } + + void reset() { + for (int i = 0; i < freqs.length; i++) + freqs[i] = 0; + codes = null; + length = null; + } + + final void writeSymbol(int code) + { + if (DeflaterConstants.DEBUGGING) + { + freqs[code]--; +// System.err.print("writeSymbol("+freqs.length+","+code+"): "); + } + pending.writeBits(codes[code] & 0xffff, length[code]); + } + + final void checkEmpty() + { + boolean empty = true; + for (int i = 0; i < freqs.length; i++) + if (freqs[i] != 0) + { + System.err.println("freqs["+i+"] == "+freqs[i]); + empty = false; + } + if (!empty) + throw new InternalError(); + System.err.println("checkEmpty suceeded!"); + } + + void setStaticCodes(short[] stCodes, byte[] stLength) + { + codes = stCodes; + length = stLength; + } + + public void buildCodes() { + int[] nextCode = new int[maxLength]; + int code = 0; + codes = new short[freqs.length]; + + if (DeflaterConstants.DEBUGGING) + System.err.println("buildCodes: "+freqs.length); + for (int bits = 0; bits < maxLength; bits++) + { + nextCode[bits] = code; + code += bl_counts[bits] << (15 - bits); + if (DeflaterConstants.DEBUGGING) + System.err.println("bits: "+(bits+1)+" count: "+bl_counts[bits] + +" nextCode: "+Integer.toHexString(code)); + } + if (DeflaterConstants.DEBUGGING && code != 65536) + throw new RuntimeException("Inconsistent bl_counts!"); + + for (int i=0; i < numCodes; i++) + { + int bits = length[i]; + if (bits > 0) + { + if (DeflaterConstants.DEBUGGING) + System.err.println("codes["+i+"] = rev(" + +Integer.toHexString(nextCode[bits-1])+")," + +bits); + codes[i] = bitReverse(nextCode[bits-1]); + nextCode[bits-1] += 1 << (16 - bits); + } + } + } + + private void buildLength(int childs[]) + { + this.length = new byte [freqs.length]; + int numNodes = childs.length / 2; + int numLeafs = (numNodes + 1) / 2; + int overflow = 0; + + for (int i = 0; i < maxLength; i++) + bl_counts[i] = 0; + + /* First calculate optimal bit lengths */ + int lengths[] = new int[numNodes]; + lengths[numNodes-1] = 0; + for (int i = numNodes - 1; i >= 0; i--) + { + if (childs[2*i+1] != -1) + { + int bitLength = lengths[i] + 1; + if (bitLength > maxLength) + { + bitLength = maxLength; + overflow++; + } + lengths[childs[2*i]] = lengths[childs[2*i+1]] = bitLength; + } + else + { + /* A leaf node */ + int bitLength = lengths[i]; + bl_counts[bitLength - 1]++; + this.length[childs[2*i]] = (byte) lengths[i]; + } + } + + if (DeflaterConstants.DEBUGGING) + { + System.err.println("Tree "+freqs.length+" lengths:"); + for (int i=0; i < numLeafs; i++) + System.err.println("Node "+childs[2*i]+" freq: "+freqs[childs[2*i]] + + " len: "+length[childs[2*i]]); + } + + if (overflow == 0) + return; + + int incrBitLen = maxLength - 1; + do + { + /* Find the first bit length which could increase: */ + while (bl_counts[--incrBitLen] == 0) + ; + + /* Move this node one down and remove a corresponding + * amount of overflow nodes. + */ + do + { + bl_counts[incrBitLen]--; + bl_counts[++incrBitLen]++; + overflow -= 1 << (maxLength - 1 - incrBitLen); + } + while (overflow > 0 && incrBitLen < maxLength - 1); + } + while (overflow > 0); + + /* We may have overshot above. Move some nodes from maxLength to + * maxLength-1 in that case. + */ + bl_counts[maxLength-1] += overflow; + bl_counts[maxLength-2] -= overflow; + + /* Now recompute all bit lengths, scanning in increasing + * frequency. It is simpler to reconstruct all lengths instead of + * fixing only the wrong ones. This idea is taken from 'ar' + * written by Haruhiko Okumura. + * + * The nodes were inserted with decreasing frequency into the childs + * array. + */ + int nodePtr = 2 * numLeafs; + for (int bits = maxLength; bits != 0; bits--) + { + int n = bl_counts[bits-1]; + while (n > 0) + { + int childPtr = 2*childs[nodePtr++]; + if (childs[childPtr + 1] == -1) + { + /* We found another leaf */ + length[childs[childPtr]] = (byte) bits; + n--; + } + } + } + if (DeflaterConstants.DEBUGGING) + { + System.err.println("*** After overflow elimination. ***"); + for (int i=0; i < numLeafs; i++) + System.err.println("Node "+childs[2*i]+" freq: "+freqs[childs[2*i]] + + " len: "+length[childs[2*i]]); + } + } + + void buildTree() + { + int numSymbols = freqs.length; + + /* heap is a priority queue, sorted by frequency, least frequent + * nodes first. The heap is a binary tree, with the property, that + * the parent node is smaller than both child nodes. This assures + * that the smallest node is the first parent. + * + * The binary tree is encoded in an array: 0 is root node and + * the nodes 2*n+1, 2*n+2 are the child nodes of node n. + */ + int[] heap = new int[numSymbols]; + int heapLen = 0; + int maxCode = 0; + for (int n = 0; n < numSymbols; n++) + { + int freq = freqs[n]; + if (freq != 0) + { + /* Insert n into heap */ + int pos = heapLen++; + int ppos; + while (pos > 0 && + freqs[heap[ppos = (pos - 1) / 2]] > freq) { + heap[pos] = heap[ppos]; + pos = ppos; + } + heap[pos] = n; + maxCode = n; + } + } + + /* We could encode a single literal with 0 bits but then we + * don't see the literals. Therefore we force at least two + * literals to avoid this case. We don't care about order in + * this case, both literals get a 1 bit code. + */ + while (heapLen < 2) + { + int node = maxCode < 2 ? ++maxCode : 0; + heap[heapLen++] = node; + } + + numCodes = Math.max(maxCode + 1, minNumCodes); + + int numLeafs = heapLen; + int[] childs = new int[4*heapLen - 2]; + int[] values = new int[2*heapLen - 1]; + int numNodes = numLeafs; + for (int i = 0; i < heapLen; i++) + { + int node = heap[i]; + childs[2*i] = node; + childs[2*i+1] = -1; + values[i] = freqs[node] << 8; + heap[i] = i; + } + + /* Construct the Huffman tree by repeatedly combining the least two + * frequent nodes. + */ + do + { + int first = heap[0]; + int last = heap[--heapLen]; + + /* Propagate the hole to the leafs of the heap */ + int ppos = 0; + int path = 1; + while (path < heapLen) + { + if (path + 1 < heapLen + && values[heap[path]] > values[heap[path+1]]) + path++; + + heap[ppos] = heap[path]; + ppos = path; + path = path * 2 + 1; + } + + /* Now propagate the last element down along path. Normally + * it shouldn't go too deep. + */ + int lastVal = values[last]; + while ((path = ppos) > 0 + && values[heap[ppos = (path - 1)/2]] > lastVal) + heap[path] = heap[ppos]; + heap[path] = last; + + + int second = heap[0]; + + /* Create a new node father of first and second */ + last = numNodes++; + childs[2*last] = first; + childs[2*last+1] = second; + int mindepth = Math.min(values[first] & 0xff, values[second] & 0xff); + values[last] = lastVal = values[first] + values[second] - mindepth + 1; + + /* Again, propagate the hole to the leafs */ + ppos = 0; + path = 1; + while (path < heapLen) + { + if (path + 1 < heapLen + && values[heap[path]] > values[heap[path+1]]) + path++; + + heap[ppos] = heap[path]; + ppos = path; + path = ppos * 2 + 1; + } + + /* Now propagate the new element down along path */ + while ((path = ppos) > 0 + && values[heap[ppos = (path - 1)/2]] > lastVal) + heap[path] = heap[ppos]; + heap[path] = last; + } + while (heapLen > 1); + + if (heap[0] != childs.length / 2 - 1) + throw new RuntimeException("Weird!"); + + buildLength(childs); + } + + int getEncodedLength() + { + int len = 0; + for (int i = 0; i < freqs.length; i++) + len += freqs[i] * length[i]; + return len; + } + + void calcBLFreq(Tree blTree) { + int max_count; /* max repeat count */ + int min_count; /* min repeat count */ + int count; /* repeat count of the current code */ + int curlen = -1; /* length of current code */ + + int i = 0; + while (i < numCodes) + { + count = 1; + int nextlen = length[i]; + if (nextlen == 0) + { + max_count = 138; + min_count = 3; + } + else + { + max_count = 6; + min_count = 3; + if (curlen != nextlen) + { + blTree.freqs[nextlen]++; + count = 0; + } + } + curlen = nextlen; + i++; + + while (i < numCodes && curlen == length[i]) + { + i++; + if (++count >= max_count) + break; + } + + if (count < min_count) + blTree.freqs[curlen] += count; + else if (curlen != 0) + blTree.freqs[REP_3_6]++; + else if (count <= 10) + blTree.freqs[REP_3_10]++; + else + blTree.freqs[REP_11_138]++; + } + } + + void writeTree(Tree blTree) + { + int max_count; /* max repeat count */ + int min_count; /* min repeat count */ + int count; /* repeat count of the current code */ + int curlen = -1; /* length of current code */ + + int i = 0; + while (i < numCodes) + { + count = 1; + int nextlen = length[i]; + if (nextlen == 0) + { + max_count = 138; + min_count = 3; + } + else + { + max_count = 6; + min_count = 3; + if (curlen != nextlen) + { + blTree.writeSymbol(nextlen); + count = 0; + } + } + curlen = nextlen; + i++; + + while (i < numCodes && curlen == length[i]) + { + i++; + if (++count >= max_count) + break; + } + + if (count < min_count) + { + while (count-- > 0) + blTree.writeSymbol(curlen); + } + else if (curlen != 0) + { + blTree.writeSymbol(REP_3_6); + pending.writeBits(count - 3, 2); + } + else if (count <= 10) + { + blTree.writeSymbol(REP_3_10); + pending.writeBits(count - 3, 3); + } + else + { + blTree.writeSymbol(REP_11_138); + pending.writeBits(count - 11, 7); + } + } + } + } + + + + DeflaterPending pending; + private Tree literalTree, distTree, blTree; + + private short d_buf[]; + private byte l_buf[]; + private int last_lit; + private int extra_bits; + + private static short staticLCodes[]; + private static byte staticLLength[]; + private static short staticDCodes[]; + private static byte staticDLength[]; + + /** + * Reverse the bits of a 16 bit value. + */ + static short bitReverse(int value) { + return (short) (bit4Reverse.charAt(value & 0xf) << 12 + | bit4Reverse.charAt((value >> 4) & 0xf) << 8 + | bit4Reverse.charAt((value >> 8) & 0xf) << 4 + | bit4Reverse.charAt(value >> 12)); + } + + static { + /* See RFC 1951 3.2.6 */ + /* Literal codes */ + staticLCodes = new short[LITERAL_NUM]; + staticLLength = new byte[LITERAL_NUM]; + int i = 0; + while (i < 144) { + staticLCodes[i] = bitReverse((0x030 + i) << 8); + staticLLength[i++] = 8; + } + while (i < 256) { + staticLCodes[i] = bitReverse((0x190 - 144 + i) << 7); + staticLLength[i++] = 9; + } + while (i < 280) { + staticLCodes[i] = bitReverse((0x000 - 256 + i) << 9); + staticLLength[i++] = 7; + } + while (i < LITERAL_NUM) { + staticLCodes[i] = bitReverse((0x0c0 - 280 + i) << 8); + staticLLength[i++] = 8; + } + + /* Distant codes */ + staticDCodes = new short[DIST_NUM]; + staticDLength = new byte[DIST_NUM]; + for (i = 0; i < DIST_NUM; i++) { + staticDCodes[i] = bitReverse(i << 11); + staticDLength[i] = 5; + } + } + + public DeflaterHuffman(DeflaterPending pending) + { + this.pending = pending; + + literalTree = new Tree(LITERAL_NUM, 257, 15); + distTree = new Tree(DIST_NUM, 1, 15); + blTree = new Tree(BITLEN_NUM, 4, 7); + + d_buf = new short[BUFSIZE]; + l_buf = new byte [BUFSIZE]; + } + + public final void reset() { + last_lit = 0; + extra_bits = 0; + literalTree.reset(); + distTree.reset(); + blTree.reset(); + } + + private int l_code(int len) { + if (len == 255) + return 285; + + int code = 257; + while (len >= 8) + { + code += 4; + len >>= 1; + } + return code + len; + } + + private int d_code(int distance) { + int code = 0; + while (distance >= 4) + { + code += 2; + distance >>= 1; + } + return code + distance; + } + + public void sendAllTrees(int blTreeCodes) { + blTree.buildCodes(); + literalTree.buildCodes(); + distTree.buildCodes(); + pending.writeBits(literalTree.numCodes - 257, 5); + pending.writeBits(distTree.numCodes - 1, 5); + pending.writeBits(blTreeCodes - 4, 4); + for (int rank = 0; rank < blTreeCodes; rank++) + pending.writeBits(blTree.length[BL_ORDER[rank]], 3); + literalTree.writeTree(blTree); + distTree.writeTree(blTree); + if (DeflaterConstants.DEBUGGING) + blTree.checkEmpty(); + } + + public void compressBlock() { + for (int i = 0; i < last_lit; i++) + { + int litlen = l_buf[i] & 0xff; + int dist = d_buf[i]; + if (dist-- != 0) + { + if (DeflaterConstants.DEBUGGING) + System.err.print("["+(dist+1)+","+(litlen+3)+"]: "); + + int lc = l_code(litlen); + literalTree.writeSymbol(lc); + + int bits = (lc - 261) / 4; + if (bits > 0 && bits <= 5) + pending.writeBits(litlen & ((1 << bits) - 1), bits); + + int dc = d_code(dist); + distTree.writeSymbol(dc); + + bits = dc / 2 - 1; + if (bits > 0) + pending.writeBits(dist & ((1 << bits) - 1), bits); + } + else + { + if (DeflaterConstants.DEBUGGING) + { + if (litlen > 32 && litlen < 127) + System.err.print("("+(char)litlen+"): "); + else + System.err.print("{"+litlen+"}: "); + } + literalTree.writeSymbol(litlen); + } + } + if (DeflaterConstants.DEBUGGING) + System.err.print("EOF: "); + literalTree.writeSymbol(EOF_SYMBOL); + if (DeflaterConstants.DEBUGGING) + { + literalTree.checkEmpty(); + distTree.checkEmpty(); + } + } + + public void flushStoredBlock(byte[] stored, + int stored_offset, int stored_len, + boolean lastBlock) { + if (DeflaterConstants.DEBUGGING) + System.err.println("Flushing stored block "+ stored_len); + pending.writeBits((DeflaterConstants.STORED_BLOCK << 1) + + (lastBlock ? 1 : 0), 3); + pending.alignToByte(); + pending.writeShort(stored_len); + pending.writeShort(~stored_len); + pending.writeBlock(stored, stored_offset, stored_len); + reset(); + } + + public void flushBlock(byte[] stored, int stored_offset, int stored_len, + boolean lastBlock) { + literalTree.freqs[EOF_SYMBOL]++; + + /* Build trees */ + literalTree.buildTree(); + distTree.buildTree(); + + /* Calculate bitlen frequency */ + literalTree.calcBLFreq(blTree); + distTree.calcBLFreq(blTree); + + /* Build bitlen tree */ + blTree.buildTree(); + + int blTreeCodes = 4; + for (int i = 18; i > blTreeCodes; i--) + { + if (blTree.length[BL_ORDER[i]] > 0) + blTreeCodes = i+1; + } + int opt_len = 14 + blTreeCodes * 3 + blTree.getEncodedLength() + + literalTree.getEncodedLength() + distTree.getEncodedLength() + + extra_bits; + + int static_len = extra_bits; + for (int i = 0; i < LITERAL_NUM; i++) + static_len += literalTree.freqs[i] * staticLLength[i]; + for (int i = 0; i < DIST_NUM; i++) + static_len += distTree.freqs[i] * staticDLength[i]; + if (opt_len >= static_len) + { + /* Force static trees */ + opt_len = static_len; + } + + if (stored_offset >= 0 && stored_len+4 < opt_len >> 3) + { + /* Store Block */ + if (DeflaterConstants.DEBUGGING) + System.err.println("Storing, since " + stored_len + " < " + opt_len + + " <= " + static_len); + flushStoredBlock(stored, stored_offset, stored_len, lastBlock); + } + else if (opt_len == static_len) + { + /* Encode with static tree */ + pending.writeBits((DeflaterConstants.STATIC_TREES << 1) + + (lastBlock ? 1 : 0), 3); + literalTree.setStaticCodes(staticLCodes, staticLLength); + distTree.setStaticCodes(staticDCodes, staticDLength); + compressBlock(); + reset(); + } + else + { + /* Encode with dynamic tree */ + pending.writeBits((DeflaterConstants.DYN_TREES << 1) + + (lastBlock ? 1 : 0), 3); + sendAllTrees(blTreeCodes); + compressBlock(); + reset(); + } + } + + public final boolean isFull() + { + return last_lit == BUFSIZE; + } + + public final boolean tallyLit(int lit) + { + if (DeflaterConstants.DEBUGGING) + { + if (lit > 32 && lit < 127) + System.err.println("("+(char)lit+")"); + else + System.err.println("{"+lit+"}"); + } + d_buf[last_lit] = 0; + l_buf[last_lit++] = (byte) lit; + literalTree.freqs[lit]++; + return last_lit == BUFSIZE; + } + + public final boolean tallyDist(int dist, int len) + { + if (DeflaterConstants.DEBUGGING) + System.err.println("["+dist+","+len+"]"); + + d_buf[last_lit] = (short) dist; + l_buf[last_lit++] = (byte) (len - 3); + + int lc = l_code(len-3); + literalTree.freqs[lc]++; + if (lc >= 265 && lc < 285) + extra_bits += (lc - 261) / 4; + + int dc = d_code(dist-1); + distTree.freqs[dc]++; + if (dc >= 4) + extra_bits += dc / 2 - 1; + return last_lit == BUFSIZE; + } +} |