xpress_decompress.c

  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  */
 21struct 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 */
 40struct 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 */
 57int 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
129invalid:
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 */
139void xpress_free_decompressor(struct xpress_decompressor *decompressor)
140{
141	kfree(decompressor);
142}