1 ///////////////////////////////////////////////////////////////////////////////
4 /// \brief LZ in window
6 // Copyright (C) 1999-2008 Igor Pavlov
7 // Copyright (C) 2007-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 #include "lz_encoder.h"
22 #include "lz_encoder_hash.h"
26 /// LZ-based encoder e.g. LZMA
29 /// History buffer and match finder
32 /// Next coder in the chain
37 /// \brief Moves the data in the input window to free space for new data
39 /// mf->buffer is a sliding input window, which keeps mf->keep_size_before
40 /// bytes of input history available all the time. Now and then we need to
41 /// "slide" the buffer to make space for the new data to the end of the
42 /// buffer. At the same time, data older than keep_size_before is dropped.
45 move_window(lzma_mf *mf)
47 // Align the move to a multiple of 16 bytes. Some LZ-based encoders
48 // like LZMA use the lowest bits of mf->read_pos to know the
49 // alignment of the uncompressed data. We also get better speed
50 // for memmove() with aligned buffers.
51 assert(mf->read_pos > mf->keep_size_before);
52 const uint32_t move_offset
53 = (mf->read_pos - mf->keep_size_before) & ~UINT32_C(15);
55 assert(mf->write_pos > move_offset);
56 const size_t move_size = mf->write_pos - move_offset;
58 assert(move_offset + move_size <= mf->size);
60 memmove(mf->buffer, mf->buffer + move_offset, move_size);
62 mf->offset += move_offset;
63 mf->read_pos -= move_offset;
64 mf->read_limit -= move_offset;
65 mf->write_pos -= move_offset;
71 /// \brief Tries to fill the input window (mf->buffer)
73 /// If we are the last encoder in the chain, our input data is in in[].
74 /// Otherwise we call the next filter in the chain to process in[] and
75 /// write its output to mf->buffer.
77 /// This function must not be called once it has returned LZMA_STREAM_END.
80 fill_window(lzma_coder *coder, lzma_allocator *allocator, const uint8_t *in,
81 size_t *in_pos, size_t in_size, lzma_action action)
83 assert(coder->mf.read_pos <= coder->mf.write_pos);
85 // Move the sliding window if needed.
86 if (coder->mf.read_pos >= coder->mf.size - coder->mf.keep_size_after)
87 move_window(&coder->mf);
89 // Maybe this is ugly, but lzma_mf uses uint32_t for most things
90 // (which I find cleanest), but we need size_t here when filling
91 // the history window.
92 size_t write_pos = coder->mf.write_pos;
95 if (coder->next.code == NULL) {
96 // Not using a filter, simply memcpy() as much as possible.
97 in_used = lzma_bufcpy(in, in_pos, in_size, coder->mf.buffer,
98 &write_pos, coder->mf.size);
100 ret = action != LZMA_RUN && *in_pos == in_size
101 ? LZMA_STREAM_END : LZMA_OK;
104 const size_t in_start = *in_pos;
105 ret = coder->next.code(coder->next.coder, allocator,
107 coder->mf.buffer, &write_pos,
108 coder->mf.size, action);
109 in_used = *in_pos - in_start;
112 coder->mf.write_pos = write_pos;
114 // If end of stream has been reached or flushing completed, we allow
115 // the encoder to process all the input (that is, read_pos is allowed
116 // to reach write_pos). Otherwise we keep keep_size_after bytes
117 // available as prebuffer.
118 if (ret == LZMA_STREAM_END) {
119 assert(*in_pos == in_size);
121 coder->mf.action = action;
122 coder->mf.read_limit = coder->mf.write_pos;
124 } else if (coder->mf.write_pos > coder->mf.keep_size_after) {
125 // This needs to be done conditionally, because if we got
126 // only little new input, there may be too little input
127 // to do any encoding yet.
128 coder->mf.read_limit = coder->mf.write_pos
129 - coder->mf.keep_size_after;
132 // Restart the match finder after finished LZMA_SYNC_FLUSH.
133 if (coder->mf.pending > 0
134 && coder->mf.read_pos < coder->mf.read_limit) {
135 // Match finder may update coder->pending and expects it to
136 // start from zero, so use a temporary variable.
137 const size_t pending = coder->mf.pending;
138 coder->mf.pending = 0;
140 // Rewind read_pos so that the match finder can hash
141 // the pending bytes.
142 assert(coder->mf.read_pos >= pending);
143 coder->mf.read_pos -= pending;
145 // Call the skip function directly instead of using
146 // mf_skip(), since we don't want to touch mf->read_ahead.
147 coder->mf.skip(&coder->mf, pending);
155 lz_encode(lzma_coder *coder, lzma_allocator *allocator,
156 const uint8_t *restrict in, size_t *restrict in_pos,
158 uint8_t *restrict out, size_t *restrict out_pos,
159 size_t out_size, lzma_action action)
161 while (*out_pos < out_size
162 && (*in_pos < in_size || action != LZMA_RUN)) {
163 // Read more data to coder->mf.buffer if needed.
164 if (coder->mf.action == LZMA_RUN && coder->mf.read_pos
165 >= coder->mf.read_limit)
166 return_if_error(fill_window(coder, allocator,
167 in, in_pos, in_size, action));
170 const lzma_ret ret = coder->lz.code(coder->lz.coder,
171 &coder->mf, out, out_pos, out_size);
172 if (ret != LZMA_OK) {
173 // Setting this to LZMA_RUN for cases when we are
174 // flushing. It doesn't matter when finishing or if
175 // an error occurred.
176 coder->mf.action = LZMA_RUN;
186 lz_encoder_prepare(lzma_mf *mf, lzma_allocator *allocator,
187 const lzma_lz_options *lz_options)
189 // For now, the dictionary size is limited to 1.5 GiB. This may grow
190 // in the future if needed, but it needs a little more work than just
191 // changing this check.
192 if (lz_options->dict_size < LZMA_DICT_SIZE_MIN
193 || lz_options->dict_size
194 > (UINT32_C(1) << 30) + (UINT32_C(1) << 29)
195 || lz_options->nice_len > lz_options->match_len_max)
198 mf->keep_size_before = lz_options->before_size + lz_options->dict_size;
200 mf->keep_size_after = lz_options->after_size
201 + lz_options->match_len_max;
203 // To avoid constant memmove()s, allocate some extra space. Since
204 // memmove()s become more expensive when the size of the buffer
205 // increases, we reserve more space when a large dictionary is
206 // used to make the memmove() calls rarer.
208 // This works with dictionaries up to about 3 GiB. If bigger
209 // dictionary is wanted, some extra work is needed:
210 // - Several variables in lzma_mf have to be changed from uint32_t
212 // - Memory usage calculation needs something too, e.g. use uint64_t
214 uint32_t reserve = lz_options->dict_size / 2;
215 if (reserve > (UINT32_C(1) << 30))
218 reserve += (lz_options->before_size + lz_options->match_len_max
219 + lz_options->after_size) / 2 + (UINT32_C(1) << 19);
221 const uint32_t old_size = mf->size;
222 mf->size = mf->keep_size_before + reserve + mf->keep_size_after;
224 // Deallocate the old history buffer if it exists but has different
225 // size than what is needed now.
226 if (mf->buffer != NULL && old_size != mf->size) {
227 lzma_free(mf->buffer, allocator);
231 // Match finder options
232 mf->match_len_max = lz_options->match_len_max;
233 mf->nice_len = lz_options->nice_len;
235 // cyclic_size has to stay smaller than 2 Gi. Note that this doesn't
236 // mean limitting dictionary size to less than 2 GiB. With a match
237 // finder that uses multibyte resolution (hashes start at e.g. every
238 // fourth byte), cyclic_size would stay below 2 Gi even when
239 // dictionary size is greater than 2 GiB.
241 // It would be possible to allow cyclic_size >= 2 Gi, but then we
242 // would need to be careful to use 64-bit types in various places
243 // (size_t could do since we would need bigger than 32-bit address
244 // space anyway). It would also require either zeroing a multigigabyte
245 // buffer at initialization (waste of time and RAM) or allow
246 // normalization in lz_encoder_mf.c to access uninitialized
247 // memory to keep the code simpler. The current way is simple and
248 // still allows pretty big dictionaries, so I don't expect these
250 mf->cyclic_size = lz_options->dict_size + 1;
252 // Validate the match finder ID and setup the function pointers.
253 switch (lz_options->match_finder) {
256 mf->find = &lzma_mf_hc3_find;
257 mf->skip = &lzma_mf_hc3_skip;
262 mf->find = &lzma_mf_hc4_find;
263 mf->skip = &lzma_mf_hc4_skip;
268 mf->find = &lzma_mf_bt2_find;
269 mf->skip = &lzma_mf_bt2_skip;
274 mf->find = &lzma_mf_bt3_find;
275 mf->skip = &lzma_mf_bt3_skip;
280 mf->find = &lzma_mf_bt4_find;
281 mf->skip = &lzma_mf_bt4_skip;
289 // Calculate the sizes of mf->hash and mf->son and check that
290 // nice_len is big enough for the selected match finder.
291 const uint32_t hash_bytes = lz_options->match_finder & 0x0F;
292 if (hash_bytes > mf->nice_len)
295 const bool is_bt = (lz_options->match_finder & 0x10) != 0;
298 if (hash_bytes == 2) {
301 // Round dictionary size up to the next 2^n - 1 so it can
302 // be used as a hash mask.
303 hs = lz_options->dict_size - 1;
311 if (hs > (UINT32_C(1) << 24)) {
313 hs = (UINT32_C(1) << 24) - 1;
327 No match finder uses this at the moment.
328 if (mf->hash_bytes > 4)
332 // If the above code calculating hs is modified, make sure that
333 // this assertion stays valid (UINT32_MAX / 5 is not strictly the
334 // exact limit). If it doesn't, you need to calculate that
335 // hash_size_sum + sons_count cannot overflow.
336 assert(hs < UINT32_MAX / 5);
338 const uint32_t old_count = mf->hash_size_sum + mf->sons_count;
339 mf->hash_size_sum = hs;
340 mf->sons_count = mf->cyclic_size;
344 const uint32_t new_count = mf->hash_size_sum + mf->sons_count;
346 // Deallocate the old hash array if it exists and has different size
347 // than what is needed now.
348 if (mf->hash != NULL && old_count != new_count) {
349 lzma_free(mf->hash, allocator);
353 // Maximum number of match finder cycles
354 mf->depth = lz_options->depth;
355 if (mf->depth == 0) {
356 mf->depth = 16 + (mf->nice_len / 2);
366 lz_encoder_init(lzma_mf *mf, lzma_allocator *allocator,
367 const lzma_lz_options *lz_options)
369 // Allocate the history buffer.
370 if (mf->buffer == NULL) {
371 mf->buffer = lzma_alloc(mf->size, allocator);
372 if (mf->buffer == NULL)
376 // Use cyclic_size as initial mf->offset. This allows
377 // avoiding a few branches in the match finders. The downside is
378 // that match finder needs to be normalized more often, which may
379 // hurt performance with huge dictionaries.
380 mf->offset = mf->cyclic_size;
387 // Allocate match finder's hash array.
388 const size_t alloc_count = mf->hash_size_sum + mf->sons_count;
390 #if UINT32_MAX >= SIZE_MAX / 4
391 // Check for integer overflow. (Huge dictionaries are not
392 // possible on 32-bit CPU.)
393 if (alloc_count > SIZE_MAX / sizeof(uint32_t))
397 if (mf->hash == NULL) {
398 mf->hash = lzma_alloc(alloc_count * sizeof(uint32_t),
400 if (mf->hash == NULL)
404 mf->son = mf->hash + mf->hash_size_sum;
407 // Initialize the hash table. Since EMPTY_HASH_VALUE is zero, we
410 for (uint32_t i = 0; i < hash_size_sum; ++i)
411 mf->hash[i] = EMPTY_HASH_VALUE;
413 memzero(mf->hash, (size_t)(mf->hash_size_sum) * sizeof(uint32_t));
415 // We don't need to initialize mf->son, but not doing that will
416 // make Valgrind complain in normalization (see normalize() in
419 // Skipping this initialization is *very* good when big dictionary is
420 // used but only small amount of data gets actually compressed: most
421 // of the mf->hash won't get actually allocated by the kernel, so
422 // we avoid wasting RAM and improve initialization speed a lot.
423 //memzero(mf->son, (size_t)(mf->sons_count) * sizeof(uint32_t));
425 // Handle preset dictionary.
426 if (lz_options->preset_dict != NULL
427 && lz_options->preset_dict_size > 0) {
428 // If the preset dictionary is bigger than the actual
429 // dictionary, use only the tail.
430 mf->write_pos = MIN(lz_options->preset_dict_size, mf->size);
431 memcpy(mf->buffer, lz_options->preset_dict
432 + lz_options->preset_dict_size - mf->write_pos,
434 mf->action = LZMA_SYNC_FLUSH;
435 mf->skip(mf, mf->write_pos);
438 mf->action = LZMA_RUN;
445 lzma_lz_encoder_memusage(const lzma_lz_options *lz_options)
447 // Old buffers must not exist when calling lz_encoder_prepare().
453 // Setup the size information into mf.
454 if (lz_encoder_prepare(&mf, NULL, lz_options))
457 // Calculate the memory usage.
458 return (uint64_t)(mf.hash_size_sum + mf.sons_count)
460 + (uint64_t)(mf.size) + sizeof(lzma_coder);
465 lz_encoder_end(lzma_coder *coder, lzma_allocator *allocator)
467 lzma_next_end(&coder->next, allocator);
469 lzma_free(coder->mf.hash, allocator);
470 lzma_free(coder->mf.buffer, allocator);
472 if (coder->lz.end != NULL)
473 coder->lz.end(coder->lz.coder, allocator);
475 lzma_free(coder->lz.coder, allocator);
477 lzma_free(coder, allocator);
483 lzma_lz_encoder_init(lzma_next_coder *next, lzma_allocator *allocator,
484 const lzma_filter_info *filters,
485 lzma_ret (*lz_init)(lzma_lz_encoder *lz,
486 lzma_allocator *allocator, const void *options,
487 lzma_lz_options *lz_options))
490 // We need that the CRC32 table has been initialized.
491 // This is enough to do it.
492 lzma_crc32(NULL, 0, 0);
495 // Allocate and initialize the base data structure.
496 if (next->coder == NULL) {
497 next->coder = lzma_alloc(sizeof(lzma_coder), allocator);
498 if (next->coder == NULL)
499 return LZMA_MEM_ERROR;
501 next->code = &lz_encode;
502 next->end = &lz_encoder_end;
504 next->coder->lz.coder = NULL;
505 next->coder->lz.code = NULL;
506 next->coder->lz.end = NULL;
508 next->coder->mf.buffer = NULL;
509 next->coder->mf.hash = NULL;
511 next->coder->next = LZMA_NEXT_CODER_INIT;
514 // Initialize the LZ-based encoder.
515 lzma_lz_options lz_options;
516 return_if_error(lz_init(&next->coder->lz, allocator,
517 filters[0].options, &lz_options));
519 // Setup the size information into next->coder->mf and deallocate
520 // old buffers if they have wrong size.
521 if (lz_encoder_prepare(&next->coder->mf, allocator, &lz_options))
522 return LZMA_OPTIONS_ERROR;
524 // Allocate new buffers if needed, and do the rest of
525 // the initialization.
526 if (lz_encoder_init(&next->coder->mf, allocator, &lz_options))
527 return LZMA_MEM_ERROR;
529 // Initialize the next filter in the chain, if any.
530 return lzma_next_filter_init(&next->coder->next, allocator,
535 extern LZMA_API(lzma_bool)
536 lzma_mf_is_supported(lzma_match_finder mf)
541 if (mf == LZMA_MF_HC3)
546 if (mf == LZMA_MF_HC4)
551 if (mf == LZMA_MF_BT2)
556 if (mf == LZMA_MF_BT3)
561 if (mf == LZMA_MF_BT4)