diff options
Diffstat (limited to 'multiarc/src/formats/7z/C/Ppmd8.c')
| -rwxr-xr-x[-rw-r--r--] | multiarc/src/formats/7z/C/Ppmd8.c | 1116 |
1 files changed, 765 insertions, 351 deletions
diff --git a/multiarc/src/formats/7z/C/Ppmd8.c b/multiarc/src/formats/7z/C/Ppmd8.c index 58141633..fda8b88a 100644..100755 --- a/multiarc/src/formats/7z/C/Ppmd8.c +++ b/multiarc/src/formats/7z/C/Ppmd8.c @@ -1,5 +1,5 @@ /* Ppmd8.c -- PPMdI codec -2018-07-04 : Igor Pavlov : Public domain +2021-04-13 : Igor Pavlov : Public domain This code is based on PPMd var.I (2002): Dmitry Shkarin : Public domain */ #include "Precomp.h" @@ -8,7 +8,12 @@ This code is based on PPMd var.I (2002): Dmitry Shkarin : Public domain */ #include "Ppmd8.h" -const Byte PPMD8_kExpEscape[16] = { 25, 14, 9, 7, 5, 5, 4, 4, 4, 3, 3, 3, 2, 2, 2, 2 }; + + + +MY_ALIGN(16) +static const Byte PPMD8_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}; #define MAX_FREQ 124 @@ -16,13 +21,10 @@ static const UInt16 kInitBinEsc[] = { 0x3CDD, 0x1F3F, 0x59BF, 0x48F3, 0x64A1, 0x #define U2B(nu) ((UInt32)(nu) * UNIT_SIZE) #define U2I(nu) (p->Units2Indx[(size_t)(nu) - 1]) -#define I2U(indx) (p->Indx2Units[indx]) +#define I2U(indx) ((unsigned)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)) @@ -35,34 +37,23 @@ typedef CPpmd8_Context * CTX_PTR; struct CPpmd8_Node_; -typedef - #ifdef PPMD_32BIT - struct CPpmd8_Node_ * - #else - UInt32 - #endif - CPpmd8_Node_Ref; +typedef Ppmd_Ref_Type(struct CPpmd8_Node_) CPpmd8_Node_Ref; typedef struct CPpmd8_Node_ { UInt32 Stamp; + CPpmd8_Node_Ref Next; UInt32 NU; } CPpmd8_Node; -#ifdef PPMD_32BIT - #define NODE(ptr) (ptr) -#else - #define NODE(offs) ((CPpmd8_Node *)(p->Base + (offs))) -#endif - -#define EMPTY_NODE 0xFFFFFFFF +#define NODE(r) Ppmd_GetPtr_Type(p, r, CPpmd8_Node) void Ppmd8_Construct(CPpmd8 *p) { unsigned i, k, m; - p->Base = 0; + p->Base = NULL; for (i = 0, k = 0; i < PPMD_NUM_INDEXES; i++) { @@ -78,39 +69,51 @@ void Ppmd8_Construct(CPpmd8 *p) for (i = 0; i < 5; i++) p->NS2Indx[i] = (Byte)i; + for (m = i, k = 1; i < 260; i++) { p->NS2Indx[i] = (Byte)m; if (--k == 0) k = (++m) - 4; } + + memcpy(p->ExpEscape, PPMD8_kExpEscape, 16); } + void Ppmd8_Free(CPpmd8 *p, ISzAllocPtr alloc) { ISzAlloc_Free(alloc, p->Base); p->Size = 0; - p->Base = 0; + p->Base = NULL; } + BoolInt Ppmd8_Alloc(CPpmd8 *p, UInt32 size, ISzAllocPtr alloc) { if (!p->Base || p->Size != size) { Ppmd8_Free(p, alloc); - p->AlignOffset = - #ifdef PPMD_32BIT - (4 - size) & 3; - #else - 4 - (size & 3); - #endif - if ((p->Base = (Byte *)ISzAlloc_Alloc(alloc, p->AlignOffset + size)) == 0) + p->AlignOffset = (4 - size) & 3; + if ((p->Base = (Byte *)ISzAlloc_Alloc(alloc, p->AlignOffset + size)) == NULL) return False; p->Size = size; } return True; } + + +// ---------- Internal Memory Allocator ---------- + + + + + + +#define EMPTY_NODE 0xFFFFFFFF + + static void InsertNode(CPpmd8 *p, void *node, unsigned indx) { ((CPpmd8_Node *)node)->Stamp = EMPTY_NODE; @@ -120,14 +123,17 @@ static void InsertNode(CPpmd8 *p, void *node, unsigned indx) p->Stamps[indx]++; } + static void *RemoveNode(CPpmd8 *p, unsigned indx) { CPpmd8_Node *node = NODE((CPpmd8_Node_Ref)p->FreeList[indx]); p->FreeList[indx] = node->Next; p->Stamps[indx]--; + return node; } + static void SplitBlock(CPpmd8 *p, void *ptr, unsigned oldIndx, unsigned newIndx) { unsigned i, nu = I2U(oldIndx) - I2U(newIndx); @@ -140,51 +146,96 @@ static void SplitBlock(CPpmd8 *p, void *ptr, unsigned oldIndx, unsigned newIndx) InsertNode(p, ptr, i); } + + + + + + + + + + + + + static void GlueFreeBlocks(CPpmd8 *p) { - CPpmd8_Node_Ref head = 0; - CPpmd8_Node_Ref *prev = &head; - unsigned i; + /* + we use first UInt32 field of 12-bytes UNITs as record type stamp + CPpmd_State { Byte Symbol; Byte Freq; : Freq != 0xFF + CPpmd8_Context { Byte NumStats; Byte Flags; UInt16 SummFreq; : Flags != 0xFF ??? + CPpmd8_Node { UInt32 Stamp : Stamp == 0xFFFFFFFF for free record + : Stamp == 0 for guard + Last 12-bytes UNIT in array is always contains 12-bytes order-0 CPpmd8_Context record + */ + CPpmd8_Node_Ref n; p->GlueCount = 1 << 13; memset(p->Stamps, 0, sizeof(p->Stamps)); - /* Order-0 context is always at top UNIT, so we don't need guard NODE at the end. - All blocks up to p->LoUnit can be free, so we need guard NODE at LoUnit. */ + /* we set guard NODE at LoUnit */ if (p->LoUnit != p->HiUnit) - ((CPpmd8_Node *)p->LoUnit)->Stamp = 0; + ((CPpmd8_Node *)(void *)p->LoUnit)->Stamp = 0; - /* Glue free blocks */ - for (i = 0; i < PPMD_NUM_INDEXES; i++) { - CPpmd8_Node_Ref next = (CPpmd8_Node_Ref)p->FreeList[i]; - p->FreeList[i] = 0; - while (next != 0) + /* Glue free blocks */ + CPpmd8_Node_Ref *prev = &n; + unsigned i; + for (i = 0; i < PPMD_NUM_INDEXES; i++) { - CPpmd8_Node *node = NODE(next); - if (node->NU != 0) + + CPpmd8_Node_Ref next = (CPpmd8_Node_Ref)p->FreeList[i]; + p->FreeList[i] = 0; + while (next != 0) { - CPpmd8_Node *node2; + CPpmd8_Node *node = NODE(next); + UInt32 nu = node->NU; *prev = next; - prev = &(node->Next); - while ((node2 = node + node->NU)->Stamp == EMPTY_NODE) + next = node->Next; + if (nu != 0) { - node->NU += node2->NU; - node2->NU = 0; + CPpmd8_Node *node2; + prev = &(node->Next); + while ((node2 = node + nu)->Stamp == EMPTY_NODE) + { + nu += node2->NU; + node2->NU = 0; + node->NU = nu; + } } } - next = node->Next; } + + *prev = 0; } - *prev = 0; + + + + + + + + + + + + + + + + + + + /* Fill lists of free blocks */ - while (head != 0) + while (n != 0) { - CPpmd8_Node *node = NODE(head); - unsigned nu; - head = node->Next; - nu = node->NU; + CPpmd8_Node *node = NODE(n); + UInt32 nu = node->NU; + unsigned i; + n = node->Next; if (nu == 0) continue; for (; nu > 128; nu -= 128, node += 128) @@ -192,57 +243,70 @@ static void GlueFreeBlocks(CPpmd8 *p) if (I2U(i = U2I(nu)) != nu) { unsigned k = I2U(--i); - InsertNode(p, node + k, nu - k - 1); + InsertNode(p, node + k, (unsigned)nu - k - 1); } InsertNode(p, node, i); } } + +MY_NO_INLINE static void *AllocUnitsRare(CPpmd8 *p, unsigned indx) { unsigned i; - void *retVal; + if (p->GlueCount == 0) { GlueFreeBlocks(p); if (p->FreeList[indx] != 0) return 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 = RemoveNode(p, i); + SplitBlock(p, block, i, indx); + return block; + } } + static void *AllocUnits(CPpmd8 *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)) { - 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); } + #define MyMem12Cpy(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(CPpmd8 *p, void *oldPtr, unsigned oldNU, unsigned newNU) { unsigned i0 = U2I(oldNU); @@ -260,11 +324,13 @@ static void *ShrinkUnits(CPpmd8 *p, void *oldPtr, unsigned oldNU, unsigned newNU return oldPtr; } + static void FreeUnits(CPpmd8 *p, void *ptr, unsigned nu) { InsertNode(p, ptr, U2I(nu)); } + static void SpecialFreeUnit(CPpmd8 *p, void *ptr) { if ((Byte *)ptr != p->UnitsStart) @@ -272,77 +338,91 @@ static void SpecialFreeUnit(CPpmd8 *p, void *ptr) else { #ifdef PPMD8_FREEZE_SUPPORT - *(UInt32 *)ptr = EMPTY_NODE; /* it's used for (Flags == 0xFF) check in RemoveBinContexts */ + *(UInt32 *)ptr = EMPTY_NODE; /* it's used for (Flags == 0xFF) check in RemoveBinContexts() */ #endif p->UnitsStart += UNIT_SIZE; } } + +/* static void *MoveUnitsUp(CPpmd8 *p, void *oldPtr, unsigned nu) { unsigned indx = U2I(nu); void *ptr; - if ((Byte *)oldPtr > p->UnitsStart + 16 * 1024 || REF(oldPtr) > p->FreeList[indx]) + if ((Byte *)oldPtr > p->UnitsStart + (1 << 14) || REF(oldPtr) > p->FreeList[indx]) return oldPtr; ptr = RemoveNode(p, indx); MyMem12Cpy(ptr, oldPtr, nu); - if ((Byte*)oldPtr != p->UnitsStart) + if ((Byte *)oldPtr != p->UnitsStart) InsertNode(p, oldPtr, indx); else p->UnitsStart += U2B(I2U(indx)); return ptr; } +*/ static void ExpandTextArea(CPpmd8 *p) { UInt32 count[PPMD_NUM_INDEXES]; unsigned i; + memset(count, 0, sizeof(count)); if (p->LoUnit != p->HiUnit) - ((CPpmd8_Node *)p->LoUnit)->Stamp = 0; + ((CPpmd8_Node *)(void *)p->LoUnit)->Stamp = 0; { - CPpmd8_Node *node = (CPpmd8_Node *)p->UnitsStart; - for (; node->Stamp == EMPTY_NODE; node += node->NU) + CPpmd8_Node *node = (CPpmd8_Node *)(void *)p->UnitsStart; + while (node->Stamp == EMPTY_NODE) { + UInt32 nu = node->NU; node->Stamp = 0; - count[U2I(node->NU)]++; + count[U2I(nu)]++; + node += nu; } p->UnitsStart = (Byte *)node; } for (i = 0; i < PPMD_NUM_INDEXES; i++) { - CPpmd8_Node_Ref *next = (CPpmd8_Node_Ref *)&p->FreeList[i]; - while (count[i] != 0) + UInt32 cnt = count[i]; + if (cnt == 0) + continue; { - CPpmd8_Node *node = NODE(*next); - while (node->Stamp == 0) + CPpmd8_Node_Ref *prev = (CPpmd8_Node_Ref *)&p->FreeList[i]; + CPpmd8_Node_Ref n = *prev; + p->Stamps[i] -= cnt; + for (;;) { - *next = node->Next; - node = NODE(*next); - p->Stamps[i]--; - if (--count[i] == 0) + CPpmd8_Node *node = NODE(n); + n = node->Next; + if (node->Stamp != 0) + { + prev = &node->Next; + continue; + } + *prev = n; + if (--cnt == 0) break; } - next = &node->Next; } } } -#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); } #define RESET_TEXT(offs) { p->Text = p->Base + p->AlignOffset + (offs); } -static void RestartModel(CPpmd8 *p) +MY_NO_INLINE +static +void RestartModel(CPpmd8 *p) { - unsigned i, k, m, r; + unsigned i, k, m; memset(p->FreeList, 0, sizeof(p->FreeList)); memset(p->Stamps, 0, sizeof(p->Stamps)); @@ -355,30 +435,47 @@ static void RestartModel(CPpmd8 *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 = 255; - p->MinContext->Flags = 0; - 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); + CPpmd8_Context *mc = (CTX_PTR)(void *)(p->HiUnit -= UNIT_SIZE); /* AllocContext(p); */ + CPpmd_State *s = (CPpmd_State *)p->LoUnit; /* AllocUnits(p, PPMD_NUM_INDEXES - 1); */ + + p->LoUnit += U2B(256 / 2); + p->MaxContext = p->MinContext = mc; + p->FoundState = s; + mc->Flags = 0; + mc->NumStats = 256 - 1; + 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); + } } + + + + + + + + + + + for (i = m = 0; m < 25; m++) { while (p->NS2Indx[i] == m) i++; for (k = 0; k < 8; k++) { - UInt16 val = (UInt16)(PPMD_BIN_SCALE - kInitBinEsc[k] / (i + 1)); + unsigned r; UInt16 *dest = p->BinSumm[m] + k; + UInt16 val = (UInt16)(PPMD_BIN_SCALE - kInitBinEsc[k] / (i + 1)); for (r = 0; r < 64; r += 8) dest[r] = val; } @@ -386,50 +483,104 @@ static void RestartModel(CPpmd8 *p) for (i = m = 0; m < 24; m++) { + unsigned summ; + CPpmd_See *s; while (p->NS2Indx[(size_t)i + 3] == m + 3) i++; - for (k = 0; k < 32; k++) + s = p->See[m]; + summ = ((2 * i + 5) << (PPMD_PERIOD_BITS - 4)); + for (k = 0; k < 32; k++, s++) { - CPpmd_See *s = &p->See[m][k]; - s->Summ = (UInt16)((2 * i + 5) << (s->Shift = PPMD_PERIOD_BITS - 4)); + s->Summ = (UInt16)summ; + s->Shift = (PPMD_PERIOD_BITS - 4); s->Count = 7; } } + + p->DummySee.Summ = 0; /* unused */ + p->DummySee.Shift = PPMD_PERIOD_BITS; + p->DummySee.Count = 64; /* unused */ } + void Ppmd8_Init(CPpmd8 *p, unsigned maxOrder, unsigned restoreMethod) { p->MaxOrder = maxOrder; p->RestoreMethod = restoreMethod; RestartModel(p); - p->DummySee.Shift = PPMD_PERIOD_BITS; - p->DummySee.Summ = 0; /* unused */ - p->DummySee.Count = 64; /* unused */ } + +#define FLAG_RESCALED (1 << 2) +// #define FLAG_SYM_HIGH (1 << 3) +#define FLAG_PREV_HIGH (1 << 4) + +#define HiBits_Prepare(sym) ((unsigned)(sym) + 0xC0) + +#define HiBits_Convert_3(flags) (((flags) >> (8 - 3)) & (1 << 3)) +#define HiBits_Convert_4(flags) (((flags) >> (8 - 4)) & (1 << 4)) + +#define PPMD8_HiBitsFlag_3(sym) HiBits_Convert_3(HiBits_Prepare(sym)) +#define PPMD8_HiBitsFlag_4(sym) HiBits_Convert_4(HiBits_Prepare(sym)) + +// #define PPMD8_HiBitsFlag_3(sym) (0x08 * ((sym) >= 0x40)) +// #define PPMD8_HiBitsFlag_4(sym) (0x10 * ((sym) >= 0x40)) + +/* +Refresh() is called when we remove some symbols (successors) in context. +It increases Escape_Freq for sum of all removed symbols. +*/ + static void Refresh(CPpmd8 *p, CTX_PTR ctx, unsigned oldNU, unsigned scale) { unsigned i = ctx->NumStats, escFreq, sumFreq, flags; CPpmd_State *s = (CPpmd_State *)ShrinkUnits(p, STATS(ctx), oldNU, (i + 2) >> 1); - ctx->Stats = REF(s); - #ifdef PPMD8_FREEZE_SUPPORT - /* fixed over Shkarin's code. Fixed code is not compatible with original code for some files in FREEZE mode. */ - scale |= (ctx->SummFreq >= ((UInt32)1 << 15)); - #endif - flags = (ctx->Flags & (0x10 + 0x04 * scale)) + 0x08 * (s->Symbol >= 0x40); - escFreq = ctx->SummFreq - s->Freq; - sumFreq = (s->Freq = (Byte)((s->Freq + scale) >> scale)); + ctx->Union4.Stats = REF(s); + + // #ifdef PPMD8_FREEZE_SUPPORT + /* + (ctx->Union2.SummFreq >= ((UInt32)1 << 15)) can be in FREEZE mode for some files. + It's not good for range coder. So new versions of support fix: + - original PPMdI code rev.1 + + original PPMdI code rev.2 + - 7-Zip default ((PPMD8_FREEZE_SUPPORT is not defined) + + 7-Zip (p->RestoreMethod >= PPMD8_RESTORE_METHOD_FREEZE) + if we use that fixed line, we can lose compatibility with some files created before fix + if we don't use that fixed line, the program can work incorrectly in FREEZE mode in rare case. + */ + // if (p->RestoreMethod >= PPMD8_RESTORE_METHOD_FREEZE) + { + scale |= (ctx->Union2.SummFreq >= ((UInt32)1 << 15)); + } + // #endif + + + + flags = HiBits_Prepare(s->Symbol); + { + unsigned freq = s->Freq; + escFreq = ctx->Union2.SummFreq - freq; + freq = (freq + scale) >> scale; + sumFreq = freq; + s->Freq = (Byte)freq; + } + do { - escFreq -= (++s)->Freq; - sumFreq += (s->Freq = (Byte)((s->Freq + scale) >> scale)); - flags |= 0x08 * (s->Symbol >= 0x40); + unsigned freq = (++s)->Freq; + escFreq -= freq; + freq = (freq + scale) >> scale; + sumFreq += freq; + s->Freq = (Byte)freq; + flags |= HiBits_Prepare(s->Symbol); } while (--i); - ctx->SummFreq = (UInt16)(sumFreq + ((escFreq + scale) >> scale)); - ctx->Flags = (Byte)flags; + + ctx->Union2.SummFreq = (UInt16)(sumFreq + ((escFreq + scale) >> scale)); + ctx->Flags = (Byte)((ctx->Flags & (FLAG_PREV_HIGH + FLAG_RESCALED * scale)) + HiBits_Convert_3(flags)); } + static void SwapStates(CPpmd_State *t1, CPpmd_State *t2) { CPpmd_State tmp = *t1; @@ -437,98 +588,169 @@ static void SwapStates(CPpmd_State *t1, CPpmd_State *t2) *t2 = tmp; } + +/* +CutOff() reduces contexts: + It conversts Successors at MaxOrder to another Contexts to NULL-Successors + It removes RAW-Successors and NULL-Successors that are not Order-0 + and it removes contexts when it has no Successors. + if the (Union4.Stats) is close to (UnitsStart), it moves it up. +*/ + static CPpmd_Void_Ref CutOff(CPpmd8 *p, CTX_PTR ctx, unsigned order) { - int i; - unsigned tmp; - CPpmd_State *s; + int ns = ctx->NumStats; + unsigned nu; + CPpmd_State *stats; - if (!ctx->NumStats) + if (ns == 0) { - s = ONE_STATE(ctx); - if ((Byte *)Ppmd8_GetPtr(p, SUCCESSOR(s)) >= p->UnitsStart) + CPpmd_State *s = ONE_STATE(ctx); + CPpmd_Void_Ref successor = SUCCESSOR(s); + if ((Byte *)Ppmd8_GetPtr(p, successor) >= p->UnitsStart) { if (order < p->MaxOrder) - SetSuccessor(s, CutOff(p, CTX(SUCCESSOR(s)), order + 1)); + successor = CutOff(p, CTX(successor), order + 1); else - SetSuccessor(s, 0); - if (SUCCESSOR(s) || order <= 9) /* O_BOUND */ + successor = 0; + SetSuccessor(s, successor); + if (successor || order <= 9) /* O_BOUND */ return REF(ctx); } SpecialFreeUnit(p, ctx); return 0; } - ctx->Stats = STATS_REF(MoveUnitsUp(p, STATS(ctx), tmp = ((unsigned)ctx->NumStats + 2) >> 1)); + nu = ((unsigned)ns + 2) >> 1; + // ctx->Union4.Stats = STATS_REF(MoveUnitsUp(p, STATS(ctx), nu)); + { + unsigned indx = U2I(nu); + stats = STATS(ctx); - for (s = STATS(ctx) + (i = ctx->NumStats); s >= STATS(ctx); s--) - if ((Byte *)Ppmd8_GetPtr(p, SUCCESSOR(s)) < p->UnitsStart) + if ((UInt32)((Byte *)stats - p->UnitsStart) <= (1 << 14) + && (CPpmd_Void_Ref)ctx->Union4.Stats <= p->FreeList[indx]) { - CPpmd_State *s2 = STATS(ctx) + (i--); - SetSuccessor(s, 0); - SwapStates(s, s2); + void *ptr = RemoveNode(p, indx); + ctx->Union4.Stats = STATS_REF(ptr); + MyMem12Cpy(ptr, (const void *)stats, nu); + if ((Byte *)stats != p->UnitsStart) + InsertNode(p, stats, indx); + else + p->UnitsStart += U2B(I2U(indx)); + stats = ptr; } - else if (order < p->MaxOrder) - SetSuccessor(s, CutOff(p, CTX(SUCCESSOR(s)), order + 1)); - else - SetSuccessor(s, 0); - - if (i != ctx->NumStats && order) + } + + { + CPpmd_State *s = stats + (unsigned)ns; + do + { + CPpmd_Void_Ref successor = SUCCESSOR(s); + if ((Byte *)Ppmd8_GetPtr(p, successor) < p->UnitsStart) + { + CPpmd_State *s2 = stats + (unsigned)(ns--); + if (order) + { + if (s != s2) + *s = *s2; + } + else + { + SwapStates(s, s2); + SetSuccessor(s2, 0); + } + } + else + { + if (order < p->MaxOrder) + SetSuccessor(s, CutOff(p, CTX(successor), order + 1)); + else + SetSuccessor(s, 0); + } + } + while (--s >= stats); + } + + if (ns != ctx->NumStats && order) { - ctx->NumStats = (Byte)i; - s = STATS(ctx); - if (i < 0) + if (ns < 0) { - FreeUnits(p, s, tmp); + FreeUnits(p, stats, nu); SpecialFreeUnit(p, ctx); return 0; } - if (i == 0) + ctx->NumStats = (Byte)ns; + if (ns == 0) { - ctx->Flags = (Byte)((ctx->Flags & 0x10) + 0x08 * (s->Symbol >= 0x40)); - *ONE_STATE(ctx) = *s; - FreeUnits(p, s, tmp); - /* 9.31: the code was fixed. It's was not BUG, if Freq <= MAX_FREQ = 124 */ - ONE_STATE(ctx)->Freq = (Byte)(((unsigned)ONE_STATE(ctx)->Freq + 11) >> 3); + const Byte sym = stats->Symbol; + ctx->Flags = (Byte)((ctx->Flags & FLAG_PREV_HIGH) + PPMD8_HiBitsFlag_3(sym)); + // *ONE_STATE(ctx) = *stats; + ctx->Union2.State2.Symbol = sym; + ctx->Union2.State2.Freq = (Byte)(((unsigned)stats->Freq + 11) >> 3); + ctx->Union4.State4.Successor_0 = stats->Successor_0; + ctx->Union4.State4.Successor_1 = stats->Successor_1; + FreeUnits(p, stats, nu); } else - Refresh(p, ctx, tmp, ctx->SummFreq > 16 * i); + { + Refresh(p, ctx, nu, ctx->Union2.SummFreq > 16 * (unsigned)ns); + } } + return REF(ctx); } + + #ifdef PPMD8_FREEZE_SUPPORT + +/* +RemoveBinContexts() + It conversts Successors at MaxOrder to another Contexts to NULL-Successors + It changes RAW-Successors to NULL-Successors + removes Bin Context without Successor, if suffix of that context is also binary. +*/ + static CPpmd_Void_Ref RemoveBinContexts(CPpmd8 *p, CTX_PTR ctx, unsigned order) { - CPpmd_State *s; if (!ctx->NumStats) { - s = ONE_STATE(ctx); - if ((Byte *)Ppmd8_GetPtr(p, SUCCESSOR(s)) >= p->UnitsStart && order < p->MaxOrder) - SetSuccessor(s, RemoveBinContexts(p, CTX(SUCCESSOR(s)), order + 1)); + CPpmd_State *s = ONE_STATE(ctx); + CPpmd_Void_Ref successor = SUCCESSOR(s); + if ((Byte *)Ppmd8_GetPtr(p, successor) >= p->UnitsStart && order < p->MaxOrder) + successor = RemoveBinContexts(p, CTX(successor), order + 1); else - SetSuccessor(s, 0); + successor = 0; + SetSuccessor(s, successor); /* Suffix context can be removed already, since different (high-order) Successors may refer to same context. So we check Flags == 0xFF (Stamp == EMPTY_NODE) */ - if (!SUCCESSOR(s) && (!SUFFIX(ctx)->NumStats || SUFFIX(ctx)->Flags == 0xFF)) + if (!successor && (!SUFFIX(ctx)->NumStats || SUFFIX(ctx)->Flags == 0xFF)) { FreeUnits(p, ctx, 1); return 0; } - else - return REF(ctx); } - - for (s = STATS(ctx) + ctx->NumStats; s >= STATS(ctx); s--) - if ((Byte *)Ppmd8_GetPtr(p, SUCCESSOR(s)) >= p->UnitsStart && order < p->MaxOrder) - SetSuccessor(s, RemoveBinContexts(p, CTX(SUCCESSOR(s)), order + 1)); - else - SetSuccessor(s, 0); + else + { + CPpmd_State *s = STATS(ctx) + ctx->NumStats; + do + { + CPpmd_Void_Ref successor = SUCCESSOR(s); + if ((Byte *)Ppmd8_GetPtr(p, successor) >= p->UnitsStart && order < p->MaxOrder) + SetSuccessor(s, RemoveBinContexts(p, CTX(successor), order + 1)); + else + SetSuccessor(s, 0); + } + while (--s >= STATS(ctx)); + } return REF(ctx); } + #endif + + static UInt32 GetUsedMemory(const CPpmd8 *p) { UInt32 v = 0; @@ -544,7 +766,8 @@ static UInt32 GetUsedMemory(const CPpmd8 *p) #define RESTORE_MODEL(c1, fSuccessor) RestoreModel(p, c1) #endif -static void RestoreModel(CPpmd8 *p, CTX_PTR c1 + +static void RestoreModel(CPpmd8 *p, CTX_PTR ctxError #ifdef PPMD8_FREEZE_SUPPORT , CTX_PTR fSuccessor #endif @@ -553,36 +776,55 @@ static void RestoreModel(CPpmd8 *p, CTX_PTR c1 CTX_PTR c; CPpmd_State *s; RESET_TEXT(0); - for (c = p->MaxContext; c != c1; c = SUFFIX(c)) + + // we go here in cases of error of allocation for context (c1) + // Order(MinContext) < Order(ctxError) <= Order(MaxContext) + + // We remove last symbol from each of contexts [p->MaxContext ... ctxError) contexts + // So we rollback all created (symbols) before error. + for (c = p->MaxContext; c != ctxError; c = SUFFIX(c)) if (--(c->NumStats) == 0) { s = STATS(c); - c->Flags = (Byte)((c->Flags & 0x10) + 0x08 * (s->Symbol >= 0x40)); - *ONE_STATE(c) = *s; + c->Flags = (Byte)((c->Flags & FLAG_PREV_HIGH) + PPMD8_HiBitsFlag_3(s->Symbol)); + // *ONE_STATE(c) = *s; + c->Union2.State2.Symbol = s->Symbol; + c->Union2.State2.Freq = (Byte)(((unsigned)s->Freq + 11) >> 3); + c->Union4.State4.Successor_0 = s->Successor_0; + c->Union4.State4.Successor_1 = s->Successor_1; + SpecialFreeUnit(p, s); - ONE_STATE(c)->Freq = (Byte)(((unsigned)ONE_STATE(c)->Freq + 11) >> 3); } else - Refresh(p, c, (c->NumStats+3) >> 1, 0); + { + /* Refresh() can increase Escape_Freq on value of Freq of last symbol, that was added before error. + so the largest possible increase for Escape_Freq is (8) from value before ModelUpoadet() */ + Refresh(p, c, ((unsigned)c->NumStats + 3) >> 1, 0); + } + // increase Escape Freq for context [ctxError ... p->MinContext) for (; c != p->MinContext; c = SUFFIX(c)) - if (!c->NumStats) - ONE_STATE(c)->Freq = (Byte)(ONE_STATE(c)->Freq - (ONE_STATE(c)->Freq >> 1)); - else if ((c->SummFreq += 4) > 128 + 4 * c->NumStats) - Refresh(p, c, (c->NumStats + 2) >> 1, 1); + if (c->NumStats == 0) + { + // ONE_STATE(c) + c->Union2.State2.Freq = (Byte)(((unsigned)c->Union2.State2.Freq + 1) >> 1); + } + else if ((c->Union2.SummFreq = (UInt16)(c->Union2.SummFreq + 4)) > 128 + 4 * c->NumStats) + Refresh(p, c, ((unsigned)c->NumStats + 2) >> 1, 1); #ifdef PPMD8_FREEZE_SUPPORT if (p->RestoreMethod > PPMD8_RESTORE_METHOD_FREEZE) { p->MaxContext = fSuccessor; - p->GlueCount += !(p->Stamps[1] & 1); + p->GlueCount += !(p->Stamps[1] & 1); // why? } else if (p->RestoreMethod == PPMD8_RESTORE_METHOD_FREEZE) { while (p->MaxContext->Suffix) p->MaxContext = SUFFIX(p->MaxContext); RemoveBinContexts(p, p->MaxContext, 0); - p->RestoreMethod++; + // we change the current mode to (PPMD8_RESTORE_METHOD_FREEZE + 1) + p->RestoreMethod = PPMD8_RESTORE_METHOD_FREEZE + 1; p->GlueCount = 0; p->OrderFall = p->MaxOrder; } @@ -603,16 +845,19 @@ static void RestoreModel(CPpmd8 *p, CTX_PTR c1 p->GlueCount = 0; p->OrderFall = p->MaxOrder; } + p->MinContext = p->MaxContext; } + + +MY_NO_INLINE static CTX_PTR CreateSuccessors(CPpmd8 *p, BoolInt skip, CPpmd_State *s1, CTX_PTR c) { - CPpmd_State upState; - Byte flags; + CPpmd_Byte_Ref upBranch = (CPpmd_Byte_Ref)SUCCESSOR(p->FoundState); - /* fixed over Shkarin's code. Maybe it could work without + 1 too. */ - CPpmd_State *ps[PPMD8_MAX_ORDER + 1]; + Byte newSym, newFreq, flags; unsigned numPs = 0; + CPpmd_State *ps[PPMD8_MAX_ORDER + 1]; /* fixed over Shkarin's code. Maybe it could work without + 1 too. */ if (!skip) ps[numPs++] = p->FoundState; @@ -622,19 +867,13 @@ static CTX_PTR CreateSuccessors(CPpmd8 *p, BoolInt skip, CPpmd_State *s1, CTX_PT CPpmd_Void_Ref successor; CPpmd_State *s; c = SUFFIX(c); - if (s1) - { - s = s1; - s1 = NULL; - } + + if (s1) { s = s1; s1 = NULL; } else if (c->NumStats != 0) { - for (s = STATS(c); s->Symbol != p->FoundState->Symbol; s++); - if (s->Freq < MAX_FREQ - 9) - { - s->Freq++; - c->SummFreq++; - } + Byte sym = p->FoundState->Symbol; + for (s = STATS(c); s->Symbol != sym; s++); + if (s->Freq < MAX_FREQ - 9) { s->Freq++; c->Union2.SummFreq++; } } else { @@ -644,36 +883,54 @@ static CTX_PTR CreateSuccessors(CPpmd8 *p, BoolInt skip, CPpmd_State *s1, CTX_PT successor = SUCCESSOR(s); if (successor != upBranch) { + c = CTX(successor); if (numPs == 0) + { + + return c; + } break; } ps[numPs++] = s; } - upState.Symbol = *(const Byte *)Ppmd8_GetPtr(p, upBranch); - SetSuccessor(&upState, upBranch + 1); - flags = (Byte)(0x10 * (p->FoundState->Symbol >= 0x40) + 0x08 * (upState.Symbol >= 0x40)); - + + + + + newSym = *(const Byte *)Ppmd8_GetPtr(p, upBranch); + upBranch++; + flags = (Byte)(PPMD8_HiBitsFlag_4(p->FoundState->Symbol) + PPMD8_HiBitsFlag_3(newSym)); + if (c->NumStats == 0) - upState.Freq = ONE_STATE(c)->Freq; + newFreq = c->Union2.State2.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) : ((cf + 2 * s0 - 3) / s0))); + for (s = STATS(c); s->Symbol != newSym; s++); + cf = (UInt32)s->Freq - 1; + s0 = (UInt32)c->Union2.SummFreq - c->NumStats - cf; + /* + + + max(newFreq)= (s->Freq - 1), when (s0 == 1) + + + */ + newFreq = (Byte)(1 + ((2 * cf <= s0) ? (5 * cf > s0) : ((cf + 2 * s0 - 3) / s0))); } + + do { - /* Create Child */ - CTX_PTR c1; /* = AllocContext(p); */ + CTX_PTR c1; + /* = AllocContext(p); */ if (p->HiUnit != p->LoUnit) - c1 = (CTX_PTR)(p->HiUnit -= UNIT_SIZE); + c1 = (CTX_PTR)(void *)(p->HiUnit -= UNIT_SIZE); else if (p->FreeList[0] != 0) c1 = (CTX_PTR)RemoveNode(p, 0); else @@ -682,9 +939,11 @@ static CTX_PTR CreateSuccessors(CPpmd8 *p, BoolInt skip, CPpmd_State *s1, CTX_PT if (!c1) return NULL; } - c1->NumStats = 0; c1->Flags = flags; - *ONE_STATE(c1) = upState; + c1->NumStats = 0; + c1->Union2.State2.Symbol = newSym; + c1->Union2.State2.Freq = newFreq; + SetSuccessor(ONE_STATE(c1), upBranch); c1->Suffix = REF(c); SetSuccessor(ps[--numPs], REF(c1)); c = c1; @@ -694,6 +953,7 @@ static CTX_PTR CreateSuccessors(CPpmd8 *p, BoolInt skip, CPpmd_State *s1, CTX_PT return c; } + static CTX_PTR ReduceOrder(CPpmd8 *p, CPpmd_State *s1, CTX_PTR c) { CPpmd_State *s = NULL; @@ -739,8 +999,8 @@ static CTX_PTR ReduceOrder(CPpmd8 *p, CPpmd_State *s1, CTX_PTR c) do { s++; } while (s->Symbol != p->FoundState->Symbol); 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); } } else @@ -776,33 +1036,42 @@ static CTX_PTR ReduceOrder(CPpmd8 *p, CPpmd_State *s1, CTX_PTR c) p->FoundState = s; successor = CreateSuccessors(p, False, NULL, c); - if (successor == NULL) + if (!successor) SetSuccessor(s, 0); else SetSuccessor(s, REF(successor)); p->FoundState = s2; } - if (p->OrderFall == 1 && c1 == p->MaxContext) { - SetSuccessor(p->FoundState, SUCCESSOR(s)); - p->Text--; + CPpmd_Void_Ref successor = SUCCESSOR(s); + if (p->OrderFall == 1 && c1 == p->MaxContext) + { + SetSuccessor(p->FoundState, successor); + p->Text--; + } + if (successor == 0) + return NULL; + return CTX(successor); } - if (SUCCESSOR(s) == 0) - return NULL; - return CTX(SUCCESSOR(s)); } -static void UpdateModel(CPpmd8 *p) + + +void Ppmd8_UpdateModel(CPpmd8 *p); +MY_NO_INLINE +void Ppmd8_UpdateModel(CPpmd8 *p) { - CPpmd_Void_Ref successor, fSuccessor = SUCCESSOR(p->FoundState); + CPpmd_Void_Ref maxSuccessor, minSuccessor = SUCCESSOR(p->FoundState); CTX_PTR c; unsigned s0, ns, fFreq = p->FoundState->Freq; Byte flag, fSymbol = p->FoundState->Symbol; + { CPpmd_State *s = NULL; - if (p->FoundState->Freq < MAX_FREQ / 4 && p->MinContext->Suffix != 0) { + /* Update Freqs in Suffix Context */ + c = SUFFIX(p->MinContext); if (c->NumStats == 0) @@ -813,91 +1082,134 @@ static void UpdateModel(CPpmd8 *p) } else { + Byte sym = p->FoundState->Symbol; s = STATS(c); - if (s->Symbol != p->FoundState->Symbol) + + if (s->Symbol != sym) { - do { s++; } while (s->Symbol != p->FoundState->Symbol); + do + { + + s++; + } + while (s->Symbol != sym); + if (s[0].Freq >= s[-1].Freq) { SwapStates(&s[0], &s[-1]); 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); } } } c = p->MaxContext; - if (p->OrderFall == 0 && fSuccessor) + if (p->OrderFall == 0 && minSuccessor) { CTX_PTR cs = CreateSuccessors(p, True, s, p->MinContext); - if (cs == 0) + if (!cs) { SetSuccessor(p->FoundState, 0); - RESTORE_MODEL(c, CTX(fSuccessor)); - } - else - { - SetSuccessor(p->FoundState, REF(cs)); - p->MaxContext = cs; + RESTORE_MODEL(c, CTX(minSuccessor)); + return; } + SetSuccessor(p->FoundState, REF(cs)); + p->MinContext = p->MaxContext = cs; return; } - *p->Text++ = p->FoundState->Symbol; - successor = REF(p->Text); - if (p->Text >= p->UnitsStart) + + + { - RESTORE_MODEL(c, CTX(fSuccessor)); /* check it */ - return; + Byte *text = p->Text; + *text++ = p->FoundState->Symbol; + p->Text = text; + if (text >= p->UnitsStart) + { + RESTORE_MODEL(c, CTX(minSuccessor)); /* check it */ + return; + } + maxSuccessor = REF(text); } - - if (!fSuccessor) + + if (!minSuccessor) { CTX_PTR cs = ReduceOrder(p, s, p->MinContext); - if (cs == NULL) + if (!cs) { - RESTORE_MODEL(c, 0); + RESTORE_MODEL(c, NULL); return; } - fSuccessor = REF(cs); + minSuccessor = REF(cs); } - else if ((Byte *)Ppmd8_GetPtr(p, fSuccessor) < p->UnitsStart) + else if ((Byte *)Ppmd8_GetPtr(p, minSuccessor) < p->UnitsStart) { CTX_PTR cs = CreateSuccessors(p, False, s, p->MinContext); - if (cs == NULL) + if (!cs) { - RESTORE_MODEL(c, 0); + RESTORE_MODEL(c, NULL); return; } - fSuccessor = REF(cs); + minSuccessor = REF(cs); } if (--p->OrderFall == 0) { - successor = fSuccessor; + maxSuccessor = minSuccessor; p->Text -= (p->MaxContext != p->MinContext); } #ifdef PPMD8_FREEZE_SUPPORT else if (p->RestoreMethod > PPMD8_RESTORE_METHOD_FREEZE) { - successor = fSuccessor; + maxSuccessor = minSuccessor; RESET_TEXT(0); p->OrderFall = 0; } #endif + } + + + + + + + + + + - s0 = p->MinContext->SummFreq - (ns = p->MinContext->NumStats) - fFreq; - flag = (Byte)(0x08 * (fSymbol >= 0x40)); + + + + + + + + + + + + + + + + + + flag = (Byte)(PPMD8_HiBitsFlag_3(fSymbol)); + s0 = p->MinContext->Union2.SummFreq - (ns = p->MinContext->NumStats) - fFreq; for (; c != p->MinContext; c = SUFFIX(c)) { unsigned ns1; - UInt32 cf, sf; + UInt32 sum; + if ((ns1 = c->NumStats) != 0) { if ((ns1 & 1) != 0) @@ -911,91 +1223,133 @@ static void UpdateModel(CPpmd8 *p) void *oldPtr; if (!ptr) { - RESTORE_MODEL(c, CTX(fSuccessor)); + RESTORE_MODEL(c, CTX(minSuccessor)); return; } oldPtr = STATS(c); MyMem12Cpy(ptr, oldPtr, oldNU); InsertNode(p, oldPtr, i); - c->Stats = STATS_REF(ptr); + c->Union4.Stats = STATS_REF(ptr); } } - c->SummFreq = (UInt16)(c->SummFreq + (3 * ns1 + 1 < ns)); + sum = c->Union2.SummFreq; + /* max increase of Escape_Freq is 1 here. + an average increase is 1/3 per symbol */ + sum += (3 * ns1 + 1 < ns); + /* original PPMdH uses 16-bit variable for (sum) here. + But (sum < ???). Do we need to truncate (sum) to 16-bit */ + // sum = (UInt16)sum; } else { - CPpmd_State *s2 = (CPpmd_State*)AllocUnits(p, 0); - if (!s2) + + CPpmd_State *s = (CPpmd_State*)AllocUnits(p, 0); + if (!s) { - RESTORE_MODEL(c, CTX(fSuccessor)); + RESTORE_MODEL(c, CTX(minSuccessor)); return; } - *s2 = *ONE_STATE(c); - c->Stats = REF(s2); - if (s2->Freq < MAX_FREQ / 4 - 1) - s2->Freq <<= 1; - else - s2->Freq = MAX_FREQ - 4; - c->SummFreq = (UInt16)(s2->Freq + p->InitEsc + (ns > 2)); - } - cf = 2 * fFreq * (c->SummFreq + 6); - sf = (UInt32)s0 + c->SummFreq; - if (cf < 6 * sf) - { - cf = 1 + (cf > sf) + (cf >= 4 * sf); - c->SummFreq += 4; - } - 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; + + s->Freq = (Byte)freq; + + sum = freq + p->InitEsc + (ns > 2); // Ppmd8 (> 2) + } } + { - CPpmd_State *s2 = STATS(c) + ns1 + 1; - SetSuccessor(s2, successor); - s2->Symbol = fSymbol; - s2->Freq = (Byte)cf; - c->Flags |= flag; + CPpmd_State *s = STATS(c) + ns1 + 1; + UInt32 cf = 2 * (sum + 6) * (UInt32)fFreq; + UInt32 sf = (UInt32)s0 + sum; + s->Symbol = fSymbol; c->NumStats = (Byte)(ns1 + 1); + SetSuccessor(s, maxSuccessor); + c->Flags |= flag; + if (cf < 6 * sf) + { + cf = (unsigned)1 + (cf > sf) + (cf >= 4 * sf); + sum += 4; + /* It can add (1, 2, 3) to Escape_Freq */ + } + else + { + cf = (unsigned)4 + (cf > 9 * sf) + (cf > 12 * sf) + (cf > 15 * sf); + sum += cf; + } + + c->Union2.SummFreq = (UInt16)sum; + s->Freq = (Byte)cf; } + } - p->MaxContext = p->MinContext = CTX(fSuccessor); + p->MaxContext = p->MinContext = CTX(minSuccessor); } + + +MY_NO_INLINE static void Rescale(CPpmd8 *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 - #ifdef PPMD8_FREEZE_SUPPORT - || p->RestoreMethod > PPMD8_RESTORE_METHOD_FREEZE - #endif - ); - s->Freq = (Byte)((s->Freq + adder) >> 1); + sumFreq = s->Freq; + escFreq = p->MinContext->Union2.SummFreq - sumFreq; + + + + + + adder = (p->OrderFall != 0); + + #ifdef PPMD8_FREEZE_SUPPORT + adder |= (p->RestoreMethod > PPMD8_RESTORE_METHOD_FREEZE); + #endif + + sumFreq = (sumFreq + 4 + adder) >> 1; i = p->MinContext->NumStats; + s->Freq = (Byte)sumFreq; + 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; } } @@ -1003,49 +1357,89 @@ static void Rescale(CPpmd8 *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 */ + CPpmd8_Context *mc; + unsigned numStats, numStatsNew, n0, n1; + + i = 0; do { i++; } while ((--s)->Freq == 0); + + + + escFreq += i; - p->MinContext->NumStats = (Byte)(p->MinContext->NumStats - i); - if (p->MinContext->NumStats == 0) + mc = p->MinContext; + numStats = mc->NumStats; + numStatsNew = numStats - i; + mc->NumStats = (Byte)(numStatsNew); + n0 = (numStats + 2) >> 1; + + if (numStatsNew == 0) { - CPpmd_State tmp = *stats; - tmp.Freq = (Byte)((2 * tmp.Freq + escFreq - 1) / escFreq); - if (tmp.Freq > MAX_FREQ / 3) - tmp.Freq = MAX_FREQ / 3; - InsertNode(p, stats, U2I((numStats + 2) >> 1)); - p->MinContext->Flags = (Byte)((p->MinContext->Flags & 0x10) + 0x08 * (tmp.Symbol >= 0x40)); - *(p->FoundState = ONE_STATE(p->MinContext)) = tmp; + + unsigned freq = (2 * (unsigned)stats->Freq + escFreq - 1) / escFreq; + if (freq > MAX_FREQ / 3) + freq = MAX_FREQ / 3; + mc->Flags = (Byte)((mc->Flags & FLAG_PREV_HIGH) + PPMD8_HiBitsFlag_3(stats->Symbol)); + + + + + + s = ONE_STATE(mc); + *s = *stats; + s->Freq = (Byte)freq; + p->FoundState = s; + InsertNode(p, stats, U2I(n0)); return; } - n0 = (numStats + 2) >> 1; - n1 = (p->MinContext->NumStats + 2) >> 1; + + n1 = (numStatsNew + 2) >> 1; if (n0 != n1) - p->MinContext->Stats = STATS_REF(ShrinkUnits(p, stats, n0, n1)); - p->MinContext->Flags &= ~0x08; - p->MinContext->Flags |= 0x08 * ((s = STATS(p->MinContext))->Symbol >= 0x40); - i = p->MinContext->NumStats; - do { p->MinContext->Flags |= 0x08*((++s)->Symbol >= 0x40); } while (--i); + mc->Union4.Stats = STATS_REF(ShrinkUnits(p, stats, n0, n1)); + { + // here we are for max order only. So Ppmd8_MakeEscFreq() doesn't use mc->Flags + // but we still need current (Flags & FLAG_PREV_HIGH), if we will convert context to 1-symbol context later. + /* + unsigned flags = HiBits_Prepare((s = STATS(mc))->Symbol); + i = mc->NumStats; + do { flags |= HiBits_Prepare((++s)->Symbol); } while (--i); + mc->Flags = (Byte)((mc->Flags & ~FLAG_SYM_HIGH) + HiBits_Convert_3(flags)); + */ + } + } + + + + + + + { + CPpmd8_Context *mc = p->MinContext; + mc->Union2.SummFreq = (UInt16)(sumFreq + escFreq - (escFreq >> 1)); + mc->Flags |= FLAG_RESCALED; + p->FoundState = STATS(mc); } - p->MinContext->SummFreq = (UInt16)(sumFreq + escFreq - (escFreq >> 1)); - p->MinContext->Flags |= 0x4; - p->FoundState = STATS(p->MinContext); } + CPpmd_See *Ppmd8_MakeEscFreq(CPpmd8 *p, unsigned numMasked1, UInt32 *escFreq) { CPpmd_See *see; - if (p->MinContext->NumStats != 0xFF) + const CPpmd8_Context *mc = p->MinContext; + unsigned numStats = mc->NumStats; + if (numStats != 0xFF) { - see = p->See[(size_t)(unsigned)p->NS2Indx[(size_t)(unsigned)p->MinContext->NumStats + 2] - 3] + - (p->MinContext->SummFreq > 11 * ((unsigned)p->MinContext->NumStats + 1)) + - 2 * (unsigned)(2 * (unsigned)p->MinContext->NumStats < - ((unsigned)SUFFIX(p->MinContext)->NumStats + numMasked1)) + - p->MinContext->Flags; + // (3 <= numStats + 2 <= 256) (3 <= NS2Indx[3] and NS2Indx[256] === 26) + see = p->See[(size_t)(unsigned)p->NS2Indx[(size_t)numStats + 2] - 3] + + (mc->Union2.SummFreq > 11 * (numStats + 1)) + + 2 * (unsigned)(2 * numStats < ((unsigned)SUFFIX(mc)->NumStats + numMasked1)) + + mc->Flags; + { - 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); } } @@ -1057,67 +1451,87 @@ CPpmd_See *Ppmd8_MakeEscFreq(CPpmd8 *p, unsigned numMasked1, UInt32 *escFreq) return see; } + static void NextContext(CPpmd8 *p) { CTX_PTR c = CTX(SUCCESSOR(p->FoundState)); - if (p->OrderFall == 0 && (Byte *)c >= p->UnitsStart) - p->MinContext = p->MaxContext = c; + if (p->OrderFall == 0 && (const Byte *)c >= p->UnitsStart) + p->MaxContext = p->MinContext = c; else - { - UpdateModel(p); - p->MinContext = p->MaxContext; - } + Ppmd8_UpdateModel(p); } + void Ppmd8_Update1(CPpmd8 *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]); + SwapStates(s, &s[-1]); p->FoundState = --s; - if (s->Freq > MAX_FREQ) + if (freq > MAX_FREQ) Rescale(p); } NextContext(p); } + void Ppmd8_Update1_0(CPpmd8 *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) + CPpmd_State *s = p->FoundState; + CPpmd8_Context *mc = p->MinContext; + unsigned freq = s->Freq; + unsigned summFreq = mc->Union2.SummFreq; + p->PrevSuccess = (2 * freq >= summFreq); // Ppmd8 (>=) + p->RunLength += (int)p->PrevSuccess; + mc->Union2.SummFreq = (UInt16)(summFreq + 4); + freq += 4; + s->Freq = (Byte)freq; + if (freq > MAX_FREQ) Rescale(p); NextContext(p); } + +/* void Ppmd8_UpdateBin(CPpmd8 *p) { - p->FoundState->Freq = (Byte)(p->FoundState->Freq + (p->FoundState->Freq < 196)); + unsigned freq = p->FoundState->Freq; + p->FoundState->Freq = (Byte)(freq + (freq < 196)); // Ppmd8 (196) p->PrevSuccess = 1; p->RunLength++; NextContext(p); } +*/ void Ppmd8_Update2(CPpmd8 *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 = p->MaxContext; + p->MinContext->Union2.SummFreq = (UInt16)(p->MinContext->Union2.SummFreq + 4); + s->Freq = (Byte)freq; + if (freq > MAX_FREQ) + Rescale(p); + Ppmd8_UpdateModel(p); } /* H->I changes: NS2Indx - GlewCount, and Glue method + GlueCount, and Glue method BinSum See / EscFreq CreateSuccessors updates more suffix contexts - UpdateModel consts. + Ppmd8_UpdateModel consts. PrevSuccess Update + +Flags: + (1 << 2) - the Context was Rescaled + (1 << 3) - there is symbol in Stats with (sym >= 0x40) in + (1 << 4) - main symbol of context is (sym >= 0x40) */ |