From: Eric Biggers Date: Sat, 9 Jul 2016 15:01:23 +0000 (-0500) Subject: decompress_common: move temp space for building decode table to heap X-Git-Tag: v1.10.0~25 X-Git-Url: https://wimlib.net/git/?p=wimlib;a=commitdiff_plain;h=4ee103c6e2a2988e1fb358bfa2dc38dcb621505a;hp=ff4f09a9848beab16d3d72f38a158848f24315ea decompress_common: move temp space for building decode table to heap --- diff --git a/include/wimlib/decompress_common.h b/include/wimlib/decompress_common.h index 945a5e9f..d20085db 100644 --- a/include/wimlib/decompress_common.h +++ b/include/wimlib/decompress_common.h @@ -398,10 +398,17 @@ read_huffsym(struct input_bitstream *is, const u16 decode_table[], (max_codeword_len))] \ _aligned_attribute(DECODE_TABLE_ALIGNMENT) +/* + * Declare the temporary "working_space" array needed for building the decode + * table for a Huffman code. + */ +#define DECODE_TABLE_WORKING_SPACE(name, num_syms, max_codeword_len) \ + u16 name[2 * ((max_codeword_len) + 1) + (num_syms)]; + extern int make_huffman_decode_table(u16 decode_table[], unsigned num_syms, unsigned table_bits, const u8 lens[], - unsigned max_codeword_len); + unsigned max_codeword_len, u16 working_space[]); /******************************************************************************/ /* LZ match copying */ diff --git a/src/decompress_common.c b/src/decompress_common.c index fa605f0c..3b492748 100644 --- a/src/decompress_common.c +++ b/src/decompress_common.c @@ -110,16 +110,19 @@ * The maximum codeword length permitted for this code. All entries in * 'lens' must be less than or equal to this value. * + * @working_space + * A temporary array that was declared with DECODE_TABLE_WORKING_SPACE(). + * * Returns 0 on success, or -1 if the lengths do not form a valid prefix code. */ int make_huffman_decode_table(u16 decode_table[], unsigned num_syms, unsigned table_bits, const u8 lens[], - unsigned max_codeword_len) + unsigned max_codeword_len, u16 working_space[]) { - u16 len_counts[max_codeword_len + 1]; - u16 offsets[max_codeword_len + 1]; - u16 sorted_syms[num_syms]; + u16 * const len_counts = &working_space[0]; + u16 * const offsets = &working_space[1 * (max_codeword_len + 1)]; + u16 * const sorted_syms = &working_space[2 * (max_codeword_len + 1)]; s32 remainder = 1; void *entry_ptr = decode_table; unsigned codeword_len = 1; diff --git a/src/lzms_decompress.c b/src/lzms_decompress.c index d6de2990..2ef2debd 100644 --- a/src/lzms_decompress.c +++ b/src/lzms_decompress.c @@ -348,7 +348,12 @@ struct lzms_decompressor { u32 delta_power_freqs[LZMS_NUM_DELTA_POWER_SYMS]; struct lzms_huffman_rebuild_info delta_power_rebuild_info; - u32 codewords[LZMS_MAX_NUM_SYMS]; + /* Temporary space for lzms_build_huffman_code() */ + union { + u32 codewords[LZMS_MAX_NUM_SYMS]; + DECODE_TABLE_WORKING_SPACE(working_space, LZMS_MAX_NUM_SYMS, + LZMS_MAX_CODEWORD_LENGTH); + }; }; // struct @@ -517,7 +522,8 @@ lzms_build_huffman_code(struct lzms_huffman_rebuild_info *rebuild_info) rebuild_info->num_syms, rebuild_info->table_bits, (u8 *)rebuild_info->decode_table, - LZMS_MAX_CODEWORD_LENGTH); + LZMS_MAX_CODEWORD_LENGTH, + (u16 *)rebuild_info->codewords); rebuild_info->num_syms_until_rebuild = rebuild_info->rebuild_freq; } diff --git a/src/lzx_decompress.c b/src/lzx_decompress.c index 7b02dbf6..cce98e32 100644 --- a/src/lzx_decompress.c +++ b/src/lzx_decompress.c @@ -93,6 +93,21 @@ struct lzx_decompressor { u8 extra_offset_bits[LZX_MAX_OFFSET_SLOTS]; }; + union { + DECODE_TABLE_WORKING_SPACE(maincode_working_space, + LZX_MAINCODE_MAX_NUM_SYMBOLS, + LZX_MAX_MAIN_CODEWORD_LEN); + DECODE_TABLE_WORKING_SPACE(lencode_working_space, + LZX_LENCODE_NUM_SYMBOLS, + LZX_MAX_LEN_CODEWORD_LEN); + DECODE_TABLE_WORKING_SPACE(alignedcode_working_space, + LZX_ALIGNEDCODE_NUM_SYMBOLS, + LZX_MAX_ALIGNED_CODEWORD_LEN); + DECODE_TABLE_WORKING_SPACE(precode_working_space, + LZX_PRECODE_NUM_SYMBOLS, + LZX_MAX_PRE_CODEWORD_LEN); + }; + unsigned window_order; unsigned num_main_syms; @@ -157,7 +172,8 @@ lzx_read_codeword_lens(struct lzx_decompressor *d, struct input_bitstream *is, LZX_PRECODE_NUM_SYMBOLS, LZX_PRECODE_TABLEBITS, d->precode_lens, - LZX_MAX_PRE_CODEWORD_LEN)) + LZX_MAX_PRE_CODEWORD_LEN, + d->precode_working_space)) return -1; /* Decode the codeword lengths. */ @@ -333,14 +349,16 @@ lzx_decompress_block(struct lzx_decompressor *d, struct input_bitstream *is, d->num_main_syms, LZX_MAINCODE_TABLEBITS, d->maincode_lens, - LZX_MAX_MAIN_CODEWORD_LEN)) + LZX_MAX_MAIN_CODEWORD_LEN, + d->maincode_working_space)) return -1; if (make_huffman_decode_table(d->lencode_decode_table, LZX_LENCODE_NUM_SYMBOLS, LZX_LENCODE_TABLEBITS, d->lencode_lens, - LZX_MAX_LEN_CODEWORD_LEN)) + LZX_MAX_LEN_CODEWORD_LEN, + d->lencode_working_space)) return -1; if (block_type == LZX_BLOCKTYPE_ALIGNED) { @@ -348,7 +366,8 @@ lzx_decompress_block(struct lzx_decompressor *d, struct input_bitstream *is, LZX_ALIGNEDCODE_NUM_SYMBOLS, LZX_ALIGNEDCODE_TABLEBITS, d->alignedcode_lens, - LZX_MAX_ALIGNED_CODEWORD_LEN)) + LZX_MAX_ALIGNED_CODEWORD_LEN, + d->alignedcode_working_space)) return -1; min_aligned_offset_slot = LZX_MIN_ALIGNED_OFFSET_SLOT; memcpy(d->extra_offset_bits, d->extra_offset_bits_minus_aligned, diff --git a/src/xpress_decompress.c b/src/xpress_decompress.c index 623ea187..16a577e8 100644 --- a/src/xpress_decompress.c +++ b/src/xpress_decompress.c @@ -82,6 +82,8 @@ struct xpress_decompressor { XPRESS_TABLEBITS, XPRESS_MAX_CODEWORD_LEN); u8 lens[XPRESS_NUM_SYMBOLS]; }; + DECODE_TABLE_WORKING_SPACE(working_space, XPRESS_NUM_SYMBOLS, + XPRESS_MAX_CODEWORD_LEN); } _aligned_attribute(DECODE_TABLE_ALIGNMENT); static int @@ -107,7 +109,8 @@ xpress_decompress(const void *restrict compressed_data, size_t compressed_size, /* Build a decoding table for the Huffman code. */ if (make_huffman_decode_table(d->decode_table, XPRESS_NUM_SYMBOLS, XPRESS_TABLEBITS, d->lens, - XPRESS_MAX_CODEWORD_LEN)) + XPRESS_MAX_CODEWORD_LEN, + d->working_space)) return -1; /* Decode the matches and literals. */