deflaterhuffman.cs

SharpZipLib之前叫做NZipLib

// DeflaterHuffman.cs
//
// Copyright (C) 2001 Mike Krueger
// Copyright (C) 2004 John Reilly
//
// This file was translated from java, it was part of the GNU Classpath
// Copyright (C) 2001 Free Software Foundation, Inc.
//
// This program 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
// of the License, or (at your option) any later version.
//
// This program 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 this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, 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.

using System;

namespace ICSharpCode.SharpZipLib.Zip.Compression 
{
	
	/// <summary>
	/// 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 of the original java version : Jochen Hoenicke
	/// </summary>
	public class DeflaterHuffman
	{
		const  int BUFSIZE = 1 << (DeflaterConstants.DEFAULT_MEM_LEVEL + 6);
		const  int LITERAL_NUM = 286;

		// Number of distance codes
		const  int DIST_NUM = 30;
		// Number of codes used to transfer bit lengths
		const  int BITLEN_NUM = 19;

		// repeat previous bit length 3-6 times (2 bits of repeat count)
		const  int REP_3_6    = 16;
		// repeat a zero length 3-10 times  (3 bits of repeat count)
		const  int REP_3_10   = 17;
		// repeat a zero length 11-138 times  (7 bits of repeat count)
		const  int REP_11_138 = 18;

		const  int EOF_SYMBOL = 256;

		// The lengths of the bit length codes are sent in order of decreasing
 		// probability, to avoid transmitting the lengths for unused bit length codes.
		static readonly int[] BL_ORDER = { 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 };
		
		static readonly byte[] bit4Reverse = {
			0,
			8,
			4,
			12,
			2,
			10,
			6,
			14,
			1,
			9,
			5,
			13,
			3,
			11,
			7,
			15
		};

		static short[] staticLCodes;
		static byte[]  staticLLength;
		static short[] staticDCodes;
		static byte[]  staticDLength;
		
		class Tree 
		{
			#region Instance Fields
			public short[] freqs;
			
			public byte[]  length;
			
			public int     minNumCodes;
			
			public int     numCodes;
			
			short[] codes;
			int[]   bl_counts;
			int     maxLength;
			DeflaterHuffman dh;
			#endregion

			#region Constructors
			public Tree(DeflaterHuffman dh, int elems, int minCodes, int maxLength) 
			{
				this.dh =  dh;
				this.minNumCodes = minCodes;
				this.maxLength  = maxLength;
				freqs  = new short[elems];
				bl_counts = new int[maxLength];
			}
			
			#endregion

			/// <summary>
			/// Resets the internal state of the tree
			/// </summary>
			public void Reset() 
			{
				for (int i = 0; i < freqs.Length; i++) {
					freqs[i] = 0;
				}
				codes = null;
				length = null;
			}
			
			public void WriteSymbol(int code)
			{
				//				if (DeflaterConstants.DEBUGGING) {
				//					freqs[code]--;
				//					//  	  Console.Write("writeSymbol("+freqs.length+","+code+"): ");
				//				}
				dh.pending.WriteBits(codes[code] & 0xffff, length[code]);
			}
			
			/// <summary>
			/// Check that all frequencies are zero
			/// </summary>
			/// <exception cref="SharpZipBaseException">
			/// At least one frequency is non-zero
			/// </exception>
			public void CheckEmpty()
			{
				bool empty = true;
				for (int i = 0; i < freqs.Length; i++) {
					if (freqs[i] != 0) {
						//Console.WriteLine("freqs[" + i + "] == " + freqs[i]);
						empty = false;
					}
				}
				
				if (!empty) {
					throw new SharpZipBaseException("!Empty");
				}
			}

			/// <summary>
			/// Set static codes and length
			/// </summary>
			/// <param name="staticCodes">new codes</param>
			/// <param name="staticLengths">length for new codes</param>
			public void SetStaticCodes(short[] staticCodes, byte[] staticLengths)
			{
				codes = staticCodes;
				length = staticLengths;
			}
			
			/// <summary>
			/// Build dynamic codes and lengths
			/// </summary>
			public void BuildCodes() 
			{
				int numSymbols = freqs.Length;
				int[] nextCode = new int[maxLength];
				int code = 0;

				codes = new short[freqs.Length];
				
				//				if (DeflaterConstants.DEBUGGING) {
				//					//Console.WriteLine("buildCodes: "+freqs.Length);
				//				}
				
				for (int bits = 0; bits < maxLength; bits++) {
					nextCode[bits] = code;
					code += bl_counts[bits] << (15 - bits);

					//					if (DeflaterConstants.DEBUGGING) {
					//						//Console.WriteLine("bits: " + ( bits + 1) + " count: " + bl_counts[bits]
					//						                  +" nextCode: "+code);
					//					}
				}

#if DebugDeflation
				if ( DeflaterConstants.DEBUGGING && (code != 65536) ) 
				{
					throw new SharpZipBaseException("Inconsistent bl_counts!");
				}
#endif				
				for (int i=0; i < numCodes; i++) {
					int bits = length[i];
					if (bits > 0) {

						//						if (DeflaterConstants.DEBUGGING) {
						//								//Console.WriteLine("codes["+i+"] = rev(" + nextCode[bits-1]+"),
						//								                  +bits);
						//						}

						codes[i] = BitReverse(nextCode[bits-1]);
						nextCode[bits-1] += 1 << (16 - bits);
					}
				}
			}
			
			public 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 SharpZipBaseException("Heap invariant violated");
				}
				
				BuildLength(childs);
			}
			
			/// <summary>
			/// Get encoded length
			/// </summary>
			/// <returns>Encoded length, the sum of frequencies * lengths</returns>
			public int GetEncodedLength()
			{
				int len = 0;
				for (int i = 0; i < freqs.Length; i++) {
					len += freqs[i] * length[i];
				}
				return len;
			}
			
			/// <summary>
			/// Scan a literal or distance tree to determine the frequencies of the codes
			/// in the bit length tree.
			/// </summary>
			public 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] += (short)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]++;
					}
				}
			}
		
			/// <summary>
			/// Write tree values
			/// </summary>
			/// <param name="blTree">Tree to write</param>
			public 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);
						dh.pending.WriteBits(count - 3, 2);