aboutsummaryrefslogtreecommitdiff
path: root/src/liblzma/lzma
diff options
context:
space:
mode:
authorLasse Collin <lasse.collin@tukaani.org>2007-12-09 00:42:33 +0200
committerLasse Collin <lasse.collin@tukaani.org>2007-12-09 00:42:33 +0200
commit5d018dc03549c1ee4958364712fb0c94e1bf2741 (patch)
tree1b211911fb33fddb3f04b77f99e81df23623ffc4 /src/liblzma/lzma
downloadxz-5d018dc03549c1ee4958364712fb0c94e1bf2741.tar.xz
Imported to git.
Diffstat (limited to 'src/liblzma/lzma')
-rw-r--r--src/liblzma/lzma/Makefile.am43
-rw-r--r--src/liblzma/lzma/lzma_common.h128
-rw-r--r--src/liblzma/lzma/lzma_decoder.c844
-rw-r--r--src/liblzma/lzma/lzma_decoder.h41
-rw-r--r--src/liblzma/lzma/lzma_encoder.c413
-rw-r--r--src/liblzma/lzma/lzma_encoder.h35
-rw-r--r--src/liblzma/lzma/lzma_encoder_features.c59
-rw-r--r--src/liblzma/lzma/lzma_encoder_getoptimum.c893
-rw-r--r--src/liblzma/lzma/lzma_encoder_getoptimumfast.c201
-rw-r--r--src/liblzma/lzma/lzma_encoder_init.c245
-rw-r--r--src/liblzma/lzma/lzma_encoder_presets.c34
-rw-r--r--src/liblzma/lzma/lzma_encoder_private.h225
-rw-r--r--src/liblzma/lzma/lzma_literal.c74
-rw-r--r--src/liblzma/lzma/lzma_literal.h74
14 files changed, 3309 insertions, 0 deletions
diff --git a/src/liblzma/lzma/Makefile.am b/src/liblzma/lzma/Makefile.am
new file mode 100644
index 00000000..48f3bb23
--- /dev/null
+++ b/src/liblzma/lzma/Makefile.am
@@ -0,0 +1,43 @@
+##
+## Copyright (C) 2007 Lasse Collin
+##
+## This library is free software; you can redistribute it and/or
+## modify it under the terms of the GNU Lesser General Public
+## License as published by the Free Software Foundation; either
+## version 2.1 of the License, or (at your option) any later version.
+##
+## This library is distributed in the hope that it will be useful,
+## but WITHOUT ANY WARRANTY; without even the implied warranty of
+## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+## Lesser General Public License for more details.
+##
+
+noinst_LTLIBRARIES = liblzma4.la
+liblzma4_la_CPPFLAGS = \
+ -I@top_srcdir@/src/liblzma/api \
+ -I@top_srcdir@/src/liblzma/common \
+ -I@top_srcdir@/src/liblzma/lz \
+ -I@top_srcdir@/src/liblzma/rangecoder
+
+liblzma4_la_SOURCES = \
+ lzma_common.h \
+ lzma_literal.c \
+ lzma_literal.h
+
+if COND_MAIN_ENCODER
+liblzma4_la_SOURCES += \
+ lzma_encoder.h \
+ lzma_encoder.c \
+ lzma_encoder_presets.c \
+ lzma_encoder_private.h \
+ lzma_encoder_init.c \
+ lzma_encoder_features.c \
+ lzma_encoder_getoptimum.c \
+ lzma_encoder_getoptimumfast.c
+endif
+
+if COND_MAIN_DECODER
+liblzma4_la_SOURCES += \
+ lzma_decoder.c \
+ lzma_decoder.h
+endif
diff --git a/src/liblzma/lzma/lzma_common.h b/src/liblzma/lzma/lzma_common.h
new file mode 100644
index 00000000..4ff59ae6
--- /dev/null
+++ b/src/liblzma/lzma/lzma_common.h
@@ -0,0 +1,128 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file lzma_common.h
+/// \brief Private definitions common to LZMA encoder and decoder
+//
+// Copyright (C) 1999-2006 Igor Pavlov
+// Copyright (C) 2007 Lasse Collin
+//
+// This library is free software; you can redistribute it and/or
+// modify it under the terms of the GNU Lesser General Public
+// License as published by the Free Software Foundation; either
+// version 2.1 of the License, or (at your option) any later version.
+//
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+// Lesser General Public License for more details.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#ifndef LZMA_LZMA_COMMON_H
+#define LZMA_LZMA_COMMON_H
+
+#include "common.h"
+#include "lzma_literal.h"
+#include "range_common.h"
+
+
+///////////////
+// Constants //
+///////////////
+
+#define REP_DISTANCES 4
+#define STATES 12
+#define LIT_STATES 7
+
+#define POS_SLOT_BITS 6
+#define DICT_LOG_SIZE_MAX 30
+#define DIST_TABLE_SIZE_MAX (DICT_LOG_SIZE_MAX * 2)
+#if (UINT32_C(1) << DICT_LOG_SIZE_MAX) != LZMA_DICTIONARY_SIZE_MAX
+# error DICT_LOG_SIZE_MAX is inconsistent with LZMA_DICTIONARY_SIZE_MAX
+#endif
+
+// 2 is for speed optimization
+#define LEN_TO_POS_STATES_BITS 2
+#define LEN_TO_POS_STATES (1 << LEN_TO_POS_STATES_BITS)
+
+#define MATCH_MIN_LEN 2
+
+#define ALIGN_BITS 4
+#define ALIGN_TABLE_SIZE (1 << ALIGN_BITS)
+#define ALIGN_MASK (ALIGN_TABLE_SIZE - 1)
+
+#define START_POS_MODEL_INDEX 4
+#define END_POS_MODEL_INDEX 14
+#define POS_MODELS (END_POS_MODEL_INDEX - START_POS_MODEL_INDEX)
+
+#define FULL_DISTANCES (1 << (END_POS_MODEL_INDEX / 2))
+
+#define LIT_POS_STATES_BITS_MAX LZMA_LITERAL_POS_BITS_MAX
+#define LIT_CONTEXT_BITS_MAX LZMA_LITERAL_CONTEXT_BITS_MAX
+
+#define POS_STATES_BITS_MAX LZMA_POS_BITS_MAX
+#define POS_STATES_MAX (1 << POS_STATES_BITS_MAX)
+
+
+// Length coder & Length price table encoder
+#define LEN_LOW_BITS 3
+#define LEN_LOW_SYMBOLS (1 << LEN_LOW_BITS)
+#define LEN_MID_BITS 3
+#define LEN_MID_SYMBOLS (1 << LEN_MID_BITS)
+#define LEN_HIGH_BITS 8
+#define LEN_HIGH_SYMBOLS (1 << LEN_HIGH_BITS)
+#define LEN_SYMBOLS (LEN_LOW_SYMBOLS + LEN_MID_SYMBOLS + LEN_HIGH_SYMBOLS)
+#define LEN_SPEC_SYMBOLS (LOW_LOW_SYMBOLS + LEN_MID_LEN_SYMBOLS)
+#define MATCH_MAX_LEN (MATCH_MIN_LEN + LEN_SYMBOLS - 1)
+
+// Total number of probs in a Len Encoder
+#define LEN_CODER_TOTAL_PROBS (LEN_HIGH_CODER + LEN_HIGH_SYMBOLS)
+
+// Price table size of Len Encoder
+#define LEN_PRICES (LEN_SYMBOLS << POS_STATES_BITS_MAX)
+
+
+// Optimal - Number of entries in the optimum array.
+#define OPTS (1 << 12)
+
+
+// Miscellaneous
+#define INFINITY_PRICE 0x0FFFFFFF
+
+
+////////////
+// Macros //
+////////////
+
+#define get_len_to_pos_state(len) \
+ ((len) < LEN_TO_POS_STATES + MATCH_MIN_LEN \
+ ? (len) - MATCH_MIN_LEN \
+ : LEN_TO_POS_STATES - 1)
+
+
+///////////
+// State //
+///////////
+
+// Used for updating strm->data->state in both encoder and decoder.
+
+#define update_char(index) \
+ index = ((index) < 4 \
+ ? 0 \
+ : ((index) < 10 \
+ ? (index) - 3 \
+ : (index) - 6))
+
+#define update_match(index) \
+ index = ((index) < LIT_STATES ? 7 : 10)
+
+#define update_rep(index) \
+ index = ((index) < LIT_STATES ? 8 : 11)
+
+#define update_short_rep(index) \
+ index = ((index) < LIT_STATES ? 9 : 11)
+
+#define is_char_state(index) \
+ ((index) < LIT_STATES)
+
+#endif
diff --git a/src/liblzma/lzma/lzma_decoder.c b/src/liblzma/lzma/lzma_decoder.c
new file mode 100644
index 00000000..6e2c166d
--- /dev/null
+++ b/src/liblzma/lzma/lzma_decoder.c
@@ -0,0 +1,844 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file lzma_decoder.c
+/// \brief LZMA decoder
+//
+// Copyright (C) 1999-2006 Igor Pavlov
+// Copyright (C) 2007 Lasse Collin
+//
+// This library is free software; you can redistribute it and/or
+// modify it under the terms of the GNU Lesser General Public
+// License as published by the Free Software Foundation; either
+// version 2.1 of the License, or (at your option) any later version.
+//
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+// Lesser General Public License for more details.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#include "lzma_common.h"
+#include "lzma_decoder.h"
+#include "lz_decoder.h"
+#include "range_decoder.h"
+
+
+/// REQUIRED_IN_BUFFER_SIZE is the number of required input bytes
+/// for the worst case: longest match with longest distance.
+/// LZMA_IN_BUFFER_SIZE must be larger than REQUIRED_IN_BUFFER_SIZE.
+/// 23 bits = 2 (match select) + 10 (len) + 6 (distance) + 4 (align)
+/// + 1 (rc_normalize)
+///
+/// \todo Is this correct for sure?
+///
+#define REQUIRED_IN_BUFFER_SIZE \
+ ((23 * (BIT_MODEL_TOTAL_BITS - MOVE_BITS + 1) + 26 + 9) / 8)
+
+
+// Length decoders are easiest to have as macros, because they use range
+// decoder macros, which use local variables rc_range and rc_code.
+
+#define length_decode(target, len_decoder, pos_state) \
+do { \
+ if_bit_0(len_decoder.choice) { \
+ update_bit_0(len_decoder.choice); \
+ target = MATCH_MIN_LEN; \
+ bittree_decode(target, \
+ len_decoder.low[pos_state], LEN_LOW_BITS); \
+ } else { \
+ update_bit_1(len_decoder.choice); \
+ if_bit_0(len_decoder.choice2) { \
+ update_bit_0(len_decoder.choice2); \
+ target = MATCH_MIN_LEN + LEN_LOW_SYMBOLS; \
+ bittree_decode(target, len_decoder.mid[pos_state], \
+ LEN_MID_BITS); \
+ } else { \
+ update_bit_1(len_decoder.choice2); \
+ target = MATCH_MIN_LEN + LEN_LOW_SYMBOLS \
+ + LEN_MID_SYMBOLS; \
+ bittree_decode(target, len_decoder.high, \
+ LEN_HIGH_BITS); \
+ } \
+ } \
+} while (0)
+
+
+#define length_decode_dummy(target, len_decoder, pos_state) \
+do { \
+ if_bit_0(len_decoder.choice) { \
+ update_bit_0_dummy(); \
+ target = MATCH_MIN_LEN; \
+ bittree_decode_dummy(target, \
+ len_decoder.low[pos_state], LEN_LOW_BITS); \
+ } else { \
+ update_bit_1_dummy(); \
+ if_bit_0(len_decoder.choice2) { \
+ update_bit_0_dummy(); \
+ target = MATCH_MIN_LEN + LEN_LOW_SYMBOLS; \
+ bittree_decode_dummy(target, \
+ len_decoder.mid[pos_state], \
+ LEN_MID_BITS); \
+ } else { \
+ update_bit_1_dummy(); \
+ target = MATCH_MIN_LEN + LEN_LOW_SYMBOLS \
+ + LEN_MID_SYMBOLS; \
+ bittree_decode_dummy(target, len_decoder.high, \
+ LEN_HIGH_BITS); \
+ } \
+ } \
+} while (0)
+
+
+typedef struct {
+ probability choice;
+ probability choice2;
+ probability low[POS_STATES_MAX][LEN_LOW_SYMBOLS];
+ probability mid[POS_STATES_MAX][LEN_MID_SYMBOLS];
+ probability high[LEN_HIGH_SYMBOLS];
+} lzma_length_decoder;
+
+
+struct lzma_coder_s {
+ /// Data of the next coder, if any.
+ lzma_next_coder next;
+
+ /// Sliding output window a.k.a. dictionary a.k.a. history buffer.
+ lzma_lz_decoder lz;
+
+ // Range coder
+ lzma_range_decoder rc;
+
+ // State
+ uint32_t state;
+ uint32_t rep0; ///< Distance of the latest match
+ uint32_t rep1; ///< Distance of second latest match
+ uint32_t rep2; ///< Distance of third latest match
+ uint32_t rep3; ///< Distance of fourth latest match
+ uint32_t pos_bits;
+ uint32_t pos_mask;
+ uint32_t now_pos; // Lowest 32-bits are enough here.
+
+ lzma_literal_coder *literal_coder;
+
+ /// If 1, it's a match. Otherwise it's a single 8-bit literal.
+ probability is_match[STATES][POS_STATES_MAX];
+
+ /// If 1, it's a repeated match. The distance is one of rep0 .. rep3.
+ probability is_rep[STATES];
+
+ /// If 0, distance of a repeated match is rep0.
+ /// Otherwise check is_rep1.
+ probability is_rep0[STATES];
+
+ /// If 0, distance of a repeated match is rep1.
+ /// Otherwise check is_rep2.
+ probability is_rep1[STATES];
+
+ /// If 0, distance of a repeated match is rep2. Otherwise it is rep3.
+ probability is_rep2[STATES];
+
+ /// If 1, the repeated match has length of one byte. Otherwise
+ /// the length is decoded from rep_match_len_decoder.
+ probability is_rep0_long[STATES][POS_STATES_MAX];
+
+ probability pos_slot_decoder[LEN_TO_POS_STATES][1 << POS_SLOT_BITS];
+ probability pos_decoders[FULL_DISTANCES - END_POS_MODEL_INDEX];
+ probability pos_align_decoder[1 << ALIGN_BITS];
+
+ /// Length of a match
+ lzma_length_decoder len_decoder;
+
+ /// Length of a repeated match.
+ lzma_length_decoder rep_match_len_decoder;
+
+ /// The first five bytes of LZMA compressed data are treated
+ /// specially. Once they are read, this stays at zero.
+ size_t init_bytes_left;
+};
+
+
+/// \brief Check if the next iteration of the decoder loop can be run.
+///
+/// \note There must always be REQUIRED_IN_BUFFER_SIZE bytes
+/// readable space!
+///
+static bool lzma_attribute((pure))
+decode_dummy(const lzma_coder *restrict coder,
+ const uint8_t *restrict in, size_t in_pos_local,
+ const size_t in_size, uint32_t rc_range, uint32_t rc_code,
+ uint32_t state, uint32_t rep0, const uint32_t now_pos)
+{
+ uint32_t rc_bound;
+
+ do {
+ const uint32_t pos_state = now_pos & coder->pos_mask;
+
+ if_bit_0(coder->is_match[state][pos_state]) {
+ // It's a literal i.e. a single 8-bit byte.
+
+ update_bit_0_dummy();
+
+ const probability *subcoder = literal_get_subcoder(
+ coder->literal_coder,
+ now_pos, lz_get_byte(coder->lz, 0));
+ uint32_t symbol = 1;
+
+ if (!is_char_state(state)) {
+ // Decode literal with match byte.
+
+ assert(rep0 != UINT32_MAX);
+ uint32_t match_byte
+ = lz_get_byte(coder->lz, rep0);
+
+ do {
+ match_byte <<= 1;
+ const uint32_t match_bit
+ = match_byte & 0x100;
+ const uint32_t subcoder_index = 0x100
+ + match_bit + symbol;
+
+ if_bit_0(subcoder[subcoder_index]) {
+ update_bit_0_dummy();
+ symbol <<= 1;
+ if (match_bit != 0)
+ break;
+ } else {
+ update_bit_1_dummy();
+ symbol = (symbol << 1) | 1;
+ if (match_bit == 0)
+ break;
+ }
+ } while (symbol < 0x100);
+ }
+
+ // Decode literal without match byte. This is also
+ // the tail of the with-match-byte function.
+ while (symbol < 0x100) {
+ if_bit_0(subcoder[symbol]) {
+ update_bit_0_dummy();
+ symbol <<= 1;
+ } else {
+ update_bit_1_dummy();
+ symbol = (symbol << 1) | 1;
+ }
+ }
+
+ break;
+ }
+
+ update_bit_1_dummy();
+ uint32_t len;
+
+ if_bit_0(coder->is_rep[state]) {
+ update_bit_0_dummy();
+ length_decode_dummy(len, coder->len_decoder, pos_state);
+ update_match(state);
+
+ const uint32_t len_to_pos_state
+ = get_len_to_pos_state(len);
+ uint32_t pos_slot = 0;
+ bittree_decode_dummy(pos_slot, coder->pos_slot_decoder[
+ len_to_pos_state], POS_SLOT_BITS);
+ assert(pos_slot <= 63);
+
+ if (pos_slot >= START_POS_MODEL_INDEX) {
+ uint32_t direct_bits = (pos_slot >> 1) - 1;
+ assert(direct_bits >= 1 && direct_bits <= 31);
+ rep0 = 2 | (pos_slot & 1);
+
+ if (pos_slot < END_POS_MODEL_INDEX) {
+ assert(direct_bits <= 5);
+ rep0 <<= direct_bits;
+ assert(rep0 <= 96);
+ // -1 is fine, because
+ // bittree_reverse_decode()
+ // starts from table index [1]
+ // (not [0]).
+ assert((int32_t)(rep0 - pos_slot - 1)
+ >= -1);
+ assert((int32_t)(rep0 - pos_slot - 1)
+ <= 82);
+ // We add the result to rep0, so rep0
+ // must not be part of second argument
+ // of the macro.
+ const int32_t offset
+ = rep0 - pos_slot - 1;
+ bittree_reverse_decode_dummy(
+ coder->pos_decoders + offset,
+ direct_bits);
+ } else {
+ // Decode direct bits
+ assert(pos_slot >= 14);
+ assert(direct_bits >= 6);
+ direct_bits -= ALIGN_BITS;
+ assert(direct_bits >= 2);
+ do {
+ rc_normalize();
+ rc_range >>= 1;
+ const uint32_t t
+ = (rc_code - rc_range)
+ >> 31;
+ rc_code -= rc_range & (t - 1);
+ } while (--direct_bits > 0);
+ rep0 <<= ALIGN_BITS;
+
+ bittree_reverse_decode_dummy(
+ coder->pos_align_decoder,
+ ALIGN_BITS);
+ }
+ }
+
+ } else {
+ update_bit_1_dummy();
+
+ if_bit_0(coder->is_rep0[state]) {
+ update_bit_0_dummy();
+
+ if_bit_0(coder->is_rep0_long[state][
+ pos_state]) {
+ update_bit_0_dummy();
+ break;
+ } else {
+ update_bit_1_dummy();
+ }
+
+ } else {
+ update_bit_1_dummy();
+
+ if_bit_0(coder->is_rep1[state]) {
+ update_bit_0_dummy();
+ } else {
+ update_bit_1_dummy();
+
+ if_bit_0(coder->is_rep2[state]) {
+ update_bit_0_dummy();
+ } else {
+ update_bit_1_dummy();
+ }
+ }
+ }
+
+ length_decode_dummy(len, coder->rep_match_len_decoder,
+ pos_state);
+ }
+ } while (0);
+
+ rc_normalize();
+
+ // Validate the buffer position.
+ if (in_pos_local > in_size)
+ return false;
+
+ return true;
+}
+
+
+static bool
+decode_real(lzma_coder *restrict coder, const uint8_t *restrict in,
+ size_t *restrict in_pos, size_t in_size, bool has_safe_buffer)
+{
+ ////////////////////
+ // Initialization //
+ ////////////////////
+
+ while (coder->init_bytes_left > 0) {
+ if (*in_pos == in_size)
+ return false;
+
+ coder->rc.code = (coder->rc.code << 8) | in[*in_pos];
+ ++*in_pos;
+ --coder->init_bytes_left;
+ }
+
+
+ ///////////////
+ // Variables //
+ ///////////////
+
+ // Making local copies of often-used variables improves both
+ // speed and readability.
+
+ // Range decoder
+ rc_to_local(coder->rc);
+
+ // State
+ uint32_t state = coder->state;
+ uint32_t rep0 = coder->rep0;
+ uint32_t rep1 = coder->rep1;
+ uint32_t rep2 = coder->rep2;
+ uint32_t rep3 = coder->rep3;
+
+ // Misc
+ uint32_t now_pos = coder->now_pos;
+
+ // Variables derived from decoder settings
+ const uint32_t pos_mask = coder->pos_mask;
+
+ size_t in_pos_local = *in_pos; // Local copy
+ size_t in_limit;
+ if (in_size <= REQUIRED_IN_BUFFER_SIZE)
+ in_limit = 0;
+ else
+ in_limit = in_size - REQUIRED_IN_BUFFER_SIZE;
+
+
+ while (coder->lz.pos < coder->lz.limit && (in_pos_local < in_limit
+ || (has_safe_buffer && decode_dummy(
+ coder, in, in_pos_local, in_size,
+ rc_range, rc_code, state, rep0, now_pos)))) {
+
+ /////////////////////
+ // Actual decoding //
+ /////////////////////
+
+ const uint32_t pos_state = now_pos & pos_mask;
+
+ if_bit_0(coder->is_match[state][pos_state]) {
+ update_bit_0(coder->is_match[state][pos_state]);
+
+ // It's a literal i.e. a single 8-bit byte.
+
+ probability *subcoder = literal_get_subcoder(
+ coder->literal_coder,
+ now_pos, lz_get_byte(coder->lz, 0));
+ uint32_t symbol = 1;
+
+ if (!is_char_state(state)) {
+ // Decode literal with match byte.
+
+ assert(rep0 != UINT32_MAX);
+ uint32_t match_byte
+ = lz_get_byte(coder->lz, rep0);
+
+ do {
+ match_byte <<= 1;
+ const uint32_t match_bit
+ = match_byte & 0x100;
+ const uint32_t subcoder_index = 0x100
+ + match_bit + symbol;
+
+ if_bit_0(subcoder[subcoder_index]) {
+ update_bit_0(subcoder[
+ subcoder_index]);
+ symbol <<= 1;
+ if (match_bit != 0)
+ break;
+ } else {
+ update_bit_1(subcoder[
+ subcoder_index]);
+ symbol = (symbol << 1) | 1;
+ if (match_bit == 0)
+ break;
+ }
+ } while (symbol < 0x100);
+ }
+
+ // Decode literal without match byte. This is also
+ // the tail of the with-match-byte function.
+ while (symbol < 0x100) {
+ if_bit_0(subcoder[symbol]) {
+ update_bit_0(subcoder[symbol]);
+ symbol <<= 1;
+ } else {
+ update_bit_1(subcoder[symbol]);
+ symbol = (symbol << 1) | 1;
+ }
+ }
+
+ // Put the decoded byte to the dictionary, update the
+ // decoder state, and start a new decoding loop.
+ coder->lz.dict[coder->lz.pos++] = (uint8_t)(symbol);
+ ++now_pos;
+ update_char(state);
+ continue;
+ }
+
+ // Instead of a new byte we are going to get a byte range
+ // (distance and length) which will be repeated from our
+ // output history.
+
+ update_bit_1(coder->is_match[state][pos_state]);
+ uint32_t len;
+
+ if_bit_0(coder->is_rep[state]) {
+ update_bit_0(coder->is_rep[state]);
+
+ // Not a repeated match
+ //
+ // We will decode a new distance and store
+ // the value to rep0.
+
+ // The latest three match distances are kept in
+ // memory in case there are repeated matches.
+ rep3 = rep2;
+ rep2 = rep1;
+ rep1 = rep0;
+
+ // Decode the length of the match.
+ length_decode(len, coder->len_decoder, pos_state);
+
+ update_match(state);
+
+ const uint32_t len_to_pos_state
+ = get_len_to_pos_state(len);
+ uint32_t pos_slot = 0;
+ bittree_decode(pos_slot, coder->pos_slot_decoder[
+ len_to_pos_state], POS_SLOT_BITS);
+ assert(pos_slot <= 63);
+
+ if (pos_slot >= START_POS_MODEL_INDEX) {
+ uint32_t direct_bits = (pos_slot >> 1) - 1;
+ assert(direct_bits >= 1 && direct_bits <= 30);
+ rep0 = 2 | (pos_slot & 1);
+
+ if (pos_slot < END_POS_MODEL_INDEX) {
+ assert(direct_bits <= 5);
+ rep0 <<= direct_bits;
+ assert(rep0 <= 96);
+ // -1 is fine, because
+ // bittree_reverse_decode()
+ // starts from table index [1]
+ // (not [0]).
+ assert((int32_t)(rep0 - pos_slot - 1)
+ >= -1);
+ assert((int32_t)(rep0 - pos_slot - 1)
+ <= 82);
+ // We add the result to rep0, so rep0
+ // must not be part of second argument
+ // of the macro.
+ const int32_t offset
+ = rep0 - pos_slot - 1;
+ bittree_reverse_decode(rep0,
+ coder->pos_decoders + offset,
+ direct_bits);
+ } else {
+ // Decode direct bits
+ assert(pos_slot >= 14);
+ assert(direct_bits >= 6);
+ direct_bits -= ALIGN_BITS;
+ assert(direct_bits >= 2);
+ do {
+ rc_normalize();
+ rc_range >>= 1;
+ const uint32_t t
+ = (rc_code - rc_range)
+ >> 31;
+ rc_code -= rc_range & (t - 1);
+ rep0 = (rep0 << 1) | (1 - t);
+ } while (--direct_bits > 0);
+ rep0 <<= ALIGN_BITS;
+
+ bittree_reverse_decode(rep0,
+ coder->pos_align_decoder,
+ ALIGN_BITS);
+
+ if (rep0 == UINT32_MAX) {
+ // End of Payload Marker found.
+ coder->lz.eopm_detected = true;
+ break;
+ }
+ }
+ } else {
+ rep0 = pos_slot;
+ }
+
+ } else {
+ update_bit_1(coder->is_rep[state]);
+
+ // Repeated match
+ //
+ // The match distance is a value that we have had
+ // earlier. The latest four match distances are
+ // available as rep0, rep1, rep2 and rep3. We will
+ // now decode which of them is the new distance.
+
+ if_bit_0(coder->is_rep0[state]) {
+ update_bit_0(coder->is_rep0[state]);
+
+ // The distance is rep0.
+
+ if_bit_0(coder->is_rep0_long[state][
+ pos_state]) {
+ update_bit_0(coder->is_rep0_long[
+ state][pos_state]);
+
+ // Repeating exactly one byte. For
+ // simplicity, it is done here inline
+ // instead of at the end of the main
+ // loop.
+
+ update_short_rep(state);
+
+ // Security/sanity checks. See the end
+ // of the main loop for explanation
+ // of these.
+ if ((rep0 >= coder->lz.pos
+ && !coder->lz.is_full)
+ || in_pos_local
+ > in_size)
+ goto error;
+
+ // Repeat one byte and start a new
+ // decoding loop.
+ coder->lz.dict[coder->lz.pos]
+ = lz_get_byte(
+ coder->lz, rep0);
+ ++coder->lz.pos;
+ ++now_pos;
+ continue;
+
+ } else {
+ update_bit_1(coder->is_rep0_long[
+ state][pos_state]);
+
+ // Repeating more than one byte at
+ // distance of rep0.
+ }
+
+ } else {
+ update_bit_1(coder->is_rep0[state]);
+
+ // The distance is rep1, rep2 or rep3. Once
+ // we find out which one of these three, it
+ // is stored to rep0 and rep1, rep2 and rep3
+ // are updated accordingly.
+
+ uint32_t distance;
+
+ if_bit_0(coder->is_rep1[state]) {
+ update_bit_0(coder->is_rep1[state]);
+ distance = rep1;
+ } else {
+ update_bit_1(coder->is_rep1[state]);
+
+ if_bit_0(coder->is_rep2[state]) {
+ update_bit_0(coder->is_rep2[
+ state]);
+ distance = rep2;
+ } else {
+ update_bit_1(coder->is_rep2[
+ state]);
+ distance = rep3;
+ rep3 = rep2;
+ }
+
+ rep2 = rep1;
+ }
+
+ rep1 = rep0;
+ rep0 = distance;
+ }
+
+ // Decode the length of the repeated match.
+ length_decode(len, coder->rep_match_len_decoder,
+ pos_state);
+
+ update_rep(state);
+ }
+
+
+ /////////////////////////////////
+ // Repeat from history buffer. //
+ /////////////////////////////////
+
+ // The length is always between these limits. There is no way
+ // to trigger the algorithm to set len outside this range.
+ assert(len >= MATCH_MIN_LEN);
+ assert(len <= MATCH_MAX_LEN);
+
+ now_pos += len;
+
+ // Validate the buffer position to avoid buffer overflows
+ // on corrupted input data.
+ if (in_pos_local > in_size)
+ goto error;
+
+ // Repeat len bytes from distance of rep0.
+ if (!lzma_lz_out_repeat(&coder->lz, rep0, len))
+ goto error;
+ }
+
+ rc_normalize();
+
+
+ /////////////////////////////////
+ // Update the *data structure. //
+ /////////////////////////////////
+
+ // Range decoder
+ rc_from_local(coder->rc);
+
+ // State
+ coder->state = state;
+ coder->rep0 = rep0;
+ coder->rep1 = rep1;
+ coder->rep2 = rep2;
+ coder->rep3 = rep3;
+
+ // Misc
+ coder->now_pos = now_pos;
+ *in_pos = in_pos_local;
+
+ return false;
+
+error:
+ return true;
+}
+
+
+static void
+lzma_decoder_end(lzma_coder *coder, lzma_allocator *allocator)
+{
+ lzma_next_coder_end(&coder->next, allocator);
+ lzma_lz_decoder_end(&coder->lz, allocator);
+ lzma_literal_end(&coder->literal_coder, allocator);
+ lzma_free(coder, allocator);
+ return;
+}
+
+
+extern lzma_ret
+lzma_lzma_decoder_init(lzma_next_coder *next, lzma_allocator *allocator,
+ const lzma_filter_info *filters)
+{
+ // Validate pos_bits. Other options are validated by the
+ // respective initialization functions.
+ const lzma_options_lzma *options = filters[0].options;
+ if (options->pos_bits > LZMA_POS_BITS_MAX)
+ return LZMA_HEADER_ERROR;
+
+ // Allocate memory for the decoder if needed.
+ if (next->coder == NULL) {
+ next->coder = lzma_alloc(sizeof(lzma_coder), allocator);
+ if (next->coder == NULL)
+ return LZMA_MEM_ERROR;
+
+ // Initialize variables so that we know later that we don't
+ // have an existing decoder initialized.
+ next->coder->next = LZMA_NEXT_CODER_INIT;
+ next->coder->lz = LZMA_LZ_DECODER_INIT;
+ next->coder->literal_coder = NULL;
+ }
+
+ // Store the pos_bits and calculate pos_mask.
+ next->coder->pos_bits = options->pos_bits;
+ next->coder->pos_mask = (1U << next->coder->pos_bits) - 1;
+
+ // Allocate (if needed) and initialize the literal decoder.
+ {
+ const lzma_ret ret = lzma_literal_init(
+ &next->coder->literal_coder, allocator,
+ options->literal_context_bits,
+ options->literal_pos_bits);
+ if (ret != LZMA_OK) {
+ lzma_free(next->coder, allocator);
+ next->coder = NULL;
+ return ret;
+ }
+ }
+
+ // Allocate and initialize the LZ decoder.
+ {
+ const lzma_ret ret = lzma_lz_decoder_reset(
+ &next->coder->lz, allocator, &decode_real,
+ filters[0].uncompressed_size,
+ options->dictionary_size, MATCH_MAX_LEN);
+ if (ret != LZMA_OK) {
+ lzma_literal_end(&next->coder->literal_coder,
+ allocator);
+ lzma_free(next->coder, allocator);
+ next->coder = NULL;
+ return ret;
+ }
+ }
+
+ // State
+ next->coder->state = 0;
+ next->coder->rep0 = 0;
+ next->coder->rep1 = 0;
+ next->coder->rep2 = 0;
+ next->coder->rep3 = 0;
+ next->coder->pos_bits = options->pos_bits;
+ next->coder->pos_mask = (1 << next->coder->pos_bits) - 1;
+ next->coder->now_pos = 0;
+ next->coder->init_bytes_left = 5;
+
+ // Range decoder
+ rc_reset(next->coder->rc);
+
+ // Bit and bittree decoders
+ for (uint32_t i = 0; i < STATES; ++i) {
+ for (uint32_t j = 0; j <= next->coder->pos_mask; ++j) {
+ bit_reset(next->coder->is_match[i][j]);
+ bit_reset(next->coder->is_rep0_long[i][j]);
+ }
+
+ bit_reset(next->coder->is_rep[i]);
+ bit_reset(next->coder->is_rep0[i]);
+ bit_reset(next->coder->is_rep1[i]);
+ bit_reset(next->coder->is_rep2[i]);
+ }
+
+ for (uint32_t i = 0; i < LEN_TO_POS_STATES; ++i)
+ bittree_reset(next->coder->pos_slot_decoder[i], POS_SLOT_BITS);
+
+ for (uint32_t i = 0; i < FULL_DISTANCES - END_POS_MODEL_INDEX; ++i)
+ bit_reset(next->coder->pos_decoders[i]);
+
+ bittree_reset(next->coder->pos_align_decoder, ALIGN_BITS);
+
+ // Len decoders (also bit/bittree)
+ const uint32_t num_pos_states = 1 << next->coder->pos_bits;
+ bit_reset(next->coder->len_decoder.choice);
+ bit_reset(next->coder->len_decoder.choice2);
+ bit_reset(next->coder->rep_match_len_decoder.choice);
+ bit_reset(next->coder->rep_match_len_decoder.choice2);
+
+ for (uint32_t pos_state = 0; pos_state < num_pos_states; ++pos_state) {
+ bittree_reset(next->coder->len_decoder.low[pos_state],
+ LEN_LOW_BITS);
+ bittree_reset(next->coder->len_decoder.mid[pos_state],
+ LEN_MID_BITS);
+
+ bittree_reset(next->coder->rep_match_len_decoder.low[
+ pos_state], LEN_LOW_BITS);
+ bittree_reset(next->coder->rep_match_len_decoder.mid[
+ pos_state], LEN_MID_BITS);
+ }
+
+ bittree_reset(next->coder->len_decoder.high, LEN_HIGH_BITS);
+ bittree_reset(next->coder->rep_match_len_decoder.high, LEN_HIGH_BITS);
+
+ // Initialize the next decoder in the chain, if any.
+ {
+ const lzma_ret ret = lzma_next_filter_init(&next->coder->next,
+ allocator, filters + 1);
+ if (ret != LZMA_OK) {
+ lzma_decoder_end(next->coder, allocator);
+ return ret;
+ }
+ }
+
+ // Initialization successful. Set the function pointers.
+ next->code = &lzma_lz_decode;
+ next->end = &lzma_decoder_end;
+
+ return LZMA_OK;
+}
+
+
+extern bool
+lzma_lzma_decode_properties(lzma_options_lzma *options, uint8_t byte)
+{
+ if (byte > (4 * 5 + 4) * 9 + 8)
+ return true;
+
+ // See the file format specification to understand this.
+ options->pos_bits = byte / (9 * 5);
+ byte -= options->pos_bits * 9 * 5;
+ options->literal_pos_bits = byte / 9;
+ options->literal_context_bits = byte - options->literal_pos_bits * 9;
+
+ return false;
+}
diff --git a/src/liblzma/lzma/lzma_decoder.h b/src/liblzma/lzma/lzma_decoder.h
new file mode 100644
index 00000000..929c2bff
--- /dev/null
+++ b/src/liblzma/lzma/lzma_decoder.h
@@ -0,0 +1,41 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file lzma_decoder.h
+/// \brief LZMA decoder API
+//
+// Copyright (C) 1999-2006 Igor Pavlov
+// Copyright (C) 2007 Lasse Collin
+//
+// This library is free software; you can redistribute it and/or
+// modify it under the terms of the GNU Lesser General Public
+// License as published by the Free Software Foundation; either
+// version 2.1 of the License, or (at your option) any later version.
+//
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+// Lesser General Public License for more details.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#ifndef LZMA_LZMA_DECODER_H
+#define LZMA_LZMA_DECODER_H
+
+#include "common.h"
+
+
+/// \brief Allocates and initializes LZMA decoder
+extern lzma_ret lzma_lzma_decoder_init(lzma_next_coder *next,
+ lzma_allocator *allocator, const lzma_filter_info *filters);
+
+/// \brief Decodes the LZMA Properties byte (lc/lp/pb)
+///
+/// \return true if error occorred, false on success
+///
+extern bool lzma_lzma_decode_properties(
+ lzma_options_lzma *options, uint8_t byte);
+
+// There is no public lzma_lzma_encode() because lzma_lz_encode() works
+// as a wrapper for it.
+
+#endif
diff --git a/src/liblzma/lzma/lzma_encoder.c b/src/liblzma/lzma/lzma_encoder.c
new file mode 100644
index 00000000..f9c1e3fe
--- /dev/null
+++ b/src/liblzma/lzma/lzma_encoder.c
@@ -0,0 +1,413 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file lzma_encoder.c
+/// \brief LZMA encoder
+//
+// Copyright (C) 1999-2006 Igor Pavlov
+// Copyright (C) 2007 Lasse Collin
+//
+// This library is free software; you can redistribute it and/or
+// modify it under the terms of the GNU Lesser General Public
+// License as published by the Free Software Foundation; either
+// version 2.1 of the License, or (at your option) any later version.
+//
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+// Lesser General Public License for more details.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+// NOTE: If you want to keep the line length in 80 characters, set
+// tab width to 4 or less in your editor when editing this file.
+
+
+#include "lzma_encoder_private.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 { \
+ \
+ 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
+///
+/// All 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)
+{
+ 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);
+
+ uint32_t *prices = lencoder->prices[pos_state];
+ uint32_t i = 0;
+
+ for (i = 0; i < num_symbols && i < LEN_LOW_SYMBOLS; ++i) {
+ prices[i] = a0;
+ bittree_get_price(prices[i], lencoder->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(prices[i], lencoder->mid[pos_state],
+ LEN_MID_BITS, i - LEN_LOW_SYMBOLS);
+ }
+
+ for (; i < num_symbols; ++i) {
+ prices[i] = b1;
+ bittree_get_price(prices[i], lencoder->high, LEN_HIGH_BITS,
+ i - LEN_LOW_SYMBOLS - LEN_MID_SYMBOLS);
+ }
+
+ lencoder->counters[pos_state] = num_symbols;
+
+ return;
+}
+
+
+/**
+ * \brief LZMA encoder
+ *
+ * \return true if end of stream was reached, false otherwise.
+ */
+extern bool
+lzma_lzma_encode(lzma_coder *coder, uint8_t *restrict out,
+ size_t *restrict out_pos, size_t out_size)
+{
+ // Flush the range encoder's temporary buffer to out[].
+ // Return immediatelly if not everything could be flushed.
+ if (rc_flush_buffer(&coder->rc, out, out_pos, out_size))
+ return false;
+
+ // Return immediatelly if we have already finished our work.
+ if (coder->lz.stream_end_was_reached
+ && coder->is_initialized
+ && coder->lz.read_pos == coder->lz.write_pos
+ && coder->additional_offset == 0)
+ return true;
+
+ // Local copies
+ rc_to_local(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) {
+ // Cannot initialize, because there is no input data.
+ if (!coder->lz.stream_end_was_reached)
+ return false;
+
+ // If we get here, we are encoding an empty file.
+ // Initialization is skipped completely.
+ assert(coder->lz.write_pos == coder->lz.read_pos);
+
+ } else {
+ // 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_char(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);
+
+ coder->previous_byte = cur_byte;
+ --coder->additional_offset;
+ ++coder->now_pos;
+
+ assert(coder->additional_offset == 0);
+ }
+
+ // Initialization is done (except if empty file).
+ coder->is_initialized = true;
+ }
+
+ // Encoding loop
+ while (true) {
+ // Check that there is free output space.
+ if (out_pos_local == out_size)
+ break;
+
+ assert(rc_buffer_size == 0);
+
+ // Check that there is some input to process.
+ if (coder->lz.read_pos >= coder->lz.read_limit) {
+ // If end of input has been reached, we must keep
+ // encoding until additional_offset becomes zero.
+ if (!coder->lz.stream_end_was_reached
+ || coder->additional_offset == 0)
+ break;
+ }
+
+ assert(coder->lz.read_pos <= coder->lz.write_pos);
+
+#ifndef NDEBUG
+ if (coder->lz.stream_end_was_reached) {
+ assert(coder->lz.read_limit == coder->lz.write_pos);
+ } else {
+ assert(coder->lz.read_limit + coder->lz.keep_size_after
+ == coder->lz.write_pos);
+ }
+#endif
+
+ const uint32_t pos_state = coder->now_pos & pos_mask;
+
+ uint32_t pos;
+ uint32_t len;
+
+ // Get optimal match (repeat position and length).
+ // Value ranges for pos:
+ // - [0, REP_DISTANCES): repeated match
+ // - [REP_DISTANCES, UINT32_MAX): match at (pos - REP_DISTANCES)
+ // - UINT32_MAX: not a match but a literal
+ // Value ranges for len:
+ // - [MATCH_MIN_LEN, MATCH_MAX_LEN]
+ if (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_char_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_char(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_match_len_encoder,
+ len - MATCH_MIN_LEN, pos_state,
+ best_compression);
+ update_rep(coder->state);
+ }
+
+ } else {
+ bit_encode_0(coder->is_rep[coder->state]);
+ update_match(coder->state);
+ length_encode(coder->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;
+ }
+
+ // Check if everything is done.
+ bool all_done = false;
+ if (coder->lz.stream_end_was_reached
+ && coder->lz.read_pos == coder->lz.write_pos
+ && coder->additional_offset == 0) {
+ // Write end of stream marker. It is encoded as a match with
+ // distance of UINT32_MAX. Match length is needed but it is
+ // ignored by the decoder.
+ if (coder->lz.uncompressed_size == LZMA_VLI_VALUE_UNKNOWN) {
+ 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 = MATCH_MIN_LEN; // MATCH_MAX_LEN;
+ length_encode(coder->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);
+
+ bittree_reverse_encode(coder->pos_align_encoder, ALIGN_BITS,
+ pos_reduced & ALIGN_MASK);
+ }
+
+ // Flush the last bytes of compressed data from
+ // the range coder to the output buffer.
+ rc_flush();
+
+ // All done. Note that some output bytes might be
+ // pending in coder->buffer. lzma_encode() will
+ // take care of those bytes.
+ if (rc_buffer_size == 0)
+ all_done = true;
+ }
+
+ // Store local variables back to *coder.
+ rc_from_local(coder->rc);
+ *out_pos = out_pos_local;
+
+ return all_done;
+}
diff --git a/src/liblzma/lzma/lzma_encoder.h b/src/liblzma/lzma/lzma_encoder.h
new file mode 100644
index 00000000..1c57f80a
--- /dev/null
+++ b/src/liblzma/lzma/lzma_encoder.h
@@ -0,0 +1,35 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file lzma_encoder.h
+/// \brief LZMA method handler API
+//
+// Copyright (C) 1999-2006 Igor Pavlov
+// Copyright (C) 2007 Lasse Collin
+//
+// This library is free software; you can redistribute it and/or
+// modify it under the terms of the GNU Lesser General Public
+// License as published by the Free Software Foundation; either
+// version 2.1 of the License, or (at your option) any later version.
+//
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+// Lesser General Public License for more details.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#ifndef LZMA_LZMA_ENCODER_H
+#define LZMA_LZMA_ENCODER_H
+
+#include "common.h"
+
+extern lzma_ret lzma_lzma_encoder_init(lzma_next_coder *next,
+ lzma_allocator *allocator, const lzma_filter_info *filters);
+
+extern bool lzma_lzma_encode_properties(
+ const lzma_options_lzma *options, uint8_t *byte);
+
+/// Initializes the lzma_fastpos[] array.
+extern void lzma_fastpos_init(void);
+
+#endif
diff --git a/src/liblzma/lzma/lzma_encoder_features.c b/src/liblzma/lzma/lzma_encoder_features.c
new file mode 100644
index 00000000..56e59c6a
--- /dev/null
+++ b/src/liblzma/lzma/lzma_encoder_features.c
@@ -0,0 +1,59 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file lzma_encoder_features.c
+/// \brief Information about features enabled at compile time
+//
+// Copyright (C) 2007 Lasse Collin
+//
+// This library is free software; you can redistribute it and/or
+// modify it under the terms of the GNU Lesser General Public
+// License as published by the Free Software Foundation; either
+// version 2.1 of the License, or (at your option) any later version.
+//
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+// Lesser General Public License for more details.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#include "common.h"
+
+
+static lzma_mode modes[] = {
+ LZMA_MODE_FAST,
+ LZMA_MODE_BEST,
+ LZMA_MODE_INVALID
+};
+
+
+LZMA_API const lzma_mode *const lzma_available_modes = modes;
+
+
+static lzma_match_finder match_finders[] = {
+#ifdef HAVE_MF_HC3
+ LZMA_MF_HC3,
+#endif
+
+#ifdef HAVE_MF_HC4
+ LZMA_MF_HC4,
+#endif
+
+#ifdef HAVE_MF_BT2
+ LZMA_MF_BT2,
+#endif
+
+#ifdef HAVE_MF_BT3
+ LZMA_MF_BT3,
+#endif
+
+#ifdef HAVE_MF_BT4
+ LZMA_MF_BT4,
+#endif
+
+ LZMA_MF_INVALID
+};
+
+
+LZMA_API const lzma_match_finder *const lzma_available_match_finders
+ = match_finders;
diff --git a/src/liblzma/lzma/lzma_encoder_getoptimum.c b/src/liblzma/lzma/lzma_encoder_getoptimum.c
new file mode 100644
index 00000000..cdeb3145
--- /dev/null
+++ b/src/liblzma/lzma/lzma_encoder_getoptimum.c
@@ -0,0 +1,893 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file lzma_encoder_getoptimum.c
+//
+// Copyright (C) 1999-2006 Igor Pavlov
+// Copyright (C) 2007 Lasse Collin
+//
+// This library is free software; you can redistribute it and/or
+// modify it under the terms of the GNU Lesser General Public
+// License as published by the Free Software Foundation; either
+// version 2.1 of the License, or (at your option) any later version.
+//
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+// Lesser General Public License for more details.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+// NOTE: If you want to keep the line length in 80 characters, set
+// tab width to 4 or less in your editor when editing this file.
+
+
+// "Would you love the monster code?
+// Could you understand beauty of the beast?"
+// --Adapted from Lordi's "Would you love a monster man".
+
+
+#include "lzma_encoder_private.h"
+
+
+#define length_get_price(length_encoder, symbol, pos_state) \
+ (length_encoder).prices[pos_state][symbol]
+
+
+#define get_rep_len_1_price(state, pos_state) \
+ bit_get_price_0(coder->is_rep0[state]) \
+ + bit_get_price_0(coder->is_rep0_long[state][pos_state])
+
+
+// Adds to price_target.
+#define get_pure_rep_price(price_target, rep_index, state, pos_state) \
+do { \
+ if ((rep_index) == 0) { \
+ price_target += bit_get_price_0(coder->is_rep0[state]); \
+ price_target += bit_get_price_1( \
+ coder->is_rep0_long[state][pos_state]); \
+ } else { \
+ price_target += bit_get_price_1(coder->is_rep0[state]); \
+ if ((rep_index) == 1) { \
+ price_target += bit_get_price_0(coder->is_rep1[state]); \
+ } else { \
+ price_target += bit_get_price_1(coder->is_rep1[state]); \
+ price_target += bit_get_price( \
+ coder->is_rep2[state], (rep_index) - 2); \
+ } \
+ } \
+} while (0)
+
+
+// Adds to price_target.
+#define get_rep_price(price_target, rep_index, len, state, pos_state) \
+do { \
+ get_pure_rep_price(price_target, rep_index, state, pos_state); \
+ price_target += length_get_price(coder->rep_match_len_encoder, \
+ (len) - MATCH_MIN_LEN, pos_state); \
+} while (0)
+
+
+// Adds to price_target.
+#define get_pos_len_price(price_target, pos, len, pos_state) \
+do { \
+ const uint32_t len_to_pos_state_tmp = get_len_to_pos_state(len); \
+ if ((pos) < FULL_DISTANCES) { \
+ price_target += distances_prices[len_to_pos_state_tmp][pos]; \
+ } else { \
+ price_target \
+ += pos_slot_prices[len_to_pos_state_tmp][get_pos_slot_2(pos)] \
+ + align_prices[(pos) & ALIGN_MASK]; \
+ } \
+ price_target += length_get_price( \
+ coder->len_encoder, (len) - MATCH_MIN_LEN, pos_state); \
+} while (0)
+
+
+// Three macros to manipulate lzma_optimal structures:
+#define make_as_char(opt) \
+do { \
+ (opt).back_prev = UINT32_MAX; \
+ (opt).prev_1_is_char = false; \
+} while (0)
+
+
+#define make_as_short_rep(opt) \
+do { \
+ (opt).back_prev = 0; \
+ (opt).prev_1_is_char = false; \
+} while (0)
+
+
+#define is_short_rep(opt) \
+ ((opt).back_prev == 0)
+
+
+static void
+fill_distances_prices(lzma_coder *coder)
+{
+ uint32_t temp_prices[FULL_DISTANCES];
+
+ for (uint32_t i = START_POS_MODEL_INDEX; i < FULL_DISTANCES; ++i) {
+ const uint32_t pos_slot = get_pos_slot(i);
+ const uint32_t footer_bits = ((pos_slot >> 1) - 1);
+ const uint32_t base = (2 | (pos_slot & 1)) << footer_bits;
+ temp_prices[i] = 0;
+ bittree_reverse_get_price(temp_prices[i],
+ coder->pos_encoders + base - pos_slot - 1,
+ footer_bits, i - base);
+ }
+
+ const uint32_t dist_table_size = coder->dist_table_size;
+
+ for (uint32_t len_to_pos_state = 0;
+ len_to_pos_state < LEN_TO_POS_STATES;
+ ++len_to_pos_state) {
+
+ const probability *encoder = coder->pos_slot_encoder[len_to_pos_state];
+ uint32_t *pos_slot_prices = coder->pos_slot_prices[len_to_pos_state];
+
+ for (uint32_t pos_slot = 0;
+ pos_slot < dist_table_size;
+ ++pos_slot) {
+ pos_slot_prices[pos_slot] = 0;
+ bittree_get_price(pos_slot_prices[pos_slot], encoder,
+ POS_SLOT_BITS, pos_slot);
+ }
+
+ for (uint32_t pos_slot = END_POS_MODEL_INDEX;
+ pos_slot < dist_table_size;
+ ++pos_slot)
+ pos_slot_prices[pos_slot] += (((pos_slot >> 1) - 1)
+ - ALIGN_BITS) << BIT_PRICE_SHIFT_BITS;
+
+
+ uint32_t *distances_prices
+ = coder->distances_prices[len_to_pos_state];
+
+ uint32_t i;
+ for (i = 0; i < START_POS_MODEL_INDEX; ++i)
+ distances_prices[i] = pos_slot_prices[i];
+
+ for (; i < FULL_DISTANCES; ++i)
+ distances_prices[i] = pos_slot_prices[get_pos_slot(i)]
+ + temp_prices[i];
+ }
+
+ coder->match_price_count = 0;
+
+ return;
+}
+
+
+static void
+fill_align_prices(lzma_coder *coder)
+{
+ for (uint32_t i = 0; i < ALIGN_TABLE_SIZE; ++i) {
+ uint32_t tmp = 0;
+ bittree_reverse_get_price(tmp, coder->pos_align_encoder,
+ ALIGN_BITS, i);
+ coder->align_prices[i] = tmp;
+ }
+
+ coder->align_price_count = 0;
+}
+
+
+// The first argument is a pointer returned by literal_get_subcoder().
+static uint32_t
+literal_get_price(const probability *encoders, const bool match_mode,
+ const uint8_t match_byte, const uint8_t symbol)
+{
+ uint32_t price = 0;
+ uint32_t context = 1;
+ int i = 8;
+
+ if (match_mode) {
+ do {
+ --i;
+ const uint32_t match_bit = (match_byte >> i) & 1;
+ const uint32_t bit = (symbol >> i) & 1;
+ const uint32_t subcoder_index
+ = 0x100 + (match_bit << 8) + context;
+
+ price += bit_get_price(encoders[subcoder_index], bit);
+ context = (context << 1) | bit;
+
+ if (match_bit != bit)
+ break;
+
+ } while (i != 0);
+ }
+
+ while (i != 0) {
+ --i;
+ const uint32_t bit = (symbol >> i) & 1;
+ price += bit_get_price(encoders[context], bit);
+ context = (context << 1) | bit;
+ }
+
+ return price;
+}
+
+
+static void
+backward(lzma_coder *restrict coder, uint32_t *restrict len_res,
+ uint32_t *restrict back_res, uint32_t cur)
+{
+ coder->optimum_end_index = cur;
+
+ uint32_t pos_mem = coder->optimum[cur].pos_prev;
+ uint32_t back_mem = coder->optimum[cur].back_prev;
+
+ do {
+ if (coder->optimum[cur].prev_1_is_char) {
+ make_as_char(coder->optimum[pos_mem]);
+ coder->optimum[pos_mem].pos_prev = pos_mem - 1;
+
+ if (coder->optimum[cur].prev_2) {
+ coder->optimum[pos_mem - 1].prev_1_is_char = false;
+ coder->optimum[pos_mem - 1].pos_prev
+ = coder->optimum[cur].pos_prev_2;
+ coder->optimum[pos_mem - 1].back_prev
+ = coder->optimum[cur].back_prev_2;
+ }
+ }
+
+ uint32_t pos_prev = pos_mem;
+ uint32_t back_cur = back_mem;
+
+ back_mem = coder->optimum[pos_prev].back_prev;
+ pos_mem = coder->optimum[pos_prev].pos_prev;
+
+ coder->optimum[pos_prev].back_prev = back_cur;
+ coder->optimum[pos_prev].pos_prev = cur;
+ cur = pos_prev;
+
+ } while (cur != 0);
+
+ coder->optimum_current_index = coder->optimum[0].pos_prev;
+ *len_res = coder->optimum[0].pos_prev;
+ *back_res = coder->optimum[0].back_prev;
+
+ return;
+}
+
+
+extern void
+lzma_get_optimum(lzma_coder *restrict coder,
+ uint32_t *restrict back_res, uint32_t *restrict len_res)
+{
+ // 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.
+ if (coder->additional_offset == 0) {
+ if (coder->match_price_count >= (1 << 7))
+ fill_distances_prices(coder);
+
+ if (coder->align_price_count >= ALIGN_TABLE_SIZE)
+ fill_align_prices(coder);
+ }
+
+
+ if (coder->optimum_end_index != coder->optimum_current_index) {
+ *len_res = coder->optimum[coder->optimum_current_index].pos_prev
+ - coder->optimum_current_index;
+ *back_res = coder->optimum[coder->optimum_current_index].back_prev;
+ coder->optimum_current_index = coder->optimum[
+ coder->optimum_current_index].pos_prev;
+ return;
+ }
+
+ coder->optimum_current_index = 0;
+ coder->optimum_end_index = 0;
+
+
+ const uint32_t fast_bytes = coder->fast_bytes;
+ uint32_t *match_distances = coder->match_distances;
+
+ uint32_t len_main;
+ uint32_t num_distance_pairs;
+
+ if (!coder->longest_match_was_found) {
+ lzma_read_match_distances(coder, &len_main, &num_distance_pairs);
+ } else {
+ len_main = coder->longest_match_length;
+ num_distance_pairs = coder->num_distance_pairs;
+ coder->longest_match_was_found = false;
+ }
+
+
+ const uint8_t *buf = coder->lz.buffer + coder->lz.read_pos - 1;
+ uint32_t num_available_bytes
+ = coder->lz.write_pos - coder->lz.read_pos + 1;
+ if (num_available_bytes < 2) {
+ *back_res = UINT32_MAX;
+ *len_res = 1;
+ return;
+ }
+
+ if (num_available_bytes > MATCH_MAX_LEN)
+ num_available_bytes = MATCH_MAX_LEN;
+
+
+ uint32_t reps[REP_DISTANCES];
+ uint32_t rep_lens[REP_DISTANCES];
+ uint32_t rep_max_index = 0;
+
+ for (uint32_t i = 0; i < REP_DISTANCES; ++i) {
+ reps[i] = coder->rep_distances[i];
+ const uint32_t back_offset = reps[i] + 1;
+
+ if (buf[0] != *(buf - back_offset)
+ || buf[1] != *(buf + 1 - back_offset)) {
+ rep_lens[i] = 0;
+ continue;
+ }
+
+ uint32_t len_test;
+ for (len_test = 2; len_test < num_available_bytes
+ && buf[len_test] == *(buf + len_test - back_offset);
+ ++len_test) ;
+
+ rep_lens[i] = len_test;
+ if (len_test > rep_lens[rep_max_index])
+ rep_max_index = i;
+ }
+
+ if (rep_lens[rep_max_index] >= fast_bytes) {
+ *back_res = rep_max_index;
+ *len_res = rep_lens[rep_max_index];
+ move_pos(*len_res - 1);
+ return;
+ }
+
+
+ if (len_main >= fast_bytes) {
+ *back_res = match_distances[num_distance_pairs] + REP_DISTANCES;
+ *len_res = len_main;
+ move_pos(len_main - 1);
+ return;
+ }
+
+ uint8_t current_byte = *buf;
+ uint8_t match_byte = *(buf - reps[0] - 1);
+
+ if (len_main < 2 && current_byte != match_byte
+ && rep_lens[rep_max_index] < 2) {
+ *back_res = UINT32_MAX;
+ *len_res = 1;
+ 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(
+ literal_get_subcoder(coder->literal_coder,
+ position, coder->previous_byte),
+ !is_char_state(coder->state), match_byte, current_byte);
+
+ make_as_char(coder->optimum[1]);
+
+ uint32_t match_price
+ = bit_get_price_1(coder->is_match[coder->state][pos_state]);
+ uint32_t rep_match_price
+ = match_price + bit_get_price_1(coder->is_rep[coder->state]);
+
+
+ if (match_byte == current_byte) {
+ const uint32_t short_rep_price = rep_match_price
+ + get_rep_len_1_price(coder->state, pos_state);
+
+ if (short_rep_price < coder->optimum[1].price) {
+ coder->optimum[1].price = short_rep_price;
+ make_as_short_rep(coder->optimum[1]);
+ }
+ }
+
+ uint32_t len_end = (len_main >= rep_lens[rep_max_index])
+ ? len_main
+ : rep_lens[rep_max_index];
+
+ if (len_end < 2) {
+ *back_res = coder->optimum[1].back_prev;
+ *len_res = 1;
+ return;
+ }
+
+ coder->optimum[1].pos_prev = 0;
+
+ for (uint32_t i = 0; i < REP_DISTANCES; ++i)
+ coder->optimum[0].backs[i] = reps[i];
+
+ uint32_t len = len_end;
+ do {
+ coder->optimum[len].price = INFINITY_PRICE;
+ } while (--len >= 2);
+
+
+ uint32_t (*distances_prices)[FULL_DISTANCES] = coder->distances_prices;
+ uint32_t (*pos_slot_prices)[DIST_TABLE_SIZE_MAX] = coder->pos_slot_prices;
+ uint32_t *align_prices = coder->align_prices;
+
+ for (uint32_t i = 0; i < REP_DISTANCES; ++i) {
+ uint32_t rep_len = rep_lens[i];
+ if (rep_len < 2)
+ continue;
+
+ uint32_t price = rep_match_price;
+ get_pure_rep_price(price, i, coder->state, pos_state);
+
+ do {
+ const uint32_t cur_and_len_price = price
+ + length_get_price(
+ coder->rep_match_len_encoder,
+ rep_len - 2, pos_state);
+
+ if (cur_and_len_price < coder->optimum[rep_len].price) {
+ coder->optimum[rep_len].price = cur_and_len_price;
+ coder->optimum[rep_len].pos_prev = 0;
+ coder->optimum[rep_len].back_prev = i;
+ coder->optimum[rep_len].prev_1_is_char = false;
+ }
+ } while (--rep_len >= 2);
+ }
+
+
+ uint32_t normal_match_price = match_price
+ + bit_get_price_0(coder->is_rep[coder->state]);
+
+ len = (rep_lens[0] >= 2) ? rep_lens[0] + 1 : 2;
+
+ if (len <= len_main) {
+ uint32_t offs = 0;
+
+ while (len > match_distances[offs + 1])
+ offs += 2;
+
+ for(; ; ++len) {
+ const uint32_t distance = match_distances[offs + 2];
+ uint32_t cur_and_len_price = normal_match_price;
+ get_pos_len_price(cur_and_len_price, distance, len, pos_state);
+
+ if (cur_and_len_price < coder->optimum[len].price) {
+ coder->optimum[len].price = cur_and_len_price;
+ coder->optimum[len].pos_prev = 0;
+ coder->optimum[len].back_prev = distance + REP_DISTANCES;
+ coder->optimum[len].prev_1_is_char = false;
+ }
+
+ if (len == match_distances[offs + 1]) {
+ offs += 2;
+ if (offs == num_distance_pairs)
+ break;
+ }
+ }
+ }
+
+
+ //////////////////
+ // Big loop ;-) //
+ //////////////////
+
+ uint32_t cur = 0;
+
+ // The rest of this function is a huge while-loop. To avoid extreme
+ // indentation, the indentation level is not increased here.
+ while (true) {
+
+ ++cur;
+
+ assert(cur < OPTS);
+
+ if (cur == len_end) {
+ backward(coder, len_res, back_res, cur);
+ return;
+ }
+
+ uint32_t new_len;
+
+ lzma_read_match_distances(coder, &new_len, &num_distance_pairs);
+
+ if (new_len >= fast_bytes) {
+ coder->num_distance_pairs = num_distance_pairs;
+ coder->longest_match_length = new_len;
+ coder->longest_match_was_found = true;
+ backward(coder, len_res, back_res, cur);
+ return;
+ }
+
+
+ ++position;
+
+ uint32_t pos_prev = coder->optimum[cur].pos_prev;
+ uint32_t state;
+
+ if (coder->optimum[cur].prev_1_is_char) {
+ --pos_prev;
+
+ if (coder->optimum[cur].prev_2) {
+ state = coder->optimum[coder->optimum[cur].pos_prev_2].state;
+
+ if (coder->optimum[cur].back_prev_2 < REP_DISTANCES)
+ update_rep(state);
+ else
+ update_match(state);
+
+ } else {
+ state = coder->optimum[pos_prev].state;
+ }
+
+ update_char(state);
+
+ } else {
+ state = coder->optimum[pos_prev].state;
+ }
+
+ if (pos_prev == cur - 1) {
+ if (is_short_rep(coder->optimum[cur]))
+ update_short_rep(state);
+ else
+ update_char(state);
+ } else {
+ uint32_t pos;
+ if (coder->optimum[cur].prev_1_is_char && coder->optimum[cur].prev_2) {
+ pos_prev = coder->optimum[cur].pos_prev_2;
+ pos = coder->optimum[cur].back_prev_2;
+ update_rep(state);
+ } else {
+ pos = coder->optimum[cur].back_prev;
+ if (pos < REP_DISTANCES)
+ update_rep(state);
+ else
+ update_match(state);
+ }
+
+ if (pos < REP_DISTANCES) {
+ reps[0] = coder->optimum[pos_prev].backs[pos];
+
+ uint32_t i;
+ for (i = 1; i <= pos; ++i)
+ reps[i] = coder->optimum[pos_prev].backs[i - 1];
+
+ for (; i < REP_DISTANCES; ++i)
+ reps[i] = coder->optimum[pos_prev].backs[i];
+
+ } else {
+ reps[0] = pos - REP_DISTANCES;
+
+ for (uint32_t i = 1; i < REP_DISTANCES; ++i)
+ reps[i] = coder->optimum[pos_prev].backs[i - 1];
+ }
+ }
+
+ coder->optimum[cur].state = state;
+
+ for (uint32_t i = 0; i < REP_DISTANCES; ++i)
+ coder->optimum[cur].backs[i] = reps[i];
+
+ const uint32_t cur_price = coder->optimum[cur].price;
+
+ buf = coder->lz.buffer + coder->lz.read_pos - 1;
+ current_byte = *buf;
+ match_byte = *(buf - reps[0] - 1);
+
+ pos_state = position & pos_mask;
+
+ const uint32_t cur_and_1_price = cur_price
+ + bit_get_price_0(coder->is_match[state][pos_state])
+ + literal_get_price(
+ literal_get_subcoder(coder->literal_coder,
+ position, buf[-1]),
+ !is_char_state(state), match_byte, current_byte);
+
+ bool next_is_char = false;
+
+ if (cur_and_1_price < coder->optimum[cur + 1].price) {
+ coder->optimum[cur + 1].price = cur_and_1_price;
+ coder->optimum[cur + 1].pos_prev = cur;
+ make_as_char(coder->optimum[cur + 1]);
+ next_is_char = true;
+ }
+
+ match_price = cur_price
+ + bit_get_price_1(coder->is_match[state][pos_state]);
+ rep_match_price = match_price
+ + bit_get_price_1(coder->is_rep[state]);
+
+ if (match_byte == current_byte
+ && !(coder->optimum[cur + 1].pos_prev < cur
+ && coder->optimum[cur + 1].back_prev == 0)) {
+
+ const uint32_t short_rep_price = rep_match_price
+ + get_rep_len_1_price(state, pos_state);
+
+ if (short_rep_price <= coder->optimum[cur + 1].price) {
+ coder->optimum[cur + 1].price = short_rep_price;
+ coder->optimum[cur + 1].pos_prev = cur;
+ make_as_short_rep(coder->optimum[cur + 1]);
+ next_is_char = true;
+ }
+ }
+
+ uint32_t num_available_bytes_full
+ = coder->lz.write_pos - coder->lz.read_pos + 1;
+ num_available_bytes_full = MIN(OPTS - 1 - cur, num_available_bytes_full);
+ num_available_bytes = num_available_bytes_full;
+
+ if (num_available_bytes < 2)
+ continue;
+
+ if (num_available_bytes > fast_bytes)
+ num_available_bytes = fast_bytes;
+
+ if (!next_is_char && match_byte != current_byte) { // speed optimization
+ // try literal + rep0
+ const uint32_t back_offset = reps[0] + 1;
+ const uint32_t limit = MIN(num_available_bytes_full, fast_bytes + 1);
+
+ uint32_t temp;
+ for (temp = 1; temp < limit
+ && buf[temp] == *(buf + temp - back_offset);
+ ++temp) ;
+
+ const uint32_t len_test_2 = temp - 1;
+
+ if (len_test_2 >= 2) {
+ uint32_t state_2 = state;
+ update_char(state_2);
+
+ const uint32_t pos_state_next = (position + 1) & 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]);
+
+ // for (; len_test_2 >= 2; --len_test_2) {
+ const uint32_t offset = cur + 1 + len_test_2;
+
+ while (len_end < offset)
+ coder->optimum[++len_end].price = INFINITY_PRICE;
+
+ uint32_t cur_and_len_price = next_rep_match_price;
+ get_rep_price(cur_and_len_price,
+ 0, len_test_2, state_2, pos_state_next);
+
+ if (cur_and_len_price < coder->optimum[offset].price) {
+ coder->optimum[offset].price = cur_and_len_price;
+ coder->optimum[offset].pos_prev = cur + 1;
+ coder->optimum[offset].back_prev = 0;
+ coder->optimum[offset].prev_1_is_char = true;
+ coder->optimum[offset].prev_2 = false;
+ }
+// }
+ }
+ }
+
+
+ uint32_t start_len = 2; // speed optimization
+
+ for (uint32_t rep_index = 0; rep_index < REP_DISTANCES; ++rep_index) {
+ const uint32_t back_offset = reps[rep_index] + 1;
+
+ if (buf[0] != *(buf - back_offset) || buf[1] != *(buf + 1 - back_offset))
+ continue;
+
+ uint32_t len_test;
+ for (len_test = 2; len_test < num_available_bytes
+ && buf[len_test] == *(buf + len_test - back_offset);
+ ++len_test) ;
+
+ while (len_end < cur + len_test)
+ coder->optimum[++len_end].price = INFINITY_PRICE;
+
+ const uint32_t len_test_temp = len_test;
+ uint32_t price = rep_match_price;
+ get_pure_rep_price(price, rep_index, state, pos_state);
+
+ do {
+ const uint32_t cur_and_len_price = price
+ + length_get_price(coder->rep_match_len_encoder,
+ len_test - 2, pos_state);
+
+ if (cur_and_len_price < coder->optimum[cur + len_test].price) {
+ coder->optimum[cur + len_test].price = cur_and_len_price;
+ coder->optimum[cur + len_test].pos_prev = cur;
+ coder->optimum[cur + len_test].back_prev = rep_index;
+ coder->optimum[cur + len_test].prev_1_is_char = false;
+ }
+ } while (--len_test >= 2);
+
+ len_test = len_test_temp;
+
+ if (rep_index == 0)
+ start_len = len_test + 1;
+
+
+ uint32_t len_test_2 = len_test + 1;
+ const uint32_t limit = MIN(num_available_bytes_full,
+ len_test_2 + fast_bytes);
+ for (; len_test_2 < limit
+ && buf[len_test_2] == *(buf + len_test_2 - back_offset);
+ ++len_test_2) ;
+
+ len_test_2 -= len_test + 1;
+
+ if (len_test_2 >= 2) {
+ uint32_t state_2 = state;
+ update_rep(state_2);
+
+ uint32_t pos_state_next = (position + len_test) & pos_mask;
+
+ const uint32_t cur_and_len_char_price = price
+ + length_get_price(coder->rep_match_len_encoder,
+ len_test - 2, pos_state)
+ + bit_get_price_0(coder->is_match[state_2][pos_state_next])
+ + literal_get_price(
+ literal_get_subcoder(coder->literal_coder,
+ position + len_test, buf[len_test - 1]),
+ true, *(buf + len_test - back_offset), buf[len_test]);
+
+ update_char(state_2);
+
+ pos_state_next = (position + len_test + 1) & 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])
+ + bit_get_price_1(coder->is_rep[state_2]);
+
+// for(; len_test_2 >= 2; len_test_2--) {
+ const uint32_t offset = cur + len_test + 1 + len_test_2;
+
+ while (len_end < offset)
+ coder->optimum[++len_end].price = INFINITY_PRICE;
+
+ uint32_t cur_and_len_price = next_rep_match_price;
+ get_rep_price(cur_and_len_price,
+ 0, len_test_2, state_2, pos_state_next);
+
+ if (cur_and_len_price < coder->optimum[offset].price) {
+ coder->optimum[offset].price = cur_and_len_price;
+ coder->optimum[offset].pos_prev = cur + len_test + 1;
+ coder->optimum[offset].back_prev = 0;
+ coder->optimum[offset].prev_1_is_char = true;
+ coder->optimum[offset].prev_2 = true;
+ coder->optimum[offset].pos_prev_2 = cur;
+ coder->optimum[offset].back_prev_2 = rep_index;
+ }
+// }
+ }
+ }
+
+
+// for (uint32_t len_test = 2; len_test <= new_len; ++len_test)
+ if (new_len > num_available_bytes) {
+ new_len = num_available_bytes;
+
+ for (num_distance_pairs = 0;
+ new_len > match_distances[num_distance_pairs + 1];
+ num_distance_pairs += 2) ;
+
+ match_distances[num_distance_pairs + 1] = new_len;
+ num_distance_pairs += 2;
+ }
+
+
+ if (new_len >= start_len) {
+ normal_match_price = match_price
+ + bit_get_price_0(coder->is_rep[state]);
+
+ while (len_end < cur + new_len)
+ coder->optimum[++len_end].price = INFINITY_PRICE;
+
+ uint32_t offs = 0;
+ while (start_len > match_distances[offs + 1])
+ offs += 2;
+
+ uint32_t cur_back = match_distances[offs + 2];
+ uint32_t pos_slot = get_pos_slot_2(cur_back);
+
+ for (uint32_t len_test = start_len; ; ++len_test) {
+ uint32_t cur_and_len_price = normal_match_price;
+ const uint32_t len_to_pos_state = get_len_to_pos_state(len_test);
+
+ if (cur_back < FULL_DISTANCES)
+ cur_and_len_price += distances_prices[
+ len_to_pos_state][cur_back];
+ else
+ cur_and_len_price += pos_slot_prices[
+ len_to_pos_state][pos_slot]
+ + align_prices[cur_back & ALIGN_MASK];
+
+ cur_and_len_price += length_get_price(coder->len_encoder,
+ len_test - MATCH_MIN_LEN, pos_state);
+
+ if (cur_and_len_price < coder->optimum[cur + len_test].price) {
+ coder->optimum[cur + len_test].price = cur_and_len_price;
+ coder->optimum[cur + len_test].pos_prev = cur;
+ coder->optimum[cur + len_test].back_prev
+ = cur_back + REP_DISTANCES;
+ coder->optimum[cur + len_test].prev_1_is_char = false;
+ }
+
+ if (len_test == match_distances[offs + 1]) {
+ // Try Match + Literal + Rep0
+ const uint32_t back_offset = cur_back + 1;
+ uint32_t len_test_2 = len_test + 1;
+ const uint32_t limit = MIN(num_available_bytes_full,
+ len_test_2 + fast_bytes);
+
+ for (; len_test_2 < limit &&
+ buf[len_test_2] == *(buf + len_test_2 - back_offset);
+ ++len_test_2) ;
+
+ len_test_2 -= len_test + 1;
+
+ if (len_test_2 >= 2) {
+ uint32_t state_2 = state;
+ update_match(state_2);
+ uint32_t pos_state_next
+ = (position + len_test) & pos_mask;
+
+ const uint32_t cur_and_len_char_price = cur_and_len_price
+ + bit_get_price_0(
+ coder->is_match[state_2][pos_state_next])
+ + literal_get_price(
+ literal_get_subcoder(
+ coder->literal_coder,
+ position + len_test,
+ buf[len_test - 1]),
+ true,
+ *(buf + len_test - back_offset),
+ buf[len_test]);
+
+ update_char(state_2);
+ pos_state_next = (pos_state_next + 1) & 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])
+ + bit_get_price_1(coder->is_rep[state_2]);
+
+ // for(; len_test_2 >= 2; --len_test_2) {
+ const uint32_t offset = cur + len_test + 1 + len_test_2;
+
+ while (len_end < offset)
+ coder->optimum[++len_end].price = INFINITY_PRICE;
+
+ cur_and_len_price = next_rep_match_price;
+ get_rep_price(cur_and_len_price,
+ 0, len_test_2, state_2, pos_state_next);
+
+ if (cur_and_len_price < coder->optimum[offset].price) {
+ coder->optimum[offset].price = cur_and_len_price;
+ coder->optimum[offset].pos_prev = cur + len_test + 1;
+ coder->optimum[offset].back_prev = 0;
+ coder->optimum[offset].prev_1_is_char = true;
+ coder->optimum[offset].prev_2 = true;
+ coder->optimum[offset].pos_prev_2 = cur;
+ coder->optimum[offset].back_prev_2
+ = cur_back + REP_DISTANCES;
+ }
+// }
+ }
+
+ offs += 2;
+ if (offs == num_distance_pairs)
+ break;
+
+ cur_back = match_distances[offs + 2];
+ if (cur_back >= FULL_DISTANCES)
+ pos_slot = get_pos_slot_2(cur_back);
+ }
+ }
+ }
+
+ } // Closes: while (true)
+}
diff --git a/src/liblzma/lzma/lzma_encoder_getoptimumfast.c b/src/liblzma/lzma/lzma_encoder_getoptimumfast.c
new file mode 100644
index 00000000..e6cee19d
--- /dev/null
+++ b/src/liblzma/lzma/lzma_encoder_getoptimumfast.c
@@ -0,0 +1,201 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file lzma_encoder_getoptimumfast.c
+//
+// Copyright (C) 1999-2006 Igor Pavlov
+// Copyright (C) 2007 Lasse Collin
+//
+// This library is free software; you can redistribute it and/or
+// modify it under the terms of the GNU Lesser General Public
+// License as published by the Free Software Foundation; either
+// version 2.1 of the License, or (at your option) any later version.
+//
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+// Lesser General Public License for more details.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+// NOTE: If you want to keep the line length in 80 characters, set
+// tab width to 4 or less in your editor when editing this file.
+
+
+#include "lzma_encoder_private.h"
+
+
+#define change_pair(small_dist, big_dist) \
+ (((big_dist) >> 7) > (small_dist))
+
+
+extern void
+lzma_get_optimum_fast(lzma_coder *restrict coder,
+ uint32_t *restrict back_res, uint32_t *restrict len_res)
+{
+ // Local copies
+ const uint32_t fast_bytes = coder->fast_bytes;
+
+ uint32_t len_main;
+ uint32_t num_distance_pairs;
+ if (!coder->longest_match_was_found) {
+ lzma_read_match_distances(coder, &len_main, &num_distance_pairs);
+ } else {
+ len_main = coder->longest_match_length;
+ num_distance_pairs = coder->num_distance_pairs;
+ coder->longest_match_was_found = false;
+ }
+
+ const uint8_t *buf = coder->lz.buffer + coder->lz.read_pos - 1;
+ uint32_t num_available_bytes
+ = coder->lz.write_pos - coder->lz.read_pos + 1;
+
+ if (num_available_bytes < 2) {
+ // There's not enough input left to encode a match.
+ *back_res = UINT32_MAX;
+ *len_res = 1;
+ return;
+ }
+
+ if (num_available_bytes > MATCH_MAX_LEN)
+ num_available_bytes = MATCH_MAX_LEN;
+
+
+ // Look for repetitive matches; scan the previous four match distances
+ uint32_t rep_lens[REP_DISTANCES];
+ 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;
+
+ // If the first two bytes (2 == MATCH_MIN_LEN) do not match,
+ // this rep_distance[i] is not useful. This is indicated
+ // using zero as the length of the repetitive match.
+ if (buf[0] != *(buf - back_offset)
+ || buf[1] != *(buf + 1 - back_offset)) {
+ rep_lens[i] = 0;
+ continue;
+ }
+
+ // The first two bytes matched.
+ // Calculate the length of the match.
+ uint32_t len;
+ for (len = 2; len < num_available_bytes
+ && buf[len] == *(buf + len - back_offset);
+ ++len) ;
+
+ // If we have found a repetitive match that is at least
+ // as long as fast_bytes, return it immediatelly.
+ if (len >= fast_bytes) {
+ *back_res = i;
+ *len_res = len;
+ move_pos(len - 1);
+ return;
+ }
+
+ rep_lens[i] = len;
+
+ // After this loop, rep_lens[rep_max_index] is the biggest
+ // value of all values in rep_lens[].
+ if (len > rep_lens[rep_max_index])
+ rep_max_index = i;
+ }
+
+
+ if (len_main >= fast_bytes) {
+ *back_res = coder->match_distances[num_distance_pairs]
+ + REP_DISTANCES;
+ *len_res = len_main;
+ move_pos(len_main - 1);
+ return;
+ }
+
+ uint32_t back_main = 0;
+ if (len_main >= 2) {
+ back_main = coder->match_distances[num_distance_pairs];
+
+ while (num_distance_pairs > 2 && len_main ==
+ coder->match_distances[num_distance_pairs - 3] + 1) {
+ if (!change_pair(coder->match_distances[
+ num_distance_pairs - 2], back_main))
+ break;
+
+ num_distance_pairs -= 2;
+ len_main = coder->match_distances[num_distance_pairs - 1];
+ back_main = coder->match_distances[num_distance_pairs];
+ }
+
+ if (len_main == 2 && back_main >= 0x80)
+ len_main = 1;
+ }
+
+ if (rep_lens[rep_max_index] >= 2) {
+ if (rep_lens[rep_max_index] + 1 >= len_main
+ || (rep_lens[rep_max_index] + 2 >= len_main
+ && (back_main > (1 << 9)))
+ || (rep_lens[rep_max_index] + 3 >= len_main
+ && (back_main > (1 << 15)))) {
+ *back_res = rep_max_index;
+ *len_res = rep_lens[rep_max_index];
+ move_pos(*len_res - 1);
+ return;
+ }
+ }
+
+ if (len_main >= 2 && num_available_bytes > 2) {
+ lzma_read_match_distances(coder, &coder->longest_match_length,
+ &coder->num_distance_pairs);
+
+ if (coder->longest_match_length >= 2) {
+ const uint32_t new_distance = coder->match_distances[
+ coder->num_distance_pairs];
+
+ if ((coder->longest_match_length >= len_main
+ && new_distance < back_main)
+ || (coder->longest_match_length == len_main + 1
+ && !change_pair(back_main, new_distance))
+ || (coder->longest_match_length > len_main + 1)
+ || (coder->longest_match_length + 1 >= len_main
+ && len_main >= 3
+ && change_pair(new_distance, back_main))) {
+ coder->longest_match_was_found = true;
+ *back_res = UINT32_MAX;
+ *len_res = 1;
+ return;
+ }
+ }
+
+ ++buf;
+ --num_available_bytes;
+
+ for (uint32_t i = 0; i < REP_DISTANCES; ++i) {
+ const uint32_t back_offset = coder->rep_distances[i] + 1;
+
+ if (buf[1] != *(buf + 1 - back_offset)
+ || buf[2] != *(buf + 2 - back_offset)) {
+ rep_lens[i] = 0;
+ continue;
+ }
+
+ uint32_t len;
+ for (len = 2; len < num_available_bytes
+ && buf[len] == *(buf + len - back_offset);
+ ++len) ;
+
+ if (len + 1 >= len_main) {
+ coder->longest_match_was_found = true;
+ *back_res = UINT32_MAX;
+ *len_res = 1;
+ return;
+ }
+ }
+
+ *back_res = back_main + REP_DISTANCES;
+ *len_res = len_main;
+ move_pos(len_main - 2);
+ return;
+ }
+
+ *back_res = UINT32_MAX;
+ *len_res = 1;
+ return;
+}
diff --git a/src/liblzma/lzma/lzma_encoder_init.c b/src/liblzma/lzma/lzma_encoder_init.c
new file mode 100644
index 00000000..d7807529
--- /dev/null
+++ b/src/liblzma/lzma/lzma_encoder_init.c
@@ -0,0 +1,245 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file lzma_encoder_init.c
+/// \brief Creating, resetting and destroying the LZMA encoder
+//
+// Copyright (C) 1999-2006 Igor Pavlov
+// Copyright (C) 2007 Lasse Collin
+//
+// This library is free software; you can redistribute it and/or
+// modify it under the terms of the GNU Lesser General Public
+// License as published by the Free Software Foundation; either
+// version 2.1 of the License, or (at your option) any later version.
+//
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+// Lesser General Public License for more details.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#include "lzma_encoder_private.h"
+
+
+uint8_t lzma_fastpos[1 << 11];
+
+extern void
+lzma_fastpos_init(void)
+{
+ static const uint8_t fast_slots = 22;
+
+ int c = 2;
+ lzma_fastpos[0] = 0;
+ lzma_fastpos[1] = 1;
+
+ for (uint8_t slot_fast = 2; slot_fast < fast_slots; ++slot_fast) {
+ const uint32_t k = (1 << ((slot_fast >> 1) - 1));
+
+ for (uint32_t j = 0; j < k; ++j, ++c)
+ lzma_fastpos[c] = slot_fast;
+ }
+
+ return;
+}
+
+
+/// \brief Initializes the length encoder
+static void
+length_encoder_reset(lzma_length_encoder *lencoder,
+ const uint32_t num_pos_states, const uint32_t table_size)
+{
+ // NLength::CPriceTableEncoder::SetTableSize()
+ lencoder->table_size = table_size;
+
+ // NLength::CEncoder::Init()
+ bit_reset(lencoder->choice);
+ bit_reset(lencoder->choice2);
+
+ for (size_t pos_state = 0; pos_state < num_pos_states; ++pos_state) {
+ bittree_reset(lencoder->low[pos_state], LEN_LOW_BITS);
+ bittree_reset(lencoder->mid[pos_state], LEN_MID_BITS);
+ }
+
+ bittree_reset(lencoder->high, LEN_HIGH_BITS);
+
+ // NLength::CPriceTableEncoder::UpdateTables()
+ for (size_t pos_state = 0; pos_state < num_pos_states; ++pos_state)
+ lzma_length_encoder_update_table(lencoder, pos_state);
+
+ return;
+}
+
+
+static void
+lzma_lzma_encoder_end(lzma_coder *coder, lzma_allocator *allocator)
+{
+ lzma_lz_encoder_end(&coder->lz, allocator);
+ lzma_literal_end(&coder->literal_coder, allocator);
+ lzma_free(coder, allocator);
+ return;
+}
+
+
+extern lzma_ret
+lzma_lzma_encoder_init(lzma_next_coder *next, lzma_allocator *allocator,
+ const lzma_filter_info *filters)
+{
+ if (next->coder == NULL) {
+ next->coder = lzma_alloc(sizeof(lzma_coder), allocator);
+ if (next->coder == NULL)
+ return LZMA_MEM_ERROR;
+
+ next->coder->next = LZMA_NEXT_CODER_INIT;
+ next->coder->lz = LZMA_LZ_ENCODER_INIT;
+ next->coder->literal_coder = NULL;
+ }
+
+ // Validate options that aren't validated elsewhere.
+ const lzma_options_lzma *options = filters[0].options;
+ if (options->pos_bits > LZMA_POS_BITS_MAX
+ || options->fast_bytes < LZMA_FAST_BYTES_MIN
+ || options->fast_bytes > LZMA_FAST_BYTES_MAX) {
+ lzma_lzma_encoder_end(next->coder, allocator);
+ return LZMA_HEADER_ERROR;
+ }
+
+ // Set compression mode.
+ switch (options->mode) {
+ case LZMA_MODE_FAST:
+ next->coder->best_compression = false;
+ break;
+
+ case LZMA_MODE_BEST:
+ next->coder->best_compression = true;
+ break;
+
+ default:
+ lzma_lzma_encoder_end(next->coder, allocator);
+ return LZMA_HEADER_ERROR;
+ }
+
+ // Initialize literal coder.
+ {
+ const lzma_ret ret = lzma_literal_init(
+ &next->coder->literal_coder, allocator,
+ options->literal_context_bits,
+ options->literal_pos_bits);
+ if (ret != LZMA_OK) {
+ lzma_lzma_encoder_end(next->coder, allocator);
+ return ret;
+ }
+ }
+
+ // Initialize LZ encoder.
+ {
+ 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,
+ options->match_finder_cycles,
+ options->preset_dictionary,
+ options->preset_dictionary_size);
+ if (ret != LZMA_OK) {
+ lzma_lzma_encoder_end(next->coder, allocator);
+ return ret;
+ }
+ }
+
+ // Set dist_table_size.
+ {
+ // Round the dictionary size up to next 2^n.
+ uint32_t log_size;
+ for (log_size = 0; (UINT32_C(1) << log_size)
+ < options->dictionary_size; ++log_size) ;
+
+ next->coder->dist_table_size = log_size * 2;
+ }
+
+ // Misc FIXME desc
+ next->coder->dictionary_size = options->dictionary_size;
+ next->coder->pos_mask = (1U << options->pos_bits) - 1;
+ next->coder->fast_bytes = options->fast_bytes;
+
+ // Range coder
+ 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;
+
+ // Bit encoders
+ for (size_t i = 0; i < STATES; ++i) {
+ for (size_t j = 0; j <= next->coder->pos_mask; ++j) {
+ bit_reset(next->coder->is_match[i][j]);
+ bit_reset(next->coder->is_rep0_long[i][j]);
+ }
+
+ bit_reset(next->coder->is_rep[i]);
+ bit_reset(next->coder->is_rep0[i]);
+ bit_reset(next->coder->is_rep1[i]);
+ bit_reset(next->coder->is_rep2[i]);
+ }
+
+ for (size_t i = 0; i < FULL_DISTANCES - END_POS_MODEL_INDEX; ++i)
+ bit_reset(next->coder->pos_encoders[i]);
+
+ // Bit tree encoders
+ for (size_t i = 0; i < LEN_TO_POS_STATES; ++i)
+ bittree_reset(next->coder->pos_slot_encoder[i], POS_SLOT_BITS);
+
+ bittree_reset(next->coder->pos_align_encoder, ALIGN_BITS);
+
+ // Length encoders
+ length_encoder_reset(&next->coder->len_encoder, 1U << options->pos_bits,
+ options->fast_bytes + 1 - MATCH_MIN_LEN);
+
+ length_encoder_reset(&next->coder->rep_match_len_encoder,
+ 1U << options->pos_bits,
+ next->coder->fast_bytes + 1 - MATCH_MIN_LEN);
+
+ // Misc
+ next->coder->longest_match_was_found = false;
+ next->coder->optimum_end_index = 0;
+ next->coder->optimum_current_index = 0;
+ next->coder->additional_offset = 0;
+
+ next->coder->now_pos = 0;
+ next->coder->is_initialized = false;
+
+ // Initialize the next decoder in the chain, if any.
+ {
+ const lzma_ret ret = lzma_next_filter_init(&next->coder->next,
+ allocator, filters + 1);
+ if (ret != LZMA_OK) {
+ lzma_lzma_encoder_end(next->coder, allocator);
+ return ret;
+ }
+ }
+
+ // Initialization successful. Set the function pointers.
+ next->code = &lzma_lz_encode;
+ next->end = &lzma_lzma_encoder_end;
+
+ return LZMA_OK;
+}
+
+
+extern bool
+lzma_lzma_encode_properties(const lzma_options_lzma *options, uint8_t *byte)
+{
+ if (options->literal_context_bits > LZMA_LITERAL_CONTEXT_BITS_MAX
+ || options->literal_pos_bits
+ > LZMA_LITERAL_POS_BITS_MAX
+ || options->pos_bits > LZMA_POS_BITS_MAX)
+ return true;
+
+ *byte = (options->pos_bits * 5 + options->literal_pos_bits) * 9
+ + options->literal_context_bits;
+ assert(*byte <= (4 * 5 + 4) * 9 + 8);
+
+ return false;
+}
diff --git a/src/liblzma/lzma/lzma_encoder_presets.c b/src/liblzma/lzma/lzma_encoder_presets.c
new file mode 100644
index 00000000..966c7c86
--- /dev/null
+++ b/src/liblzma/lzma/lzma_encoder_presets.c
@@ -0,0 +1,34 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file lzma_encoder_presets.c
+/// \brief Encoder presets
+//
+// Copyright (C) 2007 Lasse Collin
+//
+// This library is free software; you can redistribute it and/or
+// modify it under the terms of the GNU Lesser General Public
+// License as published by the Free Software Foundation; either
+// version 2.1 of the License, or (at your option) any later version.
+//
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+// Lesser General Public License for more details.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#include "common.h"
+
+
+LZMA_API const lzma_options_lzma lzma_preset_lzma[9] = {
+// dictionary_size lc lp pb mode fb mf mfc
+{ UINT32_C(1) << 16, 3, 0, 2, NULL, 0, LZMA_MODE_FAST, 64, LZMA_MF_HC3, 0 },
+{ UINT32_C(1) << 20, 3, 0, 2, NULL, 0, LZMA_MODE_FAST, 64, LZMA_MF_HC4, 0 },
+{ UINT32_C(1) << 19, 3, 0, 2, NULL, 0, LZMA_MODE_BEST, 64, LZMA_MF_BT4, 0 },
+{ UINT32_C(1) << 20, 3, 0, 2, NULL, 0, LZMA_MODE_BEST, 64, LZMA_MF_BT4, 0 },
+{ UINT32_C(1) << 21, 3, 0, 2, NULL, 0, LZMA_MODE_BEST, 128, LZMA_MF_BT4, 0 },
+{ UINT32_C(1) << 22, 3, 0, 2, NULL, 0, LZMA_MODE_BEST, 128, LZMA_MF_BT4, 0 },
+{ UINT32_C(1) << 23, 3, 0, 2, NULL, 0, LZMA_MODE_BEST, 128, LZMA_MF_BT4, 0 },
+{ UINT32_C(1) << 24, 3, 0, 2, NULL, 0, LZMA_MODE_BEST, 273, LZMA_MF_BT4, 0 },
+{ UINT32_C(1) << 25, 3, 0, 2, NULL, 0, LZMA_MODE_BEST, 273, LZMA_MF_BT4, 0 },
+};
diff --git a/src/liblzma/lzma/lzma_encoder_private.h b/src/liblzma/lzma/lzma_encoder_private.h
new file mode 100644
index 00000000..7fb1566a
--- /dev/null
+++ b/src/liblzma/lzma/lzma_encoder_private.h
@@ -0,0 +1,225 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file lzma_encoder_private.h
+/// \brief Private definitions for LZMA encoder
+//
+// Copyright (C) 1999-2006 Igor Pavlov
+// Copyright (C) 2007 Lasse Collin
+//
+// This library is free software; you can redistribute it and/or
+// modify it under the terms of the GNU Lesser General Public
+// License as published by the Free Software Foundation; either
+// version 2.1 of the License, or (at your option) any later version.
+//
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+// Lesser General Public License for more details.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#ifndef LZMA_LZMA_ENCODER_PRIVATE_H
+#define LZMA_LZMA_ENCODER_PRIVATE_H
+
+#include "lzma_encoder.h"
+#include "lzma_common.h"
+#include "lz_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. :-)
+#define RC_BUFFER_SIZE 64
+#include "range_encoder.h"
+
+
+#define move_pos(num) \
+do { \
+ assert((int32_t)(num) >= 0); \
+ if ((num) != 0) { \
+ coder->additional_offset += num; \
+ coder->lz.skip(&coder->lz, num); \
+ } \
+} while (0)
+
+
+#define get_pos_slot(pos) \
+ ((pos) < (1 << 11) \
+ ? lzma_fastpos[pos] \
+ : ((pos) < (1 << 21) \
+ ? lzma_fastpos[(pos) >> 10] + 20 \
+ : lzma_fastpos[(pos) >> 20] + 40))
+
+
+#define get_pos_slot_2(pos) \
+ ((pos) < (1 << 17) \
+ ? lzma_fastpos[(pos) >> 6] + 12 \
+ : ((pos) < (1 << 27) \
+ ? lzma_fastpos[(pos) >> 16] + 32 \
+ : lzma_fastpos[(pos) >> 26] + 52))
+
+
+/// This isn't modified once its contents have been
+/// initialized by lzma_fastpos_init().
+extern uint8_t lzma_fastpos[1 << 11];
+
+
+typedef struct {
+ probability choice;
+ probability choice2;
+ probability low[POS_STATES_MAX][LEN_LOW_SYMBOLS];
+ probability mid[POS_STATES_MAX][LEN_MID_SYMBOLS];
+ probability high[LEN_HIGH_SYMBOLS];
+
+ uint32_t prices[POS_STATES_MAX][LEN_SYMBOLS];
+ uint32_t table_size;
+ uint32_t counters[POS_STATES_MAX];
+
+} lzma_length_encoder;
+
+
+typedef struct {
+ uint32_t state;
+
+ bool prev_1_is_char;
+ bool prev_2;
+
+ uint32_t pos_prev_2;
+ uint32_t back_prev_2;
+
+ uint32_t price;
+ uint32_t pos_prev; // pos_next;
+ uint32_t back_prev;
+
+ uint32_t backs[4];
+
+} lzma_optimal;
+
+
+struct lzma_coder_s {
+ // Next coder in the chain
+ lzma_next_coder next;
+
+ // In window and match finder
+ lzma_lz_encoder lz;
+
+ // Range encoder
+ lzma_range_encoder rc;
+
+ // State
+ uint32_t state;
+ uint8_t previous_byte;
+ uint32_t rep_distances[REP_DISTANCES];
+
+ // Misc
+ uint32_t match_distances[MATCH_MAX_LEN * 2 + 2 + 1];
+ uint32_t num_distance_pairs;
+ uint32_t additional_offset;
+ uint32_t now_pos; // Lowest 32 bits are enough here.
+ bool best_compression; ///< True when LZMA_MODE_BEST is used
+ bool is_initialized;
+
+ // Literal encoder
+ lzma_literal_coder *literal_coder;
+
+ // Bit encoders
+ probability is_match[STATES][POS_STATES_MAX];
+ probability is_rep[STATES];
+ probability is_rep0[STATES];
+ probability is_rep1[STATES];
+ probability is_rep2[STATES];
+ probability is_rep0_long[STATES][POS_STATES_MAX];
+ probability pos_encoders[FULL_DISTANCES - END_POS_MODEL_INDEX];
+
+ // Bit Tree Encoders
+ probability pos_slot_encoder[LEN_TO_POS_STATES][1 << POS_SLOT_BITS];
+ probability pos_align_encoder[1 << ALIGN_BITS];
+
+ // Length encoders
+ lzma_length_encoder len_encoder;
+ lzma_length_encoder rep_match_len_encoder;
+
+ // Optimal
+ lzma_optimal optimum[OPTS];
+ uint32_t optimum_end_index;
+ uint32_t optimum_current_index;
+ uint32_t longest_match_length;
+ bool longest_match_was_found;
+
+ // Prices
+ uint32_t pos_slot_prices[LEN_TO_POS_STATES][DIST_TABLE_SIZE_MAX];
+ uint32_t distances_prices[LEN_TO_POS_STATES][FULL_DISTANCES];
+ uint32_t align_prices[ALIGN_TABLE_SIZE];
+ uint32_t align_price_count;
+ uint32_t dist_table_size;
+ uint32_t match_price_count;
+
+ // LZMA specific settings
+ uint32_t dictionary_size; ///< Size in bytes
+ uint32_t fast_bytes;
+ uint32_t pos_state_bits;
+ uint32_t pos_mask; ///< (1 << pos_state_bits) - 1
+};
+
+
+extern void lzma_length_encoder_update_table(lzma_length_encoder *lencoder,
+ const uint32_t pos_state);
+
+extern bool lzma_lzma_encode(lzma_coder *coder, uint8_t *restrict out,
+ size_t *restrict out_pos, size_t out_size);
+
+extern void lzma_get_optimum(lzma_coder *restrict coder,
+ uint32_t *restrict back_res, uint32_t *restrict len_res);
+
+extern void lzma_get_optimum_fast(lzma_coder *restrict coder,
+ uint32_t *restrict back_res, uint32_t *restrict len_res);
+
+
+// NOTE: Don't add 'restrict'.
+static inline void
+lzma_read_match_distances(lzma_coder *coder,
+ uint32_t *len_res, uint32_t *num_distance_pairs)
+{
+ *len_res = 0;
+
+ coder->lz.get_matches(&coder->lz, coder->match_distances);
+
+ *num_distance_pairs = coder->match_distances[0];
+
+ if (*num_distance_pairs > 0) {
+ *len_res = coder->match_distances[*num_distance_pairs - 1];
+ assert(*len_res <= MATCH_MAX_LEN);
+
+ if (*len_res == coder->fast_bytes) {
+ uint32_t offset = *len_res - 1;
+ const uint32_t distance = coder->match_distances[
+ *num_distance_pairs] + 1;
+ uint32_t limit = MATCH_MAX_LEN - *len_res;
+
+ assert(offset + limit < coder->lz.keep_size_after);
+
+ // If we are close to end of the stream, we may need
+ // to limit the length of the match.
+ if (coder->lz.stream_end_was_reached
+ && coder->lz.write_pos
+ < coder->lz.read_pos + offset + limit)
+ limit = coder->lz.write_pos
+ - (coder->lz.read_pos + offset);
+
+ offset += coder->lz.read_pos;
+ uint32_t i = 0;
+ while (i < limit && coder->lz.buffer[offset + i]
+ == coder->lz.buffer[
+ offset + i - distance])
+ ++i;
+
+ *len_res += i;
+ }
+ }
+
+ ++coder->additional_offset;
+
+ return;
+}
+
+#endif
diff --git a/src/liblzma/lzma/lzma_literal.c b/src/liblzma/lzma/lzma_literal.c
new file mode 100644
index 00000000..8f650fbf
--- /dev/null
+++ b/src/liblzma/lzma/lzma_literal.c
@@ -0,0 +1,74 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file lzma_literal.c
+/// \brief Literal Coder
+//
+// Copyright (C) 1999-2006 Igor Pavlov
+// Copyright (C) 2007 Lasse Collin
+//
+// This library is free software; you can redistribute it and/or
+// modify it under the terms of the GNU Lesser General Public
+// License as published by the Free Software Foundation; either
+// version 2.1 of the License, or (at your option) any later version.
+//
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+// Lesser General Public License for more details.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#include "lzma_literal.h"
+
+
+extern lzma_ret
+lzma_literal_init(lzma_literal_coder **coder, lzma_allocator *allocator,
+ uint32_t literal_context_bits, uint32_t literal_pos_bits)
+{
+ // Verify that arguments are sane.
+ if (literal_context_bits > LZMA_LITERAL_CONTEXT_BITS_MAX
+ || literal_pos_bits > LZMA_LITERAL_POS_BITS_MAX)
+ return LZMA_HEADER_ERROR;
+
+ // Calculate the number of states the literal coder must store.
+ const uint32_t states = literal_states(
+ literal_pos_bits, literal_context_bits);
+
+ // Allocate a new literal coder, if needed.
+ if (*coder == NULL || (**coder).literal_context_bits
+ != literal_context_bits
+ || (**coder).literal_pos_bits != literal_pos_bits) {
+ // Free the old coder, if any.
+ lzma_free(*coder, allocator);
+
+ // Allocate a new one.
+ *coder = lzma_alloc(sizeof(lzma_literal_coder)
+ + states * LIT_SIZE * sizeof(probability),
+ allocator);
+ if (*coder == NULL)
+ return LZMA_MEM_ERROR;
+
+ // Store the new settings.
+ (**coder).literal_context_bits = literal_context_bits;
+ (**coder).literal_pos_bits = literal_pos_bits;
+
+ // Calculate also the literal_pos_mask. It's not changed
+ // anywhere else than here.
+ (**coder).literal_pos_mask = (1 << literal_pos_bits) - 1;
+ }
+
+ // Reset the literal coder.
+ for (uint32_t i = 0; i < states; ++i)
+ for (uint32_t j = 0; j < LIT_SIZE; ++j)
+ bit_reset((**coder).coders[i][j]);
+
+ return LZMA_OK;
+}
+
+
+extern void
+lzma_literal_end(lzma_literal_coder **coder, lzma_allocator *allocator)
+{
+ lzma_free(*coder, allocator);
+ *coder = NULL;
+}
diff --git a/src/liblzma/lzma/lzma_literal.h b/src/liblzma/lzma/lzma_literal.h
new file mode 100644
index 00000000..174f5ed4
--- /dev/null
+++ b/src/liblzma/lzma/lzma_literal.h
@@ -0,0 +1,74 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file lzma_literal.h
+/// \brief Literal Coder
+///
+/// This is used as is by both LZMA encoder and decoder.
+//
+// Copyright (C) 1999-2006 Igor Pavlov
+// Copyright (C) 2007 Lasse Collin
+//
+// This library is free software; you can redistribute it and/or
+// modify it under the terms of the GNU Lesser General Public
+// License as published by the Free Software Foundation; either
+// version 2.1 of the License, or (at your option) any later version.
+//
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+// Lesser General Public License for more details.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#ifndef LZMA_LITERAL_H
+#define LZMA_LITERAL_H
+
+#include "common.h"
+
+// We need typedef of `probability'.
+#include "range_common.h"
+
+
+/// Each literal coder is divided in three sections:
+/// - 0x001-0x0FF: Without match byte
+/// - 0x101-0x1FF: With match byte; match bit is 0
+/// - 0x201-0x2FF: With match byte; match bit is 1
+#define LIT_SIZE 0x300
+
+/// Calculate how many states are needed. Each state has
+/// LIT_SIZE `probability' variables.
+#define literal_states(literal_context_bits, literal_pos_bits) \
+ (1U << ((literal_context_bits) + (literal_pos_bits)))
+
+/// Locate the literal coder for the next literal byte. The choice depends on
+/// - the lowest literal_pos_bits bits of the position of the current
+/// byte; and
+/// - the highest literal_context_bits bits of the previous byte.
+#define literal_get_subcoder(literal_coder, pos, prev_byte) \
+ (literal_coder)->coders[(((pos) & (literal_coder)->literal_pos_mask) \
+ << (literal_coder)->literal_context_bits) \
+ + ((prev_byte) >> (8 - (literal_coder)->literal_context_bits))]
+
+
+typedef struct {
+ uint32_t literal_context_bits;
+ uint32_t literal_pos_bits;
+
+ /// literal_pos_mask is always (1 << literal_pos_bits) - 1.
+ uint32_t literal_pos_mask;
+
+ /// There are (1 << (literal_pos_bits + literal_context_bits))
+ /// literal coders.
+ probability coders[][LIT_SIZE];
+
+} lzma_literal_coder;
+
+
+extern lzma_ret lzma_literal_init(
+ lzma_literal_coder **coder, lzma_allocator *allocator,
+ uint32_t literal_context_bits, uint32_t literal_pos_bits);
+
+extern void lzma_literal_end(
+ lzma_literal_coder **coder, lzma_allocator *allocator);
+
+#endif