lzw_decode.cs

PDF文件格式解析库源代码

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

namespace QiHe.CodeLib.Compress
{
    public partial class Lzw
    {
        public static void Decode(Stream input, Stream output)
        {
            long pos = input.Position;
            MemoryStream memStream = BitOrder.Reverse(input);
            BitStream inStream = new BitStream(memStream);

            Dictionary<int, TableEntry> Table = new Dictionary<int, TableEntry>();
            TableEntry phrase = new TableEntry();
            int wordIndex = -1;
            int numbits = 9;
            while (true)
            {
                int code = inStream.ReadBitsBigEndian(numbits);
                if (code == ClearTableMarker)
                {
                    ClearTable(Table);
                    wordIndex = -1;
                    numbits = 9;
                }
                else if (code == EOD || code == -1)
                {
                    break;
                }
                else
                {
                    if (code < 256)
                    {
                        phrase.RefIndex = wordIndex;
                        phrase.Symbol = code;
                        if (wordIndex != -1)
                        {
                            Table.Add(Table.Count, phrase);
                        }
                        output.WriteByte((byte)code);
                    }
                    else
                    {
                        if (Table.ContainsKey(code))
                        {
                            int head = GetHead(Table[code], Table);
                            phrase.RefIndex = wordIndex;
                            phrase.Symbol = head;
                            Table.Add(Table.Count, phrase);
                        }
                        else
                        {
                            int head = GetHead(Table[wordIndex], Table);
                            phrase.RefIndex = wordIndex;
                            phrase.Symbol = head;
                            //Table.Count == code
                            Table.Add(Table.Count, phrase);
                        }
                        Output(code, Table, output);
                    }
                    if (numbits == 9 && Table.Count > 510)
                    {
                        numbits = 10;
                    }
                    else if (numbits == 10 && Table.Count > 1022)
                    {
                        numbits = 11;
                    }
                    else if (numbits == 11 && Table.Count > 2046)
                    {
                        numbits = 12;
                    }
                    wordIndex = code;
                }
            }
            input.Position = pos + inStream.Position;
        }

        private static int GetHead(TableEntry phrase, Dictionary<int, TableEntry> Table)
        {
            if (phrase.RefIndex == -1)
            {
                return phrase.Symbol;
            }
            else
            {
                TableEntry entry = Table[phrase.RefIndex];
                while (entry.RefIndex != -1)
                {
                    entry = Table[entry.RefIndex];
                }
                return entry.Symbol;
            }
        }

        private static void Output(int code, Dictionary<int, TableEntry> Table, Stream output)
        {
            List<byte> symbols = new List<byte>();
            TableEntry entry = Table[code];
            while (entry.RefIndex != -1)
            {
                symbols.Add((byte)entry.Symbol);
                entry = Table[entry.RefIndex];
            }
            symbols.Add((byte)entry.Symbol);
            symbols.Reverse();
            output.Write(symbols.ToArray(), 0, symbols.Count);
        }

        private static void ClearTable(Dictionary<int, TableEntry> Table)
        {
            Table.Clear();
            for (int i = 0; i <= 257; i++)
            {
                Table.Add(i, new TableEntry(i));
            }
        }
    }
}