home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / lzo100.zip / lzo-1.00 / doc / LZO.TXT < prev    next >
PGP Signed Message  |  1997-07-13  |  14KB  |  315 lines
  1. -----BEGIN PGP SIGNED MESSAGE-----
  2.  
  3.  
  4.  ============================================================================
  5.  LZO -- a real-time data compression library
  6.  ============================================================================
  7.  
  8.  Author  : Markus Franz Xaver Johannes Oberhumer
  9.            <markus.oberhumer@jk.uni-linz.ac.at>
  10.            http://www.infosys.tuwien.ac.at/Staff/lux/marco/lzo.html
  11.  Version : 1.00
  12.  Date    : 13-Jul-1997
  13.  
  14.  
  15.  Abstract
  16.  --------
  17.  LZO is a portable lossless data compression library written in ANSI C.
  18.  It offers pretty fast compression and very fast decompression.
  19.  Decompression requires no memory.
  20.  
  21.  In addition there are slower compression levels achieving a quite
  22.  competitive compression ratio while still decompressing at
  23.  this very high speed.
  24.  
  25.  LZO is distributed under the GNU General Public License.
  26.  
  27.  
  28.  Introduction
  29.  ------------
  30.  LZO is a data compression library which is suitable for data
  31.  de-/compression in real-time. This means it favours speed
  32.  over compression ratio.
  33.  I named it LZO standing for Lempel-Ziv-Oberhumer.
  34.  
  35.  LZO is written in ANSI C. Both the source code and the compressed
  36.  data format are designed to be portable across platforms, and LZO
  37.  should work on each architecture that has at least 32 bit integers.
  38.  Support for some popular 16 bit systems (DOS, Win 3.1) is provided
  39.  as well.
  40.  
  41.  The LZO implements a number of algorithms with the following features:
  42.  
  43.  - Decompression is simple and *very* fast.
  44.  - Requires no memory for decompression.
  45.  - Compression is pretty fast.
  46.  - Requires 64 kB of memory for compression.
  47.  - Allows you to dial up extra compression at a speed cost in the
  48.    compressor. The speed of the decompressor is not reduced.
  49.  - Includes compression levels for generating pre-compressed
  50.    data which achieve a quite competitive compression ratio.
  51.  - There is also a compression level which needs only 8 kB for compression.
  52.  - Algorithm is thread safe.
  53.  - Algorithm is lossless.
  54.  
  55.  
  56.  Design criteria
  57.  ---------------
  58.  LZO was designed with speed in mind. Decompressor speed has been
  59.  favoured over compressor speed. Real-time decompression should be
  60.  possible for virtually any application. The implementation of the
  61.  LZO1X decompressor in optimized i386 assembler code runs about at
  62.  the third of the speed of a memcpy() - and even faster for many files.
  63.  
  64.  In fact, I first wrote the decompressor of each algorithm thereby
  65.  defining the compressed data format, verified it with manually created
  66.  test data and at last added the compressor.
  67.  
  68.  
  69.  Performance
  70.  -----------
  71.  To keep you interested, here is a short overview of the average
  72.  results when compressing the (in-)famous Calgary Corpus test suite
  73.  with a blocksize of 256kB, running on an Intel i486 DX2/66.
  74.  
  75.  This release includes the 8 algorithms LZO1, LZO1A, LZO1B, LZO1C,
  76.  LZO1F, LZO1X, LZO1Y and LZO2A.
  77.  I first published LZO1 and LZO1A in the Internet newsgroups
  78.  comp.compression and comp.compression.research in March 1996.
  79.  They are mainly included for compatibility reasons. The LZO2A
  80.  decompressor is too slow, and there is no fast compressor anyway.
  81.  So the algorithms of current interest are LZO1B, LZO1C, LZO1F,
  82.  LZO1X and LZO1Y. Each of these has a slightly different characteristics,
  83.  and it seems that the LZO1X algorithm is a good overall
  84.  choice for a wide range of data.
  85.  
  86.  The naming convention of the algorithms goes LZOxx-N, where N is the
  87.  compression level. Range 1-9 indicates the fast standard levels using
  88.  64kB memory for compression. Level 99 offers better compression at the
  89.  cost of more memory (256kB), and is still reasonable fast.
  90.  Level 999 achieves nearly optimal compression - but it is slow
  91.  and uses much memory, and is mainly intended for generating
  92.  pre-compressed data.
  93.  
  94.  The C version of LZO1X-1 is about 4-5 times faster than the fastest
  95.  zlib compression level (both when compressing and decompressing).
  96.  
  97.  +--------------------------------------------------------------------+
  98.  | Algorithm       Length  CxB  ComLen  %Remn  Bits  Com K/s  Dec K/s |
  99.  | ---------       ------  ---  ------  -----  ----  -------  ------- |
  100.  | LZO1-1          224401    1  118375   53.5  4.28  1704.11  3580.56 |
  101.  |                                                                    |
  102.  | LZO1A-1         224401    1  115988   52.0  4.16  1656.07  3670.48 |
  103.  |                                                                    |
  104.  | LZO1B-1         224401    1  110653   49.6  3.97  1575.28  4411.62 |
  105.  | LZO1B-2         224401    1  107416   48.6  3.89  1451.90  4437.53 |
  106.  | LZO1B-3         224401    1  105537   47.9  3.83  1343.32  4422.70 |
  107.  | LZO1B-4         224401    1  104828   47.4  3.79  1037.02  4514.11 |
  108.  | LZO1B-5         224401    1  102724   46.7  3.73   943.35  4521.54 |
  109.  | LZO1B-6         224401    1  101210   46.0  3.68   883.91  4483.46 |
  110.  | LZO1B-7         224401    1  101388   46.0  3.68   811.64  4572.20 |
  111.  | LZO1B-8         224401    1   99453   45.2  3.62   731.56  4514.98 |
  112.  | LZO1B-9         224401    1   99118   45.0  3.60   592.89  4426.57 |
  113.  |                                                                    |
  114.  | LZO1C-1         224401    1  112051   50.2  4.02  1518.80  4392.48 |
  115.  | LZO1C-2         224401    1  108791   49.1  3.93  1416.69  4413.89 |
  116.  | LZO1C-3         224401    1  106825   48.4  3.87  1321.23  4389.14 |
  117.  | LZO1C-4         224401    1  105717   47.7  3.82  1032.84  4494.94 |
  118.  | LZO1C-5         224401    1  103605   46.9  3.76   940.19  4498.48 |
  119.  | LZO1C-6         224401    1  102585   46.5  3.72   863.84  4452.71 |
  120.  | LZO1C-7         224401    1  101937   46.2  3.70   772.97  4548.76 |
  121.  | LZO1C-8         224401    1  100779   45.6  3.65   708.72  4487.48 |
  122.  | LZO1C-9         224401    1  100252   45.4  3.63   598.06  4396.90 |
  123.  |                                                                    |
  124.  | LZO1F-1         224401    1  116765   51.5  4.12  1665.56  4805.74 |
  125.  |                                                                    |
  126.  | LZO1X-1         224401    1  110368   49.4  3.95  1601.11  4919.72 |
  127.  |                                                                    |
  128.  | LZO1-99         224401    1  101560   46.7  3.73   473.35  3643.55 |
  129.  | LZO1A-99        224401    1   99958   45.5  3.64   471.55  3692.92 |
  130.  | LZO1B-99        224401    1   95399   43.6  3.49   454.05  4461.44 |
  131.  | LZO1C-99        224401    1   97252   44.1  3.53   455.97  4447.05 |
  132.  |                                                                    |
  133.  | LZO1B-999       224401    1   83952   39.1  3.13    74.90  4651.15 |
  134.  | LZO1C-999       224401    1   87762   40.2  3.21    87.57  4714.26 |
  135.  | LZO1F-999       224401    1   89620   40.4  3.23    78.35  5466.84 |
  136.  | LZO1X-999       224401    1   84521   38.5  3.08    53.40  5203.72 |
  137.  | LZO2A-999       224401    1   87901   40.0  3.20    84.90  3208.91 |
  138.  |                                                                    |
  139.  | LZRW1-A         224401    1  123194   55.1  4.41  1564.23  3396.10 |
  140.  | LZRW2           224401    1  115399   51.5  4.12  1301.08  2379.13 |
  141.  | LZRW3           224401    1  110942   50.0  4.00  1518.32  1893.92 |
  142.  | LZRW3-A(2)      224401    1  106308   48.1  3.85  1089.16  1989.55 |
  143.  | LZRW3-A(4)      224401    1  103126   46.8  3.74   889.30  2060.22 |
  144.  | LZRW3-A(8)      224401    1  100722   45.8  3.67   607.05  2064.86 |
  145.  | LZV             224401    1  112511   51.4  4.11  1115.18  4247.76 |
  146.  | zlib-8/1        224401    1   85302   38.8  3.10   360.44  1084.91 |
  147.  | memcpy()        224401    1  224401  100.0  8.00 19992.22 20023.29 |
  148.  +--------------------------------------------------------------------+
  149.  
  150.  More detailed results can be found in the `doc' directory.
  151.  
  152.  [ These timings are from LZO 0.20 ]
  153.  
  154.  [ Multiply the values by 3 for performance on an Intel Pentium 133 ]
  155.  
  156.  [ The assembler decompressors are even faster ]
  157.  
  158.  
  159.  Short documentation
  160.  -------------------
  161.  LZO is a block compression algorithm - it compresses and decompresses
  162.  a block of data. Block size must be the same for compression
  163.  and decompression.
  164.  
  165.  LZO compresses a block of data into matches (a LZ77 sliding dictionary)
  166.  and runs of non-matching literals. LZO takes care about long matches
  167.  and long literal runs so that it produces good results on highly
  168.  redundant data and deals accecptable with non-compressible data.
  169.  
  170.  When dealing with uncompressible data, LZO expands the input
  171.  block by a maximum of 16 bytes per 1024 bytes input (probably
  172.  only by a maximum of 8 bytes, I still have to compute the exact
  173.  value).
  174.  
  175.  I have verified LZO using gcc 2.7.2 with Richard W.M. Jones's
  176.  bounds checking patches and compressed gigabytes of files when tuning
  177.  some parameters.
  178.  And I have also consulted various `lint' programs to spot potential
  179.  portability problems.
  180.  LZO is free of any known bugs.
  181.  
  182.  
  183.  The algorithms
  184.  --------------
  185.  There are (too) many algorithms implemented. But I want to support
  186.  unlimited backwards compatibility, so I will not reduce the LZO
  187.  distribution in the future (what I had planned some time ago).
  188.  
  189.  As the many object files are mostly independent of each other, the size
  190.  overhead for an executable statically linked with the LZO library
  191.  is usually pretty low cause the linker will only add the modules that
  192.  you are actually using.
  193.  
  194.  My experiments have shown that LZO1B is good with a large blocksize
  195.  or with very redundant data, LZO1F is good with a small blocksize or
  196.  with binary data and that LZO1X is often the best choice of all.
  197.  LZO1Y is almost identical to LZO1X - it can achieve a better compression
  198.  ratio on some files. LZO1F seems to compress better than LZO1C on these
  199.  files where LZO1C is better than LZO1B.
  200.  Beware, your mileage may vary.
  201.  
  202.  
  203.  Usage of the library
  204.  --------------------
  205.  Despite of its size, the basic usage of LZO is really very simple.
  206.  
  207.  Let's assume you want to compress some data with LZO1X-1:
  208.    A) compression
  209.       * include <lzo1x.h>
  210.         call lzo_init()
  211.         compress your data with lzo1x_1_compress()
  212.       * link your application with the LZO library
  213.    B) decompression
  214.       * include <lzo1x.h>
  215.         call lzo_init()
  216.         decompress your data with lzo1x_decompress()
  217.       * link your application with the LZO library
  218.  
  219.  The program examples/simple.c shows a fully working example.
  220.  See also LZO.FAQ for more information.
  221.  
  222.  
  223.  Building LZO
  224.  ------------
  225.  Beginning with version 0.21 LZO includes GNU Autoconf support,
  226.  and in 0.90 GNU Automake support was added - this should make the
  227.  building process under UNIX very unproblematic.
  228.  For detailed instructions see the file INSTALL.
  229.  
  230.  For building under DOS, Windows 3.1/95/NT or OS/2 take a look at the
  231.  file b/00readme.txt.
  232.  
  233.  Under Linux you can also build an ELF shared library by typing
  234.  'make linux-shared'. Please note that the performance of the shared
  235.  library is somewhat slower, so you'd probably want to link your
  236.  applications with the static version (liblzo.a) anyway.
  237.  [tested with Linux 2.0.29 and gcc 2.7.2.1]
  238.  
  239.  In case of troubles (like decompression data errors) try recompiling
  240.  everything without optimizations - LZO may break the optimizer
  241.  of your compiler. See the file BUGS.
  242.  
  243.  LZO is written in ANSI C. In particular this means:
  244.    - your compiler must understand prototypes
  245.    - your compiler must understand prototypes in function pointers
  246.    - your preprocessor must implement #elif, #error and stringizing
  247.    - you must have a conforming and correct <limits.h> header
  248.    - you should have size_t, ptrdiff_t, <stddef.h> and other ANSI C headers
  249.  
  250.  
  251.  Portability
  252.  -----------
  253.  I have built and tested LZO successfully on a variety of platforms
  254.  including DOS (16 + 32 bit), Windows 3.1 (16 bit), Windows 95,
  255.  Windows NT, Linux, HPUX and a DEC Alpha workstation (64 bit).
  256.  
  257.  LZO is also reported to work under AIX, IRIX, ConvexOS, SunOS,
  258.  Solaris and VxWorks.
  259.  
  260.  
  261.  The future
  262.  ----------
  263.  LZO is out for a while and it seems the library is pretty stable.
  264.  
  265.  Here is what I'm planning for the next months. No promises, though...
  266.  
  267.  - LZOP (the LZO packer, similiar to gzip) will be available soon
  268.  - improve documentation
  269.  - check if gcc optimizer problem is fixed under IRIX
  270.  - acutally use libtool to build shared libraries
  271.  - interfaces to Perl, Java and Python
  272.  - a Java version of LZO1X-1
  273.  - a stream interface (compatible to zlib) would be nice (and slow ?)
  274.  
  275.  
  276.  Some comments about the source code
  277.  -----------------------------------
  278.  Be warned: the main source code in the `src' directory is a
  279.  real pain to understand as I've experimented with hundreds of slightly
  280.  different versions. It contains many #if and some gotos, and
  281.  is completely optimized for speed and not for readability.
  282.  Code sharing of the different algorithms is implemented by stressing
  283.  the preprocessor - this can be really confusing. Lots of marcos and
  284.  assertions don't make things better.
  285.  
  286.  Nevertheless the sources compile very quiet on a variety of
  287.  compilers with the highest warning levels turned on, even
  288.  in C++ mode.
  289.  
  290.  
  291.  Copyright
  292.  ---------
  293.  LZO is Copyright (C) 1996, 1997 Markus Franz Xaver Johannes Oberhumer
  294.  
  295.  LZO is distributed under the terms of the GNU General Public License (GPL).
  296.  See the file COPYING.
  297.  
  298.  Special licenses for commercial and other applications which
  299.  are not willing to accept the GNU General Public License
  300.  are available by contacting the author.
  301.  
  302.  
  303.  
  304.  
  305. -----BEGIN PGP SIGNATURE-----
  306. Version: 2.6.3i
  307. Charset: noconv
  308.  
  309. iQCVAwUBM8jrXm10fyLu8beJAQF+PAQAyW3vmJVdfpiOteX89yRx3mLboHqk2FV6
  310. QfDnkfLhSnxqc6LT5zyOWkisDFkNjaEK7DnbhS7jg+pa3oBhHN7p8n9QrXfz7fia
  311. yzZ/1d+JCGH6Vfm0iz2xlge7a0NTanf5Y31ZpyE2UwM9UK3KCaXnBq16BJLwHRZS
  312. DxefmCzBh9k=
  313. =Z8NN
  314. -----END PGP SIGNATURE-----
  315.