bitstream_read_bits(): Remove bogus assertion
[wimlib] / src / decompress.h
1 /*
2  * decompress.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 encapsulate a block of in-memory data that is being interpreted
17  * as a stream of bits.
18  *
19  * This is geared specifically towards the XPRESS and LZX compression formats
20  * with regards to the actual ordering the bits within the byte sequence. */
21 struct input_bitstream {
22
23         /* A variable of length at least 32 bits that is used to hold bits that
24          * have been read from the stream.  The bits are ordered from high-order
25          * to low-order, and the next bit is always the high-order bit. */
26         input_bitbuf_t  bitbuf;
27
28         /* Pointer to the next byte to be retrieved from the input. */
29         const u8 *data;
30
31         /* Number of bits in @bitbuf that are valid. */
32         unsigned bitsleft;
33
34         /* Number of words of data that are left. */
35         unsigned data_bytes_left;
36 };
37
38 /* Initializes a bitstream to receive its input from @data. */
39 static inline void init_input_bitstream(struct input_bitstream *istream,
40                                         const void *data, unsigned num_data_bytes)
41 {
42         istream->bitbuf          = 0;
43         istream->bitsleft        = 0;
44         istream->data            = data;
45         istream->data_bytes_left = num_data_bytes;
46 }
47
48 /* Ensures that the bit buffer variable for the bitstream contains @num_bits
49  * bits.
50  *
51  * If there are at least @num_bits bits remaining in the bitstream, 0 is
52  * returned.  Otherwise, -1 is returned.  */
53 static inline int bitstream_ensure_bits(struct input_bitstream *istream,
54                                         unsigned num_bits)
55 {
56         wimlib_assert2(num_bits <= 16);
57
58         int ret = 0;
59
60         /* Unfortunately this needs to be different for the different
61          * compression types.  LZX requires reading no more than the number of
62          * bits needed, otherwise the end of the compressed data may be overrun.
63          * XPRESS, on the other hand, requires that we always return with at
64          * least 16 bits in the buffer, even if fewer are requested.  This is
65          * important because this may change the location of a literal byte
66          * read with bitstream_read_byte(). */
67 #ifdef XPRESS_DECOMP
68         if (istream->bitsleft < 16) {
69 #else
70         if (istream->bitsleft < num_bits) {
71 #endif
72                 if (istream->data_bytes_left >= 2) {
73                         unsigned shift = sizeof(input_bitbuf_t) * 8 - 16 -
74                                          istream->bitsleft;
75                         istream->bitbuf |= (input_bitbuf_t)le16_to_cpu(
76                                                 *(u16*)istream->data) << shift;
77                         istream->data += 2;
78                         istream->bitsleft += 16;
79                         istream->data_bytes_left -= 2;
80                 } else {
81                         ret = -1;
82                 }
83         }
84         wimlib_assert2(ret != 0 || istream->bitsleft >= num_bits);
85         return ret;
86 }
87
88 /* Returns the next @num_bits bits in the buffer variable, which must contain at
89  * least @num_bits bits, for the bitstream. */
90 static inline unsigned
91 bitstream_peek_bits(const struct input_bitstream *istream, unsigned num_bits)
92 {
93         wimlib_assert2(istream->bitsleft >= num_bits);
94         int ret;
95         if (num_bits == 0)
96                 ret = 0;
97         else
98                 ret = istream->bitbuf >> (sizeof(input_bitbuf_t) * 8 - num_bits);
99         return ret;
100 }
101
102 /* Removes @num_bits bits from the buffer variable, which must contain at least
103  * @num_bits bits, for the bitstream. */
104 static inline void bitstream_remove_bits(struct input_bitstream *istream,
105                                          unsigned num_bits)
106 {
107         wimlib_assert2(istream->bitsleft >= num_bits);
108         istream->bitbuf <<= num_bits;
109         istream->bitsleft -= num_bits;
110 }
111
112 /* Reads @num_bits bits from the input bitstream.  @num_bits must be 16 or fewer.
113  * On success, returns 0 and returns the requested bits in @n.  If there are
114  * fewer than @num_bits remaining in the bitstream, -1 is returned. */
115 static inline int bitstream_read_bits(struct input_bitstream *istream,
116                                       unsigned num_bits, unsigned *n)
117 {
118         wimlib_assert2(num_bits <= 16);
119         int ret = bitstream_ensure_bits(istream, num_bits);
120         if (ret == 0) {
121                 *n = bitstream_peek_bits(istream, num_bits);
122                 bitstream_remove_bits(istream, num_bits);
123         } else {
124                 ERROR("bitstream_read_bits(): Input buffer exhausted");
125         }
126         return ret;
127 }
128
129 /* In the XPRESS format there can be literal bytes embedded in the bitstream.
130  * These bytes are basically separate from the bitstream, as they come AFTER the
131  * bits that are currently in the buffer variable (based on reading 16 bits at a
132  * time), even though the buffer variable may not be empty.
133  *
134  * This function returns the next such literal byte, or -1 if there are no more.
135  */
136 static inline int bitstream_read_byte(struct input_bitstream *istream)
137 {
138         wimlib_assert2(istream->bitsleft < 32);
139         int ret;
140
141         if (istream->data_bytes_left == 0) {
142                 ERROR("bitstream_read_byte(): Input buffer exhausted");
143                 ret = -1;
144         } else {
145                 istream->data_bytes_left--;
146                 ret = *istream->data++;
147         }
148         return ret;
149 }
150
151 /* Reads @num_bits bits from the buffer variable for a bistream without checking
152  * to see if that many bits are in the buffer or not. */
153 static inline unsigned
154 bitstream_read_bits_nocheck(struct input_bitstream *istream, unsigned num_bits)
155 {
156         unsigned n = bitstream_peek_bits(istream, num_bits);
157         bitstream_remove_bits(istream, num_bits);
158         return n;
159 }
160
161 extern int read_huffsym_near_end_of_input(struct input_bitstream *istream,
162                                           const u16 decode_table[],
163                                           const u8 lens[],
164                                           unsigned num_syms,
165                                           unsigned table_bits,
166                                           unsigned *n);
167
168 /*
169  * Reads a Huffman-encoded symbol from a bitstream.
170  *
171  * This function may be called hundreds of millions of times when extracting a
172  * large WIM file.  I'm not sure it could be made much faster that it is,
173  * especially since there isn't enough time to make a big table that allows
174  * decoding multiple symbols per lookup.  But if extracting files to a hard
175  * disk, the I/O will be the bottleneck anyway.
176  *
177  * @buf:        The input buffer from which the symbol will be read.
178  * @decode_table:       The fast Huffman decoding table for the Huffman tree.
179  * @lengths:            The table that gives the length of the code for each
180  *                              symbol.
181  * @num_symbols:        The number of symbols in the Huffman code.
182  * @table_bits:         Huffman codes this length or less can be looked up
183  *                              directory in the decode_table, as the
184  *                              decode_table contains 2**table_bits entries.
185  */
186 static inline int read_huffsym(struct input_bitstream *istream,
187                                const u16 decode_table[],
188                                const u8 lens[],
189                                unsigned num_syms,
190                                unsigned table_bits,
191                                unsigned *n,
192                                unsigned max_codeword_len)
193 {
194         int ret;
195
196         /* In the most common case, there are at least max_codeword_len bits
197          * remaining in the stream. */
198         if (bitstream_ensure_bits(istream, max_codeword_len) == 0) {
199
200                 /* Use the next table_bits of the input as an index into the
201                  * decode_table. */
202                 u16 key_bits = bitstream_peek_bits(istream, table_bits);
203
204                 u16 sym = decode_table[key_bits];
205
206                 /* If the entry in the decode table is not a valid symbol, it is
207                  * the offset of the root of its Huffman subtree. */
208                 if (sym >= num_syms) {
209                         bitstream_remove_bits(istream, table_bits);
210                         do {
211                                 key_bits = sym + bitstream_peek_bits(istream, 1);
212                                 bitstream_remove_bits(istream, 1);
213
214                                 wimlib_assert2(key_bits < num_syms * 2 +
215                                                (1 << table_bits));
216                         } while ((sym = decode_table[key_bits]) >= num_syms);
217                 } else {
218                         wimlib_assert2(lens[sym] <= table_bits);
219                         bitstream_remove_bits(istream, lens[sym]);
220                 }
221                 *n = sym;
222                 ret = 0;
223         } else {
224                 /* Otherwise, we must be careful to use only the bits that are
225                  * actually remaining.  */
226                 ret = read_huffsym_near_end_of_input(istream, decode_table,
227                                                      lens, num_syms,
228                                                      table_bits, n);
229         }
230         return ret;
231 }
232
233 extern int make_huffman_decode_table(u16 decode_table[], unsigned num_syms,
234                                      unsigned num_bits, const u8 lengths[],
235                                      unsigned max_codeword_len);
236
237 #endif /* _WIMLIB_DECOMP_H */