git.maemo.org Git - physicsfs/blob - lzma/CS/7zip/Compress/LZMA/LzmaDecoder.cs

   1 // LzmaDecoder.cs
   2
   3 using System;
   4
   5 namespace SevenZip.Compression.LZMA
   6 {
   7         using RangeCoder;
   8
   9         public class Decoder : ICoder, ISetDecoderProperties // ,System.IO.Stream
  10         {
  11                 class LenDecoder
  12                 {
  13                         BitDecoder m_Choice = new BitDecoder();
  14                         BitDecoder m_Choice2 = new BitDecoder();
  15                         BitTreeDecoder[] m_LowCoder = new BitTreeDecoder[Base.kNumPosStatesMax];
  16                         BitTreeDecoder[] m_MidCoder = new BitTreeDecoder[Base.kNumPosStatesMax];
  17                         BitTreeDecoder m_HighCoder = new BitTreeDecoder(Base.kNumHighLenBits);
  18                         uint m_NumPosStates = 0;
  19
  20                         public void Create(uint numPosStates)
  21                         {
  22                                 for (uint posState = m_NumPosStates; posState < numPosStates; posState++)
  23                                 {
  24                                         m_LowCoder[posState] = new BitTreeDecoder(Base.kNumLowLenBits);
  25                                         m_MidCoder[posState] = new BitTreeDecoder(Base.kNumMidLenBits);
  26                                 }
  27                                 m_NumPosStates = numPosStates;
  28                         }
  29
  30                         public void Init()
  31                         {
  32                                 m_Choice.Init();
  33                                 for (uint posState = 0; posState < m_NumPosStates; posState++)
  34                                 {
  35                                         m_LowCoder[posState].Init();
  36                                         m_MidCoder[posState].Init();
  37                                 }
  38                                 m_Choice2.Init();
  39                                 m_HighCoder.Init();
  40                         }
  41
  42                         public uint Decode(RangeCoder.Decoder rangeDecoder, uint posState)
  43                         {
  44                                 if (m_Choice.Decode(rangeDecoder) == 0)
  45                                         return m_LowCoder[posState].Decode(rangeDecoder);
  46                                 else
  47                                 {
  48                                         uint symbol = Base.kNumLowLenSymbols;
  49                                         if (m_Choice2.Decode(rangeDecoder) == 0)
  50                                                 symbol += m_MidCoder[posState].Decode(rangeDecoder);
  51                                         else
  52                                         {
  53                                                 symbol += Base.kNumMidLenSymbols;
  54                                                 symbol += m_HighCoder.Decode(rangeDecoder);
  55                                         }
  56                                         return symbol;
  57                                 }
  58                         }
  59                 }
  60
  61                 class LiteralDecoder
  62                 {
  63                         struct Decoder2
  64                         {
  65                                 BitDecoder[] m_Decoders;
  66                                 public void Create() { m_Decoders = new BitDecoder[0x300]; }
  67                                 public void Init() { for (int i = 0; i < 0x300; i++) m_Decoders[i].Init(); }
  68
  69                                 public byte DecodeNormal(RangeCoder.Decoder rangeDecoder)
  70                                 {
  71                                         uint symbol = 1;
  72                                         do
  73                                                 symbol = (symbol << 1) | m_Decoders[symbol].Decode(rangeDecoder);
  74                                         while (symbol < 0x100);
  75                                         return (byte)symbol;
  76                                 }
  77
  78                                 public byte DecodeWithMatchByte(RangeCoder.Decoder rangeDecoder, byte matchByte)
  79                                 {
  80                                         uint symbol = 1;
  81                                         do
  82                                         {
  83                                                 uint matchBit = (uint)(matchByte >> 7) & 1;
  84                                                 matchByte <<= 1;
  85                                                 uint bit = m_Decoders[((1 + matchBit) << 8) + symbol].Decode(rangeDecoder);
  86                                                 symbol = (symbol << 1) | bit;
  87                                                 if (matchBit != bit)
  88                                                 {
  89                                                         while (symbol < 0x100)
  90                                                                 symbol = (symbol << 1) | m_Decoders[symbol].Decode(rangeDecoder);
  91                                                         break;
  92                                                 }
  93                                         }
  94                                         while (symbol < 0x100);
  95                                         return (byte)symbol;
  96                                 }
  97                         }
  98
  99                         Decoder2[] m_Coders;
 100                         int m_NumPrevBits;
 101                         int m_NumPosBits;
 102                         uint m_PosMask;
 103
 104                         public void Create(int numPosBits, int numPrevBits)
 105                         {
 106                                 if (m_Coders != null && m_NumPrevBits == numPrevBits &&
 107                                         m_NumPosBits == numPosBits)
 108                                         return;
 109                                 m_NumPosBits = numPosBits;
 110                                 m_PosMask = ((uint)1 << numPosBits) - 1;
 111                                 m_NumPrevBits = numPrevBits;
 112                                 uint numStates = (uint)1 << (m_NumPrevBits + m_NumPosBits);
 113                                 m_Coders = new Decoder2[numStates];
 114                                 for (uint i = 0; i < numStates; i++)
 115                                         m_Coders[i].Create();
 116                         }
 117
 118                         public void Init()
 119                         {
 120                                 uint numStates = (uint)1 << (m_NumPrevBits + m_NumPosBits);
 121                                 for (uint i = 0; i < numStates; i++)
 122                                         m_Coders[i].Init();
 123                         }
 124
 125                         uint GetState(uint pos, byte prevByte)
 126                         { return ((pos & m_PosMask) << m_NumPrevBits) + (uint)(prevByte >> (8 - m_NumPrevBits)); }
 127
 128                         public byte DecodeNormal(RangeCoder.Decoder rangeDecoder, uint pos, byte prevByte)
 129                         { return m_Coders[GetState(pos, prevByte)].DecodeNormal(rangeDecoder); }
 130
 131                         public byte DecodeWithMatchByte(RangeCoder.Decoder rangeDecoder, uint pos, byte prevByte, byte matchByte)
 132                         { return m_Coders[GetState(pos, prevByte)].DecodeWithMatchByte(rangeDecoder, matchByte); }
 133                 };
 134
 135                 LZ.OutWindow m_OutWindow = new LZ.OutWindow();
 136                 RangeCoder.Decoder m_RangeDecoder = new RangeCoder.Decoder();
 137
 138                 BitDecoder[] m_IsMatchDecoders = new BitDecoder[Base.kNumStates << Base.kNumPosStatesBitsMax];
 139                 BitDecoder[] m_IsRepDecoders = new BitDecoder[Base.kNumStates];
 140                 BitDecoder[] m_IsRepG0Decoders = new BitDecoder[Base.kNumStates];
 141                 BitDecoder[] m_IsRepG1Decoders = new BitDecoder[Base.kNumStates];
 142                 BitDecoder[] m_IsRepG2Decoders = new BitDecoder[Base.kNumStates];
 143                 BitDecoder[] m_IsRep0LongDecoders = new BitDecoder[Base.kNumStates << Base.kNumPosStatesBitsMax];
 144
 145                 BitTreeDecoder[] m_PosSlotDecoder = new BitTreeDecoder[Base.kNumLenToPosStates];
 146                 BitDecoder[] m_PosDecoders = new BitDecoder[Base.kNumFullDistances - Base.kEndPosModelIndex];
 147
 148                 BitTreeDecoder m_PosAlignDecoder = new BitTreeDecoder(Base.kNumAlignBits);
 149
 150                 LenDecoder m_LenDecoder = new LenDecoder();
 151                 LenDecoder m_RepLenDecoder = new LenDecoder();
 152
 153                 LiteralDecoder m_LiteralDecoder = new LiteralDecoder();
 154
 155                 uint m_DictionarySize;
 156                 uint m_DictionarySizeCheck;
 157
 158                 uint m_PosStateMask;
 159
 160                 public Decoder()
 161                 {
 162                         m_DictionarySize = 0xFFFFFFFF;
 163                         for (int i = 0; i < Base.kNumLenToPosStates; i++)
 164                                 m_PosSlotDecoder[i] = new BitTreeDecoder(Base.kNumPosSlotBits);
 165                 }
 166
 167                 void SetDictionarySize(uint dictionarySize)
 168                 {
 169                         if (m_DictionarySize != dictionarySize)
 170                         {
 171                                 m_DictionarySize = dictionarySize;
 172                                 m_DictionarySizeCheck = Math.Max(m_DictionarySize, 1);
 173                                 uint blockSize = Math.Max(m_DictionarySizeCheck, (1 << 12));
 174                                 m_OutWindow.Create(blockSize);
 175                         }
 176                 }
 177
 178                 void SetLiteralProperties(int lp, int lc)
 179                 {
 180                         if (lp > 8)
 181                                 throw new InvalidParamException();
 182                         if (lc > 8)
 183                                 throw new InvalidParamException();
 184                         m_LiteralDecoder.Create(lp, lc);
 185                 }
 186
 187                 void SetPosBitsProperties(int pb)
 188                 {
 189                         if (pb > Base.kNumPosStatesBitsMax)
 190                                 throw new InvalidParamException();
 191                         uint numPosStates = (uint)1 << pb;
 192                         m_LenDecoder.Create(numPosStates);
 193                         m_RepLenDecoder.Create(numPosStates);
 194                         m_PosStateMask = numPosStates - 1;
 195                 }
 196
 197                 bool _solid = false;
 198                 void Init(System.IO.Stream inStream, System.IO.Stream outStream)
 199                 {
 200                         m_RangeDecoder.Init(inStream);
 201                         m_OutWindow.Init(outStream, _solid);
 202
 203                         uint i;
 204                         for (i = 0; i < Base.kNumStates; i++)
 205                         {
 206                                 for (uint j = 0; j <= m_PosStateMask; j++)
 207                                 {
 208                                         uint index = (i << Base.kNumPosStatesBitsMax) + j;
 209                                         m_IsMatchDecoders[index].Init();
 210                                         m_IsRep0LongDecoders[index].Init();
 211                                 }
 212                                 m_IsRepDecoders[i].Init();
 213                                 m_IsRepG0Decoders[i].Init();
 214                                 m_IsRepG1Decoders[i].Init();
 215                                 m_IsRepG2Decoders[i].Init();
 216                         }
 217
 218                         m_LiteralDecoder.Init();
 219                         for (i = 0; i < Base.kNumLenToPosStates; i++)
 220                                 m_PosSlotDecoder[i].Init();
 221                         // m_PosSpecDecoder.Init();
 222                         for (i = 0; i < Base.kNumFullDistances - Base.kEndPosModelIndex; i++)
 223                                 m_PosDecoders[i].Init();
 224
 225                         m_LenDecoder.Init();
 226                         m_RepLenDecoder.Init();
 227                         m_PosAlignDecoder.Init();
 228                 }
 229
 230                 public void Code(System.IO.Stream inStream, System.IO.Stream outStream,
 231                         Int64 inSize, Int64 outSize, ICodeProgress progress)
 232                 {
 233                         Init(inStream, outStream);
 234
 235                         Base.State state = new Base.State();
 236                         state.Init();
 237                         uint rep0 = 0, rep1 = 0, rep2 = 0, rep3 = 0;
 238
 239                         UInt64 nowPos64 = 0;
 240                         UInt64 outSize64 = (UInt64)outSize;
 241                         if (nowPos64 < outSize64)
 242                         {
 243                                 if (m_IsMatchDecoders[state.Index << Base.kNumPosStatesBitsMax].Decode(m_RangeDecoder) != 0)
 244                                         throw new DataErrorException();
 245                                 state.UpdateChar();
 246                                 byte b = m_LiteralDecoder.DecodeNormal(m_RangeDecoder, 0, 0);
 247                                 m_OutWindow.PutByte(b);
 248                                 nowPos64++;
 249                         }
 250                         while (nowPos64 < outSize64)
 251                         {
 252                                 // UInt64 next = Math.Min(nowPos64 + (1 << 18), outSize64);
 253                                         // while(nowPos64 < next)
 254                                 {
 255                                         uint posState = (uint)nowPos64 & m_PosStateMask;
 256                                         if (m_IsMatchDecoders[(state.Index << Base.kNumPosStatesBitsMax) + posState].Decode(m_RangeDecoder) == 0)
 257                                         {
 258                                                 byte b;
 259                                                 byte prevByte = m_OutWindow.GetByte(0);
 260                                                 if (!state.IsCharState())
 261                                                         b = m_LiteralDecoder.DecodeWithMatchByte(m_RangeDecoder,
 262                                                                 (uint)nowPos64, prevByte, m_OutWindow.GetByte(rep0));
 263                                                 else
 264                                                         b = m_LiteralDecoder.DecodeNormal(m_RangeDecoder, (uint)nowPos64, prevByte);
 265                                                 m_OutWindow.PutByte(b);
 266                                                 state.UpdateChar();
 267                                                 nowPos64++;
 268                                         }
 269                                         else
 270                                         {
 271                                                 uint len;
 272                                                 if (m_IsRepDecoders[state.Index].Decode(m_RangeDecoder) == 1)
 273                                                 {
 274                                                         if (m_IsRepG0Decoders[state.Index].Decode(m_RangeDecoder) == 0)
 275                                                         {
 276                                                                 if (m_IsRep0LongDecoders[(state.Index << Base.kNumPosStatesBitsMax) + posState].Decode(m_RangeDecoder) == 0)
 277                                                                 {
 278                                                                         state.UpdateShortRep();
 279                                                                         m_OutWindow.PutByte(m_OutWindow.GetByte(rep0));
 280                                                                         nowPos64++;
 281                                                                         continue;
 282                                                                 }
 283                                                         }
 284                                                         else
 285                                                         {
 286                                                                 UInt32 distance;
 287                                                                 if (m_IsRepG1Decoders[state.Index].Decode(m_RangeDecoder) == 0)
 288                                                                 {
 289                                                                         distance = rep1;
 290                                                                 }
 291                                                                 else
 292                                                                 {
 293                                                                         if (m_IsRepG2Decoders[state.Index].Decode(m_RangeDecoder) == 0)
 294                                                                                 distance = rep2;
 295                                                                         else
 296                                                                         {
 297                                                                                 distance = rep3;
 298                                                                                 rep3 = rep2;
 299                                                                         }
 300                                                                         rep2 = rep1;
 301                                                                 }
 302                                                                 rep1 = rep0;
 303                                                                 rep0 = distance;
 304                                                         }
 305                                                         len = m_RepLenDecoder.Decode(m_RangeDecoder, posState) + Base.kMatchMinLen;
 306                                                         state.UpdateRep();
 307                                                 }
 308                                                 else
 309                                                 {
 310                                                         rep3 = rep2;
 311                                                         rep2 = rep1;
 312                                                         rep1 = rep0;
 313                                                         len = Base.kMatchMinLen + m_LenDecoder.Decode(m_RangeDecoder, posState);
 314                                                         state.UpdateMatch();
 315                                                         uint posSlot = m_PosSlotDecoder[Base.GetLenToPosState(len)].Decode(m_RangeDecoder);
 316                                                         if (posSlot >= Base.kStartPosModelIndex)
 317                                                         {
 318                                                                 int numDirectBits = (int)((posSlot >> 1) - 1);
 319                                                                 rep0 = ((2 | (posSlot & 1)) << numDirectBits);
 320                                                                 if (posSlot < Base.kEndPosModelIndex)
 321                                                                         rep0 += BitTreeDecoder.ReverseDecode(m_PosDecoders,
 322                                                                                         rep0 - posSlot - 1, m_RangeDecoder, numDirectBits);
 323                                                                 else
 324                                                                 {
 325                                                                         rep0 += (m_RangeDecoder.DecodeDirectBits(
 326                                                                                 numDirectBits - Base.kNumAlignBits) << Base.kNumAlignBits);
 327                                                                         rep0 += m_PosAlignDecoder.ReverseDecode(m_RangeDecoder);
 328                                                                 }
 329                                                         }
 330                                                         else
 331                                                                 rep0 = posSlot;
 332                                                 }
 333                                                 if (rep0 >= m_OutWindow.TrainSize + nowPos64 || rep0 >= m_DictionarySizeCheck)
 334                                                 {
 335                                                         if (rep0 == 0xFFFFFFFF)
 336                                                                 break;
 337                                                         throw new DataErrorException();
 338                                                 }
 339                                                 m_OutWindow.CopyBlock(rep0, len);
 340                                                 nowPos64 += len;
 341                                         }
 342                                 }
 343                         }
 344                         m_OutWindow.Flush();
 345                         m_OutWindow.ReleaseStream();
 346                         m_RangeDecoder.ReleaseStream();
 347                 }
 348
 349                 public void SetDecoderProperties(byte[] properties)
 350                 {
 351                         if (properties.Length < 5)
 352                                 throw new InvalidParamException();
 353                         int lc = properties[0] % 9;
 354                         int remainder = properties[0] / 9;
 355                         int lp = remainder % 5;
 356                         int pb = remainder / 5;
 357                         if (pb > Base.kNumPosStatesBitsMax)
 358                                 throw new InvalidParamException();
 359                         UInt32 dictionarySize = 0;
 360                         for (int i = 0; i < 4; i++)
 361                                 dictionarySize += ((UInt32)(properties[1 + i])) << (i * 8);
 362                         SetDictionarySize(dictionarySize);
 363                         SetLiteralProperties(lp, lc);
 364                         SetPosBitsProperties(pb);
 365                 }
 366
 367                 public bool Train(System.IO.Stream stream)
 368                 {
 369                         _solid = true;
 370                         return m_OutWindow.Train(stream);
 371                 }
 372
 373                 /*
 374                 public override bool CanRead { get { return true; }}
 375                 public override bool CanWrite { get { return true; }}
 376                 public override bool CanSeek { get { return true; }}
 377                 public override long Length { get { return 0; }}
 378                 public override long Position
 379                 {
 380                         get { return 0; }
 381                         set { }
 382                 }
 383                 public override void Flush() { }
 384                 public override int Read(byte[] buffer, int offset, int count)
 385                 {
 386                         return 0;
 387                 }
 388                 public override void Write(byte[] buffer, int offset, int count)
 389                 {
 390                 }
 391                 public override long Seek(long offset, System.IO.SeekOrigin origin)
 392                 {
 393                         return 0;
 394                 }
 395                 public override void SetLength(long value) {}
 396                 */
 397         }
 398 }