ntfs: port lzx/xpress decompressors from ntfs-3g-system-compression

Port the LZX and XPRESS decompressors from the userspace
ntfs-3g-system-compression plugin (Eric Biggers,
https://github.com/ebiggers/ntfs-3g-system-compression) into the in-tree
NTFS driver under lib/, and adapt them to the kernel environment.

The upstream plugin implements WOF ("Windows Overlay Filesystem", a.k.a.
system compression / "Compact OS") decompression for the NTFS-3G FUSE
driver, and itself borrows the LZX/XPRESS decompressors that the same
author wrote for wimlib (https://wimlib.net/).  The XPRESS and LZX
formats used here are identical to those used in WIM archives.  This
commit is the kernel-side port that lets fs/ntfs/wof.c read
system-compressed files.

The library keeps the upstream subtable-based Huffman decoder (root
table + contiguous subtables decoded with MAKE_DECODE_TABLE_ENTRY()), so
long codewords only need one extra lookup instead of bit-by-bit tree
traversal.  The ntfs_codec_ops interface exported to fs/ntfs/wof.c
(ntfs_lzx32k_codec_ops and ntfs_xpress{4k,8k,16k}_codec_ops) matches
what the WOF layer expects.

Modifications made while porting from the upstream plugin:

- Replace the variable LZX window order (2^15..2^21) with a fixed
  32768-byte window, which is the only size WOF uses

- Simplify the bitstream helper:
  - bitstream_ensure_bits() now guarantees 16 valid bits instead of the
    carried-over 17-bit refill path from wimlib.  Neither LZX (max
    codeword length 16) nor XPRESS (max 15) needs more than 16 bits.

- Refactor codes to satisfy checkpatch.

Signed-off-by: Hyunchul Lee <hyc.lee@gmail.com>
Signed-off-by: Namjae Jeon <linkinjeon@kernel.org>

0 files changed, 0 insertions, 0 deletions