b4c4579543bbe59b6b57f58704689fc28216582d
[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 provide a bitstream. */
17 struct input_bitstream {
18
19         /* A variable of length at least 32 bits that is used to hold bits that
20          * have been read from the stream.  The bits are ordered from high-order
21          * to low-order; the next bit is always the high-order bit. */
22         input_bitbuf_t  bitbuf;
23
24         /* Pointer to the next byte to be retrieved from the input. */
25         const u8 *data;
26
27         /* Number of bits in @bitbuf that are valid. */
28         unsigned bitsleft;
29
30         /* Number of words of data that are left. */
31         unsigned data_bytes_left;
32 };
33
34 /* Initializes a bitstream to receive its input from @data. */
35 static inline void init_input_bitstream(struct input_bitstream *istream,
36                                         const void *data, unsigned num_data_bytes)
37 {
38         istream->bitbuf          = 0;
39         istream->bitsleft        = 0;
40         istream->data            = data;
41         istream->data_bytes_left = num_data_bytes;
42 }
43
44 /* Ensures that the bit buffer contains @num_bits bits. */
45 static inline int bitstream_ensure_bits(struct input_bitstream *istream,
46                                         unsigned num_bits)
47 {
48         wimlib_assert(num_bits <= 16);
49
50         /* Unfortunately this needs to be different for the different
51          * compression types.  LZX requires reading no more than the number of
52          * bits needed, otherwise the end of the compressed data may be overrun.
53          * XPRESS, on the other hand, requires that we always return with at
54          * least 16 bits in the buffer, even if fewer are requested.  This is
55          * important because this may change the location of a literal byte
56          * read with bitstream_read_byte(). */
57 #ifdef XPRESS_DECOMP
58         while (istream->bitsleft < 16) {
59 #else
60         while (istream->bitsleft < num_bits) {
61 #endif
62                 if (istream->data_bytes_left < 2)
63                         return 1;
64
65                 unsigned shift = sizeof(input_bitbuf_t) * 8 - 16 -
66                                  istream->bitsleft;
67                 istream->bitbuf |= (input_bitbuf_t)le16_to_cpu(
68                                         *(u16*)istream->data) << shift;
69                 istream->data += 2;
70                 istream->bitsleft += 16;
71                 istream->data_bytes_left -= 2;
72         }
73         return 0;
74 }
75
76 /* Returns the next @num_bits bits in the bit buffer.  It must contain at least
77  * @num_bits bits to call this function. */
78 static inline unsigned
79 bitstream_peek_bits(const struct input_bitstream *istream, unsigned num_bits)
80 {
81         if (num_bits == 0)
82                 return 0;
83         return istream->bitbuf >> (sizeof(input_bitbuf_t) * 8 - num_bits);
84 }
85
86 /* Removes @num_bits bits from the bit buffer.  It must contain at least
87  * @num_bits bits to call this function. */
88 static inline void bitstream_remove_bits(struct input_bitstream *istream,
89                                          unsigned num_bits)
90 {
91         istream->bitbuf <<= num_bits;
92         istream->bitsleft -= num_bits;
93 }
94
95 /* Reads and returns @num_bits bits from the input bitstream. */
96 static inline int bitstream_read_bits(struct input_bitstream *istream,
97                                       unsigned num_bits, unsigned *n)
98 {
99         int ret;
100         ret = bitstream_ensure_bits(istream, num_bits);
101         if (ret != 0) {
102                 ERROR("bitstream_read_bits(): Input buffer exhausted");
103                 return ret;
104         }
105         *n = bitstream_peek_bits(istream, num_bits);
106         bitstream_remove_bits(istream, num_bits);
107         return 0;
108 }
109
110 /* In the XPRESS format there can be literal length bytes embedded in the
111  * compressed bitstream.  These bytes are basically separate from the bitstream,
112  * as they come AFTER the bits that are currently in the buffer variable (based
113  * on reading 16 bits at a time), even though the buffer variable may not be
114  * empty.
115  *
116  * This function returns the next such literal length byte in the input
117  * bitstream.  Returns -1 if we are at the end of the bitstream. */
118 static inline int bitstream_read_byte(struct input_bitstream *istream)
119 {
120         wimlib_assert(istream->bitsleft < 32);
121
122         if (istream->data_bytes_left == 0) {
123                 ERROR("bitstream_read_byte(): Input buffer exhausted");
124                 return -1;
125         }
126         istream->data_bytes_left--;
127         return *istream->data++;
128 }
129
130 /* Reads @num_bits bits from the bit buffer without checking to see if that many
131  * bits are in the buffer or not. */
132 static inline unsigned
133 bitstream_read_bits_nocheck(struct input_bitstream *istream, unsigned num_bits)
134 {
135         unsigned n = bitstream_peek_bits(istream, num_bits);
136         bitstream_remove_bits(istream, num_bits);
137         return n;
138 }
139
140 /* Removes the bits that have been read into the bit buffer variable. */
141 static inline void flush_input_bitstream(struct input_bitstream *istream)
142 {
143         bitstream_remove_bits(istream, istream->bitsleft);
144         istream->bitsleft = 0;
145         istream->bitbuf = 0;
146 }
147
148 extern int bitstream_read_bytes(struct input_bitstream *istream, size_t n,
149                                 void *dest);
150
151 extern int align_input_bitstream(struct input_bitstream *istream,
152                                  bool skip_word_if_aligned);
153
154 extern int read_huffsym(struct input_bitstream *stream,
155                         const u16 decode_table[],
156                         const u8 lengths[],
157                         unsigned num_symbols,
158                         unsigned table_bits,
159                         unsigned *n,
160                         unsigned max_codeword_len);
161
162 extern int make_huffman_decode_table(u16 decode_table[], unsigned num_syms,
163                                      unsigned num_bits, const u8 lengths[],
164                                      unsigned max_codeword_len);
165
166 #endif /* _WIMLIB_DECOMP_H */