How are zlib, gzip and Zip related? (2013)(stackoverflow.com)
stackoverflow.com
How are zlib, gzip and Zip related? (2013)
http://stackoverflow.com/questions/20762094/how-are-zlib-gzip-and-zip-related-what-do-they-have-in-common-and-how-are-they/20765054#20765054
144 comments
History rewritten once again...
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...
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...
More compression news!: https://github.com/Cyan4973/zstd declared its format stable a couple days ago, getting a step towards 1.0. In the example there, it's a little denser than gzip -1 and a lot faster, and includes entropy encoding that uses finite state machines (and that I don't truly understand--maybe there's some similarity to lzfse there). It can look at your data and construct a static dictionary, which sounds cool for tasks like packing a bunch of 4kb database pages.
(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.)
(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.)
Strange that Apple didn't publish it on https://github.com/apple (which holds all of their open Swift repos).
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.
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.
There is an attempt to patent something ANS-related: http://cbloomrants.blogspot.com/2015/05/05-21-15-software-pa...
Question not about ANS, but patenting: Wouldn't it make more sense for Apple (or anybody) to actually patent it, and keep those patents, but make it open via licensing ? If there's patentable material and $developer passes on filing for it, doesn't that leave it open for poaching by $third_party ?
The patent is invalid if prior art exists,so publishing it is enough to avoid it being poached by others
But doesn't the patent office only look at previous patents when searching for prior art? Of course, other sources of prior art can be brought in as a defense, but it still may not stop someone from getting a patent initially and using it to harass financially weak opponents.
Lack of patent examiner familiarity with the industry, history, and the state of the art is traditionally considered a weak point in the system as a whole. Supposedly when writing the patent claims you're supposed to do a search to make sure you're not conflicting with other patents and that there is no prior art, but this is often used to word the patent in such a way to avoid the prior art from invalidating the patent, or use differences with the prior art as support for the uniqueness of the patent being applied for. Unfortunately, patent examiners are traditionally illequipped to accurately make an assessment, and the patent applicant is allowed to make adjustments to address the issues the patent examiner found. I remember there was work on getting patent examiners to be more familiar with the areas the patents they are examining/approving are for (technology, software, or business, for example), but I don't know where that stands today.
However, IANAPL and IANAPE.
However, IANAPL and IANAPE.
http://patents.stackexchange.com/ helps with this
Offtopic, but I wonder what do you intend to gain by writing "$word" instead of "a word".
As it ended up being posted, it really could have been "a <word>". During the course of producing it, it seemed like the entities involved might be confusing, and my first approach was to treat everything like a unique variable.
TLDR, made sense during composition, not w/ final product.
TLDR, made sense during composition, not w/ final product.
Apple tANS implementation was suboptimal - both from the quantization and symbol spread point of view: http://encode.ru/threads/2221-LZFSE-New-Apple-Data-Compressi...
The author of this post (Eric Biggers) has made corrections and one of them was already merged in lzfse github (the second would make it incompatible).
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
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
Interesting, but it is all spanish to me ... What are "fractional bits"?
Generally, a symbol of probability p contains lg(1/p) bits of information: 1 bit if p=1/2, 2 bits if p=1/4 etc.
In Huffman you directly assign a concrete bit sequence to every symbol - it is perfect if their probabilities are powers of 1/2, but generally is not true: requires approximations, leading to a suboptimal compression ratio.
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.
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.
This blog post [1] and its predecessor explaining Huffman Codes [2] was a very helpful guide for me.
[1] https://hbfs.wordpress.com/2011/11/01/fractional-bits-part-i... [2] https://hbfs.wordpress.com/2011/05/17/huffman-codes/
[1] https://hbfs.wordpress.com/2011/11/01/fractional-bits-part-i... [2] https://hbfs.wordpress.com/2011/05/17/huffman-codes/
I followed your link which leads me to rant a bit:
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.
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.
WWDC video talking about it:
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://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.
Those first two links should ideally have been included in the project's README. From a maintainer's perspective, "Google it" should never be acceptable.
Not only is this a great read, but the follow up for citations is replied with "I am the reference".
If this were reddit I'd post the hot fire gif. Eh, here it's anyway: http://i.imgur.com/VQLGJOL.gif
If this were reddit I'd post the hot fire gif. Eh, here it's anyway: http://i.imgur.com/VQLGJOL.gif
Neat how involved he still is this long after the initial work.
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
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
On the other hand he isn't making new zlib versions. There are a lot of patches posted on the mailing list going nowhere. Also there's a valgrind issue I reported that he ignored.
Reminds me of the time I took my friend to play D&D up in Lake Geneva with the Gygax family whom I had been gaming with for a bit.
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!"
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!"
I'd imagine the simplest answer would be "because Tolkien said so".
Citation?
The Jackson films don't count.
The Jackson films don't count.
http://tolkien.cro.net/dwarves/women.html has some references. Some of this is also apparently expanded on in the various things Christopher Tolkien has published.
I thought he was joking.
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!
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!
And then someone helpfully posted his wikipedia bio in a comment:
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é.
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é.
>> That's as close as you're gonna get to "primary source" folks!
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.
https://en.wikipedia.org/wiki/Phil_Katz
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.
https://en.wikipedia.org/wiki/Phil_Katz
I remember reading that the creators of the ARC format sued Phil Katz for essentially taking their original source code and rebranding it PKARC (with assembly optimizations). They claim [1] that Katz did essentially the same thing with PKZIP.
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.
[1] http://www.esva.net/~thom/philkatz.html
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.
[1] http://www.esva.net/~thom/philkatz.html
This is covered in the BBS Documentary[1]. A comparison of Phil Katz work showed he just renamed variables and moved things around. Phil rallied the BBS community to character assassinate Thom. The documentary is shot years later and Thom still breaks down and cries when talking about what happened. It is very sad.
[1] http://bbsdocumentary.com/
[1] http://bbsdocumentary.com/
Crazy how that documentary appears to be not for sale in any form and DVDs on Amazon go for $3xx. Am I missing something?
The page says: "Enhanced Digital Downloads of the BBS Documentary series are planned. Please sign up here: [email protected] if you wish to be notified."
But it appears to be on YouTube: https://www.youtube.com/playlist?list=PL2B9EF89CE228ED0A
But it appears to be on YouTube: https://www.youtube.com/playlist?list=PL2B9EF89CE228ED0A
Mark Adler is such a boss. Check out his answers to space questions on http://space.stackexchange.com/users/265/mark-adler
My personal favorite Adler SE post is in code golf: http://codegolf.stackexchange.com/a/78901 - Compute the Adler-32 checksum
Plus his profile lists http://zlib.net as his personal page
The list of methods looks exactly like this
https://users.cs.jmu.edu/buchhofp/forensics/formats/pkzip.ht...
https://users.cs.jmu.edu/buchhofp/forensics/formats/pkzip.ht...
It's annoyingly common how the OP doesn't mark this answer as accepted, or even acknowledge how amazing this answer is from one of the technology's creators -- instead just goes on to ask a followup.
The accepted answer is often wrong (or obsolete) and grants a small number of points. The obsession with it on SO is a bit odd.
Yeah I tend to think if another answer has double the points of an accepted answer, that answer should come first.
Plus, often there is a decent and accepted answer given quickly and then a much more complete answer given later on that is really the one that should be considered in the archive.
In the vast majority of cases the accepted answer is the most upvoted answer http://meta.stackexchange.com/questions/178439/can-we-exempt...
But then again: the most upvoted answer doesn't mean that it is the most correct (whatever it means) one. Though likely it is.
But then again: the most upvoted answer doesn't mean that it is the most correct (whatever it means) one. Though likely it is.
Out of curiosity, why do you care whether the answer is marked as accepted?
Because it more likely that beginning programmers would jump straight and look for the "accepted answer".
What mechanism would you suggest otherwise?
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?
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?
I'm no UX expert but maybe highlight the accepted answer and a different colored highlight for the top voted answer.
It seems like it wouldn't be that hard to create an indexed tar.gz format that's backwards compatible.
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.
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.
The tar.gz format is to combine a collection of files first as a single tar file and then compress the one file into gz. It's not compressing individual file and then combing the compressed files into a tar. Accessing the last file requires decompressing the whole archive. What you described is the zip format. Both zip and gz use the DEFLATE algorithm so there's no difference in compression. The difference is in how the files are packaged.
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.
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.
> It's not compressing individual file and then combing the compressed files into a tar. Accessing the last file requires decompressing the whole archive.
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).
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).
> The stream format works in blocks of up to 65k.
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.
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.
> Can you point to where in the gzip or DEFLATE spec having that stipulation?
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.
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.
See [1] for arbitrary block size during compression, [2] for the requirement of a decompressor to handle arbitrary block size.
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
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
> 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.
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.
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.
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.
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.
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.
> Tar cannot change the file format of .tar.gz. Otherwise, gzip -d won't work
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 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.
> 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.
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).
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).
[deleted]
> 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).
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.)
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.)
No, you can extract specific files from a tar archive. I believe it skips through the tar file object headers, which include file length, so it only has to read the headers. That said, there are problems with my proposal, as you pointed out elsewhere here.
One community that does use this technique (although the index is in a separate file) is the web archiving community's WARC file format. The Internet Archive Wayback Machine has ~ 13 petabytes of web archive stored that way, and you use it every time you look at a webpage in the Wayback. The file format is what you'd expect: each webpage is gzipped separately, the output is catted together, and the index stores the offset and length of each individual compressed webpage.
https://en.wikipedia.org/wiki/Web_ARChive
https://en.wikipedia.org/wiki/Web_ARChive
After writing one myself along with a guy on IRC who needed a 'quick way to access huge .tar files', I found one written in python: https://github.com/devsnd/tarindexer
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.
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.
Yeah, I almost wrote one myself in Perl a year or two ago. :)
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.
1: http://dar.linux.free.fr/
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.
1: http://dar.linux.free.fr/
If I recall correctly and it's been a while: The initial header is x bytes from the beginning of the file, or that you have to search for a known key string PKsomething. Then you have to go back and forth between that and the compressed data as you decompress. When compressing files you have to go back to the beginning of the zip file ( or disk1 in a multi disk archive) and update that table with the CRC info. Just was not practical for streaming for multiple reasons. Remember the original zip file format was created by phil in about 1987. I believe they just thought it easier to start over with a better design for gzip with the same compression algorithm.
That can't be the case anymore because I implemented a streaming function a few years back that sends an unlimited number of files as a zip, but builds the zip on the fly streaming it to the client. Maybe it works because I am not using compression (files in my case are all JPG and/or compressed video so there is little benefit). But my process definitely starts streaming the zip right away and has to pull URLs on the fly to create the zip file.
I'm pretty sure you were using the deflate stream format. There may be other formats (maybe with different magic numbers in the header) that have slightly different capabilities and needs.
This cannot be a 'true' zip file. The central directory is at the end of the zip file. It's made up of information that is needed for the decompression. So if you are streaming it, you cannot decompress until the entire file is reassembled.
You can definitely compose a zip file "on the fly" and stream it out. The central directory at the end of the zip file can be determined from all the content already streamed.
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.
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.
What the parent is saying is that the client has to buffer the entire zip file before they receive the index and can begin decompressing it. "Streaming compression" usually implies streaming decompression as well—importantly because a non-negligible use case for streaming compression is sending streams of compressed data that won't fit on the destination together with the decompressed copy; or sending continuous streams of compressed data that could never reach the end to be decompressed. What the parent is saying is that zip cannot work for these use-cases.
Yeah, the above is with an assumption that the archive is in deflate's stream format. I'm not sure off the top of my head how gzip's different levels relate to that, or what tar defaults to when compressing as the tar is created compared to a full file tar compress after it's created.
Worth reading answer about coolest kid on the block: xz compression algorithm (of lzma fame) plus tar.gz vs tar.xz scenarios/discussion.
http://stackoverflow.com/questions/6493270/why-is-tar-gz-sti...
http://stackoverflow.com/questions/6493270/why-is-tar-gz-sti...
Did you intend to link the answer, maybe?
The last few days i find myself wondering if there needs to be some kind of org set up to preserve this sort of info.
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).
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).
The Internet Archive has both curated and non-curated collections. Right now the Wayback Machine doesn't have any curation, but that doesn't mean it's going to stay that way.
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.
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.
Not quite.
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?
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?
Ah, now you want to talk about discovery! It so happens that I'm building a search engine for the Wayback Machine. But it's true that discovery for it is never going to be that great until the search engines that people commonly use index the Wayback, which is probably never.
I dunno why you seem to treat those as two separate issues.
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.
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.
I don't think they're separate issues, and I totally agree that they feed into each other. I'm just having a hard time figuring out what this HN discussion is about.
My father teaching me to type PKUNZIP on files that "ended with .zip" in the DOS shell (not long before the Norton Commander kind of GUI arrived to our computer) is one of my earliest memories as a toddler: I would ask him "What does it mean?" and he would simply not know. It was 1990 and I was 3 and a half I think. When I learned what it stood for it was kind of epic, for me.
It is rare to be able to have a question answered so completely and from such a first-hand source. This post is gold and tickles me in all the right places.
StackOverflow is sitting on a veritable treasure trove of knowledge.
StackOverflow is sitting on a veritable treasure trove of knowledge.
Reminds me of the very sad zip story:
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.
https://www.youtube.com/watch?v=dRap7uw9iWI
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.
https://www.youtube.com/watch?v=dRap7uw9iWI
Where do the other popular compression utilities (e.g. bzip2, xzip, lzma, 7zip) fit in to this?
The big picture is that there's a few compression algorithms.
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.
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.
Beside Huffman coding, there is also arithmetic/range coding and now is becoming widely used ANS coding - e.g. LZFSE (Apple), ZSTD (Facebook), VP10 (Google): http://encode.ru/threads/2078-List-of-Asymmetric-Numeral-Sys...
Almost every one as far as I know where based on the info-zip code by Mark Adler and Jean-loup Gailly. That was used as the base at the time for zip/unzip in linux, winzip, and gzip ultimately.
good video series straight from Google Developers https://www.youtube.com/watch?v=Eb7rzMxHyOk&list=PLOU2XLYxms...
He covers all that, at least in passing. It's a fairly comprehensive rundown.
One important difference in practice is that zip files needs to be saved to disk to be extracted. gzip files on the other hand can be stream unzipped i.e curl http://example.com/foo.tar.gz | tar zxvf - is possible but not with zip files. I am not sure if this is a limitation of the unzip tool. I would love to know if there is a work around to this.
Zip files can be streamed. See for example https://developer.android.com/reference/java/util/zip/ZipInp...
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.
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.
[deleted]
I wonder how their API degrades when the stream doesn't support seeking (as is often the case over HTTP, or like in gp's example of using pipes). The whole doc you linked to, and the feature of on-the-fly decompression, seems to assume that the stream is seekable.
InputStreams are not seekable (see https://developer.android.com/reference/java/io/InputStream.... ).
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...
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...
OK, makes sense. The headers at the end of the file are only required if you want to extract specific files out of order. Love the clarity of that spec, btw.
You can't do that with a .zip file because the file header information is actually at the end of the file. You could work around that by sending the header first, though.
You can't put the header first. It is an intentional feature of .zip that the header is at the end so you can update a large zip file by just appending a new header to the end. That way the entire file does not have to be rewritten. Just read the old header, append new files, append new header. This was important back in floppy disk days
>> Just read the old header, append new files, append new header. This was important back in floppy disk days
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.
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.
Don't forget 'overwrite old header'
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.
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.
Having written code to extract files from a ZIP file, it's because the header is variable sized, anywhere from 22 to 65,557 bytes in size (22 bytes fixed, up to 65,535 bytes for a comment). There are two ways to scan for the header, one is to seek just 22 bytes shy of the end of the file and start checking backwards (since the majority of ZIPs I've encountered do not have the comment) or, seek 65,557 bytes from the end and scan forward.
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.
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.
then you wrote a bad extractor. Scanning forward is against the format. Zipping up a zip file is a perfectly valid thing to do. If the inner zip is stored uncompressed you'll have 2 headers at the end. If you scan forward you'll fail.
Why not? Isn't the purpose of a file compressor to squeeze file sizes down?
You don't have to overwrite the old header. Concat any zip files you want and feed them to conforming deconpressors and they correctly extract only the last headers files.
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
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
To clarify: if it's HTTP, you can request the end of file "header" first if the server supports the `Range` HTTP header (many servers support this when it's appropriate). So it's not doable by simple bash-style piping, but a dedicated tool can request the required bytes in the correct order.
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...
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...
In fact .zip file contains file header information twice: before every compressed file (local file header) and at the end of the .zip file (central directory). It's possible to omit file size in local file header, but most most compressing utilities doesn't use this option. So most .zip files could be extracted without seeking to the end.
How do you send the header first? Is that a feature of the http framework?
It'd be something you'd have to write yourself, of course.
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.
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.
Wow a stackoverflow question that hasn't been closed or removed for some trivial reason--thought I'd never see something like that again.
That's funny; it was on hold when I saw it last, a few hours ago. Apparently whoever happens to be around with mod powers decided to hate fun a little less than usual. I'm sure it won't last.
I feel Stack Overflow mods have to a least some degree a different purpose in the site than the average user. Far too many times, I find that the answers judged bad by mods or close-voted are the ones that ended up helping me. Isn't that the point?
It was pretty close. It had 4 close votes earlier in the day which seem to have disappeared now.
Stackoverflow current objective is to answer precise technical questions related to programming. Open ended questions are generally frowned upon because they tend to be argumentative and generate debate, which SO is not well equipped to deal with. In the very beginnings of stackoverflow, the goals weren't as clearly defined and because of the overwhelming need for such a place, it quickly became flooded with any question related to computers. This is why serverfault and superuser were created along clearer rules regarding their respective content.
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 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.
You think stackoverflow has too many good questions being closed? If anything I think more could be closed.
Typically when an interesting stackoverflow thread is linked on HN, it's closed. I don't know why this is. But it gives a very bad impression of the site's moderators.
Almost every link I follow from Google to SO results in a "closed as offtopic" question.
Usually the question has the exact answer I was looking for (I guess that's why its pagerank is high).
Usually the question has the exact answer I was looking for (I guess that's why its pagerank is high).
Possibly more bad questions could be closed but more importantly SO could learn to stop trying to close good questions because of technicalities.
I guess this would take a massive effort and would have to include a rewrite of the rules if SO.
I guess this would take a massive effort and would have to include a rewrite of the rules if SO.
It's kinda bad-ass when he said: you can use this text on Wikipedia, I'm the primary reference.
I wonder if that's a bit of snark about how, if he were to actually edit the Wikipedia entry on the topic, his edits would be removed because of Wikipedia's policies on primary sources contributing to an entry.
Wikipedia mostly doesn't allow primary sources though. It needs to be corroborated by a reliable secondary source.
Which is why he actually said it could be cited:
>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.
>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.
[deleted]
No, his post on SO is a firsthand account, and is therefore an unreliable, primary source. Technically speaking; Nothing personal.
I love the discussion in the comments:
> 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
> 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
But can he invert a binary tree and is he willing to relocate to San Francisco?
We detached this subthread from https://news.ycombinator.com/item?id=11924944 and marked it off-topic.
No he can't, so no offer for him.
Mark can turn the whiteboard upside down, mic drop the marker and walk away.
Who does this refer to?
We are going to need that for our middle out compression algorithm.
What does "invert a binary tree" mean?
It's a reference to https://twitter.com/mxcl/status/608682016205344768
I know the reference and I saw the discussion around it when it came out. I still don't understand what "invert a binary tree" means.
Tho honestly homebrew is nothing more than a popular but sub-par solution to a wide-spread problem (my impression from the literature, I never used it), so having it written does not qualify him as a good dev. I'd certainly interview him and test somehow, tho I don't value algorithmic knowledge all that much, especially in the web dev sector.
Other people have explained the reference, but as for what it means: AFAIK it basically means to produce a binary tree with the same values but with parent-child relationships reversed.
So, each child will have two parents? And there will be several roots? This doesn't make sense.
It means take a binary tree and invert it. On a white board. You have 20 minutes otherwise we're not interested :)
Edit: tough crowd
Edit: tough crowd
When I read "I am the reference" it reminded me of "I am the danger".
https://www.youtube.com/watch?v=3v_zlyHgazs
https://www.youtube.com/watch?v=3v_zlyHgazs
And another one: you are not IN a traffic jam, you ARE the traffic jam.
When Chuck Norris computes checksums, he uses Adler-32
Archived link juste in case http://archive.is/SvUO5
I appreciate your effort and sentiment, but it would be nice if the awful eyesores of ads were not plastered all over the page.
I'm confused. The only adds in the Internet Archive are the ones from the original page. Either you're getting MITM'd by someone who's injecting ads, or your ad blocker doesn't deal with archived links so well.
The post is over two years old and has a score of +892 (easily in the top 0.1% of posts). It's not going anywhere.
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.