summaryrefslogtreecommitdiffstatshomepage
path: root/3rdparty/lzma/C/Ppmd7.c
diff options
context:
space:
mode:
Diffstat (limited to '3rdparty/lzma/C/Ppmd7.c')
-rw-r--r--3rdparty/lzma/C/Ppmd7.c1000
1 files changed, 706 insertions, 294 deletions
diff --git a/3rdparty/lzma/C/Ppmd7.c b/3rdparty/lzma/C/Ppmd7.c
index eda8eb70a22..6e1307e2d39 100644
--- a/3rdparty/lzma/C/Ppmd7.c
+++ b/3rdparty/lzma/C/Ppmd7.c
@@ -1,5 +1,5 @@
/* Ppmd7.c -- PPMdH codec
-2016-05-21 : Igor Pavlov : Public domain
+2023-04-02 : Igor Pavlov : Public domain
This code is based on PPMd var.H (2001): Dmitry Shkarin : Public domain */
#include "Precomp.h"
@@ -8,21 +8,23 @@ This code is based on PPMd var.H (2001): Dmitry Shkarin : Public domain */
#include "Ppmd7.h"
-const Byte PPMD7_kExpEscape[16] = { 25, 14, 9, 7, 5, 5, 4, 4, 4, 3, 3, 3, 2, 2, 2, 2 };
-static const UInt16 kInitBinEsc[] = { 0x3CDD, 0x1F3F, 0x59BF, 0x48F3, 0x64A1, 0x5ABC, 0x6632, 0x6051};
+/* define PPMD7_ORDER_0_SUPPPORT to suport order-0 mode, unsupported by orignal PPMd var.H. code */
+// #define PPMD7_ORDER_0_SUPPPORT
+
+MY_ALIGN(16)
+static const Byte PPMD7_kExpEscape[16] = { 25, 14, 9, 7, 5, 5, 4, 4, 4, 3, 3, 3, 2, 2, 2, 2 };
+MY_ALIGN(16)
+static const UInt16 PPMD7_kInitBinEsc[] = { 0x3CDD, 0x1F3F, 0x59BF, 0x48F3, 0x64A1, 0x5ABC, 0x6632, 0x6051};
#define MAX_FREQ 124
#define UNIT_SIZE 12
#define U2B(nu) ((UInt32)(nu) * UNIT_SIZE)
-#define U2I(nu) (p->Units2Indx[(nu) - 1])
-#define I2U(indx) (p->Indx2Units[indx])
+#define U2I(nu) (p->Units2Indx[(size_t)(nu) - 1])
+#define I2U(indx) ((unsigned)p->Indx2Units[indx])
+#define I2U_UInt16(indx) ((UInt16)p->Indx2Units[indx])
-#ifdef PPMD_32BIT
- #define REF(ptr) (ptr)
-#else
- #define REF(ptr) ((UInt32)((Byte *)(ptr) - (p)->Base))
-#endif
+#define REF(ptr) Ppmd_GetRef(p, ptr)
#define STATS_REF(ptr) ((CPpmd_State_Ref)REF(ptr))
@@ -31,17 +33,11 @@ static const UInt16 kInitBinEsc[] = { 0x3CDD, 0x1F3F, 0x59BF, 0x48F3, 0x64A1, 0x
#define ONE_STATE(ctx) Ppmd7Context_OneState(ctx)
#define SUFFIX(ctx) CTX((ctx)->Suffix)
-typedef CPpmd7_Context * CTX_PTR;
+typedef CPpmd7_Context * PPMD7_CTX_PTR;
struct CPpmd7_Node_;
-typedef
- #ifdef PPMD_32BIT
- struct CPpmd7_Node_ *
- #else
- UInt32
- #endif
- CPpmd7_Node_Ref;
+typedef Ppmd_Ref_Type(struct CPpmd7_Node_) CPpmd7_Node_Ref;
typedef struct CPpmd7_Node_
{
@@ -51,17 +47,13 @@ typedef struct CPpmd7_Node_
CPpmd7_Node_Ref Prev;
} CPpmd7_Node;
-#ifdef PPMD_32BIT
- #define NODE(ptr) (ptr)
-#else
- #define NODE(offs) ((CPpmd7_Node *)(p->Base + (offs)))
-#endif
+#define NODE(r) Ppmd_GetPtr_Type(p, r, CPpmd7_Node)
void Ppmd7_Construct(CPpmd7 *p)
{
unsigned i, k, m;
- p->Base = 0;
+ p->Base = NULL;
for (i = 0, k = 0; i < PPMD_NUM_INDEXES; i++)
{
@@ -77,6 +69,7 @@ void Ppmd7_Construct(CPpmd7 *p)
for (i = 0; i < 3; i++)
p->NS2Indx[i] = (Byte)i;
+
for (m = i, k = 1; i < 256; i++)
{
p->NS2Indx[i] = (Byte)m;
@@ -84,181 +77,236 @@ void Ppmd7_Construct(CPpmd7 *p)
k = (++m) - 2;
}
- memset(p->HB2Flag, 0, 0x40);
- memset(p->HB2Flag + 0x40, 8, 0x100 - 0x40);
+ memcpy(p->ExpEscape, PPMD7_kExpEscape, 16);
}
-void Ppmd7_Free(CPpmd7 *p, ISzAlloc *alloc)
+
+void Ppmd7_Free(CPpmd7 *p, ISzAllocPtr alloc)
{
- alloc->Free(alloc, p->Base);
+ ISzAlloc_Free(alloc, p->Base);
p->Size = 0;
- p->Base = 0;
+ p->Base = NULL;
}
-Bool Ppmd7_Alloc(CPpmd7 *p, UInt32 size, ISzAlloc *alloc)
+
+BoolInt Ppmd7_Alloc(CPpmd7 *p, UInt32 size, ISzAllocPtr alloc)
{
- if (p->Base == 0 || p->Size != size)
+ if (!p->Base || p->Size != size)
{
Ppmd7_Free(p, alloc);
- p->AlignOffset =
- #ifdef PPMD_32BIT
- (4 - size) & 3;
- #else
- 4 - (size & 3);
- #endif
- if ((p->Base = (Byte *)alloc->Alloc(alloc, p->AlignOffset + size
- #ifndef PPMD_32BIT
- + UNIT_SIZE
- #endif
- )) == 0)
+ p->AlignOffset = (4 - size) & 3;
+ if ((p->Base = (Byte *)ISzAlloc_Alloc(alloc, p->AlignOffset + size)) == NULL)
return False;
p->Size = size;
}
return True;
}
-static void InsertNode(CPpmd7 *p, void *node, unsigned indx)
+
+
+// ---------- Internal Memory Allocator ----------
+
+/* We can use CPpmd7_Node in list of free units (as in Ppmd8)
+ But we still need one additional list walk pass in Ppmd7_GlueFreeBlocks().
+ So we use simple CPpmd_Void_Ref instead of CPpmd7_Node in Ppmd7_InsertNode() / Ppmd7_RemoveNode()
+*/
+
+#define EMPTY_NODE 0
+
+
+static void Ppmd7_InsertNode(CPpmd7 *p, void *node, unsigned indx)
{
*((CPpmd_Void_Ref *)node) = p->FreeList[indx];
+ // ((CPpmd7_Node *)node)->Next = (CPpmd7_Node_Ref)p->FreeList[indx];
+
p->FreeList[indx] = REF(node);
+
}
-static void *RemoveNode(CPpmd7 *p, unsigned indx)
+
+static void *Ppmd7_RemoveNode(CPpmd7 *p, unsigned indx)
{
CPpmd_Void_Ref *node = (CPpmd_Void_Ref *)Ppmd7_GetPtr(p, p->FreeList[indx]);
p->FreeList[indx] = *node;
+ // CPpmd7_Node *node = NODE((CPpmd7_Node_Ref)p->FreeList[indx]);
+ // p->FreeList[indx] = node->Next;
return node;
}
-static void SplitBlock(CPpmd7 *p, void *ptr, unsigned oldIndx, unsigned newIndx)
+
+static void Ppmd7_SplitBlock(CPpmd7 *p, void *ptr, unsigned oldIndx, unsigned newIndx)
{
unsigned i, nu = I2U(oldIndx) - I2U(newIndx);
ptr = (Byte *)ptr + U2B(I2U(newIndx));
if (I2U(i = U2I(nu)) != nu)
{
unsigned k = I2U(--i);
- InsertNode(p, ((Byte *)ptr) + U2B(k), nu - k - 1);
+ Ppmd7_InsertNode(p, ((Byte *)ptr) + U2B(k), nu - k - 1);
}
- InsertNode(p, ptr, i);
+ Ppmd7_InsertNode(p, ptr, i);
}
-static void GlueFreeBlocks(CPpmd7 *p)
+
+/* we use CPpmd7_Node_Union union to solve XLC -O2 strict pointer aliasing problem */
+
+typedef union
{
- #ifdef PPMD_32BIT
- CPpmd7_Node headItem;
- CPpmd7_Node_Ref head = &headItem;
- #else
- CPpmd7_Node_Ref head = p->AlignOffset + p->Size;
- #endif
-
- CPpmd7_Node_Ref n = head;
- unsigned i;
+ CPpmd7_Node Node;
+ CPpmd7_Node_Ref NextRef;
+} CPpmd7_Node_Union;
+
+/* Original PPmdH (Ppmd7) code uses doubly linked list in Ppmd7_GlueFreeBlocks()
+ we use single linked list similar to Ppmd8 code */
+
+static void Ppmd7_GlueFreeBlocks(CPpmd7 *p)
+{
+ /*
+ we use first UInt16 field of 12-bytes UNITs as record type stamp
+ CPpmd_State { Byte Symbol; Byte Freq; : Freq != 0
+ CPpmd7_Context { UInt16 NumStats; : NumStats != 0
+ CPpmd7_Node { UInt16 Stamp : Stamp == 0 for free record
+ : Stamp == 1 for head record and guard
+ Last 12-bytes UNIT in array is always contains 12-bytes order-0 CPpmd7_Context record.
+ */
+ CPpmd7_Node_Ref head, n = 0;
+
p->GlueCount = 255;
- /* create doubly-linked list of free blocks */
- for (i = 0; i < PPMD_NUM_INDEXES; i++)
+
+ /* we set guard NODE at LoUnit */
+ if (p->LoUnit != p->HiUnit)
+ ((CPpmd7_Node *)(void *)p->LoUnit)->Stamp = 1;
+
{
- UInt16 nu = I2U(i);
- CPpmd7_Node_Ref next = (CPpmd7_Node_Ref)p->FreeList[i];
- p->FreeList[i] = 0;
- while (next != 0)
+ /* Create list of free blocks.
+ We still need one additional list walk pass before Glue. */
+ unsigned i;
+ for (i = 0; i < PPMD_NUM_INDEXES; i++)
{
- CPpmd7_Node *node = NODE(next);
- node->Next = n;
- n = NODE(n)->Prev = next;
- next = *(const CPpmd7_Node_Ref *)node;
- node->Stamp = 0;
- node->NU = (UInt16)nu;
+ const UInt16 nu = I2U_UInt16(i);
+ CPpmd7_Node_Ref next = (CPpmd7_Node_Ref)p->FreeList[i];
+ p->FreeList[i] = 0;
+ while (next != 0)
+ {
+ /* Don't change the order of the following commands: */
+ CPpmd7_Node_Union *un = (CPpmd7_Node_Union *)NODE(next);
+ const CPpmd7_Node_Ref tmp = next;
+ next = un->NextRef;
+ un->Node.Stamp = EMPTY_NODE;
+ un->Node.NU = nu;
+ un->Node.Next = n;
+ n = tmp;
+ }
}
}
- NODE(head)->Stamp = 1;
- NODE(head)->Next = n;
- NODE(n)->Prev = head;
- if (p->LoUnit != p->HiUnit)
- ((CPpmd7_Node *)p->LoUnit)->Stamp = 1;
-
- /* Glue free blocks */
- while (n != head)
+
+ head = n;
+ /* Glue and Fill must walk the list in same direction */
{
- CPpmd7_Node *node = NODE(n);
- UInt32 nu = (UInt32)node->NU;
- for (;;)
+ /* Glue free blocks */
+ CPpmd7_Node_Ref *prev = &head;
+ while (n)
{
- CPpmd7_Node *node2 = NODE(n) + nu;
- nu += node2->NU;
- if (node2->Stamp != 0 || nu >= 0x10000)
- break;
- NODE(node2->Prev)->Next = node2->Next;
- NODE(node2->Next)->Prev = node2->Prev;
- node->NU = (UInt16)nu;
+ CPpmd7_Node *node = NODE(n);
+ UInt32 nu = node->NU;
+ n = node->Next;
+ if (nu == 0)
+ {
+ *prev = n;
+ continue;
+ }
+ prev = &node->Next;
+ for (;;)
+ {
+ CPpmd7_Node *node2 = node + nu;
+ nu += node2->NU;
+ if (node2->Stamp != EMPTY_NODE || nu >= 0x10000)
+ break;
+ node->NU = (UInt16)nu;
+ node2->NU = 0;
+ }
}
- n = node->Next;
}
-
+
/* Fill lists of free blocks */
- for (n = NODE(head)->Next; n != head;)
+ for (n = head; n != 0;)
{
CPpmd7_Node *node = NODE(n);
- unsigned nu;
- CPpmd7_Node_Ref next = node->Next;
- for (nu = node->NU; nu > 128; nu -= 128, node += 128)
- InsertNode(p, node, PPMD_NUM_INDEXES - 1);
+ UInt32 nu = node->NU;
+ unsigned i;
+ n = node->Next;
+ if (nu == 0)
+ continue;
+ for (; nu > 128; nu -= 128, node += 128)
+ Ppmd7_InsertNode(p, node, PPMD_NUM_INDEXES - 1);
if (I2U(i = U2I(nu)) != nu)
{
unsigned k = I2U(--i);
- InsertNode(p, node + k, nu - k - 1);
+ Ppmd7_InsertNode(p, node + k, (unsigned)nu - k - 1);
}
- InsertNode(p, node, i);
- n = next;
+ Ppmd7_InsertNode(p, node, i);
}
}
-static void *AllocUnitsRare(CPpmd7 *p, unsigned indx)
+
+Z7_NO_INLINE
+static void *Ppmd7_AllocUnitsRare(CPpmd7 *p, unsigned indx)
{
unsigned i;
- void *retVal;
+
if (p->GlueCount == 0)
{
- GlueFreeBlocks(p);
+ Ppmd7_GlueFreeBlocks(p);
if (p->FreeList[indx] != 0)
- return RemoveNode(p, indx);
+ return Ppmd7_RemoveNode(p, indx);
}
+
i = indx;
+
do
{
if (++i == PPMD_NUM_INDEXES)
{
UInt32 numBytes = U2B(I2U(indx));
+ Byte *us = p->UnitsStart;
p->GlueCount--;
- return ((UInt32)(p->UnitsStart - p->Text) > numBytes) ? (p->UnitsStart -= numBytes) : (NULL);
+ return ((UInt32)(us - p->Text) > numBytes) ? (p->UnitsStart = us - numBytes) : NULL;
}
}
while (p->FreeList[i] == 0);
- retVal = RemoveNode(p, i);
- SplitBlock(p, retVal, i, indx);
- return retVal;
+
+ {
+ void *block = Ppmd7_RemoveNode(p, i);
+ Ppmd7_SplitBlock(p, block, i, indx);
+ return block;
+ }
}
-static void *AllocUnits(CPpmd7 *p, unsigned indx)
+
+static void *Ppmd7_AllocUnits(CPpmd7 *p, unsigned indx)
{
- UInt32 numBytes;
if (p->FreeList[indx] != 0)
- return RemoveNode(p, indx);
- numBytes = U2B(I2U(indx));
- if (numBytes <= (UInt32)(p->HiUnit - p->LoUnit))
+ return Ppmd7_RemoveNode(p, indx);
{
- void *retVal = p->LoUnit;
- p->LoUnit += numBytes;
- return retVal;
+ UInt32 numBytes = U2B(I2U(indx));
+ Byte *lo = p->LoUnit;
+ if ((UInt32)(p->HiUnit - lo) >= numBytes)
+ {
+ p->LoUnit = lo + numBytes;
+ return lo;
+ }
}
- return AllocUnitsRare(p, indx);
+ return Ppmd7_AllocUnitsRare(p, indx);
}
-#define MyMem12Cpy(dest, src, num) \
- { UInt32 *d = (UInt32 *)dest; const UInt32 *s = (const UInt32 *)src; UInt32 n = num; \
- do { d[0] = s[0]; d[1] = s[1]; d[2] = s[2]; s += 3; d += 3; } while (--n); }
+#define MEM_12_CPY(dest, src, num) \
+ { UInt32 *d = (UInt32 *)dest; const UInt32 *z = (const UInt32 *)src; UInt32 n = num; \
+ do { d[0] = z[0]; d[1] = z[1]; d[2] = z[2]; z += 3; d += 3; } while (--n); }
+
+
+/*
static void *ShrinkUnits(CPpmd7 *p, void *oldPtr, unsigned oldNU, unsigned newNU)
{
unsigned i0 = U2I(oldNU);
@@ -267,28 +315,33 @@ static void *ShrinkUnits(CPpmd7 *p, void *oldPtr, unsigned oldNU, unsigned newNU
return oldPtr;
if (p->FreeList[i1] != 0)
{
- void *ptr = RemoveNode(p, i1);
- MyMem12Cpy(ptr, oldPtr, newNU);
- InsertNode(p, oldPtr, i0);
+ void *ptr = Ppmd7_RemoveNode(p, i1);
+ MEM_12_CPY(ptr, oldPtr, newNU)
+ Ppmd7_InsertNode(p, oldPtr, i0);
return ptr;
}
- SplitBlock(p, oldPtr, i0, i1);
+ Ppmd7_SplitBlock(p, oldPtr, i0, i1);
return oldPtr;
}
+*/
-#define SUCCESSOR(p) ((CPpmd_Void_Ref)((p)->SuccessorLow | ((UInt32)(p)->SuccessorHigh << 16)))
+#define SUCCESSOR(p) Ppmd_GET_SUCCESSOR(p)
static void SetSuccessor(CPpmd_State *p, CPpmd_Void_Ref v)
{
- (p)->SuccessorLow = (UInt16)((UInt32)(v) & 0xFFFF);
- (p)->SuccessorHigh = (UInt16)(((UInt32)(v) >> 16) & 0xFFFF);
+ Ppmd_SET_SUCCESSOR(p, v)
}
-static void RestartModel(CPpmd7 *p)
+
+
+Z7_NO_INLINE
+static
+void Ppmd7_RestartModel(CPpmd7 *p)
{
- unsigned i, k, m;
+ unsigned i, k;
memset(p->FreeList, 0, sizeof(p->FreeList));
+
p->Text = p->Base + p->AlignOffset;
p->HiUnit = p->Text + p->Size;
p->LoUnit = p->UnitsStart = p->HiUnit - p->Size / 8 / UNIT_SIZE * 7 * UNIT_SIZE;
@@ -298,57 +351,110 @@ static void RestartModel(CPpmd7 *p)
p->RunLength = p->InitRL = -(Int32)((p->MaxOrder < 12) ? p->MaxOrder : 12) - 1;
p->PrevSuccess = 0;
- p->MinContext = p->MaxContext = (CTX_PTR)(p->HiUnit -= UNIT_SIZE); /* AllocContext(p); */
- p->MinContext->Suffix = 0;
- p->MinContext->NumStats = 256;
- p->MinContext->SummFreq = 256 + 1;
- p->FoundState = (CPpmd_State *)p->LoUnit; /* AllocUnits(p, PPMD_NUM_INDEXES - 1); */
- p->LoUnit += U2B(256 / 2);
- p->MinContext->Stats = REF(p->FoundState);
- for (i = 0; i < 256; i++)
{
- CPpmd_State *s = &p->FoundState[i];
- s->Symbol = (Byte)i;
- s->Freq = 1;
- SetSuccessor(s, 0);
+ CPpmd7_Context *mc = (PPMD7_CTX_PTR)(void *)(p->HiUnit -= UNIT_SIZE); /* AllocContext(p); */
+ CPpmd_State *s = (CPpmd_State *)p->LoUnit; /* Ppmd7_AllocUnits(p, PPMD_NUM_INDEXES - 1); */
+
+ p->LoUnit += U2B(256 / 2);
+ p->MaxContext = p->MinContext = mc;
+ p->FoundState = s;
+
+ mc->NumStats = 256;
+ mc->Union2.SummFreq = 256 + 1;
+ mc->Union4.Stats = REF(s);
+ mc->Suffix = 0;
+
+ for (i = 0; i < 256; i++, s++)
+ {
+ s->Symbol = (Byte)i;
+ s->Freq = 1;
+ SetSuccessor(s, 0);
+ }
+
+ #ifdef PPMD7_ORDER_0_SUPPPORT
+ if (p->MaxOrder == 0)
+ {
+ CPpmd_Void_Ref r = REF(mc);
+ s = p->FoundState;
+ for (i = 0; i < 256; i++, s++)
+ SetSuccessor(s, r);
+ return;
+ }
+ #endif
}
for (i = 0; i < 128; i++)
+
+
+
for (k = 0; k < 8; k++)
{
+ unsigned m;
UInt16 *dest = p->BinSumm[i] + k;
- UInt16 val = (UInt16)(PPMD_BIN_SCALE - kInitBinEsc[k] / (i + 2));
+ const UInt16 val = (UInt16)(PPMD_BIN_SCALE - PPMD7_kInitBinEsc[k] / (i + 2));
for (m = 0; m < 64; m += 8)
dest[m] = val;
}
-
+
+
for (i = 0; i < 25; i++)
- for (k = 0; k < 16; k++)
+ {
+
+ CPpmd_See *s = p->See[i];
+
+
+
+ unsigned summ = ((5 * i + 10) << (PPMD_PERIOD_BITS - 4));
+ for (k = 0; k < 16; k++, s++)
{
- CPpmd_See *s = &p->See[i][k];
- s->Summ = (UInt16)((5 * i + 10) << (s->Shift = PPMD_PERIOD_BITS - 4));
+ s->Summ = (UInt16)summ;
+ s->Shift = (PPMD_PERIOD_BITS - 4);
s->Count = 4;
}
+ }
+
+ p->DummySee.Summ = 0; /* unused */
+ p->DummySee.Shift = PPMD_PERIOD_BITS;
+ p->DummySee.Count = 64; /* unused */
}
+
void Ppmd7_Init(CPpmd7 *p, unsigned maxOrder)
{
p->MaxOrder = maxOrder;
- RestartModel(p);
- p->DummySee.Shift = PPMD_PERIOD_BITS;
- p->DummySee.Summ = 0; /* unused */
- p->DummySee.Count = 64; /* unused */
+
+ Ppmd7_RestartModel(p);
}
-static CTX_PTR CreateSuccessors(CPpmd7 *p, Bool skip)
+
+
+/*
+ Ppmd7_CreateSuccessors()
+ It's called when (FoundState->Successor) is RAW-Successor,
+ that is the link to position in Raw text.
+ So we create Context records and write the links to
+ FoundState->Successor and to identical RAW-Successors in suffix
+ contexts of MinContex.
+
+ The function returns:
+ if (OrderFall == 0) then MinContext is already at MAX order,
+ { return pointer to new or existing context of same MAX order }
+ else
+ { return pointer to new real context that will be (Order+1) in comparison with MinContext
+
+ also it can return pointer to real context of same order,
+*/
+
+Z7_NO_INLINE
+static PPMD7_CTX_PTR Ppmd7_CreateSuccessors(CPpmd7 *p)
{
- CPpmd_State upState;
- CTX_PTR c = p->MinContext;
+ PPMD7_CTX_PTR c = p->MinContext;
CPpmd_Byte_Ref upBranch = (CPpmd_Byte_Ref)SUCCESSOR(p->FoundState);
- CPpmd_State *ps[PPMD7_MAX_ORDER];
+ Byte newSym, newFreq;
unsigned numPs = 0;
-
- if (!skip)
+ CPpmd_State *ps[PPMD7_MAX_ORDER];
+
+ if (p->OrderFall != 0)
ps[numPs++] = p->FoundState;
while (c->Suffix)
@@ -356,54 +462,83 @@ static CTX_PTR CreateSuccessors(CPpmd7 *p, Bool skip)
CPpmd_Void_Ref successor;
CPpmd_State *s;
c = SUFFIX(c);
+
+
if (c->NumStats != 1)
{
- for (s = STATS(c); s->Symbol != p->FoundState->Symbol; s++);
+ Byte sym = p->FoundState->Symbol;
+ for (s = STATS(c); s->Symbol != sym; s++);
+
}
else
+ {
s = ONE_STATE(c);
+
+ }
successor = SUCCESSOR(s);
if (successor != upBranch)
{
+ // (c) is real record Context here,
c = CTX(successor);
if (numPs == 0)
+ {
+ // (c) is real record MAX Order Context here,
+ // So we don't need to create any new contexts.
return c;
+ }
break;
}
ps[numPs++] = s;
}
- upState.Symbol = *(const Byte *)Ppmd7_GetPtr(p, upBranch);
- SetSuccessor(&upState, upBranch + 1);
+ // All created contexts will have single-symbol with new RAW-Successor
+ // All new RAW-Successors will point to next position in RAW text
+ // after FoundState->Successor
+
+ newSym = *(const Byte *)Ppmd7_GetPtr(p, upBranch);
+ upBranch++;
+
if (c->NumStats == 1)
- upState.Freq = ONE_STATE(c)->Freq;
+ newFreq = ONE_STATE(c)->Freq;
else
{
UInt32 cf, s0;
CPpmd_State *s;
- for (s = STATS(c); s->Symbol != upState.Symbol; s++);
- cf = s->Freq - 1;
- s0 = c->SummFreq - c->NumStats - cf;
- upState.Freq = (Byte)(1 + ((2 * cf <= s0) ? (5 * cf > s0) : ((2 * cf + 3 * s0 - 1) / (2 * s0))));
+ for (s = STATS(c); s->Symbol != newSym; s++);
+ cf = (UInt32)s->Freq - 1;
+ s0 = (UInt32)c->Union2.SummFreq - c->NumStats - cf;
+ /*
+ cf - is frequency of symbol that will be Successor in new context records.
+ s0 - is commulative frequency sum of another symbols from parent context.
+ max(newFreq)= (s->Freq + 1), when (s0 == 1)
+ we have requirement (Ppmd7Context_OneState()->Freq <= 128) in BinSumm[]
+ so (s->Freq < 128) - is requirement for multi-symbol contexts
+ */
+ newFreq = (Byte)(1 + ((2 * cf <= s0) ? (5 * cf > s0) : (2 * cf + s0 - 1) / (2 * s0) + 1));
}
+ // Create new single-symbol contexts from low order to high order in loop
+
do
{
- /* Create Child */
- CTX_PTR c1; /* = AllocContext(p); */
+ PPMD7_CTX_PTR c1;
+ /* = AllocContext(p); */
if (p->HiUnit != p->LoUnit)
- c1 = (CTX_PTR)(p->HiUnit -= UNIT_SIZE);
+ c1 = (PPMD7_CTX_PTR)(void *)(p->HiUnit -= UNIT_SIZE);
else if (p->FreeList[0] != 0)
- c1 = (CTX_PTR)RemoveNode(p, 0);
+ c1 = (PPMD7_CTX_PTR)Ppmd7_RemoveNode(p, 0);
else
{
- c1 = (CTX_PTR)AllocUnitsRare(p, 0);
+ c1 = (PPMD7_CTX_PTR)Ppmd7_AllocUnitsRare(p, 0);
if (!c1)
return NULL;
}
+
c1->NumStats = 1;
- *ONE_STATE(c1) = upState;
+ ONE_STATE(c1)->Symbol = newSym;
+ ONE_STATE(c1)->Freq = newFreq;
+ SetSuccessor(ONE_STATE(c1), upBranch);
c1->Suffix = REF(c);
SetSuccessor(ps[--numPs], REF(c1));
c = c1;
@@ -413,21 +548,26 @@ static CTX_PTR CreateSuccessors(CPpmd7 *p, Bool skip)
return c;
}
-static void SwapStates(CPpmd_State *t1, CPpmd_State *t2)
-{
- CPpmd_State tmp = *t1;
- *t1 = *t2;
- *t2 = tmp;
-}
-static void UpdateModel(CPpmd7 *p)
+
+#define SWAP_STATES(s) \
+ { CPpmd_State tmp = s[0]; s[0] = s[-1]; s[-1] = tmp; }
+
+
+void Ppmd7_UpdateModel(CPpmd7 *p);
+Z7_NO_INLINE
+void Ppmd7_UpdateModel(CPpmd7 *p)
{
- CPpmd_Void_Ref successor, fSuccessor = SUCCESSOR(p->FoundState);
- CTX_PTR c;
+ CPpmd_Void_Ref maxSuccessor, minSuccessor;
+ PPMD7_CTX_PTR c, mc;
unsigned s0, ns;
-
+
+
+
if (p->FoundState->Freq < MAX_FREQ / 4 && p->MinContext->Suffix != 0)
{
+ /* Update Freqs in Suffix Context */
+
c = SUFFIX(p->MinContext);
if (c->NumStats == 1)
@@ -439,73 +579,133 @@ static void UpdateModel(CPpmd7 *p)
else
{
CPpmd_State *s = STATS(c);
- if (s->Symbol != p->FoundState->Symbol)
+ Byte sym = p->FoundState->Symbol;
+
+ if (s->Symbol != sym)
{
- do { s++; } while (s->Symbol != p->FoundState->Symbol);
+ do
+ {
+ // s++; if (s->Symbol == sym) break;
+ s++;
+ }
+ while (s->Symbol != sym);
+
if (s[0].Freq >= s[-1].Freq)
{
- SwapStates(&s[0], &s[-1]);
+ SWAP_STATES(s)
s--;
}
}
+
if (s->Freq < MAX_FREQ - 9)
{
- s->Freq += 2;
- c->SummFreq += 2;
+ s->Freq = (Byte)(s->Freq + 2);
+ c->Union2.SummFreq = (UInt16)(c->Union2.SummFreq + 2);
}
}
}
+
if (p->OrderFall == 0)
{
- p->MinContext = p->MaxContext = CreateSuccessors(p, True);
- if (p->MinContext == 0)
+ /* MAX ORDER context */
+ /* (FoundState->Successor) is RAW-Successor. */
+ p->MaxContext = p->MinContext = Ppmd7_CreateSuccessors(p);
+ if (!p->MinContext)
{
- RestartModel(p);
+ Ppmd7_RestartModel(p);
return;
}
SetSuccessor(p->FoundState, REF(p->MinContext));
return;
}
+
+
+ /* NON-MAX ORDER context */
- *p->Text++ = p->FoundState->Symbol;
- successor = REF(p->Text);
- if (p->Text >= p->UnitsStart)
{
- RestartModel(p);
- return;
+ Byte *text = p->Text;
+ *text++ = p->FoundState->Symbol;
+ p->Text = text;
+ if (text >= p->UnitsStart)
+ {
+ Ppmd7_RestartModel(p);
+ return;
+ }
+ maxSuccessor = REF(text);
}
- if (fSuccessor)
+ minSuccessor = SUCCESSOR(p->FoundState);
+
+ if (minSuccessor)
{
- if (fSuccessor <= successor)
+ // there is Successor for FoundState in MinContext.
+ // So the next context will be one order higher than MinContext.
+
+ if (minSuccessor <= maxSuccessor)
{
- CTX_PTR cs = CreateSuccessors(p, False);
- if (cs == NULL)
+ // minSuccessor is RAW-Successor. So we will create real contexts records:
+ PPMD7_CTX_PTR cs = Ppmd7_CreateSuccessors(p);
+ if (!cs)
{
- RestartModel(p);
+ Ppmd7_RestartModel(p);
return;
}
- fSuccessor = REF(cs);
+ minSuccessor = REF(cs);
}
+
+ // minSuccessor now is real Context pointer that points to existing (Order+1) context
+
if (--p->OrderFall == 0)
{
- successor = fSuccessor;
+ /*
+ if we move to MaxOrder context, then minSuccessor will be common Succesor for both:
+ MinContext that is (MaxOrder - 1)
+ MaxContext that is (MaxOrder)
+ so we don't need new RAW-Successor, and we can use real minSuccessor
+ as succssors for both MinContext and MaxContext.
+ */
+ maxSuccessor = minSuccessor;
+
+ /*
+ if (MaxContext != MinContext)
+ {
+ there was order fall from MaxOrder and we don't need current symbol
+ to transfer some RAW-Succesors to real contexts.
+ So we roll back pointer in raw data for one position.
+ }
+ */
p->Text -= (p->MaxContext != p->MinContext);
}
}
else
{
- SetSuccessor(p->FoundState, successor);
- fSuccessor = REF(p->MinContext);
+ /*
+ FoundState has NULL-Successor here.
+ And only root 0-order context can contain NULL-Successors.
+ We change Successor in FoundState to RAW-Successor,
+ And next context will be same 0-order root Context.
+ */
+ SetSuccessor(p->FoundState, maxSuccessor);
+ minSuccessor = REF(p->MinContext);
}
-
- s0 = p->MinContext->SummFreq - (ns = p->MinContext->NumStats) - (p->FoundState->Freq - 1);
-
- for (c = p->MaxContext; c != p->MinContext; c = SUFFIX(c))
+
+ mc = p->MinContext;
+ c = p->MaxContext;
+
+ p->MaxContext = p->MinContext = CTX(minSuccessor);
+
+ if (c == mc)
+ return;
+
+ // s0 : is pure Escape Freq
+ s0 = mc->Union2.SummFreq - (ns = mc->NumStats) - ((unsigned)p->FoundState->Freq - 1);
+
+ do
{
unsigned ns1;
- UInt32 cf, sf;
+ UInt32 sum;
+
if ((ns1 = c->NumStats) != 1)
{
if ((ns1 & 1) == 0)
@@ -513,92 +713,139 @@ static void UpdateModel(CPpmd7 *p)
/* Expand for one UNIT */
unsigned oldNU = ns1 >> 1;
unsigned i = U2I(oldNU);
- if (i != U2I(oldNU + 1))
+ if (i != U2I((size_t)oldNU + 1))
{
- void *ptr = AllocUnits(p, i + 1);
+ void *ptr = Ppmd7_AllocUnits(p, i + 1);
void *oldPtr;
if (!ptr)
{
- RestartModel(p);
+ Ppmd7_RestartModel(p);
return;
}
oldPtr = STATS(c);
- MyMem12Cpy(ptr, oldPtr, oldNU);
- InsertNode(p, oldPtr, i);
- c->Stats = STATS_REF(ptr);
+ MEM_12_CPY(ptr, oldPtr, oldNU)
+ Ppmd7_InsertNode(p, oldPtr, i);
+ c->Union4.Stats = STATS_REF(ptr);
}
}
- c->SummFreq = (UInt16)(c->SummFreq + (2 * ns1 < ns) + 2 * ((4 * ns1 <= ns) & (c->SummFreq <= 8 * ns1)));
+ sum = c->Union2.SummFreq;
+ /* max increase of Escape_Freq is 3 here.
+ total increase of Union2.SummFreq for all symbols is less than 256 here */
+ sum += (UInt32)(2 * ns1 < ns) + 2 * ((unsigned)(4 * ns1 <= ns) & (sum <= 8 * ns1));
+ /* original PPMdH uses 16-bit variable for (sum) here.
+ But (sum < 0x9000). So we don't truncate (sum) to 16-bit */
+ // sum = (UInt16)sum;
}
else
{
- CPpmd_State *s = (CPpmd_State*)AllocUnits(p, 0);
+ // instead of One-symbol context we create 2-symbol context
+ CPpmd_State *s = (CPpmd_State*)Ppmd7_AllocUnits(p, 0);
if (!s)
{
- RestartModel(p);
+ Ppmd7_RestartModel(p);
return;
}
- *s = *ONE_STATE(c);
- c->Stats = REF(s);
- if (s->Freq < MAX_FREQ / 4 - 1)
- s->Freq <<= 1;
- else
- s->Freq = MAX_FREQ - 4;
- c->SummFreq = (UInt16)(s->Freq + p->InitEsc + (ns > 3));
- }
- cf = 2 * (UInt32)p->FoundState->Freq * (c->SummFreq + 6);
- sf = (UInt32)s0 + c->SummFreq;
- if (cf < 6 * sf)
- {
- cf = 1 + (cf > sf) + (cf >= 4 * sf);
- c->SummFreq += 3;
- }
- else
- {
- cf = 4 + (cf >= 9 * sf) + (cf >= 12 * sf) + (cf >= 15 * sf);
- c->SummFreq = (UInt16)(c->SummFreq + cf);
+ {
+ unsigned freq = c->Union2.State2.Freq;
+ // s = *ONE_STATE(c);
+ s->Symbol = c->Union2.State2.Symbol;
+ s->Successor_0 = c->Union4.State4.Successor_0;
+ s->Successor_1 = c->Union4.State4.Successor_1;
+ // SetSuccessor(s, c->Union4.Stats); // call it only for debug purposes to check the order of
+ // (Successor_0 and Successor_1) in LE/BE.
+ c->Union4.Stats = REF(s);
+ if (freq < MAX_FREQ / 4 - 1)
+ freq <<= 1;
+ else
+ freq = MAX_FREQ - 4;
+ // (max(s->freq) == 120), when we convert from 1-symbol into 2-symbol context
+ s->Freq = (Byte)freq;
+ // max(InitEsc = PPMD7_kExpEscape[*]) is 25. So the max(escapeFreq) is 26 here
+ sum = freq + p->InitEsc + (ns > 3);
+ }
}
+
{
CPpmd_State *s = STATS(c) + ns1;
- SetSuccessor(s, successor);
+ UInt32 cf = 2 * (sum + 6) * (UInt32)p->FoundState->Freq;
+ UInt32 sf = (UInt32)s0 + sum;
s->Symbol = p->FoundState->Symbol;
- s->Freq = (Byte)cf;
c->NumStats = (UInt16)(ns1 + 1);
+ SetSuccessor(s, maxSuccessor);
+
+ if (cf < 6 * sf)
+ {
+ cf = (UInt32)1 + (cf > sf) + (cf >= 4 * sf);
+ sum += 3;
+ /* It can add (0, 1, 2) to Escape_Freq */
+ }
+ else
+ {
+ cf = (UInt32)4 + (cf >= 9 * sf) + (cf >= 12 * sf) + (cf >= 15 * sf);
+ sum += cf;
+ }
+
+ c->Union2.SummFreq = (UInt16)sum;
+ s->Freq = (Byte)cf;
}
+ c = SUFFIX(c);
}
- p->MaxContext = p->MinContext = CTX(fSuccessor);
+ while (c != mc);
}
-static void Rescale(CPpmd7 *p)
+
+
+Z7_NO_INLINE
+static void Ppmd7_Rescale(CPpmd7 *p)
{
unsigned i, adder, sumFreq, escFreq;
CPpmd_State *stats = STATS(p->MinContext);
CPpmd_State *s = p->FoundState;
+
+ /* Sort the list by Freq */
+ if (s != stats)
{
CPpmd_State tmp = *s;
- for (; s != stats; s--)
+ do
s[0] = s[-1];
+ while (--s != stats);
*s = tmp;
}
- escFreq = p->MinContext->SummFreq - s->Freq;
- s->Freq += 4;
- adder = (p->OrderFall != 0);
- s->Freq = (Byte)((s->Freq + adder) >> 1);
+
sumFreq = s->Freq;
+ escFreq = p->MinContext->Union2.SummFreq - sumFreq;
+
+ /*
+ if (p->OrderFall == 0), adder = 0 : it's allowed to remove symbol from MAX Order context
+ if (p->OrderFall != 0), adder = 1 : it's NOT allowed to remove symbol from NON-MAX Order context
+ */
+
+ adder = (p->OrderFall != 0);
+
+ #ifdef PPMD7_ORDER_0_SUPPPORT
+ adder |= (p->MaxOrder == 0); // we don't remove symbols from order-0 context
+ #endif
+
+ sumFreq = (sumFreq + 4 + adder) >> 1;
+ i = (unsigned)p->MinContext->NumStats - 1;
+ s->Freq = (Byte)sumFreq;
- i = p->MinContext->NumStats - 1;
do
{
- escFreq -= (++s)->Freq;
- s->Freq = (Byte)((s->Freq + adder) >> 1);
- sumFreq += s->Freq;
- if (s[0].Freq > s[-1].Freq)
+ unsigned freq = (++s)->Freq;
+ escFreq -= freq;
+ freq = (freq + adder) >> 1;
+ sumFreq += freq;
+ s->Freq = (Byte)freq;
+ if (freq > s[-1].Freq)
{
+ CPpmd_State tmp = *s;
CPpmd_State *s1 = s;
- CPpmd_State tmp = *s1;
do
+ {
s1[0] = s1[-1];
- while (--s1 != stats && tmp.Freq > s1[-1].Freq);
+ }
+ while (--s1 != stats && freq > s1[-1].Freq);
*s1 = tmp;
}
}
@@ -606,47 +853,89 @@ static void Rescale(CPpmd7 *p)
if (s->Freq == 0)
{
- unsigned numStats = p->MinContext->NumStats;
- unsigned n0, n1;
- do { i++; } while ((--s)->Freq == 0);
+ /* Remove all items with Freq == 0 */
+ CPpmd7_Context *mc;
+ unsigned numStats, numStatsNew, n0, n1;
+
+ i = 0; do { i++; } while ((--s)->Freq == 0);
+
+ /* We increase (escFreq) for the number of removed symbols.
+ So we will have (0.5) increase for Escape_Freq in avarage per
+ removed symbol after Escape_Freq halving */
escFreq += i;
- p->MinContext->NumStats = (UInt16)(p->MinContext->NumStats - i);
- if (p->MinContext->NumStats == 1)
+ mc = p->MinContext;
+ numStats = mc->NumStats;
+ numStatsNew = numStats - i;
+ mc->NumStats = (UInt16)(numStatsNew);
+ n0 = (numStats + 1) >> 1;
+
+ if (numStatsNew == 1)
{
- CPpmd_State tmp = *stats;
+ /* Create Single-Symbol context */
+ unsigned freq = stats->Freq;
+
do
{
- tmp.Freq = (Byte)(tmp.Freq - (tmp.Freq >> 1));
escFreq >>= 1;
+ freq = (freq + 1) >> 1;
}
while (escFreq > 1);
- InsertNode(p, stats, U2I(((numStats + 1) >> 1)));
- *(p->FoundState = ONE_STATE(p->MinContext)) = tmp;
+
+ s = ONE_STATE(mc);
+ *s = *stats;
+ s->Freq = (Byte)freq; // (freq <= 260 / 4)
+ p->FoundState = s;
+ Ppmd7_InsertNode(p, stats, U2I(n0));
return;
}
- n0 = (numStats + 1) >> 1;
- n1 = (p->MinContext->NumStats + 1) >> 1;
+
+ n1 = (numStatsNew + 1) >> 1;
if (n0 != n1)
- p->MinContext->Stats = STATS_REF(ShrinkUnits(p, stats, n0, n1));
+ {
+ // p->MinContext->Union4.Stats = STATS_REF(ShrinkUnits(p, stats, n0, n1));
+ unsigned i0 = U2I(n0);
+ unsigned i1 = U2I(n1);
+ if (i0 != i1)
+ {
+ if (p->FreeList[i1] != 0)
+ {
+ void *ptr = Ppmd7_RemoveNode(p, i1);
+ p->MinContext->Union4.Stats = STATS_REF(ptr);
+ MEM_12_CPY(ptr, (const void *)stats, n1)
+ Ppmd7_InsertNode(p, stats, i0);
+ }
+ else
+ Ppmd7_SplitBlock(p, stats, i0, i1);
+ }
+ }
+ }
+ {
+ CPpmd7_Context *mc = p->MinContext;
+ mc->Union2.SummFreq = (UInt16)(sumFreq + escFreq - (escFreq >> 1));
+ // Escape_Freq halving here
+ p->FoundState = STATS(mc);
}
- p->MinContext->SummFreq = (UInt16)(sumFreq + escFreq - (escFreq >> 1));
- p->FoundState = STATS(p->MinContext);
}
+
CPpmd_See *Ppmd7_MakeEscFreq(CPpmd7 *p, unsigned numMasked, UInt32 *escFreq)
{
CPpmd_See *see;
- unsigned nonMasked = p->MinContext->NumStats - numMasked;
- if (p->MinContext->NumStats != 256)
+ const CPpmd7_Context *mc = p->MinContext;
+ unsigned numStats = mc->NumStats;
+ if (numStats != 256)
{
- see = p->See[(unsigned)p->NS2Indx[nonMasked - 1]] +
- (nonMasked < (unsigned)SUFFIX(p->MinContext)->NumStats - p->MinContext->NumStats) +
- 2 * (unsigned)(p->MinContext->SummFreq < 11 * p->MinContext->NumStats) +
- 4 * (unsigned)(numMasked > nonMasked) +
+ unsigned nonMasked = numStats - numMasked;
+ see = p->See[(unsigned)p->NS2Indx[(size_t)nonMasked - 1]]
+ + (nonMasked < (unsigned)SUFFIX(mc)->NumStats - numStats)
+ + 2 * (unsigned)(mc->Union2.SummFreq < 11 * numStats)
+ + 4 * (unsigned)(numMasked > nonMasked) +
p->HiBitsFlag;
{
- unsigned r = (see->Summ >> see->Shift);
- see->Summ = (UInt16)(see->Summ - r);
+ // if (see->Summ) field is larger than 16-bit, we need only low 16 bits of Summ
+ unsigned summ = (UInt16)see->Summ; // & 0xFFFF
+ unsigned r = (summ >> see->Shift);
+ see->Summ = (UInt16)(summ - r);
*escFreq = r + (r == 0);
}
}
@@ -658,53 +947,176 @@ CPpmd_See *Ppmd7_MakeEscFreq(CPpmd7 *p, unsigned numMasked, UInt32 *escFreq)
return see;
}
-static void NextContext(CPpmd7 *p)
+
+static void Ppmd7_NextContext(CPpmd7 *p)
{
- CTX_PTR c = CTX(SUCCESSOR(p->FoundState));
- if (p->OrderFall == 0 && (Byte *)c > p->Text)
- p->MinContext = p->MaxContext = c;
+ PPMD7_CTX_PTR c = CTX(SUCCESSOR(p->FoundState));
+ if (p->OrderFall == 0 && (const Byte *)c > p->Text)
+ p->MaxContext = p->MinContext = c;
else
- UpdateModel(p);
+ Ppmd7_UpdateModel(p);
}
+
void Ppmd7_Update1(CPpmd7 *p)
{
CPpmd_State *s = p->FoundState;
- s->Freq += 4;
- p->MinContext->SummFreq += 4;
- if (s[0].Freq > s[-1].Freq)
+ unsigned freq = s->Freq;
+ freq += 4;
+ p->MinContext->Union2.SummFreq = (UInt16)(p->MinContext->Union2.SummFreq + 4);
+ s->Freq = (Byte)freq;
+ if (freq > s[-1].Freq)
{
- SwapStates(&s[0], &s[-1]);
+ SWAP_STATES(s)
p->FoundState = --s;
- if (s->Freq > MAX_FREQ)
- Rescale(p);
+ if (freq > MAX_FREQ)
+ Ppmd7_Rescale(p);
}
- NextContext(p);
+ Ppmd7_NextContext(p);
}
+
void Ppmd7_Update1_0(CPpmd7 *p)
{
- p->PrevSuccess = (2 * p->FoundState->Freq > p->MinContext->SummFreq);
- p->RunLength += p->PrevSuccess;
- p->MinContext->SummFreq += 4;
- if ((p->FoundState->Freq += 4) > MAX_FREQ)
- Rescale(p);
- NextContext(p);
+ CPpmd_State *s = p->FoundState;
+ CPpmd7_Context *mc = p->MinContext;
+ unsigned freq = s->Freq;
+ unsigned summFreq = mc->Union2.SummFreq;
+ p->PrevSuccess = (2 * freq > summFreq);
+ p->RunLength += (int)p->PrevSuccess;
+ mc->Union2.SummFreq = (UInt16)(summFreq + 4);
+ freq += 4;
+ s->Freq = (Byte)freq;
+ if (freq > MAX_FREQ)
+ Ppmd7_Rescale(p);
+ Ppmd7_NextContext(p);
}
+
+/*
void Ppmd7_UpdateBin(CPpmd7 *p)
{
- p->FoundState->Freq = (Byte)(p->FoundState->Freq + (p->FoundState->Freq < 128 ? 1: 0));
+ unsigned freq = p->FoundState->Freq;
+ p->FoundState->Freq = (Byte)(freq + (freq < 128));
p->PrevSuccess = 1;
p->RunLength++;
- NextContext(p);
+ Ppmd7_NextContext(p);
}
+*/
void Ppmd7_Update2(CPpmd7 *p)
{
- p->MinContext->SummFreq += 4;
- if ((p->FoundState->Freq += 4) > MAX_FREQ)
- Rescale(p);
+ CPpmd_State *s = p->FoundState;
+ unsigned freq = s->Freq;
+ freq += 4;
p->RunLength = p->InitRL;
- UpdateModel(p);
+ p->MinContext->Union2.SummFreq = (UInt16)(p->MinContext->Union2.SummFreq + 4);
+ s->Freq = (Byte)freq;
+ if (freq > MAX_FREQ)
+ Ppmd7_Rescale(p);
+ Ppmd7_UpdateModel(p);
+}
+
+
+
+/*
+PPMd Memory Map:
+{
+ [ 0 ] contains subset of original raw text, that is required to create context
+ records, Some symbols are not written, when max order context was reached
+ [ Text ] free area
+ [ UnitsStart ] CPpmd_State vectors and CPpmd7_Context records
+ [ LoUnit ] free area for CPpmd_State and CPpmd7_Context items
+[ HiUnit ] CPpmd7_Context records
+ [ Size ] end of array
}
+
+These addresses don't cross at any time.
+And the following condtions is true for addresses:
+ (0 <= Text < UnitsStart <= LoUnit <= HiUnit <= Size)
+
+Raw text is BYTE--aligned.
+the data in block [ UnitsStart ... Size ] contains 12-bytes aligned UNITs.
+
+Last UNIT of array at offset (Size - 12) is root order-0 CPpmd7_Context record.
+The code can free UNITs memory blocks that were allocated to store CPpmd_State vectors.
+The code doesn't free UNITs allocated for CPpmd7_Context records.
+
+The code calls Ppmd7_RestartModel(), when there is no free memory for allocation.
+And Ppmd7_RestartModel() changes the state to orignal start state, with full free block.
+
+
+The code allocates UNITs with the following order:
+
+Allocation of 1 UNIT for Context record
+ - from free space (HiUnit) down to (LoUnit)
+ - from FreeList[0]
+ - Ppmd7_AllocUnitsRare()
+
+Ppmd7_AllocUnits() for CPpmd_State vectors:
+ - from FreeList[i]
+ - from free space (LoUnit) up to (HiUnit)
+ - Ppmd7_AllocUnitsRare()
+
+Ppmd7_AllocUnitsRare()
+ - if (GlueCount == 0)
+ { Glue lists, GlueCount = 255, allocate from FreeList[i]] }
+ - loop for all higher sized FreeList[...] lists
+ - from (UnitsStart - Text), GlueCount--
+ - ERROR
+
+
+Each Record with Context contains the CPpmd_State vector, where each
+CPpmd_State contains the link to Successor.
+There are 3 types of Successor:
+ 1) NULL-Successor - NULL pointer. NULL-Successor links can be stored
+ only in 0-order Root Context Record.
+ We use 0 value as NULL-Successor
+ 2) RAW-Successor - the link to position in raw text,
+ that "RAW-Successor" is being created after first
+ occurrence of new symbol for some existing context record.
+ (RAW-Successor > 0).
+ 3) RECORD-Successor - the link to CPpmd7_Context record of (Order+1),
+ that record is being created when we go via RAW-Successor again.
+
+For any successors at any time: the following condtions are true for Successor links:
+(NULL-Successor < RAW-Successor < UnitsStart <= RECORD-Successor)
+
+
+---------- Symbol Frequency, SummFreq and Range in Range_Coder ----------
+
+CPpmd7_Context::SummFreq = Sum(Stats[].Freq) + Escape_Freq
+
+The PPMd code tries to fulfill the condition:
+ (SummFreq <= (256 * 128 = RC::kBot))
+
+We have (Sum(Stats[].Freq) <= 256 * 124), because of (MAX_FREQ = 124)
+So (4 = 128 - 124) is average reserve for Escape_Freq for each symbol.
+If (CPpmd_State::Freq) is not aligned for 4, the reserve can be 5, 6 or 7.
+SummFreq and Escape_Freq can be changed in Ppmd7_Rescale() and *Update*() functions.
+Ppmd7_Rescale() can remove symbols only from max-order contexts. So Escape_Freq can increase after multiple calls of Ppmd7_Rescale() for
+max-order context.
+
+When the PPMd code still break (Total <= RC::Range) condition in range coder,
+we have two ways to resolve that problem:
+ 1) we can report error, if we want to keep compatibility with original PPMd code that has no fix for such cases.
+ 2) we can reduce (Total) value to (RC::Range) by reducing (Escape_Freq) part of (Total) value.
+*/
+
+#undef MAX_FREQ
+#undef UNIT_SIZE
+#undef U2B
+#undef U2I
+#undef I2U
+#undef I2U_UInt16
+#undef REF
+#undef STATS_REF
+#undef CTX
+#undef STATS
+#undef ONE_STATE
+#undef SUFFIX
+#undef NODE
+#undef EMPTY_NODE
+#undef MEM_12_CPY
+#undef SUCCESSOR
+#undef SWAP_STATES