http://www.maximumcompression.com/compression_fun.php
A 24 byte file that uncompresses to 5 MB; another file with good compression under RAR but almost no compression under ZIP; and a compressed file that decompresses to itself.
https://bugs.launchpad.net/qemu/+bug/1462949
(I have a big collection of these, but most of the bugs have now been fixed in qemu)
There are people who take special interest in compression. The Hutter Prize would be a good place to find them. http://prize.hutter1.net/
It's a bit old now.
> Restrictions: Must run in <10 hours on a 2GHz P4 with 1GB RAM and 10GB free HD
I'd be interested to see what can happen without those restrictions.
If you did not have time limits you could exhaustively search through Pi looking for your data, then store just the offset into Pi.
Or if the offset got too large then Pi to the power of lots of random numbers. One of those numbers will, somewhere, have your data. But it's infeasible to search for it.
There is no universal compression algorithm, by the pigeonhole principle.
And your compression scheme won't work by the simple fact that the offset of where in Pi your data lies will, on average, take the same number of bits to store as the data itself. Ditto, with pi to the power of lots of random numbers, the offset and the power will, on average, take the same number of bits to store as the data itself.
It's a 1MB file that decompresses to 261 tredecillion bytes of "Hello, World".
No terribly clever stream manipulation; it's a perfectly normal gzip file, other than the size. The generation script is here: http://sprunge.us/VhFc, but see if you can figure it out without peeking.
Interestingly enough, it's not using up any memory, but it is hitting the disk at 55MB/s, so I'm guessing it's decompressing it to disk, and will eventually crash when it fills up my hard drive.
EDIT: It gave up after fifteen minutes. That's nice, now I don't have to reboot. There was about 2 gigabytes of stuff in my temp folder when I ran disk cleanup, don't know how much of that was gzip bomb output.
curl https://brage.info/hello | od -c | head -40But, no. There's a finite number of levels, and it blows up pretty quickly.
It should be possible to write an archive file that decompresses to a slightly different archive file. Say, the original archive file plus a zero byte. (Things get hairy because of the checksum in most archive file formats, but it still should be possible.)
Then a malicious party writes an archive file that decompresses to two slightly different archive files. And sets it up so that, say, 128 levels in iff you follow a specific path in said tree you get to the actual malicious content. You can't get to it unless you follow the specific path, and you can't find it unless you do substantially more than just naively decompressing files (as you won't be able to decompress 2129-1 files).