source: thirdparty/blosc/internal-complibs/zstd-0.7.4/decompress/zstd_decompress.c @ 8ebc79b

Revision 8ebc79b, 52.0 KB checked in by Hal Finkel <hfinkel@…>, 8 years ago (diff)

Add the other internal compression libraries from blocs
  • Property mode set to 100644
RevLine 
[8ebc79b]1/*
2    zstd - standard compression library
3    Copyright (C) 2014-2016, Yann Collet.
4
5    BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
6
7    Redistribution and use in source and binary forms, with or without
8    modification, are permitted provided that the following conditions are
9    met:
10    * Redistributions of source code must retain the above copyright
11    notice, this list of conditions and the following disclaimer.
12    * Redistributions in binary form must reproduce the above
13    copyright notice, this list of conditions and the following disclaimer
14    in the documentation and/or other materials provided with the
15    distribution.
16    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19    A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20    OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21    SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22    LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23    DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24    THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25    (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27
28    You can contact the author at :
29    - zstd homepage : http://www.zstd.net
30*/
31
32/* ***************************************************************
33*  Tuning parameters
34*****************************************************************/
35/*!
36 * HEAPMODE :
37 * Select how default decompression function ZSTD_decompress() will allocate memory,
38 * in memory stack (0), or in memory heap (1, requires malloc())
39 */
40#ifndef ZSTD_HEAPMODE
41#  define ZSTD_HEAPMODE 1
42#endif
43
44/*!
45*  LEGACY_SUPPORT :
46*  if set to 1, ZSTD_decompress() can decode older formats (v0.1+)
47*/
48#ifndef ZSTD_LEGACY_SUPPORT
49#  define ZSTD_LEGACY_SUPPORT 0
50#endif
51
52
53/*-*******************************************************
54*  Dependencies
55*********************************************************/
56#include <string.h>      /* memcpy, memmove, memset */
57#include <stdio.h>       /* debug only : printf */
58#include "mem.h"         /* low level memory routines */
59#define XXH_STATIC_LINKING_ONLY   /* XXH64_state_t */
60#include "xxhash.h"      /* XXH64_* */
61#define FSE_STATIC_LINKING_ONLY
62#include "fse.h"
63#define HUF_STATIC_LINKING_ONLY
64#include "huf.h"
65#include "zstd_internal.h"
66
67#if defined(ZSTD_LEGACY_SUPPORT) && (ZSTD_LEGACY_SUPPORT>=1)
68#  include "zstd_legacy.h"
69#endif
70
71
72/*-*******************************************************
73*  Compiler specifics
74*********************************************************/
75#ifdef _MSC_VER    /* Visual Studio */
76#  define FORCE_INLINE static __forceinline
77#  include <intrin.h>                    /* For Visual 2005 */
78#  pragma warning(disable : 4127)        /* disable: C4127: conditional expression is constant */
79#  pragma warning(disable : 4324)        /* disable: C4324: padded structure */
80#else
81#  ifdef __GNUC__
82#    define FORCE_INLINE static inline __attribute__((always_inline))
83#  else
84#    define FORCE_INLINE static inline
85#  endif
86#endif
87
88
89/*-*************************************
90*  Macros
91***************************************/
92#define ZSTD_isError ERR_isError   /* for inlining */
93#define FSE_isError  ERR_isError
94#define HUF_isError  ERR_isError
95
96
97/*_*******************************************************
98*  Memory operations
99**********************************************************/
100static void ZSTD_copy4(void* dst, const void* src) { memcpy(dst, src, 4); }
101
102
103/*-*************************************************************
104*   Context management
105***************************************************************/
106typedef enum { ZSTDds_getFrameHeaderSize, ZSTDds_decodeFrameHeader,
107               ZSTDds_decodeBlockHeader, ZSTDds_decompressBlock,
108               ZSTDds_decodeSkippableHeader, ZSTDds_skipFrame } ZSTD_dStage;
109
110struct ZSTD_DCtx_s
111{
112    FSE_DTable LLTable[FSE_DTABLE_SIZE_U32(LLFSELog)];
113    FSE_DTable OffTable[FSE_DTABLE_SIZE_U32(OffFSELog)];
114    FSE_DTable MLTable[FSE_DTABLE_SIZE_U32(MLFSELog)];
115    HUF_DTable hufTable[HUF_DTABLE_SIZE(HufLog)];  /* can accommodate HUF_decompress4X */
116    const void* previousDstEnd;
117    const void* base;
118    const void* vBase;
119    const void* dictEnd;
120    size_t expected;
121    U32 rep[3];
122    ZSTD_frameParams fParams;
123    blockType_t bType;   /* used in ZSTD_decompressContinue(), to transfer blockType between header decoding and block decoding stages */
124    ZSTD_dStage stage;
125    U32 litEntropy;
126    U32 fseEntropy;
127    XXH64_state_t xxhState;
128    size_t headerSize;
129    U32 dictID;
130    const BYTE* litPtr;
131    ZSTD_customMem customMem;
132    size_t litBufSize;
133    size_t litSize;
134    BYTE litBuffer[ZSTD_BLOCKSIZE_MAX + WILDCOPY_OVERLENGTH];
135    BYTE headerBuffer[ZSTD_FRAMEHEADERSIZE_MAX];
136};  /* typedef'd to ZSTD_DCtx within "zstd_static.h" */
137
138size_t ZSTD_sizeofDCtx (const ZSTD_DCtx* dctx) { return sizeof(*dctx); }
139
140size_t ZSTD_estimateDCtxSize(void) { return sizeof(ZSTD_DCtx); }
141
142size_t ZSTD_decompressBegin(ZSTD_DCtx* dctx)
143{
144    dctx->expected = ZSTD_frameHeaderSize_min;
145    dctx->stage = ZSTDds_getFrameHeaderSize;
146    dctx->previousDstEnd = NULL;
147    dctx->base = NULL;
148    dctx->vBase = NULL;
149    dctx->dictEnd = NULL;
150    dctx->hufTable[0] = (HUF_DTable)((HufLog)*0x1000001);
151    dctx->litEntropy = dctx->fseEntropy = 0;
152    dctx->dictID = 0;
153    { int i; for (i=0; i<ZSTD_REP_NUM; i++) dctx->rep[i] = repStartValue[i]; }
154    return 0;
155}
156
157ZSTD_DCtx* ZSTD_createDCtx_advanced(ZSTD_customMem customMem)
158{
159    ZSTD_DCtx* dctx;
160
161    if (!customMem.customAlloc && !customMem.customFree)
162        customMem = defaultCustomMem;
163
164    if (!customMem.customAlloc || !customMem.customFree)
165        return NULL;
166
167    dctx = (ZSTD_DCtx*) customMem.customAlloc(customMem.opaque, sizeof(ZSTD_DCtx));
168    if (!dctx) return NULL;
169    memcpy(&dctx->customMem, &customMem, sizeof(ZSTD_customMem));
170    ZSTD_decompressBegin(dctx);
171    return dctx;
172}
173
174ZSTD_DCtx* ZSTD_createDCtx(void)
175{
176    return ZSTD_createDCtx_advanced(defaultCustomMem);
177}
178
179size_t ZSTD_freeDCtx(ZSTD_DCtx* dctx)
180{
181    if (dctx==NULL) return 0;   /* support free on NULL */
182    dctx->customMem.customFree(dctx->customMem.opaque, dctx);
183    return 0;   /* reserved as a potential error code in the future */
184}
185
186void ZSTD_copyDCtx(ZSTD_DCtx* dstDCtx, const ZSTD_DCtx* srcDCtx)
187{
188    memcpy(dstDCtx, srcDCtx,
189           sizeof(ZSTD_DCtx) - (ZSTD_BLOCKSIZE_MAX+WILDCOPY_OVERLENGTH + ZSTD_frameHeaderSize_max));  /* no need to copy workspace */
190}
191
192
193/*-*************************************************************
194*   Decompression section
195***************************************************************/
196
197/* Frame format description
198   Frame Header -  [ Block Header - Block ] - Frame End
199   1) Frame Header
200      - 4 bytes - Magic Number : ZSTD_MAGICNUMBER (defined within zstd.h)
201      - 1 byte  - Frame Descriptor
202   2) Block Header
203      - 3 bytes, starting with a 2-bits descriptor
204                 Uncompressed, Compressed, Frame End, unused
205   3) Block
206      See Block Format Description
207   4) Frame End
208      - 3 bytes, compatible with Block Header
209*/
210
211
212/* Frame Header :
213
214   1 byte - FrameHeaderDescription :
215   bit 0-1 : dictID (0, 1, 2 or 4 bytes)
216   bit 2   : checksumFlag
217   bit 3   : reserved (must be zero)
218   bit 4   : reserved (unused, can be any value)
219   bit 5   : Single Segment (if 1, WindowLog byte is not present)
220   bit 6-7 : FrameContentFieldSize (0, 2, 4, or 8)
221             if (SkippedWindowLog && !FrameContentFieldsize) FrameContentFieldsize=1;
222
223   Optional : WindowLog (0 or 1 byte)
224   bit 0-2 : octal Fractional (1/8th)
225   bit 3-7 : Power of 2, with 0 = 1 KB (up to 2 TB)
226
227   Optional : dictID (0, 1, 2 or 4 bytes)
228   Automatic adaptation
229   0 : no dictID
230   1 : 1 - 255
231   2 : 256 - 65535
232   4 : all other values
233
234   Optional : content size (0, 1, 2, 4 or 8 bytes)
235   0 : unknown          (fcfs==0 and swl==0)
236   1 : 0-255 bytes      (fcfs==0 and swl==1)
237   2 : 256 - 65535+256  (fcfs==1)
238   4 : 0 - 4GB-1        (fcfs==2)
239   8 : 0 - 16EB-1       (fcfs==3)
240*/
241
242
243/* Compressed Block, format description
244
245   Block = Literal Section - Sequences Section
246   Prerequisite : size of (compressed) block, maximum size of regenerated data
247
248   1) Literal Section
249
250   1.1) Header : 1-5 bytes
251        flags: 2 bits
252            00 compressed by Huff0
253            01 unused
254            10 is Raw (uncompressed)
255            11 is Rle
256            Note : using 01 => Huff0 with precomputed table ?
257            Note : delta map ? => compressed ?
258
259   1.1.1) Huff0-compressed literal block : 3-5 bytes
260            srcSize < 1 KB => 3 bytes (2-2-10-10) => single stream
261            srcSize < 1 KB => 3 bytes (2-2-10-10)
262            srcSize < 16KB => 4 bytes (2-2-14-14)
263            else           => 5 bytes (2-2-18-18)
264            big endian convention
265
266   1.1.2) Raw (uncompressed) literal block header : 1-3 bytes
267        size :  5 bits: (IS_RAW<<6) + (0<<4) + size
268               12 bits: (IS_RAW<<6) + (2<<4) + (size>>8)
269                        size&255
270               20 bits: (IS_RAW<<6) + (3<<4) + (size>>16)
271                        size>>8&255
272                        size&255
273
274   1.1.3) Rle (repeated single byte) literal block header : 1-3 bytes
275        size :  5 bits: (IS_RLE<<6) + (0<<4) + size
276               12 bits: (IS_RLE<<6) + (2<<4) + (size>>8)
277                        size&255
278               20 bits: (IS_RLE<<6) + (3<<4) + (size>>16)
279                        size>>8&255
280                        size&255
281
282   1.1.4) Huff0-compressed literal block, using precomputed CTables : 3-5 bytes
283            srcSize < 1 KB => 3 bytes (2-2-10-10) => single stream
284            srcSize < 1 KB => 3 bytes (2-2-10-10)
285            srcSize < 16KB => 4 bytes (2-2-14-14)
286            else           => 5 bytes (2-2-18-18)
287            big endian convention
288
289        1- CTable available (stored into workspace ?)
290        2- Small input (fast heuristic ? Full comparison ? depend on clevel ?)
291
292
293   1.2) Literal block content
294
295   1.2.1) Huff0 block, using sizes from header
296        See Huff0 format
297
298   1.2.2) Huff0 block, using prepared table
299
300   1.2.3) Raw content
301
302   1.2.4) single byte
303
304
305   2) Sequences section
306      TO DO
307*/
308
309/** ZSTD_frameHeaderSize() :
310*   srcSize must be >= ZSTD_frameHeaderSize_min.
311*   @return : size of the Frame Header */
312static size_t ZSTD_frameHeaderSize(const void* src, size_t srcSize)
313{
314    if (srcSize < ZSTD_frameHeaderSize_min) return ERROR(srcSize_wrong);
315    {   BYTE const fhd = ((const BYTE*)src)[4];
316        U32 const dictID= fhd & 3;
317        U32 const directMode = (fhd >> 5) & 1;
318        U32 const fcsId = fhd >> 6;
319        return ZSTD_frameHeaderSize_min + !directMode + ZSTD_did_fieldSize[dictID] + ZSTD_fcs_fieldSize[fcsId]
320                + (directMode && !ZSTD_fcs_fieldSize[fcsId]);
321    }
322}
323
324
325/** ZSTD_getFrameParams() :
326*   decode Frame Header, or require larger `srcSize`.
327*   @return : 0, `fparamsPtr` is correctly filled,
328*            >0, `srcSize` is too small, result is expected `srcSize`,
329*             or an error code, which can be tested using ZSTD_isError() */
330size_t ZSTD_getFrameParams(ZSTD_frameParams* fparamsPtr, const void* src, size_t srcSize)
331{
332    const BYTE* ip = (const BYTE*)src;
333
334    if (srcSize < ZSTD_frameHeaderSize_min) return ZSTD_frameHeaderSize_min;
335    if (MEM_readLE32(src) != ZSTD_MAGICNUMBER) {
336        if ((MEM_readLE32(src) & 0xFFFFFFF0U) == ZSTD_MAGIC_SKIPPABLE_START) {
337            if (srcSize < ZSTD_skippableHeaderSize) return ZSTD_skippableHeaderSize; /* magic number + skippable frame length */
338            memset(fparamsPtr, 0, sizeof(*fparamsPtr));
339            fparamsPtr->frameContentSize = MEM_readLE32((const char *)src + 4);
340            fparamsPtr->windowSize = 0; /* windowSize==0 means a frame is skippable */
341            return 0;
342        }
343        return ERROR(prefix_unknown);
344    }
345
346    /* ensure there is enough `srcSize` to fully read/decode frame header */
347    { size_t const fhsize = ZSTD_frameHeaderSize(src, srcSize);
348      if (srcSize < fhsize) return fhsize; }
349
350    {   BYTE const fhdByte = ip[4];
351        size_t pos = 5;
352        U32 const dictIDSizeCode = fhdByte&3;
353        U32 const checksumFlag = (fhdByte>>2)&1;
354        U32 const directMode = (fhdByte>>5)&1;
355        U32 const fcsID = fhdByte>>6;
356        U32 const windowSizeMax = 1U << ZSTD_WINDOWLOG_MAX;
357        U32 windowSize = 0;
358        U32 dictID = 0;
359        U64 frameContentSize = 0;
360        if ((fhdByte & 0x08) != 0) return ERROR(frameParameter_unsupported);   /* reserved bits, which must be zero */
361        if (!directMode) {
362            BYTE const wlByte = ip[pos++];
363            U32 const windowLog = (wlByte >> 3) + ZSTD_WINDOWLOG_ABSOLUTEMIN;
364            if (windowLog > ZSTD_WINDOWLOG_MAX) return ERROR(frameParameter_unsupported);
365            windowSize = (1U << windowLog);
366            windowSize += (windowSize >> 3) * (wlByte&7);
367        }
368
369        switch(dictIDSizeCode)
370        {
371            default:   /* impossible */
372            case 0 : break;
373            case 1 : dictID = ip[pos]; pos++; break;
374            case 2 : dictID = MEM_readLE16(ip+pos); pos+=2; break;
375            case 3 : dictID = MEM_readLE32(ip+pos); pos+=4; break;
376        }
377        switch(fcsID)
378        {
379            default:   /* impossible */
380            case 0 : if (directMode) frameContentSize = ip[pos]; break;
381            case 1 : frameContentSize = MEM_readLE16(ip+pos)+256; break;
382            case 2 : frameContentSize = MEM_readLE32(ip+pos); break;
383            case 3 : frameContentSize = MEM_readLE64(ip+pos); break;
384        }
385        if (!windowSize) windowSize = (U32)frameContentSize;
386        if (windowSize > windowSizeMax) return ERROR(frameParameter_unsupported);
387        fparamsPtr->frameContentSize = frameContentSize;
388        fparamsPtr->windowSize = windowSize;
389        fparamsPtr->dictID = dictID;
390        fparamsPtr->checksumFlag = checksumFlag;
391    }
392    return 0;
393}
394
395
396/** ZSTD_getDecompressedSize() :
397*   compatible with legacy mode
398*   @return : decompressed size if known, 0 otherwise
399              note : 0 can mean any of the following :
400                   - decompressed size is not provided within frame header
401                   - frame header unknown / not supported
402                   - frame header not completely provided (`srcSize` too small) */
403unsigned long long ZSTD_getDecompressedSize(const void* src, size_t srcSize)
404{
405#if defined(ZSTD_LEGACY_SUPPORT) && (ZSTD_LEGACY_SUPPORT==1)
406    if (ZSTD_isLegacy(src, srcSize)) return ZSTD_getDecompressedSize_legacy(src, srcSize);
407#endif
408    {   ZSTD_frameParams fparams;
409        size_t const frResult = ZSTD_getFrameParams(&fparams, src, srcSize);
410        if (frResult!=0) return 0;
411        return fparams.frameContentSize;
412    }
413}
414
415
416/** ZSTD_decodeFrameHeader() :
417*   `srcSize` must be the size provided by ZSTD_frameHeaderSize().
418*   @return : 0 if success, or an error code, which can be tested using ZSTD_isError() */
419static size_t ZSTD_decodeFrameHeader(ZSTD_DCtx* dctx, const void* src, size_t srcSize)
420{
421    size_t const result = ZSTD_getFrameParams(&(dctx->fParams), src, srcSize);
422    if (dctx->fParams.dictID && (dctx->dictID != dctx->fParams.dictID)) return ERROR(dictionary_wrong);
423    if (dctx->fParams.checksumFlag) XXH64_reset(&dctx->xxhState, 0);
424    return result;
425}
426
427
428typedef struct
429{
430    blockType_t blockType;
431    U32 origSize;
432} blockProperties_t;
433
434/*! ZSTD_getcBlockSize() :
435*   Provides the size of compressed block from block header `src` */
436size_t ZSTD_getcBlockSize(const void* src, size_t srcSize, blockProperties_t* bpPtr)
437{
438    const BYTE* const in = (const BYTE* const)src;
439    U32 cSize;
440
441    if (srcSize < ZSTD_blockHeaderSize) return ERROR(srcSize_wrong);
442
443    bpPtr->blockType = (blockType_t)((*in) >> 6);
444    cSize = in[2] + (in[1]<<8) + ((in[0] & 7)<<16);
445    bpPtr->origSize = (bpPtr->blockType == bt_rle) ? cSize : 0;
446
447    if (bpPtr->blockType == bt_end) return 0;
448    if (bpPtr->blockType == bt_rle) return 1;
449    return cSize;
450}
451
452
453static size_t ZSTD_copyRawBlock(void* dst, size_t dstCapacity, const void* src, size_t srcSize)
454{
455    if (srcSize > dstCapacity) return ERROR(dstSize_tooSmall);
456    memcpy(dst, src, srcSize);
457    return srcSize;
458}
459
460
461/*! ZSTD_decodeLiteralsBlock() :
462    @return : nb of bytes read from src (< srcSize ) */
463size_t ZSTD_decodeLiteralsBlock(ZSTD_DCtx* dctx,
464                          const void* src, size_t srcSize)   /* note : srcSize < BLOCKSIZE */
465{
466    const BYTE* const istart = (const BYTE*) src;
467
468    if (srcSize < MIN_CBLOCK_SIZE) return ERROR(corruption_detected);
469
470    switch((litBlockType_t)(istart[0]>> 6))
471    {
472    case lbt_huffman:
473        {   size_t litSize, litCSize, singleStream=0;
474            U32 lhSize = (istart[0] >> 4) & 3;
475            if (srcSize < 5) return ERROR(corruption_detected);   /* srcSize >= MIN_CBLOCK_SIZE == 3; here we need up to 5 for lhSize, + cSize (+nbSeq) */
476            switch(lhSize)
477            {
478            case 0: case 1: default:   /* note : default is impossible, since lhSize into [0..3] */
479                /* 2 - 2 - 10 - 10 */
480                lhSize=3;
481                singleStream = istart[0] & 16;
482                litSize  = ((istart[0] & 15) << 6) + (istart[1] >> 2);
483                litCSize = ((istart[1] &  3) << 8) + istart[2];
484                break;
485            case 2:
486                /* 2 - 2 - 14 - 14 */
487                lhSize=4;
488                litSize  = ((istart[0] & 15) << 10) + (istart[1] << 2) + (istart[2] >> 6);
489                litCSize = ((istart[2] & 63) <<  8) + istart[3];
490                break;
491            case 3:
492                /* 2 - 2 - 18 - 18 */
493                lhSize=5;
494                litSize  = ((istart[0] & 15) << 14) + (istart[1] << 6) + (istart[2] >> 2);
495                litCSize = ((istart[2] &  3) << 16) + (istart[3] << 8) + istart[4];
496                break;
497            }
498            if (litSize > ZSTD_BLOCKSIZE_MAX) return ERROR(corruption_detected);
499            if (litCSize + lhSize > srcSize) return ERROR(corruption_detected);
500
501            if (HUF_isError(singleStream ?
502                            HUF_decompress1X2_DCtx(dctx->hufTable, dctx->litBuffer, litSize, istart+lhSize, litCSize) :
503                            HUF_decompress4X_hufOnly (dctx->hufTable, dctx->litBuffer, litSize, istart+lhSize, litCSize) ))
504                return ERROR(corruption_detected);
505
506            dctx->litPtr = dctx->litBuffer;
507            dctx->litBufSize = ZSTD_BLOCKSIZE_MAX+8;
508            dctx->litSize = litSize;
509            dctx->litEntropy = 1;
510            return litCSize + lhSize;
511        }
512    case lbt_repeat:
513        {   size_t litSize, litCSize;
514            U32 lhSize = ((istart[0]) >> 4) & 3;
515            if (lhSize != 1)  /* only case supported for now : small litSize, single stream */
516                return ERROR(corruption_detected);
517            if (dctx->litEntropy==0)
518                return ERROR(dictionary_corrupted);
519
520            /* 2 - 2 - 10 - 10 */
521            lhSize=3;
522            litSize  = ((istart[0] & 15) << 6) + (istart[1] >> 2);
523            litCSize = ((istart[1] &  3) << 8) + istart[2];
524            if (litCSize + lhSize > srcSize) return ERROR(corruption_detected);
525
526            {   size_t const errorCode = HUF_decompress1X4_usingDTable(dctx->litBuffer, litSize, istart+lhSize, litCSize, dctx->hufTable);
527                if (HUF_isError(errorCode)) return ERROR(corruption_detected);
528            }
529            dctx->litPtr = dctx->litBuffer;
530            dctx->litBufSize = ZSTD_BLOCKSIZE_MAX+WILDCOPY_OVERLENGTH;
531            dctx->litSize = litSize;
532            return litCSize + lhSize;
533        }
534    case lbt_raw:
535        {   size_t litSize;
536            U32 lhSize = ((istart[0]) >> 4) & 3;
537            switch(lhSize)
538            {
539            case 0: case 1: default:   /* note : default is impossible, since lhSize into [0..3] */
540                lhSize=1;
541                litSize = istart[0] & 31;
542                break;
543            case 2:
544                litSize = ((istart[0] & 15) << 8) + istart[1];
545                break;
546            case 3:
547                litSize = ((istart[0] & 15) << 16) + (istart[1] << 8) + istart[2];
548                break;
549            }
550
551            if (lhSize+litSize+WILDCOPY_OVERLENGTH > srcSize) {  /* risk reading beyond src buffer with wildcopy */
552                if (litSize+lhSize > srcSize) return ERROR(corruption_detected);
553                memcpy(dctx->litBuffer, istart+lhSize, litSize);
554                dctx->litPtr = dctx->litBuffer;
555                dctx->litBufSize = ZSTD_BLOCKSIZE_MAX+8;
556                dctx->litSize = litSize;
557                return lhSize+litSize;
558            }
559            /* direct reference into compressed stream */
560            dctx->litPtr = istart+lhSize;
561            dctx->litBufSize = srcSize-lhSize;
562            dctx->litSize = litSize;
563            return lhSize+litSize;
564        }
565    case lbt_rle:
566        {   size_t litSize;
567            U32 lhSize = ((istart[0]) >> 4) & 3;
568            switch(lhSize)
569            {
570            case 0: case 1: default:   /* note : default is impossible, since lhSize into [0..3] */
571                lhSize = 1;
572                litSize = istart[0] & 31;
573                break;
574            case 2:
575                litSize = ((istart[0] & 15) << 8) + istart[1];
576                break;
577            case 3:
578                litSize = ((istart[0] & 15) << 16) + (istart[1] << 8) + istart[2];
579                if (srcSize<4) return ERROR(corruption_detected);   /* srcSize >= MIN_CBLOCK_SIZE == 3; here we need lhSize+1 = 4 */
580                break;
581            }
582            if (litSize > ZSTD_BLOCKSIZE_MAX) return ERROR(corruption_detected);
583            memset(dctx->litBuffer, istart[lhSize], litSize);
584            dctx->litPtr = dctx->litBuffer;
585            dctx->litBufSize = ZSTD_BLOCKSIZE_MAX+WILDCOPY_OVERLENGTH;
586            dctx->litSize = litSize;
587            return lhSize+1;
588        }
589    default:
590        return ERROR(corruption_detected);   /* impossible */
591    }
592}
593
594
595/*! ZSTD_buildSeqTable() :
596    @return : nb bytes read from src,
597              or an error code if it fails, testable with ZSTD_isError()
598*/
599FORCE_INLINE size_t ZSTD_buildSeqTable(FSE_DTable* DTable, U32 type, U32 max, U32 maxLog,
600                                 const void* src, size_t srcSize,
601                                 const S16* defaultNorm, U32 defaultLog, U32 flagRepeatTable)
602{
603    switch(type)
604    {
605    case FSE_ENCODING_RLE :
606        if (!srcSize) return ERROR(srcSize_wrong);
607        if ( (*(const BYTE*)src) > max) return ERROR(corruption_detected);
608        FSE_buildDTable_rle(DTable, *(const BYTE*)src);   /* if *src > max, data is corrupted */
609        return 1;
610    case FSE_ENCODING_RAW :
611        FSE_buildDTable(DTable, defaultNorm, max, defaultLog);
612        return 0;
613    case FSE_ENCODING_STATIC:
614        if (!flagRepeatTable) return ERROR(corruption_detected);
615        return 0;
616    default :   /* impossible */
617    case FSE_ENCODING_DYNAMIC :
618        {   U32 tableLog;
619            S16 norm[MaxSeq+1];
620            size_t const headerSize = FSE_readNCount(norm, &max, &tableLog, src, srcSize);
621            if (FSE_isError(headerSize)) return ERROR(corruption_detected);
622            if (tableLog > maxLog) return ERROR(corruption_detected);
623            FSE_buildDTable(DTable, norm, max, tableLog);
624            return headerSize;
625    }   }
626}
627
628
629size_t ZSTD_decodeSeqHeaders(int* nbSeqPtr,
630                             FSE_DTable* DTableLL, FSE_DTable* DTableML, FSE_DTable* DTableOffb, U32 flagRepeatTable,
631                             const void* src, size_t srcSize)
632{
633    const BYTE* const istart = (const BYTE* const)src;
634    const BYTE* const iend = istart + srcSize;
635    const BYTE* ip = istart;
636
637    /* check */
638    if (srcSize < MIN_SEQUENCES_SIZE) return ERROR(srcSize_wrong);
639
640    /* SeqHead */
641    {   int nbSeq = *ip++;
642        if (!nbSeq) { *nbSeqPtr=0; return 1; }
643        if (nbSeq > 0x7F) {
644            if (nbSeq == 0xFF)
645                nbSeq = MEM_readLE16(ip) + LONGNBSEQ, ip+=2;
646            else
647                nbSeq = ((nbSeq-0x80)<<8) + *ip++;
648        }
649        *nbSeqPtr = nbSeq;
650    }
651
652    /* FSE table descriptors */
653    {   U32 const LLtype  = *ip >> 6;
654        U32 const OFtype = (*ip >> 4) & 3;
655        U32 const MLtype  = (*ip >> 2) & 3;
656        ip++;
657
658        /* check */
659        if (ip > iend-3) return ERROR(srcSize_wrong); /* min : all 3 are "raw", hence no header, but at least xxLog bits per type */
660
661        /* Build DTables */
662        {   size_t const llhSize = ZSTD_buildSeqTable(DTableLL, LLtype, MaxLL, LLFSELog, ip, iend-ip, LL_defaultNorm, LL_defaultNormLog, flagRepeatTable);
663            if (ZSTD_isError(llhSize)) return ERROR(corruption_detected);
664            ip += llhSize;
665        }
666        {   size_t const ofhSize = ZSTD_buildSeqTable(DTableOffb, OFtype, MaxOff, OffFSELog, ip, iend-ip, OF_defaultNorm, OF_defaultNormLog, flagRepeatTable);
667            if (ZSTD_isError(ofhSize)) return ERROR(corruption_detected);
668            ip += ofhSize;
669        }
670        {   size_t const mlhSize = ZSTD_buildSeqTable(DTableML, MLtype, MaxML, MLFSELog, ip, iend-ip, ML_defaultNorm, ML_defaultNormLog, flagRepeatTable);
671            if (ZSTD_isError(mlhSize)) return ERROR(corruption_detected);
672            ip += mlhSize;
673    }   }
674
675    return ip-istart;
676}
677
678
679typedef struct {
680    size_t litLength;
681    size_t matchLength;
682    size_t offset;
683} seq_t;
684
685typedef struct {
686    BIT_DStream_t DStream;
687    FSE_DState_t stateLL;
688    FSE_DState_t stateOffb;
689    FSE_DState_t stateML;
690    size_t prevOffset[ZSTD_REP_INIT];
691} seqState_t;
692
693
694static seq_t ZSTD_decodeSequence(seqState_t* seqState)
695{
696    seq_t seq;
697
698    U32 const llCode = FSE_peekSymbol(&(seqState->stateLL));
699    U32 const mlCode = FSE_peekSymbol(&(seqState->stateML));
700    U32 const ofCode = FSE_peekSymbol(&(seqState->stateOffb));   /* <= maxOff, by table construction */
701
702    U32 const llBits = LL_bits[llCode];
703    U32 const mlBits = ML_bits[mlCode];
704    U32 const ofBits = ofCode;
705    U32 const totalBits = llBits+mlBits+ofBits;
706
707    static const U32 LL_base[MaxLL+1] = {
708                             0,  1,  2,  3,  4,  5,  6,  7,  8,  9,   10,    11,    12,    13,    14,     15,
709                            16, 18, 20, 22, 24, 28, 32, 40, 48, 64, 0x80, 0x100, 0x200, 0x400, 0x800, 0x1000,
710                            0x2000, 0x4000, 0x8000, 0x10000 };
711
712    static const U32 ML_base[MaxML+1] = {
713                             3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13,   14,    15,    16,    17,    18,
714                            19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29,   30,    31,    32,    33,    34,
715                            35, 37, 39, 41, 43, 47, 51, 59, 67, 83, 99, 0x83, 0x103, 0x203, 0x403, 0x803,
716                            0x1003, 0x2003, 0x4003, 0x8003, 0x10003 };
717
718    static const U32 OF_base[MaxOff+1] = {
719                 0,        1,       1,       5,     0xD,     0x1D,     0x3D,     0x7D,
720                 0xFD,   0x1FD,   0x3FD,   0x7FD,   0xFFD,   0x1FFD,   0x3FFD,   0x7FFD,
721                 0xFFFD, 0x1FFFD, 0x3FFFD, 0x7FFFD, 0xFFFFD, 0x1FFFFD, 0x3FFFFD, 0x7FFFFD,
722                 0xFFFFFD, 0x1FFFFFD, 0x3FFFFFD, 0x7FFFFFD, 0xFFFFFFD };
723
724    /* sequence */
725    {   size_t offset;
726        if (!ofCode)
727            offset = 0;
728        else {
729            offset = OF_base[ofCode] + BIT_readBits(&(seqState->DStream), ofBits);   /* <=  (ZSTD_WINDOWLOG_MAX-1) bits */
730            if (MEM_32bits()) BIT_reloadDStream(&(seqState->DStream));
731        }
732
733        if (ofCode <= 1) {
734            if ((llCode == 0) & (offset <= 1)) offset = 1-offset;
735            if (offset) {
736                size_t const temp = seqState->prevOffset[offset];
737                if (offset != 1) seqState->prevOffset[2] = seqState->prevOffset[1];
738                seqState->prevOffset[1] = seqState->prevOffset[0];
739                seqState->prevOffset[0] = offset = temp;
740            } else {
741                offset = seqState->prevOffset[0];
742            }
743        } else {
744            seqState->prevOffset[2] = seqState->prevOffset[1];
745            seqState->prevOffset[1] = seqState->prevOffset[0];
746            seqState->prevOffset[0] = offset;
747        }
748        seq.offset = offset;
749    }
750
751    seq.matchLength = ML_base[mlCode] + ((mlCode>31) ? BIT_readBits(&(seqState->DStream), mlBits) : 0);   /* <=  16 bits */
752    if (MEM_32bits() && (mlBits+llBits>24)) BIT_reloadDStream(&(seqState->DStream));
753
754    seq.litLength = LL_base[llCode] + ((llCode>15) ? BIT_readBits(&(seqState->DStream), llBits) : 0);   /* <=  16 bits */
755    if (MEM_32bits() ||
756       (totalBits > 64 - 7 - (LLFSELog+MLFSELog+OffFSELog)) ) BIT_reloadDStream(&(seqState->DStream));
757
758    /* ANS state update */
759    FSE_updateState(&(seqState->stateLL), &(seqState->DStream));   /* <=  9 bits */
760    FSE_updateState(&(seqState->stateML), &(seqState->DStream));   /* <=  9 bits */
761    if (MEM_32bits()) BIT_reloadDStream(&(seqState->DStream));     /* <= 18 bits */
762    FSE_updateState(&(seqState->stateOffb), &(seqState->DStream)); /* <=  8 bits */
763
764    return seq;
765}
766
767
768FORCE_INLINE
769size_t ZSTD_execSequence(BYTE* op,
770                                BYTE* const oend, seq_t sequence,
771                                const BYTE** litPtr, const BYTE* const litLimit_w,
772                                const BYTE* const base, const BYTE* const vBase, const BYTE* const dictEnd)
773{
774    BYTE* const oLitEnd = op + sequence.litLength;
775    size_t const sequenceLength = sequence.litLength + sequence.matchLength;
776    BYTE* const oMatchEnd = op + sequenceLength;   /* risk : address space overflow (32-bits) */
777    BYTE* const oend_w = oend-WILDCOPY_OVERLENGTH;
778    const BYTE* const iLitEnd = *litPtr + sequence.litLength;
779    const BYTE* match = oLitEnd - sequence.offset;
780
781    /* check */
782    if ((oLitEnd>oend_w) | (oMatchEnd>oend)) return ERROR(dstSize_tooSmall); /* last match must start at a minimum distance of WILDCOPY_OVERLENGTH from oend */
783    if (iLitEnd > litLimit_w) return ERROR(corruption_detected);   /* over-read beyond lit buffer */
784
785    /* copy Literals */
786    ZSTD_wildcopy(op, *litPtr, sequence.litLength);   /* note : since oLitEnd <= oend-WILDCOPY_OVERLENGTH, no risk of overwrite beyond oend */
787    op = oLitEnd;
788    *litPtr = iLitEnd;   /* update for next sequence */
789
790    /* copy Match */
791    if (sequence.offset > (size_t)(oLitEnd - base)) {
792        /* offset beyond prefix */
793        if (sequence.offset > (size_t)(oLitEnd - vBase)) return ERROR(corruption_detected);
794        match = dictEnd - (base-match);
795        if (match + sequence.matchLength <= dictEnd) {
796            memmove(oLitEnd, match, sequence.matchLength);
797            return sequenceLength;
798        }
799        /* span extDict & currentPrefixSegment */
800        {   size_t const length1 = dictEnd - match;
801            memmove(oLitEnd, match, length1);
802            op = oLitEnd + length1;
803            sequence.matchLength -= length1;
804            match = base;
805    }   }
806
807    /* match within prefix */
808    if (sequence.offset < 8) {
809        /* close range match, overlap */
810        static const U32 dec32table[] = { 0, 1, 2, 1, 4, 4, 4, 4 };   /* added */
811        static const int dec64table[] = { 8, 8, 8, 7, 8, 9,10,11 };   /* substracted */
812        int const sub2 = dec64table[sequence.offset];
813        op[0] = match[0];
814        op[1] = match[1];
815        op[2] = match[2];
816        op[3] = match[3];
817        match += dec32table[sequence.offset];
818        ZSTD_copy4(op+4, match);
819        match -= sub2;
820    } else {
821        ZSTD_copy8(op, match);
822    }
823    op += 8; match += 8;
824
825    if (oMatchEnd > oend-(16-MINMATCH)) {
826        if (op < oend_w) {
827            ZSTD_wildcopy(op, match, oend_w - op);
828            match += oend_w - op;
829            op = oend_w;
830        }
831        while (op < oMatchEnd) *op++ = *match++;
832    } else {
833        ZSTD_wildcopy(op, match, sequence.matchLength-8);   /* works even if matchLength < 8 */
834    }
835    return sequenceLength;
836}
837
838
839static size_t ZSTD_decompressSequences(
840                               ZSTD_DCtx* dctx,
841                               void* dst, size_t maxDstSize,
842                         const void* seqStart, size_t seqSize)
843{
844    const BYTE* ip = (const BYTE*)seqStart;
845    const BYTE* const iend = ip + seqSize;
846    BYTE* const ostart = (BYTE* const)dst;
847    BYTE* const oend = ostart + maxDstSize;
848    BYTE* op = ostart;
849    const BYTE* litPtr = dctx->litPtr;
850    const BYTE* const litLimit_w = litPtr + dctx->litBufSize - WILDCOPY_OVERLENGTH;
851    const BYTE* const litEnd = litPtr + dctx->litSize;
852    FSE_DTable* DTableLL = dctx->LLTable;
853    FSE_DTable* DTableML = dctx->MLTable;
854    FSE_DTable* DTableOffb = dctx->OffTable;
855    const BYTE* const base = (const BYTE*) (dctx->base);
856    const BYTE* const vBase = (const BYTE*) (dctx->vBase);
857    const BYTE* const dictEnd = (const BYTE*) (dctx->dictEnd);
858    int nbSeq;
859
860    /* Build Decoding Tables */
861    {   size_t const seqHSize = ZSTD_decodeSeqHeaders(&nbSeq, DTableLL, DTableML, DTableOffb, dctx->fseEntropy, ip, seqSize);
862        if (ZSTD_isError(seqHSize)) return seqHSize;
863        ip += seqHSize;
864    }
865
866    /* Regen sequences */
867    if (nbSeq) {
868        seqState_t seqState;
869        dctx->fseEntropy = 1;
870        { U32 i; for (i=0; i<ZSTD_REP_INIT; i++) seqState.prevOffset[i] = dctx->rep[i]; }
871        { size_t const errorCode = BIT_initDStream(&(seqState.DStream), ip, iend-ip);
872          if (ERR_isError(errorCode)) return ERROR(corruption_detected); }
873        FSE_initDState(&(seqState.stateLL), &(seqState.DStream), DTableLL);
874        FSE_initDState(&(seqState.stateOffb), &(seqState.DStream), DTableOffb);
875        FSE_initDState(&(seqState.stateML), &(seqState.DStream), DTableML);
876
877        for ( ; (BIT_reloadDStream(&(seqState.DStream)) <= BIT_DStream_completed) && nbSeq ; ) {
878            nbSeq--;
879            {   seq_t const sequence = ZSTD_decodeSequence(&seqState);
880                size_t const oneSeqSize = ZSTD_execSequence(op, oend, sequence, &litPtr, litLimit_w, base, vBase, dictEnd);
881                if (ZSTD_isError(oneSeqSize)) return oneSeqSize;
882                op += oneSeqSize;
883        }   }
884
885        /* check if reached exact end */
886        if (nbSeq) return ERROR(corruption_detected);
887        /* save reps for next block */
888        { U32 i; for (i=0; i<ZSTD_REP_INIT; i++) dctx->rep[i] = (U32)(seqState.prevOffset[i]); }
889    }
890
891    /* last literal segment */
892    {   size_t const lastLLSize = litEnd - litPtr;
893        //if (litPtr > litEnd) return ERROR(corruption_detected);   /* too many literals already used */
894        if (lastLLSize > (size_t)(oend-op)) return ERROR(dstSize_tooSmall);
895        memcpy(op, litPtr, lastLLSize);
896        op += lastLLSize;
897    }
898
899    return op-ostart;
900}
901
902
903static void ZSTD_checkContinuity(ZSTD_DCtx* dctx, const void* dst)
904{
905    if (dst != dctx->previousDstEnd) {   /* not contiguous */
906        dctx->dictEnd = dctx->previousDstEnd;
907        dctx->vBase = (const char*)dst - ((const char*)(dctx->previousDstEnd) - (const char*)(dctx->base));
908        dctx->base = dst;
909        dctx->previousDstEnd = dst;
910    }
911}
912
913
914static size_t ZSTD_decompressBlock_internal(ZSTD_DCtx* dctx,
915                            void* dst, size_t dstCapacity,
916                      const void* src, size_t srcSize)
917{   /* blockType == blockCompressed */
918    const BYTE* ip = (const BYTE*)src;
919
920    if (srcSize >= ZSTD_BLOCKSIZE_MAX) return ERROR(srcSize_wrong);
921
922    /* Decode literals sub-block */
923    {   size_t const litCSize = ZSTD_decodeLiteralsBlock(dctx, src, srcSize);
924        if (ZSTD_isError(litCSize)) return litCSize;
925        ip += litCSize;
926        srcSize -= litCSize;
927    }
928    return ZSTD_decompressSequences(dctx, dst, dstCapacity, ip, srcSize);
929}
930
931
932size_t ZSTD_decompressBlock(ZSTD_DCtx* dctx,
933                            void* dst, size_t dstCapacity,
934                      const void* src, size_t srcSize)
935{
936    size_t dSize;
937    ZSTD_checkContinuity(dctx, dst);
938    dSize = ZSTD_decompressBlock_internal(dctx, dst, dstCapacity, src, srcSize);
939    dctx->previousDstEnd = (char*)dst + dSize;
940    return dSize;
941}
942
943
944/** ZSTD_insertBlock() :
945    insert `src` block into `dctx` history. Useful to track uncompressed blocks. */
946ZSTDLIB_API size_t ZSTD_insertBlock(ZSTD_DCtx* dctx, const void* blockStart, size_t blockSize)
947{
948    ZSTD_checkContinuity(dctx, blockStart);
949    dctx->previousDstEnd = (const char*)blockStart + blockSize;
950    return blockSize;
951}
952
953
954size_t ZSTD_generateNxBytes(void* dst, size_t dstCapacity, BYTE byte, size_t length)
955{
956    if (length > dstCapacity) return ERROR(dstSize_tooSmall);
957    memset(dst, byte, length);
958    return length;
959}
960
961
962/*! ZSTD_decompressFrame() :
963*   `dctx` must be properly initialized */
964static size_t ZSTD_decompressFrame(ZSTD_DCtx* dctx,
965                                 void* dst, size_t dstCapacity,
966                                 const void* src, size_t srcSize)
967{
968    const BYTE* ip = (const BYTE*)src;
969    const BYTE* const iend = ip + srcSize;
970    BYTE* const ostart = (BYTE* const)dst;
971    BYTE* const oend = ostart + dstCapacity;
972    BYTE* op = ostart;
973    size_t remainingSize = srcSize;
974
975    /* check */
976    if (srcSize < ZSTD_frameHeaderSize_min+ZSTD_blockHeaderSize) return ERROR(srcSize_wrong);
977
978    /* Frame Header */
979    {   size_t const frameHeaderSize = ZSTD_frameHeaderSize(src, ZSTD_frameHeaderSize_min);
980        if (ZSTD_isError(frameHeaderSize)) return frameHeaderSize;
981        if (srcSize < frameHeaderSize+ZSTD_blockHeaderSize) return ERROR(srcSize_wrong);
982        if (ZSTD_decodeFrameHeader(dctx, src, frameHeaderSize)) return ERROR(corruption_detected);
983        ip += frameHeaderSize; remainingSize -= frameHeaderSize;
984    }
985
986    /* Loop on each block */
987    while (1) {
988        size_t decodedSize;
989        blockProperties_t blockProperties;
990        size_t const cBlockSize = ZSTD_getcBlockSize(ip, iend-ip, &blockProperties);
991        if (ZSTD_isError(cBlockSize)) return cBlockSize;
992
993        ip += ZSTD_blockHeaderSize;
994        remainingSize -= ZSTD_blockHeaderSize;
995        if (cBlockSize > remainingSize) return ERROR(srcSize_wrong);
996
997        switch(blockProperties.blockType)
998        {
999        case bt_compressed:
1000            decodedSize = ZSTD_decompressBlock_internal(dctx, op, oend-op, ip, cBlockSize);
1001            break;
1002        case bt_raw :
1003            decodedSize = ZSTD_copyRawBlock(op, oend-op, ip, cBlockSize);
1004            break;
1005        case bt_rle :
1006            decodedSize = ZSTD_generateNxBytes(op, oend-op, *ip, blockProperties.origSize);
1007            break;
1008        case bt_end :
1009            /* end of frame */
1010            if (remainingSize) return ERROR(srcSize_wrong);
1011            decodedSize = 0;
1012            break;
1013        default:
1014            return ERROR(GENERIC);   /* impossible */
1015        }
1016        if (cBlockSize == 0) break;   /* bt_end */
1017
1018        if (ZSTD_isError(decodedSize)) return decodedSize;
1019        if (dctx->fParams.checksumFlag) XXH64_update(&dctx->xxhState, op, decodedSize);
1020        op += decodedSize;
1021        ip += cBlockSize;
1022        remainingSize -= cBlockSize;
1023    }
1024
1025    return op-ostart;
1026}
1027
1028
1029/*! ZSTD_decompress_usingPreparedDCtx() :
1030*   Same as ZSTD_decompress_usingDict, but using a reference context `preparedDCtx`, where dictionary has been loaded.
1031*   It avoids reloading the dictionary each time.
1032*   `preparedDCtx` must have been properly initialized using ZSTD_decompressBegin_usingDict().
1033*   Requires 2 contexts : 1 for reference (preparedDCtx), which will not be modified, and 1 to run the decompression operation (dctx) */
1034size_t ZSTD_decompress_usingPreparedDCtx(ZSTD_DCtx* dctx, const ZSTD_DCtx* refDCtx,
1035                                         void* dst, size_t dstCapacity,
1036                                   const void* src, size_t srcSize)
1037{
1038    ZSTD_copyDCtx(dctx, refDCtx);
1039    ZSTD_checkContinuity(dctx, dst);
1040    return ZSTD_decompressFrame(dctx, dst, dstCapacity, src, srcSize);
1041}
1042
1043
1044size_t ZSTD_decompress_usingDict(ZSTD_DCtx* dctx,
1045                                 void* dst, size_t dstCapacity,
1046                                 const void* src, size_t srcSize,
1047                                 const void* dict, size_t dictSize)
1048{
1049#if defined(ZSTD_LEGACY_SUPPORT) && (ZSTD_LEGACY_SUPPORT==1)
1050    if (ZSTD_isLegacy(src, srcSize)) return ZSTD_decompressLegacy(dst, dstCapacity, src, srcSize, dict, dictSize);
1051#endif
1052    ZSTD_decompressBegin_usingDict(dctx, dict, dictSize);
1053    ZSTD_checkContinuity(dctx, dst);
1054    return ZSTD_decompressFrame(dctx, dst, dstCapacity, src, srcSize);
1055}
1056
1057
1058size_t ZSTD_decompressDCtx(ZSTD_DCtx* dctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize)
1059{
1060    return ZSTD_decompress_usingDict(dctx, dst, dstCapacity, src, srcSize, NULL, 0);
1061}
1062
1063
1064size_t ZSTD_decompress(void* dst, size_t dstCapacity, const void* src, size_t srcSize)
1065{
1066#if defined(ZSTD_HEAPMODE) && (ZSTD_HEAPMODE==1)
1067    size_t regenSize;
1068    ZSTD_DCtx* const dctx = ZSTD_createDCtx();
1069    if (dctx==NULL) return ERROR(memory_allocation);
1070    regenSize = ZSTD_decompressDCtx(dctx, dst, dstCapacity, src, srcSize);
1071    ZSTD_freeDCtx(dctx);
1072    return regenSize;
1073#else   /* stack mode */
1074    ZSTD_DCtx dctx;
1075    return ZSTD_decompressDCtx(&dctx, dst, dstCapacity, src, srcSize);
1076#endif
1077}
1078
1079
1080/*_******************************
1081*  Streaming Decompression API
1082********************************/
1083size_t ZSTD_nextSrcSizeToDecompress(ZSTD_DCtx* dctx)
1084{
1085    return dctx->expected;
1086}
1087
1088int ZSTD_isSkipFrame(ZSTD_DCtx* dctx)
1089{
1090    return dctx->stage == ZSTDds_skipFrame;
1091}
1092
1093/** ZSTD_decompressContinue() :
1094*   @return : nb of bytes generated into `dst` (necessarily <= `dstCapacity)
1095*             or an error code, which can be tested using ZSTD_isError() */
1096size_t ZSTD_decompressContinue(ZSTD_DCtx* dctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize)
1097{
1098    /* Sanity check */
1099    if (srcSize != dctx->expected) return ERROR(srcSize_wrong);
1100    if (dstCapacity) ZSTD_checkContinuity(dctx, dst);
1101
1102    switch (dctx->stage)
1103    {
1104    case ZSTDds_getFrameHeaderSize :
1105        if (srcSize != ZSTD_frameHeaderSize_min) return ERROR(srcSize_wrong);   /* impossible */
1106        if ((MEM_readLE32(src) & 0xFFFFFFF0U) == ZSTD_MAGIC_SKIPPABLE_START) {
1107            memcpy(dctx->headerBuffer, src, ZSTD_frameHeaderSize_min);
1108            dctx->expected = ZSTD_skippableHeaderSize - ZSTD_frameHeaderSize_min; /* magic number + skippable frame length */
1109            dctx->stage = ZSTDds_decodeSkippableHeader;
1110            return 0;
1111        }
1112        dctx->headerSize = ZSTD_frameHeaderSize(src, ZSTD_frameHeaderSize_min);
1113        if (ZSTD_isError(dctx->headerSize)) return dctx->headerSize;
1114        memcpy(dctx->headerBuffer, src, ZSTD_frameHeaderSize_min);
1115        if (dctx->headerSize > ZSTD_frameHeaderSize_min) {
1116            dctx->expected = dctx->headerSize - ZSTD_frameHeaderSize_min;
1117            dctx->stage = ZSTDds_decodeFrameHeader;
1118            return 0;
1119        }
1120        dctx->expected = 0;   /* not necessary to copy more */
1121
1122    case ZSTDds_decodeFrameHeader:
1123        {   size_t result;
1124            memcpy(dctx->headerBuffer + ZSTD_frameHeaderSize_min, src, dctx->expected);
1125            result = ZSTD_decodeFrameHeader(dctx, dctx->headerBuffer, dctx->headerSize);
1126            if (ZSTD_isError(result)) return result;
1127            dctx->expected = ZSTD_blockHeaderSize;
1128            dctx->stage = ZSTDds_decodeBlockHeader;
1129            return 0;
1130        }
1131    case ZSTDds_decodeBlockHeader:
1132        {   blockProperties_t bp;
1133            size_t const cBlockSize = ZSTD_getcBlockSize(src, ZSTD_blockHeaderSize, &bp);
1134            if (ZSTD_isError(cBlockSize)) return cBlockSize;
1135            if (bp.blockType == bt_end) {
1136                if (dctx->fParams.checksumFlag) {
1137                    U64 const h64 = XXH64_digest(&dctx->xxhState);
1138                    U32 const h32 = (U32)(h64>>11) & ((1<<22)-1);
1139                    const BYTE* const ip = (const BYTE*)src;
1140                    U32 const check32 = ip[2] + (ip[1] << 8) + ((ip[0] & 0x3F) << 16);
1141                    if (check32 != h32) return ERROR(checksum_wrong);
1142                }
1143                dctx->expected = 0;
1144                dctx->stage = ZSTDds_getFrameHeaderSize;
1145            } else {
1146                dctx->expected = cBlockSize;
1147                dctx->bType = bp.blockType;
1148                dctx->stage = ZSTDds_decompressBlock;
1149            }
1150            return 0;
1151        }
1152    case ZSTDds_decompressBlock:
1153        {   size_t rSize;
1154            switch(dctx->bType)
1155            {
1156            case bt_compressed:
1157                rSize = ZSTD_decompressBlock_internal(dctx, dst, dstCapacity, src, srcSize);
1158                break;
1159            case bt_raw :
1160                rSize = ZSTD_copyRawBlock(dst, dstCapacity, src, srcSize);
1161                break;
1162            case bt_rle :
1163                return ERROR(GENERIC);   /* not yet handled */
1164                break;
1165            case bt_end :   /* should never happen (filtered at phase 1) */
1166                rSize = 0;
1167                break;
1168            default:
1169                return ERROR(GENERIC);   /* impossible */
1170            }
1171            dctx->stage = ZSTDds_decodeBlockHeader;
1172            dctx->expected = ZSTD_blockHeaderSize;
1173            dctx->previousDstEnd = (char*)dst + rSize;
1174            if (ZSTD_isError(rSize)) return rSize;
1175            if (dctx->fParams.checksumFlag) XXH64_update(&dctx->xxhState, dst, rSize);
1176            return rSize;
1177        }
1178    case ZSTDds_decodeSkippableHeader:
1179        {   memcpy(dctx->headerBuffer + ZSTD_frameHeaderSize_min, src, dctx->expected);
1180            dctx->expected = MEM_readLE32(dctx->headerBuffer + 4);
1181            dctx->stage = ZSTDds_skipFrame;
1182            return 0;
1183        }
1184    case ZSTDds_skipFrame:
1185        {   dctx->expected = 0;
1186            dctx->stage = ZSTDds_getFrameHeaderSize;
1187            return 0;
1188        }
1189    default:
1190        return ERROR(GENERIC);   /* impossible */
1191    }
1192}
1193
1194
1195static size_t ZSTD_refDictContent(ZSTD_DCtx* dctx, const void* dict, size_t dictSize)
1196{
1197    dctx->dictEnd = dctx->previousDstEnd;
1198    dctx->vBase = (const char*)dict - ((const char*)(dctx->previousDstEnd) - (const char*)(dctx->base));
1199    dctx->base = dict;
1200    dctx->previousDstEnd = (const char*)dict + dictSize;
1201    return 0;
1202}
1203
1204static size_t ZSTD_loadEntropy(ZSTD_DCtx* dctx, const void* const dict, size_t const dictSize)
1205{
1206    const BYTE* dictPtr = (const BYTE*)dict;
1207    const BYTE* const dictEnd = dictPtr + dictSize;
1208
1209    {   size_t const hSize = HUF_readDTableX4(dctx->hufTable, dict, dictSize);
1210        if (HUF_isError(hSize)) return ERROR(dictionary_corrupted);
1211        dictPtr += hSize;
1212    }
1213
1214    {   short offcodeNCount[MaxOff+1];
1215        U32 offcodeMaxValue=MaxOff, offcodeLog=OffFSELog;
1216        size_t const offcodeHeaderSize = FSE_readNCount(offcodeNCount, &offcodeMaxValue, &offcodeLog, dictPtr, dictEnd-dictPtr);
1217        if (FSE_isError(offcodeHeaderSize)) return ERROR(dictionary_corrupted);
1218        { size_t const errorCode = FSE_buildDTable(dctx->OffTable, offcodeNCount, offcodeMaxValue, offcodeLog);
1219          if (FSE_isError(errorCode)) return ERROR(dictionary_corrupted); }
1220        dictPtr += offcodeHeaderSize;
1221    }
1222
1223    {   short matchlengthNCount[MaxML+1];
1224        unsigned matchlengthMaxValue = MaxML, matchlengthLog = MLFSELog;
1225        size_t const matchlengthHeaderSize = FSE_readNCount(matchlengthNCount, &matchlengthMaxValue, &matchlengthLog, dictPtr, dictEnd-dictPtr);
1226        if (FSE_isError(matchlengthHeaderSize)) return ERROR(dictionary_corrupted);
1227        { size_t const errorCode = FSE_buildDTable(dctx->MLTable, matchlengthNCount, matchlengthMaxValue, matchlengthLog);
1228          if (FSE_isError(errorCode)) return ERROR(dictionary_corrupted); }
1229        dictPtr += matchlengthHeaderSize;
1230    }
1231
1232    {   short litlengthNCount[MaxLL+1];
1233        unsigned litlengthMaxValue = MaxLL, litlengthLog = LLFSELog;
1234        size_t const litlengthHeaderSize = FSE_readNCount(litlengthNCount, &litlengthMaxValue, &litlengthLog, dictPtr, dictEnd-dictPtr);
1235        if (FSE_isError(litlengthHeaderSize)) return ERROR(dictionary_corrupted);
1236        { size_t const errorCode = FSE_buildDTable(dctx->LLTable, litlengthNCount, litlengthMaxValue, litlengthLog);
1237          if (FSE_isError(errorCode)) return ERROR(dictionary_corrupted); }
1238        dictPtr += litlengthHeaderSize;
1239    }
1240
1241    if (dictPtr+12 > dictEnd) return ERROR(dictionary_corrupted);
1242    dctx->rep[0] = MEM_readLE32(dictPtr+0); if (dctx->rep[0] >= dictSize) return ERROR(dictionary_corrupted);
1243    dctx->rep[1] = MEM_readLE32(dictPtr+4); if (dctx->rep[1] >= dictSize) return ERROR(dictionary_corrupted);
1244    dctx->rep[2] = MEM_readLE32(dictPtr+8); if (dctx->rep[2] >= dictSize) return ERROR(dictionary_corrupted);
1245    dictPtr += 12;
1246
1247    dctx->litEntropy = dctx->fseEntropy = 1;
1248    return dictPtr - (const BYTE*)dict;
1249}
1250
1251static size_t ZSTD_decompress_insertDictionary(ZSTD_DCtx* dctx, const void* dict, size_t dictSize)
1252{
1253    if (dictSize < 8) return ZSTD_refDictContent(dctx, dict, dictSize);
1254    {   U32 const magic = MEM_readLE32(dict);
1255        if (magic != ZSTD_DICT_MAGIC) {
1256            return ZSTD_refDictContent(dctx, dict, dictSize);   /* pure content mode */
1257    }   }
1258    dctx->dictID = MEM_readLE32((const char*)dict + 4);
1259
1260    /* load entropy tables */
1261    dict = (const char*)dict + 8;
1262    dictSize -= 8;
1263    {   size_t const eSize = ZSTD_loadEntropy(dctx, dict, dictSize);
1264        if (ZSTD_isError(eSize)) return ERROR(dictionary_corrupted);
1265        dict = (const char*)dict + eSize;
1266        dictSize -= eSize;
1267    }
1268
1269    /* reference dictionary content */
1270    return ZSTD_refDictContent(dctx, dict, dictSize);
1271}
1272
1273
1274size_t ZSTD_decompressBegin_usingDict(ZSTD_DCtx* dctx, const void* dict, size_t dictSize)
1275{
1276    { size_t const errorCode = ZSTD_decompressBegin(dctx);
1277      if (ZSTD_isError(errorCode)) return errorCode; }
1278
1279    if (dict && dictSize) {
1280        size_t const errorCode = ZSTD_decompress_insertDictionary(dctx, dict, dictSize);
1281        if (ZSTD_isError(errorCode)) return ERROR(dictionary_corrupted);
1282    }
1283
1284    return 0;
1285}
1286
1287
1288struct ZSTD_DDict_s {
1289    void* dict;
1290    size_t dictSize;
1291    ZSTD_DCtx* refContext;
1292};  /* typedef'd tp ZSTD_CDict within zstd.h */
1293
1294ZSTD_DDict* ZSTD_createDDict_advanced(const void* dict, size_t dictSize, ZSTD_customMem customMem)
1295{
1296    if (!customMem.customAlloc && !customMem.customFree)
1297        customMem = defaultCustomMem;
1298
1299    if (!customMem.customAlloc || !customMem.customFree)
1300        return NULL;
1301
1302    {   ZSTD_DDict* const ddict = (ZSTD_DDict*) customMem.customAlloc(customMem.opaque, sizeof(*ddict));
1303        void* const dictContent = customMem.customAlloc(customMem.opaque, dictSize);
1304        ZSTD_DCtx* const dctx = ZSTD_createDCtx_advanced(customMem);
1305
1306        if (!dictContent || !ddict || !dctx) {
1307            customMem.customFree(customMem.opaque, dictContent);
1308            customMem.customFree(customMem.opaque, ddict);
1309            customMem.customFree(customMem.opaque, dctx);
1310            return NULL;
1311        }
1312
1313        memcpy(dictContent, dict, dictSize);
1314        {   size_t const errorCode = ZSTD_decompressBegin_usingDict(dctx, dictContent, dictSize);
1315            if (ZSTD_isError(errorCode)) {
1316                customMem.customFree(customMem.opaque, dictContent);
1317                customMem.customFree(customMem.opaque, ddict);
1318                customMem.customFree(customMem.opaque, dctx);
1319                return NULL;
1320        }   }
1321
1322        ddict->dict = dictContent;
1323        ddict->dictSize = dictSize;
1324        ddict->refContext = dctx;
1325        return ddict;
1326    }
1327}
1328
1329/*! ZSTD_createDDict() :
1330*   Create a digested dictionary, ready to start decompression without startup delay.
1331*   `dict` can be released after `ZSTD_DDict` creation */
1332ZSTD_DDict* ZSTD_createDDict(const void* dict, size_t dictSize)
1333{
1334    ZSTD_customMem const allocator = { NULL, NULL, NULL };
1335    return ZSTD_createDDict_advanced(dict, dictSize, allocator);
1336}
1337
1338size_t ZSTD_freeDDict(ZSTD_DDict* ddict)
1339{
1340    ZSTD_freeFunction const cFree = ddict->refContext->customMem.customFree;
1341    void* const opaque = ddict->refContext->customMem.opaque;
1342    ZSTD_freeDCtx(ddict->refContext);
1343    cFree(opaque, ddict->dict);
1344    cFree(opaque, ddict);
1345    return 0;
1346}
1347
1348/*! ZSTD_decompress_usingDDict() :
1349*   Decompression using a pre-digested Dictionary
1350*   Use dictionary without significant overhead. */
1351ZSTDLIB_API size_t ZSTD_decompress_usingDDict(ZSTD_DCtx* dctx,
1352                                           void* dst, size_t dstCapacity,
1353                                     const void* src, size_t srcSize,
1354                                     const ZSTD_DDict* ddict)
1355{
1356#if defined(ZSTD_LEGACY_SUPPORT) && (ZSTD_LEGACY_SUPPORT==1)
1357    if (ZSTD_isLegacy(src, srcSize)) return ZSTD_decompressLegacy(dst, dstCapacity, src, srcSize, ddict->dict, ddict->dictSize);
1358#endif
1359    return ZSTD_decompress_usingPreparedDCtx(dctx, ddict->refContext,
1360                                           dst, dstCapacity,
1361                                           src, srcSize);
1362}
Note: See TracBrowser for help on using the repository browser.