1 /* Ppmd8.c -- PPMdI codec
2 2023-09-07 : Igor Pavlov : Public domain
3 This code is based on PPMd var.I (2002): Dmitry Shkarin : Public domain */
4
5 #include "Precomp.h"
6
7 #include <string.h>
8
9 #include "Ppmd8.h"
10
11
12
13
14 MY_ALIGN(16)
15 static const Byte PPMD8_kExpEscape[16] = { 25, 14, 9, 7, 5, 5, 4, 4, 4, 3, 3, 3, 2, 2, 2, 2 };
16 MY_ALIGN(16)
17 static const UInt16 PPMD8_kInitBinEsc[] = { 0x3CDD, 0x1F3F, 0x59BF, 0x48F3, 0x64A1, 0x5ABC, 0x6632, 0x6051};
18
19 #define MAX_FREQ 124
20 #define UNIT_SIZE 12
21
22 #define U2B(nu) ((UInt32)(nu) * UNIT_SIZE)
23 #define U2I(nu) (p->Units2Indx[(size_t)(nu) - 1])
24 #define I2U(indx) ((unsigned)p->Indx2Units[indx])
25
26
27 #define REF(ptr) Ppmd_GetRef(p, ptr)
28
29 #define STATS_REF(ptr) ((CPpmd_State_Ref)REF(ptr))
30
31 #define CTX(ref) ((CPpmd8_Context *)Ppmd8_GetContext(p, ref))
32 #define STATS(ctx) Ppmd8_GetStats(p, ctx)
33 #define ONE_STATE(ctx) Ppmd8Context_OneState(ctx)
34 #define SUFFIX(ctx) CTX((ctx)->Suffix)
35
36 typedef CPpmd8_Context * PPMD8_CTX_PTR;
37
38 struct CPpmd8_Node_;
39
40 typedef Ppmd_Ref_Type(struct CPpmd8_Node_) CPpmd8_Node_Ref;
41
42 typedef struct CPpmd8_Node_
43 {
44 UInt32 Stamp;
45
46 CPpmd8_Node_Ref Next;
47 UInt32 NU;
48 } CPpmd8_Node;
49
50 #define NODE(r) Ppmd_GetPtr_Type(p, r, CPpmd8_Node)
51
Ppmd8_Construct(CPpmd8 * p)52 void Ppmd8_Construct(CPpmd8 *p)
53 {
54 unsigned i, k, m;
55
56 p->Base = NULL;
57
58 for (i = 0, k = 0; i < PPMD_NUM_INDEXES; i++)
59 {
60 unsigned step = (i >= 12 ? 4 : (i >> 2) + 1);
61 do { p->Units2Indx[k++] = (Byte)i; } while (--step);
62 p->Indx2Units[i] = (Byte)k;
63 }
64
65 p->NS2BSIndx[0] = (0 << 1);
66 p->NS2BSIndx[1] = (1 << 1);
67 memset(p->NS2BSIndx + 2, (2 << 1), 9);
68 memset(p->NS2BSIndx + 11, (3 << 1), 256 - 11);
69
70 for (i = 0; i < 5; i++)
71 p->NS2Indx[i] = (Byte)i;
72
73 for (m = i, k = 1; i < 260; i++)
74 {
75 p->NS2Indx[i] = (Byte)m;
76 if (--k == 0)
77 k = (++m) - 4;
78 }
79
80 memcpy(p->ExpEscape, PPMD8_kExpEscape, 16);
81 }
82
83
Ppmd8_Free(CPpmd8 * p,ISzAllocPtr alloc)84 void Ppmd8_Free(CPpmd8 *p, ISzAllocPtr alloc)
85 {
86 ISzAlloc_Free(alloc, p->Base);
87 p->Size = 0;
88 p->Base = NULL;
89 }
90
91
Ppmd8_Alloc(CPpmd8 * p,UInt32 size,ISzAllocPtr alloc)92 BoolInt Ppmd8_Alloc(CPpmd8 *p, UInt32 size, ISzAllocPtr alloc)
93 {
94 if (!p->Base || p->Size != size)
95 {
96 Ppmd8_Free(p, alloc);
97 p->AlignOffset = (4 - size) & 3;
98 if ((p->Base = (Byte *)ISzAlloc_Alloc(alloc, p->AlignOffset + size)) == NULL)
99 return False;
100 p->Size = size;
101 }
102 return True;
103 }
104
105
106
107 // ---------- Internal Memory Allocator ----------
108
109
110
111
112
113
114 #define EMPTY_NODE 0xFFFFFFFF
115
116
Ppmd8_InsertNode(CPpmd8 * p,void * node,unsigned indx)117 static void Ppmd8_InsertNode(CPpmd8 *p, void *node, unsigned indx)
118 {
119 ((CPpmd8_Node *)node)->Stamp = EMPTY_NODE;
120 ((CPpmd8_Node *)node)->Next = (CPpmd8_Node_Ref)p->FreeList[indx];
121 ((CPpmd8_Node *)node)->NU = I2U(indx);
122 p->FreeList[indx] = REF(node);
123 p->Stamps[indx]++;
124 }
125
126
Ppmd8_RemoveNode(CPpmd8 * p,unsigned indx)127 static void *Ppmd8_RemoveNode(CPpmd8 *p, unsigned indx)
128 {
129 CPpmd8_Node *node = NODE((CPpmd8_Node_Ref)p->FreeList[indx]);
130 p->FreeList[indx] = node->Next;
131 p->Stamps[indx]--;
132
133 return node;
134 }
135
136
Ppmd8_SplitBlock(CPpmd8 * p,void * ptr,unsigned oldIndx,unsigned newIndx)137 static void Ppmd8_SplitBlock(CPpmd8 *p, void *ptr, unsigned oldIndx, unsigned newIndx)
138 {
139 unsigned i, nu = I2U(oldIndx) - I2U(newIndx);
140 ptr = (Byte *)ptr + U2B(I2U(newIndx));
141 if (I2U(i = U2I(nu)) != nu)
142 {
143 unsigned k = I2U(--i);
144 Ppmd8_InsertNode(p, ((Byte *)ptr) + U2B(k), nu - k - 1);
145 }
146 Ppmd8_InsertNode(p, ptr, i);
147 }
148
149
150
151
152
153
154
155
156
157
158
159
160
161
Ppmd8_GlueFreeBlocks(CPpmd8 * p)162 static void Ppmd8_GlueFreeBlocks(CPpmd8 *p)
163 {
164 /*
165 we use first UInt32 field of 12-bytes UNITs as record type stamp
166 CPpmd_State { Byte Symbol; Byte Freq; : Freq != 0xFF
167 CPpmd8_Context { Byte NumStats; Byte Flags; UInt16 SummFreq; : Flags != 0xFF ???
168 CPpmd8_Node { UInt32 Stamp : Stamp == 0xFFFFFFFF for free record
169 : Stamp == 0 for guard
170 Last 12-bytes UNIT in array is always contains 12-bytes order-0 CPpmd8_Context record
171 */
172 CPpmd8_Node_Ref n;
173
174 p->GlueCount = 1 << 13;
175 memset(p->Stamps, 0, sizeof(p->Stamps));
176
177 /* we set guard NODE at LoUnit */
178 if (p->LoUnit != p->HiUnit)
179 ((CPpmd8_Node *)(void *)p->LoUnit)->Stamp = 0;
180
181 {
182 /* Glue free blocks */
183 CPpmd8_Node_Ref *prev = &n;
184 unsigned i;
185 for (i = 0; i < PPMD_NUM_INDEXES; i++)
186 {
187
188 CPpmd8_Node_Ref next = (CPpmd8_Node_Ref)p->FreeList[i];
189 p->FreeList[i] = 0;
190 while (next != 0)
191 {
192 CPpmd8_Node *node = NODE(next);
193 UInt32 nu = node->NU;
194 *prev = next;
195 next = node->Next;
196 if (nu != 0)
197 {
198 CPpmd8_Node *node2;
199 prev = &(node->Next);
200 while ((node2 = node + nu)->Stamp == EMPTY_NODE)
201 {
202 nu += node2->NU;
203 node2->NU = 0;
204 node->NU = nu;
205 }
206 }
207 }
208 }
209
210 *prev = 0;
211 }
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232 /* Fill lists of free blocks */
233 while (n != 0)
234 {
235 CPpmd8_Node *node = NODE(n);
236 UInt32 nu = node->NU;
237 unsigned i;
238 n = node->Next;
239 if (nu == 0)
240 continue;
241 for (; nu > 128; nu -= 128, node += 128)
242 Ppmd8_InsertNode(p, node, PPMD_NUM_INDEXES - 1);
243 if (I2U(i = U2I(nu)) != nu)
244 {
245 unsigned k = I2U(--i);
246 Ppmd8_InsertNode(p, node + k, (unsigned)nu - k - 1);
247 }
248 Ppmd8_InsertNode(p, node, i);
249 }
250 }
251
252
253 Z7_NO_INLINE
Ppmd8_AllocUnitsRare(CPpmd8 * p,unsigned indx)254 static void *Ppmd8_AllocUnitsRare(CPpmd8 *p, unsigned indx)
255 {
256 unsigned i;
257
258 if (p->GlueCount == 0)
259 {
260 Ppmd8_GlueFreeBlocks(p);
261 if (p->FreeList[indx] != 0)
262 return Ppmd8_RemoveNode(p, indx);
263 }
264
265 i = indx;
266
267 do
268 {
269 if (++i == PPMD_NUM_INDEXES)
270 {
271 UInt32 numBytes = U2B(I2U(indx));
272 Byte *us = p->UnitsStart;
273 p->GlueCount--;
274 return ((UInt32)(us - p->Text) > numBytes) ? (p->UnitsStart = us - numBytes) : (NULL);
275 }
276 }
277 while (p->FreeList[i] == 0);
278
279 {
280 void *block = Ppmd8_RemoveNode(p, i);
281 Ppmd8_SplitBlock(p, block, i, indx);
282 return block;
283 }
284 }
285
286
Ppmd8_AllocUnits(CPpmd8 * p,unsigned indx)287 static void *Ppmd8_AllocUnits(CPpmd8 *p, unsigned indx)
288 {
289 if (p->FreeList[indx] != 0)
290 return Ppmd8_RemoveNode(p, indx);
291 {
292 UInt32 numBytes = U2B(I2U(indx));
293 Byte *lo = p->LoUnit;
294 if ((UInt32)(p->HiUnit - lo) >= numBytes)
295 {
296 p->LoUnit = lo + numBytes;
297 return lo;
298 }
299 }
300 return Ppmd8_AllocUnitsRare(p, indx);
301 }
302
303
304 #define MEM_12_CPY(dest, src, num) \
305 { UInt32 *d = (UInt32 *)(dest); \
306 const UInt32 *z = (const UInt32 *)(src); \
307 unsigned n = (num); \
308 do { \
309 d[0] = z[0]; \
310 d[1] = z[1]; \
311 d[2] = z[2]; \
312 z += 3; \
313 d += 3; \
314 } while (--n); \
315 }
316
317
318
ShrinkUnits(CPpmd8 * p,void * oldPtr,unsigned oldNU,unsigned newNU)319 static void *ShrinkUnits(CPpmd8 *p, void *oldPtr, unsigned oldNU, unsigned newNU)
320 {
321 unsigned i0 = U2I(oldNU);
322 unsigned i1 = U2I(newNU);
323 if (i0 == i1)
324 return oldPtr;
325 if (p->FreeList[i1] != 0)
326 {
327 void *ptr = Ppmd8_RemoveNode(p, i1);
328 MEM_12_CPY(ptr, oldPtr, newNU)
329 Ppmd8_InsertNode(p, oldPtr, i0);
330 return ptr;
331 }
332 Ppmd8_SplitBlock(p, oldPtr, i0, i1);
333 return oldPtr;
334 }
335
336
FreeUnits(CPpmd8 * p,void * ptr,unsigned nu)337 static void FreeUnits(CPpmd8 *p, void *ptr, unsigned nu)
338 {
339 Ppmd8_InsertNode(p, ptr, U2I(nu));
340 }
341
342
SpecialFreeUnit(CPpmd8 * p,void * ptr)343 static void SpecialFreeUnit(CPpmd8 *p, void *ptr)
344 {
345 if ((Byte *)ptr != p->UnitsStart)
346 Ppmd8_InsertNode(p, ptr, 0);
347 else
348 {
349 #ifdef PPMD8_FREEZE_SUPPORT
350 *(UInt32 *)ptr = EMPTY_NODE; /* it's used for (Flags == 0xFF) check in RemoveBinContexts() */
351 #endif
352 p->UnitsStart += UNIT_SIZE;
353 }
354 }
355
356
357 /*
358 static void *MoveUnitsUp(CPpmd8 *p, void *oldPtr, unsigned nu)
359 {
360 unsigned indx = U2I(nu);
361 void *ptr;
362 if ((Byte *)oldPtr > p->UnitsStart + (1 << 14) || REF(oldPtr) > p->FreeList[indx])
363 return oldPtr;
364 ptr = Ppmd8_RemoveNode(p, indx);
365 MEM_12_CPY(ptr, oldPtr, nu)
366 if ((Byte *)oldPtr != p->UnitsStart)
367 Ppmd8_InsertNode(p, oldPtr, indx);
368 else
369 p->UnitsStart += U2B(I2U(indx));
370 return ptr;
371 }
372 */
373
ExpandTextArea(CPpmd8 * p)374 static void ExpandTextArea(CPpmd8 *p)
375 {
376 UInt32 count[PPMD_NUM_INDEXES];
377 unsigned i;
378
379 memset(count, 0, sizeof(count));
380 if (p->LoUnit != p->HiUnit)
381 ((CPpmd8_Node *)(void *)p->LoUnit)->Stamp = 0;
382
383 {
384 CPpmd8_Node *node = (CPpmd8_Node *)(void *)p->UnitsStart;
385 while (node->Stamp == EMPTY_NODE)
386 {
387 UInt32 nu = node->NU;
388 node->Stamp = 0;
389 count[U2I(nu)]++;
390 node += nu;
391 }
392 p->UnitsStart = (Byte *)node;
393 }
394
395 for (i = 0; i < PPMD_NUM_INDEXES; i++)
396 {
397 UInt32 cnt = count[i];
398 if (cnt == 0)
399 continue;
400 {
401 CPpmd8_Node_Ref *prev = (CPpmd8_Node_Ref *)&p->FreeList[i];
402 CPpmd8_Node_Ref n = *prev;
403 p->Stamps[i] -= cnt;
404 for (;;)
405 {
406 CPpmd8_Node *node = NODE(n);
407 n = node->Next;
408 if (node->Stamp != 0)
409 {
410 prev = &node->Next;
411 continue;
412 }
413 *prev = n;
414 if (--cnt == 0)
415 break;
416 }
417 }
418 }
419 }
420
421
422 #define SUCCESSOR(p) Ppmd_GET_SUCCESSOR(p)
Ppmd8State_SetSuccessor(CPpmd_State * p,CPpmd_Void_Ref v)423 static void Ppmd8State_SetSuccessor(CPpmd_State *p, CPpmd_Void_Ref v)
424 {
425 Ppmd_SET_SUCCESSOR(p, v)
426 }
427
428 #define RESET_TEXT(offs) { p->Text = p->Base + p->AlignOffset + (offs); }
429
430 Z7_NO_INLINE
431 static
Ppmd8_RestartModel(CPpmd8 * p)432 void Ppmd8_RestartModel(CPpmd8 *p)
433 {
434 unsigned i, k, m;
435
436 memset(p->FreeList, 0, sizeof(p->FreeList));
437 memset(p->Stamps, 0, sizeof(p->Stamps));
438 RESET_TEXT(0)
439 p->HiUnit = p->Text + p->Size;
440 p->LoUnit = p->UnitsStart = p->HiUnit - p->Size / 8 / UNIT_SIZE * 7 * UNIT_SIZE;
441 p->GlueCount = 0;
442
443 p->OrderFall = p->MaxOrder;
444 p->RunLength = p->InitRL = -(Int32)((p->MaxOrder < 12) ? p->MaxOrder : 12) - 1;
445 p->PrevSuccess = 0;
446
447 {
448 CPpmd8_Context *mc = (PPMD8_CTX_PTR)(void *)(p->HiUnit -= UNIT_SIZE); /* AllocContext(p); */
449 CPpmd_State *s = (CPpmd_State *)p->LoUnit; /* Ppmd8_AllocUnits(p, PPMD_NUM_INDEXES - 1); */
450
451 p->LoUnit += U2B(256 / 2);
452 p->MaxContext = p->MinContext = mc;
453 p->FoundState = s;
454 mc->Flags = 0;
455 mc->NumStats = 256 - 1;
456 mc->Union2.SummFreq = 256 + 1;
457 mc->Union4.Stats = REF(s);
458 mc->Suffix = 0;
459
460 for (i = 0; i < 256; i++, s++)
461 {
462 s->Symbol = (Byte)i;
463 s->Freq = 1;
464 Ppmd8State_SetSuccessor(s, 0);
465 }
466 }
467
468
469
470
471
472
473
474
475
476
477
478
479 for (i = m = 0; m < 25; m++)
480 {
481 while (p->NS2Indx[i] == m)
482 i++;
483 for (k = 0; k < 8; k++)
484 {
485 unsigned r;
486 UInt16 *dest = p->BinSumm[m] + k;
487 const UInt16 val = (UInt16)(PPMD_BIN_SCALE - PPMD8_kInitBinEsc[k] / (i + 1));
488 for (r = 0; r < 64; r += 8)
489 dest[r] = val;
490 }
491 }
492
493 for (i = m = 0; m < 24; m++)
494 {
495 unsigned summ;
496 CPpmd_See *s;
497 while (p->NS2Indx[(size_t)i + 3] == m + 3)
498 i++;
499 s = p->See[m];
500 summ = ((2 * i + 5) << (PPMD_PERIOD_BITS - 4));
501 for (k = 0; k < 32; k++, s++)
502 {
503 s->Summ = (UInt16)summ;
504 s->Shift = (PPMD_PERIOD_BITS - 4);
505 s->Count = 7;
506 }
507 }
508
509 p->DummySee.Summ = 0; /* unused */
510 p->DummySee.Shift = PPMD_PERIOD_BITS;
511 p->DummySee.Count = 64; /* unused */
512 }
513
514
Ppmd8_Init(CPpmd8 * p,unsigned maxOrder,unsigned restoreMethod)515 void Ppmd8_Init(CPpmd8 *p, unsigned maxOrder, unsigned restoreMethod)
516 {
517 p->MaxOrder = maxOrder;
518 p->RestoreMethod = restoreMethod;
519 Ppmd8_RestartModel(p);
520 }
521
522
523 #define FLAG_RESCALED (1 << 2)
524 // #define FLAG_SYM_HIGH (1 << 3)
525 #define FLAG_PREV_HIGH (1 << 4)
526
527 #define HiBits_Prepare(sym) ((unsigned)(sym) + 0xC0)
528
529 #define HiBits_Convert_3(flags) (((flags) >> (8 - 3)) & (1 << 3))
530 #define HiBits_Convert_4(flags) (((flags) >> (8 - 4)) & (1 << 4))
531
532 #define PPMD8_HiBitsFlag_3(sym) HiBits_Convert_3(HiBits_Prepare(sym))
533 #define PPMD8_HiBitsFlag_4(sym) HiBits_Convert_4(HiBits_Prepare(sym))
534
535 // #define PPMD8_HiBitsFlag_3(sym) (0x08 * ((sym) >= 0x40))
536 // #define PPMD8_HiBitsFlag_4(sym) (0x10 * ((sym) >= 0x40))
537
538 /*
539 Refresh() is called when we remove some symbols (successors) in context.
540 It increases Escape_Freq for sum of all removed symbols.
541 */
542
Refresh(CPpmd8 * p,PPMD8_CTX_PTR ctx,unsigned oldNU,unsigned scale)543 static void Refresh(CPpmd8 *p, PPMD8_CTX_PTR ctx, unsigned oldNU, unsigned scale)
544 {
545 unsigned i = ctx->NumStats, escFreq, sumFreq, flags;
546 CPpmd_State *s = (CPpmd_State *)ShrinkUnits(p, STATS(ctx), oldNU, (i + 2) >> 1);
547 ctx->Union4.Stats = REF(s);
548
549 // #ifdef PPMD8_FREEZE_SUPPORT
550 /*
551 (ctx->Union2.SummFreq >= ((UInt32)1 << 15)) can be in FREEZE mode for some files.
552 It's not good for range coder. So new versions of support fix:
553 - original PPMdI code rev.1
554 + original PPMdI code rev.2
555 - 7-Zip default ((PPMD8_FREEZE_SUPPORT is not defined)
556 + 7-Zip (p->RestoreMethod >= PPMD8_RESTORE_METHOD_FREEZE)
557 if we use that fixed line, we can lose compatibility with some files created before fix
558 if we don't use that fixed line, the program can work incorrectly in FREEZE mode in rare case.
559 */
560 // if (p->RestoreMethod >= PPMD8_RESTORE_METHOD_FREEZE)
561 {
562 scale |= (ctx->Union2.SummFreq >= ((UInt32)1 << 15));
563 }
564 // #endif
565
566
567
568 flags = HiBits_Prepare(s->Symbol);
569 {
570 unsigned freq = s->Freq;
571 escFreq = ctx->Union2.SummFreq - freq;
572 freq = (freq + scale) >> scale;
573 sumFreq = freq;
574 s->Freq = (Byte)freq;
575 }
576
577 do
578 {
579 unsigned freq = (++s)->Freq;
580 escFreq -= freq;
581 freq = (freq + scale) >> scale;
582 sumFreq += freq;
583 s->Freq = (Byte)freq;
584 flags |= HiBits_Prepare(s->Symbol);
585 }
586 while (--i);
587
588 ctx->Union2.SummFreq = (UInt16)(sumFreq + ((escFreq + scale) >> scale));
589 ctx->Flags = (Byte)((ctx->Flags & (FLAG_PREV_HIGH + FLAG_RESCALED * scale)) + HiBits_Convert_3(flags));
590 }
591
592
SWAP_STATES(CPpmd_State * t1,CPpmd_State * t2)593 static void SWAP_STATES(CPpmd_State *t1, CPpmd_State *t2)
594 {
595 CPpmd_State tmp = *t1;
596 *t1 = *t2;
597 *t2 = tmp;
598 }
599
600
601 /*
602 CutOff() reduces contexts:
603 It conversts Successors at MaxOrder to another Contexts to NULL-Successors
604 It removes RAW-Successors and NULL-Successors that are not Order-0
605 and it removes contexts when it has no Successors.
606 if the (Union4.Stats) is close to (UnitsStart), it moves it up.
607 */
608
CutOff(CPpmd8 * p,PPMD8_CTX_PTR ctx,unsigned order)609 static CPpmd_Void_Ref CutOff(CPpmd8 *p, PPMD8_CTX_PTR ctx, unsigned order)
610 {
611 int ns = ctx->NumStats;
612 unsigned nu;
613 CPpmd_State *stats;
614
615 if (ns == 0)
616 {
617 CPpmd_State *s = ONE_STATE(ctx);
618 CPpmd_Void_Ref successor = SUCCESSOR(s);
619 if ((Byte *)Ppmd8_GetPtr(p, successor) >= p->UnitsStart)
620 {
621 if (order < p->MaxOrder)
622 successor = CutOff(p, CTX(successor), order + 1);
623 else
624 successor = 0;
625 Ppmd8State_SetSuccessor(s, successor);
626 if (successor || order <= 9) /* O_BOUND */
627 return REF(ctx);
628 }
629 SpecialFreeUnit(p, ctx);
630 return 0;
631 }
632
633 nu = ((unsigned)ns + 2) >> 1;
634 // ctx->Union4.Stats = STATS_REF(MoveUnitsUp(p, STATS(ctx), nu));
635 {
636 unsigned indx = U2I(nu);
637 stats = STATS(ctx);
638
639 if ((UInt32)((Byte *)stats - p->UnitsStart) <= (1 << 14)
640 && (CPpmd_Void_Ref)ctx->Union4.Stats <= p->FreeList[indx])
641 {
642 void *ptr = Ppmd8_RemoveNode(p, indx);
643 ctx->Union4.Stats = STATS_REF(ptr);
644 MEM_12_CPY(ptr, (const void *)stats, nu)
645 if ((Byte *)stats != p->UnitsStart)
646 Ppmd8_InsertNode(p, stats, indx);
647 else
648 p->UnitsStart += U2B(I2U(indx));
649 stats = ptr;
650 }
651 }
652
653 {
654 CPpmd_State *s = stats + (unsigned)ns;
655 do
656 {
657 CPpmd_Void_Ref successor = SUCCESSOR(s);
658 if ((Byte *)Ppmd8_GetPtr(p, successor) < p->UnitsStart)
659 {
660 CPpmd_State *s2 = stats + (unsigned)(ns--);
661 if (order)
662 {
663 if (s != s2)
664 *s = *s2;
665 }
666 else
667 {
668 SWAP_STATES(s, s2);
669 Ppmd8State_SetSuccessor(s2, 0);
670 }
671 }
672 else
673 {
674 if (order < p->MaxOrder)
675 Ppmd8State_SetSuccessor(s, CutOff(p, CTX(successor), order + 1));
676 else
677 Ppmd8State_SetSuccessor(s, 0);
678 }
679 }
680 while (--s >= stats);
681 }
682
683 if (ns != ctx->NumStats && order)
684 {
685 if (ns < 0)
686 {
687 FreeUnits(p, stats, nu);
688 SpecialFreeUnit(p, ctx);
689 return 0;
690 }
691 ctx->NumStats = (Byte)ns;
692 if (ns == 0)
693 {
694 const Byte sym = stats->Symbol;
695 ctx->Flags = (Byte)((ctx->Flags & FLAG_PREV_HIGH) + PPMD8_HiBitsFlag_3(sym));
696 // *ONE_STATE(ctx) = *stats;
697 ctx->Union2.State2.Symbol = sym;
698 ctx->Union2.State2.Freq = (Byte)(((unsigned)stats->Freq + 11) >> 3);
699 ctx->Union4.State4.Successor_0 = stats->Successor_0;
700 ctx->Union4.State4.Successor_1 = stats->Successor_1;
701 FreeUnits(p, stats, nu);
702 }
703 else
704 {
705 Refresh(p, ctx, nu, ctx->Union2.SummFreq > 16 * (unsigned)ns);
706 }
707 }
708
709 return REF(ctx);
710 }
711
712
713
714 #ifdef PPMD8_FREEZE_SUPPORT
715
716 /*
717 RemoveBinContexts()
718 It conversts Successors at MaxOrder to another Contexts to NULL-Successors
719 It changes RAW-Successors to NULL-Successors
720 removes Bin Context without Successor, if suffix of that context is also binary.
721 */
722
RemoveBinContexts(CPpmd8 * p,PPMD8_CTX_PTR ctx,unsigned order)723 static CPpmd_Void_Ref RemoveBinContexts(CPpmd8 *p, PPMD8_CTX_PTR ctx, unsigned order)
724 {
725 if (!ctx->NumStats)
726 {
727 CPpmd_State *s = ONE_STATE(ctx);
728 CPpmd_Void_Ref successor = SUCCESSOR(s);
729 if ((Byte *)Ppmd8_GetPtr(p, successor) >= p->UnitsStart && order < p->MaxOrder)
730 successor = RemoveBinContexts(p, CTX(successor), order + 1);
731 else
732 successor = 0;
733 Ppmd8State_SetSuccessor(s, successor);
734 /* Suffix context can be removed already, since different (high-order)
735 Successors may refer to same context. So we check Flags == 0xFF (Stamp == EMPTY_NODE) */
736 if (!successor && (!SUFFIX(ctx)->NumStats || SUFFIX(ctx)->Flags == 0xFF))
737 {
738 FreeUnits(p, ctx, 1);
739 return 0;
740 }
741 }
742 else
743 {
744 CPpmd_State *s = STATS(ctx) + ctx->NumStats;
745 do
746 {
747 CPpmd_Void_Ref successor = SUCCESSOR(s);
748 if ((Byte *)Ppmd8_GetPtr(p, successor) >= p->UnitsStart && order < p->MaxOrder)
749 Ppmd8State_SetSuccessor(s, RemoveBinContexts(p, CTX(successor), order + 1));
750 else
751 Ppmd8State_SetSuccessor(s, 0);
752 }
753 while (--s >= STATS(ctx));
754 }
755
756 return REF(ctx);
757 }
758
759 #endif
760
761
762
GetUsedMemory(const CPpmd8 * p)763 static UInt32 GetUsedMemory(const CPpmd8 *p)
764 {
765 UInt32 v = 0;
766 unsigned i;
767 for (i = 0; i < PPMD_NUM_INDEXES; i++)
768 v += p->Stamps[i] * I2U(i);
769 return p->Size - (UInt32)(p->HiUnit - p->LoUnit) - (UInt32)(p->UnitsStart - p->Text) - U2B(v);
770 }
771
772 #ifdef PPMD8_FREEZE_SUPPORT
773 #define RESTORE_MODEL(c1, fSuccessor) RestoreModel(p, c1, fSuccessor)
774 #else
775 #define RESTORE_MODEL(c1, fSuccessor) RestoreModel(p, c1)
776 #endif
777
778
RestoreModel(CPpmd8 * p,PPMD8_CTX_PTR ctxError,PPMD8_CTX_PTR fSuccessor)779 static void RestoreModel(CPpmd8 *p, PPMD8_CTX_PTR ctxError
780 #ifdef PPMD8_FREEZE_SUPPORT
781 , PPMD8_CTX_PTR fSuccessor
782 #endif
783 )
784 {
785 PPMD8_CTX_PTR c;
786 CPpmd_State *s;
787 RESET_TEXT(0)
788
789 // we go here in cases of error of allocation for context (c1)
790 // Order(MinContext) < Order(ctxError) <= Order(MaxContext)
791
792 // We remove last symbol from each of contexts [p->MaxContext ... ctxError) contexts
793 // So we rollback all created (symbols) before error.
794 for (c = p->MaxContext; c != ctxError; c = SUFFIX(c))
795 if (--(c->NumStats) == 0)
796 {
797 s = STATS(c);
798 c->Flags = (Byte)((c->Flags & FLAG_PREV_HIGH) + PPMD8_HiBitsFlag_3(s->Symbol));
799 // *ONE_STATE(c) = *s;
800 c->Union2.State2.Symbol = s->Symbol;
801 c->Union2.State2.Freq = (Byte)(((unsigned)s->Freq + 11) >> 3);
802 c->Union4.State4.Successor_0 = s->Successor_0;
803 c->Union4.State4.Successor_1 = s->Successor_1;
804
805 SpecialFreeUnit(p, s);
806 }
807 else
808 {
809 /* Refresh() can increase Escape_Freq on value of Freq of last symbol, that was added before error.
810 so the largest possible increase for Escape_Freq is (8) from value before ModelUpoadet() */
811 Refresh(p, c, ((unsigned)c->NumStats + 3) >> 1, 0);
812 }
813
814 // increase Escape Freq for context [ctxError ... p->MinContext)
815 for (; c != p->MinContext; c = SUFFIX(c))
816 if (c->NumStats == 0)
817 {
818 // ONE_STATE(c)
819 c->Union2.State2.Freq = (Byte)(((unsigned)c->Union2.State2.Freq + 1) >> 1);
820 }
821 else if ((c->Union2.SummFreq = (UInt16)(c->Union2.SummFreq + 4)) > 128 + 4 * c->NumStats)
822 Refresh(p, c, ((unsigned)c->NumStats + 2) >> 1, 1);
823
824 #ifdef PPMD8_FREEZE_SUPPORT
825 if (p->RestoreMethod > PPMD8_RESTORE_METHOD_FREEZE)
826 {
827 p->MaxContext = fSuccessor;
828 p->GlueCount += !(p->Stamps[1] & 1); // why?
829 }
830 else if (p->RestoreMethod == PPMD8_RESTORE_METHOD_FREEZE)
831 {
832 while (p->MaxContext->Suffix)
833 p->MaxContext = SUFFIX(p->MaxContext);
834 RemoveBinContexts(p, p->MaxContext, 0);
835 // we change the current mode to (PPMD8_RESTORE_METHOD_FREEZE + 1)
836 p->RestoreMethod = PPMD8_RESTORE_METHOD_FREEZE + 1;
837 p->GlueCount = 0;
838 p->OrderFall = p->MaxOrder;
839 }
840 else
841 #endif
842 if (p->RestoreMethod == PPMD8_RESTORE_METHOD_RESTART || GetUsedMemory(p) < (p->Size >> 1))
843 Ppmd8_RestartModel(p);
844 else
845 {
846 while (p->MaxContext->Suffix)
847 p->MaxContext = SUFFIX(p->MaxContext);
848 do
849 {
850 CutOff(p, p->MaxContext, 0);
851 ExpandTextArea(p);
852 }
853 while (GetUsedMemory(p) > 3 * (p->Size >> 2));
854 p->GlueCount = 0;
855 p->OrderFall = p->MaxOrder;
856 }
857 p->MinContext = p->MaxContext;
858 }
859
860
861
862 Z7_NO_INLINE
Ppmd8_CreateSuccessors(CPpmd8 * p,BoolInt skip,CPpmd_State * s1,PPMD8_CTX_PTR c)863 static PPMD8_CTX_PTR Ppmd8_CreateSuccessors(CPpmd8 *p, BoolInt skip, CPpmd_State *s1, PPMD8_CTX_PTR c)
864 {
865
866 CPpmd_Byte_Ref upBranch = (CPpmd_Byte_Ref)SUCCESSOR(p->FoundState);
867 Byte newSym, newFreq, flags;
868 unsigned numPs = 0;
869 CPpmd_State *ps[PPMD8_MAX_ORDER + 1]; /* fixed over Shkarin's code. Maybe it could work without + 1 too. */
870
871 if (!skip)
872 ps[numPs++] = p->FoundState;
873
874 while (c->Suffix)
875 {
876 CPpmd_Void_Ref successor;
877 CPpmd_State *s;
878 c = SUFFIX(c);
879
880 if (s1) { s = s1; s1 = NULL; }
881 else if (c->NumStats != 0)
882 {
883 Byte sym = p->FoundState->Symbol;
884 for (s = STATS(c); s->Symbol != sym; s++);
885 if (s->Freq < MAX_FREQ - 9) { s->Freq++; c->Union2.SummFreq++; }
886 }
887 else
888 {
889 s = ONE_STATE(c);
890 s->Freq = (Byte)(s->Freq + (!SUFFIX(c)->NumStats & (s->Freq < 24)));
891 }
892 successor = SUCCESSOR(s);
893 if (successor != upBranch)
894 {
895
896 c = CTX(successor);
897 if (numPs == 0)
898 {
899
900
901 return c;
902 }
903 break;
904 }
905 ps[numPs++] = s;
906 }
907
908
909
910
911
912 newSym = *(const Byte *)Ppmd8_GetPtr(p, upBranch);
913 upBranch++;
914 flags = (Byte)(PPMD8_HiBitsFlag_4(p->FoundState->Symbol) + PPMD8_HiBitsFlag_3(newSym));
915
916 if (c->NumStats == 0)
917 newFreq = c->Union2.State2.Freq;
918 else
919 {
920 UInt32 cf, s0;
921 CPpmd_State *s;
922 for (s = STATS(c); s->Symbol != newSym; s++);
923 cf = (UInt32)s->Freq - 1;
924 s0 = (UInt32)c->Union2.SummFreq - c->NumStats - cf;
925 /*
926
927
928 max(newFreq)= (s->Freq - 1), when (s0 == 1)
929
930
931 */
932 newFreq = (Byte)(1 + ((2 * cf <= s0) ? (5 * cf > s0) : ((cf + 2 * s0 - 3) / s0)));
933 }
934
935
936
937 do
938 {
939 PPMD8_CTX_PTR c1;
940 /* = AllocContext(p); */
941 if (p->HiUnit != p->LoUnit)
942 c1 = (PPMD8_CTX_PTR)(void *)(p->HiUnit -= UNIT_SIZE);
943 else if (p->FreeList[0] != 0)
944 c1 = (PPMD8_CTX_PTR)Ppmd8_RemoveNode(p, 0);
945 else
946 {
947 c1 = (PPMD8_CTX_PTR)Ppmd8_AllocUnitsRare(p, 0);
948 if (!c1)
949 return NULL;
950 }
951 c1->Flags = flags;
952 c1->NumStats = 0;
953 c1->Union2.State2.Symbol = newSym;
954 c1->Union2.State2.Freq = newFreq;
955 Ppmd8State_SetSuccessor(ONE_STATE(c1), upBranch);
956 c1->Suffix = REF(c);
957 Ppmd8State_SetSuccessor(ps[--numPs], REF(c1));
958 c = c1;
959 }
960 while (numPs != 0);
961
962 return c;
963 }
964
965
ReduceOrder(CPpmd8 * p,CPpmd_State * s1,PPMD8_CTX_PTR c)966 static PPMD8_CTX_PTR ReduceOrder(CPpmd8 *p, CPpmd_State *s1, PPMD8_CTX_PTR c)
967 {
968 CPpmd_State *s = NULL;
969 PPMD8_CTX_PTR c1 = c;
970 CPpmd_Void_Ref upBranch = REF(p->Text);
971
972 #ifdef PPMD8_FREEZE_SUPPORT
973 /* The BUG in Shkarin's code was fixed: ps could overflow in CUT_OFF mode. */
974 CPpmd_State *ps[PPMD8_MAX_ORDER + 1];
975 unsigned numPs = 0;
976 ps[numPs++] = p->FoundState;
977 #endif
978
979 Ppmd8State_SetSuccessor(p->FoundState, upBranch);
980 p->OrderFall++;
981
982 for (;;)
983 {
984 if (s1)
985 {
986 c = SUFFIX(c);
987 s = s1;
988 s1 = NULL;
989 }
990 else
991 {
992 if (!c->Suffix)
993 {
994 #ifdef PPMD8_FREEZE_SUPPORT
995 if (p->RestoreMethod > PPMD8_RESTORE_METHOD_FREEZE)
996 {
997 do { Ppmd8State_SetSuccessor(ps[--numPs], REF(c)); } while (numPs);
998 RESET_TEXT(1)
999 p->OrderFall = 1;
1000 }
1001 #endif
1002 return c;
1003 }
1004 c = SUFFIX(c);
1005 if (c->NumStats)
1006 {
1007 if ((s = STATS(c))->Symbol != p->FoundState->Symbol)
1008 do { s++; } while (s->Symbol != p->FoundState->Symbol);
1009 if (s->Freq < MAX_FREQ - 9)
1010 {
1011 s->Freq = (Byte)(s->Freq + 2);
1012 c->Union2.SummFreq = (UInt16)(c->Union2.SummFreq + 2);
1013 }
1014 }
1015 else
1016 {
1017 s = ONE_STATE(c);
1018 s->Freq = (Byte)(s->Freq + (s->Freq < 32));
1019 }
1020 }
1021 if (SUCCESSOR(s))
1022 break;
1023 #ifdef PPMD8_FREEZE_SUPPORT
1024 ps[numPs++] = s;
1025 #endif
1026 Ppmd8State_SetSuccessor(s, upBranch);
1027 p->OrderFall++;
1028 }
1029
1030 #ifdef PPMD8_FREEZE_SUPPORT
1031 if (p->RestoreMethod > PPMD8_RESTORE_METHOD_FREEZE)
1032 {
1033 c = CTX(SUCCESSOR(s));
1034 do { Ppmd8State_SetSuccessor(ps[--numPs], REF(c)); } while (numPs);
1035 RESET_TEXT(1)
1036 p->OrderFall = 1;
1037 return c;
1038 }
1039 else
1040 #endif
1041 if (SUCCESSOR(s) <= upBranch)
1042 {
1043 PPMD8_CTX_PTR successor;
1044 CPpmd_State *s2 = p->FoundState;
1045 p->FoundState = s;
1046
1047 successor = Ppmd8_CreateSuccessors(p, False, NULL, c);
1048 if (!successor)
1049 Ppmd8State_SetSuccessor(s, 0);
1050 else
1051 Ppmd8State_SetSuccessor(s, REF(successor));
1052 p->FoundState = s2;
1053 }
1054
1055 {
1056 CPpmd_Void_Ref successor = SUCCESSOR(s);
1057 if (p->OrderFall == 1 && c1 == p->MaxContext)
1058 {
1059 Ppmd8State_SetSuccessor(p->FoundState, successor);
1060 p->Text--;
1061 }
1062 if (successor == 0)
1063 return NULL;
1064 return CTX(successor);
1065 }
1066 }
1067
1068
1069
1070 void Ppmd8_UpdateModel(CPpmd8 *p);
1071 Z7_NO_INLINE
Ppmd8_UpdateModel(CPpmd8 * p)1072 void Ppmd8_UpdateModel(CPpmd8 *p)
1073 {
1074 CPpmd_Void_Ref maxSuccessor, minSuccessor = SUCCESSOR(p->FoundState);
1075 PPMD8_CTX_PTR c;
1076 unsigned s0, ns, fFreq = p->FoundState->Freq;
1077 Byte flag, fSymbol = p->FoundState->Symbol;
1078 {
1079 CPpmd_State *s = NULL;
1080 if (p->FoundState->Freq < MAX_FREQ / 4 && p->MinContext->Suffix != 0)
1081 {
1082 /* Update Freqs in Suffix Context */
1083
1084 c = SUFFIX(p->MinContext);
1085
1086 if (c->NumStats == 0)
1087 {
1088 s = ONE_STATE(c);
1089 if (s->Freq < 32)
1090 s->Freq++;
1091 }
1092 else
1093 {
1094 Byte sym = p->FoundState->Symbol;
1095 s = STATS(c);
1096
1097 if (s->Symbol != sym)
1098 {
1099 do
1100 {
1101
1102 s++;
1103 }
1104 while (s->Symbol != sym);
1105
1106 if (s[0].Freq >= s[-1].Freq)
1107 {
1108 SWAP_STATES(&s[0], &s[-1]);
1109 s--;
1110 }
1111 }
1112
1113 if (s->Freq < MAX_FREQ - 9)
1114 {
1115 s->Freq = (Byte)(s->Freq + 2);
1116 c->Union2.SummFreq = (UInt16)(c->Union2.SummFreq + 2);
1117 }
1118 }
1119 }
1120
1121 c = p->MaxContext;
1122 if (p->OrderFall == 0 && minSuccessor)
1123 {
1124 PPMD8_CTX_PTR cs = Ppmd8_CreateSuccessors(p, True, s, p->MinContext);
1125 if (!cs)
1126 {
1127 Ppmd8State_SetSuccessor(p->FoundState, 0);
1128 RESTORE_MODEL(c, CTX(minSuccessor));
1129 return;
1130 }
1131 Ppmd8State_SetSuccessor(p->FoundState, REF(cs));
1132 p->MinContext = p->MaxContext = cs;
1133 return;
1134 }
1135
1136
1137
1138
1139 {
1140 Byte *text = p->Text;
1141 *text++ = p->FoundState->Symbol;
1142 p->Text = text;
1143 if (text >= p->UnitsStart)
1144 {
1145 RESTORE_MODEL(c, CTX(minSuccessor)); /* check it */
1146 return;
1147 }
1148 maxSuccessor = REF(text);
1149 }
1150
1151 if (!minSuccessor)
1152 {
1153 PPMD8_CTX_PTR cs = ReduceOrder(p, s, p->MinContext);
1154 if (!cs)
1155 {
1156 RESTORE_MODEL(c, NULL);
1157 return;
1158 }
1159 minSuccessor = REF(cs);
1160 }
1161 else if ((Byte *)Ppmd8_GetPtr(p, minSuccessor) < p->UnitsStart)
1162 {
1163 PPMD8_CTX_PTR cs = Ppmd8_CreateSuccessors(p, False, s, p->MinContext);
1164 if (!cs)
1165 {
1166 RESTORE_MODEL(c, NULL);
1167 return;
1168 }
1169 minSuccessor = REF(cs);
1170 }
1171
1172 if (--p->OrderFall == 0)
1173 {
1174 maxSuccessor = minSuccessor;
1175 p->Text -= (p->MaxContext != p->MinContext);
1176 }
1177 #ifdef PPMD8_FREEZE_SUPPORT
1178 else if (p->RestoreMethod > PPMD8_RESTORE_METHOD_FREEZE)
1179 {
1180 maxSuccessor = minSuccessor;
1181 RESET_TEXT(0)
1182 p->OrderFall = 0;
1183 }
1184 #endif
1185 }
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214 flag = (Byte)(PPMD8_HiBitsFlag_3(fSymbol));
1215 s0 = p->MinContext->Union2.SummFreq - (ns = p->MinContext->NumStats) - fFreq;
1216
1217 for (; c != p->MinContext; c = SUFFIX(c))
1218 {
1219 unsigned ns1;
1220 UInt32 sum;
1221
1222 if ((ns1 = c->NumStats) != 0)
1223 {
1224 if ((ns1 & 1) != 0)
1225 {
1226 /* Expand for one UNIT */
1227 const unsigned oldNU = (ns1 + 1) >> 1;
1228 const unsigned i = U2I(oldNU);
1229 if (i != U2I((size_t)oldNU + 1))
1230 {
1231 void *ptr = Ppmd8_AllocUnits(p, i + 1);
1232 void *oldPtr;
1233 if (!ptr)
1234 {
1235 RESTORE_MODEL(c, CTX(minSuccessor));
1236 return;
1237 }
1238 oldPtr = STATS(c);
1239 MEM_12_CPY(ptr, oldPtr, oldNU)
1240 Ppmd8_InsertNode(p, oldPtr, i);
1241 c->Union4.Stats = STATS_REF(ptr);
1242 }
1243 }
1244 sum = c->Union2.SummFreq;
1245 /* max increase of Escape_Freq is 1 here.
1246 an average increase is 1/3 per symbol */
1247 sum += (UInt32)(unsigned)(3 * ns1 + 1 < ns);
1248 /* original PPMdH uses 16-bit variable for (sum) here.
1249 But (sum < ???). Do we need to truncate (sum) to 16-bit */
1250 // sum = (UInt16)sum;
1251 }
1252 else
1253 {
1254
1255 CPpmd_State *s = (CPpmd_State*)Ppmd8_AllocUnits(p, 0);
1256 if (!s)
1257 {
1258 RESTORE_MODEL(c, CTX(minSuccessor));
1259 return;
1260 }
1261 {
1262 unsigned freq = c->Union2.State2.Freq;
1263 // s = *ONE_STATE(c);
1264 s->Symbol = c->Union2.State2.Symbol;
1265 s->Successor_0 = c->Union4.State4.Successor_0;
1266 s->Successor_1 = c->Union4.State4.Successor_1;
1267 // Ppmd8State_SetSuccessor(s, c->Union4.Stats); // call it only for debug purposes to check the order of
1268 // (Successor_0 and Successor_1) in LE/BE.
1269 c->Union4.Stats = REF(s);
1270 if (freq < MAX_FREQ / 4 - 1)
1271 freq <<= 1;
1272 else
1273 freq = MAX_FREQ - 4;
1274
1275 s->Freq = (Byte)freq;
1276
1277 sum = (UInt32)(freq + p->InitEsc + (ns > 2)); // Ppmd8 (> 2)
1278 }
1279 }
1280
1281 {
1282 CPpmd_State *s = STATS(c) + ns1 + 1;
1283 UInt32 cf = 2 * (sum + 6) * (UInt32)fFreq;
1284 UInt32 sf = (UInt32)s0 + sum;
1285 s->Symbol = fSymbol;
1286 c->NumStats = (Byte)(ns1 + 1);
1287 Ppmd8State_SetSuccessor(s, maxSuccessor);
1288 c->Flags |= flag;
1289 if (cf < 6 * sf)
1290 {
1291 cf = (unsigned)1 + (cf > sf) + (cf >= 4 * sf);
1292 sum += 4;
1293 /* It can add (1, 2, 3) to Escape_Freq */
1294 }
1295 else
1296 {
1297 cf = (unsigned)4 + (cf > 9 * sf) + (cf > 12 * sf) + (cf > 15 * sf);
1298 sum += cf;
1299 }
1300
1301 c->Union2.SummFreq = (UInt16)sum;
1302 s->Freq = (Byte)cf;
1303 }
1304
1305 }
1306 p->MaxContext = p->MinContext = CTX(minSuccessor);
1307 }
1308
1309
1310
1311 Z7_NO_INLINE
Ppmd8_Rescale(CPpmd8 * p)1312 static void Ppmd8_Rescale(CPpmd8 *p)
1313 {
1314 unsigned i, adder, sumFreq, escFreq;
1315 CPpmd_State *stats = STATS(p->MinContext);
1316 CPpmd_State *s = p->FoundState;
1317
1318 /* Sort the list by Freq */
1319 if (s != stats)
1320 {
1321 CPpmd_State tmp = *s;
1322 do
1323 s[0] = s[-1];
1324 while (--s != stats);
1325 *s = tmp;
1326 }
1327
1328 sumFreq = s->Freq;
1329 escFreq = p->MinContext->Union2.SummFreq - sumFreq;
1330
1331
1332
1333
1334
1335
1336 adder = (p->OrderFall != 0);
1337
1338 #ifdef PPMD8_FREEZE_SUPPORT
1339 adder |= (p->RestoreMethod > PPMD8_RESTORE_METHOD_FREEZE);
1340 #endif
1341
1342 sumFreq = (sumFreq + 4 + adder) >> 1;
1343 i = p->MinContext->NumStats;
1344 s->Freq = (Byte)sumFreq;
1345
1346 do
1347 {
1348 unsigned freq = (++s)->Freq;
1349 escFreq -= freq;
1350 freq = (freq + adder) >> 1;
1351 sumFreq += freq;
1352 s->Freq = (Byte)freq;
1353 if (freq > s[-1].Freq)
1354 {
1355 CPpmd_State tmp = *s;
1356 CPpmd_State *s1 = s;
1357 do
1358 {
1359 s1[0] = s1[-1];
1360 }
1361 while (--s1 != stats && freq > s1[-1].Freq);
1362 *s1 = tmp;
1363 }
1364 }
1365 while (--i);
1366
1367 if (s->Freq == 0)
1368 {
1369 /* Remove all items with Freq == 0 */
1370 CPpmd8_Context *mc;
1371 unsigned numStats, numStatsNew, n0, n1;
1372
1373 i = 0; do { i++; } while ((--s)->Freq == 0);
1374
1375
1376
1377
1378 escFreq += i;
1379 mc = p->MinContext;
1380 numStats = mc->NumStats;
1381 numStatsNew = numStats - i;
1382 mc->NumStats = (Byte)(numStatsNew);
1383 n0 = (numStats + 2) >> 1;
1384
1385 if (numStatsNew == 0)
1386 {
1387
1388 unsigned freq = (2 * (unsigned)stats->Freq + escFreq - 1) / escFreq;
1389 if (freq > MAX_FREQ / 3)
1390 freq = MAX_FREQ / 3;
1391 mc->Flags = (Byte)((mc->Flags & FLAG_PREV_HIGH) + PPMD8_HiBitsFlag_3(stats->Symbol));
1392
1393
1394
1395
1396
1397 s = ONE_STATE(mc);
1398 *s = *stats;
1399 s->Freq = (Byte)freq;
1400 p->FoundState = s;
1401 Ppmd8_InsertNode(p, stats, U2I(n0));
1402 return;
1403 }
1404
1405 n1 = (numStatsNew + 2) >> 1;
1406 if (n0 != n1)
1407 mc->Union4.Stats = STATS_REF(ShrinkUnits(p, stats, n0, n1));
1408 {
1409 // here we are for max order only. So Ppmd8_MakeEscFreq() doesn't use mc->Flags
1410 // but we still need current (Flags & FLAG_PREV_HIGH), if we will convert context to 1-symbol context later.
1411 /*
1412 unsigned flags = HiBits_Prepare((s = STATS(mc))->Symbol);
1413 i = mc->NumStats;
1414 do { flags |= HiBits_Prepare((++s)->Symbol); } while (--i);
1415 mc->Flags = (Byte)((mc->Flags & ~FLAG_SYM_HIGH) + HiBits_Convert_3(flags));
1416 */
1417 }
1418 }
1419
1420
1421
1422
1423
1424
1425 {
1426 CPpmd8_Context *mc = p->MinContext;
1427 mc->Union2.SummFreq = (UInt16)(sumFreq + escFreq - (escFreq >> 1));
1428 mc->Flags |= FLAG_RESCALED;
1429 p->FoundState = STATS(mc);
1430 }
1431 }
1432
1433
Ppmd8_MakeEscFreq(CPpmd8 * p,unsigned numMasked1,UInt32 * escFreq)1434 CPpmd_See *Ppmd8_MakeEscFreq(CPpmd8 *p, unsigned numMasked1, UInt32 *escFreq)
1435 {
1436 CPpmd_See *see;
1437 const CPpmd8_Context *mc = p->MinContext;
1438 unsigned numStats = mc->NumStats;
1439 if (numStats != 0xFF)
1440 {
1441 // (3 <= numStats + 2 <= 256) (3 <= NS2Indx[3] and NS2Indx[256] === 26)
1442 see = p->See[(size_t)(unsigned)p->NS2Indx[(size_t)numStats + 2] - 3]
1443 + (mc->Union2.SummFreq > 11 * (numStats + 1))
1444 + 2 * (unsigned)(2 * numStats < ((unsigned)SUFFIX(mc)->NumStats + numMasked1))
1445 + mc->Flags;
1446
1447 {
1448 // if (see->Summ) field is larger than 16-bit, we need only low 16 bits of Summ
1449 const unsigned summ = (UInt16)see->Summ; // & 0xFFFF
1450 const unsigned r = (summ >> see->Shift);
1451 see->Summ = (UInt16)(summ - r);
1452 *escFreq = (UInt32)(r + (r == 0));
1453 }
1454 }
1455 else
1456 {
1457 see = &p->DummySee;
1458 *escFreq = 1;
1459 }
1460 return see;
1461 }
1462
1463
Ppmd8_NextContext(CPpmd8 * p)1464 static void Ppmd8_NextContext(CPpmd8 *p)
1465 {
1466 PPMD8_CTX_PTR c = CTX(SUCCESSOR(p->FoundState));
1467 if (p->OrderFall == 0 && (const Byte *)c >= p->UnitsStart)
1468 p->MaxContext = p->MinContext = c;
1469 else
1470 Ppmd8_UpdateModel(p);
1471 }
1472
1473
Ppmd8_Update1(CPpmd8 * p)1474 void Ppmd8_Update1(CPpmd8 *p)
1475 {
1476 CPpmd_State *s = p->FoundState;
1477 unsigned freq = s->Freq;
1478 freq += 4;
1479 p->MinContext->Union2.SummFreq = (UInt16)(p->MinContext->Union2.SummFreq + 4);
1480 s->Freq = (Byte)freq;
1481 if (freq > s[-1].Freq)
1482 {
1483 SWAP_STATES(s, &s[-1]);
1484 p->FoundState = --s;
1485 if (freq > MAX_FREQ)
1486 Ppmd8_Rescale(p);
1487 }
1488 Ppmd8_NextContext(p);
1489 }
1490
1491
Ppmd8_Update1_0(CPpmd8 * p)1492 void Ppmd8_Update1_0(CPpmd8 *p)
1493 {
1494 CPpmd_State *s = p->FoundState;
1495 CPpmd8_Context *mc = p->MinContext;
1496 unsigned freq = s->Freq;
1497 const unsigned summFreq = mc->Union2.SummFreq;
1498 p->PrevSuccess = (2 * freq >= summFreq); // Ppmd8 (>=)
1499 p->RunLength += (Int32)p->PrevSuccess;
1500 mc->Union2.SummFreq = (UInt16)(summFreq + 4);
1501 freq += 4;
1502 s->Freq = (Byte)freq;
1503 if (freq > MAX_FREQ)
1504 Ppmd8_Rescale(p);
1505 Ppmd8_NextContext(p);
1506 }
1507
1508
1509 /*
1510 void Ppmd8_UpdateBin(CPpmd8 *p)
1511 {
1512 unsigned freq = p->FoundState->Freq;
1513 p->FoundState->Freq = (Byte)(freq + (freq < 196)); // Ppmd8 (196)
1514 p->PrevSuccess = 1;
1515 p->RunLength++;
1516 Ppmd8_NextContext(p);
1517 }
1518 */
1519
Ppmd8_Update2(CPpmd8 * p)1520 void Ppmd8_Update2(CPpmd8 *p)
1521 {
1522 CPpmd_State *s = p->FoundState;
1523 unsigned freq = s->Freq;
1524 freq += 4;
1525 p->RunLength = p->InitRL;
1526 p->MinContext->Union2.SummFreq = (UInt16)(p->MinContext->Union2.SummFreq + 4);
1527 s->Freq = (Byte)freq;
1528 if (freq > MAX_FREQ)
1529 Ppmd8_Rescale(p);
1530 Ppmd8_UpdateModel(p);
1531 }
1532
1533 /* H->I changes:
1534 NS2Indx
1535 GlueCount, and Glue method
1536 BinSum
1537 See / EscFreq
1538 Ppmd8_CreateSuccessors updates more suffix contexts
1539 Ppmd8_UpdateModel consts.
1540 PrevSuccess Update
1541
1542 Flags:
1543 (1 << 2) - the Context was Rescaled
1544 (1 << 3) - there is symbol in Stats with (sym >= 0x40) in
1545 (1 << 4) - main symbol of context is (sym >= 0x40)
1546 */
1547
1548 #undef RESET_TEXT
1549 #undef FLAG_RESCALED
1550 #undef FLAG_PREV_HIGH
1551 #undef HiBits_Prepare
1552 #undef HiBits_Convert_3
1553 #undef HiBits_Convert_4
1554 #undef PPMD8_HiBitsFlag_3
1555 #undef PPMD8_HiBitsFlag_4
1556 #undef RESTORE_MODEL
1557
1558 #undef MAX_FREQ
1559 #undef UNIT_SIZE
1560 #undef U2B
1561 #undef U2I
1562 #undef I2U
1563
1564 #undef REF
1565 #undef STATS_REF
1566 #undef CTX
1567 #undef STATS
1568 #undef ONE_STATE
1569 #undef SUFFIX
1570 #undef NODE
1571 #undef EMPTY_NODE
1572 #undef MEM_12_CPY
1573 #undef SUCCESSOR
1574 #undef SWAP_STATES
1575