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