c3016475b2c07f812d6d2285443e51839545c83f
[wimlib] / include / wimlib / decompress_common.h
1 /*
2  * decompress_common.h
3  *
4  * Header for decompression code shared by multiple compression formats.
5  *
6  * The following copying information applies to this specific source code file:
7  *
8  * Written in 2012-2016 by Eric Biggers <ebiggers3@gmail.com>
9  *
10  * To the extent possible under law, the author(s) have dedicated all copyright
11  * and related and neighboring rights to this software to the public domain
12  * worldwide via the Creative Commons Zero 1.0 Universal Public Domain
13  * Dedication (the "CC0").
14  *
15  * This software is distributed in the hope that it will be useful, but WITHOUT
16  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
17  * FOR A PARTICULAR PURPOSE. See the CC0 for more details.
18  *
19  * You should have received a copy of the CC0 along with this software; if not
20  * see <http://creativecommons.org/publicdomain/zero/1.0/>.
21  */
22
23 #ifndef _WIMLIB_DECOMPRESS_COMMON_H
24 #define _WIMLIB_DECOMPRESS_COMMON_H
25
26 #include <string.h>
27
28 #include "wimlib/compiler.h"
29 #include "wimlib/types.h"
30 #include "wimlib/unaligned.h"
31
32 /* Structure that encapsulates a block of in-memory data being interpreted as a
33  * stream of bits, optionally with interwoven literal bytes.  Bits are assumed
34  * to be stored in little endian 16-bit coding units, with the bits ordered high
35  * to low.  */
36 struct input_bitstream {
37
38         /* Bits that have been read from the input buffer.  The bits are
39          * left-justified; the next bit is always bit 31.  */
40         u32 bitbuf;
41
42         /* Number of bits currently held in @bitbuf.  */
43         u32 bitsleft;
44
45         /* Pointer to the next byte to be retrieved from the input buffer.  */
46         const u8 *next;
47
48         /* Pointer past the end of the input buffer.  */
49         const u8 *end;
50 };
51
52 /* Initialize a bitstream to read from the specified input buffer.  */
53 static inline void
54 init_input_bitstream(struct input_bitstream *is, const void *buffer, u32 size)
55 {
56         is->bitbuf = 0;
57         is->bitsleft = 0;
58         is->next = buffer;
59         is->end = is->next + size;
60 }
61
62 /* Note: for performance reasons, the following methods don't return error codes
63  * to the caller if the input buffer is overrun.  Instead, they just assume that
64  * all overrun data is zeroes.  This has no effect on well-formed compressed
65  * data.  The only disadvantage is that bad compressed data may go undetected,
66  * but even this is irrelevant if higher level code checksums the uncompressed
67  * data anyway.  */
68
69 /* Ensure the bit buffer variable for the bitstream contains at least @num_bits
70  * bits.  Following this, bitstream_peek_bits() and/or bitstream_remove_bits()
71  * may be called on the bitstream to peek or remove up to @num_bits bits.  */
72 static inline void
73 bitstream_ensure_bits(struct input_bitstream *is, const unsigned num_bits)
74 {
75         /* This currently works for at most 17 bits.  */
76
77         if (is->bitsleft >= num_bits)
78                 return;
79
80         if (unlikely(is->end - is->next < 2))
81                 goto overflow;
82
83         is->bitbuf |= (u32)get_unaligned_le16(is->next) << (16 - is->bitsleft);
84         is->next += 2;
85         is->bitsleft += 16;
86
87         if (unlikely(num_bits == 17 && is->bitsleft == 16)) {
88                 if (unlikely(is->end - is->next < 2))
89                         goto overflow;
90
91                 is->bitbuf |= (u32)get_unaligned_le16(is->next);
92                 is->next += 2;
93                 is->bitsleft = 32;
94         }
95
96         return;
97
98 overflow:
99         is->bitsleft = 32;
100 }
101
102 /* Return the next @num_bits bits from the bitstream, without removing them.
103  * There must be at least @num_bits remaining in the buffer variable, from a
104  * previous call to bitstream_ensure_bits().  */
105 static inline u32
106 bitstream_peek_bits(const struct input_bitstream *is, const unsigned num_bits)
107 {
108         return (is->bitbuf >> 1) >> (sizeof(is->bitbuf) * 8 - num_bits - 1);
109 }
110
111 /* Remove @num_bits from the bitstream.  There must be at least @num_bits
112  * remaining in the buffer variable, from a previous call to
113  * bitstream_ensure_bits().  */
114 static inline void
115 bitstream_remove_bits(struct input_bitstream *is, unsigned num_bits)
116 {
117         is->bitbuf <<= num_bits;
118         is->bitsleft -= num_bits;
119 }
120
121 /* Remove and return @num_bits bits from the bitstream.  There must be at least
122  * @num_bits remaining in the buffer variable, from a previous call to
123  * bitstream_ensure_bits().  */
124 static inline u32
125 bitstream_pop_bits(struct input_bitstream *is, unsigned num_bits)
126 {
127         u32 bits = bitstream_peek_bits(is, num_bits);
128         bitstream_remove_bits(is, num_bits);
129         return bits;
130 }
131
132 /* Read and return the next @num_bits bits from the bitstream.  */
133 static inline u32
134 bitstream_read_bits(struct input_bitstream *is, unsigned num_bits)
135 {
136         bitstream_ensure_bits(is, num_bits);
137         return bitstream_pop_bits(is, num_bits);
138 }
139
140 /* Read and return the next literal byte embedded in the bitstream.  */
141 static inline u8
142 bitstream_read_byte(struct input_bitstream *is)
143 {
144         if (unlikely(is->end == is->next))
145                 return 0;
146         return *is->next++;
147 }
148
149 /* Read and return the next 16-bit integer embedded in the bitstream.  */
150 static inline u16
151 bitstream_read_u16(struct input_bitstream *is)
152 {
153         u16 v;
154
155         if (unlikely(is->end - is->next < 2))
156                 return 0;
157         v = get_unaligned_le16(is->next);
158         is->next += 2;
159         return v;
160 }
161
162 /* Read and return the next 32-bit integer embedded in the bitstream.  */
163 static inline u32
164 bitstream_read_u32(struct input_bitstream *is)
165 {
166         u32 v;
167
168         if (unlikely(is->end - is->next < 4))
169                 return 0;
170         v = get_unaligned_le32(is->next);
171         is->next += 4;
172         return v;
173 }
174
175 /* Read into @dst_buffer an array of literal bytes embedded in the bitstream.
176  * Return 0 if there were enough bytes remaining in the input, otherwise -1. */
177 static inline int
178 bitstream_read_bytes(struct input_bitstream *is, void *dst_buffer, size_t count)
179 {
180         if (unlikely(is->end - is->next < count))
181                 return -1;
182         memcpy(dst_buffer, is->next, count);
183         is->next += count;
184         return 0;
185 }
186
187 /* Align the input bitstream on a coding-unit boundary.  */
188 static inline void
189 bitstream_align(struct input_bitstream *is)
190 {
191         is->bitsleft = 0;
192         is->bitbuf = 0;
193 }
194
195 /* Needed alignment of decode_table parameter to make_huffman_decode_table().
196  *
197  * Reason: We may fill the entries with SSE instructions without worrying
198  * about dealing with the unaligned case.  */
199 #define DECODE_TABLE_ALIGNMENT 16
200
201 /* Maximum supported symbol count for make_huffman_decode_table().
202  *
203  * Reason: In direct mapping entries, we store the symbol in 11 bits.  */
204 #define DECODE_TABLE_MAX_SYMBOLS 2048
205
206 /* Maximum supported table bits for make_huffman_decode_table().
207  *
208  * Reason: In internal binary tree nodes, offsets are encoded in 14 bits.
209  * But the real limit is 13, because we allocate entries past the end of
210  * the direct lookup part of the table for binary tree nodes.  (Note: if
211  * needed this limit could be removed by encoding the offsets relative to
212  * &decode_table[1 << table_bits].)  */
213 #define DECODE_TABLE_MAX_TABLE_BITS 13
214
215 /* Maximum supported codeword length for make_huffman_decode_table().
216  *
217  * Reason: In direct mapping entries, we encode the codeword length in 5
218  * bits, and the top 2 bits can't both be set because that has special
219  * meaning.  */
220 #define DECODE_TABLE_MAX_CODEWORD_LEN 23
221
222 /* Reads and returns the next Huffman-encoded symbol from a bitstream.  If the
223  * input data is exhausted, the Huffman symbol is decoded as if the missing bits
224  * are all zeroes.
225  *
226  * XXX: This is mostly duplicated in lzms_decode_huffman_symbol() in
227  * lzms_decompress.c.  */
228 static inline unsigned
229 read_huffsym(struct input_bitstream *istream, const u16 decode_table[],
230              unsigned table_bits, unsigned max_codeword_len)
231 {
232         unsigned entry;
233         unsigned key_bits;
234
235         bitstream_ensure_bits(istream, max_codeword_len);
236
237         /* Index the decode table by the next table_bits bits of the input.  */
238         key_bits = bitstream_peek_bits(istream, table_bits);
239         entry = decode_table[key_bits];
240         if (likely(entry < 0xC000)) {
241                 /* Fast case: The decode table directly provided the
242                  * symbol and codeword length.  The low 11 bits are the
243                  * symbol, and the high 5 bits are the codeword length.  */
244                 bitstream_remove_bits(istream, entry >> 11);
245                 return entry & 0x7FF;
246         } else {
247                 /* Slow case: The codeword for the symbol is longer than
248                  * table_bits, so the symbol does not have an entry
249                  * directly in the first (1 << table_bits) entries of the
250                  * decode table.  Traverse the appropriate binary tree
251                  * bit-by-bit to decode the symbol.  */
252                 bitstream_remove_bits(istream, table_bits);
253                 do {
254                         key_bits = (entry & 0x3FFF) + bitstream_pop_bits(istream, 1);
255                 } while ((entry = decode_table[key_bits]) >= 0xC000);
256                 return entry;
257         }
258 }
259
260 extern int
261 make_huffman_decode_table(u16 decode_table[], unsigned num_syms,
262                           unsigned num_bits, const u8 lens[],
263                           unsigned max_codeword_len);
264
265 static inline void
266 copy_word_unaligned(const void *src, void *dst)
267 {
268         store_word_unaligned(load_word_unaligned(src), dst);
269 }
270
271 static inline machine_word_t
272 repeat_byte(u8 b)
273 {
274         machine_word_t v;
275
276         STATIC_ASSERT(WORDBITS == 32 || WORDBITS == 64);
277
278         v = b;
279         v |= v << 8;
280         v |= v << 16;
281         v |= v << ((WORDBITS == 64) ? 32 : 0);
282         return v;
283 }
284
285 /*
286  * Copy an LZ77 match at (dst - offset) to dst.
287  *
288  * The length and offset must be already validated --- that is, (dst - offset)
289  * can't underrun the output buffer, and (dst + length) can't overrun the output
290  * buffer.  Also, the length cannot be 0.
291  *
292  * @winend points to the byte past the end of the output buffer.
293  * This function won't write any data beyond this position.
294  */
295 static inline void
296 lz_copy(u8 *dst, u32 length, u32 offset, const u8 *winend, u32 min_length)
297 {
298         const u8 *src = dst - offset;
299         const u8 * const end = dst + length;
300
301         /*
302          * Try to copy one machine word at a time.  On i386 and x86_64 this is
303          * faster than copying one byte at a time, unless the data is
304          * near-random and all the matches have very short lengths.  Note that
305          * since this requires unaligned memory accesses, it won't necessarily
306          * be faster on every architecture.
307          *
308          * Also note that we might copy more than the length of the match.  For
309          * example, if a word is 8 bytes and the match is of length 5, then
310          * we'll simply copy 8 bytes.  This is okay as long as we don't write
311          * beyond the end of the output buffer, hence the check for (winend -
312          * end >= WORDBYTES - 1).
313          */
314         if (UNALIGNED_ACCESS_IS_FAST && likely(winend - end >= WORDBYTES - 1)) {
315
316                 if (offset >= WORDBYTES) {
317                         /* The source and destination words don't overlap.  */
318
319                         /* To improve branch prediction, one iteration of this
320                          * loop is unrolled.  Most matches are short and will
321                          * fail the first check.  But if that check passes, then
322                          * it becomes increasing likely that the match is long
323                          * and we'll need to continue copying.  */
324
325                         copy_word_unaligned(src, dst);
326                         src += WORDBYTES;
327                         dst += WORDBYTES;
328
329                         if (dst < end) {
330                                 do {
331                                         copy_word_unaligned(src, dst);
332                                         src += WORDBYTES;
333                                         dst += WORDBYTES;
334                                 } while (dst < end);
335                         }
336                         return;
337                 } else if (offset == 1) {
338
339                         /* Offset 1 matches are equivalent to run-length
340                          * encoding of the previous byte.  This case is common
341                          * if the data contains many repeated bytes.  */
342
343                         machine_word_t v = repeat_byte(*(dst - 1));
344                         do {
345                                 store_word_unaligned(v, dst);
346                                 src += WORDBYTES;
347                                 dst += WORDBYTES;
348                         } while (dst < end);
349                         return;
350                 }
351                 /*
352                  * We don't bother with special cases for other 'offset <
353                  * WORDBYTES', which are usually rarer than 'offset == 1'.
354                  * Extra checks will just slow things down.  Actually, it's
355                  * possible to handle all the 'offset < WORDBYTES' cases using
356                  * the same code, but it still becomes more complicated doesn't
357                  * seem any faster overall; it definitely slows down the more
358                  * common 'offset == 1' case.
359                  */
360         }
361
362         /* Fall back to a bytewise copy.  */
363
364         if (min_length >= 2) {
365                 *dst++ = *src++;
366                 length--;
367         }
368         if (min_length >= 3) {
369                 *dst++ = *src++;
370                 length--;
371         }
372         if (min_length >= 4) {
373                 *dst++ = *src++;
374                 length--;
375         }
376         do {
377                 *dst++ = *src++;
378         } while (--length);
379 }
380
381 #endif /* _WIMLIB_DECOMPRESS_COMMON_H */