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  * Copyright 2022 Eric Biggers
   8  *
   9  * Permission is hereby granted, free of charge, to any person
  10  * obtaining a copy of this software and associated documentation
  11  * files (the "Software"), to deal in the Software without
  12  * restriction, including without limitation the rights to use,
  13  * copy, modify, merge, publish, distribute, sublicense, and/or sell
  14  * copies of the Software, and to permit persons to whom the
  15  * Software is furnished to do so, subject to the following
  16  * conditions:
  17  *
  18  * The above copyright notice and this permission notice shall be
  19  * included in all copies or substantial portions of the Software.
  20  *
  21  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  22  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
  23  * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  24  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
  25  * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
  26  * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  27  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
  28  * OTHER DEALINGS IN THE SOFTWARE.
  29  */
  30
  31 #ifndef _LCPIT_MATCHFINDER_H
  32 #define _LCPIT_MATCHFINDER_H
  33
  34 #include "wimlib/types.h"
  35
  36 struct lcpit_matchfinder {
  37         bool huge_mode;
  38         u32 cur_pos;
  39         u32 *pos_data;
  40         union {
  41                 u32 *intervals;
  42                 u64 *intervals64;
  43         };
  44         u32 min_match_len;
  45         u32 nice_match_len;
  46         u32 next[2];
  47         u32 orig_nice_match_len;
  48 };
  49
  50 struct lz_match {
  51         u32 length;
  52         u32 offset;
  53 };
  54
  55 u64
  56 lcpit_matchfinder_get_needed_memory(size_t max_bufsize);
  57
  58 bool
  59 lcpit_matchfinder_init(struct lcpit_matchfinder *mf, size_t max_bufsize,
  60                        u32 min_match_len, u32 nice_match_len);
  61
  62 void
  63 lcpit_matchfinder_load_buffer(struct lcpit_matchfinder *mf, const u8 *T, u32 n);
  64
  65 u32
  66 lcpit_matchfinder_get_matches(struct lcpit_matchfinder *mf,
  67                               struct lz_match *matches);
  68
  69 void
  70 lcpit_matchfinder_skip_bytes(struct lcpit_matchfinder *mf, u32 count);
  71
  72 void
  73 lcpit_matchfinder_destroy(struct lcpit_matchfinder *mf);
  74
  75 #endif /* _LCPIT_MATCHFINDER_H */