1 // SPDX-License-Identifier: GPL-2.0-or-later 2 /* 3 * xpress_decompress.c - A decompressor for the XPRESS compression format 4 * (Huffman variant), which can be used in "System Compressed" (WOF) files. 5 * 6 * This is a port of the upstream wimlib "xpress_decompress.c" which uses a 7 * subtable-based Huffman decode table format. The decode table and the 8 * codeword-length array share a union since the lengths are fully consumed 9 * before the table is written. 10 * 11 * Copyright (C) 2012-2016 Eric Biggers 12 */ 13 14 #include <linux/array_size.h> 15 16 #include "decompress_common.h" 17 #include "lib.h" 18 #include "../ntfs_codec.h" 19 20 #define XPRESS_NUM_CHARS 256 21 #define XPRESS_NUM_SYMBOLS 512 22 #define XPRESS_MAX_CODEWORD_LEN 15 23 #define XPRESS_MIN_MATCH_LEN 3 24 25 /* This value is chosen for fast decompression. */ 26 #define XPRESS_TABLEBITS 11 27 28 /* Reusable heap-allocated memory for XPRESS decompression. The decode table 29 * and the codeword-length array alias each other in a union: all lengths are 30 * consumed into the working space before any decode-table entry is written. 31 */ 32 struct xpress_decompressor { 33 union { 34 DECODE_TABLE(decode_table, XPRESS_NUM_SYMBOLS, XPRESS_TABLEBITS, 35 XPRESS_MAX_CODEWORD_LEN); 36 u8 lens[XPRESS_NUM_SYMBOLS]; 37 }; 38 DECODE_TABLE_WORKING_SPACE(working_space, XPRESS_NUM_SYMBOLS, 39 XPRESS_MAX_CODEWORD_LEN); 40 } __aligned(DECODE_TABLE_ALIGNMENT); 41 42 int xpress_decompress(struct xpress_decompressor *d, 43 const void *compressed_data, size_t compressed_size, 44 void *uncompressed_data, size_t uncompressed_size) 45 { 46 const u8 *const in_begin = compressed_data; 47 u8 *const out_begin = uncompressed_data; 48 u8 *out_next = out_begin; 49 u8 *const out_end = out_begin + uncompressed_size; 50 struct input_bitstream is; 51 u32 i; 52 53 /* Read the Huffman codeword lengths (512 4-bit values packed into 256 54 * bytes). 55 */ 56 if (compressed_size < XPRESS_NUM_SYMBOLS / 2) 57 return -1; 58 for (i = 0; i < XPRESS_NUM_SYMBOLS / 2; i++) { 59 d->lens[2 * i + 0] = in_begin[i] & 0xf; 60 d->lens[2 * i + 1] = in_begin[i] >> 4; 61 } 62 63 /* Build a decoding table for the Huffman code. */ 64 if (make_huffman_decode_table(d->decode_table, XPRESS_NUM_SYMBOLS, 65 XPRESS_TABLEBITS, d->lens, 66 XPRESS_MAX_CODEWORD_LEN, 67 d->working_space, 68 ARRAY_SIZE(d->decode_table))) 69 return -1; 70 71 /* Decode the matches and literals. */ 72 init_input_bitstream(&is, in_begin + XPRESS_NUM_SYMBOLS / 2, 73 compressed_size - XPRESS_NUM_SYMBOLS / 2); 74 75 while (out_next != out_end) { 76 u32 sym; 77 u32 log2_offset; 78 u32 length; 79 u32 offset; 80 81 sym = read_huffsym(&is, d->decode_table, XPRESS_TABLEBITS, 82 XPRESS_MAX_CODEWORD_LEN); 83 if (sym < XPRESS_NUM_CHARS) { 84 /* Literal */ 85 *out_next++ = sym; 86 } else { 87 /* Match */ 88 length = sym & 0xf; 89 log2_offset = (sym >> 4) & 0xf; 90 91 bitstream_ensure_bits(&is, 16); 92 93 offset = ((u32)1 << log2_offset) | 94 bitstream_pop_bits(&is, log2_offset); 95 96 if (length == 0xf) { 97 length += bitstream_read_byte(&is); 98 if (length == 0xf + 0xff) 99 length = bitstream_read_u16(&is); 100 } 101 length += XPRESS_MIN_MATCH_LEN; 102 103 if (unlikely(lz_copy(length, offset, out_begin, out_next, 104 out_end, XPRESS_MIN_MATCH_LEN))) 105 return -1; 106 107 out_next += length; 108 } 109 } 110 return 0; 111 } 112 113 struct xpress_decompressor *xpress_allocate_decompressor(void) 114 { 115 return kmalloc_obj(struct xpress_decompressor, GFP_NOFS); 116 } 117 118 void xpress_free_decompressor(struct xpress_decompressor *d) 119 { 120 kfree(d); 121 } 122 123 static size_t xpress_scratch_size(u32 chunk_size) 124 { 125 return sizeof(struct xpress_decompressor); 126 } 127 128 static int xpress_decompress_chunk(void *scratch, const void *src, 129 size_t src_len, void *dst, size_t dst_len, 130 u32 chunk_size) 131 { 132 return xpress_decompress(scratch, src, src_len, dst, dst_len); 133 } 134 135 const struct ntfs_codec_ops ntfs_xpress4k_codec_ops = { 136 .id = NTFS_CODEC_XPRESS4K, 137 .name = "xpress4k", 138 .scratch_size = xpress_scratch_size, 139 .decompress_chunk = xpress_decompress_chunk, 140 }; 141 142 const struct ntfs_codec_ops ntfs_xpress8k_codec_ops = { 143 .id = NTFS_CODEC_XPRESS8K, 144 .name = "xpress8k", 145 .scratch_size = xpress_scratch_size, 146 .decompress_chunk = xpress_decompress_chunk, 147 }; 148 149 const struct ntfs_codec_ops ntfs_xpress16k_codec_ops = { 150 .id = NTFS_CODEC_XPRESS16K, 151 .name = "xpress16k", 152 .scratch_size = xpress_scratch_size, 153 .decompress_chunk = xpress_decompress_chunk, 154 }; 155