diff options
author | cvs2svn <cvs2svn@FreeBSD.org> | 1999-01-10 09:47:01 +0000 |
---|---|---|
committer | cvs2svn <cvs2svn@FreeBSD.org> | 1999-01-10 09:47:01 +0000 |
commit | 8ff77dc6bfd0eb5e697cbe7b3eb69f261e4e95fe (patch) | |
tree | 3d83ee85338e73d7c06f3f8fe78ff74928970dc6 | |
parent | 628b9c34751f3d4523e0a5a92c53a6af1d13d103 (diff) |
This commit was manufactured by cvs2svn to create tagvendor/zlib/1.1.3
'libz-vendor-v1_1_3'.
Notes
Notes:
svn path=/vendor/libz/dist/; revision=42468
svn path=/vendor/libz/1.1.3/; revision=42470; tag=vendor/zlib/1.1.3
-rw-r--r-- | lib/libz/Makefile | 158 | ||||
-rw-r--r-- | lib/libz/algorithm.doc | 105 |
2 files changed, 0 insertions, 263 deletions
diff --git a/lib/libz/Makefile b/lib/libz/Makefile deleted file mode 100644 index 772bc31f565f..000000000000 --- a/lib/libz/Makefile +++ /dev/null @@ -1,158 +0,0 @@ -# Makefile for zlib -# Copyright (C) 1995-1998 Jean-loup Gailly. -# For conditions of distribution and use, see copyright notice in zlib.h - -# To compile and test, type: -# ./configure; make test -# The call of configure is optional if you don't have special requirements -# If you wish to build zlib as a shared library, use: ./configure -s - -# To install /usr/local/lib/libz.* and /usr/local/include/zlib.h, type: -# make install -# To install in $HOME instead of /usr/local, use: -# make install prefix=$HOME - -CC=cc - -CFLAGS=-O -#CFLAGS=-O -DMAX_WBITS=14 -DMAX_MEM_LEVEL=7 -#CFLAGS=-g -DDEBUG -#CFLAGS=-O3 -Wall -Wwrite-strings -Wpointer-arith -Wconversion \ -# -Wstrict-prototypes -Wmissing-prototypes - -LDFLAGS=-L. -lz -LDSHARED=$(CC) - -VER=1.1.1 -LIBS=libz.a -SHAREDLIB=libz.so - -AR=ar rc -RANLIB=ranlib -TAR=tar -SHELL=/bin/sh - -prefix=/usr/local -exec_prefix = $(prefix) - -OBJS = adler32.o compress.o crc32.o gzio.o uncompr.o deflate.o trees.o \ - zutil.o inflate.o infblock.o inftrees.o infcodes.o infutil.o inffast.o - -TEST_OBJS = example.o minigzip.o - -DISTFILES = README INDEX ChangeLog configure Make*[a-z0-9] *.[ch] descrip.mms \ - algorithm.txt zlib.3 msdos/Make*[a-z0-9] msdos/zlib.def msdos/zlib.rc \ - nt/Makefile.nt nt/zlib.dnt contrib/README.contrib contrib/*.txt \ - contrib/asm386/*.asm contrib/asm386/*.c \ - contrib/asm386/*.bat contrib/asm386/zlibvc.d?? contrib/iostream/*.cpp \ - contrib/iostream/*.h contrib/iostream2/*.h contrib/iostream2/*.cpp \ - contrib/untgz/Makefile contrib/untgz/*.c contrib/untgz/*.w32 - -all: example minigzip - -test: all - @LD_LIBRARY_PATH=.:$(LD_LIBRARY_PATH) ; export LD_LIBRARY_PATH; \ - echo hello world | ./minigzip | ./minigzip -d || \ - echo ' *** minigzip test FAILED ***' ; \ - if ./example; then \ - echo ' *** zlib test OK ***'; \ - else \ - echo ' *** zlib test FAILED ***'; \ - fi - -libz.a: $(OBJS) - $(AR) $@ $(OBJS) - -@ ($(RANLIB) $@ || true) >/dev/null 2>&1 - -$(SHAREDLIB).$(VER): $(OBJS) - $(LDSHARED) -o $@ $(OBJS) - rm -f $(SHAREDLIB) $(SHAREDLIB).1 - ln -s $@ $(SHAREDLIB) - ln -s $@ $(SHAREDLIB).1 - -example: example.o $(LIBS) - $(CC) $(CFLAGS) -o $@ example.o $(LDFLAGS) - -minigzip: minigzip.o $(LIBS) - $(CC) $(CFLAGS) -o $@ minigzip.o $(LDFLAGS) - -install: $(LIBS) - -@if [ ! -d $(prefix)/include ]; then mkdir $(prefix)/include; fi - -@if [ ! -d $(exec_prefix)/lib ]; then mkdir $(exec_prefix)/lib; fi - cp zlib.h zconf.h $(prefix)/include - chmod 644 $(prefix)/include/zlib.h $(prefix)/include/zconf.h - cp $(LIBS) $(exec_prefix)/lib - cd $(exec_prefix)/lib; chmod 755 $(LIBS) - -@(cd $(exec_prefix)/lib; $(RANLIB) libz.a || true) >/dev/null 2>&1 - cd $(exec_prefix)/lib; if test -f $(SHAREDLIB).$(VER); then \ - rm -f $(SHAREDLIB) $(SHAREDLIB).1; \ - ln -s $(SHAREDLIB).$(VER) $(SHAREDLIB); \ - ln -s $(SHAREDLIB).$(VER) $(SHAREDLIB).1; \ - (ldconfig || true) >/dev/null 2>&1; \ - fi -# The ranlib in install is needed on NeXTSTEP which checks file times -# ldconfig is for Linux - -uninstall: - cd $(prefix)/include; \ - v=$(VER); \ - if test -f zlib.h; then \ - v=`sed -n '/VERSION "/s/.*"\(.*\)".*/\1/p' < zlib.h`; \ - rm -f zlib.h zconf.h; \ - fi; \ - cd $(exec_prefix)/lib; rm -f libz.a; \ - if test -f $(SHAREDLIB).$$v; then \ - rm -f $(SHAREDLIB).$$v $(SHAREDLIB) $(SHAREDLIB).1; \ - fi - -clean: - rm -f *.o *~ example minigzip libz.a libz.so* foo.gz - -distclean: clean - -zip: - mv Makefile Makefile~; cp -p Makefile.in Makefile - rm -f test.c ztest*.c - v=`sed -n -e 's/\.//g' -e '/VERSION "/s/.*"\(.*\)".*/\1/p' < zlib.h`;\ - zip -ul9 zlib$$v $(DISTFILES) - mv Makefile~ Makefile - -dist: - mv Makefile Makefile~; cp -p Makefile.in Makefile - rm -f test.c ztest*.c - d=zlib-`sed -n '/VERSION "/s/.*"\(.*\)".*/\1/p' < zlib.h`;\ - rm -f $$d.tar.gz; \ - if test ! -d ../$$d; then rm -f ../$$d; ln -s `pwd` ../$$d; fi; \ - files=""; \ - for f in $(DISTFILES); do files="$$files $$d/$$f"; done; \ - cd ..; \ - GZIP=-9 $(TAR) chofz $$d/$$d.tar.gz $$files; \ - if test ! -d $$d; then rm -f $$d; fi - mv Makefile~ Makefile - -tags: - etags *.[ch] - -depend: - makedepend -- $(CFLAGS) -- *.[ch] - -# DO NOT DELETE THIS LINE -- make depend depends on it. - -adler32.o: zlib.h zconf.h -compress.o: zlib.h zconf.h -crc32.o: zlib.h zconf.h -deflate.o: deflate.h zutil.h zlib.h zconf.h -example.o: zlib.h zconf.h -gzio.o: zutil.h zlib.h zconf.h -infblock.o: infblock.h inftrees.h infcodes.h infutil.h zutil.h zlib.h zconf.h -infcodes.o: zutil.h zlib.h zconf.h -infcodes.o: inftrees.h infblock.h infcodes.h infutil.h inffast.h -inffast.o: zutil.h zlib.h zconf.h inftrees.h -inffast.o: infblock.h infcodes.h infutil.h inffast.h -inflate.o: zutil.h zlib.h zconf.h infblock.h -inftrees.o: zutil.h zlib.h zconf.h inftrees.h -infutil.o: zutil.h zlib.h zconf.h infblock.h inftrees.h infcodes.h infutil.h -minigzip.o: zlib.h zconf.h -trees.o: deflate.h zutil.h zlib.h zconf.h trees.h -uncompr.o: zlib.h zconf.h -zutil.o: zutil.h zlib.h zconf.h diff --git a/lib/libz/algorithm.doc b/lib/libz/algorithm.doc deleted file mode 100644 index 01902aff6663..000000000000 --- a/lib/libz/algorithm.doc +++ /dev/null @@ -1,105 +0,0 @@ -1. Compression algorithm (deflate) - -The deflation algorithm used by zlib (also zip and gzip) is a variation of -LZ77 (Lempel-Ziv 1977, see reference below). It finds duplicated strings in -the input data. The second occurrence of a string is replaced by a -pointer to the previous string, in the form of a pair (distance, -length). Distances are limited to 32K bytes, and lengths are limited -to 258 bytes. When a string does not occur anywhere in the previous -32K bytes, it is emitted as a sequence of literal bytes. (In this -description, `string' must be taken as an arbitrary sequence of bytes, -and is not restricted to printable characters.) - -Literals or match lengths are compressed with one Huffman tree, and -match distances are compressed with another tree. The trees are stored -in a compact form at the start of each block. The blocks can have any -size (except that the compressed data for one block must fit in -available memory). A block is terminated when deflate() determines that -it would be useful to start another block with fresh trees. (This is -somewhat similar to the behavior of LZW-based _compress_.) - -Duplicated strings are found using a hash table. All input strings of -length 3 are inserted in the hash table. A hash index is computed for -the next 3 bytes. If the hash chain for this index is not empty, all -strings in the chain are compared with the current input string, and -the longest match is selected. - -The hash chains are searched starting with the most recent strings, to -favor small distances and thus take advantage of the Huffman encoding. -The hash chains are singly linked. There are no deletions from the -hash chains, the algorithm simply discards matches that are too old. - -To avoid a worst-case situation, very long hash chains are arbitrarily -truncated at a certain length, determined by a runtime option (level -parameter of deflateInit). So deflate() does not always find the longest -possible match but generally finds a match which is long enough. - -deflate() also defers the selection of matches with a lazy evaluation -mechanism. After a match of length N has been found, deflate() searches for a -longer match at the next input byte. If a longer match is found, the -previous match is truncated to a length of one (thus producing a single -literal byte) and the longer match is emitted afterwards. Otherwise, -the original match is kept, and the next match search is attempted only -N steps later. - -The lazy match evaluation is also subject to a runtime parameter. If -the current match is long enough, deflate() reduces the search for a longer -match, thus speeding up the whole process. If compression ratio is more -important than speed, deflate() attempts a complete second search even if -the first match is already long enough. - -The lazy match evaluation is not performed for the fastest compression -modes (level parameter 1 to 3). For these fast modes, new strings -are inserted in the hash table only when no match was found, or -when the match is not too long. This degrades the compression ratio -but saves time since there are both fewer insertions and fewer searches. - - -2. Decompression algorithm (inflate) - -The real question is, given a Huffman tree, how to decode fast. The most -important realization is that shorter codes are much more common than -longer codes, so pay attention to decoding the short codes fast, and let -the long codes take longer to decode. - -inflate() sets up a first level table that covers some number of bits of -input less than the length of longest code. It gets that many bits from the -stream, and looks it up in the table. The table will tell if the next -code is that many bits or less and how many, and if it is, it will tell -the value, else it will point to the next level table for which inflate() -grabs more bits and tries to decode a longer code. - -How many bits to make the first lookup is a tradeoff between the time it -takes to decode and the time it takes to build the table. If building the -table took no time (and if you had infinite memory), then there would only -be a first level table to cover all the way to the longest code. However, -building the table ends up taking a lot longer for more bits since short -codes are replicated many times in such a table. What inflate() does is -simply to make the number of bits in the first table a variable, and set it -for the maximum speed. - -inflate() sends new trees relatively often, so it is possibly set for a -smaller first level table than an application that has only one tree for -all the data. For inflate, which has 286 possible codes for the -literal/length tree, the size of the first table is nine bits. Also the -distance trees have 30 possible values, and the size of the first table is -six bits. Note that for each of those cases, the table ended up one bit -longer than the ``average'' code length, i.e. the code length of an -approximately flat code which would be a little more than eight bits for -286 symbols and a little less than five bits for 30 symbols. It would be -interesting to see if optimizing the first level table for other -applications gave values within a bit or two of the flat code size. - - -Jean-loup Gailly Mark Adler -gzip@prep.ai.mit.edu madler@alumni.caltech.edu - - -References: - -[LZ77] Ziv J., Lempel A., ``A Universal Algorithm for Sequential Data -Compression,'' IEEE Transactions on Information Theory, Vol. 23, No. 3, -pp. 337-343. - -``DEFLATE Compressed Data Format Specification'' available in -ftp://ds.internic.net/rfc/rfc1951.txt |