C/Ppmd7Enc.c

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