Merge pull request #461 from negativeExponent/libchdr

[pcsx_rearmed.git] / deps / lzma-16.04 / C / Ppmd7Dec.c

/* Ppmd7Dec.c -- PPMdH Decoder\r
2010-03-12 : Igor Pavlov : Public domain\r
This code is based on PPMd var.H (2001): Dmitry Shkarin : Public domain */\r
\r
#include "Precomp.h"\r
\r
#include "Ppmd7.h"\r
\r
#define kTopValue (1 << 24)\r
\r
Bool Ppmd7z_RangeDec_Init(CPpmd7z_RangeDec *p)\r
{\r
  unsigned i;\r
  p->Code = 0;\r
  p->Range = 0xFFFFFFFF;\r
  if (p->Stream->Read((void *)p->Stream) != 0)\r
    return False;\r
  for (i = 0; i < 4; i++)\r
    p->Code = (p->Code << 8) | p->Stream->Read((void *)p->Stream);\r
  return (p->Code < 0xFFFFFFFF);\r
}\r
\r
static UInt32 Range_GetThreshold(void *pp, UInt32 total)\r
{\r
  CPpmd7z_RangeDec *p = (CPpmd7z_RangeDec *)pp;\r
  return (p->Code) / (p->Range /= total);\r
}\r
\r
static void Range_Normalize(CPpmd7z_RangeDec *p)\r
{\r
  if (p->Range < kTopValue)\r
  {\r
    p->Code = (p->Code << 8) | p->Stream->Read((void *)p->Stream);\r
    p->Range <<= 8;\r
    if (p->Range < kTopValue)\r
    {\r
      p->Code = (p->Code << 8) | p->Stream->Read((void *)p->Stream);\r
      p->Range <<= 8;\r
    }\r
  }\r
}\r
\r
static void Range_Decode(void *pp, UInt32 start, UInt32 size)\r
{\r
  CPpmd7z_RangeDec *p = (CPpmd7z_RangeDec *)pp;\r
  p->Code -= start * p->Range;\r
  p->Range *= size;\r
  Range_Normalize(p);\r
}\r
\r
static UInt32 Range_DecodeBit(void *pp, UInt32 size0)\r
{\r
  CPpmd7z_RangeDec *p = (CPpmd7z_RangeDec *)pp;\r
  UInt32 newBound = (p->Range >> 14) * size0;\r
  UInt32 symbol;\r
  if (p->Code < newBound)\r
  {\r
    symbol = 0;\r
    p->Range = newBound;\r
  }\r
  else\r
  {\r
    symbol = 1;\r
    p->Code -= newBound;\r
    p->Range -= newBound;\r
  }\r
  Range_Normalize(p);\r
  return symbol;\r
}\r
\r
void Ppmd7z_RangeDec_CreateVTable(CPpmd7z_RangeDec *p)\r
{\r
  p->p.GetThreshold = Range_GetThreshold;\r
  p->p.Decode = Range_Decode;\r
  p->p.DecodeBit = Range_DecodeBit;\r
}\r
\r
\r
#define MASK(sym) ((signed char *)charMask)[sym]\r
\r
int Ppmd7_DecodeSymbol(CPpmd7 *p, IPpmd7_RangeDec *rc)\r
{\r
  size_t charMask[256 / sizeof(size_t)];\r
  if (p->MinContext->NumStats != 1)\r
  {\r
    CPpmd_State *s = Ppmd7_GetStats(p, p->MinContext);\r
    unsigned i;\r
    UInt32 count, hiCnt;\r
    if ((count = rc->GetThreshold(rc, p->MinContext->SummFreq)) < (hiCnt = s->Freq))\r
    {\r
      Byte symbol;\r
      rc->Decode(rc, 0, s->Freq);\r
      p->FoundState = s;\r
      symbol = s->Symbol;\r
      Ppmd7_Update1_0(p);\r
      return symbol;\r
    }\r
    p->PrevSuccess = 0;\r
    i = p->MinContext->NumStats - 1;\r
    do\r
    {\r
      if ((hiCnt += (++s)->Freq) > count)\r
      {\r
        Byte symbol;\r
        rc->Decode(rc, hiCnt - s->Freq, s->Freq);\r
        p->FoundState = s;\r
        symbol = s->Symbol;\r
        Ppmd7_Update1(p);\r
        return symbol;\r
      }\r
    }\r
    while (--i);\r
    if (count >= p->MinContext->SummFreq)\r
      return -2;\r
    p->HiBitsFlag = p->HB2Flag[p->FoundState->Symbol];\r
    rc->Decode(rc, hiCnt, p->MinContext->SummFreq - hiCnt);\r
    PPMD_SetAllBitsIn256Bytes(charMask);\r
    MASK(s->Symbol) = 0;\r
    i = p->MinContext->NumStats - 1;\r
    do { MASK((--s)->Symbol) = 0; } while (--i);\r
  }\r
  else\r
  {\r
    UInt16 *prob = Ppmd7_GetBinSumm(p);\r
    if (rc->DecodeBit(rc, *prob) == 0)\r
    {\r
      Byte symbol;\r
      *prob = (UInt16)PPMD_UPDATE_PROB_0(*prob);\r
      symbol = (p->FoundState = Ppmd7Context_OneState(p->MinContext))->Symbol;\r
      Ppmd7_UpdateBin(p);\r
      return symbol;\r
    }\r
    *prob = (UInt16)PPMD_UPDATE_PROB_1(*prob);\r
    p->InitEsc = PPMD7_kExpEscape[*prob >> 10];\r
    PPMD_SetAllBitsIn256Bytes(charMask);\r
    MASK(Ppmd7Context_OneState(p->MinContext)->Symbol) = 0;\r
    p->PrevSuccess = 0;\r
  }\r
  for (;;)\r
  {\r
    CPpmd_State *ps[256], *s;\r
    UInt32 freqSum, count, hiCnt;\r
    CPpmd_See *see;\r
    unsigned i, num, numMasked = p->MinContext->NumStats;\r
    do\r
    {\r
      p->OrderFall++;\r
      if (!p->MinContext->Suffix)\r
        return -1;\r
      p->MinContext = Ppmd7_GetContext(p, p->MinContext->Suffix);\r
    }\r
    while (p->MinContext->NumStats == numMasked);\r
    hiCnt = 0;\r
    s = Ppmd7_GetStats(p, p->MinContext);\r
    i = 0;\r
    num = p->MinContext->NumStats - numMasked;\r
    do\r
    {\r
      int k = (int)(MASK(s->Symbol));\r
      hiCnt += (s->Freq & k);\r
      ps[i] = s++;\r
      i -= k;\r
    }\r
    while (i != num);\r
    \r
    see = Ppmd7_MakeEscFreq(p, numMasked, &freqSum);\r
    freqSum += hiCnt;\r
    count = rc->GetThreshold(rc, freqSum);\r
    \r
    if (count < hiCnt)\r
    {\r
      Byte symbol;\r
      CPpmd_State **pps = ps;\r
      for (hiCnt = 0; (hiCnt += (*pps)->Freq) <= count; pps++);\r
      s = *pps;\r
      rc->Decode(rc, hiCnt - s->Freq, s->Freq);\r
      Ppmd_See_Update(see);\r
      p->FoundState = s;\r
      symbol = s->Symbol;\r
      Ppmd7_Update2(p);\r
      return symbol;\r
    }\r
    if (count >= freqSum)\r
      return -2;\r
    rc->Decode(rc, hiCnt, freqSum - hiCnt);\r
    see->Summ = (UInt16)(see->Summ + freqSum);\r
    do { MASK(ps[--i]->Symbol) = 0; } while (i != 0);\r
  }\r
}\r