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