/* xz_dec_lzma2.c - LZMA2 decoder */
/*
* GRUB -- GRand Unified Bootloader
* Copyright (C) 2010 Free Software Foundation, Inc.
*
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* GRUB 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 General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with GRUB. If not, see <http://www.gnu.org/licenses/>.
*/
/*
* This file is based on code from XZ embedded project
*/
#include "xz_private.h"
#include "xz_lzma2.h"
/*
* Range decoder initialization eats the first five bytes of each LZMA chunk.
*/
/*
* Minimum number of usable input buffer to safely decode one LZMA symbol.
* The worst case is that we decode 22 bits using probabilities and 26
* direct bits. This may decode at maximum of 20 bytes of input. However,
* lzma_main() does an extra normalization before returning, thus we
* need to put 21 here.
*/
/*
* Dictionary (history buffer)
*
* These are always true:
* start <= pos <= full <= end
* pos <= limit <= end
*
* In multi-call mode, also these are true:
* end == size
* size <= allocated
*
* Most of these variables are size_t to support single-call mode,
* in which the dictionary variables address the actual output
* buffer directly.
*/
struct dictionary {
/* Beginning of the history buffer */
/* Old position in buf (before decoding more data) */
/* Position in buf */
/*
* How full dictionary is. This is used to detect corrupt input that
* would read beyond the beginning of the uncompressed stream.
*/
/* Write limit; we don't write to buf[limit] or later bytes. */
/*
* End of the dictionary buffer. In multi-call mode, this is
* the same as the dictionary size. In single-call mode, this
* indicates the size of the output buffer.
*/
/*
* Size of the dictionary as specified in Block Header. This is used
* together with "full" to detect corrupt input that would make us
* read beyond the beginning of the uncompressed stream.
*/
/*
* Amount of memory allocated for the dictionary. A special
* value of zero indicates that we are in single-call mode,
* where the output buffer works as the dictionary.
*/
};
/* Range decoder */
struct rc_dec {
/*
* Number of initializing bytes remaining to be read
* by rc_read_init().
*/
/*
* Buffer from which we read our input. It can be either
* temp.buf or the caller-provided input buffer.
*/
};
/* Probabilities for a length decoder. */
struct lzma_len_dec {
/* Probability of match length being at least 10 */
/* Probability of match length being at least 18 */
/* Probabilities for match lengths 2-9 */
/* Probabilities for match lengths 10-17 */
/* Probabilities for match lengths 18-273 */
};
struct lzma_dec {
/*
* LZMA properties or related bit masks (number of literal
* context bits, a mask dervied from the number of literal
* position bits, and a mask dervied from the number
* position bits)
*/
/* Types of the most recently seen LZMA symbols */
/* Distances of latest four matches */
/*
* Length of a match. This is updated so that dict_repeat can
* be called again to finish repeating the whole match.
*/
/* If 1, it's a match. Otherwise it's a single 8-bit literal. */
/* If 1, it's a repeated match. The distance is one of rep0 .. rep3. */
/*
* If 0, distance of a repeated match is rep0.
* Otherwise check is_rep1.
*/
/*
* If 0, distance of a repeated match is rep1.
* Otherwise check is_rep2.
*/
/* If 0, distance of a repeated match is rep2. Otherwise it is rep3. */
/*
* If 1, the repeated match has length of one byte. Otherwise
* the length is decoded from rep_len_decoder.
*/
/*
* Probability tree for the highest two bits of the match
* distance. There is a separate probability tree for match
* lengths of 2 (i.e. MATCH_LEN_MIN), 3, 4, and [5, 273].
*/
/*
* Probility trees for additional bits for match distance
* when the distance is in the range [4, 127].
*/
/*
* Probability tree for the lowest four bits of a match
* distance that is equal to or greater than 128.
*/
/* Length of a normal match */
/* Length of a repeated match */
/* Probabilities of literals */
};
struct xz_dec_lzma2 {
/* LZMA2 */
struct {
/* Position in xz_dec_lzma2_run(). */
enum lzma2_seq {
} sequence;
/*
* Next position after decoding the compressed size of
* the chunk.
*/
/* Uncompressed size of LZMA chunk (2 MiB at maximum) */
/*
* Compressed size of LZMA chunk or compressed/uncompressed
* size of uncompressed chunk (64 KiB at maximum)
*/
/*
* True if dictionary reset is needed. This is false before
* the first chunk (LZMA or uncompressed).
*/
bool need_dict_reset;
/*
* True if new LZMA properties are needed. This is false
* before the first LZMA chunk.
*/
bool need_props;
} lzma2;
/*
* Temporary buffer which holds small number of input bytes between
* decoder calls. See lzma2_lzma() for details.
*/
struct {
} temp;
};
/**************
* Dictionary *
**************/
/*
* Reset the dictionary state. When in single-call mode, set up the beginning
* of the dictionary to point to the actual output buffer.
*/
{
}
}
/* Set dictionary write limit */
{
else
}
/* Return true if at least one byte can be written into the dictionary. */
{
}
/*
* Get a byte from the dictionary at the given distance. The distance is
* assumed to valid, or as a special case, zero when the dictionary is
* still empty. This special case is needed for single-call decoding to
* avoid writing a '\0' to the end of the destination buffer.
*/
{
}
/*
* Put one byte into the dictionary. It is assumed that there is space for it.
*/
{
}
/*
* Repeat given number of bytes from the given distance. If the distance is
* invalid, false is returned. On success, true is returned and *len is
* updated to indicate how many bytes were left to be repeated.
*/
static bool dict_repeat(
{
return false;
do {
back = 0;
} while (--left > 0);
return true;
}
/* Copy uncompressed data as is from input to dictionary and output buffers. */
static void dict_uncompressed(
{
}
}
}
/*
* Flush pending data from dictionary to b->out. It is assumed that there is
* enough space in b->out. This is guaranteed because caller uses dict_limit()
* before decoding data into the dictionary.
*/
{
}
return copy_size;
}
/*****************
* Range decoder *
*****************/
/* Reset the range decoder. */
{
}
/*
* Read the first five initial bytes into rc->code if they haven't been
* read already. (Yes, the first byte gets completely ignored.)
*/
{
while (rc->init_bytes_left > 0) {
return false;
--rc->init_bytes_left;
}
return true;
}
/* Return true if there may not be enough input for the next decoding loop. */
{
}
/*
* Return true if it is possible (from point of view of range decoder) that
* we have reached the end of the LZMA chunk.
*/
{
}
/* Read the next input byte if needed. */
{
}
}
/*
* Decode one bit. In some versions, this function has been splitted in three
* functions so that the compiler is supposed to be able to more easily avoid
* an extra branch. In this particular version of the LZMA decoder, this
* doesn't seem to be a good idea (tested with GCC 3.3.6, 3.4.6, and 4.3.3
* on x86). Using a non-splitted version results in nicer looking code too.
*
* NOTE: This must return an int. Do not make it return a bool or the speed
* of the code generated by GCC 3.x decreases 10-15 %. (GCC 4.3 doesn't care,
* and it generates 10-20 % faster code than GCC 3.x from this file anyway.)
*/
{
int bit;
bit = 0;
} else {
bit = 1;
}
return bit;
}
/* Decode a bittree starting from the most significant bit. */
{
do {
else
symbol <<= 1;
return symbol;
}
/* Decode a bittree starting from the least significant bit. */
{
uint32_t i = 0;
do {
*dest += 1 << i;
} else {
symbol <<= 1;
}
} while (++i < limit);
}
/* Decode direct bits (fixed fifty-fifty probability) */
static inline void rc_direct(
{
do {
} while (--limit > 0);
}
/********
* LZMA *
********/
/* Get pointer to literal coder probability array. */
{
}
/* Decode a literal (one 8-bit byte) */
{
uint32_t i;
probs = lzma_literal_probs(s);
} else {
symbol = 1;
offset = 0x100;
do {
match_byte <<= 1;
} else {
symbol <<= 1;
}
} while (symbol < 0x100);
}
}
/* Decode the length of the match into s->lzma.len. */
{
} else {
} else {
}
}
}
/* Decode a match. The distance will be stored in s->lzma.rep0. */
{
if (dist_slot < DIST_MODEL_START) {
} else {
if (dist_slot < DIST_MODEL_END) {
- dist_slot - 1;
} else {
}
}
}
/*
* Decode a repeated match. The distance is one of the four most recently
* seen matches. The distance will be stored in s->lzma.rep0.
*/
{
return;
}
} else {
} else {
} else {
}
}
}
}
/* LZMA decoder core */
{
/*
* If the dictionary was reached during the previous call, try to
* finish the possibly pending repeat in the dictionary.
*/
/*
* Decode more LZMA symbols. One iteration may consume up to
* LZMA_IN_REQUIRED - 1 bytes.
*/
lzma_literal(s);
} else {
lzma_rep_match(s, pos_state);
else
lzma_match(s, pos_state);
return false;
}
}
/*
* Having the range decoder always normalized when we are outside
* this function makes it easier to correctly handle end of the chunk.
*/
rc_normalize(&s->rc);
return true;
}
/*
* Reset the LZMA decoder and range decoder state. Dictionary is nore reset
* here, because LZMA state may be reset without resetting the dictionary.
*/
{
size_t i;
/*
* All probabilities are initialized to the same value. This hack
* makes the code smaller by avoiding a separate loop for each
* probability array.
*
* This could be optimized so that only that part of literal
* probabilities that are actually required. In the common case
* we would write 12 KiB less.
*/
for (i = 0; i < PROBS_TOTAL; ++i)
}
/*
* from the decoded lp and pb values. On success, the LZMA decoder state is
* reset and true is returned.
*/
{
return false;
}
s->lzma.literal_pos_mask = 0;
while (props >= 9) {
props -= 9;
++s->lzma.literal_pos_mask;
}
return false;
lzma_reset(s);
return true;
}
/*********
* LZMA2 *
*********/
/*
* The LZMA decoder assumes that if the input limit (s->rc.in_limit) hasn't
* been exceeded, it is safe to read up to LZMA_IN_REQUIRED bytes. This
* wrapper function takes care of making the LZMA decoder's assumption safe.
*
* As long as there is plenty of input left to be decoded in the current LZMA
* chunk, we decode directly from the caller-supplied input buffer until
* there's LZMA_IN_REQUIRED bytes left. Those remaining bytes are copied into
* s->temp.buf, which (hopefully) gets filled on the next call to this
* function. We decode a few bytes from the temporary buffer so that we can
* continue decoding from the caller-supplied input buffer again.
*/
{
return true;
} else {
}
return false;
return true;
}
}
if (in_avail >= LZMA_IN_REQUIRED) {
else
if (!lzma_main(s))
return false;
return false;
}
if (in_avail < LZMA_IN_REQUIRED) {
}
return true;
}
/*
* Take care of the LZMA2 control layer, and forward the job of actual LZMA
* decoding or copying of uncompressed chunks to other functions.
*/
struct xz_dec_lzma2 *s, struct xz_buf *b)
{
case SEQ_CONTROL:
/*
* LZMA2 control byte
*
* Exact values:
* 0x00 End marker
* 0x01 Dictionary reset followed by
* an uncompressed chunk
* 0x02 Uncompressed chunk (no dictionary reset)
*
* Highest three bits (s->control & 0xE0):
* 0xE0 Dictionary reset, new properties and state
* reset, followed by LZMA compressed chunk
* 0xC0 New properties and state reset, followed
* by LZMA compressed chunk (no dictionary
* reset)
* 0xA0 State reset using old properties,
* followed by LZMA compressed chunk (no
* dictionary reset)
* 0x80 LZMA chunk (no dictionary or state reset)
*
* For LZMA compressed chunks, the lowest five bits
* (s->control & 1F) are the highest bits of the
* uncompressed size (bits 16-20).
*
* A new LZMA2 stream must begin with a dictionary
* reset. The first LZMA chunk must set new
* properties and reset the LZMA state.
*
* Values that don't match anything described above
* are invalid and we return XZ_DATA_ERROR.
*/
s->lzma2.need_props = true;
s->lzma2.need_dict_reset = false;
dict_reset(&s->dict, b);
} else if (s->lzma2.need_dict_reset) {
return XZ_DATA_ERROR;
}
if (tmp >= 0x80) {
if (tmp >= 0xC0) {
/*
* When there are new properties,
* state reset is done at
* SEQ_PROPERTIES.
*/
s->lzma2.need_props = false;
} else if (s->lzma2.need_props) {
return XZ_DATA_ERROR;
} else {
if (tmp >= 0xA0)
lzma_reset(s);
}
} else {
if (tmp == 0x00)
return XZ_STREAM_END;
if (tmp > 0x02)
return XZ_DATA_ERROR;
}
break;
case SEQ_UNCOMPRESSED_1:
break;
case SEQ_UNCOMPRESSED_2:
break;
case SEQ_COMPRESSED_0:
s->lzma2.compressed
break;
case SEQ_COMPRESSED_1:
s->lzma2.compressed
break;
case SEQ_PROPERTIES:
return XZ_DATA_ERROR;
case SEQ_LZMA_PREPARE:
return XZ_DATA_ERROR;
if (!rc_read_init(&s->rc, b))
return XZ_OK;
case SEQ_LZMA_RUN:
/*
* Set dictionary limit to indicate how much we want
* to be encoded at maximum. Decode new data into the
* dictionary. Flush the new data from dictionary to
* b->out. Check if we finished decoding this chunk.
* In case the dictionary got full but we didn't fill
* the output buffer yet, we may run this loop
* multiple times without changing s->lzma2.sequence.
*/
s->lzma2.uncompressed));
if (!lzma2_lzma(s, b))
return XZ_DATA_ERROR;
if (s->lzma2.uncompressed == 0) {
|| !rc_is_finished(&s->rc))
return XZ_DATA_ERROR;
< s->lzma2.compressed)) {
return XZ_OK;
}
break;
case SEQ_COPY:
if (s->lzma2.compressed > 0)
return XZ_OK;
break;
}
}
return XZ_OK;
}
#ifdef GRUB_EMBED_DECOMPRESSOR
#include <grub/decompressor.h>
#endif
{
struct xz_dec_lzma2 *s;
#ifndef GRUB_EMBED_DECOMPRESSOR
/* Maximum supported dictionary by this implementation is 3 GiB. */
return NULL;
s = kmalloc(sizeof(*s), GFP_KERNEL);
if (s == NULL)
return NULL;
if (dict_max > 0) {
kfree(s);
return NULL;
}
}
#else
s = &lzma2;
#endif
return s;
}
{
/* This limits dictionary size to 3 GiB (39) to keep parsing simpler. */
return XZ_OPTIONS_ERROR;
#ifndef GRUB_EMBED_DECOMPRESSOR
{
/* enlarge dictionary buffer */
if (! newdict)
return XZ_MEMLIMIT_ERROR;
}
#endif
s->lzma2.need_dict_reset = true;
return XZ_OK;
}
{
#ifndef GRUB_EMBED_DECOMPRESSOR
kfree(s);
#endif
}