Click here to Skip to main content
Click here to Skip to main content
Articles » Languages » C# » Utilities » Downloads
 
Add your own
alternative version
Go to top

Project Tool

, 23 Sep 2007
Backup your C# solution and projects for archive or source code sharing. Temporary or unused files are excluded.
projecttool.zip
ProjectTool.exe
projecttool_0908_.zip
bin
Release
ICSharpCode.SharpZipLib.dll
ProjectTool.exe
CodeLib
Controls
ProjectTool
Items
Project
Propertys
Solution
Icon
cs.png
default.ico
dir.png
diro.png
dll.png
projecttool_20070924.zip
ProjectTool.exe
Checksums
Compress
Deflate
Common
Decode
Encode
Formats
Zip
HuffmanCoding
LempelZivWelch
LempelZiv
Resources
Icon
cs.png
default.ico
dir.png
diro.png
dll.png
projecttool_src.zip
ProjectTool.exe
cs.png
default.ico
dir.png
diro.png
dll.png
release.zip
ICSharpCode.SharpZipLib.dll
ProjectTool.exe
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);
            }
        }
    }
}

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Liu Junfeng
Software Developer (Senior) Beyondsoft SH
China China
No Biography provided

| Advertise | Privacy | Mobile
Web04 | 2.8.140921.1 | Last Updated 23 Sep 2007
Article Copyright 2006 by Liu Junfeng
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid