diff options
Diffstat (limited to 'src/liblzma/lzma')
| -rw-r--r-- | src/liblzma/lzma/Makefile.am | 43 | ||||
| -rw-r--r-- | src/liblzma/lzma/lzma_common.h | 128 | ||||
| -rw-r--r-- | src/liblzma/lzma/lzma_decoder.c | 844 | ||||
| -rw-r--r-- | src/liblzma/lzma/lzma_decoder.h | 41 | ||||
| -rw-r--r-- | src/liblzma/lzma/lzma_encoder.c | 413 | ||||
| -rw-r--r-- | src/liblzma/lzma/lzma_encoder.h | 35 | ||||
| -rw-r--r-- | src/liblzma/lzma/lzma_encoder_features.c | 59 | ||||
| -rw-r--r-- | src/liblzma/lzma/lzma_encoder_getoptimum.c | 893 | ||||
| -rw-r--r-- | src/liblzma/lzma/lzma_encoder_getoptimumfast.c | 201 | ||||
| -rw-r--r-- | src/liblzma/lzma/lzma_encoder_init.c | 245 | ||||
| -rw-r--r-- | src/liblzma/lzma/lzma_encoder_presets.c | 34 | ||||
| -rw-r--r-- | src/liblzma/lzma/lzma_encoder_private.h | 225 | ||||
| -rw-r--r-- | src/liblzma/lzma/lzma_literal.c | 74 | ||||
| -rw-r--r-- | src/liblzma/lzma/lzma_literal.h | 74 |
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 |