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