ntfs3/lib/xpress_decompress.c

0001 // SPDX-License-Identifier: GPL-2.0-or-later
0002 /*
0003  * xpress_decompress.c - A decompressor for the XPRESS compression format
0004  * (Huffman variant), which can be used in "System Compressed" files.  This is
0005  * based on the code from wimlib.
0006  *
0007  * Copyright (C) 2015 Eric Biggers
0008  */
0009
0010 #include "decompress_common.h"
0011 #include "lib.h"
0012
0013 #define XPRESS_NUM_SYMBOLS  512
0014 #define XPRESS_MAX_CODEWORD_LEN 15
0015 #define XPRESS_MIN_MATCH_LEN    3
0016
0017 /* This value is chosen for fast decompression.  */
0018 #define XPRESS_TABLEBITS 12
0019
0020 /* Reusable heap-allocated memory for XPRESS decompression  */
0021 struct xpress_decompressor {
0022
0023     /* The Huffman decoding table  */
0024     u16 decode_table[(1 << XPRESS_TABLEBITS) + 2 * XPRESS_NUM_SYMBOLS];
0025
0026     /* An array that maps symbols to codeword lengths  */
0027     u8 lens[XPRESS_NUM_SYMBOLS];
0028
0029     /* Temporary space for make_huffman_decode_table()  */
0030     u16 working_space[2 * (1 + XPRESS_MAX_CODEWORD_LEN) +
0031               XPRESS_NUM_SYMBOLS];
0032 };
0033
0034 /*
0035  * xpress_allocate_decompressor - Allocate an XPRESS decompressor
0036  *
0037  * Return the pointer to the decompressor on success, or return NULL and set
0038  * errno on failure.
0039  */
0040 struct xpress_decompressor *xpress_allocate_decompressor(void)
0041 {
0042     return kmalloc(sizeof(struct xpress_decompressor), GFP_NOFS);
0043 }
0044
0045 /*
0046  * xpress_decompress - Decompress a buffer of XPRESS-compressed data
0047  *
0048  * @decompressor:       A decompressor that was allocated with
0049  *          xpress_allocate_decompressor()
0050  * @compressed_data:    The buffer of data to decompress
0051  * @compressed_size:    Number of bytes of compressed data
0052  * @uncompressed_data:  The buffer in which to store the decompressed data
0053  * @uncompressed_size:  The number of bytes the data decompresses into
0054  *
0055  * Return 0 on success, or return -1 and set errno on failure.
0056  */
0057 int xpress_decompress(struct xpress_decompressor *decompressor,
0058               const void *compressed_data, size_t compressed_size,
0059               void *uncompressed_data, size_t uncompressed_size)
0060 {
0061     struct xpress_decompressor *d = decompressor;
0062     const u8 * const in_begin = compressed_data;
0063     u8 * const out_begin = uncompressed_data;
0064     u8 *out_next = out_begin;
0065     u8 * const out_end = out_begin + uncompressed_size;
0066     struct input_bitstream is;
0067     u32 i;
0068
0069     /* Read the Huffman codeword lengths.  */
0070     if (compressed_size < XPRESS_NUM_SYMBOLS / 2)
0071         goto invalid;
0072     for (i = 0; i < XPRESS_NUM_SYMBOLS / 2; i++) {
0073         d->lens[i*2 + 0] = in_begin[i] & 0xF;
0074         d->lens[i*2 + 1] = in_begin[i] >> 4;
0075     }
0076
0077     /* Build a decoding table for the Huffman code.  */
0078     if (make_huffman_decode_table(d->decode_table, XPRESS_NUM_SYMBOLS,
0079                       XPRESS_TABLEBITS, d->lens,
0080                       XPRESS_MAX_CODEWORD_LEN,
0081                       d->working_space))
0082         goto invalid;
0083
0084     /* Decode the matches and literals.  */
0085
0086     init_input_bitstream(&is, in_begin + XPRESS_NUM_SYMBOLS / 2,
0087                  compressed_size - XPRESS_NUM_SYMBOLS / 2);
0088
0089     while (out_next != out_end) {
0090         u32 sym;
0091         u32 log2_offset;
0092         u32 length;
0093         u32 offset;
0094
0095         sym = read_huffsym(&is, d->decode_table,
0096                    XPRESS_TABLEBITS, XPRESS_MAX_CODEWORD_LEN);
0097         if (sym < 256) {
0098             /* Literal  */
0099             *out_next++ = sym;
0100         } else {
0101             /* Match  */
0102             length = sym & 0xf;
0103             log2_offset = (sym >> 4) & 0xf;
0104
0105             bitstream_ensure_bits(&is, 16);
0106
0107             offset = ((u32)1 << log2_offset) |
0108                  bitstream_pop_bits(&is, log2_offset);
0109
0110             if (length == 0xf) {
0111                 length += bitstream_read_byte(&is);
0112                 if (length == 0xf + 0xff)
0113                     length = bitstream_read_u16(&is);
0114             }
0115             length += XPRESS_MIN_MATCH_LEN;
0116
0117             if (offset > (size_t)(out_next - out_begin))
0118                 goto invalid;
0119
0120             if (length > (size_t)(out_end - out_next))
0121                 goto invalid;
0122
0123             out_next = lz_copy(out_next, length, offset, out_end,
0124                        XPRESS_MIN_MATCH_LEN);
0125         }
0126     }
0127     return 0;
0128
0129 invalid:
0130     return -1;
0131 }
0132
0133 /*
0134  * xpress_free_decompressor - Free an XPRESS decompressor
0135  *
0136  * @decompressor:       A decompressor that was allocated with
0137  *          xpress_allocate_decompressor(), or NULL.
0138  */
0139 void xpress_free_decompressor(struct xpress_decompressor *decompressor)
0140 {
0141     kfree(decompressor);
0142 }