using System;
using System.Collections.Generic;
using System.Text;
using System.IO;
namespace QiHe.CodeLib.Compress.DeflateFormat
{
public partial class HuffmanCodes
{
public HuffmanCodes(MultiSet<int> alphabetSet, MultiSet<int> distanceSet)
{
AlphabetHuffmanCode = HuffmanTree.FromSymbolWeights(alphabetSet, 15);
DistanceHuffmanCode = HuffmanTree.FromSymbolWeights(distanceSet, 15);
}
public void WriteLiteral(BitStream output, int symbol)
{
AlphabetHuffmanCode.WriteSymbol(output, symbol);
}
public void WriteLength(BitStream output, int length)
{
SymbolCode lengthCode = DeflateCoding.Length[length];
AlphabetHuffmanCode.WriteSymbol(output, lengthCode.Code);
output.WriteBits(lengthCode.Offset, lengthCode.ExtraBits);
}
public void WriteDistance(BitStream output, int distance)
{
SymbolCode distanceCode = DeflateCoding.Distance[distance];
DistanceHuffmanCode.WriteSymbol(output, distanceCode.Code);
output.WriteBits(distanceCode.Offset, distanceCode.ExtraBits);
}
public void Encode(BitStream output)
{
List<Pair<int, int>> alphabetCodeItems = EncodeCodeLengths(AlphabetHuffmanCode.CodeLengths);
List<Pair<int, int>> distanceCodeItems = EncodeCodeLengths(DistanceHuffmanCode.CodeLengths);
MultiSet<int> lengthCodeSet = new MultiSet<int>();
FillSet(lengthCodeSet, alphabetCodeItems);
FillSet(lengthCodeSet, distanceCodeItems);
HuffmanTree CodeLengthHuffmanCode = HuffmanTree.FromSymbolWeights(lengthCodeSet, 7);
int NumberOfLiteralLengthCodes = AlphabetHuffmanCode.CodeLengths.Length;
int NumberOfDistanceCodes = DistanceHuffmanCode.CodeLengths.Length;
int NumberOfCodeLengthCodes = CountCodeLengths(CodeLengthHuffmanCode.CodeLengths);
output.WriteBits(NumberOfLiteralLengthCodes - 257, 5);
output.WriteBits(NumberOfDistanceCodes - 1, 5);
output.WriteBits(NumberOfCodeLengthCodes - 4, 4);
for (int i = 0; i < NumberOfCodeLengthCodes; i++)
{
int len = GetCodeLength(CodeLengthHuffmanCode.CodeLengths, i);
//if (len > 7)
//{
// throw new Exception("Deflate Huffman code length's code length can not exceeds 7.");
//}
output.WriteBits(len, 3);
}
WriteCodeLengths(output, alphabetCodeItems, CodeLengthHuffmanCode);
WriteCodeLengths(output, distanceCodeItems, CodeLengthHuffmanCode);
}
public int CalculateHeaderSize()
{
MemoryStream memStream = new MemoryStream();
BitStream bitStream = new BitStream(memStream);
Encode(bitStream);
return (int)bitStream.Length * 8 + bitStream.bitsWritten;
}
public int CalculateBlockSize()
{
int headerSize = CalculateHeaderSize();
int wpl = AlphabetHuffmanCode.WeightedPathLength + DistanceHuffmanCode.WeightedPathLength;
return headerSize + wpl;
}
public int CalculateDefaultBlockSize()
{
int wpl = HuffmanTree.CalculateWeightedPathLength(AlphabetHuffmanCode.SymbolWeights, HuffmanCodes.Default.AlphabetHuffmanCode.CodeLengths)
+ HuffmanTree.CalculateWeightedPathLength(DistanceHuffmanCode.SymbolWeights, HuffmanCodes.Default.DistanceHuffmanCode.CodeLengths);
return wpl;
}
private static void WriteCodeLengths(BitStream output, List<Pair<int, int>> codeItems, HuffmanTree CodeLengthHuffmanCode)
{
foreach (Pair<int, int> pair in codeItems)
{
if (pair.Left < 16)
{
for (int i = 0; i < pair.Right; i++)
{
CodeLengthHuffmanCode.WriteSymbol(output, pair.Left);
}
}
else
{
CodeLengthHuffmanCode.WriteSymbol(output, pair.Left);
switch (pair.Left)
{
case 16:
output.WriteBits(pair.Right - 3, 2);
break;
case 17:
output.WriteBits(pair.Right - 3, 3);
break;
case 18:
output.WriteBits(pair.Right - 11, 7);
break;
}
}
}
}
private static int GetCodeLength(int[] codeLengths, int index)
{
int code = CodeLengthOrder[index];
if (code > codeLengths.Length - 1)
{
return 0;
}
else
{
return codeLengths[code];
}
}
private static int CountCodeLengths(int[] codeLengths)
{
int zeroCount = 0;
int codeCount = CodeLengthOrder.Length;
for (int i = codeCount - 1; i >= 0; i--)
{
int len = GetCodeLength(codeLengths, i);
if (len == 0)
{
zeroCount++;
}
else
{
break;
}
}
return codeCount - zeroCount;
}
private static void FillSet(MultiSet<int> lengthCodeSet, List<Pair<int, int>> codeItems)
{
foreach (Pair<int, int> pair in codeItems)
{
if (pair.Left < 16)
{
lengthCodeSet.AddOccur(pair.Left, pair.Right);
}
else
{
lengthCodeSet.Add(pair.Left);
}
}
}
private static List<Pair<int, int>> EncodeCodeLengths(int[] codeLengths)
{
List<Pair<int, int>> items = RunLengthEncoding.Analyze<int>(codeLengths);
List<Pair<int, int>> codeItems = new List<Pair<int, int>>();
foreach (Pair<int, int> pair in items)
{
if (pair.Left == 0)
{
HandleRepeatedZero(codeItems, pair.Right);
}
else
{
codeItems.Add(new Pair<int, int>(pair.Left, 1));
HandleRepeatedCode(codeItems, pair.Left, pair.Right - 1);
}
}
return codeItems;
}
private static void HandleRepeatedCode(List<Pair<int, int>> codeItems, int item, int times)
{
if (times == 0)
{
return;
}
else if (times < 3)
{
codeItems.Add(new Pair<int, int>(item, times));
}
else if (times >= 3 && times <= 6)
{
codeItems.Add(new Pair<int, int>(16, times));
}
else
{
codeItems.Add(new Pair<int, int>(16, 6));
HandleRepeatedCode(codeItems, item, times - 6);
}
}
private static void HandleRepeatedZero(List<Pair<int, int>> codeItems, int zeroCount)
{
if (zeroCount < 3)
{
codeItems.Add(new Pair<int, int>(0, zeroCount));
}
else if (zeroCount >= 3 && zeroCount <= 10)
{
codeItems.Add(new Pair<int, int>(17, zeroCount));
}
else if (zeroCount >= 11 && zeroCount <= 138)
{
codeItems.Add(new Pair<int, int>(18, zeroCount));
}
else
{
codeItems.Add(new Pair<int, int>(18, 138));
HandleRepeatedZero(codeItems, zeroCount - 138);
}
}
}
}