{"thread":{"id":"7267","subject":"Re: cleaner/better zlib sources?","startedAt":"2007-03-16T06:08:41Z","lastAt":"2007-03-16T22:45:42Z","messageCount":6,"participants":["linux@horizon.com","Florian Weimer","Linus Torvalds","Josef Weidendorfer"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"37207","messageId":"20070316060841.19946.qmail@science.horizon.com","threadId":"7267","inReplyTo":null,"subject":"Re: cleaner/better zlib sources?","fromName":"","fromEmail":"linux@horizon.com","sentAt":"2007-03-16T06:08:41Z","receivedAt":"2007-03-16T06:08:41Z","isPatch":false,"sender":{"key":"linux@horizon.com","avatar":null},"body":"Er, it's a little hard to see, but zlib spends the bulk of its time\nin inflate_fast().  This is the fast path, invoked as long as there's\nat least 6 bytes of input and 258 bytes of output space available.\n\nThe code in inflate.c just handles the last few bytes when near\none limit or the other.  Are you sure it's a performance problem?\n\n\nThere's equivalent inflate code in the PGP 5.0i distribution\n(src/lib/pgp/compress/pgpZInflate.c) that's in the public domain AFAICT\n(it says \"Not copyrighted\", and \"You can do whatever you like with this\nsource file, though I would prefer that if you modify it and redistribute\nit that you include comments to that effect with your name and the\ndate.\"), and uses switch statements only for resuming after a pause.\n\nIt's presumably well tested, but it's got a strong nasty-old-MSDOS\ncode smell about it, some truly bizarre indenting (don't look at lines\n1118-1126 with a full stomach), and would require a lot of massaging to\nintegrate with zlib.\n"},{"id":"37227","messageId":"87zm6dl8vw.fsf@mid.deneb.enyo.de","threadId":"7267","inReplyTo":"20070316060841.19946.qmail@science.horizon.com","subject":"Re: cleaner/better zlib sources?","fromName":"Florian Weimer","fromEmail":"fw@deneb.enyo.de","sentAt":"2007-03-16T11:34:27Z","receivedAt":"2007-03-16T11:34:27Z","isPatch":false,"sender":{"key":"fw@deneb.enyo.de","avatar":null},"body":"> There's equivalent inflate code in the PGP 5.0i distribution\n> (src/lib/pgp/compress/pgpZInflate.c) that's in the public domain AFAICT\n\nIt's an early fork from zlib.  gzip contains a copy, too.\n"},{"id":"37250","messageId":"200703161651.17478.Josef.Weidendorfer@gmx.de","threadId":"7267","inReplyTo":"20070316060841.19946.qmail@science.horizon.com","subject":"Re: cleaner/better zlib sources?","fromName":"Josef Weidendorfer","fromEmail":"josef.weidendorfer@gmx.de","sentAt":"2007-03-16T15:51:17Z","receivedAt":"2007-03-16T15:51:17Z","isPatch":false,"sender":{"key":"josef.weidendorfer@gmx.de","avatar":null},"body":"On Friday 16 March 2007, linux@horizon.com wrote:\n> Er, it's a little hard to see, but zlib spends the bulk of its time\n> in inflate_fast().  This is the fast path, invoked as long as there's\n> at least 6 bytes of input and 258 bytes of output space available.\n\nHmm...\n\nWhen running \"git log >/dev/null\" a few times on my Pentium-M here,\nI get the following from oprofile:\n\nCPU: PIII, speed 1600 MHz (estimated)\nCounted CPU_CLK_UNHALTED events (clocks processor is not halted) with a unit mask of 0x00 (No unit mask) count 100000\nCounted INST_RETIRED events (number of instructions retired) with a unit mask of 0x00 (No unit mask) count 400000\nsamples  %        samples  %        image name               app name                 symbol name\n12816    19.6492  3221     19.0772  libz.so.1.2.3            git-log                  inflate_table\n12186    18.6833  3640     21.5589  libz.so.1.2.3            git-log                  inflate\n5228      8.0155  1395      8.2623  libz.so.1.2.3            git-log                  inflate_fast\n3855      5.9104  738       4.3710  libc-2.5.so              git-log                  strlen\n3782      5.7985  1361      8.0609  git-log                  git-log                  pretty_print_commit\n2022      3.1001  600       3.5537  libc-2.5.so              git-log                  vfprintf\n\ninflate_fast() is definitly below inflate().\n\nJosef\n"},{"id":"37247","messageId":"Pine.LNX.4.64.0703160841360.3816@woody.linux-foundation.org","threadId":"7267","inReplyTo":"20070316060841.19946.qmail@science.horizon.com","subject":"Re: cleaner/better zlib sources?","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-03-16T16:11:06Z","receivedAt":"2007-03-16T16:11:06Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 16 Mar 2007, linux@horizon.com wrote:\n>\n> Er, it's a little hard to see, but zlib spends the bulk of its time\n> in inflate_fast().\n\nNot for git.\n\nIt may be true for *big* inflate events, but the bulk of git inflates are \nsmall trees etc. Here is one particular profile:\n\n\tCPU: Core 2, speed 1596 MHz (estimated)\n\tCounted CPU_CLK_UNHALTED events (Clock cycles when not halted) with a unit \n\tmask of 0x00 (Unhalted core cycles) count 100000\n\tsamples  %        image name               app name                 symbol name\n\t169540   15.9845  git                      git                      inflate\n\t138377   13.0464  git                      git                      inflate_fast\n\t94738     8.9321  git                      git                      inflate_table\n\t73511     6.9308  git                      git                      strlen\n\t70398     6.6373  git                      git                      find_pack_entry_one\n\t59200     5.5815  vmlinux                  vmlinux                  __copy_user_nocache\n\t45103     4.2524  git                      git                      adler32\n\t42973     4.0516  git                      git                      memcpy\n\t23438     2.2098  git                      git                      interesting\n\t..\n\nso yes, inflate_fast() is certainly up there too, but plain \"inflate()\" is \nactually more important.\n\n(Btw, to get this level of detail, you need to link statically, at least \nif you are using Fedora Core. If you do the normal dynamic linking, \noprofile will not be able to show you which function, and will just say \nthat 50% of all time was spent in libz.so.1.2.3).\n\nAlso note that the above is with oprofile: do *not* bother to try to \nprofile using \"-pg\" and gprof. That changes the binary so much as to be \nuseless - small functions get the profiling code overhead and things that \ntake no time at all will suddenly become twice or three times as \nexpensive. Using oprofile you get fairly correct results.\n\n> The code in inflate.c just handles the last few bytes when near\n> one limit or the other.  Are you sure it's a performance problem?\n\nSee above. I'm absolutely positive.\n\n(The load for the above was roughly:\n\n\tgit log drivers/usb/ > /dev/null\n\non the kernel tree - ie I was mainly testing the commit tree pruning, \nwhich is one of the most fundamnetal operations, and is what makes \nor breaks the performance of things like \"git blame\" etc).\n\nI'd obviously *also* like to see inflate_fast() go down, and it has some \nreally strange code too, like:\n\n\t#  define PUP(a) *++(a)\n\n\t\t\t...\n                            len -= op;\n                            do {\n                                PUP(out) = PUP(from);\n                            } while (--op);\n\t\t\t...\n\nwhich looks rather odd, wouldn't you say? That's a memcpy. But I \nespecially find the nice \"unrolled\" memcpy interestign:\n\n\t\t...\n                    while (len > 2) {\n                        PUP(out) = PUP(from);\n                        PUP(out) = PUP(from);\n                        PUP(out) = PUP(from);\n                        len -= 3;\n                    }\n                    if (len) {\n                        PUP(out) = PUP(from);\n                        if (len > 1)\n                            PUP(out) = PUP(from);\n                    }\n\t\t...\n\nyeah, that's right - we unroll memcpy() BY DOING IT THREE BYTES AT A TIME!\n\nWhoever wrote that crap must have been on some strange medication. If you \nneed to do enough of a memcpy() that you want to unroll it, you sure as \nhell don't want to do it a byte-at-a-time, you want to do it with full \nwords etc. And the thing is called \"memcpy()\", for chrissake!\n\nThat's the \"optimized\" code. Strange.\n\n> There's equivalent inflate code in the PGP 5.0i distribution\n\nInteresting. I'll take a look.\n\n\t\tLinus\n"},{"id":"37264","messageId":"20070316173928.1877.qmail@science.horizon.com","threadId":"7267","inReplyTo":"Pine.LNX.4.64.0703160841360.3816@woody.linux-foundation.org","subject":"Re: cleaner/better zlib sources?","fromName":"","fromEmail":"linux@horizon.com","sentAt":"2007-03-16T17:39:28Z","receivedAt":"2007-03-16T17:39:28Z","isPatch":false,"sender":{"key":"linux@horizon.com","avatar":null},"body":"> so yes, inflate_fast() is certainly up there too, but plain \"inflate()\" is \n> actually more important.\n\nAh, okay.  Thanks for the real data.\n\n> I'd obviously *also* like to see inflate_fast() go down, and it has some \n> really strange code too, like:\n...\n> which looks rather odd, wouldn't you say? That's a memcpy.\n\nActually, no, it's not a memcpy.  memcpy is undefined for overlapping\noperands.  The way that gzip compresses 80 \"x\" characters is:\n- Emit literal \"x\"\n- Copy 79 bytes starting at (relative) offset -1\n\nFor this to work, the copy *must* proceed byte-at-a-time.  libc memcpy(),\nor even rep movsw, won't do.  It has to be rep movsb.\n\nNow, you could check for overlap and call memcpy() when the source and\ndestination don't overlap (the length is no larger than the offset),\nbut it's not clear that it's useful.\n\n> But I especially find the nice \"unrolled\" memcpy interestign:\n> \n>\t\t...\n>                    while (len > 2) {\n>                        PUP(out) = PUP(from);\n>                        PUP(out) = PUP(from);\n>                        PUP(out) = PUP(from);\n>                        len -= 3;\n>                    }\n>                    if (len) {\n>                        PUP(out) = PUP(from);\n>                        if (len > 1)\n>                            PUP(out) = PUP(from);\n>                    }\n>\t\t...\n>\n> yeah, that's right - we unroll memcpy() BY DOING IT THREE BYTES AT A TIME!\n\nThey're actually not that stupid.  A lot of copies are very short, so\ngetting too fancy is counterproductive.  It's been a while, so it may\nnot be optimal on current processors, but the code was heavily profiled\nand optimized at one point.\n\n>> There's equivalent inflate code in the PGP 5.0i distribution\n\n> Interesting. I'll take a look.\n\nI think I figured out the whitespace damage - that code was transmitted\nusing  RFC1149-like technology: printed on paper and OCRed in.\n\nI can see how that could play hell with the whitespace.  It makes a lot\nmore sense after that is fixed.  A properly indented version is appended,\nif anyone cares.\n\n\n\n\n/*\n * inflate.c -- Not copyrighted 1992,1993 by Mark Adler\n * Latest hacking on this version by Colin Plumb\n * version p3, 19 Oct 1995\n *\n * $Id: pgpZInflate.c,v 1.2 1997/01/24 23:35:54 mhw Exp $\n */\n\n\n/*\n * You can do whatever you like with this source file, though I would\n * prefer that if you modify it and redistribute it that you include\n * comments to that effect with your name and the date. Thank you.\n *\n * History:\n * vers  date\t    who         what\n * ----  ---------  ----------  ------------------------------------\n * a     ~~ Feb 92  M. Adler\tused full (large, one-step) lookup table\n * b1    21 Mar 92  M. Adler\tfirst version with partial lookup tables\n * b2    21 Mar 92  M. Adler\tfixed bug in fixed-code blocks\n * b3    22 Mar 92  M. Adler\tsped up match copies, cleaned up some\n * b4    25 Mar 92  M. Adler\tadded prototypes; removed window[] (now\n *\t\t\t\tis the responsibility of unzip.h--also\n *\t\t\t\tchanged name to slide[]), so needs diffs\n *\t\t\t\tfor unzip.c and unzip.h (this allows\n *\t\t\t\tcompiling in the small model on MSDOS);\n *\t\t\t\tfixed cast of q in huft_build();\n * b5    26 Mar 92  M. Adler\tgot rid of unintended macro recursion.\n * b6    27 Mar 92  M. Adler\tgot rid of nextbyte() routine. fixed\n *\t\t\t\tbug in inflate_fixed().\n * c1    30 Mar 92  M. Adler\tremoved lbits, dbits environment variables.\n *\t\t\t\tchanged BMAX to 16 for explode. Removed\n *\t\t\t\tOUTB usage, and replaced it with flush()--\n *\t\t\t\tthis was a 20% speed improvement! Added\n *\t\t\t\tan explode.c (to replace unimplode.c) that\n *\t\t\t\tuses the huft routines here. Removed\n *\t\t\t\tregister union.\n * c2     4 Apr 92  M. Adler\tfixed bug for file sizes a multiple of 32k.\n * c3    10 Apr 92  M. Adler\treduced memory of code tables made by\n *\t\t\t\thuft_build significantly (factor of two to\n *\t\t\t\tthree).\n * c4    15 Apr 92  M. Adler\tadded NOMEMCPY do kill use of memcpy().\n *\t\t\t\tworked around a Turbo C optimization bug.\n * c5    21 Apr 92  M. Adler\tadded the WSIZE #define to allow reducing\n *\t\t\t\tthe 32K window size for specialized\n *\t\t\t\tapplications.\n * c6    31 May 92  M. Adler\tadded some typecasts to eliminate warnings\n * c7    27 Jun 92  G. Roelofs\tadded some more typecasts (444: MSC bug).\n * c8     5 Oct 92  J-l. Gailly\tadded ifdef'd code to deal with PKZIP bug.\n * c9     9 Oct 92  M. Adler\tremoved a memory error message (~line 416).\n * c10   17 Oct 92  G. Roelofs\tchanged ULONG/UWORD/byte to ulg/ush/uch,\n *\t\t\t\tremoved old inflate, renamed inflate_entry\n *\t\t\t\tto inflate, added Mark's fix to a comment.\n * c11   2 Jan 93  M. Adler\tfixed bug in detection of incomplete\n *\t\t\t\ttables, and removed assumption that EOB is\n *\t\t\t\tthe longest code (bad assumption).\n * c12   3 Jan 93  M. Adler\tmake tables for fixed blocks only once.\n * c13   5 Jan 93  M. Adler\tallow all zero length codes (pkzip 2.04c\n *\t\t\t\toutputs one zero length code for an empty\n *\t\t\t\tdistance tree).\n * c14   12 Mar 93  M. Adler\tmade inflate.c standalone with the\n *\t\t\t\tintroduction of inflate.h.\n * d0    25 Apr 93  M. Adler\tseveral speedups in inflate_codes of\n *\t\t\t\talmost 20% (suggested by Urban Mueller)--\n *\t\t\t\tnow requires the use of backfill.[ch]\n * d1     4 May 93  M. Adler\tdeleted extraneous statement in cheap loop,\n *\t\t\t\toptimized common copy a little more.\n * d2     5 May 93  M. Adler\tcalculate number of cheap loops, a few\n *\t\t\t\tother small optimizations.\n * p1       Nov 93  C. Plumb \tAdpated to be able to suspend itself.\n *\t\t\t\tPretty massive reorganization.\n *\t\t\t\tMany comments added.\n * p2    18 Oct 95  C. Plumb\tImproved interface some more. Now\n *\t\t\t\tnicely re-entrant. Still more comments.\n * p3    19 Oct 95  C. Plumb\tChanged infInflate core function so that\n *\t\t\t\tit sucks the input completely dry before\n *\t\t\t\treturning. This gets rid of the old ad-hoc\n *\t\t\t\ttechnique for flushing out the last little\n *\t\t\t\tbit of a compressed file by padding it\n *\t\t\t\twith some dummy data, which was ugly.\n */\n\n\n/*\n * Inflate deflated (PKZIP's method 8 compressed) data. The compression\n * method searches for as much of the current string of bytes (up to a\n * length of 258) in the previous 32K bytes. If it doesn't find any\n * matches (of at least length 3), it codes the next byte. Otherwise, it\n * codes the length of the matched string and its distance backwards from\n * the current position. There is a single Huffman code that codes both\n * single bytes (called \"literals\") and match lengths. A second Huffman\n * code codes the distance information, which follows a length code. Each\n * length or distance code actually represents a base value and a number\n * of \"extra\" (sometimes zero) bits to get to add to the base value. At\n * the end of each deflated block is a special end-of-block (EOB) literal/\n * length code. The decoding process is basically: get a literal/length\n * code; if EOB then done; if a literal, emit the decoded byte; if a\n * length then get the distance and emit the referred-to bytes from the\n * sliding window of previously emitted data.\n *\n * There are (currently) three kinds of inflate blocks: stored, fixed, and\n * dynamic. The compressor outputs a chunk of data at a time and decides\n * which method to use on a chunk-by-chunk basis. A chunk might typically\n * be 32K to 64K, uncompressed. If the chunk is uncompressible, then the\n * \"stored\" method is used. In this case, the bytes are simply stored as\n * is, eight bits per byte, with none of the above coding. The bytes are\n * preceded by a (16-bit) count, since there is no longer an EOB code.\n *\n * If the data is compressible, then either the fixed or dynamic methods\n * are used. In the dynamic method, the compressed data is preceded by\n * an encoding of the literal/length and distance Huffman codes that are\n * to be used to decode this block. The representation is itself Huffman\n * coded, and so is preceded by a description of that code. These code\n * descriptions take up a little space, and so for small blocks, there is\n * a predefined set of codes, called the fixed codes. The fixed method is\n * used if the block ends up smaller that way (usually for quite small\n * chunks); otherwise the dynamic method is used. In the latter case, the\n * codes are customized to the probabilities in the current block and so\n * can code it much better than the pre-determined fixed codes can.\n *\n * The Huffman codes themselves are decoded using a mutli-level table\n * lookup, in order to maximize the speed of decoding plus the speed of\n * building the decoding tables. See the comments below that precede the\n * LBITS and DBITS tuning parameters.\n */\n\n\n/*\n *  Notes beyond the 1.93a  appnote.txt:\n *\n * 1. Distance pointers never point before the beginning of the output\n * stream.\n * 2. Distance pointers can point back across blocks, up to 32k away.\n * 3. There is an implied maximum of 7 bits for the bit length table and\n * 15 bits for the actual data.\n * 4. If only one code exists, then it is encoded using one bit. (Zero\n * would be more efficient, but perhaps a little confusing.) If two\n * codes exist, they are coded using one bit each (0 and 1).\n * 5. There is no way of sending zero distance codes--a dummy must be\n * sent if there are none. (History: a pre 2.0 version of PKZIP would\n * store blocks with no distance codes, but this was discovered to be\n * too harsh a criterion.) Valid only for 1.93a. 2.04c does allow\n * zero distance codes, which is sent as one code of zero bits in\n * length.\n * 6. There are up to 286 literal/length codes. Code 256 represents the\n * end-of-block. Note however that the static length tree defines\n * 288 codes just to fill out the Huffman codes. Codes 286 and 287\n * cannot be used though, since there is no length base or extra bits\n *\tdefined for them. Similarily, there are up to 30 distance codes.\n *\tHowever, static trees define 32 codes (all 5 bits) to fill out the\n *\tHuffman codes, but the last two had better not show up in the data.\n * 7. Unzip can check dynamic Huffman blocks for complete code sets.\n * The exception is that a single code would not be complete (see #4).\n * 8. The five bits following the block type is really the number of\n * literal codes sent minus 257.\n * 9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits\n * (1+6+6). Therefore, to output three times the length, you output\n * three codes (1+1+1), whereas to output four times the same length,\n * you only need two codes (1+3). Hmm.\n * 10. In the tree reconstruction algorithm, Code = Code + Increment\n * only if BitLength(i) is not zero. (Pretty obvious.)\n * 11. Correction: 4 Bits: # of Bit Length codes - 4 (4 - 19)\n * 12. Note: length code 284 can represent 227-258, but length code 285\n * really is 258. The last length deserves its own, short code\n * since it gets used a lot in very redundant files. The length\n * 258 is special since 258 - 3 (the min match length) is 255.\n * 13. The literal/length and distance code bit lengths are read as a\n * single stream of lengths. It is possible (and advantageous) for\n * a repeat code (16, 17, or 18) to go across the boundary between\n * the two sets of lengths.\n */\n\n#ifdef HAVE_CONFIG_H\n#include \"config.h\"\n#endif\n\n#include <string.h> /* for memset() */\n\n#include \"pgpDebug.h\"\n#include \"pgpMem.h\"\n#include \"pgpUsuals.h\"\n#include \"pgpZInflate.h\"\n\n/* Increasing these only wastes space, so they can be changed if necessary */\ntypedef word16 ush;\ntypedef word32 ulg;\n\n/* Private context structure for use by all functions. */\nstruct InflateContext {\n\t/* Major state information */\n\tint state;\n\tint substate;\n\tint lastblock;\n\n\t/* Output-related information */\n\tunsigned char *slide; /* Circular output buffer */\n\tunsigned char *slideend;\n\tunsigned slidelen; /* slideend-slide - MUST BE POWER OF 2 */\n\tunsigned slidemask; /* slidelen-1 */\n\tunsigned char *outptr; /* Pointer into slide */\n\tunsigned char const *readptr; /* Pointer into slide for reading */\n\n\t/* Input-related information */\n\tunsigned char const *inptr; /* Input pointer */\n\tint inlen;  /* Input length */\n\tulg bitbuffer;\n\tunsigned bufbits;\n\n\t/* The literal/length tree - also used for the bit-length tree */\n\tstruct huft *tree1;\n\tunsigned bits1;\n\n\t/* The distance tree */\n\tstruct huft *tree2;\n\tunsigned bits2;\n\n\t/* Encoded huffman tree */\n\tunsigned char bitlen[286+30];\n\n\t/* For dynamic trees */\n\tunsigned bitlengths;\n\tunsigned litcodes;\n\tunsigned distcodes;\n\n\t/* Used in various places */\n\tstruct huft const *t;\n\tunsigned copylen;\n\tint distbase;\n\tint numbits; /* # of bits in dyn. tree repeat and after dist. code*/\n\tunsigned index; /* Position in dynamic tree bit lengths we've read to*/\n};\n\n/* Options for behaviour */\n#ifndef SECURE\n#define SECURE 1\t/* Wipe memory before freeing it? */\n#endif\n\n#ifndef WSIZE\n#define WSIZE 32768\t/* Window size - 32768 for PKZIP compatibility */\n#endif\n\n#ifndef STRICT\n#define STRICT 1\t/* Require unused bits to be zero? */\n#endif\n\n/*\n * Huffman code lookup table entry--this entry is four bytes for machines\n * that have 16-bit pointers (e.g. PC's in the small or medium model).\n * Valid extra bits are 0..13. e == 32 is EOB (end of block), e == 16\n * means that v is a literal, e < 0 means that v is a pointer to the next\n * table, which codes -e bits, and lastly e == -128 indicates an unused\n * code. If a code with e == -128 is looked up, this implies an error in\n * the data.\n */\nstruct huft {\n\tunion {\n\t\tstruct {\n\t\t\tsigned char exop; /* # of extra bits or operation */\n\t\t\tchar bits; /* # of bits in this code/subcode */\n\t\t} what;\n\t\tchar *pad;\t/* pad structure to a power of 2 (4 bytes for*/\n\t} word; \t\t/* 16-bit, 8 bytes for 32-bit machines) */\n\tunion {\n\t\tush base;\t/* literal, length base, or distance base */\n\t\tstruct huft *next; /* pointer to next level of table */\n\t} more;\n};\n\n#define base more.base\n#define next more.next\n#define exop word.what.exop\n#define bits word.what.bits\n\n/* Function prototypes */\n#ifndef OF\n# if defined(__STDC__) || defined(__cplusplus)\n# define OF(a) a\n# else\n# define OF(a) ()\n# endif\n#endif\n\nstatic int huft_build OF((unsigned char const *, unsigned, unsigned,\n\t\t\t  ush const *, ush const *, struct huft **,\n\t\t\t  unsigned *));\nstatic int huft_free OF((struct huft *));\n\n/*\n * The inflate algorithm uses a sliding 32K byte window on the uncompressed\n * stream to find repeated byte strings. This is implemented here as a\n * circular buffer. The index is updated simply by incrementing and then\n * and'ing with 0x7fff (32K-1).\n */\n\n/* Tables for deflate from PKZIP's appnote.txt. */\nstatic unsigned const border[] = { /* Order of the bit length code lengths */\n 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};\n\nstatic ush const cplens[] = { /* Copy lengths for literal codes 257..285 */\n 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 13, 15, 17, 21, 25, 29,\n 33, 41, 49, 57, 65, 81, 97, 113, 129, 161, 193, 225, 256, 0, 0};\n /* actually lengths - 2; also see note #13 above about 258 */\n\nstatic ush const cplext[] = { /* Extra bits for literal codes 257..285 */\n 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,\n 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 128, 128}; /* 128==invalid */\n\nstatic ush const cpdist[] = { /* Copy offsets for distance codes 0..29 */\n 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,\n 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,\n 8193, 12289, 16385, 24577};\n\nstatic ush const cpdext[] = { /* Extra bits for distance codes */\n 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,\n 7, 7, 8, 8, 9, 9, 10, 10, 11, 11,\n 12, 12, 13, 13};\n\n/* And'ing with mask[n] masks the lower n bits */\nstatic unsigned const mask[17] = {\n0x0000,\n0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff,\n0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff\n};\n\n\n/* Macros for inflate() bit peeking and grabbing.\n * The usage is:\n *\n *\tNEEDBITS(j)\n *\tx = b & mask[j];\n *\tDUMPBITS(j)\n *\n * where NEEDBITS makes sure that b has at least j bits in it, and\n * DUMPBITS removes the bits from b. The macros use the variable k\n * for the number of bits in b. Normally, b and k are register\n * variables for speed, and are initialized at the beginning of a\n * routine that uses these macros from a global bit buffer and count.\n *\n * It is allowed for more bits to be requested than actually used.\n * The remainder stay in the bit buffer. NOTE that a few more\n * bytes than necessary may be grabbed at the end of input.\n * This should not be fatal as long as the grabbed bits stay\n * in the bit buffer. The wrapup functions should check for this.\n *\n * There is also the macro GRABBITS which is like NEEDBITS, but uses\n * *g++ to get the byte without checking availability. This requires\n * using AVAILBYTES first to assure that the needed bytes are there\n * already. g is set to inptr and then inptr is restored to g around\n * this usage.\n */\n\n/*\n * Variable usage:\n * b = bit buffer, k least-significant bits valid\n * k = # of bits in bit buffer\n * g = grab bits pointer (pointer to next byte to add: b |= *g++ << k)\n * s = # of bytes available\n * ctx = InflateContext\n */\n\n/* Functions to save the state of the bit buffer before returning */\n#define LOADBITBUF \\\n\t(b=ctx->bitbuffer, k=ctx->bufbits, g=ctx->inptr, s=ctx->inlen)\n#define SAVEBITBUF \\\n\t(ctx->bitbuffer=b, ctx->bufbits=k, ctx->inptr=g, ctx->inlen=s)\n#define SAVEBITBUFEMPTY \\\n\t(ctx->bitbuffer=b, ctx->bufbits=k, ctx->inptr=g, ctx->inlen=0)\n\n/*\n * A simple macro to ensure that at least \"x\" bits are in the bit buffer.\n * Does NOT check for input underflow (s < 0).\n */\n#define GRABBITS(x) \\\n\twhile (k < x) { \\\n\t\t--s; \\\n\t\tb |= (ulg)*g++ << k; \\\n\t\tk += 8; \\\n\t}\n\n/*\n * Get \"x\" bits in the input buffer or execute the \"whatif\" code.\n * NOTE NOTE NOTE that if the \"whatif\" code is executed, s is set to -1!\n * (This is faster on a lot of machines.) You will usually have to\n * reset it to 0 manually.\n */\n#define GETBITSOR(x, whatif) \\\n\twhile (k < (unsigned)(x)) { \\\n\t\tif (--s < 0) { \\\n\t\t\twhatif; \\\n\t\t} \\\n\t\tb |= (ulg)*g++ << k; \\\n\t\tk += 8; \\\n\t}\n\n/*\n * A macro to ensure that there are at least \"x\" bits available in the\n * bit buffer. If there are not, the bit buffer is saved back into the\n * context, and any code in \"savestate\" is run to save any additional\n * context that might be needed. Then, \"return 1\" means that more input is\n * needed.\n */\n#define NEEDBITS(x, savestate) \\\n\tGETBITSOR(x, savestate; SAVEBITBUFEMPTY; return 1)\n\n/*\n * NEEDBITS2 uses two figures for the number of bits required. The first,\n * x, is cheap to compute and is used unless we run out of input data.\n * If that happens, the more expensive value, x2, is used.\n */\n#define NEEDBITS2(x, x2, savestate) \\\n\tNEEDBITS(x, if (k >= (unsigned)(x2)) {s=0; break;} savestate)\n\n#define DUMPBITS(x) (b >>= x, k -= x)\n\n/*\n * Huffman code decoding is performed using a multi-level table lookup.\n * The fastest way to decode is to simply build a lookup table whose\n * size is determined by the longest code. However, the time it takes\n * to build this table can also be a factor if the data being decoded\n * is not very long. The most common codes are necessarily the\n * shortest codes, so those codes dominate the decoding time, and hence\n * the speed. The idea is you can have a shorter table that decodes the\n * shorter, more probable codes, and then point to subsidiary tables for\n * the longer codes. The time it costs to decode the longer codes is\n * then traded against the time it takes to make longer tables.\n *\n * This results of this trade are in the values LBITS and DBITS\n * below. LBITS is the number of bits the first level table for literal/\n * length codes can decode in one step, and DBITS is the same thing for\n * the distance codes. Subsequent tables are also less than or equal to\n * those sizes. These values may be adjusted either when all of the\n * codes are shorter than that, in which case the longest code length in\n * bits is used, or when the shortest code is *longer* than the requested\n * table size, in which case the length of the shortest code in bits is\n * used.\n *\n * There are two different values for the two tables, since they code a\n * different number of possibilities each. The literal/length table\n * codes 286 possible values, or in a flat code, a little over eight\n * bits. The distance table codes 30 possible values, or a little less\n * than five bits, flat. The optimum values for speed end up being\n * about one bit more than those, so LBITS is 8+1 and DBITS is 5+1.\n * The optimum values may differ though from machine to machine, and\n * possibly even between compilers. Your mileage may vary.\n */\n\n#define LBITS 9 /* bits in base literal/length lookup table */\n#define DBITS 6 /* bits in base distance lookup table */\n\n/* If BMAX needs to be larger than 16, then h and x[] should be ulg. */\n#define BMAX 15 /* maximum bit length of any code (16 for explode) */\n#define N_MAX 288 /* maximum number of codes in any set */\n\n#if defined(__STDC__) || defined(__cplusplus)\nstatic int\nhuft_build(unsigned char const *b, unsigned n, unsigned s, ush const *d,\n           ush const *e, struct huft **t, unsigned *m)\n#else\nstatic int\nhuft_build(b, n, s, d, e, t, m)\n    unsigned char *b; /* code lengths in bits (all assumed <= BMAX) */\n    unsigned n; /* number of codes (assumed <= N_MAX) */\n    unsigned s; /* number of simple-valued codes (0..s-1) */\n    ush const *d;\t/* list of base values for non-simple codes */\n    ush const *e;\t/* list of extra bits for non-simple codes */\n    struct huft **t;\t/* result: starting table */\n    unsigned *m;\t/* suggested lookup bits, returns actual */\n#endif\n/*\n * Given a list of code lengths and a maximum table size, make a set of\n * tables to decode that set of codes. Return values:\n * 0 = success\n * 1 = the given code set is incomplete\n * (the tables are still built in this case)\n * 2 = the input is invalid\n * (all zero length codes or an oversubscribed set of lengths)\n * 3 = not enough memory.\n */\n{\n    unsigned a;\t/* counter for codes of length k */\n    unsigned c[BMAX+1];\t/* bit length count table */\n    unsigned f;\t/* i repeats in table every f entries */\n    int g;\t/* maximum code length */\n    int h;\t/* table level */\n    register unsigned i;\t/* counter, current code */\n    register unsigned j;\t/* counter */\n    register int k;\t/* number of bits in current code */\n    int l;\t/* bits per table (returned in m) */\n    register unsigned char const *bp; /* pointer into b[] */\n    register unsigned *p;\t/* pointer into c[] or v[] */\n    register struct huft *q;\t/* points to current table */\n    struct huft r;\t/* table entry for structure assignment */\n    struct huft *u[BMAX];\t/* table stack */\n    unsigned v[N_MAX];\t/* values in order of bit length */\n    register int w;\t/* bits before this table == (l * h) */\n    unsigned x[BMAX+1];\t/* bit offsets, then code stack */\n    unsigned *xp;\t/* pointer into x */\n    int y;\t/* number of dummy codes added */\n    unsigned z;\t/* number of entries in current table */\n\n\n    /* Generate counts for each bit length */\n    memset(c, 0, sizeof(c));\n    bp = b; i = n;\n    do {\n\tc[*bp++]++;\t/* assume all entries <= BMAX */\n    } while (--i);\n    if (c[0] == n) {\t/* null input--all zero length codes */\n\t*t = (struct huft *)NULL;\n\t*m = 0;\n\treturn 0;\n    }\n\n\n    /* Find minimum and maximum length, bound *m by those */\n    l = *m;\n    for (j = 1; j <= BMAX; j++)\n\tif (c[j])\n\t    break;\n    k = j;\t/* minimum code length */\n    if ((unsigned)l < j)\n\tl = j;\n    for (i = BMAX; i; i--)\n\tif (c[i])\n\t    break;\n    g = i;\t/* maximum code length */\n    if ((unsigned)l > i)\n\tl = i;\n    *m = l;\n\n\n    /* Adjust last length count to fill out codes, if needed */\n    for (y = 1 << j; j < i; j++, y <<= 1)\n\tif ((y -= c[j]) < 0)\n\t    return 2;\t/* bad input: more codes than bits */\n    if ((y -= c[i]) < 0)\n\treturn 2;\n    c[i] += y;\n\n\n    /* Generate starting offsets into the value table for each length */\n    x[1] = j = 0;\n    p = c + 1;\n    xp = x + 2;\n    while (--i) {\t/* note that i == g from above */\n\t*xp++ = (j += *p++);\n    }\n\n\n    /* Make a table of values in order of bit lengths */\n    bp = b; i = 0;\n    do {\n\tif ((j = *bp++) != 0)\n\t    v[x[j]++] = i;\n    } while (++i < n);\n\n\n    /* Generate the Huffman codes and for each, make the table entries */\n    x[0] = i = 0;\t/* first Huffman code is zero */\n    p = v;\t/* grab values in bit order */\n    h = -1;\t/* no tables yet--level -1 */\n    w = -l;\t/* bits decoded == (l * h) */\n    u[0] = (struct huft *)NULL; /* just to keep compilers happy */\n    q = (struct huft *)NULL;    /* ditto */\n    z = 0;\t/* ditto */\n\n    /* go through the bit lengths (k already is bits in shortest code) */\n    for (; k <= g; k++) {\n\ta = c[k];\n\twhile (a--) {\n\t    /* here i is the Huffman code of length k bits for value *p */\n\t    /* make tables up to required level */\n\t    while (k > w + l) {\n\t\th++;\n\t\tw += l; /* previous table always l bits */\n\n\t\t/* compute minimum size table less than or equal to l bits */\n\t\tz = (z = g - w) > (unsigned)l ? l : z; /* upper limit on table size */\n\t\tif ((f = 1 << (j = k - w)) > a + 1) /* try a k-w bit table */\n\t\t{\t/* too few codes for k-w bit table */\n\t\t    f -= a + 1; /* deduct codes from patterns left */\n\t\t    xp = c + k;\n\t\t    while (++j < z) { /* try smaller tables up to z bits */\n\t\t\tif ((f <<= 1) <= *++xp)\n\t\t\t    break;\t/* enough codes to use up j bits */\n\t\t\tf -= *xp;\t/* else deduct codes from patterns */\n\t\t    }\n\t\t}\n\t\tz = 1 << j;\t\t\t/* table entries for j-bit table */\n\n\t\t/* allocate and link in new table */\n\t\tq = (struct huft *)pgpMemAlloc((z + 1)*sizeof(struct huft));\n\t\tif (q == (struct huft *)NULL) {\n\t\t\tif (h)\n\t\t\t\thuft_free(u[0]);\n\t\t\treturn 3;\t\t/* not enough memory */\n\t\t}\n#if SECURE\n\t\tq->bits = (char)j;\t\t\t/* Track size for free */\n#endif\n\t\t*t = q + 1;\t\t\t/* link to list for huft_free() */\n\t\t*(t = &(q->next)) = (struct huft *)NULL;\n\t\tu[h] = ++q; /* table starts after link */\n\n\t\t/* connect to last table, if there is one */\n\t\tif (h) {\n\t\t    x[h] = i;\t\t/* save pattern for backing up */\n\t\t    r.bits = (char)l;\t\t/* bits to dump before this table */\n\t\t    r.exop = -(char)j;\t\t/* bits in this table */\n\t\t    r.next = q;\t\t/* pointer to this table */\n\t\t    j = i >> (w - l);\t\t/* (get around Turbo C bug) */\n\t\t    u[h-1][j] = r;\t\t/* connect to last table */\n\t\t}\n\t    }\n\n\t    /* set up table entry in r */\n\t    r.bits = (char)(k - w);\n\t    if (p >= v + n) {\n\t\tr.exop = -128; /* out of values--invalid code */\n\t    } else if (*p < s) {\n\t\tr.exop = (char)(*p < 256 ? 16 : 32); /* 256 is end-of-block code */\n\t\tr.base = *p++; /* simple code is just the value */\n\t    } else {\n\t\tr.exop = (char)e[*p - s]; /* non-simple--look up in lists */\n\t\tr.base = d[*p++ - s];\n\t    }\n\n\t    /* fill code-like entries with r */\n\t    f = 1 << (k - w);\n\t    for (j = i >> w; j < z; j += f)\n\t\tq[j] = r;\n\n\t    /* backwards increment the k-bit code i */\n\t    for (j = 1 << (k - 1); i & j; j >>= 1)\n\t\ti ^= j;\n\t    i ^= j;\n\n\t    /* back up over finished tables */\n\t    while ((i & ((1 << w) - 1)) != x[h]) {\n\t\th--; /* don't need to update q */\n\t\tw -= l;\n\t    }\n\t}\n    }\n\n    /* Return true (1) if we were given an incomplete table */\n    return y != 0 && g != 1;\n}\n\n\n#if defined(__STDC__) || defined(__cplusplus)\nstatic int\nhuft_free(struct huft *t)\n#else\nstatic int\nhuft_free(t)\n\tstruct huft *t;\t/* table to free */\n#endif\n/*\n * Free the malloc'ed tables built by huft_build(), which makes a linked\n * list of the tables it made, with the links in a dummy -1st entry of\n * each table.\n */\n{\n\tregister struct huft *p, *q;\n\n\t/* Go through linked list, freeing from the malloced (t[-1]) address. */\n\tp = t;\n\twhile (p != (struct huft *)NULL)\n\t{\n\t\tq = (--p)->next;\n#if SECURE\n\t\tmemset(p, 0, (1+(1<<p->bits)) * sizeof(*p));\n#endif\n\t\tpgpMemFree(p);\n\t\tp = q;\n\t}\n\treturn 0;\n}\n\n\n/*\n * Colin's new code.\n */\n\n#define STATE_START 0\n#define STATE_STOREDLEN 1\n#define STATE_STORED 2\n#define STATE_DYN_HDR 3\n#define STATE_DYN_BITS 4\n#define STATE_DYN_TREE 5\n#define STATE_INFLATE 6\n#define STATE_DONE 7\n#define STATE_STOP 8\n\n/*\n * All these functions return\n * 2 if the output buffer is full\n * 1 if the input buffer is empty\n * 0 if things should continue with the new ctx->state, and\n * <0 on error.\n */\n\nstatic int\ninfStoredLen(struct InflateContext *ctx)\n{\n\tulg b;\n\tunsigned k;\n\tint s;\n\tunsigned char const *g;\n\tunsigned t;\n\n\tLOADBITBUF;\n\tt = k & 7;\n#if STRICT\n\tif (b & mask[t])\t/* Require unused bits are zero */\n\t\treturn INFERR_BADINPUT;\n#endif\n\tDUMPBITS(t);\n\n\tNEEDBITS(32, (void)0);\n\n\t/* At this point, k is exactly 32 */\n\n\tctx->copylen = (unsigned)b & 0xffff;\n\tt = ~(unsigned)(b>>16) & 0xffff;\n\tb = 0;\n\tk = 0;\n\n\tSAVEBITBUF;\n\tif (t != ctx->copylen)\n\t\treturn INFERR_BADINPUT; /* Two lengths not identical */\n\n\tctx->state = STATE_STORED;\n\tctx->substate = 0;\n\n\treturn 0;\n}\n\n/*\n * Process the data in a stored block. Copy the input data to\n * the circular buffer, flushing it as necessary.\n */\nstatic int\ninfStored(struct InflateContext *ctx)\n{\n\tint len; /* # of bytes to copy */\n\tint retval = 1; /* Out of memory */\n\n\tpgpAssert(ctx->bufbits == 0);\n\n\tlen = ctx->inlen;\n\tif ((unsigned)len >= ctx->copylen) {\n\t\tlen = ctx->copylen; /* Copy done! */\n\t\tctx->state = STATE_START;\n\t\tretval = 0;\n\t}\n\tif (len > ctx->slideend-ctx->outptr) {\n\t\tlen = (int)(ctx->slideend-ctx->outptr);\n\t\tretval = 2; /* Output buffer full */\n\t}\n\n\tmemcpy(ctx->outptr, ctx->inptr, len);\n\tctx->inptr += len;\n\tctx->inlen -= len;\n\tctx->outptr += len;\n\tctx->copylen -= (unsigned)len;\n\n\t/* Return 2 if output full, 1 if input empty, 0 otherwise (copy done)*/\n\treturn retval;\n}\n\nstatic int\ninfDynHdr(struct InflateContext *ctx)\n{\n\tulg b;\n\tunsigned k;\n\tint s;\n\tunsigned char const *g;\n\n\tLOADBITBUF;\n\tNEEDBITS(14, (void)0);\n\n\tctx->litcodes = 257 + ((unsigned)b & 0x1f);\n\tDUMPBITS(5);\n\tctx->distcodes = 1 + ((unsigned)b & 0x1f);\n\tDUMPBITS(5);\n\tctx->bitlengths = 4 + ((unsigned)b & 0xf);\n\tDUMPBITS(4);\n\n\tSAVEBITBUF;\n\n#ifndef PKZIP_BUG_WORKAROUND\n\tif (ctx->litcodes > 286 || ctx->distcodes > 30)\n\t\treturn INFERR_BADINPUT; /* Bad lengths */\n#endif\n\tctx->state = STATE_DYN_BITS;\n\treturn 0;\n}\n\n/* Load up the ctx->bitlen array with the bit lengths for the encoded\n * trees. Unpermute them according to the border[] array.\n */\nstatic int\ninfDynBits(struct InflateContext *ctx)\n{\n\tulg b;\n\tunsigned k;\n\tint s;\n\tunsigned char const *g;\n\tstruct huft *t;\n\tint i, lim;\n\n\tLOADBITBUF;\n\ti = ctx->substate;\n\tlim = ctx->bitlengths;\n\n\twhile (i < lim) {\n\t\tNEEDBITS(3, ctx->substate=i)\n\t\tctx->bitlen[border[i++]] = (unsigned)b & 7;\n\t\tDUMPBITS(3);\n\t}\n\tSAVEBITBUF;\n\n\twhile (i < 19)\n\t\tctx->bitlen[border[i++]] = 0;\n\n\tk = 7; /* Bits in tree table */\n\n\ti = huft_build(ctx->bitlen, 19, 19, NULL, NULL, &t, &k);\n\tif (i) {\n\t\tif (i == 1)\n\t\t\thuft_free(t); /* Incomplete code set */\n\t\t\treturn i == 3 ? INFERR_NOMEM : INFERR_BADINPUT;\n\t\t}\n\tctx->tree1 = t;\n\tctx->bits1 = k;\n\n\tctx->state = STATE_DYN_TREE;\n\tctx->substate = 0;\n\n\treturn 0;\n}\n\n/* The static tree (built on demand) */\nstatic struct huft *fixed_tl = NULL;\nstatic struct huft *fixed_td;\nstatic unsigned fixed_bl, fixed_bd;\n\nstatic int\ninfFixedTree(void)\n{\n\tint i;\n\tunsigned char l[288];\n\n\tif (fixed_tl)\n\t\treturn 0;\t/* All okay */\n\n\t/* literal table */\n\tfor (i = 0; i < 144; i++)\n\t\tl[i] = 8;\n\tfor (; i < 256; i++)\n\t\tl[i] = 9;\n\tfor (; i < 280; i++)\n\t\tl[i] = 7;\n\tfor (; i < 288; i++)\t/* make a complete, but wrong code set */\n\t\tl[i] = 8;\n\tfixed_bl = 7;\n\ti = huft_build(l, 288, 257, cplens, cplext, &fixed_tl, &fixed_bl);\n\tif (i != 0) {\n\t\tfixed_tl = NULL;\n\t\treturn INFERR_NOMEM;\n\t}\n\n\t/* distance table */\n\tfor (i = 0; i < 30; i++)\t/* make an incomplete code set */\n\t\tl[i] = 5;\n\tfixed_bd = 5;\n\ti = huft_build(l, 30, 0, cpdist, cpdext, &fixed_td, &fixed_bd);\n\tif (i > 1) {\n\t\thuft_free(fixed_tl);\n\t\tfixed_tl = NULL;\n\t\treturn INFERR_NOMEM;\n\t}\n\n\treturn 0;\n}\n\nstatic int\ninfDynTree(struct InflateContext *ctx)\n{\n\tulg b;\n\tunsigned k;\n\tint s;\n\tunsigned char const *g;\n\tstruct huft *tl, *td;\n\tunsigned bl, bd;\n\tunsigned i, j, l, m, lim;\n\n\tLOADBITBUF;\n\ti = ctx->index;\n\tl = ctx->numbits; /* Previous # of bits for repeat code use */\n\tlim = ctx->litcodes + ctx->distcodes;\n\ttl = ctx->tree1;\n\tbl = ctx->bits1;\n\tm = mask[bl];\n\n\tswitch(ctx->substate) {\n\tcase 0:\n\t\ti = 0;\n\t\tl = 0;\n\t\t/*FALLTHROUGH*/\n\tcase 1:\n\t\twhile (i < lim) {\n\t\t\tNEEDBITS2(bl, tl[(unsigned)b & m].bits,\n\t\t\t\t  ctx->index=i; ctx->numbits=l; ctx->substate=1)\n\t\t\ttd = tl + ((unsigned)b & m);\n\t\t\tj = td->bits;\n\t\t\tDUMPBITS(j);\n\t\t\tj = td->base;\n\t\t\tif (j < 16) {\n\t\t\t\tctx->bitlen[i++] = l = j;\n\t\t\t} else if (j == 16) { /* 3 to 6 repeats */\n\t\t\t\t/*FALLTHROUGH*/\n\tcase 2:\n\t\t\t\tNEEDBITS(2, ctx->index=i; ctx->numbits=l;\n\t\t\t\t\t ctx->substate=2)\n\t\t\t\tj = 3 + ((unsigned)b & 3);\n\t\t\t\tDUMPBITS(2);\n\t\t\t\tif (i + j > lim)\n\t\t\t\t\treturn INFERR_BADINPUT;\n\t\t\t\tdo {\n\t\t\t\t\tctx->bitlen[i++] = (unsigned char)l;\n\t\t\t\t} while (--j);\n\t\t\t} else if (j == 17) { /* 3 to 10 zeros */\n\t\t\t\t/*FALLTHROUGH*/\n\tcase 3:\n\t\t\t\tNEEDBITS(3, ctx->index=i; ctx->substate=3)\n\t\t\t\tj = 3 + ((unsigned)b & 7);\n\t\t\t\tDUMPBITS(3);\n\t\t\t\tif (i + j > lim)\n\t\t\t\t\treturn INFERR_BADINPUT;\n\t\t\t\tdo {\n\t\t\t\t\t ctx->bitlen[i++] = 0;\n\t\t\t\t} while (--j);\n\t\t\t\t\tl = 0;\n\t\t\t} else { /* j == 18 -- 11 to 138 zeros */\n\t\t\t\tpgpAssert(j == 18);\n\t\t\t\t/*FALLTHROUGH*/\n\tcase 4:\n\t\t\t\tNEEDBITS(7, ctx->index=i; ctx->substate=4)\n\t\t\t\tj = 11 + ((unsigned)b & 127);\n\t\t\t\tDUMPBITS(7);\n\t\t\t\tif (i + j > lim)\n\t\t\t\t\treturn INFERR_BADINPUT;\n\t\t\t\tdo {\n\t\t\t\t\tctx->bitlen[i++] = 0;\n\t\t\t\t} while (--j);\n\t\t\t\tl = 0;\n\t\t\t}\n\t\t}\n\t}\n\n\t/* Input finished */\n\tSAVEBITBUF;\n\thuft_free(tl);\n\tctx->tree1 = 0;\n\n\t/* Now build the trees - literal/length, then distance */\n\n\tbl = LBITS;\n\ti = huft_build(ctx->bitlen, ctx->litcodes, 257,\n\t\tcplens, cplext, &tl, &bl);\n\tif (i != 0) {\n\t\tif (i == 1)\n\t\t\thuft_free(tl);\n\t\treturn i == 3 ? INFERR_NOMEM : INFERR_BADINPUT;\n\t}\n\tbd = DBITS;\n\ti = huft_build(ctx->bitlen+ctx->litcodes, ctx->distcodes, 0,\n\t\t cpdist, cpdext, &td, &bd);\n#ifdef PKZIP_BUG_WORKAROUND\n\tif (i > 1) {\n#else\n\tif (i != 0) {\n\t\tif (i == 1)\n\t\t\thuft_free(td);\n#endif\n\t\thuft_free(tl);\n\t\treturn i == 3 ? INFERR_NOMEM : INFERR_BADINPUT;\n\t}\n\tctx->tree1 = tl;\n\tctx->bits1 = bl;\n\tctx->tree2 = td;\n\tctx->bits2 = bd;\n\n\tctx->state = STATE_INFLATE;\n\tctx->substate = 0;\n\n\treturn 0;\n}\n\n/*\n * This is the heart of ZIP inflation. The code is heavily optimized\n * for speed, including for many brain-damaged compilers that can only\n * optimize one statement at a time. To generate better code from\n * such idiot compilers (which are distressingly common on platforms\n * such as MS-DOS), expressions are made big and complex, and intermediate\n * results are assigned to variables in the expression where possible\n * so the compiler won't try to use a disjoint temporary and have to\n * spill. This makes the code a little hard to follow at times.\n * Sorry.\n *\n * Also, due to the deep nesting (it's all in one function, again, for\n * speed even on systems that can't inline), the indent amount is only\n * two spaces and variable names are very short.\n *\n * This does NOT currently detect a reference to before the beginning of\n * the file. It just blindly uses the circular buffer.\n */\nstatic int\ninfInflate(struct InflateContext *ctx)\n{\n  ulg b;  /* Bit buffer info - bit buffer itself */\n  unsigned k;  /* Number of low0order bits of b that are valid */\n  int s;  /* Bytes of valid input remaining */\n  unsigned char const *g; /* Input buffer pointer */\n\n  unsigned char *w; /* Window output write pointer */\n  unsigned r;  /* Space available after w (always >0) */\n\n  struct huft *tl, *td; /* Tree info (const except for EOB processing) */\n  unsigned bl, bd;\n  unsigned ml, md;\n  struct huft const *t; /* Temporary tree pointer */\n\n  unsigned char const *p; /* Copy source pointer */\n  int i;\n  int e;\n  unsigned n;  /* Copy length */\n  unsigned d;  /* Copy distance */\n\n  LOADBITBUF; \t/* Load b, k, s, g */\n\n  w = ctx->outptr;\n  r = ctx->slideend-w;\n  pgpAssert(r);\n\n  tl = ctx->tree1;\t/* Literal/length tree */\n  bl = ctx->bits1;\t/* Number of bits in top-level table */\n  ml = mask[bl];\t/* Mask of that many bits */\n\n  td = ctx->tree2;\t/* Distance tree */\n  bd = ctx->bits2;\t/* Number of bits in top-level table */\n  md = mask[bd];\t/* Mask of that many bits */\n\n  /*\n  * We don't always need all of these, but it's easier to always\n  * load them than to do it conditionally.\n  */\n  t = ctx->t;\n  n = ctx->copylen;\n  d = ctx->distbase;\n  e = ctx->numbits;\n\n  switch (ctx->substate) {\n  case 0:\n    for (;;) {\t/* do until end of block */\n      /*\n       * This cheap loop does no input or output checking.\n       * At most 258 bytes of output are produced per iteration,\n       * so we must do no more than r/258 iterations.\n       * Also, at most 15+5+15+13 = 48 bits = 6 bytes are consumed\n       * every iteration, so we can do no more than s/6 iterations.\n       * Also, to allow for starting with an empty bit buffer and\n       * ending with a full one, subtract 4 bytes, so it's (s-4)/6.\n       *\n       * These are approximated by r/256-1 and (s-2)/8, respectively.\n       * Note: for a file that compresses to 258 bytes per symbol (e.g. all\n       * the same character), that approximation would break down if\n       *\n       * r/256-1 > r/258\n       * thus, 258 * r - 256 * 258 > 256*r\n       * thus, 2 * r > 256 * 258\n       * thus, r > 128 * 258 = 33024 > 32768\n       *\n       * Of course, the window is <= 32768, so it's not a concern.\n       *\n       * For the input approximation to break down, you'd have to have\n       *\n       * (s-2)/8 > (s-4)/6\n       * thus, 6*s - 12 > 8*s - 32\n       * thus, 20 > 2*s\n       * thus, 10 > s\n       *\n       * But for s<10, both approximations (since this is integer math)\n       * return 0, so it's not a problem. The r/258 limit is usually\n       * hit first, so the crudeness of this approximation is acceptable.\n       */\n      while (r >= 512 && s >= 10) {\n\t/* Compute number of iterations we can do, worst-case */\n\tif ((e = (s - 2) >> 3) < (i = (r >> 8) - 1))\n\t  i = e;\n\t/*\n\t * This is the cheap loop, which is performed i times before\n\t * the available buffer space is re-evaluated. If you want to\n\t * understand how the inflation process works, this is the best\n\t * part of the code to read, since it isn't cluttered up with\n\t * error checking. First comes a literal/length code, which\n\t * can be either a literal (0-255), an end of block code (256),\n\t */\n\tdo {\n\t  GRABBITS(20); /* max bits for literal/length code */\n\t  t = tl + ((unsigned)b & ml);\n\t  if ((e = t->exop) < 0) {\n\t    do {\n\t      if (e == -128)\n\t\treturn INFERR_BADINPUT;\n\t      DUMPBITS(t->bits);\n\t      e = -e;\n\t      t = t->next + ((unsigned)b & mask[e]);\n\t    } while ((e = t->exop) < 0);\n\t  }\n\t  DUMPBITS(t->bits);\n\t  if (e & 16) { /* then it's a literal */\n\t    *w++ = (unsigned char)t->base;\n\t    continue;\n\t  }\n\t  if (e & 32)  /* EOB */\n\t    goto EOB; /* At end of function */\n\n\t  /* Else length code */\n\n\t  /* get length of block to copy */\n\t  n = t->base + ((unsigned)b & mask[e]);\n\t  DUMPBITS(e);\n\n\t  /* decode distance of block to copy */\n\t  GRABBITS(15);\n\t  t = td + ((unsigned)b & md);\n\t  if ((e = t->exop) < 0) {\n\t    do {\n\t      if (e == -128)\n\t\treturn INFERR_BADINPUT;\n\t      DUMPBITS(t->bits);\n\t      e = -e;\n\t      t = t->next + ((unsigned)b & mask[e]);\n\t    } while ((e = t->exop) < 0);\n\t  }\n\t  DUMPBITS(t->bits);\n\t  GRABBITS((unsigned)e); /* get up to 13 extra bits */\n\t  d = t->base + ((unsigned)b & mask[e]);\n\t  DUMPBITS((unsigned)e);\n\n#if WSIZE < 32768\n\t  if (d > ctx->slidelen)\n\t    return INFERR_BADINPUT;\n#endif\n\n\t  /* do the copy */\n\t  if ((unsigned)(w - ctx->slide) >= d) {\n\t    p = w - d;\n\t    *w++ = *p++;\n\t    *w++ = *p++;\n\t    do {\n\t      *w++ = *p++;\n\t    } while (--n);\n\t  } else {\n\t    n += 2;\n\t    p = w - d + ctx->slidelen;\n\t    do {\n\t      n -= (e = (unsigned)(e = ctx->slideend - (p>w?p:w)) > n ? n : e);\n\t      do {\n\t\t*w++ = *p++;\n\t      } while (--e);\n\t      if (p == ctx->slideend)\n\t\tp = ctx->slide;\n\t    } while (n);\n\t  }\n\t} while (--i);\n\n\tr = ctx->slideend - w;\n      } /* while (we can use the cheap loop) */\n\n      /*\n       * Okay, we've fallen through from the cheap loop to the\n       * expensive loop. This one checks each time it gets bits\n       * from the input or writes bytes to the output that there\n       * is enough room. However, there are two versions of\n       * much of *this*, too! The first uses worst-case figures\n       * for the amount of input data needed, and obtains one batch of\n       * input bits for several uses.\n       * The second carefully avoids asking for any more bits than it really\n       * needs. When it gives up and returns, it is really not possible\n       * to extract any more symbols from the input data.\n       */\n      /* Pessimistic estimate of bits for literal/length: 15+5 */\n      GETBITSOR(20, goto getlitlength2)\n      t = tl + ((unsigned)b & ml);\n      if ((e = t->exop) < 0) {\n\tdo {\n\t  if (e == -128)\n\t    return INFERR_BADINPUT;\n\t  DUMPBITS(t->bits);\n\t  e = -e;\n\t  t = t->next + ((unsigned)b & mask[e]);\n\t} while ((e = t->exop) < 0);\n      }\n      DUMPBITS(t->bits);\n      if (e & 16) { /* then it's a literal */\n\t*w++ = (unsigned char)t->base;\n\tif (--r == 0) {\n\t  SAVEBITBUF;\n\t  ctx->outptr = w;\n\t  ctx->substate = 0; /* Restart at top of loop */\n\t  return 2; /* Output buffer full */\n\t}\n\tcontinue;\n      }\n\n      if (e & 32)\n\tbreak; /* Leave infinite loop */\n\n      goto gotlength;\n\ngetlitlength2:\n      /* Method 2: We don't even have 20 bits available - do it bit-by-bit. */\n      t = tl + ((unsigned)b & ml);\n      /*\n       * See if higher-order bits we're missing actually matter.\n       * We don't have to try to fill the bit buffer, because we only get\n       * here if s (number of following input bytes) is supposed to be zero.\n       */\n      if (k < (unsigned)t->bits) {\n\tctx->outptr = w;\n\tctx->substate = 0;\n\tSAVEBITBUFEMPTY;\n\treturn 1;\n      }\n      /* Actually, s is set (see GETBITSOR comment) to -1, so reset it */\n      s = 0;\n      if ((e = t->exop) < 0) {\n\tdo {\n\t  if (e == -128)\n\t    return INFERR_BADINPUT;\n\t  DUMPBITS(t->bits);\n\t  e = -e;\n\t  t = t->next;\ncase 1:\n\t  NEEDBITS2(e, t[(unsigned)b & mask[e]].bits,\n\t\t    ctx->t=t; ctx->outptr=w; ctx->numbits=e; ctx->substate=1)\n\t  t += (unsigned)b & mask[e];\n\t} while ((e = t->exop) < 0);\n      }\n      DUMPBITS(t->bits);\n      if (e & 16) { /* then it's a literal */\n\t*w++ = (unsigned char)t->base;\n\tif (--r == 0) {\n\t  /* We just filled the output buffer - return */\n\t  SAVEBITBUF;\n\t  ctx->outptr = w;\n\t  ctx->substate = 0; /* Restart at top of loop */\n\t  return 2; /* Output buffer full */\n\t}\n\tcontinue;\n      }\n\n      if (e & 32) /* EOB */\n\tbreak; /* Leave infinite loop */\n\n      /*FALLTHROUGH*/\ncase 2:\n      NEEDBITS(e, ctx->t = t; ctx->outptr=w; ctx->numbits=e; ctx->substate=2)\n\ngotlength:\n\n      /* All data is available - compute total length of block to copy */\n      n = t->base + ((unsigned)b & mask[e]);\n      DUMPBITS((unsigned)e);\n\n      /*FALLTHROUGH*/\ncase 3:\n      /* Get distance code - 15 is maximum code size */\n      GETBITSOR(15, goto getdistance2)\n      t = td + ((unsigned)b & md);\n      /* Negative t->exop means there's a subtable of 2^-e entries */\n      if ((e = t->exop) < 0) {\n\tdo {\n\t  if (e == -128)\n\t    return INFERR_BADINPUT;\t/* Invalid code (static table case) */\n\t  DUMPBITS(t->bits);\n\t  e = -e;\n\t  t = t->next + ((unsigned)b & mask[e]);\n\t} while ((e = t->exop) < 0);\n      }\n      goto gotdistance;\n\ngetdistance2:\n      /* We don't even have 15 bits available - do it bit-by-bit. */\n      t = td + ((unsigned)b & md);\n      /*\n       * See if higher-order bits we're missing actually matter.\n       * We don't have to try to fill the bit buffer, because we only get\n       * here if s (number of following input bytes) is supposed to be zero.\n       */\n      if (k < (unsigned)t->bits) {\n\tctx->outptr = w;\n\tctx->copylen = n;\n\tctx->substate = 3;\n\tSAVEBITBUFEMPTY;\n\treturn 1;\n      }\n      /* Actually (see GETBITSOR comment) s is set to -1, so reset it */\n      s = 0;\n      /* Negative t->exop means there's a subtable of 2^-e entries */\n      if ((e = t->exop) < 0) {\n\tdo {\n\t  if (e == -128)\n\t    return INFERR_BADINPUT;\t/* Invalid code (static table case) */\n\t  DUMPBITS(t->bits);\n\t  e = -e;\n\t  t = t->next;\ncase 4:\n\t  NEEDBITS2(e, t[(unsigned)b & mask[e]].bits, ctx->t=t; ctx->outptr=w;\n\t\t      ctx->copylen = n; ctx->numbits=e; ctx->substate=4)\n\t  t += (unsigned)b & mask[e];\n\t} while ((e = t->exop) < 0);\n      }\n\ngotdistance:\n      /* All data is available - compute the base distance */\n      DUMPBITS(t->bits);\n      d = t->base;\n      /*FALLTHROUGH*/\ncase 5:\n      /* e is number of bits extra following distance code (0..13) */\n      NEEDBITS(e, ctx->outptr=w; ctx->copylen=n; ctx->distbase=d;\n\t       ctx->numbits=e; ctx->substate=5)\n      d += ((unsigned)b & mask[e]);\n      DUMPBITS((unsigned)e);\n\n#if WSIZE < 32768\n      if (d > ctx->slidelen)\n\treturn INFERR_BADINPUT;\n#endif\n\n      /* do the copy, with handling for wrapping around end of buffer */\n      if ((unsigned)(w - ctx->slide) >= d && w + n < ctx->slideend - 2) {\n\t/* Simple case - neither source nor dest cross end of buffer */\n\tp = w - d;\n\tr -= n + 2;\n\t*w++ = *p++;\n\t*w++ = *p++;\n\tdo {\n\t  *w++ = *p++;\n\t} while (--n);\n      } else {\n\tn += 2; /* # of bytes to copy */\n\tp = ctx->slide + ((w - ctx->slide - d) & ctx->slidemask); /* src */\n\tdo {\n\t  /* Set e to number of bytes we can copy at once */\n\t  n -= (e = (unsigned)(e = ctx->slideend - (p>w?p:w)) > n ? n : e);\n\t  r -= e;\n\t  do {\n\t    *w++ = *p++;\n\t  } while (--e);\n\t  if (r == 0) { /* Did we just write everything we could? */\n\t    SAVEBITBUF;\n\t    ctx->outptr = w;\n\t    ctx->copylen = n;\n\t    ctx->distbase = d; /* Save copy distance to recompute p */\n\t    ctx->substate = 6;\n\t    return 2; /* Need more output space */\ncase 6:\n\t    p = ctx->slide + ((w - ctx->slide - d) & ctx->slidemask);\n\t  }\n\t  if (p == ctx->slideend)\n\t    p = ctx->slide;\n\t} while (n);\n      }\n    } /* for(;;) */\n  } /* switch(ctx->subcase) */\n\nEOB:\n  /* End of Block */\n  ctx->outptr = w;\n  SAVEBITBUF;\n  ctx->state = STATE_START;\n  ctx->substate = 0;\n\n  if (tl && tl != fixed_tl)\n    huft_free(tl);\n  if (td && td != fixed_td)\n    huft_free(td);\n  ctx->tree1 = 0;\n  ctx->tree2 = 0;\n\n  return 0;\n}\n\n\n/*\n * Start state - read 3 bits, which are last block flag (set to 1 on\n * last block), and 2 bits of block type.\n */\nstatic int\ninfStart(struct InflateContext *ctx)\n{\n\tulg b;\n\tunsigned k;\n\tint s;\n\tunsigned char const *g;\n\tint retval = 0;\n\n\tif (ctx->lastblock) {\n\t\tctx->state = STATE_DONE;\n\t\treturn 0;\n\t}\n\n\tLOADBITBUF;\n\tNEEDBITS(3, (void)0);\n\n\tctx->lastblock = (int)(b & 1);\n\tDUMPBITS(1);\n\n\tswitch(b & 3) {\n\tcase 0: /* Stored */\n\t\tctx->state = STATE_STOREDLEN;\n\t\tbreak;\n\tcase 1: /* Static - build fixed trees and start decoding */\n\t\tretval = infFixedTree();\n\t\tctx->tree1 = fixed_tl;\n\t\tctx->bits1 = fixed_bl;\n\t\tctx->tree2 = fixed_td;\n\t\tctx->bits2 = fixed_bd;\n\t\tctx->state = STATE_INFLATE;\n\t\tbreak;\n\tcase 2: /* Dynamic */\n\t\tctx->state = STATE_DYN_HDR;\n\t\tbreak;\n\tcase 3: /* Illegal */\n\t\tretval = INFERR_BADINPUT;\n\t\tbreak;\n\t}\n\n\tDUMPBITS(2);\n\tSAVEBITBUF;\n\n\tctx->substate = 0;\n\treturn retval;\n}\n\n/*\n * Get a pointer to available data in the output buffer\n */\nunsigned char const *\ninfGetBytes(struct InflateContext *ctx, unsigned *len)\n{\n\t*len = ctx->outptr - ctx->readptr;\n\treturn *len ? ctx->readptr : 0;\n}\n\n/*\n * Mark data in the output buffer as already read. We don't start\n * accepting new data until the entire output buffer has been read,\n * at which point the outptr is set back to the beginning of the\n * buffer.\n */\nvoid\ninfSkipBytes(struct InflateContext *ctx, unsigned len)\n{\n\tpgpAssert(len <= (unsigned)(ctx->outptr - ctx->readptr));\n\n\tctx->readptr += len;\n\n\t/* If at end of buffer, recirculate */\n\tif (ctx->readptr == ctx->slideend) {\n\t\tpgpAssert(ctx->outptr == ctx->slideend);\n\t\tctx->readptr = ctx->outptr = ctx->slide;\n\t}\n}\n\n\n/*\n * Returns number of bytes written.\n * *error < 0 on error, == 0 if no error (done with input or output full)\n */\nsize_t\ninfWrite(struct InflateContext *ctx, unsigned char const *buf, size_t len,\nint *error)\n{\n\tint i;\n\n\tif (ctx->outptr == ctx->slideend) {\n\t\t*error = (ctx->state == STATE_STOP) ? 0 : ctx->substate;\n\t\treturn 0; /* Out of output space! */\n\t}\n\n\tctx->inptr = buf;\n\t/* Decompression code can't handle more than INT_MAX bytes at a time */\n\tctx->inlen = len > INT_MAX ? INT_MAX : (int)len;\n\n\tdo {\n\t\tswitch(ctx->state) {\n\t\tcase STATE_START:\n\t\t\ti = infStart(ctx);\n\t\t\tbreak;\n\t\tcase STATE_STOREDLEN:\n\t\t\ti = infStoredLen(ctx);\n\t\t\tbreak;\n\t\tcase STATE_STORED:\n\t\t\ti = infStored(ctx);\n\t\t\tbreak;\n\t\tcase STATE_DYN_HDR:\n\t\t\ti = infDynHdr(ctx);\n\t\t\tbreak;\n\t\tcase STATE_DYN_BITS:\n\t\t\ti = infDynBits(ctx);\n\t\t\tbreak;\n\t\tcase STATE_DYN_TREE:\n\t\t\ti = infDynTree(ctx);\n\t\t\tbreak;\n\t\tcase STATE_INFLATE:\n\t\t\ti = infInflate(ctx);\n\t\t\tbreak;\n\t\tcase STATE_DONE:\n\t\t\tif (ctx->inlen || ctx->bufbits > 7)\n\t\t\t\t i = INFERR_LONG;\n#if STRICT\n\t\t\telse if (ctx->bitbuffer & mask[ctx->bufbits])\n\t\t\t\ti = INFERR_BADINPUT; /* Unused bits != 0 */\n#endif\n\t\t\telse\n\t\t\t\ti = 2; /* Read output, please */\n\t\t\tbreak;\n\t\tcase STATE_STOP:\n\t\t\ti = ctx->substate;\n\t\t\tbreak;\n\t\tdefault:\n\t\t\tpgpAssert(i=0); /* To shut up compiler warnings */\n\t\t}\n\t} while (i == 0);\n\n\tif (i < 0) {\n\t\tctx->state = STATE_STOP;\n\t\tctx->substate = i;\n\t\t*error = i;\n\t} else {\n\t\t*error = 0;\n\t}\n\n\tpgpAssert((size_t)(ctx->inptr - buf) == len - ctx->inlen);\n\treturn (size_t)(ctx->inptr - buf); /* Bytes read */\n}\n\n/*\n * Signal EOF, detecting truncated messages.\n * If another error has been reported, this just repeats it.\n */\n/* New version, hopefully useful. */\nint\ninfEOF(struct InflateContext *ctx)\n{\n\t/* If processing is halted, just return the last error (if any) */\n\tif (ctx->state == STATE_STOP)\n\t\treturn ctx->substate;\n\n\t/* If expecting still more input, we're short */\n\tif (ctx->state != STATE_DONE)\n\t\treturn INFERR_SHORT;\n\n\t/* Otherwise, all is well. */\n\treturn 0;\n}\n\nstruct InflateContext *\ninfAlloc(void)\n{\n\tstruct InflateContext *ctx;\n\tunsigned char *slide;\n\n\tslide = (unsigned char *)pgpMemAlloc(WSIZE);\n\tif (!slide)\n\t\treturn 0;\n\tctx = (struct InflateContext *)pgpMemAlloc(sizeof(*ctx));\n\tif (!ctx) {\n\t\tpgpMemFree(slide);\n\t\treturn 0;\n\t}\n\tctx->slide = slide;\n\tctx->slideend = slide+WSIZE;\n\tctx->slidelen = WSIZE;\n\tctx->slidemask = WSIZE-1;\n\n\tctx->outptr = slide;\n\tctx->readptr = slide;\n\n\tctx->state = STATE_START;\n\tctx->substate = 0;\n\tctx->inlen = 0;\n\tctx->bitbuffer = 0;\n\tctx->bufbits = 0;\n\tctx->lastblock = 0;\n\n\tctx->tree1 = 0;\n\tctx->tree2 = 0;\n\n\treturn ctx;\n}\n\nvoid\ninfFree(struct InflateContext *ctx)\n{\n\tif (ctx->tree1 && ctx->tree1 != fixed_tl)\n\t\thuft_free(ctx->tree1);\n\tif (ctx->tree2 && ctx->tree2 != fixed_td)\n\t\thuft_free(ctx->tree2);\n\n\tif (ctx->slide) {\n#if SECURE\n\t\tmemset(ctx->slide, 0, ctx->slidelen);\n#endif\n\t\tpgpMemFree(ctx->slide);\n\t}\n#if SECURE\n\tmemset(ctx, 0, sizeof(*ctx));\n#endif\n\tpgpMemFree(ctx);\n}\n"},{"id":"37281","messageId":"200703162345.42784.Josef.Weidendorfer@gmx.de","threadId":"7267","inReplyTo":"Pine.LNX.4.64.0703160841360.3816@woody.linux-foundation.org","subject":"Re: cleaner/better zlib sources?","fromName":"Josef Weidendorfer","fromEmail":"josef.weidendorfer@gmx.de","sentAt":"2007-03-16T22:45:42Z","receivedAt":"2007-03-16T22:45:42Z","isPatch":false,"sender":{"key":"josef.weidendorfer@gmx.de","avatar":null},"body":"On Friday 16 March 2007, Linus Torvalds wrote:\n> (Btw, to get this level of detail, you need to link statically, at least \n> if you are using Fedora Core. If you do the normal dynamic linking, \n> oprofile will not be able to show you which function, and will just say \n> that 50% of all time was spent in libz.so.1.2.3).\n\nI see the same here on OpenSuse 10.2.\nThis is because opreport currently does not take symbols from the dynamic\nsymbol table into account. Patching the symbol loader (I just send a\npatch to the oprofile mailing list), I get the same detail with dynamic\nlinking.\n\nJosef\n"}]}