xref: /freebsd/contrib/xz/src/liblzma/lzma/lzma2_encoder.c (revision 9f23cbd6cae82fd77edfad7173432fa8dccd0a95)
1 ///////////////////////////////////////////////////////////////////////////////
2 //
3 /// \file       lzma2_encoder.c
4 /// \brief      LZMA2 encoder
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 #include "lz_encoder.h"
15 #include "lzma_encoder.h"
16 #include "fastpos.h"
17 #include "lzma2_encoder.h"
18 
19 
20 typedef struct {
21 	enum {
22 		SEQ_INIT,
23 		SEQ_LZMA_ENCODE,
24 		SEQ_LZMA_COPY,
25 		SEQ_UNCOMPRESSED_HEADER,
26 		SEQ_UNCOMPRESSED_COPY,
27 	} sequence;
28 
29 	/// LZMA encoder
30 	void *lzma;
31 
32 	/// LZMA options currently in use.
33 	lzma_options_lzma opt_cur;
34 
35 	bool need_properties;
36 	bool need_state_reset;
37 	bool need_dictionary_reset;
38 
39 	/// Uncompressed size of a chunk
40 	size_t uncompressed_size;
41 
42 	/// Compressed size of a chunk (excluding headers); this is also used
43 	/// to indicate the end of buf[] in SEQ_LZMA_COPY.
44 	size_t compressed_size;
45 
46 	/// Read position in buf[]
47 	size_t buf_pos;
48 
49 	/// Buffer to hold the chunk header and LZMA compressed data
50 	uint8_t buf[LZMA2_HEADER_MAX + LZMA2_CHUNK_MAX];
51 } lzma_lzma2_coder;
52 
53 
54 static void
55 lzma2_header_lzma(lzma_lzma2_coder *coder)
56 {
57 	assert(coder->uncompressed_size > 0);
58 	assert(coder->uncompressed_size <= LZMA2_UNCOMPRESSED_MAX);
59 	assert(coder->compressed_size > 0);
60 	assert(coder->compressed_size <= LZMA2_CHUNK_MAX);
61 
62 	size_t pos;
63 
64 	if (coder->need_properties) {
65 		pos = 0;
66 
67 		if (coder->need_dictionary_reset)
68 			coder->buf[pos] = 0x80 + (3 << 5);
69 		else
70 			coder->buf[pos] = 0x80 + (2 << 5);
71 	} else {
72 		pos = 1;
73 
74 		if (coder->need_state_reset)
75 			coder->buf[pos] = 0x80 + (1 << 5);
76 		else
77 			coder->buf[pos] = 0x80;
78 	}
79 
80 	// Set the start position for copying.
81 	coder->buf_pos = pos;
82 
83 	// Uncompressed size
84 	size_t size = coder->uncompressed_size - 1;
85 	coder->buf[pos++] += size >> 16;
86 	coder->buf[pos++] = (size >> 8) & 0xFF;
87 	coder->buf[pos++] = size & 0xFF;
88 
89 	// Compressed size
90 	size = coder->compressed_size - 1;
91 	coder->buf[pos++] = size >> 8;
92 	coder->buf[pos++] = size & 0xFF;
93 
94 	// Properties, if needed
95 	if (coder->need_properties)
96 		lzma_lzma_lclppb_encode(&coder->opt_cur, coder->buf + pos);
97 
98 	coder->need_properties = false;
99 	coder->need_state_reset = false;
100 	coder->need_dictionary_reset = false;
101 
102 	// The copying code uses coder->compressed_size to indicate the end
103 	// of coder->buf[], so we need add the maximum size of the header here.
104 	coder->compressed_size += LZMA2_HEADER_MAX;
105 
106 	return;
107 }
108 
109 
110 static void
111 lzma2_header_uncompressed(lzma_lzma2_coder *coder)
112 {
113 	assert(coder->uncompressed_size > 0);
114 	assert(coder->uncompressed_size <= LZMA2_CHUNK_MAX);
115 
116 	// If this is the first chunk, we need to include dictionary
117 	// reset indicator.
118 	if (coder->need_dictionary_reset)
119 		coder->buf[0] = 1;
120 	else
121 		coder->buf[0] = 2;
122 
123 	coder->need_dictionary_reset = false;
124 
125 	// "Compressed" size
126 	coder->buf[1] = (coder->uncompressed_size - 1) >> 8;
127 	coder->buf[2] = (coder->uncompressed_size - 1) & 0xFF;
128 
129 	// Set the start position for copying.
130 	coder->buf_pos = 0;
131 	return;
132 }
133 
134 
135 static lzma_ret
136 lzma2_encode(void *coder_ptr, lzma_mf *restrict mf,
137 		uint8_t *restrict out, size_t *restrict out_pos,
138 		size_t out_size)
139 {
140 	lzma_lzma2_coder *restrict coder = coder_ptr;
141 
142 	while (*out_pos < out_size)
143 	switch (coder->sequence) {
144 	case SEQ_INIT:
145 		// If there's no input left and we are flushing or finishing,
146 		// don't start a new chunk.
147 		if (mf_unencoded(mf) == 0) {
148 			// Write end of payload marker if finishing.
149 			if (mf->action == LZMA_FINISH)
150 				out[(*out_pos)++] = 0;
151 
152 			return mf->action == LZMA_RUN
153 					? LZMA_OK : LZMA_STREAM_END;
154 		}
155 
156 		if (coder->need_state_reset)
157 			return_if_error(lzma_lzma_encoder_reset(
158 					coder->lzma, &coder->opt_cur));
159 
160 		coder->uncompressed_size = 0;
161 		coder->compressed_size = 0;
162 		coder->sequence = SEQ_LZMA_ENCODE;
163 
164 	// Fall through
165 
166 	case SEQ_LZMA_ENCODE: {
167 		// Calculate how much more uncompressed data this chunk
168 		// could accept.
169 		const uint32_t left = LZMA2_UNCOMPRESSED_MAX
170 				- coder->uncompressed_size;
171 		uint32_t limit;
172 
173 		if (left < mf->match_len_max) {
174 			// Must flush immediately since the next LZMA symbol
175 			// could make the uncompressed size of the chunk too
176 			// big.
177 			limit = 0;
178 		} else {
179 			// Calculate maximum read_limit that is OK from point
180 			// of view of LZMA2 chunk size.
181 			limit = mf->read_pos - mf->read_ahead
182 					+ left - mf->match_len_max;
183 		}
184 
185 		// Save the start position so that we can update
186 		// coder->uncompressed_size.
187 		const uint32_t read_start = mf->read_pos - mf->read_ahead;
188 
189 		// Call the LZMA encoder until the chunk is finished.
190 		const lzma_ret ret = lzma_lzma_encode(coder->lzma, mf,
191 				coder->buf + LZMA2_HEADER_MAX,
192 				&coder->compressed_size,
193 				LZMA2_CHUNK_MAX, limit);
194 
195 		coder->uncompressed_size += mf->read_pos - mf->read_ahead
196 				- read_start;
197 
198 		assert(coder->compressed_size <= LZMA2_CHUNK_MAX);
199 		assert(coder->uncompressed_size <= LZMA2_UNCOMPRESSED_MAX);
200 
201 		if (ret != LZMA_STREAM_END)
202 			return LZMA_OK;
203 
204 		// See if the chunk compressed. If it didn't, we encode it
205 		// as uncompressed chunk. This saves a few bytes of space
206 		// and makes decoding faster.
207 		if (coder->compressed_size >= coder->uncompressed_size) {
208 			coder->uncompressed_size += mf->read_ahead;
209 			assert(coder->uncompressed_size
210 					<= LZMA2_UNCOMPRESSED_MAX);
211 			mf->read_ahead = 0;
212 			lzma2_header_uncompressed(coder);
213 			coder->need_state_reset = true;
214 			coder->sequence = SEQ_UNCOMPRESSED_HEADER;
215 			break;
216 		}
217 
218 		// The chunk did compress at least by one byte, so we store
219 		// the chunk as LZMA.
220 		lzma2_header_lzma(coder);
221 
222 		coder->sequence = SEQ_LZMA_COPY;
223 	}
224 
225 	// Fall through
226 
227 	case SEQ_LZMA_COPY:
228 		// Copy the compressed chunk along its headers to the
229 		// output buffer.
230 		lzma_bufcpy(coder->buf, &coder->buf_pos,
231 				coder->compressed_size,
232 				out, out_pos, out_size);
233 		if (coder->buf_pos != coder->compressed_size)
234 			return LZMA_OK;
235 
236 		coder->sequence = SEQ_INIT;
237 		break;
238 
239 	case SEQ_UNCOMPRESSED_HEADER:
240 		// Copy the three-byte header to indicate uncompressed chunk.
241 		lzma_bufcpy(coder->buf, &coder->buf_pos,
242 				LZMA2_HEADER_UNCOMPRESSED,
243 				out, out_pos, out_size);
244 		if (coder->buf_pos != LZMA2_HEADER_UNCOMPRESSED)
245 			return LZMA_OK;
246 
247 		coder->sequence = SEQ_UNCOMPRESSED_COPY;
248 
249 	// Fall through
250 
251 	case SEQ_UNCOMPRESSED_COPY:
252 		// Copy the uncompressed data as is from the dictionary
253 		// to the output buffer.
254 		mf_read(mf, out, out_pos, out_size, &coder->uncompressed_size);
255 		if (coder->uncompressed_size != 0)
256 			return LZMA_OK;
257 
258 		coder->sequence = SEQ_INIT;
259 		break;
260 	}
261 
262 	return LZMA_OK;
263 }
264 
265 
266 static void
267 lzma2_encoder_end(void *coder_ptr, const lzma_allocator *allocator)
268 {
269 	lzma_lzma2_coder *coder = coder_ptr;
270 	lzma_free(coder->lzma, allocator);
271 	lzma_free(coder, allocator);
272 	return;
273 }
274 
275 
276 static lzma_ret
277 lzma2_encoder_options_update(void *coder_ptr, const lzma_filter *filter)
278 {
279 	lzma_lzma2_coder *coder = coder_ptr;
280 
281 	// New options can be set only when there is no incomplete chunk.
282 	// This is the case at the beginning of the raw stream and right
283 	// after LZMA_SYNC_FLUSH.
284 	if (filter->options == NULL || coder->sequence != SEQ_INIT)
285 		return LZMA_PROG_ERROR;
286 
287 	// Look if there are new options. At least for now,
288 	// only lc/lp/pb can be changed.
289 	const lzma_options_lzma *opt = filter->options;
290 	if (coder->opt_cur.lc != opt->lc || coder->opt_cur.lp != opt->lp
291 			|| coder->opt_cur.pb != opt->pb) {
292 		// Validate the options.
293 		if (opt->lc > LZMA_LCLP_MAX || opt->lp > LZMA_LCLP_MAX
294 				|| opt->lc + opt->lp > LZMA_LCLP_MAX
295 				|| opt->pb > LZMA_PB_MAX)
296 			return LZMA_OPTIONS_ERROR;
297 
298 		// The new options will be used when the encoder starts
299 		// a new LZMA2 chunk.
300 		coder->opt_cur.lc = opt->lc;
301 		coder->opt_cur.lp = opt->lp;
302 		coder->opt_cur.pb = opt->pb;
303 		coder->need_properties = true;
304 		coder->need_state_reset = true;
305 	}
306 
307 	return LZMA_OK;
308 }
309 
310 
311 static lzma_ret
312 lzma2_encoder_init(lzma_lz_encoder *lz, const lzma_allocator *allocator,
313 		lzma_vli id lzma_attribute((__unused__)), const void *options,
314 		lzma_lz_options *lz_options)
315 {
316 	if (options == NULL)
317 		return LZMA_PROG_ERROR;
318 
319 	lzma_lzma2_coder *coder = lz->coder;
320 	if (coder == NULL) {
321 		coder = lzma_alloc(sizeof(lzma_lzma2_coder), allocator);
322 		if (coder == NULL)
323 			return LZMA_MEM_ERROR;
324 
325 		lz->coder = coder;
326 		lz->code = &lzma2_encode;
327 		lz->end = &lzma2_encoder_end;
328 		lz->options_update = &lzma2_encoder_options_update;
329 
330 		coder->lzma = NULL;
331 	}
332 
333 	coder->opt_cur = *(const lzma_options_lzma *)(options);
334 
335 	coder->sequence = SEQ_INIT;
336 	coder->need_properties = true;
337 	coder->need_state_reset = false;
338 	coder->need_dictionary_reset
339 			= coder->opt_cur.preset_dict == NULL
340 			|| coder->opt_cur.preset_dict_size == 0;
341 
342 	// Initialize LZMA encoder
343 	return_if_error(lzma_lzma_encoder_create(&coder->lzma, allocator,
344 			LZMA_FILTER_LZMA2, &coder->opt_cur, lz_options));
345 
346 	// Make sure that we will always have enough history available in
347 	// case we need to use uncompressed chunks. They are used when the
348 	// compressed size of a chunk is not smaller than the uncompressed
349 	// size, so we need to have at least LZMA2_COMPRESSED_MAX bytes
350 	// history available.
351 	if (lz_options->before_size + lz_options->dict_size < LZMA2_CHUNK_MAX)
352 		lz_options->before_size
353 				= LZMA2_CHUNK_MAX - lz_options->dict_size;
354 
355 	return LZMA_OK;
356 }
357 
358 
359 extern lzma_ret
360 lzma_lzma2_encoder_init(lzma_next_coder *next, const lzma_allocator *allocator,
361 		const lzma_filter_info *filters)
362 {
363 	return lzma_lz_encoder_init(
364 			next, allocator, filters, &lzma2_encoder_init);
365 }
366 
367 
368 extern uint64_t
369 lzma_lzma2_encoder_memusage(const void *options)
370 {
371 	const uint64_t lzma_mem = lzma_lzma_encoder_memusage(options);
372 	if (lzma_mem == UINT64_MAX)
373 		return UINT64_MAX;
374 
375 	return sizeof(lzma_lzma2_coder) + lzma_mem;
376 }
377 
378 
379 extern lzma_ret
380 lzma_lzma2_props_encode(const void *options, uint8_t *out)
381 {
382 	if (options == NULL)
383 		return LZMA_PROG_ERROR;
384 
385 	const lzma_options_lzma *const opt = options;
386 	uint32_t d = my_max(opt->dict_size, LZMA_DICT_SIZE_MIN);
387 
388 	// Round up to the next 2^n - 1 or 2^n + 2^(n - 1) - 1 depending
389 	// on which one is the next:
390 	--d;
391 	d |= d >> 2;
392 	d |= d >> 3;
393 	d |= d >> 4;
394 	d |= d >> 8;
395 	d |= d >> 16;
396 
397 	// Get the highest two bits using the proper encoding:
398 	if (d == UINT32_MAX)
399 		out[0] = 40;
400 	else
401 		out[0] = get_dist_slot(d + 1) - 24;
402 
403 	return LZMA_OK;
404 }
405 
406 
407 extern uint64_t
408 lzma_lzma2_block_size(const void *options)
409 {
410 	const lzma_options_lzma *const opt = options;
411 
412 	// Use at least 1 MiB to keep compression ratio better.
413 	return my_max((uint64_t)(opt->dict_size) * 3, UINT64_C(1) << 20);
414 }
415