1 ///////////////////////////////////////////////////////////////////////////////
4 /// \brief LZ in window and match finder API
6 // Copyright (C) 1999-2008 Igor Pavlov
7 // Copyright (C) 2008 Lasse Collin
9 // This library is free software; you can redistribute it and/or
10 // modify it under the terms of the GNU Lesser General Public
11 // License as published by the Free Software Foundation; either
12 // version 2.1 of the License, or (at your option) any later version.
14 // This library is distributed in the hope that it will be useful,
15 // but WITHOUT ANY WARRANTY; without even the implied warranty of
16 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17 // Lesser General Public License for more details.
19 ///////////////////////////////////////////////////////////////////////////////
21 #ifndef LZMA_LZ_ENCODER_H
22 #define LZMA_LZ_ENCODER_H
27 /// A table of these is used by the LZ-based encoder to hold
28 /// the length-distance pairs found by the match finder.
35 typedef struct lzma_mf_s lzma_mf;
41 /// Pointer to buffer with data to be compressed
44 /// Total size of the allocated buffer (that is, including all
48 /// Number of bytes that must be kept available in our input history.
49 /// That is, once keep_size_before bytes have been processed,
50 /// buffer[read_pos - keep_size_before] is the oldest byte that
51 /// must be available for reading.
52 uint32_t keep_size_before;
54 /// Number of bytes that must be kept in buffer after read_pos.
55 /// That is, read_pos <= write_pos - keep_size_after as long as
56 /// stream_end_was_reached is false (once it is true, read_pos
57 /// is allowed to reach write_pos).
58 uint32_t keep_size_after;
60 /// Match finders store locations of matches using 32-bit integers.
61 /// To avoid adjusting several megabytes of integers every time the
62 /// input window is moved with move_window(), we only adjust the
63 /// offset of the buffer. Thus, buffer[match_finder_pos - offset]
64 /// is the byte pointed by match_finder_pos.
67 /// buffer[read_pos] is the current byte.
70 /// Number of bytes that have been ran through the match finder, but
71 /// which haven't been encoded by the LZ-based encoder yet.
74 /// As long as read_pos is less than read_limit, there is enough
75 /// input available in buffer for at least one encoding loop.
77 /// Because of the stateful API, read_limit may and will get greater
78 /// than read_pos quite often. This is taken into account when
79 /// calculating the value for keep_size_after.
82 /// buffer[write_pos] is the first byte that doesn't contain valid
83 /// uncompressed data; that is, the next input byte will be copied
84 /// to buffer[write_pos].
87 /// Number of bytes not hashed before read_pos. This is needed to
88 /// restart the match finder after LZMA_SYNC_FLUSH.
95 /// Find matches. Returns the number of distance-length pairs written
96 /// to the matches array. This is called only via lzma_mf_find.
97 uint32_t (*find)(lzma_mf *mf, lzma_match *matches);
99 /// Skips num bytes. This is like find() but doesn't make the
100 /// distance-length pairs available, thus being a little faster.
101 /// This is called only via mf_skip function.
102 void (*skip)(lzma_mf *mf, uint32_t num);
106 uint32_t cyclic_buffer_pos;
107 uint32_t cyclic_buffer_size; // Must be dictionary_size + 1.
110 /// Maximum number of loops in the match finder
113 /// Maximum length of a match that the match finder will try to find.
114 uint32_t find_len_max;
116 /// Maximum length of a match supported by the LZ-based encoder.
117 /// If the longest match found by the match finder is find_len_max,
118 /// lz_dict_find() tries to expand it up to match_len_max bytes.
119 uint32_t match_len_max;
121 /// When running out of input, binary tree match finders need to know
122 /// if it is due to flushing or finishing. The action is used also
123 /// by the LZ-based encoders themselves.
126 /// Number of elements in hash[]
127 uint32_t hash_size_sum;
129 /// Number of elements in son[]
135 /// Extra amount of data to keep available before the "actual"
139 /// Size of the history buffer
140 size_t dictionary_size;
142 /// Extra amount of data to keep available after the "actual"
146 /// Maximum length of a match that the LZ-based encoder can accept.
147 /// This is used to extend matches of length find_len_max to the
148 /// maximum possible length.
149 size_t match_len_max;
151 /// Match finder will search matches of at maximum of this length.
152 /// This must be less than or equal to match_len_max.
155 /// Type of the match finder to use
156 lzma_match_finder match_finder;
159 uint32_t match_finder_cycles;
162 const uint8_t *preset_dictionary;
164 uint32_t preset_dictionary_size;
169 // The total usable buffer space at any moment outside the match finder:
170 // before_size + dictionary_size + after_size + match_len_max
172 // In reality, there's some extra space allocated to prevent the number of
173 // memmove() calls reasonable. The bigger the dictionary_size is, the bigger
174 // this extra buffer will be since with bigger dictionaries memmove() would
177 // A single encoder loop in the LZ-based encoder may call the match finder
178 // (lz_dict_find() or lz_dict_skip()) at maximum of after_size times.
179 // In other words, a single encoder loop may advance lz_dict.read_pos at
180 // maximum of after_size times. Since matches are looked up to
181 // lz_dict.buffer[lz_dict.read_pos + match_len_max - 1], the total
182 // amount of extra buffer needed after dictionary_size becomes
183 // after_size + match_len_max.
185 // before_size has two uses. The first one is to keep literals available
186 // in cases when the LZ-based encoder has made some read ahead.
187 // TODO: Maybe this could be changed by making the LZ-based encoders to
188 // store the actual literals as they do with length-distance pairs.
190 // Alrogithms such as LZMA2 first try to compress a chunk, and then check
191 // if the encoded result is smaller than the uncompressed one. If the chunk
192 // was uncompressible, it is better to store it in uncompressed form in
193 // the output stream. To do this, the whole uncompressed chunk has to be
194 // still available in the history buffer. before_size achieves that.
198 /// Data specific to the LZ-based encoder
201 /// Function to encode from *dict to out[]
202 lzma_ret (*code)(lzma_coder *restrict coder,
203 lzma_mf *restrict mf, uint8_t *restrict out,
204 size_t *restrict out_pos, size_t out_size);
206 /// Free allocated resources
207 void (*end)(lzma_coder *coder, lzma_allocator *allocator);
213 // 1. Input gets copied into the dictionary.
214 // 2. Data in dictionary gets run through the match finder byte by byte.
215 // 3. The literals and matches are encoded using e.g. LZMA.
217 // The bytes that have been ran through the match finder, but not encoded yet,
218 // are called `read ahead'.
221 /// Get pointer to the first byte not ran through the match finder
222 static inline const uint8_t *
223 mf_ptr(const lzma_mf *mf)
225 return mf->buffer + mf->read_pos;
229 /// Get the number of bytes that haven't been ran through the match finder yet.
230 static inline uint32_t
231 mf_avail(const lzma_mf *mf)
233 return mf->write_pos - mf->read_pos;
237 /// Get the number of bytes that haven't been encoded yet (some of these
238 /// bytes may have been ran through the match finder though).
239 static inline uint32_t
240 mf_unencoded(const lzma_mf *mf)
242 return mf->write_pos - mf->read_pos - mf->read_ahead;
246 /// Calculate the absolute offset from the beginning of the most recent
247 /// dictionary reset. Only the lowest four bits are important, so there's no
248 /// problem that we don't know the 64-bit size of the data encoded so far.
250 /// NOTE: When moving the input window, we need to do it so that the lowest
251 /// bits of dict->read_pos are not modified to keep this macro working
253 static inline uint32_t
254 mf_position(const lzma_mf *mf)
256 return mf->read_pos - mf->read_ahead;
260 /// Since everything else begins with mf_, use it also for lzma_mf_find().
261 #define mf_find lzma_mf_find
264 /// Skip the given number of bytes. This is used when a good match was found.
265 /// For example, if mf_find() finds a match of 200 bytes long, the first byte
266 /// of that match was already consumed by mf_find(), and the rest 199 bytes
267 /// have to be skipped with mf_skip(mf, 199).
269 mf_skip(lzma_mf *mf, uint32_t amount)
272 mf->skip(mf, amount);
273 mf->read_ahead += amount;
278 /// Copies at maximum of *left amount of bytes from the history buffer
279 /// to out[]. This is needed by LZMA2 to encode uncompressed chunks.
281 mf_read(lzma_mf *mf, uint8_t *out, size_t *out_pos, size_t out_size,
284 const size_t out_avail = out_size - *out_pos;
285 const size_t copy_size = MIN(out_avail, *left);
287 assert(mf->read_ahead == 0);
288 assert(mf->read_pos >= *left);
290 memcpy(out + *out_pos, mf->buffer + mf->read_pos - *left,
293 *out_pos += copy_size;
299 extern lzma_ret lzma_lz_encoder_init(
300 lzma_next_coder *next, lzma_allocator *allocator,
301 const lzma_filter_info *filters,
302 lzma_ret (*lz_init)(lzma_lz_encoder *lz,
303 lzma_allocator *allocator, const void *options,
304 lzma_lz_options *lz_options));
307 extern uint64_t lzma_lz_encoder_memusage(const lzma_lz_options *lz_options);
310 // These are only for LZ encoder's internal use.
311 extern uint32_t lzma_mf_find(
312 lzma_mf *mf, uint32_t *count, lzma_match *matches);
314 extern uint32_t lzma_mf_hc3_find(lzma_mf *dict, lzma_match *matches);
315 extern void lzma_mf_hc3_skip(lzma_mf *dict, uint32_t amount);
317 extern uint32_t lzma_mf_hc4_find(lzma_mf *dict, lzma_match *matches);
318 extern void lzma_mf_hc4_skip(lzma_mf *dict, uint32_t amount);
320 extern uint32_t lzma_mf_bt2_find(lzma_mf *dict, lzma_match *matches);
321 extern void lzma_mf_bt2_skip(lzma_mf *dict, uint32_t amount);
323 extern uint32_t lzma_mf_bt3_find(lzma_mf *dict, lzma_match *matches);
324 extern void lzma_mf_bt3_skip(lzma_mf *dict, uint32_t amount);
326 extern uint32_t lzma_mf_bt4_find(lzma_mf *dict, lzma_match *matches);
327 extern void lzma_mf_bt4_skip(lzma_mf *dict, uint32_t amount);