1 ///////////////////////////////////////////////////////////////////////////////
4 /// \brief LZ in window and match finder API
6 // Authors: Igor Pavlov
9 // This file has been put into the public domain.
10 // You can do whatever you want with this file.
12 ///////////////////////////////////////////////////////////////////////////////
14 #ifndef LZMA_LZ_ENCODER_H
15 #define LZMA_LZ_ENCODER_H
20 // For now, the dictionary size is limited to 1.5 GiB. This may grow
21 // in the future if needed, but it needs a little more work than just
22 // changing this check.
23 #define IS_ENC_DICT_SIZE_VALID(size) \
24 ((size) >= LZMA_DICT_SIZE_MIN \
25 && (size) <= (UINT32_C(1) << 30) + (UINT32_C(1) << 29))
28 /// A table of these is used by the LZ-based encoder to hold
29 /// the length-distance pairs found by the match finder.
36 typedef struct lzma_mf_s lzma_mf
;
42 /// Pointer to buffer with data to be compressed
45 /// Total size of the allocated buffer (that is, including all
49 /// Number of bytes that must be kept available in our input history.
50 /// That is, once keep_size_before bytes have been processed,
51 /// buffer[read_pos - keep_size_before] is the oldest byte that
52 /// must be available for reading.
53 uint32_t keep_size_before
;
55 /// Number of bytes that must be kept in buffer after read_pos.
56 /// That is, read_pos <= write_pos - keep_size_after as long as
57 /// action is LZMA_RUN; when action != LZMA_RUN, read_pos is allowed
58 /// to reach write_pos so that the last bytes get encoded too.
59 uint32_t keep_size_after
;
61 /// Match finders store locations of matches using 32-bit integers.
62 /// To avoid adjusting several megabytes of integers every time the
63 /// input window is moved with move_window, we only adjust the
64 /// offset of the buffer. Thus, buffer[value_in_hash_table - offset]
65 /// is the byte pointed by value_in_hash_table.
68 /// buffer[read_pos] is the next byte to run through the match
69 /// finder. This is incremented in the match finder once the byte
70 /// has been processed.
73 /// Number of bytes that have been ran through the match finder, but
74 /// which haven't been encoded by the LZ-based encoder yet.
77 /// As long as read_pos is less than read_limit, there is enough
78 /// input available in buffer for at least one encoding loop.
80 /// Because of the stateful API, read_limit may and will get greater
81 /// than read_pos quite often. This is taken into account when
82 /// calculating the value for keep_size_after.
85 /// buffer[write_pos] is the first byte that doesn't contain valid
86 /// uncompressed data; that is, the next input byte will be copied
87 /// to buffer[write_pos].
90 /// Number of bytes not hashed before read_pos. This is needed to
91 /// restart the match finder after LZMA_SYNC_FLUSH.
98 /// Find matches. Returns the number of distance-length pairs written
99 /// to the matches array. This is called only via lzma_mf_find().
100 uint32_t (*find
)(lzma_mf
*mf
, lzma_match
*matches
);
102 /// Skips num bytes. This is like find() but doesn't make the
103 /// distance-length pairs available, thus being a little faster.
104 /// This is called only via mf_skip().
105 void (*skip
)(lzma_mf
*mf
, uint32_t num
);
110 uint32_t cyclic_size
; // Must be dictionary size + 1.
113 /// Maximum number of loops in the match finder
116 /// Maximum length of a match that the match finder will try to find.
119 /// Maximum length of a match supported by the LZ-based encoder.
120 /// If the longest match found by the match finder is nice_len,
121 /// mf_find() tries to expand it up to match_len_max bytes.
122 uint32_t match_len_max
;
124 /// When running out of input, binary tree match finders need to know
125 /// if it is due to flushing or finishing. The action is used also
126 /// by the LZ-based encoders themselves.
129 /// Number of elements in hash[]
132 /// Number of elements in son[]
138 /// Extra amount of data to keep available before the "actual"
142 /// Size of the history buffer
145 /// Extra amount of data to keep available after the "actual"
149 /// Maximum length of a match that the LZ-based encoder can accept.
150 /// This is used to extend matches of length nice_len to the
151 /// maximum possible length.
152 size_t match_len_max
;
154 /// Match finder will search matches up to this length.
155 /// This must be less than or equal to match_len_max.
158 /// Type of the match finder to use
159 lzma_match_finder match_finder
;
161 /// Maximum search depth
164 /// Initial dictionary for the match finder to search.
165 const uint8_t *preset_dict
;
167 /// If the preset dictionary is NULL, this value is ignored.
168 /// Otherwise this member must indicate the preset dictionary's
169 /// buffer size. If this size is larger than dict_size, then only
170 /// the dict_size sized tail of the preset_dict will be used.
171 uint32_t preset_dict_size
;
176 // The total usable buffer space at any moment outside the match finder:
177 // before_size + dict_size + after_size + match_len_max
179 // In reality, there's some extra space allocated to prevent the number of
180 // memmove() calls reasonable. The bigger the dict_size is, the bigger
181 // this extra buffer will be since with bigger dictionaries memmove() would
184 // A single encoder loop in the LZ-based encoder may call the match finder
185 // (mf_find() or mf_skip()) at most after_size times. In other words,
186 // a single encoder loop may increment lzma_mf.read_pos at most after_size
187 // times. Since matches are looked up to
188 // lzma_mf.buffer[lzma_mf.read_pos + match_len_max - 1], the total
189 // amount of extra buffer needed after dict_size becomes
190 // after_size + match_len_max.
192 // before_size has two uses. The first one is to keep literals available
193 // in cases when the LZ-based encoder has made some read ahead.
194 // TODO: Maybe this could be changed by making the LZ-based encoders to
195 // store the actual literals as they do with length-distance pairs.
197 // Algorithms such as LZMA2 first try to compress a chunk, and then check
198 // if the encoded result is smaller than the uncompressed one. If the chunk
199 // was incompressible, it is better to store it in uncompressed form in
200 // the output stream. To do this, the whole uncompressed chunk has to be
201 // still available in the history buffer. before_size achieves that.
205 /// Data specific to the LZ-based encoder
208 /// Function to encode from *dict to out[]
209 lzma_ret (*code
)(void *coder
,
210 lzma_mf
*restrict mf
, uint8_t *restrict out
,
211 size_t *restrict out_pos
, size_t out_size
);
213 /// Free allocated resources
214 void (*end
)(void *coder
, const lzma_allocator
*allocator
);
216 /// Update the options in the middle of the encoding.
217 lzma_ret (*options_update
)(void *coder
, const lzma_filter
*filter
);
219 /// Set maximum allowed output size
220 lzma_ret (*set_out_limit
)(void *coder
, uint64_t *uncomp_size
,
227 // 1. Input gets copied into the dictionary.
228 // 2. Data in dictionary gets run through the match finder byte by byte.
229 // 3. The literals and matches are encoded using e.g. LZMA.
231 // The bytes that have been ran through the match finder, but not encoded yet,
232 // are called 'read ahead'.
235 /// Get how many bytes the match finder hashes in its initial step.
236 /// This is also the minimum nice_len value with the match finder.
237 static inline uint32_t
238 mf_get_hash_bytes(lzma_match_finder match_finder
)
240 return (uint32_t)match_finder
& 0x0F;
244 /// Get pointer to the first byte not ran through the match finder
245 static inline const uint8_t *
246 mf_ptr(const lzma_mf
*mf
)
248 return mf
->buffer
+ mf
->read_pos
;
252 /// Get the number of bytes that haven't been ran through the match finder yet.
253 static inline uint32_t
254 mf_avail(const lzma_mf
*mf
)
256 return mf
->write_pos
- mf
->read_pos
;
260 /// Get the number of bytes that haven't been encoded yet (some of these
261 /// bytes may have been ran through the match finder though).
262 static inline uint32_t
263 mf_unencoded(const lzma_mf
*mf
)
265 return mf
->write_pos
- mf
->read_pos
+ mf
->read_ahead
;
269 /// Calculate the absolute offset from the beginning of the most recent
270 /// dictionary reset. Only the lowest four bits are important, so there's no
271 /// problem that we don't know the 64-bit size of the data encoded so far.
273 /// NOTE: When moving the input window, we need to do it so that the lowest
274 /// bits of dict->read_pos are not modified to keep this macro working
276 static inline uint32_t
277 mf_position(const lzma_mf
*mf
)
279 return mf
->read_pos
- mf
->read_ahead
;
283 /// Since everything else begins with mf_, use it also for lzma_mf_find().
284 #define mf_find lzma_mf_find
287 /// Skip the given number of bytes. This is used when a good match was found.
288 /// For example, if mf_find() finds a match of 200 bytes long, the first byte
289 /// of that match was already consumed by mf_find(), and the rest 199 bytes
290 /// have to be skipped with mf_skip(mf, 199).
292 mf_skip(lzma_mf
*mf
, uint32_t amount
)
295 mf
->skip(mf
, amount
);
296 mf
->read_ahead
+= amount
;
301 /// Copies at most *left number of bytes from the history buffer
302 /// to out[]. This is needed by LZMA2 to encode uncompressed chunks.
304 mf_read(lzma_mf
*mf
, uint8_t *out
, size_t *out_pos
, size_t out_size
,
307 const size_t out_avail
= out_size
- *out_pos
;
308 const size_t copy_size
= my_min(out_avail
, *left
);
310 assert(mf
->read_ahead
== 0);
311 assert(mf
->read_pos
>= *left
);
313 memcpy(out
+ *out_pos
, mf
->buffer
+ mf
->read_pos
- *left
,
316 *out_pos
+= copy_size
;
322 extern lzma_ret
lzma_lz_encoder_init(
323 lzma_next_coder
*next
, const lzma_allocator
*allocator
,
324 const lzma_filter_info
*filters
,
325 lzma_ret (*lz_init
)(lzma_lz_encoder
*lz
,
326 const lzma_allocator
*allocator
,
327 lzma_vli id
, const void *options
,
328 lzma_lz_options
*lz_options
));
331 extern uint64_t lzma_lz_encoder_memusage(const lzma_lz_options
*lz_options
);
334 // These are only for LZ encoder's internal use.
335 extern uint32_t lzma_mf_find(
336 lzma_mf
*mf
, uint32_t *count
, lzma_match
*matches
);
338 extern uint32_t lzma_mf_hc3_find(lzma_mf
*dict
, lzma_match
*matches
);
339 extern void lzma_mf_hc3_skip(lzma_mf
*dict
, uint32_t amount
);
341 extern uint32_t lzma_mf_hc4_find(lzma_mf
*dict
, lzma_match
*matches
);
342 extern void lzma_mf_hc4_skip(lzma_mf
*dict
, uint32_t amount
);
344 extern uint32_t lzma_mf_bt2_find(lzma_mf
*dict
, lzma_match
*matches
);
345 extern void lzma_mf_bt2_skip(lzma_mf
*dict
, uint32_t amount
);
347 extern uint32_t lzma_mf_bt3_find(lzma_mf
*dict
, lzma_match
*matches
);
348 extern void lzma_mf_bt3_skip(lzma_mf
*dict
, uint32_t amount
);
350 extern uint32_t lzma_mf_bt4_find(lzma_mf
*dict
, lzma_match
*matches
);
351 extern void lzma_mf_bt4_skip(lzma_mf
*dict
, uint32_t amount
);