Changeset View
Changeset View
Standalone View
Standalone View
sys/kern/inflate.c
Show First 20 Lines • Show All 405 Lines • ▼ Show 20 Lines | |||||
/* Given a list of code lengths and a maximum table size, make a set of | /* Given a list of code lengths and a maximum table size, make a set of | ||||
tables to decode that set of codes. Return zero on success, one if | tables to decode that set of codes. Return zero on success, one if | ||||
the given code set is incomplete (the tables are still built in this | the given code set is incomplete (the tables are still built in this | ||||
case), two if the input is invalid (all zero length codes or an | case), two if the input is invalid (all zero length codes or an | ||||
oversubscribed set of lengths), and three if not enough memory. | oversubscribed set of lengths), and three if not enough memory. | ||||
The code with value 256 is special, and the tables are constructed | The code with value 256 is special, and the tables are constructed | ||||
so that no bits beyond that code are fetched when that code is | so that no bits beyond that code are fetched when that code is | ||||
decoded. */ | decoded. */ | ||||
/* | |||||
kib: Might be, add a herald 'arguments' to this and other comments ? | |||||
* b code lengths in bits (all assumed <= BMAX) | |||||
* n number of codes (assumed <= N_MAX) | |||||
* s number of simple-valued codes (0..s-1) | |||||
* d list of base values for non-simple codes | |||||
* e list of extra bits for non-simple codes | |||||
* t result: starting table | |||||
* m maximum lookup bits, returns actual | |||||
*/ | |||||
static int | static int | ||||
huft_build(glbl, b, n, s, d, e, t, m) | huft_build(struct inflate *glbl, unsigned *b, unsigned n, unsigned s, | ||||
struct inflate *glbl; | const ush *d, const ush *e, struct huft **t, int *m) | ||||
unsigned *b; /* code lengths in bits (all assumed <= BMAX) */ | |||||
unsigned n; /* number of codes (assumed <= N_MAX) */ | |||||
unsigned s; /* number of simple-valued codes (0..s-1) */ | |||||
const ush *d; /* list of base values for non-simple codes */ | |||||
const ush *e; /* list of extra bits for non-simple codes */ | |||||
struct huft **t; /* result: starting table */ | |||||
int *m; /* maximum lookup bits, returns actual */ | |||||
{ | { | ||||
unsigned a; /* counter for codes of length k */ | unsigned a; /* counter for codes of length k */ | ||||
unsigned c[BMAX + 1]; /* bit length count table */ | unsigned c[BMAX + 1]; /* bit length count table */ | ||||
unsigned el; /* length of EOB code (value 256) */ | unsigned el; /* length of EOB code (value 256) */ | ||||
unsigned f; /* i repeats in table every f entries */ | unsigned f; /* i repeats in table every f entries */ | ||||
int g; /* maximum code length */ | int g; /* maximum code length */ | ||||
int h; /* table level */ | int h; /* table level */ | ||||
register unsigned i; /* counter, current code */ | register unsigned i; /* counter, current code */ | ||||
▲ Show 20 Lines • Show All 177 Lines • ▼ Show 20 Lines | #endif | ||||
/* return actual size of base table */ | /* return actual size of base table */ | ||||
*m = l[0]; | *m = l[0]; | ||||
/* Return true (1) if we were given an incomplete table */ | /* Return true (1) if we were given an incomplete table */ | ||||
return y != 0 && g != 1; | return y != 0 && g != 1; | ||||
} | } | ||||
/* t table to free */ | |||||
static int | static int | ||||
huft_free(glbl, t) | huft_free(struct inflate *glbl, struct huft *t) | ||||
struct inflate *glbl; | |||||
struct huft *t; /* table to free */ | |||||
/* Free the malloc'ed tables built by huft_build(), which makes a linked | /* Free the malloc'ed tables built by huft_build(), which makes a linked | ||||
list of the tables it made, with the links in a dummy first entry of | list of the tables it made, with the links in a dummy first entry of | ||||
each table. */ | each table. */ | ||||
{ | { | ||||
register struct huft *p, *q; | register struct huft *p, *q; | ||||
/* Go through linked list, freeing from the malloced (t[-1]) address. */ | /* Go through linked list, freeing from the malloced (t[-1]) address. */ | ||||
p = t; | p = t; | ||||
while (p != (struct huft *) NULL) { | while (p != (struct huft *) NULL) { | ||||
q = (--p)->v.t; | q = (--p)->v.t; | ||||
free(p, M_GZIP); | free(p, M_GZIP); | ||||
p = q; | p = q; | ||||
} | } | ||||
return 0; | return 0; | ||||
} | } | ||||
/* inflate (decompress) the codes in a deflated (compressed) block. | /* inflate (decompress) the codes in a deflated (compressed) block. | ||||
Return an error code or zero if it all goes ok. */ | Return an error code or zero if it all goes ok. */ | ||||
/* | |||||
* tl, td literal/length and distance decoder tables | |||||
* bl, bd number of bits decoded by tl[] and td[] | |||||
*/ | |||||
static int | static int | ||||
inflate_codes(glbl, tl, td, bl, bd) | inflate_codes(struct inflate *glbl, struct huft *tl, struct huft*td, int bl, | ||||
struct inflate *glbl; | int bd) | ||||
struct huft *tl, *td;/* literal/length and distance decoder tables */ | |||||
int bl, bd; /* number of bits decoded by tl[] and td[] */ | |||||
{ | { | ||||
register unsigned e; /* table entry flag/number of extra bits */ | register unsigned e; /* table entry flag/number of extra bits */ | ||||
unsigned n, d; /* length and index for copy */ | unsigned n, d; /* length and index for copy */ | ||||
unsigned w; /* current window position */ | unsigned w; /* current window position */ | ||||
struct huft *t; /* pointer to table entry */ | struct huft *t; /* pointer to table entry */ | ||||
unsigned ml, md; /* masks for bl and bd bits */ | unsigned ml, md; /* masks for bl and bd bits */ | ||||
register ulg b; /* bit buffer */ | register ulg b; /* bit buffer */ | ||||
register unsigned k; /* number of bits in bit buffer */ | register unsigned k; /* number of bits in bit buffer */ | ||||
▲ Show 20 Lines • Show All 76 Lines • ▼ Show 20 Lines | #endif /* !NOMEMCPY */ | ||||
glbl->gz_bk = k; | glbl->gz_bk = k; | ||||
/* done */ | /* done */ | ||||
return 0; | return 0; | ||||
} | } | ||||
/* "decompress" an inflated type 0 (stored) block. */ | /* "decompress" an inflated type 0 (stored) block. */ | ||||
static int | static int | ||||
inflate_stored(glbl) | inflate_stored(struct inflate *glbl) | ||||
struct inflate *glbl; | |||||
{ | { | ||||
unsigned n; /* number of bytes in block */ | unsigned n; /* number of bytes in block */ | ||||
unsigned w; /* current window position */ | unsigned w; /* current window position */ | ||||
register ulg b; /* bit buffer */ | register ulg b; /* bit buffer */ | ||||
register unsigned k; /* number of bits in bit buffer */ | register unsigned k; /* number of bits in bit buffer */ | ||||
/* make local copies of globals */ | /* make local copies of globals */ | ||||
b = glbl->gz_bb; /* initialize bit buffer */ | b = glbl->gz_bb; /* initialize bit buffer */ | ||||
Show All 29 Lines | inflate_stored(struct inflate *glbl) | ||||
glbl->gz_bk = k; | glbl->gz_bk = k; | ||||
return 0; | return 0; | ||||
} | } | ||||
/* decompress an inflated type 1 (fixed Huffman codes) block. We should | /* decompress an inflated type 1 (fixed Huffman codes) block. We should | ||||
either replace this with a custom decoder, or at least precompute the | either replace this with a custom decoder, or at least precompute the | ||||
Huffman tables. */ | Huffman tables. */ | ||||
static int | static int | ||||
inflate_fixed(glbl) | inflate_fixed(struct inflate *glbl) | ||||
struct inflate *glbl; | |||||
{ | { | ||||
/* if first time, set up tables for fixed blocks */ | /* if first time, set up tables for fixed blocks */ | ||||
if (glbl->gz_fixed_tl == (struct huft *) NULL) { | if (glbl->gz_fixed_tl == (struct huft *) NULL) { | ||||
int i; /* temporary variable */ | int i; /* temporary variable */ | ||||
static unsigned l[288]; /* length list for huft_build */ | static unsigned l[288]; /* length list for huft_build */ | ||||
/* literal table */ | /* literal table */ | ||||
for (i = 0; i < 144; i++) | for (i = 0; i < 144; i++) | ||||
Show All 24 Lines | if (glbl->gz_fixed_tl == (struct huft *) NULL) { | ||||
} | } | ||||
} | } | ||||
/* decompress until an end-of-block code */ | /* decompress until an end-of-block code */ | ||||
return inflate_codes(glbl, glbl->gz_fixed_tl, glbl->gz_fixed_td, glbl->gz_fixed_bl, glbl->gz_fixed_bd) != 0; | return inflate_codes(glbl, glbl->gz_fixed_tl, glbl->gz_fixed_td, glbl->gz_fixed_bl, glbl->gz_fixed_bd) != 0; | ||||
} | } | ||||
/* decompress an inflated type 2 (dynamic Huffman codes) block. */ | /* decompress an inflated type 2 (dynamic Huffman codes) block. */ | ||||
static int | static int | ||||
inflate_dynamic(glbl) | inflate_dynamic(struct inflate *glbl) | ||||
struct inflate *glbl; | |||||
{ | { | ||||
int i; /* temporary variables */ | int i; /* temporary variables */ | ||||
unsigned j; | unsigned j; | ||||
unsigned l; /* last length */ | unsigned l; /* last length */ | ||||
unsigned m; /* mask for bit lengths table */ | unsigned m; /* mask for bit lengths table */ | ||||
unsigned n; /* number of lengths to get */ | unsigned n; /* number of lengths to get */ | ||||
struct huft *tl; /* literal/length code table */ | struct huft *tl; /* literal/length code table */ | ||||
struct huft *td; /* distance code table */ | struct huft *td; /* distance code table */ | ||||
▲ Show 20 Lines • Show All 127 Lines • ▼ Show 20 Lines | #endif | ||||
/* free the decoding tables, return */ | /* free the decoding tables, return */ | ||||
huft_free(glbl, tl); | huft_free(glbl, tl); | ||||
huft_free(glbl, td); | huft_free(glbl, td); | ||||
return 0; | return 0; | ||||
} | } | ||||
/* decompress an inflated block */ | /* decompress an inflated block */ | ||||
/* e last block flag */ | |||||
static int | static int | ||||
inflate_block(glbl, e) | inflate_block(struct inflate *glbl, int *e) | ||||
struct inflate *glbl; | |||||
int *e; /* last block flag */ | |||||
{ | { | ||||
unsigned t; /* block type */ | unsigned t; /* block type */ | ||||
register ulg b; /* bit buffer */ | register ulg b; /* bit buffer */ | ||||
register unsigned k; /* number of bits in bit buffer */ | register unsigned k; /* number of bits in bit buffer */ | ||||
/* make local bit buffer */ | /* make local bit buffer */ | ||||
b = glbl->gz_bb; | b = glbl->gz_bb; | ||||
k = glbl->gz_bk; | k = glbl->gz_bk; | ||||
Show All 20 Lines | inflate_block(struct inflate *glbl, int *e) | ||||
/* bad block type */ | /* bad block type */ | ||||
return 2; | return 2; | ||||
} | } | ||||
/* decompress an inflated entry */ | /* decompress an inflated entry */ | ||||
static int | static int | ||||
xinflate(glbl) | xinflate(struct inflate *glbl) | ||||
struct inflate *glbl; | |||||
{ | { | ||||
int e; /* last block flag */ | int e; /* last block flag */ | ||||
int r; /* result code */ | int r; /* result code */ | ||||
unsigned h; /* maximum struct huft's malloc'ed */ | unsigned h; /* maximum struct huft's malloc'ed */ | ||||
glbl->gz_fixed_tl = (struct huft *) NULL; | glbl->gz_fixed_tl = (struct huft *) NULL; | ||||
/* initialize window, bit buffer */ | /* initialize window, bit buffer */ | ||||
Show All 15 Lines | xinflate(struct inflate *glbl) | ||||
FLUSH(glbl, glbl->gz_wp); | FLUSH(glbl, glbl->gz_wp); | ||||
/* return success */ | /* return success */ | ||||
return 0; | return 0; | ||||
} | } | ||||
/* Nobody uses this - why not? */ | /* Nobody uses this - why not? */ | ||||
int | int | ||||
inflate(glbl) | inflate(struct inflate *glbl) | ||||
struct inflate *glbl; | |||||
{ | { | ||||
int i; | int i; | ||||
#ifdef _KERNEL | #ifdef _KERNEL | ||||
u_char *p = NULL; | u_char *p = NULL; | ||||
if (!glbl->gz_slide) | if (!glbl->gz_slide) | ||||
p = glbl->gz_slide = malloc(GZ_WSIZE, M_GZIP, M_WAITOK); | p = glbl->gz_slide = malloc(GZ_WSIZE, M_GZIP, M_WAITOK); | ||||
#endif | #endif | ||||
Show All 25 Lines |
Might be, add a herald 'arguments' to this and other comments ?