From patchwork Wed Apr 17 14:37:12 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Daniel P. Smith" X-Patchwork-Id: 13633455 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from lists.xenproject.org (lists.xenproject.org [192.237.175.120]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.lore.kernel.org (Postfix) with ESMTPS id 324ADC4345F for ; Wed, 17 Apr 2024 14:38:18 +0000 (UTC) Received: from list by lists.xenproject.org with outflank-mailman.707557.1105595 (Exim 4.92) (envelope-from ) id 1rx6QK-0005nq-2f; Wed, 17 Apr 2024 14:38:08 +0000 X-Outflank-Mailman: Message body and most headers restored to incoming version Received: by outflank-mailman (output) from mailman id 707557.1105595; Wed, 17 Apr 2024 14:38:08 +0000 Received: from localhost ([127.0.0.1] helo=lists.xenproject.org) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1rx6QJ-0005nj-Vm; Wed, 17 Apr 2024 14:38:07 +0000 Received: by outflank-mailman (input) for mailman id 707557; Wed, 17 Apr 2024 14:38:06 +0000 Received: from se1-gles-sth1-in.inumbo.com ([159.253.27.254] helo=se1-gles-sth1.inumbo.com) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1rx6QI-0005ks-Cr for xen-devel@lists.xenproject.org; Wed, 17 Apr 2024 14:38:06 +0000 Received: from sender4-of-o51.zoho.com (sender4-of-o51.zoho.com [136.143.188.51]) by se1-gles-sth1.inumbo.com (Halon) with ESMTPS id 178e37d3-fcc8-11ee-b909-491648fe20b8; Wed, 17 Apr 2024 16:38:03 +0200 (CEST) Received: by mx.zohomail.com with SMTPS id 1713364647836196.0724817623684; Wed, 17 Apr 2024 07:37:27 -0700 (PDT) X-BeenThere: xen-devel@lists.xenproject.org List-Id: Xen developer discussion List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Errors-To: xen-devel-bounces@lists.xenproject.org Precedence: list Sender: "Xen-devel" X-Inumbo-ID: 178e37d3-fcc8-11ee-b909-491648fe20b8 ARC-Seal: i=1; a=rsa-sha256; t=1713364650; cv=none; d=zohomail.com; s=zohoarc; b=ctw/XfvKKD0jfxZkhH1p+lVjzoY6C1lShQ+jo/hNd6oMgsaWfVs5SG2loh+6xewyTjaKbNlEDVVIVFrxttOIlaocyR5TEGDmnz0vTvnIm8dDqKADzlMh5PJyhVVQudvezDWhdt8la27MgQApDt9HPdj3LZzrZtxih2JQtPgxRDE= ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=zohomail.com; s=zohoarc; t=1713364650; h=Content-Transfer-Encoding:Cc:Cc:Date:Date:From:From:In-Reply-To:MIME-Version:Message-ID:References:Subject:Subject:To:To:Message-Id:Reply-To; bh=OSlGTQqiRvDxNXJj4MQvDl51HgeA28F6MudGkNCE6Yw=; b=kTnf9+enC8y2kp+HlwUOlZgF5VPXrKuYjo8ZXBxd2Fl5WhRjnZ4ZNIK+WwLTXRqoydM9WXfO9L46xtKnem51zKfVNqBPTqr164jlB+6RsdQtIOTpYwXqBbUWyxCcbc+KpSiDr9ZP1Db/oqASeYig7Av7CDTAtmQcmB3NPEwx99Y= ARC-Authentication-Results: i=1; mx.zohomail.com; dkim=pass header.i=apertussolutions.com; spf=pass smtp.mailfrom=dpsmith@apertussolutions.com; dmarc=pass header.from= DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; t=1713364650; s=zoho; d=apertussolutions.com; i=dpsmith@apertussolutions.com; h=From:From:To:To:Cc:Cc:Subject:Subject:Date:Date:Message-Id:Message-Id:In-Reply-To:References:MIME-Version:Content-Transfer-Encoding:Reply-To; bh=OSlGTQqiRvDxNXJj4MQvDl51HgeA28F6MudGkNCE6Yw=; b=SJo9C6d3LSIo8nIXpqUa9Shq2suQT8JOEIDdUqES7yFT4fIZdZrGD2yCO6GFpGXv J8OUiQqnShrnB/WxJYZLUB16irBZmFlbK6bVkkwTZ5tupCsNRlfitAiVQbnq0DVOyY6 70P56xFgE57YrTpOr3tmXP0Xd/U4epQdN7yeyPl8= From: "Daniel P. Smith" To: xen-devel@lists.xenproject.org Cc: Jason Andryuk , "Daniel P. Smith" , Andrew Cooper , George Dunlap , Jan Beulich , Julien Grall , Stefano Stabellini Subject: [PATCH v2 2/6] gzip: clean up comments and fix code alignment Date: Wed, 17 Apr 2024 10:37:12 -0400 Message-Id: <20240417143716.27189-3-dpsmith@apertussolutions.com> X-Mailer: git-send-email 2.30.2 In-Reply-To: <20240417143716.27189-1-dpsmith@apertussolutions.com> References: <20240417143716.27189-1-dpsmith@apertussolutions.com> MIME-Version: 1.0 X-ZohoMailClient: External This commit cleans up the comments and fixes the code alignment using Xen coding style. This is done to make the code more legible before refactoring. Signed-off-by: Daniel P. Smith --- xen/common/gzip/gunzip.c | 10 +- xen/common/gzip/inflate.c | 790 +++++++++++++++++++------------------- 2 files changed, 405 insertions(+), 395 deletions(-) diff --git a/xen/common/gzip/gunzip.c b/xen/common/gzip/gunzip.c index 2c6eae167d54..1bcb007395ba 100644 --- a/xen/common/gzip/gunzip.c +++ b/xen/common/gzip/gunzip.c @@ -63,7 +63,6 @@ static __init int fill_inbuf(void) return 0; } - #include "inflate.c" static __init void flush_window(void) @@ -137,3 +136,12 @@ __init int perform_gunzip(char *output, char *image, unsigned long image_len) return rc; } + +/* + * Local variables: + * mode: C + * c-file-style: "BSD" + * c-basic-offset: 4 + * indent-tabs-mode: nil + * End: + */ diff --git a/xen/common/gzip/inflate.c b/xen/common/gzip/inflate.c index e95db2de4d9b..73ccfc2bdc6c 100644 --- a/xen/common/gzip/inflate.c +++ b/xen/common/gzip/inflate.c @@ -1,11 +1,13 @@ #define DEBG(x) #define DEBG1(x) -/* inflate.c -- Not copyrighted 1992 by Mark Adler - version c10p1, 10 January 1993 */ +/* + * inflate.c -- Not copyrighted 1992 by Mark Adler + * version c10p1, 10 January 1993 + */ -/* +/* * Adapted for booting Linux by Hannu Savolainen 1993 - * based on gzip-1.0.3 + * based on gzip-1.0.3 * * Nicolas Pitre , 1999/04/14 : * Little mods for all variable to reside either into rodata or bss segments @@ -15,92 +17,91 @@ */ /* - Inflate deflated (PKZIP's method 8 compressed) data. The compression - method searches for as much of the current string of bytes (up to a - length of 258) in the previous 32 K bytes. If it doesn't find any - matches (of at least length 3), it codes the next byte. Otherwise, it - codes the length of the matched string and its distance backwards from - the current position. There is a single Huffman code that codes both - single bytes (called "literals") and match lengths. A second Huffman - code codes the distance information, which follows a length code. Each - length or distance code actually represents a base value and a number - of "extra" (sometimes zero) bits to get to add to the base value. At - the end of each deflated block is a special end-of-block (EOB) literal/ - length code. The decoding process is basically: get a literal/length - code; if EOB then done; if a literal, emit the decoded byte; if a - length then get the distance and emit the referred-to bytes from the - sliding window of previously emitted data. - - There are (currently) three kinds of inflate blocks: stored, fixed, and - dynamic. The compressor deals with some chunk of data at a time, and - decides which method to use on a chunk-by-chunk basis. A chunk might - typically be 32 K or 64 K. If the chunk is incompressible, then the - "stored" method is used. In this case, the bytes are simply stored as - is, eight bits per byte, with none of the above coding. The bytes are - preceded by a count, since there is no longer an EOB code. - - If the data is compressible, then either the fixed or dynamic methods - are used. In the dynamic method, the compressed data is preceded by - an encoding of the literal/length and distance Huffman codes that are - to be used to decode this block. The representation is itself Huffman - coded, and so is preceded by a description of that code. These code - descriptions take up a little space, and so for small blocks, there is - a predefined set of codes, called the fixed codes. The fixed method is - used if the block codes up smaller that way (usually for quite small - chunks), otherwise the dynamic method is used. In the latter case, the - codes are customized to the probabilities in the current block, and so - can code it much better than the pre-determined fixed codes. - - The Huffman codes themselves are decoded using a multi-level table - lookup, in order to maximize the speed of decoding plus the speed of - building the decoding tables. See the comments below that precede the - lbits and dbits tuning parameters. + * Inflate deflated (PKZIP's method 8 compressed) data. The compression + * method searches for as much of the current string of bytes (up to a + * length of 258) in the previous 32 K bytes. If it doesn't find any + * matches (of at least length 3), it codes the next byte. Otherwise, it + * codes the length of the matched string and its distance backwards from + * the current position. There is a single Huffman code that codes both + * single bytes (called "literals") and match lengths. A second Huffman + * code codes the distance information, which follows a length code. Each + * length or distance code actually represents a base value and a number + * of "extra" (sometimes zero) bits to get to add to the base value. At + * the end of each deflated block is a special end-of-block (EOB) literal/ + * length code. The decoding process is basically: get a literal/length + * code; if EOB then done; if a literal, emit the decoded byte; if a + * length then get the distance and emit the referred-to bytes from the + * sliding window of previously emitted data. + * + * There are (currently) three kinds of inflate blocks: stored, fixed, and + * dynamic. The compressor deals with some chunk of data at a time, and + * decides which method to use on a chunk-by-chunk basis. A chunk might + * typically be 32 K or 64 K. If the chunk is incompressible, then the + * "stored" method is used. In this case, the bytes are simply stored as + * is, eight bits per byte, with none of the above coding. The bytes are + * preceded by a count, since there is no longer an EOB code. + * + * If the data is compressible, then either the fixed or dynamic methods + * are used. In the dynamic method, the compressed data is preceded by + * an encoding of the literal/length and distance Huffman codes that are + * to be used to decode this block. The representation is itself Huffman + * coded, and so is preceded by a description of that code. These code + * descriptions take up a little space, and so for small blocks, there is + * a predefined set of codes, called the fixed codes. The fixed method is + * used if the block codes up smaller that way (usually for quite small + * chunks), otherwise the dynamic method is used. In the latter case, the + * codes are customized to the probabilities in the current block, and so + * can code it much better than the pre-determined fixed codes. + * + * The Huffman codes themselves are decoded using a multi-level table + * lookup, in order to maximize the speed of decoding plus the speed of + * building the decoding tables. See the comments below that precede the + * lbits and dbits tuning parameters. */ - /* - Notes beyond the 1.93a appnote.txt: - - 1. Distance pointers never point before the beginning of the output - stream. - 2. Distance pointers can point back across blocks, up to 32k away. - 3. There is an implied maximum of 7 bits for the bit length table and - 15 bits for the actual data. - 4. If only one code exists, then it is encoded using one bit. (Zero - would be more efficient, but perhaps a little confusing.) If two - codes exist, they are coded using one bit each (0 and 1). - 5. There is no way of sending zero distance codes--a dummy must be - sent if there are none. (History: a pre 2.0 version of PKZIP would - store blocks with no distance codes, but this was discovered to be - too harsh a criterion.) Valid only for 1.93a. 2.04c does allow - zero distance codes, which is sent as one code of zero bits in - length. - 6. There are up to 286 literal/length codes. Code 256 represents the - end-of-block. Note however that the static length tree defines - 288 codes just to fill out the Huffman codes. Codes 286 and 287 - cannot be used though, since there is no length base or extra bits - defined for them. Similarly, there are up to 30 distance codes. - However, static trees define 32 codes (all 5 bits) to fill out the - Huffman codes, but the last two had better not show up in the data. - 7. Unzip can check dynamic Huffman blocks for complete code sets. - The exception is that a single code would not be complete (see #4). - 8. The five bits following the block type is really the number of - literal codes sent minus 257. - 9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits - (1+6+6). Therefore, to output three times the length, you output - three codes (1+1+1), whereas to output four times the same length, - you only need two codes (1+3). Hmm. - 10. In the tree reconstruction algorithm, Code = Code + Increment - only if BitLength(i) is not zero. (Pretty obvious.) - 11. Correction: 4 Bits: # of Bit Length codes - 4 (4 - 19) - 12. Note: length code 284 can represent 227-258, but length code 285 - really is 258. The last length deserves its own, short code - since it gets used a lot in very redundant files. The length - 258 is special since 258 - 3 (the min match length) is 255. - 13. The literal/length and distance code bit lengths are read as a - single stream of lengths. It is possible (and advantageous) for - a repeat code (16, 17, or 18) to go across the boundary between - the two sets of lengths. + * Notes beyond the 1.93a appnote.txt: + * + * 1. Distance pointers never point before the beginning of the output + * stream. + * 2. Distance pointers can point back across blocks, up to 32k away. + * 3. There is an implied maximum of 7 bits for the bit length table and + * 15 bits for the actual data. + * 4. If only one code exists, then it is encoded using one bit. (Zero + * would be more efficient, but perhaps a little confusing.) If two + * codes exist, they are coded using one bit each (0 and 1). + * 5. There is no way of sending zero distance codes--a dummy must be + * sent if there are none. (History: a pre 2.0 version of PKZIP would + * store blocks with no distance codes, but this was discovered to be + * too harsh a criterion.) Valid only for 1.93a. 2.04c does allow + * zero distance codes, which is sent as one code of zero bits in + * length. + * 6. There are up to 286 literal/length codes. Code 256 represents the + * end-of-block. Note however that the static length tree defines + * 288 codes just to fill out the Huffman codes. Codes 286 and 287 + * cannot be used though, since there is no length base or extra bits + * defined for them. Similarly, there are up to 30 distance codes. + * However, static trees define 32 codes (all 5 bits) to fill out the + * Huffman codes, but the last two had better not show up in the data. + * 7. Unzip can check dynamic Huffman blocks for complete code sets. + * The exception is that a single code would not be complete (see #4). + * 8. The five bits following the block type is really the number of + * literal codes sent minus 257. + * 9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits + * (1+6+6). Therefore, to output three times the length, you output + * three codes (1+1+1), whereas to output four times the same length, + * you only need two codes (1+3). Hmm. + * 10. In the tree reconstruction algorithm, Code = Code + Increment + * only if BitLength(i) is not zero. (Pretty obvious.) + * 11. Correction: 4 Bits: # of Bit Length codes - 4 (4 - 19) + * 12. Note: length code 284 can represent 227-258, but length code 285 + * really is 258. The last length deserves its own, short code + * since it gets used a lot in very redundant files. The length + * 258 is special since 258 - 3 (the min match length) is 255. + * 13. The literal/length and distance code bit lengths are read as a + * single stream of lengths. It is possible (and advantageous) for + * a repeat code (16, 17, or 18) to go across the boundary between + * the two sets of lengths. */ #ifdef RCSID @@ -120,13 +121,15 @@ static char rcsid[] = "#Id: inflate.c,v 0.14 1993/06/10 13:27:04 jloup Exp #"; #define slide window -/* Huffman code lookup table entry--this entry is four bytes for machines - that have 16-bit pointers (e.g. PC's in the small or medium model). - Valid extra bits are 0..13. e == 15 is EOB (end of block), e == 16 - means that v is a literal, 16 < e < 32 means that v is a pointer to - the next table, which codes e - 16 bits, and lastly e == 99 indicates - an unused code. If a code with e == 99 is looked up, this implies an - error in the data. */ +/* + * Huffman code lookup table entry--this entry is four bytes for machines + * that have 16-bit pointers (e.g. PC's in the small or medium model). + * Valid extra bits are 0..13. e == 15 is EOB (end of block), e == 16 + * means that v is a literal, 16 < e < 32 means that v is a pointer to + * the next table, which codes e - 16 bits, and lastly e == 99 indicates + * an unused code. If a code with e == 99 is looked up, this implies an + * error in the data. + */ struct huft { uch e; /* number of extra bits or operation */ uch b; /* number of bits in this code or subcode */ @@ -136,7 +139,6 @@ struct huft { } v; }; - /* Function prototypes */ static int huft_build OF((unsigned *, unsigned, unsigned, const ush *, const ush *, struct huft **, int *)); @@ -148,15 +150,17 @@ static int inflate_dynamic OF((void)); static int inflate_block OF((int *)); static int inflate OF((void)); - -/* 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 - circular buffer. The index is updated simply by incrementing and then - ANDing with 0x7fff (32K-1). */ -/* It is left to other modules to supply the 32 K area. It is assumed - to be usable as if it were declared "uch slide[32768];" or as just - "uch *slide;" and then malloc'ed in the latter case. The definition - must be in unzip.h, included above. */ +/* + * 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 + * circular buffer. The index is updated simply by incrementing and then + * ANDing with 0x7fff (32K-1). + * + * It is left to other modules to supply the 32 K area. It is assumed + * to be usable as if it were declared "uch slide[32768];" or as just + * "uch *slide;" and then malloc'ed in the latter case. The definition + * must be in unzip.h, included above. + */ /* unsigned wp; current position in slide */ #define wp outcnt #define flush_output(w) (wp=(w),flush_window()) @@ -180,36 +184,35 @@ static const ush cpdext[] = { /* Extra bits for distance codes */ 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13}; - - -/* Macros 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 register - variables for speed, and are initialized at the beginning of a - routine that uses these macros from a global bit buffer and count. - - 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. - - 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. - (The EOB code is shorter than other codes because fixed blocks are - generally short. So, while a block always has an EOB, many other - literal/length codes have a significantly lower probability of - showing up at all.) However, by making the first table have a - lookup of seven bits, the EOB code will be found in that first - lookup, and so will not require that too many bits be pulled from - the stream. +/* + * Macros 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 register + * variables for speed, and are initialized at the beginning of a + * routine that uses these macros from a global bit buffer and count. + * + * 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. + * + * 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. + * (The EOB code is shorter than other codes because fixed blocks are + * generally short. So, while a block always has an EOB, many other + * literal/length codes have a significantly lower probability of + * showing up at all.) However, by making the first table have a + * lookup of seven bits, the EOB code will be found in that first + * lookup, and so will not require that too many bits be pulled from + * the stream. */ static ulg __initdata bb; /* bit buffer */ @@ -226,7 +229,8 @@ static const ush mask_bits[] = { #define DUMPBITS(n) {b>>=(n);k-=(n);} #ifndef NO_INFLATE_MALLOC -/* A trivial malloc implementation, adapted from +/* + * A trivial malloc implementation, adapted from * malloc by Hannu Savolainen 1993 and Matthias Urlichs 1994 */ @@ -272,64 +276,64 @@ static void __init free(void *where) #endif /* - Huffman code decoding is performed using a multi-level table lookup. - The fastest way to decode is to simply build a lookup table whose - size is determined by the longest code. However, the time it takes - to build this table can also be a factor if the data being decoded - is not very long. The most common codes are necessarily the - shortest codes, so those codes dominate the decoding time, and hence - the speed. The idea is you can have a shorter table that decodes the - shorter, more probable codes, and then point to subsidiary tables for - the longer codes. The time it costs to decode the longer codes is - then traded against the time it takes to make longer tables. - - This results of this trade are in the variables lbits and dbits - below. lbits is the number of bits the first level table for literal/ - length codes can decode in one step, and dbits is the same thing for - the distance codes. Subsequent tables are also less than or equal to - those sizes. These values may be adjusted either when all of the - codes are shorter than that, in which case the longest code length in - bits is used, or when the shortest code is *longer* than the requested - table size, in which case the length of the shortest code in bits is - used. - - There are two different values for the two tables, since they code a - different number of possibilities each. The literal/length table - codes 286 possible values, or in a flat code, a little over eight - bits. The distance table codes 30 possible values, or a little less - than five bits, flat. The optimum values for speed end up being - about one bit more than those, so lbits is 8+1 and dbits is 5+1. - The optimum values may differ though from machine to machine, and - possibly even between compilers. Your mileage may vary. + * Huffman code decoding is performed using a multi-level table lookup. + * The fastest way to decode is to simply build a lookup table whose + * size is determined by the longest code. However, the time it takes + * to build this table can also be a factor if the data being decoded + * is not very long. The most common codes are necessarily the + * shortest codes, so those codes dominate the decoding time, and hence + * the speed. The idea is you can have a shorter table that decodes the + * shorter, more probable codes, and then point to subsidiary tables for + * the longer codes. The time it costs to decode the longer codes is + * then traded against the time it takes to make longer tables. + * + * This results of this trade are in the variables lbits and dbits + * below. lbits is the number of bits the first level table for literal/ + * length codes can decode in one step, and dbits is the same thing for + * the distance codes. Subsequent tables are also less than or equal to + * those sizes. These values may be adjusted either when all of the + * codes are shorter than that, in which case the longest code length in + * bits is used, or when the shortest code is *longer* than the requested + * table size, in which case the length of the shortest code in bits is + * used. + * + * There are two different values for the two tables, since they code a + * different number of possibilities each. The literal/length table + * codes 286 possible values, or in a flat code, a little over eight + * bits. The distance table codes 30 possible values, or a little less + * than five bits, flat. The optimum values for speed end up being + * about one bit more than those, so lbits is 8+1 and dbits is 5+1. + * The optimum values may differ though from machine to machine, and + * possibly even between compilers. Your mileage may vary. */ - static const int lbits = 9; /* bits in base literal/length lookup table */ static const int dbits = 6; /* bits in base distance lookup table */ - /* If BMAX needs to be larger than 16, then h and x[] should be ulg. */ #define BMAX 16 /* maximum bit length of any code (16 for explode) */ #define N_MAX 288 /* maximum number of codes in any set */ - static unsigned __initdata hufts; /* track memory usage */ - +/* + * 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 + * 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 + * oversubscribed set of lengths), and three if not enough memory. + * + * @param b Code lengths in bits (all assumed <= BMAX) + * @param n Number of codes (assumed <= N_MAX) + * @param s Number of simple-valued codes (0..s-1) + * @param d List of base values for non-simple codes + * @param e List of extra bits for non-simple codes + * @param t Result: starting table + * @param m Maximum lookup bits, returns actual + */ static int __init huft_build( - 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 */ - ) -/* 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 - 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 - oversubscribed set of lengths), and three if not enough memory. */ + unsigned *b, unsigned n, unsigned s, const ush *d, const ush *e, + struct huft **t, int *m) { unsigned a; /* counter for codes of length k */ unsigned f; /* i repeats in table every f entries */ @@ -371,7 +375,7 @@ static int __init huft_build( memzero(stk->c, sizeof(stk->c)); p = b; i = n; do { - Tracecv(*p, (stderr, (n-i >= ' ' && n-i <= '~' ? "%c %d\n" : "0x%x %d\n"), + Tracecv(*p, (stderr, (n-i >= ' ' && n-i <= '~' ? "%c %d\n" : "0x%x %d\n"), n-i, *p)); c[*p]++; /* assume all entries <= BMAX */ p++; /* Can't combine with above line (Solaris bug) */ @@ -559,14 +563,13 @@ static int __init huft_build( return ret; } - - -static int __init huft_free( - struct huft *t /* table to free */ - ) /* 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 - each table. */ + * list of the tables it made, with the links in a dummy first entry of + * each table. + * + * @param t Table to free + */ +static int __init huft_free(struct huft *t) { register struct huft *p, *q; @@ -578,19 +581,21 @@ static int __init huft_free( q = (--p)->v.t; free((char*)p); p = q; - } + } return 0; } - +/* + * inflate (decompress) the codes in a deflated (compressed) block. + * Return an error code or zero if it all goes ok. + * + * @param huft tl Literal/length decoder tables + * @param huft td Distance decoder tables + * @param bl Number of bits decoded by tl[] + * @param bd Number of bits decoded by td[] + */ static int __init inflate_codes( - struct huft *tl, /* literal/length decoder tables */ - struct huft *td, /* distance decoder tables */ - int bl, /* number of bits decoded by tl[] */ - int bd /* number of bits decoded by td[] */ - ) -/* inflate (decompress) the codes in a deflated (compressed) block. - Return an error code or zero if it all goes ok. */ + struct huft *tl, struct huft *td, int bl, int bd) { register unsigned e; /* table entry flag/number of extra bits */ unsigned n, d; /* length and index for copy */ @@ -611,77 +616,76 @@ static int __init inflate_codes( md = mask_bits[bd]; for (;;) /* do until end of block */ { - NEEDBITS((unsigned)bl) - if ((e = (t = tl + ((unsigned)b & ml))->e) > 16) + 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); + if (e == 16) /* then it's a literal */ + { + slide[w++] = (uch)t->v.n; + Tracevv((stderr, "%c", slide[w-1])); + if (w == WSIZE) + { + flush_output(w); + w = 0; + } + } + else /* it's an EOB or a length */ + { + /* exit if end of block */ + if (e == 15) + break; + + /* get length of block to copy */ + NEEDBITS(e); + n = t->v.n + ((unsigned)b & mask_bits[e]); + DUMPBITS(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) - if (e == 16) /* then it's a literal */ - { - slide[w++] = (uch)t->v.n; - Tracevv((stderr, "%c", slide[w-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); + Tracevv((stderr,"\\[%d,%d]", w-d, n)); + + /* do the copy */ + do { + n -= (e = (e = WSIZE - ((d &= WSIZE-1) > w ? d : w)) > n ? n : e); + if (w - d >= e) /* (this test assumes unsigned comparison) */ + { + memcpy(slide + w, slide + d, e); + w += e; + d += e; + } + else /* do it slow to avoid memcpy() overlap */ + do { + slide[w++] = slide[d++]; + Tracevv((stderr, "%c", slide[w-1])); + } while (--e); if (w == WSIZE) { flush_output(w); w = 0; } - } - else /* it's an EOB or a length */ - { - /* exit if end of block */ - if (e == 15) - break; - - /* get length of block to copy */ - NEEDBITS(e) - n = t->v.n + ((unsigned)b & mask_bits[e]); - DUMPBITS(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) - Tracevv((stderr,"\\[%d,%d]", w-d, n)); - - /* do the copy */ - do { - n -= (e = (e = WSIZE - ((d &= WSIZE-1) > w ? d : w)) > n ? n : e); - if (w - d >= e) /* (this test assumes unsigned comparison) */ - { - memcpy(slide + w, slide + d, e); - w += e; - d += e; - } - else /* do it slow to avoid memcpy() overlap */ - do { - slide[w++] = slide[d++]; - Tracevv((stderr, "%c", slide[w-1])); - } while (--e); - if (w == WSIZE) - { - flush_output(w); - w = 0; - } - } while (n); - } + } while (n); + } } - /* restore the globals from the locals */ wp = w; /* restore global window pointer */ bb = b; /* restore global bit buffer */ @@ -694,10 +698,8 @@ static int __init inflate_codes( return 4; /* Input underrun */ } - - -static int __init inflate_stored(void) /* "decompress" an inflated type 0 (stored) block. */ +static int __init inflate_stored(void) { unsigned n; /* number of bytes in block */ unsigned w; /* current window position */ @@ -718,28 +720,26 @@ static int __init inflate_stored(void) /* get the length and its complement */ - NEEDBITS(16) - n = ((unsigned)b & 0xffff); - DUMPBITS(16) - NEEDBITS(16) - if (n != (unsigned)((~b) & 0xffff)) - return 1; /* error in compressed data */ - DUMPBITS(16) - - - /* read and output the compressed data */ - while (n--) + NEEDBITS(16); + n = ((unsigned)b & 0xffff); + DUMPBITS(16); + NEEDBITS(16); + if (n != (unsigned)((~b) & 0xffff)) + return 1; /* error in compressed data */ + DUMPBITS(16); + + /* read and output the compressed data */ + while (n--) + { + NEEDBITS(8); + slide[w++] = (uch)b; + if (w == WSIZE) { - NEEDBITS(8) - slide[w++] = (uch)b; - if (w == WSIZE) - { - flush_output(w); - w = 0; - } - DUMPBITS(8) - } - + flush_output(w); + w = 0; + } + DUMPBITS(8); + } /* restore the globals from the locals */ wp = w; /* restore global window pointer */ @@ -757,10 +757,13 @@ static int __init inflate_stored(void) /* * We use `noinline' here to prevent gcc-3.5 from using too much stack space */ + +/* + * decompress an inflated type 1 (fixed Huffman codes) block. We should + * either replace this with a custom decoder, or at least precompute the + * Huffman tables. + */ static int noinline __init inflate_fixed(void) -/* decompress an inflated type 1 (fixed Huffman codes) block. We should - either replace this with a custom decoder, or at least precompute the - Huffman tables. */ { int i; /* temporary variable */ struct huft *tl; /* literal/length code table */ @@ -803,7 +806,6 @@ static int noinline __init inflate_fixed(void) return i; } - /* decompress until an end-of-block code */ if (inflate_codes(tl, td, bl, bd)) { free(l); @@ -817,12 +819,12 @@ static int noinline __init inflate_fixed(void) return 0; } - /* * We use `noinline' here to prevent gcc-3.5 from using too much stack space */ -static int noinline __init inflate_dynamic(void) + /* decompress an inflated type 2 (dynamic Huffman codes) block. */ +static int noinline __init inflate_dynamic(void) { int i; /* temporary variables */ unsigned j; @@ -852,32 +854,31 @@ static int noinline __init inflate_dynamic(void) b = bb; 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) - if (nl > 286 || nd > 30) - { - ret = 1; /* bad lengths */ - goto out; - } + 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); + if (nl > 286 || nd > 30) + { + ret = 1; /* bad lengths */ + goto out; + } DEBG("dyn1 "); /* read in bit-length-code lengths */ for (j = 0; j < nb; j++) { - NEEDBITS(3) - ll[border[j]] = (unsigned)b & 7; - DUMPBITS(3) - } + NEEDBITS(3); + ll[border[j]] = (unsigned)b & 7; + DUMPBITS(3); + } for (; j < 19; j++) ll[border[j]] = 0; @@ -901,46 +902,46 @@ static int noinline __init inflate_dynamic(void) i = l = 0; while ((unsigned)i < n) { - NEEDBITS((unsigned)bl) - j = (td = tl + ((unsigned)b & m))->b; - DUMPBITS(j) - j = td->v.n; + NEEDBITS((unsigned)bl); + j = (td = tl + ((unsigned)b & m))->b; + DUMPBITS(j); + 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) { - ret = 1; - goto out; - } + NEEDBITS(2); + j = 3 + ((unsigned)b & 3); + DUMPBITS(2); + if ((unsigned)i + j > n) { + ret = 1; + goto out; + } while (j--) - ll[i++] = l; + ll[i++] = l; } else if (j == 17) /* 3 to 10 zero length codes */ { - NEEDBITS(3) - j = 3 + ((unsigned)b & 7); - DUMPBITS(3) - if ((unsigned)i + j > n) { - ret = 1; - goto out; - } + NEEDBITS(3); + j = 3 + ((unsigned)b & 7); + DUMPBITS(3); + if ((unsigned)i + j > n) { + ret = 1; + goto out; + } 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) - if ((unsigned)i + j > n) { - ret = 1; - goto out; - } + NEEDBITS(7); + j = 11 + ((unsigned)b & 0x7f); + DUMPBITS(7); + if ((unsigned)i + j > n) { + ret = 1; + goto out; + } while (j--) ll[i++] = 0; l = 0; @@ -979,67 +980,64 @@ static int noinline __init inflate_dynamic(void) DEBG("dyn5d "); if (i == 1) { error("incomplete distance tree"); - huft_free(td); + huft_free(td); + } + huft_free(tl); + ret = i; /* incomplete code set */ + goto out; } - huft_free(tl); - ret = i; /* incomplete code set */ - goto out; -} -DEBG("dyn6 "); + DEBG("dyn6 "); - /* decompress until an end-of-block code */ -if (inflate_codes(tl, td, bl, bd)) { - ret = 1; - goto out; -} + /* decompress until an end-of-block code */ + if (inflate_codes(tl, td, bl, bd)) { + ret = 1; + goto out; + } -DEBG("dyn7 "); + DEBG("dyn7 "); - /* free the decoding tables, return */ -huft_free(tl); -huft_free(td); + /* free the decoding tables, return */ + huft_free(tl); + huft_free(td); -DEBG(">"); -ret = 0; -out: -free(ll); -return ret; + DEBG(">"); + ret = 0; + out: + free(ll); + return ret; -underrun: -ret = 4; /* Input underrun */ -goto out; + underrun: + ret = 4; /* Input underrun */ + goto out; } - - -static int __init inflate_block( -int *e /* last block flag */ -) -/* decompress an inflated block */ +/* + * decompress an inflated block + * + * @param e Last block flag + */ +static int __init inflate_block(int *e) { -unsigned t; /* block type */ -register ulg b; /* bit buffer */ -register unsigned k; /* number of bits in bit buffer */ - -DEBG(""); /* bad block type */ return 2; - underrun: + underrun: return 4; /* Input underrun */ } - - -static int __init inflate(void) /* decompress an inflated entry */ +static int __init inflate(void) { int e; /* last block flag */ int r; /* result code */ @@ -1076,7 +1072,6 @@ static int __init inflate(void) bk = 0; bb = 0; - /* decompress until the last block */ h = 0; do { @@ -1102,7 +1097,6 @@ static int __init inflate(void) /* flush out slide */ flush_output(wp); - /* return success */ #ifdef DEBUG fprintf(stderr, "<%u> ", h); @@ -1121,12 +1115,11 @@ static ulg __initdata crc; /* initialized in makecrc() so it'll reside in bss * #define CRC_VALUE (crc ^ 0xffffffffUL) /* - * Code to compute the CRC-32 table. Borrowed from + * Code to compute the CRC-32 table. Borrowed from * gzip-1.0.3/makecrc.c. */ -static void __init -makecrc(void) +static void __init makecrc(void) { /* Not copyrighted 1990 Mark Adler */ @@ -1229,7 +1222,7 @@ static int __init gunzip(void) if ((flags & ORIG_NAME) != 0) { /* Discard the old name */ while (NEXTBYTE() != 0) /* null */ ; - } + } /* Discard file comment if any */ if ((flags & COMMENT) != 0) { @@ -1258,7 +1251,7 @@ static int __init gunzip(void) } return -1; } - + /* Get the crc and original length */ /* crc32 (see algorithm.doc) * uncompressed input size modulo 2^32 @@ -1267,12 +1260,12 @@ static int __init gunzip(void) orig_crc |= (ulg) NEXTBYTE() << 8; orig_crc |= (ulg) NEXTBYTE() << 16; orig_crc |= (ulg) NEXTBYTE() << 24; - + orig_len = (ulg) NEXTBYTE(); orig_len |= (ulg) NEXTBYTE() << 8; orig_len |= (ulg) NEXTBYTE() << 16; orig_len |= (ulg) NEXTBYTE() << 24; - + /* Validate decompression */ if (orig_crc != CRC_VALUE) { error("crc error"); @@ -1288,3 +1281,12 @@ static int __init gunzip(void) error("out of input data"); return -1; } + +/* + * Local variables: + * mode: C + * c-file-style: "BSD" + * c-basic-offset: 4 + * indent-tabs-mode: nil + * End: + */