All of lore.kernel.org
 help / color / mirror / Atom feed
* [PATCH 0/20] inflate: refactor boot-time inflate code
@ 2005-12-22 18:26 Matt Mackall
  2005-12-22 18:26 ` [PATCH 1/20] inflate: lindent and manual formatting changes Matt Mackall
  2006-01-05  3:50 ` [PATCH 0/20] inflate: refactor boot-time inflate code Andrew Morton
  0 siblings, 2 replies; 24+ messages in thread
From: Matt Mackall @ 2005-12-22 18:26 UTC (permalink / raw)
  To: Andrew Morton; +Cc: linux-kernel, linux-arch, linux-tiny

This is a refactored version of the lib/inflate.c:

- clean up some really ugly code
- clean up atrocities like '#include "../../../lib/inflate.c"'
- drop a ton of cut and paste code from the kernel boot
- move towards making the boot decompressor pluggable
- move towards unifying the multiple inflate implementations
- save space

Recent changes include:

- use proper pointer types for minimal malloc arena
- fix up static const usage to make ARM happy
- fix compile with CONFIG_MODVERSIONS

This touches 11 architectures, which makes things slightly
interesting. Rather than break the patches out by arch, I've gone the
route of making a number of small incremental changes that sweep
across the tree. Patches that touch the per-arch code are marked
"(arch)".

I've been primarily testing this on x86, but various versions of this
code have gotten testing on a variety of architectures as part of my
linux-tiny tree.

(This work was sponsored in part by the CE Linux Forum.)

^ permalink raw reply	[flat|nested] 24+ messages in thread
* [PATCH 3/20] inflate: clean up input logic
@ 2005-10-31 20:54 Matt Mackall
  2005-10-31 20:54 ` [PATCH 4/20] inflate: start moving globals into iostate Matt Mackall
  0 siblings, 1 reply; 24+ messages in thread
From: Matt Mackall @ 2005-10-31 20:54 UTC (permalink / raw)
  To: Andrew Morton, linux-kernel; +Cc: linux-arch

inflate: cleanup input logic

Transform ugly macros to inlines
Kill mask_bits table
Eliminate magic underrun handling (dealt with by getbyte())

Signed-off-by: Matt Mackall <mpm@selenic.com>

Index: tiny/lib/inflate.c
===================================================================
--- tiny.orig/lib/inflate.c	2005-09-28 18:21:30.000000000 -0700
+++ tiny/lib/inflate.c	2005-09-28 18:22:39.000000000 -0700
@@ -183,24 +183,23 @@ static const u16 cpdext[] = {
 	12, 12, 13, 13
 };
 
-/* Macros for inflate() bit peeking and grabbing.
+/* Inlines for inflate() bit peeking and grabbing.
    The usage is:
 
-        NEEDBITS(j)
-        x = b & mask_bits[j];
-        DUMPBITS(j)
-
-   where NEEDBITS makes sure that b has at least j bits in it, and
-   DUMPBITS removes the bits from b. The macros use the variable k for
-   the number of bits in b. Normally, b and k are initialized at the
-   beginning of a routine that uses these macros from a global bit
-   buffer and count.
+        x = readbits(&b, &k, j);
+	dumpbits(&b, &k, j);
+
+	x = pullbits(&b, &k, j);
+
+   where readbits makes sure that b has at least j bits in it, and
+   dumpbits removes the bits from b, while k tracks the number of bits
+   in b.
 
    If we assume that EOB will be the longest code, then we will never
-   ask for bits with NEEDBITS that are beyond the end of the stream.
-   So, NEEDBITS should not read any more bytes than are needed to
-   meet the request.  Then no bytes need to be "returned" to the buffer
-   at the end of the last block.
+   ask for bits that are beyond the end of the stream. So, readbits
+   should not read any more bytes than are needed to meet the request.
+   Then no bytes need to be "returned" to the buffer at the end of the
+   last block.
 
    However, this assumption is not true for fixed blocks--the EOB code
    is 7 bits, but the other literal/length codes can be 8 or 9 bits.
@@ -216,15 +215,25 @@ static const u16 cpdext[] = {
 static u32 bb;			/* bit buffer */
 static unsigned bk;		/* bits in bit buffer */
 
-static const u16 mask_bits[] = {
-	0x0000,
-	0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff,
-	0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff
-};
+static inline u32 readbits(u32 *b, u32 *k, int n)
+{
+	for( ; *k < n; *k += 8)
+		*b |= (u32)get_byte() << *k;
+	return *b & ((1 << n) - 1);
+}
 
-#define NEXTBYTE()  ({ int v = get_byte(); if (v < 0) goto underrun; (u8)v; })
-#define NEEDBITS(n) do {while(k<(n)){b|=((u32)NEXTBYTE())<<k;k+=8;}} while(0)
-#define DUMPBITS(n) do {b>>=(n);k-=(n);} while(0)
+static inline void dumpbits(u32 *b, u32 *k, int n)
+{
+	*b >>= n;
+	*k -= n;
+}
+
+static inline u32 pullbits(u32 *b, u32 *k, int n)
+{
+	u32 r = readbits(b, k, n);
+	dumpbits(b, k, n);
+	return r;
+}
 
 /*
    Huffman code decoding is performed using a multi-level table lookup.
@@ -541,7 +550,6 @@ static int inflate_codes(struct huft *tl
 	unsigned n, d;		/* length and index for copy */
 	unsigned w;		/* current window position */
 	struct huft *t;		/* pointer to table entry */
-	unsigned ml, md;	/* masks for bl and bd bits */
 	u32 b;		/* bit buffer */
 	unsigned k;	/* number of bits in bit buffer */
 
@@ -551,20 +559,17 @@ static int inflate_codes(struct huft *tl
 	w = outcnt;			/* initialize window position */
 
 	/* inflate the coded data */
-	ml = mask_bits[bl];	/* precompute masks for speed */
-	md = mask_bits[bd];
 	for (;;) {		/* do until end of block */
-		NEEDBITS((unsigned)bl);
-		if ((e = (t = tl + ((unsigned)b & ml))->e) > 16)
-			do {
-				if (e == 99)
-					return 1;
-				DUMPBITS(t->b);
-				e -= 16;
-				NEEDBITS(e);
-			} while ((e = (t = t->v.t + ((unsigned)b &
-						     mask_bits[e]))->e) > 16);
-		DUMPBITS(t->b);
+		t = tl + readbits(&b, &k, bl);
+		e = t->e;
+		while (e > 16) {
+			if (e == 99)
+				return 1;
+			dumpbits(&b, &k, t->b);
+			t = t->v.t + readbits(&b, &k, e - 16);
+			e = t->e;
+		}
+		dumpbits(&b, &k, t->b);
 		if (e == 16) {	/* then it's a literal */
 			window[w++] = (u8)t->v.n;
 			if (w == WSIZE) {
@@ -577,25 +582,21 @@ static int inflate_codes(struct huft *tl
 				break;
 
 			/* get length of block to copy */
-			NEEDBITS(e);
-			n = t->v.n + ((unsigned)b & mask_bits[e]);
-			DUMPBITS(e);
+			n = t->v.n + pullbits(&b, &k, e);
 
 			/* decode distance of block to copy */
-			NEEDBITS((unsigned)bd);
-			if ((e = (t = td + ((unsigned)b & md))->e) > 16)
-				do {
-					if (e == 99)
-						return 1;
-					DUMPBITS(t->b);
-					e -= 16;
-					NEEDBITS(e);
-				} while ((e = (t = t->v.t + ((unsigned)b
-					   & mask_bits[e]))->e) > 16);
-			DUMPBITS(t->b);
-			NEEDBITS(e);
-			d = w - t->v.n - ((unsigned)b & mask_bits[e]);
-			DUMPBITS(e)
+			t = td + readbits(&b, &k, bd);
+			e = t->e;
+			while (e > 16) {
+				if (e == 99)
+					return 1;
+				dumpbits(&b, &k, t->b);
+				t = t->v.t + readbits(&b, &k, e - 16);
+				e = t->e;
+			}
+			dumpbits(&b, &k, t->b);
+
+			d = w - t->v.n - pullbits(&b, &k, e);
 
 			/* do the copy */
 			do {
@@ -628,9 +629,6 @@ static int inflate_codes(struct huft *tl
 
 	/* done */
 	return 0;
-
-      underrun:
-	return 4;		/* Input underrun */
 }
 
 /* inflate_stored - "decompress" an inflated type 0 (stored) block. */
@@ -649,27 +647,20 @@ static int INIT inflate_stored(void)
 	w = outcnt;			/* initialize window position */
 
 	/* go to byte boundary */
-	n = k & 7;
-	DUMPBITS(n);
+	dumpbits(&b, &k, k & 7);
 
 	/* get the length and its complement */
-	NEEDBITS(16);
-	n = ((unsigned)b & 0xffff);
-	DUMPBITS(16);
-	NEEDBITS(16);
-	if (n != (unsigned)((~b) & 0xffff))
+	n = pullbits(&b, &k, 16);
+	if (n != (~pullbits(&b, &k, 16) & 0xffff))
 		return 1;	/* error in compressed data */
-	DUMPBITS(16);
 
 	/* read and output the compressed data */
 	while (n--) {
-		NEEDBITS(8);
-		window[w++] = (u8)b;
+		window[w++] = (u8)get_byte();
 		if (w == WSIZE) {
 			flush_output(w);
 			w = 0;
 		}
-		DUMPBITS(8);
 	}
 
 	/* restore the globals from the locals */
@@ -679,9 +670,6 @@ static int INIT inflate_stored(void)
 
 	DEBG(">");
 	return 0;
-
-      underrun:
-	return 4;		/* Input underrun */
 }
 
 
@@ -748,7 +736,6 @@ static int noinline INIT inflate_dynamic
 	int i;			/* temporary variables */
 	unsigned j;
 	unsigned l;		/* last length */
-	unsigned m;		/* mask for bit lengths table */
 	unsigned n;		/* number of lengths to get */
 	struct huft *tl;	/* literal/length code table */
 	struct huft *td;	/* distance code table */
@@ -768,26 +755,17 @@ static int noinline INIT inflate_dynamic
 	k = bk;
 
 	/* read in table lengths */
-	NEEDBITS(5);
-	nl = 257 + ((unsigned)b & 0x1f); /* number of literal/length codes */
-	DUMPBITS(5);
-	NEEDBITS(5);
-	nd = 1 + ((unsigned)b & 0x1f);	/* number of distance codes */
-	DUMPBITS(5);
-	NEEDBITS(4);
-	nb = 4 + ((unsigned)b & 0xf);	/* number of bit length codes */
-	DUMPBITS(4);
+	nl = 257 + pullbits(&b, &k, 5); /* number of literal/length codes */
+	nd = 1 + pullbits(&b, &k, 5); /* number of distance codes */
+	nb = 4 + pullbits(&b, &k, 4); /* number of bit length codes */
 	if (nl > 286 || nd > 30)
 		return 1;	/* bad lengths */
 
 	DEBG("dyn1 ");
 
 	/* read in bit-length-code lengths */
-	for (j = 0; j < nb; j++) {
-		NEEDBITS(3);
-		ll[border[j]] = (unsigned)b & 7;
-		DUMPBITS(3);
-	}
+	for (j = 0; j < nb; j++)
+		ll[border[j]] = pullbits(&b, &k, 3);
 	for (; j < 19; j++)
 		ll[border[j]] = 0;
 
@@ -805,36 +783,28 @@ static int noinline INIT inflate_dynamic
 
 	/* read in literal and distance code lengths */
 	n = nl + nd;
-	m = mask_bits[bl];
 	i = l = 0;
 	while ((unsigned)i < n) {
-		NEEDBITS((unsigned)bl);
-		j = (td = tl + ((unsigned)b & m))->b;
-		DUMPBITS(j);
+		td = tl + readbits(&b, &k, bl);
+		dumpbits(&b, &k, td->b);
 		j = td->v.n;
 		if (j < 16)	/* length of code in bits (0..15) */
 			ll[i++] = l = j;	/* save last length in l */
 		else if (j == 16) {	/* repeat last length 3 to 6 times */
-			NEEDBITS(2);
-			j = 3 + ((unsigned)b & 3);
-			DUMPBITS(2);
-			    if ((unsigned)i + j > n)
+			j = 3 + pullbits(&b, &k, 2);
+			if ((unsigned)i + j > n)
 				return 1;
 			while (j--)
 				ll[i++] = l;
 		} else if (j == 17) {	/* 3 to 10 zero length codes */
-			NEEDBITS(3);
-			j = 3 + ((unsigned)b & 7);
-			DUMPBITS(3);
+			j = 3 + pullbits(&b, &k, 3);
 			if ((unsigned)i + j > n)
 				return 1;
 			while (j--)
 				ll[i++] = 0;
 			l = 0;
 		} else {	/* j == 18: 11 to 138 zero length codes */
-			NEEDBITS(7);
-			j = 11 + ((unsigned)b & 0x7f);
-			DUMPBITS(7);
+			j = 11 + pullbits(&b, &k, 7);
 			if ((unsigned)i + j > n)
 				return 1;
 			while (j--)
@@ -892,9 +862,6 @@ static int noinline INIT inflate_dynamic
 
 	DEBG(">");
 	return 0;
-
-      underrun:
-	return 4;		/* Input underrun */
 }
 
 /* inflate_block - decompress a deflated block
@@ -903,28 +870,11 @@ static int noinline INIT inflate_dynamic
 static int INIT inflate_block(int *e)
 {
 	unsigned t;		/* block type */
-	u32 b;		/* bit buffer */
-	unsigned k;	/* number of bits in bit buffer */
 
 	DEBG("<blk");
 
-	/* make local bit buffer */
-	b = bb;
-	k = bk;
-
-	/* read in last block bit */
-	NEEDBITS(1);
-	*e = (int)b & 1;
-	DUMPBITS(1);
-
-	/* read in block type */
-	NEEDBITS(2);
-	t = (unsigned)b & 3;
-	DUMPBITS(2);
-
-	/* restore the global bit buffer */
-	bb = b;
-	bk = k;
+	*e = pullbits(&bb, &bk, 1); /* read in last block bit */
+	t = pullbits(&bb, &bk, 2); /* read in block type */
 
 	/* inflate that block type */
 	if (t == 2)
@@ -938,9 +888,6 @@ static int INIT inflate_block(int *e)
 
 	/* bad block type */
 	return 2;
-
-      underrun:
-	return 4;		/* Input underrun */
 }
 
 /* inflate - decompress an inflated entry */
@@ -1050,9 +997,9 @@ static int INIT gunzip(void)
 	u32 orig_len = 0;	/* original uncompressed length */
 	int res;
 
-	magic[0] = NEXTBYTE();
-	magic[1] = NEXTBYTE();
-	method = NEXTBYTE();
+	magic[0] = get_byte();
+	magic[1] = get_byte();
+	method = get_byte();
 
 	if (magic[0] != 037 || ((magic[1] != 0213) && (magic[1] != 0236))) {
 		error("bad gzip magic numbers");
@@ -1078,29 +1025,29 @@ static int INIT gunzip(void)
 		error("Input has invalid flags");
 		return -1;
 	}
-	NEXTBYTE();		/* Get timestamp */
-	NEXTBYTE();
-	NEXTBYTE();
-	NEXTBYTE();
+	get_byte();		/* Get timestamp */
+	get_byte();
+	get_byte();
+	get_byte();
 
-	(void)NEXTBYTE();	/* Ignore extra flags for the moment */
-	(void)NEXTBYTE();	/* Ignore OS type for the moment */
+	get_byte();	/* Ignore extra flags for the moment */
+	get_byte();	/* Ignore OS type for the moment */
 
 	if (flags & EXTRA_FIELD) {
-		unsigned len = (unsigned)NEXTBYTE();
-		len |= ((unsigned)NEXTBYTE()) << 8;
+		unsigned len = (unsigned)get_byte();
+		len |= ((unsigned)get_byte()) << 8;
 		while (len--)
-			(void)NEXTBYTE();
+			get_byte();
 	}
 
 	/* Discard original file name if it was truncated */
 	if (flags & ORIG_NAME)
-		while (NEXTBYTE())
+		while (get_byte())
 			;
 
 	/* Discard file comment if any */
 	if (flags & COMMENT)
-		while (NEXTBYTE())
+		while (get_byte())
 			;
 
 	/* Decompress */
@@ -1130,15 +1077,15 @@ static int INIT gunzip(void)
 	/* crc32  (see algorithm.doc)
 	 * uncompressed input size modulo 2^32
 	 */
-	orig_crc = (u32)NEXTBYTE();
-	orig_crc |= (u32)NEXTBYTE() << 8;
-	orig_crc |= (u32)NEXTBYTE() << 16;
-	orig_crc |= (u32)NEXTBYTE() << 24;
-
-	orig_len = (u32)NEXTBYTE();
-	orig_len |= (u32)NEXTBYTE() << 8;
-	orig_len |= (u32)NEXTBYTE() << 16;
-	orig_len |= (u32)NEXTBYTE() << 24;
+	orig_crc = (u32)get_byte();
+	orig_crc |= (u32)get_byte() << 8;
+	orig_crc |= (u32)get_byte() << 16;
+	orig_crc |= (u32)get_byte() << 24;
+
+	orig_len = (u32)get_byte();
+	orig_len |= (u32)get_byte() << 8;
+	orig_len |= (u32)get_byte() << 16;
+	orig_len |= (u32)get_byte() << 24;
 
 	/* Validate decompression */
 	if (orig_crc != CRC_VALUE) {
@@ -1150,8 +1097,4 @@ static int INIT gunzip(void)
 		return -1;
 	}
 	return 0;
-
-      underrun:		/* NEXTBYTE() goto's here if needed */
-	error("out of input data");
-	return -1;
 }

^ permalink raw reply	[flat|nested] 24+ messages in thread
end of thread, other threads:[~2006-01-05  5:15 UTC | newest]

Thread overview: 24+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2005-12-22 18:26 [PATCH 0/20] inflate: refactor boot-time inflate code Matt Mackall
2005-12-22 18:26 ` [PATCH 1/20] inflate: lindent and manual formatting changes Matt Mackall
2005-12-22 18:26   ` [PATCH 2/20] inflate: kill legacy bits Matt Mackall
2005-12-22 18:26     ` [PATCH 3/20] inflate: clean up input logic Matt Mackall
2005-12-22 18:26       ` [PATCH 4/20] inflate: start moving globals into iostate Matt Mackall
2005-12-22 18:26         ` [PATCH 5/20] inflate: cleanup Huffman table code Matt Mackall
2005-12-22 18:26           ` [PATCH 6/20] inflate: internalize CRC calculation, cleanup table calculation Matt Mackall
2005-12-22 18:26             ` [PATCH 7/20] inflate: eliminate memzero usage Matt Mackall
2005-12-22 18:26               ` [PATCH 8/20] inflate: (arch) kill unneeded declarations Matt Mackall
2005-12-22 18:26                 ` [PATCH 9/20] inflate: (arch) refactor inflate malloc code Matt Mackall
2005-12-22 18:26                   ` [PATCH 10/20] inflate: (arch) kill external CRC calculation Matt Mackall
2005-12-22 18:26                     ` [PATCH 11/20] inflate: (arch) kill get_byte Matt Mackall
2005-12-22 18:26                       ` [PATCH 12/20] inflate: internalize (arch) most of the output window handling Matt Mackall
2005-12-22 18:26                         ` [PATCH 13/20] inflate: (arch) kill silly zlib typedefs Matt Mackall
2005-12-22 18:26                           ` [PATCH 14/20] inflate: (arch) use an error callback rather than a global Matt Mackall
2005-12-22 18:26                             ` [PATCH 15/20] inflate: (arch) tidy user declarations Matt Mackall
2005-12-22 18:26                               ` [PATCH 16/20] inflate: remove legacy DEBG macros Matt Mackall
2005-12-22 18:26                                 ` [PATCH 17/20] inflate: mark some arrays as initdata Matt Mackall
2005-12-22 18:27                                   ` [PATCH 18/20] inflate: minor const changes Matt Mackall
2005-12-22 18:27                                     ` [PATCH 19/20] inflate: (arch) use proper linking Matt Mackall
2005-12-22 18:27                                       ` [PATCH 20/20] inflate: make in-core inflate share common CRC Matt Mackall
2006-01-05  3:50 ` [PATCH 0/20] inflate: refactor boot-time inflate code Andrew Morton
2006-01-05  5:09   ` Matt Mackall
  -- strict thread matches above, loose matches on Subject: below --
2005-10-31 20:54 [PATCH 3/20] inflate: clean up input logic Matt Mackall
2005-10-31 20:54 ` [PATCH 4/20] inflate: start moving globals into iostate Matt Mackall

This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.