Attachment #630946 for bug #716520

Lines 2490-2495 size_t ZSTD_decompressStream(ZSTD_DStream zds, ZSTD_outBuffer output, ZSTD_inB Link Here

(-)a/lib/zstd/decompress.c (+2 lines)
2490	}	2490	}
2491	}	2491	}
2492		2492
		2493	#ifndef ZSTD_PREBOOT
2493	EXPORT_SYMBOL(ZSTD_DCtxWorkspaceBound);	2494	EXPORT_SYMBOL(ZSTD_DCtxWorkspaceBound);
2494	EXPORT_SYMBOL(ZSTD_initDCtx);	2495	EXPORT_SYMBOL(ZSTD_initDCtx);
2495	EXPORT_SYMBOL(ZSTD_decompressDCtx);	2496	EXPORT_SYMBOL(ZSTD_decompressDCtx);
Lines 2529-2531 EXPORT_SYMBOL(ZSTD_insertBlock); Link Here
2529		2530
2530	MODULE_LICENSE("Dual BSD/GPL");	2531	MODULE_LICENSE("Dual BSD/GPL");
2531	MODULE_DESCRIPTION("Zstd Decompressor");	2532	MODULE_DESCRIPTION("Zstd Decompressor");
		2533	#endif

Lines 47-52 Link Here

(-)a/lib/zstd/fse_decompress.c (-8 / +1 lines)
47	****************************************************************/	47	****************************************************************/
48	#include "bitstream.h"	48	#include "bitstream.h"
49	#include "fse.h"	49	#include "fse.h"
		50	#include "zstd_internal.h"
50	#include <linux/compiler.h>	51	#include <linux/compiler.h>
51	#include <linux/kernel.h>	52	#include <linux/kernel.h>
52	#include <linux/string.h> /* memcpy, memset */	53	#include <linux/string.h> /* memcpy, memset */
Lines 60-73 Link Here
60	enum { FSE_static_assert = 1 / (int)(!!(c)) }; \	61	enum { FSE_static_assert = 1 / (int)(!!(c)) }; \
61	} /* use only after variable declarations */	62	} /* use only after variable declarations */
62		63
63	/* check and forward error code */
64	#define CHECK_F(f) \
65	{ \
66	size_t const e = f; \
67	if (FSE_isError(e)) \
68	return e; \
69	}
70
71	/* **************************************************************	64	/* **************************************************************
72	* Templates	65	* Templates
73	****************************************************************/	66	****************************************************************/

Lines 127-133 static const U32 OF_defaultNormLog = OF_DEFAULTNORMLOG; Link Here

(-)a/lib/zstd/zstd_internal.h (-2 / +12 lines)
127	* Shared functions to include for inlining	127	* Shared functions to include for inlining
128	*********************************************/	128	*********************************************/
129	ZSTD_STATIC void ZSTD_copy8(void dst, const void src) {	129	ZSTD_STATIC void ZSTD_copy8(void dst, const void src) {
130	memcpy(dst, src, 8);	130	/*
		131	* zstd relies heavily on gcc being able to analyze and inline this
		132	* memcpy() call, since it is called in a tight loop. Preboot mode
		133	* is compiled in freestanding mode, which stops gcc from analyzing
		134	* memcpy(). Use __builtin_memcpy() to tell gcc to analyze this as a
		135	* regular memcpy().
		136	*/
		137	__builtin_memcpy(dst, src, 8);
131	}	138	}
132	/*! ZSTD_wildcopy() :	139	/*! ZSTD_wildcopy() :
133	* custom version of memcpy(), can copy up to 7 bytes too many (8 bytes if length==0) */	140	* custom version of memcpy(), can copy up to 7 bytes too many (8 bytes if length==0) */
Lines 137-149 ZSTD_STATIC void ZSTD_wildcopy(void dst, const void src, ptrdiff_t length) Link Here
137	const BYTE* ip = (const BYTE*)src;	144	const BYTE* ip = (const BYTE*)src;
138	BYTE* op = (BYTE*)dst;	145	BYTE* op = (BYTE*)dst;
139	BYTE* const oend = op + length;	146	BYTE* const oend = op + length;
140	/* Work around https://gcc.gnu.org/bugzilla/show_bug.cgi?id=81388.	147	#if defined(GCC_VERSION) && GCC_VERSION >= 70000 && GCC_VERSION < 70200
		148	/*
		149	* Work around https://gcc.gnu.org/bugzilla/show_bug.cgi?id=81388.
141	* Avoid the bad case where the loop only runs once by handling the	150	* Avoid the bad case where the loop only runs once by handling the
142	* special case separately. This doesn't trigger the bug because it	151	* special case separately. This doesn't trigger the bug because it
143	* doesn't involve pointer/integer overflow.	152	* doesn't involve pointer/integer overflow.
144	*/	153	*/
145	if (length <= 8)	154	if (length <= 8)
146	return ZSTD_copy8(dst, src);	155	return ZSTD_copy8(dst, src);
		156	#endif
147	do {	157	do {
148	ZSTD_copy8(op, ip);	158	ZSTD_copy8(op, ip);
149	op += 8;	159	op += 8;




{
	memcpy(dst, src, sizeof(*dst));
}
EXPORT_SYMBOL(xxh32_copy_state);

void xxh64_copy_state(struct xxh64_state *dst, const struct xxh64_state *src)
{
	memcpy(dst, src, sizeof(*dst));
}
EXPORT_SYMBOL(xxh64_copy_state);

/*-***************************
 * Simple Hash Functions


	return h32;
}
EXPORT_SYMBOL(xxh32);

static uint64_t xxh64_round(uint64_t acc, const uint64_t input)
{


	return h64;
}
EXPORT_SYMBOL(xxh64);

/*-**************************************************
 * Advanced Hash Functions

	state.v4 = seed - PRIME32_1;
	memcpy(statePtr, &state, sizeof(state));
}
EXPORT_SYMBOL(xxh32_reset);

void xxh64_reset(struct xxh64_state *statePtr, const uint64_t seed)
{

	state.v4 = seed - PRIME64_1;
	memcpy(statePtr, &state, sizeof(state));
}
EXPORT_SYMBOL(xxh64_reset);

int xxh32_update(struct xxh32_state *state, const void *input, const size_t len)
{


	return 0;
}
EXPORT_SYMBOL(xxh32_update);

uint32_t xxh32_digest(const struct xxh32_state *state)
{


	return h32;
}
EXPORT_SYMBOL(xxh32_digest);

int xxh64_update(struct xxh64_state *state, const void *input, const size_t len)
{


	return 0;
}
EXPORT_SYMBOL(xxh64_update);

uint64_t xxh64_digest(const struct xxh64_state *state)
{


	return h64;
}

#ifndef XXH_PREBOOT
EXPORT_SYMBOL(xxh32_copy_state);
EXPORT_SYMBOL(xxh64_copy_state);
EXPORT_SYMBOL(xxh32);
EXPORT_SYMBOL(xxh64);
EXPORT_SYMBOL(xxh32_reset);
EXPORT_SYMBOL(xxh64_reset);
EXPORT_SYMBOL(xxh32_update);
EXPORT_SYMBOL(xxh32_digest);
EXPORT_SYMBOL(xxh64_update);
EXPORT_SYMBOL(xxh64_digest);

MODULE_LICENSE("Dual BSD/GPL");
MODULE_DESCRIPTION("xxHash");
#endif

Line 0 Link Here

(-)a/include/linux/decompress/unzstd.h (+11 lines)
	1	/* SPDX-License-Identifier: GPL-2.0 */
	2	#ifndef LINUX_DECOMPRESS_UNZSTD_H
	3	#define LINUX_DECOMPRESS_UNZSTD_H
	4
	5	int unzstd(unsigned char *inbuf, long len,
	6	long (fill)(void, unsigned long),
	7	long (flush)(void, unsigned long),
	8	unsigned char *output,
	9	long *pos,
	10	void (error_fn)(char x));
	11	#endif

Lines 336-341 config DECOMPRESS_LZ4 Link Here

(-)a/lib/Kconfig (+4 lines)
336	select LZ4_DECOMPRESS	336	select LZ4_DECOMPRESS
337	tristate	337	tristate
338		338
		339	config DECOMPRESS_ZSTD
		340	select ZSTD_DECOMPRESS
		341	tristate
		342
339	#	343	#
340	# Generic allocator support is selected if needed	344	# Generic allocator support is selected if needed
341	#	345	#

Lines 160-165 lib-$(CONFIG_DECOMPRESS_LZMA) += decompress_unlzma.o Link Here

(-)a/lib/Makefile (+1 lines)
160	lib-$(CONFIG_DECOMPRESS_XZ) += decompress_unxz.o	160	lib-$(CONFIG_DECOMPRESS_XZ) += decompress_unxz.o
161	lib-$(CONFIG_DECOMPRESS_LZO) += decompress_unlzo.o	161	lib-$(CONFIG_DECOMPRESS_LZO) += decompress_unlzo.o
162	lib-$(CONFIG_DECOMPRESS_LZ4) += decompress_unlz4.o	162	lib-$(CONFIG_DECOMPRESS_LZ4) += decompress_unlz4.o
		163	lib-$(CONFIG_DECOMPRESS_ZSTD) += decompress_unzstd.o
163		164
164	obj-$(CONFIG_TEXTSEARCH) += textsearch.o	165	obj-$(CONFIG_TEXTSEARCH) += textsearch.o
165	obj-$(CONFIG_TEXTSEARCH_KMP) += ts_kmp.o	166	obj-$(CONFIG_TEXTSEARCH_KMP) += ts_kmp.o

Lines 13-18 Link Here

(-)a/lib/decompress.c (+5 lines)
13	#include <linux/decompress/inflate.h>	13	#include <linux/decompress/inflate.h>
14	#include <linux/decompress/unlzo.h>	14	#include <linux/decompress/unlzo.h>
15	#include <linux/decompress/unlz4.h>	15	#include <linux/decompress/unlz4.h>
		16	#include <linux/decompress/unzstd.h>
16		17
17	#include <linux/types.h>	18	#include <linux/types.h>
18	#include <linux/string.h>	19	#include <linux/string.h>
Lines 37-42 Link Here
37	#ifndef CONFIG_DECOMPRESS_LZ4	38	#ifndef CONFIG_DECOMPRESS_LZ4
38	# define unlz4 NULL	39	# define unlz4 NULL
39	#endif	40	#endif
		41	#ifndef CONFIG_DECOMPRESS_ZSTD
		42	# define unzstd NULL
		43	#endif
40		44
41	struct compress_format {	45	struct compress_format {
42	unsigned char magic[2];	46	unsigned char magic[2];
Lines 52-57 static const struct compress_format compressed_formats[] __initconst = { Link Here
52	{ {0xfd, 0x37}, "xz", unxz },	56	{ {0xfd, 0x37}, "xz", unxz },
53	{ {0x89, 0x4c}, "lzo", unlzo },	57	{ {0x89, 0x4c}, "lzo", unlzo },
54	{ {0x02, 0x21}, "lz4", unlz4 },	58	{ {0x02, 0x21}, "lz4", unlz4 },
		59	{ {0x28, 0xb5}, "zstd", unzstd },
55	{ {0, 0}, NULL, NULL }	60	{ {0, 0}, NULL, NULL }
56	};	61	};
57		62




// 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
 */

/*
 * Preboot environments #include "path/to/decompress_unzstd.c".
 * All of the source files we depend on must be #included.
 * zstd's only source dependeny is xxhash, which has no source
 * dependencies.
 *
 * zstd and xxhash avoid declaring themselves as modules
 * when ZSTD_PREBOOT and XXH_PREBOOT are defined.
 */
#ifdef STATIC
# define ZSTD_PREBOOT
# define XXH_PREBOOT
# include "xxhash.c"
# include "zstd/entropy_common.c"
# include "zstd/fse_decompress.c"
# include "zstd/huf_decompress.c"
# include "zstd/zstd_common.c"
# include "zstd/decompress.c"
#endif

#include <linux/decompress/mm.h>
#include <linux/kernel.h>
#include <linux/zstd.h>

/* 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 anyways. The larger size speeds up initramfs decompression.
 */
#define ZSTD_IOBUF_SIZE		(1 << 17)

static int INIT handle_zstd_error(size_t ret, void (*error)(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, long *in_pos,
				  void (*error)(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, long in_len,
			 long (*fill)(void*, unsigned long),
			 long (*flush)(void*, unsigned long),
			 unsigned char *out_buf, long out_len,
			 long *in_pos,
			 void (*error)(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;

	if (out_len == 0)
		out_len = LONG_MAX; /* no limit */

	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 (in_len < 0) {
		error("ZSTD-compressed data is truncated");
		err = -1;
		goto out;
	}
	/* Set the first non-empty input buffer. */
	in.src = in_buf;
	in.pos = 0;
	in.size = in_len;
	/* Allocate the output buffer if we are using flush(). */
	if (flush != NULL) {
		out_allocated = large_malloc(ZSTD_IOBUF_SIZE);
		if (out_allocated == NULL) {
			error("Out of memory while allocating output buffer");
			err = -1;
			goto out;
		}
		out_buf = out_allocated;
		out_len = ZSTD_IOBUF_SIZE;
	}
	/* Set the output buffer. */
	out.dst = out_buf;
	out.pos = 0;
	out.size = out_len;

	/*
	 * We need to know the window size to allocate the ZSTD_DStream.
	 * Since we are streaming, we need to allocate a buffer for the sliding
	 * window. The window size varies from 1 KB to ZSTD_WINDOWSIZE_MAX
	 * (8 MB), so it is important to use the actual value so as not to
	 * waste memory when it is smaller.
	 */
	ret = ZSTD_getFrameParams(&params, in.src, in.size);
	err = handle_zstd_error(ret, error);
	if (err)
		goto out;
	if (ret != 0) {
		error("ZSTD-compressed data has an incomplete frame header");
		err = -1;
		goto out;
	}
	if (params.windowSize > ZSTD_WINDOWSIZE_MAX) {
		error("ZSTD-compressed data has too large a window size");
		err = -1;
		goto out;
	}

	/*
	 * Allocate the ZSTD_DStream now that we know how much memory is
	 * required.
	 */
	wksp_size = ZSTD_DStreamWorkspaceBound(params.windowSize);
	wksp = large_malloc(wksp_size);
	dstream = ZSTD_initDStream(params.windowSize, wksp, wksp_size);
	if (dstream == NULL) {
		error("Out of memory while allocating ZSTD_DStream");
		err = -1;
		goto out;
	}

	/*
	 * Decompression loop:
	 * Read more data if necessary (error if no more data can be read).
	 * Call the decompression function, which returns 0 when finished.
	 * Flush any data produced if using flush().
	 */
	if (in_pos != NULL)
		*in_pos = 0;
	do {
		/*
		 * If we need to reload data, either we have fill() and can
		 * try to get more data, or we don't and the input is truncated.
		 */
		if (in.pos == in.size) {
			if (in_pos != NULL)
				*in_pos += in.pos;
			in_len = fill ? fill(in_buf, ZSTD_IOBUF_SIZE) : -1;
			if (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;
}

#ifndef ZSTD_PREBOOT
STATIC int INIT unzstd(unsigned char *buf, long len,
		       long (*fill)(void*, unsigned long),
		       long (*flush)(void*, unsigned long),
		       unsigned char *out_buf,
		       long *pos,
		       void (*error)(char *x))
{
	return __unzstd(buf, len, fill, flush, out_buf, 0, pos, error);
}
#else
STATIC int INIT __decompress(unsigned char *buf, long len,
			     long (*fill)(void*, unsigned long),
			     long (*flush)(void*, unsigned long),
			     unsigned char *out_buf, long out_len,
			     long *pos,
			     void (*error)(char *x))
{
	return __unzstd(buf, len, fill, flush, out_buf, out_len, pos, error);
}
#endif

Lines 173-185 config HAVE_KERNEL_LZO Link Here

(-)a/init/Kconfig (-1 / +14 lines)
173	config HAVE_KERNEL_LZ4	173	config HAVE_KERNEL_LZ4
174	bool	174	bool
175		175
		176	config HAVE_KERNEL_ZSTD
		177	bool
		178
176	config HAVE_KERNEL_UNCOMPRESSED	179	config HAVE_KERNEL_UNCOMPRESSED
177	bool	180	bool
178		181
179	choice	182	choice
180	prompt "Kernel compression mode"	183	prompt "Kernel compression mode"
181	default KERNEL_GZIP	184	default KERNEL_GZIP
182	depends on HAVE_KERNEL_GZIP \|\| HAVE_KERNEL_BZIP2 \|\| HAVE_KERNEL_LZMA \|\| HAVE_KERNEL_XZ \|\| HAVE_KERNEL_LZO \|\| HAVE_KERNEL_LZ4 \|\| HAVE_KERNEL_UNCOMPRESSED	185	depends on HAVE_KERNEL_GZIP \|\| HAVE_KERNEL_BZIP2 \|\| HAVE_KERNEL_LZMA \|\| HAVE_KERNEL_XZ \|\| HAVE_KERNEL_LZO \|\| HAVE_KERNEL_LZ4 \|\| HAVE_KERNEL_ZSTD \|\| HAVE_KERNEL_UNCOMPRESSED
183	help	186	help
184	The linux kernel is a kind of self-extracting executable.	187	The linux kernel is a kind of self-extracting executable.
185	Several compression algorithms are available, which differ	188	Several compression algorithms are available, which differ
Lines 258-263 config KERNEL_LZ4 Link Here
258	is about 8% bigger than LZO. But the decompression speed is	261	is about 8% bigger than LZO. But the decompression speed is
259	faster than LZO.	262	faster than LZO.
260		263
		264	config KERNEL_ZSTD
		265	bool "ZSTD"
		266	depends on HAVE_KERNEL_ZSTD
		267	help
		268	ZSTD is a compression algorithm targeting intermediate compression
		269	with fast decompression speed. It will compress better than GZIP and
		270	decompress around the same speed as LZO, but slower than LZ4. You
		271	will need at least 192 KB RAM or more for booting. The zstd command
		272	line tools is required for compression.
		273
261	config KERNEL_UNCOMPRESSED	274	config KERNEL_UNCOMPRESSED
262	bool "None"	275	bool "None"
263	depends on HAVE_KERNEL_UNCOMPRESSED	276	depends on HAVE_KERNEL_UNCOMPRESSED




quiet_cmd_xzmisc = XZMISC  $@
      cmd_xzmisc = cat $(real-prereqs) | xz --check=crc32 --lzma2=dict=1MiB > $@

# ZSTD
# ---------------------------------------------------------------------------
# Appends the uncompressed size of the data using size_append. The .zst
# format has the size information available at the beginning of the file too,
# but it's in a more complex format and it's good to avoid changing the part
# of the boot code that reads the uncompressed size.
# Note that the bytes added by size_append will make the zstd tool think that
# the file is corrupt. This is expected.

quiet_cmd_zstd = ZSTD    $@
cmd_zstd = (cat $(filter-out FORCE,$^) | \
	zstd -19 && \
        $(call size_append, $(filter-out FORCE,$^))) > $@ || \
	(rm -f $@ ; false)

# ASM offsets
# ---------------------------------------------------------------------------


Lines 100-105 config RD_LZ4 Link Here

(-)a/usr/Kconfig (+20 lines)
100	Support loading of a LZ4 encoded initial ramdisk or cpio buffer	100	Support loading of a LZ4 encoded initial ramdisk or cpio buffer
101	If unsure, say N.	101	If unsure, say N.
102		102
		103	config RD_ZSTD
		104	bool "Support initial ramdisk/ramfs compressed using ZSTD"
		105	default y
		106	depends on BLK_DEV_INITRD
		107	select DECOMPRESS_ZSTD
		108	help
		109	Support loading of a ZSTD encoded initial ramdisk or cpio buffer.
		110	If unsure, say N.
		111
103	choice	112	choice
104	prompt "Built-in initramfs compression mode"	113	prompt "Built-in initramfs compression mode"
105	depends on INITRAMFS_SOURCE != ""	114	depends on INITRAMFS_SOURCE != ""
Lines 207-210 config INITRAMFS_COMPRESSION_LZ4 Link Here
207	If you choose this, keep in mind that most distros don't provide lz4	216	If you choose this, keep in mind that most distros don't provide lz4
208	by default which could cause a build failure.	217	by default which could cause a build failure.
209		218
		219	config INITRAMFS_COMPRESSION_ZSTD
		220	bool "ZSTD"
		221	depends on RD_ZSTD
		222	help
		223	ZSTD is a compression algorithm targeting intermediate compression
		224	with fast decompression speed. It will compress better than GZIP and
		225	decompress around the same speed as LZO, but slower than LZ4.
		226
		227	If you choose this, keep in mind that you may need to install the zstd
		228	tool to be able to compress the initram.
		229
210	endchoice	230	endchoice

Lines 15-20 compress-$(CONFIG_INITRAMFS_COMPRESSION_LZMA) := lzma Link Here

(-)a/usr/Makefile (+1 lines)
15	compress-$(CONFIG_INITRAMFS_COMPRESSION_XZ) := xzmisc	15	compress-$(CONFIG_INITRAMFS_COMPRESSION_XZ) := xzmisc
16	compress-$(CONFIG_INITRAMFS_COMPRESSION_LZO) := lzo	16	compress-$(CONFIG_INITRAMFS_COMPRESSION_LZO) := lzo
17	compress-$(CONFIG_INITRAMFS_COMPRESSION_LZ4) := lz4	17	compress-$(CONFIG_INITRAMFS_COMPRESSION_LZ4) := lz4
		18	compress-$(CONFIG_INITRAMFS_COMPRESSION_ZSTD) := zstd
18		19
19	obj-$(CONFIG_BLK_DEV_INITRD) := initramfs_data.o	20	obj-$(CONFIG_BLK_DEV_INITRD) := initramfs_data.o
20		21

Lines 536-543 pref_address: .quad LOAD_PHYSICAL_ADDR # preferred load addr Link Here

(-)a/arch/x86/boot/header.S (-1 / +7 lines)
536	# the size-dependent part now grows so fast.	536	# the size-dependent part now grows so fast.
537	#	537	#
538	# extra_bytes = (uncompressed_size >> 8) + 65536	538	# extra_bytes = (uncompressed_size >> 8) + 65536
		539	#
		540	# ZSTD compressed data grows by at most 3 bytes per 128K, and only has a 22
		541	# byte fixed overhead but has a maximum block size of 128K, so it needs a
		542	# larger margin.
		543	#
		544	# extra_bytes = (uncompressed_size >> 8) + 131072
539		545
540	#define ZO_z_extra_bytes ((ZO_z_output_len >> 8) + 65536)	546	#define ZO_z_extra_bytes ((ZO_z_output_len >> 8) + 131072)
541	#if ZO_z_output_len > ZO_z_input_len	547	#if ZO_z_output_len > ZO_z_input_len
542	# define ZO_z_extract_offset (ZO_z_output_len + ZO_z_extra_bytes - \	548	# define ZO_z_extract_offset (ZO_z_output_len + ZO_z_extra_bytes - \
543	ZO_z_input_len)	549	ZO_z_input_len)

Lines 786-794 Protocol: 2.08+ Link Here

(-)a/Documentation/x86/boot.rst (-3 / +3 lines)
786	uncompressed data should be determined using the standard magic	786	uncompressed data should be determined using the standard magic
787	numbers. The currently supported compression formats are gzip	787	numbers. The currently supported compression formats are gzip
788	(magic numbers 1F 8B or 1F 9E), bzip2 (magic number 42 5A), LZMA	788	(magic numbers 1F 8B or 1F 9E), bzip2 (magic number 42 5A), LZMA
789	(magic number 5D 00), XZ (magic number FD 37), and LZ4 (magic number	789	(magic number 5D 00), XZ (magic number FD 37), LZ4 (magic number
790	02 21). The uncompressed payload is currently always ELF (magic	790	02 21) and ZSTD (magic number 28 B5). The uncompressed payload is
791	number 7F 45 4C 46).	791	currently always ELF (magic number 7F 45 4C 46).
792		792
793	============ ==============	793	============ ==============
794	Field name: payload_length	794	Field name: payload_length

Lines 183-188 config X86 Link Here

(-)a/arch/x86/Kconfig (+1 lines)
183	select HAVE_KERNEL_LZMA	183	select HAVE_KERNEL_LZMA
184	select HAVE_KERNEL_LZO	184	select HAVE_KERNEL_LZO
185	select HAVE_KERNEL_XZ	185	select HAVE_KERNEL_XZ
		186	select HAVE_KERNEL_ZSTD
186	select HAVE_KPROBES	187	select HAVE_KPROBES
187	select HAVE_KPROBES_ON_FTRACE	188	select HAVE_KPROBES_ON_FTRACE
188	select HAVE_FUNCTION_ERROR_INJECTION	189	select HAVE_FUNCTION_ERROR_INJECTION

Lines 24-30 OBJECT_FILES_NON_STANDARD := y Link Here

(-)a/arch/x86/boot/compressed/Makefile (-1 / +4 lines)
24	KCOV_INSTRUMENT := n	24	KCOV_INSTRUMENT := n
25		25
26	targets := vmlinux vmlinux.bin vmlinux.bin.gz vmlinux.bin.bz2 vmlinux.bin.lzma \	26	targets := vmlinux vmlinux.bin vmlinux.bin.gz vmlinux.bin.bz2 vmlinux.bin.lzma \
27	vmlinux.bin.xz vmlinux.bin.lzo vmlinux.bin.lz4	27	vmlinux.bin.xz vmlinux.bin.lzo vmlinux.bin.lz4 vmlinux.bin.zst
28		28
29	KBUILD_CFLAGS := -m$(BITS) -O2	29	KBUILD_CFLAGS := -m$(BITS) -O2
30	KBUILD_CFLAGS += -fno-strict-aliasing $(call cc-option, -fPIE, -fPIC)	30	KBUILD_CFLAGS += -fno-strict-aliasing $(call cc-option, -fPIE, -fPIC)
Lines 145-150 $(obj)/vmlinux.bin.lzo: $(vmlinux.bin.all-y) FORCE Link Here
145	$(call if_changed,lzo)	145	$(call if_changed,lzo)
146	$(obj)/vmlinux.bin.lz4: $(vmlinux.bin.all-y) FORCE	146	$(obj)/vmlinux.bin.lz4: $(vmlinux.bin.all-y) FORCE
147	$(call if_changed,lz4)	147	$(call if_changed,lz4)
		148	$(obj)/vmlinux.bin.zst: $(vmlinux.bin.all-y) FORCE
		149	$(call if_changed,zstd)
148		150
149	suffix-$(CONFIG_KERNEL_GZIP) := gz	151	suffix-$(CONFIG_KERNEL_GZIP) := gz
150	suffix-$(CONFIG_KERNEL_BZIP2) := bz2	152	suffix-$(CONFIG_KERNEL_BZIP2) := bz2
Lines 152-157 suffix-$(CONFIG_KERNEL_LZMA) := lzma Link Here
152	suffix-$(CONFIG_KERNEL_XZ) := xz	154	suffix-$(CONFIG_KERNEL_XZ) := xz
153	suffix-$(CONFIG_KERNEL_LZO) := lzo	155	suffix-$(CONFIG_KERNEL_LZO) := lzo
154	suffix-$(CONFIG_KERNEL_LZ4) := lz4	156	suffix-$(CONFIG_KERNEL_LZ4) := lz4
		157	suffix-$(CONFIG_KERNEL_ZSTD) := zst
155		158
156	quiet_cmd_mkpiggy = MKPIGGY $@	159	quiet_cmd_mkpiggy = MKPIGGY $@
157	cmd_mkpiggy = $(obj)/mkpiggy $< > $@	160	cmd_mkpiggy = $(obj)/mkpiggy $< > $@

Lines 77-82 static int lines, cols; Link Here

(-)a/arch/x86/boot/compressed/misc.c (+4 lines)
77	#ifdef CONFIG_KERNEL_LZ4	77	#ifdef CONFIG_KERNEL_LZ4
78	#include "../../../../lib/decompress_unlz4.c"	78	#include "../../../../lib/decompress_unlz4.c"
79	#endif	79	#endif
		80
		81	#ifdef CONFIG_KERNEL_ZSTD
		82	#include "../../../../lib/decompress_unzstd.c"
		83	#endif
80	/*	84	/*
81	* NOTE: When adding a new decompressor, please update the analysis in	85	* NOTE: When adding a new decompressor, please update the analysis in
82	* ../header.S.	86	* ../header.S.

Lines 24-32 Link Here

(-)a/arch/x86/include/asm/boot.h (-2 / +4 lines)
24	# error "Invalid value for CONFIG_PHYSICAL_ALIGN"	24	# error "Invalid value for CONFIG_PHYSICAL_ALIGN"
25	#endif	25	#endif
26		26
27	#ifdef CONFIG_KERNEL_BZIP2	27	#if defined(CONFIG_KERNEL_BZIP2)
28	# define BOOT_HEAP_SIZE 0x400000	28	# define BOOT_HEAP_SIZE 0x400000
29	#else /* !CONFIG_KERNEL_BZIP2 */	29	#elif defined(CONFIG_KERNEL_ZSTD)
		30	# define BOOT_HEAP_SIZE 0x30000
		31	#else
30	# define BOOT_HEAP_SIZE 0x10000	32	# define BOOT_HEAP_SIZE 0x10000
31	#endif	33	#endif
32		34

Lines 43-48 Link Here

(-)a/.gitignore (+1 lines)
43	*.tab.[ch]	43	*.tab.[ch]
44	*.tar	44	*.tar
45	*.xz	45	*.xz
		46	*.zst
46	Module.symvers	47	Module.symvers
47	modules.builtin	48	modules.builtin
48	modules.order	49	modules.order

Return to bug 716520

Lines 394-399 quiet_cmd_xzkern = XZKERN $@ Link Here

(-)a/scripts/Makefile.lib (+15 lines)
394	quiet_cmd_xzmisc = XZMISC $@	394	quiet_cmd_xzmisc = XZMISC $@
395	cmd_xzmisc = cat $(real-prereqs) \| xz --check=crc32 --lzma2=dict=1MiB > $@	395	cmd_xzmisc = cat $(real-prereqs) \| xz --check=crc32 --lzma2=dict=1MiB > $@
396		396
		397	# ZSTD
		398	# ---------------------------------------------------------------------------
		399	# Appends the uncompressed size of the data using size_append. The .zst
		400	# format has the size information available at the beginning of the file too,
		401	# but it's in a more complex format and it's good to avoid changing the part
		402	# of the boot code that reads the uncompressed size.
		403	# Note that the bytes added by size_append will make the zstd tool think that
		404	# the file is corrupt. This is expected.
		405
		406	quiet_cmd_zstd = ZSTD $@
		407	cmd_zstd = (cat $(filter-out FORCE,$^) \| \
		408	zstd -19 && \
		409	$(call size_append, $(filter-out FORCE,$^))) > $@ \|\| \
		410	(rm -f $@ ; false)
		411
397	# ASM offsets	412	# ASM offsets
398	# ---------------------------------------------------------------------------	413	# ---------------------------------------------------------------------------
399		414

Lines 80-92 void xxh32_copy_state(struct xxh32_state dst, const struct xxh32_state src) Link Here

(-)a/lib/xxhash.c (-9 / +12 lines)
80	{	80	{
81	memcpy(dst, src, sizeof(*dst));	81	memcpy(dst, src, sizeof(*dst));
82	}	82	}
83	EXPORT_SYMBOL(xxh32_copy_state);
84		83
85	void xxh64_copy_state(struct xxh64_state dst, const struct xxh64_state src)	84	void xxh64_copy_state(struct xxh64_state dst, const struct xxh64_state src)
86	{	85	{
87	memcpy(dst, src, sizeof(*dst));	86	memcpy(dst, src, sizeof(*dst));
88	}	87	}
89	EXPORT_SYMBOL(xxh64_copy_state);
90		88
91	/-**************************	89	/-**************************
92	* Simple Hash Functions	90	* Simple Hash Functions
Lines 151-157 uint32_t xxh32(const void *input, const size_t len, const uint32_t seed) Link Here
151		149
152	return h32;	150	return h32;
153	}	151	}
154	EXPORT_SYMBOL(xxh32);
155		152
156	static uint64_t xxh64_round(uint64_t acc, const uint64_t input)	153	static uint64_t xxh64_round(uint64_t acc, const uint64_t input)
157	{	154	{
Lines 234-240 uint64_t xxh64(const void *input, const size_t len, const uint64_t seed) Link Here
234		231
235	return h64;	232	return h64;
236	}	233	}
237	EXPORT_SYMBOL(xxh64);
238		234
239	/-*************************************************	235	/-*************************************************
240	* Advanced Hash Functions	236	* Advanced Hash Functions
Lines 251-257 void xxh32_reset(struct xxh32_state *statePtr, const uint32_t seed) Link Here
251	state.v4 = seed - PRIME32_1;	247	state.v4 = seed - PRIME32_1;
252	memcpy(statePtr, &state, sizeof(state));	248	memcpy(statePtr, &state, sizeof(state));
253	}	249	}
254	EXPORT_SYMBOL(xxh32_reset);
255		250
256	void xxh64_reset(struct xxh64_state *statePtr, const uint64_t seed)	251	void xxh64_reset(struct xxh64_state *statePtr, const uint64_t seed)
257	{	252	{
Lines 265-271 void xxh64_reset(struct xxh64_state *statePtr, const uint64_t seed) Link Here
265	state.v4 = seed - PRIME64_1;	260	state.v4 = seed - PRIME64_1;
266	memcpy(statePtr, &state, sizeof(state));	261	memcpy(statePtr, &state, sizeof(state));
267	}	262	}
268	EXPORT_SYMBOL(xxh64_reset);
269		263
270	int xxh32_update(struct xxh32_state state, const void input, const size_t len)	264	int xxh32_update(struct xxh32_state state, const void input, const size_t len)
271	{	265	{
Lines 334-340 int xxh32_update(struct xxh32_state state, const void input, const size_t len) Link Here
334		328
335	return 0;	329	return 0;
336	}	330	}
337	EXPORT_SYMBOL(xxh32_update);
338		331
339	uint32_t xxh32_digest(const struct xxh32_state *state)	332	uint32_t xxh32_digest(const struct xxh32_state *state)
340	{	333	{
Lines 372-378 uint32_t xxh32_digest(const struct xxh32_state *state) Link Here
372		365
373	return h32;	366	return h32;
374	}	367	}
375	EXPORT_SYMBOL(xxh32_digest);
376		368
377	int xxh64_update(struct xxh64_state state, const void input, const size_t len)	369	int xxh64_update(struct xxh64_state state, const void input, const size_t len)
378	{	370	{
Lines 439-445 int xxh64_update(struct xxh64_state state, const void input, const size_t len) Link Here
439		431
440	return 0;	432	return 0;
441	}	433	}
442	EXPORT_SYMBOL(xxh64_update);
443		434
444	uint64_t xxh64_digest(const struct xxh64_state *state)	435	uint64_t xxh64_digest(const struct xxh64_state *state)
445	{	436	{
Lines 494-500 uint64_t xxh64_digest(const struct xxh64_state *state) Link Here
494		485
495	return h64;	486	return h64;
496	}	487	}
		488
		489	#ifndef XXH_PREBOOT
		490	EXPORT_SYMBOL(xxh32_copy_state);
		491	EXPORT_SYMBOL(xxh64_copy_state);
		492	EXPORT_SYMBOL(xxh32);
		493	EXPORT_SYMBOL(xxh64);
		494	EXPORT_SYMBOL(xxh32_reset);
		495	EXPORT_SYMBOL(xxh64_reset);
		496	EXPORT_SYMBOL(xxh32_update);
		497	EXPORT_SYMBOL(xxh32_digest);
		498	EXPORT_SYMBOL(xxh64_update);
497	EXPORT_SYMBOL(xxh64_digest);	499	EXPORT_SYMBOL(xxh64_digest);
498		500
499	MODULE_LICENSE("Dual BSD/GPL");	501	MODULE_LICENSE("Dual BSD/GPL");
500	MODULE_DESCRIPTION("xxHash");	502	MODULE_DESCRIPTION("xxHash");
		503	#endif

Line 0 Link Here

(-)a/lib/decompress_unzstd.c (+342 lines)
		1	// SPDX-License-Identifier: GPL-2.0
		2
		3	/*
		4	* Important notes about in-place decompression
		5	*
		6	* At least on x86, the kernel is decompressed in place: the compressed data
		7	* is placed to the end of the output buffer, and the decompressor overwrites
		8	* most of the compressed data. There must be enough safety margin to
		9	* guarantee that the write position is always behind the read position.
		10	*
		11	* The safety margin for ZSTD with a 128 KB block size is calculated below.
		12	* Note that the margin with ZSTD is bigger than with GZIP or XZ!
		13	*
		14	* The worst case for in-place decompression is that the beginning of
		15	* the file is compressed extremely well, and the rest of the file is
		16	* uncompressible. Thus, we must look for worst-case expansion when the
		17	* compressor is encoding uncompressible data.
		18	*
		19	* The structure of the .zst file in case of a compresed kernel is as follows.
		20	* Maximum sizes (as bytes) of the fields are in parenthesis.
		21	*
		22	* Frame Header: (18)
		23	* Blocks: (N)
		24	* Checksum: (4)
		25	*
		26	* The frame header and checksum overhead is at most 22 bytes.
		27	*
		28	* ZSTD stores the data in blocks. Each block has a header whose size is
		29	* a 3 bytes. After the block header, there is up to 128 KB of payload.
		30	* The maximum uncompressed size of the payload is 128 KB. The minimum
		31	* uncompressed size of the payload is never less than the payload size
		32	* (excluding the block header).
		33	*
		34	* The assumption, that the uncompressed size of the payload is never
		35	* smaller than the payload itself, is valid only when talking about
		36	* the payload as a whole. It is possible that the payload has parts where
		37	* the decompressor consumes more input than it produces output. Calculating
		38	* the worst case for this would be tricky. Instead of trying to do that,
		39	* let's simply make sure that the decompressor never overwrites any bytes
		40	* of the payload which it is currently reading.
		41	*
		42	* Now we have enough information to calculate the safety margin. We need
		43	* - 22 bytes for the .zst file format headers;
		44	* - 3 bytes per every 128 KiB of uncompressed size (one block header per
		45	* block); and
		46	* - 128 KiB (biggest possible zstd block size) to make sure that the
		47	* decompressor never overwrites anything from the block it is currently
		48	* reading.
		49	*
		50	* We get the following formula:
		51	*
		52	* safety_margin = 22 + uncompressed_size * 3 / 131072 + 131072
		53	* <= 22 + (uncompressed_size >> 15) + 131072
		54	*/
		55
		56	/*
		57	* Preboot environments #include "path/to/decompress_unzstd.c".
		58	* All of the source files we depend on must be #included.
		59	* zstd's only source dependeny is xxhash, which has no source
		60	* dependencies.
		61	*
		62	* zstd and xxhash avoid declaring themselves as modules
		63	* when ZSTD_PREBOOT and XXH_PREBOOT are defined.
		64	*/
65	#ifdef STATIC
66	# define ZSTD_PREBOOT
67	# define XXH_PREBOOT
68	# include "xxhash.c"
69	# include "zstd/entropy_common.c"
70	# include "zstd/fse_decompress.c"
71	# include "zstd/huf_decompress.c"
72	# include "zstd/zstd_common.c"
73	# include "zstd/decompress.c"
74	#endif
75
76	#include <linux/decompress/mm.h>
77	#include <linux/kernel.h>
78	#include <linux/zstd.h>
79
80	/* 128MB is the maximum window size supported by zstd. */
81	#define ZSTD_WINDOWSIZE_MAX (1 << ZSTD_WINDOWLOG_MAX)
82	/* Size of the input and output buffers in multi-call mode.
83	* Pick a larger size because it isn't used during kernel decompression,
84	* since that is single pass, and we have to allocate a large buffer for
85	* zstd's window anyways. The larger size speeds up initramfs decompression.
86	*/
87	#define ZSTD_IOBUF_SIZE (1 << 17)
88
89	static int INIT handle_zstd_error(size_t ret, void (error)(char x))
90	{
91	const int err = ZSTD_getErrorCode(ret);
92
93	if (!ZSTD_isError(ret))
94	return 0;
95
96	switch (err) {
97	case ZSTD_error_memory_allocation:
98	error("ZSTD decompressor ran out of memory");
99	break;
100	case ZSTD_error_prefix_unknown:
101	error("Input is not in the ZSTD format (wrong magic bytes)");
102	break;
103	case ZSTD_error_dstSize_tooSmall:
104	case ZSTD_error_corruption_detected:
105	case ZSTD_error_checksum_wrong:
106	error("ZSTD-compressed data is corrupt");
107	break;
108	default:
109	error("ZSTD-compressed data is probably corrupt");
110	break;
111	}
112	return -1;
113	}
114
115	/*
116	* Handle the case where we have the entire input and output in one segment.
117	* We can allocate less memory (no circular buffer for the sliding window),
118	* and avoid some memcpy() calls.
119	*/
120	static int INIT decompress_single(const u8 in_buf, long in_len, u8 out_buf,
121	long out_len, long *in_pos,
122	void (error)(char x))
123	{
124	const size_t wksp_size = ZSTD_DCtxWorkspaceBound();
125	void *wksp = large_malloc(wksp_size);
126	ZSTD_DCtx *dctx = ZSTD_initDCtx(wksp, wksp_size);
127	int err;
128	size_t ret;
129
130	if (dctx == NULL) {
131	error("Out of memory while allocating ZSTD_DCtx");
132	err = -1;
133	goto out;
134	}
135	/*
136	* Find out how large the frame actually is, there may be junk at
137	* the end of the frame that ZSTD_decompressDCtx() can't handle.
138	*/
139	ret = ZSTD_findFrameCompressedSize(in_buf, in_len);
140	err = handle_zstd_error(ret, error);
141	if (err)
142	goto out;
143	in_len = (long)ret;
144
145	ret = ZSTD_decompressDCtx(dctx, out_buf, out_len, in_buf, in_len);
146	err = handle_zstd_error(ret, error);
147	if (err)
148	goto out;
149
150	if (in_pos != NULL)
151	*in_pos = in_len;
152
153	err = 0;
154	out:
155	if (wksp != NULL)
156	large_free(wksp);
157	return err;
158	}
159
160	static int INIT __unzstd(unsigned char *in_buf, long in_len,
161	long (fill)(void, unsigned long),
162	long (flush)(void, unsigned long),
163	unsigned char *out_buf, long out_len,
164	long *in_pos,
165	void (error)(char x))
166	{
167	ZSTD_inBuffer in;
168	ZSTD_outBuffer out;
169	ZSTD_frameParams params;
170	void *in_allocated = NULL;
171	void *out_allocated = NULL;
172	void *wksp = NULL;
173	size_t wksp_size;
174	ZSTD_DStream *dstream;
175	int err;
176	size_t ret;
177
178	if (out_len == 0)
179	out_len = LONG_MAX; /* no limit */
180
181	if (fill == NULL && flush == NULL)
182	/*
183	* We can decompress faster and with less memory when we have a
184	* single chunk.
185	*/
186	return decompress_single(in_buf, in_len, out_buf, out_len,
187	in_pos, error);
188
189	/*
190	* If in_buf is not provided, we must be using fill(), so allocate
191	* a large enough buffer. If it is provided, it must be at least
192	* ZSTD_IOBUF_SIZE large.
193	*/
194	if (in_buf == NULL) {
195	in_allocated = large_malloc(ZSTD_IOBUF_SIZE);
196	if (in_allocated == NULL) {
197	error("Out of memory while allocating input buffer");
198	err = -1;
199	goto out;
200	}
201	in_buf = in_allocated;
202	in_len = 0;
203	}
204	/* Read the first chunk, since we need to decode the frame header. */
205	if (fill != NULL)
206	in_len = fill(in_buf, ZSTD_IOBUF_SIZE);
207	if (in_len < 0) {
208	error("ZSTD-compressed data is truncated");
209	err = -1;
210	goto out;
211	}
212	/* Set the first non-empty input buffer. */
213	in.src = in_buf;
214	in.pos = 0;
215	in.size = in_len;
216	/* Allocate the output buffer if we are using flush(). */
217	if (flush != NULL) {
218	out_allocated = large_malloc(ZSTD_IOBUF_SIZE);
219	if (out_allocated == NULL) {
220	error("Out of memory while allocating output buffer");
221	err = -1;
222	goto out;
223	}
224	out_buf = out_allocated;
225	out_len = ZSTD_IOBUF_SIZE;
226	}
227	/* Set the output buffer. */
228	out.dst = out_buf;
229	out.pos = 0;
230	out.size = out_len;
231
232	/*
233	* We need to know the window size to allocate the ZSTD_DStream.
234	* Since we are streaming, we need to allocate a buffer for the sliding
235	* window. The window size varies from 1 KB to ZSTD_WINDOWSIZE_MAX
236	* (8 MB), so it is important to use the actual value so as not to
237	* waste memory when it is smaller.
238	*/
239	ret = ZSTD_getFrameParams(&params, in.src, in.size);
240	err = handle_zstd_error(ret, error);
241	if (err)
242	goto out;
243	if (ret != 0) {
244	error("ZSTD-compressed data has an incomplete frame header");
245	err = -1;
246	goto out;
247	}
248	if (params.windowSize > ZSTD_WINDOWSIZE_MAX) {
249	error("ZSTD-compressed data has too large a window size");
250	err = -1;
251	goto out;
252	}
253
254	/*
255	* Allocate the ZSTD_DStream now that we know how much memory is
256	* required.
257	*/
258	wksp_size = ZSTD_DStreamWorkspaceBound(params.windowSize);
259	wksp = large_malloc(wksp_size);
260	dstream = ZSTD_initDStream(params.windowSize, wksp, wksp_size);
261	if (dstream == NULL) {
262	error("Out of memory while allocating ZSTD_DStream");
263	err = -1;
264	goto out;
265	}
266
267	/*
268	* Decompression loop:
269	* Read more data if necessary (error if no more data can be read).
270	* Call the decompression function, which returns 0 when finished.
271	* Flush any data produced if using flush().
272	*/
273	if (in_pos != NULL)
274	*in_pos = 0;
275	do {
276	/*
277	* If we need to reload data, either we have fill() and can
278	* try to get more data, or we don't and the input is truncated.
279	*/
280	if (in.pos == in.size) {
281	if (in_pos != NULL)
282	*in_pos += in.pos;
283	in_len = fill ? fill(in_buf, ZSTD_IOBUF_SIZE) : -1;
284	if (in_len < 0) {
285	error("ZSTD-compressed data is truncated");
286	err = -1;
287	goto out;
288	}
289	in.pos = 0;
290	in.size = in_len;
291	}
292	/* Returns zero when the frame is complete. */
293	ret = ZSTD_decompressStream(dstream, &out, &in);
294	err = handle_zstd_error(ret, error);
295	if (err)
296	goto out;
297	/* Flush all of the data produced if using flush(). */
298	if (flush != NULL && out.pos > 0) {
299	if (out.pos != flush(out.dst, out.pos)) {
300	error("Failed to flush()");
301	err = -1;
302	goto out;
303	}
304	out.pos = 0;
305	}
306	} while (ret != 0);
307
308	if (in_pos != NULL)
309	*in_pos += in.pos;
310
311	err = 0;
312	out:
313	if (in_allocated != NULL)
314	large_free(in_allocated);
315	if (out_allocated != NULL)
316	large_free(out_allocated);
317	if (wksp != NULL)
318	large_free(wksp);
319	return err;
320	}
321
322	#ifndef ZSTD_PREBOOT
323	STATIC int INIT unzstd(unsigned char *buf, long len,
324	long (fill)(void, unsigned long),
325	long (flush)(void, unsigned long),
326	unsigned char *out_buf,
327	long *pos,
328	void (error)(char x))
329	{
330	return __unzstd(buf, len, fill, flush, out_buf, 0, pos, error);
331	}
332	#else
333	STATIC int INIT __decompress(unsigned char *buf, long len,
334	long (fill)(void, unsigned long),
335	long (flush)(void, unsigned long),
336	unsigned char *out_buf, long out_len,
337	long *pos,
338	void (error)(char x))
339	{
340	return __unzstd(buf, len, fill, flush, out_buf, out_len, pos, error);
341	}
342	#endif