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