wimlib.net Git - wimlib/blob - 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 */