Fix a buffer overflow in the LZMA encoder. It was due to my

misunderstanding of the code. There's no tiny fix for this
problem, so I also cleaned up the code in general.

This reduces the speed of the encoder 2-5 % in the fastest
compression mode ("lzma -1"). High compression modes should
have no noticeable performance difference.

This commit breaks things (especially LZMA_SYNC_FLUSH) but I
will fix them once the new format and LZMA2 has been roughly
implemented. Plain LZMA won't support LZMA_SYNC_FLUSH at all
and won't be supported in the new .lzma format. This may
change still but this is what it looks like now.

Support for known uncompressed size (that is, LZMA or LZMA2
without EOPM) is likely to go away. This means there will
be API changes.

5 files changed, 320 insertions, 318 deletions

diff --git a/src/liblzma/lzma/lzma_encoder.c b/src/liblzma/lzma/lzma_encoder.c
index 4eee84f3..b0052182 100644
--- a/src/liblzma/lzma/lzma_encoder.c
+++ b/src/liblzma/lzma/lzma_encoder.c
@@ -26,113 +26,248 @@
 #include "fastpos.h"
 
 
-////////////
-// Macros //
-////////////
-
-// These are as macros mostly because they use local range encoder variables.
-
-#define literal_encode(subcoder, symbol) \
-do { \
-	uint32_t context = 1; \
-	int i = 8; \
-	do { \
-		--i; \
-		const uint32_t bit = ((symbol) >> i) & 1; \
-		bit_encode(subcoder[context], bit); \
-		context = (context << 1) | bit; \
-	} while (i != 0); \
-} while (0)
-
-
-#define literal_encode_matched(subcoder, match_byte, symbol) \
-do { \
-	uint32_t context = 1; \
-	int i = 8; \
-	do { \
-		--i; \
-		uint32_t bit = ((symbol) >> i) & 1; \
-		const uint32_t match_bit = ((match_byte) >> i) & 1; \
-		const uint32_t subcoder_index = 0x100 + (match_bit << 8) + context; \
-		bit_encode(subcoder[subcoder_index], bit); \
-		context = (context << 1) | bit; \
-		if (match_bit != bit) { \
-			while (i != 0) { \
-				--i; \
-				bit = ((symbol) >> i) & 1; \
-				bit_encode(subcoder[context], bit); \
-				context = (context << 1) | bit; \
-			} \
-			break; \
-		} \
-	} while (i != 0); \
-} while (0)
-
-
-#define length_encode(length_encoder, symbol, pos_state, update_price) \
-do { \
-	assert((symbol) <= MATCH_MAX_LEN); \
-	if ((symbol) < LEN_LOW_SYMBOLS) { \
-		bit_encode_0((length_encoder).choice); \
-		bittree_encode((length_encoder).low[pos_state], \
-				LEN_LOW_BITS, symbol); \
-	} else { \
-		bit_encode_1((length_encoder).choice); \
-		if ((symbol) < LEN_LOW_SYMBOLS + LEN_MID_SYMBOLS) { \
-			bit_encode_0((length_encoder).choice2); \
-			bittree_encode((length_encoder).mid[pos_state], \
-					LEN_MID_BITS, \
-					(symbol) - LEN_LOW_SYMBOLS); \
-		} else { \
-			bit_encode_1((length_encoder).choice2); \
-			bittree_encode((length_encoder).high, LEN_HIGH_BITS, \
-					(symbol) - LEN_LOW_SYMBOLS \
-					- LEN_MID_SYMBOLS); \
-		} \
-	} \
-	if (update_price) \
-		if (--(length_encoder).counters[pos_state] == 0) \
-			lzma_length_encoder_update_table(&(length_encoder), pos_state); \
-} while (0)
-
-
-///////////////
-// Functions //
-///////////////
-
-/// \brief      Updates price table of the length encoder
-///
-/// Like all the other prices in LZMA, these are used by lzma_get_optimum().
-///
-extern void
-lzma_length_encoder_update_table(lzma_length_encoder *lencoder,
-		const uint32_t pos_state)
+/////////////
+// Literal //
+/////////////
+
+static inline void
+literal_normal(lzma_range_encoder *rc, probability *subcoder, uint32_t symbol)
+{
+	uint32_t context = 1;
+	uint32_t bit_count = 8; // Bits per byte
+	do {
+		const uint32_t bit = (symbol >> --bit_count) & 1;
+		rc_bit(rc, &subcoder[context], bit);
+		context = (context << 1) | bit;
+	} while (bit_count != 0);
+}
+
+
+static inline void
+literal_matched(lzma_range_encoder *rc, probability *subcoder,
+		uint32_t match_byte, uint32_t symbol)
+{
+	uint32_t context = 1;
+	uint32_t bit_count = 8;
+
+	do {
+		uint32_t bit = (symbol >> --bit_count) & 1;
+		const uint32_t match_bit = (match_byte >> bit_count) & 1;
+		rc_bit(rc, &subcoder[(0x100 << match_bit) + context], bit);
+		context = (context << 1) | bit;
+
+		if (match_bit != bit) {
+			// The bit from the literal being encoded and the bit
+			// from the previous match differ. Finish encoding
+			// as a normal literal.
+			while (bit_count != 0) {
+				bit = (symbol >> --bit_count) & 1;
+				rc_bit(rc, &subcoder[context], bit);
+				context = (context << 1) | bit;
+			}
+
+			break;
+		}
+
+	} while (bit_count != 0);
+}
+
+
+static inline void
+literal(lzma_coder *coder)
+{
+	// Locate the literal byte to be encoded and the subcoder.
+	const uint8_t cur_byte = coder->lz.buffer[
+			coder->lz.read_pos - coder->additional_offset];
+	probability *subcoder = literal_get_subcoder(coder->literal_coder,
+			coder->now_pos, coder->previous_byte);
+
+	if (is_literal_state(coder->state)) {
+		// Previous LZMA-symbol was a literal. Encode a normal
+		// literal without a match byte.
+		literal_normal(&coder->rc, subcoder, cur_byte);
+	} else {
+		// Previous LZMA-symbol was a match. Use the last byte of
+		// the match as a "match byte". That is, compare the bits
+		// of the current literal and the match byte.
+		const uint8_t match_byte = coder->lz.buffer[
+				coder->lz.read_pos - coder->reps[0] - 1
+				- coder->additional_offset];
+		literal_matched(&coder->rc, subcoder, match_byte, cur_byte);
+	}
+
+	update_literal(coder->state);
+	coder->previous_byte = cur_byte;
+}
+
+
+//////////////////
+// Match length //
+//////////////////
+
+static inline void
+length(lzma_range_encoder *rc, lzma_length_encoder *lc,
+		const uint32_t pos_state, uint32_t len)
+{
+	assert(len <= MATCH_MAX_LEN);
+	len -= MATCH_MIN_LEN;
+
+	if (len < LEN_LOW_SYMBOLS) {
+		rc_bit(rc, &lc->choice, 0);
+		rc_bittree(rc, lc->low[pos_state], LEN_LOW_BITS, len);
+	} else {
+		rc_bit(rc, &lc->choice, 1);
+		len -= LEN_LOW_SYMBOLS;
+
+		if (len < LEN_MID_SYMBOLS) {
+			rc_bit(rc, &lc->choice2, 0);
+			rc_bittree(rc, lc->mid[pos_state], LEN_MID_BITS, len);
+		} else {
+			rc_bit(rc, &lc->choice2, 1);
+			len -= LEN_MID_SYMBOLS;
+			rc_bittree(rc, lc->high, LEN_HIGH_BITS, len);
+		}
+	}
+}
+
+
+///////////
+// Match //
+///////////
+
+static inline void
+match(lzma_coder *coder, const uint32_t pos_state,
+		const uint32_t distance, const uint32_t len)
+{
+	update_match(coder->state);
+
+	length(&coder->rc, &coder->match_len_encoder, pos_state, len);
+	coder->prev_len_encoder = &coder->match_len_encoder;
+
+	const uint32_t pos_slot = get_pos_slot(distance);
+	const uint32_t len_to_pos_state = get_len_to_pos_state(len);
+	rc_bittree(&coder->rc, coder->pos_slot_encoder[len_to_pos_state],
+			POS_SLOT_BITS, pos_slot);
+
+	if (pos_slot >= START_POS_MODEL_INDEX) {
+		const uint32_t footer_bits = (pos_slot >> 1) - 1;
+		const uint32_t base = (2 | (pos_slot & 1)) << footer_bits;
+		const uint32_t pos_reduced = distance - base;
+
+		if (pos_slot < END_POS_MODEL_INDEX) {
+			rc_bittree_reverse(&coder->rc,
+				&coder->pos_encoders[base - pos_slot - 1],
+				footer_bits, pos_reduced);
+		} else {
+			rc_direct(&coder->rc, pos_reduced >> ALIGN_BITS,
+					footer_bits - ALIGN_BITS);
+			rc_bittree_reverse(
+					&coder->rc, coder->pos_align_encoder,
+					ALIGN_BITS, pos_reduced & ALIGN_MASK);
+			++coder->align_price_count;
+		}
+	}
+
+	coder->reps[3] = coder->reps[2];
+	coder->reps[2] = coder->reps[1];
+	coder->reps[1] = coder->reps[0];
+	coder->reps[0] = distance;
+	++coder->match_price_count;
+}
+
+
+////////////////////
+// Repeated match //
+////////////////////
+
+static inline void
+rep_match(lzma_coder *coder, const uint32_t pos_state,
+		const uint32_t rep, const uint32_t len)
 {
-	const uint32_t num_symbols = lencoder->table_size;
-	const uint32_t a0 = bit_get_price_0(lencoder->choice);
-	const uint32_t a1 = bit_get_price_1(lencoder->choice);
-	const uint32_t b0 = a1 + bit_get_price_0(lencoder->choice2);
-	const uint32_t b1 = a1 + bit_get_price_1(lencoder->choice2);
+	if (rep == 0) {
+		rc_bit(&coder->rc, &coder->is_rep0[coder->state], 0);
+		rc_bit(&coder->rc,
+				&coder->is_rep0_long[coder->state][pos_state],
+				len != 1);
+	} else {
+		const uint32_t distance = coder->reps[rep];
+		rc_bit(&coder->rc, &coder->is_rep0[coder->state], 1);
+
+		if (rep == 1) {
+			rc_bit(&coder->rc, &coder->is_rep1[coder->state], 0);
+		} else {
+			rc_bit(&coder->rc, &coder->is_rep1[coder->state], 1);
+			rc_bit(&coder->rc, &coder->is_rep2[coder->state],
+					rep - 2);
+
+			if (rep == 3)
+				coder->reps[3] = coder->reps[2];
+
+			coder->reps[2] = coder->reps[1];
+		}
+
+		coder->reps[1] = coder->reps[0];
+		coder->reps[0] = distance;
+	}
+
+	if (len == 1) {
+		update_short_rep(coder->state);
+	} else {
+		length(&coder->rc, &coder->rep_len_encoder, pos_state, len);
+		coder->prev_len_encoder = &coder->rep_len_encoder;
+		update_long_rep(coder->state);
+	}
+}
+
 
-	uint32_t *prices = lencoder->prices[pos_state];
-	uint32_t i = 0;
+//////////
+// Main //
+//////////
 
-	for (i = 0; i < num_symbols && i < LEN_LOW_SYMBOLS; ++i)
-		prices[i] = a0 + bittree_get_price(lencoder->low[pos_state],
-				LEN_LOW_BITS, i);
+static void
+encode_symbol(lzma_coder *coder, uint32_t pos, uint32_t len)
+{
+	const uint32_t pos_state = coder->now_pos & coder->pos_mask;
+
+	if (len == 1 && pos == UINT32_MAX) {
+		// Literal i.e. eight-bit byte
+		rc_bit(&coder->rc,
+				&coder->is_match[coder->state][pos_state], 0);
+		literal(coder);
+	} else {
+		// Some type of match
+		rc_bit(&coder->rc,
+			&coder->is_match[coder->state][pos_state], 1);
+
+		if (pos < REP_DISTANCES) {
+			// It's a repeated match i.e. the same distance
+			// has been used earlier.
+			rc_bit(&coder->rc, &coder->is_rep[coder->state], 1);
+			rep_match(coder, pos_state, pos, len);
+		} else {
+			// Normal match
+			rc_bit(&coder->rc, &coder->is_rep[coder->state], 0);
+			match(coder, pos_state, pos - REP_DISTANCES, len);
+		}
 
-	for (; i < num_symbols && i < LEN_LOW_SYMBOLS + LEN_MID_SYMBOLS; ++i)
-		prices[i] = b0 + bittree_get_price(lencoder->mid[pos_state],
-				LEN_MID_BITS, i - LEN_LOW_SYMBOLS);
+		coder->previous_byte = coder->lz.buffer[
+				coder->lz.read_pos + len - 1
+				- coder->additional_offset];
+	}
 
-	for (; i < num_symbols; ++i)
-		prices[i] = b1 + bittree_get_price(
-				lencoder->high, LEN_HIGH_BITS,
-				i - LEN_LOW_SYMBOLS - LEN_MID_SYMBOLS);
+	assert(coder->additional_offset >= len);
+	coder->additional_offset -= len;
+	coder->now_pos += len;
+}
 
-	lencoder->counters[pos_state] = num_symbols;
 
-	return;
+static void
+encode_eopm(lzma_coder *coder)
+{
+	const uint32_t pos_state = coder->now_pos & coder->pos_mask;
+	rc_bit(&coder->rc, &coder->is_match[coder->state][pos_state], 1);
+	rc_bit(&coder->rc, &coder->is_rep[coder->state], 0);
+	match(coder, pos_state, UINT32_MAX, MATCH_MIN_LEN);
 }
 
 
@@ -145,15 +280,6 @@ extern bool
 lzma_lzma_encode(lzma_coder *coder, uint8_t *restrict out,
 		size_t *restrict out_pos, size_t out_size)
 {
-#define rc_buffer coder->lz.temp
-#define rc_buffer_size coder->lz.temp_size
-
-	// Local copies
-	lzma_range_encoder rc = coder->rc;
-	size_t out_pos_local = *out_pos;
-	const uint32_t pos_mask = coder->pos_mask;
-	const bool best_compression = coder->best_compression;
-
 	// Initialize the stream if no data has been encoded yet.
 	if (!coder->is_initialized) {
 		if (coder->lz.read_pos == coder->lz.read_limit) {
@@ -167,20 +293,10 @@ lzma_lzma_encode(lzma_coder *coder, uint8_t *restrict out,
 			// Do the actual initialization.
 			uint32_t len;
 			uint32_t num_distance_pairs;
-			lzma_read_match_distances(coder, &len, &num_distance_pairs);
-
-			bit_encode_0(coder->is_match[coder->state][0]);
-			update_literal(coder->state);
-
-			const uint8_t cur_byte = coder->lz.buffer[
-					coder->lz.read_pos - coder->additional_offset];
-			probability *subcoder = literal_get_subcoder(coder->literal_coder,
-					coder->now_pos, coder->previous_byte);
-			literal_encode(subcoder, cur_byte);
+			lzma_read_match_distances(coder,
+					&len, &num_distance_pairs);
 
-			coder->previous_byte = cur_byte;
-			--coder->additional_offset;
-			++coder->now_pos;
+			encode_symbol(coder, UINT32_MAX, 1);
 
 			assert(coder->additional_offset == 0);
 		}
@@ -191,19 +307,19 @@ lzma_lzma_encode(lzma_coder *coder, uint8_t *restrict out,
 
 	// Encoding loop
 	while (true) {
-		// Check that there is free output space.
-		if (out_pos_local == out_size)
-			break;
-
-		assert(rc_buffer_size == 0);
+		// Encode pending bits, if any.
+		if (rc_encode(&coder->rc, out, out_pos, out_size))
+			return false;
 
 		// Check that there is some input to process.
 		if (coder->lz.read_pos >= coder->lz.read_limit) {
 			// If flushing or finishing, we must keep encoding
 			// until additional_offset becomes zero to make
 			// all the input available at output.
-			if (coder->lz.sequence == SEQ_RUN
-					|| coder->additional_offset == 0)
+			if (coder->lz.sequence == SEQ_RUN)
+				return false;
+
+			if (coder->additional_offset == 0)
 				break;
 		}
 
@@ -218,8 +334,6 @@ lzma_lzma_encode(lzma_coder *coder, uint8_t *restrict out,
 		}
 #endif
 
-		const uint32_t pos_state = coder->now_pos & pos_mask;
-
 		uint32_t pos;
 		uint32_t len;
 
@@ -230,175 +344,32 @@ lzma_lzma_encode(lzma_coder *coder, uint8_t *restrict out,
 		//   - UINT32_MAX: not a match but a literal
 		// Value ranges for len:
 		//   - [MATCH_MIN_LEN, MATCH_MAX_LEN]
-		if (best_compression)
+		if (coder->best_compression)
 			lzma_get_optimum(coder, &pos, &len);
 		else
 			lzma_get_optimum_fast(coder, &pos, &len);
 
-		if (len == 1 && pos == UINT32_MAX) {
-			// It's a literal.
-			bit_encode_0(coder->is_match[coder->state][pos_state]);
-
-			const uint8_t cur_byte = coder->lz.buffer[
-					coder->lz.read_pos - coder->additional_offset];
-			probability *subcoder = literal_get_subcoder(coder->literal_coder,
-					coder->now_pos, coder->previous_byte);
-
-			if (is_literal_state(coder->state)) {
-				literal_encode(subcoder, cur_byte);
-			} else {
-				const uint8_t match_byte = coder->lz.buffer[
-						coder->lz.read_pos
-						- coder->rep_distances[0] - 1
-						- coder->additional_offset];
-				literal_encode_matched(subcoder, match_byte, cur_byte);
-			}
-
-			update_literal(coder->state);
-			coder->previous_byte = cur_byte;
-
-		} else {
-			// It's a match.
-			bit_encode_1(coder->is_match[coder->state][pos_state]);
-
-			if (pos < REP_DISTANCES) {
-				// It's a repeated match i.e. the same distance
-				// has been used earlier.
-				bit_encode_1(coder->is_rep[coder->state]);
-
-				if (pos == 0) {
-					bit_encode_0(coder->is_rep0[coder->state]);
-					const uint32_t symbol = (len == 1) ? 0 : 1;
-					bit_encode(coder->is_rep0_long[coder->state][pos_state],
-							symbol);
-				} else {
-					const uint32_t distance = coder->rep_distances[pos];
-					bit_encode_1(coder->is_rep0[coder->state]);
-
-					if (pos == 1) {
-						bit_encode_0(coder->is_rep1[coder->state]);
-					} else {
-						bit_encode_1(coder->is_rep1[coder->state]);
-						bit_encode(coder->is_rep2[coder->state], pos - 2);
-
-						if (pos == 3)
-							coder->rep_distances[3] = coder->rep_distances[2];
-
-						coder->rep_distances[2] = coder->rep_distances[1];
-					}
-
-					coder->rep_distances[1] = coder->rep_distances[0];
-					coder->rep_distances[0] = distance;
-				}
-
-				if (len == 1) {
-					update_short_rep(coder->state);
-				} else {
-					length_encode(coder->rep_len_encoder,
-							len - MATCH_MIN_LEN, pos_state,
-							best_compression);
-					update_long_rep(coder->state);
-				}
-
-			} else {
-				bit_encode_0(coder->is_rep[coder->state]);
-				update_match(coder->state);
-				length_encode(coder->match_len_encoder, len - MATCH_MIN_LEN,
-						pos_state, best_compression);
-				pos -= REP_DISTANCES;
-
-				const uint32_t pos_slot = get_pos_slot(pos);
-				const uint32_t len_to_pos_state = get_len_to_pos_state(len);
-				bittree_encode(coder->pos_slot_encoder[len_to_pos_state],
-						POS_SLOT_BITS, pos_slot);
-
-				if (pos_slot >= START_POS_MODEL_INDEX) {
-					const uint32_t footer_bits = (pos_slot >> 1) - 1;
-					const uint32_t base = (2 | (pos_slot & 1)) << footer_bits;
-					const uint32_t pos_reduced = pos - base;
-
-					if (pos_slot < END_POS_MODEL_INDEX) {
-						bittree_reverse_encode(
-								coder->pos_encoders + base - pos_slot - 1,
-								footer_bits, pos_reduced);
-					} else {
-						rc_encode_direct_bits(pos_reduced >> ALIGN_BITS,
-								footer_bits - ALIGN_BITS);
-						bittree_reverse_encode(coder->pos_align_encoder,
-								ALIGN_BITS, pos_reduced & ALIGN_MASK);
-						++coder->align_price_count;
-					}
-				}
-
-				coder->rep_distances[3] = coder->rep_distances[2];
-				coder->rep_distances[2] = coder->rep_distances[1];
-				coder->rep_distances[1] = coder->rep_distances[0];
-				coder->rep_distances[0] = pos;
-				++coder->match_price_count;
-			}
-
-			coder->previous_byte = coder->lz.buffer[
-					coder->lz.read_pos + len - 1
-					- coder->additional_offset];
-		}
-
-		assert(coder->additional_offset >= len);
-		coder->additional_offset -= len;
-		coder->now_pos += len;
+		encode_symbol(coder, pos, len);
 	}
 
-	// Check if everything is done.
-	bool all_done = false;
-	if (coder->lz.sequence != SEQ_RUN
-			&& coder->lz.read_pos == coder->lz.write_pos
-			&& coder->additional_offset == 0) {
-		assert(coder->longest_match_was_found == false);
-
-		if (coder->lz.uncompressed_size == LZMA_VLI_VALUE_UNKNOWN
-				|| coder->lz.sequence == SEQ_FLUSH) {
-			// Write special marker: flush marker or end of payload
-			// marker. Both are encoded as a match with distance of
-			// UINT32_MAX. The match length codes the type of the marker.
-			const uint32_t pos_state = coder->now_pos & pos_mask;
-			bit_encode_1(coder->is_match[coder->state][pos_state]);
-			bit_encode_0(coder->is_rep[coder->state]);
-			update_match(coder->state);
-
-			const uint32_t len = coder->lz.sequence == SEQ_FLUSH
-					? LEN_SPECIAL_FLUSH : LEN_SPECIAL_EOPM;
-			length_encode(coder->match_len_encoder, len - MATCH_MIN_LEN,
-					pos_state, best_compression);
-
-			const uint32_t pos_slot = (1 << POS_SLOT_BITS) - 1;
-			const uint32_t len_to_pos_state = get_len_to_pos_state(len);
-			bittree_encode(coder->pos_slot_encoder[len_to_pos_state],
-					POS_SLOT_BITS, pos_slot);
-
-			const uint32_t footer_bits = 30;
-			const uint32_t pos_reduced
-					= (UINT32_C(1) << footer_bits) - 1;
-			rc_encode_direct_bits(pos_reduced >> ALIGN_BITS,
-					footer_bits - ALIGN_BITS);
+	assert(!coder->longest_match_was_found);
 
-			bittree_reverse_encode(coder->pos_align_encoder, ALIGN_BITS,
-					pos_reduced & ALIGN_MASK);
-		}
+	if (coder->is_flushed) {
+		coder->is_flushed = false;
+		return true;
+	}
 
-		// Flush the last bytes of compressed data from
-		// the range coder to the output buffer.
-		rc_flush();
+	// We don't support encoding old LZMA streams without EOPM, and LZMA2
+	// doesn't use EOPM at LZMA level.
+	if (coder->write_eopm)
+		encode_eopm(coder);
 
-		rc_reset(rc);
+	rc_flush(&coder->rc);
 
-		// All done. Note that some output bytes might be
-		// pending in coder->lz.temp. lzma_lz_encode() will
-		// take care of those bytes.
-		all_done = true;
+	if (rc_encode(&coder->rc, out, out_pos, out_size)) {
+		coder->is_flushed = true;
+		return false;
 	}
 
-	// Store local variables back to *coder.
-	coder->rc = rc;
-	*out_pos = out_pos_local;
-
-	return all_done;
+	return true;
 }
diff --git a/src/liblzma/lzma/lzma_encoder_getoptimum.c b/src/liblzma/lzma/lzma_encoder_getoptimum.c
index 535508ee..b175e4cb 100644
--- a/src/liblzma/lzma/lzma_encoder_getoptimum.c
+++ b/src/liblzma/lzma/lzma_encoder_getoptimum.c
@@ -104,6 +104,36 @@ do { \
 
 
 static void
+fill_length_prices(lzma_length_encoder *lc, uint32_t pos_state)
+{
+	const uint32_t num_symbols = lc->table_size;
+	const uint32_t a0 = bit_get_price_0(lc->choice);
+	const uint32_t a1 = bit_get_price_1(lc->choice);
+	const uint32_t b0 = a1 + bit_get_price_0(lc->choice2);
+	const uint32_t b1 = a1 + bit_get_price_1(lc->choice2);
+
+	uint32_t *prices = lc->prices[pos_state];
+	uint32_t i = 0;
+
+	for (i = 0; i < num_symbols && i < LEN_LOW_SYMBOLS; ++i)
+		prices[i] = a0 + bittree_get_price(lc->low[pos_state],
+				LEN_LOW_BITS, i);
+
+	for (; i < num_symbols && i < LEN_LOW_SYMBOLS + LEN_MID_SYMBOLS; ++i)
+		prices[i] = b0 + bittree_get_price(lc->mid[pos_state],
+				LEN_MID_BITS, i - LEN_LOW_SYMBOLS);
+
+	for (; i < num_symbols; ++i)
+		prices[i] = b1 + bittree_get_price(lc->high, LEN_HIGH_BITS,
+				i - LEN_LOW_SYMBOLS - LEN_MID_SYMBOLS);
+
+	lc->counters[pos_state] = num_symbols;
+
+	return;
+}
+
+
+static void
 fill_distances_prices(lzma_coder *coder)
 {
 	uint32_t temp_prices[FULL_DISTANCES];
@@ -254,6 +284,9 @@ extern void
 lzma_get_optimum(lzma_coder *restrict coder,
 		uint32_t *restrict back_res, uint32_t *restrict len_res)
 {
+	uint32_t position = coder->now_pos;
+	uint32_t pos_state = position & coder->pos_mask;
+
 	// Update the price tables. In the C++ LZMA SDK 4.42 this was done in both
 	// initialization function and in the main loop. In liblzma they were
 	// moved into this single place.
@@ -265,6 +298,13 @@ lzma_get_optimum(lzma_coder *restrict coder,
 			fill_align_prices(coder);
 	}
 
+	if (coder->prev_len_encoder != NULL) {
+		if (--coder->prev_len_encoder->counters[pos_state] == 0)
+			fill_length_prices(coder->prev_len_encoder, pos_state);
+
+		coder->prev_len_encoder = NULL;
+	}
+
 
 	if (coder->optimum_end_index != coder->optimum_current_index) {
 		*len_res = coder->optimum[coder->optimum_current_index].pos_prev
@@ -312,7 +352,7 @@ lzma_get_optimum(lzma_coder *restrict coder,
 	uint32_t rep_max_index = 0;
 
 	for (uint32_t i = 0; i < REP_DISTANCES; ++i) {
-		reps[i] = coder->rep_distances[i];
+		reps[i] = coder->reps[i];
 		const uint32_t back_offset = reps[i] + 1;
 
 		if (buf[0] != *(buf - back_offset)
@@ -356,13 +396,8 @@ lzma_get_optimum(lzma_coder *restrict coder,
 		return;
 	}
 
-	const uint32_t pos_mask = coder->pos_mask;
-
 	coder->optimum[0].state = coder->state;
 
-	uint32_t position = coder->now_pos;
-	uint32_t pos_state = (position & pos_mask);
-
 	coder->optimum[1].price = bit_get_price_0(
 				coder->is_match[coder->state][pos_state])
 			+ literal_get_price(
@@ -575,7 +610,7 @@ lzma_get_optimum(lzma_coder *restrict coder,
 	current_byte = *buf;
 	match_byte = *(buf - reps[0] - 1);
 
-	pos_state = position & pos_mask;
+	pos_state = position & coder->pos_mask;
 
 	const uint32_t cur_and_1_price = cur_price
 			+ bit_get_price_0(coder->is_match[state][pos_state])
@@ -640,7 +675,7 @@ lzma_get_optimum(lzma_coder *restrict coder,
 			uint32_t state_2 = state;
 			update_literal(state_2);
 
-			const uint32_t pos_state_next = (position + 1) & pos_mask;
+			const uint32_t pos_state_next = (position + 1) & coder->pos_mask;
 			const uint32_t next_rep_match_price = cur_and_1_price
 					+ bit_get_price_1(coder->is_match[state_2][pos_state_next])
 					+ bit_get_price_1(coder->is_rep[state_2]);
@@ -719,7 +754,7 @@ lzma_get_optimum(lzma_coder *restrict coder,
 			uint32_t state_2 = state;
 			update_long_rep(state_2);
 
-			uint32_t pos_state_next = (position + len_test) & pos_mask;
+			uint32_t pos_state_next = (position + len_test) & coder->pos_mask;
 
 			const uint32_t cur_and_len_char_price = price
 					+ length_get_price(coder->rep_len_encoder,
@@ -732,7 +767,7 @@ lzma_get_optimum(lzma_coder *restrict coder,
 
 			update_literal(state_2);
 
-			pos_state_next = (position + len_test + 1) & pos_mask;
+			pos_state_next = (position + len_test + 1) & coder->pos_mask;
 
 			const uint32_t next_rep_match_price = cur_and_len_char_price
 					+ bit_get_price_1(coder->is_match[state_2][pos_state_next])
@@ -829,7 +864,7 @@ lzma_get_optimum(lzma_coder *restrict coder,
 					uint32_t state_2 = state;
 					update_match(state_2);
 					uint32_t pos_state_next
-							= (position + len_test) & pos_mask;
+							= (position + len_test) & coder->pos_mask;
 
 					const uint32_t cur_and_len_char_price = cur_and_len_price
 							+ bit_get_price_0(
@@ -844,7 +879,7 @@ lzma_get_optimum(lzma_coder *restrict coder,
 								buf[len_test]);
 
 					update_literal(state_2);
-					pos_state_next = (pos_state_next + 1) & pos_mask;
+					pos_state_next = (pos_state_next + 1) & coder->pos_mask;
 
 					const uint32_t next_rep_match_price
 							= cur_and_len_char_price
diff --git a/src/liblzma/lzma/lzma_encoder_getoptimumfast.c b/src/liblzma/lzma/lzma_encoder_getoptimumfast.c
index e6cee19d..fa06be21 100644
--- a/src/liblzma/lzma/lzma_encoder_getoptimumfast.c
+++ b/src/liblzma/lzma/lzma_encoder_getoptimumfast.c
@@ -65,7 +65,7 @@ lzma_get_optimum_fast(lzma_coder *restrict coder,
 	uint32_t rep_max_index = 0;
 
 	for (uint32_t i = 0; i < REP_DISTANCES; ++i) {
-		const uint32_t back_offset = coder->rep_distances[i] + 1;
+		const uint32_t back_offset = coder->reps[i] + 1;
 
 		// If the first two bytes (2 == MATCH_MIN_LEN) do not match,
 		// this rep_distance[i] is not useful. This is indicated
@@ -168,7 +168,7 @@ lzma_get_optimum_fast(lzma_coder *restrict coder,
 		--num_available_bytes;
 
 		for (uint32_t i = 0; i < REP_DISTANCES; ++i) {
-			const uint32_t back_offset = coder->rep_distances[i] + 1;
+			const uint32_t back_offset = coder->reps[i] + 1;
 
 			if (buf[1] != *(buf + 1 - back_offset)
 					|| buf[2] != *(buf + 2 - back_offset)) {
diff --git a/src/liblzma/lzma/lzma_encoder_init.c b/src/liblzma/lzma/lzma_encoder_init.c
index 0e3fb769..306cea8c 100644
--- a/src/liblzma/lzma/lzma_encoder_init.c
+++ b/src/liblzma/lzma/lzma_encoder_init.c
@@ -42,7 +42,7 @@ length_encoder_reset(lzma_length_encoder *lencoder,
 
 	// NLength::CPriceTableEncoder::UpdateTables()
 	for (size_t pos_state = 0; pos_state < num_pos_states; ++pos_state)
-		lzma_length_encoder_update_table(lencoder, pos_state);
+		lencoder->counters[pos_state] = 1;
 
 	return;
 }
@@ -112,7 +112,6 @@ lzma_lzma_encoder_init(lzma_next_coder *next, lzma_allocator *allocator,
 	{
 		const lzma_ret ret = lzma_lz_encoder_reset(
 				&next->coder->lz, allocator, &lzma_lzma_encode,
-				filters[0].uncompressed_size,
 				options->dictionary_size, OPTS,
 				options->fast_bytes, MATCH_MAX_LEN + 1 + OPTS,
 				options->match_finder,
@@ -143,13 +142,13 @@ lzma_lzma_encoder_init(lzma_next_coder *next, lzma_allocator *allocator,
 	next->coder->fast_bytes = options->fast_bytes;
 
 	// Range coder
-	rc_reset(next->coder->rc);
+	rc_reset(&next->coder->rc);
 
 	// State
 	next->coder->state = 0;
 	next->coder->previous_byte = 0;
 	for (size_t i = 0; i < REP_DISTANCES; ++i)
-		next->coder->rep_distances[i] = 0;
+		next->coder->reps[i] = 0;
 
 	// Bit encoders
 	for (size_t i = 0; i < STATES; ++i) {
@@ -190,6 +189,8 @@ lzma_lzma_encoder_init(lzma_next_coder *next, lzma_allocator *allocator,
 
 	next->coder->now_pos = 0;
 	next->coder->is_initialized = false;
+	next->coder->is_flushed = false,
+	next->coder->write_eopm = true;
 
 	// Initialize the next decoder in the chain, if any.
 	{
diff --git a/src/liblzma/lzma/lzma_encoder_private.h b/src/liblzma/lzma/lzma_encoder_private.h
index 0feaf26a..4159b468 100644
--- a/src/liblzma/lzma/lzma_encoder_private.h
+++ b/src/liblzma/lzma/lzma_encoder_private.h
@@ -26,14 +26,6 @@
 #include "lz_encoder.h"
 #include "range_encoder.h"
 
-// We need space for about two encoding loops, because there is no check
-// for available buffer space before end of payload marker gets written.
-// 2*26 bytes should be enough for this... but Lasse isn't very sure about
-// the exact value. 64 bytes certainly is enough. :-)
-#if LZMA_LZ_TEMP_SIZE < 64
-#	error LZMA_LZ_TEMP_SIZE is too small.
-#endif
-
 
 #define move_pos(num) \
 do { \
@@ -72,7 +64,7 @@ typedef struct {
 	uint32_t pos_prev;  // pos_next;
 	uint32_t back_prev;
 
-	uint32_t backs[4];
+	uint32_t backs[REP_DISTANCES];
 
 } lzma_optimal;
 
@@ -90,7 +82,7 @@ struct lzma_coder_s {
 	// State
 	lzma_lzma_state state;
 	uint8_t previous_byte;
-	uint32_t rep_distances[REP_DISTANCES];
+	uint32_t reps[REP_DISTANCES];
 
 	// Misc
 	uint32_t match_distances[MATCH_MAX_LEN * 2 + 2 + 1];
@@ -99,6 +91,8 @@ struct lzma_coder_s {
 	uint32_t now_pos; // Lowest 32 bits are enough here.
 	bool best_compression;           ///< True when LZMA_MODE_BEST is used
 	bool is_initialized;
+	bool is_flushed;
+	bool write_eopm;
 
 	// Literal encoder
 	lzma_literal_coder *literal_coder;
@@ -119,6 +113,7 @@ struct lzma_coder_s {
 	// Length encoders
 	lzma_length_encoder match_len_encoder;
 	lzma_length_encoder rep_len_encoder;
+	lzma_length_encoder *prev_len_encoder;
 
 	// Optimal
 	lzma_optimal optimum[OPTS];