Use more comprehensive public domain dedications
[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 either a pointer to the byte past the last written, or NULL if the
177  * read overflows the input buffer.  */
178 static inline void *
179 bitstream_read_bytes(struct input_bitstream *is, void *dst_buffer, size_t count)
180 {
181         if (unlikely(is->end - is->next < count))
182                 return NULL;
183         memcpy(dst_buffer, is->next, count);
184         is->next += count;
185         return (u8 *)dst_buffer + count;
186 }
187
188 /* Align the input bitstream on a coding-unit boundary.  */
189 static inline void
190 bitstream_align(struct input_bitstream *is)
191 {
192         is->bitsleft = 0;
193         is->bitbuf = 0;
194 }
195
196 /* Needed alignment of decode_table parameter to make_huffman_decode_table().
197  *
198  * Reason: We may fill the entries with SSE instructions without worrying
199  * about dealing with the unaligned case.  */
200 #define DECODE_TABLE_ALIGNMENT 16
201
202 /* Maximum supported symbol count for make_huffman_decode_table().
203  *
204  * Reason: In direct mapping entries, we store the symbol in 11 bits.  */
205 #define DECODE_TABLE_MAX_SYMBOLS 2048
206
207 /* Maximum supported table bits for make_huffman_decode_table().
208  *
209  * Reason: In internal binary tree nodes, offsets are encoded in 14 bits.
210  * But the real limit is 13, because we allocate entries past the end of
211  * the direct lookup part of the table for binary tree nodes.  (Note: if
212  * needed this limit could be removed by encoding the offsets relative to
213  * &decode_table[1 << table_bits].)  */
214 #define DECODE_TABLE_MAX_TABLE_BITS 13
215
216 /* Maximum supported codeword length for make_huffman_decode_table().
217  *
218  * Reason: In direct mapping entries, we encode the codeword length in 5
219  * bits, and the top 2 bits can't both be set because that has special
220  * meaning.  */
221 #define DECODE_TABLE_MAX_CODEWORD_LEN 23
222
223 /* Reads and returns the next Huffman-encoded symbol from a bitstream.  If the
224  * input data is exhausted, the Huffman symbol is decoded as if the missing bits
225  * are all zeroes.
226  *
227  * XXX: This is mostly duplicated in lzms_decode_huffman_symbol() in
228  * lzms_decompress.c.  */
229 static inline unsigned
230 read_huffsym(struct input_bitstream *istream, const u16 decode_table[],
231              unsigned table_bits, unsigned max_codeword_len)
232 {
233         unsigned entry;
234         unsigned key_bits;
235
236         bitstream_ensure_bits(istream, max_codeword_len);
237
238         /* Index the decode table by the next table_bits bits of the input.  */
239         key_bits = bitstream_peek_bits(istream, table_bits);
240         entry = decode_table[key_bits];
241         if (likely(entry < 0xC000)) {
242                 /* Fast case: The decode table directly provided the
243                  * symbol and codeword length.  The low 11 bits are the
244                  * symbol, and the high 5 bits are the codeword length.  */
245                 bitstream_remove_bits(istream, entry >> 11);
246                 return entry & 0x7FF;
247         } else {
248                 /* Slow case: The codeword for the symbol is longer than
249                  * table_bits, so the symbol does not have an entry
250                  * directly in the first (1 << table_bits) entries of the
251                  * decode table.  Traverse the appropriate binary tree
252                  * bit-by-bit to decode the symbol.  */
253                 bitstream_remove_bits(istream, table_bits);
254                 do {
255                         key_bits = (entry & 0x3FFF) + bitstream_pop_bits(istream, 1);
256                 } while ((entry = decode_table[key_bits]) >= 0xC000);
257                 return entry;
258         }
259 }
260
261 extern int
262 make_huffman_decode_table(u16 decode_table[], unsigned num_syms,
263                           unsigned num_bits, const u8 lens[],
264                           unsigned max_codeword_len);
265
266 static inline void
267 copy_word_unaligned(const void *src, void *dst)
268 {
269         store_word_unaligned(load_word_unaligned(src), dst);
270 }
271
272 static inline machine_word_t
273 repeat_byte(u8 b)
274 {
275         machine_word_t v;
276
277         STATIC_ASSERT(WORDSIZE == 4 || WORDSIZE == 8);
278
279         v = b;
280         v |= v << 8;
281         v |= v << 16;
282         v |= v << ((WORDSIZE == 8) ? 32 : 0);
283         return v;
284 }
285
286 /*
287  * Copy an LZ77 match at (dst - offset) to dst.
288  *
289  * The length and offset must be already validated --- that is, (dst - offset)
290  * can't underrun the output buffer, and (dst + length) can't overrun the output
291  * buffer.  Also, the length cannot be 0.
292  *
293  * @winend points to the byte past the end of the output buffer.
294  * This function won't write any data beyond this position.
295  */
296 static inline void
297 lz_copy(u8 *dst, u32 length, u32 offset, const u8 *winend, u32 min_length)
298 {
299         const u8 *src = dst - offset;
300         const u8 * const end = dst + length;
301
302         /*
303          * Try to copy one machine word at a time.  On i386 and x86_64 this is
304          * faster than copying one byte at a time, unless the data is
305          * near-random and all the matches have very short lengths.  Note that
306          * since this requires unaligned memory accesses, it won't necessarily
307          * be faster on every architecture.
308          *
309          * Also note that we might copy more than the length of the match.  For
310          * example, if a word is 8 bytes and the match is of length 5, then
311          * we'll simply copy 8 bytes.  This is okay as long as we don't write
312          * beyond the end of the output buffer, hence the check for (winend -
313          * end >= WORDSIZE - 1).
314          */
315         if (UNALIGNED_ACCESS_IS_FAST &&
316             likely(winend - end >= WORDSIZE - 1))
317         {
318
319                 if (offset >= WORDSIZE) {
320                         /* The source and destination words don't overlap.  */
321
322                         /* To improve branch prediction, one iteration of this
323                          * loop is unrolled.  Most matches are short and will
324                          * fail the first check.  But if that check passes, then
325                          * it becomes increasing likely that the match is long
326                          * and we'll need to continue copying.  */
327
328                         copy_word_unaligned(src, dst);
329                         src += WORDSIZE;
330                         dst += WORDSIZE;
331
332                         if (dst < end) {
333                                 do {
334                                         copy_word_unaligned(src, dst);
335                                         src += WORDSIZE;
336                                         dst += WORDSIZE;
337                                 } while (dst < end);
338                         }
339                         return;
340                 } else if (offset == 1) {
341
342                         /* Offset 1 matches are equivalent to run-length
343                          * encoding of the previous byte.  This case is common
344                          * if the data contains many repeated bytes.  */
345
346                         machine_word_t v = repeat_byte(*(dst - 1));
347                         do {
348                                 store_word_unaligned(v, dst);
349                                 src += WORDSIZE;
350                                 dst += WORDSIZE;
351                         } while (dst < end);
352                         return;
353                 }
354                 /*
355                  * We don't bother with special cases for other 'offset <
356                  * WORDSIZE', which are usually rarer than 'offset == 1'.  Extra
357                  * checks will just slow things down.  Actually, it's possible
358                  * to handle all the 'offset < WORDSIZE' cases using the same
359                  * code, but it still becomes more complicated doesn't seem any
360                  * faster overall; it definitely slows down the more common
361                  * 'offset == 1' case.
362                  */
363         }
364
365         /* Fall back to a bytewise copy.  */
366
367         if (min_length >= 2) {
368                 *dst++ = *src++;
369                 length--;
370         }
371         if (min_length >= 3) {
372                 *dst++ = *src++;
373                 length--;
374         }
375         if (min_length >= 4) {
376                 *dst++ = *src++;
377                 length--;
378         }
379         do {
380                 *dst++ = *src++;
381         } while (--length);
382 }
383
384 #endif /* _WIMLIB_DECOMPRESS_COMMON_H */