1///////////////////////////////////////////////////////////////////////////////
2//
3/// \file       lz_encoder.h
4/// \brief      LZ in window and match finder API
5///
6//  Authors:    Igor Pavlov
7//              Lasse Collin
8//
9//  This file has been put into the public domain.
10//  You can do whatever you want with this file.
11//
12///////////////////////////////////////////////////////////////////////////////
13
14#ifndef LZMA_LZ_ENCODER_H
15#define LZMA_LZ_ENCODER_H
16
17#include "common.h"
18
19
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))
26
27
28/// A table of these is used by the LZ-based encoder to hold
29/// the length-distance pairs found by the match finder.
30typedef struct {
31	uint32_t len;
32	uint32_t dist;
33} lzma_match;
34
35
36typedef struct lzma_mf_s lzma_mf;
37struct lzma_mf_s {
38	///////////////
39	// In Window //
40	///////////////
41
42	/// Pointer to buffer with data to be compressed
43	uint8_t *buffer;
44
45	/// Total size of the allocated buffer (that is, including all
46	/// the extra space)
47	uint32_t size;
48
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;
54
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;
60
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.
66	uint32_t offset;
67
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.
71	uint32_t read_pos;
72
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.
75	uint32_t read_ahead;
76
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.
79	///
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.
83	uint32_t read_limit;
84
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].
88	uint32_t write_pos;
89
90	/// Number of bytes not hashed before read_pos. This is needed to
91	/// restart the match finder after LZMA_SYNC_FLUSH.
92	uint32_t pending;
93
94	//////////////////
95	// Match Finder //
96	//////////////////
97
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);
101
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);
106
107	uint32_t *hash;
108	uint32_t *son;
109	uint32_t cyclic_pos;
110	uint32_t cyclic_size; // Must be dictionary size + 1.
111	uint32_t hash_mask;
112
113	/// Maximum number of loops in the match finder
114	uint32_t depth;
115
116	/// Maximum length of a match that the match finder will try to find.
117	uint32_t nice_len;
118
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;
123
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.
127	lzma_action action;
128
129	/// Number of elements in hash[]
130	uint32_t hash_count;
131
132	/// Number of elements in son[]
133	uint32_t sons_count;
134};
135
136
137typedef struct {
138	/// Extra amount of data to keep available before the "actual"
139	/// dictionary.
140	size_t before_size;
141
142	/// Size of the history buffer
143	size_t dict_size;
144
145	/// Extra amount of data to keep available after the "actual"
146	/// dictionary.
147	size_t after_size;
148
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;
153
154	/// Match finder will search matches up to this length.
155	/// This must be less than or equal to match_len_max.
156	size_t nice_len;
157
158	/// Type of the match finder to use
159	lzma_match_finder match_finder;
160
161	/// Maximum search depth
162	uint32_t depth;
163
164	/// TODO: Comment
165	const uint8_t *preset_dict;
166
167	uint32_t preset_dict_size;
168
169} lzma_lz_options;
170
171
172// The total usable buffer space at any moment outside the match finder:
173// before_size + dict_size + after_size + match_len_max
174//
175// In reality, there's some extra space allocated to prevent the number of
176// memmove() calls reasonable. The bigger the dict_size is, the bigger
177// this extra buffer will be since with bigger dictionaries memmove() would
178// also take longer.
179//
180// A single encoder loop in the LZ-based encoder may call the match finder
181// (mf_find() or mf_skip()) at most after_size times. In other words,
182// a single encoder loop may increment lzma_mf.read_pos at most after_size
183// times. Since matches are looked up to
184// lzma_mf.buffer[lzma_mf.read_pos + match_len_max - 1], the total
185// amount of extra buffer needed after dict_size becomes
186// after_size + match_len_max.
187//
188// before_size has two uses. The first one is to keep literals available
189// in cases when the LZ-based encoder has made some read ahead.
190// TODO: Maybe this could be changed by making the LZ-based encoders to
191// store the actual literals as they do with length-distance pairs.
192//
193// Algorithms such as LZMA2 first try to compress a chunk, and then check
194// if the encoded result is smaller than the uncompressed one. If the chunk
195// was incompressible, it is better to store it in uncompressed form in
196// the output stream. To do this, the whole uncompressed chunk has to be
197// still available in the history buffer. before_size achieves that.
198
199
200typedef struct {
201	/// Data specific to the LZ-based encoder
202	void *coder;
203
204	/// Function to encode from *dict to out[]
205	lzma_ret (*code)(void *coder,
206			lzma_mf *restrict mf, uint8_t *restrict out,
207			size_t *restrict out_pos, size_t out_size);
208
209	/// Free allocated resources
210	void (*end)(void *coder, const lzma_allocator *allocator);
211
212	/// Update the options in the middle of the encoding.
213	lzma_ret (*options_update)(void *coder, const lzma_filter *filter);
214
215	/// Set maximum allowed output size
216	lzma_ret (*set_out_limit)(void *coder, uint64_t *uncomp_size,
217			uint64_t out_limit);
218
219} lzma_lz_encoder;
220
221
222// Basic steps:
223//  1. Input gets copied into the dictionary.
224//  2. Data in dictionary gets run through the match finder byte by byte.
225//  3. The literals and matches are encoded using e.g. LZMA.
226//
227// The bytes that have been ran through the match finder, but not encoded yet,
228// are called `read ahead'.
229
230
231/// Get how many bytes the match finder hashes in its initial step.
232/// This is also the minimum nice_len value with the match finder.
233static inline uint32_t
234mf_get_hash_bytes(lzma_match_finder match_finder)
235{
236	return (uint32_t)match_finder & 0x0F;
237}
238
239
240/// Get pointer to the first byte not ran through the match finder
241static inline const uint8_t *
242mf_ptr(const lzma_mf *mf)
243{
244	return mf->buffer + mf->read_pos;
245}
246
247
248/// Get the number of bytes that haven't been ran through the match finder yet.
249static inline uint32_t
250mf_avail(const lzma_mf *mf)
251{
252	return mf->write_pos - mf->read_pos;
253}
254
255
256/// Get the number of bytes that haven't been encoded yet (some of these
257/// bytes may have been ran through the match finder though).
258static inline uint32_t
259mf_unencoded(const lzma_mf *mf)
260{
261	return mf->write_pos - mf->read_pos + mf->read_ahead;
262}
263
264
265/// Calculate the absolute offset from the beginning of the most recent
266/// dictionary reset. Only the lowest four bits are important, so there's no
267/// problem that we don't know the 64-bit size of the data encoded so far.
268///
269/// NOTE: When moving the input window, we need to do it so that the lowest
270/// bits of dict->read_pos are not modified to keep this macro working
271/// as intended.
272static inline uint32_t
273mf_position(const lzma_mf *mf)
274{
275	return mf->read_pos - mf->read_ahead;
276}
277
278
279/// Since everything else begins with mf_, use it also for lzma_mf_find().
280#define mf_find lzma_mf_find
281
282
283/// Skip the given number of bytes. This is used when a good match was found.
284/// For example, if mf_find() finds a match of 200 bytes long, the first byte
285/// of that match was already consumed by mf_find(), and the rest 199 bytes
286/// have to be skipped with mf_skip(mf, 199).
287static inline void
288mf_skip(lzma_mf *mf, uint32_t amount)
289{
290	if (amount != 0) {
291		mf->skip(mf, amount);
292		mf->read_ahead += amount;
293	}
294}
295
296
297/// Copies at most *left number of bytes from the history buffer
298/// to out[]. This is needed by LZMA2 to encode uncompressed chunks.
299static inline void
300mf_read(lzma_mf *mf, uint8_t *out, size_t *out_pos, size_t out_size,
301		size_t *left)
302{
303	const size_t out_avail = out_size - *out_pos;
304	const size_t copy_size = my_min(out_avail, *left);
305
306	assert(mf->read_ahead == 0);
307	assert(mf->read_pos >= *left);
308
309	memcpy(out + *out_pos, mf->buffer + mf->read_pos - *left,
310			copy_size);
311
312	*out_pos += copy_size;
313	*left -= copy_size;
314	return;
315}
316
317
318extern lzma_ret lzma_lz_encoder_init(
319		lzma_next_coder *next, const lzma_allocator *allocator,
320		const lzma_filter_info *filters,
321		lzma_ret (*lz_init)(lzma_lz_encoder *lz,
322			const lzma_allocator *allocator,
323			lzma_vli id, const void *options,
324			lzma_lz_options *lz_options));
325
326
327extern uint64_t lzma_lz_encoder_memusage(const lzma_lz_options *lz_options);
328
329
330// These are only for LZ encoder's internal use.
331extern uint32_t lzma_mf_find(
332		lzma_mf *mf, uint32_t *count, lzma_match *matches);
333
334extern uint32_t lzma_mf_hc3_find(lzma_mf *dict, lzma_match *matches);
335extern void lzma_mf_hc3_skip(lzma_mf *dict, uint32_t amount);
336
337extern uint32_t lzma_mf_hc4_find(lzma_mf *dict, lzma_match *matches);
338extern void lzma_mf_hc4_skip(lzma_mf *dict, uint32_t amount);
339
340extern uint32_t lzma_mf_bt2_find(lzma_mf *dict, lzma_match *matches);
341extern void lzma_mf_bt2_skip(lzma_mf *dict, uint32_t amount);
342
343extern uint32_t lzma_mf_bt3_find(lzma_mf *dict, lzma_match *matches);
344extern void lzma_mf_bt3_skip(lzma_mf *dict, uint32_t amount);
345
346extern uint32_t lzma_mf_bt4_find(lzma_mf *dict, lzma_match *matches);
347extern void lzma_mf_bt4_skip(lzma_mf *dict, uint32_t amount);
348
349#endif
350