C/Ppmd7Dec.c

   1 /* Ppmd7Dec.c -- PPMdH Decoder\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 Bool Ppmd7z_RangeDec_Init(CPpmd7z_RangeDec *p)\r
  10 {\r
  11   unsigned i;\r
  12   p->Code = 0;\r
  13   p->Range = 0xFFFFFFFF;\r
  14   if (p->Stream->Read((void *)p->Stream) != 0)\r
  15     return False;\r
  16   for (i = 0; i < 4; i++)\r
  17     p->Code = (p->Code << 8) | p->Stream->Read((void *)p->Stream);\r
  18   return (p->Code < 0xFFFFFFFF);\r
  19 }\r
  20 \r
  21 static UInt32 Range_GetThreshold(void *pp, UInt32 total)\r
  22 {\r
  23   CPpmd7z_RangeDec *p = (CPpmd7z_RangeDec *)pp;\r
  24   return (p->Code) / (p->Range /= total);\r
  25 }\r
  26 \r
  27 static void Range_Normalize(CPpmd7z_RangeDec *p)\r
  28 {\r
  29   if (p->Range < kTopValue)\r
  30   {\r
  31     p->Code = (p->Code << 8) | p->Stream->Read((void *)p->Stream);\r
  32     p->Range <<= 8;\r
  33     if (p->Range < kTopValue)\r
  34     {\r
  35       p->Code = (p->Code << 8) | p->Stream->Read((void *)p->Stream);\r
  36       p->Range <<= 8;\r
  37     }\r
  38   }\r
  39 }\r
  40 \r
  41 static void Range_Decode(void *pp, UInt32 start, UInt32 size)\r
  42 {\r
  43   CPpmd7z_RangeDec *p = (CPpmd7z_RangeDec *)pp;\r
  44   p->Code -= start * p->Range;\r
  45   p->Range *= size;\r
  46   Range_Normalize(p);\r
  47 }\r
  48 \r
  49 static UInt32 Range_DecodeBit(void *pp, UInt32 size0)\r
  50 {\r
  51   CPpmd7z_RangeDec *p = (CPpmd7z_RangeDec *)pp;\r
  52   UInt32 newBound = (p->Range >> 14) * size0;\r
  53   UInt32 symbol;\r
  54   if (p->Code < newBound)\r
  55   {\r
  56     symbol = 0;\r
  57     p->Range = newBound;\r
  58   }\r
  59   else\r
  60   {\r
  61     symbol = 1;\r
  62     p->Code -= newBound;\r
  63     p->Range -= newBound;\r
  64   }\r
  65   Range_Normalize(p);\r
  66   return symbol;\r
  67 }\r
  68 \r
  69 void Ppmd7z_RangeDec_CreateVTable(CPpmd7z_RangeDec *p)\r
  70 {\r
  71   p->p.GetThreshold = Range_GetThreshold;\r
  72   p->p.Decode = Range_Decode;\r
  73   p->p.DecodeBit = Range_DecodeBit;\r
  74 }\r
  75 \r
  76 \r
  77 #define MASK(sym) ((signed char *)charMask)[sym]\r
  78 \r
  79 int Ppmd7_DecodeSymbol(CPpmd7 *p, IPpmd7_RangeDec *rc)\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     unsigned i;\r
  86     UInt32 count, hiCnt;\r
  87     if ((count = rc->GetThreshold(rc, p->MinContext->SummFreq)) < (hiCnt = s->Freq))\r
  88     {\r
  89       Byte symbol;\r
  90       rc->Decode(rc, 0, s->Freq);\r
  91       p->FoundState = s;\r
  92       symbol = s->Symbol;\r
  93       Ppmd7_Update1_0(p);\r
  94       return symbol;\r
  95     }\r
  96     p->PrevSuccess = 0;\r
  97     i = p->MinContext->NumStats - 1;\r
  98     do\r
  99     {\r
 100       if ((hiCnt += (++s)->Freq) > count)\r
 101       {\r
 102         Byte symbol;\r
 103         rc->Decode(rc, hiCnt - s->Freq, s->Freq);\r
 104         p->FoundState = s;\r
 105         symbol = s->Symbol;\r
 106         Ppmd7_Update1(p);\r
 107         return symbol;\r
 108       }\r
 109     }\r
 110     while (--i);\r
 111     if (count >= p->MinContext->SummFreq)\r
 112       return -2;\r
 113     p->HiBitsFlag = p->HB2Flag[p->FoundState->Symbol];\r
 114     rc->Decode(rc, hiCnt, p->MinContext->SummFreq - hiCnt);\r
 115     PPMD_SetAllBitsIn256Bytes(charMask);\r
 116     MASK(s->Symbol) = 0;\r
 117     i = p->MinContext->NumStats - 1;\r
 118     do { MASK((--s)->Symbol) = 0; } while (--i);\r
 119   }\r
 120   else\r
 121   {\r
 122     UInt16 *prob = Ppmd7_GetBinSumm(p);\r
 123     if (rc->DecodeBit(rc, *prob) == 0)\r
 124     {\r
 125       Byte symbol;\r
 126       *prob = (UInt16)PPMD_UPDATE_PROB_0(*prob);\r
 127       symbol = (p->FoundState = Ppmd7Context_OneState(p->MinContext))->Symbol;\r
 128       Ppmd7_UpdateBin(p);\r
 129       return symbol;\r
 130     }\r
 131     *prob = (UInt16)PPMD_UPDATE_PROB_1(*prob);\r
 132     p->InitEsc = PPMD7_kExpEscape[*prob >> 10];\r
 133     PPMD_SetAllBitsIn256Bytes(charMask);\r
 134     MASK(Ppmd7Context_OneState(p->MinContext)->Symbol) = 0;\r
 135     p->PrevSuccess = 0;\r
 136   }\r
 137   for (;;)\r
 138   {\r
 139     CPpmd_State *ps[256], *s;\r
 140     UInt32 freqSum, count, hiCnt;\r
 141     CPpmd_See *see;\r
 142     unsigned i, num, numMasked = p->MinContext->NumStats;\r
 143     do\r
 144     {\r
 145       p->OrderFall++;\r
 146       if (!p->MinContext->Suffix)\r
 147         return -1;\r
 148       p->MinContext = Ppmd7_GetContext(p, p->MinContext->Suffix);\r
 149     }\r
 150     while (p->MinContext->NumStats == numMasked);\r
 151     hiCnt = 0;\r
 152     s = Ppmd7_GetStats(p, p->MinContext);\r
 153     i = 0;\r
 154     num = p->MinContext->NumStats - numMasked;\r
 155     do\r
 156     {\r
 157       int k = (int)(MASK(s->Symbol));\r
 158       hiCnt += (s->Freq & k);\r
 159       ps[i] = s++;\r
 160       i -= k;\r
 161     }\r
 162     while (i != num);\r
 163     \r
 164     see = Ppmd7_MakeEscFreq(p, numMasked, &freqSum);\r
 165     freqSum += hiCnt;\r
 166     count = rc->GetThreshold(rc, freqSum);\r
 167     \r
 168     if (count < hiCnt)\r
 169     {\r
 170       Byte symbol;\r
 171       CPpmd_State **pps = ps;\r
 172       for (hiCnt = 0; (hiCnt += (*pps)->Freq) <= count; pps++);\r
 173       s = *pps;\r
 174       rc->Decode(rc, hiCnt - s->Freq, s->Freq);\r
 175       Ppmd_See_Update(see);\r
 176       p->FoundState = s;\r
 177       symbol = s->Symbol;\r
 178       Ppmd7_Update2(p);\r
 179       return symbol;\r
 180     }\r
 181     if (count >= freqSum)\r
 182       return -2;\r
 183     rc->Decode(rc, hiCnt, freqSum - hiCnt);\r
 184     see->Summ = (UInt16)(see->Summ + freqSum);\r
 185     do { MASK(ps[--i]->Symbol) = 0; } while (i != 0);\r
 186   }\r
 187 }\r