Mercurial > vba-linux
comparison src/win32/7zip/7z/CPP/7zip/Compress/PpmdContext.h @ 1:f9f4f1b99eed
importing src directory
author | Robert McIntyre <rlm@mit.edu> |
---|---|
date | Sat, 03 Mar 2012 10:31:27 -0600 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
0:8ced16adf2e1 | 1:f9f4f1b99eed |
---|---|
1 // PpmdContext.h | |
2 // This code is based on Dmitry Shkarin's PPMdH code | |
3 | |
4 #ifndef __COMPRESS_PPMD_CONTEXT_H | |
5 #define __COMPRESS_PPMD_CONTEXT_H | |
6 | |
7 #include "../../Common/Types.h" | |
8 | |
9 #include "PpmdSubAlloc.h" | |
10 #include "RangeCoder.h" | |
11 | |
12 namespace NCompress { | |
13 namespace NPpmd { | |
14 | |
15 const int INT_BITS=7, PERIOD_BITS=7, TOT_BITS=INT_BITS+PERIOD_BITS, | |
16 INTERVAL=1 << INT_BITS, BIN_SCALE=1 << TOT_BITS, MAX_FREQ=124; | |
17 | |
18 struct SEE2_CONTEXT | |
19 { | |
20 // SEE-contexts for PPM-contexts with masked symbols | |
21 UInt16 Summ; | |
22 Byte Shift, Count; | |
23 void init(int InitVal) { Summ = (UInt16)(InitVal << (Shift=PERIOD_BITS-4)); Count=4; } | |
24 unsigned int getMean() | |
25 { | |
26 unsigned int RetVal=(Summ >> Shift); | |
27 Summ = (UInt16)(Summ - RetVal); | |
28 return RetVal+(RetVal == 0); | |
29 } | |
30 void update() | |
31 { | |
32 if (Shift < PERIOD_BITS && --Count == 0) | |
33 { | |
34 Summ <<= 1; | |
35 Count = (Byte)(3 << Shift++); | |
36 } | |
37 } | |
38 }; | |
39 | |
40 struct PPM_CONTEXT | |
41 { | |
42 UInt16 NumStats; // sizeof(UInt16) > sizeof(Byte) | |
43 UInt16 SummFreq; | |
44 | |
45 struct STATE | |
46 { | |
47 Byte Symbol, Freq; | |
48 UInt16 SuccessorLow; | |
49 UInt16 SuccessorHigh; | |
50 | |
51 UInt32 GetSuccessor() const { return SuccessorLow | ((UInt32)SuccessorHigh << 16); } | |
52 void SetSuccessor(UInt32 v) | |
53 { | |
54 SuccessorLow = (UInt16)(v & 0xFFFF); | |
55 SuccessorHigh = (UInt16)((v >> 16) & 0xFFFF); | |
56 } | |
57 }; | |
58 | |
59 UInt32 Stats; | |
60 UInt32 Suffix; | |
61 | |
62 PPM_CONTEXT* createChild(CSubAllocator &subAllocator, STATE* pStats, STATE& FirstState) | |
63 { | |
64 PPM_CONTEXT* pc = (PPM_CONTEXT*) subAllocator.AllocContext(); | |
65 if (pc) | |
66 { | |
67 pc->NumStats = 1; | |
68 pc->oneState() = FirstState; | |
69 pc->Suffix = subAllocator.GetOffset(this); | |
70 pStats->SetSuccessor(subAllocator.GetOffsetNoCheck(pc)); | |
71 } | |
72 return pc; | |
73 } | |
74 | |
75 STATE& oneState() const { return (STATE&) SummFreq; } | |
76 }; | |
77 | |
78 ///////////////////////////////// | |
79 | |
80 const UInt16 InitBinEsc[] = | |
81 {0x3CDD, 0x1F3F, 0x59BF, 0x48F3, 0x64A1, 0x5ABC, 0x6632, 0x6051}; | |
82 | |
83 struct CInfo | |
84 { | |
85 CSubAllocator SubAllocator; | |
86 SEE2_CONTEXT SEE2Cont[25][16], DummySEE2Cont; | |
87 PPM_CONTEXT * MinContext, * MaxContext; | |
88 | |
89 PPM_CONTEXT::STATE* FoundState; // found next state transition | |
90 int NumMasked, InitEsc, OrderFall, RunLength, InitRL, MaxOrder; | |
91 Byte CharMask[256], NS2Indx[256], NS2BSIndx[256], HB2Flag[256]; | |
92 Byte EscCount, PrintCount, PrevSuccess, HiBitsFlag; | |
93 UInt16 BinSumm[128][64]; // binary SEE-contexts | |
94 | |
95 UInt16 &GetBinSumm(const PPM_CONTEXT::STATE &rs, int numStates) | |
96 { | |
97 HiBitsFlag = HB2Flag[FoundState->Symbol]; | |
98 return BinSumm[rs.Freq - 1][ | |
99 PrevSuccess + NS2BSIndx[numStates - 1] + | |
100 HiBitsFlag + 2 * HB2Flag[rs.Symbol] + | |
101 ((RunLength >> 26) & 0x20)]; | |
102 } | |
103 | |
104 PPM_CONTEXT *GetContext(UInt32 offset) const { return (PPM_CONTEXT *)SubAllocator.GetPtr(offset); } | |
105 PPM_CONTEXT *GetContextNoCheck(UInt32 offset) const { return (PPM_CONTEXT *)SubAllocator.GetPtrNoCheck(offset); } | |
106 PPM_CONTEXT::STATE *GetState(UInt32 offset) const { return (PPM_CONTEXT::STATE *)SubAllocator.GetPtr(offset); } | |
107 PPM_CONTEXT::STATE *GetStateNoCheck(UInt32 offset) const { return (PPM_CONTEXT::STATE *)SubAllocator.GetPtr(offset); } | |
108 | |
109 void RestartModelRare() | |
110 { | |
111 int i, k, m; | |
112 memset(CharMask,0,sizeof(CharMask)); | |
113 SubAllocator.InitSubAllocator(); | |
114 InitRL = -((MaxOrder < 12) ? MaxOrder : 12) - 1; | |
115 MinContext = MaxContext = (PPM_CONTEXT*) SubAllocator.AllocContext(); | |
116 MinContext->Suffix = 0; | |
117 OrderFall = MaxOrder; | |
118 MinContext->SummFreq = (UInt16)((MinContext->NumStats = 256) + 1); | |
119 FoundState = (PPM_CONTEXT::STATE*)SubAllocator.AllocUnits(256 / 2); | |
120 MinContext->Stats = SubAllocator.GetOffsetNoCheck(FoundState); | |
121 PrevSuccess = 0; | |
122 for (RunLength = InitRL, i = 0; i < 256; i++) | |
123 { | |
124 PPM_CONTEXT::STATE &state = FoundState[i]; | |
125 state.Symbol = (Byte)i; | |
126 state.Freq = 1; | |
127 state.SetSuccessor(0); | |
128 } | |
129 for (i = 0; i < 128; i++) | |
130 for (k = 0; k < 8; k++) | |
131 for ( m=0; m < 64; m += 8) | |
132 BinSumm[i][k + m] = (UInt16)(BIN_SCALE - InitBinEsc[k] / (i + 2)); | |
133 for (i = 0; i < 25; i++) | |
134 for (k = 0; k < 16; k++) | |
135 SEE2Cont[i][k].init(5*i+10); | |
136 } | |
137 | |
138 void StartModelRare(int maxOrder) | |
139 { | |
140 int i, k, m ,Step; | |
141 EscCount=PrintCount=1; | |
142 if (maxOrder < 2) | |
143 { | |
144 memset(CharMask,0,sizeof(CharMask)); | |
145 OrderFall = MaxOrder; | |
146 MinContext = MaxContext; | |
147 while (MinContext->Suffix != 0) | |
148 { | |
149 MinContext = GetContextNoCheck(MinContext->Suffix); | |
150 OrderFall--; | |
151 } | |
152 FoundState = GetState(MinContext->Stats); | |
153 MinContext = MaxContext; | |
154 } | |
155 else | |
156 { | |
157 MaxOrder = maxOrder; | |
158 RestartModelRare(); | |
159 NS2BSIndx[0] = 2 * 0; | |
160 NS2BSIndx[1] = 2 * 1; | |
161 memset(NS2BSIndx + 2, 2 * 2, 9); | |
162 memset(NS2BSIndx + 11, 2 * 3, 256 - 11); | |
163 for (i = 0; i < 3; i++) | |
164 NS2Indx[i] = (Byte)i; | |
165 for (m = i, k = Step = 1; i < 256; i++) | |
166 { | |
167 NS2Indx[i] = (Byte)m; | |
168 if ( !--k ) | |
169 { | |
170 k = ++Step; | |
171 m++; | |
172 } | |
173 } | |
174 memset(HB2Flag, 0, 0x40); | |
175 memset(HB2Flag + 0x40, 0x08, 0x100 - 0x40); | |
176 DummySEE2Cont.Shift = PERIOD_BITS; | |
177 } | |
178 } | |
179 | |
180 PPM_CONTEXT* CreateSuccessors(bool skip, PPM_CONTEXT::STATE* p1) | |
181 { | |
182 // static UpState declaration bypasses IntelC bug | |
183 // static PPM_CONTEXT::STATE UpState; | |
184 PPM_CONTEXT::STATE UpState; | |
185 | |
186 PPM_CONTEXT *pc = MinContext; | |
187 PPM_CONTEXT *UpBranch = GetContext(FoundState->GetSuccessor()); | |
188 PPM_CONTEXT::STATE * p, * ps[MAX_O], ** pps = ps; | |
189 if ( !skip ) | |
190 { | |
191 *pps++ = FoundState; | |
192 if ( !pc->Suffix ) | |
193 goto NO_LOOP; | |
194 } | |
195 if ( p1 ) | |
196 { | |
197 p = p1; | |
198 pc = GetContext(pc->Suffix); | |
199 goto LOOP_ENTRY; | |
200 } | |
201 do | |
202 { | |
203 pc = GetContext(pc->Suffix); | |
204 if (pc->NumStats != 1) | |
205 { | |
206 if ((p = GetStateNoCheck(pc->Stats))->Symbol != FoundState->Symbol) | |
207 do { p++; } while (p->Symbol != FoundState->Symbol); | |
208 } | |
209 else | |
210 p = &(pc->oneState()); | |
211 LOOP_ENTRY: | |
212 if (GetContext(p->GetSuccessor()) != UpBranch) | |
213 { | |
214 pc = GetContext(p->GetSuccessor()); | |
215 break; | |
216 } | |
217 *pps++ = p; | |
218 } | |
219 while ( pc->Suffix ); | |
220 NO_LOOP: | |
221 if (pps == ps) | |
222 return pc; | |
223 UpState.Symbol = *(Byte*) UpBranch; | |
224 UpState.SetSuccessor(SubAllocator.GetOffset(UpBranch) + 1); | |
225 if (pc->NumStats != 1) | |
226 { | |
227 if ((p = GetStateNoCheck(pc->Stats))->Symbol != UpState.Symbol) | |
228 do { p++; } while (p->Symbol != UpState.Symbol); | |
229 unsigned int cf = p->Freq-1; | |
230 unsigned int s0 = pc->SummFreq - pc->NumStats - cf; | |
231 UpState.Freq = (Byte)(1 + ((2 * cf <= s0) ? (5 * cf > s0) : | |
232 ((2 * cf + 3 * s0 - 1) / (2 * s0)))); | |
233 } | |
234 else | |
235 UpState.Freq = pc->oneState().Freq; | |
236 do | |
237 { | |
238 pc = pc->createChild(SubAllocator, *--pps, UpState); | |
239 if ( !pc ) | |
240 return NULL; | |
241 } | |
242 while (pps != ps); | |
243 return pc; | |
244 } | |
245 | |
246 void UpdateModel() | |
247 { | |
248 PPM_CONTEXT::STATE fs = *FoundState, * p = NULL; | |
249 PPM_CONTEXT* pc, * Successor; | |
250 unsigned int ns1, ns, cf, sf, s0; | |
251 if (fs.Freq < MAX_FREQ / 4 && MinContext->Suffix != 0) | |
252 { | |
253 pc = GetContextNoCheck(MinContext->Suffix); | |
254 | |
255 if (pc->NumStats != 1) | |
256 { | |
257 if ((p = GetStateNoCheck(pc->Stats))->Symbol != fs.Symbol) | |
258 { | |
259 do { p++; } while (p->Symbol != fs.Symbol); | |
260 if (p[0].Freq >= p[-1].Freq) | |
261 { | |
262 _PPMD_SWAP(p[0],p[-1]); | |
263 p--; | |
264 } | |
265 } | |
266 if (p->Freq < MAX_FREQ-9) | |
267 { | |
268 p->Freq += 2; | |
269 pc->SummFreq += 2; | |
270 } | |
271 } | |
272 else | |
273 { | |
274 p = &(pc->oneState()); | |
275 p->Freq = (Byte)(p->Freq + ((p->Freq < 32) ? 1 : 0)); | |
276 } | |
277 } | |
278 if ( !OrderFall ) | |
279 { | |
280 MinContext = MaxContext = CreateSuccessors(true, p); | |
281 FoundState->SetSuccessor(SubAllocator.GetOffset(MinContext)); | |
282 if (MinContext == 0) | |
283 goto RESTART_MODEL; | |
284 return; | |
285 } | |
286 *SubAllocator.pText++ = fs.Symbol; | |
287 Successor = (PPM_CONTEXT*) SubAllocator.pText; | |
288 if (SubAllocator.pText >= SubAllocator.UnitsStart) | |
289 goto RESTART_MODEL; | |
290 if (fs.GetSuccessor() != 0) | |
291 { | |
292 if ((Byte *)GetContext(fs.GetSuccessor()) <= SubAllocator.pText) | |
293 { | |
294 PPM_CONTEXT* cs = CreateSuccessors(false, p); | |
295 fs.SetSuccessor(SubAllocator.GetOffset(cs)); | |
296 if (cs == NULL) | |
297 goto RESTART_MODEL; | |
298 } | |
299 if ( !--OrderFall ) | |
300 { | |
301 Successor = GetContext(fs.GetSuccessor()); | |
302 SubAllocator.pText -= (MaxContext != MinContext); | |
303 } | |
304 } | |
305 else | |
306 { | |
307 FoundState->SetSuccessor(SubAllocator.GetOffsetNoCheck(Successor)); | |
308 fs.SetSuccessor(SubAllocator.GetOffsetNoCheck(MinContext)); | |
309 } | |
310 s0 = MinContext->SummFreq - (ns = MinContext->NumStats) - (fs.Freq - 1); | |
311 for (pc = MaxContext; pc != MinContext; pc = GetContext(pc->Suffix)) | |
312 { | |
313 if ((ns1 = pc->NumStats) != 1) | |
314 { | |
315 if ((ns1 & 1) == 0) | |
316 { | |
317 void *ppp = SubAllocator.ExpandUnits(GetState(pc->Stats), ns1 >> 1); | |
318 pc->Stats = SubAllocator.GetOffset(ppp); | |
319 if (!ppp) | |
320 goto RESTART_MODEL; | |
321 } | |
322 pc->SummFreq = (UInt16)(pc->SummFreq + (2 * ns1 < ns) + 2 * ((4 * ns1 <= ns) & | |
323 (pc->SummFreq <= 8 * ns1))); | |
324 } | |
325 else | |
326 { | |
327 p = (PPM_CONTEXT::STATE*) SubAllocator.AllocUnits(1); | |
328 if ( !p ) | |
329 goto RESTART_MODEL; | |
330 *p = pc->oneState(); | |
331 pc->Stats = SubAllocator.GetOffsetNoCheck(p); | |
332 if (p->Freq < MAX_FREQ / 4 - 1) | |
333 p->Freq <<= 1; | |
334 else | |
335 p->Freq = MAX_FREQ - 4; | |
336 pc->SummFreq = (UInt16)(p->Freq + InitEsc + (ns > 3)); | |
337 } | |
338 cf = 2 * fs.Freq * (pc->SummFreq+6); | |
339 sf = s0 + pc->SummFreq; | |
340 if (cf < 6 * sf) | |
341 { | |
342 cf = 1 + (cf > sf)+(cf >= 4 * sf); | |
343 pc->SummFreq += 3; | |
344 } | |
345 else | |
346 { | |
347 cf = 4 + (cf >= 9 * sf) + (cf >= 12 * sf) + (cf >= 15 * sf); | |
348 pc->SummFreq = (UInt16)(pc->SummFreq + cf); | |
349 } | |
350 p = GetState(pc->Stats) + ns1; | |
351 p->SetSuccessor(SubAllocator.GetOffset(Successor)); | |
352 p->Symbol = fs.Symbol; | |
353 p->Freq = (Byte)cf; | |
354 pc->NumStats = (UInt16)++ns1; | |
355 } | |
356 MaxContext = MinContext = GetContext(fs.GetSuccessor()); | |
357 return; | |
358 RESTART_MODEL: | |
359 RestartModelRare(); | |
360 EscCount = 0; | |
361 PrintCount = 0xFF; | |
362 } | |
363 | |
364 void ClearMask() | |
365 { | |
366 EscCount = 1; | |
367 memset(CharMask, 0, sizeof(CharMask)); | |
368 // if (++PrintCount == 0) | |
369 // PrintInfo(DecodedFile,EncodedFile); | |
370 } | |
371 | |
372 void update1(PPM_CONTEXT::STATE* p) | |
373 { | |
374 (FoundState = p)->Freq += 4; | |
375 MinContext->SummFreq += 4; | |
376 if (p[0].Freq > p[-1].Freq) | |
377 { | |
378 _PPMD_SWAP(p[0],p[-1]); | |
379 FoundState = --p; | |
380 if (p->Freq > MAX_FREQ) | |
381 rescale(); | |
382 } | |
383 } | |
384 | |
385 | |
386 void update2(PPM_CONTEXT::STATE* p) | |
387 { | |
388 (FoundState = p)->Freq += 4; | |
389 MinContext->SummFreq += 4; | |
390 if (p->Freq > MAX_FREQ) | |
391 rescale(); | |
392 EscCount++; | |
393 RunLength = InitRL; | |
394 } | |
395 | |
396 SEE2_CONTEXT* makeEscFreq2(int Diff, UInt32 &scale) | |
397 { | |
398 SEE2_CONTEXT* psee2c; | |
399 if (MinContext->NumStats != 256) | |
400 { | |
401 psee2c = SEE2Cont[NS2Indx[Diff-1]] + | |
402 (Diff < (GetContext(MinContext->Suffix))->NumStats - MinContext->NumStats) + | |
403 2 * (MinContext->SummFreq < 11 * MinContext->NumStats) + | |
404 4 * (NumMasked > Diff) + | |
405 HiBitsFlag; | |
406 scale = psee2c->getMean(); | |
407 } | |
408 else | |
409 { | |
410 psee2c = &DummySEE2Cont; | |
411 scale = 1; | |
412 } | |
413 return psee2c; | |
414 } | |
415 | |
416 | |
417 | |
418 void rescale() | |
419 { | |
420 int OldNS = MinContext->NumStats, i = MinContext->NumStats - 1, Adder, EscFreq; | |
421 PPM_CONTEXT::STATE* p1, * p; | |
422 PPM_CONTEXT::STATE *stats = GetStateNoCheck(MinContext->Stats); | |
423 for (p = FoundState; p != stats; p--) | |
424 _PPMD_SWAP(p[0], p[-1]); | |
425 stats->Freq += 4; | |
426 MinContext->SummFreq += 4; | |
427 EscFreq = MinContext->SummFreq - p->Freq; | |
428 Adder = (OrderFall != 0); | |
429 p->Freq = (Byte)((p->Freq + Adder) >> 1); | |
430 MinContext->SummFreq = p->Freq; | |
431 do | |
432 { | |
433 EscFreq -= (++p)->Freq; | |
434 p->Freq = (Byte)((p->Freq + Adder) >> 1); | |
435 MinContext->SummFreq = (UInt16)(MinContext->SummFreq + p->Freq); | |
436 if (p[0].Freq > p[-1].Freq) | |
437 { | |
438 PPM_CONTEXT::STATE tmp = *(p1 = p); | |
439 do | |
440 { | |
441 p1[0] = p1[-1]; | |
442 } | |
443 while (--p1 != stats && tmp.Freq > p1[-1].Freq); | |
444 *p1 = tmp; | |
445 } | |
446 } | |
447 while ( --i ); | |
448 if (p->Freq == 0) | |
449 { | |
450 do { i++; } while ((--p)->Freq == 0); | |
451 EscFreq += i; | |
452 MinContext->NumStats = (UInt16)(MinContext->NumStats - i); | |
453 if (MinContext->NumStats == 1) | |
454 { | |
455 PPM_CONTEXT::STATE tmp = *stats; | |
456 do { tmp.Freq = (Byte)(tmp.Freq - (tmp.Freq >> 1)); EscFreq >>= 1; } while (EscFreq > 1); | |
457 SubAllocator.FreeUnits(stats, (OldNS+1) >> 1); | |
458 *(FoundState = &MinContext->oneState()) = tmp; return; | |
459 } | |
460 } | |
461 EscFreq -= (EscFreq >> 1); | |
462 MinContext->SummFreq = (UInt16)(MinContext->SummFreq + EscFreq); | |
463 int n0 = (OldNS+1) >> 1, n1 = (MinContext->NumStats + 1) >> 1; | |
464 if (n0 != n1) | |
465 MinContext->Stats = SubAllocator.GetOffset(SubAllocator.ShrinkUnits(stats, n0, n1)); | |
466 FoundState = GetState(MinContext->Stats); | |
467 } | |
468 | |
469 void NextContext() | |
470 { | |
471 PPM_CONTEXT *c = GetContext(FoundState->GetSuccessor()); | |
472 if (!OrderFall && (Byte *)c > SubAllocator.pText) | |
473 MinContext = MaxContext = c; | |
474 else | |
475 { | |
476 UpdateModel(); | |
477 if (EscCount == 0) | |
478 ClearMask(); | |
479 } | |
480 } | |
481 }; | |
482 | |
483 // Tabulated escapes for exponential symbol distribution | |
484 const Byte ExpEscape[16]={ 25,14, 9, 7, 5, 5, 4, 4, 4, 3, 3, 3, 2, 2, 2, 2 }; | |
485 #define GET_MEAN(SUMM,SHIFT,ROUND) ((SUMM+(1 << (SHIFT-ROUND))) >> (SHIFT)) | |
486 | |
487 }} | |
488 | |
489 #endif |