wimlib.net Git - wimlib/blob - include/wimlib/decompress.h

   1 /*
   2  * decompress.h
   3  *
   4  * Header for decompression code shared by multiple compression formats.
   5  */
   6
   7 #ifndef _WIMLIB_DECOMPRESS_H
   8 #define _WIMLIB_DECOMPRESS_H
   9
  10 #include "wimlib/assert.h"
  11 #include "wimlib/compiler.h"
  12 #include "wimlib/error.h"
  13 #include "wimlib/endianness.h"
  14 #include "wimlib/types.h"
  15
  16 /* Must be at least 32 bits. */
  17 typedef u32 input_bitbuf_t;
  18 #define INPUT_BITBUF_BITS (sizeof(input_bitbuf_t) * 8)
  19
  20 #ifndef INPUT_IDX_T_DEFINED
  21 #define INPUT_IDX_T_DEFINED
  22 typedef u32 input_idx_t;
  23 #endif
  24
  25 /* Structure to encapsulate a block of in-memory data that is being interpreted
  26  * as a stream of bits.
  27  *
  28  * This is geared specifically towards the XPRESS and LZX compression formats
  29  * with regards to the actual ordering the bits within the byte sequence.  */
  30 struct input_bitstream {
  31
  32         /* A variable of length at least 32 bits that is used to hold bits that
  33          * have been read from the stream.  The bits are ordered from high-order
  34          * to low-order, and the next bit is always the high-order bit.  */
  35         input_bitbuf_t  bitbuf;
  36
  37         /* Pointer to the next byte to be retrieved from the input. */
  38         const u8 *data;
  39
  40         /* Number of bits in @bitbuf that are valid. */
  41         unsigned bitsleft;
  42
  43         /* Number of words of data that are left.  */
  44         input_idx_t data_bytes_left;
  45 };
  46
  47 /* Initializes a bitstream to receive its input from @data. */
  48 static inline void
  49 init_input_bitstream(struct input_bitstream *istream,
  50                      const void *data, input_idx_t num_data_bytes)
  51 {
  52         istream->bitbuf          = 0;
  53         istream->bitsleft        = 0;
  54         istream->data            = data;
  55         istream->data_bytes_left = num_data_bytes;
  56 }
  57
  58 /* Ensures that the bit buffer variable for the bitstream contains @num_bits
  59  * bits, which must be 16 or fewer.
  60  *
  61  * If there are at least @num_bits bits remaining in the bitstream, 0 is
  62  * returned.  Otherwise, -1 is returned.  */
  63 static inline int
  64 bitstream_ensure_bits(struct input_bitstream *istream, unsigned num_bits)
  65 {
  66         wimlib_assert2(num_bits <= 16);
  67
  68         if (istream->bitsleft >= num_bits)
  69                 return 0;
  70
  71         if (unlikely(istream->data_bytes_left < 2))
  72                 return -1;
  73
  74         istream->bitbuf |= le16_to_cpu(*(le16*)istream->data) <<
  75                            (INPUT_BITBUF_BITS - 16 - istream->bitsleft);
  76         istream->data += 2;
  77         istream->bitsleft += 16;
  78         istream->data_bytes_left -= 2;
  79         return 0;
  80 }
  81
  82 /* Returns the next @num_bits bits in the buffer variable, which must contain at
  83  * least @num_bits bits, for the bitstream.  */
  84 static inline unsigned
  85 bitstream_peek_bits(const struct input_bitstream *istream, unsigned num_bits)
  86 {
  87         wimlib_assert2(istream->bitsleft >= num_bits);
  88
  89         if (unlikely(num_bits == 0))
  90                 return 0;
  91
  92         return istream->bitbuf >> (INPUT_BITBUF_BITS - num_bits);
  93 }
  94
  95 /* Removes @num_bits bits from the buffer variable, which must contain at least
  96  * @num_bits bits, for the bitstream.  */
  97 static inline void
  98 bitstream_remove_bits(struct input_bitstream *istream, unsigned num_bits)
  99 {
 100         wimlib_assert2(istream->bitsleft >= num_bits);
 101
 102         istream->bitbuf <<= num_bits;
 103         istream->bitsleft -= num_bits;
 104 }
 105
 106 /* Gets and removes @num_bits bits from the buffer variable, which must contain
 107  * at least @num_bits bits, for the bitstream.  */
 108 static inline unsigned
 109 bitstream_pop_bits(struct input_bitstream *istream,
 110                    unsigned num_bits)
 111 {
 112         unsigned n = bitstream_peek_bits(istream, num_bits);
 113         bitstream_remove_bits(istream, num_bits);
 114         return n;
 115 }
 116
 117 /* Reads @num_bits bits from the input bitstream.  @num_bits must be 16 or
 118  * fewer.  On success, returns 0 and returns the requested bits in @n.  If there
 119  * are fewer than @num_bits remaining in the bitstream, -1 is returned. */
 120 static inline int
 121 bitstream_read_bits(struct input_bitstream *istream,
 122                     unsigned num_bits, unsigned *n)
 123 {
 124         if (unlikely(bitstream_ensure_bits(istream, num_bits)))
 125                 return -1;
 126
 127         *n = bitstream_pop_bits(istream, num_bits);
 128         return 0;
 129 }
 130
 131 /* Return the next literal byte embedded in the bitstream, or -1 if the input
 132  * was exhausted.  */
 133 static inline int
 134 bitstream_read_byte(struct input_bitstream *istream)
 135 {
 136         if (unlikely(istream->data_bytes_left < 1))
 137                 return -1;
 138
 139         istream->data_bytes_left--;
 140         return *istream->data++;
 141 }
 142
 143 /* Reads @num_bits bits from the buffer variable for a bistream without checking
 144  * to see if that many bits are in the buffer or not.  */
 145 static inline unsigned
 146 bitstream_read_bits_nocheck(struct input_bitstream *istream, unsigned num_bits)
 147 {
 148         unsigned n = bitstream_peek_bits(istream, num_bits);
 149         bitstream_remove_bits(istream, num_bits);
 150         return n;
 151 }
 152
 153 extern int
 154 read_huffsym_near_end_of_input(struct input_bitstream *istream,
 155                                const u16 decode_table[],
 156                                const u8 lens[],
 157                                unsigned num_syms,
 158                                unsigned table_bits,
 159                                unsigned *n);
 160
 161 /* Read a Huffman-encoded symbol from a bitstream.  */
 162 static inline int
 163 read_huffsym(struct input_bitstream * restrict istream,
 164              const u16 decode_table[restrict],
 165              const u8 lens[restrict],
 166              unsigned num_syms,
 167              unsigned table_bits,
 168              unsigned *restrict n,
 169              unsigned max_codeword_len)
 170 {
 171         /* If there are fewer bits remaining in the input than the maximum
 172          * codeword length, use the slow path that has extra checks.  */
 173         if (unlikely(bitstream_ensure_bits(istream, max_codeword_len))) {
 174                 return read_huffsym_near_end_of_input(istream, decode_table,
 175                                                       lens, num_syms,
 176                                                       table_bits, n);
 177         }
 178
 179         /* Use the next table_bits of the input as an index into the
 180          * decode_table.  */
 181         u16 key_bits = bitstream_peek_bits(istream, table_bits);
 182
 183         u16 sym = decode_table[key_bits];
 184
 185         if (likely(sym < num_syms)) {
 186                 /* Fast case: The decode table directly provided the symbol.  */
 187                 bitstream_remove_bits(istream, lens[sym]);
 188         } else {
 189                 /* Slow case: The symbol took too many bits to include directly
 190                  * in the decode table, so search for it in a binary tree at the
 191                  * end of the decode table.  */
 192                 bitstream_remove_bits(istream, table_bits);
 193                 do {
 194                         key_bits = sym + bitstream_peek_bits(istream, 1);
 195                         bitstream_remove_bits(istream, 1);
 196                 } while ((sym = decode_table[key_bits]) >= num_syms);
 197         }
 198         *n = sym;
 199         return 0;
 200 }
 201
 202 extern int
 203 make_huffman_decode_table(u16 decode_table[], unsigned num_syms,
 204                           unsigned num_bits, const u8 lengths[],
 205                           unsigned max_codeword_len);
 206
 207 /* Minimum alignment for the decode_table parameter to
 208  * make_huffman_decode_table().  */
 209 #define DECODE_TABLE_ALIGNMENT 16
 210
 211 #endif /* _WIMLIB_DECOMPRESS_H */