diff options
author | Thorsten Lockert <tholo@cvs.openbsd.org> | 2001-09-28 23:26:35 +0000 |
---|---|---|
committer | Thorsten Lockert <tholo@cvs.openbsd.org> | 2001-09-28 23:26:35 +0000 |
commit | 257b9a3b99db7b3c79cdafe49da86e76e8fcc4ed (patch) | |
tree | 906d81699e697bc1cc7fc3f44194e5131f47346d /gnu/usr.bin/cvs/zlib | |
parent | 9894d5f1308eb568c700ab3424cc50396c5b4a3f (diff) |
Merge local changes; work in progress
Diffstat (limited to 'gnu/usr.bin/cvs/zlib')
-rw-r--r-- | gnu/usr.bin/cvs/zlib/algorithm.doc | 105 | ||||
-rw-r--r-- | gnu/usr.bin/cvs/zlib/build_zlib.com | 18 | ||||
-rw-r--r-- | gnu/usr.bin/cvs/zlib/zlib.def | 46 | ||||
-rw-r--r-- | gnu/usr.bin/cvs/zlib/zlib.dsp | 146 | ||||
-rw-r--r-- | gnu/usr.bin/cvs/zlib/zlib.rc | 32 |
5 files changed, 0 insertions, 347 deletions
diff --git a/gnu/usr.bin/cvs/zlib/algorithm.doc b/gnu/usr.bin/cvs/zlib/algorithm.doc deleted file mode 100644 index 01902aff666..00000000000 --- a/gnu/usr.bin/cvs/zlib/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 diff --git a/gnu/usr.bin/cvs/zlib/build_zlib.com b/gnu/usr.bin/cvs/zlib/build_zlib.com deleted file mode 100644 index cd998fc4918..00000000000 --- a/gnu/usr.bin/cvs/zlib/build_zlib.com +++ /dev/null @@ -1,18 +0,0 @@ -$ CC :== CC/DEBUG/NOOPTIMIZE/STANDARD=VAXC/DEFINE=HAVE_CONFIG_H- -/INCLUDE_DIRECTORY=([-],[-.LIB],[-.SRC],[-.VMS])/PREFIX_LIBRARY_ENTRIES=ALL_ENTRIES -$ CC adler32.c -$ CC compress.c -$ CC crc32.c -$ CC uncompr.c -$ CC deflate.c -$ CC trees.c -$ CC zutil.c -$ CC inflate.c -$ CC infblock.c -$ CC inftrees.c -$ CC infcodes.c -$ CC infutil.c -$ CC inffast.c -$ library/create zlib.olb adler32.obj,- -compress.obj,crc32.obj,uncompr.obj,deflate.obj,trees.obj,zutil.obj,- -inflate.obj,infblock.obj,inftrees.obj,infcodes.obj,infutil.obj,inffast.obj diff --git a/gnu/usr.bin/cvs/zlib/zlib.def b/gnu/usr.bin/cvs/zlib/zlib.def deleted file mode 100644 index 08c6d5501a4..00000000000 --- a/gnu/usr.bin/cvs/zlib/zlib.def +++ /dev/null @@ -1,46 +0,0 @@ -LIBRARY "zlib" - -DESCRIPTION '"""zlib data compression library"""' - -EXETYPE NT - -SUBSYSTEM WINDOWS - -STUB 'WINSTUB.EXE' - -VERSION 1.04 - -CODE EXECUTE READ - -DATA READ WRITE - -HEAPSIZE 1048576,4096 - -EXPORTS - zlibVersion - deflate - deflateEnd - inflate - inflateEnd - deflateSetDictionary - deflateCopy - deflateReset - deflateParams - inflateSetDictionary - inflateSync - inflateReset - compress - uncompress - gzopen - gzdopen - gzread - gzwrite - gzflush - gzclose - gzerror - adler32 - crc32 - deflateInit_ - inflateInit_ - deflateInit2_ - inflateInit2_ diff --git a/gnu/usr.bin/cvs/zlib/zlib.dsp b/gnu/usr.bin/cvs/zlib/zlib.dsp deleted file mode 100644 index 7a20a8f9cbf..00000000000 --- a/gnu/usr.bin/cvs/zlib/zlib.dsp +++ /dev/null @@ -1,146 +0,0 @@ -# Microsoft Developer Studio Project File - Name="zlib" - Package Owner=<4>
-# Microsoft Developer Studio Generated Build File, Format Version 5.00
-# ** DO NOT EDIT **
-
-# TARGTYPE "Win32 (x86) Static Library" 0x0104
-
-CFG=zlib - Win32 Debug
-!MESSAGE This is not a valid makefile. To build this project using NMAKE,
-!MESSAGE use the Export Makefile command and run
-!MESSAGE
-!MESSAGE NMAKE /f "zlib.mak".
-!MESSAGE
-!MESSAGE You can specify a configuration when running NMAKE
-!MESSAGE by defining the macro CFG on the command line. For example:
-!MESSAGE
-!MESSAGE NMAKE /f "zlib.mak" CFG="zlib - Win32 Debug"
-!MESSAGE
-!MESSAGE Possible choices for configuration are:
-!MESSAGE
-!MESSAGE "zlib - Win32 Release" (based on "Win32 (x86) Static Library")
-!MESSAGE "zlib - Win32 Debug" (based on "Win32 (x86) Static Library")
-!MESSAGE
-
-# Begin Project
-# PROP Scc_ProjName ""
-# PROP Scc_LocalPath ""
-CPP=cl.exe
-
-!IF "$(CFG)" == "zlib - Win32 Release"
-
-# PROP BASE Use_MFC 0
-# PROP BASE Use_Debug_Libraries 0
-# PROP BASE Output_Dir "Release"
-# PROP BASE Intermediate_Dir "Release"
-# PROP BASE Target_Dir ""
-# PROP Use_MFC 0
-# PROP Use_Debug_Libraries 0
-# PROP Output_Dir "Release"
-# PROP Intermediate_Dir "Release"
-# PROP Target_Dir ""
-# ADD BASE CPP /nologo /W3 /GX /O2 /D "WIN32" /D "NDEBUG" /D "_WINDOWS" /YX /FD /c
-# ADD CPP /nologo /W3 /GX /O2 /D "WIN32" /D "NDEBUG" /D "_WINDOWS" /YX /FD /c
-BSC32=bscmake.exe
-# ADD BASE BSC32 /nologo
-# ADD BSC32 /nologo
-LIB32=link.exe -lib
-# ADD BASE LIB32 /nologo
-# ADD LIB32 /nologo
-
-!ELSEIF "$(CFG)" == "zlib - Win32 Debug"
-
-# PROP BASE Use_MFC 0
-# PROP BASE Use_Debug_Libraries 1
-# PROP BASE Output_Dir "Debug"
-# PROP BASE Intermediate_Dir "Debug"
-# PROP BASE Target_Dir ""
-# PROP Use_MFC 0
-# PROP Use_Debug_Libraries 1
-# PROP Output_Dir "Debug"
-# PROP Intermediate_Dir "Debug"
-# PROP Target_Dir ""
-# ADD BASE CPP /nologo /W3 /GX /Z7 /Od /D "WIN32" /D "_DEBUG" /D "_WINDOWS" /YX /FD /c
-# ADD CPP /nologo /W3 /GX /Z7 /Od /D "WIN32" /D "_DEBUG" /D "_WINDOWS" /YX /FD /c
-BSC32=bscmake.exe
-# ADD BASE BSC32 /nologo
-# ADD BSC32 /nologo
-LIB32=link.exe -lib
-# ADD BASE LIB32 /nologo
-# ADD LIB32 /nologo
-
-!ENDIF
-
-# Begin Target
-
-# Name "zlib - Win32 Release"
-# Name "zlib - Win32 Debug"
-# Begin Group "Source Files"
-
-# PROP Default_Filter "*.c"
-# Begin Source File
-
-SOURCE=.\adler32.c
-# End Source File
-# Begin Source File
-
-SOURCE=.\compress.c
-# End Source File
-# Begin Source File
-
-SOURCE=.\crc32.c
-# End Source File
-# Begin Source File
-
-SOURCE=.\deflate.c
-# End Source File
-# Begin Source File
-
-SOURCE=.\example.c
-# End Source File
-# Begin Source File
-
-SOURCE=.\gzio.c
-# End Source File
-# Begin Source File
-
-SOURCE=.\infblock.c
-# End Source File
-# Begin Source File
-
-SOURCE=.\infcodes.c
-# End Source File
-# Begin Source File
-
-SOURCE=.\inffast.c
-# End Source File
-# Begin Source File
-
-SOURCE=.\inflate.c
-# End Source File
-# Begin Source File
-
-SOURCE=.\inftrees.c
-# End Source File
-# Begin Source File
-
-SOURCE=.\infutil.c
-# End Source File
-# Begin Source File
-
-SOURCE=.\minigzip.c
-# End Source File
-# Begin Source File
-
-SOURCE=.\trees.c
-# End Source File
-# Begin Source File
-
-SOURCE=.\uncompr.c
-# End Source File
-# Begin Source File
-
-SOURCE=.\zutil.c
-# End Source File
-# End Group
-# End Target
-# End Project
diff --git a/gnu/usr.bin/cvs/zlib/zlib.rc b/gnu/usr.bin/cvs/zlib/zlib.rc deleted file mode 100644 index 2c0a3e4defc..00000000000 --- a/gnu/usr.bin/cvs/zlib/zlib.rc +++ /dev/null @@ -1,32 +0,0 @@ -#include <windows.h> - -#define IDR_VERSION1 1 -IDR_VERSION1 VERSIONINFO MOVEABLE IMPURE LOADONCALL DISCARDABLE - FILEVERSION 1,0,4,0 - PRODUCTVERSION 1,0,4,0 - FILEFLAGSMASK VS_FFI_FILEFLAGSMASK - FILEFLAGS 0 - FILEOS VOS_DOS_WINDOWS32 - FILETYPE VFT_DLL - FILESUBTYPE 0 // not used -BEGIN - BLOCK "StringFileInfo" - BEGIN - BLOCK "040904E4" - //language ID = U.S. English, char set = Windows, Multilingual - - BEGIN - VALUE "FileDescription", "zlib data compression library\0" - VALUE "FileVersion", "1.0.4\0" - VALUE "InternalName", "zlib\0" - VALUE "OriginalFilename", "zlib.lib\0" - VALUE "ProductName", "ZLib.DLL\0" - VALUE "Comments", "DLL support by Alessandro Iacopetti\0" - VALUE "LegalCopyright", "(C) 1995-1996 Jean-loup Gailly & Mark Adler\0" - END - END - BLOCK "VarFileInfo" - BEGIN - VALUE "Translation", 0x0409, 1252 - END -END |