📄 deflaterhuffman.cs
字号:
// 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 Fireball.IO.Compression.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
{
static int BUFSIZE = 1 << (DeflaterConstants.DEFAULT_MEM_LEVEL + 6);
static int LITERAL_NUM = 286;
static int DIST_NUM = 30;
static int BITLEN_NUM = 19;
static int REP_3_6 = 16;
static int REP_3_10 = 17;
static int REP_11_138 = 18;
static int EOF_SYMBOL = 256;
static int[] BL_ORDER = { 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 };
static byte[] bit4Reverse = {
0,
8,
4,
12,
2,
10,
6,
14,
1,
9,
5,
13,
3,
11,
7,
15
};
/// <summary>
/// Not documented
/// </summary>
public class Tree
{
/// <summary>
/// Not documented
/// </summary>
public short[] freqs;
/// <summary>
/// Not documented
/// </summary>
public byte[] length;
/// <summary>
/// Not documented
/// </summary>
public int minNumCodes;
/// <summary>
/// Not documented
/// </summary>
public int numCodes;
short[] codes;
int[] bl_counts;
int maxLength;
DeflaterHuffman dh;
/// <summary>
/// Not documented
/// </summary>
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];
}
/// <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;
}
/// <summary>
/// Not documented
/// </summary>
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 at least one frequency is non-zero
/// </summary>
/// <exception cref="SharpZipBaseException">
/// No frequencies are 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");
}
//Console.WriteLine("checkEmpty suceeded!");
}
/// <summary>
/// Set static codes and length
/// </summary>
/// <param name="stCodes">new codes</param>
/// <param name="stLength">length for new codes</param>
public void SetStaticCodes(short[] stCodes, byte[] stLength)
{
codes = stCodes;
length = stLength;
}
/// <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 (DeflaterConstants.DEBUGGING && code != 65536)
{
throw new SharpZipBaseException("Inconsistent bl_counts!");
}
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);
}
}
}
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) {
// //Console.WriteLine("Tree "+freqs.Length+" lengths:");
// for (int i=0; i < numLeafs; i++) {
// //Console.WriteLine("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--;
}
}
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -