1 /****************************************************************************
2 * This file is part of PPMd project *
3 * Written and distributed to public domain by Dmitry Shkarin 1997, *
4 * 1999-2001 *
5 * Contents: PPMII model description and encoding/decoding routines *
6 ****************************************************************************/
7 #include <string.h>
8 #include "PPMd.h"
9 #pragma hdrstop
10 #include "Coder.hpp"
11 #include "SubAlloc.hpp"
12
13 enum { UP_FREQ=5, INT_BITS=7, PERIOD_BITS=7, TOT_BITS=INT_BITS+PERIOD_BITS,
14 INTERVAL=1 << INT_BITS, BIN_SCALE=1 << TOT_BITS, MAX_FREQ=124, O_BOUND=9 };
15
16 #pragma pack(1)
17 static struct SEE2_CONTEXT { // SEE-contexts for PPM-contexts with masked symbols
18 WORD Summ;
19 BYTE Shift, Count;
initSEE2_CONTEXT20 void init(UINT InitVal) { Summ=InitVal << (Shift=PERIOD_BITS-4); Count=7; }
getMeanSEE2_CONTEXT21 UINT getMean() {
22 UINT RetVal=(Summ >> Shift); Summ -= RetVal;
23 return RetVal+(RetVal == 0);
24 }
updateSEE2_CONTEXT25 void update() {
26 if (Shift < PERIOD_BITS && --Count == 0) {
27 Summ += Summ; Count=3 << Shift++;
28 }
29 }
30 } _PACK_ATTR SEE2Cont[24][32], DummySEE2Cont;
31 static struct PPM_CONTEXT { // Notes:
32 BYTE NumStats, Flags; // 1. NumStats & NumMasked contain
33 WORD SummFreq; // number of symbols minus 1
34 struct STATE { // 2. sizeof(WORD) > sizeof(BYTE)
35 BYTE Symbol, Freq; // 3. contexts example:
36 PPM_CONTEXT* Successor; // MaxOrder:
37 } _PACK_ATTR * Stats; // ABCD context
38 PPM_CONTEXT* Suffix; // BCD suffix
39 inline void encodeBinSymbol(int symbol);// BCDE successor
40 inline void encodeSymbol1(int symbol);// other orders:
41 inline void encodeSymbol2(int symbol);// BCD context
42 inline void decodeBinSymbol();// CD suffix
43 inline void decodeSymbol1();// BCDE successor
44 inline void decodeSymbol2();
45 inline void update1(STATE* p);
46 inline void update2(STATE* p);
47 inline SEE2_CONTEXT* makeEscFreq2();
48 void rescale();
49 void refresh(int OldNU,BOOL Scale);
50 PPM_CONTEXT* cutOff(int Order);
51 PPM_CONTEXT* removeBinConts(int Order);
oneStatePPM_CONTEXT52 STATE& oneState() const { return (STATE&) SummFreq; }
53 } _PACK_ATTR* MaxContext;
54 #pragma pack()
55
56 static BYTE NS2BSIndx[256], QTable[260]; // constants
57 static PPM_CONTEXT::STATE* FoundState; // found next state transition
58 static int InitEsc, OrderFall, RunLength, InitRL, MaxOrder;
59 static BYTE CharMask[256], NumMasked, PrevSuccess, EscCount, PrintCount;
60 static WORD BinSumm[25][64]; // binary SEE-contexts
61 static MR_METHOD MRMethod;
62
SWAP(PPM_CONTEXT::STATE & s1,PPM_CONTEXT::STATE & s2)63 inline void SWAP(PPM_CONTEXT::STATE& s1,PPM_CONTEXT::STATE& s2)
64 {
65 PPM_CONTEXT::STATE t1 = s1;
66 s1 = s2;
67 s2 = t1;
68 }
69
StateCpy(PPM_CONTEXT::STATE & s1,const PPM_CONTEXT::STATE & s2)70 inline void StateCpy(PPM_CONTEXT::STATE& s1,const PPM_CONTEXT::STATE& s2)
71 {
72 s1 = s2;
73 }
74 struct PPMD_STARTUP { inline PPMD_STARTUP(); } PPMd_StartUp;
PPMD_STARTUP()75 inline PPMD_STARTUP::PPMD_STARTUP() // constants initialization
76 {
77 UINT i, k, m, Step;
78 for (i=0,k=1;i < N1 ;i++,k += 1) Indx2Units[i]=k;
79 for (k++;i < N1+N2 ;i++,k += 2) Indx2Units[i]=k;
80 for (k++;i < N1+N2+N3 ;i++,k += 3) Indx2Units[i]=k;
81 for (k++;i < N1+N2+N3+N4;i++,k += 4) Indx2Units[i]=k;
82 for (k=i=0;k < 128;k++) {
83 i += (Indx2Units[i] < k+1); Units2Indx[k]=i;
84 }
85 NS2BSIndx[0]=2*0; NS2BSIndx[1]=2*1;
86 memset(NS2BSIndx+2,2*2,9); memset(NS2BSIndx+11,2*3,256-11);
87 for (i=0;i < UP_FREQ;i++) QTable[i]=i;
88 for (m=i=UP_FREQ, k=Step=1;i < 260;i++) {
89 QTable[i]=m;
90 if ( !--k ) { k = ++Step; m++; }
91 }
92 DummySEE2Cont.Summ = (PPMdSignature & 0xffff0000) >> 16;
93 DummySEE2Cont.Shift = (PPMdSignature & 0xff00) >> 8;
94 DummySEE2Cont.Count = (PPMdSignature & 0xff);
95 }
StartModelRare(int MaxOrder,MR_METHOD MRMethod)96 static void _STDCALL StartModelRare(int MaxOrder,MR_METHOD MRMethod)
97 {
98 UINT i, k, m;
99 memset(CharMask,0,sizeof(CharMask)); EscCount=PrintCount=1;
100 if (MaxOrder < 2) { // we are in solid mode
101 OrderFall=::MaxOrder;
102 for (PPM_CONTEXT* pc=MaxContext;pc->Suffix != NULL;pc=pc->Suffix)
103 OrderFall--;
104 return;
105 }
106 OrderFall=::MaxOrder=MaxOrder; ::MRMethod=MRMethod;
107 InitSubAllocator();
108 RunLength=InitRL=-((MaxOrder < 12)?MaxOrder:12)-1;
109 MaxContext = (PPM_CONTEXT*) AllocContext();
110 MaxContext->Suffix=NULL;
111 MaxContext->SummFreq=(MaxContext->NumStats=255)+2;
112 MaxContext->Stats = (PPM_CONTEXT::STATE*) AllocUnits(256/2);
113 for (PrevSuccess=i=0;i < 256;i++) {
114 MaxContext->Stats[i].Symbol=i; MaxContext->Stats[i].Freq=1;
115 MaxContext->Stats[i].Successor=NULL;
116 }
117 static const WORD InitBinEsc[]={0x3CDD,0x1F3F,0x59BF,0x48F3,0x64A1,0x5ABC,0x6632,0x6051};
118 for (i=m=0;m < 25;m++) {
119 while (QTable[i] == m) i++;
120 for (k=0;k < 8;k++)
121 BinSumm[m][k]=BIN_SCALE-InitBinEsc[k]/(i+1);
122 for (k=8;k < 64;k += 8)
123 memcpy(BinSumm[m]+k,BinSumm[m],8*sizeof(WORD));
124 }
125 for (i=m=0;m < 24;m++) {
126 while (QTable[i+3] == m+3) i++;
127 SEE2Cont[m][0].init(2*i+5);
128 for (k=1;k < 32;k++) SEE2Cont[m][k]=SEE2Cont[m][0];
129 }
130 }
refresh(int OldNU,BOOL Scale)131 void PPM_CONTEXT::refresh(int OldNU,BOOL Scale)
132 {
133 int i=NumStats, EscFreq;
134 STATE* p = Stats = (STATE*) ShrinkUnits(Stats,OldNU,(i+2) >> 1);
135 Flags=(Flags & (0x10+0x04*Scale))+0x08*(p->Symbol >= 0x40);
136 EscFreq=SummFreq-p->Freq;
137 SummFreq = (p->Freq=(p->Freq+Scale) >> Scale);
138 do {
139 EscFreq -= (++p)->Freq;
140 SummFreq += (p->Freq=(p->Freq+Scale) >> Scale);
141 Flags |= 0x08*(p->Symbol >= 0x40);
142 } while ( --i );
143 SummFreq += (EscFreq=(EscFreq+Scale) >> Scale);
144 }
145 #define P_CALL(F) ( PrefetchData(p->Successor), \
146 p->Successor=p->Successor->F(Order+1))
cutOff(int Order)147 PPM_CONTEXT* PPM_CONTEXT::cutOff(int Order)
148 {
149 int i, tmp;
150 STATE* p;
151 if ( !NumStats ) {
152 if ((BYTE*) (p=&oneState())->Successor >= UnitsStart) {
153 if (Order < MaxOrder) P_CALL(cutOff);
154 else p->Successor=NULL;
155 if (!p->Successor && Order > O_BOUND)
156 goto REMOVE;
157 return this;
158 } else {
159 REMOVE: SpecialFreeUnit(this); return NULL;
160 }
161 }
162 PrefetchData(Stats);
163 Stats = (STATE*) MoveUnitsUp(Stats,tmp=(NumStats+2) >> 1);
164 for (p=Stats+(i=NumStats);p >= Stats;p--)
165 if ((BYTE*) p->Successor < UnitsStart) {
166 p->Successor=NULL; SWAP(*p,Stats[i--]);
167 } else if (Order < MaxOrder) P_CALL(cutOff);
168 else p->Successor=NULL;
169 if (i != NumStats && Order) {
170 NumStats=i; p=Stats;
171 if (i < 0) { FreeUnits(p,tmp); goto REMOVE; }
172 else if (i == 0) {
173 Flags=(Flags & 0x10)+0x08*(p->Symbol >= 0x40);
174 StateCpy(oneState(),*p); FreeUnits(p,tmp);
175 oneState().Freq=(oneState().Freq+11) >> 3;
176 } else refresh(tmp,SummFreq > 16*i);
177 }
178 return this;
179 }
removeBinConts(int Order)180 PPM_CONTEXT* PPM_CONTEXT::removeBinConts(int Order)
181 {
182 STATE* p;
183 if ( !NumStats ) {
184 p=&oneState();
185 if ((BYTE*) p->Successor >= UnitsStart && Order < MaxOrder)
186 P_CALL(removeBinConts);
187 else p->Successor=NULL;
188 if (!p->Successor && (!Suffix->NumStats || Suffix->Flags == 0xFF)) {
189 FreeUnits(this,1); return NULL;
190 } else return this;
191 }
192 PrefetchData(Stats);
193 for (p=Stats+NumStats;p >= Stats;p--)
194 if ((BYTE*) p->Successor >= UnitsStart && Order < MaxOrder)
195 P_CALL(removeBinConts);
196 else p->Successor=NULL;
197 return this;
198 }
RestoreModelRare(PPM_CONTEXT * pc1,PPM_CONTEXT * MinContext,PPM_CONTEXT * FSuccessor)199 static void RestoreModelRare(PPM_CONTEXT* pc1,PPM_CONTEXT* MinContext,
200 PPM_CONTEXT* FSuccessor)
201 {
202 PPM_CONTEXT* pc;
203 PPM_CONTEXT::STATE* p;
204 for (pc=MaxContext, pText=HeapStart;pc != pc1;pc=pc->Suffix)
205 if (--(pc->NumStats) == 0) {
206 pc->Flags=(pc->Flags & 0x10)+0x08*(pc->Stats->Symbol >= 0x40);
207 p=pc->Stats; StateCpy(pc->oneState(),*p);
208 SpecialFreeUnit(p);
209 pc->oneState().Freq=(pc->oneState().Freq+11) >> 3;
210 } else
211 pc->refresh((pc->NumStats+3) >> 1,FALSE);
212 for ( ;pc != MinContext;pc=pc->Suffix)
213 if ( !pc->NumStats )
214 pc->oneState().Freq -= pc->oneState().Freq >> 1;
215 else if ((pc->SummFreq += 4) > 128+4*pc->NumStats)
216 pc->refresh((pc->NumStats+2) >> 1,TRUE);
217 if (MRMethod > MRM_FREEZE) {
218 MaxContext=FSuccessor; GlueCount += !(BList[1].Stamp & 1);
219 } else if (MRMethod == MRM_FREEZE) {
220 while ( MaxContext->Suffix ) MaxContext=MaxContext->Suffix;
221 MaxContext->removeBinConts(0); MRMethod=MR_METHOD(MRMethod+1);
222 GlueCount=0; OrderFall=MaxOrder;
223 } else if (MRMethod == MRM_RESTART || GetUsedMemory() < (SubAllocatorSize >> 1)) {
224 StartModelRare(MaxOrder,MRMethod);
225 EscCount=0; PrintCount=0xFF;
226 } else {
227 while ( MaxContext->Suffix ) MaxContext=MaxContext->Suffix;
228 do {
229 MaxContext->cutOff(0); ExpandTextArea();
230 } while (GetUsedMemory() > 3*(SubAllocatorSize >> 2));
231 GlueCount=0; OrderFall=MaxOrder;
232 }
233 }
234 static PPM_CONTEXT* _FASTCALL CreateSuccessors(BOOL Skip,PPM_CONTEXT::STATE* p,
235 PPM_CONTEXT* pc);
ReduceOrder(PPM_CONTEXT::STATE * p,PPM_CONTEXT * pc)236 static PPM_CONTEXT* _FASTCALL ReduceOrder(PPM_CONTEXT::STATE* p,PPM_CONTEXT* pc)
237 {
238 PPM_CONTEXT::STATE* p1, * ps[MAX_O], ** pps=ps;
239 PPM_CONTEXT* pc1=pc, * UpBranch = (PPM_CONTEXT*) pText;
240 BYTE tmp, sym=FoundState->Symbol;
241 *pps++ = FoundState; FoundState->Successor=UpBranch;
242 OrderFall++;
243 if ( p ) { pc=pc->Suffix; goto LOOP_ENTRY; }
244 for ( ; ; ) {
245 if ( !pc->Suffix ) {
246 if (MRMethod > MRM_FREEZE) {
247 FROZEN: do { (*--pps)->Successor = pc; } while (pps != ps);
248 pText=HeapStart+1; OrderFall=1;
249 }
250 return pc;
251 }
252 pc=pc->Suffix;
253 if ( pc->NumStats ) {
254 if ((p=pc->Stats)->Symbol != sym)
255 do { tmp=p[1].Symbol; p++; } while (tmp != sym);
256 tmp=2*(p->Freq < MAX_FREQ-9);
257 p->Freq += tmp; pc->SummFreq += tmp;
258 } else { p=&(pc->oneState()); p->Freq += (p->Freq < 32); }
259 LOOP_ENTRY:
260 if ( p->Successor ) break;
261 *pps++ = p; p->Successor=UpBranch;
262 OrderFall++;
263 }
264 if (MRMethod > MRM_FREEZE) {
265 pc = p->Successor; goto FROZEN;
266 } else if (p->Successor <= UpBranch) {
267 p1=FoundState; FoundState=p;
268 p->Successor=CreateSuccessors(FALSE,NULL,pc);
269 FoundState=p1;
270 }
271 if (OrderFall == 1 && pc1 == MaxContext) {
272 FoundState->Successor=p->Successor; pText--;
273 }
274 return p->Successor;
275 }
rescale()276 void PPM_CONTEXT::rescale()
277 {
278 UINT OldNU, Adder, EscFreq, i=NumStats;
279 STATE tmp, * p1, * p;
280 for (p=FoundState;p != Stats;p--) SWAP(p[0],p[-1]);
281 p->Freq += 4; SummFreq += 4;
282 EscFreq=SummFreq-p->Freq;
283 Adder=(OrderFall != 0 || MRMethod > MRM_FREEZE);
284 SummFreq = (p->Freq=(p->Freq+Adder) >> 1);
285 do {
286 EscFreq -= (++p)->Freq;
287 SummFreq += (p->Freq=(p->Freq+Adder) >> 1);
288 if (p[0].Freq > p[-1].Freq) {
289 StateCpy(tmp,*(p1=p));
290 do StateCpy(p1[0],p1[-1]); while (tmp.Freq > (--p1)[-1].Freq);
291 StateCpy(*p1,tmp);
292 }
293 } while ( --i );
294 if (p->Freq == 0) {
295 do { i++; } while ((--p)->Freq == 0);
296 EscFreq += i; OldNU=(NumStats+2) >> 1;
297 if ((NumStats -= i) == 0) {
298 StateCpy(tmp,*Stats);
299 tmp.Freq=(2*tmp.Freq+EscFreq-1)/EscFreq;
300 if (tmp.Freq > MAX_FREQ/3) tmp.Freq=MAX_FREQ/3;
301 FreeUnits(Stats,OldNU); StateCpy(oneState(),tmp);
302 Flags=(Flags & 0x10)+0x08*(tmp.Symbol >= 0x40);
303 FoundState=&oneState(); return;
304 }
305 Stats = (STATE*) ShrinkUnits(Stats,OldNU,(NumStats+2) >> 1);
306 Flags &= ~0x08; i=NumStats;
307 Flags |= 0x08*((p=Stats)->Symbol >= 0x40);
308 do { Flags |= 0x08*((++p)->Symbol >= 0x40); } while ( --i );
309 }
310 SummFreq += (EscFreq -= (EscFreq >> 1));
311 Flags |= 0x04; FoundState=Stats;
312 }
CreateSuccessors(BOOL Skip,PPM_CONTEXT::STATE * p,PPM_CONTEXT * pc)313 static PPM_CONTEXT* _FASTCALL CreateSuccessors(BOOL Skip,PPM_CONTEXT::STATE* p,
314 PPM_CONTEXT* pc)
315 {
316 PPM_CONTEXT ct, * UpBranch=FoundState->Successor;
317 PPM_CONTEXT::STATE* ps[MAX_O], ** pps=ps;
318 UINT cf, s0;
319 BYTE tmp, sym=FoundState->Symbol;
320 if ( !Skip ) {
321 *pps++ = FoundState;
322 if ( !pc->Suffix ) goto NO_LOOP;
323 }
324 if ( p ) { pc=pc->Suffix; goto LOOP_ENTRY; }
325 do {
326 pc=pc->Suffix;
327 if ( pc->NumStats ) {
328 if ((p=pc->Stats)->Symbol != sym)
329 do { tmp=p[1].Symbol; p++; } while (tmp != sym);
330 tmp=(p->Freq < MAX_FREQ-9);
331 p->Freq += tmp; pc->SummFreq += tmp;
332 } else {
333 p=&(pc->oneState());
334 p->Freq += (!pc->Suffix->NumStats & (p->Freq < 24));
335 }
336 LOOP_ENTRY:
337 if (p->Successor != UpBranch) {
338 pc=p->Successor; break;
339 }
340 *pps++ = p;
341 } while ( pc->Suffix );
342 NO_LOOP:
343 if (pps == ps) return pc;
344 ct.NumStats=0; ct.Flags=0x10*(sym >= 0x40);
345 ct.oneState().Symbol=sym=*(BYTE*) UpBranch;
346 ct.oneState().Successor=(PPM_CONTEXT*) (((BYTE*) UpBranch)+1);
347 ct.Flags |= 0x08*(sym >= 0x40);
348 if ( pc->NumStats ) {
349 if ((p=pc->Stats)->Symbol != sym)
350 do { tmp=p[1].Symbol; p++; } while (tmp != sym);
351 s0=pc->SummFreq-pc->NumStats-(cf=p->Freq-1);
352 ct.oneState().Freq=1+((2*cf <= s0)?(5*cf > s0):((cf+2*s0-3)/s0));
353 } else
354 ct.oneState().Freq=pc->oneState().Freq;
355 do {
356 PPM_CONTEXT* pc1 = (PPM_CONTEXT*) AllocContext();
357 if ( !pc1 ) return NULL;
358 ((DWORD*) pc1)[0] = ((DWORD*) &ct)[0];
359 ((DWORD*) pc1)[1] = ((DWORD*) &ct)[1];
360 pc1->Suffix=pc; (*--pps)->Successor=pc=pc1;
361 } while (pps != ps);
362 return pc;
363 }
UpdateModel(PPM_CONTEXT * MinContext)364 static inline void UpdateModel(PPM_CONTEXT* MinContext)
365 {
366 PPM_CONTEXT::STATE* p=NULL;
367 PPM_CONTEXT* Successor, * FSuccessor, * pc, * pc1=MaxContext;
368 UINT ns1, ns, cf, sf, s0, FFreq=FoundState->Freq;
369 BYTE Flag, sym, FSymbol=FoundState->Symbol;
370 FSuccessor=FoundState->Successor; pc=MinContext->Suffix;
371 if (FFreq < MAX_FREQ/4 && pc) {
372 if ( pc->NumStats ) {
373 if ((p=pc->Stats)->Symbol != FSymbol) {
374 do { sym=p[1].Symbol; p++; } while (sym != FSymbol);
375 if (p[0].Freq >= p[-1].Freq) {
376 SWAP(p[0],p[-1]); p--;
377 }
378 }
379 cf=2*(p->Freq < MAX_FREQ-9);
380 p->Freq += cf; pc->SummFreq += cf;
381 } else { p=&(pc->oneState()); p->Freq += (p->Freq < 32); }
382 }
383 if (!OrderFall && FSuccessor) {
384 FoundState->Successor=CreateSuccessors(TRUE,p,MinContext);
385 if ( !FoundState->Successor ) goto RESTART_MODEL;
386 MaxContext=FoundState->Successor; return;
387 }
388 *pText++ = FSymbol; Successor = (PPM_CONTEXT*) pText;
389 if (pText >= UnitsStart) goto RESTART_MODEL;
390 if ( FSuccessor ) {
391 if ((BYTE*) FSuccessor < UnitsStart)
392 FSuccessor=CreateSuccessors(FALSE,p,MinContext);
393 } else
394 FSuccessor=ReduceOrder(p,MinContext);
395 if ( !FSuccessor ) goto RESTART_MODEL;
396 if ( !--OrderFall ) {
397 Successor=FSuccessor; pText -= (MaxContext != MinContext);
398 } else if (MRMethod > MRM_FREEZE) {
399 Successor=FSuccessor; pText=HeapStart;
400 OrderFall=0;
401 }
402 s0=MinContext->SummFreq-(ns=MinContext->NumStats)-FFreq;
403 for (Flag=0x08*(FSymbol >= 0x40);pc1 != MinContext;pc1=pc1->Suffix) {
404 if ((ns1=pc1->NumStats) != 0) {
405 if ((ns1 & 1) != 0) {
406 p=(PPM_CONTEXT::STATE*) ExpandUnits(pc1->Stats,(ns1+1) >> 1);
407 if ( !p ) goto RESTART_MODEL;
408 pc1->Stats=p;
409 }
410 pc1->SummFreq += (3*ns1+1 < ns);
411 } else {
412 p=(PPM_CONTEXT::STATE*) AllocUnits(1);
413 if ( !p ) goto RESTART_MODEL;
414 StateCpy(*p,pc1->oneState()); pc1->Stats=p;
415 if (p->Freq < MAX_FREQ/4-1) p->Freq += p->Freq;
416 else p->Freq = MAX_FREQ-4;
417 pc1->SummFreq=p->Freq+InitEsc+(ns > 2);
418 }
419 cf=2*FFreq*(pc1->SummFreq+6); sf=s0+pc1->SummFreq;
420 if (cf < 6*sf) {
421 cf=1+(cf > sf)+(cf >= 4*sf);
422 pc1->SummFreq += 4;
423 } else {
424 cf=4+(cf > 9*sf)+(cf > 12*sf)+(cf > 15*sf);
425 pc1->SummFreq += cf;
426 }
427 p=pc1->Stats+(++pc1->NumStats); p->Successor=Successor;
428 p->Symbol = FSymbol; p->Freq = cf;
429 pc1->Flags |= Flag;
430 }
431 MaxContext=FSuccessor; return;
432 RESTART_MODEL:
433 RestoreModelRare(pc1,MinContext,FSuccessor);
434 }
435 // Tabulated escapes for exponential symbol distribution
436 static const BYTE ExpEscape[16]={ 25,14, 9, 7, 5, 5, 4, 4, 4, 3, 3, 3, 2, 2, 2, 2 };
437 #define GET_MEAN(SUMM,SHIFT,ROUND) ((SUMM+(1 << (SHIFT-ROUND))) >> (SHIFT))
encodeBinSymbol(int symbol)438 inline void PPM_CONTEXT::encodeBinSymbol(int symbol)
439 {
440 BYTE indx=NS2BSIndx[Suffix->NumStats]+PrevSuccess+Flags;
441 STATE& rs=oneState();
442 WORD& bs=BinSumm[QTable[rs.Freq-1]][indx+((RunLength >> 26) & 0x20)];
443 if (rs.Symbol == symbol) {
444 FoundState=&rs; rs.Freq += (rs.Freq < 196);
445 SubRange.LowCount=0; SubRange.HighCount=bs;
446 bs += INTERVAL-GET_MEAN(bs,PERIOD_BITS,2);
447 PrevSuccess=1; RunLength++;
448 } else {
449 SubRange.LowCount=bs; bs -= GET_MEAN(bs,PERIOD_BITS,2);
450 SubRange.HighCount=BIN_SCALE; InitEsc=ExpEscape[bs >> 10];
451 CharMask[rs.Symbol]=EscCount;
452 NumMasked=PrevSuccess=0; FoundState=NULL;
453 }
454 }
decodeBinSymbol()455 inline void PPM_CONTEXT::decodeBinSymbol()
456 {
457 BYTE indx=NS2BSIndx[Suffix->NumStats]+PrevSuccess+Flags;
458 STATE& rs=oneState();
459 WORD& bs=BinSumm[QTable[rs.Freq-1]][indx+((RunLength >> 26) & 0x20)];
460 if (ariGetCurrentShiftCount(TOT_BITS) < bs) {
461 FoundState=&rs; rs.Freq += (rs.Freq < 196);
462 SubRange.LowCount=0; SubRange.HighCount=bs;
463 bs += INTERVAL-GET_MEAN(bs,PERIOD_BITS,2);
464 PrevSuccess=1; RunLength++;
465 } else {
466 SubRange.LowCount=bs; bs -= GET_MEAN(bs,PERIOD_BITS,2);
467 SubRange.HighCount=BIN_SCALE; InitEsc=ExpEscape[bs >> 10];
468 CharMask[rs.Symbol]=EscCount;
469 NumMasked=PrevSuccess=0; FoundState=NULL;
470 }
471 }
update1(STATE * p)472 inline void PPM_CONTEXT::update1(STATE* p)
473 {
474 (FoundState=p)->Freq += 4; SummFreq += 4;
475 if (p[0].Freq > p[-1].Freq) {
476 SWAP(p[0],p[-1]); FoundState=--p;
477 if (p->Freq > MAX_FREQ) rescale();
478 }
479 }
encodeSymbol1(int symbol)480 inline void PPM_CONTEXT::encodeSymbol1(int symbol)
481 {
482 UINT LoCnt, i=Stats->Symbol;
483 STATE* p=Stats; SubRange.scale=SummFreq;
484 if (i == symbol) {
485 PrevSuccess=(2*(SubRange.HighCount=p->Freq) >= SubRange.scale);
486 (FoundState=p)->Freq += 4; SummFreq += 4;
487 RunLength += PrevSuccess;
488 if (p->Freq > MAX_FREQ) rescale();
489 SubRange.LowCount=0; return;
490 }
491 LoCnt=p->Freq;
492 i=NumStats; PrevSuccess=0;
493 while ((++p)->Symbol != symbol) {
494 LoCnt += p->Freq;
495 if (--i == 0) {
496 if ( Suffix ) PrefetchData(Suffix);
497 SubRange.LowCount=LoCnt; CharMask[p->Symbol]=EscCount;
498 i=NumMasked=NumStats; FoundState=NULL;
499 do { CharMask[(--p)->Symbol]=EscCount; } while ( --i );
500 SubRange.HighCount=SubRange.scale;
501 return;
502 }
503 }
504 SubRange.HighCount=(SubRange.LowCount=LoCnt)+p->Freq;
505 update1(p);
506 }
decodeSymbol1()507 inline void PPM_CONTEXT::decodeSymbol1()
508 {
509 UINT i, count, HiCnt=Stats->Freq;
510 STATE* p=Stats; SubRange.scale=SummFreq;
511 if ((count=ariGetCurrentCount()) < HiCnt) {
512 PrevSuccess=(2*(SubRange.HighCount=HiCnt) >= SubRange.scale);
513 (FoundState=p)->Freq=(HiCnt += 4); SummFreq += 4;
514 RunLength += PrevSuccess;
515 if (HiCnt > MAX_FREQ) rescale();
516 SubRange.LowCount=0; return;
517 }
518 i=NumStats; PrevSuccess=0;
519 while ((HiCnt += (++p)->Freq) <= count)
520 if (--i == 0) {
521 if ( Suffix ) PrefetchData(Suffix);
522 SubRange.LowCount=HiCnt; CharMask[p->Symbol]=EscCount;
523 i=NumMasked=NumStats; FoundState=NULL;
524 do { CharMask[(--p)->Symbol]=EscCount; } while ( --i );
525 SubRange.HighCount=SubRange.scale;
526 return;
527 }
528 SubRange.LowCount=(SubRange.HighCount=HiCnt)-p->Freq;
529 update1(p);
530 }
update2(STATE * p)531 inline void PPM_CONTEXT::update2(STATE* p)
532 {
533 (FoundState=p)->Freq += 4; SummFreq += 4;
534 if (p->Freq > MAX_FREQ) rescale();
535 EscCount++; RunLength=InitRL;
536 }
makeEscFreq2()537 inline SEE2_CONTEXT* PPM_CONTEXT::makeEscFreq2()
538 {
539 BYTE* pb=(BYTE*) Stats; UINT t=2*NumStats;
540 PrefetchData(pb); PrefetchData(pb+t);
541 PrefetchData(pb += 2*t); PrefetchData(pb+t);
542 SEE2_CONTEXT* psee2c;
543 if (NumStats != 0xFF) {
544 t=Suffix->NumStats;
545 psee2c=SEE2Cont[QTable[NumStats+2]-3]+(SummFreq > 11*(NumStats+1));
546 psee2c += 2*(2*NumStats < t+NumMasked)+Flags;
547 SubRange.scale=psee2c->getMean();
548 } else {
549 psee2c=&DummySEE2Cont; SubRange.scale=1;
550 }
551 return psee2c;
552 }
encodeSymbol2(int symbol)553 inline void PPM_CONTEXT::encodeSymbol2(int symbol)
554 {
555 SEE2_CONTEXT* psee2c=makeEscFreq2();
556 UINT Sym, LoCnt=0, i=NumStats-NumMasked;
557 STATE* p1, * p=Stats-1;
558 do {
559 do { Sym=p[1].Symbol; p++; } while (CharMask[Sym] == EscCount);
560 CharMask[Sym]=EscCount;
561 if (Sym == symbol) goto SYMBOL_FOUND;
562 LoCnt += p->Freq;
563 } while ( --i );
564 SubRange.HighCount=(SubRange.scale += (SubRange.LowCount=LoCnt));
565 psee2c->Summ += SubRange.scale; NumMasked = NumStats;
566 return;
567 SYMBOL_FOUND:
568 SubRange.LowCount=LoCnt; SubRange.HighCount=(LoCnt+=p->Freq);
569 for (p1=p; --i ; ) {
570 do { Sym=p1[1].Symbol; p1++; } while (CharMask[Sym] == EscCount);
571 LoCnt += p1->Freq;
572 }
573 SubRange.scale += LoCnt;
574 psee2c->update(); update2(p);
575 }
decodeSymbol2()576 inline void PPM_CONTEXT::decodeSymbol2()
577 {
578 SEE2_CONTEXT* psee2c=makeEscFreq2();
579 UINT Sym, count, HiCnt=0, i=NumStats-NumMasked;
580 STATE* ps[256], ** pps=ps, * p=Stats-1;
581 do {
582 do { Sym=p[1].Symbol; p++; } while (CharMask[Sym] == EscCount);
583 HiCnt += p->Freq; *pps++ = p;
584 } while ( --i );
585 SubRange.scale += HiCnt; count=ariGetCurrentCount();
586 p=*(pps=ps);
587 if (count < HiCnt) {
588 HiCnt=0;
589 while ((HiCnt += p->Freq) <= count) p=*++pps;
590 SubRange.LowCount = (SubRange.HighCount=HiCnt)-p->Freq;
591 psee2c->update(); update2(p);
592 } else {
593 SubRange.LowCount=HiCnt; SubRange.HighCount=SubRange.scale;
594 i=NumStats-NumMasked; NumMasked = NumStats;
595 do { CharMask[(*pps)->Symbol]=EscCount; pps++; } while ( --i );
596 psee2c->Summ += SubRange.scale;
597 }
598 }
ClearMask(_PPMD_FILE * EncodedFile,_PPMD_FILE * DecodedFile)599 inline void ClearMask(_PPMD_FILE* EncodedFile,_PPMD_FILE* DecodedFile)
600 {
601 EscCount=1; memset(CharMask,0,sizeof(CharMask));
602 if (++PrintCount == 0) PrintInfo(DecodedFile,EncodedFile);
603 }
EncodeFile(_PPMD_FILE * EncodedFile,_PPMD_FILE * DecodedFile,int MaxOrder,MR_METHOD MRMethod)604 void _STDCALL EncodeFile(_PPMD_FILE* EncodedFile,_PPMD_FILE* DecodedFile,
605 int MaxOrder,MR_METHOD MRMethod)
606 {
607 ariInitEncoder(); StartModelRare(MaxOrder,MRMethod);
608 for (PPM_CONTEXT* MinContext; ; ) {
609 BYTE ns=(MinContext=MaxContext)->NumStats;
610 int c = _PPMD_E_GETC(DecodedFile);
611 if ( ns ) {
612 MinContext->encodeSymbol1(c); ariEncodeSymbol();
613 } else {
614 MinContext->encodeBinSymbol(c); ariShiftEncodeSymbol(TOT_BITS);
615 }
616 while ( !FoundState ) {
617 ARI_ENC_NORMALIZE(EncodedFile);
618 do {
619 OrderFall++; MinContext=MinContext->Suffix;
620 if ( !MinContext ) goto STOP_ENCODING;
621 } while (MinContext->NumStats == NumMasked);
622 MinContext->encodeSymbol2(c); ariEncodeSymbol();
623 }
624 if (!OrderFall && (BYTE*) FoundState->Successor >= UnitsStart)
625 PrefetchData(MaxContext=FoundState->Successor);
626 else {
627 UpdateModel(MinContext); PrefetchData(MaxContext);
628 if (EscCount == 0) ClearMask(EncodedFile,DecodedFile);
629 }
630 ARI_ENC_NORMALIZE(EncodedFile);
631 }
632 STOP_ENCODING:
633 ARI_FLUSH_ENCODER(EncodedFile); PrintInfo(DecodedFile,EncodedFile);
634 }
DecodeFile(_PPMD_FILE * DecodedFile,_PPMD_FILE * EncodedFile,int MaxOrder,MR_METHOD MRMethod)635 void _STDCALL DecodeFile(_PPMD_FILE* DecodedFile,_PPMD_FILE* EncodedFile,
636 int MaxOrder,MR_METHOD MRMethod)
637 {
638 ARI_INIT_DECODER(EncodedFile); StartModelRare(MaxOrder,MRMethod);
639 PPM_CONTEXT* MinContext=MaxContext;
640 for (BYTE ns=MinContext->NumStats; ; ) {
641 ( ns )?(MinContext->decodeSymbol1()):(MinContext->decodeBinSymbol());
642 ariRemoveSubrange();
643 while ( !FoundState ) {
644 ARI_DEC_NORMALIZE(EncodedFile);
645 do {
646 OrderFall++; MinContext=MinContext->Suffix;
647 if ( !MinContext ) goto STOP_DECODING;
648 } while (MinContext->NumStats == NumMasked);
649 MinContext->decodeSymbol2(); ariRemoveSubrange();
650 }
651 _PPMD_D_PUTC(FoundState->Symbol,DecodedFile);
652 if (!OrderFall && (BYTE*) FoundState->Successor >= UnitsStart)
653 PrefetchData(MaxContext=FoundState->Successor);
654 else {
655 UpdateModel(MinContext); PrefetchData(MaxContext);
656 if (EscCount == 0) ClearMask(EncodedFile,DecodedFile);
657 }
658 ns=(MinContext=MaxContext)->NumStats;
659 ARI_DEC_NORMALIZE(EncodedFile);
660 }
661 STOP_DECODING:
662 PrintInfo(DecodedFile,EncodedFile);
663 }
664