ce188d4d |
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 |