summaryrefslogtreecommitdiffstats
path: root/src/libs/7zip/unix/CPP/7zip/Compress/PpmdContext.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/libs/7zip/unix/CPP/7zip/Compress/PpmdContext.h')
-rw-r--r--src/libs/7zip/unix/CPP/7zip/Compress/PpmdContext.h490
1 files changed, 490 insertions, 0 deletions
diff --git a/src/libs/7zip/unix/CPP/7zip/Compress/PpmdContext.h b/src/libs/7zip/unix/CPP/7zip/Compress/PpmdContext.h
new file mode 100644
index 000000000..cfff53eda
--- /dev/null
+++ b/src/libs/7zip/unix/CPP/7zip/Compress/PpmdContext.h
@@ -0,0 +1,490 @@
+// PpmdContext.h
+// 2009-05-30 : Igor Pavlov : Public domain
+// This code is based on Dmitry Shkarin's PPMdH code (public domain)
+
+#ifndef __COMPRESS_PPMD_CONTEXT_H
+#define __COMPRESS_PPMD_CONTEXT_H
+
+#include "../../Common/Types.h"
+
+#include "PpmdSubAlloc.h"
+#include "RangeCoder.h"
+
+namespace NCompress {
+namespace NPpmd {
+
+const int INT_BITS=7, PERIOD_BITS=7, TOT_BITS=INT_BITS+PERIOD_BITS,
+ INTERVAL=1 << INT_BITS, BIN_SCALE=1 << TOT_BITS, MAX_FREQ=124;
+
+struct SEE2_CONTEXT
+{
+ // SEE-contexts for PPM-contexts with masked symbols
+ UInt16 Summ;
+ Byte Shift, Count;
+ void init(int InitVal) { Summ = (UInt16)(InitVal << (Shift=PERIOD_BITS-4)); Count=4; }
+ unsigned int getMean()
+ {
+ unsigned int RetVal=(Summ >> Shift);
+ Summ = (UInt16)(Summ - RetVal);
+ return RetVal+(RetVal == 0);
+ }
+ void update()
+ {
+ if (Shift < PERIOD_BITS && --Count == 0)
+ {
+ Summ <<= 1;
+ Count = (Byte)(3 << Shift++);
+ }
+ }
+};
+
+struct PPM_CONTEXT
+{
+ UInt16 NumStats; // sizeof(UInt16) > sizeof(Byte)
+ UInt16 SummFreq;
+
+ struct STATE
+ {
+ Byte Symbol, Freq;
+ UInt16 SuccessorLow;
+ UInt16 SuccessorHigh;
+
+ UInt32 GetSuccessor() const { return SuccessorLow | ((UInt32)SuccessorHigh << 16); }
+ void SetSuccessor(UInt32 v)
+ {
+ SuccessorLow = (UInt16)(v & 0xFFFF);
+ SuccessorHigh = (UInt16)((v >> 16) & 0xFFFF);
+ }
+ };
+
+ UInt32 Stats;
+ UInt32 Suffix;
+
+ PPM_CONTEXT* createChild(CSubAllocator &subAllocator, STATE* pStats, STATE& FirstState)
+ {
+ PPM_CONTEXT* pc = (PPM_CONTEXT*) subAllocator.AllocContext();
+ if (pc)
+ {
+ pc->NumStats = 1;
+ pc->oneState() = FirstState;
+ pc->Suffix = subAllocator.GetOffset(this);
+ pStats->SetSuccessor(subAllocator.GetOffsetNoCheck(pc));
+ }
+ return pc;
+ }
+
+ STATE& oneState() const { return (STATE&) SummFreq; }
+};
+
+/////////////////////////////////
+
+const UInt16 InitBinEsc[] =
+ {0x3CDD, 0x1F3F, 0x59BF, 0x48F3, 0x64A1, 0x5ABC, 0x6632, 0x6051};
+
+struct CInfo
+{
+ CSubAllocator SubAllocator;
+ SEE2_CONTEXT SEE2Cont[25][16], DummySEE2Cont;
+ PPM_CONTEXT * MinContext, * MaxContext;
+
+ PPM_CONTEXT::STATE* FoundState; // found next state transition
+ int NumMasked, InitEsc, OrderFall, RunLength, InitRL, MaxOrder;
+ Byte CharMask[256], NS2Indx[256], NS2BSIndx[256], HB2Flag[256];
+ Byte EscCount, PrintCount, PrevSuccess, HiBitsFlag;
+ UInt16 BinSumm[128][64]; // binary SEE-contexts
+
+ UInt16 &GetBinSumm(const PPM_CONTEXT::STATE &rs, int numStates)
+ {
+ HiBitsFlag = HB2Flag[FoundState->Symbol];
+ return BinSumm[rs.Freq - 1][
+ PrevSuccess + NS2BSIndx[numStates - 1] +
+ HiBitsFlag + 2 * HB2Flag[rs.Symbol] +
+ ((RunLength >> 26) & 0x20)];
+ }
+
+ PPM_CONTEXT *GetContext(UInt32 offset) const { return (PPM_CONTEXT *)SubAllocator.GetPtr(offset); }
+ PPM_CONTEXT *GetContextNoCheck(UInt32 offset) const { return (PPM_CONTEXT *)SubAllocator.GetPtrNoCheck(offset); }
+ PPM_CONTEXT::STATE *GetState(UInt32 offset) const { return (PPM_CONTEXT::STATE *)SubAllocator.GetPtr(offset); }
+ PPM_CONTEXT::STATE *GetStateNoCheck(UInt32 offset) const { return (PPM_CONTEXT::STATE *)SubAllocator.GetPtr(offset); }
+
+ void RestartModelRare()
+ {
+ int i, k, m;
+ memset(CharMask,0,sizeof(CharMask));
+ SubAllocator.InitSubAllocator();
+ InitRL = -((MaxOrder < 12) ? MaxOrder : 12) - 1;
+ MinContext = MaxContext = (PPM_CONTEXT*) SubAllocator.AllocContext();
+ MinContext->Suffix = 0;
+ OrderFall = MaxOrder;
+ MinContext->SummFreq = (UInt16)((MinContext->NumStats = 256) + 1);
+ FoundState = (PPM_CONTEXT::STATE*)SubAllocator.AllocUnits(256 / 2);
+ MinContext->Stats = SubAllocator.GetOffsetNoCheck(FoundState);
+ PrevSuccess = 0;
+ for (RunLength = InitRL, i = 0; i < 256; i++)
+ {
+ PPM_CONTEXT::STATE &state = FoundState[i];
+ state.Symbol = (Byte)i;
+ state.Freq = 1;
+ state.SetSuccessor(0);
+ }
+ for (i = 0; i < 128; i++)
+ for (k = 0; k < 8; k++)
+ for ( m=0; m < 64; m += 8)
+ BinSumm[i][k + m] = (UInt16)(BIN_SCALE - InitBinEsc[k] / (i + 2));
+ for (i = 0; i < 25; i++)
+ for (k = 0; k < 16; k++)
+ SEE2Cont[i][k].init(5*i+10);
+ }
+
+ void StartModelRare(int maxOrder)
+ {
+ int i, k, m ,Step;
+ EscCount=PrintCount=1;
+ if (maxOrder < 2)
+ {
+ memset(CharMask,0,sizeof(CharMask));
+ OrderFall = MaxOrder;
+ MinContext = MaxContext;
+ while (MinContext->Suffix != 0)
+ {
+ MinContext = GetContextNoCheck(MinContext->Suffix);
+ OrderFall--;
+ }
+ FoundState = GetState(MinContext->Stats);
+ MinContext = MaxContext;
+ }
+ else
+ {
+ MaxOrder = maxOrder;
+ RestartModelRare();
+ NS2BSIndx[0] = 2 * 0;
+ NS2BSIndx[1] = 2 * 1;
+ memset(NS2BSIndx + 2, 2 * 2, 9);
+ memset(NS2BSIndx + 11, 2 * 3, 256 - 11);
+ for (i = 0; i < 3; i++)
+ NS2Indx[i] = (Byte)i;
+ for (m = i, k = Step = 1; i < 256; i++)
+ {
+ NS2Indx[i] = (Byte)m;
+ if ( !--k )
+ {
+ k = ++Step;
+ m++;
+ }
+ }
+ memset(HB2Flag, 0, 0x40);
+ memset(HB2Flag + 0x40, 0x08, 0x100 - 0x40);
+ DummySEE2Cont.Shift = PERIOD_BITS;
+ }
+ }
+
+ PPM_CONTEXT* CreateSuccessors(bool skip, PPM_CONTEXT::STATE* p1)
+ {
+ // static UpState declaration bypasses IntelC bug
+ // static PPM_CONTEXT::STATE UpState;
+ PPM_CONTEXT::STATE UpState;
+
+ PPM_CONTEXT *pc = MinContext;
+ PPM_CONTEXT *UpBranch = GetContext(FoundState->GetSuccessor());
+ PPM_CONTEXT::STATE * p, * ps[MAX_O], ** pps = ps;
+ if ( !skip )
+ {
+ *pps++ = FoundState;
+ if ( !pc->Suffix )
+ goto NO_LOOP;
+ }
+ if ( p1 )
+ {
+ p = p1;
+ pc = GetContext(pc->Suffix);
+ goto LOOP_ENTRY;
+ }
+ do
+ {
+ pc = GetContext(pc->Suffix);
+ if (pc->NumStats != 1)
+ {
+ if ((p = GetStateNoCheck(pc->Stats))->Symbol != FoundState->Symbol)
+ do { p++; } while (p->Symbol != FoundState->Symbol);
+ }
+ else
+ p = &(pc->oneState());
+LOOP_ENTRY:
+ if (GetContext(p->GetSuccessor()) != UpBranch)
+ {
+ pc = GetContext(p->GetSuccessor());
+ break;
+ }
+ *pps++ = p;
+ }
+ while ( pc->Suffix );
+NO_LOOP:
+ if (pps == ps)
+ return pc;
+ UpState.Symbol = *(Byte*) UpBranch;
+ UpState.SetSuccessor(SubAllocator.GetOffset(UpBranch) + 1);
+ if (pc->NumStats != 1)
+ {
+ if ((p = GetStateNoCheck(pc->Stats))->Symbol != UpState.Symbol)
+ do { p++; } while (p->Symbol != UpState.Symbol);
+ unsigned int cf = p->Freq-1;
+ unsigned int s0 = pc->SummFreq - pc->NumStats - cf;
+ UpState.Freq = (Byte)(1 + ((2 * cf <= s0) ? (5 * cf > s0) :
+ ((2 * cf + 3 * s0 - 1) / (2 * s0))));
+ }
+ else
+ UpState.Freq = pc->oneState().Freq;
+ do
+ {
+ pc = pc->createChild(SubAllocator, *--pps, UpState);
+ if ( !pc )
+ return NULL;
+ }
+ while (pps != ps);
+ return pc;
+ }
+
+ void UpdateModel()
+ {
+ PPM_CONTEXT::STATE fs = *FoundState, * p = NULL;
+ PPM_CONTEXT* pc, * Successor;
+ unsigned int ns1, ns, cf, sf, s0;
+ if (fs.Freq < MAX_FREQ / 4 && MinContext->Suffix != 0)
+ {
+ pc = GetContextNoCheck(MinContext->Suffix);
+
+ if (pc->NumStats != 1)
+ {
+ if ((p = GetStateNoCheck(pc->Stats))->Symbol != fs.Symbol)
+ {
+ do { p++; } while (p->Symbol != fs.Symbol);
+ if (p[0].Freq >= p[-1].Freq)
+ {
+ _PPMD_SWAP(p[0],p[-1]);
+ p--;
+ }
+ }
+ if (p->Freq < MAX_FREQ-9)
+ {
+ p->Freq += 2;
+ pc->SummFreq += 2;
+ }
+ }
+ else
+ {
+ p = &(pc->oneState());
+ p->Freq = (Byte)(p->Freq + ((p->Freq < 32) ? 1 : 0));
+ }
+ }
+ if ( !OrderFall )
+ {
+ MinContext = MaxContext = CreateSuccessors(true, p);
+ FoundState->SetSuccessor(SubAllocator.GetOffset(MinContext));
+ if (MinContext == 0)
+ goto RESTART_MODEL;
+ return;
+ }
+ *SubAllocator.pText++ = fs.Symbol;
+ Successor = (PPM_CONTEXT*) SubAllocator.pText;
+ if (SubAllocator.pText >= SubAllocator.UnitsStart)
+ goto RESTART_MODEL;
+ if (fs.GetSuccessor() != 0)
+ {
+ if ((Byte *)GetContext(fs.GetSuccessor()) <= SubAllocator.pText)
+ {
+ PPM_CONTEXT* cs = CreateSuccessors(false, p);
+ fs.SetSuccessor(SubAllocator.GetOffset(cs));
+ if (cs == NULL)
+ goto RESTART_MODEL;
+ }
+ if ( !--OrderFall )
+ {
+ Successor = GetContext(fs.GetSuccessor());
+ SubAllocator.pText -= (MaxContext != MinContext);
+ }
+ }
+ else
+ {
+ FoundState->SetSuccessor(SubAllocator.GetOffsetNoCheck(Successor));
+ fs.SetSuccessor(SubAllocator.GetOffsetNoCheck(MinContext));
+ }
+ s0 = MinContext->SummFreq - (ns = MinContext->NumStats) - (fs.Freq - 1);
+ for (pc = MaxContext; pc != MinContext; pc = GetContext(pc->Suffix))
+ {
+ if ((ns1 = pc->NumStats) != 1)
+ {
+ if ((ns1 & 1) == 0)
+ {
+ void *ppp = SubAllocator.ExpandUnits(GetState(pc->Stats), ns1 >> 1);
+ pc->Stats = SubAllocator.GetOffset(ppp);
+ if (!ppp)
+ goto RESTART_MODEL;
+ }
+ pc->SummFreq = (UInt16)(pc->SummFreq + (2 * ns1 < ns) + 2 * ((4 * ns1 <= ns) &
+ (pc->SummFreq <= 8 * ns1)));
+ }
+ else
+ {
+ p = (PPM_CONTEXT::STATE*) SubAllocator.AllocUnits(1);
+ if ( !p )
+ goto RESTART_MODEL;
+ *p = pc->oneState();
+ pc->Stats = SubAllocator.GetOffsetNoCheck(p);
+ if (p->Freq < MAX_FREQ / 4 - 1)
+ p->Freq <<= 1;
+ else
+ p->Freq = MAX_FREQ - 4;
+ pc->SummFreq = (UInt16)(p->Freq + InitEsc + (ns > 3));
+ }
+ cf = 2 * fs.Freq * (pc->SummFreq+6);
+ sf = s0 + pc->SummFreq;
+ if (cf < 6 * sf)
+ {
+ cf = 1 + (cf > sf)+(cf >= 4 * sf);
+ pc->SummFreq += 3;
+ }
+ else
+ {
+ cf = 4 + (cf >= 9 * sf) + (cf >= 12 * sf) + (cf >= 15 * sf);
+ pc->SummFreq = (UInt16)(pc->SummFreq + cf);
+ }
+ p = GetState(pc->Stats) + ns1;
+ p->SetSuccessor(SubAllocator.GetOffset(Successor));
+ p->Symbol = fs.Symbol;
+ p->Freq = (Byte)cf;
+ pc->NumStats = (UInt16)++ns1;
+ }
+ MaxContext = MinContext = GetContext(fs.GetSuccessor());
+ return;
+RESTART_MODEL:
+ RestartModelRare();
+ EscCount = 0;
+ PrintCount = 0xFF;
+ }
+
+ void ClearMask()
+ {
+ EscCount = 1;
+ memset(CharMask, 0, sizeof(CharMask));
+ // if (++PrintCount == 0)
+ // PrintInfo(DecodedFile,EncodedFile);
+ }
+
+ void update1(PPM_CONTEXT::STATE* p)
+ {
+ (FoundState = p)->Freq += 4;
+ MinContext->SummFreq += 4;
+ if (p[0].Freq > p[-1].Freq)
+ {
+ _PPMD_SWAP(p[0],p[-1]);
+ FoundState = --p;
+ if (p->Freq > MAX_FREQ)
+ rescale();
+ }
+ }
+
+
+ void update2(PPM_CONTEXT::STATE* p)
+ {
+ (FoundState = p)->Freq += 4;
+ MinContext->SummFreq += 4;
+ if (p->Freq > MAX_FREQ)
+ rescale();
+ EscCount++;
+ RunLength = InitRL;
+ }
+
+ SEE2_CONTEXT* makeEscFreq2(int Diff, UInt32 &scale)
+ {
+ SEE2_CONTEXT* psee2c;
+ if (MinContext->NumStats != 256)
+ {
+ psee2c = SEE2Cont[NS2Indx[Diff-1]] +
+ (Diff < (GetContext(MinContext->Suffix))->NumStats - MinContext->NumStats) +
+ 2 * (MinContext->SummFreq < 11 * MinContext->NumStats) +
+ 4 * (NumMasked > Diff) +
+ HiBitsFlag;
+ scale = psee2c->getMean();
+ }
+ else
+ {
+ psee2c = &DummySEE2Cont;
+ scale = 1;
+ }
+ return psee2c;
+ }
+
+
+
+ void rescale()
+ {
+ int OldNS = MinContext->NumStats, i = MinContext->NumStats - 1, Adder, EscFreq;
+ PPM_CONTEXT::STATE* p1, * p;
+ PPM_CONTEXT::STATE *stats = GetStateNoCheck(MinContext->Stats);
+ for (p = FoundState; p != stats; p--)
+ _PPMD_SWAP(p[0], p[-1]);
+ stats->Freq += 4;
+ MinContext->SummFreq += 4;
+ EscFreq = MinContext->SummFreq - p->Freq;
+ Adder = (OrderFall != 0);
+ p->Freq = (Byte)((p->Freq + Adder) >> 1);
+ MinContext->SummFreq = p->Freq;
+ do
+ {
+ EscFreq -= (++p)->Freq;
+ p->Freq = (Byte)((p->Freq + Adder) >> 1);
+ MinContext->SummFreq = (UInt16)(MinContext->SummFreq + p->Freq);
+ if (p[0].Freq > p[-1].Freq)
+ {
+ PPM_CONTEXT::STATE tmp = *(p1 = p);
+ do
+ {
+ p1[0] = p1[-1];
+ }
+ while (--p1 != stats && tmp.Freq > p1[-1].Freq);
+ *p1 = tmp;
+ }
+ }
+ while ( --i );
+ if (p->Freq == 0)
+ {
+ do { i++; } while ((--p)->Freq == 0);
+ EscFreq += i;
+ MinContext->NumStats = (UInt16)(MinContext->NumStats - i);
+ if (MinContext->NumStats == 1)
+ {
+ PPM_CONTEXT::STATE tmp = *stats;
+ do { tmp.Freq = (Byte)(tmp.Freq - (tmp.Freq >> 1)); EscFreq >>= 1; } while (EscFreq > 1);
+ SubAllocator.FreeUnits(stats, (OldNS+1) >> 1);
+ *(FoundState = &MinContext->oneState()) = tmp; return;
+ }
+ }
+ EscFreq -= (EscFreq >> 1);
+ MinContext->SummFreq = (UInt16)(MinContext->SummFreq + EscFreq);
+ int n0 = (OldNS+1) >> 1, n1 = (MinContext->NumStats + 1) >> 1;
+ if (n0 != n1)
+ MinContext->Stats = SubAllocator.GetOffset(SubAllocator.ShrinkUnits(stats, n0, n1));
+ FoundState = GetState(MinContext->Stats);
+ }
+
+ void NextContext()
+ {
+ PPM_CONTEXT *c = GetContext(FoundState->GetSuccessor());
+ if (!OrderFall && (Byte *)c > SubAllocator.pText)
+ MinContext = MaxContext = c;
+ else
+ {
+ UpdateModel();
+ if (EscCount == 0)
+ ClearMask();
+ }
+ }
+};
+
+// Tabulated escapes for exponential symbol distribution
+const Byte ExpEscape[16]={ 25,14, 9, 7, 5, 5, 4, 4, 4, 3, 3, 3, 2, 2, 2, 2 };
+#define GET_MEAN(SUMM,SHIFT,ROUND) ((SUMM+(1 << (SHIFT-ROUND))) >> (SHIFT))
+
+}}
+
+#endif
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-02 08:56:33 +0000