?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Update THANKS
[xz/debian.git] / src / liblzma / lzma / lzma_encoder_optimum_normal.c
bloba6c0398f3af319efdb7017f37d4947133c4287d4
1 // SPDX-License-Identifier: 0BSD
2
3 ///////////////////////////////////////////////////////////////////////////////
4 //
5 /// \file lzma_encoder_optimum_normal.c
6 //
7 // Author: Igor Pavlov
8 //
9 ///////////////////////////////////////////////////////////////////////////////
10
11 #include "lzma_encoder_private.h"
12 #include "fastpos.h"
13 #include "memcmplen.h"
14
15
16 ////////////
17 // Prices //
18 ////////////
19
20 static uint32_t
21 get_literal_price(const lzma_lzma1_encoder *const coder, const uint32_t pos,
22 const uint32_t prev_byte, const bool match_mode,
23 uint32_t match_byte, uint32_t symbol)
24 {
25 const probability *const subcoder = literal_subcoder(coder->literal,
26 coder->literal_context_bits, coder->literal_mask,
27 pos, prev_byte);
28
29 uint32_t price = 0;
30
31 if (!match_mode) {
32 price = rc_bittree_price(subcoder, 8, symbol);
33 } else {
34 uint32_t offset = 0x100;
35 symbol += UINT32_C(1) << 8;
36
37 do {
38 match_byte <<= 1;
39
40 const uint32_t match_bit = match_byte & offset;
41 const uint32_t subcoder_index
42 = offset + match_bit + (symbol >> 8);
43 const uint32_t bit = (symbol >> 7) & 1;
44 price += rc_bit_price(subcoder[subcoder_index], bit);
45
46 symbol <<= 1;
47 offset &= ~(match_byte ^ symbol);
48
49 } while (symbol < (UINT32_C(1) << 16));
50 }
51
52 return price;
53 }
54
55
56 static inline uint32_t
57 get_len_price(const lzma_length_encoder *const lencoder,
58 const uint32_t len, const uint32_t pos_state)
59 {
60 // NOTE: Unlike the other price tables, length prices are updated
61 // in lzma_encoder.c
62 return lencoder->prices[pos_state][len - MATCH_LEN_MIN];
63 }
64
65
66 static inline uint32_t
67 get_short_rep_price(const lzma_lzma1_encoder *const coder,
68 const lzma_lzma_state state, const uint32_t pos_state)
69 {
70 return rc_bit_0_price(coder->is_rep0[state])
71 + rc_bit_0_price(coder->is_rep0_long[state][pos_state]);
72 }
73
74
75 static inline uint32_t
76 get_pure_rep_price(const lzma_lzma1_encoder *const coder, const uint32_t rep_index,
77 const lzma_lzma_state state, uint32_t pos_state)
78 {
79 uint32_t price;
80
81 if (rep_index == 0) {
82 price = rc_bit_0_price(coder->is_rep0[state]);
83 price += rc_bit_1_price(coder->is_rep0_long[state][pos_state]);
84 } else {
85 price = rc_bit_1_price(coder->is_rep0[state]);
86
87 if (rep_index == 1) {
88 price += rc_bit_0_price(coder->is_rep1[state]);
89 } else {
90 price += rc_bit_1_price(coder->is_rep1[state]);
91 price += rc_bit_price(coder->is_rep2[state],
92 rep_index - 2);
93 }
94 }
95
96 return price;
97 }
98
99
100 static inline uint32_t
101 get_rep_price(const lzma_lzma1_encoder *const coder, const uint32_t rep_index,
102 const uint32_t len, const lzma_lzma_state state,
103 const uint32_t pos_state)
104 {
105 return get_len_price(&coder->rep_len_encoder, len, pos_state)
106 + get_pure_rep_price(coder, rep_index, state, pos_state);
107 }
108
109
110 static inline uint32_t
111 get_dist_len_price(const lzma_lzma1_encoder *const coder, const uint32_t dist,
112 const uint32_t len, const uint32_t pos_state)
113 {
114 const uint32_t dist_state = get_dist_state(len);
115 uint32_t price;
116
117 if (dist < FULL_DISTANCES) {
118 price = coder->dist_prices[dist_state][dist];
119 } else {
120 const uint32_t dist_slot = get_dist_slot_2(dist);
121 price = coder->dist_slot_prices[dist_state][dist_slot]
122 + coder->align_prices[dist & ALIGN_MASK];
123 }
124
125 price += get_len_price(&coder->match_len_encoder, len, pos_state);
126
127 return price;
128 }
129
130
131 static void
132 fill_dist_prices(lzma_lzma1_encoder *coder)
133 {
134 for (uint32_t dist_state = 0; dist_state < DIST_STATES; ++dist_state) {
135
136 uint32_t *const dist_slot_prices
137 = coder->dist_slot_prices[dist_state];
138
139 // Price to encode the dist_slot.
140 for (uint32_t dist_slot = 0;
141 dist_slot < coder->dist_table_size; ++dist_slot)
142 dist_slot_prices[dist_slot] = rc_bittree_price(
143 coder->dist_slot[dist_state],
144 DIST_SLOT_BITS, dist_slot);
145
146 // For matches with distance >= FULL_DISTANCES, add the price
147 // of the direct bits part of the match distance. (Align bits
148 // are handled by fill_align_prices()).
149 for (uint32_t dist_slot = DIST_MODEL_END;
150 dist_slot < coder->dist_table_size;
151 ++dist_slot)
152 dist_slot_prices[dist_slot] += rc_direct_price(
153 ((dist_slot >> 1) - 1) - ALIGN_BITS);
154
155 // Distances in the range [0, 3] are fully encoded with
156 // dist_slot, so they are used for coder->dist_prices
157 // as is.
158 for (uint32_t i = 0; i < DIST_MODEL_START; ++i)
159 coder->dist_prices[dist_state][i]
160 = dist_slot_prices[i];
161 }
162
163 // Distances in the range [4, 127] depend on dist_slot and
164 // dist_special. We do this in a loop separate from the above
165 // loop to avoid redundant calls to get_dist_slot().
166 for (uint32_t i = DIST_MODEL_START; i < FULL_DISTANCES; ++i) {
167 const uint32_t dist_slot = get_dist_slot(i);
168 const uint32_t footer_bits = ((dist_slot >> 1) - 1);
169 const uint32_t base = (2 | (dist_slot & 1)) << footer_bits;
170 const uint32_t price = rc_bittree_reverse_price(
171 coder->dist_special + base - dist_slot - 1,
172 footer_bits, i - base);
173
174 for (uint32_t dist_state = 0; dist_state < DIST_STATES;
175 ++dist_state)
176 coder->dist_prices[dist_state][i]
177 = price + coder->dist_slot_prices[
178 dist_state][dist_slot];
179 }
180
181 coder->match_price_count = 0;
182 return;
183 }
184
185
186 static void
187 fill_align_prices(lzma_lzma1_encoder *coder)
188 {
189 for (uint32_t i = 0; i < ALIGN_SIZE; ++i)
190 coder->align_prices[i] = rc_bittree_reverse_price(
191 coder->dist_align, ALIGN_BITS, i);
192
193 coder->align_price_count = 0;
194 return;
195 }
196
197
198 /////////////
199 // Optimal //
200 /////////////
201
202 static inline void
203 make_literal(lzma_optimal *optimal)
204 {
205 optimal->back_prev = UINT32_MAX;
206 optimal->prev_1_is_literal = false;
207 }
208
209
210 static inline void
211 make_short_rep(lzma_optimal *optimal)
212 {
213 optimal->back_prev = 0;
214 optimal->prev_1_is_literal = false;
215 }
216
217
218 #define is_short_rep(optimal) \
219 ((optimal).back_prev == 0)
220
221
222 static void
223 backward(lzma_lzma1_encoder *restrict coder, uint32_t *restrict len_res,
224 uint32_t *restrict back_res, uint32_t cur)
225 {
226 coder->opts_end_index = cur;
227
228 uint32_t pos_mem = coder->opts[cur].pos_prev;
229 uint32_t back_mem = coder->opts[cur].back_prev;
230
231 do {
232 if (coder->opts[cur].prev_1_is_literal) {
233 make_literal(&coder->opts[pos_mem]);
234 coder->opts[pos_mem].pos_prev = pos_mem - 1;
235
236 if (coder->opts[cur].prev_2) {
237 coder->opts[pos_mem - 1].prev_1_is_literal
238 = false;
239 coder->opts[pos_mem - 1].pos_prev
240 = coder->opts[cur].pos_prev_2;
241 coder->opts[pos_mem - 1].back_prev
242 = coder->opts[cur].back_prev_2;
243 }
244 }
245
246 const uint32_t pos_prev = pos_mem;
247 const uint32_t back_cur = back_mem;
248
249 back_mem = coder->opts[pos_prev].back_prev;
250 pos_mem = coder->opts[pos_prev].pos_prev;
251
252 coder->opts[pos_prev].back_prev = back_cur;
253 coder->opts[pos_prev].pos_prev = cur;
254 cur = pos_prev;
255
256 } while (cur != 0);
257
258 coder->opts_current_index = coder->opts[0].pos_prev;
259 *len_res = coder->opts[0].pos_prev;
260 *back_res = coder->opts[0].back_prev;
261
262 return;
263 }
264
265
266 //////////
267 // Main //
268 //////////
269
270 static inline uint32_t
271 helper1(lzma_lzma1_encoder *restrict coder, lzma_mf *restrict mf,
272 uint32_t *restrict back_res, uint32_t *restrict len_res,
273 uint32_t position)
274 {
275 const uint32_t nice_len = mf->nice_len;
276
277 uint32_t len_main;
278 uint32_t matches_count;
279
280 if (mf->read_ahead == 0) {
281 len_main = mf_find(mf, &matches_count, coder->matches);
282 } else {
283 assert(mf->read_ahead == 1);
284 len_main = coder->longest_match_length;
285 matches_count = coder->matches_count;
286 }
287
288 const uint32_t buf_avail = my_min(mf_avail(mf) + 1, MATCH_LEN_MAX);
289 if (buf_avail < 2) {
290 *back_res = UINT32_MAX;
291 *len_res = 1;
292 return UINT32_MAX;
293 }
294
295 const uint8_t *const buf = mf_ptr(mf) - 1;
296
297 uint32_t rep_lens[REPS];
298 uint32_t rep_max_index = 0;
299
300 for (uint32_t i = 0; i < REPS; ++i) {
301 const uint8_t *const buf_back = buf - coder->reps[i] - 1;
302
303 if (not_equal_16(buf, buf_back)) {
304 rep_lens[i] = 0;
305 continue;
306 }
307
308 rep_lens[i] = lzma_memcmplen(buf, buf_back, 2, buf_avail);
309
310 if (rep_lens[i] > rep_lens[rep_max_index])
311 rep_max_index = i;
312 }
313
314 if (rep_lens[rep_max_index] >= nice_len) {
315 *back_res = rep_max_index;
316 *len_res = rep_lens[rep_max_index];
317 mf_skip(mf, *len_res - 1);
318 return UINT32_MAX;
319 }
320
321
322 if (len_main >= nice_len) {
323 *back_res = coder->matches[matches_count - 1].dist + REPS;
324 *len_res = len_main;
325 mf_skip(mf, len_main - 1);
326 return UINT32_MAX;
327 }
328
329 const uint8_t current_byte = *buf;
330 const uint8_t match_byte = *(buf - coder->reps[0] - 1);
331
332 if (len_main < 2 && current_byte != match_byte
333 && rep_lens[rep_max_index] < 2) {
334 *back_res = UINT32_MAX;
335 *len_res = 1;
336 return UINT32_MAX;
337 }
338
339 coder->opts[0].state = coder->state;
340
341 const uint32_t pos_state = position & coder->pos_mask;
342
343 coder->opts[1].price = rc_bit_0_price(
344 coder->is_match[coder->state][pos_state])
345 + get_literal_price(coder, position, buf[-1],
346 !is_literal_state(coder->state),
347 match_byte, current_byte);
348
349 make_literal(&coder->opts[1]);
350
351 const uint32_t match_price = rc_bit_1_price(
352 coder->is_match[coder->state][pos_state]);
353 const uint32_t rep_match_price = match_price
354 + rc_bit_1_price(coder->is_rep[coder->state]);
355
356 if (match_byte == current_byte) {
357 const uint32_t short_rep_price = rep_match_price
358 + get_short_rep_price(
359 coder, coder->state, pos_state);
360
361 if (short_rep_price < coder->opts[1].price) {
362 coder->opts[1].price = short_rep_price;
363 make_short_rep(&coder->opts[1]);
364 }
365 }
366
367 const uint32_t len_end = my_max(len_main, rep_lens[rep_max_index]);
368
369 if (len_end < 2) {
370 *back_res = coder->opts[1].back_prev;
371 *len_res = 1;
372 return UINT32_MAX;
373 }
374
375 coder->opts[1].pos_prev = 0;
376
377 for (uint32_t i = 0; i < REPS; ++i)
378 coder->opts[0].backs[i] = coder->reps[i];
379
380 uint32_t len = len_end;
381 do {
382 coder->opts[len].price = RC_INFINITY_PRICE;
383 } while (--len >= 2);
384
385
386 for (uint32_t i = 0; i < REPS; ++i) {
387 uint32_t rep_len = rep_lens[i];
388 if (rep_len < 2)
389 continue;
390
391 const uint32_t price = rep_match_price + get_pure_rep_price(
392 coder, i, coder->state, pos_state);
393
394 do {
395 const uint32_t cur_and_len_price = price
396 + get_len_price(
397 &coder->rep_len_encoder,
398 rep_len, pos_state);
399
400 if (cur_and_len_price < coder->opts[rep_len].price) {
401 coder->opts[rep_len].price = cur_and_len_price;
402 coder->opts[rep_len].pos_prev = 0;
403 coder->opts[rep_len].back_prev = i;
404 coder->opts[rep_len].prev_1_is_literal = false;
405 }
406 } while (--rep_len >= 2);
407 }
408
409
410 const uint32_t normal_match_price = match_price
411 + rc_bit_0_price(coder->is_rep[coder->state]);
412
413 len = rep_lens[0] >= 2 ? rep_lens[0] + 1 : 2;
414 if (len <= len_main) {
415 uint32_t i = 0;
416 while (len > coder->matches[i].len)
417 ++i;
418
419 for(; ; ++len) {
420 const uint32_t dist = coder->matches[i].dist;
421 const uint32_t cur_and_len_price = normal_match_price
422 + get_dist_len_price(coder,
423 dist, len, pos_state);
424
425 if (cur_and_len_price < coder->opts[len].price) {
426 coder->opts[len].price = cur_and_len_price;
427 coder->opts[len].pos_prev = 0;
428 coder->opts[len].back_prev = dist + REPS;
429 coder->opts[len].prev_1_is_literal = false;
430 }
431
432 if (len == coder->matches[i].len)
433 if (++i == matches_count)
434 break;
435 }
436 }
437
438 return len_end;
439 }
440
441
442 static inline uint32_t
443 helper2(lzma_lzma1_encoder *coder, uint32_t *reps, const uint8_t *buf,
444 uint32_t len_end, uint32_t position, const uint32_t cur,
445 const uint32_t nice_len, const uint32_t buf_avail_full)
446 {
447 uint32_t matches_count = coder->matches_count;
448 uint32_t new_len = coder->longest_match_length;
449 uint32_t pos_prev = coder->opts[cur].pos_prev;
450 lzma_lzma_state state;
451
452 if (coder->opts[cur].prev_1_is_literal) {
453 --pos_prev;
454
455 if (coder->opts[cur].prev_2) {
456 state = coder->opts[coder->opts[cur].pos_prev_2].state;
457
458 if (coder->opts[cur].back_prev_2 < REPS)
459 update_long_rep(state);
460 else
461 update_match(state);
462
463 } else {
464 state = coder->opts[pos_prev].state;
465 }
466
467 update_literal(state);
468
469 } else {
470 state = coder->opts[pos_prev].state;
471 }
472
473 if (pos_prev == cur - 1) {
474 if (is_short_rep(coder->opts[cur]))
475 update_short_rep(state);
476 else
477 update_literal(state);
478 } else {
479 uint32_t pos;
480 if (coder->opts[cur].prev_1_is_literal
481 && coder->opts[cur].prev_2) {
482 pos_prev = coder->opts[cur].pos_prev_2;
483 pos = coder->opts[cur].back_prev_2;
484 update_long_rep(state);
485 } else {
486 pos = coder->opts[cur].back_prev;
487 if (pos < REPS)
488 update_long_rep(state);
489 else
490 update_match(state);
491 }
492
493 if (pos < REPS) {
494 reps[0] = coder->opts[pos_prev].backs[pos];
495
496 uint32_t i;
497 for (i = 1; i <= pos; ++i)
498 reps[i] = coder->opts[pos_prev].backs[i - 1];
499
500 for (; i < REPS; ++i)
501 reps[i] = coder->opts[pos_prev].backs[i];
502
503 } else {
504 reps[0] = pos - REPS;
505
506 for (uint32_t i = 1; i < REPS; ++i)
507 reps[i] = coder->opts[pos_prev].backs[i - 1];
508 }
509 }
510
511 coder->opts[cur].state = state;
512
513 for (uint32_t i = 0; i < REPS; ++i)
514 coder->opts[cur].backs[i] = reps[i];
515
516 const uint32_t cur_price = coder->opts[cur].price;
517
518 const uint8_t current_byte = *buf;
519 const uint8_t match_byte = *(buf - reps[0] - 1);
520
521 const uint32_t pos_state = position & coder->pos_mask;
522
523 const uint32_t cur_and_1_price = cur_price
524 + rc_bit_0_price(coder->is_match[state][pos_state])
525 + get_literal_price(coder, position, buf[-1],
526 !is_literal_state(state), match_byte, current_byte);
527
528 bool next_is_literal = false;
529
530 if (cur_and_1_price < coder->opts[cur + 1].price) {
531 coder->opts[cur + 1].price = cur_and_1_price;
532 coder->opts[cur + 1].pos_prev = cur;
533 make_literal(&coder->opts[cur + 1]);
534 next_is_literal = true;
535 }
536
537 const uint32_t match_price = cur_price
538 + rc_bit_1_price(coder->is_match[state][pos_state]);
539 const uint32_t rep_match_price = match_price
540 + rc_bit_1_price(coder->is_rep[state]);
541
542 if (match_byte == current_byte
543 && !(coder->opts[cur + 1].pos_prev < cur
544 && coder->opts[cur + 1].back_prev == 0)) {
545
546 const uint32_t short_rep_price = rep_match_price
547 + get_short_rep_price(coder, state, pos_state);
548
549 if (short_rep_price <= coder->opts[cur + 1].price) {
550 coder->opts[cur + 1].price = short_rep_price;
551 coder->opts[cur + 1].pos_prev = cur;
552 make_short_rep(&coder->opts[cur + 1]);
553 next_is_literal = true;
554 }
555 }
556
557 if (buf_avail_full < 2)
558 return len_end;
559
560 const uint32_t buf_avail = my_min(buf_avail_full, nice_len);
561
562 if (!next_is_literal && match_byte != current_byte) { // speed optimization
563 // try literal + rep0
564 const uint8_t *const buf_back = buf - reps[0] - 1;
565 const uint32_t limit = my_min(buf_avail_full, nice_len + 1);
566
567 const uint32_t len_test = lzma_memcmplen(buf, buf_back, 1, limit) - 1;
568
569 if (len_test >= 2) {
570 lzma_lzma_state state_2 = state;
571 update_literal(state_2);
572
573 const uint32_t pos_state_next = (position + 1) & coder->pos_mask;
574 const uint32_t next_rep_match_price = cur_and_1_price
575 + rc_bit_1_price(coder->is_match[state_2][pos_state_next])
576 + rc_bit_1_price(coder->is_rep[state_2]);
577
578 //for (; len_test >= 2; --len_test) {
579 const uint32_t offset = cur + 1 + len_test;
580
581 while (len_end < offset)
582 coder->opts[++len_end].price = RC_INFINITY_PRICE;
583
584 const uint32_t cur_and_len_price = next_rep_match_price
585 + get_rep_price(coder, 0, len_test,
586 state_2, pos_state_next);
587
588 if (cur_and_len_price < coder->opts[offset].price) {
589 coder->opts[offset].price = cur_and_len_price;
590 coder->opts[offset].pos_prev = cur + 1;
591 coder->opts[offset].back_prev = 0;
592 coder->opts[offset].prev_1_is_literal = true;
593 coder->opts[offset].prev_2 = false;
594 }
595 //}
596 }
597 }
598
599
600 uint32_t start_len = 2; // speed optimization
601
602 for (uint32_t rep_index = 0; rep_index < REPS; ++rep_index) {
603 const uint8_t *const buf_back = buf - reps[rep_index] - 1;
604 if (not_equal_16(buf, buf_back))
605 continue;
606
607 uint32_t len_test = lzma_memcmplen(buf, buf_back, 2, buf_avail);
608
609 while (len_end < cur + len_test)
610 coder->opts[++len_end].price = RC_INFINITY_PRICE;
611
612 const uint32_t len_test_temp = len_test;
613 const uint32_t price = rep_match_price + get_pure_rep_price(
614 coder, rep_index, state, pos_state);
615
616 do {
617 const uint32_t cur_and_len_price = price
618 + get_len_price(&coder->rep_len_encoder,
619 len_test, pos_state);
620
621 if (cur_and_len_price < coder->opts[cur + len_test].price) {
622 coder->opts[cur + len_test].price = cur_and_len_price;
623 coder->opts[cur + len_test].pos_prev = cur;
624 coder->opts[cur + len_test].back_prev = rep_index;
625 coder->opts[cur + len_test].prev_1_is_literal = false;
626 }
627 } while (--len_test >= 2);
628
629 len_test = len_test_temp;
630
631 if (rep_index == 0)
632 start_len = len_test + 1;
633
634
635 uint32_t len_test_2 = len_test + 1;
636 const uint32_t limit = my_min(buf_avail_full,
637 len_test_2 + nice_len);
638 // NOTE: len_test_2 may be greater than limit so the call to
639 // lzma_memcmplen() must be done conditionally.
640 if (len_test_2 < limit)
641 len_test_2 = lzma_memcmplen(buf, buf_back, len_test_2, limit);
642
643 len_test_2 -= len_test + 1;
644
645 if (len_test_2 >= 2) {
646 lzma_lzma_state state_2 = state;
647 update_long_rep(state_2);
648
649 uint32_t pos_state_next = (position + len_test) & coder->pos_mask;
650
651 const uint32_t cur_and_len_literal_price = price
652 + get_len_price(&coder->rep_len_encoder,
653 len_test, pos_state)
654 + rc_bit_0_price(coder->is_match[state_2][pos_state_next])
655 + get_literal_price(coder, position + len_test,
656 buf[len_test - 1], true,
657 buf_back[len_test], buf[len_test]);
658
659 update_literal(state_2);
660
661 pos_state_next = (position + len_test + 1) & coder->pos_mask;
662
663 const uint32_t next_rep_match_price = cur_and_len_literal_price
664 + rc_bit_1_price(coder->is_match[state_2][pos_state_next])
665 + rc_bit_1_price(coder->is_rep[state_2]);
666
667 //for(; len_test_2 >= 2; len_test_2--) {
668 const uint32_t offset = cur + len_test + 1 + len_test_2;
669
670 while (len_end < offset)
671 coder->opts[++len_end].price = RC_INFINITY_PRICE;
672
673 const uint32_t cur_and_len_price = next_rep_match_price
674 + get_rep_price(coder, 0, len_test_2,
675 state_2, pos_state_next);
676
677 if (cur_and_len_price < coder->opts[offset].price) {
678 coder->opts[offset].price = cur_and_len_price;
679 coder->opts[offset].pos_prev = cur + len_test + 1;
680 coder->opts[offset].back_prev = 0;
681 coder->opts[offset].prev_1_is_literal = true;
682 coder->opts[offset].prev_2 = true;
683 coder->opts[offset].pos_prev_2 = cur;
684 coder->opts[offset].back_prev_2 = rep_index;
685 }
686 //}
687 }
688 }
689
690
691 //for (uint32_t len_test = 2; len_test <= new_len; ++len_test)
692 if (new_len > buf_avail) {
693 new_len = buf_avail;
694
695 matches_count = 0;
696 while (new_len > coder->matches[matches_count].len)
697 ++matches_count;
698
699 coder->matches[matches_count++].len = new_len;
700 }
701
702
703 if (new_len >= start_len) {
704 const uint32_t normal_match_price = match_price
705 + rc_bit_0_price(coder->is_rep[state]);
706
707 while (len_end < cur + new_len)
708 coder->opts[++len_end].price = RC_INFINITY_PRICE;
709
710 uint32_t i = 0;
711 while (start_len > coder->matches[i].len)
712 ++i;
713
714 for (uint32_t len_test = start_len; ; ++len_test) {
715 const uint32_t cur_back = coder->matches[i].dist;
716 uint32_t cur_and_len_price = normal_match_price
717 + get_dist_len_price(coder,
718 cur_back, len_test, pos_state);
719
720 if (cur_and_len_price < coder->opts[cur + len_test].price) {
721 coder->opts[cur + len_test].price = cur_and_len_price;
722 coder->opts[cur + len_test].pos_prev = cur;
723 coder->opts[cur + len_test].back_prev
724 = cur_back + REPS;
725 coder->opts[cur + len_test].prev_1_is_literal = false;
726 }
727
728 if (len_test == coder->matches[i].len) {
729 // Try Match + Literal + Rep0
730 const uint8_t *const buf_back = buf - cur_back - 1;
731 uint32_t len_test_2 = len_test + 1;
732 const uint32_t limit = my_min(buf_avail_full,
733 len_test_2 + nice_len);
734
735 // NOTE: len_test_2 may be greater than limit
736 // so the call to lzma_memcmplen() must be
737 // done conditionally.
738 if (len_test_2 < limit)
739 len_test_2 = lzma_memcmplen(buf, buf_back,
740 len_test_2, limit);
741
742 len_test_2 -= len_test + 1;
743
744 if (len_test_2 >= 2) {
745 lzma_lzma_state state_2 = state;
746 update_match(state_2);
747 uint32_t pos_state_next
748 = (position + len_test) & coder->pos_mask;
749
750 const uint32_t cur_and_len_literal_price = cur_and_len_price
751 + rc_bit_0_price(
752 coder->is_match[state_2][pos_state_next])
753 + get_literal_price(coder,
754 position + len_test,
755 buf[len_test - 1],
756 true,
757 buf_back[len_test],
758 buf[len_test]);
759
760 update_literal(state_2);
761 pos_state_next = (pos_state_next + 1) & coder->pos_mask;
762
763 const uint32_t next_rep_match_price
764 = cur_and_len_literal_price
765 + rc_bit_1_price(
766 coder->is_match[state_2][pos_state_next])
767 + rc_bit_1_price(coder->is_rep[state_2]);
768
769 // for(; len_test_2 >= 2; --len_test_2) {
770 const uint32_t offset = cur + len_test + 1 + len_test_2;
771
772 while (len_end < offset)
773 coder->opts[++len_end].price = RC_INFINITY_PRICE;
774
775 cur_and_len_price = next_rep_match_price
776 + get_rep_price(coder, 0, len_test_2,
777 state_2, pos_state_next);
778
779 if (cur_and_len_price < coder->opts[offset].price) {
780 coder->opts[offset].price = cur_and_len_price;
781 coder->opts[offset].pos_prev = cur + len_test + 1;
782 coder->opts[offset].back_prev = 0;
783 coder->opts[offset].prev_1_is_literal = true;
784 coder->opts[offset].prev_2 = true;
785 coder->opts[offset].pos_prev_2 = cur;
786 coder->opts[offset].back_prev_2
787 = cur_back + REPS;
788 }
789 //}
790 }
791
792 if (++i == matches_count)
793 break;
794 }
795 }
796 }
797
798 return len_end;
799 }
800
801
802 extern void
803 lzma_lzma_optimum_normal(lzma_lzma1_encoder *restrict coder,
804 lzma_mf *restrict mf,
805 uint32_t *restrict back_res, uint32_t *restrict len_res,
806 uint32_t position)
807 {
808 // If we have symbols pending, return the next pending symbol.
809 if (coder->opts_end_index != coder->opts_current_index) {
810 assert(mf->read_ahead > 0);
811 *len_res = coder->opts[coder->opts_current_index].pos_prev
812 - coder->opts_current_index;
813 *back_res = coder->opts[coder->opts_current_index].back_prev;
814 coder->opts_current_index = coder->opts[
815 coder->opts_current_index].pos_prev;
816 return;
817 }
818
819 // Update the price tables. In LZMA SDK <= 4.60 (and possibly later)
820 // this was done in both initialization function and in the main loop.
821 // In liblzma they were moved into this single place.
822 if (mf->read_ahead == 0) {
823 if (coder->match_price_count >= (1 << 7))
824 fill_dist_prices(coder);
825
826 if (coder->align_price_count >= ALIGN_SIZE)
827 fill_align_prices(coder);
828 }
829
830 // TODO: This needs quite a bit of cleaning still. But splitting
831 // the original function into two pieces makes it at least a little
832 // more readable, since those two parts don't share many variables.
833
834 uint32_t len_end = helper1(coder, mf, back_res, len_res, position);
835 if (len_end == UINT32_MAX)
836 return;
837
838 uint32_t reps[REPS];
839 memcpy(reps, coder->reps, sizeof(reps));
840
841 uint32_t cur;
842 for (cur = 1; cur < len_end; ++cur) {
843 assert(cur < OPTS);
844
845 coder->longest_match_length = mf_find(
846 mf, &coder->matches_count, coder->matches);
847
848 if (coder->longest_match_length >= mf->nice_len)
849 break;
850
851 len_end = helper2(coder, reps, mf_ptr(mf) - 1, len_end,
852 position + cur, cur, mf->nice_len,
853 my_min(mf_avail(mf) + 1, OPTS - 1 - cur));
854 }
855
856 backward(coder, len_res, back_res, cur);
857 return;
858 }
XZ Utils for Debian