Difference between revisions of "Library/Compression"
|Line 1:||Line 1:|
== Compression-2005 library ==
== Compression-2005 library ==
Latest revision as of 19:20, 27 December 2006
Compression-2005 library includes the most competitive compression libraries as of April'05:
- LZMA 4.06 by Igor Pavlov. You can download original library at http://www.7-zip.org. This library features fast extraction speed, minimal memory requirements for extraction, best compression for non-text files
- PPMd var.I by Dmitry Shkarin, http://www.compression.ru/ds. This library gives best compression for plain text files
- GRZipLib 0.2.4 by Grebnov Ilya, http://magicssoft.ru/. This library provides fastest compression while compress better than bzip2
All these libraries were assembled together by me and simple but powerful common interface to use them all was added. This interface consists of pairs of routines, which performs compression and decompression.
General compression routines
First pair of routines are 'compress' and 'decompress'. Their usage is similar:
compress method reader writer decompress method reader writer
What is the 'method' in these routines? Each compression algorithm has its own set of parameters, tuning them has effect of dramatically changing compression ratio and compression/decompression speed. To unify access to all these parameters, compression algorithm together with all it's parameters is represented by single string, such as "lzma:8mb:fast:hc4:fb32" or "grzip:8mb:m4". Each method has default parameters, which will be used unless overridden. For example, string "grzip" means using method GRZip with all default parameters, "grzip:m2" - using all default parameters, with exception that parameter "m" set to value "2", "grzip:m2:h20" means changing two parameters from their defaults and so on... Section #Description of compression methods parameters shows all the compression methods supported, their parameters and its' default values.
'reader' and 'writer' are callbacks, used by (de)compression code to read input data and write output data. Their types are identical:
reader, writer :: Ptr CChar -> Int -> IO Int
When called, 'reader' gets pointer to input buffer and its size. It must fill buffer with input data and return number of bytes read. If there is no more input data, it must return 0, if error occurred - it must return error code < 0. In the last case this error code will be returned as a result of entire call to '(de)compress' routine.
'writer', when called, gets pointer to output buffer and its size. It must write output data and return value >= 0 if all ok and error code < 0, if there is an error. In last case this code will be returned as a result of (de)compress.
For example, simplest compression program can be written just as:
let doPutBuf h buf size = do hPutBuf h buf size; return size compress "ppmd:10:48mb" (hGetBuf stdin) (doPutBuf stdout)
This program will work as compressing filter: read data from stdin, compress them and write result to stdout.
Corresponding decompressor, as you can guess:
decompress "ppmd:10:48mb" (hGetBuf stdin) (doPutBuf stdout)
Of course, under Windows you need to add "hSetBinaryMode stdin True", "hSetBinaryMode stdout True" operations to these simple programs.
Another paired routines that you can use are 'compressWithHeader' and 'decompressWithHeader'. They work just as previous ones, but name of used compression algorithm is saved in compressed output. Decompression routine just reads method name from input data instead of receiving it as a parameter. This is advantageous if data can be compressed with different algorithms or even one algorithm with different parameters, because some of these parameters are needed for decompression too. You can see example of using these functions in Example-Haskell.hs
Using callbacks to read and write data provides you ability to (de)compress data completely located in memory as well as data read/written to files, received/send to network sockets, another program or even another process in your own program. I use the last technique to get compressed on-the-fly the data generated by some complex algorithm, which is impractically to write as reader callback.
There are also some more functions - 'canonizeCompressionMethod' returns canonical representation of compression method (two methods are equal if their canonical representations are equal), and a set of low-level (de)compression routines, which calls concrete algorithms and pass all their parameters as separate numbers, for example:
ppmd_compress 10 (48*mb) 0 reader writer
will work just the same as
compress "ppmd:10:48mb:r0" reader writer
Compressing data in memory
In order to simplify simple in-memory compression, the following specialized variants of abovementioned functions are provided:
compressMem method inBuf inBufSize outBuf outBufSize
will compress data in 'inBuf' having length 'inBufSize'. Output data will be written to 'outBuf' of size 'outBufSize'. This function returns size of compressed data or negative value - error code. If output buffer is too small to hold all compressed data, then appropriate error code will be returned.
decompressMem method inBuf inBufSize outBuf outBufSize
will decompress data in 'inBuf' to 'outBuf' and return number of bytes decompressed or error code.
compressMemWithHeader method inBuf inBufSize outBuf outBufSize
works like 'compressMem' but adds description of method used to the data written to 'outBuf'.
decompressMemWithHeader inBuf inBufSize outBuf outBufSize
must be used to decompress such data.
Manipulating compression method parameters
There are a number of functions what can be used to query/modify compression method descriptions in general fashion, without respect to concrete method used. This functions can query/set memory usage for compression and decompression, dictionary size (if this have some meaning for particular compression method) and block size (also if this have a meaning). These functions are:
getCompressionMem, getDecompressionMem, getDictionary, getBlockSize :: String -> Int setCompressionMem, setDecompressionMem, setDictionary, setBlockSize :: String -> Int -> String limitCompressionMem, limitDecompressionMem, limitDictionary, limitBlockSize :: String -> Int -> String
First group of functions query appropriate parameter of compression method. For example, 'print (getDictionary "lzma:d1000")' will print '1000'.
Second group of functions sets appropriate parameter of compression method. For example, 'print (setDictionary 1000 "lzma")' will print 'lzma:1000b'.
Third group of functions limits appropriate parameter of compression method. For example, 'print (limitDictionary 1000 "lzma")' will print 'lzma:1000b', but 'print (limitDictionary (100*mb) "lzma")' will print 'lzma'.
Using these methods, you can for example limit memory required for compression:
compress (limitCompressionMem (20*mb) "lzma") reader writer
C part of library consist of modules Compression.cpp, PPMD/PPMD_Parser.cpp, PPMD/C_PPMD_Compress.cpp, PPMD/C_PPMD_Decompress.cpp, PPMD/C_LZP.cpp, LZMA/C_LZMA.cpp, LZMA/C_BCJ.cpp, GRZip/C_GRZip.cpp. All these modules can be compiled with compile[.cmd] if you have GHC or with Example-C.mak, if you have only GCC. To use other C++ compilers, make the appropriate changes in Example-C.mak. In any case, don't forget to change value of TEMPDIR in common.mak to some directory for temporaries existing on your machine.
To compile provided Example-Haskell.hs, use compile-Example-Haskell[.cmd]. This batch file also contains reference to "c:/temp/ghc", which must be changed to the same value as TEMPDIR in common.mak.
If you want to use only decompression code, exclude from above list of files PPMD/C_PPMD_Compress.cpp (all other compression methods contain both compressor and decompressor in one file) and define preprocessor macro FREEARC_DECOMPRESS_ONLY. This will compile only decompression code, which is about 4 times smaller (50 kb instead of 200 kb). Remember, that when compiling C sources with GHC, you must use "-optc-DFREEARC_DECOMPRESS_ONLY" option to define preprocessor symbol.
Also for reducing size of code you can try to turn off optimization, and exclude modules for unused compression algorithms from compilation. For example, if you want to use GRZip only, include only Compression.cpp and GRZip/C_GRZip.cpp in your compilation.
Description of compression methods parameters
I've written default value of each parameter together with it's name
o10 set model order to N
mem48mb use N MB memory. Can also be set as "m48mb" or even "48m"
r0 method of model restoration at memory insufficiency:
-r0 - restart model from scratch (default) -r1 - cut off model (slow) -r2 - freeze model (dangerous)
"r" alone is equivalent to "r1"
a1 compression mode: "a0" - fast, "a1" - normal, "a2" - max. Can also be set as "fast", "normal" and "max", appropriately
d8mb dictionary size
fb32 number of fast bytes - [3, 255]
lc3 number of literal context bits - [0, 8]
lp0 number of literal pos bits - [0, 4]
pb2 number of pos bits - [0, 4]
mfbt4 Match Finder: [bt2, bt3, bt4, bt4b, pat2r, pat2, pat2h, pat3h, pat4h, hc3, hc4]. Can also be set as "bt4". For "normal" and "max" mode most appropriate match finders are bt3, bt4, bt4b. For "fast" mode - hc3 and hc4.
m1 Selection of compression algorithm, from tightest to fastest:
m1 - LZP + BWT + WFC + EC m2 - LZP + BWT + MTF + EC m3 - LZP + ST4 + WFC + EC m4 - LZP + ST4 + MTF + EC
b8mb Maximum block size. Can be also set as "8mb" or even "8m". 8 mb is the maximum.
l32 LZP Minimum Matched Len. Can also be set as "32"
h15 LZP Hash table size, actual memory usage for hash table will be 4*2^Size bytes. Greater values increase compression ratio, but decreases speed of compression and decompression, because hash table will no more fit in Level-2 processor cache.
s Use alternative BWT Sorting algorithm (faster for repetitive blocks)
a Enable Adaptive block size reduction
l Disable LZP preprocessing. On some data (executables, plain text books) LZP preprocessor don't gives any improvements and only wastes CPU time
d Enable Delta filter
p Disable all Preprocessing techniques (LZP, Delta filter, Adaptive block size reduction). By default, all preprocessing techniques, except for LZP, are already disabled
LZP algorithm is just an LZP preprocessor from GRZip algorithm, optimized by Dmitry Shkarin. So it has the same parameters:
b8mb Maximum block size. Can be also set as "8mb" or even "8m"
l64 Minimum Matched Len. Can also be set as "64"
h18 Hash table size, actual memory usage for hash table will be 4*2^Size bytes. Greater values increase compression ratio, but decreases speed of compression and decompression, because hash table will no more fit in Level-2 processor cache.
This method just preprocess Win32 executables to allow better compression
In order to know more about how each parameter influence compression ratio, compression/decompression speed and memory usage, please download original libraries and study their documentation. LZMA parameters are best described in documentation for 7-zip, see description of "-m" option in 7-zip.chm.
Features planned for next versions
- Ability to use several compression algorithms sequentially, for example: compress "lzp+exe+lzma". This will improve compression ratio
- Passing to C compression/decompression functions additional pointers, which then will be passed in each call to reader and writer functions. It's needed to throw away using global variables in readers/writers, which will allow writing multi-thread friendly code. If you use only Haskell interfaces, this is completely not a problem for you (actually, I use this library in my own multi-threaded Haskell program)