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(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(d->decode_table, XPRESS_NUM_SYMBOLS, 79 XPRESS_TABLEBITS, d->lens, 80 XPRESS_MAX_CODEWORD_LEN, 81 d->working_space)) 82 goto invalid; 83 84 /* Decode the matches and literals. */ 85 86 init_input_bitstream(&is, in_begin + XPRESS_NUM_SYMBOLS / 2, 87 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(&is, 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, 16); 106 107 offset = ((u32)1 << log2_offset) | 108 bitstream_pop_bits(&is, log2_offset); 109 110 if (length == 0xf) { 111 length += bitstream_read_byte(&is); 112 if (length == 0xf + 0xff) 113 length = bitstream_read_u16(&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(out_next, length, offset, 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(decompressor); 142 } 143