The Elegance of Deflate
codersnotes.com
codersnotes.com
PK had to stop working on PKARC because of a C&D request from SEA. He wrote the first algos of PKZIP, which were on par with SEA ARC on compression (and with PKARC on speed), but weren't much better. (And have been deprecated since the 1990 if I'm not mistaken).
Then, the Japanese encoders started to rule the compression ratio (and had comparably reasonable compression times) - LHArc, LZAri, don't remember the rest of the names. LHArc or LHA (don't remember which), had basically the same scheme that PKZIP converged on, except it used adaptive arithmetic coding. PK replaced that with static huffman coding, trading a little compression for a lot of speed, and the format we now know and love as "zlib compression" was born (and quickly took the world by storm, being in a sweet spot of compression and speed).
There's another non-trivial thing that PKZIP had going for it - it put the directory at the end, which meant you could see the list of files in the archive without reading the entire archive! This sounds simple, but back then everyone adopted the tar-style "file header then data" appendable style, which meant that just listing the files inside a 300KB zip file (almost a whole floppy disk!) meant reading that entire floppy (30 seconds at least). PKZIP could do it in about 2 seconds.
Beginning and the end, which continues to bite us in the ass until today, where we regularly stumble over bugs when one part of a toolchain uses one entry and the rest the other.
The problem is, what happens if the two are different? This can be through accident or maliciously. If one tool uses the first and another uses the second, then you'll end up with different results, and it can be hard to figure out why they are different.
It's like a CD, where audio players interpret the CD different than CD-ROM players. Some anti-copying techniques tried to take advantage of this to produce un-rippable CDs. A problem, however, was that car CD players used CD-ROM drives, so these CDs weren't playable in those cars. (https://en.wikipedia.org/wiki/Compact_Disc_and_DVD_copy_prot... )
Or some HTTP header attacks based on duplicate headers. Let's say there's a firewall which allows only access requests for "Content-Type: text/plain". If the attacker includes the header twice, once as text/plain and the other as image/gif, then the firewall might only check the first while the back-end web server interprets the second. This is a silly example; I couldn't remember the real attacks which take advantage of the same mechanism.
Duplicate HTTP header vulnerabilities:
• https://bugzilla.mozilla.org/show_bug.cgi?id=376756
• https://splash.riverbed.com/thread/7772
If a spec is open for interpretation, you can be sure that some software gets it wrong.
I really don't care about HTTP headers or Reed-Salomon, as they are completely irrelevant to the Zip format designed in eighties for very specific purposes then (being fast on the floppy disk and 4 MHz 8088 processor, allowing to recover as much as possible from the floppy even after the floppy disk sector failure), I just claim, through the whole conversation here, that the Zip format is not a bad format for having a central directory and the metadata outside of it too, and I gave my arguments for that. NTFS also has some metadata on more than one place and it's an intentional design decision solving real problems: in Zip case allowing for fast access of the list of the files in the archive but also easy recovery of the single files when some part of the archive gets corrupted.
I also claim that the Zip format is not in any way "bad" for not making impossible per the archive format design and specification of having the two identical file names in the archive. I can even imagine use cases where exactly allowing that is/was beneficial.
"Almost all programming can be viewed as an exercise in caching." —Terje Mathisen
The directory at the end was a fantastic cache as the seek times were unacceptably high. It's still worth maintaining for a lot of use cases. If you have a different use case where its nonexistence would make your life easier, fine, but that doesn't mean nobody needs it or that it's "wrong" to have it.
Your first argument was about the benefits of fixing data corruption, not about latency.
Duplication is a poor way to handle data corruption. If you really wanted to recover data robustly, there are better methods for error correction.
Yes, you are free make a new argument that there are other benefits to data duplication. Do be aware that the HTTP header duplication example I gave is not one of cache consistency, but the more general problem of data consistency.
Please tell me which format is better for recovering most of the files from the multifile archive if the corruption occurs somewhere (e.g. a small part of the whole archive file gets corrupted): the tar.gz or the Zip?
Which archive format would you use to be "better"? Is it widely used? What are its disadvantages?
For the same filesize as the zip you could transmit the tar.gz + a par2, which would be much better for recovery from such corruption.
But neither method you mentioned lets you recover your data if the data itself is corrupted.
If you really want to recover data, use something with error-correction, like Parchive. RAR 5.0's recovery record is another solution, also based on Reed-Solomon error correction codes.
Archive tools usually don't use those methods because performance and compression size are the prime reasons people use an archive system, not robustness to error. In large part because the storage and network protocols are so good that such errors rarely occur. Because they use error-correction codes.
I have another experience: If I've made a zip archive of a 1000 relatively same files, even if it's a few GB big, is if I'm left with a third of the archive I can easily recover first third of the files, if I have half of the archive, around the half of the files. Exactly because the common implementations of zip archivers would recognize that the directory at the end is missing but still allow me to extract everything that it can read, as they would use the data in front of every file, even with the fully missing "central directory".
If the corruption affects the file 3 of a 1000 files I can extract both the first two and all 4-1000. If the corruption is in the first 0.3 part of the tar.gz, most probably I won't be able to extract anything but the files 1 and 2. All the remaining 998 are then lost.
And listing the files inside of the non-corrupted ZIP archive, no matter how big, is effectively instantaneous, thanks to the same central directory. Try to list the files inside of a tar.gz which is a few GB big, then compare. ZIP is a very convenient format for fast access to the list of the files and to the single file in the archive, and still very convenient when the part of the archive is missing.
Edit, this is the response to your response: I've never ever mentioned Reed-Solomon, nowhere in the discussion. I've supported in my opinion good designing decision of Zip archives having the central directory and the metadata in front of the every compressed file and I just give some real-life examples of the corrupted files I've encountered and where I've had the best recovery ratio with the ZIP format. And I've never experienced the kind of "data mismatch" myself that you refer to. You are welcome to describe it more, I'd like to read how exactly you experienced it. If the answer is that you yourself wrote a program that ignored the full format of the Zip, or used such a bad library, then there is the real problem. Once again: "Almost all programming can be viewed as an exercise in caching." —Terje Mathisen
You asked about corruption, specifically when "a small part of the whole archive file gets corrupted". I addressed that point. I'm not going to cover all of the advantages and disadvantages between the two systems, because they are well-known and boring.
You of course must choose the method that matches your expected corruption methods. A incomplete write is a different failure mode than you wanted me to address. Reed-Solomon isn't designed for that. Other methods are, and they are often used in databases.
And you of course must choose a method which fits your access model.
Just like you would of course choose tar over zip if you want to preserve all of the filesystem metadata on a unix-based machine. Zip doesn't handle hard links, for example.
My point again is that data duplication causes well-known problems when there is a data mismatch, and while the duplication in zip as the result of its write-only/journalling format helps with some forms of error recovery, there are better methods for error recovery if that is your primary concern.
The concept of metadata redundancy isn't anything specific to the archives, the filesystems do it too, and it's always an engineering trade-off, and I consider the one in Zip format is a good one, based on the real-life examples I've given.
> Beginning and the end, which continues to bite us in the ass until today, where we regularly stumble over bugs when one part of a toolchain uses one entry and the rest the other.
Do you think creshal is mistaken?
Of course they are due to bugs in the toolchain. That's a natural consequence of the file format. That's the whole point of creshal's comment.
What do you think I'm trying to say, because I don't understand your responses based on what I thought I was trying to say.
See this article, for example:
http://www.intel.com/content/www/xr/ar/support/boards-and-ki...
The file it references can be downloaded here:
https://downloadcenter.intel.com/download/8375/Logo-Update-U...
...and it's somewhat amazing that it contains the original LHA.EXE from 25 years ago:
LHA version 2.13 Copyright (c) Haruyasu Yoshizaki, 1988-91
=== <<< A High-Performance File-Compression Program >>> ======== 07/20/91 ===https://www-ssl.intel.com/content/www/xr/en/support/boards-a...
https://en.wikipedia.org/wiki/Phil_Katz
"SEA was attempting to retroactively declare the ARC file format to be closed and proprietary. Katz received positive publicity by releasing the APPNOTE.TXT specification, documenting the Zip file format, and declaring that the Zip file format would always be free for competing software to implement."
Reading the article, I was reminded of a nagging question I've had in the back of my mind for a bit.
The ASCII table was invented in the '70s, when the cost of disk storage was much higher than it is today. But it's a shared dictionary, a standard that we can all agree upon, something that's already on every computer.
The thing I've wondered about is whether there could be any advantage to creating new generations of shared dictionaries that are domain-specific, and much larger.
For example, in the specific (and over-simplified) case of transmitting large quantities of English text from a server to a client, you could reduce the amount of data sent over the wire if both parties shared a lookup table that contained the entire English dictionary. In that case, you wouldn't transmit a book as a collection of characters, but rather as a collection of words.
Furthermore, it would seem like you could apply the same traditional compression methods like what's described in the article to furthermore reduce the amount of data being sent. Rather than identifying repeating patterns of letters, you would identify repeating patterns of words.
Of course, the obvious drawback is that an English lookup table is useless for transmitting anything other than English text. But again, disk storage being as cheap as it is, I wonder if it wouldn't be such a monumental problem to store many domain-specific dictionaries.
Of course, you'd always want to keep the ASCII table as a fallback. Much in the same way that a conversation in sign language (ASL, specifically) is largely composed of hand gestures referring to words or concepts, but the language still includes the complete alphabet as a fallback.
The thing I don't understand well enough is whether modern compression already incorporates concepts that are similar enough such that a shared-word dictionary would be useless. It seems like the "LZXX" style of compression essentially includes a similar but dynamically-generated sort of dictionary at the beginning of the transmission, and subsequently refers to that in order to express the message itself. Would the gains of having enormous shared dictionaries cancel out the advantage of that approach, only in a much more "wasteful" way?
* The large data being transferred is almost never text; it's video, images, or audio which is already using advanced (sometimes lossy) compression * Even if it is text, it's probably in some document format or HTML which greatly complicates the shared dictionary scenario (and would require a separate dictionary for each format)
In reality even deflate is already doing what you propose, but it builds the dictionary dynamically and includes it with each message. The up side is its dictionary can find common phrases and patterns that wouldn't be in your fixed dictionary. As the size of the text becomes larger the dictionary becomes a smaller and smaller percentage of the total.
I've also noticed that some PDF generators include far, far more bloat than others, though I'm not sure why.
The appeal of this to me would be in the code golf style of approach of specifying the actual data. Apart from plain useful raw data, It would include a bare minimum VM that can be used to generate larger outputs from the data. More complex VMs would be permitted provided a reference implementation can be run on the Minimal VM. The code for the reference Implementation would, of course, be included in the one megabyte.
A program using the data could request
* raw bytes
* output from the VM given code and parameters (with perhaps a cycle limit to stop endless loop hangs)
* output from the VM given code and parameters specified at an index in the data.
* output from the VM given code and parameters specified at an index in the data plus user parameters.
The system would be stateless, the VM would only exist for the duration of the data generation call. The same parameters would always produce the same output.
I have doubts as to it's fundamental usefulness but it would certainly make a fun collaborative project at the very least.
- A patent from ibm for some previous dynamic dictionary [1]
- Brotli: 120kb predefined dictionary [2]
This historical correction does not alter the rest of your comment.
It does. The extreme of it is storing all information inside pi, as is done here: https://news.ycombinator.com/item?id=6698852. In the end the dictionary is so big that the indexes themselves start to be too big.
If you really had infinite space and immediate access to all digits, there actually could be some way to make it work, though.
The HPACK header compression used by HTTP2 has a static dictionary.
> The thing I don't understand well enough is whether modern compression already incorporates concepts that are similar enough such that a shared-word dictionary would be useless.
I believe this is generally the case.
However, I don't know the practical improvement obtained over the currently existing methods. This is a good project to investigate, I think. Even if text compression might not be important in the larger picture of data transmission on the web, this sounds interesting on its own merit.
The next step in improving a simple compression algorithm is to replace Huffman encoding with arithmetic/range encoding. Huffman encoding proceeds one bit at a time, treating everything as having a probability that's a power of 1/2. Arithmetic/range encoding uses more accurate probabilities and then packs them together, letting you save a fraction of a bit with every symbol. As an analogy, consider how to encode 3 decimal digits. You could spend 4 bits on each digit, and it would take 12 bits total. Or you could combine them into a single 10 bit number.
Edit: https://github.com/GaloisInc/pure-zlib?files=1. Beautiful they've done just the decompression! Challenge awaits
Did that in Java (2011) and the impl. was faster than the native one (party due to lack of proper customization of zlib from java code)
I'd strongly disagree with In many people's eyes compression was still synonymous with run-length encoding as arj was extremely popular to the point it was used to cure full stealth viruses (v512 for example). hard to provide references now but wiling to search some old bbs
Other than that - fairy nice/nostalgic article.
In LZ77/LZSS, it is basically the same, except the dictionary is not constructed explicitly but rather implicitly from the history. In both cases, you need to refer to Lempel and Ziv's proof that indeed, the codeword length converges to log_2 P(sequence), which is optimal by the Shannon Source Code Theorem.
I highly recommend Cover & Thomas book on information theory if you find that interesting and are not afraid of math. And Shannon's original 1949 paper ("A theory of communication") is surprisingly and exceptionally readable - though it doesn't cover LZ for obvious reasons.
I'll see if I can find the C&T book. Shannon's paper was part of the course material at uni, IIRC; at least I think I read it long ago.
It is important to remember what each compression algorithm is optimal for.
LZ77 and LZ78 are optimal for observable markov sources -- that is, sources in which given x recent consecutive outputs (where x is the markov order), the distribution of the next symbol is fixed. While this is rarely ever the case, it is reasonable to assume that e.g. English text is a 10-th order markov model (with respect to characters) or 3-rd order (with respect to words).
The source you described is NOT markov overall, although it might be markov in the tail (past the random blob). Asymptotically, of course, it is markov :)
Assuming no reset, over time the shorter codes fall out of use because the longer ones eventually include everything they represent, extended by all possibilities (with the more probable extensions getting shorter codes by virtue of appearing more often / earlier).
It must have taken some trial-and-error to make this sentence correct, since the number itself adds some letters.
Ok, some research showed me that the idea can probably be traced back to Schwartz & Kallick 1964 (can't find the text), popularized by TAOCP vol. 1...
I highly recommend that everybody go out and build an INFLATE implementation; it's a lot of fun.
Mine can be found at https://github.com/magcius/libt2/blob/master/t2_inflate.h
The deflate side seems a little more complex. I played with it while on vacation about a month ago, but stalled after doing the LZ77 and huffman table generation, because I really just wanted to learn on the LZ77 bits worked, and I don't actually have a project that needs it.
You can write the error handler code for a given function (which usually just resets some resources and returns an appropriate error value) in a single place, usually at the end, but jump to it from within any loop or structure within the function, as soon as you detect that the computation cannot proceed.
setjmp / longjmp is the natural extension of this mechanism to an entire library, as in a set of tightly coupled functions that are hopefully hidden behind a public API. I think it's a good design choice. If done properly it makes the code more readable, more easily maintainable, and more optimized for the most common execution path. I wouldn't avoid using those libraries just for that design choice.
My dream is something like the UX of Swift's exceptions (basically normal C error handling except for it does all the tedious pointer work for you) with the ability to tell the compiler to either implement the exceptions as return values or stack unwinds for a particular code path with the flick of a switch.
If they manage to implement zero-cost futures [1][2], maybe they will also implement sime kind of zero-cost error handling abstraction (either via exceptions, or via some other useful abstraction for that purpose).
I like Rust a lot. Zero costs is not a reason though; my reason is no GC and not as bad as C or C++.
The real cost is that exceptions force the compiler to be pessimistic and pedantically cope with exceptions everywhere. I really don't think there's much win at all, compared to that, in return values the compiler forces you to check. And if you skip the checking, that's a different kind of pain.
Checked exceptions is a different but related story. I think they're a fine idea in the small but appallingly bad in the large; when glueing together 30 different libraries with their own exception types, everything end up throwing anything, particularly when some higher level abstractions have been applied, like iterator streams or monads. Forced return code error checking like Rust's is isomorphic with checked exceptions. It is my biggest worry for the language.
That is, the problem isn't performance - the isomorphism shows that there is no necessary difference when rules are consistently applied - the problem is Java was a good demonstration the checked exceptions were misguided.
These alleviate a lot of what made Java's checked exceptions so unhelpful, so I don't think you can really conflate the two.
I think people got tired of using up their return values for error codes. And it is more efficient to use this style certainly than manually breaking out of each stack frame.
C is full of things like this which break abstractions -- it doesn't seem particularly odd to me. Though I do remember that it was one of the things at the end of C books that I didn't understand for a long time.
What's the downside?
It doesn't play well with C++ because destructors have to be run at the end of every scope, but that doesn't apply to C.
And I guess because it mutates globals, it is a bit confusing in a threaded context.
What globals?
It really needs to be in the core instruction set of x86 & ARM.