wimlib.net Git - wimlib/blob - include/wimlib/lz_bt.h

   1 /*
   2  * lz_bt.h
   3  *
   4  * Binary tree match-finder for Lempel-Ziv compression.
   5  *
   6  * Author:  Eric Biggers
   7  * Year:    2014
   8  *
   9  * The author dedicates this file to the public domain.
  10  * You can do whatever you want with this file.
  11  */
  12
  13 #ifndef _WIMLIB_LZ_BT_H
  14 #define _WIMLIB_LZ_BT_H
  15
  16 #include "wimlib/types.h"
  17
  18 /* Position type for the binary tree match-finder.
  19  * This can be changed to 'u16' if no window will exceed 65536 bytes.  */
  20 typedef u32 lz_bt_pos_t;
  21
  22 /* Match length type for the binary tree match-finder.  */
  23 typedef unsigned lz_bt_len_t;
  24
  25 /* The binary tree match-finder structure.  */
  26 struct lz_bt {
  27         lz_bt_pos_t *hash_tab;
  28         lz_bt_pos_t *digram_tab;
  29         lz_bt_pos_t *child_tab;
  30         const u8 *cur_window;
  31         lz_bt_pos_t cur_window_pos;
  32         lz_bt_pos_t cur_window_size;
  33         lz_bt_pos_t max_window_size;
  34         lz_bt_len_t min_match_len;
  35         lz_bt_len_t max_match_len;
  36         lz_bt_len_t num_fast_bytes;
  37         u32 max_search_depth;
  38 };
  39
  40 struct lz_match;
  41
  42 extern u64
  43 lz_bt_get_needed_memory(lz_bt_pos_t max_window_size);
  44
  45 extern bool
  46 lz_bt_init(struct lz_bt *mf,
  47            lz_bt_pos_t max_window_size,
  48            lz_bt_len_t min_match_len,
  49            lz_bt_len_t max_match_len,
  50            lz_bt_len_t num_fast_bytes,
  51            u32 max_search_depth);
  52
  53 extern void
  54 lz_bt_load_window(struct lz_bt *mf, const u8 *window, lz_bt_pos_t window_size);
  55
  56 extern lz_bt_len_t
  57 lz_bt_get_matches(struct lz_bt *mf, struct lz_match *matches);
  58
  59 static inline lz_bt_pos_t
  60 lz_bt_get_position(const struct lz_bt *mf)
  61 {
  62         return mf->cur_window_pos;
  63 }
  64
  65 static inline const u8 *
  66 lz_bt_get_window_ptr(const struct lz_bt *mf)
  67 {
  68         return &mf->cur_window[mf->cur_window_pos];
  69 }
  70
  71 static inline lz_bt_pos_t
  72 lz_bt_get_remaining_size(const struct lz_bt *mf)
  73 {
  74         return mf->cur_window_size - mf->cur_window_pos;
  75 }
  76
  77 extern void
  78 lz_bt_skip_positions(struct lz_bt *mf, unsigned n);
  79
  80 extern void
  81 lz_bt_destroy(struct lz_bt *mf);
  82
  83 #endif /* _WIMLIB_LZ_BT_H */