nel/3rdparty/seven_zip/Ppmd7Enc.c

   1 /* Ppmd7Enc.c -- PPMdH Encoder
   2 2017-04-03 : 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       IByteOut_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 }