huffmancodes.cs

PDF文件格式解析库源代码

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);
            }
        }
    }
}