*/
/*
- * Copyright (C) 2012, 2013, 2014 Eric Biggers
+ * Copyright (C) 2012, 2013, 2014, 2015 Eric Biggers
*
* This file 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
# include "config.h"
#endif
+#include <string.h>
+
#include "wimlib/decompressor_ops.h"
#include "wimlib/decompress_common.h"
#include "wimlib/error.h"
#include "wimlib/lzx_common.h"
#include "wimlib/util.h"
-#include <string.h>
-
/* These values are chosen for fast decompression. */
#define LZX_MAINCODE_TABLEBITS 11
#define LZX_LENCODE_TABLEBITS 10
u8 alignedcode_lens[LZX_ALIGNEDCODE_NUM_SYMBOLS];
} _aligned_attribute(DECODE_TABLE_ALIGNMENT);
+/* Least-recently used queue for match offsets. */
+struct lzx_lru_queue {
+ u32 R[LZX_NUM_RECENT_OFFSETS];
+};
+
+static inline void
+lzx_lru_queue_init(struct lzx_lru_queue *queue)
+{
+ for (unsigned i = 0; i < LZX_NUM_RECENT_OFFSETS; i++)
+ queue->R[i] = 1;
+}
+
/* The main LZX decompressor structure.
*
* Note: we keep track of most of the decompression state outside this
};
/* Read a Huffman-encoded symbol using the precode. */
-static inline u16
+static inline unsigned
read_huffsym_using_precode(struct input_bitstream *istream,
const u16 precode_decode_table[])
{
}
/* Read a Huffman-encoded symbol using the main code. */
-static inline u16
+static inline unsigned
read_huffsym_using_maincode(struct input_bitstream *istream,
const struct lzx_tables *tables)
{
}
/* Read a Huffman-encoded symbol using the length code. */
-static inline u16
+static inline unsigned
read_huffsym_using_lencode(struct input_bitstream *istream,
const struct lzx_tables *tables)
{
}
/* Read a Huffman-encoded symbol using the aligned offset code. */
-static inline u16
+static inline unsigned
read_huffsym_using_alignedcode(struct input_bitstream *istream,
const struct lzx_tables *tables)
{
run_len = 4 + bitstream_read_bits(istream, 1);
presym = read_huffsym_using_precode(istream,
precode_decode_table);
+ if (unlikely(presym > 17))
+ return -1;
len = *len_ptr - presym;
if ((s8)len < 0)
len += 17;
}
/*
- * Decompress an LZX-compressed block of data.
+ * Decompress a block of LZX-compressed data.
*
* @block_type:
* The type of the block (LZX_BLOCKTYPE_VERBATIM or LZX_BLOCKTYPE_ALIGNED).
- *
- * @block_size:
- * The size of the block, in bytes.
- *
- * @window:
- * Pointer to the beginning of the decompression window.
- *
- * @window_pos:
- * The position in the window at which the block starts.
- *
+ * @out_begin
+ * The beginning of the (uncompressed) output buffer.
+ * @out_next
+ * Pointer to the location in the (uncompressed) output buffer at which
+ * this block will start.
+ * @out_block_end
+ * Pointer to the location in the (uncompressed) output buffer at which
+ * this block will end.
* @tables:
- * The Huffman decoding tables for the block.
- *
+ * The Huffman decoding tables for this block.
* @queue:
* The least-recently-used queue for match offsets.
- *
* @istream:
* The input bitstream, positioned at the start of the block data.
*
* Returns 0 on success, or -1 if the data was invalid.
*/
static int
-lzx_decompress_block(int block_type, u32 block_size,
- u8 *window, u32 window_pos,
+lzx_decompress_block(int block_type, u8 * const out_begin,
+ u8 * out_next, u8 * const out_block_end,
const struct lzx_tables *tables,
struct lzx_lru_queue *queue,
struct input_bitstream *istream)
{
- u8 *window_ptr = &window[window_pos];
- u8 *window_end = window_ptr + block_size;
unsigned mainsym;
u32 match_len;
unsigned offset_slot;
unsigned num_extra_bits;
unsigned ones_if_aligned = 0U - (block_type == LZX_BLOCKTYPE_ALIGNED);
- while (window_ptr != window_end) {
+ while (out_next != out_block_end) {
mainsym = read_huffsym_using_maincode(istream, tables);
if (mainsym < LZX_NUM_CHARS) {
/* Literal */
- *window_ptr++ = mainsym;
+ *out_next++ = mainsym;
continue;
}
/* Decode the length header and offset slot. */
mainsym -= LZX_NUM_CHARS;
- match_len = mainsym & 0x7;
- offset_slot = mainsym >> 3;
+ match_len = mainsym % LZX_NUM_LEN_HEADERS;
+ offset_slot = mainsym / LZX_NUM_LEN_HEADERS;
/* If needed, read a length symbol to decode the full length. */
- if (match_len == 0x7)
+ if (match_len == LZX_NUM_PRIMARY_LENS)
match_len += read_huffsym_using_lencode(istream, tables);
match_len += LZX_MIN_MATCH_LEN;
- if (offset_slot <= 2) {
+ if (offset_slot < LZX_NUM_RECENT_OFFSETS) {
/* Repeat offset */
/* Note: This isn't a real LRU queue, since using the R2
* each offset are encoded using the aligned offset
* code. Otherwise, all the extra bits are literal. */
- /*if (block_type == LZX_BLOCKTYPE_ALIGNED && num_extra_bits >= 3) {*/
- if ((num_extra_bits & ones_if_aligned) >= 3) {
- match_offset += bitstream_read_bits(istream, num_extra_bits - 3) << 3;
+ if ((num_extra_bits & ones_if_aligned) >= LZX_NUM_ALIGNED_OFFSET_BITS) {
+ match_offset +=
+ bitstream_read_bits(istream,
+ num_extra_bits -
+ LZX_NUM_ALIGNED_OFFSET_BITS)
+ << LZX_NUM_ALIGNED_OFFSET_BITS;
match_offset += read_huffsym_using_alignedcode(istream, tables);
} else {
match_offset += bitstream_read_bits(istream, num_extra_bits);
}
/* Adjust the offset. */
- match_offset -= LZX_OFFSET_OFFSET;
+ match_offset -= LZX_OFFSET_ADJUSTMENT;
/* Update the match offset LRU queue. */
+ BUILD_BUG_ON(LZX_NUM_RECENT_OFFSETS != 3);
queue->R[2] = queue->R[1];
queue->R[1] = queue->R[0];
queue->R[0] = match_offset;
/* Validate the match, then copy it to the current position. */
- if (unlikely(match_len > window_end - window_ptr))
+ if (unlikely(match_len > out_block_end - out_next))
return -1;
- if (unlikely(match_offset > window_ptr - window))
+ if (unlikely(match_offset > out_next - out_begin))
return -1;
- lz_copy(window_ptr, match_len, match_offset, window_end,
+ lz_copy(out_next, match_len, match_offset, out_block_end,
LZX_MIN_MATCH_LEN);
- window_ptr += match_len;
+ out_next += match_len;
}
return 0;
}
static int
-lzx_decompress(const void *compressed_data, size_t compressed_size,
- void *uncompressed_data, size_t uncompressed_size,
- void *_dec)
+lzx_decompress(const void *restrict compressed_data, size_t compressed_size,
+ void *restrict uncompressed_data, size_t uncompressed_size,
+ void *restrict _dec)
{
struct lzx_decompressor *dec = _dec;
struct input_bitstream istream;
struct lzx_lru_queue queue;
- u32 window_pos;
+ u8 * const out_begin = uncompressed_data;
+ u8 *out_next = out_begin;
+ u8 * const out_end = out_begin + uncompressed_size;
int block_type;
u32 block_size;
bool may_have_e8_byte;
* the compressed data has been decompressed, so there are no more
* blocks. */
- for (window_pos = 0;
- window_pos < uncompressed_size;
- window_pos += block_size)
- {
+ while (out_next != out_end) {
+
ret = lzx_read_block_header(&istream, dec->num_main_syms,
dec->window_order, &block_type,
&block_size, &dec->tables, &queue);
if (ret)
return ret;
- if (block_size > uncompressed_size - window_pos)
+ if (block_size > out_end - out_next)
return -1;
if (block_type != LZX_BLOCKTYPE_UNCOMPRESSED) {
/* Compressed block. */
ret = lzx_decompress_block(block_type,
- block_size,
- uncompressed_data,
- window_pos,
+ out_begin,
+ out_next,
+ out_next + block_size,
&dec->tables,
&queue,
&istream);
* have been encoded as a literal using mainsym 0xe8. */
if (dec->tables.maincode_lens[0xe8] != 0)
may_have_e8_byte = true;
+
+ out_next += block_size;
} else {
/* Uncompressed block. */
- const u8 *p;
-
- p = bitstream_read_bytes(&istream, block_size);
- if (!p)
+ out_next = bitstream_read_bytes(&istream, out_next, block_size);
+ if (!out_next)
return -1;
- memcpy(&((u8*)uncompressed_data)[window_pos], p, block_size);
-
/* Re-align the bitstream if an odd number of bytes was
* read. */
if (block_size & 1)
git://wimlib.net / wimlib / blobdiff