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

   1 /*
   2  * lcpit_matchfinder.h
   3  *
   4  * A match-finder for Lempel-Ziv compression based on bottom-up construction and
   5  * traversal of the Longest Common Prefix (LCP) interval tree.
   6  *
   7  * Author:      Eric Biggers
   8  * Year:        2014, 2015
   9  *
  10  * The author dedicates this file to the public domain.
  11  * You can do whatever you want with this file.
  12  */
  13
  14 #ifndef _LCPIT_MATCHFINDER_H
  15 #define _LCPIT_MATCHFINDER_H
  16
  17 #include "wimlib/types.h"
  18
  19 struct lcpit_matchfinder {
  20
  21         bool huge_mode;
  22
  23         u32 cur_pos;
  24
  25         /* Mapping: suffix index ("window position") => lcp-interval index  */
  26         u32 *pos_data;
  27
  28         /* Mapping: lcp-interval index => lcp-interval data
  29          *
  30          * Initially, the lcp-interval data for an lcp-interval contains that
  31          * interval's lcp and superinterval index.
  32          *
  33          * After a lcp-interval is visited during match-finding, its
  34          * lcp-interval data contains that interval's lcp and the position of
  35          * the next suffix to consider as a match when matching against that
  36          * lcp-interval.  */
  37         union {
  38                 u32 *intervals;
  39                 u64 *intervals64;
  40         };
  41
  42         /* The suffix array  */
  43         u32 *SA;
  44
  45         u32 min_match_len;
  46         u32 nice_match_len;
  47 };
  48
  49 struct lz_match {
  50         u32 length;
  51         u32 offset;
  52 };
  53
  54 extern u64
  55 lcpit_matchfinder_get_needed_memory(size_t max_bufsize);
  56
  57 extern bool
  58 lcpit_matchfinder_init(struct lcpit_matchfinder *mf, size_t max_bufsize,
  59                        u32 min_match_len, u32 nice_match_len);
  60
  61 extern void
  62 lcpit_matchfinder_destroy(struct lcpit_matchfinder *mf);
  63
  64 extern void
  65 lcpit_matchfinder_load_buffer(struct lcpit_matchfinder *mf, const u8 *T, u32 n);
  66
  67 extern u32
  68 lcpit_matchfinder_get_matches(struct lcpit_matchfinder *mf,
  69                               struct lz_match *matches);
  70
  71 extern void
  72 lcpit_matchfinder_skip_bytes(struct lcpit_matchfinder *mf, u32 count);
  73
  74 #endif /* _LCPIT_MATCHFINDER_H */