How are zlib, gzip and Zip related? (2013)
stackoverflow.com
stackoverflow.com
Unfortunately, most open source implementations of ANS are not highly optimized and quite division heavy, so they lag on speed benchmarks. Apple's implementation looks pretty good (they're using it in OS X, err, macOS, and iOS) and there's some promising academic work being done on better implementations (optimizing Huffman for x86, ARM, and FPGA is a pretty well studied problem). The compression story is still being written.
Also, to clarify, ANS is relatively new (2009) but arithmetic coding has been around for a long time. Historically it was avoided because of patents, many (all?) of which have now expired. Apparently ANS isn't going to be patented.
However, IANAPL and IANAPE.
TLDR, made sense during composition, not w/ final product.
LZFSE has been out since one year. Not one mention on wikipedia. The repo lacks a good description what lzfse is. It also contains a LZVN encoder/decoder. The only information I found about it is some blog where someone seems to reverse engineer it for some hackintosh purposes.
I know documenting and presenting the case why people should use your software/file format can be annoying to do, but it's really important.
https://developer.apple.com/videos/play/wwdc2015/712/
Apple's docs:
https://developer.apple.com/library/mac/documentation/Perfor...
Generic info on finite state entropy compression:
http://fastcompression.blogspot.com/2013/12/finite-state-ent...
The last link was submitted to HN:
https://news.ycombinator.com/item?id=7040951
The repo's README seems pretty clear. Google provides the rest. Not really sure how much more there is to say about a reference compression algorithm.
(https://github.com/google/gipfeli is another compressor aiming at that general space ('fast but not Snappy/LZ4 fast'), but I don't think it caught on much.)
There is a paper about FPGA implementation of tANS encoder ( ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=7306068 ), but it uses branch which is removed in more recent implementations (bottom of the first post of http://encode.ru/threads/2078-List-of-Asymmetric-Numeral-Sys... ).
It is worth to mention that rANS variant - using one multiplication per symbol (e.g. in Google VP10), has recently exceeded the speed of tANS/FSE: https://github.com/jkbonfield/rans_static
Apple's fse implementation is based on an open-source work from an individual which predates lzfse by about ~20 months.
https://github.com/Cyan4973/FiniteStateEntropy
It's even less optimized than the original one, due to a few errors that slipped through during lzfse conception.
http://encode.ru/threads/2221-LZFSE-New-Apple-Data-Compressi...
[1] https://hbfs.wordpress.com/2011/11/01/fractional-bits-part-i... [2] https://hbfs.wordpress.com/2011/05/17/huffman-codes/
Accurate entropy coders like arithmetic/range coding or ANS family can directly work on symbols of general probabilities: containing a non-integer number of bits. It has to finally produce complete bits - their fractional number is handled by the state of the coder - kind of a buffer containing a fractional number of bits. Complete bits are produced as soon as they accumulate.
If this were reddit I'd post the hot fire gif. Eh, here it's anyway: http://i.imgur.com/VQLGJOL.gif
Then I read the name: Adler: as in Adler-32 (the checksum function that zlib uses).
Then I knew it was real. The darn author of zlib answered the question. That's as close as you're gonna get to "primary source" folks!
FYI: Mark Adler is an American software engineer, and has been heavily involved in space exploration. He is best known for his work in the field of data compression as the author of the Adler-32 checksum function, and a co-author of the zlib compression library and gzip. He has contributed to Info-ZIP, and has participated in developing the Portable Network Graphics (PNG) image format. Adler was also the Spirit Cruise Mission Manager for the Mars Exploration Rover mission. (wikipedia)
That's quite a résumé.
Yes it is. Whenever I think of PKzip I am reminded of the sad tale of Phil Katz death - partly because I share his first and last initials, and now reading his Wikipedia page I see we had more in common. Fortunately alcoholism is not my thing.
Can anyone verify these claims? I always thought it was an injustice that the original authors were treated poorly by the BBS community and treated like a big company despite just being run from home.
But it appears to be on YouTube: https://www.youtube.com/playlist?list=PL2B9EF89CE228ED0A
When brotli came out he implemented his own decoder (https://github.com/madler/brotli/) to check the spec, and got some things clarified in RFC. Brotli is pretty DEFLATE-y in spirit, with changes that take advantage of today's hardware (larger history window, contexts in the entropy encoding) and a bunch of tweaks (different match encoding, static dictionary, etc.).
Also, as others mention, NASA mission engineer: https://en.wikipedia.org/wiki/Mark_Adler#Mars_exploration
https://users.cs.jmu.edu/buchhofp/forensics/formats/pkzip.ht...
He ended up getting into an argument with Gary about why dwarven women would have beards (of all things). I remember having to kick him under the table and quickly whisper "This is Gary Gygax, he made the game. If he says they have beards they have beards!"
The Jackson films don't count.
But then again: the most upvoted answer doesn't mean that it is the most correct (whatever it means) one. Though likely it is.
For example, suppose I ask a question, and within 10 minutes get an answer which is good enough for me, then I accept it and move on.
Hours later, someone gives a much better answer. What is my obligation to track the topic after I already know a correct answer? What should be the mechanism to override my acceptance?
What is more achievable: putting that mechanism in place, or getting beginning programmers to look at the first answer rather than looking for the accepted one?
To which I'll add, I'm looking at it in privacy mode (not logged in), and can't tell which is accepted. Is that something that only people with an account can see? If so, aren't those also people who are now no longer beginner SO users?
One way would be to use the last file in the tar as the index, and as files are added, you can remove the index, append the new file, append some basic file metadata and the compressed offset (maybe of the deflate chunk) into the index, update the index size in bytes in a small footer at the end of the index, and append to the compressed tar (add).
You can retrieve the index by starting at the end of the compressed archive, and reading backwards until you find a deflate header (at most 65k plus a few more bytes, since that's the size of a deflate chunk), If it's an indexed tar, the last file will be the index, and the end of the index will be a footer with the index size (so you know the maximum you'll need to seek back from the end). This isn't extremely efficient, but it is limited in scope, and helped by knowing the index size.
You could verify the index by checking some or all of the reported file byte offsets. Worst case scenario is small files with one or more per deflate chunk, and you would have to visit each chunk. This makes the worst case scenario equivalent to listing files an un-indexed tar.gz, plus the overhead of locating and reading the index (relatively small).
Uncompressing the archive as a regular tar.gz would result in a normal operation, with an additional file (the index) included.
I imagine this isn't popular is not because it hasn't been done, but because most people don't really need an index.
He ended up doing the smart thing and changing his archiving program to not use .tar files, which solved all of his problems, but for the 2TB of data he already had this worked rather well.
I was going for maximal tar compatibility, graceful fallback, low impact file additions, and the ability to add an index after the tar is created without rewriting it all. That's what I came up with off the top of my head.
I did just search for indexed tar though, and it came up with dar[1], which I had heard of, but completely forgotten about.
The only wrinkle is that each entry has a header which typically states the compressed size and checksum. Either you have to compress each entry content in some temp buffer or file to figure out the compressed size and checksum, then write out the header and compressed content. Or you write out the header with these fields zeroed, then compress the content on the fly and write it out, then write out a data descriptor with the compressed size and checksum.
Also gzip supports on-the-fly stream-based compression and decompression so anything requires jumping to the end to do reading and writing while compression/decompresion is no go.
Yes, that is the whole point of this discussion. This limitation causes problems for some.
> What you described is the zip format.
That is not the zip format. Zip is a collection of file objects with uncompressed headers which specify the metadata and size of the compressed individual file that follows. As such, you can easily scan through accessing the headers.
> Both zip and gz use the DEFLATE algorithm so there's no difference in compression. The difference is in how the files are packaged.
Create 1000 files with the content "foobarbaz". Create two archives, first by using zip and then by gzipping a tarball. They will not be comparable in size. A tar is basically concatenating the files together with headers between them. Compressing this allows the DEFLATE algorithm to work across a larger dataset, and thus more efficiently. The zip archive might actually be larger than the tar before compression.
The trade-off here is that you get better compression characteristics from compressing one large file, but you don't get easy access to individual portions of the compressed file easily.
> Also gzip supports on-the-fly stream-based compression and decompression so anything requires jumping to the end to do reading and writing while compression/decompresion is no go.
The stream format works in blocks of up to 65k. That's the reason I said to read the last 65k of the compressed file. That should be guaranteed to contain at least one full block, which if I understand correctly you should be able to uncompress by itself. If the end of the tar archive is an index, and the footer of the index specifies the size of the index, you know whether you got the whole index in that last gzip block, or whether you need to get one or more prior gzip blocks (you can probably make an educated guess based on the index size). Once you have the index, which specifies file names and by offsets of the compressed file of the block at which the file/header starts, you can fairly efficiently index into large compressed files (again, assuming 65k max gzip block size and the ability to treat blocks independently).
The benefit would be that since the index is just another file in the tar, you can uncompress the format from a plain tar command with no negative consequences besides an extra file being present (the index).
Can you point to where in the gzip or DEFLATE spec having that stipulation?
The gzip format doesn't store the compressed data length, nor the offset of the compressed data blobs. It just has the header and then the blobs of DEFLATE compressed data, one after another. That's why it's good for streaming.
Same thing with DEFLATE. It's just a series of arbitrary size compressed data blocks. With a dictionary upfront for dynamic Huffman and no dictionary for static Huffman. You read as much data as you can to decompress until encountering the ending Huffman symbol, where you arrive at the next block. The 65K limit is for non-compress type block, which is not useful in the scheme of things.
There's no well known magic signature bytes to search for a DEFLATE header.
You are correct, I was misreading the stream format. There's a mode in it that mentioned 65k of data, and I was misreading what I saw (rather badly, at that). That said, it looks like, since deflate duplicate string reduction portion (LZ77 in gzip) references a sequence of bytes in the prior 32k, you could make sure to read at least 32k prior to the point you want to start looking at, and that would be covered. Unfortunately, the location of the huffman table looks to be the sticking point. If it was one large block, that would be easy, read some of the front, but it's probably not as easy as that, depending on how tar adds files.
> The gzip format doesn't store the compressed data length, nor the offset of the compressed data blobs.
I wasn't expecting it to store the offset, but I was incorrectly interpreting that it had a max length, which meant you could likely find it with high assurance.
I'm going to look deeper into the specifics of the huffman table, where it can/must be within the block, and how tar handles adding files to a compressed archive (does it add another block, or extend the existing one?) and when compressing in general (does tar arbitrarily limit deflate stream block sizes?). I'm not super confident it's possible, otherwise I imagine someone would have done it.
The 32K back distance just limits how far back to use the duplicate data from the current cursor. It doesn't really limit the block size.
The last I looked, it's really difficult to find the boundary of a Huffman block since the Huffman alphabet code is not on 8-bit boundary. Walking the bits to find the end code symbol is basically decompressing the whole block.
Tar doesn't compress data. It just packages files into an archive. Gzip then applies compression on the resulting archive. Tar works well with gzip because both can stream data. It just pipes the archiving data to gzip for on the fly compression.
Adding an index table for file metadata at the end of the archive is a good idea, but then that's what zip does, so might as well use that. That's why we end up with two popular formats: gzip for streaming, zip for random access.
[1] https://www.w3.org/Graphics/PNG/RFC-1951#overview [2] https://www.w3.org/Graphics/PNG/RFC-1951#formatcompliance
Yes, which is a problem because the huffman encoding tree is at the begiing of the block (I believe). except for that, for LZ77 I believe it doesn't really matter when the block begins, because the deduplication is based on prior occurrences (within 32k), so as long as you have that prior 32k, the relative distance to the original should be within the data you have.
> The last I looked, it's really difficult to find the boundary of a Huffman block since the Huffman alphabet code is not on 8-bit boundary. Walking the bits to find the end code symbol is basically decompressing the whole block.
Yes, which is why I was talking about how the gzipping is done (usually by tar itself), and how files are added. If it's all one big block, or blocks of set size, that would be useful to know.
> Tar doesn't compress data.
At one point that was true. Then they added flags to tar to allow tar to handle the compression at the same time. At this point, I would hazard most tar.gz files are compressed by tar itself using zlib.
> It just pipes the archiving data to gzip for on the fly compression.
Yes, but since it's all internal to the program, they have control oh how they do that. It's entirely possible (if somewhat unlikely) that tar by default compresses using a deflate stream and chunks it in specific maximum size blocks, or one large block. The question then is, when appending a file to a compressed archive through tar and letting it handle the compression steps, what does it look like? Is it an added deflate stream block (which seems easiest)?
> Adding an index table for file metadata at the end of the archive is a good idea, but then that's what zip does, so might as well use that. That's why we end up with two popular formats: gzip for streaming, zip for random access.
Well, I would say we ended up with two popular formats because tar preexisted zip be a decade, and tar works well with UNIX files while zip had some problems (initially). I'm not sure if zip files currently support some of the more esoteric UNIX file types (sockets, devices). I assume they worked that out when they got UNIX permissions working correctly. Unfortunately, since the headers are uncompressed, you end up with a bunch of separate compression chunks, which isn't efficient for lots of small files.
The archive.tar.gz means tar the files into archive.tar, then gzip it into archive.tar.gz. You can run gzip -d to get back archive.tar. Tar -czf is just a shortcut command.
Tar cannot change the file format of .tar.gz. Otherwise, gzip -d won't work.
That is very much implementation-dependent. BSD tar does not fork, it's provided by and compresses through libarchive, which depends on zlib for gzip support (although it may fallback to forking gzip if not linked against zlib).
I wasn't suggesting that tar changes the file format, but tar, if it was doing the compression through an API call utilizing the zlib library and not piping it through the gzip program would allow tar some extra control over how it chose to compress the archive. The point is moot, it's not calling an API, at least not in GNU tar.
> In the risk of dragging this too far, tar is just a command line front end to gzip. It just forks gzip in a child process to pipe data to it. No zlib is involved.
Yes, I've confirmed this for myself as well now, but that's not the only way it could have been done, which is why I was saying I wanted to take a look.
I often call zlib functions for in memory compression, It's not uncommon, so I thought it was worth looking into.
> The archive.tar.gz means tar the files into archive.tar, then gzip it into archive.tar.gz. You can run gzip -d to get back archive.tar. Tar -czf is just a shortcut command.
I'm well aware, but that doesn't mean there isn't some leeway in how a deflate stream is created. There are many eventual compressed outputs that can result from the same uncompressed input. For example, if you limited your deflate stream blocks to 65k (or whatever size), you would sacrifice a small amount of compression efficiency for the ability to (mostly) reliably discover the entire last block, and using that you could do what we've been talking about. Unfortunately, since it's not enforced by the protocol, you can't rely on it.
I still don't get how you can extract the index file from the tar.gz without uncompressing the whole gzipped archive first. Plus I believe you cannot extract a file from a tar archive without extracting all the files first (I could be wrong here.)
http://stackoverflow.com/questions/6493270/why-is-tar-gz-sti...
Right now it seems to be strewn across a myriad of blogs, forums and whatsnot that risk going poof. And even if the Internet Archive picks them up, it is anything but curated (unlike say wikipedia, even with all the warts).
However, in this situation, the collaboration between Wikipedia and the Wayback may be what you had in mind. We're working with Wikipedia to make sure all external links from Wikipedia articles are backed up in the Wayback Machine, and there's a Wikipedia bot going around adding these links to articles.
How easily would it be to find the linked to stackoverflow answer on the archive if ever stackoverflow were to vanish from the net one day?
There was also a wikipedia article linked on HN recently about a certain mainframe terminal, and a spreadsheet program that make use of a special capability of that terminal. Said article was at risk of being deleted from wikipedia because they deemed it "original research".
Again, how easily could one find such an article within the archive?
The way i see it, one feeds into the other. Wikipedia and other wikis have a repuration for being time/attention sinks, this because you can follow one article to another to another.
Search don't do that. It may or may not barf up what you are looking for if fed the right terms, not much beyond that.
Maybe what i have in mind is something akin to wikiquote but for topics rather than persons. So that this posting by Adler can be filed under zip, gzip, zlib and whatsnot, and people can find it to go alongside the "encyclopedic" description of either of the technologies.
StackOverflow is sitting on a veritable treasure trove of knowledge.
https://www.youtube.com/watch?v=_zvFeHtcxuA
The whole "The BBS Documentary" is great and I recommend starting at the beginning if you're interested in it.
Run Length Encoding
Huffman Encoding
Lempel Ziv (LZ77)
Burrows Wheeler Transform
The interesting part of all these specific implementations is their own specialized way of extending or combining these algorithms for their own niche (or tradeoff point).
Bzip2 is for example, compresses really well because BWT is expensive, but clever - rzip extends the LZ part of bzip2 to look further across the file (instead of a few hundred kb).
Zlib itself has enough of these flags exposed out, so all Zlib isn't really the same - Z_FILTERED, Z_HUFFMAN_ONLY, Z_FIXED, Z_RLE etc. Look at something like Zopfli to see how they can be remixed, provided the tradeoffs of CPU change from the historic positions of Zlib.
On the server side, read it and send it before the file. Maybe go through all your zips and copy the needed metadata to another location.
Don't forget 'overwrite old header'
Important for floppy disks in two ways, one because of space constraints and two, because of how slow floppies were.
Why? The new one will become the 'real' one since it will be at the end of the modified file. So it doesn't really matter if you delete the old one. If you're really trying to squeeze file sizes down, you could reference the old 'header' from the new one, so that you do not have to list the entire archive's contents again.
This fact has been used to construct pathological ZIP files where one tool will report one list of files and another tool will list a different set of files. That's why you really need to overwrite the old header.
If you didn't only look at the last header then you'd have the issue that I can store fake headers as uncompressed content (type 0) and your unzip util would screw up
I'm pretty sure I've used something similar, which was already implemented in the .NET framework. See their docs on constructing a ZipArchive object:
"If the underlying file or stream supports seeking, the files are read from the archive as they are requested. If the underlying file or stream does not support seeking, the entire archive is held in memory."
https://msdn.microsoft.com/en-us/library/system.io.compressi...
It even allows you to stream the zip while creating it, i.e. you do not need to know the compressed size of the files before starting to write the compressed file content.
You can also have a look at a zip file spec to see that they can be streamed: https://users.cs.jmu.edu/buchhofp/forensics/formats/pkzip.ht...
Usually the question has the exact answer I was looking for (I guess that's why its pagerank is high).
I guess this would take a massive effort and would have to include a rewrite of the rules if SO.
I am not sure why this question made it through, but "what do they have in common" generates a finite set of answers while "what are their differences" does not. The "real" place to ask such questions should be programmers.stackexchange.com. Unfortunately, it has 30 times less users and frankly, no one really cares about it. Moderators should use "Migrate question to [...]" instead of simply closing it.
I think everyone will agree that a question with 500 upvotes and 150k page views is interesting. The full problem is that SO has not managed to fit it anywhere.
>I am the reference, having been part of all of that. This post could be cited in Wikipedia as an original source.
His post on SO is the reliable secondary source.
> This post is packed with so much history and information that I feel like some citations need be added incase people try to reference this post as an information source. Though if this information is reflected somewhere with citations like Wikipedia, a link to such similar cited work would be appreciated. - ThorSummoner
> I am the reference, having been part of all of that. This post could be cited in Wikipedia as an original source. – Mark Adler
Edit: tough crowd