lkml.org 
[lkml]   [2005]   [Dec]   [22]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
Patch in this message
/
Date
From
Subject[PATCH 4/20] inflate: start moving globals into iostate
inflate: move globals into a state structure

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

Index: 2.6.14/lib/inflate.c
===================================================================
--- 2.6.14.orig/lib/inflate.c 2005-10-28 20:41:17.000000000 -0700
+++ 2.6.14/lib/inflate.c 2005-10-28 21:16:13.000000000 -0700
@@ -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;
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
\
 
 \ /
  Last update: 2005-12-22 19:34    [W:0.131 / U:0.136 seconds]
©2003-2014 Jasper Spaans. Advertise on this site