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