code.vuplus.com Git - vuplus_xbmc/blob - lib/UnrarXLib/model.cpp

   1 /****************************************************************************
   2  *  This file is part of PPMd project                                       *
   3  *  Written and distributed to public domain by Dmitry Shkarin 1997,        *
   4  *  1999-2000                                                               *
   5  *  Contents: model description and encoding/decoding routines              *
   6  ****************************************************************************/
   7
   8 inline PPM_CONTEXT* PPM_CONTEXT::createChild(ModelPPM *Model,STATE* pStats,
   9                                              STATE& FirstState)
  10 {
  11   PPM_CONTEXT* pc = (PPM_CONTEXT*) Model->SubAlloc.AllocContext();
  12   if ( pc )
  13   {
  14     pc->NumStats=1;
  15     pc->OneState=FirstState;
  16     pc->Suffix=this;
  17     pStats->Successor=pc;
  18   }
  19   return pc;
  20 }
  21
  22
  23 ModelPPM::ModelPPM()
  24 {
  25   MinContext=NULL;
  26   MaxContext=NULL;
  27   MedContext=NULL;
  28 }
  29
  30
  31 void ModelPPM::RestartModelRare()
  32 {
  33   int i, k, m;
  34   memset(CharMask,0,sizeof(CharMask));
  35   SubAlloc.InitSubAllocator();
  36   InitRL=-(MaxOrder < 12 ? MaxOrder:12)-1;
  37   MinContext = MaxContext = (PPM_CONTEXT*) SubAlloc.AllocContext();
  38   if (!MinContext)
  39     return;
  40   MinContext->Suffix=NULL;
  41   OrderFall=MaxOrder;
  42   MinContext->U.SummFreq=(MinContext->NumStats=256)+1;
  43   FoundState=MinContext->U.Stats=(STATE*)SubAlloc.AllocUnits(256/2);
  44   for (RunLength=InitRL, PrevSuccess=i=0;i < 256;i++)
  45   {
  46     MinContext->U.Stats[i].Symbol=i;
  47     MinContext->U.Stats[i].Freq=1;
  48     MinContext->U.Stats[i].Successor=NULL;
  49   }
  50
  51   static const ushort InitBinEsc[]={
  52     0x3CDD,0x1F3F,0x59BF,0x48F3,0x64A1,0x5ABC,0x6632,0x6051
  53   };
  54
  55   for (i=0;i < 128;i++)
  56     for (k=0;k < 8;k++)
  57       for (m=0;m < 64;m += 8)
  58         BinSumm[i][k+m]=BIN_SCALE-InitBinEsc[k]/(i+2);
  59   for (i=0;i < 25;i++)
  60     for (k=0;k < 16;k++)
  61       SEE2Cont[i][k].init(5*i+10);
  62 }
  63
  64
  65 void ModelPPM::StartModelRare(int MaxOrder)
  66 {
  67   int i, k, m ,Step;
  68   EscCount=1;
  69 /*
  70   if (MaxOrder < 2)
  71   {
  72     memset(CharMask,0,sizeof(CharMask));
  73     OrderFall=ModelPPM::MaxOrder;
  74     MinContext=MaxContext;
  75     while (MinContext->Suffix != NULL)
  76     {
  77       MinContext=MinContext->Suffix;
  78       OrderFall--;
  79     }
  80     FoundState=MinContext->U.Stats;
  81     MinContext=MaxContext;
  82   }
  83   else
  84 */
  85   {
  86     ModelPPM::MaxOrder=MaxOrder;
  87     RestartModelRare();
  88     NS2BSIndx[0]=2*0;
  89     NS2BSIndx[1]=2*1;
  90     memset(NS2BSIndx+2,2*2,9);
  91     memset(NS2BSIndx+11,2*3,256-11);
  92     for (i=0;i < 3;i++)
  93       NS2Indx[i]=i;
  94     for (m=i, k=Step=1;i < 256;i++)
  95     {
  96       NS2Indx[i]=m;
  97       if ( !--k )
  98       {
  99         k = ++Step;
 100         m++;
 101       }
 102     }
 103     memset(HB2Flag,0,0x40);
 104     memset(HB2Flag+0x40,0x08,0x100-0x40);
 105     DummySEE2Cont.Shift=PERIOD_BITS;
 106   }
 107 }
 108
 109
 110 void PPM_CONTEXT::rescale(ModelPPM *Model)
 111 {
 112   int OldNS=NumStats, i=NumStats-1, Adder, EscFreq;
 113   STATE* p1, * p;
 114   for (p=Model->FoundState;p != U.Stats;p--)
 115     _PPMD_SWAP(p[0],p[-1]);
 116   U.Stats->Freq += 4;
 117   U.SummFreq += 4;
 118   EscFreq=U.SummFreq-p->Freq;
 119   Adder=(Model->OrderFall != 0);
 120   U.SummFreq = (p->Freq=(p->Freq+Adder) >> 1);
 121   do
 122   {
 123     EscFreq -= (++p)->Freq;
 124     U.SummFreq += (p->Freq=(p->Freq+Adder) >> 1);
 125     if (p[0].Freq > p[-1].Freq)
 126     {
 127       STATE tmp=*(p1=p);
 128       do
 129       {
 130         p1[0]=p1[-1];
 131       } while (--p1 != U.Stats && tmp.Freq > p1[-1].Freq);
 132       *p1=tmp;
 133     }
 134   } while ( --i );
 135   if (p->Freq == 0)
 136   {
 137     do
 138     {
 139       i++;
 140     } while ((--p)->Freq == 0);
 141     EscFreq += i;
 142     if ((NumStats -= i) == 1)
 143     {
 144       STATE tmp=*U.Stats;
 145       do
 146       {
 147         tmp.Freq-=(tmp.Freq >> 1);
 148         EscFreq>>=1;
 149       } while (EscFreq > 1);
 150       Model->SubAlloc.FreeUnits(U.Stats,(OldNS+1) >> 1);
 151       *(Model->FoundState=&OneState)=tmp;  return;
 152     }
 153   }
 154   U.SummFreq += (EscFreq -= (EscFreq >> 1));
 155   int n0=(OldNS+1) >> 1, n1=(NumStats+1) >> 1;
 156   if (n0 != n1)
 157     U.Stats = (STATE*) Model->SubAlloc.ShrinkUnits(U.Stats,n0,n1);
 158   Model->FoundState=U.Stats;
 159 }
 160
 161
 162 inline PPM_CONTEXT* ModelPPM::CreateSuccessors(bool Skip,STATE* p1)
 163 {
 164 #ifdef __ICL
 165   static
 166 #endif
 167   STATE UpState;
 168   PPM_CONTEXT* pc=MinContext, * UpBranch=FoundState->Successor;
 169   STATE * p, * ps[MAX_O], ** pps=ps;
 170   if ( !Skip )
 171   {
 172     *pps++ = FoundState;
 173     if ( !pc->Suffix )
 174       goto NO_LOOP;
 175   }
 176   if ( p1 )
 177   {
 178     p=p1;
 179     pc=pc->Suffix;
 180     goto LOOP_ENTRY;
 181   }
 182   do
 183   {
 184     pc=pc->Suffix;
 185     if (pc->NumStats != 1)
 186     {
 187       if ((p=pc->U.Stats)->Symbol != FoundState->Symbol)
 188         do
 189         {
 190           p++;
 191         } while (p->Symbol != FoundState->Symbol);
 192     }
 193     else
 194       p=&(pc->OneState);
 195 LOOP_ENTRY:
 196     if (p->Successor != UpBranch)
 197     {
 198       pc=p->Successor;
 199       break;
 200     }
 201     *pps++ = p;
 202   } while ( pc->Suffix );
 203 NO_LOOP:
 204   if (pps == ps)
 205     return pc;
 206   UpState.Symbol=*(byte*) UpBranch;
 207   UpState.Successor=(PPM_CONTEXT*) (((byte*) UpBranch)+1);
 208   if (pc->NumStats != 1)
 209   {
 210     if ((byte*) pc <= SubAlloc.pText)
 211       return(NULL);
 212     if ((p=pc->U.Stats)->Symbol != UpState.Symbol)
 213     do
 214     {
 215       p++;
 216     } while (p->Symbol != UpState.Symbol);
 217     uint cf=p->Freq-1;
 218     uint s0=pc->U.SummFreq-pc->NumStats-cf;
 219     UpState.Freq=1+((2*cf <= s0)?(5*cf > s0):((2*cf+3*s0-1)/(2*s0)));
 220   }
 221   else
 222     UpState.Freq=pc->OneState.Freq;
 223   do
 224   {
 225     pc = pc->createChild(this,*--pps,UpState);
 226     if ( !pc )
 227       return NULL;
 228   } while (pps != ps);
 229   return pc;
 230 }
 231
 232
 233 inline void ModelPPM::UpdateModel()
 234 {
 235   STATE fs = *FoundState, *p = NULL;
 236   PPM_CONTEXT *pc, *Successor;
 237   uint ns1, ns, cf, sf, s0;
 238   if (fs.Freq < MAX_FREQ/4 && (pc=MinContext->Suffix) != NULL)
 239   {
 240     if (pc->NumStats != 1)
 241     {
 242       if ((p=pc->U.Stats)->Symbol != fs.Symbol)
 243       {
 244         do
 245         {
 246           p++;
 247         } while (p->Symbol != fs.Symbol);
 248         if (p[0].Freq >= p[-1].Freq)
 249         {
 250           _PPMD_SWAP(p[0],p[-1]);
 251           p--;
 252         }
 253       }
 254       if (p->Freq < MAX_FREQ-9)
 255       {
 256         p->Freq += 2;
 257         pc->U.SummFreq += 2;
 258       }
 259     }
 260     else
 261     {
 262       p=&(pc->OneState);
 263       p->Freq += (p->Freq < 32);
 264     }
 265   }
 266   if ( !OrderFall )
 267   {
 268     MinContext=MaxContext=FoundState->Successor=CreateSuccessors(TRUE,p);
 269     if ( !MinContext )
 270       goto RESTART_MODEL;
 271     return;
 272   }
 273   *SubAlloc.pText++ = fs.Symbol;
 274   Successor = (PPM_CONTEXT*) SubAlloc.pText;
 275   if (SubAlloc.pText >= SubAlloc.FakeUnitsStart)
 276     goto RESTART_MODEL;
 277   if ( fs.Successor )
 278   {
 279     if ((byte*) fs.Successor <= SubAlloc.pText &&
 280         (fs.Successor=CreateSuccessors(FALSE,p)) == NULL)
 281       goto RESTART_MODEL;
 282     if ( !--OrderFall )
 283     {
 284       Successor=fs.Successor;
 285       SubAlloc.pText -= (MaxContext != MinContext);
 286     }
 287   }
 288   else
 289   {
 290     FoundState->Successor=Successor;
 291     fs.Successor=MinContext;
 292   }
 293   s0=MinContext->U.SummFreq-(ns=MinContext->NumStats)-(fs.Freq-1);
 294   for (pc=MaxContext;pc != MinContext;pc=pc->Suffix)
 295   {
 296     if ((ns1=pc->NumStats) != 1)
 297     {
 298       if ((ns1 & 1) == 0)
 299       {
 300         pc->U.Stats=(STATE*) SubAlloc.ExpandUnits(pc->U.Stats,ns1 >> 1);
 301         if ( !pc->U.Stats )
 302           goto RESTART_MODEL;
 303       }
 304       pc->U.SummFreq += (2*ns1 < ns)+2*((4*ns1 <= ns) & (pc->U.SummFreq <= 8*ns1));
 305     }
 306     else
 307     {
 308       p=(STATE*) SubAlloc.AllocUnits(1);
 309       if ( !p )
 310         goto RESTART_MODEL;
 311       *p=pc->OneState;
 312       pc->U.Stats=p;
 313       if (p->Freq < MAX_FREQ/4-1)
 314         p->Freq += p->Freq;
 315       else
 316         p->Freq  = MAX_FREQ-4;
 317       pc->U.SummFreq=p->Freq+InitEsc+(ns > 3);
 318     }
 319     cf=2*fs.Freq*(pc->U.SummFreq+6);
 320     sf=s0+pc->U.SummFreq;
 321     if (cf < 6*sf)
 322     {
 323       cf=1+(cf > sf)+(cf >= 4*sf);
 324       pc->U.SummFreq += 3;
 325     }
 326     else
 327     {
 328       cf=4+(cf >= 9*sf)+(cf >= 12*sf)+(cf >= 15*sf);
 329       pc->U.SummFreq += cf;
 330     }
 331     p=pc->U.Stats+ns1;
 332     p->Successor=Successor;
 333     p->Symbol = fs.Symbol;
 334     p->Freq = cf;
 335     pc->NumStats=++ns1;
 336   }
 337   MaxContext=MinContext=fs.Successor;
 338   return;
 339 RESTART_MODEL:
 340   RestartModelRare();
 341   EscCount=0;
 342 }
 343
 344
 345 // Tabulated escapes for exponential symbol distribution
 346 static const byte ExpEscape[16]={ 25,14, 9, 7, 5, 5, 4, 4, 4, 3, 3, 3, 2, 2, 2, 2 };
 347 #define GET_MEAN(SUMM,SHIFT,ROUND) ((SUMM+(1 << (SHIFT-ROUND))) >> (SHIFT))
 348
 349
 350
 351 inline void PPM_CONTEXT::decodeBinSymbol(ModelPPM *Model)
 352 {
 353   STATE& rs=OneState;
 354   Model->HiBitsFlag=Model->HB2Flag[Model->FoundState->Symbol];
 355   ushort& bs=Model->BinSumm[rs.Freq-1][Model->PrevSuccess+
 356            Model->NS2BSIndx[Suffix->NumStats-1]+
 357            Model->HiBitsFlag+2*Model->HB2Flag[rs.Symbol]+
 358            ((Model->RunLength >> 26) & 0x20)];
 359   if (Model->Coder.GetCurrentShiftCount(TOT_BITS) < bs)
 360   {
 361     Model->FoundState=&rs;
 362     rs.Freq += (rs.Freq < 128);
 363     Model->Coder.SubRange.LowCount=0;
 364     Model->Coder.SubRange.HighCount=bs;
 365     bs = SHORT16(bs+INTERVAL-GET_MEAN(bs,PERIOD_BITS,2));
 366     Model->PrevSuccess=1;
 367     Model->RunLength++;
 368   }
 369   else
 370   {
 371     Model->Coder.SubRange.LowCount=bs;
 372     bs = SHORT16(bs-GET_MEAN(bs,PERIOD_BITS,2));
 373     Model->Coder.SubRange.HighCount=BIN_SCALE;
 374     Model->InitEsc=ExpEscape[bs >> 10];
 375     Model->NumMasked=1;
 376     Model->CharMask[rs.Symbol]=Model->EscCount;
 377     Model->PrevSuccess=0;
 378     Model->FoundState=NULL;
 379   }
 380 }
 381
 382
 383 inline void PPM_CONTEXT::update1(ModelPPM *Model,STATE* p)
 384 {
 385   (Model->FoundState=p)->Freq += 4;
 386   U.SummFreq += 4;
 387   if (p[0].Freq > p[-1].Freq)
 388   {
 389     _PPMD_SWAP(p[0],p[-1]);
 390     Model->FoundState=--p;
 391     if (p->Freq > MAX_FREQ)
 392       rescale(Model);
 393   }
 394 }
 395
 396
 397
 398
 399 inline bool PPM_CONTEXT::decodeSymbol1(ModelPPM *Model)
 400 {
 401   Model->Coder.SubRange.scale=U.SummFreq;
 402   STATE* p=U.Stats;
 403   int i, HiCnt;
 404   int count=Model->Coder.GetCurrentCount();
 405   if ((uint)count>=Model->Coder.SubRange.scale)
 406     return(false);
 407   if (count < (HiCnt=p->Freq))
 408   {
 409     Model->PrevSuccess=(2*(Model->Coder.SubRange.HighCount=HiCnt) > Model->Coder.SubRange.scale);
 410     Model->RunLength += Model->PrevSuccess;
 411     (Model->FoundState=p)->Freq=(HiCnt += 4);
 412     U.SummFreq += 4;
 413     if (HiCnt > MAX_FREQ)
 414       rescale(Model);
 415     Model->Coder.SubRange.LowCount=0;
 416     return(true);
 417   }
 418   else
 419     if (Model->FoundState==NULL)
 420       return(false);
 421   Model->PrevSuccess=0;
 422   i=NumStats-1;
 423   while ((HiCnt += (++p)->Freq) <= count)
 424     if (--i == 0)
 425     {
 426       Model->HiBitsFlag=Model->HB2Flag[Model->FoundState->Symbol];
 427       Model->Coder.SubRange.LowCount=HiCnt;
 428       Model->CharMask[p->Symbol]=Model->EscCount;
 429       i=(Model->NumMasked=NumStats)-1;
 430       Model->FoundState=NULL;
 431       do
 432       {
 433         Model->CharMask[(--p)->Symbol]=Model->EscCount;
 434       } while ( --i );
 435       Model->Coder.SubRange.HighCount=Model->Coder.SubRange.scale;
 436       return(true);
 437     }
 438   Model->Coder.SubRange.LowCount=(Model->Coder.SubRange.HighCount=HiCnt)-p->Freq;
 439   update1(Model,p);
 440   return(true);
 441 }
 442
 443
 444 inline void PPM_CONTEXT::update2(ModelPPM *Model,STATE* p)
 445 {
 446   (Model->FoundState=p)->Freq += 4;
 447   U.SummFreq += 4;
 448   if (p->Freq > MAX_FREQ)
 449     rescale(Model);
 450   Model->EscCount++;
 451   Model->RunLength=Model->InitRL;
 452 }
 453
 454
 455 inline SEE2_CONTEXT* PPM_CONTEXT::makeEscFreq2(ModelPPM *Model,int Diff)
 456 {
 457   SEE2_CONTEXT* psee2c;
 458   if (NumStats != 256)
 459   {
 460     psee2c=Model->SEE2Cont[Model->NS2Indx[Diff-1]]+
 461            (Diff < Suffix->NumStats-NumStats)+
 462            2*(U.SummFreq < 11*NumStats)+4*(Model->NumMasked > Diff)+
 463            Model->HiBitsFlag;
 464     Model->Coder.SubRange.scale=psee2c->getMean();
 465   }
 466   else
 467   {
 468     psee2c=&Model->DummySEE2Cont;
 469     Model->Coder.SubRange.scale=1;
 470   }
 471   return psee2c;
 472 }
 473
 474
 475
 476
 477 inline bool PPM_CONTEXT::decodeSymbol2(ModelPPM *Model)
 478 {
 479   int count, HiCnt, i=NumStats-Model->NumMasked;
 480   SEE2_CONTEXT* psee2c=makeEscFreq2(Model,i);
 481   STATE* ps[256], ** pps=ps, * p=U.Stats-1;
 482   HiCnt=0;
 483   do
 484   {
 485     do
 486     {
 487       p++;
 488     } while (Model->CharMask[p->Symbol] == Model->EscCount);
 489     HiCnt += p->Freq;
 490     *pps++ = p;
 491   } while ( --i );
 492   Model->Coder.SubRange.scale += HiCnt;
 493   count=Model->Coder.GetCurrentCount();
 494   if ((uint)count>=Model->Coder.SubRange.scale)
 495     return(false);
 496   p=*(pps=ps);
 497   if (count < HiCnt)
 498   {
 499     HiCnt=0;
 500     while ((HiCnt += p->Freq) <= count)
 501       p=*++pps;
 502     Model->Coder.SubRange.LowCount = (Model->Coder.SubRange.HighCount=HiCnt)-p->Freq;
 503     psee2c->update();
 504     update2(Model,p);
 505   }
 506   else
 507   {
 508     Model->Coder.SubRange.LowCount=HiCnt;
 509     Model->Coder.SubRange.HighCount=Model->Coder.SubRange.scale;
 510     i=NumStats-Model->NumMasked;
 511     pps--;
 512     do
 513     {
 514       Model->CharMask[(*++pps)->Symbol]=Model->EscCount;
 515     } while ( --i );
 516     psee2c->Summ += Model->Coder.SubRange.scale;
 517     Model->NumMasked = NumStats;
 518   }
 519   return(true);
 520 }
 521
 522
 523 inline void ModelPPM::ClearMask()
 524 {
 525   EscCount=1;
 526   memset(CharMask,0,sizeof(CharMask));
 527 }
 528
 529
 530
 531
 532 bool ModelPPM::DecodeInit(Unpack *UnpackRead,int &EscChar)
 533 {
 534   int MaxOrder=UnpackRead->GetChar();
 535   bool Reset=(MaxOrder & 0x20);
 536
 537   int MaxMB=0;
 538   if (Reset)
 539     MaxMB=UnpackRead->GetChar();
 540   else
 541     if (SubAlloc.GetAllocatedMemory()==0)
 542       return(false);
 543   if (MaxOrder & 0x40)
 544     EscChar=UnpackRead->GetChar();
 545   Coder.InitDecoder(UnpackRead);
 546   if (Reset)
 547   {
 548     MaxOrder=(MaxOrder & 0x1f)+1;
 549     if (MaxOrder>16)
 550       MaxOrder=16+(MaxOrder-16)*3;
 551     if (MaxOrder==1)
 552     {
 553       SubAlloc.StopSubAllocator();
 554       return(false);
 555     }
 556     SubAlloc.StartSubAllocator(MaxMB+1);
 557     StartModelRare(MaxOrder);
 558   }
 559   return(MinContext!=NULL);
 560 }
 561
 562
 563 int ModelPPM::DecodeChar()
 564 {
 565   if ((byte*)MinContext <= SubAlloc.pText || (byte*)MinContext>SubAlloc.HeapEnd)
 566     return(-1);
 567   if (MinContext->NumStats != 1)
 568   {
 569     if (!MinContext->decodeSymbol1(this))
 570       return(-1);
 571   }
 572   else
 573     MinContext->decodeBinSymbol(this);
 574   Coder.Decode();
 575   while ( !FoundState )
 576   {
 577     ARI_DEC_NORMALIZE(Coder.code,Coder.low,Coder.range,Coder.UnpackRead);
 578     do
 579     {
 580       OrderFall++;
 581       MinContext=MinContext->Suffix;
 582       if ((byte*)MinContext <= SubAlloc.pText || (byte*)MinContext>SubAlloc.HeapEnd)
 583         return(-1);
 584     } while (MinContext->NumStats == NumMasked);
 585     if (!MinContext->decodeSymbol2(this))
 586       return(-1);
 587     Coder.Decode();
 588   }
 589   int Symbol=FoundState->Symbol;
 590   if (!OrderFall && (byte*) FoundState->Successor > SubAlloc.pText)
 591     MinContext=MaxContext=FoundState->Successor;
 592   else
 593   {
 594     UpdateModel();
 595     if (EscCount == 0)
 596       ClearMask();
 597   }
 598   ARI_DEC_NORMALIZE(Coder.code,Coder.low,Coder.range,Coder.UnpackRead);
 599   return(Symbol);
 600 }