decompress_common: move temp space for building decode table to heap
authorEric Biggers <ebiggers3@gmail.com>
Sat, 9 Jul 2016 15:01:23 +0000 (10:01 -0500)
committerEric Biggers <ebiggers3@gmail.com>
Sat, 9 Jul 2016 15:11:00 +0000 (10:11 -0500)
include/wimlib/decompress_common.h
src/decompress_common.c
src/lzms_decompress.c
src/lzx_decompress.c
src/xpress_decompress.c

index 945a5e9..d20085d 100644 (file)
@@ -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                               */
index fa605f0..3b49274 100644 (file)
  *     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;
index d6de299..2ef2deb 100644 (file)
@@ -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;
 }
index 7b02dbf..cce98e3 100644 (file)
@@ -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,
index 623ea18..16a577e 100644 (file)
@@ -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.  */