Line | Count | Source (jump to first uncovered line) |
1 | | /**************************************************************************** |
2 | | * This file is part of PPMd project * |
3 | | * Written and distributed to public domain by Dmitry Shkarin 1997, * |
4 | | * 1999-2000 * |
5 | | * Contents: model description and encoding/decoding routines * |
6 | | ****************************************************************************/ |
7 | | |
8 | | static const int MAX_O=64; /* maximum allowed model order */ |
9 | | const uint TOP=1 << 24, BOT=1 << 15; |
10 | | |
11 | | template <class T> |
12 | 0 | inline void _PPMD_SWAP(T& t1,T& t2) { T tmp=t1; t1=t2; t2=tmp; } |
13 | | |
14 | | |
15 | | inline RARPPM_CONTEXT* RARPPM_CONTEXT::createChild(ModelPPM *Model,RARPPM_STATE* pStats, |
16 | | RARPPM_STATE& FirstState) |
17 | 0 | { |
18 | 0 | RARPPM_CONTEXT* pc = (RARPPM_CONTEXT*) Model->SubAlloc.AllocContext(); |
19 | 0 | if ( pc ) |
20 | 0 | { |
21 | 0 | pc->NumStats=1; |
22 | 0 | pc->OneState=FirstState; |
23 | 0 | pc->Suffix=this; |
24 | 0 | pStats->Successor=pc; |
25 | 0 | } |
26 | 0 | return pc; |
27 | 0 | } |
28 | | |
29 | | |
30 | | ModelPPM::ModelPPM() |
31 | 2 | { |
32 | 2 | MinContext=NULL; |
33 | 2 | MaxContext=NULL; |
34 | 2 | MedContext=NULL; |
35 | 2 | } |
36 | | |
37 | | |
38 | | void ModelPPM::RestartModelRare() |
39 | 0 | { |
40 | 0 | int i, k, m; |
41 | 0 | memset(CharMask,0,sizeof(CharMask)); |
42 | 0 | SubAlloc.InitSubAllocator(); |
43 | 0 | InitRL=-(MaxOrder < 12 ? MaxOrder:12)-1; |
44 | 0 | MinContext = MaxContext = (RARPPM_CONTEXT*) SubAlloc.AllocContext(); |
45 | 0 | if (MinContext == NULL) |
46 | 0 | throw std::bad_alloc(); |
47 | 0 | MinContext->Suffix=NULL; |
48 | 0 | OrderFall=MaxOrder; |
49 | 0 | MinContext->U.SummFreq=(MinContext->NumStats=256)+1; |
50 | 0 | FoundState=MinContext->U.Stats=(RARPPM_STATE*)SubAlloc.AllocUnits(256/2); |
51 | 0 | if (FoundState == NULL) |
52 | 0 | throw std::bad_alloc(); |
53 | 0 | for (RunLength=InitRL, PrevSuccess=i=0;i < 256;i++) |
54 | 0 | { |
55 | 0 | MinContext->U.Stats[i].Symbol=i; |
56 | 0 | MinContext->U.Stats[i].Freq=1; |
57 | 0 | MinContext->U.Stats[i].Successor=NULL; |
58 | 0 | } |
59 | | |
60 | 0 | static const ushort InitBinEsc[]={ |
61 | 0 | 0x3CDD,0x1F3F,0x59BF,0x48F3,0x64A1,0x5ABC,0x6632,0x6051 |
62 | 0 | }; |
63 | |
|
64 | 0 | for (i=0;i < 128;i++) |
65 | 0 | for (k=0;k < 8;k++) |
66 | 0 | for (m=0;m < 64;m += 8) |
67 | 0 | BinSumm[i][k+m]=BIN_SCALE-InitBinEsc[k]/(i+2); |
68 | 0 | for (i=0;i < 25;i++) |
69 | 0 | for (k=0;k < 16;k++) |
70 | 0 | SEE2Cont[i][k].init(5*i+10); |
71 | 0 | } |
72 | | |
73 | | |
74 | | void ModelPPM::StartModelRare(int MaxOrder) |
75 | 0 | { |
76 | 0 | int i, k, m ,Step; |
77 | 0 | EscCount=1; |
78 | | /* |
79 | | if (MaxOrder < 2) |
80 | | { |
81 | | memset(CharMask,0,sizeof(CharMask)); |
82 | | OrderFall=ModelPPM::MaxOrder; |
83 | | MinContext=MaxContext; |
84 | | while (MinContext->Suffix != NULL) |
85 | | { |
86 | | MinContext=MinContext->Suffix; |
87 | | OrderFall--; |
88 | | } |
89 | | FoundState=MinContext->U.Stats; |
90 | | MinContext=MaxContext; |
91 | | } |
92 | | else |
93 | | */ |
94 | 0 | { |
95 | 0 | ModelPPM::MaxOrder=MaxOrder; |
96 | 0 | RestartModelRare(); |
97 | 0 | NS2BSIndx[0]=2*0; |
98 | 0 | NS2BSIndx[1]=2*1; |
99 | 0 | memset(NS2BSIndx+2,2*2,9); |
100 | 0 | memset(NS2BSIndx+11,2*3,256-11); |
101 | 0 | for (i=0;i < 3;i++) |
102 | 0 | NS2Indx[i]=i; |
103 | 0 | for (m=i, k=Step=1;i < 256;i++) |
104 | 0 | { |
105 | 0 | NS2Indx[i]=m; |
106 | 0 | if ( !--k ) |
107 | 0 | { |
108 | 0 | k = ++Step; |
109 | 0 | m++; |
110 | 0 | } |
111 | 0 | } |
112 | 0 | memset(HB2Flag,0,0x40); |
113 | 0 | memset(HB2Flag+0x40,0x08,0x100-0x40); |
114 | 0 | DummySEE2Cont.Shift=PERIOD_BITS; |
115 | 0 | } |
116 | 0 | } |
117 | | |
118 | | |
119 | | void RARPPM_CONTEXT::rescale(ModelPPM *Model) |
120 | 0 | { |
121 | 0 | int OldNS=NumStats, i=NumStats-1, Adder, EscFreq; |
122 | 0 | RARPPM_STATE* p1, * p; |
123 | 0 | for (p=Model->FoundState;p != U.Stats;p--) |
124 | 0 | _PPMD_SWAP(p[0],p[-1]); |
125 | 0 | U.Stats->Freq += 4; |
126 | 0 | U.SummFreq += 4; |
127 | 0 | EscFreq=U.SummFreq-p->Freq; |
128 | 0 | Adder=(Model->OrderFall != 0); |
129 | 0 | U.SummFreq = (p->Freq=(p->Freq+Adder) >> 1); |
130 | 0 | do |
131 | 0 | { |
132 | 0 | EscFreq -= (++p)->Freq; |
133 | 0 | U.SummFreq += (p->Freq=(p->Freq+Adder) >> 1); |
134 | 0 | if (p[0].Freq > p[-1].Freq) |
135 | 0 | { |
136 | 0 | RARPPM_STATE tmp=*(p1=p); |
137 | 0 | do |
138 | 0 | { |
139 | 0 | p1[0]=p1[-1]; |
140 | 0 | } while (--p1 != U.Stats && tmp.Freq > p1[-1].Freq); |
141 | 0 | *p1=tmp; |
142 | 0 | } |
143 | 0 | } while ( --i ); |
144 | 0 | if (p->Freq == 0) |
145 | 0 | { |
146 | 0 | do |
147 | 0 | { |
148 | 0 | i++; |
149 | 0 | } while ((--p)->Freq == 0); |
150 | 0 | EscFreq += i; |
151 | 0 | if ((NumStats -= i) == 1) |
152 | 0 | { |
153 | 0 | RARPPM_STATE tmp=*U.Stats; |
154 | 0 | do |
155 | 0 | { |
156 | 0 | tmp.Freq-=(tmp.Freq >> 1); |
157 | 0 | EscFreq>>=1; |
158 | 0 | } while (EscFreq > 1); |
159 | 0 | Model->SubAlloc.FreeUnits(U.Stats,(OldNS+1) >> 1); |
160 | 0 | *(Model->FoundState=&OneState)=tmp; return; |
161 | 0 | } |
162 | 0 | } |
163 | 0 | U.SummFreq += (EscFreq -= (EscFreq >> 1)); |
164 | 0 | int n0=(OldNS+1) >> 1, n1=(NumStats+1) >> 1; |
165 | 0 | if (n0 != n1) |
166 | 0 | U.Stats = (RARPPM_STATE*) Model->SubAlloc.ShrinkUnits(U.Stats,n0,n1); |
167 | 0 | Model->FoundState=U.Stats; |
168 | 0 | } |
169 | | |
170 | | |
171 | | inline RARPPM_CONTEXT* ModelPPM::CreateSuccessors(bool Skip,RARPPM_STATE* p1) |
172 | 0 | { |
173 | 0 | RARPPM_STATE UpState; |
174 | 0 | RARPPM_CONTEXT* pc=MinContext, * UpBranch=FoundState->Successor; |
175 | 0 | RARPPM_STATE * p, * ps[MAX_O], ** pps=ps; |
176 | 0 | if ( !Skip ) |
177 | 0 | { |
178 | 0 | *pps++ = FoundState; |
179 | 0 | if ( !pc->Suffix ) |
180 | 0 | goto NO_LOOP; |
181 | 0 | } |
182 | 0 | if ( p1 ) |
183 | 0 | { |
184 | 0 | p=p1; |
185 | 0 | pc=pc->Suffix; |
186 | 0 | goto LOOP_ENTRY; |
187 | 0 | } |
188 | 0 | do |
189 | 0 | { |
190 | 0 | pc=pc->Suffix; |
191 | 0 | if (pc->NumStats != 1) |
192 | 0 | { |
193 | 0 | if ((p=pc->U.Stats)->Symbol != FoundState->Symbol) |
194 | 0 | do |
195 | 0 | { |
196 | 0 | p++; |
197 | 0 | } while (p->Symbol != FoundState->Symbol); |
198 | 0 | } |
199 | 0 | else |
200 | 0 | p=&(pc->OneState); |
201 | 0 | LOOP_ENTRY: |
202 | 0 | if (p->Successor != UpBranch) |
203 | 0 | { |
204 | 0 | pc=p->Successor; |
205 | 0 | break; |
206 | |
|
207 | 0 | } |
208 | | // We ensure that PPM order input parameter does not exceed MAX_O (64), |
209 | | // so we do not really need this check and added it for extra safety. |
210 | | // See CVE-2017-17969 for details. |
211 | 0 | if (pps>=ps+ASIZE(ps)) |
212 | 0 | return NULL; |
213 | | |
214 | 0 | *pps++ = p; |
215 | 0 | } while ( pc->Suffix ); |
216 | 0 | NO_LOOP: |
217 | 0 | if (pps == ps) |
218 | 0 | return pc; |
219 | 0 | UpState.Symbol=*(byte*) UpBranch; |
220 | 0 | UpState.Successor=(RARPPM_CONTEXT*) (((byte*) UpBranch)+1); |
221 | 0 | if (pc->NumStats != 1) |
222 | 0 | { |
223 | 0 | if ((byte*) pc <= SubAlloc.pText) |
224 | 0 | return(NULL); |
225 | 0 | if ((p=pc->U.Stats)->Symbol != UpState.Symbol) |
226 | 0 | do |
227 | 0 | { |
228 | 0 | p++; |
229 | 0 | } while (p->Symbol != UpState.Symbol); |
230 | 0 | uint cf=p->Freq-1; |
231 | 0 | uint s0=pc->U.SummFreq-pc->NumStats-cf; |
232 | 0 | UpState.Freq=1+((2*cf <= s0)?(5*cf > s0):((2*cf+3*s0-1)/(2*s0))); |
233 | 0 | } |
234 | 0 | else |
235 | 0 | UpState.Freq=pc->OneState.Freq; |
236 | 0 | do |
237 | 0 | { |
238 | 0 | pc = pc->createChild(this,*--pps,UpState); |
239 | 0 | if ( !pc ) |
240 | 0 | return NULL; |
241 | 0 | } while (pps != ps); |
242 | 0 | return pc; |
243 | 0 | } |
244 | | |
245 | | |
246 | | inline void ModelPPM::UpdateModel() |
247 | 0 | { |
248 | 0 | RARPPM_STATE fs = *FoundState, *p = NULL; |
249 | 0 | RARPPM_CONTEXT *pc, *Successor; |
250 | 0 | uint ns1, ns, cf, sf, s0; |
251 | 0 | if (fs.Freq < MAX_FREQ/4 && (pc=MinContext->Suffix) != NULL) |
252 | 0 | { |
253 | 0 | if (pc->NumStats != 1) |
254 | 0 | { |
255 | 0 | if ((p=pc->U.Stats)->Symbol != fs.Symbol) |
256 | 0 | { |
257 | 0 | do |
258 | 0 | { |
259 | 0 | p++; |
260 | 0 | } while (p->Symbol != fs.Symbol); |
261 | 0 | if (p[0].Freq >= p[-1].Freq) |
262 | 0 | { |
263 | 0 | _PPMD_SWAP(p[0],p[-1]); |
264 | 0 | p--; |
265 | 0 | } |
266 | 0 | } |
267 | 0 | if (p->Freq < MAX_FREQ-9) |
268 | 0 | { |
269 | 0 | p->Freq += 2; |
270 | 0 | pc->U.SummFreq += 2; |
271 | 0 | } |
272 | 0 | } |
273 | 0 | else |
274 | 0 | { |
275 | 0 | p=&(pc->OneState); |
276 | 0 | p->Freq += (p->Freq < 32); |
277 | 0 | } |
278 | 0 | } |
279 | 0 | if ( !OrderFall ) |
280 | 0 | { |
281 | 0 | MinContext=MaxContext=FoundState->Successor=CreateSuccessors(TRUE,p); |
282 | 0 | if ( !MinContext ) |
283 | 0 | goto RESTART_MODEL; |
284 | 0 | return; |
285 | 0 | } |
286 | 0 | *SubAlloc.pText++ = fs.Symbol; |
287 | 0 | Successor = (RARPPM_CONTEXT*) SubAlloc.pText; |
288 | 0 | if (SubAlloc.pText >= SubAlloc.FakeUnitsStart) |
289 | 0 | goto RESTART_MODEL; |
290 | 0 | if ( fs.Successor ) |
291 | 0 | { |
292 | 0 | if ((byte*) fs.Successor <= SubAlloc.pText && |
293 | 0 | (fs.Successor=CreateSuccessors(FALSE,p)) == NULL) |
294 | 0 | goto RESTART_MODEL; |
295 | 0 | if ( !--OrderFall ) |
296 | 0 | { |
297 | 0 | Successor=fs.Successor; |
298 | 0 | SubAlloc.pText -= (MaxContext != MinContext); |
299 | 0 | } |
300 | 0 | } |
301 | 0 | else |
302 | 0 | { |
303 | 0 | FoundState->Successor=Successor; |
304 | 0 | fs.Successor=MinContext; |
305 | 0 | } |
306 | 0 | s0=MinContext->U.SummFreq-(ns=MinContext->NumStats)-(fs.Freq-1); |
307 | 0 | for (pc=MaxContext;pc != MinContext;pc=pc->Suffix) |
308 | 0 | { |
309 | 0 | if ((ns1=pc->NumStats) != 1) |
310 | 0 | { |
311 | 0 | if ((ns1 & 1) == 0) |
312 | 0 | { |
313 | 0 | pc->U.Stats=(RARPPM_STATE*) SubAlloc.ExpandUnits(pc->U.Stats,ns1 >> 1); |
314 | 0 | if ( !pc->U.Stats ) |
315 | 0 | goto RESTART_MODEL; |
316 | 0 | } |
317 | 0 | pc->U.SummFreq += (2*ns1 < ns)+2*((4*ns1 <= ns) & (pc->U.SummFreq <= 8*ns1)); |
318 | 0 | } |
319 | 0 | else |
320 | 0 | { |
321 | 0 | p=(RARPPM_STATE*) SubAlloc.AllocUnits(1); |
322 | 0 | if ( !p ) |
323 | 0 | goto RESTART_MODEL; |
324 | 0 | *p=pc->OneState; |
325 | 0 | pc->U.Stats=p; |
326 | 0 | if (p->Freq < MAX_FREQ/4-1) |
327 | 0 | p->Freq += p->Freq; |
328 | 0 | else |
329 | 0 | p->Freq = MAX_FREQ-4; |
330 | 0 | pc->U.SummFreq=p->Freq+InitEsc+(ns > 3); |
331 | 0 | } |
332 | 0 | cf=2*fs.Freq*(pc->U.SummFreq+6); |
333 | 0 | sf=s0+pc->U.SummFreq; |
334 | 0 | if (cf < 6*sf) |
335 | 0 | { |
336 | 0 | cf=1+(cf > sf)+(cf >= 4*sf); |
337 | 0 | pc->U.SummFreq += 3; |
338 | 0 | } |
339 | 0 | else |
340 | 0 | { |
341 | 0 | cf=4+(cf >= 9*sf)+(cf >= 12*sf)+(cf >= 15*sf); |
342 | 0 | pc->U.SummFreq += cf; |
343 | 0 | } |
344 | 0 | p=pc->U.Stats+ns1; |
345 | 0 | p->Successor=Successor; |
346 | 0 | p->Symbol = fs.Symbol; |
347 | 0 | p->Freq = cf; |
348 | 0 | pc->NumStats=++ns1; |
349 | 0 | } |
350 | 0 | MaxContext=MinContext=fs.Successor; |
351 | 0 | return; |
352 | 0 | RESTART_MODEL: |
353 | 0 | RestartModelRare(); |
354 | 0 | EscCount=0; |
355 | 0 | } |
356 | | |
357 | | |
358 | | // Tabulated escapes for exponential symbol distribution |
359 | | static const byte ExpEscape[16]={ 25,14, 9, 7, 5, 5, 4, 4, 4, 3, 3, 3, 2, 2, 2, 2 }; |
360 | | #define GET_MEAN(SUMM,SHIFT,ROUND) ((SUMM+(1 << (SHIFT-ROUND))) >> (SHIFT)) |
361 | | |
362 | | |
363 | | |
364 | | inline void RARPPM_CONTEXT::decodeBinSymbol(ModelPPM *Model) |
365 | 0 | { |
366 | 0 | RARPPM_STATE& rs=OneState; |
367 | 0 | Model->HiBitsFlag=Model->HB2Flag[Model->FoundState->Symbol]; |
368 | 0 | ushort& bs=Model->BinSumm[rs.Freq-1][Model->PrevSuccess+ |
369 | 0 | Model->NS2BSIndx[Suffix->NumStats-1]+ |
370 | 0 | Model->HiBitsFlag+2*Model->HB2Flag[rs.Symbol]+ |
371 | 0 | ((Model->RunLength >> 26) & 0x20)]; |
372 | 0 | if (Model->Coder.GetCurrentShiftCount(TOT_BITS) < bs) |
373 | 0 | { |
374 | 0 | Model->FoundState=&rs; |
375 | 0 | rs.Freq += (rs.Freq < 128); |
376 | 0 | Model->Coder.SubRange.LowCount=0; |
377 | 0 | Model->Coder.SubRange.HighCount=bs; |
378 | 0 | bs = GET_SHORT16(bs+INTERVAL-GET_MEAN(bs,PERIOD_BITS,2)); |
379 | 0 | Model->PrevSuccess=1; |
380 | 0 | Model->RunLength++; |
381 | 0 | } |
382 | 0 | else |
383 | 0 | { |
384 | 0 | Model->Coder.SubRange.LowCount=bs; |
385 | 0 | bs = GET_SHORT16(bs-GET_MEAN(bs,PERIOD_BITS,2)); |
386 | 0 | Model->Coder.SubRange.HighCount=BIN_SCALE; |
387 | 0 | Model->InitEsc=ExpEscape[bs >> 10]; |
388 | 0 | Model->NumMasked=1; |
389 | 0 | Model->CharMask[rs.Symbol]=Model->EscCount; |
390 | 0 | Model->PrevSuccess=0; |
391 | 0 | Model->FoundState=NULL; |
392 | 0 | } |
393 | 0 | } |
394 | | |
395 | | |
396 | | inline void RARPPM_CONTEXT::update1(ModelPPM *Model,RARPPM_STATE* p) |
397 | 0 | { |
398 | 0 | (Model->FoundState=p)->Freq += 4; |
399 | 0 | U.SummFreq += 4; |
400 | 0 | if (p[0].Freq > p[-1].Freq) |
401 | 0 | { |
402 | 0 | _PPMD_SWAP(p[0],p[-1]); |
403 | 0 | Model->FoundState=--p; |
404 | 0 | if (p->Freq > MAX_FREQ) |
405 | 0 | rescale(Model); |
406 | 0 | } |
407 | 0 | } |
408 | | |
409 | | |
410 | | |
411 | | |
412 | | inline bool RARPPM_CONTEXT::decodeSymbol1(ModelPPM *Model) |
413 | 0 | { |
414 | 0 | Model->Coder.SubRange.scale=U.SummFreq; |
415 | 0 | RARPPM_STATE* p=U.Stats; |
416 | 0 | int i, HiCnt; |
417 | 0 | int count=Model->Coder.GetCurrentCount(); |
418 | 0 | if (count>=(int)Model->Coder.SubRange.scale) |
419 | 0 | return(false); |
420 | 0 | if (count < (HiCnt=p->Freq)) |
421 | 0 | { |
422 | 0 | Model->PrevSuccess=(2*(Model->Coder.SubRange.HighCount=HiCnt) > Model->Coder.SubRange.scale); |
423 | 0 | Model->RunLength += Model->PrevSuccess; |
424 | 0 | (Model->FoundState=p)->Freq=(HiCnt += 4); |
425 | 0 | U.SummFreq += 4; |
426 | 0 | if (HiCnt > MAX_FREQ) |
427 | 0 | rescale(Model); |
428 | 0 | Model->Coder.SubRange.LowCount=0; |
429 | 0 | return(true); |
430 | 0 | } |
431 | 0 | else |
432 | 0 | if (Model->FoundState==NULL) |
433 | 0 | return(false); |
434 | 0 | Model->PrevSuccess=0; |
435 | 0 | i=NumStats-1; |
436 | 0 | while ((HiCnt += (++p)->Freq) <= count) |
437 | 0 | if (--i == 0) |
438 | 0 | { |
439 | 0 | Model->HiBitsFlag=Model->HB2Flag[Model->FoundState->Symbol]; |
440 | 0 | Model->Coder.SubRange.LowCount=HiCnt; |
441 | 0 | Model->CharMask[p->Symbol]=Model->EscCount; |
442 | 0 | i=(Model->NumMasked=NumStats)-1; |
443 | 0 | Model->FoundState=NULL; |
444 | 0 | do |
445 | 0 | { |
446 | 0 | Model->CharMask[(--p)->Symbol]=Model->EscCount; |
447 | 0 | } while ( --i ); |
448 | 0 | Model->Coder.SubRange.HighCount=Model->Coder.SubRange.scale; |
449 | 0 | return(true); |
450 | 0 | } |
451 | 0 | Model->Coder.SubRange.LowCount=(Model->Coder.SubRange.HighCount=HiCnt)-p->Freq; |
452 | 0 | update1(Model,p); |
453 | 0 | return(true); |
454 | 0 | } |
455 | | |
456 | | |
457 | | inline void RARPPM_CONTEXT::update2(ModelPPM *Model,RARPPM_STATE* p) |
458 | 0 | { |
459 | 0 | (Model->FoundState=p)->Freq += 4; |
460 | 0 | U.SummFreq += 4; |
461 | 0 | if (p->Freq > MAX_FREQ) |
462 | 0 | rescale(Model); |
463 | 0 | Model->EscCount++; |
464 | 0 | Model->RunLength=Model->InitRL; |
465 | 0 | } |
466 | | |
467 | | |
468 | | inline RARPPM_SEE2_CONTEXT* RARPPM_CONTEXT::makeEscFreq2(ModelPPM *Model,int Diff) |
469 | 0 | { |
470 | 0 | RARPPM_SEE2_CONTEXT* psee2c; |
471 | 0 | if (NumStats != 256) |
472 | 0 | { |
473 | 0 | psee2c=Model->SEE2Cont[Model->NS2Indx[Diff-1]]+ |
474 | 0 | (Diff < Suffix->NumStats-NumStats)+ |
475 | 0 | 2*(U.SummFreq < 11*NumStats)+4*(Model->NumMasked > Diff)+ |
476 | 0 | Model->HiBitsFlag; |
477 | 0 | Model->Coder.SubRange.scale=psee2c->getMean(); |
478 | 0 | } |
479 | 0 | else |
480 | 0 | { |
481 | 0 | psee2c=&Model->DummySEE2Cont; |
482 | 0 | Model->Coder.SubRange.scale=1; |
483 | 0 | } |
484 | 0 | return psee2c; |
485 | 0 | } |
486 | | |
487 | | |
488 | | |
489 | | |
490 | | inline bool RARPPM_CONTEXT::decodeSymbol2(ModelPPM *Model) |
491 | 0 | { |
492 | 0 | int count, HiCnt, i=NumStats-Model->NumMasked; |
493 | 0 | RARPPM_SEE2_CONTEXT* psee2c=makeEscFreq2(Model,i); |
494 | 0 | RARPPM_STATE* ps[256], ** pps=ps, * p=U.Stats-1; |
495 | 0 | HiCnt=0; |
496 | 0 | do |
497 | 0 | { |
498 | 0 | do |
499 | 0 | { |
500 | 0 | p++; |
501 | 0 | } while (Model->CharMask[p->Symbol] == Model->EscCount); |
502 | 0 | HiCnt += p->Freq; |
503 | | |
504 | | // We do not reuse PPMd coder in unstable state, so we do not really need |
505 | | // this check and added it for extra safety. See CVE-2017-17969 for details. |
506 | 0 | if (pps>=ps+ASIZE(ps)) |
507 | 0 | return false; |
508 | | |
509 | 0 | *pps++ = p; |
510 | 0 | } while ( --i ); |
511 | 0 | Model->Coder.SubRange.scale += HiCnt; |
512 | 0 | count=Model->Coder.GetCurrentCount(); |
513 | 0 | if (count>=(int)Model->Coder.SubRange.scale) |
514 | 0 | return(false); |
515 | 0 | p=*(pps=ps); |
516 | 0 | if (count < HiCnt) |
517 | 0 | { |
518 | 0 | HiCnt=0; |
519 | 0 | while ((HiCnt += p->Freq) <= count) |
520 | 0 | { |
521 | 0 | pps++; |
522 | 0 | if (pps>=ps+ASIZE(ps)) // Extra safety check. |
523 | 0 | return false; |
524 | 0 | p=*pps; |
525 | 0 | } |
526 | 0 | Model->Coder.SubRange.LowCount = (Model->Coder.SubRange.HighCount=HiCnt)-p->Freq; |
527 | 0 | psee2c->update(); |
528 | 0 | update2(Model,p); |
529 | 0 | } |
530 | 0 | else |
531 | 0 | { |
532 | 0 | Model->Coder.SubRange.LowCount=HiCnt; |
533 | 0 | Model->Coder.SubRange.HighCount=Model->Coder.SubRange.scale; |
534 | 0 | i=NumStats-Model->NumMasked; |
535 | 0 | pps--; |
536 | 0 | do |
537 | 0 | { |
538 | 0 | pps++; |
539 | 0 | if (pps>=ps+ASIZE(ps)) // Extra safety check. |
540 | 0 | return false; |
541 | 0 | Model->CharMask[(*pps)->Symbol]=Model->EscCount; |
542 | 0 | } while ( --i ); |
543 | 0 | psee2c->Summ += Model->Coder.SubRange.scale; |
544 | 0 | Model->NumMasked = NumStats; |
545 | 0 | } |
546 | 0 | return true; |
547 | 0 | } |
548 | | |
549 | | |
550 | | inline void ModelPPM::ClearMask() |
551 | 0 | { |
552 | 0 | EscCount=1; |
553 | 0 | memset(CharMask,0,sizeof(CharMask)); |
554 | 0 | } |
555 | | |
556 | | |
557 | | |
558 | | |
559 | | // reset PPM variables after data error allowing safe resuming |
560 | | // of further data processing |
561 | | void ModelPPM::CleanUp() |
562 | 0 | { |
563 | 0 | SubAlloc.StopSubAllocator(); |
564 | 0 | SubAlloc.StartSubAllocator(1); |
565 | 0 | StartModelRare(2); |
566 | 0 | } |
567 | | |
568 | | |
569 | | bool ModelPPM::DecodeInit(Unpack *UnpackRead,int &EscChar) |
570 | 0 | { |
571 | 0 | int MaxOrder=UnpackRead->GetChar(); |
572 | 0 | bool Reset=(MaxOrder & 0x20)!=0; |
573 | |
|
574 | 0 | int MaxMB; |
575 | 0 | if (Reset) |
576 | 0 | MaxMB=UnpackRead->GetChar(); |
577 | 0 | else |
578 | 0 | if (SubAlloc.GetAllocatedMemory()==0) |
579 | 0 | return(false); |
580 | 0 | if (MaxOrder & 0x40) |
581 | 0 | EscChar=UnpackRead->GetChar(); |
582 | 0 | Coder.InitDecoder(UnpackRead); |
583 | 0 | if (Reset) |
584 | 0 | { |
585 | 0 | MaxOrder=(MaxOrder & 0x1f)+1; |
586 | 0 | if (MaxOrder>16) |
587 | 0 | MaxOrder=16+(MaxOrder-16)*3; |
588 | 0 | if (MaxOrder==1) |
589 | 0 | { |
590 | 0 | SubAlloc.StopSubAllocator(); |
591 | 0 | return(false); |
592 | 0 | } |
593 | 0 | SubAlloc.StartSubAllocator(MaxMB+1); |
594 | 0 | StartModelRare(MaxOrder); |
595 | 0 | } |
596 | 0 | return(MinContext!=NULL); |
597 | 0 | } |
598 | | |
599 | | |
600 | | int ModelPPM::DecodeChar() |
601 | 0 | { |
602 | 0 | if ((byte*)MinContext <= SubAlloc.pText || (byte*)MinContext>SubAlloc.HeapEnd) |
603 | 0 | return(-1); |
604 | 0 | if (MinContext->NumStats != 1) |
605 | 0 | { |
606 | 0 | if ((byte*)MinContext->U.Stats <= SubAlloc.pText || (byte*)MinContext->U.Stats>SubAlloc.HeapEnd) |
607 | 0 | return(-1); |
608 | 0 | if (!MinContext->decodeSymbol1(this)) |
609 | 0 | return(-1); |
610 | 0 | } |
611 | 0 | else |
612 | 0 | MinContext->decodeBinSymbol(this); |
613 | 0 | Coder.Decode(); |
614 | 0 | while ( !FoundState ) |
615 | 0 | { |
616 | 0 | ARI_DEC_NORMALIZE(Coder.code,Coder.low,Coder.range,Coder.UnpackRead); |
617 | 0 | do |
618 | 0 | { |
619 | 0 | OrderFall++; |
620 | 0 | MinContext=MinContext->Suffix; |
621 | 0 | if ((byte*)MinContext <= SubAlloc.pText || (byte*)MinContext>SubAlloc.HeapEnd) |
622 | 0 | return(-1); |
623 | 0 | } while (MinContext->NumStats == NumMasked); |
624 | 0 | if (!MinContext->decodeSymbol2(this)) |
625 | 0 | return(-1); |
626 | 0 | Coder.Decode(); |
627 | 0 | } |
628 | 0 | int Symbol=FoundState->Symbol; |
629 | 0 | if (!OrderFall && (byte*) FoundState->Successor > SubAlloc.pText) |
630 | 0 | MinContext=MaxContext=FoundState->Successor; |
631 | 0 | else |
632 | 0 | { |
633 | 0 | UpdateModel(); |
634 | 0 | if (EscCount == 0) |
635 | 0 | ClearMask(); |
636 | 0 | } |
637 | 0 | ARI_DEC_NORMALIZE(Coder.code,Coder.low,Coder.range,Coder.UnpackRead); |
638 | 0 | return(Symbol); |
639 | 0 | } |