Compiler stuff
[wimlib] / include / wimlib / compress.h
1 /*
2  * compress.h
3  *
4  * Functions useful for compression, mainly bitstreams.
5  */
6
7 #ifndef _WIMLIB_COMPRESS_H
8 #define _WIMLIB_COMPRESS_H
9
10 #include "wimlib/endianness.h"
11 #include "wimlib/types.h"
12
13 typedef u16 output_bitbuf_t;
14
15 /* Assuming that WIM chunks are at most 32768 bytes, 16 bits is enough for any
16  * symbol frequency. */
17 typedef u16 freq_t;
18
19 /* Structure to keep track of the current position in the compressed output. */
20 struct output_bitstream {
21
22         /* A variable to buffer writing bits to the output and is flushed to the
23          * compressed output when full. */
24         output_bitbuf_t bitbuf;
25
26         /* Number of free bits in @bitbuf */
27         unsigned free_bits;
28
29         u8 *bit_output;
30         u8 *next_bit_output;
31
32         /* Pointer to the next byte in the compressed output. */
33         u8 *output;
34
35
36         /* Number of bytes left in the memory pointed to by @output. */
37         int num_bytes_remaining;
38 };
39
40 static inline int
41 bitstream_put_byte(struct output_bitstream *ostream, u8 n)
42 {
43         if (ostream->num_bytes_remaining < 1)
44                 return 1;
45         *ostream->output = n;
46         ostream->output++;
47         ostream->num_bytes_remaining--;
48         return 0;
49 }
50
51 static inline int
52 bitstream_put_two_bytes(struct output_bitstream *ostream, u16 n)
53 {
54         if (ostream->num_bytes_remaining < 2)
55                 return 1;
56         *(u16*)ostream->output = cpu_to_le16(n);
57         ostream->output += 2;
58         ostream->num_bytes_remaining -= 2;
59         return 0;
60 }
61
62 struct lz_params {
63         unsigned min_match;
64         unsigned max_match;
65         unsigned nice_match;
66         unsigned good_match;
67         unsigned max_chain_len;
68         unsigned max_lazy_match;
69         unsigned too_far;
70 };
71
72 typedef unsigned (*lz_record_match_t)(unsigned, unsigned, void *, void *);
73 typedef unsigned (*lz_record_literal_t)(u8, void *);
74
75 extern unsigned
76 lz_analyze_block(const u8 uncompressed_data[],
77                  unsigned uncompressed_len,
78                  u32 match_tab[],
79                  lz_record_match_t record_match,
80                  lz_record_literal_t record_literal,
81                  void *record_match_arg1,
82                  void *record_match_arg2,
83                  void *record_literal_arg,
84                  const struct lz_params *params);
85
86 extern int bitstream_put_bits(struct output_bitstream *ostream,
87                               output_bitbuf_t bits, unsigned num_bits);
88
89 extern void
90 init_output_bitstream(struct output_bitstream *ostream,
91                       void *data, unsigned num_bytes);
92
93 extern int
94 flush_output_bitstream(struct output_bitstream *ostream);
95
96 extern void
97 make_canonical_huffman_code(unsigned num_syms,
98                             unsigned max_codeword_len,
99                             const freq_t freq_tab[],
100                             u8 lens[],
101                             u16 codewords[]);
102
103 #endif /* _WIMLIB_COMPRESS_H */