1/* Ppmd7Dec.c -- PPMdH Decoder
  22018-07-04 : Igor Pavlov : Public domain
  3This code is based on PPMd var.H (2001): Dmitry Shkarin : Public domain */
  4
  5#include "Precomp.h"
  6
  7#include "Ppmd7.h"
  8
  9#define kTopValue (1 << 24)
 10
 11BoolInt Ppmd7z_RangeDec_Init(CPpmd7z_RangeDec *p)
 12{
 13  unsigned i;
 14  p->Code = 0;
 15  p->Range = 0xFFFFFFFF;
 16  if (IByteIn_Read(p->Stream) != 0)
 17    return False;
 18  for (i = 0; i < 4; i++)
 19    p->Code = (p->Code << 8) | IByteIn_Read(p->Stream);
 20  return (p->Code < 0xFFFFFFFF);
 21}
 22
 23#define GET_Ppmd7z_RangeDec CPpmd7z_RangeDec *p = CONTAINER_FROM_VTBL(pp, CPpmd7z_RangeDec, vt);
 24 
 25static UInt32 Range_GetThreshold(const IPpmd7_RangeDec *pp, UInt32 total)
 26{
 27  GET_Ppmd7z_RangeDec
 28  return p->Code / (p->Range /= total);
 29}
 30
 31static void Range_Normalize(CPpmd7z_RangeDec *p)
 32{
 33  if (p->Range < kTopValue)
 34  {
 35    p->Code = (p->Code << 8) | IByteIn_Read(p->Stream);
 36    p->Range <<= 8;
 37    if (p->Range < kTopValue)
 38    {
 39      p->Code = (p->Code << 8) | IByteIn_Read(p->Stream);
 40      p->Range <<= 8;
 41    }
 42  }
 43}
 44
 45static void Range_Decode(const IPpmd7_RangeDec *pp, UInt32 start, UInt32 size)
 46{
 47  GET_Ppmd7z_RangeDec
 48  p->Code -= start * p->Range;
 49  p->Range *= size;
 50  Range_Normalize(p);
 51}
 52
 53static UInt32 Range_DecodeBit(const IPpmd7_RangeDec *pp, UInt32 size0)
 54{
 55  GET_Ppmd7z_RangeDec
 56  UInt32 newBound = (p->Range >> 14) * size0;
 57  UInt32 symbol;
 58  if (p->Code < newBound)
 59  {
 60    symbol = 0;
 61    p->Range = newBound;
 62  }
 63  else
 64  {
 65    symbol = 1;
 66    p->Code -= newBound;
 67    p->Range -= newBound;
 68  }
 69  Range_Normalize(p);
 70  return symbol;
 71}
 72
 73void Ppmd7z_RangeDec_CreateVTable(CPpmd7z_RangeDec *p)
 74{
 75  p->vt.GetThreshold = Range_GetThreshold;
 76  p->vt.Decode = Range_Decode;
 77  p->vt.DecodeBit = Range_DecodeBit;
 78}
 79
 80
 81#define MASK(sym) ((signed char *)charMask)[sym]
 82
 83int Ppmd7_DecodeSymbol(CPpmd7 *p, const IPpmd7_RangeDec *rc)
 84{
 85  size_t charMask[256 / sizeof(size_t)];
 86  if (p->MinContext->NumStats != 1)
 87  {
 88    CPpmd_State *s = Ppmd7_GetStats(p, p->MinContext);
 89    unsigned i;
 90    UInt32 count, hiCnt;
 91    if ((count = rc->GetThreshold(rc, p->MinContext->SummFreq)) < (hiCnt = s->Freq))
 92    {
 93      Byte symbol;
 94      rc->Decode(rc, 0, s->Freq);
 95      p->FoundState = s;
 96      symbol = s->Symbol;
 97      Ppmd7_Update1_0(p);
 98      return symbol;
 99    }
100    p->PrevSuccess = 0;
101    i = p->MinContext->NumStats - 1;
102    do
103    {
104      if ((hiCnt += (++s)->Freq) > count)
105      {
106        Byte symbol;
107        rc->Decode(rc, hiCnt - s->Freq, s->Freq);
108        p->FoundState = s;
109        symbol = s->Symbol;
110        Ppmd7_Update1(p);
111        return symbol;
112      }
113    }
114    while (--i);
115    if (count >= p->MinContext->SummFreq)
116      return -2;
117    p->HiBitsFlag = p->HB2Flag[p->FoundState->Symbol];
118    rc->Decode(rc, hiCnt, p->MinContext->SummFreq - hiCnt);
119    PPMD_SetAllBitsIn256Bytes(charMask);
120    MASK(s->Symbol) = 0;
121    i = p->MinContext->NumStats - 1;
122    do { MASK((--s)->Symbol) = 0; } while (--i);
123  }
124  else
125  {
126    UInt16 *prob = Ppmd7_GetBinSumm(p);
127    if (rc->DecodeBit(rc, *prob) == 0)
128    {
129      Byte symbol;
130      *prob = (UInt16)PPMD_UPDATE_PROB_0(*prob);
131      symbol = (p->FoundState = Ppmd7Context_OneState(p->MinContext))->Symbol;
132      Ppmd7_UpdateBin(p);
133      return symbol;
134    }
135    *prob = (UInt16)PPMD_UPDATE_PROB_1(*prob);
136    p->InitEsc = PPMD7_kExpEscape[*prob >> 10];
137    PPMD_SetAllBitsIn256Bytes(charMask);
138    MASK(Ppmd7Context_OneState(p->MinContext)->Symbol) = 0;
139    p->PrevSuccess = 0;
140  }
141  for (;;)
142  {
143    CPpmd_State *ps[256], *s;
144    UInt32 freqSum, count, hiCnt;
145    CPpmd_See *see;
146    unsigned i, num, numMasked = p->MinContext->NumStats;
147    do
148    {
149      p->OrderFall++;
150      if (!p->MinContext->Suffix)
151        return -1;
152      p->MinContext = Ppmd7_GetContext(p, p->MinContext->Suffix);
153    }
154    while (p->MinContext->NumStats == numMasked);
155    hiCnt = 0;
156    s = Ppmd7_GetStats(p, p->MinContext);
157    i = 0;
158    num = p->MinContext->NumStats - numMasked;
159    do
160    {
161      int k = (int)(MASK(s->Symbol));
162      hiCnt += (s->Freq & k);
163      ps[i] = s++;
164      i -= k;
165    }
166    while (i != num);
167    
168    see = Ppmd7_MakeEscFreq(p, numMasked, &freqSum);
169    freqSum += hiCnt;
170    count = rc->GetThreshold(rc, freqSum);
171    
172    if (count < hiCnt)
173    {
174      Byte symbol;
175      CPpmd_State **pps = ps;
176      for (hiCnt = 0; (hiCnt += (*pps)->Freq) <= count; pps++);
177      s = *pps;
178      rc->Decode(rc, hiCnt - s->Freq, s->Freq);
179      Ppmd_See_Update(see);
180      p->FoundState = s;
181      symbol = s->Symbol;
182      Ppmd7_Update2(p);
183      return symbol;
184    }
185    if (count >= freqSum)
186      return -2;
187    rc->Decode(rc, hiCnt, freqSum - hiCnt);
188    see->Summ = (UInt16)(see->Summ + freqSum);
189    do { MASK(ps[--i]->Symbol) = 0; } while (i != 0);
190  }
191}