1 /* Ppmd8Dec.c -- Ppmd8 (PPMdI) Decoder
2 2023-09-07 : Igor Pavlov : Public domain
3 This code is based on:
4 PPMd var.I (2002): Dmitry Shkarin : Public domain
5 Carryless rangecoder (1999): Dmitry Subbotin : Public domain */
6
7 #include "Precomp.h"
8
9 #include "Ppmd8.h"
10
11 #define kTop ((UInt32)1 << 24)
12 #define kBot ((UInt32)1 << 15)
13
14 #define READ_BYTE(p) IByteIn_Read((p)->Stream.In)
15
Ppmd8_Init_RangeDec(CPpmd8 * p)16 BoolInt Ppmd8_Init_RangeDec(CPpmd8 *p)
17 {
18 unsigned i;
19 p->Code = 0;
20 p->Range = 0xFFFFFFFF;
21 p->Low = 0;
22
23 for (i = 0; i < 4; i++)
24 p->Code = (p->Code << 8) | READ_BYTE(p);
25 return (p->Code < 0xFFFFFFFF);
26 }
27
28 #define RC_NORM(p) \
29 while ((p->Low ^ (p->Low + p->Range)) < kTop \
30 || (p->Range < kBot && ((p->Range = (0 - p->Low) & (kBot - 1)), 1))) { \
31 p->Code = (p->Code << 8) | READ_BYTE(p); \
32 p->Range <<= 8; p->Low <<= 8; }
33
34 // we must use only one type of Normalization from two: LOCAL or REMOTE
35 #define RC_NORM_LOCAL(p) // RC_NORM(p)
36 #define RC_NORM_REMOTE(p) RC_NORM(p)
37
38 #define R p
39
40 Z7_FORCE_INLINE
41 // Z7_NO_INLINE
Ppmd8_RD_Decode(CPpmd8 * p,UInt32 start,UInt32 size)42 static void Ppmd8_RD_Decode(CPpmd8 *p, UInt32 start, UInt32 size)
43 {
44 start *= R->Range;
45 R->Low += start;
46 R->Code -= start;
47 R->Range *= size;
48 RC_NORM_LOCAL(R)
49 }
50
51 #define RC_Decode(start, size) Ppmd8_RD_Decode(p, start, size);
52 #define RC_DecodeFinal(start, size) RC_Decode(start, size) RC_NORM_REMOTE(R)
53 #define RC_GetThreshold(total) (R->Code / (R->Range /= (total)))
54
55
56 #define CTX(ref) ((CPpmd8_Context *)Ppmd8_GetContext(p, ref))
57 // typedef CPpmd8_Context * CTX_PTR;
58 #define SUCCESSOR(p) Ppmd_GET_SUCCESSOR(p)
59 void Ppmd8_UpdateModel(CPpmd8 *p);
60
61 #define MASK(sym) ((Byte *)charMask)[sym]
62
63
Ppmd8_DecodeSymbol(CPpmd8 * p)64 int Ppmd8_DecodeSymbol(CPpmd8 *p)
65 {
66 size_t charMask[256 / sizeof(size_t)];
67
68 if (p->MinContext->NumStats != 0)
69 {
70 CPpmd_State *s = Ppmd8_GetStats(p, p->MinContext);
71 unsigned i;
72 UInt32 count, hiCnt;
73 UInt32 summFreq = p->MinContext->Union2.SummFreq;
74
75 PPMD8_CORRECT_SUM_RANGE(p, summFreq)
76
77
78 count = RC_GetThreshold(summFreq);
79 hiCnt = count;
80
81 if ((Int32)(count -= s->Freq) < 0)
82 {
83 Byte sym;
84 RC_DecodeFinal(0, s->Freq)
85 p->FoundState = s;
86 sym = s->Symbol;
87 Ppmd8_Update1_0(p);
88 return sym;
89 }
90
91 p->PrevSuccess = 0;
92 i = p->MinContext->NumStats;
93
94 do
95 {
96 if ((Int32)(count -= (++s)->Freq) < 0)
97 {
98 Byte sym;
99 RC_DecodeFinal((hiCnt - count) - s->Freq, s->Freq)
100 p->FoundState = s;
101 sym = s->Symbol;
102 Ppmd8_Update1(p);
103 return sym;
104 }
105 }
106 while (--i);
107
108 if (hiCnt >= summFreq)
109 return PPMD8_SYM_ERROR;
110
111 hiCnt -= count;
112 RC_Decode(hiCnt, summFreq - hiCnt)
113
114
115 PPMD_SetAllBitsIn256Bytes(charMask)
116 // i = p->MinContext->NumStats - 1;
117 // do { MASK((--s)->Symbol) = 0; } while (--i);
118 {
119 CPpmd_State *s2 = Ppmd8_GetStats(p, p->MinContext);
120 MASK(s->Symbol) = 0;
121 do
122 {
123 const unsigned sym0 = s2[0].Symbol;
124 const unsigned sym1 = s2[1].Symbol;
125 s2 += 2;
126 MASK(sym0) = 0;
127 MASK(sym1) = 0;
128 }
129 while (s2 < s);
130 }
131 }
132 else
133 {
134 CPpmd_State *s = Ppmd8Context_OneState(p->MinContext);
135 UInt16 *prob = Ppmd8_GetBinSumm(p);
136 UInt32 pr = *prob;
137 UInt32 size0 = (R->Range >> 14) * pr;
138 pr = PPMD_UPDATE_PROB_1(pr);
139
140 if (R->Code < size0)
141 {
142 Byte sym;
143 *prob = (UInt16)(pr + (1 << PPMD_INT_BITS));
144
145 // RangeDec_DecodeBit0(size0);
146 R->Range = size0;
147 RC_NORM(R)
148
149
150
151 // sym = (p->FoundState = Ppmd8Context_OneState(p->MinContext))->Symbol;
152 // Ppmd8_UpdateBin(p);
153 {
154 unsigned freq = s->Freq;
155 CPpmd8_Context *c = CTX(SUCCESSOR(s));
156 sym = s->Symbol;
157 p->FoundState = s;
158 p->PrevSuccess = 1;
159 p->RunLength++;
160 s->Freq = (Byte)(freq + (freq < 196));
161 // NextContext(p);
162 if (p->OrderFall == 0 && (const Byte *)c >= p->UnitsStart)
163 p->MaxContext = p->MinContext = c;
164 else
165 Ppmd8_UpdateModel(p);
166 }
167 return sym;
168 }
169
170 *prob = (UInt16)pr;
171 p->InitEsc = p->ExpEscape[pr >> 10];
172
173 // RangeDec_DecodeBit1(rc2, size0);
174 R->Low += size0;
175 R->Code -= size0;
176 R->Range = (R->Range & ~((UInt32)PPMD_BIN_SCALE - 1)) - size0;
177 RC_NORM_LOCAL(R)
178
179 PPMD_SetAllBitsIn256Bytes(charMask)
180 MASK(Ppmd8Context_OneState(p->MinContext)->Symbol) = 0;
181 p->PrevSuccess = 0;
182 }
183
184 for (;;)
185 {
186 CPpmd_State *s, *s2;
187 UInt32 freqSum, count, hiCnt;
188 UInt32 freqSum2;
189 CPpmd_See *see;
190 CPpmd8_Context *mc;
191 unsigned numMasked;
192 RC_NORM_REMOTE(R)
193 mc = p->MinContext;
194 numMasked = mc->NumStats;
195
196 do
197 {
198 p->OrderFall++;
199 if (!mc->Suffix)
200 return PPMD8_SYM_END;
201 mc = Ppmd8_GetContext(p, mc->Suffix);
202 }
203 while (mc->NumStats == numMasked);
204
205 s = Ppmd8_GetStats(p, mc);
206
207 {
208 unsigned num = (unsigned)mc->NumStats + 1;
209 unsigned num2 = num / 2;
210
211 num &= 1;
212 hiCnt = (s->Freq & (UInt32)(MASK(s->Symbol))) & (0 - (UInt32)num);
213 s += num;
214 p->MinContext = mc;
215
216 do
217 {
218 const unsigned sym0 = s[0].Symbol;
219 const unsigned sym1 = s[1].Symbol;
220 s += 2;
221 hiCnt += (s[-2].Freq & (UInt32)(MASK(sym0)));
222 hiCnt += (s[-1].Freq & (UInt32)(MASK(sym1)));
223 }
224 while (--num2);
225 }
226
227 see = Ppmd8_MakeEscFreq(p, numMasked, &freqSum);
228 freqSum += hiCnt;
229 freqSum2 = freqSum;
230 PPMD8_CORRECT_SUM_RANGE(R, freqSum2)
231
232
233 count = RC_GetThreshold(freqSum2);
234
235 if (count < hiCnt)
236 {
237 Byte sym;
238 // Ppmd_See_UPDATE(see) // new (see->Summ) value can overflow over 16-bits in some rare cases
239 s = Ppmd8_GetStats(p, p->MinContext);
240 hiCnt = count;
241
242
243 {
244 for (;;)
245 {
246 count -= s->Freq & (UInt32)(MASK((s)->Symbol)); s++; if ((Int32)count < 0) break;
247 // count -= s->Freq & (UInt32)(MASK((s)->Symbol)); s++; if ((Int32)count < 0) break;
248 }
249 }
250 s--;
251 RC_DecodeFinal((hiCnt - count) - s->Freq, s->Freq)
252
253 // new (see->Summ) value can overflow over 16-bits in some rare cases
254 Ppmd_See_UPDATE(see)
255 p->FoundState = s;
256 sym = s->Symbol;
257 Ppmd8_Update2(p);
258 return sym;
259 }
260
261 if (count >= freqSum2)
262 return PPMD8_SYM_ERROR;
263
264 RC_Decode(hiCnt, freqSum2 - hiCnt)
265
266 // We increase (see->Summ) for sum of Freqs of all non_Masked symbols.
267 // new (see->Summ) value can overflow over 16-bits in some rare cases
268 see->Summ = (UInt16)(see->Summ + freqSum);
269
270 s = Ppmd8_GetStats(p, p->MinContext);
271 s2 = s + p->MinContext->NumStats + 1;
272 do
273 {
274 MASK(s->Symbol) = 0;
275 s++;
276 }
277 while (s != s2);
278 }
279 }
280
281 #undef kTop
282 #undef kBot
283 #undef READ_BYTE
284 #undef RC_NORM_BASE
285 #undef RC_NORM_1
286 #undef RC_NORM
287 #undef RC_NORM_LOCAL
288 #undef RC_NORM_REMOTE
289 #undef R
290 #undef RC_Decode
291 #undef RC_DecodeFinal
292 #undef RC_GetThreshold
293 #undef CTX
294 #undef SUCCESSOR
295 #undef MASK
296