Home | History | Annotate | Download | only in C 
      1 /* Ppmd7Enc.c -- PPMdH Encoder
      2 2015-09-28 : Igor Pavlov : Public domain
      3 This code is based on PPMd var.H (2001): Dmitry Shkarin : Public domain */
      4 
      5 #include "Precomp.h"
      6 
      7 #include "Ppmd7.h"
      8 
      9 #define kTopValue (1 << 24)
     10 
     11 void Ppmd7z_RangeEnc_Init(CPpmd7z_RangeEnc *p)
     12 {
     13   p->Low = 0;
     14   p->Range = 0xFFFFFFFF;
     15   p->Cache = 0;
     16   p->CacheSize = 1;
     17 }
     18 
     19 static void RangeEnc_ShiftLow(CPpmd7z_RangeEnc *p)
     20 {
     21   if ((UInt32)p->Low < (UInt32)0xFF000000 || (unsigned)(p->Low >> 32) != 0)
     22   {
     23     Byte temp = p->Cache;
     24     do
     25     {
     26       p->Stream->Write(p->Stream, (Byte)(temp + (Byte)(p->Low >> 32)));
     27       temp = 0xFF;
     28     }
     29     while (--p->CacheSize != 0);
     30     p->Cache = (Byte)((UInt32)p->Low >> 24);
     31   }
     32   p->CacheSize++;
     33   p->Low = (UInt32)p->Low << 8;
     34 }
     35 
     36 static void RangeEnc_Encode(CPpmd7z_RangeEnc *p, UInt32 start, UInt32 size, UInt32 total)
     37 {
     38   p->Low += start * (p->Range /= total);
     39   p->Range *= size;
     40   while (p->Range < kTopValue)
     41   {
     42     p->Range <<= 8;
     43     RangeEnc_ShiftLow(p);
     44   }
     45 }
     46 
     47 static void RangeEnc_EncodeBit_0(CPpmd7z_RangeEnc *p, UInt32 size0)
     48 {
     49   p->Range = (p->Range >> 14) * size0;
     50   while (p->Range < kTopValue)
     51   {
     52     p->Range <<= 8;
     53     RangeEnc_ShiftLow(p);
     54   }
     55 }
     56 
     57 static void RangeEnc_EncodeBit_1(CPpmd7z_RangeEnc *p, UInt32 size0)
     58 {
     59   UInt32 newBound = (p->Range >> 14) * size0;
     60   p->Low += newBound;
     61   p->Range -= newBound;
     62   while (p->Range < kTopValue)
     63   {
     64     p->Range <<= 8;
     65     RangeEnc_ShiftLow(p);
     66   }
     67 }
     68 
     69 void Ppmd7z_RangeEnc_FlushData(CPpmd7z_RangeEnc *p)
     70 {
     71   unsigned i;
     72   for (i = 0; i < 5; i++)
     73     RangeEnc_ShiftLow(p);
     74 }
     75 
     76 
     77 #define MASK(sym) ((signed char *)charMask)[sym]
     78 
     79 void Ppmd7_EncodeSymbol(CPpmd7 *p, CPpmd7z_RangeEnc *rc, int symbol)
     80 {
     81   size_t charMask[256 / sizeof(size_t)];
     82   if (p->MinContext->NumStats != 1)
     83   {
     84     CPpmd_State *s = Ppmd7_GetStats(p, p->MinContext);
     85     UInt32 sum;
     86     unsigned i;
     87     if (s->Symbol == symbol)
     88     {
     89       RangeEnc_Encode(rc, 0, s->Freq, p->MinContext->SummFreq);
     90       p->FoundState = s;
     91       Ppmd7_Update1_0(p);
     92       return;
     93     }
     94     p->PrevSuccess = 0;
     95     sum = s->Freq;
     96     i = p->MinContext->NumStats - 1;
     97     do
     98     {
     99       if ((++s)->Symbol == symbol)
    100       {
    101         RangeEnc_Encode(rc, sum, s->Freq, p->MinContext->SummFreq);
    102         p->FoundState = s;
    103         Ppmd7_Update1(p);
    104         return;
    105       }
    106       sum += s->Freq;
    107     }
    108     while (--i);
    109 
    110     p->HiBitsFlag = p->HB2Flag[p->FoundState->Symbol];
    111     PPMD_SetAllBitsIn256Bytes(charMask);
    112     MASK(s->Symbol) = 0;
    113     i = p->MinContext->NumStats - 1;
    114     do { MASK((--s)->Symbol) = 0; } while (--i);
    115     RangeEnc_Encode(rc, sum, p->MinContext->SummFreq - sum, p->MinContext->SummFreq);
    116   }
    117   else
    118   {
    119     UInt16 *prob = Ppmd7_GetBinSumm(p);
    120     CPpmd_State *s = Ppmd7Context_OneState(p->MinContext);
    121     if (s->Symbol == symbol)
    122     {
    123       RangeEnc_EncodeBit_0(rc, *prob);
    124       *prob = (UInt16)PPMD_UPDATE_PROB_0(*prob);
    125       p->FoundState = s;
    126       Ppmd7_UpdateBin(p);
    127       return;
    128     }
    129     else
    130     {
    131       RangeEnc_EncodeBit_1(rc, *prob);
    132       *prob = (UInt16)PPMD_UPDATE_PROB_1(*prob);
    133       p->InitEsc = PPMD7_kExpEscape[*prob >> 10];
    134       PPMD_SetAllBitsIn256Bytes(charMask);
    135       MASK(s->Symbol) = 0;
    136       p->PrevSuccess = 0;
    137     }
    138   }
    139   for (;;)
    140   {
    141     UInt32 escFreq;
    142     CPpmd_See *see;
    143     CPpmd_State *s;
    144     UInt32 sum;
    145     unsigned i, numMasked = p->MinContext->NumStats;
    146     do
    147     {
    148       p->OrderFall++;
    149       if (!p->MinContext->Suffix)
    150         return; /* EndMarker (symbol = -1) */
    151       p->MinContext = Ppmd7_GetContext(p, p->MinContext->Suffix);
    152     }
    153     while (p->MinContext->NumStats == numMasked);
    154 
    155     see = Ppmd7_MakeEscFreq(p, numMasked, &escFreq);
    156     s = Ppmd7_GetStats(p, p->MinContext);
    157     sum = 0;
    158     i = p->MinContext->NumStats;
    159     do
    160     {
    161       int cur = s->Symbol;
    162       if (cur == symbol)
    163       {
    164         UInt32 low = sum;
    165         CPpmd_State *s1 = s;
    166         do
    167         {
    168           sum += (s->Freq & (int)(MASK(s->Symbol)));
    169           s++;
    170         }
    171         while (--i);
    172         RangeEnc_Encode(rc, low, s1->Freq, sum + escFreq);
    173         Ppmd_See_Update(see);
    174         p->FoundState = s1;
    175         Ppmd7_Update2(p);
    176         return;
    177       }
    178       sum += (s->Freq & (int)(MASK(cur)));
    179       MASK(cur) = 0;
    180       s++;
    181     }
    182     while (--i);
    183 
    184     RangeEnc_Encode(rc, sum, escFreq, sum + escFreq);
    185     see->Summ = (UInt16)(see->Summ + sum + escFreq);
    186   }
    187 }
    188