1 // LzfseDecoder.cpp
2
3 /*
4 This code implements LZFSE data decompressing.
5 The code from "LZFSE compression library" was used.
6
7 2018 : Igor Pavlov : BSD 3-clause License : the code in this file
8 2015-2017 : Apple Inc : BSD 3-clause License : original "LZFSE compression library" code
9
10 The code in the "LZFSE compression library" is licensed under the "BSD 3-clause License":
11 ----
12 Copyright (c) 2015-2016, Apple Inc. All rights reserved.
13
14 Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:
15
16 1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
17
18 2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer
19 in the documentation and/or other materials provided with the distribution.
20
21 3. Neither the name of the copyright holder(s) nor the names of any contributors may be used to endorse or promote products derived
22 from this software without specific prior written permission.
23
24 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
25 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
26 COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
27 (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
28 HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
29 ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30 ----
31 */
32
33 #include "StdAfx.h"
34
35 // #define SHOW_DEBUG_INFO
36
37 #ifdef SHOW_DEBUG_INFO
38 #include <stdio.h>
39 #endif
40
41 #ifdef SHOW_DEBUG_INFO
42 #define PRF(x) x
43 #else
44 #define PRF(x)
45 #endif
46
47 #include "../../../C/CpuArch.h"
48
49 #include "LzfseDecoder.h"
50
51 namespace NCompress {
52 namespace NLzfse {
53
54 static const Byte kSignature_LZFSE_V1 = 0x31; // '1'
55 static const Byte kSignature_LZFSE_V2 = 0x32; // '2'
56
57
GetUInt32(UInt32 & val)58 HRESULT CDecoder::GetUInt32(UInt32 &val)
59 {
60 Byte b[4];
61 for (unsigned i = 0; i < 4; i++)
62 if (!m_InStream.ReadByte(b[i]))
63 return S_FALSE;
64 val = GetUi32(b);
65 return S_OK;
66 }
67
68
69
DecodeUncompressed(UInt32 unpackSize)70 HRESULT CDecoder::DecodeUncompressed(UInt32 unpackSize)
71 {
72 PRF(printf("\nUncompressed %7u\n", unpackSize));
73
74 const unsigned kBufSize = 1 << 8;
75 Byte buf[kBufSize];
76 for (;;)
77 {
78 if (unpackSize == 0)
79 return S_OK;
80 UInt32 cur = unpackSize;
81 if (cur > kBufSize)
82 cur = kBufSize;
83 const UInt32 cur2 = (UInt32)m_InStream.ReadBytes(buf, cur);
84 m_OutWindowStream.PutBytes(buf, cur2);
85 if (cur != cur2)
86 return S_FALSE;
87 }
88 }
89
90
91
DecodeLzvn(UInt32 unpackSize,UInt32 packSize)92 HRESULT CDecoder::DecodeLzvn(UInt32 unpackSize, UInt32 packSize)
93 {
94 PRF(printf("\nLZVN 0x%07x 0x%07x\n", unpackSize, packSize));
95
96 UInt32 D = 0;
97
98 for (;;)
99 {
100 if (packSize == 0)
101 return S_FALSE;
102 Byte b;
103 if (!m_InStream.ReadByte(b))
104 return S_FALSE;
105 packSize--;
106
107 UInt32 M;
108 UInt32 L;
109
110 if (b >= 0xE0)
111 {
112 /*
113 large L - 11100000 LLLLLLLL <LITERALS>
114 small L - 1110LLLL <LITERALS>
115
116 large Rep - 11110000 MMMMMMMM
117 small Rep - 1111MMMM
118 */
119
120 M = b & 0xF;
121 if (M == 0)
122 {
123 if (packSize == 0)
124 return S_FALSE;
125 Byte b1;
126 if (!m_InStream.ReadByte(b1))
127 return S_FALSE;
128 packSize--;
129 M = (UInt32)b1 + 16;
130 }
131 L = 0;
132 if ((b & 0x10) == 0)
133 {
134 // Literals only
135 L = M;
136 M = 0;
137 }
138 }
139
140 // ERROR codes
141 else if ((b & 0xF0) == 0x70) // 0111xxxx
142 return S_FALSE;
143 else if ((b & 0xF0) == 0xD0) // 1101xxxx
144 return S_FALSE;
145
146 else
147 {
148 if ((b & 0xE0) == 0xA0)
149 {
150 // medium - 101LLMMM DDDDDDMM DDDDDDDD <LITERALS>
151 if (packSize < 2)
152 return S_FALSE;
153 Byte b1;
154 if (!m_InStream.ReadByte(b1))
155 return S_FALSE;
156 packSize--;
157
158 Byte b2;
159 if (!m_InStream.ReadByte(b2))
160 return S_FALSE;
161 packSize--;
162 L = (((UInt32)b >> 3) & 3);
163 M = (((UInt32)b & 7) << 2) + (b1 & 3);
164 D = ((UInt32)b1 >> 2) + ((UInt32)b2 << 6);
165 }
166 else
167 {
168 L = (UInt32)b >> 6;
169 M = ((UInt32)b >> 3) & 7;
170 if ((b & 0x7) == 6)
171 {
172 // REP - LLMMM110 <LITERALS>
173 if (L == 0)
174 {
175 // spec
176 if (M == 0)
177 break; // EOS
178 if (M <= 2)
179 continue; // NOP
180 return S_FALSE; // UNDEFINED
181 }
182 }
183 else
184 {
185 if (packSize == 0)
186 return S_FALSE;
187 Byte b1;
188 if (!m_InStream.ReadByte(b1))
189 return S_FALSE;
190 packSize--;
191
192 // large - LLMMM111 DDDDDDDD DDDDDDDD <LITERALS>
193 // small - LLMMMDDD DDDDDDDD <LITERALS>
194 D = ((UInt32)b & 7);
195 if (D == 7)
196 {
197 if (packSize == 0)
198 return S_FALSE;
199 Byte b2;
200 if (!m_InStream.ReadByte(b2))
201 return S_FALSE;
202 packSize--;
203 D = b2;
204 }
205 D = (D << 8) + b1;
206 }
207 }
208
209 M += 3;
210 }
211 {
212 for (unsigned i = 0; i < L; i++)
213 {
214 if (packSize == 0 || unpackSize == 0)
215 return S_FALSE;
216 Byte b1;
217 if (!m_InStream.ReadByte(b1))
218 return S_FALSE;
219 packSize--;
220 m_OutWindowStream.PutByte(b1);
221 unpackSize--;
222 }
223 }
224
225 if (M != 0)
226 {
227 if (unpackSize == 0 || D == 0)
228 return S_FALSE;
229 unsigned cur = M;
230 if (cur > unpackSize)
231 cur = (unsigned)unpackSize;
232 if (!m_OutWindowStream.CopyBlock(D - 1, cur))
233 return S_FALSE;
234 unpackSize -= cur;
235 if (cur != M)
236 return S_FALSE;
237 }
238 }
239
240 if (unpackSize != 0)
241 return S_FALSE;
242
243 // LZVN encoder writes 7 additional zero bytes
244 if (packSize < 7)
245 return S_FALSE;
246 for (unsigned i = 0; i < 7; i++)
247 {
248 Byte b;
249 if (!m_InStream.ReadByte(b))
250 return S_FALSE;
251 if (b != 0)
252 return S_FALSE;
253 }
254 packSize -= 7;
255 if (packSize)
256 {
257 PRF(printf("packSize after unused = %u\n", packSize));
258 // if (packSize <= 0x100) { Byte buf[0x100]; m_InStream.ReadBytes(buf, packSize); }
259 /* Lzvn block that is used in HFS can contain junk data
260 (at least 256 bytes) after payload data. Why?
261 We ignore that junk data, if it's HFS (LzvnMode) mode. */
262 if (!LzvnMode)
263 return S_FALSE;
264 }
265 return S_OK;
266 }
267
268
269
270 // ---------- LZFSE ----------
271
272 #define MATCHES_PER_BLOCK 10000
273 #define LITERALS_PER_BLOCK (4 * MATCHES_PER_BLOCK)
274
275 #define NUM_L_SYMBOLS 20
276 #define NUM_M_SYMBOLS 20
277 #define NUM_D_SYMBOLS 64
278 #define NUM_LIT_SYMBOLS 256
279
280 #define NUM_SYMBOLS ( \
281 NUM_L_SYMBOLS + \
282 NUM_M_SYMBOLS + \
283 NUM_D_SYMBOLS + \
284 NUM_LIT_SYMBOLS)
285
286 #define NUM_L_STATES (1 << 6)
287 #define NUM_M_STATES (1 << 6)
288 #define NUM_D_STATES (1 << 8)
289 #define NUM_LIT_STATES (1 << 10)
290
291
292 typedef UInt32 CFseState;
293
294
SumFreqs(const UInt16 * freqs,unsigned num)295 static UInt32 SumFreqs(const UInt16 *freqs, unsigned num)
296 {
297 UInt32 sum = 0;
298 for (unsigned i = 0; i < num; i++)
299 sum += (UInt32)freqs[i];
300 return sum;
301 }
302
303
CountZeroBits(UInt32 val,UInt32 mask)304 static Z7_FORCE_INLINE unsigned CountZeroBits(UInt32 val, UInt32 mask)
305 {
306 for (unsigned i = 0;;)
307 {
308 if (val & mask)
309 return i;
310 i++;
311 mask >>= 1;
312 }
313 }
314
315
InitLitTable(const UInt16 * freqs,UInt32 * table)316 static Z7_FORCE_INLINE void InitLitTable(const UInt16 *freqs, UInt32 *table)
317 {
318 for (unsigned i = 0; i < NUM_LIT_SYMBOLS; i++)
319 {
320 unsigned f = freqs[i];
321 if (f == 0)
322 continue;
323
324 // 0 < f <= numStates
325 // 0 <= k <= numStatesLog
326 // numStates <= (f<<k) < numStates * 2
327 // 0 < j0 <= f
328 // (f + j0) = next_power_of_2 for f
329 unsigned k = CountZeroBits(f, NUM_LIT_STATES);
330 unsigned j0 = (((unsigned)NUM_LIT_STATES * 2) >> k) - f;
331
332 /*
333 CEntry
334 {
335 Byte k;
336 Byte symbol;
337 UInt16 delta;
338 };
339 */
340
341 UInt32 e = ((UInt32)i << 8) + k;
342 k += 16;
343 UInt32 d = e + ((UInt32)f << k) - ((UInt32)NUM_LIT_STATES << 16);
344 UInt32 step = (UInt32)1 << k;
345
346 unsigned j = 0;
347 do
348 {
349 *table++ = d;
350 d += step;
351 }
352 while (++j < j0);
353
354 e--;
355 step >>= 1;
356
357 for (j = j0; j < f; j++)
358 {
359 *table++ = e;
360 e += step;
361 }
362 }
363 }
364
365
366 typedef struct
367 {
368 Byte totalBits;
369 Byte extraBits;
370 UInt16 delta;
371 UInt32 vbase;
372 } CExtraEntry;
373
374
InitExtraDecoderTable(unsigned numStates,unsigned numSymbols,const UInt16 * freqs,const Byte * vbits,CExtraEntry * table)375 static void InitExtraDecoderTable(unsigned numStates,
376 unsigned numSymbols,
377 const UInt16 *freqs,
378 const Byte *vbits,
379 CExtraEntry *table)
380 {
381 UInt32 vbase = 0;
382
383 for (unsigned i = 0; i < numSymbols; i++)
384 {
385 unsigned f = freqs[i];
386 unsigned extraBits = vbits[i];
387
388 if (f != 0)
389 {
390 unsigned k = CountZeroBits(f, numStates);
391 unsigned j0 = ((2 * numStates) >> k) - f;
392
393 unsigned j = 0;
394 do
395 {
396 CExtraEntry *e = table++;
397 e->totalBits = (Byte)(k + extraBits);
398 e->extraBits = (Byte)extraBits;
399 e->delta = (UInt16)(((f + j) << k) - numStates);
400 e->vbase = vbase;
401 }
402 while (++j < j0);
403
404 f -= j0;
405 k--;
406
407 for (j = 0; j < f; j++)
408 {
409 CExtraEntry *e = table++;
410 e->totalBits = (Byte)(k + extraBits);
411 e->extraBits = (Byte)extraBits;
412 e->delta = (UInt16)(j << k);
413 e->vbase = vbase;
414 }
415 }
416
417 vbase += ((UInt32)1 << extraBits);
418 }
419 }
420
421
422 static const Byte k_L_extra[NUM_L_SYMBOLS] =
423 {
424 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 3, 5, 8
425 };
426
427 static const Byte k_M_extra[NUM_M_SYMBOLS] =
428 {
429 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 5, 8, 11
430 };
431
432 static const Byte k_D_extra[NUM_D_SYMBOLS] =
433 {
434 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3,
435 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7,
436 8, 8, 8, 8, 9, 9, 9, 9, 10, 10, 10, 10, 11, 11, 11, 11,
437 12, 12, 12, 12, 13, 13, 13, 13, 14, 14, 14, 14, 15, 15, 15, 15
438 };
439
440
441
442 // ---------- CBitStream ----------
443
444 typedef struct
445 {
446 UInt32 accum;
447 unsigned numBits; // [0, 31] - Number of valid bits in (accum), other bits are 0
448 } CBitStream;
449
450
FseInStream_Init(CBitStream * s,int n,const Byte ** pbuf)451 static Z7_FORCE_INLINE int FseInStream_Init(CBitStream *s,
452 int n, // [-7, 0], (-n == number_of_unused_bits) in last byte
453 const Byte **pbuf)
454 {
455 *pbuf -= 4;
456 s->accum = GetUi32(*pbuf);
457 if (n)
458 {
459 s->numBits = (unsigned)(n + 32);
460 if ((s->accum >> s->numBits) != 0)
461 return -1; // ERROR, encoder should have zeroed the upper bits
462 }
463 else
464 {
465 *pbuf += 1;
466 s->accum >>= 8;
467 s->numBits = 24;
468 }
469 return 0; // OK
470 }
471
472
473 // 0 <= numBits < 32
474 #define mask31(x, numBits) ((x) & (((UInt32)1 << (numBits)) - 1))
475
476 #define FseInStream_FLUSH \
477 { const unsigned nbits = (31 - in.numBits) & (unsigned)-8; \
478 if (nbits) { \
479 buf -= (nbits >> 3); \
480 if (buf < buf_check) return S_FALSE; \
481 UInt32 v = GetUi32(buf); \
482 in.accum = (in.accum << nbits) | mask31(v, nbits); \
483 in.numBits += nbits; }}
484
485
486
BitStream_Pull(CBitStream * s,unsigned numBits)487 static Z7_FORCE_INLINE UInt32 BitStream_Pull(CBitStream *s, unsigned numBits)
488 {
489 s->numBits -= numBits;
490 const UInt32 v = s->accum >> s->numBits;
491 s->accum = mask31(s->accum, s->numBits);
492 return v;
493 }
494
495
496 #define DECODE_LIT(dest, pstate) { \
497 UInt32 e = lit_decoder[pstate]; \
498 pstate = (CFseState)((e >> 16) + BitStream_Pull(&in, e & 0xff)); \
499 dest = (Byte)(e >> 8); }
500
501
FseDecodeExtra(CFseState * pstate,const CExtraEntry * table,CBitStream * s)502 static Z7_FORCE_INLINE UInt32 FseDecodeExtra(CFseState *pstate,
503 const CExtraEntry *table,
504 CBitStream *s)
505 {
506 const CExtraEntry *e = &table[*pstate];
507 UInt32 v = BitStream_Pull(s, e->totalBits);
508 unsigned extraBits = e->extraBits;
509 *pstate = (CFseState)(e->delta + (v >> extraBits));
510 return e->vbase + mask31(v, extraBits);
511 }
512
513
514 #define freqs_L (freqs)
515 #define freqs_M (freqs_L + NUM_L_SYMBOLS)
516 #define freqs_D (freqs_M + NUM_M_SYMBOLS)
517 #define freqs_LIT (freqs_D + NUM_D_SYMBOLS)
518
519 #define GET_BITS_64(v, offset, num, dest) dest = (UInt32) ((v >> (offset)) & ((1 << (num)) - 1));
520 #define GET_BITS_64_Int32(v, offset, num, dest) dest = (Int32)((v >> (offset)) & ((1 << (num)) - 1));
521 #define GET_BITS_32(v, offset, num, dest) dest = (CFseState)((v >> (offset)) & ((1 << (num)) - 1));
522
523
DecodeLzfse(UInt32 unpackSize,Byte version)524 HRESULT CDecoder::DecodeLzfse(UInt32 unpackSize, Byte version)
525 {
526 PRF(printf("\nLZFSE-%d %7u", version - '0', unpackSize));
527
528 UInt32 numLiterals;
529 UInt32 litPayloadSize;
530 Int32 literal_bits;
531
532 UInt32 lit_state_0;
533 UInt32 lit_state_1;
534 UInt32 lit_state_2;
535 UInt32 lit_state_3;
536
537 UInt32 numMatches;
538 UInt32 lmdPayloadSize;
539 Int32 lmd_bits;
540
541 CFseState l_state;
542 CFseState m_state;
543 CFseState d_state;
544
545 UInt16 freqs[NUM_SYMBOLS];
546
547 if (version == kSignature_LZFSE_V1)
548 {
549 return E_NOTIMPL;
550 // we need examples to test LZFSE-V1 code
551 /*
552 const unsigned k_v1_SubHeaderSize = 7 * 4 + 7 * 2;
553 const unsigned k_v1_HeaderSize = k_v1_SubHeaderSize + NUM_SYMBOLS * 2;
554 _buffer.AllocAtLeast(k_v1_HeaderSize);
555 if (m_InStream.ReadBytes(_buffer, k_v1_HeaderSize) != k_v1_HeaderSize)
556 return S_FALSE;
557
558 const Byte *buf = _buffer;
559 #define GET_32(offs, dest) dest = GetUi32(buf + offs)
560 #define GET_16(offs, dest) dest = GetUi16(buf + offs)
561
562 UInt32 payload_bytes;
563 GET_32(0, payload_bytes);
564 GET_32(4, numLiterals);
565 GET_32(8, numMatches);
566 GET_32(12, litPayloadSize);
567 GET_32(16, lmdPayloadSize);
568 if (litPayloadSize > (1 << 20) || lmdPayloadSize > (1 << 20))
569 return S_FALSE;
570 GET_32(20, literal_bits);
571 if (literal_bits < -7 || literal_bits > 0)
572 return S_FALSE;
573
574 GET_16(24, lit_state_0);
575 GET_16(26, lit_state_1);
576 GET_16(28, lit_state_2);
577 GET_16(30, lit_state_3);
578
579 GET_32(32, lmd_bits);
580 if (lmd_bits < -7 || lmd_bits > 0)
581 return S_FALSE;
582
583 GET_16(36, l_state);
584 GET_16(38, m_state);
585 GET_16(40, d_state);
586
587 for (unsigned i = 0; i < NUM_SYMBOLS; i++)
588 freqs[i] = GetUi16(buf + k_v1_SubHeaderSize + i * 2);
589 */
590 }
591 else
592 {
593 UInt32 headerSize;
594 {
595 const unsigned kPreHeaderSize = 4 * 2; // signature and upackSize
596 const unsigned kHeaderSize = 8 * 3;
597 Byte temp[kHeaderSize];
598 if (m_InStream.ReadBytes(temp, kHeaderSize) != kHeaderSize)
599 return S_FALSE;
600
601 UInt64 v;
602
603 v = GetUi64(temp);
604 GET_BITS_64(v, 0, 20, numLiterals)
605 GET_BITS_64(v, 20, 20, litPayloadSize)
606 GET_BITS_64(v, 40, 20, numMatches)
607 GET_BITS_64_Int32(v, 60, 3 + 1, literal_bits) // (NumberOfUsedBits - 1)
608 literal_bits -= 7; // (-NumberOfUnusedBits)
609 if (literal_bits > 0)
610 return S_FALSE;
611 // GET_BITS_64(v, 63, 1, unused);
612
613 v = GetUi64(temp + 8);
614 GET_BITS_64(v, 0, 10, lit_state_0)
615 GET_BITS_64(v, 10, 10, lit_state_1)
616 GET_BITS_64(v, 20, 10, lit_state_2)
617 GET_BITS_64(v, 30, 10, lit_state_3)
618 GET_BITS_64(v, 40, 20, lmdPayloadSize)
619 GET_BITS_64_Int32(v, 60, 3 + 1, lmd_bits)
620 lmd_bits -= 7;
621 if (lmd_bits > 0)
622 return S_FALSE;
623 // GET_BITS_64(v, 63, 1, unused)
624
625 UInt32 v32 = GetUi32(temp + 20);
626 // (total header size in bytes; this does not
627 // correspond to a field in the uncompressed header version,
628 // but is required; we wouldn't know the size of the
629 // compresssed header otherwise.
630 GET_BITS_32(v32, 0, 10, l_state)
631 GET_BITS_32(v32, 10, 10, m_state)
632 GET_BITS_32(v32, 20, 10 + 2, d_state)
633 // GET_BITS_64(v, 62, 2, unused)
634
635 headerSize = GetUi32(temp + 16);
636 if (headerSize <= kPreHeaderSize + kHeaderSize)
637 return S_FALSE;
638 headerSize -= kPreHeaderSize + kHeaderSize;
639 }
640
641 // no freqs case is not allowed ?
642 // memset(freqs, 0, sizeof(freqs));
643 // if (headerSize != 0)
644 {
645 static const Byte numBitsTable[32] =
646 {
647 2, 3, 2, 5, 2, 3, 2, 8, 2, 3, 2, 5, 2, 3, 2, 14,
648 2, 3, 2, 5, 2, 3, 2, 8, 2, 3, 2, 5, 2, 3, 2, 14
649 };
650
651 static const Byte valueTable[32] =
652 {
653 0, 2, 1, 4, 0, 3, 1, 8, 0, 2, 1, 5, 0, 3, 1, 24,
654 0, 2, 1, 6, 0, 3, 1, 8, 0, 2, 1, 7, 0, 3, 1, 24
655 };
656
657 UInt32 accum = 0;
658 unsigned numBits = 0;
659
660 for (unsigned i = 0; i < NUM_SYMBOLS; i++)
661 {
662 while (numBits <= 14 && headerSize != 0)
663 {
664 Byte b;
665 if (!m_InStream.ReadByte(b))
666 return S_FALSE;
667 accum |= (UInt32)b << numBits;
668 numBits += 8;
669 headerSize--;
670 }
671
672 unsigned b = (unsigned)accum & 31;
673 unsigned n = numBitsTable[b];
674 if (numBits < n)
675 return S_FALSE;
676 numBits -= n;
677 UInt32 f = valueTable[b];
678 if (n >= 8)
679 f += ((accum >> 4) & (0x3ff >> (14 - n)));
680 accum >>= n;
681 freqs[i] = (UInt16)f;
682 }
683
684 if (numBits >= 8 || headerSize != 0)
685 return S_FALSE;
686 }
687 }
688
689 PRF(printf(" Literals=%6u Matches=%6u", numLiterals, numMatches));
690
691 if (numLiterals > LITERALS_PER_BLOCK
692 || (numLiterals & 3) != 0
693 || numMatches > MATCHES_PER_BLOCK
694 || lit_state_0 >= NUM_LIT_STATES
695 || lit_state_1 >= NUM_LIT_STATES
696 || lit_state_2 >= NUM_LIT_STATES
697 || lit_state_3 >= NUM_LIT_STATES
698 || l_state >= NUM_L_STATES
699 || m_state >= NUM_M_STATES
700 || d_state >= NUM_D_STATES)
701 return S_FALSE;
702
703 // only full table is allowed ?
704 if ( SumFreqs(freqs_L, NUM_L_SYMBOLS) != NUM_L_STATES
705 || SumFreqs(freqs_M, NUM_M_SYMBOLS) != NUM_M_STATES
706 || SumFreqs(freqs_D, NUM_D_SYMBOLS) != NUM_D_STATES
707 || SumFreqs(freqs_LIT, NUM_LIT_SYMBOLS) != NUM_LIT_STATES)
708 return S_FALSE;
709
710
711 const unsigned kPad = 16;
712
713 // ---------- Decode literals ----------
714
715 {
716 _literals.AllocAtLeast(LITERALS_PER_BLOCK + 16);
717 _buffer.AllocAtLeast(kPad + litPayloadSize);
718 memset(_buffer, 0, kPad);
719
720 if (m_InStream.ReadBytes(_buffer + kPad, litPayloadSize) != litPayloadSize)
721 return S_FALSE;
722
723 UInt32 lit_decoder[NUM_LIT_STATES];
724 InitLitTable(freqs_LIT, lit_decoder);
725
726 const Byte *buf_start = _buffer + kPad;
727 const Byte *buf_check = buf_start - 4;
728 const Byte *buf = buf_start + litPayloadSize;
729 CBitStream in;
730 if (FseInStream_Init(&in, literal_bits, &buf) != 0)
731 return S_FALSE;
732
733 Byte *lit = _literals;
734 const Byte *lit_limit = lit + numLiterals;
735 for (; lit < lit_limit; lit += 4)
736 {
737 FseInStream_FLUSH
738 DECODE_LIT (lit[0], lit_state_0)
739 DECODE_LIT (lit[1], lit_state_1)
740 FseInStream_FLUSH
741 DECODE_LIT (lit[2], lit_state_2)
742 DECODE_LIT (lit[3], lit_state_3)
743 }
744
745 if ((buf_start - buf) * 8 != (int)in.numBits)
746 return S_FALSE;
747 }
748
749
750 // ---------- Decode LMD ----------
751
752 _buffer.AllocAtLeast(kPad + lmdPayloadSize);
753 memset(_buffer, 0, kPad);
754 if (m_InStream.ReadBytes(_buffer + kPad, lmdPayloadSize) != lmdPayloadSize)
755 return S_FALSE;
756
757 CExtraEntry l_decoder[NUM_L_STATES];
758 CExtraEntry m_decoder[NUM_M_STATES];
759 CExtraEntry d_decoder[NUM_D_STATES];
760
761 InitExtraDecoderTable(NUM_L_STATES, NUM_L_SYMBOLS, freqs_L, k_L_extra, l_decoder);
762 InitExtraDecoderTable(NUM_M_STATES, NUM_M_SYMBOLS, freqs_M, k_M_extra, m_decoder);
763 InitExtraDecoderTable(NUM_D_STATES, NUM_D_SYMBOLS, freqs_D, k_D_extra, d_decoder);
764
765 const Byte *buf_start = _buffer + kPad;
766 const Byte *buf_check = buf_start - 4;
767 const Byte *buf = buf_start + lmdPayloadSize;
768 CBitStream in;
769 if (FseInStream_Init(&in, lmd_bits, &buf))
770 return S_FALSE;
771
772 const Byte *lit = _literals;
773 const Byte *lit_limit = lit + numLiterals;
774
775 UInt32 D = 0;
776
777 for (;;)
778 {
779 if (numMatches == 0)
780 break;
781 numMatches--;
782
783 FseInStream_FLUSH
784
785 unsigned L = (unsigned)FseDecodeExtra(&l_state, l_decoder, &in);
786
787 FseInStream_FLUSH
788
789 unsigned M = (unsigned)FseDecodeExtra(&m_state, m_decoder, &in);
790
791 FseInStream_FLUSH
792
793 {
794 UInt32 new_D = FseDecodeExtra(&d_state, d_decoder, &in);
795 if (new_D)
796 D = new_D;
797 }
798
799 if (L != 0)
800 {
801 if (L > (size_t)(lit_limit - lit))
802 return S_FALSE;
803 unsigned cur = L;
804 if (cur > unpackSize)
805 cur = (unsigned)unpackSize;
806 m_OutWindowStream.PutBytes(lit, cur);
807 unpackSize -= cur;
808 lit += cur;
809 if (cur != L)
810 return S_FALSE;
811 }
812
813 if (M != 0)
814 {
815 if (unpackSize == 0 || D == 0)
816 return S_FALSE;
817 unsigned cur = M;
818 if (cur > unpackSize)
819 cur = (unsigned)unpackSize;
820 if (!m_OutWindowStream.CopyBlock(D - 1, cur))
821 return S_FALSE;
822 unpackSize -= cur;
823 if (cur != M)
824 return S_FALSE;
825 }
826 }
827
828 if (unpackSize != 0)
829 return S_FALSE;
830
831 // LZFSE encoder writes 8 additional zero bytes before LMD payload
832 // We test it:
833 if ((size_t)(buf - buf_start) * 8 + in.numBits != 64)
834 return S_FALSE;
835 if (GetUi64(buf_start) != 0)
836 return S_FALSE;
837
838 return S_OK;
839 }
840
841
CodeReal(ISequentialInStream * inStream,ISequentialOutStream * outStream,const UInt64 * inSize,const UInt64 * outSize,ICompressProgressInfo * progress)842 HRESULT CDecoder::CodeReal(ISequentialInStream *inStream, ISequentialOutStream *outStream,
843 const UInt64 *inSize, const UInt64 *outSize, ICompressProgressInfo *progress)
844 {
845 PRF(printf("\n\nLzfseDecoder %7u %7u\n", (unsigned)*outSize, (unsigned)*inSize));
846
847 const UInt32 kLzfseDictSize = 1 << 18;
848 if (!m_OutWindowStream.Create(kLzfseDictSize))
849 return E_OUTOFMEMORY;
850 if (!m_InStream.Create(1 << 18))
851 return E_OUTOFMEMORY;
852
853 m_OutWindowStream.SetStream(outStream);
854 m_OutWindowStream.Init(false);
855 m_InStream.SetStream(inStream);
856 m_InStream.Init();
857
858 CCoderReleaser coderReleaser(this);
859
860 UInt64 prevOut = 0;
861 UInt64 prevIn = 0;
862
863 if (LzvnMode)
864 {
865 if (!outSize || !inSize)
866 return E_NOTIMPL;
867 const UInt64 unpackSize = *outSize;
868 const UInt64 packSize = *inSize;
869 if (unpackSize > (UInt32)(Int32)-1
870 || packSize > (UInt32)(Int32)-1)
871 return S_FALSE;
872 RINOK(DecodeLzvn((UInt32)unpackSize, (UInt32)packSize))
873 }
874 else
875 for (;;)
876 {
877 const UInt64 pos = m_OutWindowStream.GetProcessedSize();
878 const UInt64 packPos = m_InStream.GetProcessedSize();
879
880 if (progress && ((pos - prevOut) >= (1 << 22) || (packPos - prevIn) >= (1 << 22)))
881 {
882 RINOK(progress->SetRatioInfo(&packPos, &pos))
883 prevIn = packPos;
884 prevOut = pos;
885 }
886
887 UInt32 v;
888 RINOK(GetUInt32(v))
889 if ((v & 0xFFFFFF) != 0x787662) // bvx
890 return S_FALSE;
891 v >>= 24;
892
893 if (v == 0x24) // '$', end of stream
894 break;
895
896 UInt32 unpackSize;
897 RINOK(GetUInt32(unpackSize))
898
899 UInt32 cur = unpackSize;
900 if (outSize)
901 {
902 const UInt64 rem = *outSize - pos;
903 if (cur > rem)
904 cur = (UInt32)rem;
905 }
906 unpackSize -= cur;
907
908 HRESULT res;
909 if (v == kSignature_LZFSE_V1 || v == kSignature_LZFSE_V2)
910 res = DecodeLzfse(cur, (Byte)v);
911 else if (v == 0x6E) // 'n'
912 {
913 UInt32 packSize;
914 res = GetUInt32(packSize);
915 if (res == S_OK)
916 res = DecodeLzvn(cur, packSize);
917 }
918 else if (v == 0x2D) // '-'
919 res = DecodeUncompressed(cur);
920 else
921 return E_NOTIMPL;
922
923 if (res != S_OK)
924 return res;
925
926 if (unpackSize != 0)
927 return S_FALSE;
928 }
929
930 coderReleaser.NeedFlush = false;
931 HRESULT res = m_OutWindowStream.Flush();
932 if (res == S_OK)
933 if ((!LzvnMode && inSize && *inSize != m_InStream.GetProcessedSize())
934 || (outSize && *outSize != m_OutWindowStream.GetProcessedSize()))
935 res = S_FALSE;
936 return res;
937 }
938
939
Z7_COM7F_IMF(CDecoder::Code (ISequentialInStream * inStream,ISequentialOutStream * outStream,const UInt64 * inSize,const UInt64 * outSize,ICompressProgressInfo * progress))940 Z7_COM7F_IMF(CDecoder::Code(ISequentialInStream *inStream, ISequentialOutStream *outStream,
941 const UInt64 *inSize, const UInt64 *outSize, ICompressProgressInfo *progress))
942 {
943 try { return CodeReal(inStream, outStream, inSize, outSize, progress); }
944 catch(const CInBufferException &e) { return e.ErrorCode; }
945 catch(const CLzOutWindowException &e) { return e.ErrorCode; }
946 catch(...) { return E_OUTOFMEMORY; }
947 // catch(...) { return S_FALSE; }
948 }
949
950 }}
951