C/Ppmd8Enc.c

   1 /* Ppmd8Enc.c -- PPMdI Encoder\r
   2 2010-04-16 : Igor Pavlov : Public domain\r
   3 This code is based on:\r
   4   PPMd var.I (2002): Dmitry Shkarin : Public domain\r
   5   Carryless rangecoder (1999): Dmitry Subbotin : Public domain */\r
   6 \r
   7 #include "Ppmd8.h"\r
   8 \r
   9 #define kTop (1 << 24)\r
  10 #define kBot (1 << 15)\r
  11 \r
  12 void Ppmd8_RangeEnc_FlushData(CPpmd8 *p)\r
  13 {\r
  14   unsigned i;\r
  15   for (i = 0; i < 4; i++, p->Low <<= 8 )\r
  16     p->Stream.Out->Write(p->Stream.Out, (Byte)(p->Low >> 24));\r
  17 }\r
  18 \r
  19 static void RangeEnc_Normalize(CPpmd8 *p)\r
  20 {\r
  21   while ((p->Low ^ (p->Low + p->Range)) < kTop ||\r
  22       (p->Range < kBot && ((p->Range = (0 - p->Low) & (kBot - 1)), 1)))\r
  23   {\r
  24     p->Stream.Out->Write(p->Stream.Out, (Byte)(p->Low >> 24));\r
  25     p->Range <<= 8;\r
  26     p->Low <<= 8;\r
  27   }\r
  28 }\r
  29 \r
  30 static void RangeEnc_Encode(CPpmd8 *p, UInt32 start, UInt32 size, UInt32 total)\r
  31 {\r
  32   p->Low += start * (p->Range /= total);\r
  33   p->Range *= size;\r
  34   RangeEnc_Normalize(p);\r
  35 }\r
  36 \r
  37 static void RangeEnc_EncodeBit_0(CPpmd8 *p, UInt32 size0)\r
  38 {\r
  39   p->Range >>= 14;\r
  40   p->Range *= size0;\r
  41   RangeEnc_Normalize(p);\r
  42 }\r
  43 \r
  44 static void RangeEnc_EncodeBit_1(CPpmd8 *p, UInt32 size0)\r
  45 {\r
  46   p->Low += size0 * (p->Range >>= 14);\r
  47   p->Range *= ((1 << 14) - size0);\r
  48   RangeEnc_Normalize(p);\r
  49 }\r
  50 \r
  51 \r
  52 #define MASK(sym) ((signed char *)charMask)[sym]\r
  53 \r
  54 void Ppmd8_EncodeSymbol(CPpmd8 *p, int symbol)\r
  55 {\r
  56   size_t charMask[256 / sizeof(size_t)];\r
  57   if (p->MinContext->NumStats != 0)\r
  58   {\r
  59     CPpmd_State *s = Ppmd8_GetStats(p, p->MinContext);\r
  60     UInt32 sum;\r
  61     unsigned i;\r
  62     if (s->Symbol == symbol)\r
  63     {\r
  64       RangeEnc_Encode(p, 0, s->Freq, p->MinContext->SummFreq);\r
  65       p->FoundState = s;\r
  66       Ppmd8_Update1_0(p);\r
  67       return;\r
  68     }\r
  69     p->PrevSuccess = 0;\r
  70     sum = s->Freq;\r
  71     i = p->MinContext->NumStats;\r
  72     do\r
  73     {\r
  74       if ((++s)->Symbol == symbol)\r
  75       {\r
  76         RangeEnc_Encode(p, sum, s->Freq, p->MinContext->SummFreq);\r
  77         p->FoundState = s;\r
  78         Ppmd8_Update1(p);\r
  79         return;\r
  80       }\r
  81       sum += s->Freq;\r
  82     }\r
  83     while (--i);\r
  84     \r
  85     PPMD_SetAllBitsIn256Bytes(charMask);\r
  86     MASK(s->Symbol) = 0;\r
  87     i = p->MinContext->NumStats;\r
  88     do { MASK((--s)->Symbol) = 0; } while (--i);\r
  89     RangeEnc_Encode(p, sum, p->MinContext->SummFreq - sum, p->MinContext->SummFreq);\r
  90   }\r
  91   else\r
  92   {\r
  93     UInt16 *prob = Ppmd8_GetBinSumm(p);\r
  94     CPpmd_State *s = Ppmd8Context_OneState(p->MinContext);\r
  95     if (s->Symbol == symbol)\r
  96     {\r
  97       RangeEnc_EncodeBit_0(p, *prob);\r
  98       *prob = (UInt16)PPMD_UPDATE_PROB_0(*prob);\r
  99       p->FoundState = s;\r
 100       Ppmd8_UpdateBin(p);\r
 101       return;\r
 102     }\r
 103     else\r
 104     {\r
 105       RangeEnc_EncodeBit_1(p, *prob);\r
 106       *prob = (UInt16)PPMD_UPDATE_PROB_1(*prob);\r
 107       p->InitEsc = PPMD8_kExpEscape[*prob >> 10];\r
 108       PPMD_SetAllBitsIn256Bytes(charMask);\r
 109       MASK(s->Symbol) = 0;\r
 110       p->PrevSuccess = 0;\r
 111     }\r
 112   }\r
 113   for (;;)\r
 114   {\r
 115     UInt32 escFreq;\r
 116     CPpmd_See *see;\r
 117     CPpmd_State *s;\r
 118     UInt32 sum;\r
 119     unsigned i, numMasked = p->MinContext->NumStats;\r
 120     do\r
 121     {\r
 122       p->OrderFall++;\r
 123       if (!p->MinContext->Suffix)\r
 124         return; /* EndMarker (symbol = -1) */\r
 125       p->MinContext = Ppmd8_GetContext(p, p->MinContext->Suffix);\r
 126     }\r
 127     while (p->MinContext->NumStats == numMasked);\r
 128     \r
 129     see = Ppmd8_MakeEscFreq(p, numMasked, &escFreq);\r
 130     s = Ppmd8_GetStats(p, p->MinContext);\r
 131     sum = 0;\r
 132     i = p->MinContext->NumStats + 1;\r
 133     do\r
 134     {\r
 135       int cur = s->Symbol;\r
 136       if (cur == symbol)\r
 137       {\r
 138         UInt32 low = sum;\r
 139         CPpmd_State *s1 = s;\r
 140         do\r
 141         {\r
 142           sum += (s->Freq & (int)(MASK(s->Symbol)));\r
 143           s++;\r
 144         }\r
 145         while (--i);\r
 146         RangeEnc_Encode(p, low, s1->Freq, sum + escFreq);\r
 147         Ppmd_See_Update(see);\r
 148         p->FoundState = s1;\r
 149         Ppmd8_Update2(p);\r
 150         return;\r
 151       }\r
 152       sum += (s->Freq & (int)(MASK(cur)));\r
 153       MASK(cur) = 0;\r
 154       s++;\r
 155     }\r
 156     while (--i);\r
 157     \r
 158     RangeEnc_Encode(p, sum, escFreq, sum + escFreq);\r
 159     see->Summ = (UInt16)(see->Summ + sum + escFreq);\r
 160   }\r
 161 }\r