[git commit] gzip: code shrink

Denys Vlasenko vda.linux at googlemail.com
Fri Sep 6 15:59:45 UTC 2019


commit: https://git.busybox.net/busybox/commit/?id=d327c6b190900dcb0cb7cda9008eb4f9893a92d8
branch: https://git.busybox.net/busybox/commit/?id=refs/heads/master

Converted a few 16-bit variables and small arrays to 32-bit.

Stopped pulling desc->FOO members into temporary local variables
in gen_bitlen(): on register-starved arches, this is a loss,
temporaries go into stack slots.

Sprinkled a few "const" on pointer arguments.

function                                             old     new   delta
pack_gzip                                            742     745      +3
gen_codes                                            101      97      -4
build_tree                                           886     833     -53
------------------------------------------------------------------------------
(add/remove: 0/0 grow/shrink: 1/2 up/down: 3/-57)             Total: -54 bytes

Signed-off-by: Denys Vlasenko <vda.linux at googlemail.com>
---
 archival/gzip.c | 88 ++++++++++++++++++++++++++++-----------------------------
 1 file changed, 44 insertions(+), 44 deletions(-)

diff --git a/archival/gzip.c b/archival/gzip.c
index 3966a06b4..d9c730f13 100644
--- a/archival/gzip.c
+++ b/archival/gzip.c
@@ -507,7 +507,7 @@ static ALWAYS_INLINE void flush_outbuf_if_32bit_optimized(void)
  * pointer, then initialize the crc shift register contents instead.
  * Return the current crc in either case.
  */
-static void updcrc(uch * s, unsigned n)
+static void updcrc(uch *s, unsigned n)
 {
 	G1.crc = crc32_block_endian0(G1.crc, s, n, global_crc32_table /*G1.crc_32_tab*/);
 }
@@ -610,7 +610,7 @@ static void bi_windup(void)
  * Copy a stored block to the zip file, storing first the length and its
  * one's complement if requested.
  */
-static void copy_block(char *buf, unsigned len, int header)
+static void copy_block(const char *buf, unsigned len, int header)
 {
 	bi_windup();		/* align on byte boundary */
 
@@ -1010,7 +1010,8 @@ struct globals2 {
 	tree_desc d_desc;
 	tree_desc bl_desc;
 
-	ush bl_count[MAX_BITS + 1];
+	/* was "ush", but "unsigned" results in smaller code */
+	unsigned bl_count[MAX_BITS + 1];
 
 /* The lengths of the bit length codes are sent in order of decreasing
  * probability, to avoid transmitting the lengths for unused bit length codes.
@@ -1121,7 +1122,7 @@ static void init_block(void)
 	(tree[n].Freq < tree[m].Freq \
 	|| (tree[n].Freq == tree[m].Freq && G2.depth[n] <= G2.depth[m]))
 
-static void pqdownheap(ct_data * tree, int k)
+static void pqdownheap(const ct_data *tree, int k)
 {
 	int v = G2.heap[k];
 	int j = k << 1;		/* left son of k */
@@ -1155,22 +1156,15 @@ static void pqdownheap(ct_data * tree, int k)
  *     The length opt_len is updated; static_len is also updated if stree is
  *     not null.
  */
-static void gen_bitlen(tree_desc * desc)
+static void gen_bitlen(const tree_desc *desc)
 {
-	ct_data *tree = desc->dyn_tree;
-	const uint8_t *extra = desc->extra_bits;
-	int base = desc->extra_base;
-	int max_code = desc->max_code;
-	int max_length = desc->max_length;
-	ct_data *stree = desc->static_tree;
-	int h;				/* heap index */
-	int n, m;			/* iterate over the tree elements */
-	int bits;			/* bit length */
-	int xbits;			/* extra bits */
-	ush f;				/* frequency */
-	int overflow = 0;	/* number of elements with bit length too large */
-
-	for (bits = 0; bits <= MAX_BITS; bits++)
+#define tree desc->dyn_tree
+	int h;          /* heap index */
+	int n, m;       /* iterate over the tree elements */
+	int bits;       /* bit length */
+	int overflow;   /* number of elements with bit length too large */
+
+	for (bits = 0; bits < ARRAY_SIZE(G2.bl_count); bits++)
 		G2.bl_count[bits] = 0;
 
 	/* In a first pass, compute the optimal bit lengths (which may
@@ -1178,28 +1172,32 @@ static void gen_bitlen(tree_desc * desc)
 	 */
 	tree[G2.heap[G2.heap_max]].Len = 0;	/* root of the heap */
 
+	overflow = 0;
 	for (h = G2.heap_max + 1; h < HEAP_SIZE; h++) {
+		ulg f;          /* frequency */
+		int xbits;      /* extra bits */
+
 		n = G2.heap[h];
 		bits = tree[tree[n].Dad].Len + 1;
-		if (bits > max_length) {
-			bits = max_length;
+		if (bits > desc->max_length) {
+			bits = desc->max_length;
 			overflow++;
 		}
 		tree[n].Len = (ush) bits;
 		/* We overwrite tree[n].Dad which is no longer needed */
 
-		if (n > max_code)
+		if (n > desc->max_code)
 			continue;	/* not a leaf node */
 
 		G2.bl_count[bits]++;
 		xbits = 0;
-		if (n >= base)
-			xbits = extra[n - base];
+		if (n >= desc->extra_base)
+			xbits = desc->extra_bits[n - desc->extra_base];
 		f = tree[n].Freq;
-		G2.opt_len += (ulg) f *(bits + xbits);
+		G2.opt_len += f * (bits + xbits);
 
-		if (stree)
-			G2.static_len += (ulg) f * (stree[n].Len + xbits);
+		if (desc->static_tree)
+			G2.static_len += f * (desc->static_tree[n].Len + xbits);
 	}
 	if (overflow == 0)
 		return;
@@ -1209,14 +1207,14 @@ static void gen_bitlen(tree_desc * desc)
 
 	/* Find the first bit length which could increase: */
 	do {
-		bits = max_length - 1;
+		bits = desc->max_length - 1;
 		while (G2.bl_count[bits] == 0)
 			bits--;
 		G2.bl_count[bits]--;	/* move one leaf down the tree */
 		G2.bl_count[bits + 1] += 2;	/* move one overflow item as its brother */
-		G2.bl_count[max_length]--;
+		G2.bl_count[desc->max_length]--;
 		/* The brother of the overflow item also moves one step up,
-		 * but this does not affect bl_count[max_length]
+		 * but this does not affect bl_count[desc->max_length]
 		 */
 		overflow -= 2;
 	} while (overflow > 0);
@@ -1226,11 +1224,11 @@ static void gen_bitlen(tree_desc * desc)
 	 * lengths instead of fixing only the wrong ones. This idea is taken
 	 * from 'ar' written by Haruhiko Okumura.)
 	 */
-	for (bits = max_length; bits != 0; bits--) {
+	for (bits = desc->max_length; bits != 0; bits--) {
 		n = G2.bl_count[bits];
 		while (n != 0) {
 			m = G2.heap[--h];
-			if (m > max_code)
+			if (m > desc->max_code)
 				continue;
 			if (tree[m].Len != (unsigned) bits) {
 				Trace((stderr, "code %d bits %d->%d\n", m, tree[m].Len, bits));
@@ -1240,6 +1238,7 @@ static void gen_bitlen(tree_desc * desc)
 			n--;
 		}
 	}
+#undef tree
 }
 
 /* ===========================================================================
@@ -1250,12 +1249,13 @@ static void gen_bitlen(tree_desc * desc)
  * OUT assertion: the field code is set for all tree elements of non
  *     zero code length.
  */
-static void gen_codes(ct_data * tree, int max_code)
+static void gen_codes(ct_data *tree, int max_code)
 {
-	ush next_code[MAX_BITS + 1];	/* next code value for each bit length */
-	ush code = 0;		/* running code value */
-	int bits;			/* bit index */
-	int n;				/* code index */
+	/* next_code[] and code used to be "ush", but "unsigned" results in smaller code */
+	unsigned next_code[MAX_BITS + 1]; /* next code value for each bit length */
+	unsigned code = 0;      /* running code value */
+	int bits;               /* bit index */
+	int n;                  /* code index */
 
 	/* The distribution counts are first used to generate the code values
 	 * without bit reversal.
@@ -1307,7 +1307,7 @@ do { \
 	pqdownheap(tree, SMALLEST); \
 } while (0)
 
-static void build_tree(tree_desc * desc)
+static void build_tree(tree_desc *desc)
 {
 	ct_data *tree = desc->dyn_tree;
 	ct_data *stree = desc->static_tree;
@@ -1385,10 +1385,10 @@ static void build_tree(tree_desc * desc)
 	/* At this point, the fields freq and dad are set. We can now
 	 * generate the bit lengths.
 	 */
-	gen_bitlen((tree_desc *) desc);
+	gen_bitlen(desc);
 
 	/* The field len is now set, we can generate the bit codes */
-	gen_codes((ct_data *) tree, max_code);
+	gen_codes(tree, max_code);
 }
 
 /* ===========================================================================
@@ -1397,7 +1397,7 @@ static void build_tree(tree_desc * desc)
  * counts. (The contribution of the bit length codes will be added later
  * during the construction of bl_tree.)
  */
-static void scan_tree(ct_data * tree, int max_code)
+static void scan_tree(ct_data *tree, int max_code)
 {
 	int n;				/* iterates over all tree elements */
 	int prevlen = -1;	/* last emitted length */
@@ -1449,7 +1449,7 @@ static void scan_tree(ct_data * tree, int max_code)
  * Send a literal or distance tree in compressed form, using the codes in
  * bl_tree.
  */
-static void send_tree(ct_data * tree, int max_code)
+static void send_tree(const ct_data *tree, int max_code)
 {
 	int n;				/* iterates over all tree elements */
 	int prevlen = -1;	/* last emitted length */
@@ -1625,7 +1625,7 @@ static int ct_tally(int dist, int lc)
 /* ===========================================================================
  * Send the block data compressed using the given Huffman trees
  */
-static void compress_block(ct_data * ltree, ct_data * dtree)
+static void compress_block(const ct_data *ltree, const ct_data *dtree)
 {
 	unsigned dist;          /* distance of matched string */
 	int lc;                 /* match length or unmatched char (if dist == 0) */
@@ -1675,7 +1675,7 @@ static void compress_block(ct_data * ltree, ct_data * dtree)
  * trees or store, and output the encoded block to the zip file. This function
  * returns the total compressed length for the file so far.
  */
-static void flush_block(char *buf, ulg stored_len, int eof)
+static void flush_block(const char *buf, ulg stored_len, int eof)
 {
 	ulg opt_lenb, static_lenb;      /* opt_len and static_len in bytes */
 	int max_blindex;                /* index of last bit length code of non zero freq */


More information about the busybox-cvs mailing list