📄 deflaterhuffman.cs
字号:
// if (DeflaterConstants.DEBUGGING) {
// //Console.WriteLine("*** After overflow elimination. ***");
// for (int i=0; i < numLeafs; i++) {
// //Console.WriteLine("Node "+childs[2*i]+" freq: "+freqs[childs[2*i]]
// + " len: "+length[childs[2*i]]);
// }
// }
}
/// <summary>
/// Not documented
/// </summary>
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>
/// Not documented
/// </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);
}
else if (count <= 10)
{
blTree.WriteSymbol(REP_3_10);
dh.pending.WriteBits(count - 3, 3);
}
else
{
blTree.WriteSymbol(REP_11_138);
dh.pending.WriteBits(count - 11, 7);
}
}
}
}
/// <summary>
/// Pending buffer to use
/// </summary>
public DeflaterPending pending;
Tree literalTree, distTree, blTree;
short[] d_buf;
byte[] l_buf;
int last_lit;
int extra_bits;
static short[] staticLCodes;
static byte[] staticLLength;
static short[] staticDCodes;
static byte[] staticDLength;
/// <summary>
/// Reverse the bits of a 16 bit value.
/// </summary>
/// <param name="toReverse">Value to reverse bits</param>
/// <returns>Value with bits reversed</returns>
public static short BitReverse(int toReverse)
{
return (short)(bit4Reverse[toReverse & 0xF] << 12 |
bit4Reverse[(toReverse >> 4) & 0xF] << 8 |
bit4Reverse[(toReverse >> 8) & 0xF] << 4 |
bit4Reverse[toReverse >> 12]);
}
static DeflaterHuffman()
{
/* See RFC 1951 3.2.6 */
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -