28 ms·
How are zlib, gzip and Zip related? (2013)
- digi_owl 10y agoThe 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).
- greglindahl 10y agoThe 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.
- digi_owl 10y agoNot 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?
- greglindahl 10y agoAh, 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.
- digi_owl 10y agoI 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.
- greglindahl 10y agoI 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.
- chickenbane 10y agoNot 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 http://i.imgur.com/VQLGJOL.gif
- dragontamer 10y agoI 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!
- kbenson 10y agoAnd 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é.
- sliverstorm 10y agoPlus his profile lists http://zlib.net http://zlib.net as his personal page
- bumbledraven 10y agoMark Adler is such a boss. Check out his answers to space questions on http://space.stackexchange.com/users/265/mark-adler http://space.stackexchange.com/users/265/mark-adler
- shagie 10y agoMy personal favorite Adler SE post is in code golf: http://codegolf.stackexchange.com/a/78901 http://codegolf.stackexchange.com/a/78901 - Compute the Adler-32 checksum
- sikhnerd 10y agoIt'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.
- mixmastamyk 10y agoThe accepted answer is often wrong (or obsolete) and grants a small number of points. The obsession with it on SO is a bit odd.
- ghayes 10y agoYeah I tend to think if another answer has double the points of an accepted answer, that answer should come first.
- dexterdog 10y agoPlus, 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.
- d0mine 10y agoIn the vast majority of cases the accepted answer is the most upvoted answer http://meta.stackexchange.com/questions/178439/can-we-exempt-downvoted-accepted-answers-from-getting-the-top-spot/189424#189424 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.
- coryfklein 10y agoOut of curiosity, why do you care whether the answer is marked as accepted?
- hatchoo 10y agoBecause it more likely that beginning programmers would jump straight and look for the "accepted answer".
- 404-universe 10y agoWhere do the other popular compression utilities (e.g. bzip2, xzip, lzma, 7zip) fit in to this?
- kbenson 10y agoHe covers all that, at least in passing. It's a fairly comprehensive rundown.
- TimMeade 10y agoAlmost 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.
- gopalv 10y agoThe 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.
- eln1 10y agoBeside 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-Systems-implementations http://encode.ru/threads/2078-List-of-Asymmetric-Numeral-Sys...
- rasz_pl 10y agogood video series straight from Google Developers https://www.youtube.com/watch?v=Eb7rzMxHyOk&list=PLOU2XLYxmsIJGErt5rrCqaSGTMyyqNt2H https://www.youtube.com/watch?v=Eb7rzMxHyOk&list=PLOU2XLYxms...
- minionslave 10y agoIt's kinda bad-ass when he said: you can use this text on Wikipedia, I'm the primary reference.
- agumonkey 10y agoBut did he won the putnam ?
- deleted 10y ago[deleted]
- Grue3 10y agoWikipedia mostly doesn't allow primary sources though. It needs to be corroborated by a reliable secondary source.
- 0xffff2 10y agoWhich 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.
- deleted 10y ago[deleted]
- MyNameIsFred 10y agoNo, his post on SO is a firsthand account, and is therefore an unreliable, primary source. Technically speaking; Nothing personal.
- danso 10y agoI 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.
- agumonkey 10y agoArchived link juste in case http://archive.is/SvUO5 http://archive.is/SvUO5
- duskwuff 10y agoThe 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.
- sigjuice 10y agoI appreciate your effort and sentiment, but it would be nice if the awful eyesores of ads were not plastered all over the page.
- cyphar 10y agoI'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.
- agumonkey 10y agoArchived link juste in case http://archive.is/SvUO5 http://archive.is/SvUO5
- the_common_man 10y agoOne 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 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.
- tobias3 10y agoZip files can be streamed. See for example https://developer.android.com/reference/java/util/zip/ZipInputStream.html 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.
- deleted 10y ago[deleted]
- pierrec 10y agoI 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.
- tobias3 10y agoInputStreams are not seekable (see https://developer.android.com/reference/java/io/InputStream.html 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.html https://users.cs.jmu.edu/buchhofp/forensics/formats/pkzip.ht...
- pierrec 10y agoOK, 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.
- kbenson 10y agoIt 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.
- bluedino 10y agoAfter 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 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.
- kbenson 10y agoYeah, 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/ http://dar.linux.free.fr/
- rdslw 10y agoWorth 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-still-much-more-common-than-tar-xz http://stackoverflow.com/questions/6493270/why-is-tar-gz-sti...
- ygra 10y agoDid you intend to link the answer, maybe?
- adontz 10y agoWhen 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
- SNACKeR99 10y agoAnd another one: you are not IN a traffic jam, you ARE the traffic jam.
- tdicola 10y agoWow a stackoverflow question that hasn't been closed or removed for some trivial reason--thought I'd never see something like that again.
- brianwawok 10y agoYou think stackoverflow has too many good questions being closed? If anything I think more could be closed.
- reitanqild 10y agoPossibly 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.
- Houshalter 10y agoTypically 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.
- hrnnnnnn 10y agoAlmost 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).
- throwanem 10y agoThat'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.
- pavanky 10y agoIt was pretty close. It had 4 close votes earlier in the day which seem to have disappeared now.
- virtualized 10y agoBut can he invert a binary tree and is he willing to relocate to San Francisco?
- brianwawok 10y agoNo he can't, so no offer for him.
- technofiend 10y agoMark can turn the whiteboard upside down, mic drop the marker and walk away.
- umanwizard 10y agoWhat does "invert a binary tree" mean?
- fred256 10y agoIt's a reference to https://twitter.com/mxcl/status/608682016205344768 https://twitter.com/mxcl/status/608682016205344768
- umanwizard 10y agoI 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.
- gkya 10y agoTho 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.
- chc 10y agoOther 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.
- FunctionalMan 10y agoIt'll be removed soon as "not a programming question."
- lpage 10y agoIn other compression news, Apple open sourced their implementation of lzfse yesterday: https://github.com/lzfse/lzfse https://github.com/lzfse/lzfse. It's based on a relatively new type of coding - asymmetric numeral systems. Huffman coding is only optimal if you consider one bit as the smallest unit of information. ANS (and more broadly, arithmetic coding) allows for fractional bits and gets closer to the Shannon limit. It's also simpler to implement than (real world) Huffman. 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.
- mayoff 10y agoStrange that Apple didn't publish it on https://github.com/apple 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.
- bch 10y agoQuestion 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 ?
- winterismute 10y agoMy 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.
- new_hackers 10y agoWhen Chuck Norris computes checksums, he uses Adler-32
- coryfklein 10y agoI 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
- hardwaresofton 10y agoIt 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.
- lunchables 10y agoReminds me of the very sad zip story: https://www.youtube.com/watch?v=_zvFeHtcxuA 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=dRap7uw9iWI