/****************************************************************************
 *  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              *
 ****************************************************************************/

#pragma hdrstop
#include "Coder.hpp"

const int INT_BITS=7, PERIOD_BITS=7, MAX_FREQ=124;
const int INTERVAL=1 << INT_BITS, BIN_SCALE=INTERVAL << PERIOD_BITS;

#pragma pack(1)
static struct SEE2_CONTEXT { // SEE-contexts for PPM-contexts with masked symbols
    WORD Summ;
    BYTE Shift, Count;
    void init(int InitVal) { Summ=InitVal << (Shift=PERIOD_BITS-4); Count=3; }
    UINT getMean() {
        UINT RetVal=Summ >> Shift;          Summ -= RetVal;
        RetVal &= 0x03FF;                   return RetVal+(RetVal == 0);
    }
    void update() {
        if (Shift < PERIOD_BITS && --Count == 0) {
            Summ += Summ;                   Count=3 << Shift++;
        }
    }
} _PACK_ATTR SEE2Cont[44][8];
static struct PPM_CONTEXT {
//class PPM_CONTEXT {
//public:
    WORD NumStats,SummFreq;                     // sizeof(WORD) > sizeof(BYTE)
    struct STATE { BYTE Symbol, Freq; PPM_CONTEXT* Successor; } _PACK_ATTR * Stats;
    PPM_CONTEXT* Suffix;
    inline PPM_CONTEXT(STATE* pStats, PPM_CONTEXT* ShorterContext);
    inline PPM_CONTEXT();
    inline void encodeBinSymbol(int symbol);    // MaxOrder:
    inline void   encodeSymbol1(int symbol);    //  ABCD    context
    inline void   encodeSymbol2(int symbol);    //   BCD    suffix
    inline void           decodeBinSymbol();    //   BCDE   successor
    inline void             decodeSymbol1();    // other orders:
    inline void             decodeSymbol2();    //   BCD    context
    inline void           update1(STATE* p);    //    CD    suffix
    inline void           update2(STATE* p);    //   BCDE   successor
    void                          rescale();
    inline SEE2_CONTEXT* makeEscFreq2(int Diff);
//    void* operator new(size_t ) { return AllocContext(); }
    STATE& oneState() const { return (STATE&) SummFreq; }
} _PACK_ATTR * MinContext, * MedContext, * MaxContext;
#pragma pack()

static PPM_CONTEXT::STATE* FoundState;      // found next state transition
static int NumMasked, InitEsc, OrderFall, MaxOrder;
static BYTE CharMask[256], NS2Indx[256], NS2BSIndx[256];
static BYTE EscCount, PrintCount, PrevSuccess;
static WORD BinSumm[128][16];               // binary SEE-contexts

inline PPM_CONTEXT::PPM_CONTEXT(STATE* pStats,PPM_CONTEXT* ShorterContext):
        NumStats(1), Suffix(ShorterContext) { pStats->Successor=this; }
inline PPM_CONTEXT::PPM_CONTEXT(): NumStats(0) {}
static void StartModel()
{
    int i, k;
    PPM_CONTEXT *oldMC;

    InitSubAllocator();

//    MaxContext = new PPM_CONTEXT();
    MaxContext = (PPM_CONTEXT*) AllocContext();
    MaxContext->NumStats = 0;

    MaxContext->Suffix=NULL;
    MaxContext->SummFreq=(MaxContext->NumStats=256)+1;
    MaxContext->Stats = (PPM_CONTEXT::STATE*) AllocUnitsRare(256/2);
    for (PrevSuccess=i=0;i < 256;i++) {
        MaxContext->Stats[i].Symbol=i;      MaxContext->Stats[i].Freq=1;
        MaxContext->Stats[i].Successor=NULL;
    }
    PPM_CONTEXT::STATE* p=MaxContext->Stats;
    for (OrderFall=i=1; ;i++)
    {
//        MaxContext = new PPM_CONTEXT(p,MaxContext);

     oldMC = MaxContext;
     MaxContext = (PPM_CONTEXT*) AllocContext();
     p->Successor = MaxContext;
     MaxContext->NumStats = 1;
     MaxContext->Suffix = oldMC;

        if (i == MaxOrder)                  break;
        p=&(MaxContext->oneState());
        p->Symbol = 0;                      p->Freq = 1;
    }
    MaxContext->NumStats=0;                 MedContext=MinContext=MaxContext->Suffix;
static const WORD InitBinEsc[16] = {
                0x3CDD,0x1F3F,0x59BF,0x48F3,0x5FFB,0x5545,0x63D1,0x5D9D,
                0x64A1,0x5ABC,0x6632,0x6051,0x68F6,0x549B,0x6BCA,0x3AB0, };
    for (i=0;i < 128;i++)
        for (k=0;k < 16;k++)
            BinSumm[i][k]=BIN_SCALE-InitBinEsc[k]/(i+2);
    for (i=0;i <   6;i++)                   NS2BSIndx[i]=2*i;
    for (   ;i <  50;i++)                   NS2BSIndx[i]=12;
    for (   ;i < 256;i++)                   NS2BSIndx[i]=14;
    for (i=0;i < 43;i++)
            for (k=0;k < 8;k++)             SEE2Cont[i][k].init(4*i+10);
    SEE2Cont[i][0].Shift=PERIOD_BITS;
    for (i=0;i < 4;i++)                     NS2Indx[i]=i;
    for ( ;i < 4+8;i++)                     NS2Indx[i]=4+((i-4) >> 1);
    for ( ;i < 4+8+32;i++)                  NS2Indx[i]=4+4+((i-4-8) >> 2);
    for ( ;i < 256;i++)                     NS2Indx[i]=4+4+8+((i-4-8-32) >> 3);
    memset(CharMask,0,sizeof(CharMask));    EscCount=PrintCount=1;

    return;
}
inline void StopModel() {}
void PPM_CONTEXT::rescale()
{

    int OldNS=NumStats, i=NumStats-1, Adder, EscFreq;
    STATE* p1, * p;
    for (p=FoundState;p != Stats;p--)       SWAP(p[0],p[-1]);
    Stats->Freq += 4;                       SummFreq += 4;
    EscFreq=SummFreq-p->Freq;               Adder=(OrderFall != 0);
    SummFreq = (p->Freq=(p->Freq+Adder) >> 1);
    do {
        EscFreq -= (++p)->Freq;
        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 != 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=*Stats;
            do { tmp.Freq-=(tmp.Freq >> 1); EscFreq>>=1; } while (EscFreq > 1);
            FreeUnits(Stats,(OldNS+1) >> 1);
            *(FoundState=&oneState())=tmp;  return;
        }
    }
    SummFreq += (EscFreq -= (EscFreq >> 1));
    int n0=(OldNS+1) >> 1, n1=(NumStats+1) >> 1;
    if (n0 != n1)
            Stats=(STATE*)ShrinkUnits(Stats,n0,n1);
    FoundState=Stats;

}
static BOOL MakeRoot(UINT SkipCount,PPM_CONTEXT::STATE* p1)
{
    PPM_CONTEXT* oldPC;
    PPM_CONTEXT* pc=MinContext, * UpBranch=FoundState->Successor;
    PPM_CONTEXT::STATE* p, * ps[MAX_O], ** pps=ps;
    if (SkipCount == 0) {
        *pps++ = FoundState;
        if ( !pc->Suffix )                  goto NO_LOOP;
    } else if (SkipCount == 2)              pc=pc->Suffix;
    if ( p1 ) {
        p=p1;                               pc=pc->Suffix;
        goto LOOP_ENTRY;
    }
    do {
        pc=pc->Suffix;
        if (pc->NumStats != 1) {
            if ((p=pc->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:


    PPM_CONTEXT::STATE& UpState=UpBranch->oneState();

    if (pc->NumStats != 1)
    {
        UINT cf=UpState.Symbol;
        if ((p=pc->Stats)->Symbol != cf)
                do
                { p++; }
                while (p->Symbol != cf);
        UINT s0=pc->SummFreq-pc->NumStats-(cf=p->Freq-1);
        UpState.Freq=1+((2*cf <= s0)?(5*cf > s0):((2*cf+3*s0-1)/(2*s0)));
    }
    else
     UpState.Freq=pc->oneState().Freq;

    while (--pps >= ps)
    {

//        pc = new PPM_CONTEXT(*pps,pc);

     oldPC = pc;
     pc = (PPM_CONTEXT*) AllocContext();
     (PPM_CONTEXT*)(*pps)->Successor = pc;
     pc->NumStats = 1;
     pc->Suffix = oldPC;

          if ( !pc )
           return FALSE;

        pc->oneState()=UpState;
    }

    if ( !OrderFall )
    {
        UpBranch->NumStats=1;
        UpBranch->Suffix=pc;
    }

    return TRUE;
}
static void UpdateModel()
{

    PPM_CONTEXT::STATE fs=*FoundState, * p, *p1=NULL;
    PPM_CONTEXT* pc, * Successor;
    UINT ns1, ns, cf, sf, s0, SkipCount=0;
    if (fs.Freq < MAX_FREQ/4 && (pc=MinContext->Suffix) != NULL) {
        if (pc->NumStats != 1) {
            if ((p1=pc->Stats)->Symbol != fs.Symbol) {
                do { p1++; } while (p1->Symbol != fs.Symbol);
                if (p1[0].Freq >= p1[-1].Freq) {
                    SWAP(p1[0],p1[-1]);     p1--;
                }
            }
            if (p1->Freq < 7*MAX_FREQ/8) {
                p1->Freq += 2;              pc->SummFreq += 2;
            }
        } else {
            p1=&(pc->oneState());           p1->Freq += (p1->Freq < 32);
        }
    }
    if (OrderFall == 0)
    {
     if ( !MakeRoot(2,NULL) )            goto RESTART_MODEL;
        MinContext=MedContext=fs.Successor; return;
    }
    else