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" files. This is |
5 | * based on the code from wimlib. |
6 | * |
7 | * Copyright (C) 2015 Eric Biggers |
8 | */ |
9 | |
10 | #include "decompress_common.h" |
11 | #include "lib.h" |
12 | |
13 | #define XPRESS_NUM_SYMBOLS 512 |
14 | #define XPRESS_MAX_CODEWORD_LEN 15 |
15 | #define XPRESS_MIN_MATCH_LEN 3 |
16 | |
17 | /* This value is chosen for fast decompression. */ |
18 | #define XPRESS_TABLEBITS 12 |
19 | |
20 | /* Reusable heap-allocated memory for XPRESS decompression */ |
21 | struct xpress_decompressor { |
22 | |
23 | /* The Huffman decoding table */ |
24 | u16 decode_table[(1 << XPRESS_TABLEBITS) + 2 * XPRESS_NUM_SYMBOLS]; |
25 | |
26 | /* An array that maps symbols to codeword lengths */ |
27 | u8 lens[XPRESS_NUM_SYMBOLS]; |
28 | |
29 | /* Temporary space for make_huffman_decode_table() */ |
30 | u16 working_space[2 * (1 + XPRESS_MAX_CODEWORD_LEN) + |
31 | XPRESS_NUM_SYMBOLS]; |
32 | }; |
33 | |
34 | /* |
35 | * xpress_allocate_decompressor - Allocate an XPRESS decompressor |
36 | * |
37 | * Return the pointer to the decompressor on success, or return NULL and set |
38 | * errno on failure. |
39 | */ |
40 | struct xpress_decompressor *xpress_allocate_decompressor(void) |
41 | { |
42 | return kmalloc(size: sizeof(struct xpress_decompressor), GFP_NOFS); |
43 | } |
44 | |
45 | /* |
46 | * xpress_decompress - Decompress a buffer of XPRESS-compressed data |
47 | * |
48 | * @decompressor: A decompressor that was allocated with |
49 | * xpress_allocate_decompressor() |
50 | * @compressed_data: The buffer of data to decompress |
51 | * @compressed_size: Number of bytes of compressed data |
52 | * @uncompressed_data: The buffer in which to store the decompressed data |
53 | * @uncompressed_size: The number of bytes the data decompresses into |
54 | * |
55 | * Return 0 on success, or return -1 and set errno on failure. |
56 | */ |
57 | int xpress_decompress(struct xpress_decompressor *decompressor, |
58 | const void *compressed_data, size_t compressed_size, |
59 | void *uncompressed_data, size_t uncompressed_size) |
60 | { |
61 | struct xpress_decompressor *d = decompressor; |
62 | const u8 * const in_begin = compressed_data; |
63 | u8 * const out_begin = uncompressed_data; |
64 | u8 *out_next = out_begin; |
65 | u8 * const out_end = out_begin + uncompressed_size; |
66 | struct input_bitstream is; |
67 | u32 i; |
68 | |
69 | /* Read the Huffman codeword lengths. */ |
70 | if (compressed_size < XPRESS_NUM_SYMBOLS / 2) |
71 | goto invalid; |
72 | for (i = 0; i < XPRESS_NUM_SYMBOLS / 2; i++) { |
73 | d->lens[i*2 + 0] = in_begin[i] & 0xF; |
74 | d->lens[i*2 + 1] = in_begin[i] >> 4; |
75 | } |
76 | |
77 | /* Build a decoding table for the Huffman code. */ |
78 | if (make_huffman_decode_table(decode_table: d->decode_table, XPRESS_NUM_SYMBOLS, |
79 | XPRESS_TABLEBITS, lens: d->lens, |
80 | XPRESS_MAX_CODEWORD_LEN, |
81 | working_space: d->working_space)) |
82 | goto invalid; |
83 | |
84 | /* Decode the matches and literals. */ |
85 | |
86 | init_input_bitstream(is: &is, buffer: in_begin + XPRESS_NUM_SYMBOLS / 2, |
87 | size: compressed_size - XPRESS_NUM_SYMBOLS / 2); |
88 | |
89 | while (out_next != out_end) { |
90 | u32 sym; |
91 | u32 log2_offset; |
92 | u32 length; |
93 | u32 offset; |
94 | |
95 | sym = read_huffsym(istream: &is, decode_table: d->decode_table, |
96 | XPRESS_TABLEBITS, XPRESS_MAX_CODEWORD_LEN); |
97 | if (sym < 256) { |
98 | /* Literal */ |
99 | *out_next++ = sym; |
100 | } else { |
101 | /* Match */ |
102 | length = sym & 0xf; |
103 | log2_offset = (sym >> 4) & 0xf; |
104 | |
105 | bitstream_ensure_bits(is: &is, num_bits: 16); |
106 | |
107 | offset = ((u32)1 << log2_offset) | |
108 | bitstream_pop_bits(is: &is, num_bits: log2_offset); |
109 | |
110 | if (length == 0xf) { |
111 | length += bitstream_read_byte(is: &is); |
112 | if (length == 0xf + 0xff) |
113 | length = bitstream_read_u16(is: &is); |
114 | } |
115 | length += XPRESS_MIN_MATCH_LEN; |
116 | |
117 | if (offset > (size_t)(out_next - out_begin)) |
118 | goto invalid; |
119 | |
120 | if (length > (size_t)(out_end - out_next)) |
121 | goto invalid; |
122 | |
123 | out_next = lz_copy(dst: out_next, length, offset, bufend: out_end, |
124 | XPRESS_MIN_MATCH_LEN); |
125 | } |
126 | } |
127 | return 0; |
128 | |
129 | invalid: |
130 | return -1; |
131 | } |
132 | |
133 | /* |
134 | * xpress_free_decompressor - Free an XPRESS decompressor |
135 | * |
136 | * @decompressor: A decompressor that was allocated with |
137 | * xpress_allocate_decompressor(), or NULL. |
138 | */ |
139 | void xpress_free_decompressor(struct xpress_decompressor *decompressor) |
140 | { |
141 | kfree(objp: decompressor); |
142 | } |
143 | |