diff options
author | Igor Pavlov <87184205+ip7z@users.noreply.github.com> | 2021-12-27 00:00:00 +0000 |
---|---|---|
committer | Igor Pavlov <87184205+ip7z@users.noreply.github.com> | 2022-03-18 15:35:13 +0500 |
commit | f19f813537c7aea1c20749c914e756b54a9c3cf5 (patch) | |
tree | 816ba62ca7c0fa19f2eb46d9e9d6f7dd7c3a744d /C/Ppmd7Enc.c | |
parent | 98e06a519b63b81986abe76d28887f6984a7732b (diff) | |
download | 7zip-21.07.tar.gz 7zip-21.07.tar.bz2 7zip-21.07.zip |
'21.07'21.07
Diffstat (limited to '')
-rw-r--r-- | C/Ppmd7Enc.c | 323 |
1 files changed, 323 insertions, 0 deletions
diff --git a/C/Ppmd7Enc.c b/C/Ppmd7Enc.c new file mode 100644 index 0000000..62139c5 --- /dev/null +++ b/C/Ppmd7Enc.c | |||
@@ -0,0 +1,323 @@ | |||
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 | |||
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 | ||
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 | ||
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 | |||
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 | ||
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 | |||
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 | } | ||