New compression/decompression API
[wimlib] / include / wimlib / decompress_common.h
1 /*
2  * decompress_common.h
3  *
4  * Header for decompression code shared by multiple compression formats.
5  */
6
7 #ifndef _WIMLIB_DECOMPRESS_COMMON_H
8 #define _WIMLIB_DECOMPRESS_COMMON_H
9
10 #include "wimlib/assert.h"
11 #include "wimlib/compiler.h"
12 #include "wimlib/error.h"
13 #include "wimlib/endianness.h"
14 #include "wimlib/types.h"
15
16 #ifndef INPUT_IDX_T_DEFINED
17 #define INPUT_IDX_T_DEFINED
18 typedef u32 input_idx_t;
19 #endif
20
21 /* Structure to encapsulate a block of in-memory data that is being interpreted
22  * as a stream of bits.
23  *
24  * This is geared specifically towards the XPRESS and LZX compression formats
25  * with regards to the actual ordering the bits within the byte sequence.  */
26 struct input_bitstream {
27
28         /* A variable of length at least 32 bits that is used to hold bits that
29          * have been read from the stream.  The bits are ordered from high-order
30          * to low-order, and the next bit is always the high-order bit.  */
31         u32 bitbuf;
32
33         /* Number of bits in @bitbuf that are valid.  */
34         unsigned bitsleft;
35
36         /* Pointer to the next byte to be retrieved from the input.  */
37         const u8 *data;
38
39         /* Number of bytes of data that are left.  */
40         input_idx_t data_bytes_left;
41 };
42
43 /* Initializes a bitstream to receive its input from @data. */
44 static inline void
45 init_input_bitstream(struct input_bitstream *istream,
46                      const void *data, input_idx_t num_data_bytes)
47 {
48         istream->bitbuf          = 0;
49         istream->bitsleft        = 0;
50         istream->data            = data;
51         istream->data_bytes_left = num_data_bytes;
52 }
53
54 /* Ensures that the bit buffer variable for the bitstream contains @num_bits
55  * bits.
56  *
57  * If there are at least @num_bits bits remaining in the bitstream, 0 is
58  * returned.  Otherwise, -1 is returned.  */
59 static inline int
60 bitstream_ensure_bits(struct input_bitstream *istream, unsigned num_bits)
61 {
62         for (int nbits = num_bits; (int)istream->bitsleft < nbits; nbits -= 16) {
63                 u16 nextword;
64                 unsigned shift;
65
66                 if (unlikely(istream->data_bytes_left < 2))
67                         return -1;
68
69                 wimlib_assert2(istream->bitsleft <= sizeof(istream->bitbuf) * 8 - 16);
70
71                 nextword = le16_to_cpu(*(const le16*)istream->data);
72                 shift = sizeof(istream->bitbuf) * 8 - 16 - istream->bitsleft;
73                 istream->bitbuf |= (u32)nextword << shift;
74                 istream->data += 2;
75                 istream->bitsleft += 16;
76                 istream->data_bytes_left -= 2;
77
78         }
79         return 0;
80 }
81
82 /* Returns the next @num_bits bits in the buffer variable, which must contain at
83  * least @num_bits bits, for the bitstream.  */
84 static inline u32
85 bitstream_peek_bits(const struct input_bitstream *istream, unsigned num_bits)
86 {
87         wimlib_assert2(istream->bitsleft >= num_bits);
88
89         if (unlikely(num_bits == 0))
90                 return 0;
91
92         return istream->bitbuf >> (sizeof(istream->bitbuf) * 8 - num_bits);
93 }
94
95 /* Removes @num_bits bits from the buffer variable, which must contain at least
96  * @num_bits bits, for the bitstream.  */
97 static inline void
98 bitstream_remove_bits(struct input_bitstream *istream, unsigned num_bits)
99 {
100         wimlib_assert2(istream->bitsleft >= num_bits);
101
102         istream->bitbuf <<= num_bits;
103         istream->bitsleft -= num_bits;
104 }
105
106 /* Gets and removes @num_bits bits from the buffer variable, which must contain
107  * at least @num_bits bits, for the bitstream.  */
108 static inline u32
109 bitstream_pop_bits(struct input_bitstream *istream, unsigned num_bits)
110 {
111         u32 n = bitstream_peek_bits(istream, num_bits);
112         bitstream_remove_bits(istream, num_bits);
113         return n;
114 }
115
116 /* Reads @num_bits bits from the input bitstream.  On success, returns 0 and
117  * returns the requested bits in @n.  If there are fewer than @num_bits
118  * remaining in the bitstream, -1 is returned. */
119 static inline int
120 bitstream_read_bits(struct input_bitstream *istream, unsigned num_bits, u32 *n)
121 {
122         if (unlikely(bitstream_ensure_bits(istream, num_bits)))
123                 return -1;
124
125         *n = bitstream_pop_bits(istream, num_bits);
126         return 0;
127 }
128
129 /* Return the next literal byte embedded in the bitstream, or -1 if the input
130  * was exhausted.  */
131 static inline int
132 bitstream_read_byte(struct input_bitstream *istream)
133 {
134         if (unlikely(istream->data_bytes_left < 1))
135                 return -1;
136
137         istream->data_bytes_left--;
138         return *istream->data++;
139 }
140
141 /* Reads @num_bits bits from the buffer variable for a bistream without checking
142  * to see if that many bits are in the buffer or not.  */
143 static inline u32
144 bitstream_read_bits_nocheck(struct input_bitstream *istream, unsigned num_bits)
145 {
146         u32 n = bitstream_peek_bits(istream, num_bits);
147         bitstream_remove_bits(istream, num_bits);
148         return n;
149 }
150
151 extern int
152 read_huffsym_near_end_of_input(struct input_bitstream *istream,
153                                const u16 decode_table[],
154                                const u8 lens[],
155                                unsigned num_syms,
156                                unsigned table_bits,
157                                unsigned *n);
158
159 /* Read a Huffman-encoded symbol from a bitstream.  */
160 static inline int
161 read_huffsym(struct input_bitstream * restrict istream,
162              const u16 decode_table[restrict],
163              const u8 lens[restrict],
164              unsigned num_syms,
165              unsigned table_bits,
166              unsigned *restrict n,
167              unsigned max_codeword_len)
168 {
169         /* If there are fewer bits remaining in the input than the maximum
170          * codeword length, use the slow path that has extra checks.  */
171         if (unlikely(bitstream_ensure_bits(istream, max_codeword_len))) {
172                 return read_huffsym_near_end_of_input(istream, decode_table,
173                                                       lens, num_syms,
174                                                       table_bits, n);
175         }
176
177         /* Use the next table_bits of the input as an index into the
178          * decode_table.  */
179         u16 key_bits = bitstream_peek_bits(istream, table_bits);
180
181         u16 sym = decode_table[key_bits];
182
183         if (likely(sym < num_syms)) {
184                 /* Fast case: The decode table directly provided the symbol.  */
185                 bitstream_remove_bits(istream, lens[sym]);
186         } else {
187                 /* Slow case: The symbol took too many bits to include directly
188                  * in the decode table, so search for it in a binary tree at the
189                  * end of the decode table.  */
190                 bitstream_remove_bits(istream, table_bits);
191                 do {
192                         key_bits = sym + bitstream_peek_bits(istream, 1);
193                         bitstream_remove_bits(istream, 1);
194                 } while ((sym = decode_table[key_bits]) >= num_syms);
195         }
196         *n = sym;
197         return 0;
198 }
199
200 extern int
201 make_huffman_decode_table(u16 decode_table[], unsigned num_syms,
202                           unsigned num_bits, const u8 lengths[],
203                           unsigned max_codeword_len);
204
205 /* Minimum alignment for the decode_table parameter to
206  * make_huffman_decode_table().  */
207 #define DECODE_TABLE_ALIGNMENT 16
208
209 #endif /* _WIMLIB_DECOMPRESS_H */