[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[xen master] x86/Dom0: support zstd compressed kernels



commit d6627cf1b63ce57a6a7e2c1800dbc50eed742c32
Author:     Jan Beulich <jbeulich@xxxxxxxx>
AuthorDate: Mon Jan 18 12:12:23 2021 +0100
Commit:     Jan Beulich <jbeulich@xxxxxxxx>
CommitDate: Mon Jan 18 12:12:23 2021 +0100

    x86/Dom0: support zstd compressed kernels
    
    Taken from Linux at commit 1c4dd334df3a ("lib: decompress_unzstd: Limit
    output size") for unzstd.c (renamed from decompress_unzstd.c) and
    36f9ff9e03de ("lib: Fix fall-through warnings for Clang") for zstd/,
    with bits from linux/zstd.h merged into suitable other headers.
    
    To limit the editing necessary, introduce ptrdiff_t.
    
    Signed-off-by: Jan Beulich <jbeulich@xxxxxxxx>
    Acked-by: Andrew Cooper <andrew.cooper3@xxxxxxxxxx>
---
 xen/common/Makefile              |    2 +-
 xen/common/decompress.c          |    3 +
 xen/common/unzstd.c              |  308 +++++
 xen/common/zstd/bitstream.h      |  380 ++++++
 xen/common/zstd/decompress.c     | 2496 ++++++++++++++++++++++++++++++++++++++
 xen/common/zstd/entropy_common.c |  243 ++++
 xen/common/zstd/error_private.h  |  110 ++
 xen/common/zstd/fse.h            |  575 +++++++++
 xen/common/zstd/fse_decompress.c |  324 +++++
 xen/common/zstd/huf.h            |  212 ++++
 xen/common/zstd/huf_decompress.c |  960 +++++++++++++++
 xen/common/zstd/mem.h            |  151 +++
 xen/common/zstd/zstd_common.c    |   74 ++
 xen/common/zstd/zstd_internal.h  |  372 ++++++
 xen/include/asm-arm/types.h      |    6 +
 xen/include/asm-x86/types.h      |    6 +
 xen/include/xen/decompress.h     |    2 +-
 17 files changed, 6222 insertions(+), 2 deletions(-)

diff --git a/xen/common/Makefile b/xen/common/Makefile
index 7a4e652b57..d751315a87 100644
--- a/xen/common/Makefile
+++ b/xen/common/Makefile
@@ -55,7 +55,7 @@ obj-bin-y += warning.init.o
 obj-$(CONFIG_XENOPROF) += xenoprof.o
 obj-y += xmalloc_tlsf.o
 
-obj-bin-$(CONFIG_X86) += $(foreach n,decompress bunzip2 unxz unlzma lzo unlzo 
unlz4 earlycpio,$(n).init.o)
+obj-bin-$(CONFIG_X86) += $(foreach n,decompress bunzip2 unxz unlzma lzo unlzo 
unlz4 unzstd earlycpio,$(n).init.o)
 
 obj-$(CONFIG_COMPAT) += $(addprefix compat/,domain.o kernel.o memory.o 
multicall.o xlat.o)
 
diff --git a/xen/common/decompress.c b/xen/common/decompress.c
index 9d6e0c4ab0..79e60f4802 100644
--- a/xen/common/decompress.c
+++ b/xen/common/decompress.c
@@ -31,5 +31,8 @@ int __init decompress(void *inbuf, unsigned int len, void 
*outbuf)
     if ( len >= 2 && !memcmp(inbuf, "\x02\x21", 2) )
        return unlz4(inbuf, len, NULL, NULL, outbuf, NULL, error);
 
+    if ( len >= 4 && !memcmp(inbuf, "\x28\xb5\x2f\xfd", 4) )
+       return unzstd(inbuf, len, NULL, NULL, outbuf, NULL, error);
+
     return 1;
 }
diff --git a/xen/common/unzstd.c b/xen/common/unzstd.c
new file mode 100644
index 0000000000..a107616427
--- /dev/null
+++ b/xen/common/unzstd.c
@@ -0,0 +1,308 @@
+// SPDX-License-Identifier: GPL-2.0
+
+/*
+ * Important notes about in-place decompression
+ *
+ * At least on x86, the kernel is decompressed in place: the compressed data
+ * is placed to the end of the output buffer, and the decompressor overwrites
+ * most of the compressed data. There must be enough safety margin to
+ * guarantee that the write position is always behind the read position.
+ *
+ * The safety margin for ZSTD with a 128 KB block size is calculated below.
+ * Note that the margin with ZSTD is bigger than with GZIP or XZ!
+ *
+ * The worst case for in-place decompression is that the beginning of
+ * the file is compressed extremely well, and the rest of the file is
+ * uncompressible. Thus, we must look for worst-case expansion when the
+ * compressor is encoding uncompressible data.
+ *
+ * The structure of the .zst file in case of a compresed kernel is as follows.
+ * Maximum sizes (as bytes) of the fields are in parenthesis.
+ *
+ *    Frame Header: (18)
+ *    Blocks: (N)
+ *    Checksum: (4)
+ *
+ * The frame header and checksum overhead is at most 22 bytes.
+ *
+ * ZSTD stores the data in blocks. Each block has a header whose size is
+ * a 3 bytes. After the block header, there is up to 128 KB of payload.
+ * The maximum uncompressed size of the payload is 128 KB. The minimum
+ * uncompressed size of the payload is never less than the payload size
+ * (excluding the block header).
+ *
+ * The assumption, that the uncompressed size of the payload is never
+ * smaller than the payload itself, is valid only when talking about
+ * the payload as a whole. It is possible that the payload has parts where
+ * the decompressor consumes more input than it produces output. Calculating
+ * the worst case for this would be tricky. Instead of trying to do that,
+ * let's simply make sure that the decompressor never overwrites any bytes
+ * of the payload which it is currently reading.
+ *
+ * Now we have enough information to calculate the safety margin. We need
+ *   - 22 bytes for the .zst file format headers;
+ *   - 3 bytes per every 128 KiB of uncompressed size (one block header per
+ *     block); and
+ *   - 128 KiB (biggest possible zstd block size) to make sure that the
+ *     decompressor never overwrites anything from the block it is currently
+ *     reading.
+ *
+ * We get the following formula:
+ *
+ *    safety_margin = 22 + uncompressed_size * 3 / 131072 + 131072
+ *                 <= 22 + (uncompressed_size >> 15) + 131072
+ */
+
+#include "decompress.h"
+
+#include "zstd/entropy_common.c"
+#include "zstd/fse_decompress.c"
+#include "zstd/huf_decompress.c"
+#include "zstd/zstd_common.c"
+#include "zstd/decompress.c"
+
+/* 128MB is the maximum window size supported by zstd. */
+#define ZSTD_WINDOWSIZE_MAX    (1 << ZSTD_WINDOWLOG_MAX)
+/*
+ * Size of the input and output buffers in multi-call mode.
+ * Pick a larger size because it isn't used during kernel decompression,
+ * since that is single pass, and we have to allocate a large buffer for
+ * zstd's window anyway. The larger size speeds up initramfs decompression.
+ */
+#define ZSTD_IOBUF_SIZE                (1 << 17)
+
+static int INIT handle_zstd_error(size_t ret, void (*error)(const char *x))
+{
+       const int err = ZSTD_getErrorCode(ret);
+
+       if (!ZSTD_isError(ret))
+               return 0;
+
+       switch (err) {
+       case ZSTD_error_memory_allocation:
+               error("ZSTD decompressor ran out of memory");
+               break;
+       case ZSTD_error_prefix_unknown:
+               error("Input is not in the ZSTD format (wrong magic bytes)");
+               break;
+       case ZSTD_error_dstSize_tooSmall:
+       case ZSTD_error_corruption_detected:
+       case ZSTD_error_checksum_wrong:
+               error("ZSTD-compressed data is corrupt");
+               break;
+       default:
+               error("ZSTD-compressed data is probably corrupt");
+               break;
+       }
+       return -1;
+}
+
+/*
+ * Handle the case where we have the entire input and output in one segment.
+ * We can allocate less memory (no circular buffer for the sliding window),
+ * and avoid some memcpy() calls.
+ */
+static int INIT decompress_single(const u8 *in_buf, long in_len, u8 *out_buf,
+                                 long out_len, unsigned int *in_pos,
+                                 void (*error)(const char *x))
+{
+       const size_t wksp_size = ZSTD_DCtxWorkspaceBound();
+       void *wksp = large_malloc(wksp_size);
+       ZSTD_DCtx *dctx = ZSTD_initDCtx(wksp, wksp_size);
+       int err;
+       size_t ret;
+
+       if (dctx == NULL) {
+               error("Out of memory while allocating ZSTD_DCtx");
+               err = -1;
+               goto out;
+       }
+       /*
+        * Find out how large the frame actually is, there may be junk at
+        * the end of the frame that ZSTD_decompressDCtx() can't handle.
+        */
+       ret = ZSTD_findFrameCompressedSize(in_buf, in_len);
+       err = handle_zstd_error(ret, error);
+       if (err)
+               goto out;
+       in_len = (long)ret;
+
+       ret = ZSTD_decompressDCtx(dctx, out_buf, out_len, in_buf, in_len);
+       err = handle_zstd_error(ret, error);
+       if (err)
+               goto out;
+
+       if (in_pos != NULL)
+               *in_pos = in_len;
+
+       err = 0;
+out:
+       if (wksp != NULL)
+               large_free(wksp);
+       return err;
+}
+
+STATIC int INIT unzstd(unsigned char *in_buf, unsigned int in_len,
+                      int (*fill)(void*, unsigned int),
+                      int (*flush)(void*, unsigned int),
+                      unsigned char *out_buf,
+                      unsigned int *in_pos,
+                      void (*error)(const char *x))
+{
+       ZSTD_inBuffer in;
+       ZSTD_outBuffer out;
+       ZSTD_frameParams params;
+       void *in_allocated = NULL;
+       void *out_allocated = NULL;
+       void *wksp = NULL;
+       size_t wksp_size;
+       ZSTD_DStream *dstream;
+       int err;
+       size_t ret;
+       /*
+        * ZSTD decompression code won't be happy if the buffer size is so big
+        * that its end address overflows. When the size is not provided, make
+        * it as big as possible without having the end address overflow.
+        */
+       unsigned long out_len = ULONG_MAX - (unsigned long)out_buf;
+
+       if (fill == NULL && flush == NULL)
+               /*
+                * We can decompress faster and with less memory when we have a
+                * single chunk.
+                */
+               return decompress_single(in_buf, in_len, out_buf, out_len,
+                                        in_pos, error);
+
+       /*
+        * If in_buf is not provided, we must be using fill(), so allocate
+        * a large enough buffer. If it is provided, it must be at least
+        * ZSTD_IOBUF_SIZE large.
+        */
+       if (in_buf == NULL) {
+               in_allocated = large_malloc(ZSTD_IOBUF_SIZE);
+               if (in_allocated == NULL) {
+                       error("Out of memory while allocating input buffer");
+                       err = -1;
+                       goto out;
+               }
+               in_buf = in_allocated;
+               in_len = 0;
+       }
+       /* Read the first chunk, since we need to decode the frame header. */
+       if (fill != NULL)
+               in_len = fill(in_buf, ZSTD_IOBUF_SIZE);
+       if ((int)in_len < 0) {
+               error("ZSTD-compressed data is truncated");
+               err = -1;
+               goto out;
+       }
+       /* Set the first non-empty input buffer. */
+       in.src = in_buf;
+       in.pos = 0;
+       in.size = in_len;
+       /* Allocate the output buffer if we are using flush(). */
+       if (flush != NULL) {
+               out_allocated = large_malloc(ZSTD_IOBUF_SIZE);
+               if (out_allocated == NULL) {
+                       error("Out of memory while allocating output buffer");
+                       err = -1;
+                       goto out;
+               }
+               out_buf = out_allocated;
+               out_len = ZSTD_IOBUF_SIZE;
+       }
+       /* Set the output buffer. */
+       out.dst = out_buf;
+       out.pos = 0;
+       out.size = out_len;
+
+       /*
+        * We need to know the window size to allocate the ZSTD_DStream.
+        * Since we are streaming, we need to allocate a buffer for the sliding
+        * window. The window size varies from 1 KB to ZSTD_WINDOWSIZE_MAX
+        * (8 MB), so it is important to use the actual value so as not to
+        * waste memory when it is smaller.
+        */
+       ret = ZSTD_getFrameParams(&params, in.src, in.size);
+       err = handle_zstd_error(ret, error);
+       if (err)
+               goto out;
+       if (ret != 0) {
+               error("ZSTD-compressed data has an incomplete frame header");
+               err = -1;
+               goto out;
+       }
+       if (params.windowSize > ZSTD_WINDOWSIZE_MAX) {
+               error("ZSTD-compressed data has too large a window size");
+               err = -1;
+               goto out;
+       }
+
+       /*
+        * Allocate the ZSTD_DStream now that we know how much memory is
+        * required.
+        */
+       wksp_size = ZSTD_DStreamWorkspaceBound(params.windowSize);
+       wksp = large_malloc(wksp_size);
+       dstream = ZSTD_initDStream(params.windowSize, wksp, wksp_size);
+       if (dstream == NULL) {
+               error("Out of memory while allocating ZSTD_DStream");
+               err = -1;
+               goto out;
+       }
+
+       /*
+        * Decompression loop:
+        * Read more data if necessary (error if no more data can be read).
+        * Call the decompression function, which returns 0 when finished.
+        * Flush any data produced if using flush().
+        */
+       if (in_pos != NULL)
+               *in_pos = 0;
+       do {
+               /*
+                * If we need to reload data, either we have fill() and can
+                * try to get more data, or we don't and the input is truncated.
+                */
+               if (in.pos == in.size) {
+                       if (in_pos != NULL)
+                               *in_pos += in.pos;
+                       in_len = fill ? fill(in_buf, ZSTD_IOBUF_SIZE) : -1;
+                       if ((int)in_len < 0) {
+                               error("ZSTD-compressed data is truncated");
+                               err = -1;
+                               goto out;
+                       }
+                       in.pos = 0;
+                       in.size = in_len;
+               }
+               /* Returns zero when the frame is complete. */
+               ret = ZSTD_decompressStream(dstream, &out, &in);
+               err = handle_zstd_error(ret, error);
+               if (err)
+                       goto out;
+               /* Flush all of the data produced if using flush(). */
+               if (flush != NULL && out.pos > 0) {
+                       if (out.pos != flush(out.dst, out.pos)) {
+                               error("Failed to flush()");
+                               err = -1;
+                               goto out;
+                       }
+                       out.pos = 0;
+               }
+       } while (ret != 0);
+
+       if (in_pos != NULL)
+               *in_pos += in.pos;
+
+       err = 0;
+out:
+       if (in_allocated != NULL)
+               large_free(in_allocated);
+       if (out_allocated != NULL)
+               large_free(out_allocated);
+       if (wksp != NULL)
+               large_free(wksp);
+       return err;
+}
diff --git a/xen/common/zstd/bitstream.h b/xen/common/zstd/bitstream.h
new file mode 100644
index 0000000000..2b06d4551f
--- /dev/null
+++ b/xen/common/zstd/bitstream.h
@@ -0,0 +1,380 @@
+/*
+ * bitstream
+ * Part of FSE library
+ * header file (to include)
+ * Copyright (C) 2013-2016, Yann Collet.
+ *
+ * BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ *
+ *   * Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *   * Redistributions in binary form must reproduce the above
+ * copyright notice, this list of conditions and the following disclaimer
+ * in the documentation and/or other materials provided with the
+ * distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ *
+ * This program is free software; you can redistribute it and/or modify it 
under
+ * the terms of the GNU General Public License version 2 as published by the
+ * Free Software Foundation. This program is dual-licensed; you may select
+ * either version 2 of the GNU General Public License ("GPL") or BSD license
+ * ("BSD").
+ *
+ * You can contact the author at :
+ * - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
+ */
+#ifndef BITSTREAM_H_MODULE
+#define BITSTREAM_H_MODULE
+
+/*
+*  This API consists of small unitary functions, which must be inlined for 
best performance.
+*  Since link-time-optimization is not available for all compilers,
+*  these functions are defined into a .h to be included.
+*/
+
+/*-****************************************
+*  Dependencies
+******************************************/
+#include "error_private.h" /* error codes and messages */
+#include "mem.h"          /* unaligned access routines */
+
+/*=========================================
+*  Target specific
+=========================================*/
+#define STREAM_ACCUMULATOR_MIN_32 25
+#define STREAM_ACCUMULATOR_MIN_64 57
+#define STREAM_ACCUMULATOR_MIN ((U32)(ZSTD_32bits() ? 
STREAM_ACCUMULATOR_MIN_32 : STREAM_ACCUMULATOR_MIN_64))
+
+/*-******************************************
+*  bitStream encoding API (write forward)
+********************************************/
+/* bitStream can mix input from multiple sources.
+*  A critical property of these streams is that they encode and decode in 
**reverse** direction.
+*  So the first bit sequence you add will be the last to be read, like a LIFO 
stack.
+*/
+typedef struct {
+       size_t bitContainer;
+       int bitPos;
+       char *startPtr;
+       char *ptr;
+       char *endPtr;
+} BIT_CStream_t;
+
+ZSTD_STATIC size_t BIT_initCStream(BIT_CStream_t *bitC, void *dstBuffer, 
size_t dstCapacity);
+ZSTD_STATIC void BIT_addBits(BIT_CStream_t *bitC, size_t value, unsigned 
nbBits);
+ZSTD_STATIC void BIT_flushBits(BIT_CStream_t *bitC);
+ZSTD_STATIC size_t BIT_closeCStream(BIT_CStream_t *bitC);
+
+/* Start with initCStream, providing the size of buffer to write into.
+*  bitStream will never write outside of this buffer.
+*  `dstCapacity` must be >= sizeof(bitD->bitContainer), otherwise @return will 
be an error code.
+*
+*  bits are first added to a local register.
+*  Local register is size_t, hence 64-bits on 64-bits systems, or 32-bits on 
32-bits systems.
+*  Writing data into memory is an explicit operation, performed by the 
flushBits function.
+*  Hence keep track how many bits are potentially stored into local register 
to avoid register overflow.
+*  After a flushBits, a maximum of 7 bits might still be stored into local 
register.
+*
+*  Avoid storing elements of more than 24 bits if you want compatibility with 
32-bits bitstream readers.
+*
+*  Last operation is to close the bitStream.
+*  The function returns the final size of CStream in bytes.
+*  If data couldn't fit into `dstBuffer`, it will return a 0 ( == not storable)
+*/
+
+/*-********************************************
+*  bitStream decoding API (read backward)
+**********************************************/
+typedef struct {
+       size_t bitContainer;
+       unsigned bitsConsumed;
+       const char *ptr;
+       const char *start;
+} BIT_DStream_t;
+
+typedef enum {
+       BIT_DStream_unfinished = 0,
+       BIT_DStream_endOfBuffer = 1,
+       BIT_DStream_completed = 2,
+       BIT_DStream_overflow = 3
+} BIT_DStream_status; /* result of BIT_reloadDStream() */
+/* 1,2,4,8 would be better for bitmap combinations, but slows down performance 
a bit ... :( */
+
+ZSTD_STATIC size_t BIT_initDStream(BIT_DStream_t *bitD, const void *srcBuffer, 
size_t srcSize);
+ZSTD_STATIC size_t BIT_readBits(BIT_DStream_t *bitD, unsigned nbBits);
+ZSTD_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t *bitD);
+ZSTD_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t *bitD);
+
+/* Start by invoking BIT_initDStream().
+*  A chunk of the bitStream is then stored into a local register.
+*  Local register size is 64-bits on 64-bits systems, 32-bits on 32-bits 
systems (size_t).
+*  You can then retrieve bitFields stored into the local register, **in 
reverse order**.
+*  Local register is explicitly reloaded from memory by the 
BIT_reloadDStream() method.
+*  A reload guarantee a minimum of ((8*sizeof(bitD->bitContainer))-7) bits 
when its result is BIT_DStream_unfinished.
+*  Otherwise, it can be less than that, so proceed accordingly.
+*  Checking if DStream has reached its end can be performed with 
BIT_endOfDStream().
+*/
+
+/*-****************************************
+*  unsafe API
+******************************************/
+ZSTD_STATIC void BIT_addBitsFast(BIT_CStream_t *bitC, size_t value, unsigned 
nbBits);
+/* faster, but works only if value is "clean", meaning all high bits above 
nbBits are 0 */
+
+ZSTD_STATIC void BIT_flushBitsFast(BIT_CStream_t *bitC);
+/* unsafe version; does not check buffer overflow */
+
+ZSTD_STATIC size_t BIT_readBitsFast(BIT_DStream_t *bitD, unsigned nbBits);
+/* faster, but works only if nbBits >= 1 */
+
+/*-**************************************************************
+*  Internal functions
+****************************************************************/
+ZSTD_STATIC unsigned BIT_highbit32(register U32 val) { return 31 - 
__builtin_clz(val); }
+
+/*=====    Local Constants   =====*/
+static const unsigned BIT_mask[] = {0,       1,       3,       7,      0xF,    
  0x1F,     0x3F,     0x7F,      0xFF,
+                                   0x1FF,   0x3FF,   0x7FF,   0xFFF,    
0x1FFF,   0x3FFF,   0x7FFF,   0xFFFF,    0x1FFFF,
+                                   0x3FFFF, 0x7FFFF, 0xFFFFF, 0x1FFFFF, 
0x3FFFFF, 0x7FFFFF, 0xFFFFFF, 0x1FFFFFF, 0x3FFFFFF}; /* up to 26 bits */
+
+/*-**************************************************************
+*  bitStream encoding
+****************************************************************/
+/*! BIT_initCStream() :
+ *  `dstCapacity` must be > sizeof(void*)
+ *  @return : 0 if success,
+                         otherwise an error code (can be tested using 
ERR_isError() ) */
+ZSTD_STATIC size_t BIT_initCStream(BIT_CStream_t *bitC, void *startPtr, size_t 
dstCapacity)
+{
+       bitC->bitContainer = 0;
+       bitC->bitPos = 0;
+       bitC->startPtr = (char *)startPtr;
+       bitC->ptr = bitC->startPtr;
+       bitC->endPtr = bitC->startPtr + dstCapacity - sizeof(bitC->ptr);
+       if (dstCapacity <= sizeof(bitC->ptr))
+               return ERROR(dstSize_tooSmall);
+       return 0;
+}
+
+/*! BIT_addBits() :
+       can add up to 26 bits into `bitC`.
+       Does not check for register overflow ! */
+ZSTD_STATIC void BIT_addBits(BIT_CStream_t *bitC, size_t value, unsigned 
nbBits)
+{
+       bitC->bitContainer |= (value & BIT_mask[nbBits]) << bitC->bitPos;
+       bitC->bitPos += nbBits;
+}
+
+/*! BIT_addBitsFast() :
+ *  works only if `value` is _clean_, meaning all high bits above nbBits are 0 
*/
+ZSTD_STATIC void BIT_addBitsFast(BIT_CStream_t *bitC, size_t value, unsigned 
nbBits)
+{
+       bitC->bitContainer |= value << bitC->bitPos;
+       bitC->bitPos += nbBits;
+}
+
+/*! BIT_flushBitsFast() :
+ *  unsafe version; does not check buffer overflow */
+ZSTD_STATIC void BIT_flushBitsFast(BIT_CStream_t *bitC)
+{
+       size_t const nbBytes = bitC->bitPos >> 3;
+       ZSTD_writeLEST(bitC->ptr, bitC->bitContainer);
+       bitC->ptr += nbBytes;
+       bitC->bitPos &= 7;
+       bitC->bitContainer >>= nbBytes * 8; /* if bitPos >= 
sizeof(bitContainer)*8 --> undefined behavior */
+}
+
+/*! BIT_flushBits() :
+ *  safe version; check for buffer overflow, and prevents it.
+ *  note : does not signal buffer overflow. This will be revealed later on 
using BIT_closeCStream() */
+ZSTD_STATIC void BIT_flushBits(BIT_CStream_t *bitC)
+{
+       size_t const nbBytes = bitC->bitPos >> 3;
+       ZSTD_writeLEST(bitC->ptr, bitC->bitContainer);
+       bitC->ptr += nbBytes;
+       if (bitC->ptr > bitC->endPtr)
+               bitC->ptr = bitC->endPtr;
+       bitC->bitPos &= 7;
+       bitC->bitContainer >>= nbBytes * 8; /* if bitPos >= 
sizeof(bitContainer)*8 --> undefined behavior */
+}
+
+/*! BIT_closeCStream() :
+ *  @return : size of CStream, in bytes,
+                         or 0 if it could not fit into dstBuffer */
+ZSTD_STATIC size_t BIT_closeCStream(BIT_CStream_t *bitC)
+{
+       BIT_addBitsFast(bitC, 1, 1); /* endMark */
+       BIT_flushBits(bitC);
+
+       if (bitC->ptr >= bitC->endPtr)
+               return 0; /* doesn't fit within authorized budget : cancel */
+
+       return (bitC->ptr - bitC->startPtr) + (bitC->bitPos > 0);
+}
+
+/*-********************************************************
+* bitStream decoding
+**********************************************************/
+/*! BIT_initDStream() :
+*   Initialize a BIT_DStream_t.
+*   `bitD` : a pointer to an already allocated BIT_DStream_t structure.
+*   `srcSize` must be the *exact* size of the bitStream, in bytes.
+*   @return : size of stream (== srcSize) or an errorCode if a problem is 
detected
+*/
+ZSTD_STATIC size_t BIT_initDStream(BIT_DStream_t *bitD, const void *srcBuffer, 
size_t srcSize)
+{
+       if (srcSize < 1) {
+               memset(bitD, 0, sizeof(*bitD));
+               return ERROR(srcSize_wrong);
+       }
+
+       if (srcSize >= sizeof(bitD->bitContainer)) { /* normal case */
+               bitD->start = (const char *)srcBuffer;
+               bitD->ptr = (const char *)srcBuffer + srcSize - 
sizeof(bitD->bitContainer);
+               bitD->bitContainer = ZSTD_readLEST(bitD->ptr);
+               {
+                       BYTE const lastByte = ((const BYTE *)srcBuffer)[srcSize 
- 1];
+                       bitD->bitsConsumed = lastByte ? 8 - 
BIT_highbit32(lastByte) : 0; /* ensures bitsConsumed is always set */
+                       if (lastByte == 0)
+                               return ERROR(GENERIC); /* endMark not present */
+               }
+       } else {
+               bitD->start = (const char *)srcBuffer;
+               bitD->ptr = bitD->start;
+               bitD->bitContainer = *(const BYTE *)(bitD->start);
+               switch (srcSize) {
+               case 7: bitD->bitContainer += (size_t)(((const BYTE 
*)(srcBuffer))[6]) << (sizeof(bitD->bitContainer) * 8 - 16);
+                       /* fallthrough */
+               case 6: bitD->bitContainer += (size_t)(((const BYTE 
*)(srcBuffer))[5]) << (sizeof(bitD->bitContainer) * 8 - 24);
+                       /* fallthrough */
+               case 5: bitD->bitContainer += (size_t)(((const BYTE 
*)(srcBuffer))[4]) << (sizeof(bitD->bitContainer) * 8 - 32);
+                       /* fallthrough */
+               case 4: bitD->bitContainer += (size_t)(((const BYTE 
*)(srcBuffer))[3]) << 24;
+                       /* fallthrough */
+               case 3: bitD->bitContainer += (size_t)(((const BYTE 
*)(srcBuffer))[2]) << 16;
+                       /* fallthrough */
+               case 2: bitD->bitContainer += (size_t)(((const BYTE 
*)(srcBuffer))[1]) << 8;
+                       /* fallthrough */
+               default:;
+               }
+               {
+                       BYTE const lastByte = ((const BYTE *)srcBuffer)[srcSize 
- 1];
+                       bitD->bitsConsumed = lastByte ? 8 - 
BIT_highbit32(lastByte) : 0;
+                       if (lastByte == 0)
+                               return ERROR(GENERIC); /* endMark not present */
+               }
+               bitD->bitsConsumed += (U32)(sizeof(bitD->bitContainer) - 
srcSize) * 8;
+       }
+
+       return srcSize;
+}
+
+ZSTD_STATIC size_t BIT_getUpperBits(size_t bitContainer, U32 const start) { 
return bitContainer >> start; }
+
+ZSTD_STATIC size_t BIT_getMiddleBits(size_t bitContainer, U32 const start, U32 
const nbBits) { return (bitContainer >> start) & BIT_mask[nbBits]; }
+
+ZSTD_STATIC size_t BIT_getLowerBits(size_t bitContainer, U32 const nbBits) { 
return bitContainer & BIT_mask[nbBits]; }
+
+/*! BIT_lookBits() :
+ *  Provides next n bits from local register.
+ *  local register is not modified.
+ *  On 32-bits, maxNbBits==24.
+ *  On 64-bits, maxNbBits==56.
+ *  @return : value extracted
+ */
+ZSTD_STATIC size_t BIT_lookBits(const BIT_DStream_t *bitD, U32 nbBits)
+{
+       U32 const bitMask = sizeof(bitD->bitContainer) * 8 - 1;
+       return ((bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> 1) >> 
((bitMask - nbBits) & bitMask);
+}
+
+/*! BIT_lookBitsFast() :
+*   unsafe version; only works only if nbBits >= 1 */
+ZSTD_STATIC size_t BIT_lookBitsFast(const BIT_DStream_t *bitD, U32 nbBits)
+{
+       U32 const bitMask = sizeof(bitD->bitContainer) * 8 - 1;
+       return (bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> 
(((bitMask + 1) - nbBits) & bitMask);
+}
+
+ZSTD_STATIC void BIT_skipBits(BIT_DStream_t *bitD, U32 nbBits) { 
bitD->bitsConsumed += nbBits; }
+
+/*! BIT_readBits() :
+ *  Read (consume) next n bits from local register and update.
+ *  Pay attention to not read more than nbBits contained into local register.
+ *  @return : extracted value.
+ */
+ZSTD_STATIC size_t BIT_readBits(BIT_DStream_t *bitD, U32 nbBits)
+{
+       size_t const value = BIT_lookBits(bitD, nbBits);
+       BIT_skipBits(bitD, nbBits);
+       return value;
+}
+
+/*! BIT_readBitsFast() :
+*   unsafe version; only works only if nbBits >= 1 */
+ZSTD_STATIC size_t BIT_readBitsFast(BIT_DStream_t *bitD, U32 nbBits)
+{
+       size_t const value = BIT_lookBitsFast(bitD, nbBits);
+       BIT_skipBits(bitD, nbBits);
+       return value;
+}
+
+/*! BIT_reloadDStream() :
+*   Refill `bitD` from buffer previously set in BIT_initDStream() .
+*   This function is safe, it guarantees it will not read beyond src buffer.
+*   @return : status of `BIT_DStream_t` internal register.
+                         if status == BIT_DStream_unfinished, internal 
register is filled with >= (sizeof(bitD->bitContainer)*8 - 7) bits */
+ZSTD_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t *bitD)
+{
+       if (bitD->bitsConsumed > (sizeof(bitD->bitContainer) * 8)) /* should 
not happen => corruption detected */
+               return BIT_DStream_overflow;
+
+       if (bitD->ptr >= bitD->start + sizeof(bitD->bitContainer)) {
+               bitD->ptr -= bitD->bitsConsumed >> 3;
+               bitD->bitsConsumed &= 7;
+               bitD->bitContainer = ZSTD_readLEST(bitD->ptr);
+               return BIT_DStream_unfinished;
+       }
+       if (bitD->ptr == bitD->start) {
+               if (bitD->bitsConsumed < sizeof(bitD->bitContainer) * 8)
+                       return BIT_DStream_endOfBuffer;
+               return BIT_DStream_completed;
+       }
+       {
+               U32 nbBytes = bitD->bitsConsumed >> 3;
+               BIT_DStream_status result = BIT_DStream_unfinished;
+               if (bitD->ptr - nbBytes < bitD->start) {
+                       nbBytes = (U32)(bitD->ptr - bitD->start); /* ptr > 
start */
+                       result = BIT_DStream_endOfBuffer;
+               }
+               bitD->ptr -= nbBytes;
+               bitD->bitsConsumed -= nbBytes * 8;
+               bitD->bitContainer = ZSTD_readLEST(bitD->ptr); /* reminder : 
srcSize > sizeof(bitD) */
+               return result;
+       }
+}
+
+/*! BIT_endOfDStream() :
+*   @return Tells if DStream has exactly reached its end (all bits consumed).
+*/
+ZSTD_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t *DStream)
+{
+       return ((DStream->ptr == DStream->start) && (DStream->bitsConsumed == 
sizeof(DStream->bitContainer) * 8));
+}
+
+#endif /* BITSTREAM_H_MODULE */
diff --git a/xen/common/zstd/decompress.c b/xen/common/zstd/decompress.c
new file mode 100644
index 0000000000..3d3ef136e5
--- /dev/null
+++ b/xen/common/zstd/decompress.c
@@ -0,0 +1,2496 @@
+/**
+ * Copyright (c) 2016-present, Yann Collet, Facebook, Inc.
+ * All rights reserved.
+ *
+ * This source code is licensed under the BSD-style license found in the
+ * LICENSE file in the root directory of https://github.com/facebook/zstd.
+ * An additional grant of patent rights can be found in the PATENTS file in the
+ * same directory.
+ *
+ * This program is free software; you can redistribute it and/or modify it 
under
+ * the terms of the GNU General Public License version 2 as published by the
+ * Free Software Foundation. This program is dual-licensed; you may select
+ * either version 2 of the GNU General Public License ("GPL") or BSD license
+ * ("BSD").
+ */
+
+/* ***************************************************************
+*  Tuning parameters
+*****************************************************************/
+/*!
+*  MAXWINDOWSIZE_DEFAULT :
+*  maximum window size accepted by DStream, by default.
+*  Frames requiring more memory will be rejected.
+*/
+#ifndef ZSTD_MAXWINDOWSIZE_DEFAULT
+#define ZSTD_MAXWINDOWSIZE_DEFAULT ((1 << ZSTD_WINDOWLOG_MAX) + 1) /* defined 
within zstd.h */
+#endif
+
+/*-*******************************************************
+*  Dependencies
+*********************************************************/
+#include "fse.h"
+#include "huf.h"
+#include "mem.h" /* low level memory routines */
+#include "zstd_internal.h"
+#include <xen/string.h> /* memcpy, memmove, memset */
+
+#define ZSTD_PREFETCH(ptr) __builtin_prefetch(ptr, 0, 0)
+
+/*-*************************************
+*  Macros
+***************************************/
+#define ZSTD_isError ERR_isError /* for inlining */
+#define FSE_isError ERR_isError
+#define HUF_isError ERR_isError
+
+/*_*******************************************************
+*  Memory operations
+**********************************************************/
+static void INIT ZSTD_copy4(void *dst, const void *src) { memcpy(dst, src, 4); 
}
+
+/*-*************************************************************
+*   Context management
+***************************************************************/
+typedef enum {
+       ZSTDds_getFrameHeaderSize,
+       ZSTDds_decodeFrameHeader,
+       ZSTDds_decodeBlockHeader,
+       ZSTDds_decompressBlock,
+       ZSTDds_decompressLastBlock,
+       ZSTDds_checkChecksum,
+       ZSTDds_decodeSkippableHeader,
+       ZSTDds_skipFrame
+} ZSTD_dStage;
+
+typedef struct {
+       FSE_DTable LLTable[FSE_DTABLE_SIZE_U32(LLFSELog)];
+       FSE_DTable OFTable[FSE_DTABLE_SIZE_U32(OffFSELog)];
+       FSE_DTable MLTable[FSE_DTABLE_SIZE_U32(MLFSELog)];
+       HUF_DTable hufTable[HUF_DTABLE_SIZE(HufLog)]; /* can accommodate 
HUF_decompress4X */
+       U64 workspace[HUF_DECOMPRESS_WORKSPACE_SIZE_U32 / 2];
+       U32 rep[ZSTD_REP_NUM];
+} ZSTD_entropyTables_t;
+
+struct ZSTD_DCtx_s {
+       const FSE_DTable *LLTptr;
+       const FSE_DTable *MLTptr;
+       const FSE_DTable *OFTptr;
+       const HUF_DTable *HUFptr;
+       ZSTD_entropyTables_t entropy;
+       const void *previousDstEnd; /* detect continuity */
+       const void *base;          /* start of curr segment */
+       const void *vBase;        /* virtual start of previous segment if it 
was just before curr one */
+       const void *dictEnd;    /* end of previous segment */
+       size_t expected;
+       ZSTD_frameParams fParams;
+       blockType_e bType; /* used in ZSTD_decompressContinue(), to transfer 
blockType between header decoding and block decoding stages */
+       ZSTD_dStage stage;
+       U32 litEntropy;
+       U32 fseEntropy;
+       struct xxh64_state xxhState;
+       size_t headerSize;
+       U32 dictID;
+       const BYTE *litPtr;
+       ZSTD_customMem customMem;
+       size_t litSize;
+       size_t rleSize;
+       BYTE litBuffer[ZSTD_BLOCKSIZE_ABSOLUTEMAX + WILDCOPY_OVERLENGTH];
+       BYTE headerBuffer[ZSTD_FRAMEHEADERSIZE_MAX];
+}; /* typedef'd to ZSTD_DCtx within "zstd.h" */
+
+size_t INIT ZSTD_DCtxWorkspaceBound(void) { return 
ZSTD_ALIGN(sizeof(ZSTD_stack)) + ZSTD_ALIGN(sizeof(ZSTD_DCtx)); }
+
+size_t INIT ZSTD_decompressBegin(ZSTD_DCtx *dctx)
+{
+       dctx->expected = ZSTD_frameHeaderSize_prefix;
+       dctx->stage = ZSTDds_getFrameHeaderSize;
+       dctx->previousDstEnd = NULL;
+       dctx->base = NULL;
+       dctx->vBase = NULL;
+       dctx->dictEnd = NULL;
+       dctx->entropy.hufTable[0] = (HUF_DTable)((HufLog)*0x1000001); /* cover 
both little and big endian */
+       dctx->litEntropy = dctx->fseEntropy = 0;
+       dctx->dictID = 0;
+       ZSTD_STATIC_ASSERT(sizeof(dctx->entropy.rep) == sizeof(repStartValue));
+       memcpy(dctx->entropy.rep, repStartValue, sizeof(repStartValue)); /* 
initial repcodes */
+       dctx->LLTptr = dctx->entropy.LLTable;
+       dctx->MLTptr = dctx->entropy.MLTable;
+       dctx->OFTptr = dctx->entropy.OFTable;
+       dctx->HUFptr = dctx->entropy.hufTable;
+       return 0;
+}
+
+ZSTD_DCtx *INIT ZSTD_createDCtx_advanced(ZSTD_customMem customMem)
+{
+       ZSTD_DCtx *dctx;
+
+       if (!customMem.customAlloc || !customMem.customFree)
+               return NULL;
+
+       dctx = (ZSTD_DCtx *)ZSTD_malloc(sizeof(ZSTD_DCtx), customMem);
+       if (!dctx)
+               return NULL;
+       memcpy(&dctx->customMem, &customMem, sizeof(customMem));
+       ZSTD_decompressBegin(dctx);
+       return dctx;
+}
+
+ZSTD_DCtx *INIT ZSTD_initDCtx(void *workspace, size_t workspaceSize)
+{
+       ZSTD_customMem const stackMem = ZSTD_initStack(workspace, 
workspaceSize);
+       return ZSTD_createDCtx_advanced(stackMem);
+}
+
+size_t INIT ZSTD_freeDCtx(ZSTD_DCtx *dctx)
+{
+       if (dctx == NULL)
+               return 0; /* support free on NULL */
+       ZSTD_free(dctx, dctx->customMem);
+       return 0; /* reserved as a potential error code in the future */
+}
+
+void INIT ZSTD_copyDCtx(ZSTD_DCtx *dstDCtx, const ZSTD_DCtx *srcDCtx)
+{
+       size_t const workSpaceSize = (ZSTD_BLOCKSIZE_ABSOLUTEMAX + 
WILDCOPY_OVERLENGTH) + ZSTD_frameHeaderSize_max;
+       memcpy(dstDCtx, srcDCtx, sizeof(ZSTD_DCtx) - workSpaceSize); /* no need 
to copy workspace */
+}
+
+STATIC size_t ZSTD_findFrameCompressedSize(const void *src, size_t srcSize);
+STATIC size_t ZSTD_decompressBegin_usingDict(ZSTD_DCtx *dctx, const void *dict,
+       size_t dictSize);
+
+static void ZSTD_refDDict(ZSTD_DCtx *dstDCtx, const ZSTD_DDict *ddict);
+
+/*-*************************************************************
+*   Decompression section
+***************************************************************/
+
+/*! ZSTD_isFrame() :
+ *  Tells if the content of `buffer` starts with a valid Frame Identifier.
+ *  Note : Frame Identifier is 4 bytes. If `size < 4`, @return will always be 
0.
+ *  Note 2 : Legacy Frame Identifiers are considered valid only if Legacy 
Support is enabled.
+ *  Note 3 : Skippable Frame Identifiers are considered valid. */
+unsigned INIT ZSTD_isFrame(const void *buffer, size_t size)
+{
+       if (size < 4)
+               return 0;
+       {
+               U32 const magic = ZSTD_readLE32(buffer);
+               if (magic == ZSTD_MAGICNUMBER)
+                       return 1;
+               if ((magic & 0xFFFFFFF0U) == ZSTD_MAGIC_SKIPPABLE_START)
+                       return 1;
+       }
+       return 0;
+}
+
+/** ZSTD_frameHeaderSize() :
+*   srcSize must be >= ZSTD_frameHeaderSize_prefix.
+*   @return : size of the Frame Header */
+static size_t INIT ZSTD_frameHeaderSize(const void *src, size_t srcSize)
+{
+       if (srcSize < ZSTD_frameHeaderSize_prefix)
+               return ERROR(srcSize_wrong);
+       {
+               BYTE const fhd = ((const BYTE *)src)[4];
+               U32 const dictID = fhd & 3;
+               U32 const singleSegment = (fhd >> 5) & 1;
+               U32 const fcsId = fhd >> 6;
+               return ZSTD_frameHeaderSize_prefix + !singleSegment + 
ZSTD_did_fieldSize[dictID] + ZSTD_fcs_fieldSize[fcsId] + (singleSegment && 
!fcsId);
+       }
+}
+
+/** ZSTD_getFrameParams() :
+*   decode Frame Header, or require larger `srcSize`.
+*   @return : 0, `fparamsPtr` is correctly filled,
+*            >0, `srcSize` is too small, result is expected `srcSize`,
+*             or an error code, which can be tested using ZSTD_isError() */
+size_t INIT ZSTD_getFrameParams(ZSTD_frameParams *fparamsPtr, const void *src, 
size_t srcSize)
+{
+       const BYTE *ip = (const BYTE *)src;
+
+       if (srcSize < ZSTD_frameHeaderSize_prefix)
+               return ZSTD_frameHeaderSize_prefix;
+       if (ZSTD_readLE32(src) != ZSTD_MAGICNUMBER) {
+               if ((ZSTD_readLE32(src) & 0xFFFFFFF0U) == 
ZSTD_MAGIC_SKIPPABLE_START) {
+                       if (srcSize < ZSTD_skippableHeaderSize)
+                               return ZSTD_skippableHeaderSize; /* magic 
number + skippable frame length */
+                       memset(fparamsPtr, 0, sizeof(*fparamsPtr));
+                       fparamsPtr->frameContentSize = ZSTD_readLE32((const 
char *)src + 4);
+                       fparamsPtr->windowSize = 0; /* windowSize==0 means a 
frame is skippable */
+                       return 0;
+               }
+               return ERROR(prefix_unknown);
+       }
+
+       /* ensure there is enough `srcSize` to fully read/decode frame header */
+       {
+               size_t const fhsize = ZSTD_frameHeaderSize(src, srcSize);
+               if (srcSize < fhsize)
+                       return fhsize;
+       }
+
+       {
+               BYTE const fhdByte = ip[4];
+               size_t pos = 5;
+               U32 const dictIDSizeCode = fhdByte & 3;
+               U32 const checksumFlag = (fhdByte >> 2) & 1;
+               U32 const singleSegment = (fhdByte >> 5) & 1;
+               U32 const fcsID = fhdByte >> 6;
+               U32 const windowSizeMax = 1U << ZSTD_WINDOWLOG_MAX;
+               U32 windowSize = 0;
+               U32 dictID = 0;
+               U64 frameContentSize = 0;
+               if ((fhdByte & 0x08) != 0)
+                       return ERROR(frameParameter_unsupported); /* reserved 
bits, which must be zero */
+               if (!singleSegment) {
+                       BYTE const wlByte = ip[pos++];
+                       U32 const windowLog = (wlByte >> 3) + 
ZSTD_WINDOWLOG_ABSOLUTEMIN;
+                       if (windowLog > ZSTD_WINDOWLOG_MAX)
+                               return ERROR(frameParameter_windowTooLarge); /* 
avoids issue with 1 << windowLog */
+                       windowSize = (1U << windowLog);
+                       windowSize += (windowSize >> 3) * (wlByte & 7);
+               }
+
+               switch (dictIDSizeCode) {
+               default: /* impossible */
+               case 0: break;
+               case 1:
+                       dictID = ip[pos];
+                       pos++;
+                       break;
+               case 2:
+                       dictID = ZSTD_readLE16(ip + pos);
+                       pos += 2;
+                       break;
+               case 3:
+                       dictID = ZSTD_readLE32(ip + pos);
+                       pos += 4;
+                       break;
+               }
+               switch (fcsID) {
+               default: /* impossible */
+               case 0:
+                       if (singleSegment)
+                               frameContentSize = ip[pos];
+                       break;
+               case 1: frameContentSize = ZSTD_readLE16(ip + pos) + 256; break;
+               case 2: frameContentSize = ZSTD_readLE32(ip + pos); break;
+               case 3: frameContentSize = ZSTD_readLE64(ip + pos); break;
+               }
+               if (!windowSize)
+                       windowSize = (U32)frameContentSize;
+               if (windowSize > windowSizeMax)
+                       return ERROR(frameParameter_windowTooLarge);
+               fparamsPtr->frameContentSize = frameContentSize;
+               fparamsPtr->windowSize = windowSize;
+               fparamsPtr->dictID = dictID;
+               fparamsPtr->checksumFlag = checksumFlag;
+       }
+       return 0;
+}
+
+/** ZSTD_getFrameContentSize() :
+*   compatible with legacy mode
+*   @return : decompressed size of the single frame pointed to be `src` if 
known, otherwise
+*             - ZSTD_CONTENTSIZE_UNKNOWN if the size cannot be determined
+*             - ZSTD_CONTENTSIZE_ERROR if an error occurred (e.g. invalid 
magic number, srcSize too small) */
+unsigned long long INIT ZSTD_getFrameContentSize(const void *src, size_t 
srcSize)
+{
+       {
+               ZSTD_frameParams fParams;
+               if (ZSTD_getFrameParams(&fParams, src, srcSize) != 0)
+                       return ZSTD_CONTENTSIZE_ERROR;
+               if (fParams.windowSize == 0) {
+                       /* Either skippable or empty frame, size == 0 either 
way */
+                       return 0;
+               } else if (fParams.frameContentSize != 0) {
+                       return fParams.frameContentSize;
+               } else {
+                       return ZSTD_CONTENTSIZE_UNKNOWN;
+               }
+       }
+}
+
+/** ZSTD_findDecompressedSize() :
+ *  compatible with legacy mode
+ *  `srcSize` must be the exact length of some number of ZSTD compressed and/or
+ *      skippable frames
+ *  @return : decompressed size of the frames contained */
+unsigned long long INIT ZSTD_findDecompressedSize(const void *src, size_t 
srcSize)
+{
+       {
+               unsigned long long totalDstSize = 0;
+               while (srcSize >= ZSTD_frameHeaderSize_prefix) {
+                       const U32 magicNumber = ZSTD_readLE32(src);
+
+                       if ((magicNumber & 0xFFFFFFF0U) == 
ZSTD_MAGIC_SKIPPABLE_START) {
+                               size_t skippableSize;
+                               if (srcSize < ZSTD_skippableHeaderSize)
+                                       return ERROR(srcSize_wrong);
+                               skippableSize = ZSTD_readLE32((const BYTE *)src 
+ 4) + ZSTD_skippableHeaderSize;
+                               if (srcSize < skippableSize) {
+                                       return ZSTD_CONTENTSIZE_ERROR;
+                               }
+
+                               src = (const BYTE *)src + skippableSize;
+                               srcSize -= skippableSize;
+                               continue;
+                       }
+
+                       {
+                               unsigned long long const ret = 
ZSTD_getFrameContentSize(src, srcSize);
+                               if (ret >= ZSTD_CONTENTSIZE_ERROR)
+                                       return ret;
+
+                               /* check for overflow */
+                               if (totalDstSize + ret < totalDstSize)
+                                       return ZSTD_CONTENTSIZE_ERROR;
+                               totalDstSize += ret;
+                       }
+                       {
+                               size_t const frameSrcSize = 
ZSTD_findFrameCompressedSize(src, srcSize);
+                               if (ZSTD_isError(frameSrcSize)) {
+                                       return ZSTD_CONTENTSIZE_ERROR;
+                               }
+
+                               src = (const BYTE *)src + frameSrcSize;
+                               srcSize -= frameSrcSize;
+                       }
+               }
+
+               if (srcSize) {
+                       return ZSTD_CONTENTSIZE_ERROR;
+               }
+
+               return totalDstSize;
+       }
+}
+
+/** ZSTD_decodeFrameHeader() :
+*   `headerSize` must be the size provided by ZSTD_frameHeaderSize().
+*   @return : 0 if success, or an error code, which can be tested using 
ZSTD_isError() */
+static size_t INIT ZSTD_decodeFrameHeader(ZSTD_DCtx *dctx, const void *src, 
size_t headerSize)
+{
+       size_t const result = ZSTD_getFrameParams(&(dctx->fParams), src, 
headerSize);
+       if (ZSTD_isError(result))
+               return result; /* invalid header */
+       if (result > 0)
+               return ERROR(srcSize_wrong); /* headerSize too small */
+       if (dctx->fParams.dictID && (dctx->dictID != dctx->fParams.dictID))
+               return ERROR(dictionary_wrong);
+       if (dctx->fParams.checksumFlag)
+               xxh64_reset(&dctx->xxhState, 0);
+       return 0;
+}
+
+typedef struct {
+       blockType_e blockType;
+       U32 lastBlock;
+       U32 origSize;
+} blockProperties_t;
+
+/*! ZSTD_getcBlockSize() :
+*   Provides the size of compressed block from block header `src` */
+size_t INIT ZSTD_getcBlockSize(const void *src, size_t srcSize, 
blockProperties_t *bpPtr)
+{
+       if (srcSize < ZSTD_blockHeaderSize)
+               return ERROR(srcSize_wrong);
+       {
+               U32 const cBlockHeader = ZSTD_readLE24(src);
+               U32 const cSize = cBlockHeader >> 3;
+               bpPtr->lastBlock = cBlockHeader & 1;
+               bpPtr->blockType = (blockType_e)((cBlockHeader >> 1) & 3);
+               bpPtr->origSize = cSize; /* only useful for RLE */
+               if (bpPtr->blockType == bt_rle)
+                       return 1;
+               if (bpPtr->blockType == bt_reserved)
+                       return ERROR(corruption_detected);
+               return cSize;
+       }
+}
+
+static size_t INIT ZSTD_copyRawBlock(void *dst, size_t dstCapacity, const void 
*src, size_t srcSize)
+{
+       if (srcSize > dstCapacity)
+               return ERROR(dstSize_tooSmall);
+       memcpy(dst, src, srcSize);
+       return srcSize;
+}
+
+static size_t INIT ZSTD_setRleBlock(void *dst, size_t dstCapacity, const void 
*src, size_t srcSize, size_t regenSize)
+{
+       if (srcSize != 1)
+               return ERROR(srcSize_wrong);
+       if (regenSize > dstCapacity)
+               return ERROR(dstSize_tooSmall);
+       memset(dst, *(const BYTE *)src, regenSize);
+       return regenSize;
+}
+
+/*! ZSTD_decodeLiteralsBlock() :
+       @return : nb of bytes read from src (< srcSize ) */
+size_t INIT ZSTD_decodeLiteralsBlock(ZSTD_DCtx *dctx, const void *src, size_t 
srcSize) /* note : srcSize < BLOCKSIZE */
+{
+       if (srcSize < MIN_CBLOCK_SIZE)
+               return ERROR(corruption_detected);
+
+       {
+               const BYTE *const istart = (const BYTE *)src;
+               symbolEncodingType_e const litEncType = 
(symbolEncodingType_e)(istart[0] & 3);
+
+               switch (litEncType) {
+               case set_repeat:
+                       if (dctx->litEntropy == 0)
+                               return ERROR(dictionary_corrupted);
+                       /* fallthrough */
+               case set_compressed:
+                       if (srcSize < 5)
+                               return ERROR(corruption_detected); /* srcSize 
>= MIN_CBLOCK_SIZE == 3; here we need up to 5 for case 3 */
+                       {
+                               size_t lhSize, litSize, litCSize;
+                               U32 singleStream = 0;
+                               U32 const lhlCode = (istart[0] >> 2) & 3;
+                               U32 const lhc = ZSTD_readLE32(istart);
+                               switch (lhlCode) {
+                               case 0:
+                               case 1:
+                               default: /* note : default is impossible, since 
lhlCode into [0..3] */
+                                       /* 2 - 2 - 10 - 10 */
+                                       singleStream = !lhlCode;
+                                       lhSize = 3;
+                                       litSize = (lhc >> 4) & 0x3FF;
+                                       litCSize = (lhc >> 14) & 0x3FF;
+                                       break;
+                               case 2:
+                                       /* 2 - 2 - 14 - 14 */
+                                       lhSize = 4;
+                                       litSize = (lhc >> 4) & 0x3FFF;
+                                       litCSize = lhc >> 18;
+                                       break;
+                               case 3:
+                                       /* 2 - 2 - 18 - 18 */
+                                       lhSize = 5;
+                                       litSize = (lhc >> 4) & 0x3FFFF;
+                                       litCSize = (lhc >> 22) + (istart[4] << 
10);
+                                       break;
+                               }
+                               if (litSize > ZSTD_BLOCKSIZE_ABSOLUTEMAX)
+                                       return ERROR(corruption_detected);
+                               if (litCSize + lhSize > srcSize)
+                                       return ERROR(corruption_detected);
+
+                               if (HUF_isError(
+                                       (litEncType == set_repeat)
+                                           ? (singleStream ? 
HUF_decompress1X_usingDTable(dctx->litBuffer, litSize, istart + lhSize, 
litCSize, dctx->HUFptr)
+                                                           : 
HUF_decompress4X_usingDTable(dctx->litBuffer, litSize, istart + lhSize, 
litCSize, dctx->HUFptr))
+                                           : (singleStream
+                                                  ? 
HUF_decompress1X2_DCtx_wksp(dctx->entropy.hufTable, dctx->litBuffer, litSize, 
istart + lhSize, litCSize,
+                                                                               
 dctx->entropy.workspace, sizeof(dctx->entropy.workspace))
+                                                  : 
HUF_decompress4X_hufOnly_wksp(dctx->entropy.hufTable, dctx->litBuffer, litSize, 
istart + lhSize, litCSize,
+                                                                               
   dctx->entropy.workspace, sizeof(dctx->entropy.workspace)))))
+                                       return ERROR(corruption_detected);
+
+                               dctx->litPtr = dctx->litBuffer;
+                               dctx->litSize = litSize;
+                               dctx->litEntropy = 1;
+                               if (litEncType == set_compressed)
+                                       dctx->HUFptr = dctx->entropy.hufTable;
+                               memset(dctx->litBuffer + dctx->litSize, 0, 
WILDCOPY_OVERLENGTH);
+                               return litCSize + lhSize;
+                       }
+
+               case set_basic: {
+                       size_t litSize, lhSize;
+                       U32 const lhlCode = ((istart[0]) >> 2) & 3;
+                       switch (lhlCode) {
+                       case 0:
+                       case 2:
+                       default: /* note : default is impossible, since lhlCode 
into [0..3] */
+                               lhSize = 1;
+                               litSize = istart[0] >> 3;
+                               break;
+                       case 1:
+                               lhSize = 2;
+                               litSize = ZSTD_readLE16(istart) >> 4;
+                               break;
+                       case 3:
+                               lhSize = 3;
+                               litSize = ZSTD_readLE24(istart) >> 4;
+                               break;
+                       }
+
+                       if (lhSize + litSize + WILDCOPY_OVERLENGTH > srcSize) { 
/* risk reading beyond src buffer with wildcopy */
+                               if (litSize + lhSize > srcSize)
+                                       return ERROR(corruption_detected);
+                               memcpy(dctx->litBuffer, istart + lhSize, 
litSize);
+                               dctx->litPtr = dctx->litBuffer;
+                               dctx->litSize = litSize;
+                               memset(dctx->litBuffer + dctx->litSize, 0, 
WILDCOPY_OVERLENGTH);
+                               return lhSize + litSize;
+                       }
+                       /* direct reference into compressed stream */
+                       dctx->litPtr = istart + lhSize;
+                       dctx->litSize = litSize;
+                       return lhSize + litSize;
+               }
+
+               case set_rle: {
+                       U32 const lhlCode = ((istart[0]) >> 2) & 3;
+                       size_t litSize, lhSize;
+                       switch (lhlCode) {
+                       case 0:
+                       case 2:
+                       default: /* note : default is impossible, since lhlCode 
into [0..3] */
+                               lhSize = 1;
+                               litSize = istart[0] >> 3;
+                               break;
+                       case 1:
+                               lhSize = 2;
+                               litSize = ZSTD_readLE16(istart) >> 4;
+                               break;
+                       case 3:
+                               lhSize = 3;
+                               litSize = ZSTD_readLE24(istart) >> 4;
+                               if (srcSize < 4)
+                                       return ERROR(corruption_detected); /* 
srcSize >= MIN_CBLOCK_SIZE == 3; here we need lhSize+1 = 4 */
+                               break;
+                       }
+                       if (litSize > ZSTD_BLOCKSIZE_ABSOLUTEMAX)
+                               return ERROR(corruption_detected);
+                       memset(dctx->litBuffer, istart[lhSize], litSize + 
WILDCOPY_OVERLENGTH);
+                       dctx->litPtr = dctx->litBuffer;
+                       dctx->litSize = litSize;
+                       return lhSize + 1;
+               }
+               default:
+                       return ERROR(corruption_detected); /* impossible */
+               }
+       }
+}
+
+typedef union {
+       FSE_decode_t realData;
+       U32 alignedBy4;
+} FSE_decode_t4;
+
+static const FSE_decode_t4 LL_defaultDTable[(1 << LL_DEFAULTNORMLOG) + 1] = {
+    {{LL_DEFAULTNORMLOG, 1, 1}}, /* header : tableLog, fastMode, fastMode */
+    {{0, 0, 4}},                /* 0 : base, symbol, bits */
+    {{16, 0, 4}},
+    {{32, 1, 5}},
+    {{0, 3, 5}},
+    {{0, 4, 5}},
+    {{0, 6, 5}},
+    {{0, 7, 5}},
+    {{0, 9, 5}},
+    {{0, 10, 5}},
+    {{0, 12, 5}},
+    {{0, 14, 6}},
+    {{0, 16, 5}},
+    {{0, 18, 5}},
+    {{0, 19, 5}},
+    {{0, 21, 5}},
+    {{0, 22, 5}},
+    {{0, 24, 5}},
+    {{32, 25, 5}},
+    {{0, 26, 5}},
+    {{0, 27, 6}},
+    {{0, 29, 6}},
+    {{0, 31, 6}},
+    {{32, 0, 4}},
+    {{0, 1, 4}},
+    {{0, 2, 5}},
+    {{32, 4, 5}},
+    {{0, 5, 5}},
+    {{32, 7, 5}},
+    {{0, 8, 5}},
+    {{32, 10, 5}},
+    {{0, 11, 5}},
+    {{0, 13, 6}},
+    {{32, 16, 5}},
+    {{0, 17, 5}},
+    {{32, 19, 5}},
+    {{0, 20, 5}},
+    {{32, 22, 5}},
+    {{0, 23, 5}},
+    {{0, 25, 4}},
+    {{16, 25, 4}},
+    {{32, 26, 5}},
+    {{0, 28, 6}},
+    {{0, 30, 6}},
+    {{48, 0, 4}},
+    {{16, 1, 4}},
+    {{32, 2, 5}},
+    {{32, 3, 5}},
+    {{32, 5, 5}},
+    {{32, 6, 5}},
+    {{32, 8, 5}},
+    {{32, 9, 5}},
+    {{32, 11, 5}},
+    {{32, 12, 5}},
+    {{0, 15, 6}},
+    {{32, 17, 5}},
+    {{32, 18, 5}},
+    {{32, 20, 5}},
+    {{32, 21, 5}},
+    {{32, 23, 5}},
+    {{32, 24, 5}},
+    {{0, 35, 6}},
+    {{0, 34, 6}},
+    {{0, 33, 6}},
+    {{0, 32, 6}},
+}; /* LL_defaultDTable */
+
+static const FSE_decode_t4 ML_defaultDTable[(1 << ML_DEFAULTNORMLOG) + 1] = {
+    {{ML_DEFAULTNORMLOG, 1, 1}}, /* header : tableLog, fastMode, fastMode */
+    {{0, 0, 6}},                /* 0 : base, symbol, bits */
+    {{0, 1, 4}},
+    {{32, 2, 5}},
+    {{0, 3, 5}},
+    {{0, 5, 5}},
+    {{0, 6, 5}},
+    {{0, 8, 5}},
+    {{0, 10, 6}},
+    {{0, 13, 6}},
+    {{0, 16, 6}},
+    {{0, 19, 6}},
+    {{0, 22, 6}},
+    {{0, 25, 6}},
+    {{0, 28, 6}},
+    {{0, 31, 6}},
+    {{0, 33, 6}},
+    {{0, 35, 6}},
+    {{0, 37, 6}},
+    {{0, 39, 6}},
+    {{0, 41, 6}},
+    {{0, 43, 6}},
+    {{0, 45, 6}},
+    {{16, 1, 4}},
+    {{0, 2, 4}},
+    {{32, 3, 5}},
+    {{0, 4, 5}},
+    {{32, 6, 5}},
+    {{0, 7, 5}},
+    {{0, 9, 6}},
+    {{0, 12, 6}},
+    {{0, 15, 6}},
+    {{0, 18, 6}},
+    {{0, 21, 6}},
+    {{0, 24, 6}},
+    {{0, 27, 6}},
+    {{0, 30, 6}},
+    {{0, 32, 6}},
+    {{0, 34, 6}},
+    {{0, 36, 6}},
+    {{0, 38, 6}},
+    {{0, 40, 6}},
+    {{0, 42, 6}},
+    {{0, 44, 6}},
+    {{32, 1, 4}},
+    {{48, 1, 4}},
+    {{16, 2, 4}},
+    {{32, 4, 5}},
+    {{32, 5, 5}},
+    {{32, 7, 5}},
+    {{32, 8, 5}},
+    {{0, 11, 6}},
+    {{0, 14, 6}},
+    {{0, 17, 6}},
+    {{0, 20, 6}},
+    {{0, 23, 6}},
+    {{0, 26, 6}},
+    {{0, 29, 6}},
+    {{0, 52, 6}},
+    {{0, 51, 6}},
+    {{0, 50, 6}},
+    {{0, 49, 6}},
+    {{0, 48, 6}},
+    {{0, 47, 6}},
+    {{0, 46, 6}},
+}; /* ML_defaultDTable */
+
+static const FSE_decode_t4 OF_defaultDTable[(1 << OF_DEFAULTNORMLOG) + 1] = {
+    {{OF_DEFAULTNORMLOG, 1, 1}}, /* header : tableLog, fastMode, fastMode */
+    {{0, 0, 5}},                /* 0 : base, symbol, bits */
+    {{0, 6, 4}},
+    {{0, 9, 5}},
+    {{0, 15, 5}},
+    {{0, 21, 5}},
+    {{0, 3, 5}},
+    {{0, 7, 4}},
+    {{0, 12, 5}},
+    {{0, 18, 5}},
+    {{0, 23, 5}},
+    {{0, 5, 5}},
+    {{0, 8, 4}},
+    {{0, 14, 5}},
+    {{0, 20, 5}},
+    {{0, 2, 5}},
+    {{16, 7, 4}},
+    {{0, 11, 5}},
+    {{0, 17, 5}},
+    {{0, 22, 5}},
+    {{0, 4, 5}},
+    {{16, 8, 4}},
+    {{0, 13, 5}},
+    {{0, 19, 5}},
+    {{0, 1, 5}},
+    {{16, 6, 4}},
+    {{0, 10, 5}},
+    {{0, 16, 5}},
+    {{0, 28, 5}},
+    {{0, 27, 5}},
+    {{0, 26, 5}},
+    {{0, 25, 5}},
+    {{0, 24, 5}},
+}; /* OF_defaultDTable */
+
+/*! ZSTD_buildSeqTable() :
+       @return : nb bytes read from src,
+                         or an error code if it fails, testable with 
ZSTD_isError()
+*/
+static size_t INIT ZSTD_buildSeqTable(FSE_DTable *DTableSpace, const 
FSE_DTable **DTablePtr,
+                                     symbolEncodingType_e type, U32 max, U32 
maxLog, const void *src,
+                                     size_t srcSize, const FSE_decode_t4 
*defaultTable,
+                                     U32 flagRepeatTable, void *workspace, 
size_t workspaceSize)
+{
+       const void *const tmpPtr = defaultTable; /* bypass strict aliasing */
+       switch (type) {
+       case set_rle:
+               if (!srcSize)
+                       return ERROR(srcSize_wrong);
+               if ((*(const BYTE *)src) > max)
+                       return ERROR(corruption_detected);
+               FSE_buildDTable_rle(DTableSpace, *(const BYTE *)src);
+               *DTablePtr = DTableSpace;
+               return 1;
+       case set_basic: *DTablePtr = (const FSE_DTable *)tmpPtr; return 0;
+       case set_repeat:
+               if (!flagRepeatTable)
+                       return ERROR(corruption_detected);
+               return 0;
+       default: /* impossible */
+       case set_compressed: {
+               U32 tableLog;
+               S16 *norm = (S16 *)workspace;
+               size_t const spaceUsed32 = ALIGN(sizeof(S16) * (MaxSeq + 1), 
sizeof(U32)) >> 2;
+
+               if ((spaceUsed32 << 2) > workspaceSize)
+                       return ERROR(GENERIC);
+               workspace = (U32 *)workspace + spaceUsed32;
+               workspaceSize -= (spaceUsed32 << 2);
+               {
+                       size_t const headerSize = FSE_readNCount(norm, &max, 
&tableLog, src, srcSize);
+                       if (FSE_isError(headerSize))
+                               return ERROR(corruption_detected);
+                       if (tableLog > maxLog)
+                               return ERROR(corruption_detected);
+                       FSE_buildDTable_wksp(DTableSpace, norm, max, tableLog, 
workspace, workspaceSize);
+                       *DTablePtr = DTableSpace;
+                       return headerSize;
+               }
+       }
+       }
+}
+
+size_t INIT ZSTD_decodeSeqHeaders(ZSTD_DCtx *dctx, int *nbSeqPtr, const void 
*src, size_t srcSize)
+{
+       const BYTE *const istart = (const BYTE *const)src;
+       const BYTE *const iend = istart + srcSize;
+       const BYTE *ip = istart;
+
+       /* check */
+       if (srcSize < MIN_SEQUENCES_SIZE)
+               return ERROR(srcSize_wrong);
+
+       /* SeqHead */
+       {
+               int nbSeq = *ip++;
+               if (!nbSeq) {
+                       *nbSeqPtr = 0;
+                       return 1;
+               }
+               if (nbSeq > 0x7F) {
+                       if (nbSeq == 0xFF) {
+                               if (ip + 2 > iend)
+                                       return ERROR(srcSize_wrong);
+                               nbSeq = ZSTD_readLE16(ip) + LONGNBSEQ, ip += 2;
+                       } else {
+                               if (ip >= iend)
+                                       return ERROR(srcSize_wrong);
+                               nbSeq = ((nbSeq - 0x80) << 8) + *ip++;
+                       }
+               }
+               *nbSeqPtr = nbSeq;
+       }
+
+       /* FSE table descriptors */
+       if (ip + 4 > iend)
+               return ERROR(srcSize_wrong); /* minimum possible size */
+       {
+               symbolEncodingType_e const LLtype = (symbolEncodingType_e)(*ip 
>> 6);
+               symbolEncodingType_e const OFtype = (symbolEncodingType_e)((*ip 
>> 4) & 3);
+               symbolEncodingType_e const MLtype = (symbolEncodingType_e)((*ip 
>> 2) & 3);
+               ip++;
+
+               /* Build DTables */
+               {
+                       size_t const llhSize = 
ZSTD_buildSeqTable(dctx->entropy.LLTable, &dctx->LLTptr, LLtype, MaxLL, 
LLFSELog, ip, iend - ip,
+                                                                 
LL_defaultDTable, dctx->fseEntropy, dctx->entropy.workspace, 
sizeof(dctx->entropy.workspace));
+                       if (ZSTD_isError(llhSize))
+                               return ERROR(corruption_detected);
+                       ip += llhSize;
+               }
+               {
+                       size_t const ofhSize = 
ZSTD_buildSeqTable(dctx->entropy.OFTable, &dctx->OFTptr, OFtype, MaxOff, 
OffFSELog, ip, iend - ip,
+                                                                 
OF_defaultDTable, dctx->fseEntropy, dctx->entropy.workspace, 
sizeof(dctx->entropy.workspace));
+                       if (ZSTD_isError(ofhSize))
+                               return ERROR(corruption_detected);
+                       ip += ofhSize;
+               }
+               {
+                       size_t const mlhSize = 
ZSTD_buildSeqTable(dctx->entropy.MLTable, &dctx->MLTptr, MLtype, MaxML, 
MLFSELog, ip, iend - ip,
+                                                                 
ML_defaultDTable, dctx->fseEntropy, dctx->entropy.workspace, 
sizeof(dctx->entropy.workspace));
+                       if (ZSTD_isError(mlhSize))
+                               return ERROR(corruption_detected);
+                       ip += mlhSize;
+               }
+       }
+
+       return ip - istart;
+}
+
+typedef struct {
+       size_t litLength;
+       size_t matchLength;
+       size_t offset;
+       const BYTE *match;
+} seq_t;
+
+typedef struct {
+       BIT_DStream_t DStream;
+       FSE_DState_t stateLL;
+       FSE_DState_t stateOffb;
+       FSE_DState_t stateML;
+       size_t prevOffset[ZSTD_REP_NUM];
+       const BYTE *base;
+       size_t pos;
+       uPtrDiff gotoDict;
+} seqState_t;
+
+FORCE_NOINLINE
+size_t ZSTD_execSequenceLast7(BYTE *op, BYTE *const oend, seq_t sequence, 
const BYTE **litPtr, const BYTE *const litLimit, const BYTE *const base,
+                             const BYTE *const vBase, const BYTE *const 
dictEnd)
+{
+       BYTE *const oLitEnd = op + sequence.litLength;
+       size_t const sequenceLength = sequence.litLength + sequence.matchLength;
+       BYTE *const oMatchEnd = op + sequenceLength; /* risk : address space 
overflow (32-bits) */
+       BYTE *const oend_w = oend - WILDCOPY_OVERLENGTH;
+       const BYTE *const iLitEnd = *litPtr + sequence.litLength;
+       const BYTE *match = oLitEnd - sequence.offset;
+
+       /* check */
+       if (oMatchEnd > oend)
+               return ERROR(dstSize_tooSmall); /* last match must start at a 
minimum distance of WILDCOPY_OVERLENGTH from oend */
+       if (iLitEnd > litLimit)
+               return ERROR(corruption_detected); /* over-read beyond lit 
buffer */
+       if (oLitEnd <= oend_w)
+               return ERROR(GENERIC); /* Precondition */
+
+       /* copy literals */
+       if (op < oend_w) {
+               ZSTD_wildcopy(op, *litPtr, oend_w - op);
+               *litPtr += oend_w - op;
+               op = oend_w;
+       }
+       while (op < oLitEnd)
+               *op++ = *(*litPtr)++;
+
+       /* copy Match */
+       if (sequence.offset > (size_t)(oLitEnd - base)) {
+               /* offset beyond prefix */
+               if (sequence.offset > (size_t)(oLitEnd - vBase))
+                       return ERROR(corruption_detected);
+               match = dictEnd - (base - match);
+               if (match + sequence.matchLength <= dictEnd) {
+                       memmove(oLitEnd, match, sequence.matchLength);
+                       return sequenceLength;
+               }
+               /* span extDict & currPrefixSegment */
+               {
+                       size_t const length1 = dictEnd - match;
+                       memmove(oLitEnd, match, length1);
+                       op = oLitEnd + length1;
+                       sequence.matchLength -= length1;
+                       match = base;
+               }
+       }
+       while (op < oMatchEnd)
+               *op++ = *match++;
+       return sequenceLength;
+}
+
+static seq_t INIT ZSTD_decodeSequence(seqState_t *seqState)
+{
+       seq_t seq;
+
+       U32 const llCode = FSE_peekSymbol(&seqState->stateLL);
+       U32 const mlCode = FSE_peekSymbol(&seqState->stateML);
+       U32 const ofCode = FSE_peekSymbol(&seqState->stateOffb); /* <= maxOff, 
by table construction */
+
+       U32 const llBits = LL_bits[llCode];
+       U32 const mlBits = ML_bits[mlCode];
+       U32 const ofBits = ofCode;
+       U32 const totalBits = llBits + mlBits + ofBits;
+
+       static const U32 LL_base[MaxLL + 1] = {0,  1,  2,  3,  4,  5,  6,  7,  
8,    9,     10,    11,    12,    13,     14,     15,     16,     18,
+                                              20, 22, 24, 28, 32, 40, 48, 64, 
0x80, 0x100, 0x200, 0x400, 0x800, 0x1000, 0x2000, 0x4000, 0x8000, 0x10000};
+
+       static const U32 ML_base[MaxML + 1] = {3,  4,  5,  6,  7,  8,  9,  10,  
 11,    12,    13,    14,    15,     16,     17,     18,     19,     20,
+                                              21, 22, 23, 24, 25, 26, 27, 28,  
 29,    30,    31,    32,    33,     34,     35,     37,     39,     41,
+                                              43, 47, 51, 59, 67, 83, 99, 
0x83, 0x103, 0x203, 0x403, 0x803, 0x1003, 0x2003, 0x4003, 0x8003, 0x10003};
+
+       static const U32 OF_base[MaxOff + 1] = {0,       1,     1,      5,      
0xD,      0x1D,      0x3D,      0x7D,      0xFD,     0x1FD,
+                                               0x3FD,   0x7FD,    0xFFD,    
0x1FFD,   0x3FFD,   0x7FFD,    0xFFFD,    0x1FFFD,   0x3FFFD,  0x7FFFD,
+                                               0xFFFFD, 0x1FFFFD, 0x3FFFFD, 
0x7FFFFD, 0xFFFFFD, 0x1FFFFFD, 0x3FFFFFD, 0x7FFFFFD, 0xFFFFFFD};
+
+       /* sequence */
+       {
+               size_t offset;
+               if (!ofCode)
+                       offset = 0;
+               else {
+                       offset = OF_base[ofCode] + 
BIT_readBitsFast(&seqState->DStream, ofBits); /* <=  (ZSTD_WINDOWLOG_MAX-1) 
bits */
+                       if (ZSTD_32bits())
+                               BIT_reloadDStream(&seqState->DStream);
+               }
+
+               if (ofCode <= 1) {
+                       offset += (llCode == 0);
+                       if (offset) {
+                               size_t temp = (offset == 3) ? 
seqState->prevOffset[0] - 1 : seqState->prevOffset[offset];
+                               temp += !temp; /* 0 is not valid; input is 
corrupted; force offset to 1 */
+                               if (offset != 1)
+                                       seqState->prevOffset[2] = 
seqState->prevOffset[1];
+                               seqState->prevOffset[1] = 
seqState->prevOffset[0];
+                               seqState->prevOffset[0] = offset = temp;
+                       } else {
+                               offset = seqState->prevOffset[0];
+                       }
+               } else {
+                       seqState->prevOffset[2] = seqState->prevOffset[1];
+                       seqState->prevOffset[1] = seqState->prevOffset[0];
+                       seqState->prevOffset[0] = offset;
+               }
+               seq.offset = offset;
+       }
+
+       seq.matchLength = ML_base[mlCode] + ((mlCode > 31) ? 
BIT_readBitsFast(&seqState->DStream, mlBits) : 0); /* <=  16 bits */
+       if (ZSTD_32bits() && (mlBits + llBits > 24))
+               BIT_reloadDStream(&seqState->DStream);
+
+       seq.litLength = LL_base[llCode] + ((llCode > 15) ? 
BIT_readBitsFast(&seqState->DStream, llBits) : 0); /* <=  16 bits */
+       if (ZSTD_32bits() || (totalBits > 64 - 7 - (LLFSELog + MLFSELog + 
OffFSELog)))
+               BIT_reloadDStream(&seqState->DStream);
+
+       /* ANS state update */
+       FSE_updateState(&seqState->stateLL, &seqState->DStream); /* <=  9 bits 
*/
+       FSE_updateState(&seqState->stateML, &seqState->DStream); /* <=  9 bits 
*/
+       if (ZSTD_32bits())
+               BIT_reloadDStream(&seqState->DStream);             /* <= 18 
bits */
+       FSE_updateState(&seqState->stateOffb, &seqState->DStream); /* <=  8 
bits */
+
+       seq.match = NULL;
+
+       return seq;
+}
+
+FORCE_INLINE
+size_t ZSTD_execSequence(BYTE *op, BYTE *const oend, seq_t sequence, const 
BYTE **litPtr, const BYTE *const litLimit, const BYTE *const base,
+                        const BYTE *const vBase, const BYTE *const dictEnd)
+{
+       BYTE *const oLitEnd = op + sequence.litLength;
+       size_t const sequenceLength = sequence.litLength + sequence.matchLength;
+       BYTE *const oMatchEnd = op + sequenceLength; /* risk : address space 
overflow (32-bits) */
+       BYTE *const oend_w = oend - WILDCOPY_OVERLENGTH;
+       const BYTE *const iLitEnd = *litPtr + sequence.litLength;
+       const BYTE *match = oLitEnd - sequence.offset;
+
+       /* check */
+       if (oMatchEnd > oend)
+               return ERROR(dstSize_tooSmall); /* last match must start at a 
minimum distance of WILDCOPY_OVERLENGTH from oend */
+       if (iLitEnd > litLimit)
+               return ERROR(corruption_detected); /* over-read beyond lit 
buffer */
+       if (oLitEnd > oend_w)
+               return ZSTD_execSequenceLast7(op, oend, sequence, litPtr, 
litLimit, base, vBase, dictEnd);
+
+       /* copy Literals */
+       ZSTD_copy8(op, *litPtr);
+       if (sequence.litLength > 8)
+               ZSTD_wildcopy(op + 8, (*litPtr) + 8,
+                             sequence.litLength - 8); /* note : since oLitEnd 
<= oend-WILDCOPY_OVERLENGTH, no risk of overwrite beyond oend */
+       op = oLitEnd;
+       *litPtr = iLitEnd; /* update for next sequence */
+
+       /* copy Match */
+       if (sequence.offset > (size_t)(oLitEnd - base)) {
+               /* offset beyond prefix */
+               if (sequence.offset > (size_t)(oLitEnd - vBase))
+                       return ERROR(corruption_detected);
+               match = dictEnd + (match - base);
+               if (match + sequence.matchLength <= dictEnd) {
+                       memmove(oLitEnd, match, sequence.matchLength);
+                       return sequenceLength;
+               }
+               /* span extDict & currPrefixSegment */
+               {
+                       size_t const length1 = dictEnd - match;
+                       memmove(oLitEnd, match, length1);
+                       op = oLitEnd + length1;
+                       sequence.matchLength -= length1;
+                       match = base;
+                       if (op > oend_w || sequence.matchLength < MINMATCH) {
+                               U32 i;
+                               for (i = 0; i < sequence.matchLength; ++i)
+                                       op[i] = match[i];
+                               return sequenceLength;
+                       }
+               }
+       }
+       /* Requirement: op <= oend_w && sequence.matchLength >= MINMATCH */
+
+       /* match within prefix */
+       if (sequence.offset < 8) {
+               /* close range match, overlap */
+               static const U32 dec32table[] = {0, 1, 2, 1, 4, 4, 4, 4};   /* 
added */
+               static const int dec64table[] = {8, 8, 8, 7, 8, 9, 10, 11}; /* 
subtracted */
+               int const sub2 = dec64table[sequence.offset];
+               op[0] = match[0];
+               op[1] = match[1];
+               op[2] = match[2];
+               op[3] = match[3];
+               match += dec32table[sequence.offset];
+               ZSTD_copy4(op + 4, match);
+               match -= sub2;
+       } else {
+               ZSTD_copy8(op, match);
+       }
+       op += 8;
+       match += 8;
+
+       if (oMatchEnd > oend - (16 - MINMATCH)) {
+               if (op < oend_w) {
+                       ZSTD_wildcopy(op, match, oend_w - op);
+                       match += oend_w - op;
+                       op = oend_w;
+               }
+               while (op < oMatchEnd)
+                       *op++ = *match++;
+       } else {
+               ZSTD_wildcopy(op, match, (ptrdiff_t)sequence.matchLength - 8); 
/* works even if matchLength < 8 */
+       }
+       return sequenceLength;
+}
+
+static size_t INIT ZSTD_decompressSequences(ZSTD_DCtx *dctx, void *dst, size_t 
maxDstSize, const void *seqStart, size_t seqSize)
+{
+       const BYTE *ip = (const BYTE *)seqStart;
+       const BYTE *const iend = ip + seqSize;
+       BYTE *const ostart = (BYTE * const)dst;
+       BYTE *const oend = ostart + maxDstSize;
+       BYTE *op = ostart;
+       const BYTE *litPtr = dctx->litPtr;
+       const BYTE *const litEnd = litPtr + dctx->litSize;
+       const BYTE *const base = (const BYTE *)(dctx->base);
+       const BYTE *const vBase = (const BYTE *)(dctx->vBase);
+       const BYTE *const dictEnd = (const BYTE *)(dctx->dictEnd);
+       int nbSeq;
+
+       /* Build Decoding Tables */
+       {
+               size_t const seqHSize = ZSTD_decodeSeqHeaders(dctx, &nbSeq, ip, 
seqSize);
+               if (ZSTD_isError(seqHSize))
+                       return seqHSize;
+               ip += seqHSize;
+       }
+
+       /* Regen sequences */
+       if (nbSeq) {
+               seqState_t seqState;
+               dctx->fseEntropy = 1;
+               {
+                       U32 i;
+                       for (i = 0; i < ZSTD_REP_NUM; i++)
+                               seqState.prevOffset[i] = dctx->entropy.rep[i];
+               }
+               CHECK_E(BIT_initDStream(&seqState.DStream, ip, iend - ip), 
corruption_detected);
+               FSE_initDState(&seqState.stateLL, &seqState.DStream, 
dctx->LLTptr);
+               FSE_initDState(&seqState.stateOffb, &seqState.DStream, 
dctx->OFTptr);
+               FSE_initDState(&seqState.stateML, &seqState.DStream, 
dctx->MLTptr);
+
+               for (; (BIT_reloadDStream(&(seqState.DStream)) <= 
BIT_DStream_completed) && nbSeq;) {
+                       nbSeq--;
+                       {
+                               seq_t const sequence = 
ZSTD_decodeSequence(&seqState);
+                               size_t const oneSeqSize = ZSTD_execSequence(op, 
oend, sequence, &litPtr, litEnd, base, vBase, dictEnd);
+                               if (ZSTD_isError(oneSeqSize))
+                                       return oneSeqSize;
+                               op += oneSeqSize;
+                       }
+               }
+
+               /* check if reached exact end */
+               if (nbSeq)
+                       return ERROR(corruption_detected);
+               /* save reps for next block */
+               {
+                       U32 i;
+                       for (i = 0; i < ZSTD_REP_NUM; i++)
+                               dctx->entropy.rep[i] = 
(U32)(seqState.prevOffset[i]);
+               }
+       }
+
+       /* last literal segment */
+       {
+               size_t const lastLLSize = litEnd - litPtr;
+               if (lastLLSize > (size_t)(oend - op))
+                       return ERROR(dstSize_tooSmall);
+               memcpy(op, litPtr, lastLLSize);
+               op += lastLLSize;
+       }
+
+       return op - ostart;
+}
+
+FORCE_INLINE seq_t ZSTD_decodeSequenceLong_generic(seqState_t *seqState, int 
const longOffsets)
+{
+       seq_t seq;
+
+       U32 const llCode = FSE_peekSymbol(&seqState->stateLL);
+       U32 const mlCode = FSE_peekSymbol(&seqState->stateML);
+       U32 const ofCode = FSE_peekSymbol(&seqState->stateOffb); /* <= maxOff, 
by table construction */
+
+       U32 const llBits = LL_bits[llCode];
+       U32 const mlBits = ML_bits[mlCode];
+       U32 const ofBits = ofCode;
+       U32 const totalBits = llBits + mlBits + ofBits;
+
+       static const U32 LL_base[MaxLL + 1] = {0,  1,  2,  3,  4,  5,  6,  7,  
8,    9,     10,    11,    12,    13,     14,     15,     16,     18,
+                                              20, 22, 24, 28, 32, 40, 48, 64, 
0x80, 0x100, 0x200, 0x400, 0x800, 0x1000, 0x2000, 0x4000, 0x8000, 0x10000};
+
+       static const U32 ML_base[MaxML + 1] = {3,  4,  5,  6,  7,  8,  9,  10,  
 11,    12,    13,    14,    15,     16,     17,     18,     19,     20,
+                                              21, 22, 23, 24, 25, 26, 27, 28,  
 29,    30,    31,    32,    33,     34,     35,     37,     39,     41,
+                                              43, 47, 51, 59, 67, 83, 99, 
0x83, 0x103, 0x203, 0x403, 0x803, 0x1003, 0x2003, 0x4003, 0x8003, 0x10003};
+
+       static const U32 OF_base[MaxOff + 1] = {0,       1,     1,      5,      
0xD,      0x1D,      0x3D,      0x7D,      0xFD,     0x1FD,
+                                               0x3FD,   0x7FD,    0xFFD,    
0x1FFD,   0x3FFD,   0x7FFD,    0xFFFD,    0x1FFFD,   0x3FFFD,  0x7FFFD,
+                                               0xFFFFD, 0x1FFFFD, 0x3FFFFD, 
0x7FFFFD, 0xFFFFFD, 0x1FFFFFD, 0x3FFFFFD, 0x7FFFFFD, 0xFFFFFFD};
+
+       /* sequence */
+       {
+               size_t offset;
+               if (!ofCode)
+                       offset = 0;
+               else {
+                       if (longOffsets) {
+                               int const extraBits = ofBits - MIN(ofBits, 
STREAM_ACCUMULATOR_MIN);
+                               offset = OF_base[ofCode] + 
(BIT_readBitsFast(&seqState->DStream, ofBits - extraBits) << extraBits);
+                               if (ZSTD_32bits() || extraBits)
+                                       BIT_reloadDStream(&seqState->DStream);
+                               if (extraBits)
+                                       offset += 
BIT_readBitsFast(&seqState->DStream, extraBits);
+                       } else {
+                               offset = OF_base[ofCode] + 
BIT_readBitsFast(&seqState->DStream, ofBits); /* <=  (ZSTD_WINDOWLOG_MAX-1) 
bits */
+                               if (ZSTD_32bits())
+                                       BIT_reloadDStream(&seqState->DStream);
+                       }
+               }
+
+               if (ofCode <= 1) {
+                       offset += (llCode == 0);
+                       if (offset) {
+                               size_t temp = (offset == 3) ? 
seqState->prevOffset[0] - 1 : seqState->prevOffset[offset];
+                               temp += !temp; /* 0 is not valid; input is 
corrupted; force offset to 1 */
+                               if (offset != 1)
+                                       seqState->prevOffset[2] = 
seqState->prevOffset[1];
+                               seqState->prevOffset[1] = 
seqState->prevOffset[0];
+                               seqState->prevOffset[0] = offset = temp;
+                       } else {
+                               offset = seqState->prevOffset[0];
+                       }
+               } else {
+                       seqState->prevOffset[2] = seqState->prevOffset[1];
+                       seqState->prevOffset[1] = seqState->prevOffset[0];
+                       seqState->prevOffset[0] = offset;
+               }
+               seq.offset = offset;
+       }
+
+       seq.matchLength = ML_base[mlCode] + ((mlCode > 31) ? 
BIT_readBitsFast(&seqState->DStream, mlBits) : 0); /* <=  16 bits */
+       if (ZSTD_32bits() && (mlBits + llBits > 24))
+               BIT_reloadDStream(&seqState->DStream);
+
+       seq.litLength = LL_base[llCode] + ((llCode > 15) ? 
BIT_readBitsFast(&seqState->DStream, llBits) : 0); /* <=  16 bits */
+       if (ZSTD_32bits() || (totalBits > 64 - 7 - (LLFSELog + MLFSELog + 
OffFSELog)))
+               BIT_reloadDStream(&seqState->DStream);
+
+       {
+               size_t const pos = seqState->pos + seq.litLength;
+               seq.match = seqState->base + pos - seq.offset; /* single memory 
segment */
+               if (seq.offset > pos)
+                       seq.match += seqState->gotoDict; /* separate memory 
segment */
+               seqState->pos = pos + seq.matchLength;
+       }
+
+       /* ANS state update */
+       FSE_updateState(&seqState->stateLL, &seqState->DStream); /* <=  9 bits 
*/
+       FSE_updateState(&seqState->stateML, &seqState->DStream); /* <=  9 bits 
*/
+       if (ZSTD_32bits())
+               BIT_reloadDStream(&seqState->DStream);             /* <= 18 
bits */
+       FSE_updateState(&seqState->stateOffb, &seqState->DStream); /* <=  8 
bits */
+
+       return seq;
+}
+
+static seq_t INIT ZSTD_decodeSequenceLong(seqState_t *seqState, unsigned const 
windowSize)
+{
+       if (ZSTD_highbit32(windowSize) > STREAM_ACCUMULATOR_MIN) {
+               return ZSTD_decodeSequenceLong_generic(seqState, 1);
+       } else {
+               return ZSTD_decodeSequenceLong_generic(seqState, 0);
+       }
+}
+
+FORCE_INLINE
+size_t INIT ZSTD_execSequenceLong(BYTE *op, BYTE *const oend, seq_t sequence, 
const BYTE **litPtr,
+                                 const BYTE *const litLimit, const BYTE *const 
base,
+                                 const BYTE *const vBase, const BYTE *const 
dictEnd)
+{
+       BYTE *const oLitEnd = op + sequence.litLength;
+       size_t const sequenceLength = sequence.litLength + sequence.matchLength;
+       BYTE *const oMatchEnd = op + sequenceLength; /* risk : address space 
overflow (32-bits) */
+       BYTE *const oend_w = oend - WILDCOPY_OVERLENGTH;
+       const BYTE *const iLitEnd = *litPtr + sequence.litLength;
+       const BYTE *match = sequence.match;
+
+       /* check */
+       if (oMatchEnd > oend)
+               return ERROR(dstSize_tooSmall); /* last match must start at a 
minimum distance of WILDCOPY_OVERLENGTH from oend */
+       if (iLitEnd > litLimit)
+               return ERROR(corruption_detected); /* over-read beyond lit 
buffer */
+       if (oLitEnd > oend_w)
+               return ZSTD_execSequenceLast7(op, oend, sequence, litPtr, 
litLimit, base, vBase, dictEnd);
+
+       /* copy Literals */
+       ZSTD_copy8(op, *litPtr);
+       if (sequence.litLength > 8)
+               ZSTD_wildcopy(op + 8, (*litPtr) + 8,
+                             sequence.litLength - 8); /* note : since oLitEnd 
<= oend-WILDCOPY_OVERLENGTH, no risk of overwrite beyond oend */
+       op = oLitEnd;
+       *litPtr = iLitEnd; /* update for next sequence */
+
+       /* copy Match */
+       if (sequence.offset > (size_t)(oLitEnd - base)) {
+               /* offset beyond prefix */
+               if (sequence.offset > (size_t)(oLitEnd - vBase))
+                       return ERROR(corruption_detected);
+               if (match + sequence.matchLength <= dictEnd) {
+                       memmove(oLitEnd, match, sequence.matchLength);
+                       return sequenceLength;
+               }
+               /* span extDict & currPrefixSegment */
+               {
+                       size_t const length1 = dictEnd - match;
+                       memmove(oLitEnd, match, length1);
+                       op = oLitEnd + length1;
+                       sequence.matchLength -= length1;
+                       match = base;
+                       if (op > oend_w || sequence.matchLength < MINMATCH) {
+                               U32 i;
+                               for (i = 0; i < sequence.matchLength; ++i)
+                                       op[i] = match[i];
+                               return sequenceLength;
+                       }
+               }
+       }
+       /* Requirement: op <= oend_w && sequence.matchLength >= MINMATCH */
+
+       /* match within prefix */
+       if (sequence.offset < 8) {
+               /* close range match, overlap */
+               static const U32 dec32table[] = {0, 1, 2, 1, 4, 4, 4, 4};   /* 
added */
+               static const int dec64table[] = {8, 8, 8, 7, 8, 9, 10, 11}; /* 
subtracted */
+               int const sub2 = dec64table[sequence.offset];
+               op[0] = match[0];
+               op[1] = match[1];
+               op[2] = match[2];
+               op[3] = match[3];
+               match += dec32table[sequence.offset];
+               ZSTD_copy4(op + 4, match);
+               match -= sub2;
+       } else {
+               ZSTD_copy8(op, match);
+       }
+       op += 8;
+       match += 8;
+
+       if (oMatchEnd > oend - (16 - MINMATCH)) {
+               if (op < oend_w) {
+                       ZSTD_wildcopy(op, match, oend_w - op);
+                       match += oend_w - op;
+                       op = oend_w;
+               }
+               while (op < oMatchEnd)
+                       *op++ = *match++;
+       } else {
+               ZSTD_wildcopy(op, match, (ptrdiff_t)sequence.matchLength - 8); 
/* works even if matchLength < 8 */
+       }
+       return sequenceLength;
+}
+
+static size_t INIT ZSTD_decompressSequencesLong(ZSTD_DCtx *dctx, void *dst, 
size_t maxDstSize, const void *seqStart, size_t seqSize)
+{
+       const BYTE *ip = (const BYTE *)seqStart;
+       const BYTE *const iend = ip + seqSize;
+       BYTE *const ostart = (BYTE * const)dst;
+       BYTE *const oend = ostart + maxDstSize;
+       BYTE *op = ostart;
+       const BYTE *litPtr = dctx->litPtr;
+       const BYTE *const litEnd = litPtr + dctx->litSize;
+       const BYTE *const base = (const BYTE *)(dctx->base);
+       const BYTE *const vBase = (const BYTE *)(dctx->vBase);
+       const BYTE *const dictEnd = (const BYTE *)(dctx->dictEnd);
+       unsigned const windowSize = dctx->fParams.windowSize;
+       int nbSeq;
+
+       /* Build Decoding Tables */
+       {
+               size_t const seqHSize = ZSTD_decodeSeqHeaders(dctx, &nbSeq, ip, 
seqSize);
+               if (ZSTD_isError(seqHSize))
+                       return seqHSize;
+               ip += seqHSize;
+       }
+
+       /* Regen sequences */
+       if (nbSeq) {
+#define STORED_SEQS 4
+#define STOSEQ_MASK (STORED_SEQS - 1)
+#define ADVANCED_SEQS 4
+               seq_t *sequences = (seq_t *)dctx->entropy.workspace;
+               int const seqAdvance = MIN(nbSeq, ADVANCED_SEQS);
+               seqState_t seqState;
+               int seqNb;
+               ZSTD_STATIC_ASSERT(sizeof(dctx->entropy.workspace) >= 
sizeof(seq_t) * STORED_SEQS);
+               dctx->fseEntropy = 1;
+               {
+                       U32 i;
+                       for (i = 0; i < ZSTD_REP_NUM; i++)
+                               seqState.prevOffset[i] = dctx->entropy.rep[i];
+               }
+               seqState.base = base;
+               seqState.pos = (size_t)(op - base);
+               seqState.gotoDict = (uPtrDiff)dictEnd - (uPtrDiff)base; /* cast 
to avoid undefined behaviour */
+               CHECK_E(BIT_initDStream(&seqState.DStream, ip, iend - ip), 
corruption_detected);
+               FSE_initDState(&seqState.stateLL, &seqState.DStream, 
dctx->LLTptr);
+               FSE_initDState(&seqState.stateOffb, &seqState.DStream, 
dctx->OFTptr);
+               FSE_initDState(&seqState.stateML, &seqState.DStream, 
dctx->MLTptr);
+
+               /* prepare in advance */
+               for (seqNb = 0; (BIT_reloadDStream(&seqState.DStream) <= 
BIT_DStream_completed) && seqNb < seqAdvance; seqNb++) {
+                       sequences[seqNb] = ZSTD_decodeSequenceLong(&seqState, 
windowSize);
+               }
+               if (seqNb < seqAdvance)
+                       return ERROR(corruption_detected);
+
+               /* decode and decompress */
+               for (; (BIT_reloadDStream(&(seqState.DStream)) <= 
BIT_DStream_completed) && seqNb < nbSeq; seqNb++) {
+                       seq_t const sequence = 
ZSTD_decodeSequenceLong(&seqState, windowSize);
+                       size_t const oneSeqSize =
+                           ZSTD_execSequenceLong(op, oend, sequences[(seqNb - 
ADVANCED_SEQS) & STOSEQ_MASK], &litPtr, litEnd, base, vBase, dictEnd);
+                       if (ZSTD_isError(oneSeqSize))
+                               return oneSeqSize;
+                       ZSTD_PREFETCH(sequence.match);
+                       sequences[seqNb & STOSEQ_MASK] = sequence;
+                       op += oneSeqSize;
+               }
+               if (seqNb < nbSeq)
+                       return ERROR(corruption_detected);
+
+               /* finish queue */
+               seqNb -= seqAdvance;
+               for (; seqNb < nbSeq; seqNb++) {
+                       size_t const oneSeqSize = ZSTD_execSequenceLong(op, 
oend, sequences[seqNb & STOSEQ_MASK], &litPtr, litEnd, base, vBase, dictEnd);
+                       if (ZSTD_isError(oneSeqSize))
+                               return oneSeqSize;
+                       op += oneSeqSize;
+               }
+
+               /* save reps for next block */
+               {
+                       U32 i;
+                       for (i = 0; i < ZSTD_REP_NUM; i++)
+                               dctx->entropy.rep[i] = 
(U32)(seqState.prevOffset[i]);
+               }
+       }
+
+       /* last literal segment */
+       {
+               size_t const lastLLSize = litEnd - litPtr;
+               if (lastLLSize > (size_t)(oend - op))
+                       return ERROR(dstSize_tooSmall);
+               memcpy(op, litPtr, lastLLSize);
+               op += lastLLSize;
+       }
+
+       return op - ostart;
+}
+
+static size_t INIT ZSTD_decompressBlock_internal(ZSTD_DCtx *dctx, void *dst, 
size_t dstCapacity, const void *src, size_t srcSize)
+{ /* blockType == blockCompressed */
+       const BYTE *ip = (const BYTE *)src;
+
+       if (srcSize >= ZSTD_BLOCKSIZE_ABSOLUTEMAX)
+               return ERROR(srcSize_wrong);
+
+       /* Decode literals section */
+       {
+               size_t const litCSize = ZSTD_decodeLiteralsBlock(dctx, src, 
srcSize);
+               if (ZSTD_isError(litCSize))
+                       return litCSize;
+               ip += litCSize;
+               srcSize -= litCSize;
+       }
+       if (sizeof(size_t) > 4) /* do not enable prefetching on 32-bits x86, as 
it's performance detrimental */
+                               /* likely because of register pressure */
+                               /* if that's the correct cause, then 32-bits 
ARM should be affected differently */
+                               /* it would be good to test this on ARM real 
hardware, to see if prefetch version improves speed */
+               if (dctx->fParams.windowSize > (1 << 23))
+                       return ZSTD_decompressSequencesLong(dctx, dst, 
dstCapacity, ip, srcSize);
+       return ZSTD_decompressSequences(dctx, dst, dstCapacity, ip, srcSize);
+}
+
+static void INIT ZSTD_checkContinuity(ZSTD_DCtx *dctx, const void *dst)
+{
+       if (dst != dctx->previousDstEnd) { /* not contiguous */
+               dctx->dictEnd = dctx->previousDstEnd;
+               dctx->vBase = (const char *)dst - ((const char 
*)(dctx->previousDstEnd) - (const char *)(dctx->base));
+               dctx->base = dst;
+               dctx->previousDstEnd = dst;
+       }
+}
+
+size_t INIT ZSTD_decompressBlock(ZSTD_DCtx *dctx, void *dst, size_t 
dstCapacity, const void *src, size_t srcSize)
+{
+       size_t dSize;
+       ZSTD_checkContinuity(dctx, dst);
+       dSize = ZSTD_decompressBlock_internal(dctx, dst, dstCapacity, src, 
srcSize);
+       dctx->previousDstEnd = (char *)dst + dSize;
+       return dSize;
+}
+
+/** ZSTD_insertBlock() :
+       insert `src` block into `dctx` history. Useful to track uncompressed 
blocks. */
+size_t INIT ZSTD_insertBlock(ZSTD_DCtx *dctx, const void *blockStart, size_t 
blockSize)
+{
+       ZSTD_checkContinuity(dctx, blockStart);
+       dctx->previousDstEnd = (const char *)blockStart + blockSize;
+       return blockSize;
+}
+
+size_t INIT ZSTD_generateNxBytes(void *dst, size_t dstCapacity, BYTE byte, 
size_t length)
+{
+       if (length > dstCapacity)
+               return ERROR(dstSize_tooSmall);
+       memset(dst, byte, length);
+       return length;
+}
+
+/** ZSTD_findFrameCompressedSize() :
+ *  compatible with legacy mode
+ *  `src` must point to the start of a ZSTD frame, ZSTD legacy frame, or 
skippable frame
+ *  `srcSize` must be at least as large as the frame contained
+ *  @return : the compressed size of the frame starting at `src` */
+size_t INIT ZSTD_findFrameCompressedSize(const void *src, size_t srcSize)
+{
+       if (srcSize >= ZSTD_skippableHeaderSize && (ZSTD_readLE32(src) & 
0xFFFFFFF0U) == ZSTD_MAGIC_SKIPPABLE_START) {
+               return ZSTD_skippableHeaderSize + ZSTD_readLE32((const BYTE 
*)src + 4);
+       } else {
+               const BYTE *ip = (const BYTE *)src;
+               const BYTE *const ipstart = ip;
+               size_t remainingSize = srcSize;
+               ZSTD_frameParams fParams;
+
+               size_t const headerSize = ZSTD_frameHeaderSize(ip, 
remainingSize);
+               if (ZSTD_isError(headerSize))
+                       return headerSize;
+
+               /* Frame Header */
+               {
+                       size_t const ret = ZSTD_getFrameParams(&fParams, ip, 
remainingSize);
+                       if (ZSTD_isError(ret))
+                               return ret;
+                       if (ret > 0)
+                               return ERROR(srcSize_wrong);
+               }
+
+               ip += headerSize;
+               remainingSize -= headerSize;
+
+               /* Loop on each block */
+               while (1) {
+                       blockProperties_t blockProperties;
+                       size_t const cBlockSize = ZSTD_getcBlockSize(ip, 
remainingSize, &blockProperties);
+                       if (ZSTD_isError(cBlockSize))
+                               return cBlockSize;
+
+                       if (ZSTD_blockHeaderSize + cBlockSize > remainingSize)
+                               return ERROR(srcSize_wrong);
+
+                       ip += ZSTD_blockHeaderSize + cBlockSize;
+                       remainingSize -= ZSTD_blockHeaderSize + cBlockSize;
+
+                       if (blockProperties.lastBlock)
+                               break;
+               }
+
+               if (fParams.checksumFlag) { /* Frame content checksum */
+                       if (remainingSize < 4)
+                               return ERROR(srcSize_wrong);
+                       ip += 4;
+                       remainingSize -= 4;
+               }
+
+               return ip - ipstart;
+       }
+}
+
+/*! ZSTD_decompressFrame() :
+*   @dctx must be properly initialized */
+static size_t INIT ZSTD_decompressFrame(ZSTD_DCtx *dctx, void *dst, size_t 
dstCapacity, const void **srcPtr, size_t *srcSizePtr)
+{
+       const BYTE *ip = (const BYTE *)(*srcPtr);
+       BYTE *const ostart = (BYTE * const)dst;
+       BYTE *const oend = ostart + dstCapacity;
+       BYTE *op = ostart;
+       size_t remainingSize = *srcSizePtr;
+
+       /* check */
+       if (remainingSize < ZSTD_frameHeaderSize_min + ZSTD_blockHeaderSize)
+               return ERROR(srcSize_wrong);
+
+       /* Frame Header */
+       {
+               size_t const frameHeaderSize = ZSTD_frameHeaderSize(ip, 
ZSTD_frameHeaderSize_prefix);
+               if (ZSTD_isError(frameHeaderSize))
+                       return frameHeaderSize;
+               if (remainingSize < frameHeaderSize + ZSTD_blockHeaderSize)
+                       return ERROR(srcSize_wrong);
+               CHECK_F(ZSTD_decodeFrameHeader(dctx, ip, frameHeaderSize));
+               ip += frameHeaderSize;
+               remainingSize -= frameHeaderSize;
+       }
+
+       /* Loop on each block */
+       while (1) {
+               size_t decodedSize;
+               blockProperties_t blockProperties;
+               size_t const cBlockSize = ZSTD_getcBlockSize(ip, remainingSize, 
&blockProperties);
+               if (ZSTD_isError(cBlockSize))
+                       return cBlockSize;
+
+               ip += ZSTD_blockHeaderSize;
+               remainingSize -= ZSTD_blockHeaderSize;
+               if (cBlockSize > remainingSize)
+                       return ERROR(srcSize_wrong);
+
+               switch (blockProperties.blockType) {
+               case bt_compressed: decodedSize = 
ZSTD_decompressBlock_internal(dctx, op, oend - op, ip, cBlockSize); break;
+               case bt_raw: decodedSize = ZSTD_copyRawBlock(op, oend - op, ip, 
cBlockSize); break;
+               case bt_rle: decodedSize = ZSTD_generateNxBytes(op, oend - op, 
*ip, blockProperties.origSize); break;
+               case bt_reserved:
+               default: return ERROR(corruption_detected);
+               }
+
+               if (ZSTD_isError(decodedSize))
+                       return decodedSize;
+               if (dctx->fParams.checksumFlag)
+                       xxh64_update(&dctx->xxhState, op, decodedSize);
+               op += decodedSize;
+               ip += cBlockSize;
+               remainingSize -= cBlockSize;
+               if (blockProperties.lastBlock)
+                       break;
+       }
+
+       if (dctx->fParams.checksumFlag) { /* Frame content checksum 
verification */
+               U32 const checkCalc = (U32)xxh64_digest(&dctx->xxhState);
+               U32 checkRead;
+               if (remainingSize < 4)
+                       return ERROR(checksum_wrong);
+               checkRead = ZSTD_readLE32(ip);
+               if (checkRead != checkCalc)
+                       return ERROR(checksum_wrong);
+               ip += 4;
+               remainingSize -= 4;
+       }
+
+       /* Allow caller to get size read */
+       *srcPtr = ip;
+       *srcSizePtr = remainingSize;
+       return op - ostart;
+}
+
+static const void *ZSTD_DDictDictContent(const ZSTD_DDict *ddict);
+static size_t ZSTD_DDictDictSize(const ZSTD_DDict *ddict);
+
+static size_t INIT ZSTD_decompressMultiFrame(ZSTD_DCtx *dctx, void *dst, 
size_t dstCapacity, const void *src, size_t srcSize, const void *dict, size_t 
dictSize,
+                                       const ZSTD_DDict *ddict)
+{
+       void *const dststart = dst;
+
+       if (ddict) {
+               if (dict) {
+                       /* programmer error, these two cases should be mutually 
exclusive */
+                       return ERROR(GENERIC);
+               }
+
+               dict = ZSTD_DDictDictContent(ddict);
+               dictSize = ZSTD_DDictDictSize(ddict);
+       }
+
+       while (srcSize >= ZSTD_frameHeaderSize_prefix) {
+               U32 magicNumber;
+
+               magicNumber = ZSTD_readLE32(src);
+               if (magicNumber != ZSTD_MAGICNUMBER) {
+                       if ((magicNumber & 0xFFFFFFF0U) == 
ZSTD_MAGIC_SKIPPABLE_START) {
+                               size_t skippableSize;
+                               if (srcSize < ZSTD_skippableHeaderSize)
+                                       return ERROR(srcSize_wrong);
+                               skippableSize = ZSTD_readLE32((const BYTE *)src 
+ 4) + ZSTD_skippableHeaderSize;
+                               if (srcSize < skippableSize) {
+                                       return ERROR(srcSize_wrong);
+                               }
+
+                               src = (const BYTE *)src + skippableSize;
+                               srcSize -= skippableSize;
+                               continue;
+                       } else {
+                               return ERROR(prefix_unknown);
+                       }
+               }
+
+               if (ddict) {
+                       /* we were called from ZSTD_decompress_usingDDict */
+                       ZSTD_refDDict(dctx, ddict);
+               } else {
+                       /* this will initialize correctly with no dict if dict 
== NULL, so
+                        * use this in all cases but ddict */
+                       CHECK_F(ZSTD_decompressBegin_usingDict(dctx, dict, 
dictSize));
+               }
+               ZSTD_checkContinuity(dctx, dst);
+
+               {
+                       const size_t res = ZSTD_decompressFrame(dctx, dst, 
dstCapacity, &src, &srcSize);
+                       if (ZSTD_isError(res))
+                               return res;
+                       /* don't need to bounds check this, 
ZSTD_decompressFrame will have
+                        * already */
+                       dst = (BYTE *)dst + res;
+                       dstCapacity -= res;
+               }
+       }
+
+       if (srcSize)
+               return ERROR(srcSize_wrong); /* input not entirely consumed */
+
+       return (BYTE *)dst - (BYTE *)dststart;
+}
+
+size_t INIT ZSTD_decompress_usingDict(ZSTD_DCtx *dctx, void *dst, size_t 
dstCapacity, const void *src, size_t srcSize, const void *dict, size_t dictSize)
+{
+       return ZSTD_decompressMultiFrame(dctx, dst, dstCapacity, src, srcSize, 
dict, dictSize, NULL);
+}
+
+size_t INIT ZSTD_decompressDCtx(ZSTD_DCtx *dctx, void *dst, size_t 
dstCapacity, const void *src, size_t srcSize)
+{
+       return ZSTD_decompress_usingDict(dctx, dst, dstCapacity, src, srcSize, 
NULL, 0);
+}
+
+/*-**************************************
+*   Advanced Streaming Decompression API
+*   Bufferless and synchronous
+****************************************/
+size_t INIT ZSTD_nextSrcSizeToDecompress(ZSTD_DCtx *dctx) { return 
dctx->expected; }
+
+ZSTD_nextInputType_e INIT ZSTD_nextInputType(ZSTD_DCtx *dctx)
+{
+       switch (dctx->stage) {
+       default: /* should not happen */
+       case ZSTDds_getFrameHeaderSize:
+       case ZSTDds_decodeFrameHeader: return ZSTDnit_frameHeader;
+       case ZSTDds_decodeBlockHeader: return ZSTDnit_blockHeader;
+       case ZSTDds_decompressBlock: return ZSTDnit_block;
+       case ZSTDds_decompressLastBlock: return ZSTDnit_lastBlock;
+       case ZSTDds_checkChecksum: return ZSTDnit_checksum;
+       case ZSTDds_decodeSkippableHeader:
+       case ZSTDds_skipFrame: return ZSTDnit_skippableFrame;
+       }
+}
+
+int INIT ZSTD_isSkipFrame(ZSTD_DCtx *dctx) { return dctx->stage == 
ZSTDds_skipFrame; } /* for zbuff */
+
+/** ZSTD_decompressContinue() :
+*   @return : nb of bytes generated into `dst` (necessarily <= `dstCapacity)
+*             or an error code, which can be tested using ZSTD_isError() */
+size_t INIT ZSTD_decompressContinue(ZSTD_DCtx *dctx, void *dst, size_t 
dstCapacity, const void *src, size_t srcSize)
+{
+       /* Sanity check */
+       if (srcSize != dctx->expected)
+               return ERROR(srcSize_wrong);
+       if (dstCapacity)
+               ZSTD_checkContinuity(dctx, dst);
+
+       switch (dctx->stage) {
+       case ZSTDds_getFrameHeaderSize:
+               if (srcSize != ZSTD_frameHeaderSize_prefix)
+                       return ERROR(srcSize_wrong);                            
        /* impossible */
+               if ((ZSTD_readLE32(src) & 0xFFFFFFF0U) == 
ZSTD_MAGIC_SKIPPABLE_START) { /* skippable frame */
+                       memcpy(dctx->headerBuffer, src, 
ZSTD_frameHeaderSize_prefix);
+                       dctx->expected = ZSTD_skippableHeaderSize - 
ZSTD_frameHeaderSize_prefix; /* magic number + skippable frame length */
+                       dctx->stage = ZSTDds_decodeSkippableHeader;
+                       return 0;
+               }
+               dctx->headerSize = ZSTD_frameHeaderSize(src, 
ZSTD_frameHeaderSize_prefix);
+               if (ZSTD_isError(dctx->headerSize))
+                       return dctx->headerSize;
+               memcpy(dctx->headerBuffer, src, ZSTD_frameHeaderSize_prefix);
+               if (dctx->headerSize > ZSTD_frameHeaderSize_prefix) {
+                       dctx->expected = dctx->headerSize - 
ZSTD_frameHeaderSize_prefix;
+                       dctx->stage = ZSTDds_decodeFrameHeader;
+                       return 0;
+               }
+               dctx->expected = 0; /* not necessary to copy more */
+               /* fallthrough */
+
+       case ZSTDds_decodeFrameHeader:
+               memcpy(dctx->headerBuffer + ZSTD_frameHeaderSize_prefix, src, 
dctx->expected);
+               CHECK_F(ZSTD_decodeFrameHeader(dctx, dctx->headerBuffer, 
dctx->headerSize));
+               dctx->expected = ZSTD_blockHeaderSize;
+               dctx->stage = ZSTDds_decodeBlockHeader;
+               return 0;
+
+       case ZSTDds_decodeBlockHeader: {
+               blockProperties_t bp;
+               size_t const cBlockSize = ZSTD_getcBlockSize(src, 
ZSTD_blockHeaderSize, &bp);
+               if (ZSTD_isError(cBlockSize))
+                       return cBlockSize;
+               dctx->expected = cBlockSize;
+               dctx->bType = bp.blockType;
+               dctx->rleSize = bp.origSize;
+               if (cBlockSize) {
+                       dctx->stage = bp.lastBlock ? ZSTDds_decompressLastBlock 
: ZSTDds_decompressBlock;
+                       return 0;
+               }
+               /* empty block */
+               if (bp.lastBlock) {
+                       if (dctx->fParams.checksumFlag) {
+                               dctx->expected = 4;
+                               dctx->stage = ZSTDds_checkChecksum;
+                       } else {
+                               dctx->expected = 0; /* end of frame */
+                               dctx->stage = ZSTDds_getFrameHeaderSize;
+                       }
+               } else {
+                       dctx->expected = 3; /* go directly to next header */
+                       dctx->stage = ZSTDds_decodeBlockHeader;
+               }
+               return 0;
+       }
+       case ZSTDds_decompressLastBlock:
+       case ZSTDds_decompressBlock: {
+               size_t rSize;
+               switch (dctx->bType) {
+               case bt_compressed: rSize = ZSTD_decompressBlock_internal(dctx, 
dst, dstCapacity, src, srcSize); break;
+               case bt_raw: rSize = ZSTD_copyRawBlock(dst, dstCapacity, src, 
srcSize); break;
+               case bt_rle: rSize = ZSTD_setRleBlock(dst, dstCapacity, src, 
srcSize, dctx->rleSize); break;
+               case bt_reserved: /* should never happen */
+               default: return ERROR(corruption_detected);
+               }
+               if (ZSTD_isError(rSize))
+                       return rSize;
+               if (dctx->fParams.checksumFlag)
+                       xxh64_update(&dctx->xxhState, dst, rSize);
+
+               if (dctx->stage == ZSTDds_decompressLastBlock) { /* end of 
frame */
+                       if (dctx->fParams.checksumFlag) {       /* another 
round for frame checksum */
+                               dctx->expected = 4;
+                               dctx->stage = ZSTDds_checkChecksum;
+                       } else {
+                               dctx->expected = 0; /* ends here */
+                               dctx->stage = ZSTDds_getFrameHeaderSize;
+                       }
+               } else {
+                       dctx->stage = ZSTDds_decodeBlockHeader;
+                       dctx->expected = ZSTD_blockHeaderSize;
+                       dctx->previousDstEnd = (char *)dst + rSize;
+               }
+               return rSize;
+       }
+       case ZSTDds_checkChecksum: {
+               U32 const h32 = (U32)xxh64_digest(&dctx->xxhState);
+               U32 const check32 = ZSTD_readLE32(src); /* srcSize == 4, 
guaranteed by dctx->expected */
+               if (check32 != h32)
+                       return ERROR(checksum_wrong);
+               dctx->expected = 0;
+               dctx->stage = ZSTDds_getFrameHeaderSize;
+               return 0;
+       }
+       case ZSTDds_decodeSkippableHeader: {
+               memcpy(dctx->headerBuffer + ZSTD_frameHeaderSize_prefix, src, 
dctx->expected);
+               dctx->expected = ZSTD_readLE32(dctx->headerBuffer + 4);
+               dctx->stage = ZSTDds_skipFrame;
+               return 0;
+       }
+       case ZSTDds_skipFrame: {
+               dctx->expected = 0;
+               dctx->stage = ZSTDds_getFrameHeaderSize;
+               return 0;
+       }
+       default:
+               return ERROR(GENERIC); /* impossible */
+       }
+}
+
+static size_t INIT ZSTD_refDictContent(ZSTD_DCtx *dctx, const void *dict, 
size_t dictSize)
+{
+       dctx->dictEnd = dctx->previousDstEnd;
+       dctx->vBase = (const char *)dict - ((const char 
*)(dctx->previousDstEnd) - (const char *)(dctx->base));
+       dctx->base = dict;
+       dctx->previousDstEnd = (const char *)dict + dictSize;
+       return 0;
+}
+
+/* ZSTD_loadEntropy() :
+ * dict : must point at beginning of a valid zstd dictionary
+ * @return : size of entropy tables read */
+static size_t INIT ZSTD_loadEntropy(ZSTD_entropyTables_t *entropy, const void 
*const dict, size_t const dictSize)
+{
+       const BYTE *dictPtr = (const BYTE *)dict;
+       const BYTE *const dictEnd = dictPtr + dictSize;
+
+       if (dictSize <= 8)
+               return ERROR(dictionary_corrupted);
+       dictPtr += 8; /* skip header = magic + dictID */
+
+       {
+               size_t const hSize = HUF_readDTableX4_wksp(entropy->hufTable, 
dictPtr, dictEnd - dictPtr, entropy->workspace, sizeof(entropy->workspace));
+               if (HUF_isError(hSize))
+                       return ERROR(dictionary_corrupted);
+               dictPtr += hSize;
+       }
+
+       {
+               short offcodeNCount[MaxOff + 1];
+               U32 offcodeMaxValue = MaxOff, offcodeLog;
+               size_t const offcodeHeaderSize = FSE_readNCount(offcodeNCount, 
&offcodeMaxValue, &offcodeLog, dictPtr, dictEnd - dictPtr);
+               if (FSE_isError(offcodeHeaderSize))
+                       return ERROR(dictionary_corrupted);
+               if (offcodeLog > OffFSELog)
+                       return ERROR(dictionary_corrupted);
+               CHECK_E(FSE_buildDTable_wksp(entropy->OFTable, offcodeNCount, 
offcodeMaxValue, offcodeLog, entropy->workspace, sizeof(entropy->workspace)), 
dictionary_corrupted);
+               dictPtr += offcodeHeaderSize;
+       }
+
+       {
+               short matchlengthNCount[MaxML + 1];
+               unsigned matchlengthMaxValue = MaxML, matchlengthLog;
+               size_t const matchlengthHeaderSize = 
FSE_readNCount(matchlengthNCount, &matchlengthMaxValue, &matchlengthLog, 
dictPtr, dictEnd - dictPtr);
+               if (FSE_isError(matchlengthHeaderSize))
+                       return ERROR(dictionary_corrupted);
+               if (matchlengthLog > MLFSELog)
+                       return ERROR(dictionary_corrupted);
+               CHECK_E(FSE_buildDTable_wksp(entropy->MLTable, 
matchlengthNCount, matchlengthMaxValue, matchlengthLog, entropy->workspace, 
sizeof(entropy->workspace)), dictionary_corrupted);
+               dictPtr += matchlengthHeaderSize;
+       }
+
+       {
+               short litlengthNCount[MaxLL + 1];
+               unsigned litlengthMaxValue = MaxLL, litlengthLog;
+               size_t const litlengthHeaderSize = 
FSE_readNCount(litlengthNCount, &litlengthMaxValue, &litlengthLog, dictPtr, 
dictEnd - dictPtr);
+               if (FSE_isError(litlengthHeaderSize))
+                       return ERROR(dictionary_corrupted);
+               if (litlengthLog > LLFSELog)
+                       return ERROR(dictionary_corrupted);
+               CHECK_E(FSE_buildDTable_wksp(entropy->LLTable, litlengthNCount, 
litlengthMaxValue, litlengthLog, entropy->workspace, 
sizeof(entropy->workspace)), dictionary_corrupted);
+               dictPtr += litlengthHeaderSize;
+       }
+
+       if (dictPtr + 12 > dictEnd)
+               return ERROR(dictionary_corrupted);
+       {
+               int i;
+               size_t const dictContentSize = (size_t)(dictEnd - (dictPtr + 
12));
+               for (i = 0; i < 3; i++) {
+                       U32 const rep = ZSTD_readLE32(dictPtr);
+                       dictPtr += 4;
+                       if (rep == 0 || rep >= dictContentSize)
+                               return ERROR(dictionary_corrupted);
+                       entropy->rep[i] = rep;
+               }
+       }
+
+       return dictPtr - (const BYTE *)dict;
+}
+
+static size_t INIT ZSTD_decompress_insertDictionary(ZSTD_DCtx *dctx, const 
void *dict, size_t dictSize)
+{
+       if (dictSize < 8)
+               return ZSTD_refDictContent(dctx, dict, dictSize);
+       {
+               U32 const magic = ZSTD_readLE32(dict);
+               if (magic != ZSTD_DICT_MAGIC) {
+                       return ZSTD_refDictContent(dctx, dict, dictSize); /* 
pure content mode */
+               }
+       }
+       dctx->dictID = ZSTD_readLE32((const char *)dict + 4);
+
+       /* load entropy tables */
+       {
+               size_t const eSize = ZSTD_loadEntropy(&dctx->entropy, dict, 
dictSize);
+               if (ZSTD_isError(eSize))
+                       return ERROR(dictionary_corrupted);
+               dict = (const char *)dict + eSize;
+               dictSize -= eSize;
+       }
+       dctx->litEntropy = dctx->fseEntropy = 1;
+
+       /* reference dictionary content */
+       return ZSTD_refDictContent(dctx, dict, dictSize);
+}
+
+size_t INIT ZSTD_decompressBegin_usingDict(ZSTD_DCtx *dctx, const void *dict, 
size_t dictSize)
+{
+       CHECK_F(ZSTD_decompressBegin(dctx));
+       if (dict && dictSize)
+               CHECK_E(ZSTD_decompress_insertDictionary(dctx, dict, dictSize), 
dictionary_corrupted);
+       return 0;
+}
+
+/* ======   ZSTD_DDict   ====== */
+
+struct ZSTD_DDict_s {
+       void *dictBuffer;
+       const void *dictContent;
+       size_t dictSize;
+       ZSTD_entropyTables_t entropy;
+       U32 dictID;
+       U32 entropyPresent;
+       ZSTD_customMem cMem;
+}; /* typedef'd to ZSTD_DDict within "zstd.h" */
+
+size_t INIT ZSTD_DDictWorkspaceBound(void) { return 
ZSTD_ALIGN(sizeof(ZSTD_stack)) + ZSTD_ALIGN(sizeof(ZSTD_DDict)); }
+
+static const void *INIT ZSTD_DDictDictContent(const ZSTD_DDict *ddict) { 
return ddict->dictContent; }
+
+static size_t INIT ZSTD_DDictDictSize(const ZSTD_DDict *ddict) { return 
ddict->dictSize; }
+
+static void INIT ZSTD_refDDict(ZSTD_DCtx *dstDCtx, const ZSTD_DDict *ddict)
+{
+       ZSTD_decompressBegin(dstDCtx); /* init */
+       if (ddict) {                   /* support refDDict on NULL */
+               dstDCtx->dictID = ddict->dictID;
+               dstDCtx->base = ddict->dictContent;
+               dstDCtx->vBase = ddict->dictContent;
+               dstDCtx->dictEnd = (const BYTE *)ddict->dictContent + 
ddict->dictSize;
+               dstDCtx->previousDstEnd = dstDCtx->dictEnd;
+               if (ddict->entropyPresent) {
+                       dstDCtx->litEntropy = 1;
+                       dstDCtx->fseEntropy = 1;
+                       dstDCtx->LLTptr = ddict->entropy.LLTable;
+                       dstDCtx->MLTptr = ddict->entropy.MLTable;
+                       dstDCtx->OFTptr = ddict->entropy.OFTable;
+                       dstDCtx->HUFptr = ddict->entropy.hufTable;
+                       dstDCtx->entropy.rep[0] = ddict->entropy.rep[0];
+                       dstDCtx->entropy.rep[1] = ddict->entropy.rep[1];
+                       dstDCtx->entropy.rep[2] = ddict->entropy.rep[2];
+               } else {
+                       dstDCtx->litEntropy = 0;
+                       dstDCtx->fseEntropy = 0;
+               }
+       }
+}
+
+static size_t INIT ZSTD_loadEntropy_inDDict(ZSTD_DDict *ddict)
+{
+       ddict->dictID = 0;
+       ddict->entropyPresent = 0;
+       if (ddict->dictSize < 8)
+               return 0;
+       {
+               U32 const magic = ZSTD_readLE32(ddict->dictContent);
+               if (magic != ZSTD_DICT_MAGIC)
+                       return 0; /* pure content mode */
+       }
+       ddict->dictID = ZSTD_readLE32((const char *)ddict->dictContent + 4);
+
+       /* load entropy tables */
+       CHECK_E(ZSTD_loadEntropy(&ddict->entropy, ddict->dictContent, 
ddict->dictSize), dictionary_corrupted);
+       ddict->entropyPresent = 1;
+       return 0;
+}
+
+static ZSTD_DDict *INIT ZSTD_createDDict_advanced(const void *dict, size_t 
dictSize, unsigned byReference, ZSTD_customMem customMem)
+{
+       if (!customMem.customAlloc || !customMem.customFree)
+               return NULL;
+
+       {
+               ZSTD_DDict *const ddict = (ZSTD_DDict 
*)ZSTD_malloc(sizeof(ZSTD_DDict), customMem);
+               if (!ddict)
+                       return NULL;
+               ddict->cMem = customMem;
+
+               if ((byReference) || (!dict) || (!dictSize)) {
+                       ddict->dictBuffer = NULL;
+                       ddict->dictContent = dict;
+               } else {
+                       void *const internalBuffer = ZSTD_malloc(dictSize, 
customMem);
+                       if (!internalBuffer) {
+                               ZSTD_freeDDict(ddict);
+                               return NULL;
+                       }
+                       memcpy(internalBuffer, dict, dictSize);
+                       ddict->dictBuffer = internalBuffer;
+                       ddict->dictContent = internalBuffer;
+               }
+               ddict->dictSize = dictSize;
+               ddict->entropy.hufTable[0] = (HUF_DTable)((HufLog)*0x1000001); 
/* cover both little and big endian */
+               /* parse dictionary content */
+               {
+                       size_t const errorCode = 
ZSTD_loadEntropy_inDDict(ddict);
+                       if (ZSTD_isError(errorCode)) {
+                               ZSTD_freeDDict(ddict);
+                               return NULL;
+                       }
+               }
+
+               return ddict;
+       }
+}
+
+/*! ZSTD_initDDict() :
+*   Create a digested dictionary, to start decompression without startup delay.
+*   `dict` content is copied inside DDict.
+*   Consequently, `dict` can be released after `ZSTD_DDict` creation */
+ZSTD_DDict *INIT ZSTD_initDDict(const void *dict, size_t dictSize, void 
*workspace, size_t workspaceSize)
+{
+       ZSTD_customMem const stackMem = ZSTD_initStack(workspace, 
workspaceSize);
+       return ZSTD_createDDict_advanced(dict, dictSize, 1, stackMem);
+}
+
+size_t INIT ZSTD_freeDDict(ZSTD_DDict *ddict)
+{
+       if (ddict == NULL)
+               return 0; /* support free on NULL */
+       {
+               ZSTD_customMem const cMem = ddict->cMem;
+               ZSTD_free(ddict->dictBuffer, cMem);
+               ZSTD_free(ddict, cMem);
+               return 0;
+       }
+}
+
+/*! ZSTD_getDictID_fromDict() :
+ *  Provides the dictID stored within dictionary.
+ *  if @return == 0, the dictionary is not conformant with Zstandard 
specification.
+ *  It can still be loaded, but as a content-only dictionary. */
+unsigned INIT ZSTD_getDictID_fromDict(const void *dict, size_t dictSize)
+{
+       if (dictSize < 8)
+               return 0;
+       if (ZSTD_readLE32(dict) != ZSTD_DICT_MAGIC)
+               return 0;
+       return ZSTD_readLE32((const char *)dict + 4);
+}
+
+/*! ZSTD_getDictID_fromDDict() :
+ *  Provides the dictID of the dictionary loaded into `ddict`.
+ *  If @return == 0, the dictionary is not conformant to Zstandard 
specification, or empty.
+ *  Non-conformant dictionaries can still be loaded, but as content-only 
dictionaries. */
+unsigned INIT ZSTD_getDictID_fromDDict(const ZSTD_DDict *ddict)
+{
+       if (ddict == NULL)
+               return 0;
+       return ZSTD_getDictID_fromDict(ddict->dictContent, ddict->dictSize);
+}
+
+/*! ZSTD_getDictID_fromFrame() :
+ *  Provides the dictID required to decompressed the frame stored within `src`.
+ *  If @return == 0, the dictID could not be decoded.
+ *  This could for one of the following reasons :
+ *  - The frame does not require a dictionary to be decoded (most common case).
+ *  - The frame was built with dictID intentionally removed. Whatever 
dictionary is necessary is a hidden information.
+ *    Note : this use case also happens when using a non-conformant dictionary.
+ *  - `srcSize` is too small, and as a result, the frame header could not be 
decoded (only possible if `srcSize < ZSTD_FRAMEHEADERSIZE_MAX`).
+ *  - This is not a Zstandard frame.
+ *  When identifying the exact failure cause, it's possible to used 
ZSTD_getFrameParams(), which will provide a more precise error code. */
+unsigned INIT ZSTD_getDictID_fromFrame(const void *src, size_t srcSize)
+{
+       ZSTD_frameParams zfp = {0, 0, 0, 0};
+       size_t const hError = ZSTD_getFrameParams(&zfp, src, srcSize);
+       if (ZSTD_isError(hError))
+               return 0;
+       return zfp.dictID;
+}
+
+/*! ZSTD_decompress_usingDDict() :
+*   Decompression using a pre-digested Dictionary
+*   Use dictionary without significant overhead. */
+size_t INIT ZSTD_decompress_usingDDict(ZSTD_DCtx *dctx, void *dst, size_t 
dstCapacity, const void *src, size_t srcSize, const ZSTD_DDict *ddict)
+{
+       /* pass content and size in case legacy frames are encountered */
+       return ZSTD_decompressMultiFrame(dctx, dst, dstCapacity, src, srcSize, 
NULL, 0, ddict);
+}
+
+/*=====================================
+*   Streaming decompression
+*====================================*/
+
+typedef enum { zdss_init, zdss_loadHeader, zdss_read, zdss_load, zdss_flush } 
ZSTD_dStreamStage;
+
+/* *** Resource management *** */
+struct ZSTD_DStream_s {
+       ZSTD_DCtx *dctx;
+       ZSTD_DDict *ddictLocal;
+       const ZSTD_DDict *ddict;
+       ZSTD_frameParams fParams;
+       ZSTD_dStreamStage stage;
+       char *inBuff;
+       size_t inBuffSize;
+       size_t inPos;
+       size_t maxWindowSize;
+       char *outBuff;
+       size_t outBuffSize;
+       size_t outStart;
+       size_t outEnd;
+       size_t blockSize;
+       BYTE headerBuffer[ZSTD_FRAMEHEADERSIZE_MAX]; /* tmp buffer to store 
frame header */
+       size_t lhSize;
+       ZSTD_customMem customMem;
+       void *legacyContext;
+       U32 previousLegacyVersion;
+       U32 legacyVersion;
+       U32 hostageByte;
+}; /* typedef'd to ZSTD_DStream within "zstd.h" */
+
+size_t INIT ZSTD_DStreamWorkspaceBound(size_t maxWindowSize)
+{
+       size_t const blockSize = MIN(maxWindowSize, ZSTD_BLOCKSIZE_ABSOLUTEMAX);
+       size_t const inBuffSize = blockSize;
+       size_t const outBuffSize = maxWindowSize + blockSize + 
WILDCOPY_OVERLENGTH * 2;
+       return ZSTD_DCtxWorkspaceBound() + ZSTD_ALIGN(sizeof(ZSTD_DStream)) + 
ZSTD_ALIGN(inBuffSize) + ZSTD_ALIGN(outBuffSize);
+}
+
+static ZSTD_DStream *INIT ZSTD_createDStream_advanced(ZSTD_customMem customMem)
+{
+       ZSTD_DStream *zds;
+
+       if (!customMem.customAlloc || !customMem.customFree)
+               return NULL;
+
+       zds = (ZSTD_DStream *)ZSTD_malloc(sizeof(ZSTD_DStream), customMem);
+       if (zds == NULL)
+               return NULL;
+       memset(zds, 0, sizeof(ZSTD_DStream));
+       memcpy(&zds->customMem, &customMem, sizeof(ZSTD_customMem));
+       zds->dctx = ZSTD_createDCtx_advanced(customMem);
+       if (zds->dctx == NULL) {
+               ZSTD_freeDStream(zds);
+               return NULL;
+       }
+       zds->stage = zdss_init;
+       zds->maxWindowSize = ZSTD_MAXWINDOWSIZE_DEFAULT;
+       return zds;
+}
+
+ZSTD_DStream *INIT ZSTD_initDStream(size_t maxWindowSize, void *workspace, 
size_t workspaceSize)
+{
+       ZSTD_customMem const stackMem = ZSTD_initStack(workspace, 
workspaceSize);
+       ZSTD_DStream *zds = ZSTD_createDStream_advanced(stackMem);
+       if (!zds) {
+               return NULL;
+       }
+



 


Rackspace

Lists.xenproject.org is hosted with RackSpace, monitoring our
servers 24x7x365 and backed by RackSpace's Fanatical Support®.