cachepc-linux

Fork of AMDESE/linux with modifications for CachePC side-channel attack
git clone https://git.sinitax.com/sinitax/cachepc-linux
Log | Files | Refs | README | LICENSE | sfeed.txt

xpress_decompress.c (3964B)

      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}