tor-browser

The Tor Browser
git clone https://git.dasho.dev/tor-browser.git
Log | Files | Refs | README | LICENSE

Ppmd7Enc.c (4555B)

      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 }