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

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