wimlib.net Git - wimlib/blob - src/decomp.h

   1 /*
   2  * decomp.h
   3  *
   4  * Functions useful for decompression, mainly bitstreams.
   5  */
   6
   7 #ifndef _WIMLIB_DECOMP_H
   8 #define _WIMLIB_DECOMP_H
   9
  10 #include "util.h"
  11 #include "endianness.h"
  12
  13 /* Must be at least 32 bits. */
  14 typedef unsigned long input_bitbuf_t;
  15
  16 /* Structure to provide a bitstream. */
  17 struct input_bitstream {
  18
  19         /* A variable of length at least 32 bits that is used to hold bits that
  20          * have been read from the stream.  The bits are ordered from high-order
  21          * to low-order; the next bit is always the high-order bit. */
  22         input_bitbuf_t  bitbuf;
  23
  24         /* Pointer to the next byte to be retrieved from the input. */
  25         const u8 *data;
  26
  27         /* Number of bits in @bitbuf that are valid. */
  28         uint bitsleft;
  29
  30         /* Number of words of data that are left. */
  31         uint data_bytes_left;
  32 };
  33
  34 /* Initializes a bitstream to receive its input from @data. */
  35 static inline void init_input_bitstream(struct input_bitstream *istream,
  36                                         const void *data, uint num_data_bytes)
  37 {
  38         istream->bitbuf          = 0;
  39         istream->bitsleft        = 0;
  40         istream->data            = data;
  41         istream->data_bytes_left = num_data_bytes;
  42 }
  43
  44 /* Ensures that the bit buffer contains @num_bits bits. */
  45 static inline int bitstream_ensure_bits(struct input_bitstream *istream,
  46                                          uint num_bits)
  47 {
  48         wimlib_assert(num_bits <= 16);
  49
  50         /* Unfortunately this needs to be different for the different
  51          * compression types.  LZX requires reading no more than the number of
  52          * bits needed, otherwise the end of the compressed data may be overrun.
  53          * XPRESS, on the other hand, requires that we always return with at
  54          * least 16 bits in the buffer, even if fewer are requested.  This is
  55          * important because this may change the location of a literal byte
  56          * read with bitstream_read_byte(). */
  57 #ifdef XPRESS_DECOMP
  58         while (istream->bitsleft < 16) {
  59 #else
  60         while (istream->bitsleft < num_bits) {
  61 #endif
  62                 if (istream->data_bytes_left < 2)
  63                         return 1;
  64
  65                 uint shift = sizeof(input_bitbuf_t) * 8 - 16 -
  66                              istream->bitsleft;
  67                 istream->bitbuf |= (input_bitbuf_t)le16_to_cpu(
  68                                         *(u16*)istream->data) << shift;
  69                 istream->data += 2;
  70                 istream->bitsleft += 16;
  71                 istream->data_bytes_left -= 2;
  72         }
  73         return 0;
  74 }
  75
  76 /* Returns the next @num_bits bits in the bit buffer.  It must contain at least
  77  * @num_bits bits to call this function. */
  78 static inline uint bitstream_peek_bits(const struct input_bitstream *istream,
  79                                        uint num_bits)
  80 {
  81         if (num_bits == 0)
  82                 return 0;
  83         return istream->bitbuf >> (sizeof(input_bitbuf_t) * 8 - num_bits);
  84 }
  85
  86 /* Removes @num_bits bits from the bit buffer.  It must contain at least
  87  * @num_bits bits to call this function. */
  88 static inline void bitstream_remove_bits(struct input_bitstream *istream,
  89                                          uint num_bits)
  90 {
  91         istream->bitbuf <<= num_bits;
  92         istream->bitsleft -= num_bits;
  93 }
  94
  95 /* Reads and returns @num_bits bits from the input bitstream. */
  96 static inline int bitstream_read_bits(struct input_bitstream *istream,
  97                                        uint num_bits, uint *n)
  98 {
  99         int ret;
 100         ret = bitstream_ensure_bits(istream, num_bits);
 101         if (ret != 0) {
 102                 ERROR("bitstream_read_bits(): Input buffer exhausted");
 103                 return ret;
 104         }
 105         *n = bitstream_peek_bits(istream, num_bits);
 106         bitstream_remove_bits(istream, num_bits);
 107         return 0;
 108 }
 109
 110 /* In the XPRESS format there can be literal length bytes embedded in the
 111  * compressed bitstream.  These bytes are basically separate from the bitstream,
 112  * as they come AFTER the bits that are currently in the buffer variable (based
 113  * on reading 16 bits at a time), even though the buffer variable may not be
 114  * empty.
 115  *
 116  * This function returns the next such literal length byte in the input
 117  * bitstream.  Returns -1 if we are at the end of the bitstream. */
 118 static inline int bitstream_read_byte(struct input_bitstream *istream)
 119 {
 120         wimlib_assert(istream->bitsleft < 32);
 121
 122         if (istream->data_bytes_left == 0) {
 123                 ERROR("bitstream_read_byte(): Input buffer exhausted");
 124                 return -1;
 125         }
 126         istream->data_bytes_left--;
 127         return *istream->data++;
 128 }
 129
 130 /* Reads @num_bits bits from the bit buffer without checking to see if that many
 131  * bits are in the buffer or not. */
 132 static inline uint bitstream_read_bits_nocheck(struct input_bitstream *istream,
 133                                                uint num_bits)
 134 {
 135         uint n = bitstream_peek_bits(istream, num_bits);
 136         bitstream_remove_bits(istream, num_bits);
 137         return n;
 138 }
 139
 140 /* Removes the bits that have been read into the bit buffer variable. */
 141 static inline void flush_input_bitstream(struct input_bitstream *istream)
 142 {
 143         bitstream_remove_bits(istream, istream->bitsleft);
 144         istream->bitsleft = 0;
 145         istream->bitbuf   = 0;
 146 }
 147
 148 extern int bitstream_read_bytes(struct input_bitstream *istream, size_t n,
 149                                 void *dest);
 150
 151 extern int align_input_bitstream(struct input_bitstream *istream,
 152                                  bool skip_word_if_aligned);
 153
 154 extern int read_huffsym(struct input_bitstream *stream,
 155                         const u16 decode_table[],
 156                         const u8 lengths[],
 157                         unsigned num_symbols,
 158                         unsigned table_bits,
 159                         uint *n,
 160                         unsigned max_codeword_len);
 161
 162 extern int make_huffman_decode_table(u16 decode_table[], uint num_syms,
 163                                      uint num_bits, const u8 lengths[],
 164                                      uint max_codeword_len);
 165
 166 #endif /* _WIMLIB_DECOMP_H */