Project Tool

using System;
using System.Collections.Generic;
using System.Text;
using System.IO;
using QiHe.CodeLib.Compress.DeflateFormat;

namespace QiHe.CodeLib.Compress
{
    public partial class Deflate
    {
        public static byte[] Decompress(byte[] compressed)
        {
            MemoryStream input = new MemoryStream(compressed);
            MemoryStream output = new MemoryStream();
            Decompress(input, output);
            return output.ToArray();
        }

        public static void Decompress(Stream input, Stream output)
        {
            Decode(new BitStream(input), new BitStream(output));
        }

        private static void Decode(BitStream input, BitStream output)
        {
            //decode blocks
            bool isFinalBlock = false;
            while (!isFinalBlock)
            {
                //read block header from input stream
                isFinalBlock = Convert.ToBoolean(input.ReadBit());
                BlockType blockType = (BlockType)input.ReadBits(2);

                //decompress block
                switch (blockType)
                {
                    case BlockType.NoCompression:
                        DecodeUncompressedBlock(input, output);
                        break;
                    case BlockType.FixedHuffmanCodes:
                        DecodeCompressedBlock(input, output, HuffmanCodes.Default);
                        break;
                    case BlockType.DynamicHuffmanCodes:
                        HuffmanCodes huffmanCodes = HuffmanCodes.Decode(input);
                        DecodeCompressedBlock(input, output, huffmanCodes);
                        break;
                    default:
                        throw new Exception("Unknown block type " + blockType);
                }
            }
            input.Flush();
            output.Flush();
        }

        private static void DecodeUncompressedBlock(BitStream input, BitStream output)
        {
            //Any bits of input up to the next byte boundary are ignored.
            input.GotoNextByte();

            //read length and nlength
            UInt16 length = input.ReadUInt16();
            UInt16 nlength = input.ReadUInt16();
            if (nlength != Bits.Not(length))
            {
                throw new Exception("Error in decode block length");
            }

            //copy length bytes of data to output
            byte[] data = input.ReadBytes(length);
            output.WriteBytes(data);
        }

        private static void DecodeCompressedBlock(BitStream input, BitStream output, HuffmanCodes huffmanCodes)
        {
            while (true)
            {
                int symbol = huffmanCodes.ReadLiteralOrLength(input);
                if (symbol >= 0 && symbol < 256) //literal byte
                {
                    output.WriteByte((byte)symbol);
                }
                else if (symbol == 256) //end of block
                {
                    break;
                }
                else if (symbol >= 257 && symbol <= 285) //length code
                {
                    int length = DecodeSymbol(input, symbol, DeflateCoding.Length);
                    int distance = DecodeSymbol(input, huffmanCodes.ReadDistance(input), DeflateCoding.Distance);
                    CopyBytes(output, distance, length);
                }
                else
                {
                    throw new Exception("Invalid literal/length value");
                }
            }
        }

        /// <summary>
        /// Move backwards distance bytes in the output stream, 
        /// and copy length bytes from this position to the output stream.
        /// A distance cannot refer past the beginning of the output,
        /// however the referenced string may overlap the current position.
        /// </summary>
        /// <param name="output">output stream</param>
        /// <param name="distance">backward distance</param>
        /// <param name="length">length bytes to copy</param>
        private static void CopyBytes(BitStream output, int distance, int length)
        {
            long offset = output.Position - distance;
            byte[] data = output.PeekBytes(offset, length);
            if (data.Length < length)
            {
                int times = length / data.Length;
                int remain = length % data.Length;
                for (int t = 0; t < times; t++)
                {
                    output.WriteBytes(data);
                }
                if (remain > 0)
                {
                    output.WriteBytes(data, 0, remain);
                }
            }
            else
            {
                output.WriteBytes(data);
            }
        }

        private static int DecodeSymbol(BitStream input, int symbol, SymbolCoding coding)
        {
            int value = coding.GetSymbolBase(symbol);
            int extraBits = coding.GetSymbolExtrabits(symbol);
            if (extraBits > 0)
            {
                value += input.ReadBits(extraBits);
            }
            return value;
        }
    }
}