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