Merge tag 'trace-v7.3-2' of git://git.kernel.org/pub/scm/linux/kernel/git/trace/linux-tracegrafted

Pull tracing fixes from Steven Rostedt:

 - Fix error output of boot instance creation failure

   Currently if a boot instance creation fails, instead of printing out
   the name of the instance that failed, it prints "(null)". That is
   because it prints "cur_str" that had already been processed by
   strsep(). Print the saved name instead.

   While at it, print the error code of the failure.

 - Fix use-after-free for same named historgrams

   Histograms can be named so that they can be used in multiple events.
   But if the named histogram has a variable attached, the second event
   that uses the named histogram which duplicates it and needs to free
   the original after duplication leaves the old variable in place and
   still visible. If another histogram uses than variable, it will use
   the stale one which will try to reference the freed duplicate
   histogram and crash the kernel.

   Free the duplicate variables along with the duplicated histogram
   data.

 - Check return value of kthread_run() in event self test

   The events self tests uses a kthread for testing but does not check
   if it succeeded in creating a kthread. If the kthread creation were
   to fail, the code will still try to call kthread_stop() on the error
   returned.

 - Fix race between reading trace_pipe and updating subbuffer size

   If a user is reading the trace_pipe file at the same time they update
   the ring buffer sub-buffer size, can cause the trace_pipe read to
   read stale data. Add trace_access_lock() around updating the ring
   buffer sub-buffer size.

 - Fix eventfs_inode on failure path in creation of the events directory

   In the creation of the "events" directory, if after allocating the
   eventfs_inode a failure is detected, it calls cleanup_ei() which
   calls free_ei(). The free_ei() will test if eventfs_inode being freed
   has no children. It is a bug if it does. But on the failure case of
   the creation of the "events" directory, the children lists have not
   yet been initialized and the free will trigger a warning because
   list_empty() on an uninitialized list returns false.

   Move the initialization into init_ei() where it makes more sense and
   makes sure that a created eventfs_inode has its lists initialized
   upon creation.

 - Check return value of kthread_run() in ftrace direct sample code

   The sample code that shows how to use the ftrace direct calls does
   not test the return of kthread_run() to see if it succeeds. Return a
   failure if the kthread_run() doesn't succeed.

 - Clear user events state on fork in case of alloc failure

   On fork, the child gets a pointer to the parent's user events state.
   It makes a copy of it then updates the child's pointer to it. But if
   the allocation fails, the duplication function leaves the child with
   a pointer to its parent's descriptor. When the child cleans up its
   data, it will free the parent's descriptor while the parent is still
   using it.

   In the duplication function, set the child's user_event_mm to NULL
   before testing if the allocation succeeded, and when it exits it will
   not free the parent's descriptor.

 - Fix retry exhaustion in simple ring buffer reader swap

   simple_ring_buffer_swap_reader_page() starts with retry set to 8 and
   post-decrements it only after a failed link replacement. On the final
   attempt, a successful replacement leaves retry at zero, while a
   failed replacement leaves it at -1.

   But the check for success expects the retry value to be non-zero and
   exits with an error on zero. This is the opposite result. Fix it.

 - Fail nicely when the remote swap_reader_page() returns an error

   Currently, if the swap_reader_page() of a remote buffer fails, it
   triggers a WARN_ON_ONCE() and continues normally. Instead, have it
   exit with an error and a pr_warn() print instead of a full WARNING.

* tag 'trace-v7.3-2' of git://git.kernel.org/pub/scm/linux/kernel/git/trace/linux-trace:
  ring-buffer: Stop remote reader update when page swap fails
  tracing: Fix retry exhaustion in simple ring buffer reader swap
  tracing/user_events: Clear copied tracing state before fork duplication
  samples/ftrace: Fix kthread_stop() on ERR_PTR in ftrace-direct-multi-modify
  samples/ftrace: Fix kthread_stop() on ERR_PTR in ftrace-direct-modify
  eventfs: Initialize ei->children and ei->list in init_ei()
  tracing: Fix use-after-free in trace_pipe read on sub-buffer order change
  tracing: Fix crash passing ERR_PTR to kthread_stop()
  tracing: Fix use-after-free with same-name named triggers
  tracing: Fix logged instance name on creation failure

5 files changed, 1458 insertions, 0 deletions

diff --git a/fs/ntfs/lib/decompress_common.c b/fs/ntfs/lib/decompress_common.c
new file mode 100644
index 000000000..1705face4
--- /dev/null
+++ b/fs/ntfs/lib/decompress_common.c
@@ -0,0 +1,200 @@
+// SPDX-License-Identifier: MIT
+/*
+ * decompress_common.c - Code shared by the XPRESS and LZX decompressors
+ *
+ * This is a port of the upstream wimlib "decompress_common.c" which builds
+ * subtable-based Huffman decode tables, as opposed to the older
+ * binary-tree-based format previously used in this library.  The vectorized
+ * (SSE2/AVX2) fill paths are omitted for portability in the kernel.
+ *
+ * Copyright (C) 2022 Eric Biggers
+ */
+
+#include "decompress_common.h"
+
+/* Compute the number of bits with which a subtable must be indexed for a
+ * codeword of length @codeword_len, given that the root table is indexed with
+ * @table_bits bits.
+ */
+static u32 compute_subtable_bits(u32 table_bits,
+				 u32 codeword_len, u16 len_counts[])
+{
+	u32 subtable_bits = codeword_len - table_bits;
+	s32 remainder = (s32)1 << subtable_bits;
+
+	for (;;) {
+		remainder -= len_counts[table_bits + subtable_bits];
+		if (remainder <= 0)
+			break;
+		subtable_bits++;
+		remainder <<= 1;
+	}
+	return subtable_bits;
+}
+
+/* Build the subtables for codewords longer than table_bits. */
+static int build_subtables(u16 decode_table[], u32 num_syms, u32 table_bits,
+			   u16 len_counts[], const u16 sorted_syms[], u32 sym_idx,
+			   u32 decode_table_pos, u32 decode_table_size)
+{
+	u32 subtable_pos = 1U << table_bits;
+	u32 subtable_bits = table_bits;
+	u32 subtable_prefix = (u32)-1;
+	u32 codeword_len = table_bits + 1;
+	u32 codeword = decode_table_pos << 1;
+	u32 prefix;
+	u16 entry;
+	u32 n;
+
+	for (; sym_idx < num_syms; sym_idx++) {
+		while (len_counts[codeword_len] == 0) {
+			codeword_len++;
+			codeword <<= 1;
+		}
+
+		prefix = codeword >> (codeword_len - table_bits);
+
+		if (prefix != subtable_prefix) {
+			subtable_prefix = prefix;
+			subtable_bits = compute_subtable_bits(table_bits, codeword_len,
+							      len_counts);
+			decode_table[subtable_prefix] =
+				MAKE_DECODE_TABLE_ENTRY(subtable_pos, subtable_bits);
+		}
+
+		entry = MAKE_DECODE_TABLE_ENTRY(sorted_syms[sym_idx],
+						codeword_len - table_bits);
+		n = 1U << (subtable_bits - (codeword_len - table_bits));
+
+		/* Defensive bound check: 'lens' is derived from untrusted
+		 * on-disk compressed data, and subtable growth depends on
+		 * its content.  This should never trigger for a correctly
+		 * sized DECODE_TABLE_ENOUGH() value, but turns a wrong value
+		 * into a clean decode failure instead of writing past the
+		 * caller's decode_table[].
+		 */
+		if (unlikely(subtable_pos + n > decode_table_size))
+			return -1;
+
+		do {
+			decode_table[subtable_pos++] = entry;
+		} while (--n);
+
+		len_counts[codeword_len]--;
+		codeword++;
+	}
+
+	return 0;
+}
+
+/*
+ * Given an alphabet of symbols and the length of each symbol's codeword in a
+ * canonical prefix code, build a table for quickly decoding symbols that were
+ * encoded with that code.
+ *
+ * The root table is indexed with 'table_bits' bits.  Codewords not longer than
+ * 'table_bits' are decoded directly from the root table.  Longer codewords are
+ * decoded via subtables: the corresponding root entry is a pointer (the index
+ * of the subtable plus the number of bits with which the subtable is indexed),
+ * and the subtable is indexed with the remaining bits of the codeword.
+ *
+ * Each entry stores both the symbol (high 12 bits) and the codeword length (low
+ * 4 bits), so a single lookup yields the symbol and lets the bitstream be
+ * advanced by the correct number of bits.
+ *
+ * @decode_table:  array in which to build the table (declared with
+ *		   DECODE_TABLE()).  May alias @lens.
+ * @num_syms:      number of symbols in the alphabet.
+ * @table_bits:    log2 of the number of root table entries.
+ * @lens:         array of @num_syms codeword lengths, indexed by symbol.
+ * @max_codeword_len: longest codeword length allowed for this code.
+ * @working_space: temporary array declared with DECODE_TABLE_WORKING_SPACE().
+ * @decode_table_size: number of u16 entries in @decode_table (i.e.
+ *		   ARRAY_SIZE(decode_table) at the call site).  Used only as a
+ *		   defensive bound check against @lens-dependent subtable growth.
+ *
+ * Returns 0 on success, or -1 if the lengths do not form a valid prefix code,
+ * or if building the subtables would overflow @decode_table_size entries.
+ */
+int make_huffman_decode_table(u16 decode_table[], u32 num_syms, u32 table_bits,
+			      const u8 lens[], u32 max_codeword_len,
+			      u16 working_space[], u32 decode_table_size)
+{
+	u16 *const len_counts = &working_space[0];
+	u16 *const offsets = &working_space[1 * (max_codeword_len + 1)];
+	u16 *const sorted_syms = &working_space[2 * (max_codeword_len + 1)];
+	u32 decode_table_pos = 0;
+	u32 sym_idx;
+	u32 codeword_len;
+	s32 remainder = 1;
+	void *entry_ptr = decode_table;
+	u32 len;
+	u32 sym;
+
+	/* Count how many codewords have each length, including 0. */
+	for (len = 0; len <= max_codeword_len; len++)
+		len_counts[len] = 0;
+	for (sym = 0; sym < num_syms; sym++)
+		len_counts[lens[sym]]++;
+
+	/* A codeword of length n should require a proportion of the codespace
+	 * equaling (1/2)^n.  The code is complete iff the codespace is exactly
+	 * filled by the lengths.
+	 */
+	for (len = 1; len <= max_codeword_len; len++) {
+		remainder = (remainder << 1) - len_counts[len];
+		if (unlikely(remainder < 0))
+			return -1;	/* over-subscribed */
+	}
+
+	if (remainder != 0) {
+		/* Incomplete code.  Permitted only if the code is empty. */
+		if (unlikely(remainder != (s32)(1U << max_codeword_len)))
+			return -1;
+
+		/* Empty code: zero the root table so lookups yield symbol 0
+		 * without consuming any bits.
+		 */
+		memset(decode_table, 0, sizeof(decode_table[0]) << table_bits);
+		return 0;
+	}
+
+	/* Sort the symbols primarily by increasing codeword length and
+	 * secondarily by increasing symbol value.
+	 */
+	offsets[0] = 0;
+	for (len = 0; len < max_codeword_len; len++)
+		offsets[len + 1] = offsets[len] + len_counts[len];
+	for (sym = 0; sym < num_syms; sym++)
+		sorted_syms[offsets[lens[sym]]++] = sym;
+
+	/* Fill the root table entries for codewords no longer than table_bits. */
+	sym_idx = offsets[0];
+	codeword_len = 1;
+	for (; codeword_len <= table_bits; codeword_len++) {
+		u32 stores_per_loop = 1U << (table_bits - codeword_len);
+		u32 end_sym_idx = sym_idx + len_counts[codeword_len];
+
+		for (; sym_idx < end_sym_idx; sym_idx++) {
+			u16 v = MAKE_DECODE_TABLE_ENTRY(sorted_syms[sym_idx],
+							codeword_len);
+			u32 n = stores_per_loop;
+			u16 *p = entry_ptr;
+
+			do {
+				*p++ = v;
+			} while (--n);
+			entry_ptr = p;
+		}
+	}
+	decode_table_pos = (u16 *)entry_ptr - decode_table;
+
+	/* If all symbols were processed, no subtables are required. */
+	if (sym_idx == num_syms)
+		return 0;
+
+	/* At least one subtable is required.  Process the remaining symbols. */
+	return build_subtables(decode_table, num_syms, table_bits, len_counts,
+			       sorted_syms, sym_idx, decode_table_pos,
+			       decode_table_size);
+}
diff --git a/fs/ntfs/lib/decompress_common.h b/fs/ntfs/lib/decompress_common.h
new file mode 100644
index 000000000..9bf85cd52
--- /dev/null
+++ b/fs/ntfs/lib/decompress_common.h
@@ -0,0 +1,444 @@
+/* SPDX-License-Identifier: MIT */
+/*
+ * decompress_common.h - Code shared by the XPRESS and LZX decompressors
+ *
+ * This is a port of the upstream wimlib "decompress_common.h" which uses a
+ * subtable-based Huffman decode table format, as opposed to the older
+ * binary-tree-based format previously used in this library.
+ *
+ * Copyright (C) 2022 Eric Biggers
+ */
+
+#ifndef _LINUX_NTFS_LIB_DECOMPRESS_COMMON_H
+#define _LINUX_NTFS_LIB_DECOMPRESS_COMMON_H
+
+#include <linux/compiler.h>
+#include <linux/string.h>
+#include <linux/types.h>
+#include <linux/slab.h>
+#include <linux/unaligned.h>
+
+/* "Force inline" macro (not required, but helpful for performance). */
+#define forceinline __always_inline
+
+/* Size of a machine word. */
+#define WORDBYTES	sizeof(size_t)
+#define WORDBITS	(8 * WORDBYTES)
+
+/* UNALIGNED_ACCESS_IS_FAST should be 1 if unaligned memory accesses can be
+ * performed efficiently on the target platform.
+ */
+#ifdef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS
+#  define UNALIGNED_ACCESS_IS_FAST 1
+#else
+#  define UNALIGNED_ACCESS_IS_FAST 0
+#endif
+
+/* Deprecated name kept for compatibility with the upstream source. */
+#define FAST_UNALIGNED_ACCESS	UNALIGNED_ACCESS_IS_FAST
+
+/* likely()/unlikely() are provided by <linux/compiler.h>. */
+
+/* STATIC_ASSERT() - verify the truth of an expression at compile time. */
+#define STATIC_ASSERT(expr)	((void)sizeof(char[1 - 2 * !(expr)]))
+
+/* STATIC_ASSERT_ZERO() - like STATIC_ASSERT() but evaluates to 0 so it can be
+ * used in constant expressions.
+ */
+#define STATIC_ASSERT_ZERO(expr) ((int)sizeof(char[-!(expr)]))
+
+/* Unaligned word load/store helpers. */
+static forceinline size_t load_word_unaligned(const void *p)
+{
+	size_t v;
+
+	memcpy(&v, p, sizeof(v));
+	return v;
+}
+
+static forceinline void store_word_unaligned(size_t v, void *p)
+{
+	memcpy(p, &v, sizeof(v));
+}
+
+static forceinline void copy_word_unaligned(const void *src, void *dst)
+{
+	store_word_unaligned(load_word_unaligned(src), dst);
+}
+
+static forceinline size_t repeat_u16(u16 b)
+{
+	size_t v = b;
+
+	STATIC_ASSERT(WORDBITS == 32 || WORDBITS == 64);
+	v |= v << 16;
+	v |= v << ((WORDBITS == 64) ? 32 : 0);
+	return v;
+}
+
+static forceinline size_t repeat_byte(u8 b)
+{
+	return repeat_u16(((u16)b << 8) | b);
+}
+
+/******************************************************************************/
+/*                   Input bitstream for XPRESS and LZX                       */
+/*----------------------------------------------------------------------------*/
+
+/* Structure that encapsulates a block of in-memory data being interpreted as a
+ * stream of bits, optionally with interwoven literal bytes.  Bits are assumed
+ * to be stored in little endian 16-bit coding units, with the bits ordered high
+ * to low.
+ */
+struct input_bitstream {
+	/* Bits that have been read from the input buffer.  The bits are
+	 * left-justified; the next bit is always bit 31.
+	 */
+	u32 bitbuf;
+
+	/* Number of bits currently held in @bitbuf. */
+	u32 bitsleft;
+
+	/* Pointer to the next byte to be retrieved from the input buffer. */
+	const u8 *next;
+
+	/* Pointer past the end of the input buffer. */
+	const u8 *end;
+};
+
+/* Initialize a bitstream to read from the specified input buffer. */
+static forceinline void init_input_bitstream(struct input_bitstream *is,
+					     const void *buffer, u32 size)
+{
+	is->bitbuf = 0;
+	is->bitsleft = 0;
+	is->next = buffer;
+	is->end = is->next + size;
+}
+
+/* Note: for performance reasons, the following methods don't return error
+ * codes to the caller if the input buffer is overrun.  Instead, they just
+ * assume that all overrun data is zeroes.
+ */
+
+/* Ensure the bit buffer variable for the bitstream contains at least @num_bits
+ * bits.  Following this, bitstream_peek_bits() and/or bitstream_remove_bits()
+ * may be called on the bitstream to peek or remove up to @num_bits bits.  This
+ * works for at most 16 bits, which is sufficient for LZX (max codeword length
+ * 16) and XPRESS (max codeword length 15).
+ */
+static forceinline void bitstream_ensure_bits(struct input_bitstream *is,
+					      unsigned int num_bits)
+{
+	if (is->bitsleft >= num_bits)
+		return;
+
+	if (unlikely(is->end - is->next < 2))
+		goto overflow;
+
+	is->bitbuf |= (u32)get_unaligned_le16(is->next) << (16 - is->bitsleft);
+	is->next += 2;
+	is->bitsleft += 16;
+	return;
+
+overflow:
+	is->bitsleft = 32;
+}
+
+/* Return the next @num_bits bits from the bitstream, without removing them.
+ * There must be at least @num_bits remaining in the buffer variable.
+ */
+static forceinline u32 bitstream_peek_bits(const struct input_bitstream *is,
+					   unsigned int num_bits)
+{
+	return (is->bitbuf >> 1) >> (sizeof(is->bitbuf) * 8 - num_bits - 1);
+}
+
+/* Remove @num_bits from the bitstream. */
+static forceinline void bitstream_remove_bits(struct input_bitstream *is,
+					      unsigned int num_bits)
+{
+	is->bitbuf <<= num_bits;
+	is->bitsleft -= num_bits;
+}
+
+/* Remove and return @num_bits bits from the bitstream. */
+static forceinline u32 bitstream_pop_bits(struct input_bitstream *is,
+					  unsigned int num_bits)
+{
+	u32 bits = bitstream_peek_bits(is, num_bits);
+
+	bitstream_remove_bits(is, num_bits);
+	return bits;
+}
+
+/* Read and return the next @num_bits bits from the bitstream. */
+static forceinline u32 bitstream_read_bits(struct input_bitstream *is,
+					   unsigned int num_bits)
+{
+	bitstream_ensure_bits(is, num_bits);
+	return bitstream_pop_bits(is, num_bits);
+}
+
+/* Read and return the next literal byte embedded in the bitstream. */
+static forceinline u8 bitstream_read_byte(struct input_bitstream *is)
+{
+	if (unlikely(is->end == is->next))
+		return 0;
+	return *is->next++;
+}
+
+/* Read and return the next 16-bit integer embedded in the bitstream. */
+static forceinline u16 bitstream_read_u16(struct input_bitstream *is)
+{
+	u16 v;
+
+	if (unlikely(is->end - is->next < 2))
+		return 0;
+	v = get_unaligned_le16(is->next);
+	is->next += 2;
+	return v;
+}
+
+/* Read and return the next 32-bit integer embedded in the bitstream. */
+static forceinline u32 bitstream_read_u32(struct input_bitstream *is)
+{
+	u32 v;
+
+	if (unlikely(is->end - is->next < 4))
+		return 0;
+	v = get_unaligned_le32(is->next);
+	is->next += 4;
+	return v;
+}
+
+/* Read into @dst_buffer an array of literal bytes embedded in the bitstream.
+ * Return 0 if there were enough bytes remaining in the input, otherwise -1.
+ */
+static forceinline int bitstream_read_bytes(struct input_bitstream *is,
+					    void *dst_buffer, size_t count)
+{
+	if (unlikely((size_t)(is->end - is->next) < count))
+		return -1;
+	memcpy(dst_buffer, is->next, count);
+	is->next += count;
+	return 0;
+}
+
+/* Align the input bitstream on a coding-unit boundary. */
+static forceinline void bitstream_align(struct input_bitstream *is)
+{
+	is->bitsleft = 0;
+	is->bitbuf = 0;
+}
+
+/******************************************************************************/
+/*                             Huffman decoding                               */
+/*----------------------------------------------------------------------------*/
+
+/*
+ * Required alignment for the Huffman decode tables.  We require this alignment
+ * so that we can fill the entries with word instructions without having to deal
+ * with misaligned buffers.
+ */
+#define DECODE_TABLE_ALIGNMENT 16
+
+/*
+ * Each decode table entry is 16 bits divided into two fields: 'symbol' (high 12
+ * bits) and 'length' (low 4 bits).  See the comments in decompress_common.c for
+ * the precise meaning of these fields depending on the entry type.
+ */
+#define DECODE_TABLE_SYMBOL_SHIFT  4
+#define DECODE_TABLE_MAX_SYMBOL	   ((1 << (16 - DECODE_TABLE_SYMBOL_SHIFT)) - 1)
+#define DECODE_TABLE_MAX_LENGTH    ((1 << DECODE_TABLE_SYMBOL_SHIFT) - 1)
+#define DECODE_TABLE_LENGTH_MASK   DECODE_TABLE_MAX_LENGTH
+#define MAKE_DECODE_TABLE_ENTRY(symbol, length) \
+	(((symbol) << DECODE_TABLE_SYMBOL_SHIFT) | (length))
+
+/*
+ * Read and return the next Huffman-encoded symbol from the given bitstream
+ * using the given decode table.  If the input data is exhausted, then the
+ * Huffman symbol will be decoded as if the missing bits were all zeroes.
+ */
+static forceinline unsigned int read_huffsym(struct input_bitstream *is,
+					     const u16 decode_table[],
+					     unsigned int table_bits,
+					     unsigned int max_codeword_len)
+{
+	unsigned int entry;
+	unsigned int symbol;
+	unsigned int length;
+
+	/* Preload the bitbuffer with 'max_codeword_len' bits. */
+	bitstream_ensure_bits(is, max_codeword_len);
+
+	/* Index the root table by the next 'table_bits' bits of input. */
+	entry = decode_table[bitstream_peek_bits(is, table_bits)];
+
+	/* Extract the "symbol" and "length" from the entry. */
+	symbol = entry >> DECODE_TABLE_SYMBOL_SHIFT;
+	length = entry & DECODE_TABLE_LENGTH_MASK;
+
+	/* If the codeword is longer than 'table_bits', the root entry is a
+	 * subtable pointer.  Discard the bits used to index the root table and
+	 * index the subtable by the next 'length' bits.
+	 */
+	if (max_codeword_len > table_bits &&
+	    entry >= (1U << (table_bits + DECODE_TABLE_SYMBOL_SHIFT))) {
+		bitstream_remove_bits(is, table_bits);
+		entry = decode_table[symbol + bitstream_peek_bits(is, length)];
+		symbol = entry >> DECODE_TABLE_SYMBOL_SHIFT;
+		length = entry & DECODE_TABLE_LENGTH_MASK;
+	}
+
+	/* Discard the (remaining) bits of the codeword. */
+	bitstream_remove_bits(is, length);
+
+	return symbol;
+}
+
+/*
+ * DECODE_TABLE_ENOUGH() evaluates to the maximum number of decode table
+ * entries, including all subtable entries, that may be required for decoding a
+ * given Huffman code.  It is a compile-time mapping computed by the zlib
+ * 'enough' utility.  An unknown combination produces a build error.
+ */
+#define DECODE_TABLE_ENOUGH(num_syms, table_bits, max_codeword_len) (	\
+	((num_syms) == 8 && (table_bits) == 5 && (max_codeword_len) == 7) ? 36 : \
+	((num_syms) == 8 && (table_bits) == 6 && (max_codeword_len) == 7) ? 66 : \
+	((num_syms) == 8 && (table_bits) == 7 && (max_codeword_len) == 7) ? 128 : \
+	((num_syms) == 20 && (table_bits) == 5 && (max_codeword_len) == 15) ? 1062 : \
+	((num_syms) == 20 && (table_bits) == 6 && (max_codeword_len) == 15) ? 582 : \
+	((num_syms) == 20 && (table_bits) == 7 && (max_codeword_len) == 15) ? 390 : \
+	((num_syms) == 54 && (table_bits) == 9 && (max_codeword_len) == 15) ? 618 : \
+	((num_syms) == 54 && (table_bits) == 10 && (max_codeword_len) == 15) ? 1098 : \
+	((num_syms) == 249 && (table_bits) == 9 && (max_codeword_len) == 16) ? 878 : \
+	((num_syms) == 249 && (table_bits) == 10 && (max_codeword_len) == 16) ? 1326 : \
+	((num_syms) == 249 && (table_bits) == 11 && (max_codeword_len) == 16) ? 2318 : \
+	((num_syms) == 496 && (table_bits) == 11 && (max_codeword_len) == 16) ? 2566 : \
+	((num_syms) == 256 && (table_bits) == 9 && (max_codeword_len) == 15) ? 822 : \
+	((num_syms) == 256 && (table_bits) == 10 && (max_codeword_len) == 15) ? 1302 : \
+	((num_syms) == 256 && (table_bits) == 11 && (max_codeword_len) == 15) ? 2310 : \
+	((num_syms) == 512 && (table_bits) == 10 && (max_codeword_len) == 15) ? 1558 : \
+	((num_syms) == 512 && (table_bits) == 11 && (max_codeword_len) == 15) ? 2566 : \
+	((num_syms) == 512 && (table_bits) == 12 && (max_codeword_len) == 15) ? 4606 : \
+	((num_syms) == 656 && (table_bits) == 10 && (max_codeword_len) == 16) ? 1734 : \
+	((num_syms) == 656 && (table_bits) == 11 && (max_codeword_len) == 16) ? 2726 : \
+	((num_syms) == 656 && (table_bits) == 12 && (max_codeword_len) == 16) ? 4758 : \
+	((num_syms) == 799 && (table_bits) == 9 && (max_codeword_len) == 15) ? 1366 : \
+	((num_syms) == 799 && (table_bits) == 10 && (max_codeword_len) == 15) ? 1846 : \
+	((num_syms) == 799 && (table_bits) == 11 && (max_codeword_len) == 15) ? 2854 : \
+	-1)
+
+/* Wrapper around DECODE_TABLE_ENOUGH() that does additional compile-time
+ * validation.
+ */
+#define DECODE_TABLE_SIZE(num_syms, table_bits, max_codeword_len) (	\
+	STATIC_ASSERT_ZERO((num_syms) > 0) +				\
+	STATIC_ASSERT_ZERO((table_bits) > 0) +				\
+	STATIC_ASSERT_ZERO((max_codeword_len) > 0) +			\
+	STATIC_ASSERT_ZERO((num_syms) <= 1U << (max_codeword_len)) +	\
+	STATIC_ASSERT_ZERO((table_bits) <= (max_codeword_len)) +	\
+	STATIC_ASSERT_ZERO((num_syms) - 1 <= DECODE_TABLE_MAX_SYMBOL) +	\
+	STATIC_ASSERT_ZERO((table_bits) <= DECODE_TABLE_MAX_LENGTH) +	\
+	STATIC_ASSERT_ZERO((max_codeword_len) - (table_bits) <=		\
+			   DECODE_TABLE_MAX_LENGTH) +			\
+	STATIC_ASSERT_ZERO((1U << table_bits) > (num_syms) - 1) +	\
+	STATIC_ASSERT_ZERO(DECODE_TABLE_ENOUGH(				\
+				(num_syms), (table_bits),		\
+				(max_codeword_len)) > 0) +		\
+	STATIC_ASSERT_ZERO(DECODE_TABLE_ENOUGH(				\
+				(num_syms), (table_bits),		\
+				(max_codeword_len)) - 1 <=		\
+					DECODE_TABLE_MAX_SYMBOL) +	\
+	DECODE_TABLE_ENOUGH((num_syms), (table_bits),			\
+			    (max_codeword_len))				\
+)
+
+/* Declare the decode table for a Huffman code. */
+#define DECODE_TABLE(name, num_syms, table_bits, max_codeword_len) \
+	u16 name[DECODE_TABLE_SIZE((num_syms), (table_bits),		\
+				   (max_codeword_len))]		\
+		__aligned(DECODE_TABLE_ALIGNMENT)
+
+/* Declare the temporary "working_space" array needed for building the decode
+ * table for a Huffman code.
+ */
+#define DECODE_TABLE_WORKING_SPACE(name, num_syms, max_codeword_len)	\
+	u16 name[2 * ((max_codeword_len) + 1) + (num_syms)]
+
+int make_huffman_decode_table(u16 decode_table[], u32 num_syms,
+			      u32 table_bits, const u8 lens[],
+			      u32 max_codeword_len, u16 working_space[],
+			      u32 decode_table_size);
+
+/******************************************************************************/
+/*                             LZ match copying                               */
+/*----------------------------------------------------------------------------*/
+
+/*
+ * Copy an LZ77 match of 'length' bytes from the match source at 'out_next -
+ * offset' to the match destination at 'out_next'.  The source and destination
+ * may overlap.  This handles validating the length and offset; it returns 0 if
+ * the match was valid (and was copied), otherwise -1.
+ */
+static forceinline int lz_copy(u32 length, u32 offset, u8 *out_begin,
+			       u8 *out_next, u8 *out_end, u32 min_length)
+{
+	const u8 *src;
+	u8 *end;
+
+	/* Validate the offset. */
+	if (unlikely(offset > (u32)(out_next - out_begin)))
+		return -1;
+
+	src = out_next - offset;
+
+	/* Fast path: copy a short, non-overlapping match whose end is not too
+	 * close to the end of the buffer.
+	 */
+	if (UNALIGNED_ACCESS_IS_FAST && length <= 3 * WORDBYTES &&
+	    offset >= WORDBYTES && out_end - out_next >= 3 * WORDBYTES) {
+		copy_word_unaligned(src + WORDBYTES * 0, out_next + WORDBYTES * 0);
+		copy_word_unaligned(src + WORDBYTES * 1, out_next + WORDBYTES * 1);
+		copy_word_unaligned(src + WORDBYTES * 2, out_next + WORDBYTES * 2);
+		return 0;
+	}
+
+	/* Validate the length. */
+	if (unlikely(length > (u32)(out_end - out_next)))
+		return -1;
+	end = out_next + length;
+
+	if (UNALIGNED_ACCESS_IS_FAST && likely(out_end - end >= WORDBYTES - 1)) {
+		if (offset >= WORDBYTES) {
+			do {
+				copy_word_unaligned(src, out_next);
+				src += WORDBYTES;
+				out_next += WORDBYTES;
+			} while (out_next < end);
+			return 0;
+		} else if (offset == 1) {
+			size_t v = repeat_byte(*(out_next - 1));
+
+			do {
+				store_word_unaligned(v, out_next);
+				src += WORDBYTES;
+				out_next += WORDBYTES;
+			} while (out_next < end);
+			return 0;
+		}
+	}
+
+	/* Fall back to a bytewise copy. */
+	if (min_length >= 2)
+		*out_next++ = *src++;
+	if (min_length >= 3)
+		*out_next++ = *src++;
+	do {
+		*out_next++ = *src++;
+	} while (out_next != end);
+	return 0;
+}
+
+#endif /* _LINUX_NTFS_LIB_DECOMPRESS_COMMON_H */
diff --git a/fs/ntfs/lib/lib.h b/fs/ntfs/lib/lib.h
new file mode 100644
index 000000000..a684d600f
--- /dev/null
+++ b/fs/ntfs/lib/lib.h
@@ -0,0 +1,29 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+/*
+ * lib.h - Public declarations for the LZX and XPRESS decompressors.
+ *
+ * Adapted for the linux kernel.  These are the low-level decompressor
+ * allocations; WOF (system-compressed) access goes through the
+ * ntfs_codec_ops interface declared in "../ntfs_codec.h".
+ */
+
+#ifndef _LINUX_NTFS_LIB_LIB_H
+#define _LINUX_NTFS_LIB_LIB_H
+
+#include <linux/types.h>
+
+/* globals from xpress_decompress.c */
+struct xpress_decompressor *xpress_allocate_decompressor(void);
+void xpress_free_decompressor(struct xpress_decompressor *d);
+int xpress_decompress(struct xpress_decompressor *d,
+		      const void *compressed_data, size_t compressed_size,
+		      void *uncompressed_data, size_t uncompressed_size);
+
+/* globals from lzx_decompress.c */
+struct lzx_decompressor *lzx_allocate_decompressor(void);
+void lzx_free_decompressor(struct lzx_decompressor *d);
+int lzx_decompress(struct lzx_decompressor *d, const void *compressed_data,
+		   size_t compressed_size, void *uncompressed_data,
+		   size_t uncompressed_size);
+
+#endif /* _LINUX_NTFS_LIB_LIB_H */
diff --git a/fs/ntfs/lib/lzx_decompress.c b/fs/ntfs/lib/lzx_decompress.c
new file mode 100644
index 000000000..be040dce6
--- /dev/null
+++ b/fs/ntfs/lib/lzx_decompress.c
@@ -0,0 +1,631 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/*
+ * lzx_decompress.c - A decompressor for the LZX compression format
+ *
+ * This is a port of the upstream wimlib "lzx_decompress.c" which uses a
+ * subtable-based Huffman decode table format.  The window size is fixed at
+ * 32768 bytes, which is the only size used in System-compressed (WOF) files.
+ *
+ * Copyright (C) 2012-2016 Eric Biggers
+ */
+
+#include <linux/array_size.h>
+#include <linux/bits.h>
+
+#include "decompress_common.h"
+#include "lib.h"
+#include "../ntfs_codec.h"
+
+/* Number of literal byte values. */
+#define LZX_NUM_CHARS		256
+
+/* The smallest and largest allowed match lengths. */
+#define LZX_MIN_MATCH_LEN	2
+#define LZX_MAX_MATCH_LEN	257
+
+/* Number of distinct match lengths that can be represented. */
+#define LZX_NUM_LENS		(LZX_MAX_MATCH_LEN - LZX_MIN_MATCH_LEN + 1)
+
+/* Number of match lengths for which no length symbol is required. */
+#define LZX_NUM_PRIMARY_LENS	7
+#define LZX_NUM_LEN_HEADERS	(LZX_NUM_PRIMARY_LENS + 1)
+
+/* Valid values of the 3-bit block type field. */
+#define LZX_BLOCKTYPE_VERBATIM		1
+#define LZX_BLOCKTYPE_ALIGNED		2
+#define LZX_BLOCKTYPE_UNCOMPRESSED	3
+
+/* LZX window size is fixed at 32768 bytes for System-compressed files. */
+
+/* Number of offset slots for a 32768-byte window. */
+#define LZX_NUM_OFFSET_SLOTS	30
+
+/* Number of symbols in the main code. */
+#define LZX_MAINCODE_NUM_SYMBOLS	\
+	(LZX_NUM_CHARS + (LZX_NUM_OFFSET_SLOTS * LZX_NUM_LEN_HEADERS))
+
+/* Number of symbols in the length code. */
+#define LZX_LENCODE_NUM_SYMBOLS		(LZX_NUM_LENS - LZX_NUM_PRIMARY_LENS)
+
+/* Number of symbols in the precode. */
+#define LZX_PRECODE_NUM_SYMBOLS		20
+
+/* Number of bits in which each precode codeword length is represented. */
+#define LZX_PRECODE_ELEMENT_SIZE	4
+
+/* Number of low-order bits of each match offset that are entropy-encoded in
+ * aligned offset blocks.
+ */
+#define LZX_NUM_ALIGNED_OFFSET_BITS	3
+
+/* Number of symbols in the aligned offset code. */
+#define LZX_ALIGNEDCODE_NUM_SYMBOLS	BIT(LZX_NUM_ALIGNED_OFFSET_BITS)
+
+/* Mask for the match offset bits that are entropy-encoded in aligned offset
+ * blocks.
+ */
+#define LZX_ALIGNED_OFFSET_BITMASK	(BIT(LZX_NUM_ALIGNED_OFFSET_BITS) - 1)
+
+/* Number of bits in which each aligned offset codeword length is represented. */
+#define LZX_ALIGNEDCODE_ELEMENT_SIZE	3
+
+/* The first offset slot which requires an aligned offset symbol in aligned
+ * offset blocks.
+ */
+#define LZX_MIN_ALIGNED_OFFSET_SLOT	8
+
+/* Maximum lengths (in bits) of the codewords in each Huffman code. */
+#define LZX_MAX_MAIN_CODEWORD_LEN	16
+#define LZX_MAX_LEN_CODEWORD_LEN	16
+#define LZX_MAX_PRE_CODEWORD_LEN	((1 << LZX_PRECODE_ELEMENT_SIZE) - 1)
+#define LZX_MAX_ALIGNED_CODEWORD_LEN	((1 << LZX_ALIGNEDCODE_ELEMENT_SIZE) - 1)
+
+/* For LZX-compressed blocks in WIM/system-compressed files this value is
+ * always used as the filesize parameter for the E8 call preprocessing.
+ */
+#define LZX_WIM_MAGIC_FILESIZE	12000000
+
+/* Assumed LZX block size when the encoded block size begins with a 0 bit. */
+#define LZX_DEFAULT_BLOCK_SIZE	32768
+
+/* Number of offsets in the recent (or "repeat") offsets queue. */
+#define LZX_NUM_RECENT_OFFSETS	3
+
+/* An offset of n bytes is actually encoded as (n + LZX_OFFSET_ADJUSTMENT). */
+#define LZX_OFFSET_ADJUSTMENT	(LZX_NUM_RECENT_OFFSETS - 1)
+
+/* These values are chosen for fast decompression. */
+#define LZX_MAINCODE_TABLEBITS		11
+#define LZX_LENCODE_TABLEBITS		9
+#define LZX_PRECODE_TABLEBITS		6
+#define LZX_ALIGNEDCODE_TABLEBITS	7
+
+#define LZX_READ_LENS_MAX_OVERRUN	50
+
+/* Mapping: offset slot => first match offset that uses that offset slot.
+ * The offset slots for repeat offsets map to "fake" offsets < 1.
+ */
+static const s32 lzx_offset_slot_base[LZX_NUM_OFFSET_SLOTS + 1] = {
+	-2,      -1,      0,       1,       2,       /* 0  --- 4  */
+	4,       6,       10,      14,      22,      /* 5  --- 9  */
+	30,      46,      62,      94,      126,     /* 10 --- 14 */
+	190,     254,     382,     510,     766,     /* 15 --- 19 */
+	1022,    1534,    2046,    3070,    4094,    /* 20 --- 24 */
+	6142,    8190,    12286,   16382,   24574,   /* 25 --- 29 */
+	32766,					 /* extra     */
+};
+
+/* Mapping: offset slot => how many extra bits must be read and added to the
+ * corresponding offset slot base to decode the match offset.
+ */
+static const u8 lzx_extra_offset_bits[LZX_NUM_OFFSET_SLOTS] = {
+	0,  0,  0,  0,  1,
+	1,  2,  2,  3,  3,
+	4,  4,  5,  5,  6,
+	6,  7,  7,  8,  8,
+	9,  9,  10, 10, 11,
+	11, 12, 12, 13, 13,
+};
+
+/* Like lzx_extra_offset_bits[], but with the entropy-coded aligned offset
+ * bits already subtracted.  Valid only for offset slots that may appear in
+ * aligned offset blocks.
+ */
+static const u8 lzx_extra_offset_bits_minus_aligned[LZX_NUM_OFFSET_SLOTS] = {
+	0,  0,  0,  0,  1,
+	1,  2,  2,  0,  0,
+	1,  1,  2,  2,  3,
+	3,  4,  4,  5,  5,
+	6,  6,  7,  7,  8,
+	8,  9,  9,  10, 10,
+};
+
+/* Reusable heap-allocated memory for LZX decompression.  The decode tables and
+ * their corresponding codeword length arrays are grouped in unions so the
+ * memory can be reused across phases, and the per-code working spaces share a
+ * single union since only one is needed at a time.
+ */
+struct lzx_decompressor {
+	DECODE_TABLE(maincode_decode_table, LZX_MAINCODE_NUM_SYMBOLS,
+		     LZX_MAINCODE_TABLEBITS, LZX_MAX_MAIN_CODEWORD_LEN);
+	u8 maincode_lens[LZX_MAINCODE_NUM_SYMBOLS + LZX_READ_LENS_MAX_OVERRUN];
+
+	DECODE_TABLE(lencode_decode_table, LZX_LENCODE_NUM_SYMBOLS,
+		     LZX_LENCODE_TABLEBITS, LZX_MAX_LEN_CODEWORD_LEN);
+	u8 lencode_lens[LZX_LENCODE_NUM_SYMBOLS + LZX_READ_LENS_MAX_OVERRUN];
+
+	union {
+		DECODE_TABLE(alignedcode_decode_table,
+			     LZX_ALIGNEDCODE_NUM_SYMBOLS,
+			     LZX_ALIGNEDCODE_TABLEBITS,
+			     LZX_MAX_ALIGNED_CODEWORD_LEN);
+		u8 alignedcode_lens[LZX_ALIGNEDCODE_NUM_SYMBOLS];
+	};
+
+	union {
+		DECODE_TABLE(precode_decode_table, LZX_PRECODE_NUM_SYMBOLS,
+			     LZX_PRECODE_TABLEBITS, LZX_MAX_PRE_CODEWORD_LEN);
+		u8 precode_lens[LZX_PRECODE_NUM_SYMBOLS];
+		/* extra_offset_bits[] is used as scratch in aligned blocks. */
+		u8 extra_offset_bits[LZX_NUM_OFFSET_SLOTS];
+	};
+
+	union {
+		DECODE_TABLE_WORKING_SPACE(maincode_working_space,
+					   LZX_MAINCODE_NUM_SYMBOLS,
+					   LZX_MAX_MAIN_CODEWORD_LEN);
+		DECODE_TABLE_WORKING_SPACE(lencode_working_space,
+					   LZX_LENCODE_NUM_SYMBOLS,
+					   LZX_MAX_LEN_CODEWORD_LEN);
+		DECODE_TABLE_WORKING_SPACE(alignedcode_working_space,
+					   LZX_ALIGNEDCODE_NUM_SYMBOLS,
+					   LZX_MAX_ALIGNED_CODEWORD_LEN);
+		DECODE_TABLE_WORKING_SPACE(precode_working_space,
+					   LZX_PRECODE_NUM_SYMBOLS,
+					   LZX_MAX_PRE_CODEWORD_LEN);
+	};
+} __aligned(DECODE_TABLE_ALIGNMENT);
+
+static forceinline unsigned int read_presym(const struct lzx_decompressor *d,
+					    struct input_bitstream *is)
+{
+	return read_huffsym(is, d->precode_decode_table, LZX_PRECODE_TABLEBITS,
+			    LZX_MAX_PRE_CODEWORD_LEN);
+}
+
+static forceinline unsigned int read_mainsym(const struct lzx_decompressor *d,
+					     struct input_bitstream *is)
+{
+	return read_huffsym(is, d->maincode_decode_table,
+			    LZX_MAINCODE_TABLEBITS, LZX_MAX_MAIN_CODEWORD_LEN);
+}
+
+static forceinline unsigned int read_lensym(const struct lzx_decompressor *d,
+					    struct input_bitstream *is)
+{
+	return read_huffsym(is, d->lencode_decode_table, LZX_LENCODE_TABLEBITS,
+			    LZX_MAX_LEN_CODEWORD_LEN);
+}
+
+static forceinline unsigned int
+read_alignedsym(const struct lzx_decompressor *d, struct input_bitstream *is)
+{
+	return read_huffsym(is, d->alignedcode_decode_table,
+			    LZX_ALIGNEDCODE_TABLEBITS,
+			    LZX_MAX_ALIGNED_CODEWORD_LEN);
+}
+
+/*
+ * Read a precode from the compressed bitstream, then use it to decode
+ * @num_lens codeword length values and write them to @lens.
+ */
+static int lzx_read_codeword_lens(struct lzx_decompressor *d,
+				  struct input_bitstream *is, u8 *lens,
+				  u32 num_lens)
+{
+	u8 *len_ptr = lens;
+	u8 *lens_end = lens + num_lens;
+	u32 i;
+
+	/* Read the lengths of the precode codewords.  These are stored
+	 * explicitly.
+	 */
+	for (i = 0; i < LZX_PRECODE_NUM_SYMBOLS; i++) {
+		d->precode_lens[i] =
+			bitstream_read_bits(is, LZX_PRECODE_ELEMENT_SIZE);
+	}
+
+	/* Build the decoding table for the precode. */
+	if (make_huffman_decode_table(d->precode_decode_table,
+				      LZX_PRECODE_NUM_SYMBOLS,
+				      LZX_PRECODE_TABLEBITS,
+				      d->precode_lens,
+				      LZX_MAX_PRE_CODEWORD_LEN,
+				      d->precode_working_space,
+				      ARRAY_SIZE(d->precode_decode_table)))
+		return -1;
+
+	/* Decode the codeword lengths. */
+	do {
+		u32 presym;
+		u8 len;
+
+		presym = read_presym(d, is);
+		if (presym < 17) {
+			/* Difference from old length. */
+			len = *len_ptr - presym;
+			if ((s8)len < 0)
+				len += 17;
+			*len_ptr++ = len;
+		} else {
+			/* Special RLE values. */
+			u32 run_len;
+
+			if (presym == 17) {
+				run_len = 4 + bitstream_read_bits(is, 4);
+				len = 0;
+			} else if (presym == 18) {
+				run_len = 20 + bitstream_read_bits(is, 5);
+				len = 0;
+			} else {
+				run_len = 4 + bitstream_read_bits(is, 1);
+				presym = read_presym(d, is);
+				if (unlikely(presym > 17))
+					return -1;
+				len = *len_ptr - presym;
+				if ((s8)len < 0)
+					len += 17;
+			}
+
+			do {
+				*len_ptr++ = len;
+			} while (--run_len);
+			/* The worst case overrun is when presym == 18,
+			 * run_len == 20 + 31, and only 1 length was
+			 * remaining, so LZX_READ_LENS_MAX_OVERRUN == 50.
+			 * Overrun while reading the first half of
+			 * maincode_lens can corrupt the previous values in
+			 * the second half, but the resulting lengths will
+			 * still be in range, and data that generates overruns
+			 * is invalid anyway.
+			 */
+		}
+	} while (len_ptr < lens_end);
+
+	return 0;
+}
+
+static void undo_translate_target(void *target, s32 input_pos)
+{
+	s32 abs_offset, rel_offset;
+
+	abs_offset = get_unaligned_le32(target);
+	if (abs_offset >= 0) {
+		if (abs_offset < LZX_WIM_MAGIC_FILESIZE) {
+			/* "good translation" */
+			rel_offset = abs_offset - input_pos;
+			put_unaligned_le32(rel_offset, target);
+		}
+	} else {
+		if (abs_offset >= -input_pos) {
+			/* "compensating translation" */
+			rel_offset = abs_offset + LZX_WIM_MAGIC_FILESIZE;
+			put_unaligned_le32(rel_offset, target);
+		}
+	}
+}
+
+/*
+ * Undo the 'E8' preprocessing used in LZX.  Before compression, the
+ * uncompressed data was preprocessed by changing the targets of suspected x86
+ * CALL instructions from relative offsets to absolute offsets.  After
+ * match/literal decoding, the decompressor must undo the translation.
+ *
+ * E8 preprocessing is disabled in the last 6 bytes of the data, which means
+ * the 5-byte call instruction cannot start in the last 10 bytes.  The scalar
+ * implementation below exploits this by replacing the last 6 bytes with 0xE8
+ * trap bytes, eliminating end-of-buffer checks from the inner loop.
+ */
+static void lzx_postprocess(u8 *data, u32 size)
+{
+	u8 *tail;
+	u8 saved_bytes[6];
+	u8 *p;
+
+	if (size <= 10)
+		return;
+
+	tail = &data[size - 6];
+	memcpy(saved_bytes, tail, 6);
+	memset(tail, 0xE8, 6);
+	p = data;
+	for (;;) {
+		while (*p != 0xE8)
+			p++;
+		if (p >= tail)
+			break;
+		undo_translate_target(p + 1, (s32)(p - data));
+		p += 5;
+	}
+	memcpy(tail, saved_bytes, 6);
+}
+
+static int lzx_read_block_header(struct lzx_decompressor *d,
+				 struct input_bitstream *is,
+				 u32 recent_offsets[], int *block_type_ret,
+				 u32 *block_size_ret)
+{
+	int block_type;
+	u32 block_size;
+	u32 i;
+
+	bitstream_ensure_bits(is, 4);
+
+	/* Read the block type. */
+	block_type = bitstream_pop_bits(is, 3);
+
+	/* Read the block size.  With the 32768-byte window used in system
+	 * compression, block sizes are always encoded in 16 bits.
+	 */
+	if (bitstream_pop_bits(is, 1))
+		block_size = LZX_DEFAULT_BLOCK_SIZE;
+	else
+		block_size = bitstream_read_bits(is, 16);
+
+	switch (block_type) {
+	case LZX_BLOCKTYPE_ALIGNED:
+		/* Read the aligned offset codeword lengths. */
+		for (i = 0; i < LZX_ALIGNEDCODE_NUM_SYMBOLS; i++) {
+			d->alignedcode_lens[i] =
+				bitstream_read_bits(is,
+						    LZX_ALIGNEDCODE_ELEMENT_SIZE);
+		}
+		/* Fall though, since the rest of the header for aligned offset
+		 * blocks is the same as that for verbatim blocks.
+		 */
+		fallthrough;
+
+	case LZX_BLOCKTYPE_VERBATIM:
+		/* Read the main codeword lengths, which are divided into two
+		 * parts: literal symbols and match headers.
+		 */
+		if (lzx_read_codeword_lens(d, is, d->maincode_lens,
+					   LZX_NUM_CHARS))
+			return -1;
+		if (lzx_read_codeword_lens(d, is,
+					   d->maincode_lens + LZX_NUM_CHARS,
+					   LZX_MAINCODE_NUM_SYMBOLS - LZX_NUM_CHARS))
+			return -1;
+
+		/* Read the length codeword lengths. */
+		if (lzx_read_codeword_lens(d, is, d->lencode_lens,
+					   LZX_LENCODE_NUM_SYMBOLS))
+			return -1;
+		break;
+
+	case LZX_BLOCKTYPE_UNCOMPRESSED:
+		/* The header of an uncompressed block contains new values for
+		 * the recent offsets queue, starting on the next 16-bit
+		 * boundary in the bitstream.  If the stream is *already*
+		 * aligned, the next 16 bits must be discarded.
+		 */
+		bitstream_ensure_bits(is, 1);
+		bitstream_align(is);
+		recent_offsets[0] = bitstream_read_u32(is);
+		recent_offsets[1] = bitstream_read_u32(is);
+		recent_offsets[2] = bitstream_read_u32(is);
+
+		/* Offsets of 0 are invalid. */
+		if (recent_offsets[0] == 0 || recent_offsets[1] == 0 ||
+		    recent_offsets[2] == 0)
+			return -1;
+		break;
+
+	default:
+		/* Unrecognized block type. */
+		return -1;
+	}
+
+	*block_type_ret = block_type;
+	*block_size_ret = block_size;
+	return 0;
+}
+
+static int lzx_decompress_block(struct lzx_decompressor *d,
+				struct input_bitstream *is, int block_type,
+				u32 block_size, u8 *const out_begin,
+				u8 *out_next, u32 recent_offsets[])
+{
+	u8 *const block_end = out_next + block_size;
+	unsigned int min_aligned_offset_slot;
+	const u8 *extra_offset_bits;
+
+	/* Build the Huffman decode tables.  The main and length tables are
+	 * always needed; for aligned blocks the aligned offset table is also
+	 * needed.
+	 */
+	if (make_huffman_decode_table(d->maincode_decode_table,
+				      LZX_MAINCODE_NUM_SYMBOLS,
+				      LZX_MAINCODE_TABLEBITS, d->maincode_lens,
+				      LZX_MAX_MAIN_CODEWORD_LEN,
+				      d->maincode_working_space,
+				      ARRAY_SIZE(d->maincode_decode_table)))
+		return -1;
+
+	if (make_huffman_decode_table(d->lencode_decode_table,
+				      LZX_LENCODE_NUM_SYMBOLS,
+				      LZX_LENCODE_TABLEBITS, d->lencode_lens,
+				      LZX_MAX_LEN_CODEWORD_LEN,
+				      d->lencode_working_space,
+				      ARRAY_SIZE(d->lencode_decode_table)))
+		return -1;
+
+	if (block_type == LZX_BLOCKTYPE_ALIGNED) {
+		if (make_huffman_decode_table(d->alignedcode_decode_table,
+					      LZX_ALIGNEDCODE_NUM_SYMBOLS,
+					      LZX_ALIGNEDCODE_TABLEBITS,
+					      d->alignedcode_lens,
+					      LZX_MAX_ALIGNED_CODEWORD_LEN,
+					      d->alignedcode_working_space,
+					      ARRAY_SIZE(d->alignedcode_decode_table)))
+			return -1;
+		min_aligned_offset_slot = LZX_MIN_ALIGNED_OFFSET_SLOT;
+		extra_offset_bits = lzx_extra_offset_bits_minus_aligned;
+	} else {
+		min_aligned_offset_slot = LZX_NUM_OFFSET_SLOTS;
+		extra_offset_bits = lzx_extra_offset_bits;
+	}
+
+	/* Decode the literals and matches. */
+	do {
+		unsigned int mainsym;
+		unsigned int length;
+		u32 offset;
+		unsigned int offset_slot;
+
+		mainsym = read_mainsym(d, is);
+		if (mainsym < LZX_NUM_CHARS) {
+			/* Literal */
+			*out_next++ = mainsym;
+			continue;
+		}
+
+		/* Match */
+
+		/* Decode the length header and offset slot.
+		 */
+		STATIC_ASSERT(LZX_NUM_CHARS % LZX_NUM_LEN_HEADERS == 0);
+		length = mainsym % LZX_NUM_LEN_HEADERS;
+		offset_slot = (mainsym - LZX_NUM_CHARS) / LZX_NUM_LEN_HEADERS;
+
+		/* If needed, read a length symbol to decode the full length. */
+		if (length == LZX_NUM_PRIMARY_LENS)
+			length += read_lensym(d, is);
+		length += LZX_MIN_MATCH_LEN;
+
+		if (offset_slot < LZX_NUM_RECENT_OFFSETS) {
+			/* Repeat offset.  This isn't a real LRU queue, since
+			 * using the R2 offset doesn't bump the R1 offset down
+			 * to R2.
+			 */
+			offset = recent_offsets[offset_slot];
+			recent_offsets[offset_slot] = recent_offsets[0];
+		} else {
+			/* Explicit offset. */
+			offset = bitstream_read_bits(is,
+						     extra_offset_bits[offset_slot]);
+			if (offset_slot >= min_aligned_offset_slot) {
+				offset = (offset << LZX_NUM_ALIGNED_OFFSET_BITS) |
+					 read_alignedsym(d, is);
+			}
+			offset += lzx_offset_slot_base[offset_slot];
+
+			/* Update the match offset LRU queue. */
+			STATIC_ASSERT(LZX_NUM_RECENT_OFFSETS == 3);
+			recent_offsets[2] = recent_offsets[1];
+			recent_offsets[1] = recent_offsets[0];
+		}
+		recent_offsets[0] = offset;
+
+		/* Validate the match and copy it to the current position. */
+		if (unlikely(lz_copy(length, offset, out_begin, out_next,
+				     block_end, LZX_MIN_MATCH_LEN)))
+			return -1;
+		out_next += length;
+	} while (out_next != block_end);
+
+	return 0;
+}
+
+int lzx_decompress(struct lzx_decompressor *d, const void *compressed_data,
+		   size_t compressed_size, void *uncompressed_data,
+		   size_t uncompressed_size)
+{
+	u8 *const out_begin = uncompressed_data;
+	u8 *out_next = out_begin;
+	u8 *const out_end = out_begin + uncompressed_size;
+	struct input_bitstream is;
+
+	STATIC_ASSERT(LZX_NUM_RECENT_OFFSETS == 3);
+	u32 recent_offsets[LZX_NUM_RECENT_OFFSETS] = {1, 1, 1};
+	bool may_have_e8_byte = false;
+
+	init_input_bitstream(&is, compressed_data, compressed_size);
+
+	/* Codeword lengths begin as all 0's for delta encoding purposes. */
+	memset(d->maincode_lens, 0, LZX_MAINCODE_NUM_SYMBOLS);
+	memset(d->lencode_lens, 0, LZX_LENCODE_NUM_SYMBOLS);
+
+	/* Decompress blocks until we have all the uncompressed data.
+	 */
+	while (out_next != out_end) {
+		int block_type;
+		u32 block_size;
+
+		if (lzx_read_block_header(d, &is, recent_offsets, &block_type,
+					  &block_size))
+			return -1;
+
+		if (block_size < 1 || block_size > (u32)(out_end - out_next))
+			return -1;
+
+		if (likely(block_type != LZX_BLOCKTYPE_UNCOMPRESSED)) {
+			/* Compressed block. */
+			if (lzx_decompress_block(d, &is, block_type, block_size,
+						 out_begin, out_next,
+						 recent_offsets))
+				return -1;
+
+			/* If the first E8 byte was in this block, then it
+			 * must have been encoded as a literal (mainsym E8).
+			 */
+			if (d->maincode_lens[0xE8])
+				may_have_e8_byte = true;
+		} else {
+			/* Uncompressed block. */
+			if (bitstream_read_bytes(&is, out_next, block_size))
+				return -1;
+			if (block_size & 1)
+				bitstream_read_byte(&is);
+			/* There may have been an E8 byte in the block. */
+			may_have_e8_byte = true;
+		}
+		out_next += block_size;
+	}
+
+	/* Postprocess the data unless it cannot possibly contain E8 bytes. */
+	if (may_have_e8_byte)
+		lzx_postprocess(uncompressed_data, uncompressed_size);
+
+	return 0;
+}
+
+struct lzx_decompressor *lzx_allocate_decompressor(void)
+{
+	return kmalloc_obj(struct lzx_decompressor, GFP_NOFS);
+}
+
+void lzx_free_decompressor(struct lzx_decompressor *d)
+{
+	kfree(d);
+}
+
+static size_t lzx_scratch_size(u32 chunk_size)
+{
+	return sizeof(struct lzx_decompressor);
+}
+
+static int lzx_decompress_chunk(void *scratch, const void *src, size_t src_len,
+				void *dst, size_t dst_len, u32 chunk_size)
+{
+	struct lzx_decompressor *d = scratch;
+
+	return lzx_decompress(d, src, src_len, dst, dst_len);
+}
+
+const struct ntfs_codec_ops ntfs_lzx32k_codec_ops = {
+	.id = NTFS_CODEC_LZX32K,
+	.name = "lzx32k",
+	.scratch_size = lzx_scratch_size,
+	.decompress_chunk = lzx_decompress_chunk,
+};
diff --git a/fs/ntfs/lib/xpress_decompress.c b/fs/ntfs/lib/xpress_decompress.c
new file mode 100644
index 000000000..cb2125432
--- /dev/null
+++ b/fs/ntfs/lib/xpress_decompress.c
@@ -0,0 +1,154 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/*
+ * xpress_decompress.c - A decompressor for the XPRESS compression format
+ * (Huffman variant), which can be used in "System Compressed" (WOF) files.
+ *
+ * This is a port of the upstream wimlib "xpress_decompress.c" which uses a
+ * subtable-based Huffman decode table format.  The decode table and the
+ * codeword-length array share a union since the lengths are fully consumed
+ * before the table is written.
+ *
+ * Copyright (C) 2012-2016 Eric Biggers
+ */
+
+#include <linux/array_size.h>
+
+#include "decompress_common.h"
+#include "lib.h"
+#include "../ntfs_codec.h"
+
+#define XPRESS_NUM_CHARS	256
+#define XPRESS_NUM_SYMBOLS	512
+#define XPRESS_MAX_CODEWORD_LEN	15
+#define XPRESS_MIN_MATCH_LEN	3
+
+/* This value is chosen for fast decompression. */
+#define XPRESS_TABLEBITS	11
+
+/* Reusable heap-allocated memory for XPRESS decompression.  The decode table
+ * and the codeword-length array alias each other in a union: all lengths are
+ * consumed into the working space before any decode-table entry is written.
+ */
+struct xpress_decompressor {
+	union {
+		DECODE_TABLE(decode_table, XPRESS_NUM_SYMBOLS, XPRESS_TABLEBITS,
+			     XPRESS_MAX_CODEWORD_LEN);
+		u8 lens[XPRESS_NUM_SYMBOLS];
+	};
+	DECODE_TABLE_WORKING_SPACE(working_space, XPRESS_NUM_SYMBOLS,
+				   XPRESS_MAX_CODEWORD_LEN);
+} __aligned(DECODE_TABLE_ALIGNMENT);
+
+int xpress_decompress(struct xpress_decompressor *d,
+		      const void *compressed_data, size_t compressed_size,
+		      void *uncompressed_data, size_t uncompressed_size)
+{
+	const u8 *const in_begin = compressed_data;
+	u8 *const out_begin = uncompressed_data;
+	u8 *out_next = out_begin;
+	u8 *const out_end = out_begin + uncompressed_size;
+	struct input_bitstream is;
+	u32 i;
+
+	/* Read the Huffman codeword lengths (512 4-bit values packed into 256
+	 * bytes).
+	 */
+	if (compressed_size < XPRESS_NUM_SYMBOLS / 2)
+		return -1;
+	for (i = 0; i < XPRESS_NUM_SYMBOLS / 2; i++) {
+		d->lens[2 * i + 0] = in_begin[i] & 0xf;
+		d->lens[2 * i + 1] = in_begin[i] >> 4;
+	}
+
+	/* Build a decoding table for the Huffman code. */
+	if (make_huffman_decode_table(d->decode_table, XPRESS_NUM_SYMBOLS,
+				      XPRESS_TABLEBITS, d->lens,
+				      XPRESS_MAX_CODEWORD_LEN,
+				      d->working_space,
+				      ARRAY_SIZE(d->decode_table)))
+		return -1;
+
+	/* Decode the matches and literals. */
+	init_input_bitstream(&is, in_begin + XPRESS_NUM_SYMBOLS / 2,
+			     compressed_size - XPRESS_NUM_SYMBOLS / 2);
+
+	while (out_next != out_end) {
+		u32 sym;
+		u32 log2_offset;
+		u32 length;
+		u32 offset;
+
+		sym = read_huffsym(&is, d->decode_table, XPRESS_TABLEBITS,
+				   XPRESS_MAX_CODEWORD_LEN);
+		if (sym < XPRESS_NUM_CHARS) {
+			/* Literal */
+			*out_next++ = sym;
+		} else {
+			/* Match */
+			length = sym & 0xf;
+			log2_offset = (sym >> 4) & 0xf;
+
+			bitstream_ensure_bits(&is, 16);
+
+			offset = ((u32)1 << log2_offset) |
+				 bitstream_pop_bits(&is, log2_offset);
+
+			if (length == 0xf) {
+				length += bitstream_read_byte(&is);
+				if (length == 0xf + 0xff)
+					length = bitstream_read_u16(&is);
+			}
+			length += XPRESS_MIN_MATCH_LEN;
+
+			if (unlikely(lz_copy(length, offset, out_begin, out_next,
+					     out_end, XPRESS_MIN_MATCH_LEN)))
+				return -1;
+
+			out_next += length;
+		}
+	}
+	return 0;
+}
+
+struct xpress_decompressor *xpress_allocate_decompressor(void)
+{
+	return kmalloc_obj(struct xpress_decompressor, GFP_NOFS);
+}
+
+void xpress_free_decompressor(struct xpress_decompressor *d)
+{
+	kfree(d);
+}
+
+static size_t xpress_scratch_size(u32 chunk_size)
+{
+	return sizeof(struct xpress_decompressor);
+}
+
+static int xpress_decompress_chunk(void *scratch, const void *src,
+				   size_t src_len, void *dst, size_t dst_len,
+				   u32 chunk_size)
+{
+	return xpress_decompress(scratch, src, src_len, dst, dst_len);
+}
+
+const struct ntfs_codec_ops ntfs_xpress4k_codec_ops = {
+	.id = NTFS_CODEC_XPRESS4K,
+	.name = "xpress4k",
+	.scratch_size = xpress_scratch_size,
+	.decompress_chunk = xpress_decompress_chunk,
+};
+
+const struct ntfs_codec_ops ntfs_xpress8k_codec_ops = {
+	.id = NTFS_CODEC_XPRESS8K,
+	.name = "xpress8k",
+	.scratch_size = xpress_scratch_size,
+	.decompress_chunk = xpress_decompress_chunk,
+};
+
+const struct ntfs_codec_ops ntfs_xpress16k_codec_ops = {
+	.id = NTFS_CODEC_XPRESS16K,
+	.name = "xpress16k",
+	.scratch_size = xpress_scratch_size,
+	.decompress_chunk = xpress_decompress_chunk,
+};