1 /* Ppmd7Enc.c -- Ppmd7z (PPMdH with 7z Range Coder) Encoder
2 2021-04-13 : Igor Pavlov : Public domain
3 This code is based on:
4 PPMd var.H (2001): Dmitry Shkarin : Public domain */
5
6
7 #include "Precomp.h"
8
9 #include "Ppmd7.h"
10
11 #define kTopValue (1 << 24)
12
13 #define R (&p->rc.enc)
14
Ppmd7z_Init_RangeEnc(CPpmd7 * p)15 void Ppmd7z_Init_RangeEnc(CPpmd7 *p)
16 {
17 R->Low = 0;
18 R->Range = 0xFFFFFFFF;
19 R->Cache = 0;
20 R->CacheSize = 1;
21 }
22
23 MY_NO_INLINE
RangeEnc_ShiftLow(CPpmd7 * p)24 static void RangeEnc_ShiftLow(CPpmd7 *p)
25 {
26 if ((UInt32)R->Low < (UInt32)0xFF000000 || (unsigned)(R->Low >> 32) != 0)
27 {
28 Byte temp = R->Cache;
29 do
30 {
31 IByteOut_Write(R->Stream, (Byte)(temp + (Byte)(R->Low >> 32)));
32 temp = 0xFF;
33 }
34 while (--R->CacheSize != 0);
35 R->Cache = (Byte)((UInt32)R->Low >> 24);
36 }
37 R->CacheSize++;
38 R->Low = (UInt32)((UInt32)R->Low << 8);
39 }
40
41 #define RC_NORM_BASE(p) if (R->Range < kTopValue) { R->Range <<= 8; RangeEnc_ShiftLow(p);
42 #define RC_NORM_1(p) RC_NORM_BASE(p) }
43 #define RC_NORM(p) RC_NORM_BASE(p) RC_NORM_BASE(p) }}
44
45 // we must use only one type of Normalization from two: LOCAL or REMOTE
46 #define RC_NORM_LOCAL(p) // RC_NORM(p)
47 #define RC_NORM_REMOTE(p) RC_NORM(p)
48
49 /*
50 #define RangeEnc_Encode(p, start, _size_) \
51 { UInt32 size = _size_; \
52 R->Low += start * R->Range; \
53 R->Range *= size; \
54 RC_NORM_LOCAL(p); }
55 */
56
57 MY_FORCE_INLINE
58 // MY_NO_INLINE
RangeEnc_Encode(CPpmd7 * p,UInt32 start,UInt32 size)59 static void RangeEnc_Encode(CPpmd7 *p, UInt32 start, UInt32 size)
60 {
61 R->Low += start * R->Range;
62 R->Range *= size;
63 RC_NORM_LOCAL(p);
64 }
65
Ppmd7z_Flush_RangeEnc(CPpmd7 * p)66 void Ppmd7z_Flush_RangeEnc(CPpmd7 *p)
67 {
68 unsigned i;
69 for (i = 0; i < 5; i++)
70 RangeEnc_ShiftLow(p);
71 }
72
73
74
75 #define RC_Encode(start, size) RangeEnc_Encode(p, start, size);
76 #define RC_EncodeFinal(start, size) RC_Encode(start, size); RC_NORM_REMOTE(p);
77
78 #define CTX(ref) ((CPpmd7_Context *)Ppmd7_GetContext(p, ref))
79 #define SUFFIX(ctx) CTX((ctx)->Suffix)
80 typedef CPpmd7_Context * CTX_PTR;
81 #define SUCCESSOR(p) Ppmd_GET_SUCCESSOR(p)
82
83 void Ppmd7_UpdateModel(CPpmd7 *p);
84
85 #define MASK(sym) ((unsigned char *)charMask)[sym]
86
87 MY_FORCE_INLINE
88 static
Ppmd7z_EncodeSymbol(CPpmd7 * p,int symbol)89 void Ppmd7z_EncodeSymbol(CPpmd7 *p, int symbol)
90 {
91 size_t charMask[256 / sizeof(size_t)];
92
93 if (p->MinContext->NumStats != 1)
94 {
95 CPpmd_State *s = Ppmd7_GetStats(p, p->MinContext);
96 UInt32 sum;
97 unsigned i;
98
99
100
101
102 R->Range /= p->MinContext->Union2.SummFreq;
103
104 if (s->Symbol == symbol)
105 {
106 // R->Range /= p->MinContext->Union2.SummFreq;
107 RC_EncodeFinal(0, s->Freq);
108 p->FoundState = s;
109 Ppmd7_Update1_0(p);
110 return;
111 }
112 p->PrevSuccess = 0;
113 sum = s->Freq;
114 i = (unsigned)p->MinContext->NumStats - 1;
115 do
116 {
117 if ((++s)->Symbol == symbol)
118 {
119 // R->Range /= p->MinContext->Union2.SummFreq;
120 RC_EncodeFinal(sum, s->Freq);
121 p->FoundState = s;
122 Ppmd7_Update1(p);
123 return;
124 }
125 sum += s->Freq;
126 }
127 while (--i);
128
129 // R->Range /= p->MinContext->Union2.SummFreq;
130 RC_Encode(sum, p->MinContext->Union2.SummFreq - sum);
131
132 p->HiBitsFlag = PPMD7_HiBitsFlag_3(p->FoundState->Symbol);
133 PPMD_SetAllBitsIn256Bytes(charMask);
134 // MASK(s->Symbol) = 0;
135 // i = p->MinContext->NumStats - 1;
136 // do { MASK((--s)->Symbol) = 0; } while (--i);
137 {
138 CPpmd_State *s2 = Ppmd7_GetStats(p, p->MinContext);
139 MASK(s->Symbol) = 0;
140 do
141 {
142 unsigned sym0 = s2[0].Symbol;
143 unsigned sym1 = s2[1].Symbol;
144 s2 += 2;
145 MASK(sym0) = 0;
146 MASK(sym1) = 0;
147 }
148 while (s2 < s);
149 }
150 }
151 else
152 {
153 UInt16 *prob = Ppmd7_GetBinSumm(p);
154 CPpmd_State *s = Ppmd7Context_OneState(p->MinContext);
155 UInt32 pr = *prob;
156 UInt32 bound = (R->Range >> 14) * pr;
157 pr = PPMD_UPDATE_PROB_1(pr);
158 if (s->Symbol == symbol)
159 {
160 *prob = (UInt16)(pr + (1 << PPMD_INT_BITS));
161 // RangeEnc_EncodeBit_0(p, bound);
162 R->Range = bound;
163 RC_NORM_1(p);
164
165 // p->FoundState = s;
166 // Ppmd7_UpdateBin(p);
167 {
168 unsigned freq = s->Freq;
169 CTX_PTR c = CTX(SUCCESSOR(s));
170 p->FoundState = s;
171 p->PrevSuccess = 1;
172 p->RunLength++;
173 s->Freq = (Byte)(freq + (freq < 128));
174 // NextContext(p);
175 if (p->OrderFall == 0 && (const Byte *)c > p->Text)
176 p->MaxContext = p->MinContext = c;
177 else
178 Ppmd7_UpdateModel(p);
179 }
180 return;
181 }
182
183 *prob = (UInt16)pr;
184 p->InitEsc = p->ExpEscape[pr >> 10];
185 // RangeEnc_EncodeBit_1(p, bound);
186 R->Low += bound;
187 R->Range -= bound;
188 RC_NORM_LOCAL(p)
189
190 PPMD_SetAllBitsIn256Bytes(charMask);
191 MASK(s->Symbol) = 0;
192 p->PrevSuccess = 0;
193 }
194
195 for (;;)
196 {
197 CPpmd_See *see;
198 CPpmd_State *s;
199 UInt32 sum, escFreq;
200 CPpmd7_Context *mc;
201 unsigned i, numMasked;
202
203 RC_NORM_REMOTE(p)
204
205 mc = p->MinContext;
206 numMasked = mc->NumStats;
207
208 do
209 {
210 p->OrderFall++;
211 if (!mc->Suffix)
212 return; /* EndMarker (symbol = -1) */
213 mc = Ppmd7_GetContext(p, mc->Suffix);
214 i = mc->NumStats;
215 }
216 while (i == numMasked);
217
218 p->MinContext = mc;
219
220 // see = Ppmd7_MakeEscFreq(p, numMasked, &escFreq);
221 {
222 if (i != 256)
223 {
224 unsigned nonMasked = i - numMasked;
225 see = p->See[(unsigned)p->NS2Indx[(size_t)nonMasked - 1]]
226 + p->HiBitsFlag
227 + (nonMasked < (unsigned)SUFFIX(mc)->NumStats - i)
228 + 2 * (unsigned)(mc->Union2.SummFreq < 11 * i)
229 + 4 * (unsigned)(numMasked > nonMasked);
230 {
231 // if (see->Summ) field is larger than 16-bit, we need only low 16 bits of Summ
232 unsigned summ = (UInt16)see->Summ; // & 0xFFFF
233 unsigned r = (summ >> see->Shift);
234 see->Summ = (UInt16)(summ - r);
235 escFreq = r + (r == 0);
236 }
237 }
238 else
239 {
240 see = &p->DummySee;
241 escFreq = 1;
242 }
243 }
244
245 s = Ppmd7_GetStats(p, mc);
246 sum = 0;
247 // i = mc->NumStats;
248
249 do
250 {
251 unsigned cur = s->Symbol;
252 if ((int)cur == symbol)
253 {
254 UInt32 low = sum;
255 UInt32 freq = s->Freq;
256 unsigned num2;
257
258 Ppmd_See_Update(see);
259 p->FoundState = s;
260 sum += escFreq;
261
262 num2 = i / 2;
263 i &= 1;
264 sum += freq & (0 - (UInt32)i);
265 if (num2 != 0)
266 {
267 s += i;
268 for (;;)
269 {
270 unsigned sym0 = s[0].Symbol;
271 unsigned sym1 = s[1].Symbol;
272 s += 2;
273 sum += (s[-2].Freq & (unsigned)(MASK(sym0)));
274 sum += (s[-1].Freq & (unsigned)(MASK(sym1)));
275 if (--num2 == 0)
276 break;
277 }
278 }
279
280
281 R->Range /= sum;
282 RC_EncodeFinal(low, freq);
283 Ppmd7_Update2(p);
284 return;
285 }
286 sum += (s->Freq & (unsigned)(MASK(cur)));
287 s++;
288 }
289 while (--i);
290
291 {
292 UInt32 total = sum + escFreq;
293 see->Summ = (UInt16)(see->Summ + total);
294
295 R->Range /= total;
296 RC_Encode(sum, escFreq);
297 }
298
299 {
300 CPpmd_State *s2 = Ppmd7_GetStats(p, p->MinContext);
301 s--;
302 MASK(s->Symbol) = 0;
303 do
304 {
305 unsigned sym0 = s2[0].Symbol;
306 unsigned sym1 = s2[1].Symbol;
307 s2 += 2;
308 MASK(sym0) = 0;
309 MASK(sym1) = 0;
310 }
311 while (s2 < s);
312 }
313 }
314 }
315
316
Ppmd7z_EncodeSymbols(CPpmd7 * p,const Byte * buf,const Byte * lim)317 void Ppmd7z_EncodeSymbols(CPpmd7 *p, const Byte *buf, const Byte *lim)
318 {
319 for (; buf < lim; buf++)
320 {
321 Ppmd7z_EncodeSymbol(p, *buf);
322 }
323 }
324