1 /* Ppmd7.c -- PPMdH codec
2 2010-03-12 : Igor Pavlov : Public domain
3 This code is based on PPMd var.H (2001): Dmitry Shkarin : Public domain */
5 #include "archive_platform.h"
9 #include "archive_ppmd7_private.h"
12 #define Ppmd7_GetPtr(p, ptr) (ptr)
13 #define Ppmd7_GetContext(p, ptr) (ptr)
14 #define Ppmd7_GetStats(p, ctx) ((ctx)->Stats)
16 #define Ppmd7_GetPtr(p, offs) ((void *)((p)->Base + (offs)))
17 #define Ppmd7_GetContext(p, offs) ((CPpmd7_Context *)Ppmd7_GetPtr((p), (offs)))
18 #define Ppmd7_GetStats(p, ctx) ((CPpmd_State *)Ppmd7_GetPtr((p), ((ctx)->Stats)))
21 #define Ppmd7_GetBinSumm(p) \
22 &p->BinSumm[Ppmd7Context_OneState(p->MinContext)->Freq - 1][p->PrevSuccess + \
23 p->NS2BSIndx[Ppmd7_GetContext(p, p->MinContext->Suffix)->NumStats - 1] + \
24 (p->HiBitsFlag = p->HB2Flag[p->FoundState->Symbol]) + \
25 2 * p->HB2Flag[Ppmd7Context_OneState(p->MinContext)->Symbol] + \
26 ((p->RunLength >> 26) & 0x20)]
28 #define kTopValue (1 << 24)
32 #define U2B(nu) ((UInt32)(nu) * UNIT_SIZE)
33 #define U2I(nu) (p->Units2Indx[(nu) - 1])
34 #define I2U(indx) (p->Indx2Units[indx])
37 #define REF(ptr) (ptr)
39 #define REF(ptr) ((UInt32)((Byte *)(ptr) - (p)->Base))
42 #define STATS_REF(ptr) ((CPpmd_State_Ref)REF(ptr))
44 #define CTX(ref) ((CPpmd7_Context *)Ppmd7_GetContext(p, ref))
45 #define STATS(ctx) Ppmd7_GetStats(p, ctx)
46 #define ONE_STATE(ctx) Ppmd7Context_OneState(ctx)
47 #define SUFFIX(ctx) CTX((ctx)->Suffix)
49 static const UInt16 kInitBinEsc
[] = { 0x3CDD, 0x1F3F, 0x59BF, 0x48F3, 0x64A1, 0x5ABC, 0x6632, 0x6051};
50 static const Byte PPMD7_kExpEscape
[16] = { 25, 14, 9, 7, 5, 5, 4, 4, 4, 3, 3, 3, 2, 2, 2, 2 };
52 typedef CPpmd7_Context
* CTX_PTR
;
64 typedef struct CPpmd7_Node_
66 UInt16 Stamp
; /* must be at offset 0 as CPpmd7_Context::NumStats. Stamp=0 means free */
68 CPpmd7_Node_Ref Next
; /* must be at offset >= 4 */
73 #define NODE(ptr) (ptr)
75 #define NODE(offs) ((CPpmd7_Node *)(p->Base + (offs)))
78 static void Ppmd7_Update1(CPpmd7
*p
);
79 static void Ppmd7_Update1_0(CPpmd7
*p
);
80 static void Ppmd7_Update2(CPpmd7
*p
);
81 static void Ppmd7_UpdateBin(CPpmd7
*p
);
82 static CPpmd_See
*Ppmd7_MakeEscFreq(CPpmd7
*p
, unsigned numMasked
,
85 /* ----------- Base ----------- */
87 static void Ppmd7_Construct(CPpmd7
*p
)
93 for (i
= 0, k
= 0; i
< PPMD_NUM_INDEXES
; i
++)
95 unsigned step
= (i
>= 12 ? 4 : (i
>> 2) + 1);
96 do { p
->Units2Indx
[k
++] = (Byte
)i
; } while(--step
);
97 p
->Indx2Units
[i
] = (Byte
)k
;
100 p
->NS2BSIndx
[0] = (0 << 1);
101 p
->NS2BSIndx
[1] = (1 << 1);
102 memset(p
->NS2BSIndx
+ 2, (2 << 1), 9);
103 memset(p
->NS2BSIndx
+ 11, (3 << 1), 256 - 11);
105 for (i
= 0; i
< 3; i
++)
106 p
->NS2Indx
[i
] = (Byte
)i
;
107 for (m
= i
, k
= 1; i
< 256; i
++)
109 p
->NS2Indx
[i
] = (Byte
)m
;
114 memset(p
->HB2Flag
, 0, 0x40);
115 memset(p
->HB2Flag
+ 0x40, 8, 0x100 - 0x40);
118 static void Ppmd7_Free(CPpmd7
*p
, ISzAlloc
*alloc
)
120 alloc
->Free(alloc
, p
->Base
);
125 static Bool
Ppmd7_Alloc(CPpmd7
*p
, UInt32 size
, ISzAlloc
*alloc
)
127 if (p
->Base
== 0 || p
->Size
!= size
)
129 Ppmd7_Free(p
, alloc
);
136 if ((p
->Base
= (Byte
*)alloc
->Alloc(alloc
, p
->AlignOffset
+ size
147 static void InsertNode(CPpmd7
*p
, void *node
, unsigned indx
)
149 *((CPpmd_Void_Ref
*)node
) = p
->FreeList
[indx
];
150 p
->FreeList
[indx
] = REF(node
);
153 static void *RemoveNode(CPpmd7
*p
, unsigned indx
)
155 CPpmd_Void_Ref
*node
= (CPpmd_Void_Ref
*)Ppmd7_GetPtr(p
, p
->FreeList
[indx
]);
156 p
->FreeList
[indx
] = *node
;
160 static void SplitBlock(CPpmd7
*p
, void *ptr
, unsigned oldIndx
, unsigned newIndx
)
162 unsigned i
, nu
= I2U(oldIndx
) - I2U(newIndx
);
163 ptr
= (Byte
*)ptr
+ U2B(I2U(newIndx
));
164 if (I2U(i
= U2I(nu
)) != nu
)
166 unsigned k
= I2U(--i
);
167 InsertNode(p
, ((Byte
*)ptr
) + U2B(k
), nu
- k
- 1);
169 InsertNode(p
, ptr
, i
);
172 static void GlueFreeBlocks(CPpmd7
*p
)
175 CPpmd7_Node headItem
;
176 CPpmd7_Node_Ref head
= &headItem
;
178 CPpmd7_Node_Ref head
= p
->AlignOffset
+ p
->Size
;
181 CPpmd7_Node_Ref n
= head
;
186 /* create doubly-linked list of free blocks */
187 for (i
= 0; i
< PPMD_NUM_INDEXES
; i
++)
190 CPpmd7_Node_Ref next
= (CPpmd7_Node_Ref
)p
->FreeList
[i
];
194 CPpmd7_Node
*node
= NODE(next
);
196 n
= NODE(n
)->Prev
= next
;
197 next
= *(const CPpmd7_Node_Ref
*)node
;
199 node
->NU
= (UInt16
)nu
;
202 NODE(head
)->Stamp
= 1;
203 NODE(head
)->Next
= n
;
204 NODE(n
)->Prev
= head
;
205 if (p
->LoUnit
!= p
->HiUnit
)
206 ((CPpmd7_Node
*)p
->LoUnit
)->Stamp
= 1;
208 /* Glue free blocks */
211 CPpmd7_Node
*node
= NODE(n
);
212 UInt32 nu
= (UInt32
)node
->NU
;
215 CPpmd7_Node
*node2
= NODE(n
) + nu
;
217 if (node2
->Stamp
!= 0 || nu
>= 0x10000)
219 NODE(node2
->Prev
)->Next
= node2
->Next
;
220 NODE(node2
->Next
)->Prev
= node2
->Prev
;
221 node
->NU
= (UInt16
)nu
;
226 /* Fill lists of free blocks */
227 for (n
= NODE(head
)->Next
; n
!= head
;)
229 CPpmd7_Node
*node
= NODE(n
);
231 CPpmd7_Node_Ref next
= node
->Next
;
232 for (nu
= node
->NU
; nu
> 128; nu
-= 128, node
+= 128)
233 InsertNode(p
, node
, PPMD_NUM_INDEXES
- 1);
234 if (I2U(i
= U2I(nu
)) != nu
)
236 unsigned k
= I2U(--i
);
237 InsertNode(p
, node
+ k
, nu
- k
- 1);
239 InsertNode(p
, node
, i
);
244 static void *AllocUnitsRare(CPpmd7
*p
, unsigned indx
)
248 if (p
->GlueCount
== 0)
251 if (p
->FreeList
[indx
] != 0)
252 return RemoveNode(p
, indx
);
257 if (++i
== PPMD_NUM_INDEXES
)
259 UInt32 numBytes
= U2B(I2U(indx
));
261 return ((UInt32
)(p
->UnitsStart
- p
->Text
) > numBytes
) ? (p
->UnitsStart
-= numBytes
) : (NULL
);
264 while (p
->FreeList
[i
] == 0);
265 retVal
= RemoveNode(p
, i
);
266 SplitBlock(p
, retVal
, i
, indx
);
270 static void *AllocUnits(CPpmd7
*p
, unsigned indx
)
273 if (p
->FreeList
[indx
] != 0)
274 return RemoveNode(p
, indx
);
275 numBytes
= U2B(I2U(indx
));
276 if (numBytes
<= (UInt32
)(p
->HiUnit
- p
->LoUnit
))
278 void *retVal
= p
->LoUnit
;
279 p
->LoUnit
+= numBytes
;
282 return AllocUnitsRare(p
, indx
);
285 #define MyMem12Cpy(dest, src, num) \
286 { UInt32 *d = (UInt32 *)dest; const UInt32 *s = (const UInt32 *)src; UInt32 n = num; \
287 do { d[0] = s[0]; d[1] = s[1]; d[2] = s[2]; s += 3; d += 3; } while(--n); }
289 static void *ShrinkUnits(CPpmd7
*p
, void *oldPtr
, unsigned oldNU
, unsigned newNU
)
291 unsigned i0
= U2I(oldNU
);
292 unsigned i1
= U2I(newNU
);
295 if (p
->FreeList
[i1
] != 0)
297 void *ptr
= RemoveNode(p
, i1
);
298 MyMem12Cpy(ptr
, oldPtr
, newNU
);
299 InsertNode(p
, oldPtr
, i0
);
302 SplitBlock(p
, oldPtr
, i0
, i1
);
306 #define SUCCESSOR(p) ((CPpmd_Void_Ref)((p)->SuccessorLow | ((UInt32)(p)->SuccessorHigh << 16)))
308 static void SetSuccessor(CPpmd_State
*p
, CPpmd_Void_Ref v
)
310 (p
)->SuccessorLow
= (UInt16
)((UInt32
)(v
) & 0xFFFF);
311 (p
)->SuccessorHigh
= (UInt16
)(((UInt32
)(v
) >> 16) & 0xFFFF);
314 static void RestartModel(CPpmd7
*p
)
318 memset(p
->FreeList
, 0, sizeof(p
->FreeList
));
319 p
->Text
= p
->Base
+ p
->AlignOffset
;
320 p
->HiUnit
= p
->Text
+ p
->Size
;
321 p
->LoUnit
= p
->UnitsStart
= p
->HiUnit
- p
->Size
/ 8 / UNIT_SIZE
* 7 * UNIT_SIZE
;
324 p
->OrderFall
= p
->MaxOrder
;
325 p
->RunLength
= p
->InitRL
= -(Int32
)((p
->MaxOrder
< 12) ? p
->MaxOrder
: 12) - 1;
328 p
->MinContext
= p
->MaxContext
= (CTX_PTR
)(p
->HiUnit
-= UNIT_SIZE
); /* AllocContext(p); */
329 p
->MinContext
->Suffix
= 0;
330 p
->MinContext
->NumStats
= 256;
331 p
->MinContext
->SummFreq
= 256 + 1;
332 p
->FoundState
= (CPpmd_State
*)p
->LoUnit
; /* AllocUnits(p, PPMD_NUM_INDEXES - 1); */
333 p
->LoUnit
+= U2B(256 / 2);
334 p
->MinContext
->Stats
= REF(p
->FoundState
);
335 for (i
= 0; i
< 256; i
++)
337 CPpmd_State
*s
= &p
->FoundState
[i
];
343 for (i
= 0; i
< 128; i
++)
344 for (k
= 0; k
< 8; k
++)
346 UInt16
*dest
= p
->BinSumm
[i
] + k
;
347 UInt16 val
= (UInt16
)(PPMD_BIN_SCALE
- kInitBinEsc
[k
] / (i
+ 2));
348 for (m
= 0; m
< 64; m
+= 8)
352 for (i
= 0; i
< 25; i
++)
353 for (k
= 0; k
< 16; k
++)
355 CPpmd_See
*s
= &p
->See
[i
][k
];
356 s
->Summ
= (UInt16
)((5 * i
+ 10) << (s
->Shift
= PPMD_PERIOD_BITS
- 4));
361 static void Ppmd7_Init(CPpmd7
*p
, unsigned maxOrder
)
363 p
->MaxOrder
= maxOrder
;
365 p
->DummySee
.Shift
= PPMD_PERIOD_BITS
;
366 p
->DummySee
.Summ
= 0; /* unused */
367 p
->DummySee
.Count
= 64; /* unused */
370 static CTX_PTR
CreateSuccessors(CPpmd7
*p
, Bool skip
)
373 CTX_PTR c
= p
->MinContext
;
374 CPpmd_Byte_Ref upBranch
= (CPpmd_Byte_Ref
)SUCCESSOR(p
->FoundState
);
375 CPpmd_State
*ps
[PPMD7_MAX_ORDER
];
379 ps
[numPs
++] = p
->FoundState
;
383 CPpmd_Void_Ref successor
;
386 if (c
->NumStats
!= 1)
388 for (s
= STATS(c
); s
->Symbol
!= p
->FoundState
->Symbol
; s
++);
392 successor
= SUCCESSOR(s
);
393 if (successor
!= upBranch
)
403 upState
.Symbol
= *(const Byte
*)Ppmd7_GetPtr(p
, upBranch
);
404 SetSuccessor(&upState
, upBranch
+ 1);
406 if (c
->NumStats
== 1)
407 upState
.Freq
= ONE_STATE(c
)->Freq
;
412 for (s
= STATS(c
); s
->Symbol
!= upState
.Symbol
; s
++);
414 s0
= c
->SummFreq
- c
->NumStats
- cf
;
415 upState
.Freq
= (Byte
)(1 + ((2 * cf
<= s0
) ? (5 * cf
> s0
) : ((2 * cf
+ 3 * s0
- 1) / (2 * s0
))));
421 CTX_PTR c1
; /* = AllocContext(p); */
422 if (p
->HiUnit
!= p
->LoUnit
)
423 c1
= (CTX_PTR
)(p
->HiUnit
-= UNIT_SIZE
);
424 else if (p
->FreeList
[0] != 0)
425 c1
= (CTX_PTR
)RemoveNode(p
, 0);
428 c1
= (CTX_PTR
)AllocUnitsRare(p
, 0);
433 *ONE_STATE(c1
) = upState
;
435 SetSuccessor(ps
[--numPs
], REF(c1
));
442 static void SwapStates(CPpmd_State
*t1
, CPpmd_State
*t2
)
444 CPpmd_State tmp
= *t1
;
449 static void UpdateModel(CPpmd7
*p
)
451 CPpmd_Void_Ref successor
, fSuccessor
= SUCCESSOR(p
->FoundState
);
455 if (p
->FoundState
->Freq
< MAX_FREQ
/ 4 && p
->MinContext
->Suffix
!= 0)
457 c
= SUFFIX(p
->MinContext
);
459 if (c
->NumStats
== 1)
461 CPpmd_State
*s
= ONE_STATE(c
);
467 CPpmd_State
*s
= STATS(c
);
468 if (s
->Symbol
!= p
->FoundState
->Symbol
)
470 do { s
++; } while (s
->Symbol
!= p
->FoundState
->Symbol
);
471 if (s
[0].Freq
>= s
[-1].Freq
)
473 SwapStates(&s
[0], &s
[-1]);
477 if (s
->Freq
< MAX_FREQ
- 9)
485 if (p
->OrderFall
== 0)
487 p
->MinContext
= p
->MaxContext
= CreateSuccessors(p
, True
);
488 if (p
->MinContext
== 0)
493 SetSuccessor(p
->FoundState
, REF(p
->MinContext
));
497 *p
->Text
++ = p
->FoundState
->Symbol
;
498 successor
= REF(p
->Text
);
499 if (p
->Text
>= p
->UnitsStart
)
507 if (fSuccessor
<= successor
)
509 CTX_PTR cs
= CreateSuccessors(p
, False
);
515 fSuccessor
= REF(cs
);
517 if (--p
->OrderFall
== 0)
519 successor
= fSuccessor
;
520 p
->Text
-= (p
->MaxContext
!= p
->MinContext
);
525 SetSuccessor(p
->FoundState
, successor
);
526 fSuccessor
= REF(p
->MinContext
);
529 s0
= p
->MinContext
->SummFreq
- (ns
= p
->MinContext
->NumStats
) - (p
->FoundState
->Freq
- 1);
531 for (c
= p
->MaxContext
; c
!= p
->MinContext
; c
= SUFFIX(c
))
535 if ((ns1
= c
->NumStats
) != 1)
539 /* Expand for one UNIT */
540 unsigned oldNU
= ns1
>> 1;
541 unsigned i
= U2I(oldNU
);
542 if (i
!= U2I(oldNU
+ 1))
544 void *ptr
= AllocUnits(p
, i
+ 1);
552 MyMem12Cpy(ptr
, oldPtr
, oldNU
);
553 InsertNode(p
, oldPtr
, i
);
554 c
->Stats
= STATS_REF(ptr
);
557 c
->SummFreq
= (UInt16
)(c
->SummFreq
+ (2 * ns1
< ns
) + 2 * ((4 * ns1
<= ns
) & (c
->SummFreq
<= 8 * ns1
)));
561 CPpmd_State
*s
= (CPpmd_State
*)AllocUnits(p
, 0);
569 if (s
->Freq
< MAX_FREQ
/ 4 - 1)
572 s
->Freq
= MAX_FREQ
- 4;
573 c
->SummFreq
= (UInt16
)(s
->Freq
+ p
->InitEsc
+ (ns
> 3));
575 cf
= 2 * (UInt32
)p
->FoundState
->Freq
* (c
->SummFreq
+ 6);
576 sf
= (UInt32
)s0
+ c
->SummFreq
;
579 cf
= 1 + (cf
> sf
) + (cf
>= 4 * sf
);
584 cf
= 4 + (cf
>= 9 * sf
) + (cf
>= 12 * sf
) + (cf
>= 15 * sf
);
585 c
->SummFreq
= (UInt16
)(c
->SummFreq
+ cf
);
588 CPpmd_State
*s
= STATS(c
) + ns1
;
589 SetSuccessor(s
, successor
);
590 s
->Symbol
= p
->FoundState
->Symbol
;
592 c
->NumStats
= (UInt16
)(ns1
+ 1);
595 p
->MaxContext
= p
->MinContext
= CTX(fSuccessor
);
598 static void Rescale(CPpmd7
*p
)
600 unsigned i
, adder
, sumFreq
, escFreq
;
601 CPpmd_State
*stats
= STATS(p
->MinContext
);
602 CPpmd_State
*s
= p
->FoundState
;
604 CPpmd_State tmp
= *s
;
605 for (; s
!= stats
; s
--)
609 escFreq
= p
->MinContext
->SummFreq
- s
->Freq
;
611 adder
= (p
->OrderFall
!= 0);
612 s
->Freq
= (Byte
)((s
->Freq
+ adder
) >> 1);
615 i
= p
->MinContext
->NumStats
- 1;
618 escFreq
-= (++s
)->Freq
;
619 s
->Freq
= (Byte
)((s
->Freq
+ adder
) >> 1);
621 if (s
[0].Freq
> s
[-1].Freq
)
624 CPpmd_State tmp
= *s1
;
627 while (--s1
!= stats
&& tmp
.Freq
> s1
[-1].Freq
);
635 unsigned numStats
= p
->MinContext
->NumStats
;
637 do { i
++; } while ((--s
)->Freq
== 0);
639 p
->MinContext
->NumStats
= (UInt16
)(p
->MinContext
->NumStats
- i
);
640 if (p
->MinContext
->NumStats
== 1)
642 CPpmd_State tmp
= *stats
;
645 tmp
.Freq
= (Byte
)(tmp
.Freq
- (tmp
.Freq
>> 1));
649 InsertNode(p
, stats
, U2I(((numStats
+ 1) >> 1)));
650 *(p
->FoundState
= ONE_STATE(p
->MinContext
)) = tmp
;
653 n0
= (numStats
+ 1) >> 1;
654 n1
= (p
->MinContext
->NumStats
+ 1) >> 1;
656 p
->MinContext
->Stats
= STATS_REF(ShrinkUnits(p
, stats
, n0
, n1
));
658 p
->MinContext
->SummFreq
= (UInt16
)(sumFreq
+ escFreq
- (escFreq
>> 1));
659 p
->FoundState
= STATS(p
->MinContext
);
662 static CPpmd_See
*Ppmd7_MakeEscFreq(CPpmd7
*p
, unsigned numMasked
, UInt32
*escFreq
)
665 unsigned nonMasked
= p
->MinContext
->NumStats
- numMasked
;
666 if (p
->MinContext
->NumStats
!= 256)
668 see
= p
->See
[p
->NS2Indx
[nonMasked
- 1]] +
669 (nonMasked
< (unsigned)SUFFIX(p
->MinContext
)->NumStats
- p
->MinContext
->NumStats
) +
670 2 * (p
->MinContext
->SummFreq
< 11 * p
->MinContext
->NumStats
) +
671 4 * (numMasked
> nonMasked
) +
674 unsigned r
= (see
->Summ
>> see
->Shift
);
675 see
->Summ
= (UInt16
)(see
->Summ
- r
);
676 *escFreq
= r
+ (r
== 0);
687 static void NextContext(CPpmd7
*p
)
689 CTX_PTR c
= CTX(SUCCESSOR(p
->FoundState
));
690 if (p
->OrderFall
== 0 && (Byte
*)c
> p
->Text
)
691 p
->MinContext
= p
->MaxContext
= c
;
696 static void Ppmd7_Update1(CPpmd7
*p
)
698 CPpmd_State
*s
= p
->FoundState
;
700 p
->MinContext
->SummFreq
+= 4;
701 if (s
[0].Freq
> s
[-1].Freq
)
703 SwapStates(&s
[0], &s
[-1]);
705 if (s
->Freq
> MAX_FREQ
)
711 static void Ppmd7_Update1_0(CPpmd7
*p
)
713 p
->PrevSuccess
= (2 * p
->FoundState
->Freq
> p
->MinContext
->SummFreq
);
714 p
->RunLength
+= p
->PrevSuccess
;
715 p
->MinContext
->SummFreq
+= 4;
716 if ((p
->FoundState
->Freq
+= 4) > MAX_FREQ
)
721 static void Ppmd7_UpdateBin(CPpmd7
*p
)
723 p
->FoundState
->Freq
= (Byte
)(p
->FoundState
->Freq
+ (p
->FoundState
->Freq
< 128 ? 1: 0));
729 static void Ppmd7_Update2(CPpmd7
*p
)
731 p
->MinContext
->SummFreq
+= 4;
732 if ((p
->FoundState
->Freq
+= 4) > MAX_FREQ
)
734 p
->RunLength
= p
->InitRL
;
738 /* ---------- Decode ---------- */
740 static Bool
Ppmd_RangeDec_Init(CPpmd7z_RangeDec
*p
)
743 p
->Low
= p
->Bottom
= 0;
744 p
->Range
= 0xFFFFFFFF;
745 for (i
= 0; i
< 4; i
++)
746 p
->Code
= (p
->Code
<< 8) | p
->Stream
->Read((void *)p
->Stream
);
747 return (p
->Code
< 0xFFFFFFFF);
750 static Bool
Ppmd7z_RangeDec_Init(CPpmd7z_RangeDec
*p
)
752 if (p
->Stream
->Read((void *)p
->Stream
) != 0)
754 return Ppmd_RangeDec_Init(p
);
757 static Bool
PpmdRAR_RangeDec_Init(CPpmd7z_RangeDec
*p
)
759 if (!Ppmd_RangeDec_Init(p
))
765 static UInt32
Range_GetThreshold(void *pp
, UInt32 total
)
767 CPpmd7z_RangeDec
*p
= (CPpmd7z_RangeDec
*)pp
;
768 return (p
->Code
- p
->Low
) / (p
->Range
/= total
);
771 static void Range_Normalize(CPpmd7z_RangeDec
*p
)
775 if((p
->Low
^ (p
->Low
+ p
->Range
)) >= kTopValue
)
777 if(p
->Range
>= p
->Bottom
)
780 p
->Range
= ((uint32_t)(-(int32_t)p
->Low
)) & (p
->Bottom
- 1);
782 p
->Code
= (p
->Code
<< 8) | p
->Stream
->Read((void *)p
->Stream
);
788 static void Range_Decode_7z(void *pp
, UInt32 start
, UInt32 size
)
790 CPpmd7z_RangeDec
*p
= (CPpmd7z_RangeDec
*)pp
;
791 p
->Code
-= start
* p
->Range
;
796 static void Range_Decode_RAR(void *pp
, UInt32 start
, UInt32 size
)
798 CPpmd7z_RangeDec
*p
= (CPpmd7z_RangeDec
*)pp
;
799 p
->Low
+= start
* p
->Range
;
804 static UInt32
Range_DecodeBit_7z(void *pp
, UInt32 size0
)
806 CPpmd7z_RangeDec
*p
= (CPpmd7z_RangeDec
*)pp
;
807 UInt32 newBound
= (p
->Range
>> 14) * size0
;
809 if (p
->Code
< newBound
)
818 p
->Range
-= newBound
;
824 static UInt32
Range_DecodeBit_RAR(void *pp
, UInt32 size0
)
826 CPpmd7z_RangeDec
*p
= (CPpmd7z_RangeDec
*)pp
;
827 UInt32 bit
, value
= p
->p
.GetThreshold(p
, PPMD_BIN_SCALE
);
831 p
->p
.Decode(p
, 0, size0
);
836 p
->p
.Decode(p
, size0
, PPMD_BIN_SCALE
- size0
);
841 static void Ppmd7z_RangeDec_CreateVTable(CPpmd7z_RangeDec
*p
)
843 p
->p
.GetThreshold
= Range_GetThreshold
;
844 p
->p
.Decode
= Range_Decode_7z
;
845 p
->p
.DecodeBit
= Range_DecodeBit_7z
;
848 static void PpmdRAR_RangeDec_CreateVTable(CPpmd7z_RangeDec
*p
)
850 p
->p
.GetThreshold
= Range_GetThreshold
;
851 p
->p
.Decode
= Range_Decode_RAR
;
852 p
->p
.DecodeBit
= Range_DecodeBit_RAR
;
855 #define MASK(sym) ((signed char *)charMask)[sym]
857 static int Ppmd7_DecodeSymbol(CPpmd7
*p
, IPpmd7_RangeDec
*rc
)
859 size_t charMask
[256 / sizeof(size_t)];
860 if (p
->MinContext
->NumStats
!= 1)
862 CPpmd_State
*s
= Ppmd7_GetStats(p
, p
->MinContext
);
865 if ((count
= rc
->GetThreshold(rc
, p
->MinContext
->SummFreq
)) < (hiCnt
= s
->Freq
))
868 rc
->Decode(rc
, 0, s
->Freq
);
875 i
= p
->MinContext
->NumStats
- 1;
878 if ((hiCnt
+= (++s
)->Freq
) > count
)
881 rc
->Decode(rc
, hiCnt
- s
->Freq
, s
->Freq
);
889 if (count
>= p
->MinContext
->SummFreq
)
891 p
->HiBitsFlag
= p
->HB2Flag
[p
->FoundState
->Symbol
];
892 rc
->Decode(rc
, hiCnt
, p
->MinContext
->SummFreq
- hiCnt
);
893 PPMD_SetAllBitsIn256Bytes(charMask
);
895 i
= p
->MinContext
->NumStats
- 1;
896 do { MASK((--s
)->Symbol
) = 0; } while (--i
);
900 UInt16
*prob
= Ppmd7_GetBinSumm(p
);
901 if (rc
->DecodeBit(rc
, *prob
) == 0)
904 *prob
= (UInt16
)PPMD_UPDATE_PROB_0(*prob
);
905 symbol
= (p
->FoundState
= Ppmd7Context_OneState(p
->MinContext
))->Symbol
;
909 *prob
= (UInt16
)PPMD_UPDATE_PROB_1(*prob
);
910 p
->InitEsc
= PPMD7_kExpEscape
[*prob
>> 10];
911 PPMD_SetAllBitsIn256Bytes(charMask
);
912 MASK(Ppmd7Context_OneState(p
->MinContext
)->Symbol
) = 0;
917 CPpmd_State
*ps
[256], *s
;
918 UInt32 freqSum
, count
, hiCnt
;
920 unsigned i
, num
, numMasked
= p
->MinContext
->NumStats
;
924 if (!p
->MinContext
->Suffix
)
926 p
->MinContext
= Ppmd7_GetContext(p
, p
->MinContext
->Suffix
);
928 while (p
->MinContext
->NumStats
== numMasked
);
930 s
= Ppmd7_GetStats(p
, p
->MinContext
);
932 num
= p
->MinContext
->NumStats
- numMasked
;
935 int k
= (int)(MASK(s
->Symbol
));
936 hiCnt
+= (s
->Freq
& k
);
942 see
= Ppmd7_MakeEscFreq(p
, numMasked
, &freqSum
);
944 count
= rc
->GetThreshold(rc
, freqSum
);
949 CPpmd_State
**pps
= ps
;
950 for (hiCnt
= 0; (hiCnt
+= (*pps
)->Freq
) <= count
; pps
++);
952 rc
->Decode(rc
, hiCnt
- s
->Freq
, s
->Freq
);
953 Ppmd_See_Update(see
);
959 if (count
>= freqSum
)
961 rc
->Decode(rc
, hiCnt
, freqSum
- hiCnt
);
962 see
->Summ
= (UInt16
)(see
->Summ
+ freqSum
);
963 do { MASK(ps
[--i
]->Symbol
) = 0; } while (i
!= 0);
967 /* ---------- Encode ---------- Ppmd7Enc.c */
969 #define kTopValue (1 << 24)
971 static void Ppmd7z_RangeEnc_Init(CPpmd7z_RangeEnc
*p
)
974 p
->Range
= 0xFFFFFFFF;
979 static void RangeEnc_ShiftLow(CPpmd7z_RangeEnc
*p
)
981 if ((UInt32
)p
->Low
< (UInt32
)0xFF000000 || (unsigned)(p
->Low
>> 32) != 0)
983 Byte temp
= p
->Cache
;
986 p
->Stream
->Write(p
->Stream
, (Byte
)(temp
+ (Byte
)(p
->Low
>> 32)));
989 while(--p
->CacheSize
!= 0);
990 p
->Cache
= (Byte
)((UInt32
)p
->Low
>> 24);
993 p
->Low
= ((UInt32
)p
->Low
<< 8) & 0xFFFFFFFF;
996 static void RangeEnc_Encode(CPpmd7z_RangeEnc
*p
, UInt32 start
, UInt32 size
, UInt32 total
)
998 p
->Low
+= start
* (p
->Range
/= total
);
1000 while (p
->Range
< kTopValue
)
1003 RangeEnc_ShiftLow(p
);
1007 static void RangeEnc_EncodeBit_0(CPpmd7z_RangeEnc
*p
, UInt32 size0
)
1009 p
->Range
= (p
->Range
>> 14) * size0
;
1010 while (p
->Range
< kTopValue
)
1013 RangeEnc_ShiftLow(p
);
1017 static void RangeEnc_EncodeBit_1(CPpmd7z_RangeEnc
*p
, UInt32 size0
)
1019 UInt32 newBound
= (p
->Range
>> 14) * size0
;
1021 p
->Range
-= newBound
;
1022 while (p
->Range
< kTopValue
)
1025 RangeEnc_ShiftLow(p
);
1029 static void Ppmd7z_RangeEnc_FlushData(CPpmd7z_RangeEnc
*p
)
1032 for (i
= 0; i
< 5; i
++)
1033 RangeEnc_ShiftLow(p
);
1037 #define MASK(sym) ((signed char *)charMask)[sym]
1039 static void Ppmd7_EncodeSymbol(CPpmd7
*p
, CPpmd7z_RangeEnc
*rc
, int symbol
)
1041 size_t charMask
[256 / sizeof(size_t)];
1042 if (p
->MinContext
->NumStats
!= 1)
1044 CPpmd_State
*s
= Ppmd7_GetStats(p
, p
->MinContext
);
1047 if (s
->Symbol
== symbol
)
1049 RangeEnc_Encode(rc
, 0, s
->Freq
, p
->MinContext
->SummFreq
);
1056 i
= p
->MinContext
->NumStats
- 1;
1059 if ((++s
)->Symbol
== symbol
)
1061 RangeEnc_Encode(rc
, sum
, s
->Freq
, p
->MinContext
->SummFreq
);
1070 p
->HiBitsFlag
= p
->HB2Flag
[p
->FoundState
->Symbol
];
1071 PPMD_SetAllBitsIn256Bytes(charMask
);
1072 MASK(s
->Symbol
) = 0;
1073 i
= p
->MinContext
->NumStats
- 1;
1074 do { MASK((--s
)->Symbol
) = 0; } while (--i
);
1075 RangeEnc_Encode(rc
, sum
, p
->MinContext
->SummFreq
- sum
, p
->MinContext
->SummFreq
);
1079 UInt16
*prob
= Ppmd7_GetBinSumm(p
);
1080 CPpmd_State
*s
= Ppmd7Context_OneState(p
->MinContext
);
1081 if (s
->Symbol
== symbol
)
1083 RangeEnc_EncodeBit_0(rc
, *prob
);
1084 *prob
= (UInt16
)PPMD_UPDATE_PROB_0(*prob
);
1091 RangeEnc_EncodeBit_1(rc
, *prob
);
1092 *prob
= (UInt16
)PPMD_UPDATE_PROB_1(*prob
);
1093 p
->InitEsc
= PPMD7_kExpEscape
[*prob
>> 10];
1094 PPMD_SetAllBitsIn256Bytes(charMask
);
1095 MASK(s
->Symbol
) = 0;
1105 unsigned i
, numMasked
= p
->MinContext
->NumStats
;
1109 if (!p
->MinContext
->Suffix
)
1110 return; /* EndMarker (symbol = -1) */
1111 p
->MinContext
= Ppmd7_GetContext(p
, p
->MinContext
->Suffix
);
1113 while (p
->MinContext
->NumStats
== numMasked
);
1115 see
= Ppmd7_MakeEscFreq(p
, numMasked
, &escFreq
);
1116 s
= Ppmd7_GetStats(p
, p
->MinContext
);
1118 i
= p
->MinContext
->NumStats
;
1121 int cur
= s
->Symbol
;
1125 CPpmd_State
*s1
= s
;
1128 sum
+= (s
->Freq
& (int)(MASK(s
->Symbol
)));
1132 RangeEnc_Encode(rc
, low
, s1
->Freq
, sum
+ escFreq
);
1133 Ppmd_See_Update(see
);
1138 sum
+= (s
->Freq
& (int)(MASK(cur
)));
1144 RangeEnc_Encode(rc
, sum
, escFreq
, sum
+ escFreq
);
1145 see
->Summ
= (UInt16
)(see
->Summ
+ sum
+ escFreq
);
1149 const IPpmd7 __archive_ppmd7_functions
=
1155 &Ppmd7z_RangeDec_CreateVTable
,
1156 &PpmdRAR_RangeDec_CreateVTable
,
1157 &Ppmd7z_RangeDec_Init
,
1158 &PpmdRAR_RangeDec_Init
,
1159 &Ppmd7_DecodeSymbol
,
1160 &Ppmd7z_RangeEnc_Init
,
1161 &Ppmd7z_RangeEnc_FlushData
,