4 * Binary tree match-finder for Lempel-Ziv compression.
9 * The author dedicates this file to the public domain.
10 * You can do whatever you want with this file.
13 #ifndef _WIMLIB_LZ_BT_H
14 #define _WIMLIB_LZ_BT_H
16 #include "wimlib/types.h"
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;
22 /* Match length type for the binary tree match-finder. */
23 typedef unsigned lz_bt_len_t;
25 /* The binary tree match-finder structure. */
27 lz_bt_pos_t *hash_tab;
28 lz_bt_pos_t *digram_tab;
29 lz_bt_pos_t *child_tab;
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;
43 lz_bt_get_needed_memory(lz_bt_pos_t max_window_size);
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);
54 lz_bt_load_window(struct lz_bt *mf, const u8 *window, lz_bt_pos_t window_size);
57 lz_bt_get_matches(struct lz_bt *mf, struct raw_match *matches);
59 static inline lz_bt_pos_t
60 lz_bt_get_position(const struct lz_bt *mf)
62 return mf->cur_window_pos;
65 static inline const u8 *
66 lz_bt_get_window_ptr(const struct lz_bt *mf)
68 return &mf->cur_window[mf->cur_window_pos];
71 static inline lz_bt_pos_t
72 lz_bt_get_remaining_size(const struct lz_bt *mf)
74 return mf->cur_window_size - mf->cur_window_pos;
78 lz_bt_skip_positions(struct lz_bt *mf, unsigned n);
81 lz_bt_destroy(struct lz_bt *mf);
83 #endif /* _WIMLIB_LZ_BT_H */