diff options
Diffstat (limited to '')
33 files changed, 5513 insertions, 0 deletions
diff --git a/src/liblzma/lz/Makefile.am b/src/liblzma/lz/Makefile.am new file mode 100644 index 00000000..5c27e2f2 --- /dev/null +++ b/src/liblzma/lz/Makefile.am @@ -0,0 +1,63 @@ +## +## 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 = liblz.la +liblz_la_CPPFLAGS = \ + -I@top_srcdir@/src/liblzma/api \ + -I@top_srcdir@/src/liblzma/common \ + -I@top_srcdir@/src/liblzma/check +liblz_la_SOURCES = + + +if COND_MAIN_ENCODER +liblz_la_SOURCES += \ + lz_encoder.c \ + lz_encoder.h \ + lz_encoder_private.h \ + match_c.h \ + match_h.h + +if COND_MF_HC3 +liblz_la_SOURCES += hc3.c hc3.h +liblz_la_CPPFLAGS += -DHAVE_HC3 +endif + +if COND_MF_HC4 +liblz_la_SOURCES += hc4.c hc4.h +liblz_la_CPPFLAGS += -DHAVE_HC4 +endif + +if COND_MF_BT2 +liblz_la_SOURCES += bt2.c bt2.h +liblz_la_CPPFLAGS += -DHAVE_BT2 +endif + +if COND_MF_BT3 +liblz_la_SOURCES += bt3.c bt3.h +liblz_la_CPPFLAGS += -DHAVE_BT3 +endif + +if COND_MF_BT4 +liblz_la_SOURCES += bt4.c bt4.h +liblz_la_CPPFLAGS += -DHAVE_BT4 +endif + +endif + + +if COND_MAIN_DECODER +liblz_la_SOURCES += \ + lz_decoder.c \ + lz_decoder.h +endif diff --git a/src/liblzma/lz/bt2.c b/src/liblzma/lz/bt2.c new file mode 100644 index 00000000..7dc4cb80 --- /dev/null +++ b/src/liblzma/lz/bt2.c @@ -0,0 +1,27 @@ +/////////////////////////////////////////////////////////////////////////////// +// +/// \file bt2.c +/// \brief Binary Tree 2 +// +// 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 "bt2.h" + +#undef IS_HASH_CHAIN +#undef HASH_ARRAY_2 +#undef HASH_ARRAY_3 + +#include "match_c.h" diff --git a/src/liblzma/lz/bt2.h b/src/liblzma/lz/bt2.h new file mode 100644 index 00000000..33cb52cd --- /dev/null +++ b/src/liblzma/lz/bt2.h @@ -0,0 +1,31 @@ +/////////////////////////////////////////////////////////////////////////////// +// +/// \file bt2.h +/// \brief Binary Tree 2 +// +// 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_BT2_H +#define LZMA_BT2_H + +#undef LZMA_MATCH_FINDER_NAME_LOWER +#undef LZMA_MATCH_FINDER_NAME_UPPER +#define LZMA_MATCH_FINDER_NAME_LOWER bt2 +#define LZMA_MATCH_FINDER_NAME_UPPER BT2 + +#include "match_h.h" + +#endif diff --git a/src/liblzma/lz/bt3.c b/src/liblzma/lz/bt3.c new file mode 100644 index 00000000..d44310f3 --- /dev/null +++ b/src/liblzma/lz/bt3.c @@ -0,0 +1,29 @@ +/////////////////////////////////////////////////////////////////////////////// +// +/// \file bt3.c +/// \brief Binary Tree 3 +// +// 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 "bt3.h" + +#undef IS_HASH_CHAIN +#undef HASH_ARRAY_2 +#undef HASH_ARRAY_3 + +#define HASH_ARRAY_2 + +#include "match_c.h" diff --git a/src/liblzma/lz/bt3.h b/src/liblzma/lz/bt3.h new file mode 100644 index 00000000..247c7e5f --- /dev/null +++ b/src/liblzma/lz/bt3.h @@ -0,0 +1,31 @@ +/////////////////////////////////////////////////////////////////////////////// +// +/// \file bt3.h +/// \brief Binary Tree 3 +// +// 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_BT3_H +#define LZMA_BT3_H + +#undef LZMA_MATCH_FINDER_NAME_LOWER +#undef LZMA_MATCH_FINDER_NAME_UPPER +#define LZMA_MATCH_FINDER_NAME_LOWER bt3 +#define LZMA_MATCH_FINDER_NAME_UPPER BT3 + +#include "match_h.h" + +#endif diff --git a/src/liblzma/lz/bt4.c b/src/liblzma/lz/bt4.c new file mode 100644 index 00000000..6e1042c9 --- /dev/null +++ b/src/liblzma/lz/bt4.c @@ -0,0 +1,30 @@ +/////////////////////////////////////////////////////////////////////////////// +// +/// \file bt4.c +/// \brief Binary Tree 4 +// +// 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 "bt4.h" + +#undef IS_HASH_CHAIN +#undef HASH_ARRAY_2 +#undef HASH_ARRAY_3 + +#define HASH_ARRAY_2 +#define HASH_ARRAY_3 + +#include "match_c.h" diff --git a/src/liblzma/lz/bt4.h b/src/liblzma/lz/bt4.h new file mode 100644 index 00000000..e3fcf6ac --- /dev/null +++ b/src/liblzma/lz/bt4.h @@ -0,0 +1,31 @@ +/////////////////////////////////////////////////////////////////////////////// +// +/// \file bt4.h +/// \brief Binary Tree 4 +// +// 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_BT4_H +#define LZMA_BT4_H + +#undef LZMA_MATCH_FINDER_NAME_LOWER +#undef LZMA_MATCH_FINDER_NAME_UPPER +#define LZMA_MATCH_FINDER_NAME_LOWER bt4 +#define LZMA_MATCH_FINDER_NAME_UPPER BT4 + +#include "match_h.h" + +#endif diff --git a/src/liblzma/lz/hc3.c b/src/liblzma/lz/hc3.c new file mode 100644 index 00000000..22b5689b --- /dev/null +++ b/src/liblzma/lz/hc3.c @@ -0,0 +1,30 @@ +/////////////////////////////////////////////////////////////////////////////// +// +/// \file hc3.c +/// \brief Hash Chain 3 +// +// 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 "hc3.h" + +#undef IS_HASH_CHAIN +#undef HASH_ARRAY_2 +#undef HASH_ARRAY_3 + +#define IS_HASH_CHAIN +#define HASH_ARRAY_2 + +#include "match_c.h" diff --git a/src/liblzma/lz/hc3.h b/src/liblzma/lz/hc3.h new file mode 100644 index 00000000..97be0b1d --- /dev/null +++ b/src/liblzma/lz/hc3.h @@ -0,0 +1,31 @@ +/////////////////////////////////////////////////////////////////////////////// +// +/// \file hc3.h +/// \brief Hash Chain 3 +// +// 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_HC3_H +#define LZMA_HC3_H + +#undef LZMA_MATCH_FINDER_NAME_LOWER +#undef LZMA_MATCH_FINDER_NAME_UPPER +#define LZMA_MATCH_FINDER_NAME_LOWER hc3 +#define LZMA_MATCH_FINDER_NAME_UPPER HC3 + +#include "match_h.h" + +#endif diff --git a/src/liblzma/lz/hc4.c b/src/liblzma/lz/hc4.c new file mode 100644 index 00000000..a55cfd09 --- /dev/null +++ b/src/liblzma/lz/hc4.c @@ -0,0 +1,31 @@ +/////////////////////////////////////////////////////////////////////////////// +// +/// \file hc4.c +/// \brief Hash Chain 4 +// +// 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 "hc4.h" + +#undef IS_HASH_CHAIN +#undef HASH_ARRAY_2 +#undef HASH_ARRAY_3 + +#define IS_HASH_CHAIN +#define HASH_ARRAY_2 +#define HASH_ARRAY_3 + +#include "match_c.h" diff --git a/src/liblzma/lz/hc4.h b/src/liblzma/lz/hc4.h new file mode 100644 index 00000000..dc072e2f --- /dev/null +++ b/src/liblzma/lz/hc4.h @@ -0,0 +1,31 @@ +/////////////////////////////////////////////////////////////////////////////// +// +/// \file hc4.h +/// \brief Hash Chain 4 +// +// 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_HC4_H +#define LZMA_HC4_H + +#undef LZMA_MATCH_FINDER_NAME_LOWER +#undef LZMA_MATCH_FINDER_NAME_UPPER +#define LZMA_MATCH_FINDER_NAME_LOWER hc4 +#define LZMA_MATCH_FINDER_NAME_UPPER HC4 + +#include "match_h.h" + +#endif diff --git a/src/liblzma/lz/lz_decoder.c b/src/liblzma/lz/lz_decoder.c new file mode 100644 index 00000000..9c110dec --- /dev/null +++ b/src/liblzma/lz/lz_decoder.c @@ -0,0 +1,462 @@ +/////////////////////////////////////////////////////////////////////////////// +// +/// \file lz_decoder.c +/// \brief LZ out window +// +// 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 "lz_decoder.h" + + +/// Minimum size of allocated dictionary +#define DICT_SIZE_MIN 8192 + +/// When there is less than this amount of data available for decoding, +/// it is moved to the temporary buffer which +/// - protects from reads past the end of the buffer; and +/// - stored the incomplete data between lzma_code() calls. +/// +/// \note TEMP_LIMIT must be at least as much as +/// REQUIRED_IN_BUFFER_SIZE defined in lzma_decoder.c. +#define TEMP_LIMIT 32 + +// lzma_lz_decoder.dict[] must be three times the size of TEMP_LIMIT. +// 2 * TEMP_LIMIT is used for the actual data, and the third TEMP_LIMIT +// bytes is needed for safety to allow decode_dummy() in lzma_decoder.c +// to read past end of the buffer. This way it should be both fast and simple. +#if LZMA_BUFFER_SIZE < 3 * TEMP_LIMIT +# error LZMA_BUFFER_SIZE < 3 * TEMP_LIMIT +#endif + + +struct lzma_coder_s { + lzma_next_coder next; + lzma_lz_decoder lz; + + // There are more members in this structure but they are not + // visible in LZ coder. +}; + + +/// - Copy as much data as possible from lz->dict[] to out[]. +/// - Update *out_pos, lz->start, and lz->end accordingly. +/// - Wrap lz-pos to the beginning of lz->dict[] if there is a danger that +/// it may go past the end of the buffer (lz->pos >= lz->must_flush_pos). +static inline bool +flush(lzma_lz_decoder *restrict lz, uint8_t *restrict out, + size_t *restrict out_pos, size_t out_size) +{ + // Flush uncompressed data from the history buffer to + // the output buffer. This is done in two phases. + + assert(lz->start <= lz->end); + + // Flush if pos < start < end. + if (lz->pos < lz->start && lz->start < lz->end) { + bufcpy(lz->dict, &lz->start, lz->end, out, out_pos, out_size); + + // If we reached end of the data in history buffer, + // wrap to the beginning. + if (lz->start == lz->end) + lz->start = 0; + } + + // Flush if start start < pos <= end. This is not as `else' for + // previous `if' because the previous one may make this one true. + if (lz->start < lz->pos) { + bufcpy(lz->dict, &lz->start, + lz->pos, out, out_pos, out_size); + + if (lz->pos >= lz->must_flush_pos) { + // Wrap the flushing position if we have + // flushed the whole history buffer. + if (lz->pos == lz->start) + lz->start = 0; + + // Wrap the write position and store to lz.end + // how much there is new data available. + lz->end = lz->pos; + lz->pos = 0; + lz->is_full = true; + } + } + + assert(lz->pos < lz->must_flush_pos); + + return *out_pos == out_size; +} + + +/// Calculate safe value for lz->limit. If no safe value can be found, +/// set lz->limit to zero. When flushing, only as little data will be +/// decoded as is needed to fill the output buffer (lowers both latency +/// and throughput). +/// +/// \return true if there is no space for new uncompressed data. +/// +static inline bool +set_limit(lzma_lz_decoder *lz, size_t out_avail, bool flushing) +{ + // Set the limit so that writing to dict[limit + match_max_len - 1] + // doesn't overwrite any unflushed data and doesn't write past the + // end of the dict buffer. + if (lz->start <= lz->pos) { + // We can fill the buffer from pos till the end + // of the dict buffer. + lz->limit = lz->must_flush_pos; + } else if (lz->pos + lz->match_max_len < lz->start) { + // There's some unflushed data between pos and end of the + // buffer. Limit so that we don't overwrite the unflushed data. + lz->limit = lz->start - lz->match_max_len; + } else { + // Buffer is too full. + lz->limit = 0; + return true; + } + + // Finetune the limit a bit if it isn't zero. + + assert(lz->limit > lz->pos); + const size_t dict_avail = lz->limit - lz->pos; + + if (lz->uncompressed_size < dict_avail) { + // Finishing a stream that doesn't have + // an end of stream marker. + lz->limit = lz->pos + lz->uncompressed_size; + + } else if (flushing && out_avail < dict_avail) { + // Flushing enabled, decoding only as little as needed to + // fill the out buffer (if there's enough input, of course). + lz->limit = lz->pos + out_avail; + } + + return lz->limit == lz->pos; +} + + +/// Takes care of wrapping the data into temporary buffer when needed, +/// and calls the actual decoder. +/// +/// \return true if error occurred +/// +static inline bool +call_process(lzma_coder *restrict coder, const uint8_t *restrict in, + size_t *restrict in_pos, size_t in_size) +{ + // It would be nice and simple if we could just give in[] to the + // decoder, but the requirement of zlib-like API forces us to be + // able to make *in_pos == in_size whenever there is enough output + // space. If needed, we will append a few bytes from in[] to + // a temporary buffer and decode enough to reach the part that + // was copied from in[]. Then we can continue with the real in[]. + + bool error; + const size_t dict_old_pos = coder->lz.pos; + const size_t in_avail = in_size - *in_pos; + + if (coder->lz.temp_size + in_avail < 2 * TEMP_LIMIT) { + // Copy all the available input from in[] to temp[]. + memcpy(coder->lz.temp + coder->lz.temp_size, + in + *in_pos, in_avail); + coder->lz.temp_size += in_avail; + *in_pos += in_avail; + assert(*in_pos == in_size); + + // Decode as much as possible. + size_t temp_used = 0; + error = coder->lz.process(coder, coder->lz.temp, &temp_used, + coder->lz.temp_size, true); + assert(temp_used <= coder->lz.temp_size); + + // Move the remaining data to the beginning of temp[]. + coder->lz.temp_size -= temp_used; + memmove(coder->lz.temp, coder->lz.temp + temp_used, + coder->lz.temp_size); + + } else if (coder->lz.temp_size > 0) { + // Fill temp[] unless it is already full because we aren't + // the last filter in the chain. + size_t copy_size = 0; + if (coder->lz.temp_size < 2 * TEMP_LIMIT) { + assert(*in_pos < in_size); + copy_size = 2 * TEMP_LIMIT - coder->lz.temp_size; + memcpy(coder->lz.temp + coder->lz.temp_size, + in + *in_pos, copy_size); + // NOTE: We don't update lz.temp_size or *in_pos yet. + } + + size_t temp_used = 0; + error = coder->lz.process(coder, coder->lz.temp, &temp_used, + coder->lz.temp_size + copy_size, false); + + if (temp_used < coder->lz.temp_size) { + // Only very little input data was consumed. Move + // the unprocessed data to the beginning temp[]. + coder->lz.temp_size += copy_size - temp_used; + memmove(coder->lz.temp, coder->lz.temp + temp_used, + coder->lz.temp_size); + *in_pos += copy_size; + assert(*in_pos <= in_size); + + } else { + // We were able to decode so much data that next time + // we can decode directly from in[]. That is, we can + // consider temp[] to be empty now. + *in_pos += temp_used - coder->lz.temp_size; + coder->lz.temp_size = 0; + assert(*in_pos <= in_size); + } + + } else { + // Decode directly from in[]. + error = coder->lz.process(coder, in, in_pos, in_size, false); + assert(*in_pos <= in_size); + } + + assert(coder->lz.pos >= dict_old_pos); + if (coder->lz.uncompressed_size != LZMA_VLI_VALUE_UNKNOWN) { + // Update uncompressed size. + coder->lz.uncompressed_size -= coder->lz.pos - dict_old_pos; + + // Check that End of Payload Marker hasn't been detected + // since it must not be present because uncompressed size + // is known. + if (coder->lz.eopm_detected) + error = true; + } + + return error; +} + + +static lzma_ret +decode_buffer(lzma_coder *coder, + const uint8_t *restrict in, size_t *restrict in_pos, + size_t in_size, uint8_t *restrict out, + size_t *restrict out_pos, size_t out_size, + bool flushing) +{ + bool stop = false; + + while (true) { + // Flush from coder->lz.dict to out[]. + flush(&coder->lz, out, out_pos, out_size); + + // All done? + if (*out_pos == out_size + || stop + || coder->lz.eopm_detected + || coder->lz.uncompressed_size == 0) + break; + + // Set write limit in the dictionary. + if (set_limit(&coder->lz, out_size - *out_pos, flushing)) + break; + + // Decode more data. + if (call_process(coder, in, in_pos, in_size)) + return LZMA_DATA_ERROR; + + // Set stop to true if we must not call call_process() again + // during this function call. + // FIXME: Can this make the loop exist too early? It wouldn't + // cause data corruption so not a critical problem. It can + // happen if dictionary gets full and lz.temp still contains + // a few bytes data that we could decode right now. + if (*in_pos == in_size && coder->lz.temp_size <= TEMP_LIMIT + && coder->lz.pos < coder->lz.limit) + stop = true; + } + + // If we have decoded everything (EOPM detected or uncompressed_size + // bytes were processed) to the history buffer, and also flushed + // everything from the history buffer, our job is done. + if ((coder->lz.eopm_detected + || coder->lz.uncompressed_size == 0) + && coder->lz.start == coder->lz.pos) + return LZMA_STREAM_END; + + return LZMA_OK; +} + + +extern lzma_ret +lzma_lz_decode(lzma_coder *coder, + lzma_allocator *allocator lzma_attribute((unused)), + const uint8_t *restrict in, size_t *restrict in_pos, + size_t in_size, uint8_t *restrict out, + size_t *restrict out_pos, size_t out_size, + lzma_action action) +{ + if (coder->next.code == NULL) { + const lzma_ret ret = decode_buffer(coder, in, in_pos, in_size, + out, out_pos, out_size, + action == LZMA_SYNC_FLUSH); + + if (*out_pos == out_size || ret == LZMA_STREAM_END) { + // Unread to make coder->temp[] empty. This is easy, + // because we know that all the data currently in + // coder->temp[] has been copied form in[] during this + // call to the decoder. + // + // If we didn't do this, we could have data left in + // coder->temp[] when end of stream is reached. That + // data could be left there from *previous* call to + // the decoder; in that case we wouldn't know where + // to put that data. + assert(*in_pos >= coder->lz.temp_size); + *in_pos -= coder->lz.temp_size; + coder->lz.temp_size = 0; + } + + return ret; + } + + // We aren't the last coder in the chain, we need to decode + // our input to a temporary buffer. + const bool flushing = action == LZMA_SYNC_FLUSH; + while (*out_pos < out_size) { + if (!coder->lz.next_finished + && coder->lz.temp_size < LZMA_BUFFER_SIZE) { + const lzma_ret ret = coder->next.code( + coder->next.coder, + allocator, in, in_pos, in_size, + coder->lz.temp, &coder->lz.temp_size, + LZMA_BUFFER_SIZE, action); + + if (ret == LZMA_STREAM_END) + coder->lz.next_finished = true; + else if (coder->lz.temp_size < LZMA_BUFFER_SIZE + || ret != LZMA_OK) + return ret; + } + + if (coder->lz.this_finished) { + if (coder->lz.temp_size != 0) + return LZMA_DATA_ERROR; + + if (coder->lz.next_finished) + return LZMA_STREAM_END; + + return LZMA_OK; + } + + size_t dummy = 0; + const lzma_ret ret = decode_buffer(coder, NULL, &dummy, 0, + out, out_pos, out_size, flushing); + + if (ret == LZMA_STREAM_END) + coder->lz.this_finished = true; + else if (ret != LZMA_OK) + return ret; + else if (coder->lz.next_finished && *out_pos < out_size) + return LZMA_DATA_ERROR; + } + + return LZMA_OK; +} + + +/// \brief Initializes LZ part of the LZMA decoder or Inflate +/// +/// \param history_size Number of bytes the LZ out window is +/// supposed keep available from the output +/// history. +/// \param match_max_len Number of bytes a single decoding loop +/// can advance the write position (lz->pos) +/// in the history buffer (lz->dict). +/// +/// \note This function is called by LZMA decoder and Inflate init()s. +/// It's up to those functions allocate *lz and initialize it +/// with LZMA_LZ_DECODER_INIT. +extern lzma_ret +lzma_lz_decoder_reset(lzma_lz_decoder *lz, lzma_allocator *allocator, + bool (*process)(lzma_coder *restrict coder, + const uint8_t *restrict in, size_t *restrict in_pos, + size_t in_size, bool has_safe_buffer), + lzma_vli uncompressed_size, + size_t history_size, size_t match_max_len) +{ + // Set uncompressed size. + lz->uncompressed_size = uncompressed_size; + + // Limit the history size to roughly sane values. This is primarily + // to prevent integer overflows. + if (history_size > UINT32_MAX / 2) + return LZMA_HEADER_ERROR; + + // Store the value actually requested. We use it for sanity checks + // when repeating data from the history buffer. + lz->requested_size = history_size; + + // Avoid tiny history buffer sizes for performance reasons. + // TODO: Test if this actually helps... + if (history_size < DICT_SIZE_MIN) + history_size = DICT_SIZE_MIN; + + // The real size of the history buffer is a bit bigger than + // requested by our caller. This allows us to do some optimizations, + // which help not only speed but simplicity of the code; specifically, + // we can make sure that there is always at least match_max_len + // bytes immediatelly available for writing without a need to wrap + // the history buffer. + const size_t dict_real_size = history_size + 2 * match_max_len + 1; + + // Reallocate memory if needed. + if (history_size != lz->size || match_max_len != lz->match_max_len) { + // Destroy the old buffer. + lzma_lz_decoder_end(lz, allocator); + + lz->size = history_size; + lz->match_max_len = match_max_len; + lz->must_flush_pos = history_size + match_max_len + 1; + + lz->dict = lzma_alloc(dict_real_size, allocator); + if (lz->dict == NULL) + return LZMA_MEM_ERROR; + } + + // Clean up the buffers to make it very sure that there are + // no information leaks when multiple steams are decoded + // with the same decoder structures. + memzero(lz->dict, dict_real_size); + memzero(lz->temp, LZMA_BUFFER_SIZE); + + // Reset the variables so that lz_get_byte(lz, 0) will return '\0'. + lz->pos = 0; + lz->start = 0; + lz->end = dict_real_size; + lz->is_full = false; + lz->eopm_detected = false; + lz->next_finished = false; + lz->this_finished = false; + + // Set the process function pointer. + lz->process = process; + + return LZMA_OK; +} + + +extern void +lzma_lz_decoder_end(lzma_lz_decoder *lz, lzma_allocator *allocator) +{ + lzma_free(lz->dict, allocator); + lz->dict = NULL; + lz->size = 0; + lz->match_max_len = 0; + return; +} diff --git a/src/liblzma/lz/lz_decoder.h b/src/liblzma/lz/lz_decoder.h new file mode 100644 index 00000000..a8a585cd --- /dev/null +++ b/src/liblzma/lz/lz_decoder.h @@ -0,0 +1,214 @@ +/////////////////////////////////////////////////////////////////////////////// +// +/// \file lz_decoder.h +/// \brief LZ out window +// +// 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_LZ_OUT_H +#define LZMA_LZ_OUT_H + +#include "common.h" + + +/// Get a byte from the history buffer. +#define lz_get_byte(lz, distance) \ + ((distance) < (lz).pos \ + ? (lz).dict[(lz).pos - (distance) - 1] \ + : (lz).dict[(lz).pos - (distance) - 1 + (lz).end]) + + +#define LZMA_LZ_DECODER_INIT \ + (lzma_lz_decoder){ .dict = NULL, .size = 0, .match_max_len = 0 } + + +typedef struct { + /// Function to do the actual decoding (LZMA or Inflate) + bool (*process)(lzma_coder *restrict coder, const uint8_t *restrict in, + size_t *restrict in_pos, size_t size_in, + bool has_safe_buffer); + + /// Pointer to dictionary (history) buffer. + /// \note Not 'restrict' because can alias next_out. + uint8_t *dict; + + /// Next write goes to dict[pos]. + size_t pos; + + /// Next byte to flush is buffer[start]. + size_t start; + + /// First byte to not flush is buffer[end]. + size_t end; + + /// First position to which data must not be written. + size_t limit; + + /// True if dictionary has needed wrapping. + bool is_full; + + /// True if process() has detected End of Payload Marker. + bool eopm_detected; + + /// True if the next coder in the chain has returned LZMA_STREAM_END. + bool next_finished; + + /// True if the LZ decoder (e.g. LZMA) has detected End of Payload + /// Marker. This may become true before next_finished becomes true. + bool this_finished; + + /// When pos >= must_flush_pos, we must not call process(). + size_t must_flush_pos; + + /// Maximum number of bytes that a single decoding loop inside + /// process() can produce data into dict. This amount is kept + /// always available at dict + pos i.e. it is safe to write a byte + /// to dict[pos + match_max_len - 1]. + size_t match_max_len; + + /// Number of bytes allocated to dict. + size_t size; + + /// Requested size of the dictionary. This is needed because we avoid + /// using extremely tiny history buffers. + size_t requested_size; + + /// Uncompressed Size or LZMA_VLI_VALUE_UNKNOWN if unknown. + lzma_vli uncompressed_size; + + /// Number of bytes currently in temp[]. + size_t temp_size; + + /// Temporary buffer needed when + /// 1) we cannot make the input buffer completely empty; or + /// 2) we are not the last filter in the chain. + uint8_t temp[LZMA_BUFFER_SIZE]; + +} lzma_lz_decoder; + + +///////////////////////// +// Function prototypes // +///////////////////////// + +extern lzma_ret lzma_lz_decoder_reset(lzma_lz_decoder *lz, + lzma_allocator *allocator, bool (*process)( + lzma_coder *restrict coder, const uint8_t *restrict in, + size_t *restrict in_pos, size_t in_size, + bool has_safe_buffer), + lzma_vli uncompressed_size, + size_t history_size, size_t match_max_len); + +extern lzma_ret lzma_lz_decode(lzma_coder *coder, lzma_allocator *allocator, + const uint8_t *restrict in, size_t *restrict in_pos, + size_t in_size, uint8_t *restrict out, + size_t *restrict out_pos, size_t out_size, + lzma_action action); + +/// Deallocates the history buffer if one exists. +extern void lzma_lz_decoder_end( + lzma_lz_decoder *lz, lzma_allocator *allocator); + +////////////////////// +// Inline functions // +////////////////////// + +// Repeat a block of data from the history. Because memcpy() is faster +// than copying byte by byte in a loop, the copying process gets split +// into three cases: +// 1. distance < length +// Source and target areas overlap, thus we can't use memcpy() +// (nor memmove()) safely. +// TODO: If this is common enough, it might be worth optimizing this +// more e.g. by checking if distance > sizeof(uint8_t*) and using +// memcpy in small chunks. +// 2. distance < pos +// This is the easiest and the fastest case. The block being copied +// is a contiguous piece in the history buffer. The buffer offset +// doesn't need wrapping. +// 3. distance >= pos +// We need to wrap the position, because otherwise we would try copying +// behind the first byte of the allocated buffer. It is possible that +// the block is fragmeneted into two pieces, thus we might need to call +// memcpy() twice. +// NOTE: The function using this macro must ensure that length is positive +// and that distance is FIXME +static inline bool +lzma_lz_out_repeat(lzma_lz_decoder *lz, size_t distance, size_t length) +{ + // Validate offset of the block to be repeated. It doesn't + // make sense to copy data behind the beginning of the stream. + // Leaving this check away would lead to a security problem, + // in which e.g. the data of the previously decoded file(s) + // would be leaked (or whatever happens to be in unused + // part of the dictionary buffer). + if (distance >= lz->pos && !lz->is_full) + return false; + + // It also doesn't make sense to copy data farer than + // the dictionary size. + if (distance >= lz->requested_size) + return false; + + // The caller must have checked these! + assert(distance <= lz->size); + assert(length > 0); + assert(length <= lz->match_max_len); + + // Copy the amount of data requested by the decoder. + if (distance < length) { + // Source and target areas overlap, thus we can't use + // memcpy() nor even memmove() safely. :-( + // TODO: Copying byte by byte is slow. It might be + // worth optimizing this more if this case is common. + do { + lz->dict[lz->pos] = lz_get_byte(*lz, distance); + ++lz->pos; + } while (--length > 0); + + } else if (distance < lz->pos) { + // The easiest and fastest case + memcpy(lz->dict + lz->pos, + lz->dict + lz->pos - distance - 1, + length); + lz->pos += length; + + } else { + // The bigger the dictionary, the more rare this + // case occurs. We need to "wrap" the dict, thus + // we might need two memcpy() to copy all the data. + assert(lz->is_full); + const uint32_t copy_pos = lz->pos - distance - 1 + lz->end; + uint32_t copy_size = lz->end - copy_pos; + + if (copy_size < length) { + memcpy(lz->dict + lz->pos, lz->dict + copy_pos, + copy_size); + lz->pos += copy_size; + copy_size = length - copy_size; + memcpy(lz->dict + lz->pos, lz->dict, copy_size); + lz->pos += copy_size; + } else { + memcpy(lz->dict + lz->pos, lz->dict + copy_pos, + length); + lz->pos += length; + } + } + + return true; +} + +#endif diff --git a/src/liblzma/lz/lz_encoder.c b/src/liblzma/lz/lz_encoder.c new file mode 100644 index 00000000..bc38cae2 --- /dev/null +++ b/src/liblzma/lz/lz_encoder.c @@ -0,0 +1,481 @@ +/////////////////////////////////////////////////////////////////////////////// +// +/// \file lz_encoder.c +/// \brief LZ in window +// +// 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 "lz_encoder_private.h" + +// Hash Chains +#ifdef HAVE_HC3 +# include "hc3.h" +#endif +#ifdef HAVE_HC4 +# include "hc4.h" +#endif + +// Binary Trees +#ifdef HAVE_BT2 +# include "bt2.h" +#endif +#ifdef HAVE_BT3 +# include "bt3.h" +#endif +#ifdef HAVE_BT4 +# include "bt4.h" +#endif + + +/// This is needed in two places so provide a macro. +#define get_cyclic_buffer_size(history_size) ((history_size) + 1) + + +/// Calculate certain match finder properties and validate the calculated +/// values. This is as its own function, because *num_items is needed to +/// calculate memory requirements in common/memory.c. +extern uint32_t +lzma_lz_encoder_hash_properties(lzma_match_finder match_finder, + uint32_t history_size, uint32_t *restrict hash_mask, + uint32_t *restrict hash_size_sum, uint32_t *restrict num_items) +{ + uint32_t fix_hash_size; + uint32_t sons; + + switch (match_finder) { +#ifdef HAVE_HC3 + case LZMA_MF_HC3: + fix_hash_size = LZMA_HC3_FIX_HASH_SIZE; + sons = 1; + break; +#endif +#ifdef HAVE_HC4 + case LZMA_MF_HC4: + fix_hash_size = LZMA_HC4_FIX_HASH_SIZE; + sons = 1; + break; +#endif +#ifdef HAVE_BT2 + case LZMA_MF_BT2: + fix_hash_size = LZMA_BT2_FIX_HASH_SIZE; + sons = 2; + break; +#endif +#ifdef HAVE_BT3 + case LZMA_MF_BT3: + fix_hash_size = LZMA_BT3_FIX_HASH_SIZE; + sons = 2; + break; +#endif +#ifdef HAVE_BT4 + case LZMA_MF_BT4: + fix_hash_size = LZMA_BT4_FIX_HASH_SIZE; + sons = 2; + break; +#endif + default: + return true; + } + + uint32_t hs; + +#ifdef HAVE_LZMA_BT2 + if (match_finder == LZMA_BT2) { + // NOTE: hash_mask is not used by the BT2 match finder, + // but it is initialized just in case. + hs = LZMA_BT2_HASH_SIZE; + *hash_mask = 0; + } else +#endif + { + hs = history_size - 1; + hs |= (hs >> 1); + hs |= (hs >> 2); + hs |= (hs >> 4); + hs |= (hs >> 8); + hs >>= 1; + hs |= 0xFFFF; + + if (hs > (UINT32_C(1) << 24)) { + if (match_finder == LZMA_MF_HC4 + || match_finder == LZMA_MF_BT4) + hs >>= 1; + else + hs = (1 << 24) - 1; + } + + *hash_mask = hs; + ++hs; + } + + *hash_size_sum = hs + fix_hash_size; + + *num_items = *hash_size_sum + + get_cyclic_buffer_size(history_size) * sons; + + return false; +} + + +extern lzma_ret +lzma_lz_encoder_reset(lzma_lz_encoder *lz, lzma_allocator *allocator, + bool (*process)(lzma_coder *coder, uint8_t *restrict out, + size_t *restrict out_pos, size_t out_size), + lzma_vli uncompressed_size, + size_t history_size, size_t additional_buffer_before, + size_t match_max_len, size_t additional_buffer_after, + lzma_match_finder match_finder, uint32_t match_finder_cycles, + const uint8_t *preset_dictionary, + size_t preset_dictionary_size) +{ + // Set uncompressed size. + lz->uncompressed_size = uncompressed_size; + + /////////////// + // In Window // + /////////////// + + // Validate history size. + if (history_size < LZMA_DICTIONARY_SIZE_MIN + || history_size > LZMA_DICTIONARY_SIZE_MAX) { + lzma_lz_encoder_end(lz, allocator); + return LZMA_HEADER_ERROR; + } + + assert(history_size <= MAX_VAL_FOR_NORMALIZE - 256); + assert(LZMA_DICTIONARY_SIZE_MAX <= MAX_VAL_FOR_NORMALIZE - 256); + + // Calculate the size of the history buffer to allocate. + // TODO: Get a reason for magic constant of 256. + const size_t size_reserv = (history_size + additional_buffer_before + + match_max_len + additional_buffer_after) / 2 + 256; + + lz->keep_size_before = history_size + additional_buffer_before; + lz->keep_size_after = match_max_len + additional_buffer_after; + + const size_t buffer_size = lz->keep_size_before + lz->keep_size_after + + size_reserv; + + // Allocate history buffer if its size has changed. + if (buffer_size != lz->size) { + lzma_free(lz->buffer, allocator); + lz->buffer = lzma_alloc(buffer_size, allocator); + if (lz->buffer == NULL) { + lzma_lz_encoder_end(lz, allocator); + return LZMA_MEM_ERROR; + } + } + + // Allocation successful. Store the new size and calculate + // must_move_pos. + lz->size = buffer_size; + lz->must_move_pos = lz->size - lz->keep_size_after; + + // Reset in window variables. + lz->offset = 0; + lz->read_pos = 0; + lz->read_limit = 0; + lz->write_pos = 0; + lz->stream_end_was_reached = false; + + + ////////////////// + // Match Finder // + ////////////////// + + // Validate match_finder, set function pointers and a few match + // finder specific variables. + switch (match_finder) { +#ifdef HAVE_HC3 + case LZMA_MF_HC3: + lz->get_matches = &lzma_hc3_get_matches; + lz->skip = &lzma_hc3_skip; + lz->cut_value = 8 + (match_max_len >> 2); + break; +#endif +#ifdef HAVE_HC4 + case LZMA_MF_HC4: + lz->get_matches = &lzma_hc4_get_matches; + lz->skip = &lzma_hc4_skip; + lz->cut_value = 8 + (match_max_len >> 2); + break; +#endif +#ifdef HAVE_BT2 + case LZMA_MF_BT2: + lz->get_matches = &lzma_bt2_get_matches; + lz->skip = &lzma_bt2_skip; + lz->cut_value = 16 + (match_max_len >> 1); + break; +#endif +#ifdef HAVE_BT3 + case LZMA_MF_BT3: + lz->get_matches = &lzma_bt3_get_matches; + lz->skip = &lzma_bt3_skip; + lz->cut_value = 16 + (match_max_len >> 1); + break; +#endif +#ifdef HAVE_BT4 + case LZMA_MF_BT4: + lz->get_matches = &lzma_bt4_get_matches; + lz->skip = &lzma_bt4_skip; + lz->cut_value = 16 + (match_max_len >> 1); + break; +#endif + default: + lzma_lz_encoder_end(lz, allocator); + return LZMA_HEADER_ERROR; + } + + // Check if we have been requested to use a non-default cut_value. + if (match_finder_cycles > 0) + lz->cut_value = match_finder_cycles; + + lz->match_max_len = match_max_len; + lz->cyclic_buffer_size = get_cyclic_buffer_size(history_size); + + uint32_t hash_size_sum; + uint32_t num_items; + if (lzma_lz_encoder_hash_properties(match_finder, history_size, + &lz->hash_mask, &hash_size_sum, &num_items)) { + lzma_lz_encoder_end(lz, allocator); + return LZMA_HEADER_ERROR; + } + + if (num_items != lz->num_items) { +#if UINT32_MAX >= SIZE_MAX / 4 + // Check for integer overflow. (Huge dictionaries are not + // possible on 32-bit CPU.) + if (num_items > SIZE_MAX / sizeof(uint32_t)) { + lzma_lz_encoder_end(lz, allocator); + return LZMA_MEM_ERROR; + } +#endif + + const size_t size_in_bytes + = (size_t)(num_items) * sizeof(uint32_t); + + lzma_free(lz->hash, allocator); + lz->hash = lzma_alloc(size_in_bytes, allocator); + if (lz->hash == NULL) { + lzma_lz_encoder_end(lz, allocator); + return LZMA_MEM_ERROR; + } + + lz->num_items = num_items; + } + + lz->son = lz->hash + hash_size_sum; + + // Reset the hash table to empty hash values. + { + uint32_t *restrict items = lz->hash; + + for (uint32_t i = 0; i < hash_size_sum; ++i) + items[i] = EMPTY_HASH_VALUE; + } + + lz->cyclic_buffer_pos = 0; + + // Because zero is used as empty hash value, make the first byte + // appear at buffer[1 - offset]. + ++lz->offset; + + // If we are using a preset dictionary, read it now. + // TODO: This isn't implemented yet so return LZMA_HEADER_ERROR. + if (preset_dictionary != NULL && preset_dictionary_size > 0) { + lzma_lz_encoder_end(lz, allocator); + return LZMA_HEADER_ERROR; + } + + // Set the process function pointer. + lz->process = process; + + return LZMA_OK; +} + + +extern void +lzma_lz_encoder_end(lzma_lz_encoder *lz, lzma_allocator *allocator) +{ + lzma_free(lz->hash, allocator); + lz->hash = NULL; + lz->num_items = 0; + + lzma_free(lz->buffer, allocator); + lz->buffer = NULL; + lz->size = 0; + + return; +} + + +/// \brief Moves the data in the input window to free space for new data +/// +/// lz->buffer is a sliding input window, which keeps lz->keep_size_before +/// bytes of input history available all the time. Now and then we need to +/// "slide" the buffer to make space for the new data to the end of the +/// buffer. At the same time, data older than keep_size_before is dropped. +/// +static void +move_window(lzma_lz_encoder *lz) +{ + // buffer[move_offset] will become buffer[0]. + assert(lz->read_pos > lz->keep_size_after); + size_t move_offset = lz->read_pos - lz->keep_size_before; + + // We need one additional byte, since move_pos() moves on 1 byte. + // TODO: Clean up? At least document more. + if (move_offset > 0) + --move_offset; + + assert(lz->write_pos > move_offset); + const size_t move_size = lz->write_pos - move_offset; + + assert(move_offset + move_size <= lz->size); + + memmove(lz->buffer, lz->buffer + move_offset, move_size); + + lz->offset += move_offset; + lz->read_pos -= move_offset; + lz->read_limit -= move_offset; + lz->write_pos -= move_offset; + + return; +} + + +/// \brief Tries to fill the input window (lz->buffer) +/// +/// If we are the last encoder in the chain, our input data is in in[]. +/// Otherwise we call the next filter in the chain to process in[] and +/// write its output to lz->buffer. +/// +/// This function must not be called once it has returned LZMA_STREAM_END. +/// +static lzma_ret +fill_window(lzma_coder *coder, lzma_allocator *allocator, const uint8_t *in, + size_t *in_pos, size_t in_size, lzma_action action) +{ + assert(coder->lz.read_pos <= coder->lz.write_pos); + lzma_ret ret; + + // Move the sliding window if needed. + if (coder->lz.read_pos >= coder->lz.must_move_pos) + move_window(&coder->lz); + + if (coder->next.code == NULL) { + // Not using a filter, simply memcpy() as much as possible. + bufcpy(in, in_pos, in_size, coder->lz.buffer, + &coder->lz.write_pos, coder->lz.size); + + if (action == LZMA_FINISH && *in_pos == in_size) + ret = LZMA_STREAM_END; + else + ret = LZMA_OK; + + } else { + ret = coder->next.code(coder->next.coder, allocator, + in, in_pos, in_size, + coder->lz.buffer, &coder->lz.write_pos, + coder->lz.size, action); + } + + // If end of stream has been reached, we allow the encoder to process + // all the input (that is, read_pos is allowed to reach write_pos). + // Otherwise we keep keep_size_after bytes available as prebuffer. + if (ret == LZMA_STREAM_END) { + coder->lz.stream_end_was_reached = true; + coder->lz.read_limit = coder->lz.write_pos; + + } else if (coder->lz.write_pos > coder->lz.keep_size_after) { + // This needs to be done conditionally, because if we got + // only little new input, there may be too little input + // to do any encoding yet. + coder->lz.read_limit = coder->lz.write_pos + - coder->lz.keep_size_after; + } + + return ret; +} + + +extern lzma_ret +lzma_lz_encode(lzma_coder *coder, lzma_allocator *allocator, + const uint8_t *restrict in, size_t *restrict in_pos, + size_t in_size, + uint8_t *restrict out, size_t *restrict out_pos, + size_t out_size, lzma_action action) +{ + while (*out_pos < out_size + && (*in_pos < in_size || action == LZMA_FINISH)) { + // Fill the input window if there is no more usable data. + if (!coder->lz.stream_end_was_reached && coder->lz.read_pos + >= coder->lz.read_limit) { + const lzma_ret ret = fill_window(coder, allocator, + in, in_pos, in_size, action); + if (ret != LZMA_OK && ret != LZMA_STREAM_END) + return ret; + } + + // Encode + if (coder->lz.process(coder, out, out_pos, out_size)) + return LZMA_STREAM_END; + } + + return LZMA_OK; +} + + +/// \brief Normalizes hash values +/// +/// lzma_lz_normalize is called when lz->pos hits MAX_VAL_FOR_NORMALIZE, +/// which currently happens once every 2 GiB of input data (to be exact, +/// after the first 2 GiB it happens once every 2 GiB minus dictionary_size +/// bytes). lz->pos is incremented by lzma_lz_move_pos(). +/// +/// lz->hash contains big amount of offsets relative to lz->buffer. +/// The offsets are stored as uint32_t, which is the only reasonable +/// datatype for these offsets; uint64_t would waste far too much RAM +/// and uint16_t would limit the dictionary to 64 KiB (far too small). +/// +/// When compressing files over 2 GiB, lz->buffer needs to be moved forward +/// to avoid integer overflows. We scan the lz->hash array and fix every +/// value to match the updated lz->buffer. +extern void +lzma_lz_encoder_normalize(lzma_lz_encoder *lz) +{ + const uint32_t subvalue = lz->read_pos - lz->cyclic_buffer_size; + assert(subvalue <= INT32_MAX); + + { + const uint32_t num_items = lz->num_items; + uint32_t *restrict items = lz->hash; + + for (uint32_t i = 0; i < num_items; ++i) { + // If the distance is greater than the dictionary + // size, we can simply mark the item as empty. + if (items[i] <= subvalue) + items[i] = EMPTY_HASH_VALUE; + else + items[i] -= subvalue; + } + } + + // Update offset to match the new locations. + lz->offset -= subvalue; + + return; +} diff --git a/src/liblzma/lz/lz_encoder.h b/src/liblzma/lz/lz_encoder.h new file mode 100644 index 00000000..b39c88e5 --- /dev/null +++ b/src/liblzma/lz/lz_encoder.h @@ -0,0 +1,161 @@ +/////////////////////////////////////////////////////////////////////////////// +// +/// \file lz_encoder.h +/// \brief LZ in window and match finder 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_LZ_ENCODER_H +#define LZMA_LZ_ENCODER_H + +#include "common.h" + + +typedef struct lzma_lz_encoder_s lzma_lz_encoder; +struct lzma_lz_encoder_s { + enum { + SEQ_INIT, + SEQ_RUN, + SEQ_FINISH, + SEQ_END + } sequence; + + bool (*process)(lzma_coder *coder, uint8_t *restrict out, + size_t *restrict out_pos, size_t out_size); + + lzma_vli uncompressed_size; + + /////////////// + // In Window // + /////////////// + + /// Pointer to buffer with data to be compressed + uint8_t *buffer; + + /// Total size of the allocated buffer (that is, including all + /// the extra space) + size_t size; + + /// Match finders store locations of matches using 32-bit integers. + /// To avoid adjusting several megabytes of integers every time the + /// input window is moved with move_window(), we only adjust the + /// offset of the buffer. Thus, buffer[match_finder_pos - offset] + /// is the byte pointed by match_finder_pos. + size_t offset; + + /// buffer[read_pos] is the current byte. + size_t read_pos; + + /// As long as read_pos is less than read_limit, there is enough + /// input available in buffer for at least one encoding loop. + /// + /// Because of the stateful API, read_limit may and will get greater + /// than read_pos quite often. This is taken into account when + /// calculating the value for keep_size_after. + size_t read_limit; + + /// buffer[write_pos] is the first byte that doesn't contain valid + /// uncompressed data; that is, the next input byte will be copied + /// to buffer[write_pos]. + size_t write_pos; + + /// When read_pos >= must_move_pos, move_window() must be called + /// to make more space for the input data. + size_t must_move_pos; + + /// Number of bytes that must be kept available in our input history. + /// That is, once keep_size_before bytes have been processed, + /// buffer[read_pos - keep_size_before] is the oldest byte that + /// must be available for reading. + size_t keep_size_before; + + /// Number of bytes that must be kept in buffer after read_pos. + /// That is, read_pos <= write_pos - keep_size_after as long as + /// stream_end_was_reached is false (once it is true, read_pos + /// is allowed to reach write_pos). + size_t keep_size_after; + + /// This is set to true once the last byte of the input data has + /// been copied to buffer. + bool stream_end_was_reached; + + ////////////////// + // Match Finder // + ////////////////// + + // Pointers to match finder functions + void (*get_matches)(lzma_lz_encoder *restrict lz, + uint32_t *restrict distances); + void (*skip)(lzma_lz_encoder *restrict lz, uint32_t num); + + // Match finder data + uint32_t *hash; // TODO: Check if hash aliases son + uint32_t *son; // and add 'restrict' if possible. + uint32_t cyclic_buffer_pos; + uint32_t cyclic_buffer_size; // Must be dictionary_size + 1. + uint32_t hash_mask; + uint32_t cut_value; + uint32_t hash_size_sum; + uint32_t num_items; + uint32_t match_max_len; +}; + + +#define LZMA_LZ_ENCODER_INIT \ + (lzma_lz_encoder){ \ + .buffer = NULL, \ + .size = 0, \ + .hash = NULL, \ + .num_items = 0, \ + } + + +/// Calculates +extern uint32_t lzma_lz_encoder_hash_properties(lzma_match_finder match_finder, + uint32_t history_size, uint32_t *restrict hash_mask, + uint32_t *restrict hash_size_sum, + uint32_t *restrict num_items); + +// NOTE: liblzma doesn't use callback API like LZMA SDK does. The caller +// must make sure that keep_size_after is big enough for single encoding pass +// i.e. keep_size_after >= maximum number of bytes possibly needed after +// the current position between calls to lzma_lz_read(). +extern lzma_ret lzma_lz_encoder_reset(lzma_lz_encoder *lz, + lzma_allocator *allocator, + bool (*process)(lzma_coder *coder, uint8_t *restrict out, + size_t *restrict out_pos, size_t out_size), + lzma_vli uncompressed_size, + size_t history_size, size_t additional_buffer_before, + size_t match_max_len, size_t additional_buffer_after, + lzma_match_finder match_finder, uint32_t match_finder_cycles, + const uint8_t *preset_dictionary, + size_t preset_dictionary_size); + +/// Frees memory allocated for in window and match finder buffers. +extern void lzma_lz_encoder_end( + lzma_lz_encoder *lz, lzma_allocator *allocator); + +extern lzma_ret lzma_lz_encode(lzma_coder *coder, + lzma_allocator *allocator lzma_attribute((unused)), + const uint8_t *restrict in, size_t *restrict in_pos, + size_t in_size, uint8_t *restrict out, + size_t *restrict out_pos, size_t out_size, + lzma_action action); + +/// This should not be called directly, but only via move_pos() macro. +extern void lzma_lz_encoder_normalize(lzma_lz_encoder *lz); + +#endif diff --git a/src/liblzma/lz/lz_encoder_private.h b/src/liblzma/lz/lz_encoder_private.h new file mode 100644 index 00000000..638fcb2d --- /dev/null +++ b/src/liblzma/lz/lz_encoder_private.h @@ -0,0 +1,40 @@ +/////////////////////////////////////////////////////////////////////////////// +// +/// \file lz_encoder_private.h +/// \brief Private definitions for LZ 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_LZ_ENCODER_PRIVATE_H +#define LZMA_LZ_ENCODER_PRIVATE_H + +#include "lz_encoder.h" + +/// Value used to indicate unused slot +#define EMPTY_HASH_VALUE 0 + +/// When the dictionary and hash variables need to be adjusted to prevent +/// integer overflows. Since we use uint32_t to store the offsets, half +/// of it is the biggest safe limit. +#define MAX_VAL_FOR_NORMALIZE (UINT32_MAX / 2) + + +struct lzma_coder_s { + lzma_next_coder next; + lzma_lz_encoder lz; +}; + +#endif diff --git a/src/liblzma/lz/match_c.h b/src/liblzma/lz/match_c.h new file mode 100644 index 00000000..68766385 --- /dev/null +++ b/src/liblzma/lz/match_c.h @@ -0,0 +1,401 @@ +/////////////////////////////////////////////////////////////////////////////// +// +/// \file match_c.h +/// \brief Template for different match finders +/// +/// This file is included by hc3.c, hc4, bt2.c, bt3.c and bt4.c. Each file +/// sets slighly different #defines, resulting the different match finders. +// +// 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. +// +/////////////////////////////////////////////////////////////////////////////// + +////////////// +// Includes // +////////////// + +#include "check.h" + + +/////////////// +// Constants // +/////////////// + +#define START_MAX_LEN 1 + +#ifdef HASH_ARRAY_2 +# define NUM_HASH_DIRECT_BYTES 0 +# define HASH_2_SIZE (1 << 10) +# ifdef HASH_ARRAY_3 +# define NUM_HASH_BYTES 4 +# define HASH_3_SIZE (1 << 16) +# define HASH_3_OFFSET HASH_2_SIZE +# define FIX_HASH_SIZE (HASH_2_SIZE + HASH_3_SIZE) +# else +# define NUM_HASH_BYTES 3 +# define FIX_HASH_SIZE HASH_2_SIZE +# endif +# define HASH_SIZE 0 +# define MIN_MATCH_CHECK NUM_HASH_BYTES +#else +# define NUM_HASH_DIRECT_BYTES 2 +# define NUM_HASH_BYTES 2 +# define HASH_SIZE (1 << (8 * NUM_HASH_BYTES)) +# define MIN_MATCH_CHECK (NUM_HASH_BYTES + 1) +# define FIX_HASH_SIZE 0 +#endif + + +//////////// +// Macros // +//////////// + +#ifdef HASH_ARRAY_2 +# ifdef HASH_ARRAY_3 +# define HASH_CALC() \ + do { \ + const uint32_t temp = lzma_crc32_table[0][ \ + cur[0]] ^ cur[1]; \ + hash_2_value = temp & (HASH_2_SIZE - 1); \ + hash_3_value = (temp ^ ((uint32_t)(cur[2]) << 8)) \ + & (HASH_3_SIZE - 1); \ + hash_value = (temp ^ ((uint32_t)(cur[2]) << 8) \ + ^ (lzma_crc32_table[0][cur[3]] << 5)) \ + & lz->hash_mask; \ + } while (0) +# else +# define HASH_CALC() \ + do { \ + const uint32_t temp = lzma_crc32_table[0][ \ + cur[0]] ^ cur[1]; \ + hash_2_value = temp & (HASH_2_SIZE - 1); \ + hash_value = (temp ^ ((uint32_t)(cur[2]) << 8)) \ + & lz->hash_mask; \ + } while (0) +# endif +#else +# define HASH_CALC() hash_value = cur[0] ^ ((uint32_t)(cur[1]) << 8) +#endif + + +// Moves the current read position forward by one byte. In LZMA SDK, +// CLZInWindow::MovePos() can read more input data if needed, because of +// the callback style API. In liblzma we must have ensured earlier, that +// there is enough data available in lz->buffer. +#define move_pos() \ +do { \ + if (++lz->cyclic_buffer_pos == lz->cyclic_buffer_size) \ + lz->cyclic_buffer_pos = 0; \ + ++lz->read_pos; \ + assert(lz->read_pos <= lz->write_pos); \ + if (lz->read_pos == MAX_VAL_FOR_NORMALIZE) \ + lzma_lz_encoder_normalize(lz); \ +} while (0) + + +////////////////////// +// Global constants // +////////////////////// + +LZMA_HASH_SIZE(LZMA_MATCH_FINDER_NAME_UPPER) = HASH_SIZE; +LZMA_FIX_HASH_SIZE(LZMA_MATCH_FINDER_NAME_UPPER) = FIX_HASH_SIZE; + + +/////////////////// +// API functions // +/////////////////// + +LZMA_GET_MATCHES(LZMA_MATCH_FINDER_NAME_LOWER) +{ + uint32_t len_limit; + if (lz->read_pos + lz->match_max_len <= lz->write_pos) { + len_limit = lz->match_max_len; + } else { + assert(lz->stream_end_was_reached); + len_limit = lz->write_pos - lz->read_pos; + if (len_limit < MIN_MATCH_CHECK) { + distances[0] = 0; + move_pos(); + return; + } + } + + int32_t offset = 1; + const uint32_t match_min_pos + = lz->read_pos + lz->offset > lz->cyclic_buffer_size + ? lz->read_pos + lz->offset - lz->cyclic_buffer_size + : 0; + const uint8_t *cur = lz->buffer + lz->read_pos; + uint32_t max_len = START_MAX_LEN; // to avoid items for len < hash_size + +#ifdef HASH_ARRAY_2 + uint32_t hash_2_value; +# ifdef HASH_ARRAY_3 + uint32_t hash_3_value; +# endif +#endif + uint32_t hash_value; + HASH_CALC(); + + uint32_t cur_match = lz->hash[FIX_HASH_SIZE + hash_value]; +#ifdef HASH_ARRAY_2 + uint32_t cur_match2 = lz->hash[hash_2_value]; +# ifdef HASH_ARRAY_3 + uint32_t cur_match3 = lz->hash[HASH_3_OFFSET + hash_3_value]; +# endif + lz->hash[hash_2_value] = lz->read_pos + lz->offset; + + if (cur_match2 > match_min_pos) { + if (lz->buffer[cur_match2 - lz->offset] == cur[0]) { + max_len = 2; + distances[offset++] = 2; + distances[offset++] = lz->read_pos + lz->offset + - cur_match2 - 1; + } + } + +# ifdef HASH_ARRAY_3 + lz->hash[HASH_3_OFFSET + hash_3_value] = lz->read_pos + lz->offset; + if (cur_match3 > match_min_pos) { + if (lz->buffer[cur_match3 - lz->offset] == cur[0]) { + if (cur_match3 == cur_match2) + offset -= 2; + + max_len = 3; + distances[offset++] = 3; + distances[offset++] = lz->read_pos + lz->offset + - cur_match3 - 1; + cur_match2 = cur_match3; + } + } +# endif + + if (offset != 1 && cur_match2 == cur_match) { + offset -= 2; + max_len = START_MAX_LEN; + } +#endif + + lz->hash[FIX_HASH_SIZE + hash_value] = lz->read_pos + lz->offset; + +#ifdef IS_HASH_CHAIN + lz->son[lz->cyclic_buffer_pos] = cur_match; +#else + uint32_t *ptr0 = lz->son + (lz->cyclic_buffer_pos << 1) + 1; + uint32_t *ptr1 = lz->son + (lz->cyclic_buffer_pos << 1); + + uint32_t len0 = NUM_HASH_DIRECT_BYTES; + uint32_t len1 = NUM_HASH_DIRECT_BYTES; +#endif + +#if NUM_HASH_DIRECT_BYTES != 0 + if (cur_match > match_min_pos) { + if (lz->buffer[cur_match + NUM_HASH_DIRECT_BYTES - lz->offset] + != cur[NUM_HASH_DIRECT_BYTES]) { + max_len = NUM_HASH_DIRECT_BYTES; + distances[offset++] = NUM_HASH_DIRECT_BYTES; + distances[offset++] = lz->read_pos + lz->offset + - cur_match - 1; + } + } +#endif + + uint32_t count = lz->cut_value; + + while (true) { + if (cur_match <= match_min_pos || count-- == 0) { +#ifndef IS_HASH_CHAIN + *ptr0 = EMPTY_HASH_VALUE; + *ptr1 = EMPTY_HASH_VALUE; +#endif + break; + } + + const uint32_t delta = lz->read_pos + lz->offset - cur_match; + const uint32_t cyclic_pos = delta <= lz->cyclic_buffer_pos + ? lz->cyclic_buffer_pos - delta + : lz->cyclic_buffer_pos - delta + + lz->cyclic_buffer_size; + uint32_t *pair = lz->son + +#ifdef IS_HASH_CHAIN + cyclic_pos; +#else + (cyclic_pos << 1); +#endif + + const uint8_t *pb = lz->buffer + cur_match - lz->offset; + uint32_t len = +#ifdef IS_HASH_CHAIN + NUM_HASH_DIRECT_BYTES; + if (pb[max_len] == cur[max_len]) +#else + MIN(len0, len1); +#endif + + if (pb[len] == cur[len]) { + while (++len != len_limit) + if (pb[len] != cur[len]) + break; + + if (max_len < len) { + max_len = len; + distances[offset++] = len; + distances[offset++] = delta - 1; + if (len == len_limit) { +#ifndef IS_HASH_CHAIN + *ptr1 = pair[0]; + *ptr0 = pair[1]; +#endif + break; + } + } + } + +#ifdef IS_HASH_CHAIN + cur_match = *pair; +#else + if (pb[len] < cur[len]) { + *ptr1 = cur_match; + ptr1 = pair + 1; + cur_match = *ptr1; + len1 = len; + } else { + *ptr0 = cur_match; + ptr0 = pair; + cur_match = *ptr0; + len0 = len; + } +#endif + } + + distances[0] = offset - 1; + + move_pos(); + + return; +} + + +LZMA_SKIP(LZMA_MATCH_FINDER_NAME_LOWER) +{ + do { +#ifdef IS_HASH_CHAIN + if (lz->write_pos - lz->read_pos < NUM_HASH_BYTES) { + move_pos(); + continue; + } +#else + uint32_t len_limit; + if (lz->read_pos + lz->match_max_len <= lz->write_pos) { + len_limit = lz->match_max_len; + } else { + assert(lz->stream_end_was_reached == true); + len_limit = lz->write_pos - lz->read_pos; + if (len_limit < MIN_MATCH_CHECK) { + move_pos(); + continue; + } + } + const uint32_t match_min_pos + = lz->read_pos + lz->offset > lz->cyclic_buffer_size + ? lz->read_pos + lz->offset - lz->cyclic_buffer_size + : 0; +#endif + + const uint8_t *cur = lz->buffer + lz->read_pos; + +#ifdef HASH_ARRAY_2 + uint32_t hash_2_value; +# ifdef HASH_ARRAY_3 + uint32_t hash_3_value; + uint32_t hash_value; + HASH_CALC(); + lz->hash[HASH_3_OFFSET + hash_3_value] + = lz->read_pos + lz->offset; +# else + uint32_t hash_value; + HASH_CALC(); +# endif + lz->hash[hash_2_value] = lz->read_pos + lz->offset; +#else + uint32_t hash_value; + HASH_CALC(); +#endif + + uint32_t cur_match = lz->hash[FIX_HASH_SIZE + hash_value]; + lz->hash[FIX_HASH_SIZE + hash_value] + = lz->read_pos + lz->offset; + +#ifdef IS_HASH_CHAIN + lz->son[lz->cyclic_buffer_pos] = cur_match; +#else + uint32_t *ptr0 = lz->son + (lz->cyclic_buffer_pos << 1) + 1; + uint32_t *ptr1 = lz->son + (lz->cyclic_buffer_pos << 1); + + uint32_t len0 = NUM_HASH_DIRECT_BYTES; + uint32_t len1 = NUM_HASH_DIRECT_BYTES; + uint32_t count = lz->cut_value; + + while (true) { + if (cur_match <= match_min_pos || count-- == 0) { + *ptr0 = EMPTY_HASH_VALUE; + *ptr1 = EMPTY_HASH_VALUE; + break; + } + + const uint32_t delta = lz->read_pos + + lz->offset - cur_match; + const uint32_t cyclic_pos + = delta <= lz->cyclic_buffer_pos + ? lz->cyclic_buffer_pos - delta + : lz->cyclic_buffer_pos - delta + + lz->cyclic_buffer_size; + uint32_t *pair = lz->son + (cyclic_pos << 1); + + const uint8_t *pb = lz->buffer + cur_match + - lz->offset; + uint32_t len = MIN(len0, len1); + + if (pb[len] == cur[len]) { + while (++len != len_limit) + if (pb[len] != cur[len]) + break; + + if (len == len_limit) { + *ptr1 = pair[0]; + *ptr0 = pair[1]; + break; + } + } + + if (pb[len] < cur[len]) { + *ptr1 = cur_match; + ptr1 = pair + 1; + cur_match = *ptr1; + len1 = len; + } else { + *ptr0 = cur_match; + ptr0 = pair; + cur_match = *ptr0; + len0 = len; + } + } +#endif + + move_pos(); + + } while (--num != 0); + + return; +} diff --git a/src/liblzma/lz/match_h.h b/src/liblzma/lz/match_h.h new file mode 100644 index 00000000..2eae90ba --- /dev/null +++ b/src/liblzma/lz/match_h.h @@ -0,0 +1,69 @@ +/////////////////////////////////////////////////////////////////////////////// +// +/// \file match_h.h +/// \brief Header template for different match finders +// +// 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 "lz_encoder_private.h" + + +////////////////////// +// Global constants // +////////////////////// + +#undef LZMA_HASH_SIZE +#undef LZMA_FIX_HASH_SIZE +#undef LZMA_HASH_SIZE_C +#undef LZMA_FIX_HASH_SIZE_C + +#define LZMA_HASH_SIZE(mf_name) LZMA_HASH_SIZE_C(mf_name) +#define LZMA_FIX_HASH_SIZE(mf_name) LZMA_FIX_HASH_SIZE_C(mf_name) + +#define LZMA_HASH_SIZE_C(mf_name) \ + const uint32_t LZMA_ ## mf_name ## _HASH_SIZE + +#define LZMA_FIX_HASH_SIZE_C(mf_name) \ + const uint32_t LZMA_ ## mf_name ## _FIX_HASH_SIZE + +extern LZMA_HASH_SIZE(LZMA_MATCH_FINDER_NAME_UPPER); +extern LZMA_FIX_HASH_SIZE(LZMA_MATCH_FINDER_NAME_UPPER); + + +/////////////// +// Functions // +/////////////// + +#undef LZMA_GET_MATCHES +#undef LZMA_SKIP +#undef LZMA_GET_MATCHES_C +#undef LZMA_SKIP_C + +#define LZMA_GET_MATCHES(mf_name) LZMA_GET_MATCHES_C(mf_name) +#define LZMA_SKIP(mf_name) LZMA_SKIP_C(mf_name) + +#define LZMA_GET_MATCHES_C(mf_name) \ + extern void lzma_ ## mf_name ## _get_matches( \ + lzma_lz_encoder *restrict lz, \ + uint32_t *restrict distances) + +#define LZMA_SKIP_C(mf_name) \ + extern void lzma_ ## mf_name ## _skip( \ + lzma_lz_encoder *lz, uint32_t num) + +LZMA_GET_MATCHES(LZMA_MATCH_FINDER_NAME_LOWER); + +LZMA_SKIP(LZMA_MATCH_FINDER_NAME_LOWER); diff --git a/src/liblzma/lzma.pc.in b/src/liblzma/lzma.pc.in new file mode 100644 index 00000000..5bf9bb10 --- /dev/null +++ b/src/liblzma/lzma.pc.in @@ -0,0 +1,11 @@ +prefix=@prefix@ +exec_prefix=@exec_prefix@ +libdir=@libdir@ +includedir=@includedir@ + +Name: liblzma +Description: LZMA compression library +URL: http://tukaani.org/lzma/ +Version: @PACKAGE_VERSION@ +Cflags: -I${includedir} +Libs: -L${libdir} -llzma 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 |