deps/lzma-16.04/C/Ppmd7Enc.c

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