#ifndef _WIMLIB_COMPRESS_H
#define _WIMLIB_COMPRESS_H
-#include "wimlib/endianness.h"
#include "wimlib/types.h"
-typedef u16 output_bitbuf_t;
-
/* Variable type that can represent all possible window positions. */
-typedef u32 freq_t;
#ifndef INPUT_IDX_T_DEFINED
#define INPUT_IDX_T_DEFINED
typedef u32 input_idx_t;
#endif
-/* Structure to keep track of the current position in the compressed output. */
+/* Structure to keep track of the current state sending bits and bytes to the
+ * compressed output buffer. */
struct output_bitstream {
- /* A variable to buffer writing bits to the output and is flushed to the
- * compressed output when full. */
- output_bitbuf_t bitbuf;
+ /* Variable that holds up to 16 bits that haven't yet been flushed to
+ * the output. */
+ u16 bitbuf;
- /* Number of free bits in @bitbuf */
+ /* Number of free bits in @bitbuf; that is, 16 minus the number of valid
+ * bits in @bitbuf. */
unsigned free_bits;
/* Pointer to the start of the output buffer. */
*/
u8 *output;
- /* Bytes remaining in @output buffer. */
+ /* Number of bytes remaining in the @output buffer. */
input_idx_t bytes_remaining;
/* Set to true if the buffer has been exhausted. */
typedef void (*lz_record_literal_t)(u8 lit, void *ctx);
extern void
-lz_analyze_block(const u8 window[],
+lz_analyze_block(const u8 window[restrict],
input_idx_t window_size,
lz_record_match_t record_match,
lz_record_literal_t record_literal,
void *record_ctx,
const struct lz_params *params,
- input_idx_t prev_tab[]);
+ input_idx_t prev_tab[restrict]);
extern void
make_canonical_huffman_code(unsigned num_syms,
unsigned max_codeword_len,
- const freq_t freq_tab[restrict],
+ const input_idx_t freq_tab[restrict],
u8 lens[restrict],
u16 codewords[restrict]);
#include "wimlib/endianness.h"
#include "wimlib/types.h"
-/* Must be at least 32 bits. */
-typedef u32 input_bitbuf_t;
-#define INPUT_BITBUF_BITS (sizeof(input_bitbuf_t) * 8)
-
#ifndef INPUT_IDX_T_DEFINED
#define INPUT_IDX_T_DEFINED
typedef u32 input_idx_t;
/* A variable of length at least 32 bits that is used to hold bits that
* have been read from the stream. The bits are ordered from high-order
* to low-order, and the next bit is always the high-order bit. */
- input_bitbuf_t bitbuf;
-
- /* Pointer to the next byte to be retrieved from the input. */
- const u8 *data;
+ u32 bitbuf;
- /* Number of bits in @bitbuf that are valid. */
+ /* Number of bits in @bitbuf that are valid. */
unsigned bitsleft;
- /* Number of words of data that are left. */
+ /* Pointer to the next byte to be retrieved from the input. */
+ const u8 *data;
+
+ /* Number of bytes of data that are left. */
input_idx_t data_bytes_left;
};
}
/* Ensures that the bit buffer variable for the bitstream contains @num_bits
- * bits, which must be 16 or fewer.
+ * bits.
*
* If there are at least @num_bits bits remaining in the bitstream, 0 is
* returned. Otherwise, -1 is returned. */
static inline int
bitstream_ensure_bits(struct input_bitstream *istream, unsigned num_bits)
{
- wimlib_assert2(num_bits <= 16);
+ for (int nbits = num_bits; (int)istream->bitsleft < nbits; nbits -= 16) {
+ u16 nextword;
+ unsigned shift;
- if (istream->bitsleft >= num_bits)
- return 0;
+ if (unlikely(istream->data_bytes_left < 2))
+ return -1;
- if (unlikely(istream->data_bytes_left < 2))
- return -1;
+ wimlib_assert2(istream->bitsleft <= sizeof(istream->bitbuf) * 8 - 16);
- istream->bitbuf |= le16_to_cpu(*(le16*)istream->data) <<
- (INPUT_BITBUF_BITS - 16 - istream->bitsleft);
- istream->data += 2;
- istream->bitsleft += 16;
- istream->data_bytes_left -= 2;
+ nextword = le16_to_cpu(*(const le16*)istream->data);
+ shift = sizeof(istream->bitbuf) * 8 - 16 - istream->bitsleft;
+ istream->bitbuf |= (u32)nextword << shift;
+ istream->data += 2;
+ istream->bitsleft += 16;
+ istream->data_bytes_left -= 2;
+
+ }
return 0;
}
/* Returns the next @num_bits bits in the buffer variable, which must contain at
* least @num_bits bits, for the bitstream. */
-static inline unsigned
+static inline u32
bitstream_peek_bits(const struct input_bitstream *istream, unsigned num_bits)
{
wimlib_assert2(istream->bitsleft >= num_bits);
if (unlikely(num_bits == 0))
return 0;
- return istream->bitbuf >> (INPUT_BITBUF_BITS - num_bits);
+ return istream->bitbuf >> (sizeof(istream->bitbuf) * 8 - num_bits);
}
/* Removes @num_bits bits from the buffer variable, which must contain at least
/* Gets and removes @num_bits bits from the buffer variable, which must contain
* at least @num_bits bits, for the bitstream. */
-static inline unsigned
-bitstream_pop_bits(struct input_bitstream *istream,
- unsigned num_bits)
+static inline u32
+bitstream_pop_bits(struct input_bitstream *istream, unsigned num_bits)
{
- unsigned n = bitstream_peek_bits(istream, num_bits);
+ u32 n = bitstream_peek_bits(istream, num_bits);
bitstream_remove_bits(istream, num_bits);
return n;
}
-/* Reads @num_bits bits from the input bitstream. @num_bits must be 16 or
- * fewer. On success, returns 0 and returns the requested bits in @n. If there
- * are fewer than @num_bits remaining in the bitstream, -1 is returned. */
+/* Reads @num_bits bits from the input bitstream. On success, returns 0 and
+ * returns the requested bits in @n. If there are fewer than @num_bits
+ * remaining in the bitstream, -1 is returned. */
static inline int
-bitstream_read_bits(struct input_bitstream *istream,
- unsigned num_bits, unsigned *n)
+bitstream_read_bits(struct input_bitstream *istream, unsigned num_bits, u32 *n)
{
if (unlikely(bitstream_ensure_bits(istream, num_bits)))
return -1;
/* Reads @num_bits bits from the buffer variable for a bistream without checking
* to see if that many bits are in the buffer or not. */
-static inline unsigned
+static inline u32
bitstream_read_bits_nocheck(struct input_bitstream *istream, unsigned num_bits)
{
- unsigned n = bitstream_peek_bits(istream, num_bits);
+ u32 n = bitstream_peek_bits(istream, num_bits);
bitstream_remove_bits(istream, num_bits);
return n;
}
#endif
#include "wimlib/assert.h"
+#include "wimlib/endianness.h"
#include "wimlib/compiler.h"
#include "wimlib/compress.h"
#include "wimlib/util.h"
}
typedef struct {
- freq_t freq;
+ input_idx_t freq;
u16 sym;
union {
u16 path_len;
void
make_canonical_huffman_code(unsigned num_syms,
unsigned max_codeword_len,
- const freq_t freq_tab[restrict],
+ const input_idx_t freq_tab[restrict],
u8 lens[restrict],
u16 codewords[restrict])
{
* @prev_tab: Temporary space containing least @window_size elements.
*/
void
-lz_analyze_block(const u8 window[],
+lz_analyze_block(const u8 window[restrict],
input_idx_t window_size,
lz_record_match_t record_match,
lz_record_literal_t record_literal,
void *record_ctx,
const struct lz_params *params,
- input_idx_t prev_tab[])
+ input_idx_t prev_tab[restrict])
{
unsigned cur_input_pos = 0;
unsigned hash = 0;
#include "wimlib.h"
#include "wimlib/compress.h"
+#include "wimlib/endianness.h"
#include "wimlib/error.h"
#include "wimlib/lzx.h"
#include "wimlib/util.h"
/* Tables for tallying symbol frequencies in the three LZX alphabets */
struct lzx_freqs {
- freq_t main[LZX_MAINCODE_MAX_NUM_SYMBOLS];
- freq_t len[LZX_LENCODE_NUM_SYMBOLS];
- freq_t aligned[LZX_ALIGNEDCODE_NUM_SYMBOLS];
+ input_idx_t main[LZX_MAINCODE_MAX_NUM_SYMBOLS];
+ input_idx_t len[LZX_LENCODE_NUM_SYMBOLS];
+ input_idx_t aligned[LZX_ALIGNEDCODE_NUM_SYMBOLS];
};
/* LZX intermediate match/literal format */
lzx_build_precode(const u8 lens[restrict],
const u8 prev_lens[restrict],
const unsigned num_syms,
- freq_t precode_freqs[restrict LZX_PRECODE_NUM_SYMBOLS],
+ input_idx_t precode_freqs[restrict LZX_PRECODE_NUM_SYMBOLS],
u8 output_syms[restrict num_syms],
u8 precode_lens[restrict LZX_PRECODE_NUM_SYMBOLS],
u16 precode_codewords[restrict LZX_PRECODE_NUM_SYMBOLS],
const u8 prev_lens[restrict],
unsigned num_syms)
{
- freq_t precode_freqs[LZX_PRECODE_NUM_SYMBOLS];
+ input_idx_t precode_freqs[LZX_PRECODE_NUM_SYMBOLS];
u8 output_syms[num_syms];
u8 precode_lens[LZX_PRECODE_NUM_SYMBOLS];
u16 precode_codewords[LZX_PRECODE_NUM_SYMBOLS];
_aligned_attribute(DECODE_TABLE_ALIGNMENT);
u8 pretree_lens[LZX_PRECODE_NUM_SYMBOLS];
unsigned i;
- unsigned len;
+ u32 len;
int ret;
/* Read the code lengths of the pretree codes. There are 20 lengths of
* the next lengths are all equal to the next symbol in the
* input. */
unsigned tree_code;
- unsigned num_zeroes;
+ u32 num_zeroes;
unsigned code;
- unsigned num_same;
+ u32 num_same;
signed char value;
ret = read_huffsym_using_pretree(istream, pretree_decode_table,
int ret;
unsigned block_type;
unsigned block_size;
- unsigned s;
- unsigned i;
- unsigned len;
ret = bitstream_ensure_bits(istream, 4);
- if (ret) {
- LZX_DEBUG("LZX input stream overrun");
+ if (ret)
return ret;
- }
/* The first three bits tell us what kind of block it is, and are one
* of the LZX_BLOCKTYPE_* values. */
/* Read the block size. This mirrors the behavior
* lzx_write_compressed_block() in lzx-compress.c; see that for more
* details. */
- s = bitstream_read_bits_nocheck(istream, 1);
- if (s) {
+ if (bitstream_read_bits_nocheck(istream, 1)) {
block_size = LZX_DEFAULT_BLOCK_SIZE;
} else {
- unsigned tmp;
+ u32 tmp;
block_size = 0;
ret = bitstream_read_bits(istream, 8, &tmp);
/* Read the path lengths for the elements of the aligned tree,
* then build it. */
- for (i = 0; i < LZX_ALIGNEDCODE_NUM_SYMBOLS; i++) {
+ for (unsigned i = 0; i < LZX_ALIGNEDCODE_NUM_SYMBOLS; i++) {
+ u32 len;
+
ret = bitstream_read_bits(istream,
LZX_ALIGNEDCODE_ELEMENT_SIZE,
&len);
unsigned match_offset;
unsigned additional_len;
unsigned num_extra_bits;
- unsigned verbatim_bits;
- unsigned aligned_bits;
+ u32 verbatim_bits;
+ u32 aligned_bits;
unsigned i;
int ret;
u8 *match_dest;
}
struct xpress_record_ctx {
- freq_t freqs[XPRESS_NUM_SYMBOLS];
+ input_idx_t freqs[XPRESS_NUM_SYMBOLS];
struct xpress_match *matches;
};