From: jloup@chorus.fr (Jean-loup Gailly)
Newsgroups: comp.compression,news.answers
Subject: comp.compression Frequently Asked Questions (part 1/2)
Summary: *** READ THIS BEFORE POSTING ***
Keywords: data compression, FAQ
Date: 2 Oct 92 19:01:04 GMT
Expires: 10 Nov 92 16:17:20 GMT
Reply-To: jloup@chorus.fr
Followup-To: comp.compression
Supersedes: <compr1_4sep92@chorus.fr>

Archive-name: compression-faq/part1
Last-modified: Oct 2nd, 1992

		"I've already explained this once, but repetition is
		the very soul of the net."		(from alt.config)

This file is part 1 of a set of Frequently Asked Questions (FAQ) for
the groups comp.compression and comp.compression.research.  Certain
questions get asked time and again, and this is an attempt to reduce
the bandwidth taken up by these posts and their associated replies.
If you have a question, *please* check this file before you post.  It
may save a lot of peoples time.

If you have not already read the overall Usenet introductory material
posted to "news.announce.newusers", please do.

If you don't want to see this FAQ regularly, please add the
subject line to your kill file. If you have corrections or suggestions
for this FAQ, send them to Jean-loup Gailly <jloup@chorus.fr>.
Thank you.

Part 1 is oriented towards practical usage of compression programs.
Part 2 is more intended for people who want to know how compression works.

Main changes relative to the previous version: 

- added brief descriptions of all compression algorithms (item 2)
- added two patents on run length encoding (yes!) (item 8)
- added more information on other patents (item 8)
- standard images are back on eedsp.gatech.edu (item 55)
- fixed description of Shannon-Fano encoding (item 70)
- more precise pointer to MPGEG draft standard (item 71)


Contents
========

General questions:

[1]  What are these newsgroups about?
[2]  What is this .xxx file type?
     Where can I find the corresponding compression program?
[4]  What is an archiver?
[5]  What is the best general purpose compression program?
[7]  Which books should I read?
[8]  What about patents on data compression algorithms?
[9]  The WEB 16:1 compressor.
[11] What is the V.42bis standard?
[12] I need source for the winners of the Dr Dobbs compression contest
[13] I need source for arithmetic coding

Image and audio compression:

[15] Where can I get image compression programs?
[16] What is the state of the art in lossless image compression?
[17] What is the state of fractal compression?
[18] I need specs and source for TIFF and CCITT group 4 Fax.
[19] What is JPEG?
[20] I am looking for source of an H.261 codec.
[25] Fast DCT (Discrete Cosine Transform) algorithms
[26] Are there algorithms and standards for audio compression?

Common problems:

[30] My archive is corrupted!
[31] pkunzip reports a CRC error!
[32] VMS zip is not compatible with pkzip!

Questions which do not really belong to comp.compression:

[50] What is this 'tar' compression program?
[51] I need a CRC algorithm
[52] What about those people who continue to ask frequently asked questions?
[53] Where are FAQ lists archived?
[54] I need specs for graphics formats
[55] Where can I find Lenna and other images?
[56] I am looking for a message digest algorithm


(Long) introductions to data compression techniques (in part 2)

[70] Introduction to data compression (long)
       Huffman and Related Compression Techniques
       Arithmetic Coding
       Substitutional Compressors
          The LZ78 family of compressors
          The LZ77 family of compressors

[71] Introduction to MPEG (long)
       What is MPEG?
       Does it have anything to do with JPEG?
       Then what's JBIG and MHEG?
       What has MPEG accomplished?
       So how does MPEG I work?
       What about the audio compression?
       So how much does it compress?
       What's phase II?
       When will all this be finished?
       How do I join MPEG?
       How do I get the documents, like the MPEG I draft?

[72] What is wavelet theory?
[73] What is the theoretical compression limit?
[74] Introduction to JBIG

[99] Acknowledgments

Search for "Subject: [#]" to get to question number # quickly. Some news
readers can also take advantage of the message digest format used here.

If you know very little about data compression, read question 70 in
part 2 first.

------------------------------------------------------------------------------

Subject: [1] What are these newsgroups about?


comp.compression is the place to discuss about data compression, both
lossless (for text or data) and lossy (for images, sound, etc..).
comp.compression.research was created later to provide a forum for
current research on data compression and data compression algorithms.
If you are not experienced in data compression, please post in
comp.compression only.

If you only want to find a particular compression program for a
particular operating system, please read first this FAQ and the
article "How to find sources" which is regularly posted in
news.answers.

If you can't resist posting such a request, other groups are probably
more appropriate (comp.binaries.ibm.pc.wanted, comp.sources.wanted,
comp.sys.mac.wanted, alt.graphics.pixutils). Please post your request
in comp.compression only as a last resource.

Please do not post any program in binary form to comp.compression.
Very short sources can be posted, but long sources should be be posted
to the specialized source groups, such as comp.sources.* or alt.sources.

------------------------------------------------------------------------------

Subject: [2] What is this .xxx file type?
             Where can I find the corresponding compression program?


All the programs mentioned in this section are lossless.
For most programs, one US and one European ftp site are given.
(wuarchive.wustl.edu: 128.152.135.4, garbo.uwasa.fi: 128.214.87.1)
Many other sites (in particular wsmr-simtel20.army.mil: 192.88.110.2)
have the same programs.

To keep this list to a reasonable size, many programs are not
mentioned here. Additional information can be found in the file
ux1.cso.uiuc.edu:/doc/pcnet/compression [128.174.5.59] maintained by
David Lemson (lemson@uiuc.edu). When several programs can handle
the same archive format, only one of them is given.

For Macintosh programs, look on sumex-aim.stanford.edu:/info-mac [36.44.0.6].
For VM/CMS, look on vmd.cso.uiuc.edu:/public.477 [128.174.5.98].
For Atari, look on terminator.cc.umich.edu:/atari/archivers [141.211.164.8]
For Amiga, look on ux1.cso.uiuc.edu:/pub/amiga [128.174.5.59]
	
If you don't know how to use ftp or don't have ftp access, read the
article "How to find sources" which is regularly posted in news.answers.

If you can't find a program given below, it is likely that a newer
version exists in the same directory. (Tell me <jloup@chorus.fr>)

A very short description of the compression algorithm is given for
most programs. For the meaning of LZ77, LZ78 and LZW, see question 
70 in part 2 of the FAQ.)

ext:  produced by or read by

.arc: arc, pkarc for MSDOS. (LZW algorithm)
	wuarchive.wustl.edu:/mirrors/msdos/starter/pk361.exe
	garbo.uwasa.fi:/pc/arcers/pk361.exe

      arc for Unix
        wuarchive.wustl.edu:/mirrors/misc/unix/arc521e.tar-z
	garbo.uwasa.fi:/unix/arcers/arc.tar.Z
        Contact: Howard Chu <hyc@umix.cc.umich.edu>

      arc for VMS
	wuarchive.wustl.edu:/packages/compression/vax-vms/arc.exe

      arcmac for Mac
	mac.archive.umich.edu:/mac/utilities/compressionapps/arcmac.hqx

.arj: arj for MSDOS (LZ77 with hashing, plus secondary static Huffman
          encoding on a block basis)
        Contact: Robert K Jung <robjung@world.std.com>
        wuarchive.wustl.edu:/mirrors/msdos/arc-lbr/arj230.exe
	garbo.uwasa.fi:/pc/arcers/arj230ng.exe

      unarj for Unix. There is *no* arj for Unix. Don't post a request.
        wuarchive.wustl.edu:/mirrors/misc/unix/unarj230.tar-z
	garbo.uwasa.fi:/unix/arcers/unarj230.tar.Z

      unarj for Mac
        mac.archive.umich.edu:/mac/util/compression/unarjmac.cpt.hqx      

.cpt: Compact Pro for Mac
        sumex-aim.stanford.edu:/info-mac/util/compact-pro-132.hqx [36.44.0.6]

.gif: gif files are images compressed with the LZW algorithm. See the
      comp.graphics FAQ list for programs manipulating .gif files. See
      suffix .Z below for source of LZW.

.hqx: Macintosh BinHex format. (binhex is *not* a compression program, BTW.)
       for Mac:
	 mac.archive.umich.edu:/mac/utilities/compressionapps/binhex4.0.bin

       for Unix:
         sumex-aim.stanford.edu:/info-mac/unix/mcvert-165.shar [36.44.0.6]

.lzh: lha for MSDOS (LZ77 with a trie data structure, plus secondary static
          Huffman coding on a block basis)
	wuarchive.wustl.edu:/mirrors/msdos/arc-lbr/lha213.exe
	garbo.uwasa.fi:/pc/arcers/lha213.exe

      lharc for Unix. (LZ77 with hash table and binary trees, plus secondary
          Huffman coding)
           Warning: lharc can extract .lzh files created by
           lharc 1.xx but not those created by lha. See lha for Unix below.
        wuarchive.wustl.edu:/mirrors/misc/unix/lharc102a.tar-z
	garbo.uwasa.fi:/unix/arcers/lharcsrc.zoo

      lha for Unix. Warning: all doc is in Japanese.
        grind.isca.uiowa.edu:/unix/arc-progs/lha-1.00.tar.Z
	garbo.uwasa.fi:/unix/arcers/lha-1.00.tar.Z
          Contact: lha-admin@oki.co.jp

      lha for Mac
        mac.archive.umich.edu:/mac/utilities/compressionapps/maclha2.0.cpt.hqx

      lharc for VMS. Same warning as for Unix lharc.
	wuarchive.wustl.edu:/packages/compression/vax-vms/lharc.exe

.pak: pak for MSDOS (LZW algorithm)
        wuarchive.wustl.edu:/mirrors/msdos/arc-lbr/pak251.exe
	garbo.uwasa.fi:/pc/arcers/pak251.exe

.pit: PackIt (Macintosh)
       for Mac:
         sumex-aim.stanford.edu:/info-mac/util/stuffit-151.hqx  [36.44.0.6]

       for Unix:
         sumex-aim.stanford.edu:/info-mac/unix/mcvert-165.shar [36.44.0.6]

.sea: self-extracting archive (Macintosh)
         Run the file to extract it. The self-extraction code can be
         removed with:
 	 mac.archive.umich.edu:/mac/utilities/compressionapps/desea1.11.cpt.hqx

.sit: Stuffit for Macintosh
       for Mac:
         sumex-aim.stanford.edu:/info-mac/util/stuffit-lite-30.hqx [36.44.0.6]

       for Unix:
         sumex-aim.stanford.edu:/info-mac/unix/unsit-15.shar [36.44.0.6]

.tar: tar is *not* a compression program. However, to be kind for you:
      for MSDOS
	wuarchive.wustl.edu:/mirrors/msdos/starter/tarread.exe
	garbo.uwasa.fi:/pc/unix/tar4dos.zoo

      for Unix
        tar (you have it already. To extract: tar xvf file.tar)

      for VMS
	wuarchive.wustl.edu:/packages/compression/vax-vms/tar.exe

      for Macintosh
        sumex-aim.stanford.edu:/info-mac/util/tar-30.hqx

.tar.Z, .tar-z, .taz: tar + compress
      For Unix: zcat file.tar.Z | tar xvf -
      Other OS: first uncompress (see .Z below) then untar (see .tar above)

.zip: pkzip 1.10 for MSDOS. (LZ77 with hashing, plus secondary static
          Shannon-Fano encoding on whole file)
           Contact: pkware.inc@mixcom.com
         wuarchive.wustl.edu:/mirrors/msdos/zip/pkz110eu.exe.
         garbo.uwasa.fi:/pc/arcers/pkz110eu.exe.
           Note: pkz110eu.exe is an 'export' version without encryption.

      pkzip 1.93a for MSDOS. (LZ77 with hashing, plus secondary static
           Huffman coding on a block basis)
        Note: pkzip 1.93a is an alpha version.
	From the PKWARE BBS (June 92): "PKZIP 2.0 is expected to be released
            sometime in the next few months, as soon as possible".
         ux1.cso.uiuc.edu:/pc/exec-pc/pkz193a.exe [128.174.5.59]
           pkz201.exe is a hacked (illegal) copy of pkz193a.exe
           pkz220.exe is also a hack and destroys your hard disk

      zip 1.9p1 and unzip 5.0 for Unix, MSDOS, VMS, OS/2, Atari, Mac, ...
          Compatible with pkzip 1.93a (LZ77 with hashing, plus secondary static
          Huffman coding on a block basis)
            Contact: zip-bugs@cs.ucla.edu
	 oak.oakland.edu:/pub/msdos/zip/zip19p1.zip  (source)
	 oak.oakland.edu:/pub/msdos/zip/zip19p1x.zip (MSDOS exe)
	 oak.oakland.edu:/pub/msdos/zip/unzip50.zip  (source)
	 oak.oakland.edu:/pub/misc/unix/unzip50.tar-z (tar.Z source)
	 oak.oakland.edu:/pub/msdos/zip/unzip50.exe  (MSDOS exe)
         wuarchive.wustl.edu:/mirrors/garbo.uwasa.fi/arcutil/zcrypt19.zip
         (encryption source. Non US residents must get it from garbo,see below)

	 garbo.uwasa.fi:/unix/arcers/zip19p1.zip
	 garbo.uwasa.fi:/unix/arcers/unzip50.tar.Z.
         garbo.uwasa.fi:/pc/arcutil/zcrypt19.zip (encryption code)

.zoo: zoo 2.10 for MSDOS (algorithm copied from that of lha, see lha above)
	 wuarchive.wustl.edu:/mirrors/msdos/zoo/zoo210.exe
	 garbo.uwasa.fi:/pc/arcers/zoo210.exe

      zoo 2.10 for Unix, VMS
         wsmr-simtel20.army.mil:pd8:<misc.unix>zoo210.tar-z [192.88.110.2]
	 garbo.uwasa.fi:/unix/arcers/zoo210.tar.Z

      zoo for Mac
 	 mac.archive.umich.edu:/mac/utilities/compressionapps/maczoo.sit.hqx

      Contact: Rahul Dhesi <dhesi@cirrus.com>

.F: freeze for Unix (LZ77 with hashing, plus secondary dynamic Huffman
         encoding)
     wuarchive.wustl.edu:/usenet/comp.sources.misc/volume25/freeze/part0[1-2].Z
     ftp.inria.fr:/system/arch-compr/freeze-2.3.4.tar.Z
     Contact: Leonid A. Broukhis <leo@s514.ipmce.su>

.Y: yabba for Unix, VMS, ... (Y coding, a variant of LZ78)
  wuarchive.wustl.edu:/usenet/comp.sources.unix/volume24/yabbawhap/part0[1-4].Z
  ftp.inria.fr:/system/arch-compr/yabba.tar.Z
  Contact: Dan Bernstein <brnstnd@nyu.edu>

.Z: compress for Unix ('the' LZW algorithm)
      It is likely that your Unix system has 'compress' already. Otherwise:
	wuarchive.wustl.edu:/packages/compression/compress-4.1.tar
        (not in .Z format to avoid chicken and egg problem)

    compress for MSDOS
	wuarchive.wustl.edu:/mirrors/msdos/compress/comp430[ds].zip
	garbo.uwasa.fi:/pc/unix/comp430d.zip

    compress for Macintosh
        sumex-aim.stanford.edu:/info-mac/util/maccompress-32.hqx

------------------------------------------------------------------------------

Subject: [4] What is an archiver?


There is a distinction between archivers and other compression
programs:

- an archiver takes several input files, compresses them and produces
  a single archive file. Examples are arc, arj, lha, zip, zoo.

- other compression programs create one compressed file for each
  input file. Examples are freeze, yabba, compress. Such programs
  are often combined with tar to create compressed archives (see
  question 50: "What is this tar compression program?").

------------------------------------------------------------------------------

Subject: [5] What is the best general purpose compression program?


The answer is: it depends. (You did not expect a definitive answer,
did you?)

It depends whether you favor speed, compression ratio, a standard and
widely used archive format, the number of features, etc...  Just as
for text editors, personal taste plays an important role. compress has
4 options, arj 2.30 has about 130 options; different people like
different programs. *Please* do not start or continue flame wars on
such matters of taste.

The only objective comparisons are speed and compression ratio. Here
is a short table comparing various programs on a 33Mhz Compaq 386.
All programs have been run on Unix SVR4, except pkzip and arj which
only run on MSDOS.  Detailed benchmarks have been posted in
comp.compression by Peter Gutmann <pgut1@cs.aukuni.ac.nz>.

*Please* do not post your own benchmarks made on your own files that
nobody else can access. If you think that you must absolutely post yet
another benchmark, make sure that your test files are available by
anonymous ftp.

The programs compared here were chosen because they are the most popular
or because they run on Unix and source is available.  For ftp
information, see above. Two programs (hpack and comp-2) have been added
because they achieve better compression (at the expense of speed)
and one program (lzrw3-a) has been added because it favors speed at
the expense of compression:
- comp-2 is in wuarchive.wustl.edu:/mirrors/msdos/ddjmag/ddj9102.zip
  (inner zip file nelson.zip),
- hpack is in wuarchive.wustl.edu:/mirrors/misc/unix/hpack75a.tar-z
  and garbo.uwasa.fi:/unix/arcers/hpack75a.tar.Z
- sirius.ucs.adelaide.edu.au:/pub/compression/lzrw3-a.c  [129.127.40.3]

The 14 files used in the comparison are from the standard Calgary
Text Compression Corpus, available by ftp on fsa.cpsc.ucalgary.ca [136.159.2.1]
in /pub/text.compression.corpus/text.compression.corpus.tar.Z.

The whole corpus includes 18 files, but the 4 files paper[3-6] are
generally omitted in benchmarks. It contains several kinds of file
(ascii, binary, image, etc...) but has a bias towards large files.
You may well get different ratings on the typical mix of files that
you use daily, so keep in mind that the comparisons given below are
only indicative.

The programs are ordered by decreasing total compressed size. For a
fair comparison between archivers and other programs, this size is
only the size of the compressed data, not the archive size.

The programs were run on an idle machine, so the elapsed time
is significant and can be used to compare Unix and MSDOS programs.

[Note: I still have to add all decompression times.]

       size     lzrw3a   compress    lharc    yabba     pkzip    freeze 
version:                   4.0       1.02      1.0       1.10     2.3.5
options:                                    -m300000                    
       ------    -----    ------    ------    ------    ------   ------
bib    111261    49040     46528     46502     40456     41354    41515 
book1  768771   416131    332056    369479    306813    350560   344793 
book2  610856   274371    250759    252540    229851    232589   230861 
geo    102400    84214     77777     70955     76695     76172    68626 
news   377109   191291    182121    166048    168287    157326   155783 
obj1    21504    12647     14048     10748     13859     10546    10453 
obj2   246814   108040    128659     90848    114323     90130    85500 
paper1  53161    24522     25077     21748     22453     20041    20021 
paper2  82199    39479     36161     35275     32733     32867    32693 
pic    513216   111000     62215     61394     65377     63805    53291 
progc   39611    17919     19143     15399     17064     14164    14143 
progl   71646    24358     27148     18760     23512     17255    17064 
progp   49379    16801     19209     12792     16617     11877    11686 
trans   93695    30292     38240     28092     31300     23135    22861 
    3,141,622  1,400,105 1,259,141 1,200,580 1,159,340 1,141,821 1,109,290
real             0m35s     0m59s     5m03s     2m40s              5m27s
user             0m25s     0m29s     4m29s     1m46s              4m58s
sys              0m05s     0m10s     0m07s     0m18s              0m08s
MSDOS:                                                   1m39s
                        

         zoo       lha       arj      pkzip      zip      hpack   comp-2   
        2.10    1.0(Unix)   2.30      1.93a      1.9      0.75a      
         ah    2.13(MSDOS)   -jm       -ex        -6                         
       ------    ------    ------    ------    -------   ------   ------
bib     40742     40740     36090     35186      34950    35619    29840  
book1  339076    339074    318382    313566     312619   306876   237380  
book2  228444    228442    210521    207204     206306   208486   174085  
geo     68576     68574     69209     68698      68418    58976    64590  
news   155086    155084    146855    144954     144395   141608   128047  
obj1    10312     10310     10333     10307      10295    10572    10819  
obj2    84983     84981     82052     81213      81336    80806    85465  
paper1  19678     19676     18710     18519      18525    18607    16895  
paper2  32098     32096     30034     29566      29674    29825    25453  
pic     52223     52221     53578     52777      55051    51778    55461  
progc   13943     13941     13408     13363      13238    13475    12896  
progl   16916     16914     16408     16148      16175    16586    17354  
progp   11509     11507     11308     11214      11182    11647    11668  
trans   22580     22578     20046     19808      18879    20506    21023  
      1,096,166 1,096,138 1,036,934 1,022,523 1,021,043 1,005,367  890,976
real    4m07s     6m03s                         1m49s   1h22m17s  27m05s
user    3m47s     4m23s                         1m43s   1h20m46s  19m27s
sys     0m04s     0m08s                         0m02s      0m12s   2m03s
MSDOS:            1m49s     2m41s     1m55s

Notes:

- the compressed data for 'zoo ah' is always two bytes longer than for
  lha. This is simply because both programs are derived from the same
  source (ar002, written by Haruhiko Okumura).

- hpack 0.75a gives slightly different results on SunOS (undeterministic
  behaviour still under investigation).

- the MSDOS versions are all optimized with assembler code and were run
  on a RAM disk. So it is not surprising that they often go faster than
  their Unix equivalent.

------------------------------------------------------------------------------

Subject: [7] Which books should I read?


[BWC 1989] Bell, T.C, Witten, I.H, and Cleary, J.G.  "Text Compression",
    Prentice-Hall 1989. ISBN: 0-13-911991-4. Price: approx. US$40
    The reference on text data compression.

[Nel 1991] Mark Nelson, "The Data Compression Book"
    M&T Books, Redwood City, CA, 1991.  ISBN 1-55851-216-0.
    Price $36.95 including two 5" PC-compatible disks bearing
    all the source code printed in the book.
    A practical introduction to data compression.
    The book is targeted at a person who is comfortable reading C code but
    doesn't know anything about data compression.  Its stated goal is to get
    you up to the point where you are competent to program standard
    compression algorithms.

[Will 1990] Williams, R.  "Adaptive Data Compression", Kluwer Books, 1990.
    ISBN: 0-7923-9085-7. Price: US$75.
    Reviews the field of text data compression and then addresses the
    problem of compressing rapidly changing data streams.

[Stor 1988] Storer, J.A.  "Data Compression: Methods and Theory", Computer
    Science Press, Rockville, MD. ISBN: 0-88175-161-8.
    A survey of various compression techniques, mainly statistical
    non-arithmetic compression and LZSS compression.  Includes complete Pascal
    code for a series of LZ78 variants.

[ACG 1991] Advances in Speech Coding, edited by Atal, Cuperman, and Gersho,
    Kluwer Academic Press, 1991.

[GG 1991] Vector Quantization and Signal Compression, by Gersho and Gray,
    Kluwer Acad. Press, 1991

[CT 1991] Elements of Information Theory, by T.M.Cover and J.A.Thomas
     John Wiley & Sons, 1991.

Review papers:

[BWC 1989] Bell, T.C, Witten, I.H, and Cleary, J.G.  "Modeling for Text
    Compression", ACM Computing Surveys, Vol.21, No.4 (December 1989), p.557
    A good general overview of compression techniques (as well as modeling for
    text compression); the condensed version of "Text Compression".

[Lele 1987] Lelewer, D.A, and Hirschberg, D.S.  "Data Compression", ACM
    Computing Surveys, Vol.19, No.3 (September 1987), p.261.
    A survey of data compression techniques which concentrates on Huffman
    compression and makes only passing mention of other techniques.


------------------------------------------------------------------------------

Subject: [8] What about patents on data compression algorithms?


[Note: the appropriate group for discussing software patents is
comp.patents (or misc.legal.computing), not comp.compression.]

All patents mentioned here are US patents, and thus probably
not applicable outside the US. See item 70, "Introduction to data
compression" for the meaning of LZ77, LZ78 or LZW.


(a) Run length encoding

- Tsukiyama has two patents on run length encoding: 4,586,027 and 4,872,009
  granted in 1986 and 1989 respectively. The first one covers run length
  encoding in its most primitive form: a length byte followed by the
  repeated byte. The second patent covers the 'invention' of limiting the
  run length to 16 bytes and thus the encoding of the length on 4 bits.
  Here is the start of claim 1 of patent 4,872,009, just for pleasure:

    1. A method of transforming an input data string comprising a plurality
    of data bytes, said plurality including portions of a plurality of
    consecutive data bytes identical to one another, wherein said data
    bytes may be of a plurality of types, each type representing different
    information, said method comprising the steps of: [...]


(b) LZ77

- The Gibson & Graybill patent 5,049,881 covers the LZRW1 algorithm
  previously discovered by Ross Williams. (See item 5 for the ftp site
  with all LZRW derivatives). Claims 4 and 12 are very general and
  could be interpreted as applying to any LZ algorithm using hashing
  (including all variants of LZ78):

     4. A compression method for compressing a stream of input data into
     a compressed stream of output data based on a minimum number of
     characters in each input data string to be compressed, said
     compression method comprising the creation of a hash table, hashing
     each occurrence of a string of input data and subsequently searching
     for identical strings of input data and if such an identical string
     of input data is located whose string size is at least equal to the
     minimum compression size selected, compressing the second and all
     subsequent occurrences of such identical string of data, if a string
     of data is located which does not match to a previously compressed
     string of data, storing such data as uncompressed data, and for each
     input strings after each hash is used to find a possible previous
     match location of the string, the location of the string is stored
     in the hash table, thereby using the previously processed data to
     act as a compression dictionary.

  Claim 12 is identical, with 'method' replaced with 'apparatus'.
  Since the 'minimal compression size' can be as small as 2, the claim
  could cover any dictionary technique of the LZ family. However the
  text of the patent and the other claims make clear that the patent 
  should cover the LZRW1 algorithm only.

  The following papers, published before the patent was filed, describe
  various applications of hashing to LZ77 compression:

    Brent, R.P.  "A Linear Algorithm for Data Compression", Australian
    Computer Journal, Vol.19, No.2 (May 1987), p.64.

    Raita, T. and Teuhola, J. (1987), "Predictive text compression by hashing",
    ACM Conference on Information Retrieval, New Orleans.

    Bell, T. "Longest match string searching for Ziv-Lempel compression"
    Res. Rept. 6/89, Dept. of Computer Science, Univ. of Canterbury,
    New Zealand (Feb 89).


- Phil Katz, author of pkzip, also has a patent on LZ77 (5,051,745)
  but the claims only apply to sorted hash tables, and when the hash
  table is substantially smaller than the window size.

- Robert Jung, author of 'arj', has recently been granted patent 5,140,321
  for one variation of LZ77 with hashing.  This patent covers the LZRW3-A
  algorithm, also previously discovered by Ross Williams. LZRW3-A was posted
  on comp.compression on July 15, 1991. The patent was filed two months later
  on Sept 4, 1991. (The US patent system allows this because of the
  'invention date' rule.)

- Fiala and Greene have a patent (4,906,991) on the algorithms they
  published in Comm.ACM, April 89. The patent covers the algorithms used
  in lharc, lha and zoo. It is very similar to the Eastman-Lempel-Ziv
  patent 4,464,650 (LZ77 with a trie data structure) but much more general.
  (There are 244 specific claims in the Eastman patent, only 7 in the
  Fiala patent.)

- IBM patented (5,001,478) the idea of combining a history buffer (the
  LZ77 technique) and a lexicon (as in LZ78).


(c) LZ78

- The LZW algorithm used in 'compress'is patented by IBM (4,814,746)
  and Unisys (4,558,302). It is also used in the V.42bis compression
  standard (see question 11 on V.42bis below) and in Postscript Level 2.
  (Unisys sells the license to modem manufacturers for a onetime
  $25,000 fee.) The IBM patent application was filed three weeks
  before that of Unisys, but the US patent office failed to recognize
  that they covered the same algorithm. (The IBM patent is more
  general, but its claim 7 is exactly LZW.)

- AP coding is patented by Storer (4,876,541). (Get the yabba package
  for source code, see question 2 above, file type .Y)


(d) other data compression algorithms

- IBM holds a patent on the Q-coder implementation of arithmetic
  coding.  The arithmetic coding option of the JPEG standard requires
  use of the patented algorithm.  No JPEG-compatible method is
  possible without infringing the patent, because what IBM actually
  claims rights to is the underlying probability model (the heart of
  an arithmetic coder). (See the JPEG FAQ for details.)

- Bacon has patented (4,612,532) some from of Markov modeling.


As can be seen from the above list, *all* the most popular compression
programs (compress, pkzip, zoo, lha, arj) are now covered by patents.


Here are some references on data compression patents. A number of them are
taken from the list maintained by Michael Ernst <mernst@theory.lcs.mit.edu>
in mintaka.lcs.mit.edu:/mitlpf/ai/patent-list (or patent-list.Z).

4,464,650
Apparatus and method for compressing data signals and restoring the
compressed data signals
inventors Lempel, Ziv, Cohn, Eastman
assignees Sperry Corporation and At&T Bell Laboratories
filed 8/10/81, granted 8/7/84

4,558,302
High speed data compression and decompression apparatus and method
inventor Welch
assignee Sperry Corporation (now Unisys)
filed 6/20/83, granted 12/10/85
The text for this patent can be ftped from rusmv1.rus.uni-stuttgart.de
(129.69.1.12) in /info/comp.patents/US4558302.Z.

4,612,532
inventor Bacon
granted 9/1986

4,814,746
Data compression method
inventors Victor S. Miller, Mark N. Wegman
assignee IBM
filed 8/11/86, granted 3/21/89
A previous application was filed on 6/1/83, three weeks before the
application by Welch (4,558,302)

4,876,541
Stem [sic] for dynamically compressing and decompressing electronic data
inventor James A. Storer
assignee Data Compression Corporation
filed 10/15/87, granted 10/24/89

4,955,066
Compressing and Decompressing Text Files
inventor Notenboom, L.A.
assignee Microsoft
filed  10/13/89, granted 09/04/90

5,001,478
Method of Encoding Compressed Data
filed 12/28/89, granted 03/19/91
inventor Michael E. Nagy
assignee IBM

5,049,881
Apparatus and method for very high data rate-compression incorporating
lossless data compression and expansion utilizing a hashing technique
inventors Dean K. Gibson, Mark D. Graybill
assignee Intersecting Concepts, Inc.
filed 6/18/90, granted 9/17/91

5,051,745
String searcher, and compressor using same
inventor  Phillip W. Katz (author of pkzip)
filed  8/21/90, granted 9/24/91

4,906,991
Textual substitution data compression with finite length search window
inventors Fiala,E.R., and Greene,D.H.
filed 4/29/1988, granted 3/6/1990
assignee Xerox Corporation

5,140,321
Data compression/decompression method and apparatus
filed 9/4/91, granted 8/18/92
inventor Robert Jung
assignee Prime Computer

------------------------------------------------------------------------------

Subject: [9]  The WEB 16:1 compressor.


[WARNING: this topic has generated the greatest volume of news in the
history of comp.compression. Read this before posting on this subject.]


(a) What the press says

April 20, 1992  Byte Week Vol 4. No. 25:

   "In an announcement that has generated high interest - and more than a
   bit of skepticism - WEB Technologies (Smyrna, GA) says it has
   developed a utility that will compress files of greater than 64KB in
   size to about 1/16th their original length.  Furthermore, WEB says its
   DataFiles/16 program can shrink files it has already compressed."
   [...]
   "A week after our preliminary test, WEB showed us the program successfully
   compressing a file without losing any data.  But we have not been able
   to test this latest beta release ourselves."
   [...]
   "WEB, in fact, says that virtually any amount of data can be squeezed 
   to under 1024 bytes by using DataFiles/16 to compress its own output
   multiple times."

June 1992 Byte, Vol 17 No 6:

   [...] According to Earl Bradley, WEB Technologies' vice president of
   sales and marketing, the compression algorithm used by DataFiles/16
   is not subject to the laws of information theory. [...]


(b) First details, by John Wallace <buckeye@spf.trw.com>:

I called WEB at (404)514-8000 and they sent me some product
literature as well as chatting for a few minutes with me on the phone.
Their product is called DataFiles/16, and their claims for it are
roughly those heard on the net.

According to their flier:

"DataFiles/16 will compress all types of binary files to approximately
one-sixteenth of their original size ... regardless of the type of
file (word processing document, spreadsheet file, image file,
executable file, etc.), NO DATA WILL BE LOST by DataFiles/16."
(Their capitalizations; 16:1 compression only promised for files >64K
bytes in length.)

"Performed on a 386/25 machine, the program can complete a
compression/decompression cycle on one megabyte of data in less than
thirty seconds"

"The compressed output file created by DataFiles/16 can be used as the 
input file to subsequent executions of the program.  This feature of 
the utility is known as recursive or iterative compression, and will 
enable you to compress your data files to a tiny fraction of the 
original size.  In fact, virtually any amount of computer data can 
be compressed to under 1024 bytes using DataFiles/16 to compress its 
own output files muliple times.  Then, by repeating in reverse the 
steps taken to perform the recusive compression, all original data 
can be decompressed to its original form without the loss of a single 
bit."

They had a table that showed the expected size of resulting files,
with the warning that "Your actual compresion results may vary
slightly from the figures shown".  Here is my abridged version of their
table. 
		---------- Iteration -------
INPUT		1	2	3 	4		Ratio
1K		630					1.6:1
16K		1.5K	812				20:1
64K		4K	1K	644			101:1
512K		30K	2K	938			558:1
8M		490K	14K	1.5K	798		10512:1
64M		3M	40K	3K	994		67513:1

Their flier also claims: 

"Constant levels of compression across ALL TYPES of FILES"
"Convenient, single floppy DATA TRANSPORTATION"

From my telephone conversation, I was was assured that this is an
actual compression program.  Decompression is done by using only the 
data in the compressed file; there are no hidden or extra files.


(c) More information, by Rafael Ramirez <rafael.ramirez@channel1.com>:

   Today (Tuesday, 28th) I got a call from Earl Bradley of Web
who now says that they have put off releasing a software version of
the algorithm because they are close to signing a major contract with
a big company to put the algorithm in silicon.  He said he could not
name the company due to non-disclosure agreements, but that they had
run extensive independent tests of their own and verified that the
algorithm works. [...]

   Mr. Bradley went on to say that Web will not be sending out any
more copies to magazines and that they had even recalled the copy they
had sent to Byte.  He claimed that he told the guy at Byte that the
version they had at the time had just been translated to assembler and
had some bugs, but that the guy at Byte kept insisting that they send
a copy anyway, and so of course the version Byte had didn't work.

[Correction from Russ Schnapp <rschnapp@metaflow.com>:
Contrary to WEB's claim, I did NOT insist that WEB send me a
non-functional copy of the program. I didn't even ask for the latest
version.]

He said the algorithm is so simple that he doesn't want anybody
getting their hands on it and copying it even though he said they
have filed a patent on it. [...] Mr. Bradley said the silicon version
would hold up much better to patent enforcement and be harder to copy.

   He claimed that the algorithm takes up about 4K of code, uses only
integer math, and the current software implementation only uses a 65K
buffer.  He said the silicon version would likely use a parallel
version and work in real-time.

   He said they will be sending out copies to about seven companies
that want to license the technology for various applications but he
could not give out any names due to non-disclosure agreements.  He
hoped that in about two weeks he will be able to make an announcement
and said he would call me when he could provide independent
verification that the algorithm works.  For now, we can only wait.

   He also said they have not as yet sold anything, but that he's
been traveling constantly for the last three weeks (presumably to
the seven companies he mentioned) and that he hasn't slept very
well lately just thinking about all the applications the algorithm
could be applied to.

   And he confirmed that each pass will get 16:1 compression as
long as the data is >64K, and that regardless, any file should be
able to be compressed to less than 1024 bytes after enough passes.
I asked if he is claiming that they can compress ANY data including
data that is already compressed, and he just answered by saying
that they had tested the program by compressing PKZIP files, and
other files and that they all compressed as claimed (which of course
still doesn't answer the question).


(d) The impossiblity proofs.

It is impossible for a given program to compress without loss *all*
files greater than a certain size by at least one bit. This can be
proven by a simple counting argument. (Many other proofs have been
posted on comp.compression, *please* do not post yet another one.)

Assume that the program can compress without loss all files of size >= N
bits.  Compress with this program all the 2^N files which have
exactly N bits.  All compressed files have at most N-1 bits, so there
are at most (2^N)-1 different compressed files [2^(N-1) files of size
N-1, 2^(N-2) of size N-2, and so on, down to 1 file of size 0]. So at
least two different input files must compress to the same output file.
Hence the compression program cannot be lossless. (Stronger results
about the number of incompressible files can be obtained, but the
proofs are a little more complex.)

This argument applies of course to WEB's case (take N = 64K*8 bits).
Note that no assumption is made about the compression algorithm.
The proof applies to *any* algorithm, including those using an
external dictionary, or repeated application of another algorithm,
or combination of different algorithms, or representation of the
data as formulas, etc... All schemes are subject to the counting argument.
There is no need to use information theory to provide a proof, just
basic mathematics.

This assumes of course that the information available to the decompressor
is only the bit sequence of the compressed data. If external information
such as a file name or a number of iterations is necessary to decompress
the data, the bits providing the extra information must be included in
the bit count of the compressed data. (Otherwise, it would be sufficient
to consider any input data as a number, use this as the iteration
count or file name, and pretend that the compressed size is zero.)

[See also question 73 "What is the theoretical compression limit?" in
part 2 of this FAQ.]


(e) No software version

Appeared on BIX, reposted by Bruce Hoult <Bruce.Hoult@actrix.gen.nz>:

tojerry/chaos #673, from abailey, 562 chars, Tue Jun 16 20:40:34 1992
Comment(s). 
----------
TITLE: WEB Technology
I promised everyone a report when I finally got the poop on WEB's
16:1 data compression. After talking back and forth for a year
and being put off for the past month by un-returned phone calls,
I finally got hold of Marc Spindler who is their sales manager.
 
_No_ software product is forth coming, period!
 
He began talking about hardware they are designing for delivery
at the end of the year. [...]


(f) Product cancelled

Posted by John Toebes <toebes@bnr.ca> on Aug 10th, 1992:

[Long story omitted, confirming the reports made above about the
original WEB claims.]

10JUL92 - Called to Check Status.  Was told that testing had uncovered a
          new problem where 'four numbers in a matrix were the same
          value' and that the programmers were off attempting to code a
          preprocessor to eliminate this rare case.  I indicated that he
          had told me this story before.  He told me that the
          programmers were still working on the problem.

31JUL92 - Final Call to Check Status.  Called Earl in the morning and
          was told that he still had not heard from the programmers. [...]
          Stated that if they could not resolve the problem then there would
          probably not be a product.

03AUG92 - Final Call.  Earl claims that the programmers are unable to
          resolve the problem.  I asked if this meant that there would
          not be a product as a result and he said yes.


(g) Conclusion

The last report given above should put an end to the WEB story.

[Note from the FAQ maintainer: I will keep this long story in the FAQ
for a while, and will remove it when the dust has finally settled
down.]

------------------------------------------------------------------------------

Subject: [11] What is the V.42bis standard?


from Alejo Hausner <hausner@qucis.queensu.ca>:

The V.42bis Compression Standard was proposed by the International
Consultative Committee on Telephony and Telegraphy (CCITT) as an
addition to the v.42 error-correction protocol for modems. Its purpose
is to increase data throughput, and uses a variant of the
Lempel-Ziv-Welch (LZW) compression method.  It is meant to be
implemented in the modem hardware, but can also be built into the
software that interfaces to an ordinary non-compressing modem.

V.42bis can send data compressed or not, depending on the
data.  There are some types of data that cannot be
compressed.  For example, if a file was compressed first,
and then sent through a V.42bis modem, the modem would not
likely reduce the number of bits sent.  Indeed it is likely
that the amount of data would increase somewhat.

To avoid this problem, the algorithm constantly monitors the
compressibility of the data, and if it finds fewer bits
would be necessary to send it uncompressed, it switches to
transparent mode.  The sender informs the receiver of this
transition through a reserved escape code.  Henceforth the
data is passed as plain bytes.

The choice of escape code is clever.  Initially, it is a
zero byte.  Any occurrence of the escape code is replaced,
as is customary, by two escape codes.  In order to prevent a
string of escape codes from temporarily cutting throughput
in half, the escape code is redefined by adding 51 mod 256
each time it is used.

While transmitting in transparent mode, the sender maintains
the LZW trees of strings, and expects the receiver to do
likewise.  If it finds an advantage in returning to
compressed mode, it will do so, first informing the receiver
by a special control code.  Thus the method allows the
hardware to adapt to the compressibility of the data.


The CCITT standards documents are available by ftp on src.doc.ic.ac.uk,
in directory doc/ccitt-standards/ccitt. The v42bis standard is in
/doc/ccitt-standards/ccitt/1992/v/v42bis.asc.Z.
(ccitt standards used to be on ftp.uu.net in /doc/standards/ccitt
but this directory is now empty -- Aug 11th.)

------------------------------------------------------------------------------

Subject: [12] I need source for the winners of the Dr Dobbs compression contest


The source of the top 6 programs of the Feb 91 Dr Dobbs data compression
contest are available by ftp on
  wsmr-simtel20.army.mil in pd1:<msdos.compress>ddjcompr.zip. [192.88.110.2]
  garbo.uwasa.fi:/pc/source/ddjcompr.zip [128.214.87.1]

The sources are in MSDOS end-of-line format, one directory per
program.  Unix or VMS users, use "unzip -a ddjcompr" to get correct
end-of-lines (add -d to recreate the directory structure if you are
using an obsolete version of unzip such as 4.1). Three of the 6
programs are not portable and only run on MSDOS. compact and urban
work on Unix, sixpack only requires minor modifications.

------------------------------------------------------------------------------

Subject: [13] I need source for arithmetic coding


(See question 70 for an introduction to arithmetic coding.)

The source for the arithmetic coder described in Chap.5 of Bell,
Cleary, and Witten's book "Text Compression" (see question 7 above)
(or, equivalently, in: Witten, Neal, and Cleary's article "Arithmetic
Coding for data Compression" from Communications of the Association
for Computing Machinery, 30 (6), pp.520-540, June, 1987) is available
via anonymous ftp from fsa.cpsc.ucalgary.ca (136.159.2.1) in directory
/pub/arithmetic.coding.  It only comes with a simple order-0 model but
it's set up so that adding your own more sophisticated one is
straightforward.

A low precision arithmetic coding implementation avoiding hardware
division is available on the same site (fsa.cpsc.ucalgary.ca)
in /pub/arithmetic.coding/low.precision.version/low.precision.version.shar.

Kris Popat <popat@image.mit.edu> has worked on "Scalar Quantization
with Arithmetic Coding."  It describes an arithmetic coding technique
which is quite general and computationally inexpensive.  The
documentation and example C code are available via anonymous ftp from
media-lab.media.mit.edu (18.85.0.2), in /pub/k-arith-code.

------------------------------------------------------------------------------

Subject: [15] Where can I get image compression programs?


JPEG:
      Source code for most any machine:
      ftp.uu.net:/graphics/jpeg/jpegsrc.v3.tar.Z [137.39.1.9]
      nic.funet.fi:/pub/graphics/programs/jpeg/jpegsrc.v3.tar.Z [128.214.6.100]
      Contact: jpeg-info@uunet.uu.net (Independent JPEG Group)

      xv, an image viewer which can read JPEG pictures, is available in
      ftp.cicb.fr:/pub/X11R5/contrib/xv-2.20.tar.Z  [129.20.128.2]

epic:
      whitechapel.media.mit.edu:/pub/epic.tar.Z [18.85.0.125]
      The "Lenna" test image is available as part of the EPIC package,
      where it is named "test_image".

compfits:
      uwila.cfht.hawaii.edu:/pub/compfits/compfits.tar.Z  [128.171.80.50]
      Contact: Jim Wright <jwright@cfht.hawaii.edu>

fitspress:
      cfata4.harvard.edu:/pub/fitspress08.tar.Z [128.103.40.79]

tiff:
      For source and sample images, see question 18 below.

------------------------------------------------------------------------------

Subject: [16] What is the state of the art in lossless image compression?


The current state-of-the-art is the JBIG algorithm.  For an
introduction to JBIG, see question 74 in part 2.

JBIG works best on bi-level images (like faxes) and also works well on
Gray-coded grey scale images up to about six or so bits per pixel.  You
just apply JBIG to the bit planes individually.  For more bits/pixel,
lossless JPEG provides better performance, sometimes. (For JPEG, see
question 19 below.)

You can find a description of JBIG in ISO/IEC CD 11544, contained in
document ISO/IEC JTC1/SC2/N2285.  The only way to get it is to ask
your National Standards Body for a copy. In the USA, call ANSI at
(212) 642-4900.

------------------------------------------------------------------------------

Subject: [17] What is the state of fractal compression?


from Tal Kubo <kubo@zariski.harvard.edu>:

According to Barnsley's book 'Fractals Everywhere', this method is
based on a measure of deviation between a given image and its
approximation by an IFS code.  The Collage Theorem states that there is
a convergent process to minimize this deviation.  Unfortunately,
according to an article Barnsley wrote for BYTE a few years ago, this
convergence was rather slow, about 100 hours on a Cray, unless assisted by
a person.

Barnsley et al are not divulging any technical information beyond the
meager bit in 'Fractals Everywhere'.  The book explains the idea of IFS
codes at length, but is vague about the application of the Collage theorem
to specific compression problems.

There is reason to believe that Barnsley's company has
*no algorithm* which takes a given reasonable image and achieves
the compression ratios initially claimed for their fractal methods.
The 1000-to-1 compression advertised was achieved only for a 'rigged'
class of images, with human assistance. The best unaided
performance I've heard of is good lossy compression of about 80-1.

Steve Tate <srt@duke.cs.duke.edu> confirms:

Compression ratios (unzoomed) seem to range from 20:1 to 60:1...  The
quality is considerably worse than wavelets or JPEG on most of the
non-contrived images I have seen.

But Yuval Fisher <fisher@inls1.ucsd.edu> disagrees:

Their performance has improved dramatically beyond what they were
talking about in BYTE a few years ago.  Human assistance to the
compression is no longer needed and the compression time is
reasonable, although the more time and compute power you throw at the
compression, the smaller the resulting file for the same level of
quality.



There is a fractal image decompression demo program  available via anonymous
ftp in directory lyapunov.ucsd.edu:/pub/inls-ucsd/fractal-2.0.
There are executables and sample images in the same directory.

References:
  A. Jacquin, 'Fractal image coding based on a theory of iterated
    contractive image transformations', Visual Comm. and Image
    Processing, vol SPIE-1360, 1990. (The best paper that explains
    the concept in a simple way.)

  A. Jacquin, "A Fractal Theory of Iterated Markov Operators with
    Applications to Digital Image Coding", PhD Thesis, Georgia Tech, 1989.
  It can be obtained from university microfilms for $35, phone 1-800-521-0600.

  M. Barnsley, L. Anson, "Graphics Compression Technology, SunWorld,
    October 1991, pp. 42-52.
  M.F. Barnsley, A. Jacquin, F. Malassenet, L. Reuter & A.D. Sloan,
    'Harnessing chaos for image synthesis', Computer Graphics,
    vol 22 no 4 pp 131-140, 1988.
  M.F. Barnsley, A.E. Jacquin, 'Application of recurrent iterated
    function systems to images', Visual Comm. and Image Processing,
    vol SPIE-1001, 1988.
  A. Jacquin, "Image Coding Based on a Fractal Theory of Iterated Contractive
    Image Transformations" p.18, January 1992 (Vol 1 Issue 1) of IEEE Trans
    on Image Processing.
  A.E. Jacquin, 'A novel fractal block-coding technique for digital
    images', Proc. ICASSP 1990.
  G.E. Oien, S. Lepsoy & T.A. Ramstad, 'An inner product space
    approach to image coding by contractive transformations',
    Proc. ICASSP 1991, pp 2773-2776.
  D.S. Mazel, Fractal Modeling of Time-Series Data, PhD Thesis,
    Georgia Tech, 1991.    (One dimensional, not pictures)
  S. A. Hollatz, "Digital image compression with two-dimensional affine
    fractal interpolation functions", Department of Mathematics and
    Statistics, University of Minnesota-Duluth, Technical Report 91-2.
    (a nuts-and-bolts how-to-do-it paper on the technique)
  Stark, J., "Iterated function systems as neural networks",
    Neural Networks, Vol 4, pp 679-690, Pergamon Press, 1991.
  Monro D M and Dudbridge F, "Fractal block coding of images",
    Electronics Letters 28(11):1053-1054 (1992)
  Beaumont J M, "Image data compression using fractal techniques",
    British Telecom Technological Journal 9(4):93-108 (1991)
  Fisher Y, "Fractal image compression", Siggraph 92
  Graf S, "Barnsley's Scheme for the Fractal Encoding of Images",
    Journal Of Complexity, V8, 72-78 (1992).

Books:
    The Fractal Transform,
    Michael F. Barnsley and Louisa F. Anson
    ISBN 0-86720-218-1, ca. 250 pp, $49.95

    Fractal Image Compression
    Michael F. Barnsley and Lyman P. Hurd
    ISBN 0-86720-457-5, ca. 250 pp., $49.95

Barnsley's company is:

Iterated Systems, Inc.
5550A Peachtree Parkway, Suite 545
Norcross, GA  30092
404-840-0728
404-840-0029 (fax)

------------------------------------------------------------------------------

Subject: [18] I need specs and source for TIFF and CCITT group 4 Fax


Specs for Group 3 and 4 image coding (group 3 is very similar to group 4)
are in CCITT (1988) volume VII fascicle VII.3. They are recommendations
T.4 and T.6 respectively. There is also an updated spec contained in 1992
recommendations T.1 to T.6.

CCITT specs are available by anonymous ftp (see above answer on V.42bis).
The T.4 spec is in ccitt/1988/ascii/7_3_01.txt.Z, the T.6 spec
is in 7_3_02.txt.Z.

Source code can be obtained as part of a TIFF toolkit - TIFF image
compression techniques for binary images include CCITT T.4 and T.6:

    sgi.com:/graphics/tiff/v3.0beta.tar.Z     [192.48.153.1]
    Contact: sam@sgi.com

There is also a companion compressed tar file (v3.0pics.tar.Z) that
has sample TIFF image files. A draft of TIFF 6.0 is in TIFF6.ps.Z.

See also question 54 below.

------------------------------------------------------------------------------

Subject: [19] What is JPEG?


JPEG (pronounced "jay-peg") is a standardized image compression mechanism.
JPEG stands for Joint Photographic Experts Group, the original name of the
committee that wrote the standard.  JPEG is designed for compressing either
full-color or gray-scale digital images of "natural" (real-world) scenes.
JPEG does not handle black-and-white (1-bit-per-pixel) images, nor does it
handle motion picture compression.  (Standards for compressing those types
of images are being worked on by other committees, named JBIG and MPEG
respectively.)

A good introduction to JPEG is posted regularly in news.answers by
Tom Lane <tgl+@cs.cmu.edu>. (See question 53 "Where are FAQ lists archived"
if this posting has expired at your site.)

------------------------------------------------------------------------------

Subject: [20] I am looking for source of an H.261 codec.


The H.261 spec is available on src.doc.ic.ac.uk in
/doc/ccitt-standards/ccitt/1992/h/h261.doc.Z (or h261.rtf.Z)


from Thierry TURLETTI <turletti@sophia.inria.fr>:

We have implemented a software version of H.261 codec. 
It runs on top of UNIX and X-Windows. The coder uses the simple video capture
board "VideoPix" provided by SUN for the SparcStation. The output is directed
towards a standard TCP connection, instead of the leased lines or switched 
circuits for which regular H.261 codecs are designed. This enable us to test
video conferences over regular internet connections.
We have to polish it a bit, but the first release is now available by anonymous
ftp from avahi.inria.fr, in "/pub/h261.tar.Z".

------------------------------------------------------------------------------

Subject: [25] Fast DCT (Discrete Cosine Transform) algorithms


Here are some references provided by Tom Lane <tgl+@cs.cmu.edu>:

Polynomial Transform Computation of the 2-D DCT, Duhamel & Guillemot,
  ICASSP '90 p. 1515.
A Forward-Mapping Realization of the Inverse DCT, McMillan & Westover,
  DCC '92 p. 219.
A Fast Algorithm for 2-D DCT, Cho, Yun & Lee, ICASSP '91 p. 2197.
Fast Algorithm and Implementation of 2-D DCT, Cho & Lee, Tr. CAS v38 p. 297.
A DCT Chip based on a new Structured and Computationally Efficient DCT
  Algorithm, Duhamel, Guillemot & Carlach, ICCAS '90 p. 77.
Trade-offs in the Computation of Mono- and Multi-dimensional DCTs,
  Vetterli, Duhamel & Guillemot, ICASSP '89 p. 999.
Practical Fast 1-D DCT Algorithms with 11 Multiplications,
  Loeffler, Ligtenberg & Moschytz, ICASSP '89 p. 988.
New Scaled DCT Algorithms for Fused Multiply/Add Architectures,
  Linzer & Feig, ICASSP '91 p. 2201.
Fast Algorithms for the 2-D Discrete Cosine Transform, Kamangar & Rao,
  IEEE Tr. Computers, v C-31 p. 899.
Fast 2-D Discrete Cosine Transform, Vetterli, ICASSP '85 p. 1538.
A Two-Dimensional Fast Cosine Transform, Haque, Tr. ASSP v ASSP-33 p. 1532.
Real-Time Parallel and Fully Pipelined 2-D DCT Lattice Structures with
  Application to HDTV Systems, Chiu & Liu, Tr. CAS for Video Tech, v 2 p. 25.

The Rao & Yip book cited in the jpeg v3 DCT code (see item 15 above) is a
good overall introduction, with an extensive (though now dated) bibliography.

------------------------------------------------------------------------------

Subject: [26] Are there algorithms and standards for audio compression?


Yes. See the introduction to MPEG given in part 2 of this FAQ.

A lossless compressor for 8bit and 16bit audio data (.au) is available by
anonymous ftp at svr-ftp.eng.cam.ac.uk:/pub/misc/shorten-0.4.shar. It works
by using Huffman coding of prediction residuals.  Compression is generally
better than that obtained by applying general purpose compression utilities
to audio files.


Copied from the comp.dsp FAQ posted by guido@cwi.nl (Guido van Rossum):

Strange though it seems, audio data is remarkably hard to compress
effectively.  For 8-bit data, a Huffman encoding of the deltas between
successive samples is relatively successful.  For 16-bit data,
companies like Sony and Philips have spent millions to develop
proprietary schemes.

Public standards for voice compression are slowly gaining popularity,
e.g. CCITT G.721 and G.723 (ADPCM at 32 and 24 kbits/sec).  (ADPCM ==
Adaptive Delta Pulse Code Modulation.)  Free source code for a *fast*
32 kbits/sec ADPCM (lossy) algorithm is available by ftp from ftp.cwi.nl
as /pub/adpcm.shar.

(Note that U-LAW and silence detection can also be considered
compression schemes.)


See also the comp.dsp FAQ for more information on:

- The U.S. DoD's Federal-Standard-1016 based 4800 bps code excited linear
  prediction voice coder version 3.2 (CELP 3.2)
- The U.S. DoD's Federal-Standard-1015/NATO-STANAG-4198 based 2400 bps
  linear prediction coder version 53 (LPC-10e v53)
- Realtime DSP code and hardware for FS-1015 and FS-1016

You can find the comp.dsp FAQ in comp.dsp or news.answers with subject:
"FAQ: Audio File Formats" or by ftp on pit-manager.mit.edu
in /pub/usenet/news.answers/audio-fmts/part1.


from Markus Kuhn <mskuhn@immd4.informatik.uni-erlangen.de>:

One highest quality sound compression format is called ASPEC and has
been developped by a team at the Frauenhofer Institut in Erlangen, Germany.

ASPEC produces CD like quality and offers several bitrates, one is
128 kbit/s. It is a lossy algorithm that throws away frequencys that
aren't registered in the human cochlea in addition to sophisticated
entropy coding. The 64 kbit/s ASPEC variant might soon bring hifi
quality ISDN phone connections ...

It has been implemented on standard DSPs.


------------------------------------------------------------------------------

Subject: [30] My archive is corrupted!


The two most common reasons for this are

(1) failing to use the magic word "tenex" (when connected to SIMTEL20 and
    other TOPS20 systems) or "binary" (when connected to UNIX systems) when
    transferring the file from an ftp site to your host machine.  The
    reasons for this are technical and boring.  A synonym for "tenex" is
    "type L 8", in case your ftp doesn't know what "tenex" means.

(2) failing to use an eight-bit binary transfer protocol when transferring
    the file from the host to your PC.  Make sure to set the transfer type
    to "binary" on both your host machine and your PC.

------------------------------------------------------------------------------

Subject: [31] pkunzip reports a CRC error!


The portable zip 1.0 contains many workarounds for undocumented restrictions
in pkunzip. Compatibility is ensured for pkunzip 1.10 only. All previous
versions (pkunzip 1.0x) have too many bugs and cannot be supported. This
includes Borland unzip.

So if your pkunzip reports a CRC error, check that you are not using
an obsolete version. Get either pkzip 1.10 or unzip 5.0 (see question
2 above for ftp sites).

Immediately after zip 1.0 was released, a new undocumented feature
of pkunzip was discovered, which causes CRC errors even with pkunzip 1.10
on rare occasions. A patch is available on valeria.cs.ucla.edu in
/pub/zip10.patch.

------------------------------------------------------------------------------

Subject: [32] VMS zip is not compatible with pkzip!


The problem is most likely in the file transfer program.

Many use kermit to transfer zipped files between PC and VMS VAX.  The
following VMS kermit settings make VMS-ZIP compatible with PKZIP:

                                             VMS kermit        PC kermit
                                           ---------------   --------------

Uploading PKZIPped file to be UNZIPped:    set fi ty fixed    set fi ty bi
Downloading ZIPped file to be PKUNZIPped:  set fi ty block    set fi ty bi

If you are not using kermit, transfer a file created by pkzip on MSDOS
to VMS, transfer it back to your PC and check that pkunzip can extract it.

------------------------------------------------------------------------------

Subject: [50] What is this 'tar' compression program?


tar is not a compression program. It just combines several files
into one, without compressing them. tar file are often compressed with
'compress', resulting in a .tar.Z file. See question 2, file type .tar.Z.
(However, some versions of tar have the capability to compress files
as well.)

When you have to archive a lot of very small files, it is often
preferable to create a single .tar file and compress it, than to
compress the individual files separately. The compression program can
thus take advantage of redundancy between separate files.  The
disadvantage is that you must uncompress the whole .tar file to
extract any member.

------------------------------------------------------------------------------

Subject: [51] I need a CRC algorithm


As its name implies (Cyclic Redundancy Check) a crc adds redundancy
whereas the topic of this group is to remove it. But since this
question comes up often, here is some code (by Rob Warnock <rpw3@sgi.com>).

The following C code does CRC-32 in BigEndian/BigEndian byte/bit order.
That is, the data is sent most significant byte first, and each of the bits
within a byte is sent most significant bit first, as in FDDI. You will need
to twiddle with it to do Ethernet CRC, i.e., BigEndian/LittleEndian byte/bit
order. [Left as an exercise for the reader.]

The CRCs this code generates agree with the vendor-supplied Verilog models
of several of the popular FDDI "MAC" chips.

u_long crc32_table[256];
/* Initialized first time "crc32()" is called. If you prefer, you can
 * statically initialize it at compile time. [Another exercise.]
 */

u_long crc32(u_char *buf, int len)
{
        u_char *p;
        u_long  crc;

        if (!crc32_table[1])    /* if not already done, */
                init_crc32();   /* build table */
        crc = 0xffffffff;       /* preload shift register, per CRC-32 spec */
        for (p = buf; len > 0; ++p, --len)
                crc = (crc << 8) ^ crc32_table[(crc >> 24) ^ *p];
        return ~crc;            /* transmit complement, per CRC-32 spec */
}

/*
 * Build auxiliary table for parallel byte-at-a-time CRC-32.
 */
#define CRC32_POLY 0x04c11db7     /* AUTODIN II, Ethernet, & FDDI */

init_crc32()
{
        int i, j;
        u_long c;

        for (i = 0; i < 256; ++i) {
                for (c = i << 24, j = 8; j > 0; --j)
                        c = c & 0x80000000 ? (c << 1) ^ CRC32_POLY : (c << 1);
                crc32_table[i] = c;
        }
}

------------------------------------------------------------------------------

Subject: [52] What about those people who continue to ask frequently asked
              questions in spite of the frequently asked questions document?


Just send them a polite mail message, referring them to this document.
There is no need to flame them on comp.compression.  That would just
add more noise to this group.  Posted answers that are in the FAQ are
just as annoying as posted questions that are in the FAQ.

------------------------------------------------------------------------------

Subject: [53] Where are FAQ lists archived?


Many are crossposted to news.answers.  That newsgroup should have a
long expiry time at your site; if not, talk to your sysadmin.

FAQ lists are available by anonymous FTP from rtfm.mit.edu (18.72.1.58).
The comp.compression FAQ that you are reading is in directory
   /pub/usenet/news.answers/compression-faq

If you don't have FTP access, you can access the archives by mail
server.  Send an email message to mail-server@pit-manager.mit.edu
containing the commands
    send usenet/news.answers/compression-faq/part1
    send usenet/news.answers/compression-faq/part2
For instructions, send an email message to the same address with the
words "help" and "index" (no quotes) on separate lines. If you don't
get a reply, check your return address, or add a line such as
    path myname@foo.edu

------------------------------------------------------------------------------

Subject: [54] I need specs for graphics formats


Have a look in directory /pub/graphics.formats on zamenhof.cs.rice.edu.
It contains descriptions of gif, tiff, fits, etc...

See also the FAQ list for comp.graphics.

------------------------------------------------------------------------------

Subject: [55] Where can I find Lenna and other images?


A bunch of standard images (lenna, baboon, cameraman, crowd, moon
etc..) are on ftp site eedsp.gatech.edu (130.207.226.2) in directory
/database/images. The images are in 256-level grayshades (256x256
pixels, 256 "colors").

The site ftp.ipl.rpi.edu also has standard images, in two directories:
   ftp.ipl.rpi.edu:/pub/image/still/usc 
   ftp.ipl.rpi.edu:/pub/image/still/canon

In each of those directories are the following directories:
   bgr     - 24 bit blue, green, red
   color   - 24 bit red, green, blue
   gray    - 8 bit grayscale uniform weighted
   gray601 - 8 bit grayscale CCIR-601 weighted

And in these directories are the actual images.  

For example, the popular lena image is in
   ftp.ipl.rpi.edu:/pub/image/still/usc/color/lena  # 24 bit RGB
   ftp.ipl.rpi.edu:/pub/image/still/usc/bgr/lena    # 24 bit BGR
   ftp.ipl.rpi.edu:/pub/image/still/usc/gray/lena   # 8 bit gray

All of the images are in Sun rasterfile format.  You can use the pbm
utilities to convert them to whatever format is most convenient.
[pbm is available in ftp.ee.lbl.gov:/pbmplus*.tar.Z].
Questions about the ipl archive should be sent to rodney@ipl.rpi.edu.

The archive maintainer at ftp.ipl.rpi.edu is interested in some method
of establishing a canonical ftp database of images and could volunteer
the ipl to be an ftp site for that database. Send suggestions to
rodney@ipl.rpi.edu.


Beware: the same image often comes in many different forms, at
different resolutions, etc... The original lenna image is 512 wide,
512 high, 8 bits per pel, red, green and blue fields.  Gray-scale
versions of Lenna have been obtained in two different ways from the
original:
 (1) Using the green field as a gray-scale image, and
 (2) Doing an RGB->YUV transformation and saving the Y component.
Method (1) makes it easier to compare different people's results since
everyone's version should be the same using that method.  Method (2)
produces a more correct image.

For the curious: 'lena' or 'lenna' is a digitized Playboy centerfold,
from November 1972. (Lenna is the spelling in Playboy, Lena is the
Swedish spelling of the name.) Lena Soderberg (ne Sjooblom) was last
reported living in her native Sweden, happily married with three kids
and a job with the state liquor monopoly.  In 1988, she was
interviewed by some Swedish computer related publication, and she was
pleasantly amused by what had happened to her picture.  That was the
first she knew of the use of that picture in the computer business.

The editorial in the January 1992 issue of Optical Engineering (v. 31
no. 1) details how Playboy has finally caught on to the fact that
their copyright on Lenna Sjooblom's photo is being widely infringed.
It sounds as if you will have to get permission from Playboy to
publish it in the future.

------------------------------------------------------------------------------

Subject: [56] I am looking for a message digest algorithm


Look on the ftp site rsa.com, in directory /pub. MD4 and MD5 are there.
This question would be more appropriate on sci.crypt.



          End of part 1 of the comp.compression faq.