|
[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(¶ms, 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;
+ }
+
|
 |
Lists.xenproject.org is hosted with RackSpace, monitoring our |