summaryrefslogtreecommitdiffstatshomepage
path: root/3rdparty/lzma/C/Ppmd7.c
diff options
context:
space:
mode:
author Vas Crabb <vas@vastheman.com>2023-12-06 07:58:49 +1100
committer Vas Crabb <vas@vastheman.com>2023-12-06 07:58:49 +1100
commit79bef1e23049fdac25f1fefd132e0b6c7d2cc3a1 (patch)
tree643e9313fe86f583c4022c338677cbc12b761df7 /3rdparty/lzma/C/Ppmd7.c
parent512ccf0c7c9b4f08e41038b2ed2de220e140385b (diff)
3rdparty/lzma: Updated to version 23.01.
Diffstat (limited to '3rdparty/lzma/C/Ppmd7.c')
-rw-r--r--3rdparty/lzma/C/Ppmd7.c186
1 files changed, 102 insertions, 84 deletions
diff --git a/3rdparty/lzma/C/Ppmd7.c b/3rdparty/lzma/C/Ppmd7.c
index cf401cb37c6..6e1307e2d39 100644
--- a/3rdparty/lzma/C/Ppmd7.c
+++ b/3rdparty/lzma/C/Ppmd7.c
@@ -1,5 +1,5 @@
/* Ppmd7.c -- PPMdH codec
-2021-04-13 : 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"
@@ -14,7 +14,7 @@ This code is based on PPMd var.H (2001): Dmitry Shkarin : Public domain */
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 kInitBinEsc[] = { 0x3CDD, 0x1F3F, 0x59BF, 0x48F3, 0x64A1, 0x5ABC, 0x6632, 0x6051};
+static const UInt16 PPMD7_kInitBinEsc[] = { 0x3CDD, 0x1F3F, 0x59BF, 0x48F3, 0x64A1, 0x5ABC, 0x6632, 0x6051};
#define MAX_FREQ 124
#define UNIT_SIZE 12
@@ -33,7 +33,7 @@ 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_;
@@ -107,14 +107,14 @@ BoolInt Ppmd7_Alloc(CPpmd7 *p, UInt32 size, ISzAllocPtr alloc)
// ---------- 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 GlueFreeBlocks().
- So we use simple CPpmd_Void_Ref instead of CPpmd7_Node in InsertNode() / RemoveNode()
+ 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 InsertNode(CPpmd7 *p, void *node, unsigned indx)
+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];
@@ -124,7 +124,7 @@ static void InsertNode(CPpmd7 *p, void *node, unsigned indx)
}
-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;
@@ -134,32 +134,32 @@ static void *RemoveNode(CPpmd7 *p, unsigned indx)
}
-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);
}
/* we use CPpmd7_Node_Union union to solve XLC -O2 strict pointer aliasing problem */
-typedef union _CPpmd7_Node_Union
+typedef union
{
CPpmd7_Node Node;
CPpmd7_Node_Ref NextRef;
} CPpmd7_Node_Union;
-/* Original PPmdH (Ppmd7) code uses doubly linked list in GlueFreeBlocks()
+/* Original PPmdH (Ppmd7) code uses doubly linked list in Ppmd7_GlueFreeBlocks()
we use single linked list similar to Ppmd8 code */
-static void GlueFreeBlocks(CPpmd7 *p)
+static void Ppmd7_GlueFreeBlocks(CPpmd7 *p)
{
/*
we use first UInt16 field of 12-bytes UNITs as record type stamp
@@ -239,27 +239,27 @@ static void GlueFreeBlocks(CPpmd7 *p)
if (nu == 0)
continue;
for (; nu > 128; nu -= 128, node += 128)
- InsertNode(p, node, PPMD_NUM_INDEXES - 1);
+ Ppmd7_InsertNode(p, node, PPMD_NUM_INDEXES - 1);
if (I2U(i = U2I(nu)) != nu)
{
unsigned k = I2U(--i);
- InsertNode(p, node + k, (unsigned)nu - k - 1);
+ Ppmd7_InsertNode(p, node + k, (unsigned)nu - k - 1);
}
- InsertNode(p, node, i);
+ Ppmd7_InsertNode(p, node, i);
}
}
-MY_NO_INLINE
-static void *AllocUnitsRare(CPpmd7 *p, unsigned indx)
+Z7_NO_INLINE
+static void *Ppmd7_AllocUnitsRare(CPpmd7 *p, unsigned indx)
{
unsigned i;
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;
@@ -277,17 +277,17 @@ static void *AllocUnitsRare(CPpmd7 *p, unsigned indx)
while (p->FreeList[i] == 0);
{
- void *block = RemoveNode(p, i);
- SplitBlock(p, block, i, indx);
+ 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)
{
if (p->FreeList[indx] != 0)
- return RemoveNode(p, indx);
+ return Ppmd7_RemoveNode(p, indx);
{
UInt32 numBytes = U2B(I2U(indx));
Byte *lo = p->LoUnit;
@@ -297,11 +297,11 @@ static void *AllocUnits(CPpmd7 *p, unsigned indx)
return lo;
}
}
- return AllocUnitsRare(p, indx);
+ return Ppmd7_AllocUnitsRare(p, indx);
}
-#define MyMem12Cpy(dest, src, num) \
+#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); }
@@ -315,12 +315,12 @@ 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;
}
*/
@@ -329,14 +329,14 @@ static void *ShrinkUnits(CPpmd7 *p, void *oldPtr, unsigned oldNU, unsigned newNU
#define SUCCESSOR(p) Ppmd_GET_SUCCESSOR(p)
static void SetSuccessor(CPpmd_State *p, CPpmd_Void_Ref v)
{
- Ppmd_SET_SUCCESSOR(p, v);
+ Ppmd_SET_SUCCESSOR(p, v)
}
-MY_NO_INLINE
+Z7_NO_INLINE
static
-void RestartModel(CPpmd7 *p)
+void Ppmd7_RestartModel(CPpmd7 *p)
{
unsigned i, k;
@@ -352,8 +352,8 @@ void RestartModel(CPpmd7 *p)
p->PrevSuccess = 0;
{
- CPpmd7_Context *mc = (CTX_PTR)(void *)(p->HiUnit -= UNIT_SIZE); /* AllocContext(p); */
- CPpmd_State *s = (CPpmd_State *)p->LoUnit; /* AllocUnits(p, PPMD_NUM_INDEXES - 1); */
+ 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;
@@ -391,7 +391,7 @@ void RestartModel(CPpmd7 *p)
{
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;
}
@@ -423,13 +423,13 @@ void Ppmd7_Init(CPpmd7 *p, unsigned maxOrder)
{
p->MaxOrder = maxOrder;
- RestartModel(p);
+ Ppmd7_RestartModel(p);
}
/*
- CreateSuccessors()
+ 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
@@ -445,10 +445,10 @@ void Ppmd7_Init(CPpmd7 *p, unsigned maxOrder)
also it can return pointer to real context of same order,
*/
-MY_NO_INLINE
-static CTX_PTR CreateSuccessors(CPpmd7 *p)
+Z7_NO_INLINE
+static PPMD7_CTX_PTR Ppmd7_CreateSuccessors(CPpmd7 *p)
{
- CTX_PTR c = p->MinContext;
+ PPMD7_CTX_PTR c = p->MinContext;
CPpmd_Byte_Ref upBranch = (CPpmd_Byte_Ref)SUCCESSOR(p->FoundState);
Byte newSym, newFreq;
unsigned numPs = 0;
@@ -522,15 +522,15 @@ static CTX_PTR CreateSuccessors(CPpmd7 *p)
do
{
- CTX_PTR c1;
+ PPMD7_CTX_PTR c1;
/* = AllocContext(p); */
if (p->HiUnit != p->LoUnit)
- c1 = (CTX_PTR)(void *)(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;
}
@@ -550,16 +550,16 @@ static CTX_PTR CreateSuccessors(CPpmd7 *p)
-#define SwapStates(s) \
+#define SWAP_STATES(s) \
{ CPpmd_State tmp = s[0]; s[0] = s[-1]; s[-1] = tmp; }
void Ppmd7_UpdateModel(CPpmd7 *p);
-MY_NO_INLINE
+Z7_NO_INLINE
void Ppmd7_UpdateModel(CPpmd7 *p)
{
CPpmd_Void_Ref maxSuccessor, minSuccessor;
- CTX_PTR c, mc;
+ PPMD7_CTX_PTR c, mc;
unsigned s0, ns;
@@ -592,7 +592,7 @@ void Ppmd7_UpdateModel(CPpmd7 *p)
if (s[0].Freq >= s[-1].Freq)
{
- SwapStates(s);
+ SWAP_STATES(s)
s--;
}
}
@@ -610,10 +610,10 @@ void Ppmd7_UpdateModel(CPpmd7 *p)
{
/* MAX ORDER context */
/* (FoundState->Successor) is RAW-Successor. */
- p->MaxContext = p->MinContext = CreateSuccessors(p);
+ p->MaxContext = p->MinContext = Ppmd7_CreateSuccessors(p);
if (!p->MinContext)
{
- RestartModel(p);
+ Ppmd7_RestartModel(p);
return;
}
SetSuccessor(p->FoundState, REF(p->MinContext));
@@ -629,7 +629,7 @@ void Ppmd7_UpdateModel(CPpmd7 *p)
p->Text = text;
if (text >= p->UnitsStart)
{
- RestartModel(p);
+ Ppmd7_RestartModel(p);
return;
}
maxSuccessor = REF(text);
@@ -645,10 +645,10 @@ void Ppmd7_UpdateModel(CPpmd7 *p)
if (minSuccessor <= maxSuccessor)
{
// minSuccessor is RAW-Successor. So we will create real contexts records:
- CTX_PTR cs = CreateSuccessors(p);
+ PPMD7_CTX_PTR cs = Ppmd7_CreateSuccessors(p);
if (!cs)
{
- RestartModel(p);
+ Ppmd7_RestartModel(p);
return;
}
minSuccessor = REF(cs);
@@ -715,16 +715,16 @@ void Ppmd7_UpdateModel(CPpmd7 *p)
unsigned i = U2I(oldNU);
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);
+ MEM_12_CPY(ptr, oldPtr, oldNU)
+ Ppmd7_InsertNode(p, oldPtr, i);
c->Union4.Stats = STATS_REF(ptr);
}
}
@@ -739,10 +739,10 @@ void Ppmd7_UpdateModel(CPpmd7 *p)
else
{
// instead of One-symbol context we create 2-symbol context
- CPpmd_State *s = (CPpmd_State*)AllocUnits(p, 0);
+ CPpmd_State *s = (CPpmd_State*)Ppmd7_AllocUnits(p, 0);
if (!s)
{
- RestartModel(p);
+ Ppmd7_RestartModel(p);
return;
}
{
@@ -795,8 +795,8 @@ void Ppmd7_UpdateModel(CPpmd7 *p)
-MY_NO_INLINE
-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);
@@ -885,7 +885,7 @@ static void Rescale(CPpmd7 *p)
*s = *stats;
s->Freq = (Byte)freq; // (freq <= 260 / 4)
p->FoundState = s;
- InsertNode(p, stats, U2I(n0));
+ Ppmd7_InsertNode(p, stats, U2I(n0));
return;
}
@@ -899,13 +899,13 @@ static void Rescale(CPpmd7 *p)
{
if (p->FreeList[i1] != 0)
{
- void *ptr = RemoveNode(p, i1);
+ void *ptr = Ppmd7_RemoveNode(p, i1);
p->MinContext->Union4.Stats = STATS_REF(ptr);
- MyMem12Cpy(ptr, (const void *)stats, n1);
- InsertNode(p, stats, i0);
+ MEM_12_CPY(ptr, (const void *)stats, n1)
+ Ppmd7_InsertNode(p, stats, i0);
}
else
- SplitBlock(p, stats, i0, i1);
+ Ppmd7_SplitBlock(p, stats, i0, i1);
}
}
}
@@ -948,9 +948,9 @@ CPpmd_See *Ppmd7_MakeEscFreq(CPpmd7 *p, unsigned numMasked, UInt32 *escFreq)
}
-static void NextContext(CPpmd7 *p)
+static void Ppmd7_NextContext(CPpmd7 *p)
{
- CTX_PTR c = CTX(SUCCESSOR(p->FoundState));
+ PPMD7_CTX_PTR c = CTX(SUCCESSOR(p->FoundState));
if (p->OrderFall == 0 && (const Byte *)c > p->Text)
p->MaxContext = p->MinContext = c;
else
@@ -967,12 +967,12 @@ void Ppmd7_Update1(CPpmd7 *p)
s->Freq = (Byte)freq;
if (freq > s[-1].Freq)
{
- SwapStates(s);
+ SWAP_STATES(s)
p->FoundState = --s;
if (freq > MAX_FREQ)
- Rescale(p);
+ Ppmd7_Rescale(p);
}
- NextContext(p);
+ Ppmd7_NextContext(p);
}
@@ -988,8 +988,8 @@ void Ppmd7_Update1_0(CPpmd7 *p)
freq += 4;
s->Freq = (Byte)freq;
if (freq > MAX_FREQ)
- Rescale(p);
- NextContext(p);
+ Ppmd7_Rescale(p);
+ Ppmd7_NextContext(p);
}
@@ -1000,7 +1000,7 @@ void Ppmd7_UpdateBin(CPpmd7 *p)
p->FoundState->Freq = (Byte)(freq + (freq < 128));
p->PrevSuccess = 1;
p->RunLength++;
- NextContext(p);
+ Ppmd7_NextContext(p);
}
*/
@@ -1013,7 +1013,7 @@ void Ppmd7_Update2(CPpmd7 *p)
p->MinContext->Union2.SummFreq = (UInt16)(p->MinContext->Union2.SummFreq + 4);
s->Freq = (Byte)freq;
if (freq > MAX_FREQ)
- Rescale(p);
+ Ppmd7_Rescale(p);
Ppmd7_UpdateModel(p);
}
@@ -1042,8 +1042,8 @@ 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 RestartModel(), when there is no free memory for allocation.
-And RestartModel() changes the state to orignal start state, with full free block.
+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:
@@ -1051,14 +1051,14 @@ 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]
- - AllocUnitsRare()
+ - Ppmd7_AllocUnitsRare()
-AllocUnits() for CPpmd_State vectors:
+Ppmd7_AllocUnits() for CPpmd_State vectors:
- from FreeList[i]
- from free space (LoUnit) up to (HiUnit)
- - AllocUnitsRare()
+ - Ppmd7_AllocUnitsRare()
-AllocUnitsRare()
+Ppmd7_AllocUnitsRare()
- if (GlueCount == 0)
{ Glue lists, GlueCount = 255, allocate from FreeList[i]] }
- loop for all higher sized FreeList[...] lists
@@ -1093,8 +1093,8 @@ The PPMd code tries to fulfill the condition:
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 Rescale() and *Update*() functions.
-Rescale() can remove symbols only from max-order contexts. So Escape_Freq can increase after multiple calls of Rescale() for
+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,
@@ -1102,3 +1102,21 @@ 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