In other compression news, Apple open sourced their implementation of lzfse yesterday: 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.
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.)
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.
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.
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.
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 ?
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.
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.
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
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.
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.).
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!"
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 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.
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.
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.
The page says: "Enhanced Digital Downloads of the BBS Documentary series are planned. Please sign up here: sales@bbsdocumentary.com if you wish to be notified."
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.
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.
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?
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.
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.
> 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).
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.
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.
> 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.
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.
> 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.
> 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).
> 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.)
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.
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.
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.
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.
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.
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.
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).
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.
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.
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.
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.
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.
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.
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.
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.
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
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.
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.
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
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."
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.
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?
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.
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.
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.
> 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
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.
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.
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.