lzma_encoder_optimum_fast.c revision 292588 
1///////////////////////////////////////////////////////////////////////////////
2//
3/// \file       lzma_encoder_optimum_fast.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 "memcmplen.h"
14
15
16#define change_pair(small_dist, big_dist) \
17	(((big_dist) >> 7) > (small_dist))
18
19
20extern void
21lzma_lzma_optimum_fast(lzma_coder *restrict coder, lzma_mf *restrict mf,
22		uint32_t *restrict back_res, uint32_t *restrict len_res)
23{
24	const uint32_t nice_len = mf->nice_len;
25
26	uint32_t len_main;
27	uint32_t matches_count;
28	if (mf->read_ahead == 0) {
29		len_main = mf_find(mf, &matches_count, coder->matches);
30	} else {
31		assert(mf->read_ahead == 1);
32		len_main = coder->longest_match_length;
33		matches_count = coder->matches_count;
34	}
35
36	const uint8_t *buf = mf_ptr(mf) - 1;
37	const uint32_t buf_avail = my_min(mf_avail(mf) + 1, MATCH_LEN_MAX);
38
39	if (buf_avail < 2) {
40		// There's not enough input left to encode a match.
41		*back_res = UINT32_MAX;
42		*len_res = 1;
43		return;
44	}
45
46	// Look for repeated matches; scan the previous four match distances
47	uint32_t rep_len = 0;
48	uint32_t rep_index = 0;
49
50	for (uint32_t i = 0; i < REPS; ++i) {
51		// Pointer to the beginning of the match candidate
52		const uint8_t *const buf_back = buf - coder->reps[i] - 1;
53
54		// If the first two bytes (2 == MATCH_LEN_MIN) do not match,
55		// this rep is not useful.
56		if (not_equal_16(buf, buf_back))
57			continue;
58
59		// The first two bytes matched.
60		// Calculate the length of the match.
61		const uint32_t len = lzma_memcmplen(
62				buf, buf_back, 2, buf_avail);
63
64		// If we have found a repeated match that is at least
65		// nice_len long, return it immediately.
66		if (len >= nice_len) {
67			*back_res = i;
68			*len_res = len;
69			mf_skip(mf, len - 1);
70			return;
71		}
72
73		if (len > rep_len) {
74			rep_index = i;
75			rep_len = len;
76		}
77	}
78
79	// We didn't find a long enough repeated match. Encode it as a normal
80	// match if the match length is at least nice_len.
81	if (len_main >= nice_len) {
82		*back_res = coder->matches[matches_count - 1].dist + REPS;
83		*len_res = len_main;
84		mf_skip(mf, len_main - 1);
85		return;
86	}
87
88	uint32_t back_main = 0;
89	if (len_main >= 2) {
90		back_main = coder->matches[matches_count - 1].dist;
91
92		while (matches_count > 1 && len_main ==
93				coder->matches[matches_count - 2].len + 1) {
94			if (!change_pair(coder->matches[
95						matches_count - 2].dist,
96					back_main))
97				break;
98
99			--matches_count;
100			len_main = coder->matches[matches_count - 1].len;
101			back_main = coder->matches[matches_count - 1].dist;
102		}
103
104		if (len_main == 2 && back_main >= 0x80)
105			len_main = 1;
106	}
107
108	if (rep_len >= 2) {
109		if (rep_len + 1 >= len_main
110				|| (rep_len + 2 >= len_main
111					&& back_main > (UINT32_C(1) << 9))
112				|| (rep_len + 3 >= len_main
113					&& back_main > (UINT32_C(1) << 15))) {
114			*back_res = rep_index;
115			*len_res = rep_len;
116			mf_skip(mf, rep_len - 1);
117			return;
118		}
119	}
120
121	if (len_main < 2 || buf_avail <= 2) {
122		*back_res = UINT32_MAX;
123		*len_res = 1;
124		return;
125	}
126
127	// Get the matches for the next byte. If we find a better match,
128	// the current byte is encoded as a literal.
129	coder->longest_match_length = mf_find(mf,
130			&coder->matches_count, coder->matches);
131
132	if (coder->longest_match_length >= 2) {
133		const uint32_t new_dist = coder->matches[
134				coder->matches_count - 1].dist;
135
136		if ((coder->longest_match_length >= len_main
137					&& new_dist < back_main)
138				|| (coder->longest_match_length == len_main + 1
139					&& !change_pair(back_main, new_dist))
140				|| (coder->longest_match_length > len_main + 1)
141				|| (coder->longest_match_length + 1 >= len_main
142					&& len_main >= 3
143					&& change_pair(new_dist, back_main))) {
144			*back_res = UINT32_MAX;
145			*len_res = 1;
146			return;
147		}
148	}
149
150	// In contrast to LZMA SDK, dictionary could not have been moved
151	// between mf_find() calls, thus it is safe to just increment
152	// the old buf pointer instead of recalculating it with mf_ptr().
153	++buf;
154
155	const uint32_t limit = my_max(2, len_main - 1);
156
157	for (uint32_t i = 0; i < REPS; ++i) {
158		if (memcmp(buf, buf - coder->reps[i] - 1, limit) == 0) {
159			*back_res = UINT32_MAX;
160			*len_res = 1;
161			return;
162		}
163	}
164
165	*back_res = back_main + REPS;
166	*len_res = len_main;
167	mf_skip(mf, len_main - 2);
168	return;
169}
170