From: Eric Biggers <ebiggers3@gmail.com>
Date: Fri, 21 Dec 2012 04:22:32 +0000 (-0600)
Subject: Use only 16 bits for symbol frequencies
X-Git-Tag: v1.2.2~6
X-Git-Url: https://wimlib.net/git/?p=wimlib;a=commitdiff_plain;h=d66b5c805c4e9a660bac6f979d88c1820cb031f2

Use only 16 bits for symbol frequencies
---

diff --git a/src/compress.c b/src/compress.c
index c1a52ff6..f98a4416 100644
--- a/src/compress.c
+++ b/src/compress.c
@@ -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
diff --git a/src/compress.h b/src/compress.h
index 37ab23d3..88c55f26 100644
--- a/src/compress.h
+++ b/src/compress.h
@@ -12,6 +12,10 @@
 
 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[]);
 
diff --git a/src/lzx-compress.c b/src/lzx-compress.c
index 81a6256e..effe656b 100644
--- a/src/lzx-compress.c
+++ b/src/lzx-compress.c
@@ -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];
diff --git a/src/xpress-compress.c b/src/xpress-compress.c
index 2b3a6a6e..d131ada5 100644
--- a/src/xpress-compress.c
+++ b/src/xpress-compress.c
@@ -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;