Slashdot Mirror

Mozilla's latest milestone, M17, arrived today(ish); early adopters, go thou and download. And while you're waiting, check out this summary of the state of the art of PNG written by Greg Roelofs. PNG is ready for prime time in its Mozilla incarnation (though there are a few outstanding issues). Imminent takeover of the net predicted. Film at 11. Update later by J: OK, so M17 isn't available yet. Mea culpa; Greg and I misread a planning page. Here are Greg's comments/corrections to clear up the matter.

PNG, MNG, JNG and Mozilla M17
26 June 2000
by Greg Roelofs

PNG support in Mozilla has improved greatly over the last few releases ("milestones"), and with each milestone comes a corresponding Slashdot posting and a lot of discussion. Unfortunately, not all of the discussion is entirely accurate, so here's a preemptive posting that attempts to update folks on the status of PNG support in Mozilla and other apps and to clear up some of the more common misconceptions. (This seems to be an annual event...)

Home Page

First of all, the PNG home page got booted off of cdrom.com in early March, and in early May it settled into what should be its absolutely final home:

• http://www.libpng.org/pub/png/
• ftp://ftp.libpng.org/pub/png/

This is currently hosted on freesoftware.com, Walnut Creek CD-ROM's new site for free software (quel surprise!), but if something should ever happen to Walnut Creek, libpng.org will be redirected appropriately. (On a related note, the new zlib URL is http://www.info-zip.org/pub/infozip/zlib/, which is also currently hosted on freesoftware.com.)

PNG Features for the Web

Insofar as this is ostensibly a Mozilla posting, let's have a brief rundown of the PNG features that are most useful to Web designers:

• alpha transparency - This is geek jargon for partial or variable transparency, and it lets you do nice effects that are independent of the background color(s), such as antialiased (non-jaggy) text, drop shadows, gradient fades, and translucency. PNG not only supports a full 8-bit alpha channel in grayscale and RGB images but also what amounts to an "RGBA palette" in colormapped images. The latter lets you do nice transparency without a huge hit in file size. For example, all but one of the transparent images on my PNG alpha-transparency test page are 8-bit or less; the lone exception (one of the toucans) is a 32-bit RGBA image, virtually indistinguishable from its 8-bit cousins. Note that PNG supports only unassociated (non-premultiplied) alpha, since the alternative is not lossless.

• gamma correction - Gamma allows you to display the same image on different platforms without looking too dark on some and too light on others. For best results it does require that both the designer's display system and the user's be calibrated, but even educated guessing is better than nothing in a viewing program (which is what Mozilla does). Warning! Watch out for Adobe Photoshop; version 5.0 had a serious factor-of-two bug in its PNG gamma support, and 4.0 also had some problems. (Things seem to be fixed in 5.5, however.)

• color correction - Where gamma has to do with image "brightness," color correction has to do with rendering shades of color precisely. PNG supports it, but not many applications do; it's pretty tricky to get right. Note that Photoshop 5.5 writes incorrect PNG "iCCP" chunks, and this will crash applications based on libpng 1.0.6. (Older versions of libpng ignore the chunk, and the soon-to-be-released libpng 1.0.7 will work around it.) Also note that feeding a valid iCCP chunk to PS 5.5 will hang it.

• compression - A lot of people have some seriously crazy ideas about PNG's compression. Here's the straight dope:
  • PNGs tend to be 15% to 20% smaller than equivalent GIFs on average. There are some GIFs, particularly 32- or 64-color ones, that are smaller than the best PNGs, but usually by only a couple of percent. There are also many that are more than twice as large as the corresponding PNGs, but these tend to be tiny images. (One exception is this image, which is dimensionally rather large yet only 1/3 the file size of the GIF version.)

  • PNGs tend to be much larger than standard JPEGs. JPEGs are lossy, while PNGs are lossless; for natural (photographic) material, no lossless format can compete with JPEG--PNGs will typically be 5 or 10 times as large. On the other hand, for simple graphics or text-filled images with relatively few colors and sharp edges, JPEG is much worse, both in quality and in file size. (This means you, Slackware guys!) Use the proper tool for the job--no single image format is best in all cases.

  • PNG is roughly comparable to JPEG-LS, the new lossless JPEG standard. On the Waterloo BragZone test suite, JPEG-LS beat PNG by 5% to 10% on natural images, but PNG beat JPEG-LS by 35% to 270% on "artistic" images. YMMV.

  • PNG's compression method can be implemented in such a way that it is completely free of all known patents, but it can also be implemented in such a way that it infringes on patents held by PKWARE, Stac and others. You can guess which way zlib was written. Folks who are neither rich nor expert in patent law should probably stick to zlib- and libpng-based implementations.

  • Unlike (LZW-based) GIF, in which the compression is basically deterministic--that is, you end up with pretty much the same data regardless of who does the compression--PNG's scheme leaves a lot of room for optimization. Some programs do a good job, some don't. The GIMP happens to be one of the good ones, as is pngcrush. Photoshop traditionally has been one of the not-so-good ones, although version 5.5 includes a "Save for Web" option that presumably invokes ImageReady. ImageReady 1.0 was mediocre and reportedly isn't much better in its current release (i.e., pngcrush beats it by 15% to 25%), but it is better than Photoshop's normal "Save as" option.

  • The compression engine can't help clueless users who perform apples-and-oranges comparisons. If you start with a truecolor image and save it as both GIF and PNG, chances are the PNG will be 24-bit while the GIF will be 8-bit. Guess what? It's pretty tough to overcome that initial 3:1 deficit, no matter how good your compression engine is. (If you're not sure what kind of PNGs you have, check!) Also don't add a lot of text annotations to the PNG--unless you do the same to the GIF--and especially don't add a useless alpha channel to opaque images! (That last is directed at the Burn All GIFs folks...) Recompressing an image after it's been through JPEG compression is also a bad idea; JPEG leaves a lot of nasty little artifacts (often invisible to the naked eye) that screw up non-JPEG compressors.

• interlacing - PNG's interlacing scheme is two-dimensional, much like progressive JPEG, but unlike GIF--which uses a one-dimensional, line-based scheme. The upshot is that an interlaced PNG with text in it will be readable roughly twice as soon as the corresponding interlaced GIF.

• animation - Nope. But see MNG, below.

• MIME type - image/png. If PNG images on your server show up as broken images within Web pages and as gobbledygook text when referenced directly (i.e., as standalone URLs), you probably don't have the MIME type set up correctly. On the other hand, if they show up correctly for MSIE and some versions of Netscape but not others, you're probably running Microsoft's IIS server. Technically it's a bug in older versions of Netscape (versions 4.04 through 4.5), but consider switching to Apache anyway...

• browser compatibility - We'll get to that in a moment.

PNG Extensions and the Future

PNG is extensible. PNG is lossless. PNG is a single-image, raster (bitmap) format. One of its overriding design goals was backward compatibility. As a result, don't expect to see any sort of lossy compression methods (JPEG is doing a fine job of that, with the exception of transparency--but see JNG, below). Also don't expect to see any vector-based extensions--SVG with gzip content-encoding has that covered. Indeed, don't expect to see any new, incompatible compression methods for quite a while. Until there are lossless methods that can, on average, halve the size of PNG images, the cost in software compatibility is far too great. (Keep in mind that there still browsers that don't support progressive JPEG, and that was a relatively trivial change! And let's not even talk about JPEG 2000...)

PNG is also not going to become an animated format. Leaving multiple-image support out of PNG was a conscious design decision by the PNG development group, and it's still the right decision. Overloading a still image format with animation or video features merely confuses users and Web browsers, which have no way to distinguish still images from animations without prying into the data streams (which usually means downloading them first). Developers who prefer to program monolithically can always program for MNG instead; it's architecturally identical to PNG, and PNG is a pure subset of MNG.

Related Formats

MNG: As the previous paragraph suggests, the animated version of PNG is called MNG, for Multiple-image Network Graphics. It supports looping (including nested loops), clipping, deltas, and other features, plus everything PNG supports--including alpha transparency, of course. The home page is here:

• http://www.libpng.org/pub/mng/
• ftp://ftp.libpng.org/pub/mng/

Since this spring, a free reference library, libmng, has been under development by Gerard Juyn; its home page is at:

• http://www.libmng.com/

Note that the MIME type is video/x-mng; it has not yet been registered with the IETF. Undoubtedly there will be many misconfigured Web servers in coming years...

JNG: JNG is short for JPEG Network Graphics and is a proper subset of MNG, just as PNG is, but it's worth a separate mention. The idea is to combine the best of both worlds: JPEG's excellent compression and PNG's incredibly spiffy alpha transparency and color correction. JNG is almost identical to PNG, but in addition to standard IDAT chunks (which in JNG contain the alpha channel), there are also JDAT chunks that contain a standard JPEG/JFIF stream (suitable for handing off to libjpeg). From a developer's standpoint, if you've got support for both PNG alpha and ordinary JPEG/JFIF, adding JNG is a breeze. Of course, JNG is also supported by recent libmng betas. Its MIME type is image/x-jng.

Browser Status

Most browsers have supported PNG since at least late 1997 (when Netscape Navigator and Microsoft Internet Explorer finally did), but almost without exception, their support for alpha transparency has been abominable. Amazingly enough, it seems that 2000 may be the year that browsers finally support it, more or less ubiquitously. In April alone there were three newcomers, with another in May; so far this year, the total has more than doubled. Here's the current list of browsers that at least attempt to do alpha transparency correctly, with their supported platforms indicated in italics. If screen shots of the PNG alpha-transparency test page are available, they're linked to the browser name:

• Arena (Unix/X) - this was the first browser with good alpha support (at least for Unix, and I think anywhere). It died in 1998, however, and the final release tends to core-dump on PNG images. It always used its own "sandy" background pattern rather than that specified in the HTML. (Very old screen shot.)
• Browse (RISC OS) - Acorn's browser was the first to fully support PNG transparency and gamma correction, including background images, but it died along with Acorn itself in June 1999. The browser may or may not eventually show up in Pace Micro's digital set-top boxes. (Very old screen shot.)
• iCab (Macintosh) - this was the first Macintosh browser to support alpha transparency (since the 1.8 beta), but it doesn't do gamma correction yet.
• ICE Browser (Java) - ICEsoft's commercial browser for Java reportedly has full alpha support, but I haven't verified that.
• Internet Explorer (Macintosh) - version 5.0 added superb PNG support, including alpha, gamma and color correction. This is probably the best PNG-supporting browser available today. Unfortunately, the Windows and Unix versions seem to be a completely separate code base, so there's no telling when (or if) they'll have equally good support. (See the browsers page for details.)
• Konqueror (Unix/KDE) - I just heard that KDE's file-manager-cum-browser has full alpha support, but I haven't had a chance to check it myself. I'll try to get some screen shots added soon, however.
• Mozilla (Macintosh, Unix/X, Windows) - alpha was enabled in April, though there are a few gotchas: the Windows code is currently broken (bug 36694 and 19283, to be fixed by beta3), and the X code is a slightly nasty hack--it looks beautiful on 24-bit displays, but it's slow when scrolling, and the quality for users of 8- and 16-bit displays will be relatively poor. Nevertheless, it's a vast improvement over the previous code, and it's basically the only game in town for Unix users. Note that the infamous PNG interlacing bug (3195) was fixed in May, and Tim Rowley checked in initial MNG and JNG support on 12June.
• NetPositive (BeOS) - version 2.2, released in April, added support for alpha transparency; but like iCab, it doesn't yet do gamma correction. (It also doesn't display interlaced PNGs progressively.)
• Netscape - see Mozilla (which is basically what Navigator 6.0 will be).
• Sega Dreamcast Web Browser (Dreamcast) - version 2.0 of Planetweb's browser for the Sega Dreamcast game console, released in May, fully supports alpha transparency, but I don't have any screen shots yet.
• Webster XL (RISC OS) - R-Comp's RISC OS browser is claimed to have full alpha support, but I don't have verification, and it doesn't appear to be under development anymore.
• WebTV (WebTV) - surprisingly enough, WebTV has decent support for 32-bit RGBA PNGs, but its support for palette transparency is broken. In principle it should be easy to fix, but then again, it's a strange platform. (Note that the fonts look considerably better on a television screen.)

Honorable Mention goes to Siegel & Gale's PNG Live plug-in for Netscape, which was the only plug-in ever to manage alpha transparency (in Windows only). It died before ever getting out of beta, though, and plug-ins in general are useless for PNG. So is the HTML 4.0 OBJECT tag, but don't get me started...

Other Apps, Libs, etc.

I currently list some 500 distinct PNG-supporting packages (more if you break things like Microsoft Office into their constituent parts) in 8 categories (soon to be 9 or 10), not to mention a dozen pieces of hardware. PNG has now reached the point where even freeware authors generally don't bother to tell me when they've added support; it's largely taken for granted. (I do occasional Freshmeat sweeps, but I usually don't have time, and many entries don't mention PNG even if it's supported.) Quite a number of the apps include full source code, by the way--which is the way it should be, of course. ;-)

Within the libraries-and-toolkits category, there are a surprising number of independent PNG implementations (either encoders or decoders or both), including ones in C, C++, Java, JavaScript, Pascal, and even Ada95. PNG is now a standard part of Java 2 SE 1.3 and Tcl/Tk, and it is the main image format in the popular gd library and all of its Perl-based derivatives. In turn, this has led to its online use in areas as diverse as server statistics, chemical diagrams, computer-generated mazes, and weather maps.

Even better, PNG is the native, internal image format for a number of major applications (including Macromedia Fireworks and Microsoft Office), and it's becoming a popular icon format for advanced GUIs. It also ships as a standard part of BeOS, via the Translation Kit, and it's supported natively in the Windows Me shell (and possibly in Windows 2000 Professional).

Conclusion?

Ordinarily I'd mumble something about how PNG has finally achieved massive studliness and will soon be taking over the world, but what the hell--it has, it is, and if it's not obvious from what I've already written, another couple of lines won't make any difference. Go forth, visit the web site, write code, make lots of PNGs, etc., etc.

And Microsoft, pleeeeease get on the ball with Internet Explorer for Windows and Unix...

Jean-loup is the kind of person I love to see us interview here. He's important in the sense that work he's done (positively) affects almost every Linux or Unix user, but the chance of Jean-loup ever getting any "mainstream" media attention is zero. Or possibly less. Without people like Jean-loup there would be no Open Source movement, and I consider the chance to present him as a Slashdot interview guest a *huge* honor. The readers who asked the excellent questions, and the moderators who helped select them, also deserve major kudos. So thanks to all of you for an excellent Q&A session!

1) bzip2 Support
by Aaron M. Renn

When is gzip going to provide (transparent) support for bzip2 files and the Burrows-Wheeler algorithm?

Will BW be an algorithm option within the gzip file format itself ever?

Gailly:

I have worked very closely with Julian Seward, the author of bzip and bzip2. The goal was to integrate a Burrows-Wheeler algorithm inside zlib 2.0 (upon which gzip 2.0 is based). One of the requirements was to avoid the kind of arithmetic coding used in bzip because of both patent and decoding speed concerns, so Julian wrote the Huffman coding code now used in bzip2. Another requirement was to put the code in library form and Julian did that too.

Unfortunately, Julian decided to release bzip2 independently instead of staying within the gzip 2.0 project. It was mainly my fault, since I couldn't spend enough time on the other parts of the project, and the project was not advancing fast enough. Since Julian left, the project progressed even more slowly, and new blood is obviously necessary, because other responsibilities no longer leave me enough time for gzip. If you're an expert in data compression, e-mail me to convince me that you are the most qualified person to turn the zlib/gzip 2.0 project into an overwhelming success :-)

2) The Data Compression Book
by drudd

I am a happy owner of The Data Compression Book (2nd Ed). With the increasing availability of compression routines within libraries (Java's GZIP streams spring to mind), does this make your book a little unnecessary?

Should software authors continue to write their own compression routines, or simply trust the versions available to them in library form?

I can see some definite advantages to library code, i.e. the ability to upgrade routines, and having standardized algorithms which can be read by any program which utilizes the library.

Gailly:

The compression routines in The Data Compression Book were written mainly for clarity, not for efficiency. The source code is present to help understand how the compression algorithms work. It is not designed to be used as is in other software packages, although it does work if efficiency is not a concern. Consider the book as teaching material, not as a data compression library distributed in printed form.

This doesn't mean that the book is unnecessary. Good data compression libraries don't appear magically; their authors had to learn compression techniques one day. If the book helps one person to get started in the data compression area and this person later writes a great compression library, the book will have been useful.

Judging by the success of my zlib data compression library, I think that a vast majority of software authors prefer using an existing library rather than reinventing the wheel. This is how the open-source model works: building upon the work of others is far more efficient than rewriting everything.

3) Compression patents
by Stephen

The compression world has many patents, notably for Lempel-Ziv compression as used in GIF. What is your view on companies patenting non-obvious algorithms for such processes as data compression?

Gailly:

The worst problem is companies patenting obvious algorithms. There are far more patents on obvious ideas than patents on really innovative ideas. In the data compression area, even something as basic as run-length encoding (replace "aaaaa" with a special code indicating repeat "a" 5 times) has been patented at a time where this technique had been well known and widely used for many years.

It is distressing to see the U.S. patent office granting such patents, in contradiction with the law requiring an idea to be both novel and non-obvious to be patentable. Philip Karn has made a good analysis of the problem.

Patents on non-obvious algorithms are a different matter. One view is that algorithms should not be patentable at all, whether obvious or not. This used to be the case, until the US patent office started to grant patents on methods which were nothing else than pure algorithms. I'm afraid that a switch back to the original situation is extremely unlikely.

Several reforms are necessary:

• The patent term should be significantly shortened, at least for algorithms. The patent system was designed to benefit society as a whole, ensuring that new ideas would eventually be made public after a limited period of time instead of being kept as trade secrets. But 20 years is incredibly long in the software area. Granting a monopoly for such a long time no longer benefits society.
• The non-obviousness requirement should be applied much more strictly. A little bit of common sense would avoid a lot of patents on trivial ideas.
• Prior art should be checked more thoroughly. Even non-obvious ideas should not be patented if they have been in use for several years already.

4) A question about Mandrake...
by Mr. Penguin

As we all know, at first Mandrake was little more than a repackaged version of Red Hat. That's changed a bit with the newer versions. My question is this: to what degree will Mandrake continue to differ from RedHat and will there ever be a "developer" version (i.e. one that is centered towards those who are a bit more technically competant)?

Gailly:

That's changed more than a bit. Our distribution is now completely made by us. Believe me, doing everything ourselves represents a significant amount of work. Few people understand how much work is involved in making an independent distribution. We have our own development teams producing things like our graphical install DrakX, our disk partionner DiskDrake, management of security levels in msec, hardware detection with Lothar, etc... Our packages are more recent than those of Red Hat and have more functionality (such as supermount support in the kernel). Red Hat is now even copying packages made by MandrakeSoft (e.g. rpmlint). I hate having to speak like a salesman here, but it is really unfair to say that Mandrake just repackages RedHat; this is simply not true anymore.

Have you looked at Linux-Mandrake 7.0? It does include a developer version. At install time, select the option "Custom" then "Development". You will get all necessary development tools. We, as developers, use our own distribution :-)

5)Why is Mandrake better than Red Hat?

I guess that you have at least a little something to say about this.

Is the 586 optimization enough to justify Mandrake's position? Are you especially proud of any of the architectural differences between the distributions (from what I have been told, the Apache-PHP layout is quite a bit different).

How do feel about the steps that Red Hat has taken to change their distribution in reaction to yours?

Gailly:

Mandrake is far more than Red Hat plus 586 optimization. It is an independent distribution. (See the answer to A question about Mandrake above.) We have enhanced some packages (such as the kernel or Apache) to provide additional functionality for users.

It's clear that Mandrake pushes Red Hat to improve its own version and nowdays Red Hat includes some development from Mandrakesoft. There is a coopetition: Red Hat and MandrakeSoft both benefit from the same open-source community, but they compete for the customer. This coopetition is fully beneficial for the Linux users since we both need to constantly improve our version. We just make sure that Mandrake stays ahead :-)

6)Winzip
by Uruk

I noticed that you allowed the people who make the Winzip product to incorporate code written for Gzip. I think it's cool that you did that, because it would be horrible if winzip couldn't handle the gzip format, but at the same time, what are your thoughts about allowing free software code to be included in closed-source products?

Just out of curiosity, (tell me it's none of my business if you want to and I'll be OK with that) did you receive a licensure fee from the company that makes Winzip for the code?

Gailly:

I started writing compression code simply because my 20 MB hard disk, the biggest size one could get at the time, was always full. I didn't write it for money. Even after I got a bigger hard disk, I continued writing compression code for fun. In particular I was not interested in writing a Windows interface. This is why I allowed my code to be used in Winzip. I received exactly 0$ for this.

The zlib license also allows it to be used in closed-source products. This was an absolute requirement for the success of the PNG image format, which relies on zlib for data compression. If we had used a GPL license, Netscape and Microsoft Explorer wouldn't support PNG, and the PNG format would be dead by now. I also received 0$ for zlib, if you're curious...

Even though I allowed my code to be used in closed-source products, I am a strong supporter of the open-source model. That's also why I work for MandrakeSoft. The open-source model is getting so much momentum that it will in the end dominate the software industry.

7) What about wavelets? by Tom Womack

The Data Compression Book was an excellent reference when it came out, but there are some hot topics in compression that it doesn't cover - frequency-domain lossy audio techniques (MP3), video techniques (MPEG2 and especially MPEG4), wavelets (Sorenson video uses these, I believe, and JPEG2000 will), and the Burrows-Wheeler transform from bzip.

Do you have any plans for a new edition of the book, or good Web references for these techniques? BZip is covered well by a Digital research note, but documentation for MPEG2 seems only to exist as source code and I can't find anything concrete about using wavelets for compression. The data is all there on the comp.compression FAQ, but the excellent exposition of the book is sorely lacking.

Gailly:

These are all very worthy topics, and Mark Nelson and I would like to incorporate them into a new version of the book someday. However, the decision to produce a new version is taken by the publisher, not us.

Note also that these are all very big topics, and it would be quite easy to write an entire book on each one. I don't think they will fit well in a chapter or two. Covering JPEG in one chapter was difficult, and Mark Nelson has been criticized for not describing the specifics of the standard algorithm.

You can find some Web references here and there, in addition to the comp.compression FAQ.

8) Compression software
by jd

It is a "truism" in the Free Software community that code should be released early and released often.

However, much of the software you've written has started gathering a few grey hairs. Gzip, for example, has been at 1.2.4 for many, many moons, and looks about ready to collect it's gold watch.

Is compression software in a category that inherently plateus quickly, so that significant further work simply isn't possible? Or is there some other reason, such as Real Life(tm) intruding and preventing any substantial development?

(I noticed, for example, a patch for >4Gb files for gzip, which could have been rolled into the master sources to make a 1.2.5. This hasn't happened.)

Gailly:

I knew this question would come when I accepted a Slashdot interview. But I had to face it :-(

In short, you are completely right. While working on gzip 2.0, I continued to maintain gzip 1.x, accumulating small patches, and answering a lot of e-mail. But I was hoping to be able to release gzip 2.0 directly, without having to make an intermediate 1.x release. See my answer to the question bzip2 support concerning the state of gzip 2.0 and the Real Life interference. I'd be glad to hand over all my patches for 1.2.4 to the person who can help me getting the gzip 2.0 project to full speed.

9) Proprietary algorithms
by Tom Womack

The field of compression has been thronged with patents for a long time - but patents at least reveal the algorithm.

What do you think of the expansion of trade-secret algorithms (MP3 quantisation tables, Sorensen, RealAudio and RealVideo, Microsoft Streaming Media) where the format of the data stream is not documented anywhere?

Gailly:

The hardware specifications for some video cards were kept as trade secrets. As a result, the XFree86 project couldn't support these cards. Increasing pressure from users who didn't buy those cards because they couldn't be supported has led the manufacturers to release the hardware specifications, and those cards are now well supported.

Similarly, I think that pressure from the open-source community can become strong enough to force companies to open their formats. We're not completely there yet, but I believe that the open-source model will win in the end. Even a giant like Microsoft starts considering Linux as a real threat.

10) Go and Compression
by Inquisiter

When I think of a game like go or chess, I think that each player develops there own algorithm to beat their opponent. If you agree, what relationships or similarities do you see between your intrest in Go and your intrest in compression?

Gailly:

What a nice question!

Even though the rules of go are very simple, the complexity of go is astonishing. The best go programs can be beaten by a human beginner. The search space in go is so large that is impossible to apply the techniques that are so successful in chess. Professional go players never evaluate all possible moves. They are able to compress an enormous amount of information into a relatively small number of concepts.

Where a human beginner would have to painfully examine many possibilities to realize that a certain group is doomed, and would most likely fail in the process, a go expert can immediately recognize certain shapes and can very quickly determine the status of a group. One gets stronger at the game by reaching higher levels of abstraction, which are in effect better compression ratios. A professional go player can elaborate concepts that an average player would have great difficulties to understand.

Current go programs are overwhelmed by the amount of information present in a game of go. They are unable to understand what is really going on. Since brute force techniques can't work in go, programs will only improve by compressing the available information down to a manageable level.

Jean-loup is the kind of person I love to see us interview here. He's important in the sense that work he's done (positively) affects almost every Linux or Unix user, but the chance of Jean-loup ever getting any "mainstream" media attention is zero. Or possibly less. Without people like Jean-loup there would be no Open Source movement, and I consider the chance to present him as a Slashdot interview guest a *huge* honor. The readers who asked the excellent questions, and the moderators who helped select them, also deserve major kudos. So thanks to all of you for an excellent Q&A session!

1) bzip2 Support
by Aaron M. Renn

When is gzip going to provide (transparent) support for bzip2 files and the Burrows-Wheeler algorithm?

Will BW be an algorithm option within the gzip file format itself ever?

Gailly:

I have worked very closely with Julian Seward, the author of bzip and bzip2. The goal was to integrate a Burrows-Wheeler algorithm inside zlib 2.0 (upon which gzip 2.0 is based). One of the requirements was to avoid the kind of arithmetic coding used in bzip because of both patent and decoding speed concerns, so Julian wrote the Huffman coding code now used in bzip2. Another requirement was to put the code in library form and Julian did that too.

Unfortunately, Julian decided to release bzip2 independently instead of staying within the gzip 2.0 project. It was mainly my fault, since I couldn't spend enough time on the other parts of the project, and the project was not advancing fast enough. Since Julian left, the project progressed even more slowly, and new blood is obviously necessary, because other responsibilities no longer leave me enough time for gzip. If you're an expert in data compression, e-mail me to convince me that you are the most qualified person to turn the zlib/gzip 2.0 project into an overwhelming success :-)

2) The Data Compression Book
by drudd

I am a happy owner of The Data Compression Book (2nd Ed). With the increasing availability of compression routines within libraries (Java's GZIP streams spring to mind), does this make your book a little unnecessary?

Should software authors continue to write their own compression routines, or simply trust the versions available to them in library form?

I can see some definite advantages to library code, i.e. the ability to upgrade routines, and having standardized algorithms which can be read by any program which utilizes the library.

Gailly:

The compression routines in The Data Compression Book were written mainly for clarity, not for efficiency. The source code is present to help understand how the compression algorithms work. It is not designed to be used as is in other software packages, although it does work if efficiency is not a concern. Consider the book as teaching material, not as a data compression library distributed in printed form.

This doesn't mean that the book is unnecessary. Good data compression libraries don't appear magically; their authors had to learn compression techniques one day. If the book helps one person to get started in the data compression area and this person later writes a great compression library, the book will have been useful.

Judging by the success of my zlib data compression library, I think that a vast majority of software authors prefer using an existing library rather than reinventing the wheel. This is how the open-source model works: building upon the work of others is far more efficient than rewriting everything.

3) Compression patents
by Stephen

The compression world has many patents, notably for Lempel-Ziv compression as used in GIF. What is your view on companies patenting non-obvious algorithms for such processes as data compression?

Gailly:

The worst problem is companies patenting obvious algorithms. There are far more patents on obvious ideas than patents on really innovative ideas. In the data compression area, even something as basic as run-length encoding (replace "aaaaa" with a special code indicating repeat "a" 5 times) has been patented at a time where this technique had been well known and widely used for many years.

It is distressing to see the U.S. patent office granting such patents, in contradiction with the law requiring an idea to be both novel and non-obvious to be patentable. Philip Karn has made a good analysis of the problem.

Patents on non-obvious algorithms are a different matter. One view is that algorithms should not be patentable at all, whether obvious or not. This used to be the case, until the US patent office started to grant patents on methods which were nothing else than pure algorithms. I'm afraid that a switch back to the original situation is extremely unlikely.

Several reforms are necessary:

• The patent term should be significantly shortened, at least for algorithms. The patent system was designed to benefit society as a whole, ensuring that new ideas would eventually be made public after a limited period of time instead of being kept as trade secrets. But 20 years is incredibly long in the software area. Granting a monopoly for such a long time no longer benefits society.
• The non-obviousness requirement should be applied much more strictly. A little bit of common sense would avoid a lot of patents on trivial ideas.
• Prior art should be checked more thoroughly. Even non-obvious ideas should not be patented if they have been in use for several years already.

4) A question about Mandrake...
by Mr. Penguin

As we all know, at first Mandrake was little more than a repackaged version of Red Hat. That's changed a bit with the newer versions. My question is this: to what degree will Mandrake continue to differ from RedHat and will there ever be a "developer" version (i.e. one that is centered towards those who are a bit more technically competant)?

Gailly:

That's changed more than a bit. Our distribution is now completely made by us. Believe me, doing everything ourselves represents a significant amount of work. Few people understand how much work is involved in making an independent distribution. We have our own development teams producing things like our graphical install DrakX, our disk partionner DiskDrake, management of security levels in msec, hardware detection with Lothar, etc... Our packages are more recent than those of Red Hat and have more functionality (such as supermount support in the kernel). Red Hat is now even copying packages made by MandrakeSoft (e.g. rpmlint). I hate having to speak like a salesman here, but it is really unfair to say that Mandrake just repackages RedHat; this is simply not true anymore.

Have you looked at Linux-Mandrake 7.0? It does include a developer version. At install time, select the option "Custom" then "Development". You will get all necessary development tools. We, as developers, use our own distribution :-)

5)Why is Mandrake better than Red Hat?

I guess that you have at least a little something to say about this.

Is the 586 optimization enough to justify Mandrake's position? Are you especially proud of any of the architectural differences between the distributions (from what I have been told, the Apache-PHP layout is quite a bit different).

How do feel about the steps that Red Hat has taken to change their distribution in reaction to yours?

Gailly:

Mandrake is far more than Red Hat plus 586 optimization. It is an independent distribution. (See the answer to A question about Mandrake above.) We have enhanced some packages (such as the kernel or Apache) to provide additional functionality for users.

It's clear that Mandrake pushes Red Hat to improve its own version and nowdays Red Hat includes some development from Mandrakesoft. There is a coopetition: Red Hat and MandrakeSoft both benefit from the same open-source community, but they compete for the customer. This coopetition is fully beneficial for the Linux users since we both need to constantly improve our version. We just make sure that Mandrake stays ahead :-)

6)Winzip
by Uruk

I noticed that you allowed the people who make the Winzip product to incorporate code written for Gzip. I think it's cool that you did that, because it would be horrible if winzip couldn't handle the gzip format, but at the same time, what are your thoughts about allowing free software code to be included in closed-source products?

Just out of curiosity, (tell me it's none of my business if you want to and I'll be OK with that) did you receive a licensure fee from the company that makes Winzip for the code?

Gailly:

I started writing compression code simply because my 20 MB hard disk, the biggest size one could get at the time, was always full. I didn't write it for money. Even after I got a bigger hard disk, I continued writing compression code for fun. In particular I was not interested in writing a Windows interface. This is why I allowed my code to be used in Winzip. I received exactly 0$ for this.

The zlib license also allows it to be used in closed-source products. This was an absolute requirement for the success of the PNG image format, which relies on zlib for data compression. If we had used a GPL license, Netscape and Microsoft Explorer wouldn't support PNG, and the PNG format would be dead by now. I also received 0$ for zlib, if you're curious...

Even though I allowed my code to be used in closed-source products, I am a strong supporter of the open-source model. That's also why I work for MandrakeSoft. The open-source model is getting so much momentum that it will in the end dominate the software industry.

7) What about wavelets? by Tom Womack

The Data Compression Book was an excellent reference when it came out, but there are some hot topics in compression that it doesn't cover - frequency-domain lossy audio techniques (MP3), video techniques (MPEG2 and especially MPEG4), wavelets (Sorenson video uses these, I believe, and JPEG2000 will), and the Burrows-Wheeler transform from bzip.

Do you have any plans for a new edition of the book, or good Web references for these techniques? BZip is covered well by a Digital research note, but documentation for MPEG2 seems only to exist as source code and I can't find anything concrete about using wavelets for compression. The data is all there on the comp.compression FAQ, but the excellent exposition of the book is sorely lacking.

Gailly:

These are all very worthy topics, and Mark Nelson and I would like to incorporate them into a new version of the book someday. However, the decision to produce a new version is taken by the publisher, not us.

Note also that these are all very big topics, and it would be quite easy to write an entire book on each one. I don't think they will fit well in a chapter or two. Covering JPEG in one chapter was difficult, and Mark Nelson has been criticized for not describing the specifics of the standard algorithm.

You can find some Web references here and there, in addition to the comp.compression FAQ.

8) Compression software
by jd

It is a "truism" in the Free Software community that code should be released early and released often.

However, much of the software you've written has started gathering a few grey hairs. Gzip, for example, has been at 1.2.4 for many, many moons, and looks about ready to collect it's gold watch.

Is compression software in a category that inherently plateus quickly, so that significant further work simply isn't possible? Or is there some other reason, such as Real Life(tm) intruding and preventing any substantial development?

(I noticed, for example, a patch for >4Gb files for gzip, which could have been rolled into the master sources to make a 1.2.5. This hasn't happened.)

Gailly:

I knew this question would come when I accepted a Slashdot interview. But I had to face it :-(

In short, you are completely right. While working on gzip 2.0, I continued to maintain gzip 1.x, accumulating small patches, and answering a lot of e-mail. But I was hoping to be able to release gzip 2.0 directly, without having to make an intermediate 1.x release. See my answer to the question bzip2 support concerning the state of gzip 2.0 and the Real Life interference. I'd be glad to hand over all my patches for 1.2.4 to the person who can help me getting the gzip 2.0 project to full speed.

9) Proprietary algorithms
by Tom Womack

The field of compression has been thronged with patents for a long time - but patents at least reveal the algorithm.

What do you think of the expansion of trade-secret algorithms (MP3 quantisation tables, Sorensen, RealAudio and RealVideo, Microsoft Streaming Media) where the format of the data stream is not documented anywhere?

Gailly:

The hardware specifications for some video cards were kept as trade secrets. As a result, the XFree86 project couldn't support these cards. Increasing pressure from users who didn't buy those cards because they couldn't be supported has led the manufacturers to release the hardware specifications, and those cards are now well supported.

Similarly, I think that pressure from the open-source community can become strong enough to force companies to open their formats. We're not completely there yet, but I believe that the open-source model will win in the end. Even a giant like Microsoft starts considering Linux as a real threat.

10) Go and Compression
by Inquisiter

When I think of a game like go or chess, I think that each player develops there own algorithm to beat their opponent. If you agree, what relationships or similarities do you see between your intrest in Go and your intrest in compression?

Gailly:

What a nice question!

Even though the rules of go are very simple, the complexity of go is astonishing. The best go programs can be beaten by a human beginner. The search space in go is so large that is impossible to apply the techniques that are so successful in chess. Professional go players never evaluate all possible moves. They are able to compress an enormous amount of information into a relatively small number of concepts.

Where a human beginner would have to painfully examine many possibilities to realize that a certain group is doomed, and would most likely fail in the process, a go expert can immediately recognize certain shapes and can very quickly determine the status of a group. One gets stronger at the game by reaching higher levels of abstraction, which are in effect better compression ratios. A professional go player can elaborate concepts that an average player would have great difficulties to understand.

Current go programs are overwhelmed by the amount of information present in a game of go. They are unable to understand what is really going on. Since brute force techniques can't work in go, programs will only improve by compressing the available information down to a manageable level.

Joey Lawrance wrote to us with an updated announcement from the fine folks from Slackware with the news that the wait is over: slackware-current has been updated with the 2.2.14 kernel, XFree86 3.3.6, and a few minor fixes.' Kudos to Patrick Volkerding ^[?] and the Slackware team.