summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--ChangeLog51
-rw-r--r--Makefile59
-rw-r--r--README57
-rw-r--r--adler32.c46
-rw-r--r--compress.c55
-rw-r--r--crc32.c103
-rw-r--r--deflate.c932
-rw-r--r--deflate.h270
-rw-r--r--example.c201
-rw-r--r--gzio.c459
-rw-r--r--infblock.c324
-rw-r--r--infblock.h26
-rw-r--r--infcodes.c217
-rw-r--r--infcodes.h25
-rw-r--r--inflate.c221
-rw-r--r--inflate.h22
-rw-r--r--inftest.c67
-rw-r--r--inftrees.c471
-rw-r--r--inftrees.h62
-rw-r--r--infutil.c76
-rw-r--r--infutil.h86
-rw-r--r--minigzip.c210
-rw-r--r--trees.c1048
-rw-r--r--uncompr.c58
-rw-r--r--zconf.h66
-rw-r--r--zlib.h604
-rw-r--r--zutil.c164
-rw-r--r--zutil.h166
28 files changed, 6146 insertions, 0 deletions
diff --git a/ChangeLog b/ChangeLog
new file mode 100644
index 0000000..40fc89f
--- /dev/null
+++ b/ChangeLog
@@ -0,0 +1,51 @@
1 ChangeLog file for zlib
2
3Changes in 0.71 (14 April 95)
4- Fixed more MSDOS compilation problems :( There is still a bug with
5 TurboC large model.
6
7Changes in 0.7 (14 April 95)
8- Added full inflate support.
9- Simplified the crc32() interface. The pre- and post-conditioning
10 (one's complement) is now done inside crc32(). WARNING: this is
11 incompatible with previous versions; see zlib.h for the new usage.
12
13Changes in 0.61 (12 April 95)
14- workaround for a bug in TurboC. example and minigzip now work on MSDOS.
15
16Changes in 0.6 (11 April 95)
17- added minigzip.c
18- added gzdopen to reopen a file descriptor as gzFile
19- added transparent reading of non-gziped files in gzread.
20- fixed bug in gzread (don't read crc as data)
21- fixed bug in destroy (gzio.c) (don't return Z_STREAM_END for gzclose).
22- don't allocate big arrays in the stack (for MSDOS)
23- fix some MSDOS compilation problems
24
25Changes in 0.5:
26- do real compression in deflate.c. Z_PARTIAL_FLUSH is supported but
27 not yet Z_FULL_FLUSH.
28- support decompression but only in a single step (forced Z_FINISH)
29- added opaque object for zalloc and zfree.
30- added deflateReset and inflateReset
31- added a variable zlib_version for consistency checking.
32- renamed the 'filter' parameter of deflateInit2 as 'strategy'.
33 Added Z_FILTERED and Z_HUFFMAN_ONLY constants.
34
35Changes in 0.4:
36- avoid "zip" everywhere, use zlib instead of ziplib.
37- suppress Z_BLOCK_FLUSH, interpret Z_PARTIAL_FLUSH as block flush
38 if compression method == 8.
39- added adler32 and crc32
40- renamed deflateOptions as deflateInit2, call one or the other but not both
41- added the method parameter for deflateInit2.
42- added inflateInit2
43- simplied considerably deflateInit and inflateInit by not supporting
44 user-provided history buffer. This is supported only in deflateInit2
45 and inflateInit2.
46
47Changes in 0.3:
48- prefix all macro names with Z_
49- use Z_FINISH instead of deflateEnd to finish compression.
50- added Z_HUFFMAN_ONLY
51- added gzerror()
diff --git a/Makefile b/Makefile
new file mode 100644
index 0000000..478920a
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,59 @@
1CC=cc
2CFLAGS=-O
3#CFLAGS=-g -DDEBUG
4LDFLAGS=-L. -lgz
5
6RANLIB=ranlib
7
8OBJS = adler32.o compress.o crc32.o gzio.o uncompr.o deflate.o trees.o \
9 zutil.o inflate.o infblock.o inftrees.o infcodes.o infutil.o
10
11TEST_OBJS = example.o minigzip.o inftest.o
12
13all: example minigzip inftest
14
15test: all
16 ./example
17 echo hello world | ./minigzip | ./minigzip -d
18
19libgz.a: $(OBJS)
20 ar rc $@ $(OBJS)
21 $(RANLIB) $@
22
23example: example.o libgz.a
24 $(CC) $(CFLAGS) -o $@ example.o $(LDFLAGS)
25
26minigzip: minigzip.o libgz.a
27 $(CC) $(CFLAGS) -o $@ minigzip.o $(LDFLAGS)
28
29inftest: inftest.o libgz.a
30 $(CC) $(CFLAGS) -o $@ inftest.o $(LDFLAGS)
31
32clean:
33 rm -f *.o example minigzip inftest libgz.a foo.gz
34
35zip:
36 zip -ul9 zlib README ChangeLog Makefile *.[ch]
37
38tgz:
39 cd ..; tar cfz zlib/zlib.tgz zlib/README zlib/ChangeLog zlib/Makefile \
40 zlib/*.[ch]
41
42# DO NOT DELETE THIS LINE -- make depend depends on it.
43
44adler32.o: zutil.h zlib.h zconf.h
45compress.o: zlib.h zconf.h
46crc32.o: zutil.h zlib.h zconf.h
47deflate.o: deflate.h zutil.h zlib.h zconf.h
48example.o: zlib.h zconf.h
49gzio.o: zutil.h zlib.h zconf.h
50infblock.o: zutil.h zlib.h zconf.h infblock.h inftrees.h infcodes.h infutil.h
51infcodes.o: zutil.h zlib.h zconf.h inftrees.h infutil.h infcodes.h
52inflate.o: zutil.h zlib.h zconf.h infblock.h
53inftest.o: zutil.h zlib.h zconf.h
54inftrees.o: zutil.h zlib.h zconf.h inftrees.h
55infutil.o: zutil.h zlib.h zconf.h inftrees.h infutil.h
56minigzip.o: zlib.h zconf.h
57trees.o: deflate.h zutil.h zlib.h zconf.h
58uncompr.o: zlib.h zconf.h
59zutil.o: zutil.h zlib.h zconf.h
diff --git a/README b/README
new file mode 100644
index 0000000..5c42402
--- /dev/null
+++ b/README
@@ -0,0 +1,57 @@
1zlib 0.71 is a beta version of a general purpose compression library.
2
3The data format used by the zlib library is described in the
4file zlib-3.1.doc, deflate-1.1.doc and gzip-4.1.doc, available
5in ftp.uu.net:/pub/archiving/zip/doc.
6
7All functions of the compression library are documented in the file
8zlib.h. A usage example of the library is given in the file example.c
9which also tests that the library is working correctly.
10To compile all files and run the test program, just type: make test
11
12The changes made in version 0.71 are documented in the file ChangeLog.
13The main changes since 0.5 are:
14- added full inflate support
15- added minigzip.c
16- added gzdopen to reopen a file descriptor as gzFile
17- added transparent reading of non-gziped files in gzread.
18- fix some MSDOS problems. example and minigzip now work on MSDOS.
19- Simplified the crc32() interface. The pre- and post-conditioning
20 (one's complement) is now done inside crc32(). WARNING: this is
21 incompatible with previous versions; see zlib.h for the new usage.
22
23On MSDOS, this version works in large and small model with MSC; in
24small model only with TurboC (bug being investigated). For both
25compilers, small model compression works only for small values of
26MEM_LEVEL and WBITS (see zutil.h), and requires -DUSE_CALLOC.
27
28
29 Copyright (C) 1995 Jean-loup Gailly and Mark Adler
30
31 This software is provided 'as-is', without any express or implied
32 warranty. In no event will the authors be held liable for any damages
33 arising from the use of this software.
34
35 Permission is granted to anyone to use this software for any purpose,
36 including commercial applications, and to alter it and redistribute it
37 freely, subject to the following restrictions:
38
39 1. The origin of this software must not be misrepresented; you must not
40 claim that you wrote the original software. If you use this software
41 in a product, an acknowledgment in the product documentation would be
42 appreciated but is not required.
43 2. Altered source versions must be plainly marked as such, and must not be
44 misrepresented as being the original software.
45 3. This notice may not be removed or altered from any source distribution.
46
47 Jean-loup Gailly Mark Adler
48 gzip@prep.ai.mit.edu madler@cco.caltech.edu
49
50If you use the zlib library in a product, we would appreciate *not*
51receiving lengthy legal documents to sign. The sources are provided
52for free but without warranty of any kind. The library has been
53entirely written by Jean-loup Gailly and Mark Adler; it does not
54include third-party code.
55
56If you redistribute modified sources, we would appreciate that you include
57in the file ChangeLog history information documenting your changes.
diff --git a/adler32.c b/adler32.c
new file mode 100644
index 0000000..0b2b820
--- /dev/null
+++ b/adler32.c
@@ -0,0 +1,46 @@
1/* adler32.c -- compute the Adler-32 checksum of a data stream
2 * Copyright (C) 1995 Mark Adler
3 * For conditions of distribution and use, see copyright notice in zlib.h
4 */
5
6/* $Id: adler32.c,v 1.5 1995/04/14 14:49:51 jloup Exp $ */
7
8#include "zutil.h"
9
10#define BASE 65521 /* largest prime smaller than 65536 */
11#define NMAX 5552
12/* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */
13
14#define DO1(buf) {s1 += *buf++; s2 += s1;}
15#define DO2(buf) DO1(buf); DO1(buf);
16#define DO4(buf) DO2(buf); DO2(buf);
17#define DO8(buf) DO4(buf); DO4(buf);
18#define DO16(buf) DO8(buf); DO8(buf);
19
20/* ========================================================================= */
21uLong adler32(adler, buf, len)
22 uLong adler;
23 Byte *buf;
24 uInt len;
25{
26 unsigned long s1 = adler & 0xffff;
27 unsigned long s2 = (adler >> 16) & 0xffff;
28 int k;
29
30 if (buf == Z_NULL) return 1L;
31
32 while (len > 0) {
33 k = len < NMAX ? len : NMAX;
34 len -= k;
35 while (k >= 16) {
36 DO16(buf);
37 k -= 16;
38 }
39 if (k != 0) do {
40 DO1(buf);
41 } while (--k);
42 s1 %= BASE;
43 s2 %= BASE;
44 }
45 return (s2 << 16) | s1;
46}
diff --git a/compress.c b/compress.c
new file mode 100644
index 0000000..8edcb2a
--- /dev/null
+++ b/compress.c
@@ -0,0 +1,55 @@
1/* compress.c -- compress a memory buffer
2 * Copyright (C) 1995 Jean-loup Gailly.
3 * For conditions of distribution and use, see copyright notice in zlib.h
4 */
5
6/* $Id: compress.c,v 1.4 1995/04/10 15:52:04 jloup Exp $ */
7
8#include "zlib.h"
9
10/* ===========================================================================
11 Compresses the source buffer into the destination buffer. sourceLen is
12 the byte length of the source buffer. Upon entry, destLen is the total
13 size of the destination buffer, which must be at least 0.1% larger than
14 sourceLen plus 8 bytes. Upon exit, destLen is the actual size of the
15 compressed buffer.
16 This function can be used to compress a whole file at once if the
17 input file is mmap'ed.
18 compress returns Z_OK if success, Z_MEM_ERROR if there was not
19 enough memory, Z_BUF_ERROR if there was not enough room in the output
20 buffer.
21*/
22int compress (dest, destLen, source, sourceLen)
23 Byte *dest;
24 uLong *destLen;
25 Byte *source;
26 uLong sourceLen;
27{
28 z_stream stream;
29 int err;
30
31 stream.next_in = source;
32 stream.avail_in = (uInt)sourceLen;
33 /* Check for source > 64K on 16-bit machine: */
34 if ((uLong)stream.avail_in != sourceLen) return Z_BUF_ERROR;
35
36 stream.next_out = dest;
37 stream.avail_out = (uInt)*destLen;
38 if ((uLong)stream.avail_out != *destLen) return Z_BUF_ERROR;
39
40 stream.zalloc = (alloc_func)0;
41 stream.zfree = (free_func)0;
42
43 err = deflateInit(&stream, Z_DEFAULT_COMPRESSION);
44 if (err != Z_OK) return err;
45
46 err = deflate(&stream, Z_FINISH);
47 if (err != Z_OK) {
48 deflateEnd(&stream);
49 return err;
50 }
51 *destLen = stream.total_out;
52
53 err = deflateEnd(&stream);
54 return err;
55}
diff --git a/crc32.c b/crc32.c
new file mode 100644
index 0000000..e8d385f
--- /dev/null
+++ b/crc32.c
@@ -0,0 +1,103 @@
1/* crc32.c -- compute the CRC-32 of a data stream
2 * Copyright (C) 1995 Mark Adler
3 * For conditions of distribution and use, see copyright notice in zlib.h
4 */
5
6/* $Id: crc32.c,v 1.4 1995/04/14 14:55:12 jloup Exp $ */
7
8#include "zlib.h"
9
10extern uLong crc_table[]; /* crc table, defined below */
11
12/* ========================================================================= */
13uLong crc32(crc, buf, len)
14 uLong crc;
15 Byte *buf;
16 uInt len;
17{
18 if (buf == Z_NULL) return 0L;
19 crc = crc ^ 0xffffffffL;
20 if (len) do {
21 crc = crc_table[((int)crc ^ (*buf++)) & 0xff] ^ (crc >> 8);
22 } while (--len);
23 return crc ^ 0xffffffffL;
24}
25
26/* =========================================================================
27 * Make the crc table. This function is needed only if you want to compute
28 * the table dynamically.
29 */
30#ifdef DYNAMIC_CRC_TABLE
31
32void make_crc_table()
33{
34 uLong c;
35 int n, k;
36
37 for (n = 0; n &lt; 256; n++)
38 {
39 c = (uLong)n;
40 for (k = 0; k &lt; 8; k++)
41 c = c & 1 ? 0xedb88320L ^ (c >> 1) : c >> 1;
42 crc_table[n] = c;
43 }
44}
45#endif
46
47/* ========================================================================
48 * Table of CRC-32's of all single-byte values (made by make_crc_table)
49 */
50uLong crc_table[] = {
51 0x00000000L, 0x77073096L, 0xee0e612cL, 0x990951baL, 0x076dc419L,
52 0x706af48fL, 0xe963a535L, 0x9e6495a3L, 0x0edb8832L, 0x79dcb8a4L,
53 0xe0d5e91eL, 0x97d2d988L, 0x09b64c2bL, 0x7eb17cbdL, 0xe7b82d07L,
54 0x90bf1d91L, 0x1db71064L, 0x6ab020f2L, 0xf3b97148L, 0x84be41deL,
55 0x1adad47dL, 0x6ddde4ebL, 0xf4d4b551L, 0x83d385c7L, 0x136c9856L,
56 0x646ba8c0L, 0xfd62f97aL, 0x8a65c9ecL, 0x14015c4fL, 0x63066cd9L,
57 0xfa0f3d63L, 0x8d080df5L, 0x3b6e20c8L, 0x4c69105eL, 0xd56041e4L,
58 0xa2677172L, 0x3c03e4d1L, 0x4b04d447L, 0xd20d85fdL, 0xa50ab56bL,
59 0x35b5a8faL, 0x42b2986cL, 0xdbbbc9d6L, 0xacbcf940L, 0x32d86ce3L,
60 0x45df5c75L, 0xdcd60dcfL, 0xabd13d59L, 0x26d930acL, 0x51de003aL,
61 0xc8d75180L, 0xbfd06116L, 0x21b4f4b5L, 0x56b3c423L, 0xcfba9599L,
62 0xb8bda50fL, 0x2802b89eL, 0x5f058808L, 0xc60cd9b2L, 0xb10be924L,
63 0x2f6f7c87L, 0x58684c11L, 0xc1611dabL, 0xb6662d3dL, 0x76dc4190L,
64 0x01db7106L, 0x98d220bcL, 0xefd5102aL, 0x71b18589L, 0x06b6b51fL,
65 0x9fbfe4a5L, 0xe8b8d433L, 0x7807c9a2L, 0x0f00f934L, 0x9609a88eL,
66 0xe10e9818L, 0x7f6a0dbbL, 0x086d3d2dL, 0x91646c97L, 0xe6635c01L,
67 0x6b6b51f4L, 0x1c6c6162L, 0x856530d8L, 0xf262004eL, 0x6c0695edL,
68 0x1b01a57bL, 0x8208f4c1L, 0xf50fc457L, 0x65b0d9c6L, 0x12b7e950L,
69 0x8bbeb8eaL, 0xfcb9887cL, 0x62dd1ddfL, 0x15da2d49L, 0x8cd37cf3L,
70 0xfbd44c65L, 0x4db26158L, 0x3ab551ceL, 0xa3bc0074L, 0xd4bb30e2L,
71 0x4adfa541L, 0x3dd895d7L, 0xa4d1c46dL, 0xd3d6f4fbL, 0x4369e96aL,
72 0x346ed9fcL, 0xad678846L, 0xda60b8d0L, 0x44042d73L, 0x33031de5L,
73 0xaa0a4c5fL, 0xdd0d7cc9L, 0x5005713cL, 0x270241aaL, 0xbe0b1010L,
74 0xc90c2086L, 0x5768b525L, 0x206f85b3L, 0xb966d409L, 0xce61e49fL,
75 0x5edef90eL, 0x29d9c998L, 0xb0d09822L, 0xc7d7a8b4L, 0x59b33d17L,
76 0x2eb40d81L, 0xb7bd5c3bL, 0xc0ba6cadL, 0xedb88320L, 0x9abfb3b6L,
77 0x03b6e20cL, 0x74b1d29aL, 0xead54739L, 0x9dd277afL, 0x04db2615L,
78 0x73dc1683L, 0xe3630b12L, 0x94643b84L, 0x0d6d6a3eL, 0x7a6a5aa8L,
79 0xe40ecf0bL, 0x9309ff9dL, 0x0a00ae27L, 0x7d079eb1L, 0xf00f9344L,
80 0x8708a3d2L, 0x1e01f268L, 0x6906c2feL, 0xf762575dL, 0x806567cbL,
81 0x196c3671L, 0x6e6b06e7L, 0xfed41b76L, 0x89d32be0L, 0x10da7a5aL,
82 0x67dd4accL, 0xf9b9df6fL, 0x8ebeeff9L, 0x17b7be43L, 0x60b08ed5L,
83 0xd6d6a3e8L, 0xa1d1937eL, 0x38d8c2c4L, 0x4fdff252L, 0xd1bb67f1L,
84 0xa6bc5767L, 0x3fb506ddL, 0x48b2364bL, 0xd80d2bdaL, 0xaf0a1b4cL,
85 0x36034af6L, 0x41047a60L, 0xdf60efc3L, 0xa867df55L, 0x316e8eefL,
86 0x4669be79L, 0xcb61b38cL, 0xbc66831aL, 0x256fd2a0L, 0x5268e236L,
87 0xcc0c7795L, 0xbb0b4703L, 0x220216b9L, 0x5505262fL, 0xc5ba3bbeL,
88 0xb2bd0b28L, 0x2bb45a92L, 0x5cb36a04L, 0xc2d7ffa7L, 0xb5d0cf31L,
89 0x2cd99e8bL, 0x5bdeae1dL, 0x9b64c2b0L, 0xec63f226L, 0x756aa39cL,
90 0x026d930aL, 0x9c0906a9L, 0xeb0e363fL, 0x72076785L, 0x05005713L,
91 0x95bf4a82L, 0xe2b87a14L, 0x7bb12baeL, 0x0cb61b38L, 0x92d28e9bL,
92 0xe5d5be0dL, 0x7cdcefb7L, 0x0bdbdf21L, 0x86d3d2d4L, 0xf1d4e242L,
93 0x68ddb3f8L, 0x1fda836eL, 0x81be16cdL, 0xf6b9265bL, 0x6fb077e1L,
94 0x18b74777L, 0x88085ae6L, 0xff0f6a70L, 0x66063bcaL, 0x11010b5cL,
95 0x8f659effL, 0xf862ae69L, 0x616bffd3L, 0x166ccf45L, 0xa00ae278L,
96 0xd70dd2eeL, 0x4e048354L, 0x3903b3c2L, 0xa7672661L, 0xd06016f7L,
97 0x4969474dL, 0x3e6e77dbL, 0xaed16a4aL, 0xd9d65adcL, 0x40df0b66L,
98 0x37d83bf0L, 0xa9bcae53L, 0xdebb9ec5L, 0x47b2cf7fL, 0x30b5ffe9L,
99 0xbdbdf21cL, 0xcabac28aL, 0x53b39330L, 0x24b4a3a6L, 0xbad03605L,
100 0xcdd70693L, 0x54de5729L, 0x23d967bfL, 0xb3667a2eL, 0xc4614ab8L,
101 0x5d681b02L, 0x2a6f2b94L, 0xb40bbe37L, 0xc30c8ea1L, 0x5a05df1bL,
102 0x2d02ef8dL
103};
diff --git a/deflate.c b/deflate.c
new file mode 100644
index 0000000..2409f07
--- /dev/null
+++ b/deflate.c
@@ -0,0 +1,932 @@
1/* deflate.c -- compress data using the deflation algorithm
2 * Copyright (C) 1995 Jean-loup Gailly.
3 * For conditions of distribution and use, see copyright notice in zlib.h
4 */
5
6/*
7 * ALGORITHM
8 *
9 * The "deflation" process depends on being able to identify portions
10 * of the input text which are identical to earlier input (within a
11 * sliding window trailing behind the input currently being processed).
12 *
13 * The most straightforward technique turns out to be the fastest for
14 * most input files: try all possible matches and select the longest.
15 * The key feature of this algorithm is that insertions into the string
16 * dictionary are very simple and thus fast, and deletions are avoided
17 * completely. Insertions are performed at each input character, whereas
18 * string matches are performed only when the previous match ends. So it
19 * is preferable to spend more time in matches to allow very fast string
20 * insertions and avoid deletions. The matching algorithm for small
21 * strings is inspired from that of Rabin & Karp. A brute force approach
22 * is used to find longer strings when a small match has been found.
23 * A similar algorithm is used in comic (by Jan-Mark Wams) and freeze
24 * (by Leonid Broukhis).
25 * A previous version of this file used a more sophisticated algorithm
26 * (by Fiala and Greene) which is guaranteed to run in linear amortized
27 * time, but has a larger average cost, uses more memory and is patented.
28 * However the F&G algorithm may be faster for some highly redundant
29 * files if the parameter max_chain_length (described below) is too large.
30 *
31 * ACKNOWLEDGEMENTS
32 *
33 * The idea of lazy evaluation of matches is due to Jan-Mark Wams, and
34 * I found it in 'freeze' written by Leonid Broukhis.
35 * Thanks to many people for bug reports and testing.
36 *
37 * REFERENCES
38 *
39 * Deutsch, L.P.,"'Deflate' Compressed Data Format Specification".
40 * Available in ftp.uu.net:/pub/archiving/zip/doc/deflate-1.1.doc
41 *
42 * A description of the Rabin and Karp algorithm is given in the book
43 * "Algorithms" by R. Sedgewick, Addison-Wesley, p252.
44 *
45 * Fiala,E.R., and Greene,D.H.
46 * Data Compression with Finite Windows, Comm.ACM, 32,4 (1989) 490-595
47 *
48 */
49
50/* $Id: deflate.c,v 1.3 1995/04/10 16:03:45 jloup Exp $ */
51
52#include "deflate.h"
53
54char copyright[] = " deflate Copyright 1995 Jean-loup Gailly ";
55/*
56 If you use the zlib library in a product, an acknowledgment is welcome
57 in the documentation of your product. If for some reason you cannot
58 include such an acknowledgment, I would appreciate that you keep this
59 copyright string in the executable of your product.
60 */
61
62#define NIL 0
63/* Tail of hash chains */
64
65#ifndef TOO_FAR
66# define TOO_FAR 4096
67#endif
68/* Matches of length 3 are discarded if their distance exceeds TOO_FAR */
69
70#define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1)
71/* Minimum amount of lookahead, except at the end of the input file.
72 * See deflate.c for comments about the MIN_MATCH+1.
73 */
74
75/* Values for max_lazy_match, good_match and max_chain_length, depending on
76 * the desired pack level (0..9). The values given below have been tuned to
77 * exclude worst case performance for pathological files. Better values may be
78 * found for specific files.
79 */
80
81typedef struct config_s {
82 ush good_length; /* reduce lazy search above this match length */
83 ush max_lazy; /* do not perform lazy search above this match length */
84 ush nice_length; /* quit search above this match length */
85 ush max_chain;
86} config;
87
88local config configuration_table[10] = {
89/* good lazy nice chain */
90/* 0 */ {0, 0, 0, 0}, /* store only */
91/* 1 */ {4, 4, 8, 4}, /* maximum speed, no lazy matches */
92/* 2 */ {4, 5, 16, 8},
93/* 3 */ {4, 6, 32, 32},
94
95/* 4 */ {4, 4, 16, 16}, /* lazy matches */
96/* 5 */ {8, 16, 32, 32},
97/* 6 */ {8, 16, 128, 128},
98/* 7 */ {8, 32, 128, 256},
99/* 8 */ {32, 128, 258, 1024},
100/* 9 */ {32, 258, 258, 4096}}; /* maximum compression */
101
102/* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4
103 * For deflate_fast() (levels <= 3) good is ignored and lazy has a different
104 * meaning.
105 */
106
107#define EQUAL 0
108/* result of memcmp for equal strings */
109
110struct static_tree_desc_s {int dummy;}; /* for buggy compilers */
111
112/* ===========================================================================
113 * Prototypes for local functions.
114 */
115
116local void fill_window __P((deflate_state *s));
117local int deflate_fast __P((deflate_state *s, int flush));
118local int deflate_slow __P((deflate_state *s, int flush));
119local void lm_init __P((deflate_state *s));
120
121local int longest_match __P((deflate_state *s, IPos cur_match));
122#ifdef ASMV
123 void match_init __P((void)); /* asm code initialization */
124#endif
125
126#ifdef DEBUG
127local void check_match __P((deflate_state *s, IPos start, IPos match,
128 int length));
129#endif
130
131
132/* ===========================================================================
133 * Update a hash value with the given input byte
134 * IN assertion: all calls to to UPDATE_HASH are made with consecutive
135 * input characters, so that a running hash key can be computed from the
136 * previous key instead of complete recalculation each time.
137 */
138#define UPDATE_HASH(s,h,c) (h = (((h)<<s->hash_shift) ^ (c)) & s->hash_mask)
139
140/* ===========================================================================
141 * Insert string str in the dictionary and set match_head to the previous head
142 * of the hash chain (the most recent string with same hash key). Return
143 * the previous length of the hash chain.
144 * IN assertion: all calls to to INSERT_STRING are made with consecutive
145 * input characters and the first MIN_MATCH bytes of str are valid
146 * (except for the last MIN_MATCH-1 bytes of the input file).
147 */
148#define INSERT_STRING(s, str, match_head) \
149 (UPDATE_HASH(s, s->ins_h, s->window[(str) + MIN_MATCH-1]), \
150 s->prev[(str) & s->w_mask] = match_head = s->head[s->ins_h], \
151 s->head[s->ins_h] = (str))
152
153/* ========================================================================= */
154int deflateInit (strm, level)
155 z_stream *strm;
156 int level;
157{
158 return deflateInit2 (strm, level, DEFLATED, WBITS, MEM_LEVEL, 0);
159 /* To do: ignore strm->next_in if we use it as window */
160}
161
162/* ========================================================================= */
163int deflateInit2 (strm, level, method, windowBits, memLevel, strategy)
164 z_stream *strm;
165 int level;
166 int method;
167 int windowBits;
168 int memLevel;
169 int strategy;
170{
171 deflate_state *s;
172 int noheader = 0;
173
174 if (strm == Z_NULL) return Z_STREAM_ERROR;
175
176 strm->msg = Z_NULL;
177 if (strm->zalloc == Z_NULL) strm->zalloc = zcalloc;
178 if (strm->zfree == Z_NULL) strm->zfree = zcfree;
179
180 if (level == Z_DEFAULT_COMPRESSION) level = 6;
181
182 if (windowBits < 0) { /* undocumented feature: suppress zlib header */
183 noheader = 1;
184 windowBits = -windowBits;
185 }
186 if (memLevel < 1 || memLevel > MAX_MEM_LEVEL || method != DEFLATED ||
187 windowBits < 8 || windowBits > 15 || level < 1 || level > 9) {
188 return Z_STREAM_ERROR;
189 }
190 s = (deflate_state *) ZALLOC(strm, 1, sizeof(deflate_state));
191 if (s == Z_NULL) return Z_MEM_ERROR;
192 strm->state = (struct internal_state *)s;
193 s->strm = strm;
194
195 s->noheader = noheader;
196 s->w_bits = windowBits;
197 s->w_size = 1 << s->w_bits;
198
199 s->hash_bits = memLevel + 7;
200 s->hash_size = 1 << s->hash_bits;
201 s->hash_shift = ((s->hash_bits+MIN_MATCH-1)/MIN_MATCH);
202
203 s->window = (Byte*) ZALLOC(strm, s->w_size, 2*sizeof(Byte));
204 s->prev = (Pos*) ZALLOC(strm, s->w_size, sizeof(Pos));
205 s->head = (Pos*) ZALLOC(strm, s->hash_size, sizeof(Pos));
206
207 s->lit_bufsize = 1 << (memLevel + 6); /* 16K elements by default */
208
209 s->pending_buf = (uch*) ZALLOC(strm, s->lit_bufsize, 2*sizeof(ush));
210
211 if (s->window == Z_NULL || s->prev == Z_NULL || s->head == Z_NULL ||
212 s->pending_buf == Z_NULL) {
213 strm->msg = z_errmsg[1-Z_MEM_ERROR];
214 deflateEnd (strm);
215 return Z_MEM_ERROR;
216 }
217 s->d_buf = (ush*) &(s->pending_buf[s->lit_bufsize]);
218 s->l_buf = (uch*) &(s->pending_buf[3*s->lit_bufsize]);
219 /* We overlay pending_buf and d_buf+l_buf. This works since the average
220 * output size for (length,distance) codes is <= 32 bits (worst case
221 * is 15+15+13=33).
222 */
223
224 s->level = level;
225 s->strategy = strategy;
226 s->method = method;
227
228 return deflateReset(strm);
229}
230
231/* ========================================================================= */
232int deflateReset (strm)
233 z_stream *strm;
234{
235 deflate_state *s;
236
237 if (strm == Z_NULL || strm->state == Z_NULL ||
238 strm->zalloc == Z_NULL || strm->zfree == Z_NULL) return Z_STREAM_ERROR;
239
240 strm->total_in = strm->total_out = 0;
241 strm->msg = Z_NULL; /* use zfree if we ever allocate msg dynamically */
242 strm->data_type = Z_UNKNOWN;
243
244 s = (deflate_state *)strm->state;
245 s->pending = 0;
246 s->pending_out = s->pending_buf;
247
248 s->status = s->noheader ? BUSY_STATE : INIT_STATE;
249 s->adler = 1;
250
251 ct_init(s);
252 lm_init(s);
253
254 return Z_OK;
255}
256
257/* =========================================================================
258 * Put a short the pending_out buffer. The 16-bit value is put in MSB order.
259 * IN assertion: the stream state is correct and there is enough room in
260 * the pending_out buffer.
261 */
262local void putShortMSB (s, b)
263 deflate_state *s;
264 uInt b;
265{
266 put_byte(s, b >> 8);
267 put_byte(s, b & 0xff);
268}
269
270/* =========================================================================
271 * Flush as much pending output as possible.
272 */
273local void flush_pending(strm)
274 z_stream *strm;
275{
276 unsigned len = strm->state->pending;
277
278 if (len > strm->avail_out) len = strm->avail_out;
279 if (len == 0) return;
280
281 zmemcpy(strm->next_out, strm->state->pending_out, len);
282 strm->next_out += len;
283 strm->state->pending_out += len;
284 strm->total_out += len;
285 strm->avail_out -= len;
286 strm->state->pending -= len;
287 if (strm->state->pending == 0) {
288 strm->state->pending_out = strm->state->pending_buf;
289 }
290}
291
292/* ========================================================================= */
293int deflate (strm, flush)
294 z_stream *strm;
295 int flush;
296{
297 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
298
299 if (strm->next_out == Z_NULL || strm->next_in == Z_NULL) {
300 ERR_RETURN(strm, Z_STREAM_ERROR);
301 }
302 if (strm->avail_out == 0) ERR_RETURN(strm, Z_BUF_ERROR);
303
304 strm->state->strm = strm; /* just in case */
305
306 /* Write the zlib header */
307 if (strm->state->status == INIT_STATE) {
308
309 uInt header = (DEFLATED + ((strm->state->w_bits-8)<<4)) << 8;
310 uInt level_flags = (strm->state->level-1) >> 1;
311
312 if (level_flags > 3) level_flags = 3;
313 header |= (level_flags << 6);
314 header += 31 - (header % 31);
315
316 strm->state->status = BUSY_STATE;
317 putShortMSB(strm->state, header);
318 }
319
320 /* Flush as much pending output as possible */
321 if (strm->state->pending != 0) {
322 flush_pending(strm);
323 if (strm->avail_out == 0) return Z_OK;
324 }
325
326 /* User must not provide more input after the first FINISH: */
327 if (strm->state->status == FINISH_STATE && strm->avail_in != 0) {
328 ERR_RETURN(strm, Z_BUF_ERROR);
329 }
330
331 /* Start a new block or continue the current one.
332 */
333 if (strm->avail_in != 0 ||
334 (flush == Z_FINISH && strm->state->status != FINISH_STATE)) {
335
336 if (flush == Z_FINISH) {
337 strm->state->status = FINISH_STATE;
338 }
339 if (strm->state->level <= 3) {
340 if (deflate_fast(strm->state, flush)) return Z_OK;
341 } else {
342 if (deflate_slow(strm->state, flush)) return Z_OK;
343 }
344 }
345 Assert(strm->avail_out > 0, "bug2");
346
347 if (flush != Z_FINISH || strm->state->noheader) return Z_OK;
348
349 /* Write the zlib trailer (adler32) */
350 putShortMSB(strm->state, strm->state->adler >> 16);
351 putShortMSB(strm->state, strm->state->adler & 0xffff);
352 flush_pending(strm);
353 /* If avail_out is zero, the application will call deflate again
354 * to flush the rest.
355 */
356 strm->state->noheader = 1; /* write the trailer only once! */
357 return Z_OK;
358}
359
360/* ========================================================================= */
361int deflateEnd (strm)
362 z_stream *strm;
363{
364 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
365
366 TRY_FREE(strm, strm->state->window);
367 TRY_FREE(strm, strm->state->prev);
368 TRY_FREE(strm, strm->state->head);
369 TRY_FREE(strm, strm->state->pending_buf);
370
371 ZFREE(strm, strm->state);
372 strm->state = Z_NULL;
373
374 return Z_OK;
375}
376
377/* ========================================================================= */
378int deflateCopy (dest, source)
379 z_stream *dest;
380 z_stream *source;
381{
382 if (source == Z_NULL || dest == Z_NULL || source->state == Z_NULL) {
383 return Z_STREAM_ERROR;
384 }
385 *dest = *source;
386 return Z_STREAM_ERROR; /* to be implemented */
387#if 0
388 dest->state = (struct internal_state *)
389 (*dest->zalloc)(1, sizeof(deflate_state));
390 if (dest->state == Z_NULL) return Z_MEM_ERROR;
391
392 *(dest->state) = *(source->state);
393 return Z_OK;
394#endif
395}
396
397/* ===========================================================================
398 * Read a new buffer from the current input stream, update the adler32
399 * and total number of bytes read.
400 */
401local int read_buf(strm, buf, size)
402 z_stream *strm;
403 char *buf;
404 unsigned size;
405{
406 unsigned len = strm->avail_in;
407
408 if (len > size) len = size;
409 if (len == 0) return 0;
410
411 strm->avail_in -= len;
412
413 if (!strm->state->noheader) {
414 strm->state->adler = adler32(strm->state->adler, strm->next_in, len);
415 }
416 zmemcpy(buf, strm->next_in, len);
417 strm->next_in += len;
418 strm->total_in += len;
419
420 return (int)len;
421}
422
423/* ===========================================================================
424 * Initialize the "longest match" routines for a new zlib stream
425 */
426local void lm_init (s)
427 deflate_state *s;
428{
429 register unsigned j;
430
431 s->window_size = (ulg)2L*s->w_size;
432
433
434 /* Initialize the hash table (avoiding 64K overflow for 16 bit systems).
435 * prev[] will be initialized on the fly.
436 */
437 s->head[s->hash_size-1] = NIL;
438 zmemzero((char*)s->head, (unsigned)(s->hash_size-1)*sizeof(*s->head));
439
440 /* Set the default configuration parameters:
441 */
442 s->max_lazy_match = configuration_table[s->level].max_lazy;
443 s->good_match = configuration_table[s->level].good_length;
444 s->nice_match = configuration_table[s->level].nice_length;
445 s->max_chain_length = configuration_table[s->level].max_chain;
446
447 s->strstart = 0;
448 s->block_start = 0L;
449 s->lookahead = 0;
450 s->match_length = MIN_MATCH-1;
451 s->match_available = 0;
452#ifdef ASMV
453 match_init(); /* initialize the asm code */
454#endif
455
456 s->ins_h = 0;
457 for (j=0; j<MIN_MATCH-1; j++) UPDATE_HASH(s, s->ins_h, s->window[j]);
458 /* If lookahead < MIN_MATCH, ins_h is garbage, but this is
459 * not important since only literal bytes will be emitted.
460 */
461}
462
463/* ===========================================================================
464 * Set match_start to the longest match starting at the given string and
465 * return its length. Matches shorter or equal to prev_length are discarded,
466 * in which case the result is equal to prev_length and match_start is
467 * garbage.
468 * IN assertions: cur_match is the head of the hash chain for the current
469 * string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1
470 */
471#ifndef ASMV
472/* For 80x86 and 680x0, an optimized version will be provided in match.asm or
473 * match.S. The code will be functionally equivalent.
474 */
475local int longest_match(s, cur_match)
476 deflate_state *s;
477 IPos cur_match; /* current match */
478{
479 unsigned chain_length = s->max_chain_length;/* max hash chain length */
480 register Byte *scan = s->window + s->strstart; /* current string */
481 register Byte *match; /* matched string */
482 register int len; /* length of current match */
483 int best_len = s->prev_length; /* best match length so far */
484 IPos limit = s->strstart > (IPos)MAX_DIST(s) ?
485 s->strstart - (IPos)MAX_DIST(s) : NIL;
486 /* Stop when cur_match becomes <= limit. To simplify the code,
487 * we prevent matches with the string of window index 0.
488 */
489
490#ifdef UNALIGNED_OK
491 /* Compare two bytes at a time. Note: this is not always beneficial.
492 * Try with and without -DUNALIGNED_OK to check.
493 */
494 register Byte *strend = s->window + s->strstart + MAX_MATCH - 1;
495 register ush scan_start = *(ush*)scan;
496 register ush scan_end = *(ush*)(scan+best_len-1);
497#else
498 register Byte *strend = s->window + s->strstart + MAX_MATCH;
499 register Byte scan_end1 = scan[best_len-1];
500 register Byte scan_end = scan[best_len];
501#endif
502
503 /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16.
504 * It is easy to get rid of this optimization if necessary.
505 */
506 Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever");
507
508 /* Do not waste too much time if we already have a good match: */
509 if (s->prev_length >= s->good_match) {
510 chain_length >>= 2;
511 }
512 Assert(s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead");
513
514 do {
515 Assert(cur_match < s->strstart, "no future");
516 match = s->window + cur_match;
517
518 /* Skip to next match if the match length cannot increase
519 * or if the match length is less than 2:
520 */
521#if (defined(UNALIGNED_OK) && MAX_MATCH == 258)
522 /* This code assumes sizeof(unsigned short) == 2. Do not use
523 * UNALIGNED_OK if your compiler uses a different size.
524 */
525 if (*(ush*)(match+best_len-1) != scan_end ||
526 *(ush*)match != scan_start) continue;
527
528 /* It is not necessary to compare scan[2] and match[2] since they are
529 * always equal when the other bytes match, given that the hash keys
530 * are equal and that HASH_BITS >= 8. Compare 2 bytes at a time at
531 * strstart+3, +5, ... up to strstart+257. We check for insufficient
532 * lookahead only every 4th comparison; the 128th check will be made
533 * at strstart+257. If MAX_MATCH-2 is not a multiple of 8, it is
534 * necessary to put more guard bytes at the end of the window, or
535 * to check more often for insufficient lookahead.
536 */
537 scan++, match++;
538 do {
539 } while (*(ush*)(scan+=2) == *(ush*)(match+=2) &&
540 *(ush*)(scan+=2) == *(ush*)(match+=2) &&
541 *(ush*)(scan+=2) == *(ush*)(match+=2) &&
542 *(ush*)(scan+=2) == *(ush*)(match+=2) &&
543 scan < strend);
544 /* The funny "do {}" generates better code on most compilers */
545
546 /* Here, scan <= window+strstart+257 */
547 Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
548 if (*scan == *match) scan++;
549
550 len = (MAX_MATCH - 1) - (int)(strend-scan);
551 scan = strend - (MAX_MATCH-1);
552
553#else /* UNALIGNED_OK */
554
555 if (match[best_len] != scan_end ||
556 match[best_len-1] != scan_end1 ||
557 *match != *scan ||
558 *++match != scan[1]) continue;
559
560 /* The check at best_len-1 can be removed because it will be made
561 * again later. (This heuristic is not always a win.)
562 * It is not necessary to compare scan[2] and match[2] since they
563 * are always equal when the other bytes match, given that
564 * the hash keys are equal and that HASH_BITS >= 8.
565 */
566 scan += 2, match++;
567
568 /* We check for insufficient lookahead only every 8th comparison;
569 * the 256th check will be made at strstart+258.
570 */
571 do {
572 } while (*++scan == *++match && *++scan == *++match &&
573 *++scan == *++match && *++scan == *++match &&
574 *++scan == *++match && *++scan == *++match &&
575 *++scan == *++match && *++scan == *++match &&
576 scan < strend);
577
578 Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
579
580 len = MAX_MATCH - (int)(strend - scan);
581 scan = strend - MAX_MATCH;
582
583#endif /* UNALIGNED_OK */
584
585 if (len > best_len) {
586 s->match_start = cur_match;
587 best_len = len;
588 if (len >= s->nice_match) break;
589#ifdef UNALIGNED_OK
590 scan_end = *(ush*)(scan+best_len-1);
591#else
592 scan_end1 = scan[best_len-1];
593 scan_end = scan[best_len];
594#endif
595 }
596 } while ((cur_match = s->prev[cur_match & s->w_mask]) > limit
597 && --chain_length != 0);
598
599 return best_len;
600}
601#endif /* ASMV */
602
603#ifdef DEBUG
604/* ===========================================================================
605 * Check that the match at match_start is indeed a match.
606 */
607local void check_match(s, start, match, length)
608 deflate_state *s;
609 IPos start, match;
610 int length;
611{
612 /* check that the match is indeed a match */
613 if (memcmp((char*)s->window + match,
614 (char*)s->window + start, length) != EQUAL) {
615 fprintf(stderr,
616 " start %d, match %d, length %d\n",
617 start, match, length);
618 z_error("invalid match");
619 }
620 if (verbose > 1) {
621 fprintf(stderr,"\\[%d,%d]", start-match, length);
622 do { putc(s->window[start++], stderr); } while (--length != 0);
623 }
624}
625#else
626# define check_match(s, start, match, length)
627#endif
628
629/* ===========================================================================
630 * Fill the window when the lookahead becomes insufficient.
631 * Updates strstart and lookahead.
632 *
633 * IN assertion: lookahead < MIN_LOOKAHEAD
634 * OUT assertions: strstart <= window_size-MIN_LOOKAHEAD
635 * At least one byte has been read, or avail_in == 0; reads are
636 * performed for at least two bytes (required for the zip translate_eol
637 * option -- not supported here).
638 */
639local void fill_window(s)
640 deflate_state *s;
641{
642 register unsigned n, m;
643 unsigned more; /* Amount of free space at the end of the window. */
644
645 do {
646 more = (unsigned)(s->window_size -(ulg)s->lookahead -(ulg)s->strstart);
647
648 /* Deal with !@#$% 64K limit: */
649 if (more == 0 && s->strstart == 0 && s->lookahead == 0) {
650 more = s->w_size;
651 } else if (more == (unsigned)(-1)) {
652 /* Very unlikely, but possible on 16 bit machine if strstart == 0
653 * and lookahead == 1 (input done one byte at time)
654 */
655 more--;
656
657 /* If the window is almost full and there is insufficient lookahead,
658 * move the upper half to the lower one to make room in the upper half.
659 */
660 } else if (s->strstart >= s->w_size+MAX_DIST(s)) {
661
662 /* By the IN assertion, the window is not empty so we can't confuse
663 * more == 0 with more == 64K on a 16 bit machine.
664 */
665 memcpy((char*)s->window, (char*)s->window+s->w_size,
666 (unsigned)s->w_size);
667 s->match_start -= s->w_size;
668 s->strstart -= s->w_size; /* we now have strstart >= MAX_DIST */
669
670 s->block_start -= (long) s->w_size;
671
672 for (n = 0; n < s->hash_size; n++) {
673 m = s->head[n];
674 s->head[n] = (Pos)(m >= s->w_size ? m-s->w_size : NIL);
675 }
676 for (n = 0; n < s->w_size; n++) {
677 m = s->prev[n];
678 s->prev[n] = (Pos)(m >= s->w_size ? m-s->w_size : NIL);
679 /* If n is not on any hash chain, prev[n] is garbage but
680 * its value will never be used.
681 */
682 }
683 more += s->w_size;
684 }
685 if (s->strm->avail_in == 0) return;
686
687 /* If there was no sliding:
688 * strstart <= WSIZE+MAX_DIST-1 && lookahead <= MIN_LOOKAHEAD - 1 &&
689 * more == window_size - lookahead - strstart
690 * => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE + MAX_DIST-1)
691 * => more >= window_size - 2*WSIZE + 2
692 * In the BIG_MEM or MMAP case (not yet supported),
693 * window_size == input_size + MIN_LOOKAHEAD &&
694 * strstart + s->lookahead <= input_size => more >= MIN_LOOKAHEAD.
695 * Otherwise, window_size == 2*WSIZE so more >= 2.
696 * If there was sliding, more >= WSIZE. So in all cases, more >= 2.
697 */
698 Assert(more >= 2, "more < 2");
699
700 n = read_buf(s->strm, (char*)s->window + s->strstart + s->lookahead,
701 more);
702 s->lookahead += n;
703
704 } while (s->lookahead < MIN_LOOKAHEAD && s->strm->avail_in != 0);
705}
706
707/* ===========================================================================
708 * Flush the current block, with given end-of-file flag.
709 * IN assertion: strstart is set to the end of the current match.
710 */
711#define FLUSH_BLOCK_ONLY(s, eof) { \
712 ct_flush_block(s, (s->block_start >= 0L ? \
713 (char*)&s->window[(unsigned)s->block_start] : \
714 (char*)Z_NULL), (long)s->strstart - s->block_start, (eof)); \
715 s->block_start = s->strstart; \
716 flush_pending(s->strm); \
717}
718
719/* Same but force premature exit if necessary. */
720#define FLUSH_BLOCK(s, eof) { \
721 FLUSH_BLOCK_ONLY(s, eof); \
722 if (s->strm->avail_out == 0) return 1; \
723}
724
725/* ===========================================================================
726 * Compress as much as possible from the input stream, return true if
727 * processing was terminated prematurely (no more input or output space).
728 * This function does not perform lazy evaluationof matches and inserts
729 * new strings in the dictionary only for unmatched strings or for short
730 * matches. It is used only for the fast compression options.
731 */
732local int deflate_fast(s, flush)
733 deflate_state *s;
734 int flush;
735{
736 IPos hash_head; /* head of the hash chain */
737 int bflush; /* set if current block must be flushed */
738
739 s->prev_length = MIN_MATCH-1;
740
741 for (;;) {
742 /* Make sure that we always have enough lookahead, except
743 * at the end of the input file. We need MAX_MATCH bytes
744 * for the next match, plus MIN_MATCH bytes to insert the
745 * string following the next match.
746 */
747 if (s->lookahead < MIN_LOOKAHEAD) {
748 fill_window(s);
749 if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) return 1;
750
751 if (s->lookahead == 0) break; /* flush the current block */
752 }
753
754 /* Insert the string window[strstart .. strstart+2] in the
755 * dictionary, and set hash_head to the head of the hash chain:
756 */
757 INSERT_STRING(s, s->strstart, hash_head);
758
759 /* Find the longest match, discarding those <= prev_length.
760 * At this point we have always match_length < MIN_MATCH
761 */
762 if (hash_head != NIL && s->strstart - hash_head <= MAX_DIST(s)) {
763 /* To simplify the code, we prevent matches with the string
764 * of window index 0 (in particular we have to avoid a match
765 * of the string with itself at the start of the input file).
766 */
767 if (s->strategy != Z_HUFFMAN_ONLY) {
768 s->match_length = longest_match (s, hash_head);
769 }
770 /* longest_match() sets match_start */
771
772 if (s->match_length > s->lookahead) s->match_length = s->lookahead;
773 }
774 if (s->match_length >= MIN_MATCH) {
775 check_match(s, s->strstart, s->match_start, s->match_length);
776
777 bflush = ct_tally(s, s->strstart - s->match_start,
778 s->match_length - MIN_MATCH);
779
780 s->lookahead -= s->match_length;
781
782 /* Insert new strings in the hash table only if the match length
783 * is not too large. This saves time but degrades compression.
784 */
785 if (s->match_length <= s->max_insert_length) {
786 s->match_length--; /* string at strstart already in hash table */
787 do {
788 s->strstart++;
789 INSERT_STRING(s, s->strstart, hash_head);
790 /* strstart never exceeds WSIZE-MAX_MATCH, so there are
791 * always MIN_MATCH bytes ahead. If lookahead < MIN_MATCH
792 * these bytes are garbage, but it does not matter since
793 * the next lookahead bytes will be emitted as literals.
794 */
795 } while (--s->match_length != 0);
796 s->strstart++;
797 } else {
798 s->strstart += s->match_length;
799 s->match_length = 0;
800 s->ins_h = s->window[s->strstart];
801 UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]);
802#if MIN_MATCH != 3
803 Call UPDATE_HASH() MIN_MATCH-3 more times
804#endif
805 }
806 } else {
807 /* No match, output a literal byte */
808 Tracevv((stderr,"%c", s->window[s->strstart]));
809 bflush = ct_tally (s, 0, s->window[s->strstart]);
810 s->lookahead--;
811 s->strstart++;
812 }
813 if (bflush) FLUSH_BLOCK(s, 0);
814 }
815 FLUSH_BLOCK(s, flush == Z_FINISH);
816 return 0; /* normal exit */
817}
818
819/* ===========================================================================
820 * Same as above, but achieves better compression. We use a lazy
821 * evaluation for matches: a match is finally adopted only if there is
822 * no better match at the next window position.
823 */
824local int deflate_slow(s, flush)
825 deflate_state *s;
826 int flush;
827{
828 IPos hash_head; /* head of hash chain */
829 int bflush; /* set if current block must be flushed */
830
831 /* Process the input block. */
832 for (;;) {
833 /* Make sure that we always have enough lookahead, except
834 * at the end of the input file. We need MAX_MATCH bytes
835 * for the next match, plus MIN_MATCH bytes to insert the
836 * string following the next match.
837 */
838 if (s->lookahead < MIN_LOOKAHEAD) {
839 fill_window(s);
840 if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) return 1;
841
842 if (s->lookahead == 0) break; /* flush the current block */
843 }
844
845 /* Insert the string window[strstart .. strstart+2] in the
846 * dictionary, and set hash_head to the head of the hash chain:
847 */
848 INSERT_STRING(s, s->strstart, hash_head);
849
850 /* Find the longest match, discarding those <= prev_length.
851 */
852 s->prev_length = s->match_length, s->prev_match = s->match_start;
853 s->match_length = MIN_MATCH-1;
854
855 if (hash_head != NIL && s->prev_length < s->max_lazy_match &&
856 s->strstart - hash_head <= MAX_DIST(s)) {
857 /* To simplify the code, we prevent matches with the string
858 * of window index 0 (in particular we have to avoid a match
859 * of the string with itself at the start of the input file).
860 */
861 if (s->strategy != Z_HUFFMAN_ONLY) {
862 s->match_length = longest_match (s, hash_head);
863 }
864 /* longest_match() sets match_start */
865 if (s->match_length > s->lookahead) s->match_length = s->lookahead;
866
867 if (s->match_length <= 5 && (s->strategy == Z_FILTERED ||
868 (s->match_length == MIN_MATCH &&
869 s->strstart - s->match_start > TOO_FAR))) {
870
871 /* If prev_match is also MIN_MATCH, match_start is garbage
872 * but we will ignore the current match anyway.
873 */
874 s->match_length = MIN_MATCH-1;
875 }
876 }
877 /* If there was a match at the previous step and the current
878 * match is not better, output the previous match:
879 */
880 if (s->prev_length >= MIN_MATCH && s->match_length <= s->prev_length) {
881
882 check_match(s, s->strstart-1, s->prev_match, s->prev_length);
883
884 bflush = ct_tally(s, s->strstart -1 - s->prev_match,
885 s->prev_length - MIN_MATCH);
886
887 /* Insert in hash table all strings up to the end of the match.
888 * strstart-1 and strstart are already inserted.
889 */
890 s->lookahead -= s->prev_length-1;
891 s->prev_length -= 2;
892 do {
893 s->strstart++;
894 INSERT_STRING(s, s->strstart, hash_head);
895 /* strstart never exceeds WSIZE-MAX_MATCH, so there are
896 * always MIN_MATCH bytes ahead. If lookahead < MIN_MATCH
897 * these bytes are garbage, but it does not matter since the
898 * next lookahead bytes will always be emitted as literals.
899 */
900 } while (--s->prev_length != 0);
901 s->match_available = 0;
902 s->match_length = MIN_MATCH-1;
903 s->strstart++;
904
905 if (bflush) FLUSH_BLOCK(s, 0);
906
907 } else if (s->match_available) {
908 /* If there was no match at the previous position, output a
909 * single literal. If there was a match but the current match
910 * is longer, truncate the previous match to a single literal.
911 */
912 Tracevv((stderr,"%c", s->window[s->strstart-1]));
913 if (ct_tally (s, 0, s->window[s->strstart-1])) {
914 FLUSH_BLOCK_ONLY(s, 0);
915 }
916 s->strstart++;
917 s->lookahead--;
918 if (s->strm->avail_out == 0) return 1;
919 } else {
920 /* There is no previous match to compare with, wait for
921 * the next step to decide.
922 */
923 s->match_available = 1;
924 s->strstart++;
925 s->lookahead--;
926 }
927 }
928 if (s->match_available) ct_tally (s, 0, s->window[s->strstart-1]);
929
930 FLUSH_BLOCK(s, flush == Z_FINISH);
931 return 0;
932}
diff --git a/deflate.h b/deflate.h
new file mode 100644
index 0000000..740c25a
--- /dev/null
+++ b/deflate.h
@@ -0,0 +1,270 @@
1/* deflate.h -- internal compression state
2 * Copyright (C) 1995 Jean-loup Gailly
3 * For conditions of distribution and use, see copyright notice in zlib.h
4 */
5
6/* WARNING: this file should *not* be used by applications. It is
7 part of the implementation of the compression library and is
8 subject to change. Applications should only use zlib.h.
9 */
10
11/* $Id: deflate.h,v 1.3 1995/04/14 12:39:45 jloup Exp $ */
12
13#include "zutil.h"
14
15/* ===========================================================================
16 * Internal compression state.
17 */
18
19/* Data type */
20#define BINARY 0
21#define ASCII 1
22#define UNKNOWN 2
23
24#define LENGTH_CODES 29
25/* number of length codes, not counting the special END_BLOCK code */
26
27#define LITERALS 256
28/* number of literal bytes 0..255 */
29
30#define L_CODES (LITERALS+1+LENGTH_CODES)
31/* number of Literal or Length codes, including the END_BLOCK code */
32
33#define D_CODES 30
34/* number of distance codes */
35
36#define BL_CODES 19
37/* number of codes used to transfer the bit lengths */
38
39#define HEAP_SIZE (2*L_CODES+1)
40/* maximum heap size */
41
42#define MAX_BITS 15
43/* All codes must not exceed MAX_BITS bits */
44
45#define INIT_STATE 42
46#define BUSY_STATE 113
47#define FINISH_STATE 666
48/* Stream status */
49
50
51/* Data structure describing a single value and its code string. */
52typedef struct ct_data_s {
53 union {
54 ush freq; /* frequency count */
55 ush code; /* bit string */
56 } fc;
57 union {
58 ush dad; /* father node in Huffman tree */
59 ush len; /* length of bit string */
60 } dl;
61} ct_data;
62
63#define Freq fc.freq
64#define Code fc.code
65#define Dad dl.dad
66#define Len dl.len
67
68typedef struct static_tree_desc_s static_tree_desc;
69
70typedef struct tree_desc_s {
71 ct_data *dyn_tree; /* the dynamic tree */
72 int max_code; /* largest code with non zero frequency */
73 static_tree_desc *stat_desc; /* the corresponding static tree */
74} tree_desc;
75
76typedef ush Pos;
77typedef unsigned IPos;
78/* A Pos is an index in the character window. We use short instead of int to
79 * save space in the various tables. IPos is used only for parameter passing.
80 */
81
82typedef struct internal_state {
83 z_stream *strm; /* pointer back to this zlib stream */
84 int status; /* as the name implies */
85 Byte *pending_buf; /* output still pending */
86 Byte *pending_out; /* next pending byte to output to the stream */
87 int pending; /* nb of bytes in the pending buffer */
88 uLong adler; /* adler32 of uncompressed data */
89 int noheader; /* suppress zlib header and adler32 */
90 Byte data_type; /* UNKNOWN, BINARY or ASCII */
91 Byte method; /* STORED (for zip only) or DEFLATED */
92
93 /* used by deflate.c: */
94
95 uInt w_size; /* LZ77 window size (32K by default) */
96 uInt w_bits; /* log2(w_size) (8..16) */
97 uInt w_mask; /* w_size - 1 */
98
99 Byte *window;
100 /* Sliding window. Input bytes are read into the second half of the window,
101 * and move to the first half later to keep a dictionary of at least wSize
102 * bytes. With this organization, matches are limited to a distance of
103 * wSize-MAX_MATCH bytes, but this ensures that IO is always
104 * performed with a length multiple of the block size. Also, it limits
105 * the window size to 64K, which is quite useful on MSDOS.
106 * To do: use the user input buffer as sliding window.
107 */
108
109 ulg window_size;
110 /* Actual size of window: 2*wSize, except when the user input buffer
111 * is directly used as sliding window.
112 */
113
114 Pos *prev;
115 /* Link to older string with same hash index. To limit the size of this
116 * array to 64K, this link is maintained only for the last 32K strings.
117 * An index in this array is thus a window index modulo 32K.
118 */
119
120 Pos *head; /* Heads of the hash chains or NIL. */
121
122 uInt ins_h; /* hash index of string to be inserted */
123 uInt hash_size; /* number of elements in hash table */
124 uInt hash_bits; /* log2(hash_size) */
125 uInt hash_mask; /* hash_size-1 */
126
127 uInt hash_shift;
128 /* Number of bits by which ins_h must be shifted at each input
129 * step. It must be such that after MIN_MATCH steps, the oldest
130 * byte no longer takes part in the hash key, that is:
131 * hash_shift * MIN_MATCH >= hash_bits
132 */
133
134 long block_start;
135 /* Window position at the beginning of the current output block. Gets
136 * negative when the window is moved backwards.
137 */
138
139 uInt match_length; /* length of best match */
140 IPos prev_match; /* previous match */
141 int match_available; /* set if previous match exists */
142 uInt strstart; /* start of string to insert */
143 uInt match_start; /* start of matching string */
144 uInt lookahead; /* number of valid bytes ahead in window */
145
146 uInt prev_length;
147 /* Length of the best match at previous step. Matches not greater than this
148 * are discarded. This is used in the lazy match evaluation.
149 */
150
151 uInt max_chain_length;
152 /* To speed up deflation, hash chains are never searched beyond this
153 * length. A higher limit improves compression ratio but degrades the
154 * speed.
155 */
156
157 uInt max_lazy_match;
158 /* Attempt to find a better match only when the current match is strictly
159 * smaller than this value. This mechanism is used only for compression
160 * levels >= 4.
161 */
162# define max_insert_length max_lazy_match
163 /* Insert new strings in the hash table only if the match length is not
164 * greater than this length. This saves time but degrades compression.
165 * max_insert_length is used only for compression levels <= 3.
166 */
167
168 int level; /* compression level (1..9) */
169 int strategy; /* favor or force Huffman coding*/
170
171 uInt good_match;
172 /* Use a faster search when the previous match is longer than this */
173
174 int nice_match; /* Stop searching when current match exceeds this */
175
176 /* used by trees.c: */
177
178 ct_data dyn_ltree[HEAP_SIZE]; /* literal and length tree */
179 ct_data dyn_dtree[2*D_CODES+1]; /* distance tree */
180 ct_data bl_tree[2*BL_CODES+1]; /* Huffman tree for the bit lengths */
181
182 tree_desc l_desc; /* descriptor for literal tree */
183 tree_desc d_desc; /* descriptor for distance tree */
184 tree_desc bl_desc; /* descriptor for bit length tree */
185
186 ush bl_count[MAX_BITS+1];
187 /* number of codes at each bit length for an optimal tree */
188
189 int heap[2*L_CODES+1]; /* heap used to build the Huffman trees */
190 int heap_len; /* number of elements in the heap */
191 int heap_max; /* element of largest frequency */
192 /* The sons of heap[n] are heap[2*n] and heap[2*n+1]. heap[0] is not used.
193 * The same heap array is used to build all trees.
194 */
195
196 uch depth[2*L_CODES+1];
197 /* Depth of each subtree used as tie breaker for trees of equal frequency
198 */
199
200 uch *l_buf; /* buffer for literals or lengths */
201
202 uInt lit_bufsize;
203 /* Size of match buffer for literals/lengths. There are 4 reasons for
204 * limiting lit_bufsize to 64K:
205 * - frequencies can be kept in 16 bit counters
206 * - if compression is not successful for the first block, all input
207 * data is still in the window so we can still emit a stored block even
208 * when input comes from standard input. (This can also be done for
209 * all blocks if lit_bufsize is not greater than 32K.)
210 * - if compression is not successful for a file smaller than 64K, we can
211 * even emit a stored file instead of a stored block (saving 5 bytes).
212 * This is applicable only for zip (not gzip or zlib).
213 * - creating new Huffman trees less frequently may not provide fast
214 * adaptation to changes in the input data statistics. (Take for
215 * example a binary file with poorly compressible code followed by
216 * a highly compressible string table.) Smaller buffer sizes give
217 * fast adaptation but have of course the overhead of transmitting
218 * trees more frequently.
219 * - I can't count above 4
220 */
221
222 uInt last_lit; /* running index in l_buf */
223
224 ush *d_buf;
225 /* Buffer for distances. To simplify the code, d_buf and l_buf have
226 * the same number of elements. To use different lengths, an extra flag
227 * array would be necessary.
228 */
229
230 ulg opt_len; /* bit length of current block with optimal trees */
231 ulg static_len; /* bit length of current block with static trees */
232 ulg compressed_len; /* total bit length of compressed file */
233 uInt matches; /* number of string matches in current block */
234
235#ifdef DEBUG
236 ulg bits_sent; /* bit length of the compressed data */
237#endif
238
239 ush bi_buf;
240 /* Output buffer. bits are inserted starting at the bottom (least
241 * significant bits).
242 */
243 int bi_valid;
244 /* Number of valid bits in bi_buf. All bits above the last valid bit
245 * are always zero.
246 */
247
248} deflate_state;
249
250
251/* Output a byte on the stream.
252 * IN assertion: there is enough room in pending_buf.
253 */
254#define put_byte(s, c) {s->pending_buf[s->pending++] = (c);}
255
256
257#define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1)
258/* Minimum amount of lookahead, except at the end of the input file.
259 * See deflate.c for comments about the MIN_MATCH+1.
260 */
261
262#define MAX_DIST(s) ((s)->w_size-MIN_LOOKAHEAD)
263/* In order to simplify the code, particularly on 16 bit machines, match
264 * distances are limited to MAX_DIST instead of WSIZE.
265 */
266
267 /* in trees.c */
268void ct_init __P((deflate_state *s));
269int ct_tally __P((deflate_state *s, int dist, int lc));
270ulg ct_flush_block __P((deflate_state *s, char *buf, ulg stored_len, int eof));
diff --git a/example.c b/example.c
new file mode 100644
index 0000000..ea1a9eb
--- /dev/null
+++ b/example.c
@@ -0,0 +1,201 @@
1/* example.c -- usage example of the zlib compression library
2 * Copyright (C) 1995 Jean-loup Gailly.
3 * For conditions of distribution and use, see copyright notice in zlib.h
4 */
5
6/* $Id: example.c,v 1.4 1995/04/14 13:32:49 jloup Exp $ */
7
8#include <stdio.h>
9#include "zlib.h"
10
11#define BUFLEN 4096
12
13#define local static
14/* For MSDOS and other systems with limitation on stack size. For Unix,
15 #define local
16 works also.
17 */
18
19#define CHECK_ERR(err, msg) { \
20 if (err != Z_OK) { \
21 fprintf(stderr, "%s error: %d\n", msg, err); \
22 exit(1); \
23 } \
24}
25
26char *hello = "hello world";
27
28/* ===========================================================================
29 * Test compress() and uncompress()
30 */
31void test_compress()
32{
33 local Byte compr[BUFLEN];
34 uLong comprLen = sizeof(compr);
35 local Byte uncompr[BUFLEN];
36 uLong uncomprLen = sizeof(uncompr);
37 int err;
38 uLong len = strlen(hello)+1;
39
40 err = compress(compr, &comprLen, hello, len);
41 CHECK_ERR(err, "compress");
42
43 strcpy(uncompr, "garbage");
44
45 err = uncompress(uncompr, &uncomprLen, compr, comprLen);
46 CHECK_ERR(err, "uncompress");
47
48 if (strcmp(uncompr, hello)) {
49 fprintf(stderr, "bad uncompress\n");
50 } else {
51 printf("uncompress(): %s\n", uncompr);
52 }
53}
54
55/* ===========================================================================
56 * Test read/write of .gz files
57 */
58void test_gzio(out, in)
59 char *out; /* output file */
60 char *in; /* input file */
61{
62 local Byte uncompr[BUFLEN];
63 uLong uncomprLen = sizeof(uncompr);
64 int err;
65 int len = strlen(hello)+1;
66 gzFile file;
67
68 file = gzopen(out, "wb");
69 if (file == NULL) {
70 fprintf(stderr, "gzopen error\n");
71 exit(1);
72 }
73
74 if (gzwrite(file, hello, len) != len) {
75 fprintf(stderr, "gzwrite err: %s\n", gzerror(file, &err));
76 }
77 gzclose(file);
78
79 file = gzopen(in, "rb");
80 if (file == NULL) {
81 fprintf(stderr, "gzopen error\n");
82 }
83 strcpy(uncompr, "garbage");
84
85 uncomprLen = gzread(file, uncompr, uncomprLen);
86 if (uncomprLen != len) {
87 fprintf(stderr, "gzread err: %s\n", gzerror(file, &err));
88 }
89 gzclose(file);
90
91 if (strcmp(uncompr, hello)) {
92 fprintf(stderr, "bad gzread\n");
93 } else {
94 printf("gzread(): %s\n", uncompr);
95 }
96}
97
98/* ===========================================================================
99 * Test deflate() with small buffers, return the compressed length.
100 */
101uLong test_deflate(compr)
102 Byte compr[];
103{
104 z_stream c_stream; /* compression stream */
105 int err;
106 int len = strlen(hello)+1;
107
108 c_stream.zalloc = (alloc_func)0;
109 c_stream.zfree = (free_func)0;
110
111 err = deflateInit(&c_stream, Z_DEFAULT_COMPRESSION);
112 CHECK_ERR(err, "deflateInit");
113
114 c_stream.next_in = (Byte*)hello;
115 c_stream.next_out = compr;
116
117 while (c_stream.total_in != len) {
118 c_stream.avail_in = c_stream.avail_out = 1; /* force small buffers */
119 err = deflate(&c_stream, Z_NO_FLUSH);
120 CHECK_ERR(err, "deflate");
121 }
122 /* Finish the stream, still forcing small buffers: */
123 do {
124 c_stream.avail_out = 1;
125 err = deflate(&c_stream, Z_FINISH);
126 CHECK_ERR(err, "deflate");
127 } while (c_stream.avail_out == 0);
128
129 err = deflateEnd(&c_stream);
130 CHECK_ERR(err, "deflateEnd");
131
132 return c_stream.total_out;
133}
134
135/* ===========================================================================
136 * Test inflate() with small buffers
137 */
138void test_inflate(compr)
139 Byte compr[];
140{
141 local Byte uncompr[BUFLEN];
142 int err;
143 z_stream d_stream; /* decompression stream */
144
145 strcpy(uncompr, "garbage");
146
147 d_stream.zalloc = (alloc_func)0;
148 d_stream.zfree = (free_func)0;
149
150 err = inflateInit(&d_stream);
151 CHECK_ERR(err, "inflateInit");
152
153 d_stream.next_in = compr;
154 d_stream.next_out = uncompr;
155
156 for (;;) {
157 d_stream.avail_in = d_stream.avail_out = 1; /* force small buffers */
158 err = inflate(&d_stream, Z_NO_FLUSH);
159 if (err == Z_STREAM_END) break;
160 CHECK_ERR(err, "inflate");
161 }
162
163 err = inflateEnd(&d_stream);
164 CHECK_ERR(err, "inflateEnd");
165
166 if (strcmp(uncompr, hello)) {
167 fprintf(stderr, "bad inflate\n");
168 } else {
169 printf("inflate(): %s\n", uncompr);
170 }
171}
172
173/* ===========================================================================
174 * Usage: example [output.gz [input.gz]]
175 */
176
177void main(argc, argv)
178 int argc;
179 char *argv[];
180{
181 local Byte compr[BUFLEN];
182 uLong comprLen;
183
184 if (zlib_version[0] != ZLIB_VERSION[0]) {
185 fprintf(stderr, "incompatible zlib version\n");
186 exit(1);
187
188 } else if (strcmp(zlib_version, ZLIB_VERSION) != 0) {
189 fprintf(stderr, "warning: different zlib version\n");
190 }
191 test_compress();
192
193 test_gzio((argc > 1 ? argv[1] : "foo.gz"),
194 (argc > 2 ? argv[2] : "foo.gz"));
195
196 comprLen = test_deflate(compr);
197
198 test_inflate(compr);
199
200 exit(0);
201}
diff --git a/gzio.c b/gzio.c
new file mode 100644
index 0000000..b488e96
--- /dev/null
+++ b/gzio.c
@@ -0,0 +1,459 @@
1/* gzio.c -- IO on .gz files
2 * Copyright (C) 1995 Jean-loup Gailly.
3 * For conditions of distribution and use, see copyright notice in zlib.h
4 */
5
6/* $Id: gzio.c,v 1.4 1995/04/14 14:50:52 jloup Exp $ */
7
8#include <stdio.h>
9
10#include "zutil.h"
11
12struct internal_state {int dummy;}; /* for buggy compilers */
13
14#define Z_BUFSIZE 4096
15
16#define ALLOC(size) zcalloc((voidp)0, 1, size)
17#define TRYFREE(p) {if (p) zcfree((voidp)0, p);}
18
19#define GZ_MAGIC_1 0x1f
20#define GZ_MAGIC_2 0x8b
21
22/* gzip flag byte */
23#define ASCII_FLAG 0x01 /* bit 0 set: file probably ascii text */
24#define HEAD_CRC 0x02 /* bit 1 set: header CRC present */
25#define EXTRA_FIELD 0x04 /* bit 2 set: extra field present */
26#define ORIG_NAME 0x08 /* bit 3 set: original file name present */
27#define COMMENT 0x10 /* bit 4 set: file comment present */
28#define RESERVED 0xE0 /* bits 5..7: reserved */
29
30#ifndef SEEK_CUR
31# define SEEK_CUR 1
32#endif
33
34typedef struct gz_stream {
35 z_stream stream;
36 int z_err; /* error code for last stream operation */
37 int z_eof; /* set if end of input file */
38 FILE *file; /* .gz file */
39 Byte *inbuf; /* input buffer */
40 Byte *outbuf; /* output buffer */
41 uLong crc; /* crc32 of uncompressed data */
42 char *msg; /* error message */
43 char *path; /* path name for debugging only */
44 int transparent; /* 1 if input file is not a .gz file */
45 char mode; /* 'w' or 'r' */
46} gz_stream;
47
48
49/* ===========================================================================
50 * Cleanup then free the given gz_stream. Return a zlib error code.
51 */
52local int destroy (s)
53 gz_stream *s;
54{
55 int err = Z_OK;
56
57 if (!s) return Z_STREAM_ERROR;
58
59 TRYFREE(s->inbuf);
60 TRYFREE(s->outbuf);
61 TRYFREE(s->path);
62 TRYFREE(s->msg);
63
64 if (s->stream.state != NULL) {
65 if (s->mode == 'w') {
66 err = deflateEnd(&(s->stream));
67 } else if (s->mode == 'r') {
68 err = inflateEnd(&(s->stream));
69 }
70 }
71 if (s->file != NULL && fclose(s->file)) {
72 err = Z_ERRNO;
73 }
74 zcfree((voidp)0, s);
75 return s->z_err < 0 ? s->z_err : err;
76}
77
78/* ===========================================================================
79 Opens a gzip (.gz) file for reading or writing. The mode parameter
80 is as in fopen ("rb" or "wb"). The file is given either by file descritor
81 or path name (if fd == -1).
82 gz_open return NULL if the file could not be opened or if there was
83 insufficient memory to allocate the (de)compression state; errno
84 can be checked to distinguish the two cases (if errno is zero, the
85 zlib error is Z_MEM_ERROR).
86*/
87local gzFile gz_open (path, mode, fd)
88 char *path;
89 char *mode;
90 int fd;
91{
92 int err;
93 char *p = mode;
94 gz_stream *s = (gz_stream *)ALLOC(sizeof(gz_stream));
95
96 if (!s) return Z_NULL;
97
98 s->stream.zalloc = (alloc_func)0;
99 s->stream.zfree = (free_func)0;
100 s->stream.next_in = s->inbuf = Z_NULL;
101 s->stream.next_out = s->outbuf = Z_NULL;
102 s->stream.avail_in = s->stream.avail_out = 0;
103 s->file = NULL;
104 s->z_err = Z_OK;
105 s->z_eof = 0;
106 s->crc = crc32(0L, Z_NULL, 0);
107 s->msg = NULL;
108 s->transparent = 0;
109
110 s->path = (char*)ALLOC(strlen(path)+1);
111 if (s->path == NULL) {
112 return destroy(s), (gzFile)Z_NULL;
113 }
114 strcpy(s->path, path); /* do this early for debugging */
115
116 s->mode = '\0';
117 do {
118 if (*p == 'r') s->mode = 'r';
119 if (*p == 'w') s->mode = 'w';
120 } while (*p++);
121 if (s->mode == '\0') return destroy(s), (gzFile)Z_NULL;
122
123 if (s->mode == 'w') {
124 err = deflateInit2(&(s->stream), Z_DEFAULT_COMPRESSION,
125 DEFLATED, -WBITS, MEM_LEVEL, 0);
126 /* windowBits is passed < 0 to suppress zlib header */
127
128 s->stream.next_out = s->outbuf = ALLOC(Z_BUFSIZE);
129
130 if (err != Z_OK || s->outbuf == Z_NULL) {
131 return destroy(s), (gzFile)Z_NULL;
132 }
133 } else {
134 err = inflateInit2(&(s->stream), -WBITS);
135 s->stream.next_in = s->inbuf = ALLOC(Z_BUFSIZE);
136
137 if (err != Z_OK || s->inbuf == Z_NULL) {
138 return destroy(s), (gzFile)Z_NULL;
139 }
140 }
141 s->stream.avail_out = Z_BUFSIZE;
142
143 errno = 0;
144 s->file = fd < 0 ? FOPEN(path, mode) : fdopen(fd, mode);
145
146 if (s->file == NULL) {
147 return destroy(s), (gzFile)Z_NULL;
148 }
149 if (s->mode == 'w') {
150 /* Write a very simple .gz header:
151 */
152 fprintf(s->file, "%c%c%c%c%c%c%c%c%c%c", GZ_MAGIC_1, GZ_MAGIC_2,
153 DEFLATED, 0 /*flags*/, 0,0,0,0 /*time*/, 0 /*xflags*/, OS_CODE);
154 } else {
155 /* Check and skip the header:
156 */
157 Byte c1 = 0, c2 = 0;
158 Byte method = 0;
159 Byte flags = 0;
160 Byte xflags = 0;
161 Byte time[4];
162 Byte osCode;
163 int c;
164
165 s->stream.avail_in = fread(s->inbuf, 1, 2, s->file);
166 if (s->stream.avail_in != 2 || s->inbuf[0] != GZ_MAGIC_1
167 || s->inbuf[1] != GZ_MAGIC_2) {
168 s->transparent = 1;
169 return (gzFile)s;
170 }
171 s->stream.avail_in = 0;
172 fscanf(s->file,"%c%c%4c%c%c", &method, &flags, time, &xflags, &osCode);
173
174 if (method != DEFLATED || feof(s->file) || (flags & RESERVED) != 0) {
175 s->z_err = Z_DATA_ERROR;
176 return (gzFile)s;
177 }
178 if ((flags & EXTRA_FIELD) != 0) { /* skip the extra field */
179 long len;
180 fscanf(s->file, "%c%c", &c1, &c2);
181 len = c1 + ((long)c2<<8);
182 fseek(s->file, len, SEEK_CUR);
183 }
184 if ((flags & ORIG_NAME) != 0) { /* skip the original file name */
185 while ((c = getc(s->file)) != 0 && c != EOF) ;
186 }
187 if ((flags & COMMENT) != 0) { /* skip the .gz file comment */
188 while ((c = getc(s->file)) != 0 && c != EOF) ;
189 }
190 if ((flags & HEAD_CRC) != 0) { /* skip the header crc */
191 fscanf(s->file, "%c%c", &c1, &c2);
192 }
193 if (feof(s->file)) {
194 s->z_err = Z_DATA_ERROR;
195 }
196 }
197 return (gzFile)s;
198}
199
200/* ===========================================================================
201 Opens a gzip (.gz) file for reading or writing.
202*/
203gzFile gzopen (path, mode)
204 char *path;
205 char *mode;
206{
207 return gz_open (path, mode, -1);
208}
209
210/* ===========================================================================
211 Associate a gzFile with the file descriptor fd.
212*/
213gzFile gzdopen (fd, mode)
214 int fd;
215 char *mode;
216{
217 char name[20];
218 sprintf(name, "_fd:%d_", fd); /* for debugging */
219
220 return gz_open (name, mode, fd);
221}
222
223/* ===========================================================================
224 Reads the given number of uncompressed bytes from the compressed file.
225 gzread returns the number of bytes actually read (0 for end of file).
226*/
227int gzread (file, buf, len)
228 gzFile file;
229 voidp buf;
230 unsigned len;
231{
232 gz_stream *s = (gz_stream*)file;
233
234 if (s == NULL || s->mode != 'r') return Z_STREAM_ERROR;
235
236 if (s->transparent) {
237 unsigned n = 0;
238 /* Copy the first two (non-magic) bytes if not done already */
239 while (s->stream.avail_in > 0 && len > 0) {
240 *((Byte*)buf)++ = *s->stream.next_in++;
241 s->stream.avail_in--;
242 len--; n++;
243 }
244 if (len == 0) return n;
245 return n + fread(buf, 1, len, s->file);
246 }
247 if (s->z_err == Z_DATA_ERROR) return -1; /* bad .gz file */
248 if (s->z_err == Z_STREAM_END) return 0; /* don't read crc as data */
249
250 s->stream.next_out = buf;
251 s->stream.avail_out = len;
252
253 while (s->stream.avail_out != 0) {
254
255 if (s->stream.avail_in == 0 && !s->z_eof) {
256
257 errno = 0;
258 s->stream.avail_in =
259 fread(s->inbuf, 1, Z_BUFSIZE, s->file);
260 if (s->stream.avail_in == 0) {
261 s->z_eof = 1;
262 } else if (s->stream.avail_in == (uInt)EOF) {
263 s->stream.avail_in = 0;
264 s->z_eof = 1;
265 s->z_err = Z_ERRNO;
266 break;
267 }
268 s->stream.next_in = s->inbuf;
269 }
270 s->z_err = inflate(&(s->stream), Z_NO_FLUSH);
271
272 if (s->z_err == Z_STREAM_END ||
273 s->z_err != Z_OK || s->z_eof) break;
274 }
275 len -= s->stream.avail_out;
276 s->crc = crc32(s->crc, buf, len);
277 return len;
278}
279
280/* ===========================================================================
281 Writes the given number of uncompressed bytes into the compressed file.
282 gzwrite returns the number of bytes actually written (0 in case of error).
283*/
284int gzwrite (file, buf, len)
285 gzFile file;
286 voidp buf;
287 unsigned len;
288{
289 gz_stream *s = (gz_stream*)file;
290
291 if (s == NULL || s->mode != 'w') return Z_STREAM_ERROR;
292
293 s->stream.next_in = buf;
294 s->stream.avail_in = len;
295
296 while (s->stream.avail_in != 0) {
297
298 if (s->stream.avail_out == 0) {
299
300 s->stream.next_out = s->outbuf;
301 if (fwrite(s->outbuf, 1, Z_BUFSIZE, s->file) != Z_BUFSIZE) {
302 s->z_err = Z_ERRNO;
303 break;
304 }
305 s->stream.avail_out = Z_BUFSIZE;
306 }
307 s->z_err = deflate(&(s->stream), Z_NO_FLUSH);
308
309 if (s->z_err != Z_OK) break;
310 }
311 s->crc = crc32(s->crc, buf, len);
312
313 return len - s->stream.avail_in;
314}
315
316/* ===========================================================================
317 Flushes all pending output into the compressed file. The parameter
318 flush is as in the deflate() function.
319 gzflush should be called only when strictly necessary because it can
320 degrade compression.
321*/
322int gzflush (file, flush)
323 gzFile file;
324 int flush;
325{
326 uInt len;
327 int done = 0;
328 gz_stream *s = (gz_stream*)file;
329
330 if (s == NULL || s->mode != 'w') return Z_STREAM_ERROR;
331
332 s->stream.avail_in = 0; /* should be zero already anyway */
333
334 for (;;) {
335 len = Z_BUFSIZE - s->stream.avail_out;
336
337 if (len != 0) {
338 if (fwrite(s->outbuf, 1, len, s->file) != len) {
339 s->z_err = Z_ERRNO;
340 break;
341 }
342 s->stream.next_out = s->outbuf;
343 s->stream.avail_out = Z_BUFSIZE;
344 }
345 if (done) break;
346 s->z_err = deflate(&(s->stream), flush);
347
348 if (s->z_err != Z_OK) break;
349
350 /* deflate has finished flushing only when it hasn't used up
351 * all the available space in the output buffer:
352 */
353 done = (s->stream.avail_out != 0);
354 }
355 return s->z_err;
356}
357
358/* ===========================================================================
359 Outputs a long in LSB order to the given file
360*/
361local void putLong (file, x)
362 FILE *file;
363 uLong x;
364{
365 int n;
366 for (n = 0; n < 4; n++) {
367 fputc(x & 0xff, file);
368 x >>= 8;
369 }
370}
371
372/* ===========================================================================
373 Reads a long in LSB order from the given buffer
374*/
375local uLong getLong (buf)
376 Byte *buf;
377{
378 uLong x = 0;
379 Byte *p = buf+4;
380
381 do {
382 x <<= 8;
383 x |= *--p;
384 } while (p != buf);
385 return x;
386}
387
388/* ===========================================================================
389 Flushes all pending output if necessary, closes the compressed file
390 and deallocates all the (de)compression state.
391*/
392int gzclose (file)
393 gzFile file;
394{
395 uInt n;
396 gz_stream *s = (gz_stream*)file;
397
398 if (s == NULL) return Z_STREAM_ERROR;
399
400 if (s->mode == 'w') {
401 gzflush (file, Z_FINISH);
402 putLong (s->file, s->crc);
403 putLong (s->file, s->stream.total_in);
404
405 } else if (s->mode == 'r' && s->z_err == Z_STREAM_END) {
406
407 /* slide CRC and original size if they are at the end of inbuf */
408 if ((n = s->stream.avail_in) < 8 && !s->z_eof) {
409 Byte *p = s->inbuf;
410 Byte *q = s->stream.next_in;
411 while (n--) { *p++ = *q++; };
412
413 n = s->stream.avail_in;
414 n += fread(p, 1, 8, s->file);
415 s->stream.next_in = s->inbuf;
416 }
417 /* check CRC and original size */
418 if (n < 8 ||
419 getLong(s->stream.next_in) != s->crc ||
420 getLong(s->stream.next_in + 4) != s->stream.total_out) {
421
422 s->z_err = Z_DATA_ERROR;
423 }
424 }
425 return destroy(file);
426}
427
428/* ===========================================================================
429 Returns the error message for the last error which occured on the
430 given compressed file. errnum is set to zlib error number. If an
431 error occured in the file system and not in the compression library,
432 errnum is set to Z_ERRNO and the application may consult errno
433 to get the exact error code.
434*/
435char* gzerror (file, errnum)
436 gzFile file;
437 int *errnum;
438{
439 char *m;
440 gz_stream *s = (gz_stream*)file;
441
442 if (s == NULL) {
443 *errnum = Z_STREAM_ERROR;
444 return z_errmsg[1-Z_STREAM_ERROR];
445 }
446 *errnum = s->z_err;
447 if (*errnum == Z_OK) return "";
448
449 m = *errnum == Z_ERRNO ? zstrerror(errno) : s->stream.msg;
450
451 if (m == NULL || *m == '\0') m = z_errmsg[1-s->z_err];
452
453 TRYFREE(s->msg);
454 s->msg = (char*)ALLOC(strlen(s->path) + strlen(m) + 3);
455 strcpy(s->msg, s->path);
456 strcat(s->msg, ": ");
457 strcat(s->msg, m);
458 return s->msg;
459}
diff --git a/infblock.c b/infblock.c
new file mode 100644
index 0000000..3a58280
--- /dev/null
+++ b/infblock.c
@@ -0,0 +1,324 @@
1/* infblock.c -- interpret and process block types to last block
2 * Copyright (C) 1995 Mark Adler
3 * For conditions of distribution and use, see copyright notice in zlib.h
4 */
5
6#include "zutil.h"
7#include "infblock.h"
8#include "inftrees.h"
9#include "infcodes.h"
10#include "infutil.h"
11
12struct inflate_codes_state {int dummy;}; /* for buggy compilers */
13
14/* Table for deflate from PKZIP's appnote.txt. */
15local uInt border[] = { /* Order of the bit length code lengths */
16 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
17
18/*
19 Notes beyond the 1.93a appnote.txt:
20
21 1. Distance pointers never point before the beginning of the output
22 stream.
23 2. Distance pointers can point back across blocks, up to 32k away.
24 3. There is an implied maximum of 7 bits for the bit length table and
25 15 bits for the actual data.
26 4. If only one code exists, then it is encoded using one bit. (Zero
27 would be more efficient, but perhaps a little confusing.) If two
28 codes exist, they are coded using one bit each (0 and 1).
29 5. There is no way of sending zero distance codes--a dummy must be
30 sent if there are none. (History: a pre 2.0 version of PKZIP would
31 store blocks with no distance codes, but this was discovered to be
32 too harsh a criterion.) Valid only for 1.93a. 2.04c does allow
33 zero distance codes, which is sent as one code of zero bits in
34 length.
35 6. There are up to 286 literal/length codes. Code 256 represents the
36 end-of-block. Note however that the static length tree defines
37 288 codes just to fill out the Huffman codes. Codes 286 and 287
38 cannot be used though, since there is no length base or extra bits
39 defined for them. Similarily, there are up to 30 distance codes.
40 However, static trees define 32 codes (all 5 bits) to fill out the
41 Huffman codes, but the last two had better not show up in the data.
42 7. Unzip can check dynamic Huffman blocks for complete code sets.
43 The exception is that a single code would not be complete (see #4).
44 8. The five bits following the block type is really the number of
45 literal codes sent minus 257.
46 9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits
47 (1+6+6). Therefore, to output three times the length, you output
48 three codes (1+1+1), whereas to output four times the same length,
49 you only need two codes (1+3). Hmm.
50 10. In the tree reconstruction algorithm, Code = Code + Increment
51 only if BitLength(i) is not zero. (Pretty obvious.)
52 11. Correction: 4 Bits: # of Bit Length codes - 4 (4 - 19)
53 12. Note: length code 284 can represent 227-258, but length code 285
54 really is 258. The last length deserves its own, short code
55 since it gets used a lot in very redundant files. The length
56 258 is special since 258 - 3 (the min match length) is 255.
57 13. The literal/length and distance code bit lengths are read as a
58 single stream of lengths. It is possible (and advantageous) for
59 a repeat code (16, 17, or 18) to go across the boundary between
60 the two sets of lengths.
61 */
62
63struct inflate_blocks_state *inflate_blocks_new(z,wsize)
64z_stream *z;
65uInt wsize;
66{
67 struct inflate_blocks_state *s;
68
69 if ((s = (struct inflate_blocks_state *)ZALLOC
70 (z,1,sizeof(struct inflate_blocks_state))) == Z_NULL)
71 return s;
72 if ((s->window = (Byte *)ZALLOC(z,1,wsize)) == Z_NULL)
73 {
74 ZFREE(z, s);
75 return Z_NULL;
76 }
77 s->mode = TYPE;
78 s->bitk = 0;
79 s->read = s->write = s->window;
80 s->end = s->window + wsize;
81 s->check = 1;
82 return s;
83}
84
85
86int inflate_blocks(s, z, r)
87struct inflate_blocks_state *s;
88z_stream *z;
89int r;
90{
91 uInt t; /* temporary storage */
92 uLong b; /* bit buffer */
93 uInt k; /* bits in bit buffer */
94 Byte *p; /* input data pointer */
95 uInt n; /* bytes available there */
96 Byte *q; /* output window write pointer */
97 uInt m; /* bytes to end of window or read pointer */
98
99 /* copy input/output information to locals (UPDATE macro restores) */
100 LOAD
101
102 /* process input based on current state */
103 while (1) switch (s->mode)
104 {
105 case TYPE:
106 NEEDBITS(3)
107 t = (uInt)b & 7;
108 s->last = t & 1;
109 switch (t >> 1)
110 {
111 case 0: /* stored */
112 DUMPBITS(3)
113 t = k & 7; /* go to byte boundary */
114 DUMPBITS(t)
115 s->mode = LENS; /* get length of stored block */
116 break;
117 case 1: /* fixed */
118 {
119 uInt bl, bd;
120 inflate_huft *tl, *td;
121
122 inflate_trees_fixed(&bl, &bd, &tl, &td);
123 s->sub.codes = inflate_codes_new(bl, bd, tl, td, z);
124 if (s->sub.codes == Z_NULL)
125 {
126 r = Z_MEM_ERROR;
127 LEAVE
128 }
129 }
130 DUMPBITS(3)
131 s->mode = CODES;
132 break;
133 case 2: /* dynamic */
134 DUMPBITS(3)
135 s->mode = TABLE;
136 break;
137 case 3: /* illegal */
138 DUMPBITS(3)
139 s->mode = ERROR;
140 z->msg = "invalid block type";
141 r = Z_DATA_ERROR;
142 LEAVE
143 }
144 break;
145 case LENS:
146 NEEDBITS(32)
147 if ((~b) >> 16 != (b & 0xffff))
148 {
149 s->mode = ERROR;
150 z->msg = "invalid stored block lengths";
151 r = Z_DATA_ERROR;
152 LEAVE
153 }
154 k = 0; /* dump bits */
155 s->sub.left = (uInt)b & 0xffff;
156 s->mode = s->sub.left ? STORED : TYPE;
157 break;
158 case STORED:
159 do {
160 NEEDBYTE
161 NEEDOUT
162 OUTBYTE(NEXTBYTE)
163 } while (--s->sub.left);
164 s->mode = s->last ? DRY : TYPE;
165 break;
166 case TABLE:
167 NEEDBITS(14)
168 s->sub.trees.table = t = (uInt)b & 0x3fff;
169#ifndef PKZIP_BUG_WORKAROUND
170 if ((t & 0x1f) > 29 || ((t >> 5) & 0x1f) > 29)
171 {
172 s->mode = ERROR;
173 z->msg = "too many length or distance symbols";
174 r = Z_DATA_ERROR;
175 LEAVE
176 }
177#endif
178 t = 258 + (t & 0x1f) + ((t >> 5) & 0x1f);
179 if (t < 19)
180 t = 19;
181 if ((s->sub.trees.blens = (uInt*)ZALLOC(z, t, sizeof(uInt))) == Z_NULL)
182 {
183 r = Z_MEM_ERROR;
184 LEAVE
185 }
186 DUMPBITS(14)
187 s->sub.trees.index = 0;
188 s->mode = BTREE;
189 case BTREE:
190 while (s->sub.trees.index < 4 + (s->sub.trees.table >> 10))
191 {
192 NEEDBITS(3)
193 s->sub.trees.blens[border[s->sub.trees.index++]] = (uInt)b & 7;
194 DUMPBITS(3)
195 }
196 while (s->sub.trees.index < 19)
197 s->sub.trees.blens[border[s->sub.trees.index++]] = 0;
198 s->sub.trees.bb = 7;
199 t = inflate_trees_bits(s->sub.trees.blens, &s->sub.trees.bb,
200 &s->sub.trees.tb, z);
201 if (t != Z_OK)
202 {
203 r = t;
204 if (r == Z_DATA_ERROR)
205 s->mode = ERROR;
206 LEAVE
207 }
208 s->sub.trees.index = 0;
209 s->mode = DTREE;
210 case DTREE:
211 while (t = s->sub.trees.table,
212 s->sub.trees.index < 258 + (t & 0x1f) + ((t >> 5) & 0x1f))
213 {
214 inflate_huft *h;
215 uInt i, j, c;
216
217 t = s->sub.trees.bb;
218 NEEDBITS(t)
219 h = s->sub.trees.tb + ((uInt)b & inflate_mask[t]);
220 t = h->word.what.Bits;
221 c = h->more.Base;
222 if (c < 16)
223 {
224 DUMPBITS(t)
225 s->sub.trees.blens[s->sub.trees.index++] = c;
226 }
227 else /* c == 16..18 */
228 {
229 i = c == 18 ? 7 : c - 14;
230 j = c == 18 ? 11 : 3;
231 NEEDBITS(t + i)
232 DUMPBITS(t)
233 j += (uInt)b & inflate_mask[i];
234 DUMPBITS(i)
235 i = s->sub.trees.index;
236 t = s->sub.trees.table;
237 if (i + j > 258 + (t & 0x1f) + ((t >> 5) & 0x1f) ||
238 (c == 16 && i < 1))
239 {
240 s->mode = ERROR;
241 z->msg = "invalid bit length repeat";
242 r = Z_DATA_ERROR;
243 LEAVE
244 }
245 c = c == 16 ? s->sub.trees.blens[i - 1] : 0;
246 do {
247 s->sub.trees.blens[i++] = c;
248 } while (--j);
249 s->sub.trees.index = i;
250 }
251 }
252 inflate_trees_free(s->sub.trees.tb, z);
253 s->sub.trees.tb = Z_NULL;
254 {
255 uInt bl, bd;
256 inflate_huft *tl, *td;
257 struct inflate_codes_state *c;
258
259 bl = 9;
260 bd = 6;
261 t = s->sub.trees.table;
262 t = inflate_trees_dynamic(257 + (t & 0x1f), 1 + ((t >> 5) & 0x1f),
263 s->sub.trees.blens, &bl, &bd, &tl, &td, z);
264 if (t != Z_OK)
265 {
266 if (t == (uInt)Z_DATA_ERROR)
267 s->mode = ERROR;
268 r = t;
269 LEAVE
270 }
271 if ((c = inflate_codes_new(bl, bd, tl, td, z)) == Z_NULL)
272 {
273 inflate_trees_free(td, z);
274 inflate_trees_free(tl, z);
275 r = Z_MEM_ERROR;
276 LEAVE
277 }
278 ZFREE(z, s->sub.trees.blens);
279 s->sub.codes = c;
280 }
281 s->mode = CODES;
282 case CODES:
283 UPDATE
284 if ((r = inflate_codes(s, z, r)) != Z_STREAM_END)
285 return inflate_flush(s, z, r);
286 r = Z_OK;
287 inflate_codes_free(s->sub.codes, z);
288 LOAD
289 s->mode = s->last ? DRY : TYPE;
290 break;
291 case DRY:
292 FLUSH
293 if (s->read != s->write)
294 LEAVE
295 s->mode = DONE;
296 case DONE:
297 r = Z_STREAM_END;
298 LEAVE
299 case ERROR:
300 r = Z_DATA_ERROR;
301 LEAVE
302 default:
303 r = Z_STREAM_ERROR;
304 LEAVE
305 }
306}
307
308
309int inflate_blocks_free(s, z, c, e)
310struct inflate_blocks_state *s;
311z_stream *z;
312uLong *c;
313int *e;
314{
315 *e = s->bitk > 7 ? (s->bitb >> (s->bitk & 7)) & 0xff : -1;
316 *c = s->check;
317 if (s->mode == BTREE || s->mode == DTREE)
318 ZFREE(z, s->sub.trees.blens);
319 if (s->mode == CODES)
320 inflate_codes_free(s->sub.codes, z);
321 ZFREE(z, s->window);
322 ZFREE(z, s);
323 return Z_OK;
324}
diff --git a/infblock.h b/infblock.h
new file mode 100644
index 0000000..f70c471
--- /dev/null
+++ b/infblock.h
@@ -0,0 +1,26 @@
1/* infblock.h -- header to use infblock.c
2 * Copyright (C) 1995 Mark Adler
3 * For conditions of distribution and use, see copyright notice in zlib.h
4 */
5
6/* WARNING: this file should *not* be used by applications. It is
7 part of the implementation of the compression library and is
8 subject to change. Applications should only use zlib.h.
9 */
10
11struct inflate_blocks_state;
12
13extern struct inflate_blocks_state * inflate_blocks_new __P((
14 z_stream *,
15 uInt)); /* window size */
16
17extern int inflate_blocks __P((
18 struct inflate_blocks_state *,
19 z_stream *,
20 int)); /* initial return code */
21
22extern int inflate_blocks_free __P((
23 struct inflate_blocks_state *,
24 z_stream *,
25 uLong *, /* check value on output */
26 int *)); /* possible leftover byte to return */
diff --git a/infcodes.c b/infcodes.c
new file mode 100644
index 0000000..ffae26d
--- /dev/null
+++ b/infcodes.c
@@ -0,0 +1,217 @@
1/* infcodes.c -- process literals and length/distance pairs
2 * Copyright (C) 1995 Mark Adler
3 * For conditions of distribution and use, see copyright notice in zlib.h
4 */
5
6#include "zutil.h"
7#include "inftrees.h"
8#include "infutil.h"
9#include "infcodes.h"
10
11/* simplify the use of the inflate_huft type with some defines */
12#define base more.Base
13#define next more.Next
14#define exop word.what.Exop
15#define bits word.what.Bits
16
17/* inflate codes private state */
18struct inflate_codes_state {
19
20 /* mode */
21 enum { /* waiting for "i:"=input, "o:"=output, "x:"=nothing */
22 START, /* x: set up for LEN */
23 LEN, /* i: get length/literal/eob next */
24 LENEXT, /* i: getting length extra (have base) */
25 DIST, /* i: get distance next */
26 DISTEXT, /* i: getting distance extra */
27 COPY, /* o: copying bytes in window, waiting for space */
28 LIT, /* o: got literal, waiting for output space */
29 WASH, /* o: got eob, possibly still output waiting */
30 END, /* x: got eob and all data flushed */
31 BAD} /* x: got error */
32 mode; /* current inflate_codes mode */
33
34 /* mode dependent information */
35 uInt len;
36 union {
37 struct {
38 inflate_huft *tree; /* pointer into tree */
39 uInt need; /* bits needed */
40 } code; /* if LEN or DIST, where in tree */
41 uInt lit; /* if LIT, literal */
42 struct {
43 uInt get; /* bits to get for extra */
44 uInt dist; /* distance back to copy from */
45 } copy; /* if EXT or COPY, where and how much */
46 } sub; /* submode */
47
48 /* mode independent information */
49 Byte lbits; /* ltree bits decoded per branch */
50 Byte dbits; /* dtree bits decoder per branch */
51 inflate_huft *ltree; /* literal/length/eob tree */
52 inflate_huft *dtree; /* distance tree */
53
54};
55
56
57struct inflate_codes_state *inflate_codes_new(bl, bd, tl, td, z)
58uInt bl, bd;
59inflate_huft *tl, *td;
60z_stream *z;
61{
62 struct inflate_codes_state *c;
63
64 if ((c = (struct inflate_codes_state *)
65 ZALLOC(z,1,sizeof(struct inflate_codes_state))) != Z_NULL)
66 {
67 c->mode = START;
68 c->lbits = (Byte)bl;
69 c->dbits = (Byte)bd;
70 c->ltree = tl;
71 c->dtree = td;
72 }
73 return c;
74}
75
76
77int inflate_codes(s, z, r)
78struct inflate_blocks_state *s;
79z_stream *z;
80int r;
81{
82 uInt j; /* temporary storage */
83 inflate_huft *t; /* temporary pointer */
84 int e; /* extra bits or operation */
85 uLong b; /* bit buffer */
86 uInt k; /* bits in bit buffer */
87 Byte *p; /* input data pointer */
88 uInt n; /* bytes available there */
89 Byte *q; /* output window write pointer */
90 uInt m; /* bytes to end of window or read pointer */
91 Byte *f; /* pointer to copy strings from */
92 struct inflate_codes_state *c = s->sub.codes; /* codes state */
93
94 /* copy input/output information to locals (UPDATE macro restores) */
95 LOAD
96
97 /* process input and output based on current state */
98 while (1) switch (c->mode)
99 { /* waiting for "i:"=input, "o:"=output, "x:"=nothing */
100 case START: /* x: set up for LEN */
101 /* %%% check for avail in and out to do fast loop %%% */
102 c->sub.code.need = c->lbits;
103 c->sub.code.tree = c->ltree;
104 c->mode = LEN;
105 case LEN: /* i: get length/literal/eob next */
106 j = c->sub.code.need;
107 NEEDBITS(j)
108 t = c->sub.code.tree + ((uInt)b & inflate_mask[j]);
109 DUMPBITS(t->bits)
110 if ((e = (int)(t->exop)) < 0)
111 {
112 if (e == -128) /* invalid code */
113 {
114 c->mode = BAD;
115 z->msg = "invalid huffman code";
116 r = Z_DATA_ERROR;
117 LEAVE
118 }
119 e = -e;
120 if (e & 64) /* end of block */
121 {
122 c->mode = END;
123 break;
124 }
125 c->sub.code.need = e;
126 c->sub.code.tree = t->next;
127 break;
128 }
129 if (e & 16) /* literal */
130 {
131 c->sub.lit = t->base;
132 c->mode = LIT;
133 break;
134 }
135 c->sub.copy.get = e;
136 c->len = t->base;
137 c->mode = LENEXT;
138 case LENEXT: /* i: getting length extra (have base) */
139 j = c->sub.copy.get;
140 NEEDBITS(j)
141 c->len += (uInt)b & inflate_mask[j];
142 DUMPBITS(j)
143 c->sub.code.need = c->dbits;
144 c->sub.code.tree = c->dtree;
145 c->mode = DIST;
146 case DIST: /* i: get distance next */
147 j = c->sub.code.need;
148 NEEDBITS(j)
149 t = c->sub.code.tree + ((uInt)b & inflate_mask[j]);
150 DUMPBITS(t->bits)
151 if ((e = (int)(t->exop)) < 0)
152 {
153 if (e == -128)
154 {
155 c->mode = BAD;
156 z->msg = "invalid huffman code";
157 r = Z_DATA_ERROR;
158 LEAVE
159 }
160 c->sub.code.need = -e;
161 c->sub.code.tree = t->next;
162 break;
163 }
164 c->sub.copy.dist = t->base;
165 c->sub.copy.get = e;
166 c->mode = DISTEXT;
167 case DISTEXT: /* i: getting distance extra */
168 j = c->sub.copy.get;
169 NEEDBITS(j)
170 c->sub.copy.dist += (uInt)b & inflate_mask[j];
171 DUMPBITS(j)
172 c->mode = COPY;
173 case COPY: /* o: copying bytes in window, waiting for space */
174 f = q - s->window < c->sub.copy.dist ?
175 s->end - (c->sub.copy.dist - (q - s->window)) :
176 q - c->sub.copy.dist;
177 while (c->len)
178 {
179 NEEDOUT
180 OUTBYTE(*f++)
181 if (f == s->end)
182 f = s->window;
183 c->len--;
184 }
185 c->mode = START;
186 break;
187 case LIT: /* o: got literal, waiting for output space */
188 NEEDOUT
189 OUTBYTE(c->sub.lit)
190 c->mode = START;
191 break;
192 case WASH: /* o: got eob, possibly more output */
193 FLUSH
194 if (s->read != s->write)
195 LEAVE
196 c->mode = END;
197 case END:
198 r = Z_STREAM_END;
199 LEAVE
200 case BAD: /* x: got error */
201 r = Z_DATA_ERROR;
202 LEAVE
203 default:
204 r = Z_STREAM_ERROR;
205 LEAVE
206 }
207}
208
209
210void inflate_codes_free(c, z)
211struct inflate_codes_state *c;
212z_stream *z;
213{
214 inflate_trees_free(c->dtree, z);
215 inflate_trees_free(c->ltree, z);
216 ZFREE(z, c);
217}
diff --git a/infcodes.h b/infcodes.h
new file mode 100644
index 0000000..af99cd1
--- /dev/null
+++ b/infcodes.h
@@ -0,0 +1,25 @@
1/* infcodes.h -- header to use infcodes.c
2 * Copyright (C) 1995 Mark Adler
3 * For conditions of distribution and use, see copyright notice in zlib.h
4 */
5
6/* WARNING: this file should *not* be used by applications. It is
7 part of the implementation of the compression library and is
8 subject to change. Applications should only use zlib.h.
9 */
10
11struct inflate_codes_state;
12
13extern struct inflate_codes_state *inflate_codes_new __P((
14 uInt, uInt,
15 inflate_huft *, inflate_huft *,
16 z_stream *));
17
18extern int inflate_codes __P((
19 struct inflate_blocks_state *,
20 z_stream *,
21 int));
22
23extern void inflate_codes_free __P((
24 struct inflate_codes_state *,
25 z_stream *));
diff --git a/inflate.c b/inflate.c
new file mode 100644
index 0000000..478f46d
--- /dev/null
+++ b/inflate.c
@@ -0,0 +1,221 @@
1/* inflate.c -- zlib interface to inflate modules
2 * Copyright (C) 1995 Mark Adler
3 * For conditions of distribution and use, see copyright notice in zlib.h
4 */
5
6#include "zutil.h"
7#include "infblock.h"
8
9struct inflate_blocks_state {int dummy;}; /* for buggy compilers */
10
11/* inflate private state */
12struct internal_state {
13
14 /* mode */
15 enum {
16 METHOD, /* waiting for method byte */
17 FLAG, /* waiting for flag byte */
18 START, /* make new blocks state */
19 BLOCKS, /* decompressing blocks */
20 CHECK4, /* four check bytes to go */
21 CHECK3, /* three check bytes to go */
22 CHECK2, /* two check bytes to go */
23 CHECK1, /* one check byte to go */
24 DONE, /* finished check, done */
25 ERROR} /* got an error--stay here */
26 mode; /* current inflate mode */
27
28 int no_header;
29 uInt w_size; /* LZ77 window size (32K by default) */
30 uInt w_bits; /* log2(w_size) (8..16) */
31
32 /* mode dependent information */
33 union {
34 uInt method; /* if FLAGS, method byte */
35 struct inflate_blocks_state
36 *blocks; /* if BLOCKS, current state */
37 struct {
38 uLong was; /* computed check value */
39 uLong need; /* stream check value */
40 } check; /* if CHECK, check values to compare */
41 } sub; /* submode */
42};
43
44
45int inflateInit (strm)
46z_stream *strm;
47{
48 return inflateInit2(strm, WBITS);
49}
50
51int inflateInit2(z, windowBits)
52z_stream *z;
53int windowBits;
54{
55 if (z == Z_NULL)
56 return Z_STREAM_ERROR;
57 if (z->zalloc == Z_NULL) z->zalloc = zcalloc;
58 if (z->zfree == Z_NULL) z->zfree = zcfree;
59 z->total_in = z->total_out = 0;
60 z->msg = Z_NULL;
61 if ((z->state = (struct internal_state *)
62 ZALLOC(z,1,sizeof(struct internal_state))) == Z_NULL)
63 return Z_MEM_ERROR;
64 z->state->mode = METHOD;
65
66 z->state->no_header = 0;
67 if (windowBits < 0) { /* undocumented feature: no zlib header */
68 windowBits = - windowBits;
69 z->state->no_header = 1;
70 z->state->sub.method = DEFLATED;
71 z->state->mode = START;
72 }
73 if (windowBits < 8 || windowBits > 15) {
74 inflateEnd(z);
75 return Z_STREAM_ERROR;
76 }
77 z->state->w_bits = windowBits;
78 z->state->w_size = 1<<windowBits;
79 return Z_OK;
80}
81
82
83#define NEXTBYTE (z->avail_in--,z->total_in++,*z->next_in++)
84
85int inflate(z, f)
86z_stream *z;
87int f;
88{
89 int r;
90 uInt b;
91 uLong c;
92
93 if (z == Z_NULL || z->next_in == Z_NULL)
94 return Z_STREAM_ERROR;
95 r = Z_BUF_ERROR;
96 while (1) switch (z->state->mode)
97 {
98 case METHOD:
99 if (z->avail_in == 0) return r; r = Z_OK;
100 if (((z->state->sub.method = NEXTBYTE) & 0xf != DEFLATED))
101 {
102 z->state->mode = ERROR;
103 z->msg = "unknown compression method";
104 return Z_DATA_ERROR;
105 }
106 if ((z->state->sub.method >> 4) > z->state->w_bits)
107 {
108 z->state->mode = ERROR;
109 z->msg = "invalid window size";
110 return Z_DATA_ERROR;
111 }
112 z->state->mode = FLAG;
113 case FLAG:
114 if (z->avail_in == 0) return r; r = Z_OK;
115 if ((b = NEXTBYTE) & 0x20)
116 {
117 z->state->mode = ERROR;
118 z->msg = "invalid reserved bit";
119 return Z_DATA_ERROR;
120 }
121 if (((z->state->sub.method << 8) + b) % 31)
122 {
123 z->state->mode = ERROR;
124 z->msg = "incorrect header check";
125 return Z_DATA_ERROR;
126 }
127 z->state->mode = START;
128 case START:
129 if ((z->state->sub.blocks = inflate_blocks_new(z,z->state->w_size))
130 == Z_NULL)
131 return Z_MEM_ERROR;
132 z->state->mode = BLOCKS;
133 case BLOCKS:
134 if ((r = inflate_blocks(z->state->sub.blocks, z, r)) != Z_STREAM_END)
135 return r;
136 inflate_blocks_free(z->state->sub.blocks, z, &c, &r);
137 if (z->state->no_header) {
138 z->state->mode = DONE;
139 return Z_STREAM_END;
140 }
141 z->state->sub.check.was = c;
142 if (r != -1)
143 {
144 z->state->sub.check.need = (uLong)r << 24;
145 z->state->mode = CHECK3;
146 r = Z_OK;
147 break;
148 }
149 r = Z_OK;
150 z->state->mode = CHECK4;
151 case CHECK4:
152 if (z->avail_in == 0) return r; r = Z_OK;
153 z->state->sub.check.need = (uLong)NEXTBYTE << 24;
154 z->state->mode = CHECK3;
155 case CHECK3:
156 if (z->avail_in == 0) return r; r = Z_OK;
157 z->state->sub.check.need += (uLong)NEXTBYTE << 16;
158 z->state->mode = CHECK2;
159 case CHECK2:
160 if (z->avail_in == 0) return r; r = Z_OK;
161 z->state->sub.check.need += (uLong)NEXTBYTE << 8;
162 z->state->mode = CHECK1;
163 case CHECK1:
164 if (z->avail_in == 0) return r; r = Z_OK;
165 z->state->sub.check.need += (uLong)NEXTBYTE;
166 if (z->state->sub.check.was != z->state->sub.check.need)
167 {
168 z->state->mode = ERROR;
169 z->msg = "incorrect data check";
170 return Z_DATA_ERROR;
171 }
172 z->state->mode = DONE;
173 case DONE:
174 return Z_STREAM_END;
175 case ERROR:
176 return Z_DATA_ERROR;
177 default:
178 return Z_STREAM_ERROR;
179 }
180}
181
182
183int inflateEnd(z)
184z_stream *z;
185{
186 uLong c;
187 int e;
188
189 if (z == Z_NULL || z->state == Z_NULL || z->zfree == Z_NULL)
190 return Z_STREAM_ERROR;
191 if (z->state->mode == BLOCKS)
192 inflate_blocks_free(z->state->sub.blocks, z, &c, &e);
193 ZFREE(z, z->state);
194 z->state = Z_NULL;
195 return Z_OK;
196}
197
198
199/* inflateSync not implemented yet--this just consumes input */
200int inflateSync(z)
201z_stream *z;
202{
203 if (z == Z_NULL) return Z_STREAM_ERROR;
204 if (z->avail_in == 0) return Z_BUF_ERROR;
205 do {
206 z->total_in++;
207 } while (--z->avail_in);
208 return Z_DATA_ERROR;
209}
210
211
212/* inflateReset not fully implemented yet--this frees and reallocates */
213int inflateReset(z)
214z_stream *z;
215{
216 int r;
217
218 if ((r = inflateEnd(z)) != Z_OK)
219 return r;
220 return inflateInit(z);
221}
diff --git a/inflate.h b/inflate.h
new file mode 100644
index 0000000..843224f
--- /dev/null
+++ b/inflate.h
@@ -0,0 +1,22 @@
1/* temporary kludge assuming single pass decompression */
2
3/* $Id: inflate.h,v 1.2 1995/04/11 14:47:32 jloup Exp $ */
4
5#include <stdio.h>
6
7#define NEXTBYTE \
8 (istrm->total_in++, istrm->avail_in-- == 0 ? \
9 (z_error("too small"), 0) : *istrm->next_in++)
10
11#define FLUSH(n) { \
12 if (istrm->avail_out < n) z_error("too big"); \
13 istrm->avail_out -= n; \
14 memcpy(istrm->next_out, slide, n); \
15 istrm->next_out += n; \
16 istrm->total_out += n; \
17}
18#define WSIZE istrm->state->w_size
19#define slide istrm->state->window
20#define memzero(a,s) memset((a),0,(s))
21#define inflate z_inflate
22#define qflag 1
diff --git a/inftest.c b/inftest.c
new file mode 100644
index 0000000..7dc2907
--- /dev/null
+++ b/inftest.c
@@ -0,0 +1,67 @@
1#include <stdio.h>
2#include <stdlib.h>
3#include "zutil.h"
4
5/* This test is in honor of Ed Hamrick who suggested that the interface
6 to inflate be a byte at a time--this implements that, and is, of course,
7 monumentally slow. It has the virtue though of stressing the push-pull
8 interface for testing purposes. */
9
10void main()
11{
12 int a, r;
13 char c;
14 z_stream z;
15
16 z.zalloc = Z_NULL;
17 z.zfree = Z_NULL;
18 r = inflateInit(&z);
19 if (r != Z_OK)
20 fprintf(stderr, "init error: %s\n", z_errmsg[1 - r]);
21 while ((a = getchar()) != EOF)
22 {
23 /* feed one byte of input */
24 z.avail_out = 0;
25 c = (char)a;
26 z.next_in = (Byte*)&c;
27 z.avail_in = 1;
28 r = inflate(&z, 0);
29 if (r == Z_STREAM_END)
30 break;
31 if (r != Z_OK)
32 {
33 fprintf(stderr, "inflate error: %s\n", z_errmsg[1 - r]);
34 break;
35 }
36 if (z.avail_in != 0)
37 {
38 fprintf(stderr, "inflate didn't eat byte and didn't say buf err!\n");
39 break;
40 }
41
42 /* empty output one byte at a time */
43 while (1)
44 {
45 z.next_out = (Byte*)&c;
46 z.avail_out = 1;
47 r = inflate(&z, 0);
48 if (r == Z_STREAM_END)
49 break;
50 if (r != Z_OK && r != Z_BUF_ERROR)
51 {
52 fprintf(stderr, "inflate error: %s\n", z_errmsg[1 - r]);
53 break;
54 }
55 if (z.avail_out == 0)
56 putchar(c);
57 else
58 break;
59 }
60 if (r != Z_OK && r != Z_BUF_ERROR)
61 break;
62 }
63 inflateEnd(&z);
64 fprintf(stderr, "%d bytes in, %d bytes out\n", z.total_in, z.total_out);
65 if (z.msg != NULL)
66 fprintf(stderr, "msg is <%s>\n", z.msg);
67}
diff --git a/inftrees.c b/inftrees.c
new file mode 100644
index 0000000..4b00e3c
--- /dev/null
+++ b/inftrees.c
@@ -0,0 +1,471 @@
1/* inftrees.c -- generate Huffman trees for efficient decoding
2 * Copyright (C) 1995 Mark Adler
3 * For conditions of distribution and use, see copyright notice in zlib.h
4 */
5
6#include "zutil.h"
7#include "inftrees.h"
8
9struct internal_state {int dummy;}; /* for buggy compilers */
10
11/* simplify the use of the inflate_huft type with some defines */
12#define base more.Base
13#define next more.Next
14#define exop word.what.Exop
15#define bits word.what.Bits
16
17
18local int huft_build __P((
19 uInt *, /* code lengths in bits */
20 uInt, /* number of codes */
21 uInt, /* number of "simple" codes */
22 uInt *, /* list of base values for non-simple codes */
23 uInt *, /* list of extra bits for non-simple codes */
24 inflate_huft **, /* result: starting table */
25 uInt *, /* maximum lookup bits (returns actual) */
26 z_stream *)); /* for zalloc function */
27
28local voidp falloc __P((
29 voidp, /* opaque pointer (not used) */
30 uInt, /* number of items */
31 uInt)); /* size of item */
32
33local void ffree __P((
34 voidp q, /* opaque pointer (not used) */
35 voidp p)); /* what to free (not used) */
36
37/* Tables for deflate from PKZIP's appnote.txt. */
38local uInt cplens[] = { /* Copy lengths for literal codes 257..285 */
39 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
40 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0};
41 /* actually lengths - 2; also see note #13 above about 258 */
42local uInt cplext[] = { /* Extra bits for literal codes 257..285 */
43 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
44 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 128, 128}; /* 128==invalid */
45local uInt cpdist[] = { /* Copy offsets for distance codes 0..29 */
46 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
47 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
48 8193, 12289, 16385, 24577};
49local uInt cpdext[] = { /* Extra bits for distance codes */
50 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
51 7, 7, 8, 8, 9, 9, 10, 10, 11, 11,
52 12, 12, 13, 13};
53
54/*
55 Huffman code decoding is performed using a multi-level table lookup.
56 The fastest way to decode is to simply build a lookup table whose
57 size is determined by the longest code. However, the time it takes
58 to build this table can also be a factor if the data being decoded
59 is not very long. The most common codes are necessarily the
60 shortest codes, so those codes dominate the decoding time, and hence
61 the speed. The idea is you can have a shorter table that decodes the
62 shorter, more probable codes, and then point to subsidiary tables for
63 the longer codes. The time it costs to decode the longer codes is
64 then traded against the time it takes to make longer tables.
65
66 This results of this trade are in the variables lbits and dbits
67 below. lbits is the number of bits the first level table for literal/
68 length codes can decode in one step, and dbits is the same thing for
69 the distance codes. Subsequent tables are also less than or equal to
70 those sizes. These values may be adjusted either when all of the
71 codes are shorter than that, in which case the longest code length in
72 bits is used, or when the shortest code is *longer* than the requested
73 table size, in which case the length of the shortest code in bits is
74 used.
75
76 There are two different values for the two tables, since they code a
77 different number of possibilities each. The literal/length table
78 codes 286 possible values, or in a flat code, a little over eight
79 bits. The distance table codes 30 possible values, or a little less
80 than five bits, flat. The optimum values for speed end up being
81 about one bit more than those, so lbits is 8+1 and dbits is 5+1.
82 The optimum values may differ though from machine to machine, and
83 possibly even between compilers. Your mileage may vary.
84 */
85
86
87/* If BMAX needs to be larger than 16, then h and x[] should be uLong. */
88#define BMAX 15 /* maximum bit length of any code */
89#define N_MAX 288 /* maximum number of codes in any set */
90
91#ifdef DEBUG
92 uInt inflate_hufts;
93#endif
94
95local int huft_build(b, n, s, d, e, t, m, zs)
96uInt *b; /* code lengths in bits (all assumed <= BMAX) */
97uInt n; /* number of codes (assumed <= N_MAX) */
98uInt s; /* number of simple-valued codes (0..s-1) */
99uInt *d; /* list of base values for non-simple codes */
100uInt *e; /* list of extra bits for non-simple codes */
101inflate_huft **t; /* result: starting table */
102uInt *m; /* maximum lookup bits, returns actual */
103z_stream *zs; /* for zalloc function */
104/* Given a list of code lengths and a maximum table size, make a set of
105 tables to decode that set of codes. Return Z_OK on success, Z_BUF_ERROR
106 if the given code set is incomplete (the tables are still built in this
107 case), Z_DATA_ERROR if the input is invalid (all zero length codes or an
108 over-subscribed set of lengths), or Z_MEM_ERROR if not enough memory. */
109{
110 uInt a; /* counter for codes of length k */
111 uInt c[BMAX+1]; /* bit length count table */
112 uInt f; /* i repeats in table every f entries */
113 int g; /* maximum code length */
114 int h; /* table level */
115 register uInt i; /* counter, current code */
116 register uInt j; /* counter */
117 register int k; /* number of bits in current code */
118 int l; /* bits per table (returned in m) */
119 register uInt *p; /* pointer into c[], b[], or v[] */
120 register inflate_huft *q; /* points to current table */
121 inflate_huft r; /* table entry for structure assignment */
122 inflate_huft *u[BMAX]; /* table stack */
123 uInt v[N_MAX]; /* values in order of bit length */
124 register int w; /* bits before this table == (l * h) */
125 uInt x[BMAX+1]; /* bit offsets, then code stack */
126 uInt *xp; /* pointer into x */
127 int y; /* number of dummy codes added */
128 uInt z; /* number of entries in current table */
129
130
131 /* Generate counts for each bit length */
132 p = c;
133#define C0 *p++ = 0;
134#define C2 C0 C0 C0 C0
135#define C4 C2 C2 C2 C2
136 C4 /* clear c[]--assume BMAX+1 is 16 */
137 p = b; i = n;
138 do {
139 c[*p++]++; /* assume all entries <= BMAX */
140 } while (--i);
141 if (c[0] == n) /* null input--all zero length codes */
142 {
143 *t = (inflate_huft *)Z_NULL;
144 *m = 0;
145 return Z_OK;
146 }
147
148
149 /* Find minimum and maximum length, bound *m by those */
150 l = *m;
151 for (j = 1; j <= BMAX; j++)
152 if (c[j])
153 break;
154 k = j; /* minimum code length */
155 if ((uInt)l < j)
156 l = j;
157 for (i = BMAX; i; i--)
158 if (c[i])
159 break;
160 g = i; /* maximum code length */
161 if ((uInt)l > i)
162 l = i;
163 *m = l;
164
165
166 /* Adjust last length count to fill out codes, if needed */
167 for (y = 1 << j; j < i; j++, y <<= 1)
168 if ((y -= c[j]) < 0)
169 return Z_DATA_ERROR;
170 if ((y -= c[i]) < 0)
171 return Z_DATA_ERROR;
172 c[i] += y;
173
174
175 /* Generate starting offsets into the value table for each length */
176 x[1] = j = 0;
177 p = c + 1; xp = x + 2;
178 while (--i) { /* note that i == g from above */
179 *xp++ = (j += *p++);
180 }
181
182
183 /* Make a table of values in order of bit lengths */
184 p = b; i = 0;
185 do {
186 if ((j = *p++) != 0)
187 v[x[j]++] = i;
188 } while (++i < n);
189
190
191 /* Generate the Huffman codes and for each, make the table entries */
192 x[0] = i = 0; /* first Huffman code is zero */
193 p = v; /* grab values in bit order */
194 h = -1; /* no tables yet--level -1 */
195 w = -l; /* bits decoded == (l * h) */
196 u[0] = (inflate_huft *)Z_NULL; /* just to keep compilers happy */
197 q = (inflate_huft *)Z_NULL; /* ditto */
198 z = 0; /* ditto */
199
200 /* go through the bit lengths (k already is bits in shortest code) */
201 for (; k <= g; k++)
202 {
203 a = c[k];
204 while (a--)
205 {
206 /* here i is the Huffman code of length k bits for value *p */
207 /* make tables up to required level */
208 while (k > w + l)
209 {
210 h++;
211 w += l; /* previous table always l bits */
212
213 /* compute minimum size table less than or equal to l bits */
214 z = (z = g - w) > (uInt)l ? l : z; /* table size upper limit */
215 if ((f = 1 << (j = k - w)) > a + 1) /* try a k-w bit table */
216 { /* too few codes for k-w bit table */
217 f -= a + 1; /* deduct codes from patterns left */
218 xp = c + k;
219 if (j < z)
220 while (++j < z) /* try smaller tables up to z bits */
221 {
222 if ((f <<= 1) <= *++xp)
223 break; /* enough codes to use up j bits */
224 f -= *xp; /* else deduct codes from patterns */
225 }
226 }
227 z = 1 << j; /* table entries for j-bit table */
228
229 /* allocate and link in new table */
230 if ((q = (inflate_huft *)ZALLOC
231 (zs,z + 1,sizeof(inflate_huft))) == Z_NULL)
232 {
233 if (h)
234 inflate_trees_free(u[0], zs);
235 return Z_MEM_ERROR; /* not enough memory */
236 }
237#ifdef DEBUG
238 inflate_hufts += z + 1;
239#endif
240 *t = q + 1; /* link to list for huft_free() */
241 *(t = &(q->next)) = (inflate_huft *)Z_NULL;
242 u[h] = ++q; /* table starts after link */
243
244 /* connect to last table, if there is one */
245 if (h)
246 {
247 x[h] = i; /* save pattern for backing up */
248 r.bits = (char)l; /* bits to dump before this table */
249 r.exop = (char)(-j); /* bits in this table */
250 r.next = q; /* pointer to this table */
251 j = i >> (w - l); /* (get around Turbo C bug) */
252 u[h-1][j] = r; /* connect to last table */
253 }
254 }
255
256 /* set up table entry in r */
257 r.bits = (char)(k - w);
258 if (p >= v + n)
259 r.exop = -128; /* out of values--invalid code */
260 else if (*p < s)
261 {
262 r.exop = (char)(*p < 256 ? 16 : -64); /* 256 is end-of-block code */
263 r.base = *p++; /* simple code is just the value */
264 }
265 else
266 {
267 r.exop = (char)e[*p - s]; /* non-simple--look up in lists */
268 r.base = d[*p++ - s];
269 }
270
271 /* fill code-like entries with r */
272 f = 1 << (k - w);
273 for (j = i >> w; j < z; j += f)
274 q[j] = r;
275
276 /* backwards increment the k-bit code i */
277 for (j = 1 << (k - 1); i & j; j >>= 1)
278 i ^= j;
279 i ^= j;
280
281 /* backup over finished tables */
282 while ((i & ((1 << w) - 1)) != x[h])
283 {
284 h--; /* don't need to update q */
285 w -= l;
286 }
287 }
288 }
289
290
291 /* Return Z_BUF_ERROR if we were given an incomplete table */
292 return y != 0 && g != 1 ? Z_BUF_ERROR : Z_OK;
293}
294
295
296int inflate_trees_bits(c, bb, tb, z)
297uInt *c; /* 19 code lengths */
298uInt *bb; /* bits tree desired/actual depth */
299inflate_huft **tb; /* bits tree result */
300z_stream *z; /* for zfree function */
301{
302 int r;
303
304 r = huft_build(c, 19, 19, (uInt*)Z_NULL, (uInt*)Z_NULL, tb, bb, z);
305 if (r == Z_DATA_ERROR)
306 z->msg = "oversubscribed dynamic bit lengths tree";
307 else if (r == Z_BUF_ERROR)
308 {
309 inflate_trees_free(*tb, z);
310 z->msg = "incomplete dynamic bit lengths tree";
311 r = Z_DATA_ERROR;
312 }
313 return r;
314}
315
316
317int inflate_trees_dynamic(nl, nd, c, bl, bd, tl, td, z)
318uInt nl; /* number of literal/length codes */
319uInt nd; /* number of distance codes */
320uInt *c; /* that many (total) code lengths */
321uInt *bl; /* literal desired/actual bit depth */
322uInt *bd; /* distance desired/actual bit depth */
323inflate_huft **tl; /* literal/length tree result */
324inflate_huft **td; /* distance tree result */
325z_stream *z; /* for zfree function */
326{
327 int r;
328
329 /* build literal/length tree */
330 if ((r = huft_build(c, nl, 257, cplens, cplext, tl, bl, z)) != Z_OK)
331 {
332 if (r == Z_DATA_ERROR)
333 z->msg = "oversubscribed literal/length tree";
334 else if (r == Z_BUF_ERROR)
335 {
336 inflate_trees_free(*tl, z);
337 z->msg = "incomplete literal/length tree";
338 r = Z_DATA_ERROR;
339 }
340 return r;
341 }
342
343 /* build distance tree */
344 if ((r = huft_build(c + nl, nd, 0, cpdist, cpdext, td, bd, z)) != Z_OK)
345 {
346 if (r == Z_DATA_ERROR)
347 z->msg = "oversubscribed literal/length tree";
348 else if (r == Z_BUF_ERROR) {
349#ifdef PKZIP_BUG_WORKAROUND
350 r = Z_OK;
351 }
352#else
353 inflate_trees_free(*td, z);
354 z->msg = "incomplete literal/length tree";
355 r = Z_DATA_ERROR;
356 }
357 inflate_trees_free(*tl, z);
358 return r;
359#endif
360 }
361
362 /* done */
363 return Z_OK;
364}
365
366
367/* build fixed tables only once--keep them here */
368local int fixed_lock = 0;
369local int fixed_built = 0;
370#define FIXEDH 530 /* number of hufts used by fixed tables */
371local uInt fixed_left = FIXEDH;
372local inflate_huft fixed_mem[FIXEDH];
373local uInt fixed_bl;
374local uInt fixed_bd;
375local inflate_huft *fixed_tl;
376local inflate_huft *fixed_td;
377
378
379local voidp falloc(q, n, s)
380voidp q; /* opaque pointer (not used) */
381uInt n; /* number of items */
382uInt s; /* size of item */
383{
384 Assert(s == sizeof(inflate_huft) && n <= fixed_left,
385 "inflate_trees falloc overflow");
386 fixed_left -= n;
387 return (voidp)(fixed_mem + fixed_left);
388}
389
390
391local void ffree(q, p)
392voidp q;
393voidp p;
394{
395 Assert(0, "inflate_trees ffree called!");
396}
397
398
399int inflate_trees_fixed(bl, bd, tl, td)
400uInt *bl; /* literal desired/actual bit depth */
401uInt *bd; /* distance desired/actual bit depth */
402inflate_huft **tl; /* literal/length tree result */
403inflate_huft **td; /* distance tree result */
404{
405 /* build fixed tables if not built already--lock out other instances */
406 while (++fixed_lock > 1)
407 fixed_lock--;
408 if (!fixed_built)
409 {
410 int k; /* temporary variable */
411 unsigned c[288]; /* length list for huft_build */
412 z_stream z; /* for falloc function */
413
414 /* set up fake z_stream for memory routines */
415 z.zalloc = falloc;
416 z.zfree = ffree;
417 z.opaque = Z_NULL;
418
419 /* literal table */
420 for (k = 0; k < 144; k++)
421 c[k] = 8;
422 for (; k < 256; k++)
423 c[k] = 9;
424 for (; k < 280; k++)
425 c[k] = 7;
426 for (; k < 288; k++)
427 c[k] = 8;
428 fixed_bl = 7;
429 huft_build(c, 288, 257, cplens, cplext, &fixed_tl, &fixed_bl, &z);
430
431 /* distance table */
432 for (k = 0; k < 30; k++)
433 c[k] = 5;
434 fixed_bd = 5;
435 huft_build(c, 30, 0, cpdist, cpdext, &fixed_td, &fixed_bd, &z);
436
437 /* done */
438 fixed_built = 1;
439 }
440 fixed_lock--;
441 *bl = fixed_bl;
442 *bd = fixed_bd;
443 *tl = fixed_tl;
444 *td = fixed_td;
445 return Z_OK;
446}
447
448
449int inflate_trees_free(t, z)
450inflate_huft *t; /* table to free */
451z_stream *z; /* for zfree function */
452/* Free the malloc'ed tables built by huft_build(), which makes a linked
453 list of the tables it made, with the links in a dummy first entry of
454 each table. */
455{
456 register inflate_huft *p, *q;
457
458 /* Don't free fixed trees */
459 if (t >= fixed_mem && t <= fixed_mem + FIXEDH)
460 return Z_OK;
461
462 /* Go through linked list, freeing from the malloced (t[-1]) address. */
463 p = t;
464 while (p != Z_NULL)
465 {
466 q = (--p)->next;
467 ZFREE(z,p);
468 p = q;
469 }
470 return Z_OK;
471}
diff --git a/inftrees.h b/inftrees.h
new file mode 100644
index 0000000..6001a4e
--- /dev/null
+++ b/inftrees.h
@@ -0,0 +1,62 @@
1/* inftrees.h -- header to use inftrees.c
2 * Copyright (C) 1995 Mark Adler
3 * For conditions of distribution and use, see copyright notice in zlib.h
4 */
5
6/* WARNING: this file should *not* be used by applications. It is
7 part of the implementation of the compression library and is
8 subject to change. Applications should only use zlib.h.
9 */
10
11/* Huffman code lookup table entry--this entry is four bytes for machines
12 that have 16-bit pointers (e.g. PC's in the small or medium model).
13 Valid extra bits (exop) are 0..13. exop == -64 is EOB (end of block),
14 exop == 16 means that v is a literal, exop < 0 means that v is a pointer
15 to the next table, which codes -exop bits, and lastly exop == -128
16 indicates an unused code. If a code with exop == -128 is looked up,
17 this implies an error in the data. */
18
19typedef struct inflate_huft_s inflate_huft;
20struct inflate_huft_s {
21 union {
22 struct {
23 char Exop; /* number of extra bits or operation */
24 char Bits; /* number of bits in this code or subcode */
25 } what;
26 Byte *pad; /* pad structure to a power of 2 (4 bytes for */
27 } word; /* 16-bit, 8 bytes for 32-bit machines) */
28 union {
29 uInt Base; /* literal, length base, or distance base */
30 inflate_huft *Next; /* pointer to next level of table */
31 } more;
32};
33
34#ifdef DEBUG
35 extern uInt inflate_hufts;
36#endif
37
38extern int inflate_trees_bits __P((
39 uInt *, /* 19 code lengths */
40 uInt *, /* bits tree desired/actual depth */
41 inflate_huft **, /* bits tree result */
42 z_stream *)); /* for zalloc, zfree functions */
43
44extern int inflate_trees_dynamic __P((
45 uInt, /* number of literal/length codes */
46 uInt, /* number of distance codes */
47 uInt *, /* that many (total) code lengths */
48 uInt *, /* literal desired/actual bit depth */
49 uInt *, /* distance desired/actual bit depth */
50 inflate_huft **, /* literal/length tree result */
51 inflate_huft **, /* distance tree result */
52 z_stream *)); /* for zalloc, zfree functions */
53
54extern int inflate_trees_fixed __P((
55 uInt *, /* literal desired/actual bit depth */
56 uInt *, /* distance desired/actual bit depth */
57 inflate_huft **, /* literal/length tree result */
58 inflate_huft **)); /* distance tree result */
59
60extern int inflate_trees_free __P((
61 inflate_huft *, /* tables to free */
62 z_stream *)); /* for zfree function */
diff --git a/infutil.c b/infutil.c
new file mode 100644
index 0000000..92d115f
--- /dev/null
+++ b/infutil.c
@@ -0,0 +1,76 @@
1/* inflate_util.c -- data and routines common to blocks and codes
2 * Copyright (C) 1995 Mark Adler
3 * For conditions of distribution and use, see copyright notice in zlib.h
4 */
5
6#include "zutil.h"
7#include "inftrees.h"
8#include "infutil.h"
9
10struct inflate_codes_state {int dummy;}; /* for buggy compilers */
11
12/* And'ing with mask[n] masks the lower n bits */
13uInt inflate_mask[] = {
14 0x0000,
15 0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff,
16 0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff
17};
18
19
20/* copy as much as possible from the sliding window to the output area */
21int inflate_flush(s, z, r)
22struct inflate_blocks_state *s;
23z_stream *z;
24int r;
25{
26 uInt n;
27 Byte *p, *q;
28
29 /* local copies of source and destination pointers */
30 p = z->next_out;
31 q = s->read;
32
33 /* compute number of bytes to copy as far as end of window */
34 n = (q <= s->write ? s->write : s->end) - q;
35 if (n > z->avail_out) n = z->avail_out;
36 if (n && r == Z_BUF_ERROR) r = Z_OK;
37
38 /* update counters */
39 z->avail_out -= n;
40 z->total_out += n;
41
42 /* update check information */
43 s->check = adler32(s->check, q, n);
44
45 /* copy as far as end of window */
46 while (n--) *p++ = *q++;
47
48 /* see if more to copy at beginning of window */
49 if (q == s->end)
50 {
51 /* wrap source pointer */
52 q = s->window;
53
54 /* compute bytes to copy */
55 n = s->write - q;
56 if (n > z->avail_out) n = z->avail_out;
57 if (n && r == Z_BUF_ERROR) r = Z_OK;
58
59 /* update counters */
60 z->avail_out -= n;
61 z->total_out += n;
62
63 /* update check information */
64 s->check = adler32(s->check, q, n);
65
66 /* copy */
67 while (n--) *p++ = *q++;
68 }
69
70 /* update pointers */
71 z->next_out = p;
72 s->read = q;
73
74 /* done */
75 return r;
76}
diff --git a/infutil.h b/infutil.h
new file mode 100644
index 0000000..af07372
--- /dev/null
+++ b/infutil.h
@@ -0,0 +1,86 @@
1/* infutil.h -- types and macros common to blocks and codes
2 * Copyright (C) 1995 Mark Adler
3 * For conditions of distribution and use, see copyright notice in zlib.h
4 */
5
6/* WARNING: this file should *not* be used by applications. It is
7 part of the implementation of the compression library and is
8 subject to change. Applications should only use zlib.h.
9 */
10
11/* inflate blocks semi-private state */
12struct inflate_blocks_state {
13
14 /* mode */
15 enum {
16 TYPE, /* get type bits (3, including end bit) */
17 LENS, /* get lengths for stored */
18 STORED, /* processing stored block */
19 TABLE, /* get table lengths */
20 BTREE, /* get bit lengths tree for a dynamic block */
21 DTREE, /* get length, distance trees for a dynamic block */
22 CODES, /* processing fixed or dynamic block */
23 DRY, /* output remaining window bytes */
24 DONE, /* finished last block, done */
25 ERROR} /* got a data error--stuck here */
26 mode; /* current inflate_block mode */
27
28 /* mode dependent information */
29 union {
30 uInt left; /* if STORED, bytes left to copy */
31 struct {
32 uInt table; /* table lengths (14 bits) */
33 uInt index; /* index into blens (or border) */
34 uInt *blens; /* bit lengths of codes */
35 uInt bb; /* bit length tree depth */
36 inflate_huft *tb; /* bit length decoding tree */
37 } trees; /* if DTREE, decoding info for trees */
38 struct inflate_codes_state
39 *codes; /* if CODES, current state */
40 } sub; /* submode */
41 uInt last; /* true if this block is the last block */
42
43 /* mode independent information */
44 uInt bitk; /* bits in bit buffer */
45 uLong bitb; /* bit buffer */
46 Byte *window; /* sliding window */
47 Byte *end; /* one byte after sliding window */
48 Byte *read; /* window read pointer */
49 Byte *write; /* window write pointer */
50 uLong check; /* check on output */
51
52};
53
54/* defines for inflate input/output */
55/* update pointers and return */
56#define UPDBITS {s->bitb=b;s->bitk=k;}
57#define UPDIN {z->avail_in=n;z->total_in+=p-z->next_in;z->next_in=p;}
58#define UPDOUT {s->write=q;}
59#define UPDATE {UPDBITS UPDIN UPDOUT}
60#define LEAVE {UPDATE return inflate_flush(s,z,r);}
61/* get bytes and bits */
62#define LOADIN {p=z->next_in;n=z->avail_in;b=s->bitb;k=s->bitk;}
63#define NEEDBYTE {if(n)r=Z_OK;else LEAVE}
64#define NEXTBYTE (n--,*p++)
65#define NEEDBITS(j) {while(k<(j)){NEEDBYTE;b|=((uLong)NEXTBYTE)<<k;k+=8;}}
66#define DUMPBITS(j) {b>>=(j);k-=(j);}
67/* output bytes */
68#define WAVAIL (q<s->read?s->read-q-1:s->end-q)
69#define LOADOUT {q=s->write;m=WAVAIL;}
70#define WRAP {if(q==s->end&&s->read!=s->window){q=s->window;m=WAVAIL;}}
71#define FLUSH {UPDOUT r=inflate_flush(s,z,r); LOADOUT}
72#define NEEDOUT {if(m==0){WRAP if(m==0){FLUSH WRAP if(m==0) LEAVE}}r=Z_OK;}
73#define OUTBYTE(a) {*q++=(Byte)(a);m--;}
74/* load local pointers */
75#define LOAD {LOADIN LOADOUT}
76
77/* masks for lower bits */
78extern uInt inflate_mask[];
79
80/* copy as much as possible from the sliding window to the output area */
81extern int inflate_flush __P((
82 struct inflate_blocks_state *,
83 z_stream *,
84 int));
85
86struct internal_state {int dummy;}; /* for buggy compilers */
diff --git a/minigzip.c b/minigzip.c
new file mode 100644
index 0000000..688b3a1
--- /dev/null
+++ b/minigzip.c
@@ -0,0 +1,210 @@
1/* minigzip.c -- simulate gzip using the zlib compression library
2 * Copyright (C) 1995 Jean-loup Gailly.
3 * For conditions of distribution and use, see copyright notice in zlib.h
4 */
5
6/*
7 * minigzip is a minimal implementation of the gzip utility. This is
8 * only an example of using zlib and isn't meant to replace the
9 * full-featured gzip. No attempt is made to deal with file systems
10 * limiting names to 14 or 8+3 characters, etc... Error checking is
11 * very limited. So use minigzip only for testing; use gzip for the
12 * real thing. On MSDOS, use only on file names without extension
13 * or in pipe mode.
14 */
15
16/* $Id: minigzip.c,v 1.1 1995/04/14 13:35:59 jloup Exp $ */
17
18#include <stdio.h>
19#include "zlib.h"
20
21#ifdef MSDOS
22# include <fcntl.h>
23# define SET_BINARY_MODE(file) setmode(fileno(file), O_BINARY)
24#else
25# define SET_BINARY_MODE(file)
26#endif
27
28#define BUFLEN 4096
29#define MAX_NAME_LEN 1024
30
31#define local static
32/* For MSDOS and other systems with limitation on stack size. For Unix,
33 #define local
34 works also.
35 */
36
37char *prog;
38
39/* ===========================================================================
40 * Display error message and exit
41 */
42void error(msg)
43 char *msg;
44{
45 fprintf(stderr, "%s: %s\n", prog, msg);
46 exit(1);
47}
48
49/* ===========================================================================
50 * Compress input to output then close both files.
51 */
52void gz_compress(in, out)
53 FILE *in;
54 gzFile out;
55{
56 local char buf[BUFLEN];
57 int len;
58 int err;
59
60 for (;;) {
61 len = fread(buf, 1, sizeof(buf), in);
62 if (ferror(in)) {
63 perror("fread");
64 exit(1);
65 }
66 if (len == 0) break;
67
68 if (gzwrite(out, buf, len) != len) error(gzerror(out, &err));
69 }
70 fclose(in);
71 if (gzclose(out) != Z_OK) error("failed gzclose");
72}
73
74/* ===========================================================================
75 * Uncompress input to output then close both files.
76 */
77void gz_uncompress(in, out)
78 gzFile in;
79 FILE *out;
80{
81 local char buf[BUFLEN];
82 int len;
83 int err;
84
85 for (;;) {
86 len = gzread(in, buf, sizeof(buf));
87 if (len < 0) error (gzerror(in, &err));
88 if (len == 0) break;
89
90 if (fwrite(buf, 1, len, out) != len) error("failed fwrite");
91 }
92 if (fclose(out)) error("failed fclose");
93
94 if (gzclose(in) != Z_OK) error("failed gzclose");
95}
96
97
98/* ===========================================================================
99 * Compress the given file: create a corresponding .gz file and remove the
100 * original.
101 */
102void file_compress(file)
103 char *file;
104{
105 local char outfile[MAX_NAME_LEN];
106 FILE *in;
107 gzFile out;
108
109 strcpy(outfile, file);
110 strcat(outfile, ".gz");
111
112 in = fopen(file, "rb");
113 if (in == NULL) {
114 perror(file);
115 exit(1);
116 }
117 out = gzopen(outfile, "wb");
118 if (out == NULL) {
119 fprintf(stderr, "%s: can't gzopen %s\n", prog, outfile);
120 exit(1);
121 }
122 gz_compress(in, out);
123
124 unlink(file);
125}
126
127
128/* ===========================================================================
129 * Uncompress the given file and remove the original.
130 */
131void file_uncompress(file)
132 char *file;
133{
134 local char buf[MAX_NAME_LEN];
135 char *infile, *outfile;
136 FILE *out;
137 gzFile in;
138 int len = strlen(file);
139
140 strcpy(buf, file);
141
142 if (len > 3 && strcmp(file+len-3, ".gz") == 0) {
143 infile = file;
144 outfile = buf;
145 outfile[len-3] = '\0';
146 } else {
147 outfile = file;
148 infile = buf;
149 strcat(infile, ".gz");
150 }
151 in = gzopen(infile, "rb");
152 if (in == NULL) {
153 fprintf(stderr, "%s: can't gzopen %s\n", prog, infile);
154 exit(1);
155 }
156 out = fopen(outfile, "wb");
157 if (out == NULL) {
158 perror(file);
159 exit(1);
160 }
161
162 gz_uncompress(in, out);
163
164 unlink(infile);
165}
166
167
168/* ===========================================================================
169 * Usage: minigzip [-d] [files...]
170 */
171
172void main(argc, argv)
173 int argc;
174 char *argv[];
175{
176 int uncompr = 0;
177 gzFile file;
178
179 prog = argv[0];
180 argc--, argv++;
181
182 if (argc > 0) {
183 uncompr = (strcmp(*argv, "-d") == 0);
184 if (uncompr) {
185 argc--, argv++;
186 }
187 }
188 if (argc == 0) {
189 SET_BINARY_MODE(stdin);
190 SET_BINARY_MODE(stdout);
191 if (uncompr) {
192 file = gzdopen(fileno(stdin), "rb");
193 if (file == NULL) error("can't gzdopen stdin");
194 gz_uncompress(file, stdout);
195 } else {
196 file = gzdopen(fileno(stdout), "wb");
197 if (file == NULL) error("can't gzdopen stdout");
198 gz_compress(stdin, file);
199 }
200 } else {
201 do {
202 if (uncompr) {
203 file_uncompress(*argv);
204 } else {
205 file_compress(*argv);
206 }
207 } while (argv++, --argc);
208 }
209 exit(0);
210}
diff --git a/trees.c b/trees.c
new file mode 100644
index 0000000..79cab9f
--- /dev/null
+++ b/trees.c
@@ -0,0 +1,1048 @@
1/* trees.c -- output deflated data using Huffman coding
2 * Copyright (C) 1995 Jean-loup Gailly
3 * For conditions of distribution and use, see copyright notice in zlib.h
4 */
5
6/*
7 * ALGORITHM
8 *
9 * The "deflation" process uses several Huffman trees. The more
10 * common source values are represented by shorter bit sequences.
11 *
12 * Each code tree is stored in a compressed form which is itself
13 * a Huffman encoding of the lengths of all the code strings (in
14 * ascending order by source values). The actual code strings are
15 * reconstructed from the lengths in the inflate process, as described
16 * in the deflate specification.
17 *
18 * REFERENCES
19 *
20 * Deutsch, L.P.,"'Deflate' Compressed Data Format Specification".
21 * Available in ftp.uu.net:/pub/archiving/zip/doc/deflate-1.1.doc
22 *
23 * Storer, James A.
24 * Data Compression: Methods and Theory, pp. 49-50.
25 * Computer Science Press, 1988. ISBN 0-7167-8156-5.
26 *
27 * Sedgewick, R.
28 * Algorithms, p290.
29 * Addison-Wesley, 1983. ISBN 0-201-06672-6.
30 */
31
32/* $Id: trees.c,v 1.2 1995/04/10 16:21:44 jloup Exp $ */
33
34#include "deflate.h"
35
36#ifdef DEBUG
37# include <ctype.h>
38#endif
39
40/* ===========================================================================
41 * Constants
42 */
43
44#define MAX_BL_BITS 7
45/* Bit length codes must not exceed MAX_BL_BITS bits */
46
47#define END_BLOCK 256
48/* end of block literal code */
49
50#define REP_3_6 16
51/* repeat previous bit length 3-6 times (2 bits of repeat count) */
52
53#define REPZ_3_10 17
54/* repeat a zero length 3-10 times (3 bits of repeat count) */
55
56#define REPZ_11_138 18
57/* repeat a zero length 11-138 times (7 bits of repeat count) */
58
59local int extra_lbits[LENGTH_CODES] /* extra bits for each length code */
60 = {0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,0};
61
62local int extra_dbits[D_CODES] /* extra bits for each distance code */
63 = {0,0,0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13};
64
65local int extra_blbits[BL_CODES]/* extra bits for each bit length code */
66 = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,7};
67
68local uch bl_order[BL_CODES]
69 = {16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15};
70/* The lengths of the bit length codes are sent in order of decreasing
71 * probability, to avoid transmitting the lengths for unused bit length codes.
72 */
73
74#define Buf_size (8 * 2*sizeof(char))
75/* Number of bits used within bi_buf. (bi_buf might be implemented on
76 * more than 16 bits on some systems.)
77 */
78
79/* ===========================================================================
80 * Local data. These are initialized only once.
81 * To do: initialize at compile time to be completely reentrant. ???
82 */
83
84local ct_data static_ltree[L_CODES+2];
85/* The static literal tree. Since the bit lengths are imposed, there is no
86 * need for the L_CODES extra codes used during heap construction. However
87 * The codes 286 and 287 are needed to build a canonical tree (see ct_init
88 * below).
89 */
90
91local ct_data static_dtree[D_CODES];
92/* The static distance tree. (Actually a trivial tree since all codes use
93 * 5 bits.)
94 */
95
96local uch dist_code[512];
97/* distance codes. The first 256 values correspond to the distances
98 * 3 .. 258, the last 256 values correspond to the top 8 bits of
99 * the 15 bit distances.
100 */
101
102local uch length_code[MAX_MATCH-MIN_MATCH+1];
103/* length code for each normalized match length (0 == MIN_MATCH) */
104
105local int base_length[LENGTH_CODES];
106/* First normalized length for each code (0 = MIN_MATCH) */
107
108local int base_dist[D_CODES];
109/* First normalized distance for each code (0 = distance of 1) */
110
111struct static_tree_desc_s {
112 ct_data *static_tree; /* static tree or NULL */
113 int *extra_bits; /* extra bits for each code or NULL */
114 int extra_base; /* base index for extra_bits */
115 int elems; /* max number of elements in the tree */
116 int max_length; /* max bit length for the codes */
117};
118
119local static_tree_desc static_l_desc =
120{static_ltree, extra_lbits, LITERALS+1, L_CODES, MAX_BITS};
121
122local static_tree_desc static_d_desc =
123{static_dtree, extra_dbits, 0, D_CODES, MAX_BITS};
124
125local static_tree_desc static_bl_desc =
126{(ct_data *)0, extra_blbits, 0, BL_CODES, MAX_BL_BITS};
127
128/* ===========================================================================
129 * Local (static) routines in this file.
130 */
131
132local void ct_static_init __P((void));
133local void init_block __P((deflate_state *s));
134local void pqdownheap __P((deflate_state *s, ct_data *tree, int k));
135local void gen_bitlen __P((deflate_state *s, tree_desc *desc));
136local void gen_codes __P((ct_data *tree, int max_code, ush bl_count[]));
137local void build_tree __P((deflate_state *s, tree_desc *desc));
138local void scan_tree __P((deflate_state *s, ct_data *tree, int max_code));
139local void send_tree __P((deflate_state *s, ct_data *tree, int max_code));
140local int build_bl_tree __P((deflate_state *s));
141local void send_all_trees __P((deflate_state *s, int lcodes, int dcodes,
142 int blcodes));
143local void compress_block __P((deflate_state *s, ct_data *ltree,
144 ct_data *dtree));
145local void set_data_type __P((deflate_state *s));
146local void send_bits __P((deflate_state *s, int value, int length));
147local unsigned bi_reverse __P((unsigned value, int length));
148local void bi_windup __P((deflate_state *s));
149local void copy_block __P((deflate_state *s, char *buf, unsigned len,
150 int header));
151
152#ifndef DEBUG
153# define send_code(s, c, tree) send_bits(s, tree[c].Code, tree[c].Len)
154 /* Send a code of the given tree. c and tree must not have side effects */
155
156#else /* DEBUG */
157# define send_code(s, c, tree) \
158 { if (verbose>1) fprintf(stderr,"\ncd %3d ",(c)); \
159 send_bits(s, tree[c].Code, tree[c].Len); }
160#endif
161
162#define d_code(dist) \
163 ((dist) < 256 ? dist_code[dist] : dist_code[256+((dist)>>7)])
164/* Mapping from a distance to a distance code. dist is the distance - 1 and
165 * must not have side effects. dist_code[256] and dist_code[257] are never
166 * used.
167 */
168
169#define MAX(a,b) (a >= b ? a : b)
170/* the arguments must not have side effects */
171
172/* ===========================================================================
173 * Initialize the various 'constant' tables.
174 * To do: do this at compile time.
175 */
176local void ct_static_init()
177{
178 int n; /* iterates over tree elements */
179 int bits; /* bit counter */
180 int length; /* length value */
181 int code; /* code value */
182 int dist; /* distance index */
183 ush bl_count[MAX_BITS+1];
184 /* number of codes at each bit length for an optimal tree */
185
186 /* Initialize the mapping length (0..255) -> length code (0..28) */
187 length = 0;
188 for (code = 0; code < LENGTH_CODES-1; code++) {
189 base_length[code] = length;
190 for (n = 0; n < (1<<extra_lbits[code]); n++) {
191 length_code[length++] = (uch)code;
192 }
193 }
194 Assert (length == 256, "ct_static_init: length != 256");
195 /* Note that the length 255 (match length 258) can be represented
196 * in two different ways: code 284 + 5 bits or code 285, so we
197 * overwrite length_code[255] to use the best encoding:
198 */
199 length_code[length-1] = (uch)code;
200
201 /* Initialize the mapping dist (0..32K) -> dist code (0..29) */
202 dist = 0;
203 for (code = 0 ; code < 16; code++) {
204 base_dist[code] = dist;
205 for (n = 0; n < (1<<extra_dbits[code]); n++) {
206 dist_code[dist++] = (uch)code;
207 }
208 }
209 Assert (dist == 256, "ct_static_init: dist != 256");
210 dist >>= 7; /* from now on, all distances are divided by 128 */
211 for ( ; code < D_CODES; code++) {
212 base_dist[code] = dist << 7;
213 for (n = 0; n < (1<<(extra_dbits[code]-7)); n++) {
214 dist_code[256 + dist++] = (uch)code;
215 }
216 }
217 Assert (dist == 256, "ct_static_init: 256+dist != 512");
218
219 /* Construct the codes of the static literal tree */
220 for (bits = 0; bits <= MAX_BITS; bits++) bl_count[bits] = 0;
221 n = 0;
222 while (n <= 143) static_ltree[n++].Len = 8, bl_count[8]++;
223 while (n <= 255) static_ltree[n++].Len = 9, bl_count[9]++;
224 while (n <= 279) static_ltree[n++].Len = 7, bl_count[7]++;
225 while (n <= 287) static_ltree[n++].Len = 8, bl_count[8]++;
226 /* Codes 286 and 287 do not exist, but we must include them in the
227 * tree construction to get a canonical Huffman tree (longest code
228 * all ones)
229 */
230 gen_codes((ct_data *)static_ltree, L_CODES+1, bl_count);
231
232 /* The static distance tree is trivial: */
233 for (n = 0; n < D_CODES; n++) {
234 static_dtree[n].Len = 5;
235 static_dtree[n].Code = bi_reverse(n, 5);
236 }
237}
238
239/* ===========================================================================
240 * Initialize the tree data structures for a new zlib stream.
241 */
242void ct_init(s)
243 deflate_state *s;
244{
245 if (static_dtree[0].Len == 0) {
246 ct_static_init(); /* To do: at compile time */
247 }
248
249 s->compressed_len = 0L;
250
251 s->l_desc.dyn_tree = s->dyn_ltree;
252 s->l_desc.stat_desc = &static_l_desc;
253
254 s->d_desc.dyn_tree = s->dyn_dtree;
255 s->d_desc.stat_desc = &static_d_desc;
256
257 s->bl_desc.dyn_tree = s->bl_tree;
258 s->bl_desc.stat_desc = &static_bl_desc;
259
260 s->bi_buf = 0;
261 s->bi_valid = 0;
262#ifdef DEBUG
263 s->bits_sent = 0L;
264#endif
265
266 /* Initialize the first block of the first file: */
267 init_block(s);
268}
269
270/* ===========================================================================
271 * Initialize a new block.
272 */
273local void init_block(s)
274 deflate_state *s;
275{
276 int n; /* iterates over tree elements */
277
278 /* Initialize the trees. */
279 for (n = 0; n < L_CODES; n++) s->dyn_ltree[n].Freq = 0;
280 for (n = 0; n < D_CODES; n++) s->dyn_dtree[n].Freq = 0;
281 for (n = 0; n < BL_CODES; n++) s->bl_tree[n].Freq = 0;
282
283 s->dyn_ltree[END_BLOCK].Freq = 1;
284 s->opt_len = s->static_len = 0L;
285 s->last_lit = s->matches = 0;
286}
287
288#define SMALLEST 1
289/* Index within the heap array of least frequent node in the Huffman tree */
290
291
292/* ===========================================================================
293 * Remove the smallest element from the heap and recreate the heap with
294 * one less element. Updates heap and heap_len.
295 */
296#define pqremove(s, tree, top) \
297{\
298 top = s->heap[SMALLEST]; \
299 s->heap[SMALLEST] = s->heap[s->heap_len--]; \
300 pqdownheap(s, tree, SMALLEST); \
301}
302
303/* ===========================================================================
304 * Compares to subtrees, using the tree depth as tie breaker when
305 * the subtrees have equal frequency. This minimizes the worst case length.
306 */
307#define smaller(tree, n, m, depth) \
308 (tree[n].Freq < tree[m].Freq || \
309 (tree[n].Freq == tree[m].Freq && depth[n] <= depth[m]))
310
311/* ===========================================================================
312 * Restore the heap property by moving down the tree starting at node k,
313 * exchanging a node with the smallest of its two sons if necessary, stopping
314 * when the heap property is re-established (each father smaller than its
315 * two sons).
316 */
317local void pqdownheap(s, tree, k)
318 deflate_state *s;
319 ct_data *tree; /* the tree to restore */
320 int k; /* node to move down */
321{
322 int v = s->heap[k];
323 int j = k << 1; /* left son of k */
324 while (j <= s->heap_len) {
325 /* Set j to the smallest of the two sons: */
326 if (j < s->heap_len &&
327 smaller(tree, s->heap[j+1], s->heap[j], s->depth)) {
328 j++;
329 }
330 /* Exit if v is smaller than both sons */
331 if (smaller(tree, v, s->heap[j], s->depth)) break;
332
333 /* Exchange v with the smallest son */
334 s->heap[k] = s->heap[j]; k = j;
335
336 /* And continue down the tree, setting j to the left son of k */
337 j <<= 1;
338 }
339 s->heap[k] = v;
340}
341
342/* ===========================================================================
343 * Compute the optimal bit lengths for a tree and update the total bit length
344 * for the current block.
345 * IN assertion: the fields freq and dad are set, heap[heap_max] and
346 * above are the tree nodes sorted by increasing frequency.
347 * OUT assertions: the field len is set to the optimal bit length, the
348 * array bl_count contains the frequencies for each bit length.
349 * The length opt_len is updated; static_len is also updated if stree is
350 * not null.
351 */
352local void gen_bitlen(s, desc)
353 deflate_state *s;
354 tree_desc *desc; /* the tree descriptor */
355{
356 ct_data *tree = desc->dyn_tree;
357 int max_code = desc->max_code;
358 ct_data *stree = desc->stat_desc->static_tree;
359 int *extra = desc->stat_desc->extra_bits;
360 int base = desc->stat_desc->extra_base;
361 int max_length = desc->stat_desc->max_length;
362 int h; /* heap index */
363 int n, m; /* iterate over the tree elements */
364 int bits; /* bit length */
365 int xbits; /* extra bits */
366 ush f; /* frequency */
367 int overflow = 0; /* number of elements with bit length too large */
368
369 for (bits = 0; bits <= MAX_BITS; bits++) s->bl_count[bits] = 0;
370
371 /* In a first pass, compute the optimal bit lengths (which may
372 * overflow in the case of the bit length tree).
373 */
374 tree[s->heap[s->heap_max]].Len = 0; /* root of the heap */
375
376 for (h = s->heap_max+1; h < HEAP_SIZE; h++) {
377 n = s->heap[h];
378 bits = tree[tree[n].Dad].Len + 1;
379 if (bits > max_length) bits = max_length, overflow++;
380 tree[n].Len = (ush)bits;
381 /* We overwrite tree[n].Dad which is no longer needed */
382
383 if (n > max_code) continue; /* not a leaf node */
384
385 s->bl_count[bits]++;
386 xbits = 0;
387 if (n >= base) xbits = extra[n-base];
388 f = tree[n].Freq;
389 s->opt_len += (ulg)f * (bits + xbits);
390 if (stree) s->static_len += (ulg)f * (stree[n].Len + xbits);
391 }
392 if (overflow == 0) return;
393
394 Trace((stderr,"\nbit length overflow\n"));
395 /* This happens for example on obj2 and pic of the Calgary corpus */
396
397 /* Find the first bit length which could increase: */
398 do {
399 bits = max_length-1;
400 while (s->bl_count[bits] == 0) bits--;
401 s->bl_count[bits]--; /* move one leaf down the tree */
402 s->bl_count[bits+1] += 2; /* move one overflow item as its brother */
403 s->bl_count[max_length]--;
404 /* The brother of the overflow item also moves one step up,
405 * but this does not affect bl_count[max_length]
406 */
407 overflow -= 2;
408 } while (overflow > 0);
409
410 /* Now recompute all bit lengths, scanning in increasing frequency.
411 * h is still equal to HEAP_SIZE. (It is simpler to reconstruct all
412 * lengths instead of fixing only the wrong ones. This idea is taken
413 * from 'ar' written by Haruhiko Okumura.)
414 */
415 for (bits = max_length; bits != 0; bits--) {
416 n = s->bl_count[bits];
417 while (n != 0) {
418 m = s->heap[--h];
419 if (m > max_code) continue;
420 if (tree[m].Len != (unsigned) bits) {
421 Trace((stderr,"code %d bits %d->%d\n", m, tree[m].Len, bits));
422 s->opt_len += ((long)bits - (long)tree[m].Len)
423 *(long)tree[m].Freq;
424 tree[m].Len = (ush)bits;
425 }
426 n--;
427 }
428 }
429}
430
431/* ===========================================================================
432 * Generate the codes for a given tree and bit counts (which need not be
433 * optimal).
434 * IN assertion: the array bl_count contains the bit length statistics for
435 * the given tree and the field len is set for all tree elements.
436 * OUT assertion: the field code is set for all tree elements of non
437 * zero code length.
438 */
439local void gen_codes (tree, max_code, bl_count)
440 ct_data *tree; /* the tree to decorate */
441 int max_code; /* largest code with non zero frequency */
442 ush bl_count[]; /* number of codes at each bit length */
443{
444 ush next_code[MAX_BITS+1]; /* next code value for each bit length */
445 ush code = 0; /* running code value */
446 int bits; /* bit index */
447 int n; /* code index */
448
449 /* The distribution counts are first used to generate the code values
450 * without bit reversal.
451 */
452 for (bits = 1; bits <= MAX_BITS; bits++) {
453 next_code[bits] = code = (code + bl_count[bits-1]) << 1;
454 }
455 /* Check that the bit counts in bl_count are consistent. The last code
456 * must be all ones.
457 */
458 Assert (code + bl_count[MAX_BITS]-1 == (1<<MAX_BITS)-1,
459 "inconsistent bit counts");
460 Tracev((stderr,"\ngen_codes: max_code %d ", max_code));
461
462 for (n = 0; n <= max_code; n++) {
463 int len = tree[n].Len;
464 if (len == 0) continue;
465 /* Now reverse the bits */
466 tree[n].Code = bi_reverse(next_code[len]++, len);
467
468 Tracec(tree != static_ltree, (stderr,"\nn %3d %c l %2d c %4x (%x) ",
469 n, (isgraph(n) ? n : ' '), len, tree[n].Code, next_code[len]-1));
470 }
471}
472
473/* ===========================================================================
474 * Construct one Huffman tree and assigns the code bit strings and lengths.
475 * Update the total bit length for the current block.
476 * IN assertion: the field freq is set for all tree elements.
477 * OUT assertions: the fields len and code are set to the optimal bit length
478 * and corresponding code. The length opt_len is updated; static_len is
479 * also updated if stree is not null. The field max_code is set.
480 */
481local void build_tree(s, desc)
482 deflate_state *s;
483 tree_desc *desc; /* the tree descriptor */
484{
485 ct_data *tree = desc->dyn_tree;
486 ct_data *stree = desc->stat_desc->static_tree;
487 int elems = desc->stat_desc->elems;
488 int n, m; /* iterate over heap elements */
489 int max_code = -1; /* largest code with non zero frequency */
490 int node = elems; /* next internal node of the tree */
491 int new; /* new node being created */
492
493 /* Construct the initial heap, with least frequent element in
494 * heap[SMALLEST]. The sons of heap[n] are heap[2*n] and heap[2*n+1].
495 * heap[0] is not used.
496 */
497 s->heap_len = 0, s->heap_max = HEAP_SIZE;
498
499 for (n = 0; n < elems; n++) {
500 if (tree[n].Freq != 0) {
501 s->heap[++(s->heap_len)] = max_code = n;
502 s->depth[n] = 0;
503 } else {
504 tree[n].Len = 0;
505 }
506 }
507
508 /* The pkzip format requires that at least one distance code exists,
509 * and that at least one bit should be sent even if there is only one
510 * possible code. So to avoid special checks later on we force at least
511 * two codes of non zero frequency.
512 */
513 while (s->heap_len < 2) {
514 new = s->heap[++(s->heap_len)] = (max_code < 2 ? ++max_code : 0);
515 tree[new].Freq = 1;
516 s->depth[new] = 0;
517 s->opt_len--; if (stree) s->static_len -= stree[new].Len;
518 /* new is 0 or 1 so it does not have extra bits */
519 }
520 desc->max_code = max_code;
521
522 /* The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree,
523 * establish sub-heaps of increasing lengths:
524 */
525 for (n = s->heap_len/2; n >= 1; n--) pqdownheap(s, tree, n);
526
527 /* Construct the Huffman tree by repeatedly combining the least two
528 * frequent nodes.
529 */
530 do {
531 pqremove(s, tree, n); /* n = node of least frequency */
532 m = s->heap[SMALLEST]; /* m = node of next least frequency */
533
534 s->heap[--(s->heap_max)] = n; /* keep the nodes sorted by frequency */
535 s->heap[--(s->heap_max)] = m;
536
537 /* Create a new node father of n and m */
538 tree[node].Freq = tree[n].Freq + tree[m].Freq;
539 s->depth[node] = (uch) (MAX(s->depth[n], s->depth[m]) + 1);
540 tree[n].Dad = tree[m].Dad = (ush)node;
541#ifdef DUMP_BL_TREE
542 if (tree == s->bl_tree) {
543 fprintf(stderr,"\nnode %d(%d), sons %d(%d) %d(%d)",
544 node, tree[node].Freq, n, tree[n].Freq, m, tree[m].Freq);
545 }
546#endif
547 /* and insert the new node in the heap */
548 s->heap[SMALLEST] = node++;
549 pqdownheap(s, tree, SMALLEST);
550
551 } while (s->heap_len >= 2);
552
553 s->heap[--(s->heap_max)] = s->heap[SMALLEST];
554
555 /* At this point, the fields freq and dad are set. We can now
556 * generate the bit lengths.
557 */
558 gen_bitlen(s, (tree_desc *)desc);
559
560 /* The field len is now set, we can generate the bit codes */
561 gen_codes ((ct_data *)tree, max_code, s->bl_count);
562}
563
564/* ===========================================================================
565 * Scan a literal or distance tree to determine the frequencies of the codes
566 * in the bit length tree.
567 */
568local void scan_tree (s, tree, max_code)
569 deflate_state *s;
570 ct_data *tree; /* the tree to be scanned */
571 int max_code; /* and its largest code of non zero frequency */
572{
573 int n; /* iterates over all tree elements */
574 int prevlen = -1; /* last emitted length */
575 int curlen; /* length of current code */
576 int nextlen = tree[0].Len; /* length of next code */
577 int count = 0; /* repeat count of the current code */
578 int max_count = 7; /* max repeat count */
579 int min_count = 4; /* min repeat count */
580
581 if (nextlen == 0) max_count = 138, min_count = 3;
582 tree[max_code+1].Len = (ush)0xffff; /* guard */
583
584 for (n = 0; n <= max_code; n++) {
585 curlen = nextlen; nextlen = tree[n+1].Len;
586 if (++count < max_count && curlen == nextlen) {
587 continue;
588 } else if (count < min_count) {
589 s->bl_tree[curlen].Freq += count;
590 } else if (curlen != 0) {
591 if (curlen != prevlen) s->bl_tree[curlen].Freq++;
592 s->bl_tree[REP_3_6].Freq++;
593 } else if (count <= 10) {
594 s->bl_tree[REPZ_3_10].Freq++;
595 } else {
596 s->bl_tree[REPZ_11_138].Freq++;
597 }
598 count = 0; prevlen = curlen;
599 if (nextlen == 0) {
600 max_count = 138, min_count = 3;
601 } else if (curlen == nextlen) {
602 max_count = 6, min_count = 3;
603 } else {
604 max_count = 7, min_count = 4;
605 }
606 }
607}
608
609/* ===========================================================================
610 * Send a literal or distance tree in compressed form, using the codes in
611 * bl_tree.
612 */
613local void send_tree (s, tree, max_code)
614 deflate_state *s;
615 ct_data *tree; /* the tree to be scanned */
616 int max_code; /* and its largest code of non zero frequency */
617{
618 int n; /* iterates over all tree elements */
619 int prevlen = -1; /* last emitted length */
620 int curlen; /* length of current code */
621 int nextlen = tree[0].Len; /* length of next code */
622 int count = 0; /* repeat count of the current code */
623 int max_count = 7; /* max repeat count */
624 int min_count = 4; /* min repeat count */
625
626 /* tree[max_code+1].Len = -1; */ /* guard already set */
627 if (nextlen == 0) max_count = 138, min_count = 3;
628
629 for (n = 0; n <= max_code; n++) {
630 curlen = nextlen; nextlen = tree[n+1].Len;
631 if (++count < max_count && curlen == nextlen) {
632 continue;
633 } else if (count < min_count) {
634 do { send_code(s, curlen, s->bl_tree); } while (--count != 0);
635
636 } else if (curlen != 0) {
637 if (curlen != prevlen) {
638 send_code(s, curlen, s->bl_tree); count--;
639 }
640 Assert(count >= 3 && count <= 6, " 3_6?");
641 send_code(s, REP_3_6, s->bl_tree); send_bits(s, count-3, 2);
642
643 } else if (count <= 10) {
644 send_code(s, REPZ_3_10, s->bl_tree); send_bits(s, count-3, 3);
645
646 } else {
647 send_code(s, REPZ_11_138, s->bl_tree); send_bits(s, count-11, 7);
648 }
649 count = 0; prevlen = curlen;
650 if (nextlen == 0) {
651 max_count = 138, min_count = 3;
652 } else if (curlen == nextlen) {
653 max_count = 6, min_count = 3;
654 } else {
655 max_count = 7, min_count = 4;
656 }
657 }
658}
659
660/* ===========================================================================
661 * Construct the Huffman tree for the bit lengths and return the index in
662 * bl_order of the last bit length code to send.
663 */
664local int build_bl_tree(s)
665 deflate_state *s;
666{
667 int max_blindex; /* index of last bit length code of non zero freq */
668
669 /* Determine the bit length frequencies for literal and distance trees */
670 scan_tree(s, (ct_data *)s->dyn_ltree, s->l_desc.max_code);
671 scan_tree(s, (ct_data *)s->dyn_dtree, s->d_desc.max_code);
672
673 /* Build the bit length tree: */
674 build_tree(s, (tree_desc *)(&(s->bl_desc)));
675 /* opt_len now includes the length of the tree representations, except
676 * the lengths of the bit lengths codes and the 5+5+4 bits for the counts.
677 */
678
679 /* Determine the number of bit length codes to send. The pkzip format
680 * requires that at least 4 bit length codes be sent. (appnote.txt says
681 * 3 but the actual value used is 4.)
682 */
683 for (max_blindex = BL_CODES-1; max_blindex >= 3; max_blindex--) {
684 if (s->bl_tree[bl_order[max_blindex]].Len != 0) break;
685 }
686 /* Update opt_len to include the bit length tree and counts */
687 s->opt_len += 3*(max_blindex+1) + 5+5+4;
688 Tracev((stderr, "\ndyn trees: dyn %ld, stat %ld",
689 s->opt_len, s->static_len));
690
691 return max_blindex;
692}
693
694/* ===========================================================================
695 * Send the header for a block using dynamic Huffman trees: the counts, the
696 * lengths of the bit length codes, the literal tree and the distance tree.
697 * IN assertion: lcodes >= 257, dcodes >= 1, blcodes >= 4.
698 */
699local void send_all_trees(s, lcodes, dcodes, blcodes)
700 deflate_state *s;
701 int lcodes, dcodes, blcodes; /* number of codes for each tree */
702{
703 int rank; /* index in bl_order */
704
705 Assert (lcodes >= 257 && dcodes >= 1 && blcodes >= 4, "not enough codes");
706 Assert (lcodes <= L_CODES && dcodes <= D_CODES && blcodes <= BL_CODES,
707 "too many codes");
708 Tracev((stderr, "\nbl counts: "));
709 send_bits(s, lcodes-257, 5); /* not +255 as stated in appnote.txt */
710 send_bits(s, dcodes-1, 5);
711 send_bits(s, blcodes-4, 4); /* not -3 as stated in appnote.txt */
712 for (rank = 0; rank < blcodes; rank++) {
713 Tracev((stderr, "\nbl code %2d ", bl_order[rank]));
714 send_bits(s, s->bl_tree[bl_order[rank]].Len, 3);
715 }
716 Tracev((stderr, "\nbl tree: sent %ld", s->bits_sent));
717
718 send_tree(s, (ct_data *)s->dyn_ltree, lcodes-1); /* literal tree */
719 Tracev((stderr, "\nlit tree: sent %ld", s->bits_sent));
720
721 send_tree(s, (ct_data *)s->dyn_dtree, dcodes-1); /* distance tree */
722 Tracev((stderr, "\ndist tree: sent %ld", s->bits_sent));
723}
724
725/* ===========================================================================
726 * Determine the best encoding for the current block: dynamic trees, static
727 * trees or store, and output the encoded block to the zip file. This function
728 * returns the total compressed length for the file so far.
729 */
730ulg ct_flush_block(s, buf, stored_len, eof)
731 deflate_state *s;
732 char *buf; /* input block, or NULL if too old */
733 ulg stored_len; /* length of input block */
734 int eof; /* true if this is the last block for a file */
735{
736 ulg opt_lenb, static_lenb; /* opt_len and static_len in bytes */
737 int max_blindex; /* index of last bit length code of non zero freq */
738
739 /* Check if the file is ascii or binary */
740 if (s->data_type == UNKNOWN) set_data_type(s);
741
742 /* Construct the literal and distance trees */
743 build_tree(s, (tree_desc *)(&(s->l_desc)));
744 Tracev((stderr, "\nlit data: dyn %ld, stat %ld", s->opt_len,
745 s->static_len));
746
747 build_tree(s, (tree_desc *)(&(s->d_desc)));
748 Tracev((stderr, "\ndist data: dyn %ld, stat %ld", s->opt_len,
749 s->static_len));
750 /* At this point, opt_len and static_len are the total bit lengths of
751 * the compressed block data, excluding the tree representations.
752 */
753
754 /* Build the bit length tree for the above two trees, and get the index
755 * in bl_order of the last bit length code to send.
756 */
757 max_blindex = build_bl_tree(s);
758
759 /* Determine the best encoding. Compute first the block length in bytes */
760 opt_lenb = (s->opt_len+3+7)>>3;
761 static_lenb = (s->static_len+3+7)>>3;
762
763 Tracev((stderr, "\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u ",
764 opt_lenb, s->opt_len, static_lenb, s->static_len, stored_len,
765 s->last_lit));
766
767 if (static_lenb <= opt_lenb) opt_lenb = static_lenb;
768
769 /* If compression failed and this is the first and last block,
770 * and if the .zip file can be seeked (to rewrite the local header),
771 * the whole file is transformed into a stored file:
772 */
773#ifdef STORED_FILE_OK
774# ifdef FORCE_METHOD
775 if (level == 1 && eof && compressed_len == 0L) { /* force stored file */
776# else
777 if (stored_len <= opt_lenb && eof && s->compressed_len==0L && seekable()) {
778# endif
779 /* Since LIT_BUFSIZE <= 2*WSIZE, the input data must be there: */
780 if (buf == (char*)0) error ("block vanished");
781
782 copy_block(buf, (unsigned)stored_len, 0); /* without header */
783 s->compressed_len = stored_len << 3;
784 s->method = STORED;
785 } else
786#endif /* STORED_FILE_OK */
787
788#ifdef FORCE_METHOD
789 if (level == 2 && buf != (char*)0) { /* force stored block */
790#else
791 if (stored_len+4 <= opt_lenb && buf != (char*)0) {
792 /* 4: two words for the lengths */
793#endif
794 /* The test buf != NULL is only necessary if LIT_BUFSIZE > WSIZE.
795 * Otherwise we can't have processed more than WSIZE input bytes since
796 * the last block flush, because compression would have been
797 * successful. If LIT_BUFSIZE <= WSIZE, it is never too late to
798 * transform a block into a stored block.
799 */
800 send_bits(s, (STORED_BLOCK<<1)+eof, 3); /* send block type */
801 s->compressed_len = (s->compressed_len + 3 + 7) & ~7L;
802 s->compressed_len += (stored_len + 4) << 3;
803
804 copy_block(s, buf, (unsigned)stored_len, 1); /* with header */
805
806#ifdef FORCE_METHOD
807 } else if (level == 3) { /* force static trees */
808#else
809 } else if (static_lenb == opt_lenb) {
810#endif
811 send_bits(s, (STATIC_TREES<<1)+eof, 3);
812 compress_block(s, (ct_data *)static_ltree, (ct_data *)static_dtree);
813 s->compressed_len += 3 + s->static_len;
814 } else {
815 send_bits(s, (DYN_TREES<<1)+eof, 3);
816 send_all_trees(s, s->l_desc.max_code+1, s->d_desc.max_code+1,
817 max_blindex+1);
818 compress_block(s, (ct_data *)s->dyn_ltree, (ct_data *)s->dyn_dtree);
819 s->compressed_len += 3 + s->opt_len;
820 }
821 Assert (s->compressed_len == s->bits_sent, "bad compressed size");
822 init_block(s);
823
824 if (eof) {
825 bi_windup(s);
826 s->compressed_len += 7; /* align on byte boundary */
827 }
828 Tracev((stderr,"\ncomprlen %lu(%lu) ", s->compressed_len>>3,
829 s->compressed_len-7*eof));
830
831 return s->compressed_len >> 3;
832}
833
834/* ===========================================================================
835 * Save the match info and tally the frequency counts. Return true if
836 * the current block must be flushed.
837 */
838int ct_tally (s, dist, lc)
839 deflate_state *s;
840 int dist; /* distance of matched string */
841 int lc; /* match length-MIN_MATCH or unmatched char (if dist==0) */
842{
843 s->d_buf[s->last_lit] = (ush)dist;
844 s->l_buf[s->last_lit++] = (uch)lc;
845 if (dist == 0) {
846 /* lc is the unmatched char */
847 s->dyn_ltree[lc].Freq++;
848 } else {
849 s->matches++;
850 /* Here, lc is the match length - MIN_MATCH */
851 dist--; /* dist = match distance - 1 */
852 Assert((ush)dist < (ush)MAX_DIST(s) &&
853 (ush)lc <= (ush)(MAX_MATCH-MIN_MATCH) &&
854 (ush)d_code(dist) < (ush)D_CODES, "ct_tally: bad match");
855
856 s->dyn_ltree[length_code[lc]+LITERALS+1].Freq++;
857 s->dyn_dtree[d_code(dist)].Freq++;
858 }
859
860 /* Try to guess if it is profitable to stop the current block here */
861 if (s->level > 2 && (s->last_lit & 0xfff) == 0) {
862 /* Compute an upper bound for the compressed length */
863 ulg out_length = (ulg)s->last_lit*8L;
864 ulg in_length = (ulg)s->strstart - s->block_start;
865 int dcode;
866 for (dcode = 0; dcode < D_CODES; dcode++) {
867 out_length += (ulg)s->dyn_dtree[dcode].Freq *
868 (5L+extra_dbits[dcode]);
869 }
870 out_length >>= 3;
871 Tracev((stderr,"\nlast_lit %u, in %ld, out ~%ld(%ld%%) ",
872 s->last_lit, in_length, out_length,
873 100L - out_length*100L/in_length));
874 if (s->matches < s->last_lit/2 && out_length < in_length/2) return 1;
875 }
876 return (s->last_lit == s->lit_bufsize-1);
877 /* We avoid equality with lit_bufsize because of wraparound at 64K
878 * on 16 bit machines and because stored blocks are restricted to
879 * 64K-1 bytes.
880 */
881}
882
883/* ===========================================================================
884 * Send the block data compressed using the given Huffman trees
885 */
886local void compress_block(s, ltree, dtree)
887 deflate_state *s;
888 ct_data *ltree; /* literal tree */
889 ct_data *dtree; /* distance tree */
890{
891 unsigned dist; /* distance of matched string */
892 int lc; /* match length or unmatched char (if dist == 0) */
893 unsigned lx = 0; /* running index in l_buf */
894 unsigned code; /* the code to send */
895 int extra; /* number of extra bits to send */
896
897 if (s->last_lit != 0) do {
898 dist = s->d_buf[lx];
899 lc = s->l_buf[lx++];
900 if (dist == 0) {
901 send_code(s, lc, ltree); /* send a literal byte */
902 Tracecv(isgraph(lc), (stderr," '%c' ", lc));
903 } else {
904 /* Here, lc is the match length - MIN_MATCH */
905 code = length_code[lc];
906 send_code(s, code+LITERALS+1, ltree); /* send the length code */
907 extra = extra_lbits[code];
908 if (extra != 0) {
909 lc -= base_length[code];
910 send_bits(s, lc, extra); /* send the extra length bits */
911 }
912 dist--; /* dist is now the match distance - 1 */
913 code = d_code(dist);
914 Assert (code < D_CODES, "bad d_code");
915
916 send_code(s, code, dtree); /* send the distance code */
917 extra = extra_dbits[code];
918 if (extra != 0) {
919 dist -= base_dist[code];
920 send_bits(s, dist, extra); /* send the extra distance bits */
921 }
922 } /* literal or match pair ? */
923
924 /* Check that the overlay between pending_buf and d_buf+l_buf is ok: */
925 Assert(s->pending < s->lit_bufsize + 2*lx, "pendingBuf overflow");
926
927 } while (lx < s->last_lit);
928
929 send_code(s, END_BLOCK, ltree);
930}
931
932/* ===========================================================================
933 * Set the data type to ASCII or BINARY, using a crude approximation:
934 * binary if more than 20% of the bytes are <= 6 or >= 128, ascii otherwise.
935 * IN assertion: the fields freq of dyn_ltree are set and the total of all
936 * frequencies does not exceed 64K (to fit in an int on 16 bit machines).
937 */
938local void set_data_type(s)
939 deflate_state *s;
940{
941 int n = 0;
942 unsigned ascii_freq = 0;
943 unsigned bin_freq = 0;
944 while (n < 7) bin_freq += s->dyn_ltree[n++].Freq;
945 while (n < 128) ascii_freq += s->dyn_ltree[n++].Freq;
946 while (n < LITERALS) bin_freq += s->dyn_ltree[n++].Freq;
947 s->data_type = bin_freq > (ascii_freq >> 2) ? BINARY : ASCII;
948}
949
950/* ===========================================================================
951 * Output a short LSB first on the stream.
952 * IN assertion: there is enough room in pendingBuf.
953 */
954#define put_short(s, w) { \
955 put_byte(s, (uch)((w) & 0xff)); \
956 put_byte(s, (uch)((ush)(w) >> 8)); \
957}
958
959/* ===========================================================================
960 * Send a value on a given number of bits.
961 * IN assertion: length <= 16 and value fits in length bits.
962 */
963local void send_bits(s, value, length)
964 deflate_state *s;
965 int value; /* value to send */
966 int length; /* number of bits */
967{
968#ifdef DEBUG
969 Tracev((stderr," l %2d v %4x ", length, value));
970 Assert(length > 0 && length <= 15, "invalid length");
971 s->bits_sent += (ulg)length;
972#endif
973 /* If not enough room in bi_buf, use (valid) bits from bi_buf and
974 * (16 - bi_valid) bits from value, leaving (width - (16-bi_valid))
975 * unused bits in value.
976 */
977 if (s->bi_valid > (int)Buf_size - length) {
978 s->bi_buf |= (value << s->bi_valid);
979 put_short(s, s->bi_buf);
980 s->bi_buf = (ush)value >> (Buf_size - s->bi_valid);
981 s->bi_valid += length - Buf_size;
982 } else {
983 s->bi_buf |= value << s->bi_valid;
984 s->bi_valid += length;
985 }
986}
987
988/* ===========================================================================
989 * Reverse the first len bits of a code, using straightforward code (a faster
990 * method would use a table)
991 * IN assertion: 1 <= len <= 15
992 */
993local unsigned bi_reverse(code, len)
994 unsigned code; /* the value to invert */
995 int len; /* its bit length */
996{
997 register unsigned res = 0;
998 do {
999 res |= code & 1;
1000 code >>= 1, res <<= 1;
1001 } while (--len > 0);
1002 return res >> 1;
1003}
1004
1005/* ===========================================================================
1006 * Write out any remaining bits in an incomplete byte.
1007 */
1008local void bi_windup(s)
1009 deflate_state *s;
1010{
1011 if (s->bi_valid > 8) {
1012 put_short(s, s->bi_buf);
1013 } else if (s->bi_valid > 0) {
1014 put_byte(s, s->bi_buf);
1015 }
1016 s->bi_buf = 0;
1017 s->bi_valid = 0;
1018#ifdef DEBUG
1019 s->bits_sent = (s->bits_sent+7) & ~7;
1020#endif
1021}
1022
1023/* ===========================================================================
1024 * Copy a stored block, storing first the length and its
1025 * one's complement if requested.
1026 */
1027local void copy_block(s, buf, len, header)
1028 deflate_state *s;
1029 char *buf; /* the input data */
1030 unsigned len; /* its length */
1031 int header; /* true if block header must be written */
1032{
1033 bi_windup(s); /* align on byte boundary */
1034
1035 if (header) {
1036 put_short(s, (ush)len);
1037 put_short(s, (ush)~len);
1038#ifdef DEBUG
1039 s->bits_sent += 2*16;
1040#endif
1041 }
1042#ifdef DEBUG
1043 s->bits_sent += (ulg)len<<3;
1044#endif
1045 while (len--) {
1046 put_byte(s, *buf++);
1047 }
1048}
diff --git a/uncompr.c b/uncompr.c
new file mode 100644
index 0000000..4c8b3af
--- /dev/null
+++ b/uncompr.c
@@ -0,0 +1,58 @@
1/* uncompr.c -- decompress a memory buffer
2 * Copyright (C) 1995 Jean-loup Gailly.
3 * For conditions of distribution and use, see copyright notice in zlib.h
4 */
5
6/* $Id: uncompr.c,v 1.4 1995/04/10 16:22:22 jloup Exp $ */
7
8#include "zlib.h"
9
10/* ===========================================================================
11 Decompresses the source buffer into the destination buffer. sourceLen is
12 the byte length of the source buffer. Upon entry, destLen is the total
13 size of the destination buffer, which must be large enough to hold the
14 entire uncompressed data. (The size of the uncompressed data must have
15 been saved previously by the compressor and transmitted to the decompressor
16 by some mechanism outside the scope of this compression library.)
17 Upon exit, destLen is the actual size of the compressed buffer.
18 This function can be used to decompress a whole file at once if the
19 input file is mmap'ed.
20
21 uncompress returns Z_OK if success, Z_MEM_ERROR if there was not
22 enough memory, Z_BUF_ERROR if there was not enough room in the output
23 buffer, or Z_DATA_ERROR if the input data was corrupted.
24*/
25int uncompress (dest, destLen, source, sourceLen)
26 Byte *dest;
27 uLong *destLen;
28 Byte *source;
29 uLong sourceLen;
30{
31 z_stream stream;
32 int err;
33
34 stream.next_in = source;
35 stream.avail_in = (uInt)sourceLen;
36 /* Check for source > 64K on 16-bit machine: */
37 if ((uLong)stream.avail_in != sourceLen) return Z_BUF_ERROR;
38
39 stream.next_out = dest;
40 stream.avail_out = (uInt)*destLen;
41 if ((uLong)stream.avail_out != *destLen) return Z_BUF_ERROR;
42
43 stream.zalloc = (alloc_func)0;
44 stream.zfree = (free_func)0;
45
46 err = inflateInit(&stream);
47 if (err != Z_OK) return err;
48
49 err = inflate(&stream, Z_FINISH);
50 if (err != Z_STREAM_END) {
51 inflateEnd(&stream);
52 return err;
53 }
54 *destLen = stream.total_out;
55
56 err = inflateEnd(&stream);
57 return err;
58}
diff --git a/zconf.h b/zconf.h
new file mode 100644
index 0000000..29496d7
--- /dev/null
+++ b/zconf.h
@@ -0,0 +1,66 @@
1/* zconf.h -- configuration of the zlib compression library
2 * Copyright (C) 1995 Jean-loup Gailly.
3 * For conditions of distribution and use, see copyright notice in zlib.h
4 */
5
6/* $Id: zconf.h,v 1.7 1995/04/12 20:42:28 jloup Exp $ */
7
8#ifndef _ZCONF_H
9#define _ZCONF_H
10
11/*
12 The library does not install any signal handler. It is recommended to
13 add at least a handler for SIGSEGV when decompressing; the library checks
14 the consistency of the input data whenever possible but may go nuts
15 for some forms of corrupted input.
16 */
17
18/*
19 * Compile with -DMAXSEG_64K if the alloc function cannot allocate more
20 * than 64k bytes at a time (needed on systems with 16-bit int).
21 */
22#if defined(_GNUC__) && !defined(__32BIT__)
23# define __32BIT__
24#endif
25#if defined(__MSDOS__) && !defined(MSDOS)
26# define MSDOS
27#endif
28#if defined(MSDOS) && !defined(__32BIT__)
29# define MAXSEG_64K
30#endif
31
32#ifdef MAXSEG_64K
33# define MAX_MEM_LEVEL 8
34#else
35# define MAX_MEM_LEVEL 9
36#endif
37
38 /* Type declarations */
39
40#ifndef __P /* function prototypes */
41# if defined(__STDC__) || defined(MSDOS)
42# define __P(args) args
43# else
44# define __P(args) ()
45# endif
46#endif
47
48#ifndef Byte
49 typedef unsigned char Byte; /* 8 bits */
50#endif
51#ifndef uInt
52 typedef unsigned int uInt; /* may be 16 or 32 bits */
53#endif
54#ifndef uLong
55 typedef unsigned long uLong; /* 32 bits or more */
56#endif
57#ifndef voidp
58# if defined(__STDC__) || defined(MSDOS)
59 typedef void *voidp;
60# else
61 typedef Byte *voidp;
62# endif
63#endif
64
65#endif /* _ZCONF_H */
66
diff --git a/zlib.h b/zlib.h
new file mode 100644
index 0000000..d1f2ca9
--- /dev/null
+++ b/zlib.h
@@ -0,0 +1,604 @@
1/* zlib.h -- interface of the 'zlib' general purpose compression library
2 version 0.7 April 14th, 1995.
3
4 Copyright (C) 1995 Jean-loup Gailly and Mark Adler
5
6 This software is provided 'as-is', without any express or implied
7 warranty. In no event will the authors be held liable for any damages
8 arising from the use of this software.
9
10 Permission is granted to anyone to use this software for any purpose,
11 including commercial applications, and to alter it and redistribute it
12 freely, subject to the following restrictions:
13
14 1. The origin of this software must not be misrepresented; you must not
15 claim that you wrote the original software. If you use this software
16 in a product, an acknowledgment in the product documentation would be
17 appreciated but is not required.
18 2. Altered source versions must be plainly marked as such, and must not be
19 misrepresented as being the original software.
20 3. This notice may not be removed or altered from any source distribution.
21
22 Jean-loup Gailly Mark Adler
23 gzip@prep.ai.mit.edu madler@cco.caltech.edu
24 */
25
26#ifndef _ZLIB_H
27#define _ZLIB_H
28
29#include "zconf.h"
30
31#define ZLIB_VERSION "0.7"
32
33/*
34 The 'zlib' compression library provides in-memory compression and
35 decompression functions, including integrity checks of the uncompressed
36 data. This version of the library supports only one compression method
37 (deflation) but other algorithms may be added later and will have the same
38 stream interface.
39
40 For compression the application must provide the output buffer and
41 may optionally provide the input buffer for optimization. For decompression,
42 the application must provide the input buffer and may optionally provide
43 the output buffer for optimization.
44
45 Compression can be done in a single step if the buffers are large
46 enough (for example if an input file is mmap'ed), or can be done by
47 repeated calls of the compression function. In the latter case, the
48 application must provide more input and/or consume the output
49 (providing more output space) before each call.
50*/
51
52typedef voidp (*alloc_func) __P((voidp opaque, uInt items, uInt size));
53typedef void (*free_func) __P((voidp opaque, voidp address));
54
55struct internal_state;
56
57typedef struct z_stream_s {
58 Byte *next_in; /* next input byte */
59 uInt avail_in; /* number of bytes available at next_in */
60 uLong total_in; /* total nb of input bytes read so far */
61
62 Byte *next_out; /* next output byte should be put there */
63 uInt avail_out; /* remaining free space at next_out */
64 uLong total_out; /* total nb of bytes output so far */
65
66 char *msg; /* last error message, NULL if no error */
67 struct internal_state *state; /* not visible by applications */
68
69 alloc_func zalloc; /* used to allocate the internal state */
70 free_func zfree; /* used to free the internal state */
71 voidp opaque; /* private data object passed to zalloc and zfree */
72
73 Byte data_type; /* best guess about the data type: ascii or binary */
74
75} z_stream;
76
77/*
78 The application must update next_in and avail_in when avail_in has
79 dropped to zero. It must update next_out and avail_out when avail_out
80 has dropped to zero. The application must initialize zalloc, zfree and
81 opaque before calling the init function. All other fields are set by the
82 compression library and must not be updated by the application.
83
84 The opaque value provided by the application will be passed as first
85 parameter for calls of zalloc and zfree. This can be useful for custom
86 memory management. The compression library attaches no meaning to the
87 opaque value.
88
89 zalloc must return Z_NULL if there is not enough memory for the object.
90 On 16-bit systems, the functions zalloc and zfree must be able to allocate
91 exactly 65536 bytes, but will not be require to allocate more than this
92 if the symbol MAXSEG_64K is defined (see zconf.h).
93
94 The fields total_in and total_out can be used for statistics or
95 progress reports. After compression, total_in holds the total size of
96 the uncompressed data and may be saved for use in the decompressor
97 (particularly if the decompressor wants to decompress everything in
98 a single step).
99*/
100
101 /* constants */
102
103#define Z_NO_FLUSH 0
104#define Z_PARTIAL_FLUSH 1
105#define Z_FULL_FLUSH 2
106#define Z_FINISH 4
107/* See deflate() below for the usage of these constants */
108
109#define Z_OK 0
110#define Z_STREAM_END 1
111#define Z_ERRNO (-1)
112#define Z_STREAM_ERROR (-2)
113#define Z_DATA_ERROR (-3)
114#define Z_MEM_ERROR (-4)
115#define Z_BUF_ERROR (-5)
116/* error codes for the compression/decompression functions */
117
118#define Z_BEST_SPEED 1
119#define Z_BEST_COMPRESSION 9
120#define Z_DEFAULT_COMPRESSION (-1)
121/* compression levels */
122
123#define Z_FILTERED 1
124#define Z_HUFFMAN_ONLY 2
125#define Z_DEFAULT_STRATEGY 0
126
127#define Z_BINARY 0
128#define Z_ASCII 1
129#define Z_UNKNOWN 2
130/* Used to set the data_type field */
131
132#define Z_NULL 0 /* for initializing zalloc, zfree, opaque */
133
134extern char *zlib_version;
135/* The application can compare zlib_version and ZLIB_VERSION for consistency.
136 If the first character differs, the library code actually used is
137 not compatible with the zlib.h header file used by the application.
138 */
139
140 /* basic functions */
141
142extern int deflateInit __P((z_stream *strm, int level));
143/*
144 Initializes the internal stream state for compression. The fields
145 zalloc, zfree and opaque must be initialized before by the caller.
146 If zalloc and zfree are set to Z_NULL, deflateInit updates them to
147 use default allocation functions.
148
149 The compression level must be Z_DEFAULT_COMPRESSION, or between 1 and 9:
150 1 gives best speed, 9 gives best compression. Z_DEFAULT_COMPRESSION requests
151 a default compromise between speed and compression (currently equivalent
152 to level 6).
153
154 deflateInit returns Z_OK if success, Z_MEM_ERROR if there was not
155 enough memory, Z_STREAM_ERROR if the stream state was inconsistent (such
156 as zalloc being NULL). msg is set to null if there is no error message.
157 deflateInit does not perform any compression: this will be done by
158 deflate(). */
159
160
161extern int deflate __P((z_stream *strm, int flush));
162/*
163 Performs one or both of the following actions:
164
165 - Compress more input starting at next_in and update next_in and avail_in
166 accordingly. If not all input can be processed (because there is not
167 enough room in the output buffer), next_in is updated and processing
168 will resume at this point for the next call of deflate().
169
170 - Provide more output starting at next_out and update next_out and avail_out
171 accordingly. This action is forced if the parameter flush is non zero.
172 Forcing flush frequently degrades the compression ratio, so this parameter
173 should be set only when necessary (in interactive applications).
174 Some output may be provided even if flush is not set.
175
176 Before the call of deflate(), the application should ensure that at least
177 one of the actions is possible, by providing more input and/or consuming
178 more output, and updating avail_in or avail_out accordingly.
179 The application can consume the compressed output when the output
180 buffer is full (avail_out == 0), or after each call of deflate().
181
182 If the parameter flush is set to Z_PARTIAL_FLUSH, the current compression
183 block is byte aligned and flushed to the output buffer so that the
184 decompressor can get all input data available so far; if the compression
185 method is 8 (deflate without partial flush capability), the current block
186 is terminated. If flush is set to Z_FULL_FLUSH, the compression block is
187 terminated, a special marker is output and the compression dictionary is
188 discarded; this is useful to allow the decompressor to synchronize if one
189 compressed block has been damaged.
190 Flushing degrades compression and so should be used only when necessary.
191 Using Z_FULL_FLUSH too often can seriously degrade the compression.
192
193 If the parameter flush is set to Z_FINISH, all pending input is
194 processed and all pending output is flushed. The next operation on this
195 stream must be another call of deflate with Z_FINISH but no more input data
196 (unchanged avail_in) if this call returned with avail_out equal to zero,
197 or a call of deflateEnd to deallocate the compression state. Z_FINISH can
198 be used immediately after deflateInit if all the compression is to be
199 done in a single step. In this case, avail_out must be at least 0.1%
200 larger than avail_in plus 8 bytes.
201
202 deflate() may update strm->data_type if it can make a good guess about
203 the input data type (Z_ASCII or Z_BINARY). In doubt, the data is considered
204 binary. This field is only for information purposes and does not affect
205 the compression algorithm in any manner.
206
207 deflate() return Z_OK if some progress has been made (more input processed
208 or more output produced), Z_STREAM_ERROR if the stream state was
209 inconsistent (for example if next_in or next_out was NULL), Z_BUF_ERROR if
210 no progress is possible or if there was not enough room in the output buffer
211 when Z_FINISH is used.
212*/
213
214
215extern int deflateEnd __P((z_stream *strm));
216/*
217 All dynamically allocated data structures for this stream are freed.
218 This function discards any unprocessed input and does not flush any
219 pending output.
220
221 deflateEnd returns Z_OK if success, Z_STREAM_ERROR if the
222 stream state was inconsistent. In the error case, msg may be set
223 but then points to a static string (which must not be deallocated).
224*/
225
226
227extern int inflateInit __P((z_stream *strm));
228/*
229 Initializes the internal stream state for decompression. The fields
230 zalloc and zfree must be initialized before by the caller. If zalloc and
231 zfree are set to Z_NULL, deflateInit updates them to use default allocation
232 functions.
233
234 inflateInit returns Z_OK if success, Z_MEM_ERROR if there was not
235 enough memory, Z_STREAM_ERROR if the stream state was inconsistent (such
236 as zalloc being NULL). msg is set to null if there is no error message.
237 inflateInit does not perform any decompression: this will be done by
238 inflate().
239*/
240
241
242extern int inflate __P((z_stream *strm, int flush));
243/*
244 Performs one or both of the following actions:
245
246 - Decompress more input starting at next_in and update next_in and avail_in
247 accordingly. If not all input can be processed (because there is not
248 enough room in the output buffer), next_in is updated and processing
249 will resume at this point for the next call of inflate().
250
251 - Provide more output starting at next_out and update next_out and avail_out
252 accordingly. inflate() always provides as much output as possible
253 (until no more input data or no more space in the output buffer).
254
255 Before the call of inflate(), the application should ensure that at least
256 one of the actions is possible, by providing more input and/or consuming
257 more output, and updating the next_* and avail_* values accordingly.
258 The application can consume the uncompressed output when the output
259 buffer is full (avail_out == 0), or after each call of inflate().
260
261 If the parameter flush is set to Z_PARTIAL_FLUSH, inflate flushes as much
262 output as possible to the output buffer. The flushing behavior of inflate is
263 not specified for values of the flush paramater other than Z_PARTIAL_FLUSH
264 and Z_FINISH, but the current implementation actually flushes as much output
265 as possible anyway.
266
267 inflate() should normally be called until it returns Z_STREAM_END or an
268 error. However if all decompression is to be performed in a single step
269 (a single call of inflate), the parameter flush should be set to
270 Z_FINISH. In this case all pending input is processed and all pending
271 output is flushed; avail_out must be large enough to hold all the
272 uncompressed data. (The size of the uncompressed data may have been saved
273 by the compressor for this purpose.) The next operation on this stream must
274 be inflateEnd to deallocate the decompression state.
275
276 inflate() returns Z_OK if some progress has been made (more input
277 processed or more output produced), Z_STREAM_END if the end of the
278 compressed data has been reached, Z_DATA_ERROR if the input data was
279 corrupted, Z_STREAM_ERROR if the stream structure was inconsistent (for
280 example if next_in or next_out was NULL), Z_MEM_ERROR if there was not enough
281 memory, Z_BUF_ERROR if no progress is possible or if there was not enough
282 room in the output buffer when Z_FINISH is used. In the Z_DATA_ERROR case,
283 the application may then call inflateSync to look for a good compression
284 block.
285*/
286
287
288extern int inflateEnd __P((z_stream *strm));
289/*
290 All dynamically allocated data structures for this stream are freed.
291 This function discards any unprocessed input and does not flush any
292 pending output.
293
294 inflateEnd returns Z_OK if success, Z_STREAM_ERROR if the stream state
295 was inconsistent. In the error case, msg may be set but then points to a
296 static string (which must not be deallocated).
297*/
298
299 /* advanced functions */
300
301/*
302 The following functions are needed only in some special applications.
303*/
304
305extern int deflateInit2 __P((z_stream *strm,
306 int level,
307 int method,
308 int windowBits,
309 int memLevel,
310 int strategy));
311/*
312 This is another version of deflateInit with more compression options. The
313 fields next_in, zalloc and zfree must be initialized before by the caller.
314
315 The method parameter is the compression method. It must be 8 in this
316 version of the library. (Method 9 will allow a 64K history buffer and
317 partial block flushes.)
318
319 The windowBits parameter is the base two logarithm of the window size
320 (the size of the history buffer). It should be in the range 8..15 for this
321 version of the library (the value 16 will be allowed soon). Larger values
322 of this parameter result in better compression at the expense of memory
323 usage. The default value is 15 if deflateInit is used instead.
324
325 The memLevel parameter specifies how much memory should be allocated
326 for the internal compression state. memLevel=1 uses minimum memory but
327 is slow and reduces compression ratio; memLevel=9 uses maximum memory
328 for optimal speed. The default value is 8.
329
330 The strategy parameter is used to tune the compression algorithm. Use
331 the value Z_DEFAULT_STRATEGY for normal data, Z_FILTERED for data
332 produced by a filter (or predictor), or Z_HUFFMAN_ONLY to force Huffman
333 encoding only (no string match). Filtered data consists mostly of small
334 values with a somewhat random distribution. In this case, the
335 compression algorithm is tuned to compress them better. The strategy
336 parameter only affects the compression ratio but not the correctness of
337 the compressed output even if it is not set appropriately.
338
339 If next_in is not null, the library will use this buffer to hold also
340 some history information; the buffer must either hold the entire input
341 data, or have at least (1<<windowBits) bytes and be writable. If next_in is
342 null, the library will allocate its own history buffer (and leave next_in
343 null). next_out need not be provided here but must be provided by the
344 application for the next call of deflate().
345
346 If the history buffer is provided by the application, next_in must
347 must never be changed by the application since the compressor maintains
348 information inside this buffer from call to call; the application
349 must provide more input only by increasing avail_in. next_in is always
350 reset by the library in this case.
351
352 deflateInit2 returns Z_OK if success, Z_MEM_ERROR if there was
353 not enough memory, Z_STREAM_ERROR if the stream state was inconsistent
354 (such as zalloc being NULL) or the parameters are invalid (such as
355 an invalid method). msg is set to null if there is no error message.
356 deflateInit2 does not perform any compression: this will be done by
357 deflate().
358*/
359
360extern int deflateCopy __P((z_stream *dest,
361 z_stream *source));
362/*
363 Sets the destination stream as a complete copy of the source stream. If
364 the source stream is using an application-supplied history buffer, a new
365 buffer is allocated for the destination stream. The compressed output
366 buffer is always application-supplied. It's the responsability of the
367 application to provide the correct values of next_out and avail_out for the
368 next call of deflate.
369
370 This function is useful when several compression strategies will be
371 tried, for example when there are several ways of pre-processing the input
372 data with a filter. The streams that will be discarded should then be freed
373 by calling deflateEnd. Note that deflateCopy duplicates the internal
374 compression state which can be quite large, so this strategy is slow and
375 can consume lots of memory.
376
377 deflateCopy returns Z_OK if success, Z_MEM_ERROR if there was not
378 enough memory, Z_STREAM_ERROR if the source stream state was inconsistent
379 (such as zalloc being NULL). msg is left unchanged in both source and
380 destination.
381*/
382
383extern int deflateReset __P((z_stream *strm));
384/*
385 This function is equivalent to deflateEnd followed by deflateInit,
386 but does not free and reallocate all the internal compression state.
387 The stream will keep the same compression level and any other attributes
388 that may have been set by deflateInit2.
389
390 deflateReset returns Z_OK if success, or Z_STREAM_ERROR if the source
391 stream state was inconsistent (such as zalloc or state being NULL).
392*/
393
394extern int inflateInit2 __P((z_stream *strm,
395 int windowBits));
396/*
397 This is another version of inflateInit with more compression options. The
398 fields next_out, zalloc and zfree must be initialized before by the caller.
399
400 The windowBits parameter is the base two logarithm of the maximum window
401 size (the size of the history buffer). It should be in the range 8..15 for
402 this version of the library (the value 16 will be allowed soon). The
403 default value is 15 if inflateInit is used instead. If a compressed stream
404 with a larger window size is given as input, inflate() will return with
405 the error code Z_DATA_ERROR instead of trying to allocate a larger window.
406
407 If next_out is not null, the library will use this buffer for the history
408 buffer; the buffer must either be large enough to hold the entire output
409 data, or have at least 1<<(windowBits-1) bytes. If next_out is null, the
410 library will allocate its own buffer (and leave next_out null). next_in
411 need not be provided here but must be provided by the application for the
412 next call of inflate().
413
414 If the history buffer is provided by the application, next_out must
415 never be changed by the application since the decompressor maintains
416 history information inside this buffer from call to call; the application
417 can only reset next_out to the beginning of the history buffer when
418 avail_out is zero and all output has been consumed.
419
420 inflateInit2 returns Z_OK if success, Z_MEM_ERROR if there was
421 not enough memory, Z_STREAM_ERROR if the stream state was inconsistent
422 (such as zalloc being NULL) or the parameters are invalid (such as
423 windowBits < 9). msg is set to null if there is no error message.
424 inflateInit2 does not perform any compression: this will be done by
425 inflate().
426*/
427
428extern int inflateSync __P((z_stream *strm));
429/*
430 Skips invalid compressed data until the special marker and a valid block
431 can be found, or until all available input is skipped. No output is provided.
432
433 inflateSync returns Z_OK if a valid block has been found, Z_BUF_ERROR if
434 no more input was provided, Z_DATA_ERROR if not valid block has been found,
435 Z_STREAM_ERROR if the stream structure was inconsistent. In the success
436 case, the application may save the current current value of total_in which
437 indicates where valid compressed data was found. In the error case, the
438 application may repeatedly call inflateSync, providing more input each time,
439 until success or end of the input data.
440*/
441
442extern int inflateReset __P((z_stream *strm));
443/*
444 This function is equivalent to inflateEnd followed by inflateInit,
445 but does not free and reallocate all the internal decompression state.
446 The stream will keep attributes that may have been set by inflateInit2.
447
448 inflateReset returns Z_OK if success, or Z_STREAM_ERROR if the source
449 stream state was inconsistent (such as zalloc or state being NULL).
450*/
451
452
453 /* utility functions */
454
455/*
456 The following utility functions are implemented on top of the
457 basic stream-oriented functions. To simplify the interface, some
458 default options are assumed (compression level, window size,
459 standard memory allocation functions). The source code of these
460 utility functions can easily be modified if you need special options.
461*/
462
463extern int compress __P((Byte *dest, uLong *destLen,
464 Byte *source, uLong sourceLen));
465/*
466 Compresses the source buffer into the destination buffer. sourceLen is
467 the byte length of the source buffer. Upon entry, destLen is the total
468 size of the destination buffer, which must be at least 0.1% larger than
469 sourceLen plus 8 bytes. Upon exit, destLen is the actual size of the
470 compressed buffer.
471 This function can be used to compress a whole file at once if the
472 input file is mmap'ed.
473 compress returns Z_OK if success, Z_MEM_ERROR if there was not
474 enough memory, Z_BUF_ERROR if there was not enough room in the output
475 buffer.
476*/
477
478extern int uncompress __P((Byte *dest, uLong *destLen,
479 Byte *source, uLong sourceLen));
480/*
481 Decompresses the source buffer into the destination buffer. sourceLen is
482 the byte length of the source buffer. Upon entry, destLen is the total
483 size of the destination buffer, which must be large enough to hold the
484 entire uncompressed data. (The size of the uncompressed data must have
485 been saved previously by the compressor and transmitted to the decompressor
486 by some mechanism outside the scope of this compression library.)
487 Upon exit, destLen is the actual size of the compressed buffer.
488 This function can be used to decompress a whole file at once if the
489 input file is mmap'ed.
490
491 uncompress returns Z_OK if success, Z_MEM_ERROR if there was not
492 enough memory, Z_BUF_ERROR if there was not enough room in the output
493 buffer, or Z_DATA_ERROR if the input data was corrupted.
494*/
495
496
497typedef voidp gzFile;
498
499extern gzFile gzopen __P((char *path, char *mode));
500/*
501 Opens a gzip (.gz) file for reading or writing. The mode parameter
502 is as in fopen ("rb" or "wb"). gzopen can also be used to read a file
503 which is not in gzip format; in this case gzread will directly read from
504 the file without decompression.
505 gzopen return NULL if the file could not be opened or if there was
506 insufficient memory to allocate the (de)compression state; errno
507 can be checked to distinguish the two cases (if errno is zero, the
508 zlib error is Z_MEM_ERROR).
509*/
510
511extern gzFile gzdopen __P((int fd, char *mode));
512/*
513 gzdopen() associates a gzFile with the file descriptor fd. File
514 descriptors are obtained from calls like open, dup, creat, or pipe.
515 The mode parameter is as in fopen ("rb" or "wb").
516 gzdopen return NULL if there was insufficient memory to allocate
517 the (de)compression state.
518*/
519
520extern int gzread __P((gzFile file, voidp buf, unsigned len));
521/*
522 Reads the given number of uncompressed bytes from the compressed file.
523 If the input file was not in gzip format, gzread copies the given number
524 of bytes into the buffer.
525 gzread returns the number of uncompressed bytes actually read (0 for
526 end of file, -1 for error). */
527
528extern int gzwrite __P((gzFile file, voidp buf, unsigned len));
529/*
530 Writes the given number of uncompressed bytes into the compressed file.
531 gzwrite returns the number of uncompressed bytes actually written
532 (0 in case of error).
533*/
534
535extern int gzflush __P((gzFile file, int flush));
536/*
537 Flushes all pending output into the compressed file. The parameter
538 flush is as in the deflate() function. The return value is the zlib
539 error number (see function gzerror below).
540 gzflush should be called only when strictly necessary because it can
541 degrade compression.
542*/
543
544extern int gzclose __P((gzFile file));
545/*
546 Flushes all pending output if necessary, closes the compressed file
547 and deallocates all the (de)compression state. The return value is the zlib
548 error number (see function gzerror below).
549*/
550
551extern char* gzerror __P((gzFile file, int *errnum));
552/*
553 Returns the error message for the last error which occurred on the
554 given compressed file. errnum is set to zlib error number. If an
555 error occurred in the file system and not in the compression library,
556 errnum is set to Z_ERRNO and the application may consult errno
557 to get the exact error code.
558*/
559
560 /* checksum functions */
561
562/*
563 These functions are not related to compression but are exported
564 anyway because they might be useful in applications using the
565 compression library.
566*/
567
568extern uLong adler32 __P((uLong adler, Byte *buf, uInt len));
569/*
570 Update a running Adler-32 checksum with the bytes buf[0..len-1] and
571 return the updated checksum. If buf is NULL, this function returns
572 the required initial value for the checksum.
573 An Adler-32 cheksum is almost as reliable as a CRC32 but can be computed
574 much faster. Usage example:
575
576 uLong adler = adler32(0L, Z_NULL, 0);
577
578 while (read_buffer(buffer, length) != EOF) {
579 adler = adler32(adler, buffer, length);
580 }
581 if (adler != original_adler) error();
582*/
583
584extern uLong crc32 __P((uLong crc, Byte *buf, uInt len));
585/*
586 Update a running crc with the bytes buf[0..len-1] and return the updated
587 crc. If buf is NULL, this function returns the required initial value
588 for the crc (0). Pre- and post-conditioning (one's complement) is performed
589 within this function so it shouldn't be done by the application.
590 Usage example:
591
592 uLong crc = crc32(0L, Z_NULL, 0);
593
594 while (read_buffer(buffer, length) != EOF) {
595 crc = crc32(crc, buffer, length);
596 }
597 if (crc != original_crc) error();
598*/
599
600#ifndef _Z_UTIL_H
601 struct internal_state {int dummy;}; /* hack for buggy compilers */
602#endif
603
604#endif /* _ZLIB_H */
diff --git a/zutil.c b/zutil.c
new file mode 100644
index 0000000..1a2e7ef
--- /dev/null
+++ b/zutil.c
@@ -0,0 +1,164 @@
1/* zutil.c -- target dependent utility functions for the compression library
2 * Copyright (C) 1995 Jean-loup Gailly.
3 * For conditions of distribution and use, see copyright notice in zlib.h
4 */
5
6/* $Id: zutil.c,v 1.3 1995/04/10 09:52:26 jloup Exp $ */
7
8#include <stdio.h>
9
10#include "zutil.h"
11
12char *zlib_version = ZLIB_VERSION;
13
14char *z_errmsg[] = {
15"stream end", /* Z_STREAM_END 1 */
16"", /* Z_OK 0 */
17"file error", /* Z_ERRNO (-1) */
18"stream error", /* Z_STREAM_ERROR (-2) */
19"data error", /* Z_DATA_ERROR (-3) */
20"insufficient memory", /* Z_MEM_ERROR (-4) */
21"buffer error", /* Z_BUF_ERROR (-5) */
22""};
23
24
25void z_error (m)
26 char *m;
27{
28 fprintf(stderr, "%s\n", m);
29 exit(1);
30}
31
32#ifndef HAVE_MEMCPY
33
34void zmemcpy(dest, source, len)
35 Byte* dest;
36 Byte* source;
37 uInt len;
38{
39 if (len == 0) return;
40 do {
41 *dest++ = *source++; /* ??? to be unrolled */
42 } while (--len != 0);
43}
44
45void zmemzero(dest, len)
46 Byte* dest;
47 uInt len;
48{
49 if (len == 0) return;
50 do {
51 *dest++ = 0; /* ??? to be unrolled */
52 } while (--len != 0);
53}
54#endif
55
56#if defined(MSDOS) && !defined(USE_CALLOC)
57# ifdef __TURBOC__
58
59/* Turbo C malloc() does not allow dynamic allocation of 64K bytes
60 * and farmalloc(64K) returns a pointer with an offset of 8, so we
61 * must fix the pointer. Warning: the pointer must be put back to its
62 * original form in order to free it, use zcfree().
63 */
64
65#define MAX_PTR 10
66/* 10*64K = 640K */
67
68local int next_ptr = 0;
69
70typedef struct ptr_table_s {
71 voidp org_ptr;
72 voidp new_ptr;
73} ptr_table;
74
75local ptr_table table[MAX_PTR];
76/* This table is used to remember the original form of pointers
77 * to large buffers (64K). Such pointers are normalized with a zero offset.
78 * Since MSDOS is not a preemptive multitasking OS, this table is not
79 * protected from concurrent access. This hack doesn't work anyway on
80 * a protected system like OS/2. Use Microsoft C instead.
81 */
82
83voidp zcalloc (voidp opaque, unsigned items, unsigned size)
84{
85 voidp buf;
86 ulg bsize = (ulg)items*size;
87
88 if (bsize < 65536L) {
89 buf = farmalloc(bsize);
90 if (*(ush*)&buf != 0) return buf;
91 } else {
92 buf = farmalloc(bsize + 16L);
93 }
94 if (buf == NULL || next_ptr >= MAX_PTR) return NULL;
95 table[next_ptr].org_ptr = buf;
96
97 /* Normalize the pointer to seg:0 */
98 *((ush*)&buf+1) += ((ush)((uch*)buf-0) + 15) >> 4;
99 *(ush*)&buf = 0;
100 table[next_ptr++].new_ptr = buf;
101 return buf;
102}
103
104void zcfree (voidp opaque, voidp ptr)
105{
106 int n;
107 if (*(ush*)&ptr != 0) { /* object < 64K */
108 farfree(ptr);
109 return;
110 }
111 /* Find the original pointer */
112 for (n = 0; n < next_ptr; n++) {
113 if (ptr != table[n].new_ptr) continue;
114
115 farfree(table[n].org_ptr);
116 while (++n < next_ptr) {
117 table[n-1] = table[n];
118 }
119 next_ptr--;
120 return;
121 }
122 z_error("zcfree: ptr not found");
123}
124
125# else /* MSC */
126
127#if (!defined(_MSC_VER) || (_MSC_VER < 600))
128# define _halloc halloc
129# define _hfree hfree
130#endif
131
132voidp zcalloc (voidp opaque, unsigned items, unsigned size)
133{
134 return _halloc((long)items, size);
135}
136
137void zcfree (voidp opaque, voidp ptr)
138{
139 return _hfree(ptr);
140}
141
142# endif /* __TURBOC__ ? */
143
144#else /* !MSDOS */
145
146extern voidp calloc __P((uInt items, uInt size));
147extern void free __P((voidp ptr));
148
149voidp zcalloc (opaque, items, size)
150 voidp opaque;
151 unsigned items;
152 unsigned size;
153{
154 return calloc(items, size);
155}
156
157void zcfree (opaque, ptr)
158 voidp opaque;
159 voidp ptr;
160{
161 free(ptr);
162}
163
164#endif /* MSDOS */
diff --git a/zutil.h b/zutil.h
new file mode 100644
index 0000000..a1108e6
--- /dev/null
+++ b/zutil.h
@@ -0,0 +1,166 @@
1/* zutil.h -- internal interface and configuration of the compression library
2 * Copyright (C) 1995 Jean-loup Gailly.
3 * For conditions of distribution and use, see copyright notice in zlib.h
4 */
5
6/* WARNING: this file should *not* be used by applications. It is
7 part of the implementation of the compression library and is
8 subject to change. Applications should only use zlib.h.
9 */
10
11/* $Id: zutil.h,v 1.4 1995/04/14 10:22:17 jloup Exp $ */
12
13#ifndef _Z_UTIL_H
14#define _Z_UTIL_H
15
16#include "zlib.h"
17
18#ifdef MSDOS
19# include <stddef.h>
20#else
21 extern int errno;
22#endif
23
24#ifndef local
25# define local static
26#endif
27/* compile with -Dlocal if your debugger can't find static symbols */
28
29typedef unsigned char uch;
30typedef unsigned short ush;
31typedef unsigned long ulg;
32
33extern char *z_errmsg[]; /* indexed by 1-zlib_error */
34
35#define ERR_RETURN(strm,err) return (strm->msg=z_errmsg[1-err], err)
36/* To be used only when the state is known to be valid */
37
38 /* common constants */
39
40#define DEFLATED 8
41
42#ifndef WBITS
43# define WBITS 15 /* 32K window */
44#endif
45
46#ifndef MEM_LEVEL
47# define MEM_LEVEL 8
48#endif
49
50#define STORED_BLOCK 0
51#define STATIC_TREES 1
52#define DYN_TREES 2
53/* The three kinds of block type */
54
55#define MIN_MATCH 3
56#define MAX_MATCH 258
57/* The minimum and maximum match lengths */
58
59 /* target dependencies */
60
61#ifdef MSDOS
62# define OS_CODE 0x00
63# ifdef __TURBOC__
64# include <alloc.h>
65# define exit(n) _exit(n)
66# else /* MSC */
67# include <malloc.h>
68# endif
69#endif
70
71#ifdef OS2
72# define OS_CODE 0x06
73#endif
74
75#ifdef WIN32 /* Windows NT */
76# define OS_CODE 0x0b
77#endif
78
79#if defined(VAXC) || defined(VMS)
80# define OS_CODE 0x02
81# define FOPEN(name, mode) \
82 fopen((name), (mode), "mbc=60", "ctx=stm", "rfm=fix", "mrs=512")
83#endif
84
85#ifdef AMIGA
86# define OS_CODE 0x01
87#endif
88
89#if defined(ATARI) || defined(atarist)
90# define OS_CODE 0x05
91#endif
92
93#ifdef MACOS
94# define OS_CODE 0x07
95#endif
96
97#ifdef __50SERIES /* Prime/PRIMOS */
98# define OS_CODE 0x0F
99#endif
100
101#ifdef TOPS20
102# define OS_CODE 0x0a
103#endif
104
105 /* Common defaults */
106
107#ifndef OS_CODE
108# define OS_CODE 0x03 /* assume Unix */
109#endif
110
111#ifndef FOPEN
112# define FOPEN(name, mode) fopen((name), (mode))
113#endif
114
115 /* functions */
116
117#ifdef HAVE_STRERROR
118 extern char *strerror __P((int));
119# define zstrerror(errnum) strerror(errnum)
120#else
121# define zstrerror(errnum) ""
122#endif
123
124#if defined(__STDC__) && !defined(HAVE_MEMCPY)
125# define HAVE_MEMCPY
126#endif
127#ifdef HAVE_MEMCPY
128# define zmemcpy memcpy
129# define zmemzero(dest, len) memset(dest, 0, len)
130#else
131 extern void zmemcpy __P((Byte* dest, Byte* source, uInt len));
132 extern void zmemzero __P((Byte* dest, uInt len));
133#endif
134
135/* Diagnostic functions */
136#ifdef DEBUG
137# include <stdio.h>
138# ifndef verbose
139# define verbose 0
140# endif
141# define Assert(cond,msg) {if(!(cond)) z_error(msg);}
142# define Trace(x) fprintf x
143# define Tracev(x) {if (verbose) fprintf x ;}
144# define Tracevv(x) {if (verbose>1) fprintf x ;}
145# define Tracec(c,x) {if (verbose && (c)) fprintf x ;}
146# define Tracecv(c,x) {if (verbose>1 && (c)) fprintf x ;}
147#else
148# define Assert(cond,msg)
149# define Trace(x)
150# define Tracev(x)
151# define Tracevv(x)
152# define Tracec(c,x)
153# define Tracecv(c,x)
154#endif
155
156
157extern void z_error __P((char *m));
158
159voidp zcalloc __P((voidp opaque, unsigned items, unsigned size));
160void zcfree __P((voidp opaque, voidp ptr));
161
162#define ZALLOC(strm, items, size) (*strm->zalloc)(strm->opaque, items, size)
163#define ZFREE(strm, addr) (*strm->zfree) (strm->opaque, (voidp)addr)
164#define TRY_FREE(s, p) {if (p) ZFREE(s, p);}
165
166#endif /* _Z_UTIL_H */
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-03-15 20:12:45 +0000