From: Matt Mackall <mpm@selenic.com>
To: Andrew Morton <akpm@osdl.org>
Cc: linux-kernel@vger.kernel.org
Subject: [PATCH 4/7] inflate pt1: start moving globals into iostate
Date: Fri, 24 Feb 2006 14:12:16 -0600 [thread overview]
Message-ID: <5.399206195@selenic.com> (raw)
In-Reply-To: <0.399206195@selenic.com>
inflate: move globals into a state structure
Signed-off-by: Matt Mackall <mpm@selenic.com>
Index: 2.6.16-rc4-inflate/lib/inflate.c
===================================================================
--- 2.6.16-rc4-inflate.orig/lib/inflate.c 2006-02-22 17:16:05.000000000 -0600
+++ 2.6.16-rc4-inflate/lib/inflate.c 2006-02-22 17:16:07.000000000 -0600
@@ -125,16 +125,23 @@ struct huft {
} v;
};
+struct iostate {
+ u8 *window;
+ int opos, osize, bits;
+ u32 buf;
+};
+
/* Function prototypes */
static int INIT huft_build(unsigned *, unsigned, unsigned,
const u16 *, const u16 *, struct huft **, int *);
static int INIT huft_free(struct huft *);
-static int INIT inflate_codes(struct huft *, struct huft *, int, int);
-static int INIT inflate_stored(void);
-static int INIT inflate_fixed(void);
-static int INIT inflate_dynamic(void);
-static int INIT inflate_block(int *);
-static int INIT inflate(void);
+static int INIT inflate_codes(struct iostate *, struct huft *, struct huft *,
+ int, int);
+static int INIT inflate_stored(struct iostate *);
+static int INIT inflate_fixed(struct iostate *);
+static int INIT inflate_dynamic(struct iostate *);
+static int INIT inflate_block(struct iostate *, int *);
+static int INIT inflate(struct iostate *);
/* The inflate algorithm uses a sliding 32 K byte window on the uncompressed
stream to find repeated byte strings. This is implemented here as a
@@ -145,7 +152,36 @@ static int INIT inflate(void);
"u8 *window;" and then malloc'ed in the latter case. The definition
must be in unzip.h, included above. */
-#define flush_output(w) (outcnt=(w),flush_window())
+static void flush_output(struct iostate *io)
+{
+ outcnt = io->opos;
+ flush_window();
+ io->opos = 0;
+}
+
+static inline void put_byte(struct iostate *io, u8 byte)
+{
+ io->window[io->opos++] = byte;
+ if (io->opos == io->osize)
+ flush_output(io);
+}
+
+static void copy_bytes(struct iostate *io, int len, int dist)
+{
+ int part, pos = io->opos - dist;
+
+ do {
+ pos &= io->osize - 1;
+ part = min(len, io->osize - max(pos, io->opos));
+ len -= part;
+
+ while (part--)
+ io->window[io->opos++] = io->window[pos++];
+
+ if (io->opos == io->osize)
+ flush_output(io);
+ } while (len);
+}
/* Tables for deflate from PKZIP's appnote.txt. */
@@ -186,10 +222,10 @@ static const u16 cpdext[] = {
/* Inlines for inflate() bit peeking and grabbing.
The usage is:
- x = readbits(&b, &k, j);
- dumpbits(&b, &k, j);
+ x = readbits(io, j);
+ dumpbits(io, j);
- x = pullbits(&b, &k, j);
+ x = pullbits(io, 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
@@ -212,29 +248,32 @@ static const u16 cpdext[] = {
the stream.
*/
-static u32 bb; /* bit buffer */
-static unsigned bk; /* bits in bit buffer */
-
-static inline u32 readbits(u32 *b, u32 *k, int n)
+static inline u32 readbits(struct iostate *io, int n)
{
- for( ; *k < n; *k += 8)
- *b |= (u32)get_byte() << *k;
- return *b & ((1 << n) - 1);
+ for( ; io->bits < n; io->bits += 8)
+ io->buf |= (u32)get_byte() << io->bits;
+ return io->buf & ((1 << n) - 1);
}
-static inline void dumpbits(u32 *b, u32 *k, int n)
+static inline void dumpbits(struct iostate *io, int n)
{
- *b >>= n;
- *k -= n;
+ io->buf >>= n;
+ io->bits -= n;
}
-static inline u32 pullbits(u32 *b, u32 *k, int n)
+static inline u32 pullbits(struct iostate *io, int n)
{
- u32 r = readbits(b, k, n);
- dumpbits(b, k, n);
+ u32 r = readbits(io, n);
+ dumpbits(io, n);
return r;
}
+static inline void popbytes(struct iostate *io)
+{
+ inptr -= (io->bits >> 3);
+ io->bits &= 7;
+}
+
/*
Huffman code decoding is performed using a multi-level table lookup.
The fastest way to decode is to simply build a lookup table whose
@@ -536,6 +575,7 @@ STATIC int INIT huft_free(struct huft *t
/*
* inflate_codes - decompress the codes in a deflated block
+ * @io: current i/o state
* @tl: literal/length decoder tables
* @td: distance decoder tables
* @bl: number of bits decoded by tl
@@ -544,129 +584,75 @@ STATIC int INIT huft_free(struct huft *t
* inflate (decompress) the codes in a deflated (compressed) block.
* Return an error code or zero if it all goes ok.
*/
-static int inflate_codes(struct huft *tl, struct huft *td, int bl, int bd)
+static int INIT inflate_codes(struct iostate *io, struct huft *tl, struct huft *td,
+ int bl, int bd)
{
unsigned e; /* table entry flag/number of extra bits */
- unsigned n, d; /* length and index for copy */
- unsigned w; /* current window position */
+ unsigned len, dist;
struct huft *t; /* pointer to table entry */
- u32 b; /* bit buffer */
- unsigned k; /* number of bits in bit buffer */
-
- /* make local copies of globals */
- b = bb; /* initialize bit buffer */
- k = bk;
- w = outcnt; /* initialize window position */
/* inflate the coded data */
for (;;) { /* do until end of block */
- t = tl + readbits(&b, &k, bl);
+ t = tl + readbits(io, 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);
+ dumpbits(io, t->b);
+ t = t->v.t + readbits(io, e - 16);
e = t->e;
}
- dumpbits(&b, &k, t->b);
+ dumpbits(io, t->b);
if (e == 16) { /* then it's a literal */
- window[w++] = (u8)t->v.n;
- if (w == WSIZE) {
- flush_output(w);
- w = 0;
- }
+ put_byte(io, t->v.n);
} else { /* it's an EOB or a length */
/* exit if end of block */
if (e == 15)
break;
/* get length of block to copy */
- n = t->v.n + pullbits(&b, &k, e);
+ len = t->v.n + pullbits(io, e);
/* decode distance of block to copy */
- t = td + readbits(&b, &k, bd);
+ t = td + readbits(io, 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);
+ dumpbits(io, t->b);
+ t = t->v.t + readbits(io, e - 16);
e = t->e;
}
- dumpbits(&b, &k, t->b);
+ dumpbits(io, t->b);
- d = w - t->v.n - pullbits(&b, &k, e);
-
- /* do the copy */
- do {
- n -= (e = (e = WSIZE - ((d &= WSIZE - 1) > w ?
- d : w)) > n ? n : e);
-#if !defined(NOMEMCPY) && !defined(DEBUG)
- /* (this test assumes unsigned comparison) */
- if (w - d >= e) {
- memcpy(window + w, window + d, e);
- w += e;
- d += e;
- } else
-#endif /* !NOMEMCPY */
- /* avoid memcpy() overlap */
- do {
- window[w++] = window[d++];
- } while (--e);
- if (w == WSIZE) {
- flush_output(w);
- w = 0;
- }
- } while (n);
+ dist = t->v.n + pullbits(io, e);
+ copy_bytes(io, len, dist);
}
}
- /* restore the globals from the locals */
- outcnt = w; /* restore global window pointer */
- bb = b; /* restore global bit buffer */
- bk = k;
-
- /* done */
return 0;
}
-/* inflate_stored - "decompress" an inflated type 0 (stored) block. */
-static int INIT inflate_stored(void)
+/* inflate_stored - "decompress" an inflated type 0 (stored) block.
+ * @io: current i/o state
+ */
+static int INIT inflate_stored(struct iostate *io)
{
unsigned n; /* number of bytes in block */
- unsigned w; /* current window position */
- u32 b; /* bit buffer */
- unsigned k; /* number of bits in bit buffer */
DEBG("<stor");
- /* make local copies of globals */
- b = bb; /* initialize bit buffer */
- k = bk;
- w = outcnt; /* initialize window position */
-
/* go to byte boundary */
- dumpbits(&b, &k, k & 7);
+ dumpbits(io, io->bits & 7);
/* get the length and its complement */
- n = pullbits(&b, &k, 16);
- if (n != (~pullbits(&b, &k, 16) & 0xffff))
+ n = pullbits(io, 16);
+ if (n != (~pullbits(io, 16) & 0xffff))
return 1; /* error in compressed data */
/* read and output the compressed data */
- while (n--) {
- window[w++] = (u8)get_byte();
- if (w == WSIZE) {
- flush_output(w);
- w = 0;
- }
- }
-
- /* restore the globals from the locals */
- outcnt = w; /* restore global window pointer */
- bb = b; /* restore global bit buffer */
- bk = k;
+ while (n--)
+ put_byte(io, get_byte());
DEBG(">");
return 0;
@@ -674,6 +660,7 @@ static int INIT inflate_stored(void)
/* inflate_fixed - decompress a block with fixed Huffman codes
+ * @io: current i/o state
*
* decompress an inflated type 1 (fixed Huffman codes) block. We
* should either replace this with a custom decoder, or at least
@@ -681,7 +668,7 @@ static int INIT inflate_stored(void)
*
* We use `noinline' here to prevent gcc-3.5 from using too much stack space
*/
-static int noinline INIT inflate_fixed(void)
+static int noinline INIT inflate_fixed(struct iostate *io)
{
int i; /* temporary variable */
struct huft *tl; /* literal/length code table */
@@ -717,7 +704,7 @@ static int noinline INIT inflate_fixed(v
}
/* decompress until an end-of-block code */
- if (inflate_codes(tl, td, bl, bd))
+ if (inflate_codes(io, tl, td, bl, bd))
return 1;
/* free the decoding tables, return */
@@ -731,7 +718,7 @@ static int noinline INIT inflate_fixed(v
*
* We use `noinline' here to prevent gcc-3.5 from using too much stack space
*/
-static int noinline INIT inflate_dynamic(void)
+static int noinline INIT inflate_dynamic(struct iostate *io)
{
int i; /* temporary variables */
unsigned j;
@@ -745,19 +732,13 @@ static int noinline INIT inflate_dynamic
unsigned nl; /* number of literal/length codes */
unsigned nd; /* number of distance codes */
unsigned ll[286 + 30]; /* literal/length and distance code lengths */
- u32 b; /* bit buffer */
- unsigned k; /* number of bits in bit buffer */
DEBG("<dyn");
- /* make local bit buffer */
- b = bb;
- k = bk;
-
/* read in table lengths */
- 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 */
+ nl = 257 + pullbits(io, 5); /* number of literal/length codes */
+ nd = 1 + pullbits(io, 5); /* number of distance codes */
+ nb = 4 + pullbits(io, 4); /* number of bit length codes */
if (nl > 286 || nd > 30)
return 1; /* bad lengths */
@@ -765,7 +746,7 @@ static int noinline INIT inflate_dynamic
/* read in bit-length-code lengths */
for (j = 0; j < nb; j++)
- ll[border[j]] = pullbits(&b, &k, 3);
+ ll[border[j]] = pullbits(io, 3);
for (; j < 19; j++)
ll[border[j]] = 0;
@@ -785,26 +766,26 @@ static int noinline INIT inflate_dynamic
n = nl + nd;
i = l = 0;
while ((unsigned)i < n) {
- td = tl + readbits(&b, &k, bl);
- dumpbits(&b, &k, td->b);
+ td = tl + readbits(io, bl);
+ dumpbits(io, 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 */
- j = 3 + pullbits(&b, &k, 2);
+ j = 3 + pullbits(io, 2);
if ((unsigned)i + j > n)
return 1;
while (j--)
ll[i++] = l;
} else if (j == 17) { /* 3 to 10 zero length codes */
- j = 3 + pullbits(&b, &k, 3);
+ j = 3 + pullbits(io, 3);
if ((unsigned)i + j > n)
return 1;
while (j--)
ll[i++] = 0;
l = 0;
} else { /* j == 18: 11 to 138 zero length codes */
- j = 11 + pullbits(&b, &k, 7);
+ j = 11 + pullbits(io, 7);
if ((unsigned)i + j > n)
return 1;
while (j--)
@@ -820,10 +801,6 @@ static int noinline INIT inflate_dynamic
DEBG("dyn5 ");
- /* restore the global bit buffer */
- bb = b;
- bk = k;
-
DEBG("dyn5a ");
/* build the decoding tables for literal/length and distance codes */
@@ -851,7 +828,7 @@ static int noinline INIT inflate_dynamic
DEBG("dyn6 ");
/* decompress until an end-of-block code */
- if (inflate_codes(tl, td, bl, bd))
+ if (inflate_codes(io, tl, td, bl, bd))
return 1;
DEBG("dyn7 ");
@@ -865,24 +842,25 @@ static int noinline INIT inflate_dynamic
}
/* inflate_block - decompress a deflated block
+ * @io: current i/o state
* @e: last block flag
*/
-static int INIT inflate_block(int *e)
+static int INIT inflate_block(struct iostate *io, int *e)
{
unsigned t; /* block type */
DEBG("<blk");
- *e = pullbits(&bb, &bk, 1); /* read in last block bit */
- t = pullbits(&bb, &bk, 2); /* read in block type */
+ *e = pullbits(io, 1); /* read in last block bit */
+ t = pullbits(io, 2); /* read in block type */
/* inflate that block type */
if (t == 2)
- return inflate_dynamic();
+ return inflate_dynamic(io);
if (t == 0)
- return inflate_stored();
+ return inflate_stored(io);
if (t == 1)
- return inflate_fixed();
+ return inflate_fixed(io);
DEBG(">");
@@ -890,40 +868,27 @@ static int INIT inflate_block(int *e)
return 2;
}
-/* inflate - decompress an inflated entry */
-static int INIT inflate(void)
+/* inflate - decompress an inflated entry
+ * @io: current i/o state
+ */
+static int INIT inflate(struct iostate *io)
{
int e; /* last block flag */
int r; /* result code */
void *ptr;
- /* initialize window, bit buffer */
- outcnt = 0;
- bk = 0;
- bb = 0;
-
/* decompress until the last block */
do {
gzip_mark(&ptr);
- if ((r = inflate_block(&e))) {
+ if ((r = inflate_block(io, &e))) {
gzip_release(&ptr);
return r;
}
gzip_release(&ptr);
} while (!e);
- /* Undo too much lookahead. The next read will be byte aligned so we
- * can discard unused bits in the last meaningful byte.
- */
- while (bk >= 8) {
- bk -= 8;
- inptr--;
- }
-
- /* flush out window */
- flush_output(outcnt);
-
- /* return success */
+ popbytes(io);
+ flush_output(io);
return 0;
}
@@ -996,6 +961,11 @@ static int INIT gunzip(void)
u32 orig_crc = 0; /* original crc */
u32 orig_len = 0; /* original uncompressed length */
int res;
+ struct iostate io;
+
+ io.window = window;
+ io.osize = WSIZE;
+ io.opos = io.bits = io.buf = 0;
magic[0] = get_byte();
magic[1] = get_byte();
@@ -1051,7 +1021,7 @@ static int INIT gunzip(void)
;
/* Decompress */
- if ((res = inflate())) {
+ if ((res = inflate(&io))) {
switch (res) {
case 0:
break;
next prev parent reply other threads:[~2006-02-24 20:12 UTC|newest]
Thread overview: 31+ messages / expand[flat|nested] mbox.gz Atom feed top
[not found] <0.399206195@selenic.com>
2006-02-24 20:12 ` [PATCH 2/7] inflate pt1: kill legacy bits Matt Mackall
2006-02-24 20:12 ` Matt Mackall [this message]
2006-02-24 20:12 ` [PATCH 3/7] inflate pt1: clean up input logic Matt Mackall
2006-02-24 22:19 ` Russell King
2006-02-25 6:51 ` Matt Mackall
2006-02-25 8:49 ` Russell King
2006-02-25 8:55 ` Russell King
2006-02-25 9:04 ` Andrew Morton
2006-02-25 9:09 ` Russell King
2006-02-25 14:54 ` Matt Mackall
2006-02-25 18:05 ` Russell King
2006-02-25 21:04 ` Matt Mackall
2006-02-25 21:22 ` Russell King
2006-02-25 21:47 ` Matt Mackall
2006-02-25 21:58 ` Russell King
2006-02-25 22:37 ` Matt Mackall
2006-02-25 22:57 ` Russell King
2006-02-27 1:18 ` Johannes Stezenbach
2006-02-27 8:32 ` Russell King
2006-02-27 12:07 ` Johannes Stezenbach
2006-02-27 15:47 ` Russell King
2006-02-27 9:06 ` Matt Mackall
2006-02-25 22:25 ` John Reiser
2006-03-07 23:26 ` H. Peter Anvin
2006-03-10 18:55 ` Matt Mackall
2006-02-24 20:12 ` [PATCH 1/7] inflate pt1: lindent and manual formatting changes Matt Mackall
2006-02-24 20:12 ` [PATCH 6/7] inflate pt1: internalize CRC calculation, cleanup table calculation Matt Mackall
2006-02-24 20:12 ` [PATCH 5/7] inflate pt1: cleanup Huffman table code Matt Mackall
2006-02-24 21:52 ` John Reiser
2006-02-24 22:06 ` Matt Mackall
2006-02-24 20:12 ` [PATCH 7/7] inflate pt1: eliminate memzero usage Matt Mackall
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=5.399206195@selenic.com \
--to=mpm@selenic.com \
--cc=akpm@osdl.org \
--cc=linux-kernel@vger.kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
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.