Diffstat (limited to 'noncore/apps/opie-reader/Model.cpp') (more/less context) (show whitespace changes)
-rw-r--r-- | noncore/apps/opie-reader/Model.cpp | 721 |
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 | |||
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; | ||
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; | ||
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); | ||
52 | 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 | |||
63 | inline 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 | } | ||
74 | inline 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 | } | ||
79 | struct PPMD_STARTUP { inline PPMD_STARTUP(); } PPMd_StartUp; | ||
80 | inline 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 | } | ||
99 | static 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 | } | ||
120 | static 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 | } | ||
134 | void 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)) | ||
150 | PPM_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 { | ||
162 | REMOVE: 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 | } | ||
183 | PPM_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 | } | ||
202 | static 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 | } | ||
237 | static PPM_CONTEXT* _FASTCALL CreateSuccessors(BOOL Skip,PPM_CONTEXT::STATE* p, | ||
238 | PPM_CONTEXT* pc); | ||
239 | static 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) { | ||
250 | FROZEN: 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); } | ||
262 | LOOP_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 | } | ||
279 | void 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 | } | ||
316 | static 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 | } | ||
339 | LOOP_ENTRY: | ||
340 | if (p->Successor != UpBranch) { | ||
341 | pc=p->Successor; break; | ||
342 | } | ||
343 | *pps++ = p; | ||
344 | } while ( pc->Suffix ); | ||
345 | NO_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 | } | ||
367 | static 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; | ||
435 | RESTART_MODEL: | ||
436 | RestoreModelRare(pc1,MinContext,FSuccessor); | ||
437 | } | ||
438 | // Tabulated escapes for exponential symbol distribution | ||
439 | static 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)) | ||
441 | inline 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 | } | ||
458 | inline 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 | } | ||
475 | inline 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 | } | ||
483 | inline 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 | } | ||
510 | inline 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 | } | ||
534 | inline 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 | } | ||
540 | inline 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 | } | ||
556 | inline 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; | ||
570 | SYMBOL_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 | } | ||
579 | inline 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 | } | ||
602 | inline void ClearMask(CInfo* EncodedFile, CInfo* DecodedFile) | ||
603 | { | ||
604 | EscCount=1; memset(CharMask,0,sizeof(CharMask)); | ||
605 | // if (++PrintCount == 0) PrintInfo(DecodedFile,EncodedFile); | ||
606 | } | ||
607 | void _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 | } | ||
635 | STOP_ENCODING: | ||
636 | ARI_FLUSH_ENCODER(EncodedFile); //PrintInfo(DecodedFile,EncodedFile); | ||
637 | } | ||
638 | void _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 | } | ||
664 | STOP_DECODING: | ||
665 | // PrintInfo(DecodedFile,EncodedFile); | ||
666 | return; | ||
667 | } | ||
668 | |||
669 | |||
670 | |||
671 | #include "PPMd.h" | ||
672 | #include "CSource.h" | ||
673 | |||
674 | size_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 | |||
703 | extern "C" | ||
704 | { | ||
705 | |||
706 | size_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 | |||
711 | size_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 | |||
716 | size_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 | } | ||