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