Use only 16 bits for symbol frequencies
authorEric Biggers <ebiggers3@gmail.com>
Fri, 21 Dec 2012 04:22:32 +0000 (22:22 -0600)
committerEric Biggers <ebiggers3@gmail.com>
Fri, 21 Dec 2012 04:22:32 +0000 (22:22 -0600)
src/compress.c
src/compress.h
src/lzx-compress.c
src/xpress-compress.c

index c1a52ff63df7c04527f0d74e8c34832fd6929ed3..f98a4416f666fd9776eb84953c5deea79c51e019 100644 (file)
@@ -224,7 +224,7 @@ static void huffman_tree_compute_path_lengths(HuffmanNode *node, u16 cur_len)
  *                     for symbol i.
  */
 void make_canonical_huffman_code(unsigned num_syms, unsigned max_codeword_len,
-                                const u32 freq_tab[], u8 lens[],
+                                const freq_t freq_tab[], u8 lens[],
                                 u16 codewords[])
 {
        /* We require at least 2 possible symbols in the alphabet to produce a
index 37ab23d315763b471ca7c442cf4ac39ba05bf1e6..88c55f26b3fa9a2afad9b74e6ff2f40b9d5eaff6 100644 (file)
 
 typedef u16 output_bitbuf_t;
 
+/* Assuming that WIM chunks are at most 32768 bytes, 16 bits is enough for any
+ * symbol frequency. */
+typedef u16 freq_t;
+
 /* Structure to keep track of the current position in the compressed output. */
 struct output_bitstream {
 
@@ -88,7 +92,7 @@ extern int flush_output_bitstream(struct output_bitstream *ostream);
 
 extern void make_canonical_huffman_code(unsigned num_syms,
                                        unsigned max_codeword_len,
-                                       const u32 freq_tab[],
+                                       const freq_t freq_tab[],
                                        u8 lens[],
                                        u16 codewords[]);
 
index 81a6256eb7e8a88c67e6a6e091bd9f4131c34efe..effe656bf20fcd14f65c780e13b7fc78c1d31483 100644 (file)
@@ -77,9 +77,9 @@ struct lzx_codes {
 };
 
 struct lzx_freq_tables {
-       u32 main_freq_table[LZX_MAINTREE_NUM_SYMBOLS];
-       u32 len_freq_table[LZX_LENTREE_NUM_SYMBOLS];
-       u32 aligned_freq_table[LZX_ALIGNEDTREE_NUM_SYMBOLS];
+       freq_t main_freq_table[LZX_MAINTREE_NUM_SYMBOLS];
+       freq_t len_freq_table[LZX_LENTREE_NUM_SYMBOLS];
+       freq_t aligned_freq_table[LZX_ALIGNEDTREE_NUM_SYMBOLS];
 };
 
 /* Returns the LZX position slot that corresponds to a given formatted offset.
@@ -122,7 +122,7 @@ static inline unsigned lzx_get_position_slot(unsigned formatted_offset)
 
 static u32 lzx_record_literal(u8 literal, void *__main_freq_tab)
 {
-       u32 *main_freq_tab = __main_freq_tab;
+       freq_t *main_freq_tab = __main_freq_tab;
        main_freq_tab[literal]++;
        return literal;
 }
@@ -406,7 +406,7 @@ static int lzx_write_compressed_tree(struct output_bitstream *out,
 {
        /* Frequencies of the length symbols, including the RLE symbols (NOT the
         * actual lengths themselves). */
-       unsigned pretree_freqs[LZX_PRETREE_NUM_SYMBOLS];
+       freq_t pretree_freqs[LZX_PRETREE_NUM_SYMBOLS];
        u8 pretree_lens[LZX_PRETREE_NUM_SYMBOLS];
        u16 pretree_codewords[LZX_PRETREE_NUM_SYMBOLS];
        u8 output_syms[num_symbols * 2];
index 2b3a6a6e9d980a14ce7ca2e6f062b5505c53656a..d131ada5d277038e564b929c0c514c302caf9f31 100644 (file)
@@ -90,7 +90,7 @@ static int xpress_write_compressed_literals(struct output_bitstream *ostream,
 
 static u32 xpress_record_literal(u8 literal, void *__freq_tab)
 {
-       u32 *freq_tab = __freq_tab;
+       freq_t *freq_tab = __freq_tab;
        freq_tab[literal]++;
        return literal;
 }
@@ -121,7 +121,7 @@ static u32 xpress_record_match(unsigned match_offset, unsigned match_len,
        u32 len_hdr = min(adjusted_match_len, 0xf);
        u32 offset_bsr = bsr32(match_offset);
        u32 sym = len_hdr | (offset_bsr << 4) | XPRESS_NUM_CHARS;
-       ((u32*)freq_tab)[sym]++;
+       ((freq_t*)freq_tab)[sym]++;
        return adjusted_match_len | (match_offset << 16);
 }
 
@@ -159,7 +159,7 @@ int xpress_compress(const void *__uncompressed_data, unsigned uncompressed_len,
        u8 *compressed_data = __compressed_data;
        struct output_bitstream ostream;
        u32 match_tab[uncompressed_len];
-       u32 freq_tab[XPRESS_NUM_SYMBOLS];
+       freq_t freq_tab[XPRESS_NUM_SYMBOLS];
        u16 codewords[XPRESS_NUM_SYMBOLS];
        u8 lens[XPRESS_NUM_SYMBOLS];
        unsigned num_matches;