1///////////////////////////////////////////////////////////////////////////////
2//
3/// \file lz_encoder.c
4/// \brief LZ in window
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 "lz_encoder_hash.h"
16
17// See lz_encoder_hash.h. This is a bit hackish but avoids making
18// endianness a conditional in makefiles.
19#if defined(WORDS_BIGENDIAN) && !defined(HAVE_SMALL)
20# include "lz_encoder_hash_table.h"
21#endif
22
23#include "memcmplen.h"
24
25
| 1///////////////////////////////////////////////////////////////////////////////
2//
3/// \file lz_encoder.c
4/// \brief LZ in window
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 "lz_encoder_hash.h"
16
17// See lz_encoder_hash.h. This is a bit hackish but avoids making
18// endianness a conditional in makefiles.
19#if defined(WORDS_BIGENDIAN) && !defined(HAVE_SMALL)
20# include "lz_encoder_hash_table.h"
21#endif
22
23#include "memcmplen.h"
24
25
|
26struct lzma_coder_s {
| 26typedef struct {
|
27 /// LZ-based encoder e.g. LZMA
28 lzma_lz_encoder lz;
29
30 /// History buffer and match finder
31 lzma_mf mf;
32
33 /// Next coder in the chain
34 lzma_next_coder next;
| 27 /// LZ-based encoder e.g. LZMA
28 lzma_lz_encoder lz;
29
30 /// History buffer and match finder
31 lzma_mf mf;
32
33 /// Next coder in the chain
34 lzma_next_coder next;
|
35};
| 35} lzma_coder;
|
36
37
38/// \brief Moves the data in the input window to free space for new data
39///
40/// mf->buffer is a sliding input window, which keeps mf->keep_size_before
41/// bytes of input history available all the time. Now and then we need to
42/// "slide" the buffer to make space for the new data to the end of the
43/// buffer. At the same time, data older than keep_size_before is dropped.
44///
45static void
46move_window(lzma_mf *mf)
47{
48 // Align the move to a multiple of 16 bytes. Some LZ-based encoders
49 // like LZMA use the lowest bits of mf->read_pos to know the
50 // alignment of the uncompressed data. We also get better speed
51 // for memmove() with aligned buffers.
52 assert(mf->read_pos > mf->keep_size_before);
53 const uint32_t move_offset
54 = (mf->read_pos - mf->keep_size_before) & ~UINT32_C(15);
55
56 assert(mf->write_pos > move_offset);
57 const size_t move_size = mf->write_pos - move_offset;
58
59 assert(move_offset + move_size <= mf->size);
60
61 memmove(mf->buffer, mf->buffer + move_offset, move_size);
62
63 mf->offset += move_offset;
64 mf->read_pos -= move_offset;
65 mf->read_limit -= move_offset;
66 mf->write_pos -= move_offset;
67
68 return;
69}
70
71
72/// \brief Tries to fill the input window (mf->buffer)
73///
74/// If we are the last encoder in the chain, our input data is in in[].
75/// Otherwise we call the next filter in the chain to process in[] and
76/// write its output to mf->buffer.
77///
78/// This function must not be called once it has returned LZMA_STREAM_END.
79///
80static lzma_ret
81fill_window(lzma_coder *coder, const lzma_allocator *allocator,
82 const uint8_t *in, size_t *in_pos, size_t in_size,
83 lzma_action action)
84{
85 assert(coder->mf.read_pos <= coder->mf.write_pos);
86
87 // Move the sliding window if needed.
88 if (coder->mf.read_pos >= coder->mf.size - coder->mf.keep_size_after)
89 move_window(&coder->mf);
90
91 // Maybe this is ugly, but lzma_mf uses uint32_t for most things
92 // (which I find cleanest), but we need size_t here when filling
93 // the history window.
94 size_t write_pos = coder->mf.write_pos;
95 lzma_ret ret;
96 if (coder->next.code == NULL) {
97 // Not using a filter, simply memcpy() as much as possible.
98 lzma_bufcpy(in, in_pos, in_size, coder->mf.buffer,
99 &write_pos, coder->mf.size);
100
101 ret = action != LZMA_RUN && *in_pos == in_size
102 ? LZMA_STREAM_END : LZMA_OK;
103
104 } else {
105 ret = coder->next.code(coder->next.coder, allocator,
106 in, in_pos, in_size,
107 coder->mf.buffer, &write_pos,
108 coder->mf.size, action);
109 }
110
111 coder->mf.write_pos = write_pos;
112
113 // Silence Valgrind. lzma_memcmplen() can read extra bytes
114 // and Valgrind will give warnings if those bytes are uninitialized
115 // because Valgrind cannot see that the values of the uninitialized
116 // bytes are eventually ignored.
117 memzero(coder->mf.buffer + write_pos, LZMA_MEMCMPLEN_EXTRA);
118
119 // If end of stream has been reached or flushing completed, we allow
120 // the encoder to process all the input (that is, read_pos is allowed
121 // to reach write_pos). Otherwise we keep keep_size_after bytes
122 // available as prebuffer.
123 if (ret == LZMA_STREAM_END) {
124 assert(*in_pos == in_size);
125 ret = LZMA_OK;
126 coder->mf.action = action;
127 coder->mf.read_limit = coder->mf.write_pos;
128
129 } else if (coder->mf.write_pos > coder->mf.keep_size_after) {
130 // This needs to be done conditionally, because if we got
131 // only little new input, there may be too little input
132 // to do any encoding yet.
133 coder->mf.read_limit = coder->mf.write_pos
134 - coder->mf.keep_size_after;
135 }
136
137 // Restart the match finder after finished LZMA_SYNC_FLUSH.
138 if (coder->mf.pending > 0
139 && coder->mf.read_pos < coder->mf.read_limit) {
140 // Match finder may update coder->pending and expects it to
141 // start from zero, so use a temporary variable.
142 const uint32_t pending = coder->mf.pending;
143 coder->mf.pending = 0;
144
145 // Rewind read_pos so that the match finder can hash
146 // the pending bytes.
147 assert(coder->mf.read_pos >= pending);
148 coder->mf.read_pos -= pending;
149
150 // Call the skip function directly instead of using
151 // mf_skip(), since we don't want to touch mf->read_ahead.
152 coder->mf.skip(&coder->mf, pending);
153 }
154
155 return ret;
156}
157
158
159static lzma_ret
| 36
37
38/// \brief Moves the data in the input window to free space for new data
39///
40/// mf->buffer is a sliding input window, which keeps mf->keep_size_before
41/// bytes of input history available all the time. Now and then we need to
42/// "slide" the buffer to make space for the new data to the end of the
43/// buffer. At the same time, data older than keep_size_before is dropped.
44///
45static void
46move_window(lzma_mf *mf)
47{
48 // Align the move to a multiple of 16 bytes. Some LZ-based encoders
49 // like LZMA use the lowest bits of mf->read_pos to know the
50 // alignment of the uncompressed data. We also get better speed
51 // for memmove() with aligned buffers.
52 assert(mf->read_pos > mf->keep_size_before);
53 const uint32_t move_offset
54 = (mf->read_pos - mf->keep_size_before) & ~UINT32_C(15);
55
56 assert(mf->write_pos > move_offset);
57 const size_t move_size = mf->write_pos - move_offset;
58
59 assert(move_offset + move_size <= mf->size);
60
61 memmove(mf->buffer, mf->buffer + move_offset, move_size);
62
63 mf->offset += move_offset;
64 mf->read_pos -= move_offset;
65 mf->read_limit -= move_offset;
66 mf->write_pos -= move_offset;
67
68 return;
69}
70
71
72/// \brief Tries to fill the input window (mf->buffer)
73///
74/// If we are the last encoder in the chain, our input data is in in[].
75/// Otherwise we call the next filter in the chain to process in[] and
76/// write its output to mf->buffer.
77///
78/// This function must not be called once it has returned LZMA_STREAM_END.
79///
80static lzma_ret
81fill_window(lzma_coder *coder, const lzma_allocator *allocator,
82 const uint8_t *in, size_t *in_pos, size_t in_size,
83 lzma_action action)
84{
85 assert(coder->mf.read_pos <= coder->mf.write_pos);
86
87 // Move the sliding window if needed.
88 if (coder->mf.read_pos >= coder->mf.size - coder->mf.keep_size_after)
89 move_window(&coder->mf);
90
91 // Maybe this is ugly, but lzma_mf uses uint32_t for most things
92 // (which I find cleanest), but we need size_t here when filling
93 // the history window.
94 size_t write_pos = coder->mf.write_pos;
95 lzma_ret ret;
96 if (coder->next.code == NULL) {
97 // Not using a filter, simply memcpy() as much as possible.
98 lzma_bufcpy(in, in_pos, in_size, coder->mf.buffer,
99 &write_pos, coder->mf.size);
100
101 ret = action != LZMA_RUN && *in_pos == in_size
102 ? LZMA_STREAM_END : LZMA_OK;
103
104 } else {
105 ret = coder->next.code(coder->next.coder, allocator,
106 in, in_pos, in_size,
107 coder->mf.buffer, &write_pos,
108 coder->mf.size, action);
109 }
110
111 coder->mf.write_pos = write_pos;
112
113 // Silence Valgrind. lzma_memcmplen() can read extra bytes
114 // and Valgrind will give warnings if those bytes are uninitialized
115 // because Valgrind cannot see that the values of the uninitialized
116 // bytes are eventually ignored.
117 memzero(coder->mf.buffer + write_pos, LZMA_MEMCMPLEN_EXTRA);
118
119 // If end of stream has been reached or flushing completed, we allow
120 // the encoder to process all the input (that is, read_pos is allowed
121 // to reach write_pos). Otherwise we keep keep_size_after bytes
122 // available as prebuffer.
123 if (ret == LZMA_STREAM_END) {
124 assert(*in_pos == in_size);
125 ret = LZMA_OK;
126 coder->mf.action = action;
127 coder->mf.read_limit = coder->mf.write_pos;
128
129 } else if (coder->mf.write_pos > coder->mf.keep_size_after) {
130 // This needs to be done conditionally, because if we got
131 // only little new input, there may be too little input
132 // to do any encoding yet.
133 coder->mf.read_limit = coder->mf.write_pos
134 - coder->mf.keep_size_after;
135 }
136
137 // Restart the match finder after finished LZMA_SYNC_FLUSH.
138 if (coder->mf.pending > 0
139 && coder->mf.read_pos < coder->mf.read_limit) {
140 // Match finder may update coder->pending and expects it to
141 // start from zero, so use a temporary variable.
142 const uint32_t pending = coder->mf.pending;
143 coder->mf.pending = 0;
144
145 // Rewind read_pos so that the match finder can hash
146 // the pending bytes.
147 assert(coder->mf.read_pos >= pending);
148 coder->mf.read_pos -= pending;
149
150 // Call the skip function directly instead of using
151 // mf_skip(), since we don't want to touch mf->read_ahead.
152 coder->mf.skip(&coder->mf, pending);
153 }
154
155 return ret;
156}
157
158
159static lzma_ret
|
160lz_encode(lzma_coder *coder, const lzma_allocator *allocator,
| 160lz_encode(void *coder_ptr, const lzma_allocator *allocator,
|
161 const uint8_t *restrict in, size_t *restrict in_pos,
162 size_t in_size,
163 uint8_t *restrict out, size_t *restrict out_pos,
164 size_t out_size, lzma_action action)
165{
| 161 const uint8_t *restrict in, size_t *restrict in_pos,
162 size_t in_size,
163 uint8_t *restrict out, size_t *restrict out_pos,
164 size_t out_size, lzma_action action)
165{
|
| 166 lzma_coder *coder = coder_ptr;
167
|
166 while (*out_pos < out_size
167 && (*in_pos < in_size || action != LZMA_RUN)) {
168 // Read more data to coder->mf.buffer if needed.
169 if (coder->mf.action == LZMA_RUN && coder->mf.read_pos
170 >= coder->mf.read_limit)
171 return_if_error(fill_window(coder, allocator,
172 in, in_pos, in_size, action));
173
174 // Encode
175 const lzma_ret ret = coder->lz.code(coder->lz.coder,
176 &coder->mf, out, out_pos, out_size);
177 if (ret != LZMA_OK) {
178 // Setting this to LZMA_RUN for cases when we are
179 // flushing. It doesn't matter when finishing or if
180 // an error occurred.
181 coder->mf.action = LZMA_RUN;
182 return ret;
183 }
184 }
185
186 return LZMA_OK;
187}
188
189
190static bool
191lz_encoder_prepare(lzma_mf *mf, const lzma_allocator *allocator,
192 const lzma_lz_options *lz_options)
193{
194 // For now, the dictionary size is limited to 1.5 GiB. This may grow
195 // in the future if needed, but it needs a little more work than just
196 // changing this check.
197 if (lz_options->dict_size < LZMA_DICT_SIZE_MIN
198 || lz_options->dict_size
199 > (UINT32_C(1) << 30) + (UINT32_C(1) << 29)
200 || lz_options->nice_len > lz_options->match_len_max)
201 return true;
202
203 mf->keep_size_before = lz_options->before_size + lz_options->dict_size;
204
205 mf->keep_size_after = lz_options->after_size
206 + lz_options->match_len_max;
207
208 // To avoid constant memmove()s, allocate some extra space. Since
209 // memmove()s become more expensive when the size of the buffer
210 // increases, we reserve more space when a large dictionary is
211 // used to make the memmove() calls rarer.
212 //
213 // This works with dictionaries up to about 3 GiB. If bigger
214 // dictionary is wanted, some extra work is needed:
215 // - Several variables in lzma_mf have to be changed from uint32_t
216 // to size_t.
217 // - Memory usage calculation needs something too, e.g. use uint64_t
218 // for mf->size.
219 uint32_t reserve = lz_options->dict_size / 2;
220 if (reserve > (UINT32_C(1) << 30))
221 reserve /= 2;
222
223 reserve += (lz_options->before_size + lz_options->match_len_max
224 + lz_options->after_size) / 2 + (UINT32_C(1) << 19);
225
226 const uint32_t old_size = mf->size;
227 mf->size = mf->keep_size_before + reserve + mf->keep_size_after;
228
229 // Deallocate the old history buffer if it exists but has different
230 // size than what is needed now.
231 if (mf->buffer != NULL && old_size != mf->size) {
232 lzma_free(mf->buffer, allocator);
233 mf->buffer = NULL;
234 }
235
236 // Match finder options
237 mf->match_len_max = lz_options->match_len_max;
238 mf->nice_len = lz_options->nice_len;
239
240 // cyclic_size has to stay smaller than 2 Gi. Note that this doesn't
241 // mean limiting dictionary size to less than 2 GiB. With a match
242 // finder that uses multibyte resolution (hashes start at e.g. every
243 // fourth byte), cyclic_size would stay below 2 Gi even when
244 // dictionary size is greater than 2 GiB.
245 //
246 // It would be possible to allow cyclic_size >= 2 Gi, but then we
247 // would need to be careful to use 64-bit types in various places
248 // (size_t could do since we would need bigger than 32-bit address
249 // space anyway). It would also require either zeroing a multigigabyte
250 // buffer at initialization (waste of time and RAM) or allow
251 // normalization in lz_encoder_mf.c to access uninitialized
252 // memory to keep the code simpler. The current way is simple and
253 // still allows pretty big dictionaries, so I don't expect these
254 // limits to change.
255 mf->cyclic_size = lz_options->dict_size + 1;
256
257 // Validate the match finder ID and setup the function pointers.
258 switch (lz_options->match_finder) {
259#ifdef HAVE_MF_HC3
260 case LZMA_MF_HC3:
261 mf->find = &lzma_mf_hc3_find;
262 mf->skip = &lzma_mf_hc3_skip;
263 break;
264#endif
265#ifdef HAVE_MF_HC4
266 case LZMA_MF_HC4:
267 mf->find = &lzma_mf_hc4_find;
268 mf->skip = &lzma_mf_hc4_skip;
269 break;
270#endif
271#ifdef HAVE_MF_BT2
272 case LZMA_MF_BT2:
273 mf->find = &lzma_mf_bt2_find;
274 mf->skip = &lzma_mf_bt2_skip;
275 break;
276#endif
277#ifdef HAVE_MF_BT3
278 case LZMA_MF_BT3:
279 mf->find = &lzma_mf_bt3_find;
280 mf->skip = &lzma_mf_bt3_skip;
281 break;
282#endif
283#ifdef HAVE_MF_BT4
284 case LZMA_MF_BT4:
285 mf->find = &lzma_mf_bt4_find;
286 mf->skip = &lzma_mf_bt4_skip;
287 break;
288#endif
289
290 default:
291 return true;
292 }
293
294 // Calculate the sizes of mf->hash and mf->son and check that
295 // nice_len is big enough for the selected match finder.
296 const uint32_t hash_bytes = lz_options->match_finder & 0x0F;
297 if (hash_bytes > mf->nice_len)
298 return true;
299
300 const bool is_bt = (lz_options->match_finder & 0x10) != 0;
301 uint32_t hs;
302
303 if (hash_bytes == 2) {
304 hs = 0xFFFF;
305 } else {
306 // Round dictionary size up to the next 2^n - 1 so it can
307 // be used as a hash mask.
308 hs = lz_options->dict_size - 1;
309 hs |= hs >> 1;
310 hs |= hs >> 2;
311 hs |= hs >> 4;
312 hs |= hs >> 8;
313 hs >>= 1;
314 hs |= 0xFFFF;
315
316 if (hs > (UINT32_C(1) << 24)) {
317 if (hash_bytes == 3)
318 hs = (UINT32_C(1) << 24) - 1;
319 else
320 hs >>= 1;
321 }
322 }
323
324 mf->hash_mask = hs;
325
326 ++hs;
327 if (hash_bytes > 2)
328 hs += HASH_2_SIZE;
329 if (hash_bytes > 3)
330 hs += HASH_3_SIZE;
331/*
332 No match finder uses this at the moment.
333 if (mf->hash_bytes > 4)
334 hs += HASH_4_SIZE;
335*/
336
337 const uint32_t old_hash_count = mf->hash_count;
338 const uint32_t old_sons_count = mf->sons_count;
339 mf->hash_count = hs;
340 mf->sons_count = mf->cyclic_size;
341 if (is_bt)
342 mf->sons_count *= 2;
343
344 // Deallocate the old hash array if it exists and has different size
345 // than what is needed now.
346 if (old_hash_count != mf->hash_count
347 || old_sons_count != mf->sons_count) {
348 lzma_free(mf->hash, allocator);
349 mf->hash = NULL;
350
351 lzma_free(mf->son, allocator);
352 mf->son = NULL;
353 }
354
355 // Maximum number of match finder cycles
356 mf->depth = lz_options->depth;
357 if (mf->depth == 0) {
358 if (is_bt)
359 mf->depth = 16 + mf->nice_len / 2;
360 else
361 mf->depth = 4 + mf->nice_len / 4;
362 }
363
364 return false;
365}
366
367
368static bool
369lz_encoder_init(lzma_mf *mf, const lzma_allocator *allocator,
370 const lzma_lz_options *lz_options)
371{
372 // Allocate the history buffer.
373 if (mf->buffer == NULL) {
374 // lzma_memcmplen() is used for the dictionary buffer
375 // so we need to allocate a few extra bytes to prevent
376 // it from reading past the end of the buffer.
377 mf->buffer = lzma_alloc(mf->size + LZMA_MEMCMPLEN_EXTRA,
378 allocator);
379 if (mf->buffer == NULL)
380 return true;
381
382 // Keep Valgrind happy with lzma_memcmplen() and initialize
383 // the extra bytes whose value may get read but which will
384 // effectively get ignored.
385 memzero(mf->buffer + mf->size, LZMA_MEMCMPLEN_EXTRA);
386 }
387
388 // Use cyclic_size as initial mf->offset. This allows
389 // avoiding a few branches in the match finders. The downside is
390 // that match finder needs to be normalized more often, which may
391 // hurt performance with huge dictionaries.
392 mf->offset = mf->cyclic_size;
393 mf->read_pos = 0;
394 mf->read_ahead = 0;
395 mf->read_limit = 0;
396 mf->write_pos = 0;
397 mf->pending = 0;
398
399#if UINT32_MAX >= SIZE_MAX / 4
400 // Check for integer overflow. (Huge dictionaries are not
401 // possible on 32-bit CPU.)
402 if (mf->hash_count > SIZE_MAX / sizeof(uint32_t)
403 || mf->sons_count > SIZE_MAX / sizeof(uint32_t))
404 return true;
405#endif
406
407 // Allocate and initialize the hash table. Since EMPTY_HASH_VALUE
408 // is zero, we can use lzma_alloc_zero() or memzero() for mf->hash.
409 //
410 // We don't need to initialize mf->son, but not doing that may
411 // make Valgrind complain in normalization (see normalize() in
412 // lz_encoder_mf.c). Skipping the initialization is *very* good
413 // when big dictionary is used but only small amount of data gets
414 // actually compressed: most of the mf->son won't get actually
415 // allocated by the kernel, so we avoid wasting RAM and improve
416 // initialization speed a lot.
417 if (mf->hash == NULL) {
418 mf->hash = lzma_alloc_zero(mf->hash_count * sizeof(uint32_t),
419 allocator);
420 mf->son = lzma_alloc(mf->sons_count * sizeof(uint32_t),
421 allocator);
422
423 if (mf->hash == NULL || mf->son == NULL) {
424 lzma_free(mf->hash, allocator);
425 mf->hash = NULL;
426
427 lzma_free(mf->son, allocator);
428 mf->son = NULL;
429
430 return true;
431 }
432 } else {
433/*
434 for (uint32_t i = 0; i < mf->hash_count; ++i)
435 mf->hash[i] = EMPTY_HASH_VALUE;
436*/
437 memzero(mf->hash, mf->hash_count * sizeof(uint32_t));
438 }
439
440 mf->cyclic_pos = 0;
441
442 // Handle preset dictionary.
443 if (lz_options->preset_dict != NULL
444 && lz_options->preset_dict_size > 0) {
445 // If the preset dictionary is bigger than the actual
446 // dictionary, use only the tail.
447 mf->write_pos = my_min(lz_options->preset_dict_size, mf->size);
448 memcpy(mf->buffer, lz_options->preset_dict
449 + lz_options->preset_dict_size - mf->write_pos,
450 mf->write_pos);
451 mf->action = LZMA_SYNC_FLUSH;
452 mf->skip(mf, mf->write_pos);
453 }
454
455 mf->action = LZMA_RUN;
456
457 return false;
458}
459
460
461extern uint64_t
462lzma_lz_encoder_memusage(const lzma_lz_options *lz_options)
463{
464 // Old buffers must not exist when calling lz_encoder_prepare().
465 lzma_mf mf = {
466 .buffer = NULL,
467 .hash = NULL,
468 .son = NULL,
469 .hash_count = 0,
470 .sons_count = 0,
471 };
472
473 // Setup the size information into mf.
474 if (lz_encoder_prepare(&mf, NULL, lz_options))
475 return UINT64_MAX;
476
477 // Calculate the memory usage.
478 return ((uint64_t)(mf.hash_count) + mf.sons_count) * sizeof(uint32_t)
479 + mf.size + sizeof(lzma_coder);
480}
481
482
483static void
| 168 while (*out_pos < out_size
169 && (*in_pos < in_size || action != LZMA_RUN)) {
170 // Read more data to coder->mf.buffer if needed.
171 if (coder->mf.action == LZMA_RUN && coder->mf.read_pos
172 >= coder->mf.read_limit)
173 return_if_error(fill_window(coder, allocator,
174 in, in_pos, in_size, action));
175
176 // Encode
177 const lzma_ret ret = coder->lz.code(coder->lz.coder,
178 &coder->mf, out, out_pos, out_size);
179 if (ret != LZMA_OK) {
180 // Setting this to LZMA_RUN for cases when we are
181 // flushing. It doesn't matter when finishing or if
182 // an error occurred.
183 coder->mf.action = LZMA_RUN;
184 return ret;
185 }
186 }
187
188 return LZMA_OK;
189}
190
191
192static bool
193lz_encoder_prepare(lzma_mf *mf, const lzma_allocator *allocator,
194 const lzma_lz_options *lz_options)
195{
196 // For now, the dictionary size is limited to 1.5 GiB. This may grow
197 // in the future if needed, but it needs a little more work than just
198 // changing this check.
199 if (lz_options->dict_size < LZMA_DICT_SIZE_MIN
200 || lz_options->dict_size
201 > (UINT32_C(1) << 30) + (UINT32_C(1) << 29)
202 || lz_options->nice_len > lz_options->match_len_max)
203 return true;
204
205 mf->keep_size_before = lz_options->before_size + lz_options->dict_size;
206
207 mf->keep_size_after = lz_options->after_size
208 + lz_options->match_len_max;
209
210 // To avoid constant memmove()s, allocate some extra space. Since
211 // memmove()s become more expensive when the size of the buffer
212 // increases, we reserve more space when a large dictionary is
213 // used to make the memmove() calls rarer.
214 //
215 // This works with dictionaries up to about 3 GiB. If bigger
216 // dictionary is wanted, some extra work is needed:
217 // - Several variables in lzma_mf have to be changed from uint32_t
218 // to size_t.
219 // - Memory usage calculation needs something too, e.g. use uint64_t
220 // for mf->size.
221 uint32_t reserve = lz_options->dict_size / 2;
222 if (reserve > (UINT32_C(1) << 30))
223 reserve /= 2;
224
225 reserve += (lz_options->before_size + lz_options->match_len_max
226 + lz_options->after_size) / 2 + (UINT32_C(1) << 19);
227
228 const uint32_t old_size = mf->size;
229 mf->size = mf->keep_size_before + reserve + mf->keep_size_after;
230
231 // Deallocate the old history buffer if it exists but has different
232 // size than what is needed now.
233 if (mf->buffer != NULL && old_size != mf->size) {
234 lzma_free(mf->buffer, allocator);
235 mf->buffer = NULL;
236 }
237
238 // Match finder options
239 mf->match_len_max = lz_options->match_len_max;
240 mf->nice_len = lz_options->nice_len;
241
242 // cyclic_size has to stay smaller than 2 Gi. Note that this doesn't
243 // mean limiting dictionary size to less than 2 GiB. With a match
244 // finder that uses multibyte resolution (hashes start at e.g. every
245 // fourth byte), cyclic_size would stay below 2 Gi even when
246 // dictionary size is greater than 2 GiB.
247 //
248 // It would be possible to allow cyclic_size >= 2 Gi, but then we
249 // would need to be careful to use 64-bit types in various places
250 // (size_t could do since we would need bigger than 32-bit address
251 // space anyway). It would also require either zeroing a multigigabyte
252 // buffer at initialization (waste of time and RAM) or allow
253 // normalization in lz_encoder_mf.c to access uninitialized
254 // memory to keep the code simpler. The current way is simple and
255 // still allows pretty big dictionaries, so I don't expect these
256 // limits to change.
257 mf->cyclic_size = lz_options->dict_size + 1;
258
259 // Validate the match finder ID and setup the function pointers.
260 switch (lz_options->match_finder) {
261#ifdef HAVE_MF_HC3
262 case LZMA_MF_HC3:
263 mf->find = &lzma_mf_hc3_find;
264 mf->skip = &lzma_mf_hc3_skip;
265 break;
266#endif
267#ifdef HAVE_MF_HC4
268 case LZMA_MF_HC4:
269 mf->find = &lzma_mf_hc4_find;
270 mf->skip = &lzma_mf_hc4_skip;
271 break;
272#endif
273#ifdef HAVE_MF_BT2
274 case LZMA_MF_BT2:
275 mf->find = &lzma_mf_bt2_find;
276 mf->skip = &lzma_mf_bt2_skip;
277 break;
278#endif
279#ifdef HAVE_MF_BT3
280 case LZMA_MF_BT3:
281 mf->find = &lzma_mf_bt3_find;
282 mf->skip = &lzma_mf_bt3_skip;
283 break;
284#endif
285#ifdef HAVE_MF_BT4
286 case LZMA_MF_BT4:
287 mf->find = &lzma_mf_bt4_find;
288 mf->skip = &lzma_mf_bt4_skip;
289 break;
290#endif
291
292 default:
293 return true;
294 }
295
296 // Calculate the sizes of mf->hash and mf->son and check that
297 // nice_len is big enough for the selected match finder.
298 const uint32_t hash_bytes = lz_options->match_finder & 0x0F;
299 if (hash_bytes > mf->nice_len)
300 return true;
301
302 const bool is_bt = (lz_options->match_finder & 0x10) != 0;
303 uint32_t hs;
304
305 if (hash_bytes == 2) {
306 hs = 0xFFFF;
307 } else {
308 // Round dictionary size up to the next 2^n - 1 so it can
309 // be used as a hash mask.
310 hs = lz_options->dict_size - 1;
311 hs |= hs >> 1;
312 hs |= hs >> 2;
313 hs |= hs >> 4;
314 hs |= hs >> 8;
315 hs >>= 1;
316 hs |= 0xFFFF;
317
318 if (hs > (UINT32_C(1) << 24)) {
319 if (hash_bytes == 3)
320 hs = (UINT32_C(1) << 24) - 1;
321 else
322 hs >>= 1;
323 }
324 }
325
326 mf->hash_mask = hs;
327
328 ++hs;
329 if (hash_bytes > 2)
330 hs += HASH_2_SIZE;
331 if (hash_bytes > 3)
332 hs += HASH_3_SIZE;
333/*
334 No match finder uses this at the moment.
335 if (mf->hash_bytes > 4)
336 hs += HASH_4_SIZE;
337*/
338
339 const uint32_t old_hash_count = mf->hash_count;
340 const uint32_t old_sons_count = mf->sons_count;
341 mf->hash_count = hs;
342 mf->sons_count = mf->cyclic_size;
343 if (is_bt)
344 mf->sons_count *= 2;
345
346 // Deallocate the old hash array if it exists and has different size
347 // than what is needed now.
348 if (old_hash_count != mf->hash_count
349 || old_sons_count != mf->sons_count) {
350 lzma_free(mf->hash, allocator);
351 mf->hash = NULL;
352
353 lzma_free(mf->son, allocator);
354 mf->son = NULL;
355 }
356
357 // Maximum number of match finder cycles
358 mf->depth = lz_options->depth;
359 if (mf->depth == 0) {
360 if (is_bt)
361 mf->depth = 16 + mf->nice_len / 2;
362 else
363 mf->depth = 4 + mf->nice_len / 4;
364 }
365
366 return false;
367}
368
369
370static bool
371lz_encoder_init(lzma_mf *mf, const lzma_allocator *allocator,
372 const lzma_lz_options *lz_options)
373{
374 // Allocate the history buffer.
375 if (mf->buffer == NULL) {
376 // lzma_memcmplen() is used for the dictionary buffer
377 // so we need to allocate a few extra bytes to prevent
378 // it from reading past the end of the buffer.
379 mf->buffer = lzma_alloc(mf->size + LZMA_MEMCMPLEN_EXTRA,
380 allocator);
381 if (mf->buffer == NULL)
382 return true;
383
384 // Keep Valgrind happy with lzma_memcmplen() and initialize
385 // the extra bytes whose value may get read but which will
386 // effectively get ignored.
387 memzero(mf->buffer + mf->size, LZMA_MEMCMPLEN_EXTRA);
388 }
389
390 // Use cyclic_size as initial mf->offset. This allows
391 // avoiding a few branches in the match finders. The downside is
392 // that match finder needs to be normalized more often, which may
393 // hurt performance with huge dictionaries.
394 mf->offset = mf->cyclic_size;
395 mf->read_pos = 0;
396 mf->read_ahead = 0;
397 mf->read_limit = 0;
398 mf->write_pos = 0;
399 mf->pending = 0;
400
401#if UINT32_MAX >= SIZE_MAX / 4
402 // Check for integer overflow. (Huge dictionaries are not
403 // possible on 32-bit CPU.)
404 if (mf->hash_count > SIZE_MAX / sizeof(uint32_t)
405 || mf->sons_count > SIZE_MAX / sizeof(uint32_t))
406 return true;
407#endif
408
409 // Allocate and initialize the hash table. Since EMPTY_HASH_VALUE
410 // is zero, we can use lzma_alloc_zero() or memzero() for mf->hash.
411 //
412 // We don't need to initialize mf->son, but not doing that may
413 // make Valgrind complain in normalization (see normalize() in
414 // lz_encoder_mf.c). Skipping the initialization is *very* good
415 // when big dictionary is used but only small amount of data gets
416 // actually compressed: most of the mf->son won't get actually
417 // allocated by the kernel, so we avoid wasting RAM and improve
418 // initialization speed a lot.
419 if (mf->hash == NULL) {
420 mf->hash = lzma_alloc_zero(mf->hash_count * sizeof(uint32_t),
421 allocator);
422 mf->son = lzma_alloc(mf->sons_count * sizeof(uint32_t),
423 allocator);
424
425 if (mf->hash == NULL || mf->son == NULL) {
426 lzma_free(mf->hash, allocator);
427 mf->hash = NULL;
428
429 lzma_free(mf->son, allocator);
430 mf->son = NULL;
431
432 return true;
433 }
434 } else {
435/*
436 for (uint32_t i = 0; i < mf->hash_count; ++i)
437 mf->hash[i] = EMPTY_HASH_VALUE;
438*/
439 memzero(mf->hash, mf->hash_count * sizeof(uint32_t));
440 }
441
442 mf->cyclic_pos = 0;
443
444 // Handle preset dictionary.
445 if (lz_options->preset_dict != NULL
446 && lz_options->preset_dict_size > 0) {
447 // If the preset dictionary is bigger than the actual
448 // dictionary, use only the tail.
449 mf->write_pos = my_min(lz_options->preset_dict_size, mf->size);
450 memcpy(mf->buffer, lz_options->preset_dict
451 + lz_options->preset_dict_size - mf->write_pos,
452 mf->write_pos);
453 mf->action = LZMA_SYNC_FLUSH;
454 mf->skip(mf, mf->write_pos);
455 }
456
457 mf->action = LZMA_RUN;
458
459 return false;
460}
461
462
463extern uint64_t
464lzma_lz_encoder_memusage(const lzma_lz_options *lz_options)
465{
466 // Old buffers must not exist when calling lz_encoder_prepare().
467 lzma_mf mf = {
468 .buffer = NULL,
469 .hash = NULL,
470 .son = NULL,
471 .hash_count = 0,
472 .sons_count = 0,
473 };
474
475 // Setup the size information into mf.
476 if (lz_encoder_prepare(&mf, NULL, lz_options))
477 return UINT64_MAX;
478
479 // Calculate the memory usage.
480 return ((uint64_t)(mf.hash_count) + mf.sons_count) * sizeof(uint32_t)
481 + mf.size + sizeof(lzma_coder);
482}
483
484
485static void
|
484lz_encoder_end(lzma_coder *coder, const lzma_allocator *allocator)
| 486lz_encoder_end(void *coder_ptr, const lzma_allocator *allocator)
|
485{
| 487{
|
| 488 lzma_coder *coder = coder_ptr;
489
|
486 lzma_next_end(&coder->next, allocator);
487
488 lzma_free(coder->mf.son, allocator);
489 lzma_free(coder->mf.hash, allocator);
490 lzma_free(coder->mf.buffer, allocator);
491
492 if (coder->lz.end != NULL)
493 coder->lz.end(coder->lz.coder, allocator);
494 else
495 lzma_free(coder->lz.coder, allocator);
496
497 lzma_free(coder, allocator);
498 return;
499}
500
501
502static lzma_ret
| 490 lzma_next_end(&coder->next, allocator);
491
492 lzma_free(coder->mf.son, allocator);
493 lzma_free(coder->mf.hash, allocator);
494 lzma_free(coder->mf.buffer, allocator);
495
496 if (coder->lz.end != NULL)
497 coder->lz.end(coder->lz.coder, allocator);
498 else
499 lzma_free(coder->lz.coder, allocator);
500
501 lzma_free(coder, allocator);
502 return;
503}
504
505
506static lzma_ret
|
503lz_encoder_update(lzma_coder *coder, const lzma_allocator *allocator,
| 507lz_encoder_update(void *coder_ptr, const lzma_allocator *allocator,
|
504 const lzma_filter *filters_null lzma_attribute((__unused__)),
505 const lzma_filter *reversed_filters)
506{
| 508 const lzma_filter *filters_null lzma_attribute((__unused__)),
509 const lzma_filter *reversed_filters)
510{
|
| 511 lzma_coder *coder = coder_ptr;
512
|
507 if (coder->lz.options_update == NULL)
508 return LZMA_PROG_ERROR;
509
510 return_if_error(coder->lz.options_update(
511 coder->lz.coder, reversed_filters));
512
513 return lzma_next_filter_update(
514 &coder->next, allocator, reversed_filters + 1);
515}
516
517
518extern lzma_ret
519lzma_lz_encoder_init(lzma_next_coder *next, const lzma_allocator *allocator,
520 const lzma_filter_info *filters,
521 lzma_ret (*lz_init)(lzma_lz_encoder *lz,
522 const lzma_allocator *allocator, const void *options,
523 lzma_lz_options *lz_options))
524{
525#ifdef HAVE_SMALL
526 // We need that the CRC32 table has been initialized.
527 lzma_crc32_init();
528#endif
529
530 // Allocate and initialize the base data structure.
| 513 if (coder->lz.options_update == NULL)
514 return LZMA_PROG_ERROR;
515
516 return_if_error(coder->lz.options_update(
517 coder->lz.coder, reversed_filters));
518
519 return lzma_next_filter_update(
520 &coder->next, allocator, reversed_filters + 1);
521}
522
523
524extern lzma_ret
525lzma_lz_encoder_init(lzma_next_coder *next, const lzma_allocator *allocator,
526 const lzma_filter_info *filters,
527 lzma_ret (*lz_init)(lzma_lz_encoder *lz,
528 const lzma_allocator *allocator, const void *options,
529 lzma_lz_options *lz_options))
530{
531#ifdef HAVE_SMALL
532 // We need that the CRC32 table has been initialized.
533 lzma_crc32_init();
534#endif
535
536 // Allocate and initialize the base data structure.
|
531 if (next->coder == NULL) {
532 next->coder = lzma_alloc(sizeof(lzma_coder), allocator);
533 if (next->coder == NULL)
| 537 lzma_coder *coder = next->coder;
538 if (coder == NULL) {
539 coder = lzma_alloc(sizeof(lzma_coder), allocator);
540 if (coder == NULL)
|
534 return LZMA_MEM_ERROR;
535
| 541 return LZMA_MEM_ERROR;
542
|
| 543 next->coder = coder;
|
536 next->code = &lz_encode;
537 next->end = &lz_encoder_end;
538 next->update = &lz_encoder_update;
539
| 544 next->code = &lz_encode;
545 next->end = &lz_encoder_end;
546 next->update = &lz_encoder_update;
547
|
540 next->coder->lz.coder = NULL;
541 next->coder->lz.code = NULL;
542 next->coder->lz.end = NULL;
| 548 coder->lz.coder = NULL;
549 coder->lz.code = NULL;
550 coder->lz.end = NULL;
|
543
| 551
|
544 next->coder->mf.buffer = NULL;
545 next->coder->mf.hash = NULL;
546 next->coder->mf.son = NULL;
547 next->coder->mf.hash_count = 0;
548 next->coder->mf.sons_count = 0;
| 552 // mf.size is initialized to silence Valgrind
553 // when used on optimized binaries (GCC may reorder
554 // code in a way that Valgrind gets unhappy).
555 coder->mf.buffer = NULL;
556 coder->mf.size = 0;
557 coder->mf.hash = NULL;
558 coder->mf.son = NULL;
559 coder->mf.hash_count = 0;
560 coder->mf.sons_count = 0;
|
549
| 561
|
550 next->coder->next = LZMA_NEXT_CODER_INIT;
| 562 coder->next = LZMA_NEXT_CODER_INIT;
|
551 }
552
553 // Initialize the LZ-based encoder.
554 lzma_lz_options lz_options;
| 563 }
564
565 // Initialize the LZ-based encoder.
566 lzma_lz_options lz_options;
|
555 return_if_error(lz_init(&next->coder->lz, allocator,
| 567 return_if_error(lz_init(&coder->lz, allocator,
|
556 filters[0].options, &lz_options));
557
| 568 filters[0].options, &lz_options));
569
|
558 // Setup the size information into next->coder->mf and deallocate
| 570 // Setup the size information into coder->mf and deallocate
|
559 // old buffers if they have wrong size.
| 571 // old buffers if they have wrong size.
|
560 if (lz_encoder_prepare(&next->coder->mf, allocator, &lz_options))
| 572 if (lz_encoder_prepare(&coder->mf, allocator, &lz_options))
|
561 return LZMA_OPTIONS_ERROR;
562
563 // Allocate new buffers if needed, and do the rest of
564 // the initialization.
| 573 return LZMA_OPTIONS_ERROR;
574
575 // Allocate new buffers if needed, and do the rest of
576 // the initialization.
|
565 if (lz_encoder_init(&next->coder->mf, allocator, &lz_options))
| 577 if (lz_encoder_init(&coder->mf, allocator, &lz_options))
|
566 return LZMA_MEM_ERROR;
567
568 // Initialize the next filter in the chain, if any.
| 578 return LZMA_MEM_ERROR;
579
580 // Initialize the next filter in the chain, if any.
|
569 return lzma_next_filter_init(&next->coder->next, allocator,
570 filters + 1);
| 581 return lzma_next_filter_init(&coder->next, allocator, filters + 1);
|
571}
572
573
574extern LZMA_API(lzma_bool)
575lzma_mf_is_supported(lzma_match_finder mf)
576{
577 bool ret = false;
578
579#ifdef HAVE_MF_HC3
580 if (mf == LZMA_MF_HC3)
581 ret = true;
582#endif
583
584#ifdef HAVE_MF_HC4
585 if (mf == LZMA_MF_HC4)
586 ret = true;
587#endif
588
589#ifdef HAVE_MF_BT2
590 if (mf == LZMA_MF_BT2)
591 ret = true;
592#endif
593
594#ifdef HAVE_MF_BT3
595 if (mf == LZMA_MF_BT3)
596 ret = true;
597#endif
598
599#ifdef HAVE_MF_BT4
600 if (mf == LZMA_MF_BT4)
601 ret = true;
602#endif
603
604 return ret;
605}
| 582}
583
584
585extern LZMA_API(lzma_bool)
586lzma_mf_is_supported(lzma_match_finder mf)
587{
588 bool ret = false;
589
590#ifdef HAVE_MF_HC3
591 if (mf == LZMA_MF_HC3)
592 ret = true;
593#endif
594
595#ifdef HAVE_MF_HC4
596 if (mf == LZMA_MF_HC4)
597 ret = true;
598#endif
599
600#ifdef HAVE_MF_BT2
601 if (mf == LZMA_MF_BT2)
602 ret = true;
603#endif
604
605#ifdef HAVE_MF_BT3
606 if (mf == LZMA_MF_BT3)
607 ret = true;
608#endif
609
610#ifdef HAVE_MF_BT4
611 if (mf == LZMA_MF_BT4)
612 ret = true;
613#endif
614
615 return ret;
616}
|