/*
 * LZMADecode.c
 * 
 * This file is a part of LZMA compression module for NSIS.
 * 
 * Original LZMA SDK Copyright (C) 1999-2006 Igor Pavlov
 * Modifications Copyright (C) 2003-2008 Amir Szekely <kichik@netvision.net.il>
 * 
 * Licensed under the Common Public License version 1.0 (the "License");
 * you may not use this file except in compliance with the License.
 * 
 * Licence details can be found in the file COPYING.
 * 
 * This software is provided 'as-is', without any express or implied
 * warranty.
 */

#include <stdlib.h>
#include "LZMADecode.h"

#define LEAVE { goto saveStateAndReturn; }
#define NEED_BYTE(c) case c: if (!avail_in) { mode = c; LEAVE; }
#define NEED_BYTE_ if (!avail_in) LEAVE;
#define NEXT_BYTE (avail_in--, *next_in++)
#define NEED_OUT(c) case c: if (!avail_out) { mode = c; LEAVE; }
#define PUT_BYTE_(b) { *next_out = b; next_out++; avail_out--; }
#define PUT_BYTE(b) { totalOut++; PUT_BYTE_(b) }
#define DECODE_BIT(c, x) prob = x; last = c; goto _LZMA_C_RDBD; case c:
#define DECODE_LEN(c, x) probs = x; last2 = c; goto _LZMA_C_LEND; case c:
#define DECODE_BIT_TREE(c, x, y) probs = x; numLevels = y; last3 = c; goto _LZMA_C_BTD; case c:

enum {
  /*  0 */ LZMA_C_INIT = 0,
  /*  1 */ LZMA_C_GETDICT,
  /*  2 */ LZMA_C_BLOCK,
  /*  3 */ LZMA_C_RDI, /* RangeDecoderInit */
  /*  4 */ LZMA_C_RDBD, /* RangeDecoderBitDecode */
  /*  5 */ LZMA_C_RDBD_IN, /* RangeDecoderBitDecode */
  /*  6 */ LZMA_C_TYPE,
  /*  7 */ LZMA_C_ISREP,
  /*  8 */ LZMA_C_ISREPG0,
  /*  9 */ LZMA_C_ISREP0LONG,
  /* 10 */ LZMA_C_ISREPG1,
  /* 11 */ LZMA_C_ISREPG2,
  /* 12 */ LZMA_C_NORM,
  /* 13 */ LZMA_C_LITDM1, /* LzmaLiteralDecodeMatch */
  /* 14 */ LZMA_C_LITDM2, /* LzmaLiteralDecodeMatch */
  /* 15 */ LZMA_C_LITD, /* LzmaLiteralDecode */
  /* 16 */ LZMA_C_RDRBTD, /* RangeDecoderReverseBitTreeDecode */
  /* 17 */ LZMA_C_LEND, /* LzmaLenDecode */
  /* 18 */ LZMA_C_LEND1, /* LzmaLenDecode */
  /* 19 */ LZMA_C_LEND2, /* LzmaLenDecode */
  /* 20 */ LZMA_C_LEND_RES, /* LzmaLenDecode */
  /* 21 */ LZMA_C_LEND_C1,
  /* 22 */ LZMA_C_LEND_C2,
  /* 23 */ LZMA_C_BTD, /* RangeDecoderBitTreeDecode */
  /* 24 */ LZMA_C_BTD_LOOP,
  /* 25 */ LZMA_C_BTD_C1,
  /* 26 */ LZMA_C_OUTPUT_1,
  /* 27 */ LZMA_C_OUTPUT_2,
  /* 28 */ LZMA_C_OUTPUT_3
};

#define kNumTopBits 24
#define kTopValue ((UInt32)1 << kNumTopBits)

#define kNumBitModelTotalBits 11
#define kBitModelTotal (1 << kNumBitModelTotalBits)
#define kNumMoveBits 5

#define RC_NORMALIZE(c) if (range < kTopValue) { NEED_BYTE(c); range <<= 8; code = (code << 8) | NEXT_BYTE; }

#define RC_GET_BIT2(c, prob, mi, A0, A1) { \
  UInt32 bound = (range >> kNumBitModelTotalBits) * *prob; \
  if (code < bound) \
    { A0; range = bound; *prob += (kBitModelTotal - *prob) >> kNumMoveBits; mi <<= 1; } \
  else \
    { A1; range -= bound; code -= bound; *prob -= (*prob) >> kNumMoveBits; mi = (mi + mi) + 1; } \
  RC_NORMALIZE(c) \
}

#define RC_GET_BIT(c, prob, mi) RC_GET_BIT2(c, prob, mi, ; , ;)

#define kNumPosBitsMax 4
#define kNumPosStatesMax (1 << kNumPosBitsMax)

#define kLenNumLowBits 3
#define kLenNumLowSymbols (1 << kLenNumLowBits)
#define kLenNumMidBits 3
#define kLenNumMidSymbols (1 << kLenNumMidBits)
#define kLenNumHighBits 8
#define kLenNumHighSymbols (1 << kLenNumHighBits)

#define LenChoice 0
#define LenChoice2 (LenChoice + 1)
#define LenLow (LenChoice2 + 1)
#define LenMid (LenLow + (kNumPosStatesMax << kLenNumLowBits))
#define LenHigh (LenMid + (kNumPosStatesMax << kLenNumMidBits))
#define kNumLenProbs (LenHigh + kLenNumHighSymbols)

#define kNumStates 12

#define kStartPosModelIndex 4
#define kEndPosModelIndex 14
#define kNumFullDistances (1 << (kEndPosModelIndex >> 1))

#define kNumPosSlotBits 6
#define kNumLenToPosStates 4

#define kNumAlignBits 4
#define kAlignTableSize (1 << kNumAlignBits)

#define kMatchMinLen 2

#define IsMatch 0
#define IsRep (IsMatch + (kNumStates << kNumPosBitsMax))
#define IsRepG0 (IsRep + kNumStates)
#define IsRepG1 (IsRepG0 + kNumStates)
#define IsRepG2 (IsRepG1 + kNumStates)
#define IsRep0Long (IsRepG2 + kNumStates)
#define PosSlot (IsRep0Long + (kNumStates << kNumPosBitsMax))
#define SpecPos (PosSlot + (kNumLenToPosStates << kNumPosSlotBits))
#define Align (SpecPos + kNumFullDistances - kEndPosModelIndex)
#define LenCoder (Align + kAlignTableSize)
#define RepLenCoder (LenCoder + kNumLenProbs)
#define Literal (RepLenCoder + kNumLenProbs)

#define LZMA_BASE_SIZE 1846
#define LZMA_LIT_SIZE 768

#if Literal != LZMA_BASE_SIZE
StopCompilingDueBUG
#endif

void LZMACALL lzmaInit(lzma_stream *s)
{
  /* size of lzma_stream minus the size of the two allocated buffer pointers.
     we don't want to lose to pointer or else we won't be able to free them. */
  size_t i = sizeof(lzma_stream) - (sizeof(unsigned char *) * 2);
  while (i--)
    ((Byte *)s)[i] = 0;

  s->rep0 = s->rep1 = s->rep2 = s->rep3 = 1;
  s->range = (0xFFFFFFFF);
}

int LZMACALL lzmaDecode(lzma_stream *s)
{
  /* restore decoder state */
  lzma_stream _s = *s;

#define mode _s.mode
#define last _s.last
#define last2 _s.last2
#define last3 _s.last3

#define p (*(CProb **) &_s.dynamicData)
#define dynamicDataSize _s.dynamicDataSize

#define state _s.state
#define isPreviousMatch _s.isPreviousMatch
#define previousByte _s.previousByte
#define rep0 _s.rep0
#define rep1 _s.rep1
#define rep2 _s.rep2
#define rep3 _s.rep3
#define lc _s.lc
#define len _s.len
#define totalOut _s.totalOut

#define dictionary _s.dictionary
#define dictionarySize _s.dictionarySize
#define dictionaryPos _s.dictionaryPos

#define posStateMask _s.posStateMask
#define literalPosMask _s.literalPosMask

#define avail_in _s.avail_in
#define next_in _s.next_in
#define avail_out _s.avail_out
#define next_out _s.next_out

#define range _s.range
#define code _s.code

#define probs _s.probs
#define prob _s.prob

#define symbol _s.temp2
#define bit _s.temp3
#define matchBit _s.temp1
#define i _s.temp1
#define result _s.temp2
#define numLevels _s.temp3
#define posSlot _s.temp2
#define newDictionarySize (*(UInt32*) &_s.temp3)

#define matchByte _s.matchByte
#define mi _s.mi
#define posState _s.posState

  if (len == -1)
    return LZMA_STREAM_END;

  for (;;) switch (mode)
  {
  case LZMA_C_INIT:
    {
      Byte firstByte;
      UInt32 newDynamicDataSize;
      UInt32 numProbs;
      int lp;
      int pb;

      NEED_BYTE_;

      firstByte = NEXT_BYTE;

      if (firstByte > (9*5*5))
        return LZMA_DATA_ERROR;

      pb = firstByte / (9*5);
      firstByte %= (9*5);
      lp = firstByte / 9;
      firstByte %= 9;
      lc = firstByte;

      posStateMask = (1 << (pb)) - 1;
      literalPosMask = (1 << (lp)) - 1;

      numProbs = Literal + (LZMA_LIT_SIZE << (lc + pb));
      newDynamicDataSize = numProbs * sizeof(CProb);

      if (newDynamicDataSize != dynamicDataSize)
      {
        if (p)
          lzmafree(p);
        p = lzmaalloc(newDynamicDataSize);
        if (!p)
          return LZMA_NOT_ENOUGH_MEM;
        dynamicDataSize = newDynamicDataSize;
      }

      while (numProbs--)
        p[numProbs] = kBitModelTotal >> 1;

      for (i = 0, newDictionarySize = 0; i < 4; i++)
      {
        NEED_BYTE(LZMA_C_GETDICT);
        newDictionarySize |= NEXT_BYTE << (i * 8);
      }

      if (newDictionarySize != dictionarySize)
      {
        dictionarySize = newDictionarySize;
        if (dictionary)
          lzmafree(dictionary);
        dictionary = lzmaalloc(dictionarySize);
        if (!dictionary)
          return LZMA_NOT_ENOUGH_MEM;
      }

      dictionary[dictionarySize - 1] = 0;

      i = 5;
      while (i--)
      {
        NEED_BYTE(LZMA_C_RDI);
        code = (code << 8) | NEXT_BYTE;
      }
    }
  case LZMA_C_BLOCK:
    posState = (int)(totalOut & posStateMask);
    DECODE_BIT(LZMA_C_TYPE, p + IsMatch + (state << kNumPosBitsMax) + posState);
    if (bit == 0)
    {
      probs = p + Literal + (LZMA_LIT_SIZE *
        (((totalOut & literalPosMask) << lc) + (previousByte >> (8 - lc))));

      if (state < 4) state = 0;
      else if (state < 10) state -= 3;
      else state -= 6;
      if (isPreviousMatch)
      {
        UInt32 pos = dictionaryPos - rep0;
        if (pos >= dictionarySize)
          pos += dictionarySize;
        matchByte = dictionary[pos];
        {
          symbol = 1;
          do
          {
            matchBit = (matchByte >> 7) & 1;
            matchByte <<= 1;
            {
              prob = probs + ((1 + matchBit) << 8) + symbol;
              RC_GET_BIT2(LZMA_C_LITDM1, prob, symbol, bit = 0, bit = 1)
            }
            if (matchBit != bit)
            {
              while (symbol < 0x100)
              {
                prob = probs + symbol;
                RC_GET_BIT(LZMA_C_LITDM2, prob, symbol)
              }
              break;
            }
          }
          while (symbol < 0x100);
          previousByte = symbol;
        }
        isPreviousMatch = 0;
      }
      else
      {
        symbol = 1;
        do
        {
          prob = probs + symbol;
          RC_GET_BIT(LZMA_C_LITD, prob, symbol)
        }
        while (symbol < 0x100);
        previousByte = symbol;
      }
      NEED_OUT(LZMA_C_OUTPUT_1);
      PUT_BYTE(previousByte);
      dictionary[dictionaryPos] = previousByte;
      dictionaryPos = (dictionaryPos + 1) % dictionarySize;
    }
    /* bit == 1 */
    else
    {
      isPreviousMatch = 1;
      DECODE_BIT(LZMA_C_ISREP, p + IsRep + state);
      if (bit == 1)
      {
        DECODE_BIT(LZMA_C_ISREPG0, p + IsRepG0 + state);
        if (bit == 0)
        {
          DECODE_BIT(LZMA_C_ISREP0LONG, p + IsRep0Long + (state << kNumPosBitsMax) + posState);
          if (bit == 0)
          {
            UInt32 pos;
            if (totalOut == 0)
              return LZMA_DATA_ERROR;
            state = state < 7 ? 9 : 11;
            NEED_OUT(LZMA_C_OUTPUT_2);
            pos = dictionaryPos - rep0;
            if (pos >= dictionarySize)
              pos += dictionarySize;
            previousByte = dictionary[pos];
            dictionary[dictionaryPos] = previousByte;
            dictionaryPos = (dictionaryPos + 1) % dictionarySize;
            PUT_BYTE(previousByte);
            mode = LZMA_C_BLOCK;
            break;
          }
        }
        else
        {
          UInt32 distance;
          DECODE_BIT(LZMA_C_ISREPG1, p + IsRepG1 + state);
          if (bit == 0)
          {
            distance = rep1;
          }
          else
          {
            DECODE_BIT(LZMA_C_ISREPG2, p + IsRepG2 + state);
            if (bit == 0)
              distance = rep2;
            else
            {
              distance = rep3;
              rep3 = rep2;
            }
            rep2 = rep1;
          }
          rep1 = rep0;
          rep0 = distance;
        }
        DECODE_LEN(LZMA_C_LEND_C1, p + RepLenCoder);
        state = state < 7 ? 8 : 11;
      }
      else
      {
        rep3 = rep2;
        rep2 = rep1;
        rep1 = rep0;
        state = state < 7 ? 7 : 10;
        DECODE_LEN(LZMA_C_LEND_C2, p + LenCoder);
        DECODE_BIT_TREE(
          LZMA_C_BTD_C1,
          p + PosSlot + ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) << kNumPosSlotBits),
          kNumPosSlotBits
        );
        if (posSlot >= kStartPosModelIndex)
        {
          int numDirectBits = ((posSlot >> 1) - 1);
          rep0 = ((2 | ((UInt32)posSlot & 1)) << numDirectBits);
          if (posSlot < kEndPosModelIndex)
          {
            probs = p + SpecPos + rep0 - posSlot - 1;
            numLevels = numDirectBits;
          }
          else
          {
            int numTotalBits = numDirectBits - kNumAlignBits;
            result = 0;
            for (i = numTotalBits; i > 0; i--)
            {
              /* UInt32 t; */
              range >>= 1;

              result <<= 1;
              if (code >= range)
              {
                code -= range;
                result |= 1;
              }
              /*
              t = (code - range) >> 31;
              t &= 1;
              code -= range & (t - 1);
              result = (result + result) | (1 - t);
              */
              RC_NORMALIZE(LZMA_C_NORM)
            }
            rep0 += result << kNumAlignBits;
            probs = p + Align;
            numLevels = kNumAlignBits;
          }
          mi = 1;
          symbol = 0;
          for(i = 0; i < numLevels; i++)
          {
            prob = probs + mi;
            RC_GET_BIT2(LZMA_C_RDRBTD, prob, mi, ; , symbol |= (1 << i));
          }
          rep0 += symbol;
        }
        else
          rep0 = posSlot;
        rep0++;
      }
      if (rep0 == (UInt32)(0))
      {
        len = -1;
        LEAVE;
      }
      if (rep0 > totalOut)
      {
        return LZMA_DATA_ERROR;
      }
      len += kMatchMinLen;
      totalOut += len;
      do
      {
        UInt32 pos;
        NEED_OUT(LZMA_C_OUTPUT_3);
        pos = dictionaryPos - rep0;
        if (pos >= dictionarySize)
          pos += dictionarySize;
        previousByte = dictionary[pos];
        dictionary[dictionaryPos] = previousByte;
        dictionaryPos = (dictionaryPos + 1) % dictionarySize;
        PUT_BYTE_(previousByte);
        len--;
      }
      while(len > 0);
    }
    mode = LZMA_C_BLOCK;
    break;
  case LZMA_C_RDBD:
  _LZMA_C_RDBD:
    {
      UInt32 bound = (range >> kNumBitModelTotalBits) * *prob;
      if (code < bound)
      {
        range = bound;
        *prob += (kBitModelTotal - *prob) >> kNumMoveBits;
        bit = 0;
      }
      else
      {
        range -= bound;
        code -= bound;
        *prob -= (*prob) >> kNumMoveBits;
        bit = 1;
      }
      RC_NORMALIZE(LZMA_C_RDBD_IN);
    }
    mode = last;
    break;
  case LZMA_C_LEND:
  _LZMA_C_LEND:
      DECODE_BIT(LZMA_C_LEND1, probs + LenChoice);
      if (bit == 0)
      {
        len = 0;
        probs += LenLow + (posState << kLenNumLowBits);
        numLevels = kLenNumLowBits;
      }
      else {
        DECODE_BIT(LZMA_C_LEND2, probs + LenChoice2);
        if (bit == 0)
        {
          len = kLenNumLowSymbols;
          probs += + LenMid + (posState << kLenNumMidBits);
          numLevels = kLenNumMidBits;
        }
        else
        {
          len = kLenNumLowSymbols + kLenNumMidSymbols;
          probs += LenHigh;
          numLevels = kLenNumHighBits;
        }
      }

      last3 = LZMA_C_LEND_RES;
  case LZMA_C_BTD:
  _LZMA_C_BTD:
    mi = 1;
    for(i = numLevels; i > 0; i--)
    {
      prob = probs + mi;
      RC_GET_BIT(LZMA_C_BTD_LOOP, prob, mi)
    }
    result = mi - (1 << numLevels);
    mode = last3;
    break;
  case LZMA_C_LEND_RES:
    len += result;
    mode = last2;
    break;
  default:
    return LZMA_DATA_ERROR;
  }

saveStateAndReturn:

  /* save decoder state */
  *s = _s;

  return LZMA_OK;
}