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