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