diff options
Diffstat (limited to '7zip/Compress/Rar29/Original/model.cpp')
-rwxr-xr-x | 7zip/Compress/Rar29/Original/model.cpp | 600 |
1 files changed, 0 insertions, 600 deletions
diff --git a/7zip/Compress/Rar29/Original/model.cpp b/7zip/Compress/Rar29/Original/model.cpp deleted file mode 100755 index e708feb2..00000000 --- a/7zip/Compress/Rar29/Original/model.cpp +++ /dev/null @@ -1,600 +0,0 @@ -/**************************************************************************** - * This file is part of PPMd project * - * Written and distributed to public domain by Dmitry Shkarin 1997, * - * 1999-2000 * - * Contents: model description and encoding/decoding routines * - ****************************************************************************/ - -inline PPM_CONTEXT* PPM_CONTEXT::createChild(ModelPPM *Model,STATE* pStats, - STATE& FirstState) -{ - PPM_CONTEXT* pc = (PPM_CONTEXT*) Model->SubAlloc.AllocContext(); - if ( pc ) - { - pc->NumStats=1; - pc->OneState=FirstState; - pc->Suffix=this; - pStats->Successor=pc; - } - return pc; -} - - -ModelPPM::ModelPPM() -{ - MinContext=NULL; - MaxContext=NULL; - MedContext=NULL; -} - - -void ModelPPM::RestartModelRare() -{ - int i, k, m; - memset(CharMask,0,sizeof(CharMask)); - SubAlloc.InitSubAllocator(); - InitRL=-(MaxOrder < 12 ? MaxOrder:12)-1; - MinContext = MaxContext = (PPM_CONTEXT*) SubAlloc.AllocContext(); - MinContext->Suffix=NULL; - OrderFall=MaxOrder; - MinContext->U.SummFreq=(MinContext->NumStats=256)+1; - FoundState=MinContext->U.Stats=(STATE*)SubAlloc.AllocUnits(256/2); - for (RunLength=InitRL, PrevSuccess=i=0;i < 256;i++) - { - MinContext->U.Stats[i].Symbol=i; - MinContext->U.Stats[i].Freq=1; - MinContext->U.Stats[i].Successor=NULL; - } - - static const ushort InitBinEsc[]={ - 0x3CDD,0x1F3F,0x59BF,0x48F3,0x64A1,0x5ABC,0x6632,0x6051 - }; - - for (i=0;i < 128;i++) - for (k=0;k < 8;k++) - for (m=0;m < 64;m += 8) - BinSumm[i][k+m]=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 ModelPPM::StartModelRare(int MaxOrder) -{ - int i, k, m ,Step; - EscCount=1; -/* - if (MaxOrder < 2) - { - memset(CharMask,0,sizeof(CharMask)); - OrderFall=ModelPPM::MaxOrder; - MinContext=MaxContext; - while (MinContext->Suffix != NULL) - { - MinContext=MinContext->Suffix; - OrderFall--; - } - FoundState=MinContext->U.Stats; - MinContext=MaxContext; - } - else -*/ - { - ModelPPM::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]=i; - for (m=i, k=Step=1;i < 256;i++) - { - NS2Indx[i]=m; - if ( !--k ) - { - k = ++Step; - m++; - } - } - memset(HB2Flag,0,0x40); - memset(HB2Flag+0x40,0x08,0x100-0x40); - DummySEE2Cont.Shift=PERIOD_BITS; - } -} - - -void PPM_CONTEXT::rescale(ModelPPM *Model) -{ - int OldNS=NumStats, i=NumStats-1, Adder, EscFreq; - STATE* p1, * p; - for (p=Model->FoundState;p != U.Stats;p--) - _PPMD_SWAP(p[0],p[-1]); - U.Stats->Freq += 4; - U.SummFreq += 4; - EscFreq=U.SummFreq-p->Freq; - Adder=(Model->OrderFall != 0); - U.SummFreq = (p->Freq=(p->Freq+Adder) >> 1); - do - { - EscFreq -= (++p)->Freq; - U.SummFreq += (p->Freq=(p->Freq+Adder) >> 1); - if (p[0].Freq > p[-1].Freq) - { - STATE tmp=*(p1=p); - do - { - p1[0]=p1[-1]; - } while (--p1 != U.Stats && tmp.Freq > p1[-1].Freq); - *p1=tmp; - } - } while ( --i ); - if (p->Freq == 0) - { - do - { - i++; - } while ((--p)->Freq == 0); - EscFreq += i; - if ((NumStats -= i) == 1) - { - STATE tmp=*U.Stats; - do - { - tmp.Freq-=(tmp.Freq >> 1); - EscFreq>>=1; - } while (EscFreq > 1); - Model->SubAlloc.FreeUnits(U.Stats,(OldNS+1) >> 1); - *(Model->FoundState=&OneState)=tmp; return; - } - } - U.SummFreq += (EscFreq -= (EscFreq >> 1)); - int n0=(OldNS+1) >> 1, n1=(NumStats+1) >> 1; - if (n0 != n1) - U.Stats = (STATE*) Model->SubAlloc.ShrinkUnits(U.Stats,n0,n1); - Model->FoundState=U.Stats; -} - - -inline PPM_CONTEXT* ModelPPM::CreateSuccessors(bool Skip,STATE* p1) -{ -#ifdef __ICL - static -#endif - STATE UpState; - PPM_CONTEXT* pc=MinContext, * UpBranch=FoundState->Successor; - STATE * p, * ps[MAX_O], ** pps=ps; - if ( !Skip ) - { - *pps++ = FoundState; - if ( !pc->Suffix ) - goto NO_LOOP; - } - if ( p1 ) - { - p=p1; - pc=pc->Suffix; - goto LOOP_ENTRY; - } - do - { - pc=pc->Suffix; - if (pc->NumStats != 1) - { - if ((p=pc->U.Stats)->Symbol != FoundState->Symbol) - do - { - p++; - } while (p->Symbol != FoundState->Symbol); - } - else - p=&(pc->OneState); -LOOP_ENTRY: - if (p->Successor != UpBranch) - { - pc=p->Successor; - break; - } - *pps++ = p; - } while ( pc->Suffix ); -NO_LOOP: - if (pps == ps) - return pc; - UpState.Symbol=*(byte*) UpBranch; - UpState.Successor=(PPM_CONTEXT*) (((byte*) UpBranch)+1); - if (pc->NumStats != 1) - { - if ((byte*) pc <= SubAlloc.pText) - return(NULL); - if ((p=pc->U.Stats)->Symbol != UpState.Symbol) - do - { - p++; - } while (p->Symbol != UpState.Symbol); - uint cf=p->Freq-1; - uint s0=pc->U.SummFreq-pc->NumStats-cf; - UpState.Freq=1+((2*cf <= s0)?(5*cf > s0):((2*cf+3*s0-1)/(2*s0))); - } - else - UpState.Freq=pc->OneState.Freq; - do - { - pc = pc->createChild(this,*--pps,UpState); - if ( !pc ) - return NULL; - } while (pps != ps); - return pc; -} - - -inline void ModelPPM::UpdateModel() -{ - STATE fs = *FoundState, *p = NULL; - PPM_CONTEXT *pc, *Successor; - uint ns1, ns, cf, sf, s0; - if (fs.Freq < MAX_FREQ/4 && (pc=MinContext->Suffix) != NULL) - { - if (pc->NumStats != 1) - { - if ((p=pc->U.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->U.SummFreq += 2; - } - } - else - { - p=&(pc->OneState); - p->Freq += (p->Freq < 32); - } - } - if ( !OrderFall ) - { - MinContext=MaxContext=FoundState->Successor=CreateSuccessors(TRUE,p); - if ( !MinContext ) - goto RESTART_MODEL; - return; - } - *SubAlloc.pText++ = fs.Symbol; - Successor = (PPM_CONTEXT*) SubAlloc.pText; - if (SubAlloc.pText >= SubAlloc.FakeUnitsStart) - goto RESTART_MODEL; - if ( fs.Successor ) - { - if ((byte*) fs.Successor <= SubAlloc.pText && - (fs.Successor=CreateSuccessors(FALSE,p)) == NULL) - goto RESTART_MODEL; - if ( !--OrderFall ) - { - Successor=fs.Successor; - SubAlloc.pText -= (MaxContext != MinContext); - } - } - else - { - FoundState->Successor=Successor; - fs.Successor=MinContext; - } - s0=MinContext->U.SummFreq-(ns=MinContext->NumStats)-(fs.Freq-1); - for (pc=MaxContext;pc != MinContext;pc=pc->Suffix) - { - if ((ns1=pc->NumStats) != 1) - { - if ((ns1 & 1) == 0) - { - pc->U.Stats=(STATE*) SubAlloc.ExpandUnits(pc->U.Stats,ns1 >> 1); - if ( !pc->U.Stats ) - goto RESTART_MODEL; - } - pc->U.SummFreq += (2*ns1 < ns)+2*((4*ns1 <= ns) & (pc->U.SummFreq <= 8*ns1)); - } - else - { - p=(STATE*) SubAlloc.AllocUnits(1); - if ( !p ) - goto RESTART_MODEL; - *p=pc->OneState; - pc->U.Stats=p; - if (p->Freq < MAX_FREQ/4-1) - p->Freq += p->Freq; - else - p->Freq = MAX_FREQ-4; - pc->U.SummFreq=p->Freq+InitEsc+(ns > 3); - } - cf=2*fs.Freq*(pc->U.SummFreq+6); - sf=s0+pc->U.SummFreq; - if (cf < 6*sf) - { - cf=1+(cf > sf)+(cf >= 4*sf); - pc->U.SummFreq += 3; - } - else - { - cf=4+(cf >= 9*sf)+(cf >= 12*sf)+(cf >= 15*sf); - pc->U.SummFreq += cf; - } - p=pc->U.Stats+ns1; - p->Successor=Successor; - p->Symbol = fs.Symbol; - p->Freq = cf; - pc->NumStats=++ns1; - } - MaxContext=MinContext=fs.Successor; - return; -RESTART_MODEL: - RestartModelRare(); - EscCount=0; -} - - -// Tabulated escapes for exponential symbol distribution -static 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)) - - - -inline void PPM_CONTEXT::decodeBinSymbol(ModelPPM *Model) -{ - STATE& rs=OneState; - Model->HiBitsFlag=Model->HB2Flag[Model->FoundState->Symbol]; - ushort& bs=Model->BinSumm[rs.Freq-1][Model->PrevSuccess+ - Model->NS2BSIndx[Suffix->NumStats-1]+ - Model->HiBitsFlag+2*Model->HB2Flag[rs.Symbol]+ - ((Model->RunLength >> 26) & 0x20)]; - if (Model->Coder.GetCurrentShiftCount(TOT_BITS) < bs) - { - Model->FoundState=&rs; - rs.Freq += (rs.Freq < 128); - Model->Coder.SubRange.LowCount=0; - Model->Coder.SubRange.HighCount=bs; - bs = SHORT16(bs+INTERVAL-GET_MEAN(bs,PERIOD_BITS,2)); - Model->PrevSuccess=1; - Model->RunLength++; - } - else - { - Model->Coder.SubRange.LowCount=bs; - bs = SHORT16(bs-GET_MEAN(bs,PERIOD_BITS,2)); - Model->Coder.SubRange.HighCount=BIN_SCALE; - Model->InitEsc=ExpEscape[bs >> 10]; - Model->NumMasked=1; - Model->CharMask[rs.Symbol]=Model->EscCount; - Model->PrevSuccess=0; - Model->FoundState=NULL; - } -} - - -inline void PPM_CONTEXT::update1(ModelPPM *Model,STATE* p) -{ - (Model->FoundState=p)->Freq += 4; - U.SummFreq += 4; - if (p[0].Freq > p[-1].Freq) - { - _PPMD_SWAP(p[0],p[-1]); - Model->FoundState=--p; - if (p->Freq > MAX_FREQ) - rescale(Model); - } -} - - - - -inline bool PPM_CONTEXT::decodeSymbol1(ModelPPM *Model) -{ - Model->Coder.SubRange.scale=U.SummFreq; - STATE* p=U.Stats; - int i, HiCnt; - int count=Model->Coder.GetCurrentCount(); - if (count>=Model->Coder.SubRange.scale) - return(false); - if (count < (HiCnt=p->Freq)) - { - Model->PrevSuccess=(2*(Model->Coder.SubRange.HighCount=HiCnt) > Model->Coder.SubRange.scale); - Model->RunLength += Model->PrevSuccess; - (Model->FoundState=p)->Freq=(HiCnt += 4); - U.SummFreq += 4; - if (HiCnt > MAX_FREQ) - rescale(Model); - Model->Coder.SubRange.LowCount=0; - return(true); - } - else - if (Model->FoundState==NULL) - return(false); - Model->PrevSuccess=0; - i=NumStats-1; - while ((HiCnt += (++p)->Freq) <= count) - if (--i == 0) - { - Model->HiBitsFlag=Model->HB2Flag[Model->FoundState->Symbol]; - Model->Coder.SubRange.LowCount=HiCnt; - Model->CharMask[p->Symbol]=Model->EscCount; - i=(Model->NumMasked=NumStats)-1; - Model->FoundState=NULL; - do - { - Model->CharMask[(--p)->Symbol]=Model->EscCount; - } while ( --i ); - Model->Coder.SubRange.HighCount=Model->Coder.SubRange.scale; - return(true); - } - Model->Coder.SubRange.LowCount=(Model->Coder.SubRange.HighCount=HiCnt)-p->Freq; - update1(Model,p); - return(true); -} - - -inline void PPM_CONTEXT::update2(ModelPPM *Model,STATE* p) -{ - (Model->FoundState=p)->Freq += 4; - U.SummFreq += 4; - if (p->Freq > MAX_FREQ) - rescale(Model); - Model->EscCount++; - Model->RunLength=Model->InitRL; -} - - -inline SEE2_CONTEXT* PPM_CONTEXT::makeEscFreq2(ModelPPM *Model,int Diff) -{ - SEE2_CONTEXT* psee2c; - if (NumStats != 256) - { - psee2c=Model->SEE2Cont[Model->NS2Indx[Diff-1]]+ - (Diff < Suffix->NumStats-NumStats)+ - 2*(U.SummFreq < 11*NumStats)+4*(Model->NumMasked > Diff)+ - Model->HiBitsFlag; - Model->Coder.SubRange.scale=psee2c->getMean(); - } - else - { - psee2c=&Model->DummySEE2Cont; - Model->Coder.SubRange.scale=1; - } - return psee2c; -} - - - - -inline bool PPM_CONTEXT::decodeSymbol2(ModelPPM *Model) -{ - int count, HiCnt, i=NumStats-Model->NumMasked; - SEE2_CONTEXT* psee2c=makeEscFreq2(Model,i); - STATE* ps[256], ** pps=ps, * p=U.Stats-1; - HiCnt=0; - do - { - do - { - p++; - } while (Model->CharMask[p->Symbol] == Model->EscCount); - HiCnt += p->Freq; - *pps++ = p; - } while ( --i ); - Model->Coder.SubRange.scale += HiCnt; - count=Model->Coder.GetCurrentCount(); - if (count>=Model->Coder.SubRange.scale) - return(false); - p=*(pps=ps); - if (count < HiCnt) - { - HiCnt=0; - while ((HiCnt += p->Freq) <= count) - p=*++pps; - Model->Coder.SubRange.LowCount = (Model->Coder.SubRange.HighCount=HiCnt)-p->Freq; - psee2c->update(); - update2(Model,p); - } - else - { - Model->Coder.SubRange.LowCount=HiCnt; - Model->Coder.SubRange.HighCount=Model->Coder.SubRange.scale; - i=NumStats-Model->NumMasked; - pps--; - do - { - Model->CharMask[(*++pps)->Symbol]=Model->EscCount; - } while ( --i ); - psee2c->Summ += Model->Coder.SubRange.scale; - Model->NumMasked = NumStats; - } - return(true); -} - - -inline void ModelPPM::ClearMask() -{ - EscCount=1; - memset(CharMask,0,sizeof(CharMask)); -} - - - - -bool ModelPPM::DecodeInit(Unpack *UnpackRead,int &EscChar) -{ - int MaxOrder=UnpackRead->GetChar(); - - // Igor Pavlov - bool Reset = ((MaxOrder & 0x20) != 0); - - int MaxMB; - if (Reset) - MaxMB=UnpackRead->GetChar(); - else - if (SubAlloc.GetAllocatedMemory()==0) - return(false); - if (MaxOrder & 0x40) - EscChar=UnpackRead->GetChar(); - Coder.InitDecoder(UnpackRead); - if (Reset) - { - MaxOrder=(MaxOrder & 0x1f)+1; - if (MaxOrder>16) - MaxOrder=16+(MaxOrder-16)*3; - if (MaxOrder==1) - { - SubAlloc.StopSubAllocator(); - return(false); - } - SubAlloc.StartSubAllocator(MaxMB+1); - StartModelRare(MaxOrder); - } - return(MinContext!=NULL); -} - - -int ModelPPM::DecodeChar() -{ - if ((byte*)MinContext <= SubAlloc.pText || (byte*)MinContext>SubAlloc.HeapEnd) - return(-1); - if (MinContext->NumStats != 1) - { - if (!MinContext->decodeSymbol1(this)) - return(-1); - } - else - MinContext->decodeBinSymbol(this); - Coder.Decode(); - while ( !FoundState ) - { - ARI_DEC_NORMALIZE(Coder.code,Coder.low,Coder.range,Coder.UnpackRead); - do - { - OrderFall++; - MinContext=MinContext->Suffix; - if ((byte*)MinContext <= SubAlloc.pText || (byte*)MinContext>SubAlloc.HeapEnd) - return(-1); - } while (MinContext->NumStats == NumMasked); - if (!MinContext->decodeSymbol2(this)) - return(-1); - Coder.Decode(); - } - int Symbol=FoundState->Symbol; - if (!OrderFall && (byte*) FoundState->Successor > SubAlloc.pText) - MinContext=MaxContext=FoundState->Successor; - else - { - UpdateModel(); - if (EscCount == 0) - ClearMask(); - } - ARI_DEC_NORMALIZE(Coder.code,Coder.low,Coder.range,Coder.UnpackRead); - return(Symbol); -} |