fs/ntfs3/lib/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  */
  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 }