Mercurial > vba-linux

     1 // PpmdContext.h

     2 // This code is based on Dmitry Shkarin's PPMdH code

     3 

     4 #ifndef __COMPRESS_PPMD_CONTEXT_H

     5 #define __COMPRESS_PPMD_CONTEXT_H

     6 

     7 #include "../../Common/Types.h"

     8 

     9 #include "PpmdSubAlloc.h"

    10 #include "RangeCoder.h"

    11 

    12 namespace NCompress {

    13 namespace NPpmd {

    14 

    15 const int INT_BITS=7, PERIOD_BITS=7, TOT_BITS=INT_BITS+PERIOD_BITS,

    16         INTERVAL=1 << INT_BITS, BIN_SCALE=1 << TOT_BITS, MAX_FREQ=124;

    17 

    18 struct SEE2_CONTEXT

    19 {

    20   // SEE-contexts for PPM-contexts with masked symbols

    21   UInt16 Summ;

    22   Byte Shift, Count;

    23   void init(int InitVal) { Summ = (UInt16)(InitVal << (Shift=PERIOD_BITS-4)); Count=4; }

    24   unsigned int getMean()

    25   {

    26     unsigned int RetVal=(Summ >> Shift);

    27     Summ = (UInt16)(Summ - RetVal);

    28     return RetVal+(RetVal == 0);

    29   }

    30   void update()

    31   {

    32     if (Shift < PERIOD_BITS && --Count == 0)

    33     {

    34       Summ <<= 1;

    35       Count = (Byte)(3 << Shift++);

    36     }

    37   }

    38 };

    39 

    40 struct PPM_CONTEXT

    41 {

    42   UInt16 NumStats; // sizeof(UInt16) > sizeof(Byte)

    43   UInt16 SummFreq;

    44   

    45   struct STATE

    46   {

    47     Byte Symbol, Freq;

    48     UInt16 SuccessorLow;

    49     UInt16 SuccessorHigh;

    50 

    51     UInt32 GetSuccessor() const { return SuccessorLow | ((UInt32)SuccessorHigh << 16); }

    52     void SetSuccessor(UInt32 v)

    53     {

    54       SuccessorLow = (UInt16)(v & 0xFFFF);

    55       SuccessorHigh = (UInt16)((v >> 16) & 0xFFFF);

    56     }

    57   };

    58   

    59   UInt32 Stats;

    60   UInt32 Suffix;

    61   

    62   PPM_CONTEXT* createChild(CSubAllocator &subAllocator, STATE* pStats, STATE& FirstState)

    63   {

    64     PPM_CONTEXT* pc = (PPM_CONTEXT*) subAllocator.AllocContext();

    65     if (pc)

    66     {

    67       pc->NumStats = 1;

    68       pc->oneState() = FirstState;

    69       pc->Suffix = subAllocator.GetOffset(this);

    70       pStats->SetSuccessor(subAllocator.GetOffsetNoCheck(pc));

    71     }

    72     return pc;

    73   }

    74 

    75   STATE& oneState() const { return (STATE&) SummFreq; }

    76 };

    77 

    78 /////////////////////////////////

    79 

    80 const UInt16 InitBinEsc[] =

    81   {0x3CDD, 0x1F3F, 0x59BF, 0x48F3, 0x64A1, 0x5ABC, 0x6632, 0x6051};

    82 

    83 struct CInfo

    84 {

    85   CSubAllocator SubAllocator;

    86   SEE2_CONTEXT SEE2Cont[25][16], DummySEE2Cont;

    87   PPM_CONTEXT * MinContext, * MaxContext;

    88 

    89   PPM_CONTEXT::STATE* FoundState;      // found next state transition

    90   int NumMasked, InitEsc, OrderFall, RunLength, InitRL, MaxOrder;

    91   Byte CharMask[256], NS2Indx[256], NS2BSIndx[256], HB2Flag[256];

    92   Byte EscCount, PrintCount, PrevSuccess, HiBitsFlag;

    93   UInt16 BinSumm[128][64];               // binary SEE-contexts

    94 

    95   UInt16 &GetBinSumm(const PPM_CONTEXT::STATE &rs, int numStates)

    96   {

    97     HiBitsFlag = HB2Flag[FoundState->Symbol];

    98     return BinSumm[rs.Freq - 1][

    99          PrevSuccess + NS2BSIndx[numStates - 1] +

   100          HiBitsFlag + 2 * HB2Flag[rs.Symbol] +

   101          ((RunLength >> 26) & 0x20)];

   102   }

   103 

   104   PPM_CONTEXT *GetContext(UInt32 offset) const { return (PPM_CONTEXT *)SubAllocator.GetPtr(offset); }

   105   PPM_CONTEXT *GetContextNoCheck(UInt32 offset) const { return (PPM_CONTEXT *)SubAllocator.GetPtrNoCheck(offset); }

   106   PPM_CONTEXT::STATE *GetState(UInt32 offset) const { return (PPM_CONTEXT::STATE *)SubAllocator.GetPtr(offset); }

   107   PPM_CONTEXT::STATE *GetStateNoCheck(UInt32 offset) const { return (PPM_CONTEXT::STATE *)SubAllocator.GetPtr(offset); }

   108 

   109   void RestartModelRare()

   110   {

   111     int i, k, m;

   112     memset(CharMask,0,sizeof(CharMask));

   113     SubAllocator.InitSubAllocator();

   114     InitRL = -((MaxOrder < 12) ? MaxOrder : 12) - 1;

   115     MinContext = MaxContext = (PPM_CONTEXT*) SubAllocator.AllocContext();

   116     MinContext->Suffix = 0;

   117     OrderFall = MaxOrder;

   118     MinContext->SummFreq = (UInt16)((MinContext->NumStats = 256) + 1);

   119     FoundState = (PPM_CONTEXT::STATE*)SubAllocator.AllocUnits(256 / 2);

   120     MinContext->Stats = SubAllocator.GetOffsetNoCheck(FoundState);

   121     PrevSuccess = 0;

   122     for (RunLength = InitRL, i = 0; i < 256; i++)

   123     {

   124       PPM_CONTEXT::STATE &state = FoundState[i];

   125       state.Symbol = (Byte)i;

   126       state.Freq = 1;

   127       state.SetSuccessor(0);

   128     }

   129     for (i = 0; i < 128; i++)

   130         for (k = 0; k < 8; k++)

   131             for ( m=0; m < 64; m += 8)

   132                 BinSumm[i][k + m] = (UInt16)(BIN_SCALE - InitBinEsc[k] / (i + 2));

   133     for (i = 0; i < 25; i++)

   134         for (k = 0; k < 16; k++)

   135             SEE2Cont[i][k].init(5*i+10);

   136   }

   137 

   138   void StartModelRare(int maxOrder)

   139   {

   140     int i, k, m ,Step;

   141     EscCount=PrintCount=1;

   142     if (maxOrder < 2)

   143     {

   144         memset(CharMask,0,sizeof(CharMask));

   145         OrderFall = MaxOrder;

   146         MinContext = MaxContext;

   147         while (MinContext->Suffix != 0)

   148         {

   149           MinContext = GetContextNoCheck(MinContext->Suffix);

   150           OrderFall--;

   151         }

   152         FoundState = GetState(MinContext->Stats);

   153         MinContext = MaxContext;

   154     }

   155     else

   156     {

   157         MaxOrder = maxOrder;

   158         RestartModelRare();

   159         NS2BSIndx[0] = 2 * 0;

   160         NS2BSIndx[1] = 2 * 1;

   161         memset(NS2BSIndx + 2, 2 * 2, 9);

   162         memset(NS2BSIndx + 11, 2 * 3, 256 - 11);

   163         for (i = 0; i < 3; i++)

   164           NS2Indx[i] = (Byte)i;

   165         for (m = i, k = Step = 1; i < 256; i++)

   166         {

   167             NS2Indx[i] = (Byte)m;

   168             if ( !--k )

   169             {

   170               k = ++Step;

   171               m++;

   172             }

   173         }

   174         memset(HB2Flag, 0, 0x40);

   175         memset(HB2Flag + 0x40, 0x08, 0x100 - 0x40);

   176         DummySEE2Cont.Shift = PERIOD_BITS;

   177     }

   178   }

   179 

   180   PPM_CONTEXT* CreateSuccessors(bool skip, PPM_CONTEXT::STATE* p1)

   181   {

   182     // static UpState declaration bypasses IntelC bug

   183     // static PPM_CONTEXT::STATE UpState;

   184     PPM_CONTEXT::STATE UpState;

   185 

   186     PPM_CONTEXT *pc = MinContext;

   187     PPM_CONTEXT *UpBranch = GetContext(FoundState->GetSuccessor());

   188     PPM_CONTEXT::STATE * p, * ps[MAX_O], ** pps = ps;

   189     if ( !skip )

   190     {

   191         *pps++ = FoundState;

   192         if ( !pc->Suffix )

   193           goto NO_LOOP;

   194     }

   195     if ( p1 )

   196     {

   197         p = p1;

   198         pc = GetContext(pc->Suffix);

   199         goto LOOP_ENTRY;

   200     }

   201     do

   202     {

   203         pc = GetContext(pc->Suffix);

   204         if (pc->NumStats != 1)

   205         {

   206             if ((p = GetStateNoCheck(pc->Stats))->Symbol != FoundState->Symbol)

   207                 do { p++; } while (p->Symbol != FoundState->Symbol);

   208         }

   209         else

   210           p = &(pc->oneState());

   211 LOOP_ENTRY:

   212         if (GetContext(p->GetSuccessor()) != UpBranch)

   213         {

   214             pc = GetContext(p->GetSuccessor());

   215             break;

   216         }

   217         *pps++ = p;

   218     }

   219     while ( pc->Suffix );

   220 NO_LOOP:

   221     if (pps == ps)

   222       return pc;

   223     UpState.Symbol = *(Byte*) UpBranch;

   224     UpState.SetSuccessor(SubAllocator.GetOffset(UpBranch) + 1);

   225     if (pc->NumStats != 1)

   226     {

   227         if ((p = GetStateNoCheck(pc->Stats))->Symbol != UpState.Symbol)

   228                 do { p++; } while (p->Symbol != UpState.Symbol);

   229         unsigned int cf = p->Freq-1;

   230         unsigned int s0 = pc->SummFreq - pc->NumStats - cf;

   231         UpState.Freq = (Byte)(1 + ((2 * cf <= s0) ? (5 * cf > s0) :

   232             ((2 * cf + 3 * s0 - 1) / (2 * s0))));

   233     }

   234     else

   235       UpState.Freq = pc->oneState().Freq;

   236     do

   237     {

   238         pc = pc->createChild(SubAllocator, *--pps, UpState);

   239         if ( !pc )

   240           return NULL;

   241     }

   242     while (pps != ps);

   243     return pc;

   244   }

   245 

   246   void UpdateModel()

   247   {

   248     PPM_CONTEXT::STATE fs = *FoundState, * p = NULL;

   249     PPM_CONTEXT* pc, * Successor;

   250     unsigned int ns1, ns, cf, sf, s0;

   251     if (fs.Freq < MAX_FREQ / 4 && MinContext->Suffix != 0)

   252     {

   253         pc = GetContextNoCheck(MinContext->Suffix);

   254       

   255         if (pc->NumStats != 1)

   256         {

   257             if ((p = GetStateNoCheck(pc->Stats))->Symbol != fs.Symbol)

   258             {

   259                 do { p++; } while (p->Symbol != fs.Symbol);

   260                 if (p[0].Freq >= p[-1].Freq)

   261                 {

   262                     _PPMD_SWAP(p[0],p[-1]);

   263                     p--;

   264                 }

   265             }

   266             if (p->Freq < MAX_FREQ-9)

   267             {

   268                 p->Freq += 2;

   269                 pc->SummFreq += 2;

   270             }

   271         }

   272         else

   273         {

   274             p = &(pc->oneState());

   275             p->Freq = (Byte)(p->Freq + ((p->Freq < 32) ? 1 : 0));

   276         }

   277     }

   278     if ( !OrderFall )

   279     {

   280         MinContext = MaxContext = CreateSuccessors(true, p);

   281         FoundState->SetSuccessor(SubAllocator.GetOffset(MinContext));

   282         if (MinContext == 0)

   283           goto RESTART_MODEL;

   284         return;

   285     }

   286     *SubAllocator.pText++ = fs.Symbol;

   287     Successor = (PPM_CONTEXT*) SubAllocator.pText;

   288     if (SubAllocator.pText >= SubAllocator.UnitsStart)

   289       goto RESTART_MODEL;

   290     if (fs.GetSuccessor() != 0)

   291     {

   292         if ((Byte *)GetContext(fs.GetSuccessor()) <= SubAllocator.pText)

   293         {

   294           PPM_CONTEXT* cs = CreateSuccessors(false, p);

   295           fs.SetSuccessor(SubAllocator.GetOffset(cs));

   296           if (cs == NULL)

   297             goto RESTART_MODEL;

   298         }

   299         if ( !--OrderFall )

   300         {

   301             Successor = GetContext(fs.GetSuccessor());

   302             SubAllocator.pText -= (MaxContext != MinContext);

   303         }

   304     }

   305     else

   306     {

   307         FoundState->SetSuccessor(SubAllocator.GetOffsetNoCheck(Successor));

   308         fs.SetSuccessor(SubAllocator.GetOffsetNoCheck(MinContext));

   309     }

   310     s0 = MinContext->SummFreq - (ns = MinContext->NumStats) - (fs.Freq - 1);

   311     for (pc = MaxContext; pc != MinContext; pc = GetContext(pc->Suffix))

   312     {

   313         if ((ns1 = pc->NumStats) != 1)

   314         {

   315             if ((ns1 & 1) == 0)

   316             {

   317                 void *ppp = SubAllocator.ExpandUnits(GetState(pc->Stats), ns1 >> 1);

   318                 pc->Stats = SubAllocator.GetOffset(ppp);

   319                 if (!ppp)

   320                   goto RESTART_MODEL;

   321             }

   322             pc->SummFreq = (UInt16)(pc->SummFreq + (2 * ns1 < ns) + 2 * ((4 * ns1 <= ns) &

   323                     (pc->SummFreq <= 8 * ns1)));

   324         }

   325         else

   326         {

   327             p = (PPM_CONTEXT::STATE*) SubAllocator.AllocUnits(1);

   328             if ( !p )

   329               goto RESTART_MODEL;

   330             *p = pc->oneState();

   331             pc->Stats = SubAllocator.GetOffsetNoCheck(p);

   332             if (p->Freq < MAX_FREQ / 4 - 1)

   333               p->Freq <<= 1;

   334             else

   335               p->Freq  = MAX_FREQ - 4;

   336             pc->SummFreq = (UInt16)(p->Freq + InitEsc + (ns > 3));

   337         }

   338         cf = 2 * fs.Freq * (pc->SummFreq+6);

   339         sf = s0 + pc->SummFreq;

   340         if (cf < 6 * sf)

   341         {

   342             cf = 1 + (cf > sf)+(cf >= 4 * sf);

   343             pc->SummFreq += 3;

   344         }

   345         else

   346         {

   347             cf = 4 + (cf >= 9 * sf) + (cf >= 12 * sf) + (cf >= 15 * sf);

   348             pc->SummFreq = (UInt16)(pc->SummFreq + cf);

   349         }

   350         p = GetState(pc->Stats) + ns1;

   351         p->SetSuccessor(SubAllocator.GetOffset(Successor));

   352         p->Symbol = fs.Symbol;

   353         p->Freq = (Byte)cf;

   354         pc->NumStats = (UInt16)++ns1;

   355     }

   356     MaxContext = MinContext = GetContext(fs.GetSuccessor());

   357     return;

   358 RESTART_MODEL:

   359     RestartModelRare();

   360     EscCount = 0;

   361     PrintCount = 0xFF;

   362   }

   363 

   364   void ClearMask()

   365   {

   366     EscCount = 1;

   367     memset(CharMask, 0, sizeof(CharMask));

   368     // if (++PrintCount == 0)

   369     //   PrintInfo(DecodedFile,EncodedFile);

   370   }

   371 

   372   void update1(PPM_CONTEXT::STATE* p)

   373   {

   374     (FoundState = p)->Freq += 4;

   375     MinContext->SummFreq += 4;

   376     if (p[0].Freq > p[-1].Freq)

   377     {

   378         _PPMD_SWAP(p[0],p[-1]);

   379         FoundState = --p;

   380         if (p->Freq > MAX_FREQ)

   381           rescale();

   382     }

   383   }

   384 

   385 

   386   void update2(PPM_CONTEXT::STATE* p)

   387   {

   388     (FoundState = p)->Freq += 4;

   389     MinContext->SummFreq += 4;

   390     if (p->Freq > MAX_FREQ)

   391       rescale();

   392     EscCount++;

   393     RunLength = InitRL;

   394   }

   395   

   396   SEE2_CONTEXT* makeEscFreq2(int Diff, UInt32 &scale)

   397   {

   398     SEE2_CONTEXT* psee2c;

   399     if (MinContext->NumStats != 256)

   400     {

   401       psee2c = SEE2Cont[NS2Indx[Diff-1]] +

   402         (Diff < (GetContext(MinContext->Suffix))->NumStats - MinContext->NumStats) +

   403         2 * (MinContext->SummFreq < 11 * MinContext->NumStats) +

   404         4 * (NumMasked > Diff) +

   405         HiBitsFlag;

   406       scale = psee2c->getMean();

   407     }

   408     else

   409     {

   410       psee2c = &DummySEE2Cont;

   411       scale = 1;

   412     }

   413     return psee2c;

   414   }

   415 

   416 

   417 

   418   void rescale()

   419   {

   420     int OldNS = MinContext->NumStats, i = MinContext->NumStats - 1, Adder, EscFreq;

   421     PPM_CONTEXT::STATE* p1, * p;

   422     PPM_CONTEXT::STATE *stats = GetStateNoCheck(MinContext->Stats);

   423     for (p = FoundState; p != stats; p--)

   424       _PPMD_SWAP(p[0], p[-1]);

   425     stats->Freq += 4;

   426     MinContext->SummFreq += 4;

   427     EscFreq = MinContext->SummFreq - p->Freq;

   428     Adder = (OrderFall != 0);

   429     p->Freq = (Byte)((p->Freq + Adder) >> 1);

   430     MinContext->SummFreq = p->Freq;

   431     do

   432     {

   433         EscFreq -= (++p)->Freq;

   434         p->Freq = (Byte)((p->Freq + Adder) >> 1);

   435         MinContext->SummFreq = (UInt16)(MinContext->SummFreq + p->Freq);

   436         if (p[0].Freq > p[-1].Freq)

   437         {

   438             PPM_CONTEXT::STATE tmp = *(p1 = p);

   439             do

   440             {

   441               p1[0] = p1[-1];

   442             }

   443             while (--p1 != stats && tmp.Freq > p1[-1].Freq);

   444             *p1 = tmp;

   445         }

   446     }

   447     while ( --i );

   448     if (p->Freq == 0)

   449     {

   450         do { i++; } while ((--p)->Freq == 0);

   451         EscFreq += i;

   452         MinContext->NumStats = (UInt16)(MinContext->NumStats - i);

   453         if (MinContext->NumStats == 1)

   454         {

   455             PPM_CONTEXT::STATE tmp = *stats;

   456             do { tmp.Freq = (Byte)(tmp.Freq - (tmp.Freq >> 1)); EscFreq >>= 1; } while (EscFreq > 1);

   457             SubAllocator.FreeUnits(stats, (OldNS+1) >> 1);

   458             *(FoundState = &MinContext->oneState()) = tmp;  return;

   459         }

   460     }

   461     EscFreq -= (EscFreq >> 1);

   462     MinContext->SummFreq = (UInt16)(MinContext->SummFreq + EscFreq);

   463     int n0 = (OldNS+1) >> 1, n1 = (MinContext->NumStats + 1) >> 1;

   464     if (n0 != n1)

   465       MinContext->Stats = SubAllocator.GetOffset(SubAllocator.ShrinkUnits(stats, n0, n1));

   466     FoundState = GetState(MinContext->Stats);

   467   }

   468 

   469   void NextContext()

   470   {

   471     PPM_CONTEXT *c = GetContext(FoundState->GetSuccessor());

   472     if (!OrderFall && (Byte *)c > SubAllocator.pText)

   473       MinContext = MaxContext = c;

   474     else

   475     {

   476       UpdateModel();

   477       if (EscCount == 0)

   478         ClearMask();

   479     }

   480   }

   481 };

   482 

   483 // Tabulated escapes for exponential symbol distribution

   484 const Byte ExpEscape[16]={ 25,14, 9, 7, 5, 5, 4, 4, 4, 3, 3, 3, 2, 2, 2, 2 };

   485 #define GET_MEAN(SUMM,SHIFT,ROUND) ((SUMM+(1 << (SHIFT-ROUND))) >> (SHIFT))

   486 

   487 }}

   488 

   489 #endif
author	Robert McIntyre <rlm@mit.edu>
date	Sat, 03 Mar 2012 10:31:27 -0600
parents
children