home *** CD-ROM | disk | FTP | other *** search
/ Peanuts NeXT Software Archives / Peanuts-1.iso / CDROM / FAQs / compression / part1 next >
Encoding:
Internet Message Format  |  1996-10-24  |  152.8 KB
  1. Path: informatik.tu-muenchen.de!fu-berlin.de!news.mathworks.com!howland.erols.net!mathserv.mps.ohio-state.edu!jussieu.fr!rain.fr!teaser.fr!!jloup
  2. From: gzip@prep.ai.mit.edu.remove_this_part (Jean-loup Gailly)
  3. Newsgroups: comp.compression,comp.compression.research,news.answers,comp.answers
  4. Subject: comp.compression Frequently Asked Questions (part 1/3)
  5. Supersedes: <compr1_20sep96@prep.ai.mit.edu>
  6. Followup-To: comp.compression
  7. Date: 23 Oct 1996 21:18:11 GMT
  8. Organization: none
  9. Lines: 3546
  10. Approved: news-answers-request@mit.edu
  11. Distribution: world
  12. Expires: 15 Dec 1996 16:17:20 GMT
  13. Message-ID: <compr1_22oct96@prep.ai.mit.edu>
  14. Reply-To: gzip@prep.ai.mit.edu.remove_this_part
  15. NNTP-Posting-Host: ppp1273-ft.teaser.fr
  16. Summary: *** READ THIS BEFORE POSTING ***
  17. Keywords: data compression, FAQ
  18. Originator: jloup@
  19. Xref: informatik.tu-muenchen.de comp.compression:32191 comp.compression.research:2272 news.answers:84877 comp.answers:21848
  20.  
  21. Archive-name: compression-faq/part1
  22. Last-modified: Oct 22nd, 1996
  23.  
  24.         "I've already explained this once, but repetition is
  25.         the very soul of the net."        (from alt.config)
  26.  
  27. This file is part 1 of a set of Frequently Asked Questions (FAQ) for
  28. the groups comp.compression and comp.compression.research.  If you
  29. can't find part 2 or 3, see item 53 below. A copy of this FAQ is available
  30. by ftp in ftp://rtfm.mit.edu/pub/usenet/news.answers/compression-faq/
  31. files part1 to part3. This FAQ is also accessible in the World Wide Web at
  32. http://www.cis.ohio-state.edu/hypertext/faq/usenet/compression-faq/top.html
  33. or http://www.cs.ruu.nl/wais/html/na-dir/compression-faq/.html
  34.  
  35. Certain questions get asked time and again, and this is an attempt to
  36. reduce the bandwidth taken up by these posts and their associated
  37. replies.  If you have a question, *please* check this file before you
  38. post.  It may save a lot of peoples time.
  39.  
  40. If you have not already read the overall Usenet introductory material
  41. posted to "news.announce.newusers", please do. It is also available by
  42. ftp in ftp://garbo.uwasa.fi/pc/doc-net/usenews.zip (see item 2 below
  43. about .zip).
  44.  
  45. If you don't want to see this FAQ regularly, please add the subject
  46. line to your kill file.  If you don't know what a kill file is, get
  47. by ftp the file ftp://rtfm.mit.edu/pub/usenet/news.answers/killfile-faq
  48. If you have corrections or suggestions for this FAQ, send them to
  49. Jean-loup Gailly <gzip@prep.ai.mit.edu.remove_this_part>
  50. after fixing the email address as described. (This is a protection
  51. against junk mail. Sorry for the inconvenience.)
  52.  
  53. Part 1 is oriented towards practical usage of compression programs.
  54. Part 2 is more intended for people who want to know how compression works.
  55. Part 3 is a long (but somewhat obsolete) list of image compression hardware.
  56.  
  57. Main changes relative to the previous version:
  58.  
  59. - changed the From and Reply-To fields to reduce spamming to my account.
  60.   You must now edit the address manually. Sorry but I get too much junk mail.
  61. - added pointers to mime64b.zip, LZO, untgz [item 2]
  62. - updated pointers for MPEG Software Simulation Group and VMPEG [item 15]
  63. - added MPEGTV [item 15]
  64.  
  65.  
  66. Contents
  67. ========
  68.  
  69. General questions:
  70.  
  71. [1]  What are these newsgroups about?
  72. [2]  What is this .xxx file type?
  73.      Where can I find the corresponding compression program?
  74. [3]  What is the latest pkzip version?
  75. [4]  What is an archiver?
  76. [5]  What is the best general purpose compression program?
  77. [7]  Which books should I read?
  78. [8]  What about patents on data compression algorithms?
  79. [9]  Compression of random data (WEB, Gilbert and others)
  80. [10] Fake compression programs (OWS, WIC)
  81. [11] What is the V.42bis standard?
  82. [12] I need source for the winners of the Dr Dobbs compression contest
  83. [13] I need source for arithmetic coding
  84.  
  85. Image and audio compression:
  86.  
  87. [15] Where can I get image compression programs?
  88. [16] What is the state of the art in lossless image compression?
  89. [17] What is the state of fractal compression?
  90. [18] I need specs and source for TIFF and CCITT group 4 Fax.
  91. [19] What is JPEG?
  92. [20] I am looking for source of an H.261/H.263 codec and MPEG
  93. [25] Fast DCT (Discrete Cosine Transform) algorithms
  94. [26] Are there algorithms and standards for audio compression?
  95.  
  96. Common problems:
  97.  
  98. [30] My archive is corrupted!
  99. [31] pkunzip reports a CRC error!
  100. [32] VMS zip is not compatible with pkzip!
  101. [33] I have a problem with Stacker or DoubleSpace!
  102.  
  103. Questions which do not really belong to comp.compression:
  104.  
  105. [50] What is this 'tar' compression program?
  106. [51] I need a CRC algorithm
  107. [52] What about those people who continue to ask frequently asked questions?
  108. [53] Where are FAQ lists archived?
  109. [54] I need specs for graphics formats
  110. [55] Where can I find Lenna and other images?
  111. [56] I am looking for a message digest algorithm
  112. [57] I have lost my password on a .zip file
  113.  
  114.  
  115. Part 2: (Long) introductions to data compression techniques
  116.  
  117. [70] Introduction to data compression (long)
  118.        Huffman and Related Compression Techniques
  119.        Arithmetic Coding
  120.        Substitutional Compressors
  121.           The LZ78 family of compressors
  122.           The LZ77 family of compressors
  123.  
  124. [71] Introduction to MPEG (long)
  125.        What is MPEG?
  126.        Does it have anything to do with JPEG?
  127.        Then what's JBIG and MHEG?
  128.        What has MPEG accomplished?
  129.        So how does MPEG I work?
  130.        What about the audio compression?
  131.        So how much does it compress?
  132.        What's phase II?
  133.        When will all this be finished?
  134.        How do I join MPEG?
  135.        How do I get the documents, like the MPEG I draft?
  136.  
  137. [72] What is wavelet theory?
  138. [73] What is the theoretical compression limit?
  139. [74] Introduction to JBIG
  140. [75] Introduction to JPEG
  141. [76] What is Vector Quantization?
  142. [77] Introduction to Fractal compression
  143. [78] The Burrows-Wheeler block sorting algorithm
  144.  
  145.  
  146. Part 3: (Long) list of image compression hardware
  147.  
  148. [85] Image compression hardware
  149. [99] Acknowledgments
  150.  
  151.  
  152. Search for "Subject: [#]" to get to question number # quickly. Some news
  153. readers can also take advantage of the message digest format used here.
  154.  
  155. If you know very little about data compression, read question 70 in
  156. part 2 first.
  157.  
  158. ------------------------------------------------------------------------------
  159.  
  160. Subject: [1] What are these newsgroups about?
  161.  
  162.  
  163. comp.compression is the place to discuss about data compression, both
  164. lossless (for text or data) and lossy (for images, sound, etc..).
  165. comp.compression.research was created later to provide a forum for
  166. current research on data compression and data compression algorithms;
  167. this group is now moderated. If you are not experienced in data compression,
  168. please post in comp.compression only.
  169.  
  170. An archive of this newsgroup since Oct 1993 is available in
  171. ftp://spib.rice.edu/pub/news/comp.compression/
  172.  
  173. An excellent collection of compression based information is provided at
  174. http://www.internz.com/compression-pointers.html
  175.  
  176. If you only want to find a particular compression program for a
  177. particular operating system, please read first this FAQ and the
  178. article "How to find sources" which is regularly posted in
  179. news.answers.
  180.  
  181. If you can't resist posting such a request, other groups are probably
  182. more appropriate (comp.binaries.ibm.pc.wanted, comp.os.msdos.apps,
  183. comp.sources.wanted, comp.sys.mac.wanted, comp.archives.msdos.d, comp.dsp,
  184. alt.graphics.pixutils). Please post your request in comp.compression
  185. only as a last resource.
  186.  
  187. If your question is about graphics only (no compression), please
  188. post to comp.graphics.misc, *after* reading the comp.graphics FAQ (see
  189. item 54 below). For some unknown reason, many questions about
  190. graphics are incorrectly posted to comp.compression.
  191. For questions related to audio compression, check also comp.dsp.
  192.  
  193. Please do not post any program in binary form to comp.compression.
  194. Very short sources can be posted, but long sources should be be posted
  195. to the specialized source groups, such as comp.sources.* or alt.sources.
  196. If the program is already available by ftp, just give the name of the
  197. ftp site and the full path name of the file.
  198.  
  199. As for any newsgroups, do not post the same message separately to
  200. comp.compression and comp.compression.research.
  201.  
  202. ------------------------------------------------------------------------------
  203.  
  204. Subject: [2] What is this .xxx file type?
  205.              Where can I find the corresponding compression program?
  206.  
  207.  
  208. All the programs mentioned in this section are lossless.  For most
  209. programs, one US and one European ftp site are given.  (ftp.coast.net
  210. & garbo.uwasa.fi) Many other sites (in particular wuarchive.wustl.edu)
  211. have the same programs.
  212.  
  213. To keep this list to a reasonable size, many programs are not
  214. mentioned here. Additional information can be found in the file
  215. ftp://ftp.cso.uiuc.edu/pub/doc/pcnet/compression maintained by
  216. David Lemson (lemson@uiuc.edu). When several programs can handle
  217. the same archive format, only one of them is given. If you don't
  218. find a particular MSDOS archiver here, look also in
  219. ftp://ftp.cs.tu-berlin.de/pub/msdos/mirrors/ftp.elf.stuba.sk/pc/
  220.  
  221. Sources for additional lossless data compressors can be found in
  222.   ftp://garbo.uwasa.fi/pc/programming/lds_11.zip
  223.   ftp://ftp.simtel.net/pub/simtelnet/msdos/arcutils/lz-comp2.zip
  224.   http://wwwvms.utexas.edu/~cbloom/index.html
  225.   ftp://ftp.imag.fr/pub/archive/compression/codecs/codecs.tgz
  226.   ftp://garbo.uwasa.fi/pc/turbopas/preskit2.zip (sources in Pascal)
  227.   ftp://ftp.cs.uiowa.edu/pub/jones/compress/ (Splay tree compression)
  228.  
  229. For Macintosh programs, look on ftp://sumex-aim.stanford.edu/info-mac
  230.   on in http://hyperarchive.lcs.mit.edu/HyperArchive.html
  231. For VM/CMS, look on ftp://vmd.cso.uiuc.edu/public.477
  232. For Atari, look on ftp://atari.archive.umich.edu
  233. For Amiga, look on ftp://ftp.wustl.edu/pub/aminet/
  234.  
  235. A general purpose lossless data compression library is available in
  236. ftp://ftp.uu.net/pub/archiving/zip/zlib/zlib-1.0.4.tar.gz or zlib104.zip;
  237. see http://quest.jpl.nasa.gov/zlib/ for more information.
  238. Another library favoring speed over compression ratio is available at
  239. http://www.infosys.tuwien.ac.at/Staff/lux/marco/lzo.html
  240.  
  241. If you don't know how to use ftp or don't have ftp access, read the
  242. article "How to find sources" which is regularly posted in news.answers.
  243.  
  244. If you can't find a program given below, a newer version probably exists in
  245. the same directory.  Tell me at gzip@prep.ai.mit.edu.remove_this_part
  246.  
  247. A very short description of the compression algorithm is given for
  248. most programs. For the meaning of LZ77, LZ78 and LZW, see question 70
  249. in part 2 of the FAQ.  If you are looking for the file format of a
  250. specific compression program, get the sources of the decompressor.
  251. For the format of uuencode, do "man 5 uuencode" on a Unix box.
  252.  
  253. ext:  produced by or read by
  254.  
  255. ..arc, .ark: arc, pkarc for MSDOS. (LZW algorithm)
  256.     ftp://wuarchive.wustl.edu/mirrors/msdos/starter/pk361.exe
  257.     ftp://garbo.uwasa.fi/pc/arcers/pk361.exe
  258.  
  259.       arc for Unix
  260.         ftp://wuarchive.wustl.edu/mirrors/misc/unix/arc521e.tar-z
  261.     ftp://garbo.uwasa.fi/unix/arcers/arc.tar.Z
  262.         Contact: Howard Chu <hyc@umix.cc.umich.edu>
  263.  
  264.       arc for VMS
  265.     ftp://wuarchive.wustl.edu/packages/compression/vax-vms/arc.exe
  266.  
  267.       for Mac
  268.     ftp://wuarchive.wustl.edu/systems/mac/info-mac/cmp/stuffit-expander-352.hqx
  269.  
  270.       arc for Amiga
  271.     ftp.funet.fi:pub/amiga/fish/001-100/ff070/arc.lha
  272.  
  273. ..arj: arj for MSDOS (LZ77 with hashing, plus secondary static Huffman
  274.           encoding on a block basis)
  275.         Contact: Robert K Jung <robjung@world.std.com>
  276.         ftp://ftp.simtel.net/pub/simtelnet/msdos/arcers/arj250a.exe
  277.     ftp://garbo.uwasa.fi/pc/arcers/arj250a.exe
  278.  
  279.       unarj for Unix. Decompresses only. (There is no arj compressor for Unix.
  280.         Don't post a request.)
  281.         ftp://wuarchive.wustl.edu/mirrors/misc/unix/unarj241.tar-z
  282.     ftp://garbo.uwasa.fi/unix/arcers/unarj241.tar.Z
  283.  
  284.       unarj for Mac
  285.         ftp://mac.archive.umich.edu/mac/util/compression/unarjmac.cpt.hqx      
  286.  
  287.       unarj for Amiga
  288.     ftp.funet.fi:pub/amiga/utilities/archivers/unarj-0.5.lha
  289.  
  290. base64 (MIME encoding): This is *not* a compression issue but it keeps
  291.        coming as a question on comp.compression. So:
  292.           ftp://ftp.andrew.cmu.edu/pub/mpack/mpack-1.5-src.tar.Z (source)
  293.           ftp://ftp.andrew.cmu.edu/pub/mpack/mpack15d.zip        (MSDOS exe)
  294.           ftp://wuarchive.wustl.edu/systems/mac/info-mac/cmp/mpack-15.hqx (Mac)
  295.           ftp://garbo.uwasa.fi/pc/decode/mime64b.zip
  296.  
  297. ..bck: VMS BACKUP. BACKUP is *not* a compression program. Do "help backup".
  298.  
  299. ..cpt: Compact Pro for Mac and Power PC
  300.          ftp://wuarchive.wustl.edu/systems/mac/info-mac/cmp/compact-pro-151.hqx
  301.  
  302.       For Unix:
  303.     ftp://sumex-aim.stanford.edu/info-mac/unix/macutil-20b1.shar
  304.         ftp://ftp.cwi.nl/pub/dik/macutil2.0b3.shar.Z
  305.  
  306.       For DOS:
  307.         ftp://ftp.scruz.net/users/aladdin/public/SITEX10.EXE
  308.     ftp://garbo.uwasa.fi/pc/arcers/ext-pc.zip
  309.  
  310. ..ddi:  files made by DiskDupe (Pro)
  311.      ftp://ftp.tem.nctu.edu.tw/Msdos/arcutil/unddi11u.zip
  312.      ftp://ftp.tem.nctu.edu.tw/Msdos/arcutil/x2file15.zip
  313.  
  314. ..exe: self-extracting MSDOS executable (creates files on disk when run)
  315.       Run the file, or try unzip, lha or arj on it.
  316.  
  317. ..exe: compressed MSDOS executable (decompresses itself in memory then runs
  318.       the decompressed code). To get the original uncompressed .exe:
  319.         ftp://garbo.uwasa.fi/pc/execomp/unp411.zip
  320.       To create such files:
  321.     ftp://ftp.simtel.net/pub/simtelnet/msdos/execomp/lzexe91e.zip
  322.     ftp://nic.funet.fi/pub/msdos/windows/util/winlite1.zip (for Windows)
  323.  
  324. ..gif: gif files are images compressed with the LZW algorithm. See the
  325.       comp.graphics FAQ list for programs manipulating .gif files. See
  326.       suffix .Z below for source of LZW.
  327.  
  328. ..gz, .z: gzip (or pack, see .z below). gzip uses the same algorithm as
  329.          zip 2.0x (see below); it can also extract packed and compressed files.
  330.     Contact: Jean-loup Gailly <gzip@prep.ai.mit.edu.remove_this_part>
  331.                  http://www.teaser.fr/~jlgailly/
  332.  
  333.       For Unix, MSDOS, OS/2, VMS, Atari, Amiga, Primos:
  334.     ftp://prep.ai.mit.edu/pub/gnu/gzip-1.2.4.tar (.shar or .tar.gz: source)
  335.     ftp://prep.ai.mit.edu/pub/gnu/gzip-1.2.4.msdos.exe (MSDOS self-extract)
  336.     ftp://ftp.simtel.net/pub/simtelnet/msdos/compress/gzip124.zip (MSDOS)
  337.     ftp://garbo.uwasa.fi/unix/arcers/gzip-1.2.4.tar.Z       (source)
  338.     ftp://garbo.uwasa.fi/pc/unix/gzip124.zip                (MSDOS exe)
  339.     ftp://ftp.uu.net/pub/archiving/zip/WIN32/gzip124xN.zip  (WIN95 & NT)
  340.     ftp://ftp.uu.net/pub/archiving/zip/VMS/gzip124x.vax_exe (VMS exe)
  341.         ftp://ftp.uu.net/pub/archiving/zip/UNIX/SUN/gzip124x.tar.Z (Solaris 2)
  342.         ftp://quest.jpl.nasa.gov/beta/vmcms_mvs/gzip123-mvs.exe (MVS)
  343.  
  344.       For Mac:
  345.        ftp://ivo.cps.unizar.es//Graficos/Public/SPDsoft/MacGzip_FAT_1.0.cpt.hqx
  346.        http://persephone.cps.unizar.es/general/gente/spd/gzip/ (MacGzip page)
  347.  
  348. ..ha: ha 0.99 (improved PPMC - 4th order Markov modeling)
  349.     Contact: Harri Hirvola <harri.hirvola@vaisala.infonet.com>
  350.     ftp://garbo.uwasa.fi/pc/arcers/ha098.zip
  351.     ftp://ftp.nl.net/gopher/NLnet-connected/aipnl/ha0999.exe
  352.         ftp://sunsite.unc.edu/pub/Linux/utils/compress/ha0999p-linux.tar.gz
  353.  
  354. ..hap: Hamarsoft HAP archiver (Markov modeling + arithmetic coding)
  355.       Contact: feldmann@xs4all.nl or feldmann@pi.net
  356.         ftp://garbo.uwasa.fi/pc/arcers/hap305bp.com
  357.         http://www.xs4all.nl/~feldmann
  358.  
  359. ..hpk: hpack (archiver with strong encryption)
  360.       Contact: Peter Gutmann <pgut1@cs.aukuni.ac.nz>
  361.         ftp://src.doc.ic.ac.uk/computing/archiving/compress/hpack/
  362.  
  363. ..hqx: Macintosh BinHex format.. (BinHex is *not* a compression program,
  364.       it is similar to uuencode but handles multiple forks.)
  365.        for Mac:
  366.     ftp://mac.archive.umich.edu/mac/utilities/compressionapps/binhex4.0.bin
  367.  
  368.        for Unix:
  369.          ftp://sumex-aim.stanford.edu/info-mac/cmp/mcvert-216.shar
  370.  
  371.        for MSDOS:
  372.      ftp://ftp.simtel.net/pub/simtelnet/msdos/mac/xbin23.zip
  373.          ftp://garbo.uwasa.fi/pc/unix/xbin23.zip
  374.  
  375. ..jam: JAM real-time compressor for MSDOS
  376.        ftp://garbo.uwasa.fi/pc/arcers/jam125sw.zip
  377.  
  378. ..lha:
  379. ..lzh: lha for MSDOS (LZ77 with a trie data structure, plus secondary static
  380.           Huffman coding on a block basis)
  381.     ftp://ftp.simtel.net/pub/simtelnet/msdos/arcers/lha255e.exe
  382.     ftp://garbo.uwasa.fi/pc/arcers/lha255b.exe
  383.  
  384.       lharc for Unix. (LZ77 with hash table and binary trees, plus secondary
  385.           Huffman coding)
  386.            Warning: lharc can extract .lzh files created by
  387.            lharc 1.xx but not those created by lha. See lha for Unix below.
  388.         ftp://wuarchive.wustl.edu/mirrors/misc/unix/lharc102a.tar-z
  389.     ftp://garbo.uwasa.fi/unix/arcers/lha101u.tar.Z
  390.  
  391.       lharc for VMS. Same warning as for Unix lharc.
  392.     ftp://wuarchive.wustl.edu/packages/compression/vax-vms/lharc.exe
  393.  
  394.       lha for Unix. Warning: all doc is in Japanese.
  395.     ftp://wuarchive.wustl.edu/mirrors/misc/unix/lha101u.tar-z
  396.     ftp://garbo.uwasa.fi/unix/arcers/lha-1.00.tar.Z
  397.           Contact: lha-admin@oki.co.jp or oki@fs.telcom.oki.ac.jp
  398.       lha for Mac
  399.     ftp://mac.archive.umich.edu/mac/utilities/compressionapps/maclha2.0.cpt.hqx
  400.       lha for Amiga
  401.     ftp://ftp.funet.fi/pub/amiga/utilities/archivers/LhA_e138.run
  402.       lha for OS/2:
  403.     ftp://hobbes.nmsu.edu/os2/16bit/archiver/lh2_222.zip
  404.  
  405. MIME: see base64 above
  406.  
  407. ..pak: pak for MSDOS (LZW algorithm)
  408.         ftp://ftp.simtel.net/pub/simtelnet/msdos/arcers/pak251.exe
  409.     ftp://garbo.uwasa.fi/pc/arcers/pak251.exe
  410.  
  411. ..pit: PackIt (Macintosh)
  412.        for Mac:
  413.          ftp://sumex-aim.stanford.edu/info-mac/cmp/stuffit-lite-35.hqx
  414.  
  415.        for Unix:
  416.          ftp://sumex-aim.stanford.edu/info-mac/cmp/mcvert-215.shar.gz
  417.          ftp://garbo.uwasa.fi/mac/arcers/mcvert-215.shar
  418.  
  419. ..pp: PowerPacker (Amiga)
  420.     ftp.funet.fi:pub/amiga/fish/501-600/ff561/PPLib.lha
  421.  
  422. ..rar: RAR (MSDOS) Contact: Eugene_Roshal@p0.f23.n5010.z2.fidonet.org
  423.           or Andrey Spasibozhko <as@hq.icb.chel.su>
  424.         ftp://ftp.simtel.net/pub/simtelnet/msdos/arcers/rar200.exe
  425.         ftp://garbo.uwasa.fi/pc/arcers/rar200.exe
  426.         ftp://ftp.kiae.su/msdos/arcers/rar*.exe
  427.         ftp://ftp.elf.stuba.sk/pub/pc/pack/*rar2*.exe
  428.  
  429. ..sea: self-extracting archive (Macintosh)
  430.          Run the file to extract it. The self-extraction code can be
  431.          removed with:
  432.     ftp://mac.archive.umich.edu/mac/utilities/compressionapps/desea1.11.cpt.hqx
  433.     ftp://ftp.scruz.net/users/aladdin/public/SITEX10.EXE (MS Windows)
  434.  
  435. ..sdn: used by the Shareware Distribution Network.
  436.       Try the decompressors for .pak or .arj (see above)
  437.  
  438. ..shar:  Shell archive. This is not a compression program. Use "sh foo.shar"
  439.         to extract on Unix. For MSDOS, use:
  440.     ftp://garbo.uwasa.fi/pc/unix/unshar.zip
  441.  
  442. ..sit: Stuffit for Macintosh
  443.        for Mac:
  444.          ftp://sumex-aim.stanford.edu/info-mac/cmp/stuffit-lite-35.hqx
  445.  
  446.        for Unix:
  447.          ftp://sumex-aim.stanford.edu/info-mac/cmp/unsit-15-unix.shar
  448.  
  449.        for Amiga:
  450.      ftp.funet.fi:pub/amiga/utilities/archivers/unsit-1.5c2.lha
  451.  
  452.        for MSDOS:
  453.      ftp://ftp.scruz.net/users/aladdin/public/SITEX10.EXE
  454.      ftp://garbo.uwasa.fi/pc/arcers/unsit30.zip
  455.  
  456. ..?q?: Squeeze for MSDOS (do not confuse with other 'squeeze' below).
  457.       Static Huffman coding.
  458.        ftp://ftp.simtel.net/pub/simtelnet/msdos/starter/sqpc12a.com (squeeze)
  459.        ftp://ftp.simtel.net/pub/simtelnet/msdos/starter/nusq110.com (unsqueeze)
  460.  
  461. ..sqz: Squeeze for MSDOS (do not confuse with other 'squeeze' above)
  462.       LZ77 with hashing.
  463.         ftp://ftp.simtel.net/pub/simtelnet/msdos/arcers/sqz1083e.exe
  464.         ftp://garbo.uwasa.fi/pc/arcers/sqz1083e.exe
  465.  
  466. ..tar: tar is *not* a compression program. However, to be kind for you:
  467.       for MSDOS
  468.     ftp://ftp.simtel.net/pub/simtelnet/msdos/starter/tarread.exe
  469.     ftp://garbo.uwasa.fi/pc/unix/tar4dos.zoo
  470.  
  471.       for Unix
  472.         tar (you have it already. To extract: tar xvf file.tar)
  473.  
  474.       for VMS
  475.     ftp://wuarchive.wustl.edu/packages/compression/vax-vms/tar.exe
  476.  
  477.       for Macintosh
  478.         ftp://sumex-aim.stanford.edu/info-mac/util/tar-30.hqx
  479.  
  480.       for Amiga:
  481.     ftp.funet.fi:pub/amiga/fish/401-500/ff445/Tar.lha
  482.  
  483. ..tar.Z, .tar-z, .taz: tar + compress
  484.       For Unix:     zcat file.tar.Z | tar xvf -
  485.       with GNU tar: tar xvzf file.tar.Z
  486.       for MSDOS:
  487.         ftp://garbo.uwasa.fi/pc/unix/tar320g.zip  (MSDOS exe)
  488.         ftp://ftp.kiae.su/msdos/arcers/tar*sr.zip (sources)
  489.         ftp://ftp.kiae.su/msdos/arcers/tar*_p.zip (MSDOS exe)
  490.       Other OS: first uncompress (see .Z below) then untar (see .tar above)
  491.  
  492. ..tar.gz, .tgz, .tar-gz, .tar.z: tar + gzip
  493.       For Unix: gzip -cd file.tar.gz | tar xvf -
  494.         with GNU tar: tar xvzf file.tar.gz
  495.       for MSDOS:
  496.         ftp://ftp.simtel.net/pub/simtelnet/msdos/arcers/tar320g.zip
  497.         ftp://garbo.uwasa.fi/pc/unix/tar320g.zip
  498.         ftp://garbo.uwasa.fi/pc/unix/untgz094.zip
  499.          or http://www.schlund.de/privat/tst/untgz.htm
  500.       Other OS: first uncompress (see .gz above) then untar (see .tar above)
  501.  
  502. ..td0: (compressed MS-DOS floppy image produced by TeleDisk)
  503.       ftp://ftp.simtel.net/pub/simtelnet/msdos/diskutil/teled212.zip
  504.  
  505. ..uc2: UC2 for MSDOS and OS/2. (LZ77 with secondary static Huffman encoding on
  506.      a block basis, and dynamic dictionaries shared among files.)
  507.     Contact: desk@aip.nl
  508.       ftp://garbo.uwasa.fi/pc/arcers/uc2r3.exe  (or uc2pro.exe)
  509.  
  510. ..z:   pack or gzip (see .gz above). pack uses static Huffman coding.
  511.       To extract, see .gz above.
  512.  
  513. ..zip: pkzip 2.04g for MSDOS. (LZ77 with hashing, plus secondary static
  514.            Huffman coding on a block basis). Contact: support@pkware.com
  515.            or http://www.pkware.com/
  516.      ftp://ftp.simtel.net/pub/simtelnet/msdos/zip/pkz204g.exe
  517.          ftp://garbo.uwasa.fi/pc/arcers/pkz204g.exe
  518.          ftp://garbo.uwasa.fi/windows/util/pkzws201.exe (Windows version)
  519.  
  520.       arcutil 2.0 for VM/CMS (unzip only, not yet compatible with pkzip 2.04)
  521.          ftp://vmd.cso.uiuc.edu/public.477/arcutil.*
  522.  
  523.       zip 1.1 for Unix, MSDOS, VMS, OS/2, ... (compatible with pkzip 1.10.
  524.      For corresponding unzip, see unzip 5.12 below).
  525.      ftp://ftp.uu.net/pub/archiving/zip/zip11.zip
  526.  
  527.       zip 2.1 and unzip 5.20 for Unix, MSDOS, VMS, OS/2, Amiga, ...
  528.           Compatible with pkzip 2.04g (LZ77 with hashing, plus secondary static
  529.           Huffman coding on a block basis). Contact: zip-bugs@lists.wku.edu
  530.           See also http://quest.jpl.nasa.gov/Info-ZIP/
  531.           (On SGI, do not confuse with the editor also named 'zip'.)
  532.  
  533.      ftp://ftp.uu.net/pub/archiving/zip/zip21.zip          (source)
  534.      ftp://ftp.uu.net/pub/archiving/zip/unzip52.*          (source)
  535.      ftp://ftp.uu.net/pub/archiving/zip/MSDOS/zip21x.zip   (MSDOS exe)
  536.      ftp://ftp.uu.net/pub/archiving/zip/MSDOS/unz520x*.exe (MSDOS exe)
  537.      ftp://ftp.uu.net/pub/archiving/zip/WIN32/zip21xN.zip  (Win95 & NT)
  538.      ftp://ftp.uu.net/pub/archiving/zip/WIN32/unz520xN.exe (Win95 & NT)
  539.          [The Win95 version supports long file names; MSDOS version doesn't]
  540.      ftp://ftp.uu.net/pub/archiving/zip/OS2/*          (OS/2 exe 16&32 bit)
  541.           See also AMIGA, ATARI, MAC, UNIX, RISCOS, VMS... subdirectories.
  542.       If ftp.uu.net not available, use ftp://nic.switch.ch/mirror/Info-Zip/
  543.  
  544.      ftp://ftp.uu.net/pub/archiving/zip/zcrypt26.zip    (encryption source)
  545.          Non US residents must get the crypt versions from nic.switch.ch
  546.  
  547.        for Macintosh:
  548.          ftp://mac.archive.umich.edu/mac/util/compression/unzip2.01.cpt.hqx
  549.      ftp://mac.archive.umich.edu/mac/util/compression/zipit1.31.cpt.hqx
  550.      ftp://ftp.uu.net/pub/archiving/zip/MAC/unz512x.hqx
  551.     ftp://wuarchive.wustl.edu/systems/mac/info-mac/cmp/stuffit-expander-352.hqx
  552.  
  553.        WinZip by Nico Mak <support@winzip.com> (uses Info-ZIP compress. code):
  554.          ftp://ftp.winzip.com/winzip/                    (MS Windows)
  555.  
  556. ..zoo: zoo 2.10 for MSDOS (algorithm copied from that of lha, see lha above)
  557.       Contact: Rahul Dhesi <dhesi@cirrus.com>
  558.      ftp://wuarchive.wustl.edu/mirrors/msdos/zoo/zoo210.exe
  559.      ftp://garbo.uwasa.fi/pc/arcers/zoo210.exe
  560.  
  561.       zoo 2.10 for Unix, VMS
  562.          ftp://oak.oakland.edu/pub/misc/unix/zoo210.tar.Z
  563.      ftp://garbo.uwasa.fi/unix/arcers/zoo210.tar.Z
  564.  
  565.       zoo for Mac
  566.        ftp://mac.archive.umich.edu/mac/utilities/compressionapps/maczoo.sit.hqx
  567.  
  568.       zoo for Amiga
  569.     ftp://ftp.funet.fi/pub/amiga/utilities/archivers/Zoo-2.1.lha
  570.  
  571. ..??_: Microsoft compress.exe and expand.exe. compress.exe is available
  572.     in the Windows SDK (Software Development Kit) and in
  573.        ftp://ftp.microsoft.com/softlib/mslfiles/CP0982.EXE
  574.  
  575. ..F: freeze for Unix (LZ77 with hashing, plus secondary dynamic Huffman
  576.          encoding)
  577. ftp://wuarchive.wustl.edu/usenet/comp.sources.misc/volume35/freeze/part0[1-3].Z
  578.      ftp://ftp.inria.fr/system/arch-compr/freeze-2.5.tar.Z
  579.      Contact: Leonid A. Broukhis <leo@zycad.com>
  580.  
  581. ..Y: yabba for Unix, VMS, ... (Y coding, a variant of LZ78)
  582.   ftp://wuarchive.wustl.edu/usenet/comp.sources.unix/volume24/yabbawhap/part*.Z
  583.   ftp://ftp.inria.fr/system/arch-compr/yabba.tar.Z
  584.   Contact: Dan Bernstein <djb@silverton.berkeley.edu>
  585.  
  586. ..Z: compress for Unix ('the' LZW algorithm)
  587.       It is likely that your Unix system has 'compress' already. Otherwise:
  588.     ftp://wuarchive.wustl.edu/packages/compression/compress-4.1.tar
  589.         (not in .Z format to avoid chicken and egg problem)
  590.  
  591.     compress for MSDOS
  592.     ftp://ftp.simtel.net/pub/simtelnet/msdos/compress/comp430d.zip
  593.     ftp://garbo.uwasa.fi/pc/unix/comp430d.zip
  594.     ftp://garbo.uwasa.fi/pc/source/comp430s.zip
  595.  
  596.     compress for Macintosh
  597.     ftp://wuarchive.wustl.edu/systems/mac/info-mac/cmp/stuffit-expander-352.hqx
  598.         ftp://sumex-aim.stanford.edu/info-mac/cmp/maccompress-32.hqx
  599.  
  600.     compress for Amiga
  601.     ftp.funet.fi:pub/amiga/utilities/archivers/compress-4.1.lha
  602.  
  603.     compress for VAX/VMS
  604.     ftp://wuarchive.wustl.edu/packages/compression/vax-vms/lzcomp.exe
  605.     ftp://wuarchive.wustl.edu/packages/compression/vax-vms/lzdcmp.exe
  606.  
  607. ------------------------------------------------------------------------------
  608.  
  609. Subject: [3]  What is the latest PKZIP version?
  610.  
  611. The latest official DOS version is 2.04g. Release 2.04c had serious bugs,
  612. corrected in 2.04e and 2.04g. The latest Windows version is pkzws201.exe.
  613.  
  614. Be warned that there are countless bogus PKZIP 1.20, 2.0, 2.02, 3.00B,
  615. 3.05, 4.1 and whatever scams floating around.  They usually are hacks
  616. of PKZIP 1.93A beta test version.  Some of them are trojans and / or
  617. carry computer virii.
  618.  
  619. Note about pkzip 2.06 from a PKware employee:
  620.  
  621.     Version 2.06 was released as an INTERNAL use only IBM version.
  622.     It is identical to 2.04G, but it has IBM names in the help
  623.     screens and such. That release is meant for IBM only.
  624.  
  625. If pkunzip indicates that you need version 2.8 to extract an
  626. archive, your archive has been corrupted by a transfer not
  627. made in binary mode (see item 30 below).
  628. ------------------------------------------------------------------------------
  629.  
  630. Subject: [4] What is an archiver?
  631.  
  632.  
  633. There is a distinction between archivers and other compression
  634. programs:
  635.  
  636. - an archiver takes several input files, compresses them and produces
  637.   a single archive file. Examples are arc, arj, lha, zip, zoo.
  638.  
  639. - other compression programs create one compressed file for each
  640.   input file. Examples are freeze, yabba, compress, gzip. Such programs
  641.   are often combined with tar to create compressed archives (see
  642.   question 50: "What is this tar compression program?").
  643.  
  644. For a comparison of zip and gzip, see the gzip README file. (In short:
  645. zip is an archiver, gzip is not; only zip is compatible with pkzip.)
  646.  
  647. ------------------------------------------------------------------------------
  648.  
  649. Subject: [5] What is the best general purpose compression program?
  650.  
  651.  
  652. The answer is: it depends. (You did not expect a definitive answer,
  653. did you?)
  654.  
  655. It depends whether you favor speed, compression ratio, a standard and
  656. widely used archive format, the number of features, etc...  Just as
  657. for text editors, personal taste plays an important role. compress has
  658. 4 options, arj 2.30 has about 130 options; different people like
  659. different programs. *Please* do not start or continue flame wars on
  660. such matters of taste.
  661.  
  662. Several benchmarks of MSDOS archivers are available:
  663. - ftp://ftp.simtel.net/pub/simtelnet/msdos/arcers/actest*.zip
  664.   and http://www.geocities.com/SiliconValley/Park/4264/act.html
  665.   by Jeff Gilchrist <jeffg@nbnet.nb.ca>
  666. - ftp://garbo.uwasa.fi/pc/arcers/act-*.zip
  667.   by Jonathan Burt <jonathan@jaburt.demon.co.uk>
  668.  
  669. Please do not post your own benchmarks made on your own files that
  670. nobody else can access. If you think that you must absolutely post yet
  671. another benchmark, make sure that your test files are available by
  672. anonymous ftp.
  673.  
  674. Since all other benchmarks are for MSDOS only, here is one mainly for
  675. Unix, on a 33Mhz Compaq 386.  All programs have been run on Unix SVR4,
  676. except pkzip and arj which only run on MSDOS.
  677.  
  678. The programs compared here were chosen because they are the most
  679. popular or because they run on Unix and source is available.  For ftp
  680. information, see above. Three programs (hpack, comp-2 and ha) have
  681. been added because they achieve better compression (at the expense of
  682. speed) and one program (lzrw3-a) has been added because it favors
  683. speed at the expense of compression:
  684.  
  685. - comp-2 is in ftp://wuarchive.wustl.edu/mirrors/msdos/ddjmag/ddj9102.zip
  686.   (inner zip file nelson.zip),
  687. - hpack is in ftp://garbo.uwasa.fi/unix/arcers/hpack78src.tar.Z
  688. - ha 0.98 is in ftp://garbo.uwasa.fi/pc/arcers/ha098.zip
  689. - lzrw3-a is in http://wwwvms.utexas.edu/~cbloom/src/lzrw.zip
  690.  
  691. The 14 files used in the comparison are from the standard Calgary
  692. Text Compression Corpus, available in
  693. ftp://ftp.cpsc.ucalgary.ca/pub/projects/text.compression.corpus/
  694.  
  695. The whole corpus includes 18 files, but the 4 files paper[3-6] are
  696. generally omitted in benchmarks. It contains several kinds of file
  697. (ascii, binary, image, etc...) but has a bias towards large files.
  698. You may well get different ratings on the typical mix of files that
  699. you use daily, so keep in mind that the comparisons given below are
  700. only indicative.
  701.  
  702. The programs are ordered by decreasing total compressed size. For a
  703. fair comparison between archivers and other programs, this size is
  704. only the size of the compressed data, not the archive size.
  705.  
  706. The programs were run on an idle machine, so the elapsed time
  707. is significant and can be used to compare Unix and MSDOS programs.
  708.  
  709. [Note: These benchmarks are now very old. I have to do them again
  710. on more recent hardware with the latest programs.]
  711.  
  712.        size     lzrw3a   compress    lharc    yabba     pkzip    freeze 
  713. version:                   4.0       1.02      1.0       1.10     2.3.5
  714. options:                                    -m300000                    
  715.        ------    -----    ------    ------    ------    ------   ------
  716. bib    111261    49040     46528     46502     40456     41354    41515 
  717. book1  768771   416131    332056    369479    306813    350560   344793 
  718. book2  610856   274371    250759    252540    229851    232589   230861 
  719. geo    102400    84214     77777     70955     76695     76172    68626 
  720. news   377109   191291    182121    166048    168287    157326   155783 
  721. obj1    21504    12647     14048     10748     13859     10546    10453 
  722. obj2   246814   108040    128659     90848    114323     90130    85500 
  723. paper1  53161    24522     25077     21748     22453     20041    20021 
  724. paper2  82199    39479     36161     35275     32733     32867    32693 
  725. pic    513216   111000     62215     61394     65377     63805    53291 
  726. progc   39611    17919     19143     15399     17064     14164    14143 
  727. progl   71646    24358     27148     18760     23512     17255    17064 
  728. progp   49379    16801     19209     12792     16617     11877    11686 
  729. trans   93695    30292     38240     28092     31300     23135    22861 
  730.     3,141,622  1,400,105 1,259,141 1,200,580 1,159,340 1,141,821 1,109,290
  731. real             0m35s     0m59s     5m03s     2m40s              5m27s
  732. user             0m25s     0m29s     4m29s     1m46s              4m58s
  733. sys              0m05s     0m10s     0m07s     0m18s              0m08s
  734. MSDOS:                                                   1m39s
  735.                         
  736.  
  737.          zoo       lha       arj      pkzip    zip      hpack   comp-2    ha
  738.         2.10    1.0(Unix)   2.30      2.04g    1.9      0.75a            0.98
  739.          ah    2.13(MSDOS)   -jm       -ex      -6                        a2
  740.        ------    ------    ------    ------  -------   ------   ------  ------
  741. bib     40742     40740     36090    35126    34950    35619    29840   26927
  742. book1  339076    339074    318382   312490   312619   306876   237380  235733
  743. book2  228444    228442    210521   206513   206306   208486   174085  163535
  744. geo     68576     68574     69209    68706    68418    58976    64590   59356
  745. news   155086    155084    146855   144545   144395   141608   128047  123335
  746. obj1    10312     10310     10333    10306    10295    10572    10819    9799
  747. obj2    84983     84981     82052    81132    81336    80806    85465   80381
  748. paper1  19678     19676     18710    18531    18525    18607    16895   15675
  749. paper2  32098     32096     30034    29568    29674    29825    25453   23956
  750. pic     52223     52221     53578    52409    55051    51778    55461   51639
  751. progc   13943     13941     13408    13341    13238    13475    12896   11795
  752. progl   16916     16914     16408    16122    16175    16586    17354   15298
  753. progp   11509     11507     11308    11200    11182    11647    11668   10498
  754. trans   22580     22578     20046    19462    18879    20506    21023   17927
  755.     1,096,166 1,096,138 1,036,934 1,019,451 1,021,043 1,005,367 890,976 845,854
  756. real    4m07s     6m03s                        1m49s   1h22m17s  27m05s
  757. user    3m47s     4m23s                        1m43s   1h20m46s  19m27s
  758. sys     0m04s     0m08s                        0m02s      0m12s   2m03s
  759. MSDOS:            1m49s     2m41s     1m43s                              14m43s
  760.  
  761. Notes:
  762.  
  763. - the compressed data for 'zoo ah' is always two bytes longer than for
  764.   lha. This is simply because both programs are derived from the same
  765.   source (ar002, written by Haruhiko Okumura, available by ftp in
  766.   ftp://ftp.simtel.net/pub/simtelnet/msdos/arcers/ar002.zip).
  767.  
  768. - hpack 0.75a gives slightly different results on SunOS. (To be checked
  769.   with latest version of hpack).
  770.  
  771. - the MSDOS versions are all optimized with assembler code and were run
  772.   on a RAM disk. So it is not surprising that they often go faster than
  773.   their Unix equivalent.
  774.  
  775. ------------------------------------------------------------------------------
  776.  
  777. Subject: [7] Which books should I read?
  778.  
  779.  
  780. [BWC 1989] Bell, T.C, Cleary, J.G. and Witten, I.H, "Text Compression",
  781.     Prentice-Hall 1989. ISBN: 0-13-911991-4. Price: approx. US$60
  782.     The reference on text data compression.
  783.  
  784. [Nel 1996] Mark Nelson & Jean-loup Gailly, "The Data Compression Book",
  785.     2nd edition. M&T Books, New York, NY 1996. ISBN 1-55851-434-1
  786.     541 pages. List price in the US is $39.95 including one PC-compatible
  787.     disk bearing all the source code printed in the book.
  788.     A practical introduction to data compression.
  789.     The book is targeted at a person who is comfortable reading C code but
  790.     doesn't know anything about data compression.  Its stated goal is to get
  791.     you up to the point where you are competent to program standard
  792.     compression algorithms.
  793.  
  794. [Will 1990] Williams, R.  "Adaptive Data Compression", Kluwer Books, 1990.
  795.     ISBN: 0-7923-9085-7. Price: US$75.
  796.     Reviews the field of text data compression and then addresses the
  797.     problem of compressing rapidly changing data streams.
  798.  
  799. [Stor 1988] Storer, J.A.  "Data Compression: Methods and Theory", Computer
  800.     Science Press, Rockville, MD. ISBN: 0-88175-161-8.
  801.     A survey of various compression techniques, mainly statistical
  802.     non-arithmetic compression and LZSS compression.  Includes complete Pascal
  803.     code for a series of LZ78 variants.
  804.  
  805. [Stor 1992] Storer, J.A. "Image and Text Compression", Kluwer Academic
  806.     Publishers, 1992, ISBN 0-7923-9243-4
  807.  
  808. [Say 1996] Sayood, Khalid. "Introduction to Data Compression",
  809.   San Francisco:  Morgan Kaufmann Publishers, 1996. ISBN 1-55860-346-8;
  810.   US&Canada $64.95. More info in http://www.mkp.com/pages/3468/index.html
  811.   The book covers both lossy and lossless compression techniques and their
  812.   applications to image, speech, text, audio, and video compression.
  813.  
  814. [BK 95] Bhaskaran V. and Konstantinides K., "Image and Video Compression
  815.     Standards: Algorithms and Architectures", Kluwer Academic Publishers, 1995.
  816.     ISBN 0-7923-9591-3
  817.  
  818. [ACG 1991] Advances in Speech Coding, edited by Atal, Cuperman, and Gersho,
  819.     Kluwer Academic Press, 1991.
  820.  
  821. [GG 1991] Vector Quantization and Signal Compression, by Gersho and Gray,
  822.     Kluwer Acad. Press, 1991, ISBN 0-7923-9181-0.
  823.  
  824. [CT 1991] Elements of Information Theory, by T.M.Cover and J.A.Thomas
  825.      John Wiley & Sons, 1991. ISBN 0-471-06259-6.
  826.  
  827. Review papers:
  828.  
  829. [BWC 1989] Bell, T.C, Witten, I.H, and Cleary, J.G.  "Modeling for Text
  830.     Compression", ACM Computing Surveys, Vol.21, No.4 (December 1989), p.557
  831.     A good general overview of compression techniques (as well as modeling for
  832.     text compression); the condensed version of "Text Compression".
  833.  
  834. [Lele 1987] Lelewer, D.A, and Hirschberg, D.S.  "Data Compression", ACM
  835.     Computing Surveys, Vol.19, No.3 (September 1987), p.261.
  836.     A survey of data compression techniques which concentrates on Huffman
  837.     compression and makes only passing mention of other techniques.
  838.  
  839.  
  840. ------------------------------------------------------------------------------
  841.  
  842. Subject: [8] What about patents on data compression algorithms?
  843.  
  844.  
  845. [Note: the appropriate group for discussing software patents is
  846. comp.patents or misc.legal.computing, not comp.compression.]
  847.  
  848. Only a very small subset of all patents on data compression are mentioned
  849. here; there are several hundred patents on lossless data compression alone.
  850. All patents mentioned here are US patents, and thus probably not applicable
  851. outside the US.  See item 70, "Introduction to data compression" for the
  852. meaning of LZ77, LZ78 or LZW.
  853.  
  854.  
  855. (a) Run length encoding
  856.  
  857. - Tsukiyama has two patents on run length encoding: 4,586,027 and 4,872,009
  858.   granted in 1986 and 1989 respectively. The first one covers run length
  859.   encoding in its most primitive form: a length byte followed by the
  860.   repeated byte. The second patent covers the 'invention' of limiting the
  861.   run length to 16 bytes and thus the encoding of the length on 4 bits.
  862.   Here is the start of claim 1 of patent 4,872,009, just for pleasure:
  863.  
  864.     1. A method of transforming an input data string comprising a plurality
  865.     of data bytes, said plurality including portions of a plurality of
  866.     consecutive data bytes identical to one another, wherein said data
  867.     bytes may be of a plurality of types, each type representing different
  868.     information, said method comprising the steps of: [...]
  869.  
  870. - O'Brien has patented (4,988,998) run length encoding followed by LZ77.
  871.  
  872.  
  873. (b) LZ77
  874.  
  875. - Waterworth patented (4,701,745) the algorithm now known as LZRW1,
  876.   because Ross Williams reinvented it later and posted it on
  877.   comp.compression on April 22, 1991. (See item 5 for the ftp site
  878.   with all LZRW derivatives.) The *same* algorithm has later been
  879.   patented by Gibson & Graybill (see below). The patent office failed
  880.   to recognize that the same algorithm was patented twice, even though
  881.   the wording used in the two patents is very similar.
  882.  
  883.   The Waterworth patent is now owned by Stac Inc, which won a lawsuit
  884.   against Microsoft, concerning the compression feature of MSDOS 6.0.
  885.   Damages awarded were $120 million. (Microsoft and Stac later
  886.   settled out of court.)
  887.  
  888. - Fiala and Greene obtained in 1990 a patent (4,906,991) on all
  889.   implementations of LZ77 using a tree data structure. Claim 1 of the
  890.   patent is much broader than the algorithms published by Fiala and
  891.   Greene in Comm.ACM, April 89. The patent covers the algorithm
  892.   published by Rodeh and Pratt in 1981 (J. of the ACM, vol 28, no 1,
  893.   pp 16-24).  It also covers the algorithms used in lharc, lha and zoo.
  894.  
  895. - Notenboom (from Microsoft) 4,955,066 uses three levels of
  896.   compression, starting with run length encoding.
  897.  
  898. - The Gibson & Graybill patent 5,049,881 covers the LZRW1 algorithm
  899.   previously patented by Waterworth and reinvented by Ross Williams.
  900.   Claims 4 and 12 are very general and could be interpreted as
  901.   applying to any LZ algorithm using hashing (including all variants
  902.   of LZ78):
  903.  
  904.      4. A compression method for compressing a stream of input data into
  905.      a compressed stream of output data based on a minimum number of
  906.      characters in each input data string to be compressed, said
  907.      compression method comprising the creation of a hash table, hashing
  908.      each occurrence of a string of input data and subsequently searching
  909.      for identical strings of input data and if such an identical string
  910.      of input data is located whose string size is at least equal to the
  911.      minimum compression size selected, compressing the second and all
  912.      subsequent occurrences of such identical string of data, if a string
  913.      of data is located which does not match to a previously compressed
  914.      string of data, storing such data as uncompressed data, and for each
  915.      input strings after each hash is used to find a possible previous
  916.      match location of the string, the location of the string is stored
  917.      in the hash table, thereby using the previously processed data to
  918.      act as a compression dictionary.
  919.  
  920.   Claim 12 is identical, with 'method' replaced with 'apparatus'.  Since
  921.   the 'minimal compression size' can be as small as 2, the claim could
  922.   cover any dictionary technique of the LZ family. However the text of the
  923.   patent and the other claims make clear that the patent should cover the
  924.   LZRW1 algorithm only. (In any case the Gibson & Graybill patent is likely
  925.   to be invalid because of the prior art in the Waterworth patent.)
  926.  
  927. - Phil Katz, author of pkzip, also has a patent on LZ77 (5,051,745)
  928.   but the claims only apply to sorted hash tables, and when the hash
  929.   table is substantially smaller than the window size.
  930.  
  931. - IBM patented (5,001,478) the idea of combining a history buffer (the
  932.   LZ77 technique) and a lexicon (as in LZ78).
  933.  
  934. - Stac Inc patented (5,016,009 and 5,126,739) yet another variation of LZ77
  935.   with hashing. The '009 patent was used in the lawsuit against Microsoft
  936.   (see above). Stac also has a patent on LZ77 with parallel lookup in
  937.   hardware (5,003,307).
  938.  
  939. - Robert Jung, author of 'arj', has been granted patent 5,140,321
  940.   for one variation of LZ77 with hashing.  This patent covers the LZRW3-A
  941.   algorithm, also previously discovered by Ross Williams. LZRW3-A was posted
  942.   on comp.compression on July 15, 1991. The patent was filed two months later
  943.   on Sept 4, 1991. (The US patent system allows this because of the
  944.   'invention date' rule.)
  945.  
  946. - Chambers 5,155,484 is yet another variation of LZ77 with hashing.
  947.   The hash function is just the juxtaposition of two input bytes,
  948.   this is the 'invention' being patented. The hash table is named
  949.   'direct lookup table'.
  950.  
  951.  
  952. (c) LZ78
  953.  
  954. - One form of the original LZ78 algorithm was patented (4,464,650) by
  955.   its authors Lempel, Ziv, Cohn and Eastman. This patent is owned
  956.   by Unisys.
  957.  
  958.  
  959. - The LZW algorithm used in 'compress' is patented by IBM (4,814,746)
  960.   and Unisys (4,558,302). It is also used in the V.42bis compression
  961.   standard (see question 11 on V.42bis below), in Postscript Level 2, in
  962.   GIF and TIFF.  Unisys sells the license to modem manufacturers for a
  963.   onetime fee (contact: Welch Patent Desk, Unisys Corp., P.O. Box 500,
  964.   Bluebell, PA 19424 Mailcode C SW 19). CompuServe is licensing the
  965.   usage of LZW in GIF products for 1.5% of the product price, of which
  966.   1% goes to Unisys; usage of LZW in non-GIF products must be licensed
  967.   directly from Unisys. For more information, see http://www.unisys.com/
  968.   or email to lzw_info@unisys.com.
  969.  
  970.      The IBM patent application was first filed three weeks before that of
  971.   Unisys, but the US patent office failed to recognize that they
  972.   covered the same algorithm. (The IBM patent is more general, but its
  973.   claim 7 is exactly LZW.)
  974.  
  975. - Klaus Holtz also claims that patent 4,366,551 for his "autosophy"
  976.   data compression method covers LZ78 and LZW. According to Holtz, most of
  977.   the largest V.42bis modem manufacturers have paid for patent licenses.
  978.  
  979. - AP coding is patented by Storer (4,876,541). (Get the yabba package
  980.   for source code, see question 2 above, file type .Y) Storer also
  981.   claims that his patent covers V.42bis.
  982.  
  983.  
  984. (d) arithmetic coding
  985.  
  986. - IBM holds many patents on arithmetic coding (4,122,440 4,286,256 4,295,125
  987.   4,463,342 4,467,317 4,633,490 4,652,856 4,792,954 4,891,643 4,901,363
  988.   4,905,297 4,933,883 4,935,882 5,045,852 5,142,283 5,210,536 5,414,423
  989.   5,546,080). It has patented in particular the Q-coder implementation of
  990.   arithmetic coding.  The JBIG standard, and the arithmetic coding option of
  991.   the JPEG standard requires use of the patented algorithm.  No JPEG-compatible
  992.   method is possible without infringing the patent, because what IBM actually
  993.   claims rights to is the underlying probability model (the heart of an
  994.   arithmetic coder). (See item 75 for details.)
  995.  
  996.   See also below details on many other patents on arithmetic coding (4,973,961
  997.   4,989,000 5,023,611 5,025,258 5,099,440 5,272,478 5,307,062 5,309,381
  998.   5,311,177 5,363,099 5,404,140 5,406,282 5,418,532). The list is not
  999.   exhaustive.
  1000.  
  1001.  
  1002. (e) predictor
  1003.  
  1004. - The 'predictor' algorithm was first described in the paper
  1005.  
  1006.     Raita, T. and Teuhola, J. (1987), "Predictive text compression by hashing",
  1007.     ACM Conference on Information Retrieval
  1008.  
  1009.   This algorithm has been patented (5,229,768) by K. Thomas in 1993. It
  1010.   is used in the Internet Draft "PPP Predictor Compression Protocol" (see
  1011.   ftp://venera.isi.edu/internet-drafts/draft-ietf-pppext-predictor-00.txt).
  1012.  
  1013. (f) compression of random data
  1014.  
  1015. - The US patent office no longer grants patents on perpetual motion machines,
  1016.   but has recently granted a patent on a mathematically impossible process
  1017.   (compression of truly random data): 5,533,051 "Method for Data Compression".
  1018.   See item 9.5 of this FAQ for details.
  1019.  
  1020.  
  1021. As can be seen from the above list, some of the most popular compression
  1022. programs (compress, pkzip, zoo, lha, arj) are now covered by patents.
  1023. (This says nothing about the validity of these patents.)
  1024.  
  1025. Here are some references on data compression patents. Some of them are
  1026. taken from the list ftp://prep.ai.mit.edu/pub/lpf/patent-list.
  1027.  
  1028. 3,914,586
  1029. Data compression method and apparatus
  1030. filed 10/25/73, granted 10/21/75
  1031. General Motors Corporation, Detroit MI
  1032. Duane E. McIntosh, Santa Ynez CA
  1033. Data compression apparatus is disclosed is operable in either a bit
  1034. pair coding mode of a word coding mode depending on the degree of
  1035. redundancy of the data to be encoded.
  1036.  
  1037. 3,976,844
  1038. Data communication system for transmitting data in compressed form
  1039. filed Apr. 4, 1975, granted Aug. 24, 1976
  1040. inventor  Bernard K. Betz, assignee Honeywell Information Systems, Inc.
  1041. [encode differences with previous line]
  1042.  
  1043. 4,021,782
  1044. Data compaction system and apparatus
  1045. inventor Hoerning
  1046. filed 04/30/1975, granted 05/03/1977
  1047. [A primitive form of LZ77 with implicit offsets (compare with previous record)]
  1048.  
  1049. 4,054,951
  1050. Data expansion apparatus
  1051. inventor R.D. Jackson, assignee IBM
  1052. filed Jun. 30, 1976, granted Oct. 18, 1977
  1053. [Covers only decompression of data compressed with a variant of LZ77.]
  1054.  
  1055. 4,087,788
  1056. Data compression system
  1057. filed 1/14/77, granted 5/2/78
  1058. NCR Canada LTD - NCR Canada Ltee, Mississauga CA
  1059. Brian J. Johannesson, Waterloo CA
  1060. A data compression system is disclosed in which the left hand boundary
  1061. of a character is developed in the form of a sequence of Freeman
  1062. direction codes, the codes being stored in digital form within a
  1063. processor.
  1064.  
  1065. 4,122,440
  1066. Method and means for arithmetic string coding
  1067. assignee IBM
  1068. filed 1977/03/04, granted 1978/10/24
  1069. [This is the basic idea of arithmetic coding. Note that the patent is
  1070. expired now.]
  1071.  
  1072. 4,286,256
  1073. Method and means for arithmetic coding using a reduced number of operations.
  1074. granted Aug 25, 1981
  1075. assignee IBM
  1076.  
  1077. 4,295,125
  1078. A method and means for pipeline decoding of the high to low order pairwise
  1079. combined digits of a decodable set of relatively shifted finite number of
  1080. strings
  1081. granted Oct 13, 1981
  1082. assignee IBM
  1083.  
  1084. 4,366,551
  1085. Associative Memory Search System
  1086. filed June 16, 1975, granted Dec. 28, 1982.
  1087. inventor Klaus Holtz, assignee Omni Dimensional Networks.
  1088.  
  1089. 4,412,306
  1090. System for minimizing space requirements for storage and transmission of
  1091. digital signals
  1092. filed May 14, 1981, granted Oct. 25, 1983
  1093. inventor  Edward W. Moll
  1094.  
  1095. 4,463,342
  1096. A method and means for carry-over control in a high order to low order
  1097. combining of digits of a decodable set of relatively shifted finite number
  1098. strings.
  1099. granted Jul 31, 1984
  1100. assignee IBM
  1101.  
  1102. 4,491,934
  1103. Data compression process
  1104. filed May 12, 1982, granted Jan. 1, 1985
  1105. inventor  Karl E. Heinz
  1106.  
  1107. 4,464,650
  1108. Apparatus and method for compressing data signals and restoring the
  1109. compressed data signals
  1110. inventors Lempel, Ziv, Cohn, Eastman
  1111. assignee Sperry Corporation (now Unisys)
  1112. filed 8/10/81, granted 8/7/84
  1113. A compressor parses the input data stream into segments where each
  1114. segment comprises a prefix and the next symbol in the data stream
  1115. following the prefix. [This is the original LZ78 algorithm.]
  1116.  
  1117. 4,467,317
  1118. High-speed arithmetic compression using using concurrent value updating.
  1119. granted Aug 21, 1984
  1120. assignee IBM
  1121.  
  1122. 4,494,108
  1123. Adaptive source modeling for data file compression within bounded memory
  1124. filed Jun. 5, 1984, granted Jan. 15, 1985
  1125. invntors Glen G. Langdon, Jorma J. Rissanen
  1126. assignee IBM
  1127. order 1 Markov modeling
  1128.  
  1129. 4,558,302
  1130. High speed data compression and decompression apparatus and method
  1131. inventor Welch
  1132. assignee Sperry Corporation (now Unisys)
  1133. filed 6/20/83, granted 12/10/85
  1134. re-examined: filed 12/14/92, granted 4/1/94.
  1135. The text for the original patent can be ftped from ftp.uni-stuttgart.de
  1136. in /pub/doc/comp-patents/US4558302.Z.
  1137. There is also a European Patent 0,129,439  1/2/89 for DE, FR, GB, IT
  1138. and patent pending for Japan.
  1139.  
  1140. 4,560,976
  1141. Data compression
  1142. filed 6/5/84, granted 12/24/85
  1143. Codex Corporation, Mansfield MA
  1144. Steven G. Finn, Framingham, MA
  1145. A stream of source characters, which occur with varying relative
  1146. frequencies, is encoded into a compressed stream of codewords, each
  1147. having one, two or three subwords, by ranking the source characters by
  1148. their current frequency of appearance, encoding the source characters
  1149. having ranks no higher than a first number as one subword codewords,
  1150. source characters having ranks higher than the first number but no
  1151. higher than a second number as two subword codewords, and the
  1152. remaining source characters as three subword codewords.
  1153.  
  1154. 4,586,027
  1155. Method and system for data compression and restoration
  1156. inventor Tsukimaya et al.
  1157. assignee Hitachi
  1158. filed 08/07/84, granted 04/29/86
  1159. patents run length encoding
  1160.  
  1161. 4,597,057
  1162. System for compressed storate of 8-bit ascii bytes using coded strings
  1163. of 4-bit nibbles.
  1164. inventor Snow, assignee System Development corporation.
  1165. filed 12/31/1981, granted 06/24/1986.
  1166. Compression using static dictionary of common words, prefixes and suffixes.
  1167.  
  1168. 4,612,532
  1169. Data compression apparatus and method
  1170. inventor Bacon, assignee Telebyte Corportion
  1171. filed Jun. 19, 1984, granted Sep. 16, 1986
  1172. [Uses followsets as in the pkzip 0.92 'reduce' algorithm, but the
  1173. followsets are dynamically updated. This is in effect a sort of order-1
  1174. Markov modeling.]
  1175.  
  1176. 4,622,545
  1177. Method and apparatus for image compression and Manipulation
  1178. inventor William D. Atkinson
  1179. assignee Apple computer Inc.
  1180. filed 9/30/82
  1181. granted 11/11/86
  1182.  
  1183. 4,633,490
  1184. Symmetrical adaptive data compression/decompression system.
  1185. granted Dec 30, 1985
  1186. assignee IBM
  1187.  
  1188. 4,652,856
  1189. A multiplication-free multi-alphabet arithmetic code.
  1190. granted Feb  4, 1986
  1191. assignee IBM
  1192.  
  1193. 4,667,649
  1194. Data receiving apparatus
  1195. filed 4/18/84, granted 6/30/87
  1196. inventors Kunishi et al.
  1197. assignee Canon Kabushiki Kaisha, Tokyo Japan
  1198. compression of Fax images.
  1199.  
  1200. 4,682,150
  1201. Data compression method and apparatus
  1202. inventors Mathes and Protheroe, 
  1203. assignee NCR Corporation, Dayton OH
  1204. A system and apparatus for compressing redundant and nonredundant
  1205. binary data generated as part of an operation of a time and attendance
  1206. terminal in which the data represents the time an employee is present
  1207. during working hours.
  1208.  
  1209. 4,701,745
  1210. Data compression system
  1211. inventor Waterworth John R
  1212. assignee Ferranti PLC GB, patent rights now acquired by Stac Inc.
  1213. filed 03/03/1986 (03/06/1985 in GB), granted 10/20/1987
  1214. Algorithm now known as LZRW1 (see above)
  1215. I claim:
  1216. 1. A data compression system comprising an input store for receiving
  1217. and storing a plurality of bytes of uncompressed data from an outside
  1218. source, and data processing means for processing successive bytes of
  1219. data from the input store;
  1220. the data processing means including circuit means operable to check
  1221. whether a sequence of successive bytes to be processed identical with
  1222. a sequence of bytes already processed, and including hash generating
  1223. means responsive to the application of a predetermined number of
  1224. bytes in sequence to derive a hash code appropriate to those bytes, a
  1225. temporary store in which the hash code may represent the address of a
  1226. storage location, and a pointer counter operable to store in the
  1227. temporary store at said address a pointer indicative of the position
  1228. in the input store of one of the predetermined number of bytes;
  1229. output means operable to apply to a transfer medium each byte of data
  1230. not forming part of such an identical sequence; and
  1231. encoding means responsive to the identification of such a sequence to
  1232. apply to the transfer medium an identification signal which identifies
  1233. both the location in the input store of the previous occurrence of the
  1234. sequence of bytes and the number of bytes contained in the sequence.
  1235.  
  1236. 4,730,348
  1237. Adaptive data compression system
  1238. inventor MacCrisken, assignee Adaptive Computer Technologies
  1239. filed Sep. 19, 1986, granted Mar. 8, 1988
  1240. [order-1 Markov modeling + Huffman coding + LZ77]
  1241.  
  1242. 4,758,899
  1243. Data compression control device
  1244. inventor Tsukiyama, assignee Hitachi
  1245. filed 11/20/1985, granted 07/19/1988
  1246. Limits compression to ensure that tape drive stays busy.
  1247.  
  1248. 4,792,954
  1249. Concurrent detection of errors in arithmetic data compression coding
  1250. assignee IBM
  1251. filed 1986/10/31, granted 1988/12/20
  1252.  
  1253. 4,809,350
  1254. Data compression system
  1255. filed Jan. 30, 1987, granted Feb. 28, 1989
  1256. inventor Yair Shimoni & Ron Niv
  1257. assignee Elscint Ltd., Haifa, Israel
  1258. [Image compression via variable length encoding of differences with
  1259. predicted data.]
  1260.  
  1261. 4,814,746
  1262. Data compression method
  1263. inventors Victor S. Miller, Mark N. Wegman
  1264. assignee IBM
  1265. filed 8/11/86, granted 3/21/89
  1266. A previous application was filed on 6/1/83, three weeks before the
  1267. application by Welch (4,558,302)
  1268. Communications between a Host Computing System and a number of remote
  1269. terminals is enhanced by a data compression method which modifies the
  1270. data compression method of Lempel and Ziv by addition of new character
  1271. and new string extensions to improve the compression ratio, and
  1272. deletion of a least recently used routine to limit the encoding tables
  1273. to a fixed size to significantly improve data transmission efficiency.
  1274.  
  1275. 4,841,092
  1276. continued in 5,003,307
  1277.  
  1278. 4,853,696
  1279. Code converter for data compression/decompression
  1280. filed 4/13/87, granted 8/1/89
  1281. inventor Amar Mukherjee, Maitland FL
  1282. assignee University of Central Florida, Orlando FL
  1283. Another hardware Huffman encoder:
  1284. A code converter has a network of logic circuits connected in reverse
  1285. binary tree fashion with logic paths between leaf nodes and a common
  1286. root node.
  1287.  
  1288. 4,872,009
  1289. Method and apparatus for data compression and restoration
  1290. inventor Tsukimaya et al.
  1291. assignee Hitachi
  1292. filed 12/07/87, granted 10/03/89
  1293. This patent on run length encoding covers the 'invention' of limiting
  1294. the run length to 16 bytes and thus the encoding of the length on 4 bits.
  1295.  
  1296. 4,876,541
  1297. Stem [sic] for dynamically compressing and decompressing electronic data
  1298. filed 10/15/87, granted 10/24/89
  1299. inventor James A. Storer
  1300. assignee Data Compression Corporation
  1301. A data compression system for encoding and decoding textual data,
  1302. including an encoder for encoding the data and for a decoder for
  1303. decoding the encoded data.
  1304.  
  1305. 4,891,643
  1306. Arithmetic coding data compression/de-compression by selectively
  1307. employed, diverse arithmetic encoders and decoders.
  1308. file 1986/09/15, granted 1990/01/02
  1309. assignee IBM
  1310.  
  1311. 4,901,363
  1312. System for compressing bi-level data
  1313. assignee IBM
  1314. [arithmetic coding]
  1315.  
  1316. 4,905,297
  1317. Arithmetic coding encoder and decoder system.
  1318. granted Feb 27, 1990
  1319. assignee IBM
  1320.  
  1321. 4,906,991
  1322. Textual substitution data compression with finite length search window
  1323. filed 4/29/1988, granted 3/6/1990
  1324. inventors Fiala,E.R., and Greene,D.H.
  1325. assignee Xerox Corporation
  1326.  
  1327. 4,933,883
  1328. Probability adaptation for arithmetic coders.
  1329. granted Jun 12, 1990
  1330. assignee IBM
  1331.  
  1332. 4,935,882
  1333. Probability adaptation for arithmetic coders.
  1334. granted Jun 19, 1990
  1335. assignee IBM
  1336.  
  1337. 4,941,193
  1338. Barnsley, fractal compression.
  1339.  
  1340. 4,943,869
  1341. Compression Method for Dot Image Data
  1342. filed 1988-05-04, granted 1990-07-24
  1343. assignee Fuji Photo Film Co.
  1344. Lossy and lossless image compression schemes.
  1345.  
  1346. 4,955,066
  1347. Compressing and Decompressing Text Files
  1348. filed  10/13/89, granted 09/04/90
  1349. inventor Notenboom, L.A.
  1350. assignee Microsoft
  1351. Now extended as 5,109,433
  1352. [Noted in signon screen of Word 5.5 and on the outside of the MS-DOS 5.0
  1353. Upgrade.]
  1354. A method of compressing a text file in digital form is disclosed.
  1355. A full text file having characters formed into phrases is provided by an
  1356. author.  The characters are digitally represented by bytes.  A first pass
  1357. compression is sequentially followed by a second pass compression of the
  1358. text which has previously been compressed.  A third or fourth level of
  1359. compression is serially performed on the compressed text.  For example, in
  1360. a first pass, the text is run-length compressed.  In a second pass, the
  1361. compressed text is further compressed with key phrase compression.  In a
  1362. third pass, the compressed text is further compressed with Huffman
  1363. compression.  The compressed text is stored in a text file having a Huffman
  1364. decode tree, a key phrase table, and a topic index.  The data is
  1365. decompressed in a single pass and provided one line at a time as an output.
  1366. Sequential compressing of the text minimizes the storage space required for
  1367. the file.  Decompressing of the text is performed in a single pass.  As a
  1368. complete line is decompressed, it is output rapidly, providing full text to
  1369. the user.
  1370.  
  1371. 4,973,961
  1372. Method and apparatus for carry-over control in arithmetic coding.
  1373. granted Nov 27, 1990
  1374. assignee AT&T
  1375.  
  1376. 4,988,998
  1377. Data compression system for successively applying at least two data
  1378. compression methods to an input data stream.
  1379. inventor O'Brien
  1380. assignee Storage Technology Corporation, Louisville, Colorado
  1381. filed Sep 5, 1989, granted Jan 29, 1991.
  1382. Run length encoding followed by LZ77.
  1383.  
  1384. 4,989,000
  1385. Data string compression using arithmetic encoding with simplified probability
  1386. subinterval estimation
  1387. filed 1989/06/19, granted 1991/01/29]
  1388. [shift & add instead of multiply]
  1389.  
  1390. 5,001,478
  1391. Method of Encoding Compressed Data
  1392. filed 12/28/89, granted 03/19/91
  1393. inventor Michael E. Nagy
  1394. assignee IBM
  1395. 1. A method of encoding a compressed data stream made up of a sequence of
  1396. literal references, lexicon references and history references, which
  1397. comprises the steps of:
  1398. assigning to each literal reference a literal identifier;
  1399. assigning to each history reference a history identifier;
  1400. assigning to each lexicon reference a lexicon identifier;
  1401. and emitting a data stream with said identifiers assigned to said references.
  1402. Gordon Irlam <gordoni@cs.adelaide.edu.au> says:
  1403. The invention can probably be best understood by considering the
  1404. decompressor.  It consists of a history buffer, and a lexicon buffer, both
  1405. of which are initially empty.  The history buffer contains the last n
  1406. symbols emitted.  Whenever a history buffer reference is to be output the
  1407. string so referenced is subsequently moved to the lexicon buffer for future
  1408. reference.  Thus the history buffer keeps track of strings that may be
  1409. repeated on a very short term basis, while the lexicon buffer stores items
  1410. for a longer time.  Furthermore a history reference involves specifying
  1411. both the offset and length within the history buffer, whereas a lexicon
  1412. reference simply specifies a number denoting the string.  Both buffers have
  1413. a finite size.
  1414.  
  1415. 5,003,307
  1416. Data compression apparatus with shift register search means
  1417. filed Oct. 6, 1989, granted Mar. 26, 1991
  1418. inventors George Glen A, Ivey Glen E, Whiting Douglas L
  1419. assignee Stac Inc
  1420. continuation of 4,841,092
  1421.  
  1422. 5,016,009
  1423. Data compression apparatus and method
  1424. filed 01/13/1989, granted 05/14/1991
  1425. inventors George Glen A, Ivey Glen E, Whiting Douglas L
  1426. assignee Stac Inc
  1427. LZ77 with offset hash table (extended in 5,126,739)
  1428.  
  1429. 5,023,611
  1430. Entropy encoder/decoder including a context extractor.
  1431. granted Jun 11, 1991
  1432. assignee AT&T
  1433.  
  1434. 5,025,258
  1435. Adaptive probability estimator for entropy encoder/decoder.
  1436. granted Jun 18, 1991
  1437. assignee AT&T
  1438.  
  1439. 5,045,852
  1440. Dynamic model selection during data compression
  1441. assignee IBM
  1442. [arithmetic coding]
  1443.  
  1444. 5,049,881
  1445. Apparatus and method for very high data rate-compression incorporating
  1446. lossless data compression and expansion utilizing a hashing technique
  1447. inventors Dean K. Gibson, Mark D. Graybill
  1448. assignee Intersecting Concepts, Inc.
  1449. filed 6/18/90, granted 9/17/91
  1450. [covers lzrw1, almost identical with Waterworth 4,701,745]
  1451.  
  1452. 5,051,745
  1453. String searcher, and compressor using same
  1454. filed  8/21/90, granted 9/24/91
  1455. inventor  Phillip W. Katz (author of pkzip)
  1456. In the string search method and apparatus pointers to the string to be
  1457. searched are indexed via a hashing function and organized according to the
  1458. hashing values of the string elements pointed to. The hashing function is
  1459. also run on the string desired to be found, and the resulting hashing value
  1460. is used to access the index. If the resulting hashing value is not in the
  1461. index, it is known that the target string does not appear in the string
  1462. being searched. Otherwise the index is used to determine the pointers which
  1463. correspond to the target hashing value, these pointers pointing to likely
  1464. candidates for matching the target string. The pointers are then used to
  1465. sequentially compare each of the locations in the string being searched to
  1466. the target string, to determine whether each location contains a match to
  1467. the target string.
  1468. In the method and apparatus for compressing a stream of data symbols, a
  1469. fixed length search window, comprising a predetermined contiguous portion
  1470. of the symbol stream, is selected as the string to be searched by the
  1471. string searcher. If a string to be compressed is found in the symbol
  1472. stream, a code is output designating the location within the search window
  1473. of the matching string and the length of the matching string.
  1474.  
  1475. 5,065,447 (continued in 5,347,600)
  1476. Method and apparatus for processing digital data
  1477. filed Jul. 5, 1989, granted Nov. 12, 1991
  1478. inventors Michael F. Barnsley and Alan D. Sloan
  1479. [Patents image compression with the "Fractal Transform"]
  1480.  
  1481. 5,099,440
  1482. Probability adaptation for arithmetic coders
  1483.  
  1484. 5,109,433
  1485. Compressing and decompressing text files
  1486. inventor Notenboom
  1487. assignee Microsoft
  1488. extension of 4,955,066
  1489.  
  1490. 5,126,739
  1491. Data Compression Apparatus and Method
  1492. filed Nov. 27, 1990, granted June 30, 1992.
  1493. inventor Whiting et. al
  1494. assignee Stac Inc
  1495. LZ77 with offset hash table (extension of 5,016,009)
  1496.  
  1497. 5,140,321
  1498. Data compression/decompression method and apparatus
  1499. filed 9/4/91, granted 8/18/92
  1500. inventor Robert Jung
  1501. assignee Prime Computer
  1502.  
  1503. 5,142,283
  1504. Arithmetic compression coding using interpolation for ambiguous symbols
  1505. filed 1990/07/10, granted 1992/08/25
  1506. assignee IBM
  1507.  
  1508. 5,155,484
  1509. Fast data compressor with direct lookup table indexing into history buffer
  1510. filed 9/13/1991, granted 10/13/1992
  1511. inventor Chambers, IV, Lloyd L., Menlo Park, California
  1512. assignee Salient Software, Inc., Palo Alto, California (02)
  1513. Uses a 64K hash table indexed by the first two characters of
  1514. the input string. Includes several claims on the LZ77 file format
  1515. (literal or pair offset,length).
  1516.  
  1517. 5,179,378
  1518. file Jul. 30, 1991, granted Jan. 12, 1993
  1519. inventor Ranganathan
  1520. assignee University of South Florida
  1521. Method and apparatus for the compression and decompression of data
  1522. using Lempel-Ziv based techniques.
  1523. [This covers LZ77 hardware compression with a systolic array of
  1524. processors working in parallel.]
  1525.  
  1526. 5,210,536
  1527. Data compression/coding method and device for implementing said method
  1528. assignee IBM
  1529. [PPM + arithmetic coding]
  1530.  
  1531. 5,229,768
  1532. Adaptive data compression system
  1533. granted Jul. 20, 1993
  1534. inventor Kasman E. Thomas
  1535. assignee Traveling Software, Inc. 
  1536.   A system for data compression and decompression is disclosed. A series of
  1537. fixed length overlapping segments, called hash strings, are formed from an
  1538. input data sequence. A retrieved character is the next character in the input
  1539. data sequence after a particular hash string. A hash function relates a
  1540. particular hash string to a unique address in a look-up table (LUT). An
  1541. associated character for the particular hash string is stored in the LUT at
  1542. the address. When a particular hash string is considered, the content of the
  1543. LUT address associated with the hash string is checked to determine whether
  1544. the associated character matches the retrieved character following the hash
  1545. string. If there is a match, a Boolean TRUE is output; if there is no match,
  1546. a Boolean FALSE along with the retrieved character is output. Furthermore, if
  1547. there is no match, then the LUT is updated by replacing the associated
  1548. character in the LUT with the retrieved character. [...]
  1549. [This algorithm is used in the Internet draft
  1550. "PPP Predictor Compression Protocol".]
  1551.  
  1552. 5,272,478
  1553. Method and apparatus for entropy coding
  1554. assignee Ricoh
  1555. [arithmetic coding with finite state machine]
  1556.  
  1557. 5,307,062
  1558. Coding system
  1559. filed 1992/12/15, granted 1994/04/26
  1560. assignee Mitsubishi
  1561. [binary arithmetic coding, see also 5,404,140]
  1562.  
  1563. 5,309,381
  1564. Probability estimation table apparatus
  1565. filed 1992/04/08, granted 1994/05/03
  1566. assignee Ricoh
  1567. [arithmetic coding]
  1568.  
  1569. 5,311,177
  1570. Code transmitting apparatus with limited carry propagation
  1571. filed 1992/06/19, granted 1994/05/10
  1572. assignee Mitsubishi
  1573. [arithmetic coding]
  1574.  
  1575. 5,347,600 (continuation of 5,065,447)
  1576. Method and apparatus for compression and decompression of digital image
  1577. filed 10/23/1991, granted 09/13/1994
  1578. inventors Barnsley and Sloan
  1579.  
  1580. 5,363,099
  1581. Method and apparatus for entropy coding
  1582. [arithmetic coding with state machine]
  1583.  
  1584. 5,384,867 (continued in 5,430,812)
  1585. filed 10/23/1991, granted 01/24/1995
  1586. Fractal transform compression board
  1587. inventors Barnsley et al.
  1588.  
  1589. 5,404,140
  1590. Coding system
  1591. filed 1994/01/13, granted 1995/04/04
  1592. assignee Mitsubishi
  1593. [binary arithmetic coding, see also 5,307,062]
  1594.  
  1595. 5,406,282
  1596. Data coding and decoding with improved efficiency
  1597. assignee Ricoh
  1598. [PPM & arithmedic coding]
  1599.  
  1600. 5,414,423
  1601. Stabilization of probability estimates by conditioning on prior decisions
  1602.   of a given context
  1603. assignee IBM
  1604. arithmetic coding]
  1605.  
  1606. 5,416,856
  1607. Method of encoding a digital image using iterated image transformations
  1608.   to form an eventually contractive map
  1609. filed 1992/03/30, granted 1995/05/16
  1610. inventors Jacobs, Boss and Fisher
  1611.  
  1612. 5,418,532
  1613. Method and system for efficient, multiplication-free arithmetic coding
  1614. filed 1993/05/13, granted 1995/05/23.
  1615. inventors Lei & Shaw-Min
  1616. assignee Bell Communications Research, Inc. (Livingston, NJ). 
  1617.  
  1618. 5,430,812 (continuation of 5,384,867)
  1619. Fractal transform compression board
  1620. filed 1994/05/18, granted 1995/07/04
  1621. inventors Barnsley et al.
  1622.  
  1623. 5,533,051
  1624. Method for Data Compression
  1625. filed 1993/03/12, granted 1996/07/02
  1626. inventor David C. James, assignee The James Group
  1627. This is a patent on compression of random data, see item 9.5 below.
  1628.  
  1629. Japan 2-46275
  1630. Coding system
  1631. granted Feb 26, 1990
  1632. [Patents one form of arithmetic coding.]
  1633.  
  1634.  
  1635. ------------------------------------------------------------------------------
  1636.  
  1637. Subject: [9]  Compression of random data (WEB, Gilbert and others)
  1638.  
  1639.  
  1640. [Note from the FAQ maintainer: this topic has generated and is still generating
  1641. the greatest volume of news in the history of comp.compression. Read this
  1642. before posting on this subject.
  1643.  
  1644. I intended to remove the WEB story from the FAQ, but similar affairs come up
  1645. regularly on comp.compression.  The advertized revolutionary methods have all
  1646. in common their supposed ability to compress random or already compressed data.
  1647. I will keep this item in the FAQ to encourage people to take such claims with
  1648. great precautions.]
  1649.  
  1650.  
  1651. 9.1 Introduction
  1652.  
  1653. It is mathematically impossible to compress without loss truly random data (see
  1654. below and also item 73 in part 2 of this FAQ). Yet from time to time some
  1655. people claim to have invented a new algorithm for doing so. Such algorithms are
  1656. claimed to be applicable recursively, that is, applying the compressor to the
  1657. compressed output of the previous run, possibly multiple times. Fantastic
  1658. compression ratios of over 100:1 on random data are claimed to be actually
  1659. obtained.
  1660.  
  1661. Such claims inevitably generate a lot of activity on comp.compression, which
  1662. can last for several months. The two largest bursts of activity were generated
  1663. by WEB Technologies and by Jules Gilbert. Premier Research Corporation
  1664. (with a compressor called MINC) made only a brief appearance. The Hyper Space
  1665. method invented by David C. James is a new contender with a patent obtained
  1666. in July 96.
  1667.  
  1668. Other people have also claimed incredible compression ratios, but the programs
  1669. (OWS, WIC) were quickly shown to be fake (not compressing at all). This topic
  1670. is covered in item 10 of this FAQ.
  1671.  
  1672.  
  1673. 9.2 The counting argument
  1674.  
  1675. The WEB compressor (see details in section 9.3 below) was claimed to compress
  1676. without loss *all* files of greater than 64KB in size to about 1/16th their
  1677. original length. A very simple counting argument shows that this is impossible,
  1678. regardless of the compression method. It is even impossible to guarantee
  1679. lossless compression of all files by at least one bit. (Many other proofs have
  1680. been posted on comp.compression, please do not post yet another one.)
  1681.  
  1682. Assume that the program can compress without loss all files of size >= N bits.
  1683. Compress with this program all the 2^N files which have exactly N bits.  All
  1684. compressed files have at most N-1 bits, so there are at most (2^N)-1 different
  1685. compressed files [2^(N-1) files of size N-1, 2^(N-2) of size N-2, and so on,
  1686. down to 1 file of size 0]. So at least two different input files must compress
  1687. to the same output file.  Hence the compression program cannot be
  1688. lossless. (Much stronger results about the number of incompressible files can
  1689. be obtained, but the proofs are a little more complex.)
  1690.  
  1691. This argument applies of course to WEB's case (take N = 64K*8 bits).  Note that
  1692. no assumption is made about the compression algorithm.  The proof applies to
  1693. *any* algorithm, including those using an external dictionary, or repeated
  1694. application of another algorithm, or combination of different algorithms, or
  1695. representation of the data as formulas, etc... All schemes are subject to the
  1696. counting argument.  There is no need to use information theory to provide a
  1697. proof, just basic mathematics. [People interested in more elaborate proofs can
  1698. consult http://wwwvms.utexas.edu/~cbloom/news/nomagic.html ]
  1699.  
  1700. This assumes of course that the information available to the decompressor is
  1701. only the bit sequence of the compressed data. If external information such as a
  1702. file name, a number of iterations, or a bit length is necessary to decompress
  1703. the data, the bits necessary to provide the extra information must be included
  1704. in the bit count of the compressed data.  Otherwise, it would be sufficient to
  1705. consider any input data as a number, use this as the file name, iteration count
  1706. or bit length, and pretend that the compressed size is zero.  For an example of
  1707. storing information in the file name, see the program lmfjyh in the 1993
  1708. International Obfuscated C Code Contest, available on all comp.sources.misc
  1709. archives (Volume 39, Issue 104).
  1710.  
  1711. A common flaw in the algorithms claimed to compress all files is to assume that
  1712. arbitrary bit strings can be sent to the decompressor without actually
  1713. transmitting their bit length. If the decompressor needs such bit lengths
  1714. to decode the data (when the bit strings do not form a prefix code), the
  1715. number of bits needed to encode those lengths must be taken into account
  1716. in the total size of the compressed data.
  1717.  
  1718. Another common (but still incorrect) argument is to assume that for any file,
  1719. some still to be discovered algorithm might find a seed for a pseudo-random
  1720. number generator which would actually generate the whole sequence of bytes
  1721. contained in the file. However this idea still fails to take into account the
  1722. counting argument. For example, if the seed is limited to 64 bits, this
  1723. algorithm can generate at most 2^64 different files, and thus is unable to
  1724. compress *all* files longer than 8 bytes.
  1725.  
  1726. Yet another popular idea is to split the input bit stream into a sequence of
  1727. large numbers, and factorize those numbers. Unfortunately, the number of
  1728. bits required to encode the factors and their exponents is on average
  1729. not smaller than the number of bits of the original bit stream, so this
  1730. scheme too cannot compress random data.
  1731.  
  1732. Steve Tate <srt@cs.unt.edu> suggests a good challenge for programs
  1733. that are claimed to compress random data by a significant amount:
  1734.  
  1735.     Here's a wager for you: First, send me the DEcompression algorithm.  Then I
  1736.     will send you a file of whatever size you want, but at least 100k.  If you
  1737.     can send me back a compressed version that is even 20% shorter (80k if the
  1738.     input is 100k) I'll send you $100.  Of course, the file must be able to be
  1739.     decompressed with the program you previously sent me, and must match
  1740.     exactly my original file.  Now what are you going to provide
  1741.     when... er... if you can't demonstrate your compression in such a way?
  1742.  
  1743. So far no one has accepted this challenge (for good reasons).
  1744.  
  1745.  
  1746. 9.3 The WEB 16:1 compressor
  1747.  
  1748. 9.3.1 What the press says
  1749.  
  1750. April 20, 1992  Byte Week Vol 4. No. 25:
  1751.  
  1752.    "In an announcement that has generated high interest - and more than a
  1753.    bit of skepticism - WEB Technologies (Smyrna, GA) says it has
  1754.    developed a utility that will compress files of greater than 64KB in
  1755.    size to about 1/16th their original length.  Furthermore, WEB says its
  1756.    DataFiles/16 program can shrink files it has already compressed."
  1757.    [...]
  1758.    "A week after our preliminary test, WEB showed us the program successfully
  1759.    compressing a file without losing any data.  But we have not been able
  1760.    to test this latest beta release ourselves."
  1761.    [...]
  1762.    "WEB, in fact, says that virtually any amount of data can be squeezed 
  1763.    to under 1024 bytes by using DataFiles/16 to compress its own output
  1764.    multiple times."
  1765.  
  1766. June 1992 Byte, Vol 17 No 6:
  1767.  
  1768.    [...] According to Earl Bradley, WEB Technologies' vice president of
  1769.    sales and marketing, the compression algorithm used by DataFiles/16
  1770.    is not subject to the laws of information theory. [...]
  1771.       ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  1772.  
  1773. 9.3.2 First details, by John Wallace <buckeye@spf.trw.com>
  1774.  
  1775. I called WEB at (404)514-8000 and they sent me some product
  1776. literature as well as chatting for a few minutes with me on the phone.
  1777. Their product is called DataFiles/16, and their claims for it are
  1778. roughly those heard on the net.
  1779.  
  1780. According to their flier:
  1781.  
  1782. "DataFiles/16 will compress all types of binary files to approximately
  1783. one-sixteenth of their original size ... regardless of the type of
  1784. file (word processing document, spreadsheet file, image file,
  1785. executable file, etc.), NO DATA WILL BE LOST by DataFiles/16."
  1786. (Their capitalizations; 16:1 compression only promised for files >64K
  1787. bytes in length.)
  1788.  
  1789. "Performed on a 386/25 machine, the program can complete a
  1790. compression/decompression cycle on one megabyte of data in less than
  1791. thirty seconds"
  1792.  
  1793. "The compressed output file created by DataFiles/16 can be used as the 
  1794. input file to subsequent executions of the program.  This feature of 
  1795. the utility is known as recursive or iterative compression, and will 
  1796. enable you to compress your data files to a tiny fraction of the 
  1797. original size.  In fact, virtually any amount of computer data can 
  1798. be compressed to under 1024 bytes using DataFiles/16 to compress its 
  1799. own output files muliple times.  Then, by repeating in reverse the 
  1800. steps taken to perform the recusive compression, all original data 
  1801. can be decompressed to its original form without the loss of a single 
  1802. bit."
  1803.  
  1804. Their flier also claims: 
  1805.  
  1806. "Constant levels of compression across ALL TYPES of FILES"
  1807. "Convenient, single floppy DATA TRANSPORTATION"
  1808.  
  1809. From my telephone conversation, I was assured that this is an
  1810. actual compression program.  Decompression is done by using only the 
  1811. data in the compressed file; there are no hidden or extra files.
  1812.  
  1813.  
  1814. 9.3.3 More information, by Rafael Ramirez <rafael.ramirez@channel1.com>:
  1815.  
  1816.    Today (Tuesday, 28th) I got a call from Earl Bradley of Web
  1817. who now says that they have put off releasing a software version of
  1818. the algorithm because they are close to signing a major contract with
  1819. a big company to put the algorithm in silicon.  He said he could not
  1820. name the company due to non-disclosure agreements, but that they had
  1821. run extensive independent tests of their own and verified that the
  1822. algorithm works. [...]
  1823.  
  1824. He said the algorithm is so simple that he doesn't want anybody
  1825. getting their hands on it and copying it even though he said they
  1826. have filed a patent on it. [...] Mr. Bradley said the silicon version
  1827. would hold up much better to patent enforcement and be harder to copy.
  1828.  
  1829.    He claimed that the algorithm takes up about 4K of code, uses only
  1830. integer math, and the current software implementation only uses a 65K
  1831. buffer.  He said the silicon version would likely use a parallel
  1832. version and work in real-time. [...]
  1833.  
  1834.  
  1835. 9.3.4 No software version
  1836.  
  1837. Appeared on BIX, reposted by Bruce Hoult <Bruce.Hoult@actrix.gen.nz>:
  1838.  
  1839. tojerry/chaos #673, from abailey, 562 chars, Tue Jun 16 20:40:34 1992
  1840. Comment(s). 
  1841. ----------
  1842. TITLE: WEB Technology
  1843. I promised everyone a report when I finally got the poop on WEB's
  1844. 16:1 data compression. After talking back and forth for a year
  1845. and being put off for the past month by un-returned phone calls,
  1846. I finally got hold of Marc Spindler who is their sales manager.
  1847.  
  1848. _No_ software product is forth coming, period!
  1849.  
  1850. He began talking about hardware they are designing for delivery
  1851. at the end of the year. [...]
  1852.  
  1853.  
  1854. 9.3.5 Product cancelled
  1855.  
  1856. Posted by John Toebes <toebes@bnr.ca> on Aug 10th, 1992:
  1857.  
  1858. [Long story omitted, confirming the reports made above about the
  1859. original WEB claims.]
  1860.  
  1861. 10JUL92 - Called to Check Status.  Was told that testing had uncovered a
  1862.           new problem where 'four numbers in a matrix were the same
  1863.           value' and that the programmers were off attempting to code a
  1864.           preprocessor to eliminate this rare case.  I indicated that he
  1865.           had told me this story before.  He told me that the
  1866.           programmers were still working on the problem.
  1867.  
  1868. 31JUL92 - Final Call to Check Status.  Called Earl in the morning and
  1869.           was told that he still had not heard from the programmers. [...]
  1870.           Stated that if they could not resolve the problem then there would
  1871.           probably not be a product.
  1872.  
  1873. 03AUG92 - Final Call.  Earl claims that the programmers are unable to
  1874.           resolve the problem.  I asked if this meant that there would
  1875.           not be a product as a result and he said yes.
  1876.  
  1877.  
  1878. 9.3.6 Byte's final report
  1879.  
  1880. Extract from the Nov. 95 issue of Byte, page 42:
  1881.  
  1882. Not suprisingly, the beta version of DataFiles/16 that reporter Russ Schnapp
  1883. tested didn't work. DataFiles/16 compressed files, but when decompressed, those
  1884. files bore no resemblance to their originals. WEB said it would send us a
  1885. version of the program that worked, but we never received it.
  1886.  
  1887. When we attempted to follow up on the story about three months later, the
  1888. company's phone had been disconnected. Attempts to reach company officers
  1889. were also unsuccessful. [...]
  1890.  
  1891.  
  1892. 9.4 Jules Gilbert
  1893.  
  1894. As opposed to WEB Technologies, Jules Gilbert <coffee@spock.ici.net> does not
  1895. claim to compress *all* files, but only "random or random-appearing" files.
  1896. Here are some quotes from a few of Mr Gilbert's articles, which can be helpful
  1897. to get a better idea of his claims. No comments or conclusions are given; if
  1898. you need more information contact Mr. Gilbert directly.
  1899.  
  1900.   From: coffee@spock.ici.net (Jules Gilbert)
  1901.   Newsgroups: comp.compression
  1902.   Subject: Re: No Magic Compressors, No Factoring Compressors, Jules Gilbert
  1903.     is a liar
  1904.   Date: 14 May 1996 03:13:31 -0400
  1905.   Message-ID: <4n9bqr$89k@spock.ici.net>
  1906.  
  1907.   [...]
  1908.   I will, in front of several Boston area computer scientists ('monitors'),
  1909.   people I choose but generally known to be fair and competent, under
  1910.   conditions which are sufficient to prevent disclosure of the method and fully
  1911.   protect the algorithm and other aspects of the underlying method from
  1912.   untoward discovery, use two computers, (which I am permitted to examine but
  1913.   not alter) with both machine's running Linux, and with the file-systems and
  1914.   Linux OS freshly restored from commercial CD-ROM's do the following:
  1915.  
  1916.   On one machine (the 'src-CPU') will be loaded a copy of the CALGARY-CORPUS.
  1917.   (Or other agreed on '.ZIP' or '.ARJ' file.)
  1918.  
  1919.   I will compress the CALGARY-CORPUS for transfer from the src-CPU onto 3.5"
  1920.   disks and transfer it (by sneaker-net) to the other machine for decompression
  1921.   and produce a perfect copy of the CORPUS file on the 'dst-CPU'.
  1922.  
  1923.   The CORPUS archive contents will not be 'cracked', ie', the original CORPUS
  1924.   can be encrypted and the password kept from me.  All I care about is that the
  1925.   input file is highly random-aprearing.
  1926.  
  1927.   I claim that I can perform this process several times, and each iteration
  1928.   will reduce the overall file by at least 50%, ie., a ratio of 2:1.  An
  1929.   'iteration' will constitute copying, using compression, from the src-CPU to
  1930.   the dst-CPU, and then reversing the direction to achieve another iteration.
  1931.  
  1932.   For example, for say a 4M input file, it is reasonable to expect an
  1933.   approximately 1M output file, after two complete iterations.
  1934.   [...]
  1935.   ONLY RANDOM OR RANDOM-APPEARING DATA INPUT CAN BE COMPRESSED BY MY METHOD.
  1936.   [...]
  1937.   If one iteration (of the compression 'sandwich') consists of two parts, say
  1938.   an LZ phase followed by a JG phase, the LZ method will compression by
  1939.   perhaps a ration of 2:1 (at the first iteration), perhaps much better if the
  1940.   input is text, and the JG phase will do 3-4:1, but slowly!!  During
  1941.   subsequent iterations, the LZ phase will do perhaps 1.25:1 and the JG phase
  1942.   will continue to do about 3-4:1.
  1943.  
  1944.   Experimentally, I have achieved compression results of nearly 150:1, overall,
  1945.   ^^^^^^^^^^^^^^                                                ^^^^^
  1946.   for a 60M file.  (I started with a '.arj' archive of a large DOS partition.)
  1947.   [...]
  1948.   ----------------------------------------------------------------------------
  1949.   From: coffee@spock.ici.net (Jules Gilbert)
  1950.   Newsgroups: comp.compression
  1951.   Subject: Re: Explanation: that uh, alg thing...
  1952.   Date: 15 May 1996 16:38:18 -0400
  1953.   Message-ID: <4ndfbq$cf3@spock.ici.net>
  1954.  
  1955.   [...]
  1956.   One more thing, I am preparing a short technical note to deal with the reason
  1957.   most programmers' and computer scientists' think it's impossible to (further)
  1958.   compress random input.  (Many people think that because you can't get more
  1959.   than 2^N messages from a N-bit compressed msg, that it means that you can't
  1960.   compress random input.  (Lot's of folks have told me that.)  The short story
  1961.   is:
  1962.  
  1963.   I agree that you can not get more than 2^N messages from N bits.  No question
  1964.   about it.  BUT THAT STATMENT HAS NOTHING TO DO WHATSOEVER WITH THE
  1965.   INTERPRETATION OF WHAT THOSE BITS 'MEAN'.
  1966.   [...]
  1967.   ----------------------------------------------------------------------------
  1968.   From: coffee@spock.ici.net (Jules Gilbert)
  1969.   Newsgroups: comp.compression
  1970.   Subject: Seeing is believing!
  1971.   Date: 9 Jun 1996 03:20:52 -0400
  1972.   Message-ID: <4pdu0k$otg@spock.ici.net>
  1973.  
  1974.   [...]
  1975.   If your firm needs industrial-strength compression, contact 'coffee@ici.net'
  1976.   and ask us for an on-site demonstration of our MR2 compressors.  Each can
  1977.   compress large files of 'random-appearing' information, whether RSA-encrypted
  1978.   blocks, or files already compressed using LZ-techniques.
  1979.  
  1980.   Our demonstration will give you the opportunity to observe compression of
  1981.   'random-appearing' files of at least 100MB by at least 3:1 per iteration.
  1982.   Usually, several iterations are possible.  (These are minimum figures easily
  1983.   exceeded.)
  1984.   [...]
  1985.   ----------------------------------------------------------------------------
  1986.   From: coffee@spock.ici.net (Jules Gilbert)
  1987.   Newsgroups: comp.compression
  1988.   Subject: Re: My remarks on Jules Gilbert
  1989.   Date: 24 Jul 1996 18:05:44 -0400
  1990.   Message-ID: <4t66no$9qq@spock.ici.net>
  1991.  
  1992.   [...]
  1993.   My claims can not possibly be true IF I'M PLAYING BY THE 'RULES' THAT YOU
  1994.   ASSUME APPLY TO ME.  (Sorry to shout).
  1995.  
  1996.   Clearly, anyone sending a signal (in the Shannon context), is constrained by
  1997.   limits which make it impossible to compress RAD ('random-appearing data')
  1998.   input.
  1999.   [...]
  2000.   1)  I can't compress bits any better than the next guy.  Maybe not as well,
  2001.       in fact.  
  2002.  
  2003.   2)  I have designed an engine that accepts RAD input and emits far too little
  2004.       data to reconstitute the original data, based on conventional
  2005.       assumptions. Okay!   I know this.
  2006.  
  2007.   3)  But, I none-the-less reconstitute the original data.
  2008.   [...]
  2009.   ----------------------------------------------------------------------------
  2010.   From: coffee@soran.ici.net (Jules Gilbert)
  2011.   Newsgroups: comp.compression
  2012.   Subject: Re: Jules Gilbert's New Compresssion Technology
  2013.   Date: 12 Aug 1996 08:11:10 -0400
  2014.   Message-ID: <4un70u$a2r@soran.ici.net>
  2015.  
  2016.   I have multiple methods for compressing RAD.  Watch carefully:
  2017.  
  2018.   MR1 does 3:1, on large buffers and is repeatable until the volume of input
  2019.   data falls below 128k or so.  (This figure is under user control, but
  2020.   compreesion quality will suffer as the buffer size is decreased).  Recent
  2021.   changes make this method about as fast as any conventional compressor.
  2022.  
  2023.   MR2 does at least 6:1, with a minimum buffer size of perhaps 32k.  It is also
  2024.   repeatable.  MR2 does not actually compress, though.  Instead, it translates
  2025.   an input buffer into an output buffer of roughly equivalent size.  This
  2026.   output buffer contains mostly constants, and other things, such as simple
  2027.   sequences: 28,29,31,32,33,35,40,41,42,43,44,45.  (An actual sequence of
  2028.   bytes).  Obviously, this kind of information is readily compressed, and that
  2029.   is why I claim that MR2 can achieve a minimum of 6:1.  Again, like MR1, this
  2030.   process can be re-applied over it's own output.
  2031.  
  2032.   When, I've said, "No, it's impossible to compress by 100:1" I was trying to
  2033.   get this audience to see this as realistic.  But I can compress RAD files
  2034.   100:1 if allowed to re-process the output through the same process.  I first
  2035.   actually achieved a 100:1 compression level in March of this year using tools
  2036.   ^^^^^^^^^^^^^^^^^^^^^^^^^
  2037.   designed for experimenting in RAD issues.  But now I have C programs which
  2038.   have been written to be easy to understand and are intended to be part of my
  2039.   technology transfer process for clients.
  2040.   [...]
  2041.   So, can someone compress by 100:1 or even 1000:1?  Yes! But ONLY if the input
  2042.   file is sufficiently large.  A 1000:1 compression ratio would require a very
  2043.   large input file, and, at least for PC users, archive files of this size are
  2044.   almost never produced.
  2045.   ----------------------------------------------------------------------------
  2046.   From: coffee@soran.ici.net (Jules Gilbert)
  2047.   Newsgroups: comp.compression
  2048.   Subject: Re: Gilbert's RAD compression product
  2049.   Date: 18 Aug 1996 08:40:28 -0400
  2050.   Message-ID: <4v72vs$quc@soran.ici.net>
  2051.  
  2052.   [...]
  2053.   (In my original remarks), I am quoted above as claiming that a 3,152,896 byte
  2054.   'tar 'file (conventionally compressed to 1,029,790 bytes) can be compressed
  2055.   to 50*1024 bytes.  It's an accurate quote.
  2056.  
  2057.   Now how can that be possible?
  2058.  
  2059.   If a gzip compressed version of the Corpus requires roughly a 1MB, what do I
  2060.   do with the 950k bytes I don't store in the compressed intermediate file?
  2061.  
  2062.   Well, that's certainly a puzzler!
  2063.  
  2064.   For now, all I will say is that it does not go into the compressed
  2065.   intermediate file.  And because it doesn't, Shannons' channel capacity axioms
  2066.   apply only to the 50k component.
  2067.   ----------------------------------------------------------------------------
  2068.   From: coffee@soran.ici.net (Jules Gilbert)
  2069.   Newsgroups: comp.compression
  2070.   Subject: Some answers about MR1
  2071.   Date: 22 Aug 1996 23:45:54 -0400
  2072.   Message-ID: <4vj9hi$pkb@soran.ici.net>
  2073.  
  2074.   [...]
  2075.   However, arrangements are being made to do another demo in September at MIT. 
  2076.  
  2077.   One of the files compressed and decompressed will be the Corpus, after it's
  2078.   already been compressed using ARJ, a good quality conventional compressor.
  2079.   (It should be about a 1MB at that point).  My program has made the corpus
  2080.   as small as 6k, although that requires SEVERAL separate physical passes.
  2081.   ^^^^^^^^^^^^^^
  2082.   Because we will only have a few minutes to spend on this single file, I'll
  2083.   likely stop at 250k or so.
  2084.  
  2085.   Under Linux, the total size of the compressor and decompressor load modules
  2086.   is about 50k bytes.  And under DOS, using the Intel C compiler (a great
  2087.   product, but sadly, not sold anymore), the same files total about 300k bytes.
  2088.  
  2089.   MR1 contains code that is highly dependent on the particularities of a host
  2090.   computer's floating point processor, or more correctly, architectural differ-
  2091.   ences existing between the source machine and the target machine would likely
  2092.   cause failure to de-compress.
  2093.   [...]
  2094.  
  2095.  
  2096. 9.5 David C. James
  2097.  
  2098. On July 2, 1996, David C. James was granted patent 5,533,051 "Method for data
  2099. compression" for a method claimed to be effective even on random data.
  2100.  
  2101.   From: u137@aol.com (Peter J. Cranstone)
  2102.   Newsgroups: comp.compression
  2103.   Subject: Re: Jules Gilbert's Compression Technology
  2104.   Date: Sun Aug 18 12:48:11 EDT 1996
  2105.  
  2106.   Wh have just been issued a patent (US. #5,533,051) and have several more
  2107.   pending on a new method for data compression. It will compess all types of
  2108.   data, including "random", and data containing a uniform distribution of
  2109.   "0's" and "1's".
  2110.   [...]
  2111.  
  2112. The first line of the patent abstract is:
  2113.  
  2114.   Methods for compressing data including methods for compressing highly
  2115.   randomized data are disclosed.
  2116.  
  2117. Page 3, line 34 of the patent states:
  2118.  
  2119.   A second aspect of the present invention which further enhances its ability
  2120.   to achieve high compression percentages, is its ability to be applied to
  2121.   data recursively. Specifically, the methods of the present invention are
  2122.   able to make multiple passes over a file, each time further compressing the
  2123.   file. Thus, a series of recursions are repeated until the desired
  2124.   compression level is achieved.
  2125.  
  2126. Page 27, line 18 of the patent states that the claimed method can compress
  2127. without loss *all* files by at least one bit:
  2128.  
  2129.   the direct bit encode method of the present invention is effective for
  2130.   reducing an input string by one bit regardless of the bit pattern of the
  2131.   input string.
  2132.  
  2133. The counting argument shows that this is mathematically impossible (see section
  2134. 9.2) above. If the method were indeed able to shrink any file by at least one
  2135. bit, applying it recursively would shrink gigabytes down to a few bits.
  2136.  
  2137. The patent contains evasive arguments to justify the impossible claims:
  2138.  
  2139. Page 12, line 22:
  2140.  
  2141.   Of course, this does not take into account any overhead registers or other
  2142.   "house-keeping" type information which must be tracked. However such
  2143.   overhead tends to be negligible when processing the large quantities of
  2144.   data typically encountered in data compression applications.
  2145.  
  2146. Page 27, line 17:
  2147.  
  2148.   Thus, one skilled in the art can see that by keeping the appropriate
  2149.   counters, the direct bit encode method of the present invention is
  2150.   effective for reducing an input string by one bit regardless of the bit
  2151.   pattern of the input string. Although a certain amount of "loss" is
  2152.   necessary in keeping and maintaining various counters and registers, for
  2153.   files which are sufficiently large, this overhead is insignificant compared
  2154.   to the savings obtained by the direct bit encode method.
  2155.  
  2156. The flaw in these arguments is that the the "house-keeping" type information
  2157. is *not* negligible. If it is properly taken it into account, it cancels any
  2158. gains made elsewhere when attempting to compress random data.
  2159.  
  2160. The patent contains even more evasive arguments:
  2161.  
  2162. Page 22, line 31:
  2163.  
  2164.   It is commonly stated that perfectly entropic data streams cannot be
  2165.   compressed. This misbelief is in part based on the sobering fact that for a
  2166.   large set of entropic data, calculating the number of possible bit pattern
  2167.   combinations is unfathomable. For example, if 100 ones and 100 zeros are
  2168.   randomly distributed in a block 200 bits long, there are
  2169.      200C100 = 9.055 10^58
  2170.   combinations possible. The numbers are clearly unmanageable and hence the
  2171.   inception that perfectly entropic data streams cannot be compressed. The
  2172.   key to the present compression method under discussion is that it makes no
  2173.   attempt to deal with such large amounts of data and simply operates on
  2174.   smaller portions.
  2175.  
  2176. The actual claims of the patent are harmless since they only describe
  2177. methods which cannot work (they actually expand random data instead of
  2178. compressing it). For example, claims 6 and 7 are:
  2179.  
  2180.  6. A method of compressing a stream of binary data, comprising the steps of:
  2181.   A) parsing n-bits from said stream of binary data;
  2182.   B) determining the value of said parsed n-bits;
  2183.   C) based on the results of step B, coding said values of said n-bits in at
  2184.      least one of a first, second, and third target string, wherein coding
  2185.      said value includes generating a plurality of code strings and
  2186.      correlating said value with one of said code strings and dividing said
  2187.      correlated code string variable length codes and dividing at least some
  2188.      of said into at least first and second segments, and assigning at least
  2189.      one of said correlated code string segments to at least one of said
  2190.      first, second, and third target strings, wherein at least one of said
  2191.      plurality of codes is not greater than n-1 bits long.
  2192.  
  2193.  7. The method of compressing a stream of binary data of claim 6, wherein n=2.
  2194.  
  2195. Making abstraction of the legalese, claim 7 says in short that you can
  2196. compress an arbitrary sequence of two bits down to one bit.
  2197.  
  2198. ------------------------------------------------------------------------------
  2199.  
  2200. Subject: [10] Fake compression programs (OWS, WIC)
  2201.  
  2202.  
  2203. Some programs claimed to achieve incredible compression ratios are completely
  2204. fake: they do not compress at all but just stored the uncompressed data in
  2205. hidden files on the hard disk or keep it in unused clusters. Needless to say,
  2206. such programs are dangerous and should never be used because there is a
  2207. significant risk of losing all the data.
  2208.  
  2209. The OWS program just remembers which clusters contained the data on the hard
  2210. disk. The data can be recovered only if those clusters are not used again for
  2211. another file.
  2212.  
  2213. The WIC program searches for the first directory in drive C: and creates a
  2214. hidden file called WINFILE.DLL containing a copy of all the original files.
  2215. If you copy the compressed file to another computer (which doesn't have the
  2216. file WINFILE.DLL), WIC reports a CRC error.
  2217.  
  2218. ------------------------------------------------------------------------------
  2219.  
  2220. Subject: [11] What is the V.42bis standard?
  2221.  
  2222.  
  2223. A description of the V.42bis standard is given in "The V.42bis
  2224. standard for data-compressing modems," by Clark Thomborson
  2225. <cthombor@theory.lcs.mit.edu>, IEEE Micro, Oct 1992, pp. 41-53. 
  2226.  
  2227. If you are looking for freeware source of V.42bis, please read the note
  2228. below by Peter Gutman explaining why there is no such source code.
  2229.  
  2230. Short introduction, by Alejo Hausner <hausner@qucis.queensu.ca>:
  2231.  
  2232.   The V.42bis Compression Standard was proposed by the International
  2233.   Consultative Committee on Telephony and Telegraphy (CCITT, now ITU-T) as
  2234.   an addition to the v.42 error-correction protocol for modems. Its purpose
  2235.   is to increase data throughput, and uses a variant of the
  2236.   Lempel-Ziv-Welch (LZW) compression method.  It is meant to be
  2237.   implemented in the modem hardware, but can also be built into the
  2238.   software that interfaces to an ordinary non-compressing modem.
  2239.  
  2240.   V.42bis can send data compressed or not, depending on the
  2241.   data.  There are some types of data that cannot be
  2242.   compressed.  For example, if a file was compressed first,
  2243.   and then sent through a V.42bis modem, the modem would not
  2244.   likely reduce the number of bits sent.  Indeed it is likely
  2245.   that the amount of data would increase somewhat.
  2246.  
  2247.   To avoid this problem, the algorithm constantly monitors the
  2248.   compressibility of the data, and if it finds fewer bits
  2249.   would be necessary to send it uncompressed, it switches to
  2250.   transparent mode.  The sender informs the receiver of this
  2251.   transition through a reserved code word.  Henceforth the
  2252.   data is passed as plain bytes.
  2253.  
  2254.   While transmitting in transparent mode, the sender maintains
  2255.   the LZW trees of strings, and expects the receiver to do
  2256.   likewise.  If it finds an advantage in returning to
  2257.   compressed mode, it will do so, first informing the receiver
  2258.   by a special escape code.  Thus the method allows the
  2259.   hardware to adapt to the compressibility of the data.
  2260.  
  2261.   The choice of escape code is clever.  Initially, it is a
  2262.   zero byte.  Any occurrence of the escape code is replaced,
  2263.   as is customary, by two escape codes.  In order to prevent a
  2264.   string of escape codes from temporarily cutting throughput
  2265.   in half, the escape code is redefined by adding 51 mod 256
  2266.   each time it is used.
  2267.  
  2268.  
  2269. A note from Peter Gutman <pgut01@cs.auckland.ac.nz> about V.42bis
  2270. implementations:
  2271.  
  2272.   V.42bis is covered by patents, and the licensing terms are rather complex
  2273.   because you need to license it from multiple organisations.  At one point
  2274.   British Telecom were charging something like 30,000 pounds for a license
  2275.   (this was a few years ago, things may have changed since then). Because of
  2276.   this, noone has ever implemented a freely-available version of V.42bis as
  2277.   you'd find in a modem.  There is a Unix implementation (called "compact") of
  2278.   a V.42bis-like algorithm which comes with a great many disclaimers that it
  2279.   can only be used for research purposes. [Note from FAQ maintainer: "compact"
  2280.   is available in
  2281.      http://ftp.sunet.se/ftp/pub/usenet/comp.sources.misc/volume15/compact_sv/
  2282.   The 'shrink' method of zip 1.1 (see item 2 above) is also similar to V.42bis]
  2283.  
  2284.   If you've ever wondered why noone other than modem manufacturers ever use
  2285.   V.42bis for anything, this is it.  
  2286.  
  2287.  
  2288. The CCITT (ITU-T) standards documents used to be available by ftp on
  2289. ftp.uu.net in /doc/standards/ccitt, but this service has been
  2290. discontinued. If you ftp to digital.resource.org, in directory
  2291. pub/standards there is a file that says that making the standards
  2292. available in the first place was just an experiment.
  2293.  
  2294. The documents are now on src.doc.ic.ac.uk, but the directory name
  2295. keeps changing. Check one of:
  2296.   /computing/ccitt/ccitt-standards/ccitt/
  2297.   /computing/ccitt/standards/ccitt
  2298.   /doc/ccitt-standards/ccitt
  2299. in this order. The v42bis standard is in *standards/ccitt/1992/v/v42bis.asc.Z.
  2300.  
  2301. See also item 20 below for other sites with standards documents.
  2302.  
  2303. A mail server for CCITT (ITU-T) documents is available at teledoc@itu.arcom.ch
  2304. or itudoc@itu.ch. A Gopher server is also available at gopher://info.itu.ch
  2305.  
  2306. See also the Standards FAQ posted to news.answers or get it by ftp in
  2307. ftp://rtfm.mit.edu/pub/usenet/news.answers/standards-faq
  2308.  
  2309. For ISO documents, try http://www.iso.ch/
  2310.  
  2311. ------------------------------------------------------------------------------
  2312.  
  2313. Subject: [12] I need source for the winners of the Dr Dobbs compression contest
  2314.  
  2315.  
  2316. The source of the top 6 programs of the Feb 91 Dr Dobbs data compression
  2317. contest are available by ftp on
  2318.   ftp://ftp.simtel.net/pub/simtelnet/msdos/compress/ddjcompr.zip
  2319.   ftp://garbo.uwasa.fi/pc/source/ddjcompr.zip
  2320.  
  2321. The sources are in MSDOS end-of-line format, one directory per
  2322. program.  Unix or VMS users, use "unzip -a ddjcompr" to get correct
  2323. end-of-lines (add -d to recreate the directory structure if you are
  2324. using an obsolete version of unzip such as 4.1). Three of the 6
  2325. programs are not portable and only run on MSDOS. compact and urban
  2326. work on Unix, sixpack only requires minor modifications.
  2327.  
  2328. ------------------------------------------------------------------------------
  2329.  
  2330. Subject: [13] I need source for arithmetic coding
  2331.  
  2332.  
  2333. (See question 70 for an introduction to arithmetic coding.)
  2334.  
  2335. The source for the arithmetic coder described in Chap.5 of Bell, Cleary, and
  2336. Witten's book "Text Compression" (see question 7 above) (or, equivalently, in:
  2337. Witten, Neal, and Cleary's article "Arithmetic Coding for data Compression"
  2338. from Communications of the Association for Computing Machinery, 30 (6),
  2339. pp.520-540, June, 1987) is in ftp://ftp.cpsc.ucalgary.ca/pub/projects/ar.cod/
  2340. It only comes with a simple order-0 model but it's set up so that adding your
  2341. own more sophisticated one is straightforward. Look also in
  2342. ftp://munnari.mu.oz.au/pub/arith_coder
  2343.  
  2344. A low precision arithmetic coding implementation avoiding hardware
  2345. division is available on the same site in
  2346. ftp://ftp.cpsc.ucalgary.ca/pub/projects/arithmetic.coding/low.precision.version
  2347. file low.precision.version.shar
  2348.  
  2349. Kris Popat <popat@image.mit.edu> has worked on "Scalar Quantization
  2350. with Arithmetic Coding."  It describes an arithmetic coding technique
  2351. which is quite general and computationally inexpensive.  The
  2352. documentation and example C code are available via anonymous ftp from
  2353. media-lab.media.mit.edu (18.85.0.2), in /pub/k-arith-code.
  2354.  
  2355. The program 'urban' in ddjcompr.zip (see item 12 above) is a high order
  2356. arithmetic coder working at the bit level. It is written by Urban Koistinen
  2357. <md85-epi@nada.kth.se>.
  2358.  
  2359. The DMC program is available in ftp://plg.uwaterloo.ca/pub/dmc/*.c. It
  2360. implements the algorithm described in "Data Compression using Dynamic
  2361. Markov Modelling", by Gordon Cormack and Nigel Horspool, Computer
  2362. Journal 30:6 (December 1987).  This program uses Guazzo's version of
  2363. arithmetic coding.
  2364.  
  2365. An implementation of Moffat's arithmetic coder is available in
  2366. http://www.cs.dartmouth.edu/~jmd/ArithCoder.tar.gz
  2367.  
  2368. ------------------------------------------------------------------------------
  2369.  
  2370. Subject: [15] Where can I get image compression programs?
  2371.  
  2372.  
  2373. JPEG:
  2374.     Source code for most any machine:
  2375.     ftp://ftp.uu.net/graphics/jpeg/jpegsrc.v6a.tar.gz
  2376.     ftp://nic.funet.fi/pub/graphics/packages/jpeg/jpegsrc.v6.tar.gz
  2377.     Contact: jpeg-info@uunet.uu.net (Independent JPEG Group)
  2378.  
  2379.     havefun.stanford.edu:pub/jpeg/JPEGv1.2.1.tar.Z (supports lossless mode)
  2380.     Contact: Andy Hung <achung@cs.stanford.edu> (see item 20 below)
  2381.  
  2382.     ftp://ftp.cs.cornell.edu/pub/multimed/ljpg.tar.Z (lossless jpeg)
  2383.  
  2384.     xv, an image viewer which can read JPEG pictures, is available in
  2385.     ftp://ftp.cis.upenn.edu/pub/xv/xv-3.10a.tar.Z
  2386.  
  2387. MPEG: If you don't find here what you are looking for, check also
  2388.   http://www.mpeg.org and http://www.powerweb.de/mpeg/
  2389.  
  2390.     ftp://havefun.stanford.edu/pub/mpeg/MPEGv1.2.1.tar.Z
  2391.     Contact: Andy Hung <achung@cs.stanford.edu> (see item 20 below)
  2392.  
  2393.     ftp://mm-ftp.cs.berkeley.edu/pub/multimedia/mpeg/play/
  2394.                                                mpeg_play-2.3-patched-src.tar.gz
  2395.     Contact: mpeg-bugs@cs.berkeley.edu
  2396.  
  2397.     ftp://flash.bu.edu/pub/code/mpeg_system/mpeg_system_source_v1.0.tar.gz
  2398.     (MPEG-I Multi-Stream System Layer encoder/player; includes an
  2399.      enhanced version of mpeg_play)
  2400.     Contact: Jim Boucher <jboucher@spiderman.bu.edu> or Ziv Yaar <zyaar@bu.edu>
  2401.  
  2402.     ftp://ftp.mni.mcgill.ca/pub/mpeg/mpeg_lib-1.2.tar.gz [MPEG library]
  2403.     Contact: Gregory Ward <greg@pet.mni.mcgill.ca>
  2404.  
  2405.     ftp://nvr.com/pub/NVR-software/Product-1.0.4.tar.Z
  2406.     (free demo copy of NVR's software toolkit for SPARCstations)
  2407.     Contact: Todd Brunhoff <toddb@nvr.com>
  2408.  
  2409.     ftp://havefun.stanford.edu/pub/mpeg/MPEGv1.2.1.tar.Z
  2410.     Contact: Andy Hung <achung@cs.stanford.edu> (see item 20 below)
  2411.  
  2412.     ftp://mm-ftp.cs.berkeley.edu/pub/multimedia/mpeg/play/
  2413.                                                mpeg_play-2.3-patched-src.tar.gz
  2414.     Contact: mpeg-bugs@cs.berkeley.edu
  2415.  
  2416.     ftp://flash.bu.edu/pub/code/mpeg_system/mpeg_system_source_v1.0.tar.gz
  2417.     (MPEG-I Multi-Stream System Layer encoder/player; includes an
  2418.      enhanced version of mpeg_play)
  2419.     Contact: Jim Boucher <jboucher@spiderman.bu.edu> or Ziv Yaar <zyaar@bu.edu>
  2420.  
  2421.     ftp://ftp.mni.mcgill.ca/pub/mpeg/mpeg_lib-1.2.tar.gz [MPEG library]
  2422.     Contact: Gregory Ward <greg@pet.mni.mcgill.ca>
  2423.  
  2424.     ftp://nvr.com/pub/NVR-software/Product-1.0.4.tar.Z
  2425.     (free demo copy of NVR's software toolkit for SPARCstations)
  2426.     Contact: Todd Brunhoff <toddb@nvr.com>
  2427.  
  2428.     http://www.mpeg.org/MSSG or ftp://ftp.mpeg.org/pub/mpeg/mssg/
  2429.       Contacts:  MPEG Software Simulation Group <mssg@mpeg.org>
  2430.       Concerning VMPEG: Stefan Eckart <stefan@chromatic.com>
  2431.  
  2432.     http://www.mpegtv.com (MPEGTV Software MPEG Video Player for Unix)
  2433.     Contact: Tristan Savatier <tristan@mpeg.org>
  2434.  
  2435. H.261(P*64):
  2436.     havefun.stanford.edu:pub/p64/P64v1.2.tar.Z
  2437.     Contact: Andy Hung <achung@cs.stanford.edu> (see item 20 below)
  2438.  
  2439.     ftp://zenon.inria.fr/rodeo/ivs/last_version/ivs*-src.tar.gz
  2440.     (Inria videoconference system)
  2441.     Contact: Thierry Turletti <turletti@sophia.inria.fr> (see item 20 below).
  2442.  
  2443. H.263: (by Telenor Research)
  2444.     http://www.nta.no/brukere/DVC/h263_software
  2445.  
  2446. JBIG:
  2447.     ftp://nic.funet.fi/pub/graphics/misc/test-images/jbig.tar.gz.
  2448.  
  2449.     ftp://ftp.informatik.uni-erlangen.de/pub/doc/ISO/JBIG/jbigkit-0.9.tar.gz
  2450.     Contact: Markus Kuhn <mskuhn@cip.informatik.uni-erlangen.de>
  2451.  
  2452. PNG: For code and sample images, see:
  2453.     http://quest.jpl.nasa.gov/PNG/
  2454.     ftp://ftp.uu.net/graphics/png/
  2455.     ftp://swrinde.nde.swri.edu/pub/png/
  2456.  
  2457. mg: (the MG system for compressing and indexing text and images, see item 16)
  2458.     ftp://munnari.oz.au/pub/mg/*
  2459.     Contact: Stuart Inglis <singlis@cs.waikato.ac.nz>
  2460.  
  2461. BTPC: Binary Tree Predictive Coding
  2462.     ftp://monet.uwaterloo.ca/pub/john/btpcv3.tar.Z
  2463.     Contact: John Robinson <john@monet.uwaterloo.ca>
  2464.  
  2465. epic: (pyramid wavelet coder, see item 72)
  2466.     ftp://whitechapel.media.mit.edu/pub/epic.tar.Z
  2467.     Contact: Eero P. Simoncelli <eero@media.mit.edu>
  2468.     The "Lenna" test image is available as part of the EPIC package,
  2469.     where it is named "test_image".
  2470.  
  2471. hcompress: (wavelet image compression, see item 72)
  2472.     ftp://stsci.edu/software/hcompress/hcompress.tar.Z
  2473.  
  2474. wavethresh: (wavelet software for the language S)
  2475.     http://www.stats.bris.ac.uk/pub/software/wavethresh/wavethresh2.2/
  2476.     Contact: gpn@maths.bath.ac.uk
  2477.  
  2478. rice-wlet: (wavelet software, see item 72)
  2479.     ftp://cml.rice.edu/pub/dsp/software/rice-wlet-tools.tar.Z
  2480.  
  2481. Wavelet Transform Coder Construction Kit:
  2482.     http://www.cs.dartmouth.edu/~gdavis/wavelet/wavelet.html
  2483.     Contact: Geoff Davis <gdavis@cs.dartmouth.edu>
  2484.  
  2485. scalable: (2 & 3 dimensional subband transformation)
  2486.     ftp://robotics.eecs.berkeley.edu/pub/multimedia/scalable2.tar.Z
  2487.     Contact: scalable@robotics.eecs.berkeley.edu
  2488.  
  2489. compfits:
  2490.     ftp://uwila.cfht.hawaii.edu/pub/compfits/compfits.tar.Z
  2491.     Contact: Jim Wright <jwright@cfht.hawaii.edu>
  2492.  
  2493. fitspress:
  2494.     ftp://cfata4.harvard.edu/pub/fitspress08.tar.Z
  2495.  
  2496. tiff:
  2497.     For source and sample images, see question 18 below.
  2498.  
  2499. DCT algorithms used to be in:
  2500.     ftp://etro.vub.ac.be/pub/transfer/DCT_ALGORITHMS/
  2501.     Contact: Charilos Christopoulos <chchrist@etro2.vub.ac.be> for the sources
  2502.  
  2503. xanim: (X11 animation viewer, supports Quicktime and several other formats)
  2504.     ftp://ftp.x.org/contrib/applications/xanim2683.tar.Z
  2505.     ftp://ftp.shell.portal.com/pub/podlipec/xanim26978.tar.gz
  2506.  
  2507. ppm2pz: (lossless 24-bit image compression)
  2508.     http://www.jyu.fi/~kuru/compression.html
  2509.  
  2510. A demo of image compression using neural networks is available in
  2511. http://www.ee.duke.edu/~cec/index.html.
  2512.  
  2513. For fractal compression programs, see item 17 below.
  2514. For Vector Quantization software, see item 76 in part 2 of this FAQ.
  2515. For image compression hardware, see item 85 in part 3 of this FAQ.
  2516.  
  2517. ------------------------------------------------------------------------------
  2518.  
  2519. Subject: [16] What is the state of the art in lossless image compression?
  2520.  
  2521.  
  2522. The current state-of-the-art is the JBIG algorithm.  For an
  2523. introduction to JBIG, see question 74 in part 2.
  2524.  
  2525. JBIG works best on bi-level images (like faxes) and also works well on
  2526. Gray-coded grey scale images up to about six or so bits per pixel.  You
  2527. just apply JBIG to the bit planes individually.  For more bits/pixel,
  2528. lossless JPEG provides better performance, sometimes. (For JPEG, see
  2529. question 19 below.)
  2530.  
  2531. You can find the specification of JBIG in International Standard
  2532. ISO/IEC 11544 or in ITU-T Recommendation T.82. You can order a copy
  2533. directly from ISO (www.iso.ch) or ITU (www.itu.ch) or from your
  2534. National Standards Body. In the USA, call ANSI at (212) 642-4900.
  2535.  
  2536. See also the MG system containing an implementation of the 'FELICS'
  2537. algorithm of P.G. Howard and J.S. Vitter.  FELICS usually gives better
  2538. and faster compression than lossless JPEG, at least for 8-bit
  2539. grayscale images. (See item 15 above for ftp location). From the MG
  2540. README file:
  2541.  
  2542.   The MG system is a suite of programs for compressing and
  2543.   indexing text and images. Most of the functionality implemented
  2544.   in the suite is as described in the book ``Managing Gigabytes:
  2545.   Compressing and Indexing Documents and Images'', I.H. Witten, A.
  2546.   Moffat, and T.C. Bell; Van Nostrand Reinhold, New York, 1994, ISBN
  2547.   0-442-01863-0; US $54.95; call 1 (800) 544-0550 to order.
  2548.  
  2549.   These features include:
  2550.  
  2551.   -- text compression using a Huffman-coded semi-static word-based
  2552.      scheme
  2553.   -- two-level context-based compression of bi-level images
  2554.   -- FELICS lossless compression of gray-scale images
  2555.   -- combined lossy/lossless compression for textual images
  2556.   -- indexing algorithms for large volumes of text in limited main
  2557.      memory
  2558.   -- index compression
  2559.   -- a retrieval system that processes Boolean and ranked queries
  2560.   -- an X windows interface to the retrieval system
  2561.  
  2562. Paul Howard's PhD thesis, which among other things describes FELICS,
  2563. is available in ftp://ftp.cs.brown.edu/pub/techreports/93/cs93-28.ps.Z
  2564.  
  2565. ------------------------------------------------------------------------------
  2566.  
  2567. Subject: [17] What is the state of fractal compression?
  2568.  
  2569. You may want to read first item 77 in part 2 of this FAQ:
  2570. "Introduction to Fractal compression".
  2571.  
  2572.  
  2573. from Tal Kubo <kubo@zariski.harvard.edu>:
  2574.  
  2575. According to Barnsley's book 'Fractals Everywhere', this method is
  2576. based on a measure of deviation between a given image and its
  2577. approximation by an IFS code.  The Collage Theorem states that there is
  2578. a convergent process to minimize this deviation.  Unfortunately,
  2579. according to an article Barnsley wrote for BYTE a few years ago, this
  2580. convergence was rather slow, about 100 hours on a Cray, unless assisted by
  2581. a person.
  2582.  
  2583. Barnsley et al are not divulging any technical information beyond the
  2584. meager bit in 'Fractals Everywhere'.  The book explains the idea of IFS
  2585. codes at length, but is vague about the application of the Collage theorem
  2586. to specific compression problems.
  2587.  
  2588. There is reason to believe that Barnsley's company has
  2589. *no algorithm* which takes a given reasonable image and achieves
  2590. the compression ratios initially claimed for their fractal methods.
  2591. The 1000-to-1 compression advertised was achieved only for a 'rigged'
  2592. class of images, with human assistance. The best unaided
  2593. performance I've heard of is good lossy compression of about 80-1.
  2594.  
  2595. Steve Tate <srt@duke.cs.duke.edu> confirms:
  2596.  
  2597. Compression ratios (unzoomed) seem to range from 20:1 to 60:1...  The
  2598. quality is considerably worse than wavelets or JPEG on most of the
  2599. non-contrived images I have seen.
  2600.  
  2601. But Yuval Fisher <fisher@inls1.ucsd.edu> disagrees:
  2602.  
  2603. Their performance has improved dramatically beyond what they were
  2604. talking about in BYTE a few years ago.  Human assistance to the
  2605. compression is no longer needed and the compression time is
  2606. reasonable, although the more time and compute power you throw at the
  2607. compression, the smaller the resulting file for the same level of
  2608. quality.
  2609.  
  2610. Geoffrey A Stephenson <ketlux@ketlux.demon.co.uk> adds:
  2611.  
  2612. Iterated systems are shipping a general purpose compressor at about
  2613. 300 Pounds in the UK that claims "640x480 24 bit colour compression of
  2614. about 1 min at 922k -> 10k on a 486/50 software only, decomp. to 8
  2615. bits in 3 secs, etc." At a recent multimedia conference in London they
  2616. handed out free demo disks that show the decomp. in action. The
  2617. package runs under both DOS anf WIN (DLLs provided for use in
  2618. applications). They also sell a board to speed up compression and
  2619. offer versions supporting full motion video (but not apparently at all
  2620. SVGA sizes like the static picture version). I have not yet got my
  2621. hands on a full version to test different types of pictures, but
  2622. friends have a and claim it looks good.
  2623.  
  2624.  
  2625. Thomas W. Colthurst <thomasc@athena.mit.edu> clarifies the distinction
  2626. between IFS and the Fractal Transform:
  2627.  
  2628. It is time, once and for all, to put to death the Barnsley myth that
  2629. IFSs are good for image compression.  They are not.  Various algorithms
  2630. have been proposed for this "inverse problem" ranging from the trendy
  2631. (genetic algorithms) to the deep (moment methods) to the ad hoc (the
  2632. hungry algorithm) to the absurd (the so-called "graduate student
  2633. algorithm", consisting of locking up a grad student in a tiny office
  2634. with a SGI workstation and not letting them out until they come up
  2635. with a good IFS for your image).  They are all useless for practical
  2636. image compression.
  2637.  
  2638. In fact, there are even good theoretical reasons for believing that
  2639. IFSs will never be useful for image compression.  For example, even
  2640. if you have an IFS for object A and an IFS for object B, there is no
  2641. way to combine these IFSs to get an IFS for object A union B or
  2642. object A intersect B.
  2643.  
  2644. Even Barnsley himself admits, in his latest book, that he doesn't use
  2645. IFS image compression.  Instead, he uses the so-called "fractal
  2646. transform," which is really just a variant of vector quantization
  2647. where you use the image itself, sampled at a higher scale, as the
  2648. VQ codebook.  To be fair, the fractal transform can be analyzed using
  2649. local IFSs, but local IFSs are immensely more complicated and general
  2650. than normal IFSs, to the point where one feels suspect even using the
  2651. word "IFS" to describe them.
  2652.  
  2653. It should be emphasized that the fractal transform is a real, working
  2654. method that performs about as well as other existing methods like VQ
  2655. or the discrete cosine transform. The fractal transform will probably
  2656. never beat vector quantization (VQ) as for size of the compressed
  2657. image, but does have the advantage that you don't need to carry your
  2658. codebook around.  The latest results have it slightly winning over
  2659. the discrete cosine transform; only time and more research will tell
  2660. if this advantage persists.  Just like VQ, the fractal transform
  2661. takes a while to compress, but is quick at decompression (Barnsley's
  2662. company has hardware to do this in realtime).
  2663.  
  2664. In short, IFSs are good for just about everything fractals are (and
  2665. more!), but are absolutely horrid for image compression.
  2666.  
  2667.  
  2668. Programs:
  2669.  
  2670. Check http://links.uwaterloo.ca/ for pointers to some fractal compression
  2671. programs and lots of papers on fractal compression.
  2672.  
  2673. The Waterloo BragZone (http://links.uwaterloo.ca/bragzone.base.html
  2674. or ftp://links.uwaterloo.ca/pub/BragZone/ ) compares the results of
  2675. various image compression schemes against a 32 element test suite.
  2676. Numerous rate-distortion graphs, data tables, and sample images are available.
  2677.  
  2678. A fractal image compression program is available by ftp in
  2679. ftp://inls.ucsd.edu/pub/young-fractal/yuvpak20.zip ; it contains source for
  2680. compression and decompression, source for X-windows decompression,
  2681. MSDOS executables and images. [Note from FAQ maintainer: Fisher's
  2682. program (see below) implements the same algorithm but is more general;
  2683. see http://inls.ucsd.edu/y/Fractals/ for the source code.]
  2684.  
  2685. A fractal image decompression program (note: decompression only) is
  2686. available in ftp://inls.ucsd.edu/pub/inls-ucsd/fractal-2.0.tar
  2687. In the same directory, fractal_paper.ps.Z is the paper "Fractal image
  2688. compression" by Yuval Fisher, Siggraph 92.  Reading this paper is
  2689. required to understand how the Young compression programs (see above) works.
  2690.  
  2691. A note from Yuval Fisher <yfisher@ucsd.edu>:
  2692.  
  2693.     Connect to http://inls.ucsd.edu/y/Fractals/ .  There is
  2694.     information there on my new book of contributed articles on
  2695.     fractal image compression, as well as the book's table of
  2696.     contents, some C code to encode and decode raw byte files of any
  2697.     size using a quadtree method, a manual explaining the use of the
  2698.     code, a fractal image compression bibliography (not guaranteed to
  2699.     be complete or close to it), some better executable code with
  2700.     sample encodings, and the SIGGRAPH '92 course notes on fractal
  2701.     image compression (these are based on appendix A of Chaos and
  2702.     Fractals by Peitgen et al., Springer Verlag). [The C code is also
  2703.     available in ftp://inls.ucsd.edu/pub/inls-ucsd/frac_comp.tar.Z ]
  2704.  
  2705. Another fractal compression program is available by ftp in
  2706. ftp://vision.auc.dk/pub/Limbo/Limbo*.tar.Z. It is also based on quadtrees,
  2707. as yuvpak20 and frac_comp.
  2708.  
  2709. The source code for the program published in the Oct 93 issue of
  2710. Byte is in ftp://ftp.uu.net/published/byte/93oct/fractal.exe. This is
  2711. a self-extractible arc file (must be run on MSDOS for extraction).
  2712. The source code is for a TARGA video board. [Note from FAQ maintainer:
  2713. this code is taken from Barnsley's book "Fractal Image Compression";
  2714. it implements the brute force method and is thus very slow.]
  2715.  
  2716. Iterated Systems have released a beta version of their fractal imager.
  2717. It will let you view a number of formats including JPG and do
  2718. conversions to their fractal format.  The program can be downloaded
  2719. from http://www.iterated.com
  2720.  
  2721. "The Data Compression Book" (see [NEL 1996] in item 7 above) contains
  2722. a chapter on fractal compression; it includes source code for a simple
  2723. fractal compression program.
  2724.  
  2725. Several papers on fractal image compression are available on
  2726. ftp.informatik.uni-freiburg.de in directory /documents/papers/fractal . A
  2727. biliography is in ftp://schmance.uwaterloo.ca/pub/Fractal/fractal.biblio.ps.Z
  2728.  
  2729. References:
  2730.   A. Jacquin, 'Fractal image coding based on a theory of iterated
  2731.     contractive image transformations', Proc. SPIE Visual Communications
  2732.     and Image Processing, 1990, pages 227-239.  (The best paper that explains
  2733.     the concept in a simple way.)
  2734.  
  2735.   A. Jacquin, "A Fractal Theory of Iterated Markov Operators with
  2736.     Applications to Digital Image Coding", PhD Thesis, Georgia Tech, 1989.
  2737.   It can be obtained from university microfilms for $35, phone 1-800-521-0600.
  2738.  
  2739.   M. Barnsley, L. Anson, "Graphics Compression Technology, SunWorld,
  2740.     October 1991, pp. 42-52.
  2741.   M.F. Barnsley, A. Jacquin, F. Malassenet, L. Reuter & A.D. Sloan,
  2742.     'Harnessing chaos for image synthesis', Computer Graphics,
  2743.     vol 22 no 4 pp 131-140, 1988.
  2744.   M.F. Barnsley, A.E. Jacquin, 'Application of recurrent iterated
  2745.     function systems to images', Visual Comm. and Image Processing,
  2746.     vol SPIE-1001, 1988.
  2747.   A. Jacquin, "Image Coding Based on a Fractal Theory of Iterated Contractive
  2748.     Image Transformations" p.18, January 1992 (Vol 1 Issue 1) of IEEE Trans
  2749.     on Image Processing.
  2750.   A.E. Jacquin, 'A novel fractal block-coding technique for digital
  2751.     images', Proc. ICASSP 1990.
  2752.   G.E. Oien, S. Lepsoy & T.A. Ramstad, 'An inner product space
  2753.     approach to image coding by contractive transformations',
  2754.     Proc. ICASSP 1991, pp 2773-2776.
  2755.   D.S. Mazel, Fractal Modeling of Time-Series Data, PhD Thesis,
  2756.     Georgia Tech, 1991.    (One dimensional, not pictures)
  2757.   S. A. Hollatz, "Digital image compression with two-dimensional affine
  2758.     fractal interpolation functions", Department of Mathematics and
  2759.     Statistics, University of Minnesota-Duluth, Technical Report 91-2.
  2760.     (a nuts-and-bolts how-to-do-it paper on the technique)
  2761.   Stark, J., "Iterated function systems as neural networks",
  2762.     Neural Networks, Vol 4, pp 679-690, Pergamon Press, 1991.
  2763.   Monro D M and Dudbridge F, "Fractal block coding of images",
  2764.     Electronics Letters 28(11):1053-1054 (1992)
  2765.   Beaumont J M, "Image data compression using fractal techniques",
  2766.     British Telecom Technological Journal 9(4):93-108 (1991)
  2767.   Fisher Y, "Fractal image compression", Siggraph 92
  2768.   Graf S, "Barnsley's Scheme for the Fractal Encoding of Images",
  2769.     Journal Of Complexity, V8, 72-78 (1992).
  2770.   Monro D.M. 'A hybrid fractal transform', Proc ICASSP 93, pp. V: 169-72
  2771.   Monro D.M. & Dudbridge F. 'Fractal approximation of image blocks',
  2772.     Proc ICASSP 92, pp. III: 485-488
  2773.   Monro D.M., Wilson D., Nicholls J.A. 'High speed image coding with the Bath
  2774.     Fractal Transform', IEEE International Symposium on Multimedia Technologies
  2775.     Southampton, April 1993
  2776.   Jacobs, E.W., Y. Fisher and R.D. Boss.  "Image Compression:  A study
  2777.     of the Iterated Transform Method."  _Signal Processing 29_  (1992) 25-263
  2778.   Vrscay, Edward R.  "Iterated Function Systems:  Theory, Applications,
  2779.     and the Inverse Problem."  _Fractal Geometry and Analysis_,
  2780.     J. Belair and S. Dubuc (eds.)  Kluwer Academic, 1991.  405-468.
  2781.  
  2782. Books:
  2783.     Fractal Image Compression: Theory and Application, Yuval Fisher (ed.),
  2784.     Springer Verlag, New York, 1995.
  2785.     To order the book, call 1-800-SPRINGER and ask for the book with
  2786.     ISBN number 0-387-94211-4 or check http://www.springer-ny.com/
  2787.  
  2788.     Fractal Image Compression
  2789.     Michael F. Barnsley and Lyman P. Hurd
  2790.     ISBN 0-86720-457-5, ca. 250 pp., $49.95
  2791.     Copies can be ordered directly from the publisher by sending a message
  2792.     to kpeters@math.harvard.edu with name, address and a Mastercard or
  2793.     Visa card number with expiration date.
  2794.  
  2795. Barnsley's company is:
  2796.  
  2797. Iterated Systems, Inc.
  2798. 5550A Peachtree Parkway, Suite 650
  2799. Norcross, GA  30092
  2800. tel: 404-840-0310 or 1-800-4FRACTL
  2801. fax: 404-840-0806
  2802. In UK: Phone (0734) 880261, Fax (0734) 880360
  2803.  
  2804. ------------------------------------------------------------------------------
  2805.  
  2806. Subject: [18] I need specs and source for TIFF and CCITT group 4 Fax
  2807.  
  2808.  
  2809. Specs for Group 3 and 4 image coding (group 3 is very similar to group 4)
  2810. are in CCITT (1988) volume VII fascicle VII.3. They are recommendations
  2811. T.4 and T.6 respectively. There is also an updated spec contained in 1992
  2812. recommendations T.1 to T.6.
  2813.  
  2814. CCITT (now ITU-T) specs are available by anonymous ftp (see above answer on
  2815. V.42bis).  The T.4 and T.6 specs are on src.doc.ic.ac.uk in directory
  2816. /computing/ccitt/ccitt-standards/ccitt/1988/ascii, files 7_3_01.txt.Z and
  2817. 7_3_02.txt.Z respectively.
  2818.  
  2819. The following paper covers T.4, T.6 and JBIG:
  2820.  
  2821.   "Review of standards for electronic imaging for facsimile systems"
  2822.   in Journal of Electronic Imaging, Vol. 1, No. 1, pp. 5-21, January 1992.
  2823.  
  2824.  
  2825. Source code can be obtained as part of a TIFF toolkit - TIFF image
  2826. compression techniques for binary images include CCITT T.4 and T.6:
  2827.  
  2828.     ftp://ftp.sgi.com/graphics/tiff/tiff-v3.4beta035-tar.gz
  2829.     Contact: sam@engr.sgi.com
  2830.  
  2831. There is also a companion compressed tar file (v3.0pics.tar.Z) that
  2832. has sample TIFF image files. A draft of TIFF 6.0 is in TIFF6.ps.Z.
  2833. Concerning JPEG compression in TIFF 6.0, Tom Lane <tgl@sss.pgh.pa.us> adds:
  2834.  
  2835.   TIFF 6.0's scheme for incorporating JPEG compression (spec section 22) has
  2836.   a bunch of serious deficiencies.  Don't use it.  A revised design is given
  2837.   by TIFF Technical Note #2, ftp://ftp.sgi.com/graphics/tiff/TTN2.draft.txt
  2838.   The revised design will replace section 22 in TIFF 7.0, and is implemented
  2839.   in Sam Leffler's libtiff.  See also item 75 of this FAQ for more JPEG info.
  2840.  
  2841. Software for reading and writing CCITT Group 3 and 4 images is
  2842. also available in directory ftp://merry.cs.monash.edu.au/pub/alanf/TIFF_FAX
  2843. Contact: Alan Finlay <alanf@bruce.cs.monash.edu.au>.
  2844.  
  2845.  
  2846. See also question 54 below.
  2847.  
  2848. ------------------------------------------------------------------------------
  2849.  
  2850. Subject: [19] What is JPEG?
  2851.  
  2852.  
  2853. JPEG (pronounced "jay-peg") is a standardized image compression mechanism.
  2854. JPEG stands for Joint Photographic Experts Group, the original name of the
  2855. committee that wrote the standard.  JPEG is designed for compressing either
  2856. full-color or gray-scale digital images of "natural", real-world scenes.
  2857. It does not work very well on non-realistic images, such as cartoons or
  2858. line drawings.
  2859.  
  2860. JPEG does not handle black-and-white (1-bit-per-pixel) images, nor does it
  2861. handle motion picture compression.  Related standards for compressing those
  2862. types of images exist, and are called JBIG and MPEG respectively.
  2863.  
  2864. Regular JPEG is "lossy", meaning that the image you get out of decompression
  2865. isn't quite identical to what you originally put in.  The algorithm achieves
  2866. much of its compression by exploiting known limitations of the human eye,
  2867. notably the fact that small color details aren't perceived as well as small
  2868. details of light-and-dark.  Thus, JPEG is intended for compressing images that
  2869. will be looked at by humans.  If you plan to machine-analyze your images, the
  2870. small errors introduced by JPEG may be a problem for you, even if they are
  2871. invisible to the eye.  The JPEG standard includes a separate lossless mode,
  2872. but it is rarely used and does not give nearly as much compression as the
  2873. lossy mode.
  2874.  
  2875. Question 75 "Introduction to JPEG" (in part 2 of this FAQ) gives an overview
  2876. of how JPEG works and provides references for further reading.  Also see the
  2877. JPEG FAQ article, which covers JPEG software and usage hints.  The JPEG FAQ is
  2878. posted regularly in news.answers by Tom Lane <tgl@netcom.com>.  (See question
  2879. 53 "Where are FAQ lists archived" if this posting has expired at your site.)
  2880.  
  2881. For JPEG software, see item 15 above.
  2882. For JPEG hardware, see item 85 in part 3 of this FAQ.
  2883.  
  2884. ------------------------------------------------------------------------------
  2885.  
  2886. Subject: [20] I am looking for source of an H.261/H.263 codec and MPEG
  2887.  
  2888. Many standards and draft recommendations (including H.261, H.263,
  2889. H.320, H.324), are available in http://www.imtc.org/imtc/
  2890.  
  2891. The H.261 spec is also available on src.doc.ic.ac.uk in
  2892. /computing/ccitt/standards/ccitt-standards/1992/h/h261.doc.Z (or h261.rtf.Z).
  2893.  
  2894. For H.261 hardware, see item 85 in part 3 of this FAQ.
  2895.  
  2896. Current drafts of H.324 and related recommendations including H.263 are
  2897. available in ftp://ftp.std.com/vendors/PictureTel/h324
  2898.  
  2899. Telenor Research have made available a complete simulation of
  2900. H.263. See http://www.nta.no/brukere/DVC/h263_software
  2901.  
  2902. from Thierry TURLETTI <turletti@sophia.inria.fr>:
  2903.  
  2904.      IVS (INRIA VIDEOCONFERENCING SYSTEM)
  2905.       - X11-based videoconferencing tool for SPARC, HP,  DEC  and
  2906.      Silicon Graphic workstations.
  2907.  
  2908.      ivs allows users  to  conduct  multi-host  audio  and  video
  2909.      conferences  over  the  Internet. ivs requires a workstation
  2910.      with a screen with 1, 4, 8 or  24  bits  depth.   Multi-host
  2911.      conferences  require  that  the  kernel support multicast IP
  2912.      extensions (RFC 1112).
  2913.  
  2914.      On video input, video frames are grabbed  by  the  VideoPix,
  2915.      SunVideo or Parallax boards for SparcStations or Raster Rops
  2916.      board for HP stations or the IndigoVideo board for SGI  IRIS
  2917.      Indigo workstations.  or the VIDEOTX board for DEC stations.
  2918.      No special hardware apart from  the  workstation's  build-in
  2919.      audio hardware is required for audio conference.
  2920.  
  2921.      Video encoding is done according to the H.261 standard.
  2922.      The video stream can be encoded in either Super CIF 
  2923.      (704x576 pixels) format or  CIF  (352x288  pixels) format or 
  2924.      QCIF (176x144 pixels). Default format is CIF.
  2925.  
  2926.      Sources, binaries & manuals are freely available by anonymous 
  2927.      ftp from zenon.inria.fr in the rodeo/ivs directory. An INRIA
  2928.      report describing this application is also available in the 
  2929.      same directory.
  2930.  
  2931.      If you ftp & use this package, please send all remarks or 
  2932.      modifications made to <turletti@sophia.inria.fr>. If you want 
  2933.      to be added or deleted to the ivs-users mailing list, please send 
  2934.      e-mail to ivs-users-request@sophia.inria.fr.
  2935.  
  2936.  
  2937. from Andy Hung <achung@cs.stanford.edu>:
  2938.  
  2939. Public domain UNIX C source code to do both image and image sequence
  2940. compression and decompression is available by anonymous ftp:
  2941.  
  2942. MPEG-I            ftp://havefun.stanford.edu/pub/mpeg/MPEGv*.tar.Z
  2943. CCITT H.261(P*64)    ftp://havefun.stanford.edu/pub/p64/P64v*.tar.Z
  2944. JPEG            ftp://havefun.stanford.edu/pub/jpeg/JPEGv*.tar.Z
  2945.  
  2946. These codecs operate on raw raster scanned images.
  2947.  
  2948. A software program to display raw raster-scanned YUV images and image
  2949. sequences on X grayscale or color monitors is provided by a program in
  2950. ftp://havefun.stanford.edu/pub/cv/CVv*.tar.Z
  2951. If you are using the codecs above, we recommend that you ftp this file
  2952. over as well.
  2953.  
  2954. The source code has been compiled on DEC and SUN workstations.
  2955. Caution: the P64 codec has not been tested compliant (any available
  2956. p64 video streams would be much appreciated - please let us know at
  2957. achung@cs.stanford.edu).  The other codecs have been tested with
  2958. streams from other encoders.
  2959.  
  2960. We also have some IPB MPEG-I video coded streams in pub/mpeg/*.mpg;
  2961. and P64 video streams in pub/p64/*.p64 that we have generated using
  2962. our codecs.
  2963.  
  2964. For a more complete description see the file
  2965. havefun.stanford.edu:pub/README.
  2966.  
  2967. ------------------------------------------------------------------------------
  2968.  
  2969. Subject: [25] Fast DCT (Discrete Cosine Transform) algorithms
  2970.  
  2971.  
  2972. Many image compression methods, including the JPEG, MPEG, and H.261 standards,
  2973. are based on the discrete cosine transform.  A good overall introduction to
  2974. DCT is the book "Discrete Cosine Transform---Algorithms, Advantages,
  2975. Applications" by K.R. Rao and P. Yip (Academic Press, London, 1990),
  2976. ISBN 0-12-580203-X. This has an extensive, though already dated, bibliography.
  2977.  
  2978. Here are some references mostly provided by Tom Lane <tgl@sss.pgh.pa.us>.
  2979. (This list is now rather dated.)
  2980. Most of these are in IEEE journals or conference proceedings, notably
  2981. ICASSP = IEEE Intl. Conf. on Acoustics, Speech, and Signal Processing.
  2982. ICCAS = IEEE Intl. Conf. on Circuits and Systems.
  2983. DCC = Data Compression Conference.
  2984.  
  2985. Polynomial Transform Computation of the 2-D DCT, Duhamel & Guillemot,
  2986.   ICASSP '90 p. 1515.
  2987. A Forward-Mapping Realization of the Inverse DCT, McMillan & Westover,
  2988.   DCC '92 p. 219.
  2989. A Fast Algorithm for 2-D DCT, Cho, Yun & Lee, ICASSP '91 p. 2197.
  2990. Fast Algorithm and Implementation of 2-D DCT, Cho & Lee, Tr. CAS v38 p. 297.
  2991. A DCT Chip based on a new Structured and Computationally Efficient DCT
  2992.   Algorithm, Duhamel, Guillemot & Carlach, ICCAS '90 p. 77.
  2993. Trade-offs in the Computation of Mono- and Multi-dimensional DCTs,
  2994.   Vetterli, Duhamel & Guillemot, ICASSP '89 p. 999.
  2995. Practical Fast 1-D DCT Algorithms with 11 Multiplications,
  2996.   Loeffler, Ligtenberg & Moschytz, ICASSP '89 p. 988.
  2997. New Scaled DCT Algorithms for Fused Multiply/Add Architectures,
  2998.   Linzer & Feig, ICASSP '91 p. 2201.
  2999. Fast Algorithms for the 2-D Discrete Cosine Transform, Kamangar & Rao,
  3000.   IEEE Tr. Computers, v C-31 p. 899.
  3001. Fast 2-D Discrete Cosine Transform, Vetterli, ICASSP '85 p. 1538.
  3002. A Two-Dimensional Fast Cosine Transform, Haque, Tr. ASSP v ASSP-33 p. 1532.
  3003. Real-Time Parallel and Fully Pipelined 2-D DCT Lattice Structures with
  3004.   Application to HDTV Systems, Chiu & Liu, Tr. CAS for Video Tech, v 2 p. 25.
  3005. J.F. Blinn, "What's the Deal with the DCT", IEEE Computer Graphics and
  3006.   Applications, July 1993, pp.78-83.
  3007. A C Hung and TH-Y Meng, "A Comparison of fast DCT algorithms, Multimedia 
  3008.   Systems, No. 5 Vol. 2, Dec 1994
  3009.  
  3010. For actual implementations, try the JPEG and MPEG software listed
  3011. in item 15.
  3012.  
  3013. ------------------------------------------------------------------------------
  3014.  
  3015. Subject: [26] Are there algorithms and standards for audio compression?
  3016.  
  3017.  
  3018. Yes. See the introduction to MPEG given in part 2 of this FAQ.
  3019.  
  3020. A lossless compressor for 8bit and 16bit audio data (.au) is available
  3021. in ftp://svr-ftp.eng.cam.ac.uk/pub/comp.speech/coding/shorten.tar.gz
  3022. Shorten works by using Huffman coding of prediction residuals.
  3023. Compression is generally better than that obtained by applying general
  3024. purpose compression utilities to audio files. Also supports lossy
  3025. compression.  Contact: Tony Robinson <ajr@eng.cam.ac.uk>.
  3026.  
  3027. Audio software is available on sunsite.unc.edu in subdirectories of
  3028. /pub/electronic-publications/IUMA/audio_utils:
  3029. - An MPEG audio player is in mpeg_players/Workstations/maplay1_2.tar.Z.
  3030. - The sources of the XING MPEG audio player for Windows is in
  3031.   mpeg_players/Windows/mpgaudio.zip.
  3032. - An encoder/decoder is in converters/source/mpegaudio.tar.Z.
  3033.  
  3034. MSDOS audio software is available in
  3035. ftp://ftp.simtel.net/pub/simtelnet/msdos/sound/
  3036. In particular, MPEG-2 audio software is in ampegsrc.zip and ampeg43.zip.
  3037.  
  3038. MPEG audio files are available in ftp.iuma.com and http://www.iuma.com/
  3039.  
  3040. Copied from the comp.dsp FAQ posted by guido@cwi.nl (Guido van Rossum):
  3041.  
  3042.   Strange though it seems, audio data is remarkably hard to compress
  3043.   effectively.  For 8-bit data, a Huffman encoding of the deltas between
  3044.   successive samples is relatively successful.  For 16-bit data,
  3045.   companies like Sony and Philips have spent millions to develop
  3046.   proprietary schemes.
  3047.  
  3048.   Public standards for voice compression are slowly gaining popularity,
  3049.   e.g. CCITT G.721 and G.723 (ADPCM at 32 and 24 kbits/sec).  (ADPCM ==
  3050.   Adaptive Delta Pulse Code Modulation.)  Free source code for a *fast*
  3051.   32 kbits/sec ADPCM (lossy) algorithm is available by ftp from ftp.cwi.nl
  3052.   as /pub/audio/adpcm.shar.  (** NOTE: if you are using v1.0, you should get
  3053.   v1.1, released 17-Dec-1992, which fixes a serious bug -- the quality
  3054.   of v1.1 is claimed to be better than uLAW **)
  3055.  
  3056.   (Note that U-LAW and silence detection can also be considered
  3057.   compression schemes.)
  3058.  
  3059. Information and source code for adpcm are available in
  3060. http://www.nb.rockwell.com/ref/adpcm.html
  3061.  
  3062. Source for Sun's free implementation of CCITT compression types G.711,
  3063. G.721 and G.723 is in ftp://ftp.cwi.nl/pub/audio/ccitt-adpcm.tar.gz
  3064.  
  3065. You can get a G.721/722/723 package by email to teledoc@itu.arcom.ch, with
  3066. GET ITU-3022
  3067. as the *only* line in the body of the message.
  3068.  
  3069.  
  3070. A note on u-law from Markus Kuhn <mskuhn@immd4.informatik.uni-erlangen.de>:
  3071.  
  3072.   u-law (more precisely (greek mu)-law or 5-law if you have an 8-bit
  3073.   ISO terminal) is more an encoding then a compression method,
  3074.   although a 12 to 8 bit reduction is normally part of the encoding.
  3075.   The official definition is CCITT recommendation G.711. If you want
  3076.   to know how to get CCITT documents, check the Standards FAQ
  3077.   posted to news.answers or get the file standards-faq by ftp in
  3078.   directory ftp://rtfm.mit.edu/pub/usenet/news.answers/
  3079.  
  3080.  
  3081. See also the comp.dsp FAQ for more information on:
  3082.  
  3083. - The U.S. DoD's Federal-Standard-1016 based 4800 bps code excited linear
  3084.   prediction voice coder version 3.2a (CELP 3.2a)
  3085. - The U.S. DoD's Federal-Standard-1015/NATO-STANAG-4198 based 2400 bps
  3086.   linear prediction coder version 53 (LPC-10e v53)
  3087. - Realtime DSP code and hardware for FS-1015 and FS-1016
  3088.  
  3089. The comp.dsp FAQ is in comp.dsp with subject "FAQ: Audio File Formats" and in
  3090. ftp://rtfm.mit.edu/pub/usenet/news.answers/audio-fmts/part1
  3091.  
  3092.  
  3093. CELP C code for Sun SPARCs is in ftp://ftp.super.org/pub/speech/celp_3.2a.tar.Z
  3094. An LPC10 speech coder is in ftp://ftp.super.org/pub/speech/lpc10-1.0.tar.gz ;
  3095. a derived version is in http://www.arl.wustl.edu/~jaf/lpc/lpc10-1.1.tar.gz
  3096.  
  3097. Source code for ITU-T (CCITT) G.728 Low Delay CELP speech compression
  3098. is in ftp://svr-ftp.eng.cam.ac.uk/pub/comp.speech/sources/ldcelp-2.0.tar.gz
  3099.  
  3100.  
  3101. Recommended reading:
  3102.   Digital Coding of Waveforms: Principles and Applications to Speech and
  3103.   Video.  N. S. Jayant and Peter Noll.  Prentice-Hall, 1984, ISBN
  3104.   0-13-211913-7.
  3105.  
  3106. Information on GSM sound compression is available at
  3107. http://ccnga.uwaterloo.ca/~jscouria/gsm.html
  3108.  
  3109.  
  3110. from Markus Kuhn <mskuhn@immd4.informatik.uni-erlangen.de>:
  3111.  
  3112.   One highest quality sound compression format is called ASPEC and has
  3113.   been developed by a team at the Frauenhofer Institut in Erlangen (Germany)
  3114.   and others.
  3115.  
  3116.   ASPEC produces CD like quality and offers several bitrates, one is
  3117.   128 kbit/s. It is a lossy algorithm that throws away frequencies that
  3118.   aren't registered in the human cochlea in addition to sophisticated
  3119.   entropy coding. The 64 kbit/s ASPEC variant might soon bring hifi
  3120.   quality ISDN phone connections. It has been implemented on standard DSPs.
  3121.  
  3122.   The Layer 3 MPEG audio compression standard now contains what is officially
  3123.   called the best parts of the ASPEC and MUSICAM algorithms. A reference is:
  3124.  
  3125.     K.Brandenburg, G.Stoll, Y.F.Dehery, J.D.Johnston, L.v.d.Kerkhof,
  3126.     E.F.Schroeder: "The ISO/MPEG-Audio Codec: A Generic Standard for Coding
  3127.     of High Quality Digital Audio",
  3128.     92nd. AES-convention, Vienna 1992, preprint 3336
  3129.  
  3130.  
  3131. from Jutta Degener <jutta@cs.tu-berlin.de> and Carsten Bormann
  3132. <cabo@cs.tu-berlin.de>:
  3133.  
  3134.   GSM 06.10 13 kbit/s RPE/LTP speech compression available
  3135.   --------------------------------------------------------
  3136.  
  3137.   The Communications and Operating Systems Research Group (KBS) at the
  3138.   Technische Universitaet Berlin is currently working on a set of
  3139.   UNIX-based tools for computer-mediated telecooperation that will be
  3140.   made freely available.
  3141.  
  3142.   As part of this effort we are publishing an implementation of the
  3143.   European GSM 06.10 provisional standard for full-rate speech
  3144.   transcoding, prI-ETS 300 036, which uses RPE/LTP (residual pulse
  3145.   excitation/long term prediction) coding at 13 kbit/s.
  3146.  
  3147.   GSM 06.10 compresses frames of 160 13-bit samples (8 kHz sampling
  3148.   rate, i.e. a frame rate of 50 Hz) into 260 bits; for compatibility
  3149.   with typical UNIX applications, our implementation turns frames of 160
  3150.   16-bit linear samples into 33-byte frames (1650 Bytes/s).
  3151.   The quality of the algorithm is good enough for reliable speaker
  3152.   recognition; even music often survives transcoding in recognizable 
  3153.   form (given the bandwidth limitations of 8 kHz sampling rate).
  3154.  
  3155.   Version 1.0 of the implementation is available per anonymous ftp from
  3156.   ftp.cs.tu-berlin.de in the directory /pub/local/kbs/tubmik/gsm/ ;
  3157.   more information about the library can be found on the World-Wide Web
  3158.   at http://www.cs.tu-berlin.de/~jutta/toast.html .
  3159.   Questions and bug reports should be directed to jutta@cs.tu-berlin.de
  3160.   and cabo@informatik.uni-bremen.de .
  3161.  
  3162.  
  3163. from Bob Kimball <rkimball@qualcomm.com>:
  3164.  
  3165.   I work for Qualcomm Inc. and we are designing a digital cellular telephone
  3166.   system.  Our phone uses our variable rate vocoder (QCELP) which is designed
  3167.   for speach and compresses 64Kb/s speach to 8Kb/s through 1Kb/s with 8Kb/s
  3168.   being full rate and 1Kb/s for 1/8 rate speach.  It works great for speach.
  3169.  
  3170.   The QCELP process is documented in our Common Air Interface (CAI) which is
  3171.   available for anonymous ftp from lorien.qualcomm.com in /pub/cdma
  3172.   each chapter is a postscript file.  The vocoder is described in appendix A.
  3173.   The whole document is quite large.  This is the document which is currently
  3174.   going through the TIA standard committee so it is not a final version.  The
  3175.   appendix on the vocoder should be almost identical to the final version...
  3176.   whenever that comes out.
  3177.  
  3178.  
  3179. from Nicola Ferioli <ser1509@cdc835.cdc.polimi.it>:
  3180.  
  3181.   ftp://ftp.simtel.net/pub/simtelnet/msdos/sound/vocpak20.zip
  3182.     Lossless 8-bit sound file compressor
  3183.  
  3184.   VOCPACK is a compressor/decompressor for 8-bit digital sound using a
  3185.   lossless algorithm; it is useful to save disk space without degrading
  3186.   sound quality.  It can compress signed and unsigned data, sampled at any
  3187.   rate, mono or stereo.  Since the method used is not lossy, it isn't
  3188.   necessary to strip file headers before compressing.
  3189.  
  3190.   VOCPACK was developed for use with .VOC (SoundBlaster) and .WAV (Windows)
  3191.   files, but any 8-bit sound can be compressed since the program takes no
  3192.   assumptions about the file structure.
  3193.  
  3194.   The typical compression ratio obtained goes from 0,8 for files sampled at
  3195.   11 KHz to 0,4 for 44 Khz files.  The best results are obtained with 44 KHz
  3196.   sounds (mono or stereo): general-purpose archivers create files that can be
  3197.   twice longer than the output of VOCPACK.  You can obtain smaller values
  3198.   using lossy compressors but if your goal is to keep the sound quality
  3199.   unaltered you should use a lossless program like VOCPACK.
  3200.  
  3201. from Harald Popp <popp@iis.fhg.de>:
  3202.  
  3203.   new version 1.0 of ISO/MPEG1 Audio Layer 3 Shareware available
  3204.  
  3205.   major improvements of the new version:
  3206.        - encoder works twice as fast
  3207.        - improved file handling for encoder including .WAV files
  3208.  
  3209.   You may download the shareware from fhginfo.fhg.de (153.96.1.4)
  3210.   from the directory /pub/layer3
  3211.  
  3212.   The source code for the MPEG1 audio decoder layer 1, 2 and 3 is
  3213.   now available on fhginfo.fhg.de (153.96.1.4) in /pub/layer3/public_c.
  3214.  
  3215.   There are two files:
  3216.      mpeg1_iis.tar.Z     (Unix: lines seperated by line feed only)
  3217.      mpeg1iis.zip        (PC: lines seperated by carriage return and line feed)
  3218.  
  3219. For more information about this product and MPEG Audio Layer 3, see
  3220. the document "Informations about MPEG Audio Layer-3" maintained by
  3221. Juergen Zeller <zeller@iis.fhg.de>, available in
  3222. ftp://fhginfo.fhg.de/pub/layer3/MPEG_Audio_L3_FAQ.html
  3223.  
  3224. from Monty <xiphmont@athena.mit.edu>:
  3225.  
  3226.   A beta release of the OggSquish audio compression/decompression utility is
  3227.   available at http://deskfish.cs.titech.ac.jp:8001/squish/squish_index.html
  3228.  
  3229.   OggSquish is a compression package designed to reduce the file size of
  3230.   digitized 8 and 16 bit audio samples (or samples of any periodic
  3231.   data).  OggSquish will operate on files sampled at any speed, but it is
  3232.   designed to work with very high quality samples, for example, CD
  3233.   quality samples.
  3234.  
  3235. ------------------------------------------------------------------------------
  3236.  
  3237. Subject: [30] My archive is corrupted!
  3238.  
  3239.  
  3240. The two most common reasons for this are
  3241.  
  3242. (1) failing to use the magic word "tenex" (when connected to SIMTEL20 and
  3243.     other TOPS20 systems) or "binary" (when connected to UNIX systems) when
  3244.     transferring the file from an ftp site to your host machine.  The
  3245.     reasons for this are technical and boring.  A synonym for "tenex" is
  3246.     "type L 8", in case your ftp doesn't know what "tenex" means.
  3247.  
  3248. (2) failing to use an eight-bit binary transfer protocol when transferring
  3249.     the file from the host to your PC.  Make sure to set the transfer type
  3250.     to "binary" on both your host machine and your PC.
  3251.  
  3252. gopher is also known to corrupt binary files. In particular, if gzip
  3253. complains about a multi-part file, it's likely that the .gz file
  3254. has been corrupted by gopher. Use ftp in binary mode instead.
  3255.  
  3256. ------------------------------------------------------------------------------
  3257.  
  3258. Subject: [31] pkunzip reports a CRC error!
  3259.  
  3260.  
  3261. The portable zip 1.1 contains many workarounds for undocumented restrictions
  3262. in pkunzip. Compatibility is ensured for pkunzip 1.10 only. All previous
  3263. versions (pkunzip 1.0x) have too many bugs and cannot be supported. This
  3264. includes Borland unzip.
  3265.  
  3266. So if your pkunzip reports a CRC error, check that you are not using
  3267. an obsolete version. Get either pkzip 2.04g or unzip 5.12 (see question
  3268. 2 above for ftp sites). To generate zip files compatible with pkunzip 1.10,
  3269. use zip 1.1 (see item 2 above for ftp site).
  3270.  
  3271. ------------------------------------------------------------------------------
  3272.  
  3273. Subject: [32] VMS zip is not compatible with pkzip!
  3274.  
  3275.  
  3276. The problem is most likely in the file transfer program.
  3277.  
  3278. Many use kermit to transfer zipped files between PC and VMS VAX.  The
  3279. following VMS kermit settings make VMS-ZIP compatible with PKZIP:
  3280.  
  3281.                                              VMS kermit        PC kermit
  3282.                                            ---------------   --------------
  3283.  
  3284. Uploading PKZIPped file to be UNZIPped:    set fi ty fixed    set fi ty bi
  3285. Downloading ZIPped file to be PKUNZIPped:  set fi ty block    set fi ty bi
  3286.  
  3287. If you are not using kermit, transfer a file created by pkzip on MSDOS
  3288. to VMS, transfer it back to your PC and check that pkunzip can extract it.
  3289.  
  3290. ------------------------------------------------------------------------------
  3291.  
  3292. Subject: [33] I have a problem with Stacker or DoubleSpace!
  3293.  
  3294.  
  3295. The newsgroup comp.compression is *not* the appropriate place to
  3296. discuss about one specific program on one specific operating system.
  3297. Since you have bought a legal copy of Stacker or MSDOS 6.x, you have
  3298. the documentation of your product; please read it. If you can't find
  3299. the answer in the documentation, please report the problem to the Stac
  3300. or Microsoft customer support. (For Stac, use one of StacTec@aol.com,
  3301. StacMacTec@aol.com or StacOS2tec@aol.com.)  If you really feel that the
  3302. net has to know about your problem, please post in one of the MSDOS
  3303. newsgroups, such as comp.os.msdos.apps or comp.binaries.ibm.pc.d.
  3304.  
  3305. ------------------------------------------------------------------------------
  3306.  
  3307. Subject: [50] What is this 'tar' compression program?
  3308.  
  3309.  
  3310. tar is not a compression program. It just combines several files
  3311. into one, without compressing them. tar file are often compressed with
  3312. 'compress', resulting in a .tar.Z file. See question 2, file type .tar.Z.
  3313. GNU tar has the capability to (de)compress files as well.
  3314.  
  3315. When you have to archive a lot of very small files, it is often
  3316. preferable to create a single .tar file and compress it, than to
  3317. compress the individual files separately. The compression program can
  3318. thus take advantage of redundancy between separate files.  The
  3319. disadvantage is that you must uncompress the whole .tar file to
  3320. extract any member. You can also improve compression by grouping
  3321. files by type, as in:
  3322.  
  3323.   tar cvf - `ls | sort -t. +1` | gzip > file.tar.gz
  3324.  
  3325. ------------------------------------------------------------------------------
  3326.  
  3327. Subject: [51] I need a CRC algorithm
  3328.  
  3329.  
  3330. As its name implies (Cyclic Redundancy Check) a crc adds redundancy whereas
  3331. the topic of this group is to remove it. Yet this question comes up often in
  3332. comp.compression.
  3333.  
  3334. The file ftp://ftp.rocksoft.com/clients/rocksoft/papers/crc_v3.txt is a pretty
  3335. comprehensive description of the whole CRC concept, including a C program.
  3336.  
  3337. See also:
  3338. - Schwaderer W.D., "CRC Calculation", April 85 PC Tech Journal, pp.118-133.
  3339. - "Calculating CRCs by Bits and Bytes", BYTE Magazine, September 1986
  3340. - Ramabadran T.V., Gaitonde S.S., "A tutorial on CRC computations", IEEE
  3341.   Micro, Aug 1988.
  3342. - ftp://ftp.uni-erlangen.de/pub/doc/ISO/english/async-HDLC
  3343. - the source of all archivers, such as the file makecrc.c in the Info-ZIP
  3344.   sources (see extension .zip in item 2)
  3345.  
  3346.  
  3347. The following C code (by Rob Warnock <rpw3@sgi.com>) does CRC-32 in
  3348. BigEndian/BigEndian byte/bit order.  That is, the data is sent most
  3349. significant byte first, and each of the bits within a byte is sent most
  3350. significant bit first, as in FDDI. You will need to twiddle with it to do
  3351. Ethernet CRC, i.e., BigEndian/LittleEndian byte/bit order. [Left as an
  3352. exercise for the reader.]
  3353.  
  3354. The CRCs this code generates agree with the vendor-supplied Verilog models
  3355. of several of the popular FDDI "MAC" chips.
  3356.  
  3357. u_long crc32_table[256];
  3358. /* Initialized first time "crc32()" is called. If you prefer, you can
  3359.  * statically initialize it at compile time. [Another exercise.]
  3360.  */
  3361.  
  3362. u_long crc32(u_char *buf, int len)
  3363. {
  3364.         u_char *p;
  3365.         u_long  crc;
  3366.  
  3367.         if (!crc32_table[1])    /* if not already done, */
  3368.                 init_crc32();   /* build table */
  3369.         crc = 0xffffffff;       /* preload shift register, per CRC-32 spec */
  3370.         for (p = buf; len > 0; ++p, --len)
  3371.                 crc = (crc << 8) ^ crc32_table[(crc >> 24) ^ *p];
  3372.         return ~crc;            /* transmit complement, per CRC-32 spec */
  3373. }
  3374.  
  3375. /*
  3376.  * Build auxiliary table for parallel byte-at-a-time CRC-32.
  3377.  */
  3378. #define CRC32_POLY 0x04c11db7     /* AUTODIN II, Ethernet, & FDDI */
  3379.  
  3380. init_crc32()
  3381. {
  3382.         int i, j;
  3383.         u_long c;
  3384.  
  3385.         for (i = 0; i < 256; ++i) {
  3386.                 for (c = i << 24, j = 8; j > 0; --j)
  3387.                         c = c & 0x80000000 ? (c << 1) ^ CRC32_POLY : (c << 1);
  3388.                 crc32_table[i] = c;
  3389.         }
  3390. }
  3391.  
  3392. ------------------------------------------------------------------------------
  3393.  
  3394. Subject: [52] What about those people who continue to ask frequently asked
  3395.               questions in spite of the frequently asked questions document?
  3396.  
  3397.  
  3398. Just send them a polite mail message, referring them to this document.
  3399. There is no need to flame them on comp.compression.  That would just
  3400. add more noise to this group.  Posted answers that are in the FAQ are
  3401. just as annoying as posted questions that are in the FAQ.
  3402.  
  3403. ------------------------------------------------------------------------------
  3404.  
  3405. Subject: [53] Where are FAQ lists archived?
  3406.  
  3407.  
  3408. Many are crossposted to news.answers.  That newsgroup should have a
  3409. long expiry time at your site; if not, talk to your sysadmin.
  3410.  
  3411. FAQ lists are available by anonymous FTP from rtfm.mit.edu.
  3412. The comp.compression FAQ that you are reading is in directory
  3413.    ftp://rtfm.mit.edu/pub/usenet/news.answers/compression-faq/
  3414.  
  3415. This FAQ is also accessible in the World Wide Web at
  3416. http://www.cis.ohio-state.edu/hypertext/faq/usenet/compression-faq/top.html
  3417. or http://www.cs.ruu.nl/wais/html/na-dir/compression-faq/.html
  3418.  
  3419. If you don't have FTP access, you can access the archives by mail
  3420. server.  Send an email message to mail-server@rtfm.mit.edu
  3421. containing the commands
  3422.     send usenet/news.answers/compression-faq/part1
  3423.     send usenet/news.answers/compression-faq/part2
  3424.     send usenet/news.answers/compression-faq/part3
  3425. For instructions, send an email message to the same address with the
  3426. words "help" and "index" (no quotes) on separate lines. If you don't
  3427. get a reply, check your return address, or add a line such as
  3428.     path myname@foo.edu
  3429.  
  3430. ------------------------------------------------------------------------------
  3431.  
  3432. Subject: [54] I need specs for graphics formats
  3433.  
  3434. Get the book by Murray & vanRyper "Encyclopedia of graphics file formats",
  3435. O'Reilly & associates, ISBN 1-56592-058-9. Or have a look in directory
  3436. /pub/graphics.formats on zamenhof.cs.rice.edu; it contains descriptions of
  3437. gif, tiff, fits, etc...
  3438.  
  3439. See also the comp.graphics FAQ and the Graphics Formats FAQ. The latter is in
  3440. ftp://rtfm.mit.edu/pub/usenet/news.answers/graphics/fileformats-faq/
  3441. http://www.cis.ohio-state.edu/hypertext/faq/usenet/graphics/fileformats-faq/top.html
  3442.  
  3443. ------------------------------------------------------------------------------
  3444.  
  3445. Subject: [55] Where can I find Lenna and other images?
  3446.  
  3447. The Waterloo BragZone (http://links.uwaterloo.ca/bragzone.base.html
  3448. or ftp://links.uwaterloo.ca:/pub/BragZone/ ) compares the results of
  3449. various image compression schemes against a 32 element test suite.
  3450. Sample images are available.
  3451.  
  3452. The Computer Vision Home Page has many links to test images in
  3453. http://www.cs.cmu.edu:80/afs/cs/project/cil/ftp/html/v-images.html
  3454.  
  3455. A bunch of standard images (lenna, baboon, cameraman, crowd, moon
  3456. etc..) used to be in ftp://eedsp.gatech.edu/database/images . The
  3457. images are in 256-level grayshades (256x256 pixels, 256 "colors").
  3458.  
  3459. [Note: the site ipl.rpi.edu mentioned below keeps changing. Images
  3460. stay there for a while then disappear. They are again available at
  3461. the time of writing (27 Dec 93).]
  3462.  
  3463. The site ipl.rpi.edu (128.113.14.50) has standard images in two
  3464. directories:
  3465.    ftp://ipl.rpi.edu/pub/image/still/usc 
  3466.    ftp://ipl.rpi.edu/pub/image/still/canon
  3467.  
  3468. (The directory /pub/image/sequence was taken offline because of
  3469. possible copyright problems, but has come back again. In particular,
  3470. Miss America is in subdirectories of /pub/image/sequence/missa.)
  3471.  
  3472. In each of those directories are (usually) the following directories:
  3473.    bgr     - 24 bit blue, green, red
  3474.    color   - 24 bit red, green, blue
  3475.    gray    - 8 bit grayscale uniform weighted
  3476.    gray601 - 8 bit grayscale CCIR-601 weighted
  3477.  
  3478. And in these directories are the actual images.  
  3479.  
  3480. For example, the popular lena image is in
  3481.    ftp://ipl.rpi.edu/pub/image/still/usc/bgr/lena        # 24 bit BGR
  3482.    ftp://ipl.rpi.edu/pub/image/still/usc/gray/lena-y.ras # 8 bit gray
  3483.  
  3484. All of the images are in Sun rasterfile format.  You can use the pbm
  3485. utilities to convert them to whatever format is most convenient.
  3486. [pbm is available in ftp://ftp.ee.lbl.gov/pbmplus*.tar.Z ].
  3487. Questions about the ipl archive should be sent to help@ipl.rpi.edu.
  3488.  
  3489.  
  3490. There are few gray-scale still images and some raw data of test results
  3491. available in directory ftp://nic.funet.fi/pub/graphics/misc/test-images/
  3492. There are lots of .gif images in ftp://nic.funet.fi/pub/pics/
  3493.  
  3494. Medical images can be found in:
  3495.   ftp://decaf.stanford.edu/pub/images/medical/mri
  3496.   ftp://eedsp.gatech.edu/database/images/wchung/medical
  3497.   ftp://omicron.cs.unc.edu/pub/projects/softlab/CHVRTD
  3498.  
  3499. The WWW address for the National Library of Medicine is http://www.nlm.nih.gov
  3500. A list of health and medical related Internet resources is available ftp://in
  3501. ftp.sura.net/pub/nic/HealthResources/medical.resources.3-94
  3502.  
  3503. Rodney Peck <rodney@balltown.cma.com> is interested in some method
  3504. of establishing a canonical ftp database of images but does not have
  3505. the resources to provide an ftp site for that database. Send suggestions to
  3506. rodney@balltown.cma.com.
  3507.  
  3508.  
  3509. Beware: the same image often comes in many different forms, at
  3510. different resolutions, etc... The original lenna image is 512 wide,
  3511. 512 high, 8 bits per pel, red, green and blue fields.  Gray-scale
  3512. versions of Lenna have been obtained in two different ways from the
  3513. original:
  3514.  (1) Using the green field as a gray-scale image, and
  3515.  (2) Doing an RGB->YUV transformation and saving the Y component.
  3516. Method (1) makes it easier to compare different people's results since
  3517. everyone's version should be the same using that method.  Method (2)
  3518. produces a more correct image.
  3519.  
  3520. For the curious: 'lena' or 'lenna' is a digitized Playboy centerfold, from
  3521. November 1972. (Lenna is the spelling in Playboy, Lena is the Swedish spelling
  3522. of the name.) Lena Soderberg (ne Sjooblom) was last reported living in her
  3523. native Sweden, happily married with three kids and a job with the state liquor
  3524. monopoly.  In 1988, she was interviewed by some Swedish computer related
  3525. publication, and she was pleasantly amused by what had happened to her
  3526. picture.  That was the first she knew of the use of that picture in the
  3527. computer business.  A scan of the original Lenna from Playboy is available at
  3528. http://www.isr.com/~chuck/lenna.html
  3529.  
  3530. The editorial in the January 1992 issue of Optical Engineering (v. 31 no. 1)
  3531. details how Playboy has finally caught on to the fact that their copyright on
  3532. Lena Sjooblom's photo is being widely infringed.  It sounds as if you will
  3533. have to get permission from Playboy to publish it in the future.
  3534.  
  3535. The CCITT (ITU-T) test images are in ftp://ftp.cs.waikato.ac.nz/pub/ccitt/
  3536. and http://www.cs.waikato.ac.nz/~singlis/ccitt.html
  3537. [The images in ftp://nic.funet.fi/pub/graphics/misc/test-images/ccitt*.tif are
  3538. corrupted.] This set is commonly used to compare binary image compression
  3539. techniques. The images are 1728x2376 pixels.
  3540.  
  3541. ------------------------------------------------------------------------------
  3542.  
  3543. Subject: [56] I am looking for a message digest algorithm
  3544.  
  3545.  
  3546. Look on the ftp site rsa.com, in directory /pub. MD4 and MD5 are there.
  3547. This question would be more appropriate on sci.crypt.
  3548.  
  3549. ------------------------------------------------------------------------------
  3550.  
  3551. Subject: [57] I have lost my password on a .zip file
  3552.  
  3553. This question would be more appropriate on sci.crypt.
  3554. Try the following:
  3555. ftp://idea.sec.dsi.unimi.it/pub/security/crypt/code/zipcrack.c.gz
  3556. ftp://idea.sec.dsi.unimi.it/pub/security/crypt/rpub.cl.msu.edu/crypt/msdos/zipcrack*
  3557. ftp://idea.sec.dsi.unimi.it/pub/security/crypt/rpub.cl.msu.edu/crypt/other/zipcrack.c
  3558. ftp://ftp.ox.ac.uk/pub/crypto/cryptanalysis/fzc100.zip
  3559. ftp://ftp.ox.ac.uk/pub/crypto/cryptanalysis/pkcrack.zip
  3560. ftp://ftp.ox.ac.uk/pub/crypto/cryptanalysis/zipcrk20.zip
  3561.  
  3562. These are brute force crackers. A known plaintext attack is also possible,
  3563. see http://www.unix-ag.uni-kl.de/~conrad/krypto/pkcrack.html
  3564. or ftp://ripem.msu.edu/pub/crypt/docs/kocher-pkzip-attack.ps.gz
  3565.  
  3566.           End of part 1 of the comp.compression faq.
  3567.