1 // LzmsDecoder.cpp
2 // The code is based on LZMS description from wimlib code
3
4 #include "StdAfx.h"
5
6 #include "../../../C/Alloc.h"
7
8 #include "LzmsDecoder.h"
9
10 namespace NCompress {
11 namespace NLzms {
12
13 static UInt32 g_PosBases[k_NumPosSyms /* + 1 */];
14
15 static Byte g_PosDirectBits[k_NumPosSyms];
16
17 static const Byte k_PosRuns[31] =
18 {
19 8, 0, 9, 7, 10, 15, 15, 20, 20, 30, 33, 40, 42, 45, 60, 73,
20 80, 85, 95, 105, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1
21 };
22
23 static UInt32 g_LenBases[k_NumLenSyms];
24
25 static const Byte k_LenDirectBits[k_NumLenSyms] =
26 {
27 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
28 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2,
29 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 6,
30 7, 8, 9, 10, 16, 30,
31 };
32
33 static struct CInit
34 {
CInitNCompress::NLzms::CInit35 CInit()
36 {
37 {
38 unsigned sum = 0;
39 for (unsigned i = 0; i < sizeof(k_PosRuns); i++)
40 {
41 unsigned t = k_PosRuns[i];
42 for (unsigned y = 0; y < t; y++)
43 g_PosDirectBits[sum + y] = (Byte)i;
44 sum += t;
45 }
46 }
47 {
48 UInt32 sum = 1;
49 for (unsigned i = 0; i < k_NumPosSyms; i++)
50 {
51 g_PosBases[i] = sum;
52 sum += (UInt32)1 << g_PosDirectBits[i];
53 }
54 // g_PosBases[k_NumPosSyms] = sum;
55 }
56 {
57 UInt32 sum = 1;
58 for (unsigned i = 0; i < k_NumLenSyms; i++)
59 {
60 g_LenBases[i] = sum;
61 sum += (UInt32)1 << k_LenDirectBits[i];
62 }
63 }
64 }
65 } g_Init;
66
GetNumPosSlots(size_t size)67 static unsigned GetNumPosSlots(size_t size)
68 {
69 if (size < 2)
70 return 0;
71
72 size--;
73
74 if (size >= g_PosBases[k_NumPosSyms - 1])
75 return k_NumPosSyms;
76 unsigned left = 0;
77 unsigned right = k_NumPosSyms;
78 for (;;)
79 {
80 unsigned m = (left + right) / 2;
81 if (left == m)
82 return m + 1;
83 if (size >= g_PosBases[m])
84 left = m;
85 else
86 right = m;
87 }
88 }
89
90
91 static const Int32 k_x86_WindowSize = 65535;
92 static const Int32 k_x86_TransOffset = 1023;
93
94 static const size_t k_x86_HistorySize = (1 << 16);
95
x86_Filter(Byte * data,UInt32 size,Int32 * history)96 static void x86_Filter(Byte *data, UInt32 size, Int32 *history)
97 {
98 if (size <= 17)
99 return;
100
101 Byte isCode[256];
102 memset(isCode, 0, 256);
103 isCode[0x48] = 1;
104 isCode[0x4C] = 1;
105 isCode[0xE8] = 1;
106 isCode[0xE9] = 1;
107 isCode[0xF0] = 1;
108 isCode[0xFF] = 1;
109
110 {
111 for (size_t i = 0; i < k_x86_HistorySize; i++)
112 history[i] = -(Int32)k_x86_WindowSize - 1;
113 }
114
115 size -= 16;
116 const unsigned kSave = 6;
117 const Byte savedByte = data[(size_t)size + kSave];
118 data[(size_t)size + kSave] = 0xE8;
119 Int32 last_x86_pos = -k_x86_TransOffset - 1;
120
121 // first byte is ignored
122 Int32 i = 0;
123
124 for (;;)
125 {
126 Byte *p = data + (UInt32)i;
127
128 for (;;)
129 {
130 if (isCode[*(++p)]) break;
131 if (isCode[*(++p)]) break;
132 }
133
134 i = (Int32)(p - data);
135 if ((UInt32)i >= size)
136 break;
137
138 UInt32 codeLen;
139
140 Int32 maxTransOffset = k_x86_TransOffset;
141
142 Byte b = p[0];
143
144 if (b == 0x48)
145 {
146 if (p[1] == 0x8B)
147 {
148 if ((p[2] & 0xF7) != 0x5)
149 continue;
150 // MOV RAX / RCX, [RIP + disp32]
151 }
152 else if (p[1] == 0x8D) // LEA
153 {
154 if ((p[2] & 0x7) != 0x5)
155 continue;
156 // LEA R**, []
157 }
158 else
159 continue;
160 codeLen = 3;
161 }
162 else if (b == 0x4C)
163 {
164 if (p[1] != 0x8D || (p[2] & 0x7) != 0x5)
165 continue;
166 // LEA R*, []
167 codeLen = 3;
168 }
169 else if (b == 0xE8)
170 {
171 // CALL
172 codeLen = 1;
173 maxTransOffset /= 2;
174 }
175 else if (b == 0xE9)
176 {
177 // JUMP
178 i += 4;
179 continue;
180 }
181 else if (b == 0xF0)
182 {
183 if (p[1] != 0x83 || p[2] != 0x05)
184 continue;
185 // LOCK ADD [RIP + disp32], imm8
186 // LOCK ADD [disp32], imm8
187 codeLen = 3;
188 }
189 else
190 // if (b == 0xFF)
191 {
192 if (p[1] != 0x15)
193 continue;
194 // CALL [RIP + disp32];
195 // CALL [disp32];
196 codeLen = 2;
197 }
198
199 Int32 *target;
200 {
201 Byte *p2 = p + codeLen;
202 UInt32 n = GetUi32(p2);
203 if (i - last_x86_pos <= maxTransOffset)
204 {
205 n -= i;
206 SetUi32(p2, n);
207 }
208 target = history + (((UInt32)i + n) & 0xFFFF);
209 }
210
211 i += (Int32)(codeLen + sizeof(UInt32) - 1);
212
213 if (i - *target <= k_x86_WindowSize)
214 last_x86_pos = i;
215 *target = i;
216 }
217
218 data[(size_t)size + kSave] = savedByte;
219 }
220
221
222
223 // static const int kLenIdNeedInit = -2;
224
CDecoder()225 CDecoder::CDecoder():
226 _x86_history(NULL)
227 {
228 }
229
~CDecoder()230 CDecoder::~CDecoder()
231 {
232 ::MidFree(_x86_history);
233 }
234
235 // #define RIF(x) { if (!(x)) return false; }
236
237 #define LIMIT_CHECK if (_bs._buf < _rc.cur) return S_FALSE;
238 // #define LIMIT_CHECK
239
240 #define READ_BITS_CHECK(numDirectBits) \
241 if (_bs._buf < _rc.cur) return S_FALSE; \
242 if ((size_t)(_bs._buf - _rc.cur) < (numDirectBits >> 3)) return S_FALSE;
243
244
245 #define HUFF_DEC(sym, pp) \
246 sym = pp.DecodeFull(&_bs); \
247 pp.Freqs[sym]++; \
248 if (--pp.RebuildRem == 0) pp.Rebuild();
249
250
CodeReal(const Byte * in,size_t inSize,Byte * _win,size_t outSize)251 HRESULT CDecoder::CodeReal(const Byte *in, size_t inSize, Byte *_win, size_t outSize)
252 {
253 // size_t inSizeT = (size_t)(inSize);
254 // Byte *_win;
255 // size_t _pos;
256 _pos = 0;
257
258 CBitDecoder _bs;
259 CRangeDecoder _rc;
260
261 if (inSize < 8 || (inSize & 1) != 0)
262 return S_FALSE;
263 _rc.Init(in, inSize);
264 if (_rc.code >= _rc.range)
265 return S_FALSE;
266 _bs.Init(in, inSize);
267
268 {
269 {
270 {
271 for (unsigned i = 0 ; i < k_NumReps + 1; i++)
272 _reps[i] = i + 1;
273 }
274
275 {
276 for (unsigned i = 0 ; i < k_NumReps + 1; i++)
277 _deltaReps[i] = i + 1;
278 }
279
280 mainState = 0;
281 matchState = 0;
282
283 { for (size_t i = 0; i < k_NumMainProbs; i++) mainProbs[i].Init(); }
284 { for (size_t i = 0; i < k_NumMatchProbs; i++) matchProbs[i].Init(); }
285
286 {
287 for (size_t k = 0; k < k_NumReps; k++)
288 {
289 lzRepStates[k] = 0;
290 for (size_t i = 0; i < k_NumRepProbs; i++)
291 lzRepProbs[k][i].Init();
292 }
293 }
294 {
295 for (size_t k = 0; k < k_NumReps; k++)
296 {
297 deltaRepStates[k] = 0;
298 for (size_t i = 0; i < k_NumRepProbs; i++)
299 deltaRepProbs[k][i].Init();
300 }
301 }
302
303 m_LitDecoder.Init();
304 m_LenDecoder.Init();
305 m_PowerDecoder.Init();
306 unsigned numPosSyms = GetNumPosSlots(outSize);
307 if (numPosSyms < 2)
308 numPosSyms = 2;
309 m_PosDecoder.Init(numPosSyms);
310 m_DeltaDecoder.Init(numPosSyms);
311 }
312 }
313
314 {
315 unsigned prevType = 0;
316
317 while (_pos < outSize)
318 {
319 if (_rc.Decode(&mainState, k_NumMainProbs, mainProbs) == 0)
320 {
321 UInt32 number;
322 HUFF_DEC(number, m_LitDecoder);
323 LIMIT_CHECK
324 _win[_pos++] = (Byte)number;
325 prevType = 0;
326 }
327 else if (_rc.Decode(&matchState, k_NumMatchProbs, matchProbs) == 0)
328 {
329 UInt32 distance;
330
331 if (_rc.Decode(&lzRepStates[0], k_NumRepProbs, lzRepProbs[0]) == 0)
332 {
333 UInt32 number;
334 HUFF_DEC(number, m_PosDecoder);
335 LIMIT_CHECK
336
337 unsigned numDirectBits = g_PosDirectBits[number];
338 distance = g_PosBases[number];
339 READ_BITS_CHECK(numDirectBits);
340 distance += _bs.ReadBits32(numDirectBits);
341 // LIMIT_CHECK
342 _reps[3] = _reps[2];
343 _reps[2] = _reps[1];
344 _reps[1] = _reps[0];
345 _reps[0] = distance;
346 }
347 else
348 {
349 if (_rc.Decode(&lzRepStates[1], k_NumRepProbs, lzRepProbs[1]) == 0)
350 {
351 if (prevType != 1)
352 distance = _reps[0];
353 else
354 {
355 distance = _reps[1];
356 _reps[1] = _reps[0];
357 _reps[0] = distance;
358 }
359 }
360 else if (_rc.Decode(&lzRepStates[2], k_NumRepProbs, lzRepProbs[2]) == 0)
361 {
362 if (prevType != 1)
363 {
364 distance = _reps[1];
365 _reps[1] = _reps[0];
366 _reps[0] = distance;
367 }
368 else
369 {
370 distance = _reps[2];
371 _reps[2] = _reps[1];
372 _reps[1] = _reps[0];
373 _reps[0] = distance;
374 }
375 }
376 else
377 {
378 if (prevType != 1)
379 {
380 distance = _reps[2];
381 _reps[2] = _reps[1];
382 _reps[1] = _reps[0];
383 _reps[0] = distance;
384 }
385 else
386 {
387 distance = _reps[3];
388 _reps[3] = _reps[2];
389 _reps[2] = _reps[1];
390 _reps[1] = _reps[0];
391 _reps[0] = distance;
392 }
393 }
394 }
395
396 UInt32 lenSlot;
397 HUFF_DEC(lenSlot, m_LenDecoder);
398 LIMIT_CHECK
399
400 UInt32 len = g_LenBases[lenSlot];
401 {
402 unsigned numDirectBits = k_LenDirectBits[lenSlot];
403 READ_BITS_CHECK(numDirectBits);
404 len += _bs.ReadBits32(numDirectBits);
405 }
406 // LIMIT_CHECK
407
408 if (len > outSize - _pos)
409 return S_FALSE;
410
411 if (distance > _pos)
412 return S_FALSE;
413
414 Byte *dest = _win + _pos;
415 const Byte *src = dest - distance;
416 _pos += len;
417 do
418 *dest++ = *src++;
419 while (--len);
420
421 prevType = 1;
422 }
423 else
424 {
425 UInt64 distance;
426
427 UInt32 power;
428 UInt32 distance32;
429
430 if (_rc.Decode(&deltaRepStates[0], k_NumRepProbs, deltaRepProbs[0]) == 0)
431 {
432 HUFF_DEC(power, m_PowerDecoder);
433 LIMIT_CHECK
434
435 UInt32 number;
436 HUFF_DEC(number, m_DeltaDecoder);
437 LIMIT_CHECK
438
439 unsigned numDirectBits = g_PosDirectBits[number];
440 distance32 = g_PosBases[number];
441 READ_BITS_CHECK(numDirectBits);
442 distance32 += _bs.ReadBits32(numDirectBits);
443 // LIMIT_CHECK
444
445 distance = ((UInt64)power << 32) | distance32;
446
447 _deltaReps[3] = _deltaReps[2];
448 _deltaReps[2] = _deltaReps[1];
449 _deltaReps[1] = _deltaReps[0];
450 _deltaReps[0] = distance;
451 }
452 else
453 {
454 if (_rc.Decode(&deltaRepStates[1], k_NumRepProbs, deltaRepProbs[1]) == 0)
455 {
456 if (prevType != 2)
457 distance = _deltaReps[0];
458 else
459 {
460 distance = _deltaReps[1];
461 _deltaReps[1] = _deltaReps[0];
462 _deltaReps[0] = distance;
463 }
464 }
465 else if (_rc.Decode(&deltaRepStates[2], k_NumRepProbs, deltaRepProbs[2]) == 0)
466 {
467 if (prevType != 2)
468 {
469 distance = _deltaReps[1];
470 _deltaReps[1] = _deltaReps[0];
471 _deltaReps[0] = distance;
472 }
473 else
474 {
475 distance = _deltaReps[2];
476 _deltaReps[2] = _deltaReps[1];
477 _deltaReps[1] = _deltaReps[0];
478 _deltaReps[0] = distance;
479 }
480 }
481 else
482 {
483 if (prevType != 2)
484 {
485 distance = _deltaReps[2];
486 _deltaReps[2] = _deltaReps[1];
487 _deltaReps[1] = _deltaReps[0];
488 _deltaReps[0] = distance;
489 }
490 else
491 {
492 distance = _deltaReps[3];
493 _deltaReps[3] = _deltaReps[2];
494 _deltaReps[2] = _deltaReps[1];
495 _deltaReps[1] = _deltaReps[0];
496 _deltaReps[0] = distance;
497 }
498 }
499 distance32 = (UInt32)_deltaReps[0] & 0xFFFFFFFF;
500 power = (UInt32)(_deltaReps[0] >> 32);
501 }
502
503 UInt32 dist = (distance32 << power);
504
505 UInt32 lenSlot;
506 HUFF_DEC(lenSlot, m_LenDecoder);
507 LIMIT_CHECK
508
509 UInt32 len = g_LenBases[lenSlot];
510 {
511 unsigned numDirectBits = k_LenDirectBits[lenSlot];
512 READ_BITS_CHECK(numDirectBits);
513 len += _bs.ReadBits32(numDirectBits);
514 }
515 // LIMIT_CHECK
516
517 if (len > outSize - _pos)
518 return S_FALSE;
519
520 size_t span = (size_t)1 << power;
521 if ((UInt64)dist + span > _pos)
522 return S_FALSE;
523 Byte *dest = _win + _pos - span;
524 const Byte *src = dest - dist;
525 _pos += len;
526 do
527 {
528 *(dest + span) = (Byte)(*(dest) + *(src + span) - *(src));
529 src++;
530 dest++;
531 }
532 while (--len);
533
534 prevType = 2;
535 }
536 }
537 }
538
539 _rc.Normalize();
540 if (_rc.code != 0)
541 return S_FALSE;
542 if (_rc.cur > _bs._buf
543 || (_rc.cur == _bs._buf && _bs._bitPos != 0))
544 return S_FALSE;
545
546 /*
547 int delta = (int)(_bs._buf - _rc.cur);
548 if (_bs._bitPos != 0)
549 delta--;
550 if ((delta & 1))
551 delta--;
552 printf("%d ", delta);
553 */
554
555 return S_OK;
556 }
557
Code(const Byte * in,size_t inSize,Byte * out,size_t outSize)558 HRESULT CDecoder::Code(const Byte *in, size_t inSize, Byte *out, size_t outSize)
559 {
560 if (!_x86_history)
561 {
562 _x86_history = (Int32 *)::MidAlloc(sizeof(Int32) * k_x86_HistorySize);
563 if (!_x86_history)
564 return E_OUTOFMEMORY;
565 }
566 HRESULT res;
567 // try
568 {
569 res = CodeReal(in, inSize, out, outSize);
570 }
571 // catch (...) { res = S_FALSE; }
572 x86_Filter(out, (UInt32)_pos, _x86_history);
573 return res;
574 }
575
576 }}
577