self-reproducing compressed file
Przemyslaw Brojewski
Is it, in theory, possible to produce a .zip file, which,
when decompressed with standard pkzip/winzip/unzip produces
an exact copy of itself?
I appreciate any pointers, if this "problem" has beed discussed before.
I couldn' find anything about it in the FAQ, nor in Google.
Przemyslaw Brojewski
DSCOTT
<bf3pco$ks2$1...@kujawiak.man.lodz.pl>:
>
>
>Is it, in theory, possible to produce a .zip file, which,
>when decompressed with standard pkzip/winzip/unzip produces
>an exact copy of itself?
>
>
My gut tells me this is not possible using standard
pkunzip and the like. But its not hard to write a short
file for some bijective compressor decompressor where this
is possible.
David A. Scott
--
My Crypto code
http://cryptography.org/cgi-bin/crypto.cgi/Misc/scott19u.zip
http://cryptography.org/cgi-bin/crypto.cgi/Misc/scott16u.zip
http://www.jim.com/jamesd/Kong/scott19u.zip old version
My Compression code http://bijective.dogma.net/
**TO EMAIL ME drop the roman "five" **
Disclaimer:I am in no way responsible for any of the statements
made in the above text. For all I know I might be drugged.
As a famous person once said "any cryptograhic
system is only as strong as its weakest link"
Colin Andrew Percival
> Is it, in theory, possible to produce a .zip file, which,
> when decompressed with standard pkzip/winzip/unzip produces
> an exact copy of itself?
I suspect not. When files can't be compressed much, *zip just stores the
file "raw" with a header appended; for this reason, I'd be surprised if
there were any files which compressed to a file of the same size, let alone
the same file.
Colin Percival
DSCOTT
<bf4efb$so3$1...@morgoth.sfu.ca>:
I think you didn't read what he wrote. He didn't say that he
file was created by *zip during a compression. His only concern
was can one "produce a .zip file" which on some standard zip
DECOMPRESSION produce an exact copy of itself. It of no concern
that zip product may deduce compression a waste of time. Also many
zip type of programs are such that various compression options
can be overridden. That said I am not sure such a file exists
with standard zip products that would do what he wants. I do
know that many bijective products do meet what he wants.
KLinZ
> It of no concern
> that zip product may deduce compression a waste of time. Also many
> zip type of programs are such that various compression options
> can be overridden. That said I am not sure such a file exists
> with standard zip products that would do what he wants. I do
> know that many bijective products do meet what he wants.
What is all this fuzz about this bijective thingie? You seem to mention it a
lot in really strange contexts :-)
DSCOTT
<aelRa.17117$KF1.303637@amstwist00>:
Why did the scropion sting the frog?
DSCOTT
<bf5m7c$dnn$1...@hermes.castel.nl>:
>DSCOTT wrote:
>> kl...@NOSPAMzenobitsSPAMNO.com (KLinZ) wrote in
>> <aelRa.17117$KF1.303637@amstwist00>:
>>
>>> DSCOTT wrote:
>>>
>>>> It of no concern
>>>> that zip product may deduce compression a waste of time. Also many
>>>> zip type of programs are such that various compression options
>>>> can be overridden. That said I am not sure such a file exists
>>>> with standard zip products that would do what he wants. I do
>>>> know that many bijective products do meet what he wants.
>>>
>>> What is all this fuzz about this bijective thingie? You seem to
>>> mention it a lot in really strange contexts :-)
>>
>> Why did the scropion sting the frog?
>
>I don't know.
>
Well when you find out the anwser to both questions are the same.
KLinZ
>>>> What is all this fuzz about this bijective thingie? You seem to
>>>> mention it a lot in really strange contexts :-)
>>>
>>> Why did the scropion sting the frog?
>>
>> I don't know.
>>
>
> Well when you find out the anwser to both questions are the same.
So you don't know why you post it?
DSCOTT
<bf6f32$4n0$1...@hermes.castel.nl>:
I know the anwser I just wanted you to think about it.
Phil Frisbie, Jr.
> Why did the scropion sting the frog?
He might be a little young to understand that one.....Or his native country
might not pass that story along.
> David A. Scott
--
Phil Frisbie, Jr.
Hawk Software
http://www.hawksoft.com
Stuart Caie
>>>>What is all this fuzz about this bijective thingie? You seem to
>>>>mention it a lot in really strange contexts :-)
>>>
>>> Why did the scropion sting the frog?
>>
>>I don't know.
> Well when you find out the anwser to both questions are the same.
You keep mentioning bijective compression because you're a sadistic bastard
who'd gladly die today if you could be sure of taking the life of an
innocent with you?
That's a somewhat odd life philosophy.
Regards
Stuart
DSCOTT
<3f16e073$0$11379$cc9e...@news.dial.pipex.com>:
I guess though its not how I would have worded it. You
did understand the questions. But I am not infected with
that particular form of software brain disease. Which
causes fools to take there lies along with the lives of
the innocent. But since millions of weak feebled brained
people are. I can see where one could make that mistake.
KLinZ
> DSCOTT wrote:
>
>> Why did the scropion sting the frog?
>
> He might be a little young to understand that one.....Or his native
> country might not pass that story along.
>
Yes, the latter. Or maybe both. Tell me about it. I like ancient stories.
Phil Frisbie, Jr.
The Frog and the Scorpion
A frog and a scorpion both found themselves at the bank of a river. The scorpion
turned to the frog and said "Mr. Frog I cannot swim. Could you please carry me
across the river on your back?"
The frog replied "Mr. Scorpion, if I carry you on my back you will sting me."
The Scorpion replied "Mr. Frog if I sting you we will both drown, why would I do
that? Please carry me across, I will not sting you."
With that the frog consented. The scorpion climbed on his back and they began
their trip across the river. About halfway across the river, the frog felt the
scorpion sting him.
"Why did you sting me Mr. Scorpion?" asked the frog "Now we will both die!"
The scorpion replied "I couldn't help myself, it is my nature to sting."
DSCOTT
<7DWRa.2968$dk4.1...@typhoon.sonic.net>:
I could not write it better than you did.
Phil Frisbie, Jr.
> ph...@hawksoft.com (Phil Frisbie, Jr.) wrote in
> <7DWRa.2968$dk4.1...@typhoon.sonic.net>:
> I could not write it better than you did.
Two minutes on Google to find the one I remembered, then cut'n paste ;)
> David A. Scott
Raymond Wan
On Wed, 16 Jul 2003, Przemyslaw Brojewski wrote:
> Is it, in theory, possible to produce a .zip file, which,
> when decompressed with standard pkzip/winzip/unzip produces
> an exact copy of itself?
Hi,
Based on how you worded it, I'm inclined to say "no", it is not
possible. At the very least, when you compress a file, it would add a few
header bytes identifying it to be a zip file. So, if you have a zip file
in a zip file, they will differ by at least the header bytes.
And if you next question was whether or not you can run "unzip" on
a file and it would go in an infinite loop decompressing it forever, then
the answer to that is also "no". Each time it decompresses, it would
remove the header byte, until it gets to something that is a non-zip file.
Ray
Robert Bonomi
Przemyslaw Brojewski
: On Wed, 16 Jul 2003, Przemyslaw Brojewski wrote:
:> Is it, in theory, possible to produce a .zip file, which,
:> when decompressed with standard pkzip/winzip/unzip produces
:> an exact copy of itself?
: Hi,
: Based on how you worded it, I'm inclined to say "no", it is not
: possible. At the very least, when you compress a file, it would add a few
: header bytes identifying it to be a zip file. So, if you have a zip file
: in a zip file, they will differ by at least the header bytes.
I have the odd feeling, that carefully crafted Huffman compressed
data might do wonders. But then again, I'm fairly ignorant, and that
algorithm may not have necessary powers of arithmetic coding.
And there are other obstacles: the presence of checksums, and other
algorithms are applied to the same data beforehand.
I think, the answer is "practically no", but the reason is not that
simple.
Przemyslaw Brojewski.
Raymond Wan
Hi,
On Mon, 21 Jul 2003, Przemyslaw Brojewski wrote:
> : On Wed, 16 Jul 2003, Przemyslaw Brojewski wrote:
> :> Is it, in theory, possible to produce a .zip file, which,
> :> when decompressed with standard pkzip/winzip/unzip produces
> :> an exact copy of itself?
> : Based on how you worded it, I'm inclined to say "no", it is not
> : possible. At the very least, when you compress a file, it would add a few
> : header bytes identifying it to be a zip file. So, if you have a zip file
> : in a zip file, they will differ by at least the header bytes.
> I have the odd feeling, that carefully crafted Huffman compressed
> data might do wonders. But then again, I'm fairly ignorant, and that
> algorithm may not have necessary powers of arithmetic coding.
> And there are other obstacles: the presence of checksums, and other
> algorithms are applied to the same data beforehand.
Your original question was not about *some* program that could be
made to satisfy the goal, but zip and its variants. A general compression
does not have to add header bytes, checksum, etc. and I think, it is
possible to create a compression program that does what you want. Well,
let's put it this way. How about the Unix program "cat" (DOS program
"type")? That program displays a text file to the screen -- it's not
really a compression program, but in a way, you could argue it is one that
offers an awful constant compression ratio of 8.0 bits per character.
And in this case, I can run it over and over again forever.
Could a program be made so that, when it decompresses a file, the
original file will be identical? Yes, sure -- especially if this was one
of your design goals...I'm sure you could always force yourself to do it.
But does the program (not algorithm -- but "zip" isn't an algorithm
anyway) zip, etc. do this? No...because of the header information, but
probably other things as well.
Ray
Przemyslaw Brojewski
: Hi,
: On Mon, 21 Jul 2003, Przemyslaw Brojewski wrote:
:> : On Wed, 16 Jul 2003, Przemyslaw Brojewski wrote:
:> :> Is it, in theory, possible to produce a .zip file, which,
:> :> when decompressed with standard pkzip/winzip/unzip produces
:> :> an exact copy of itself?
:> : Based on how you worded it, I'm inclined to say "no", it is not
:> : possible. At the very least, when you compress a file, it would add a few
:> : header bytes identifying it to be a zip file. So, if you have a zip file
:> : in a zip file, they will differ by at least the header bytes.
:> I have the odd feeling, that carefully crafted Huffman compressed
:> data might do wonders. But then again, I'm fairly ignorant, and that
:> algorithm may not have necessary powers of arithmetic coding.
:> And there are other obstacles: the presence of checksums, and other
:> algorithms are applied to the same data beforehand.
: Your original question was not about *some* program that could be
: made to satisfy the goal, but zip and its variants. A general compression
: does not have to add header bytes, checksum, etc. and I think, it is
: possible to create a compression program that does what you want. Well,
: let's put it this way. How about the Unix program "cat" (DOS program
: "type")? That program displays a text file to the screen -- it's not
: really a compression program, but in a way, you could argue it is one that
: offers an awful constant compression ratio of 8.0 bits per character.
: And in this case, I can run it over and over again forever.
The "cat" compression algorithm is way too simple. Consider a file that
contains few bytes of "header" and the compressed data. Now consider
decompressor that skips header bytes, and then decompresses data.
The result of decompression would be indentical to the original file.
In the simplest case, where content of the header is not important,
and you have a freedom of chosing compression algorithm, (just don't
cheat here) the task is fairly easy to implement. I believe I could do
it in a month, being totally new to the subject.
Now, zip imposes several limitations. The limited set of compression
algorithms, and header (and trailer, for that matter) that have to
be adjusted to the contents of compressed data.
In general, the presence of headers is just a nuisance. The fact,
that compressed data should contain its own CRC is a greater nuisance.
The only show-stopper would be lack of necessary power in the
compression/decompression algorithm.
Przemyslaw Brojewski.
Raymond Wan
Hi,
On Tue, 22 Jul 2003, Przemyslaw Brojewski wrote:
> The "cat" compression algorithm is way too simple. Consider a file that
> contains few bytes of "header" and the compressed data.
Ok, but the question was asked in the __context__ of zip (winzip,
pkzip, etc.). All of them insert a header which limits the number of
times you can decompress a file. Up to a point, it will stop and say the
compressed file is not a valid zip file. The LZ77 algorithm itself does
not specify a header. With some work, I'm sure any algorithm can be
implemented in such a way so that certain criteria, even "repeated
decompression", could be allowed.
In any case, you need to make a distinction between an algorithm
and a program which implements the algorithm. The answer to your question
is definitely "no" for the zip program for the reason (at least) of a
header. As for the LZ77 algorithm, I'm sure one could implement a
sliding-window-like algorithm which satisfies your requirement. In
programming terms, it's "just" an extra if statement.
As for your comment about "cat" being too simple, *if* we are
talking about the existence of an implementation of a compression program
that satisfies your requirement, "cat" proves that one could exist , and
that's what you wanted. Compression programs can reduce the size of a
file, or enlarge it -- so why can't it always return a constant
compression ratio of 8.0 bits per character? [Granted, I don't think such
a compression program would sell well! :-)]
> In the simplest case, where content of the header is not important,
> and you have a freedom of chosing compression algorithm, (just don't
> cheat here) the task is fairly easy to implement. I believe I could do
> it in a month, being totally new to the subject.
If you read my previous posting, I did say it could be done. But,
if you wish to satisfy your curiosity by implementing one, then go ahead.
> Now, zip imposes several limitations. The limited set of compression
> algorithms, and header (and trailer, for that matter) that have to
> be adjusted to the contents of compressed data.
zip is a program (well, ok, actually not; pkzip, winzip, etc. are
programs...we're sort of abusing the word "zip" here) and the algorithm it
uses is LZ77. I'm not sure where the "set" of compression algorithms
comes from, unless you include the Huffman coding used by the deflate
variant of the LZ77 algorithm.
> In general, the presence of headers is just a nuisance. The fact,
> that compressed data should contain its own CRC is a greater nuisance.
No, it isn't a nuisance. First, it allows someone to test the
file type by reading the first few bytes. In Unix, this would be the
"file" command. Secondly, it allows the program to return a useful
message. Instead of returning a simple "fail" message, it can return one
of two: "the compression format does not match" or "the compression
format matches, but the file is corrupt". If you're writing a compression
program for an embedded system with limited space, then yes, it's a waste.
If you have a gigabyte hard disk, I don't see if a few bytes would hurt in
making your program a bit more robust.
Granted, the question you proposed was kind of interesting and
might be worth playing with to satisfy your curiosity. However, I don't
think there's a point in claiming one program compresses better than
another just because one doesn't add header bytes to the file.
Ray
Przemyslaw Brojewski
: Hi,
: On Tue, 22 Jul 2003, Przemyslaw Brojewski wrote:
:> The "cat" compression algorithm is way too simple. Consider a file that
:> contains few bytes of "header" and the compressed data.
: Ok, but the question was asked in the __context__ of zip (winzip,
: pkzip, etc.). All of them insert a header which limits the number of
: times you can decompress a file. Up to a point, it will stop and say the
: compressed file is not a valid zip file.
Not, if decompressing data re-creates valid header and the compressed
data along with it. This is the essence of my original question.
And the "cat" algorithm isn't capable of doing such a thing, but it
doesn't imply other algorithms can't either. To narrow the problem to
the original context: Would algorithms used in zip files allow for
such a thing?
: In any case, you need to make a distinction between an algorithm
: and a program which implements the algorithm. The answer to your question
: is definitely "no" for the zip program for the reason (at least) of a
: header.
Oh, come on, next thing you will say that quines (a programs which, when
run, produce complete listing of their source code) are impossible.
The headers are "just" added difficulty level. Of course, they can
add so much as to making task comparable to brute-forcing strong crypto.
But my original question contained magic words: "in theory"
: zip is a program (well, ok, actually not; pkzip, winzip, etc. are
: programs...we're sort of abusing the word "zip" here) and the algorithm it
: uses is LZ77. I'm not sure where the "set" of compression algorithms
: comes from, unless you include the Huffman coding used by the deflate
: variant of the LZ77 algorithm.
The "set" comes from Appnotes.txt, freely accessible documentation
of pkzip etc archives. It mentions few different compression algorithms,
"cat" being one of them :), and some variation of Huffman coding being
another.
: Granted, the question you proposed was kind of interesting and
: might be worth playing with to satisfy your curiosity.
I'm glad to hear it. However, I do not demand that anybody
drops what they are doing and go satisfy me :)
: However, I don't
: think there's a point in claiming one program compresses better than
: another just because one doesn't add header bytes to the file.
Huh? Just what exactly made you think I ever claimed such a thing?
Cheers,
Przemyslaw Brojewski.
Raymond Wan
On Tue, 22 Jul 2003, Przemyslaw Brojewski wrote:
> Not, if decompressing data re-creates valid header and the compressed
> data along with it.
Asking such a question is the same as asking if compressing a file
"x" produces the same file "x". The answer is "no". Even if the file is
"incompressible" (and don't ask me to quantify what that means :) ), the
file would be expected to expand. Even if a zip header is not added,
other information is added, such as information about the alphabet used in
the original file, or in the case of zip, a command that says to do a
"literal copy / store".
> This is the essence of my original question.
> And the "cat" algorithm isn't capable of doing such a thing, but it
> doesn't imply other algorithms can't either. To narrow the problem to
The "cat" program produces a header of 0 bytes...it just so
happens that it is a header that is acceptable by the program.
> Oh, come on, next thing you will say that quines (a programs which, when
> run, produce complete listing of their source code) are impossible.
> The headers are "just" added difficulty level. Of course, they can
> add so much as to making task comparable to brute-forcing strong crypto.
> But my original question contained magic words: "in theory"
Despite your current posting, my answer is still a "no". You're
combining the word "zip" with the words "in theory", which is wrong. "zip"
is not a theory, but a theory (LZ77 or Deflate) put into practice. If
you're going to tweak "zip" to do something you want, it isn't "zip"
anymore, but a variant of the LZ77 algorithm. Put it this way, if you
changed a "zip" [de]compressor to support this functionality, do you think
Winzip or pkzip would be able to decompress it? No.
You're combining two separate issues. Can "zip" files have the
property you said -- no. But can a LZ77 algorith be tweaked to support
the property you said -- perhaps yes.
> : However, I don't
> : think there's a point in claiming one program compresses better than
> : another just because one doesn't add header bytes to the file.
> Huh? Just what exactly made you think I ever claimed such a thing?
The direction you were heading seemed to lead to this. If not,
then don't worry about it.
Ray
Przemyslaw Brojewski
I give up. I feel you are missing the point, but I am unable to
make it more clear to You. I'm sorry.
You state that is impossible to create a file which when decompressed
with standard *zip program produces exact copy of itself, because such
a file would have to contain a header. You imply that the header
cannot be reproduced in the process of decompressing data.
I don't buy it. For me the naswer is unknown. I don't know if it
is possible to craft such a compressed data, which upon decompression
would produce valid *zip header and the copy of itself. Maybe yes, maybe
not. You don't even comment on this issue, you consequently snipped it out
in your replies and drifted to modifying *zip executables and other
things I was never interested in.
Let's go busy ourselves with something different.
Przemyslaw Brojewski.
Raymond Wan
On Wed, 23 Jul 2003, Przemyslaw Brojewski wrote:
> I give up. I feel you are missing the point, but I am unable to
> make it more clear to You. I'm sorry.
Well, let's get at least one point clear. You posted a message
asking for other people's opinion. I gave mine. I'm sorry, but someone
else's opinion can support your's or it can be against; but if you ask for
it, you have to be prepared for both.
Now, if you were going to try your experiments regardless of what
other people said, then why ask for someone else's opinion -- just do it.
> You state that is impossible to create a file which when decompressed
> with standard *zip program produces exact copy of itself, because such
> a file would have to contain a header. You imply that the header
> cannot be reproduced in the process of decompressing data.
Suppose you're mailing a box of fragile cups to me as a present.
The cups are the present, so you put it in a box purchased from your local
post office to protect it and mail it off. Now, suppose the cups came
with a box from the store...a nice boxed set. I'll bet you're not going
to just mail that to me...you'll still buy a box or wrapping paper and
mail it off. A bit redundant since you're putting a box in a box, but
you'll still do it. Why? The outer box protects it. The inner box is
the present.
The header of a compressed file identifies certain things about
the file. It is, by definition, separate from the file. What you're
asking is, if it's possible that the header could serve two
purposes...both as a header, and as part of the compressed message. If
that were true, wouldn't that defeat the purpose of the header?? Suppose
now the box of cups was encased in yet another box. Two boxes for a set
of cups -- you'll still go to the post office and buy a third box,
wouldn't you? Because whatever's inside, no matter how many boxes there
are, is the present...you want to keep it separate from the harsh
treatment during transport so you'll add an outer box. For me, whatever I
receive from you, I'll take the outer box and throw it away...because I
*expect* that it protects whatever inside and does not form part of the
present.
> I don't buy it. For me the naswer is unknown. I don't know if it
If you don't buy it, then write a program and experiment on it.
I don't see the point in posting a question asking for help, when you
think you knew the answer and you were just waiting for someone to say
"good idea!".
> is possible to craft such a compressed data, which upon decompression
> would produce valid *zip header and the copy of itself. Maybe yes, maybe
> not. You don't even comment on this issue, you consequently snipped it out
> in your replies
If I mistakenly snipped it from my replies, I apologise. I
rectify that mistake by saying once and for all that (a) I don't believe
what you say is possible, based on the framework of standard zip file
formats and while I'm open to the possibility that it might work, (b) you
haven't succeeded in convincing me it is true.
So, please, go ahead and give your idea a try and post whatever
result you get on this newsgroup -- I would be interested in any result.
As a suggestion, in the future, if you have an idea and you were going to
implement it regardless of what others say, then just do it -- you
shouldn't need to wait for encouragement (or discouragement, I guess, in
this case) to start.
Ray
Phil Carmody
[SNIP - waffle about cups and saucers or something]
I see no intrinsic reason why there should be no length-1 cycles in the
action of any particular action upon the set of all files.
I see no reason why there shouldn't be two files, each of which
decompresses to form the other (a length-2 cycle).
I expect such things to be exceptionally rare, but for an existance
statement, you only need one. Given that there are an infinite number of
files, if such a coincidence can be shown to have any non-zero probability
then the wise money is on existance rather than not.
Header or no header, this is just a simple matter of group theory.
Maybe Floyd has something to say about it. (As in Floyd's cycle
finding algorithm, as used in Pollard/Brent Rho, et al.)
Phil
Raymond Wan
On Thu, 24 Jul 2003, Phil Carmody wrote:
> On Thu, 24 Jul 2003 05:06:06 +0000, Raymond Wan wrote:
> [SNIP - waffle about cups and saucers or something]
>
> I see no intrinsic reason why there should be no length-1 cycles in the
> action of any particular action upon the set of all files.
> I see no reason why there shouldn't be two files, each of which
> decompresses to form the other (a length-2 cycle).
>
> I expect such things to be exceptionally rare, but for an existance
> statement, you only need one. Given that there are an infinite number of
No, we aren't talking simply about the existance of a particular
case -- we're talking about the existance of a case within the confines of
a particular implementation, the zip file format.
Some compression methods don't add extra bytes around a compressed
message like zip does, to serve as meta-information. cat, for example, at
8.0 bpc. For those implementations, then yes, it's quite possible. But,
my money is still on "not possible" for a format that compresses a message
and then adds bytes of information to the front. But I'm open to the
possibility of being proved wrong.
Ray
Przemyslaw Brojewski
What you're
: asking is, if it's possible that the header could serve two
: purposes...both as a header, and as part of the compressed message.
No. That is certainly not what I was asking. The box in a box analogy
does not apply at all.
: If you don't buy it, then write a program and experiment on it.
: I don't see the point in posting a question asking for help, when you
: think you knew the answer and you were just waiting for someone to say
: "good idea!".
You are giving replies not to the question I have asked, but to
some other. We don't understand each other. The program I would have
to write would have the form of a valid zip archive, and the machine
executing the program would be the *zip archiver in decompressing mode.
:> is possible to craft such a compressed data, which upon decompression
:> would produce valid *zip header and the copy of itself. Maybe yes, maybe
:> not. You don't even comment on this issue, you consequently snipped it out
:> in your replies
: If I mistakenly snipped it from my replies, I apologise. I
: rectify that mistake by saying once and for all that (a) I don't believe
: what you say is possible, based on the framework of standard zip file
: formats and while I'm open to the possibility that it might work, (b) you
: haven't succeeded in convincing me it is true.
OK.
: So, please, go ahead and give your idea a try and post whatever
: result you get on this newsgroup -- I would be interested in any result.
: As a suggestion, in the future, if you have an idea and you were going to
: implement it regardless of what others say, then just do it -- you
: shouldn't need to wait for encouragement (or discouragement, I guess, in
: this case) to start.
I expected to get some pro and contras. I got one contra from you, but it
did not convince me.
Julien Oster
Hello Raymond,
> Some compression methods don't add extra bytes around a compressed
> message like zip does, to serve as meta-information. cat, for example, at
> 8.0 bpc. For those implementations, then yes, it's quite possible. But,
> my money is still on "not possible" for a format that compresses a message
> and then adds bytes of information to the front. But I'm open to the
> possibility of being proved wrong.
You still don't get his point.
The challenge is to achieve a ZIP file which "contains" itself. Of
course you can't achieve that by putting a ZIP within a ZIP within
another ZIP. The challenge is a mathematical one, you have to assemble
a ZIP file which somehow mathemagically builds up another ZIP file
(including headers and all other overhead) which by hazard looks
exactly the same.
With your argumentation, quines (as stated by someone else, quines are
programs which output their own sourcecode) would also be
impossible. Of course, in a conventional manner, it doesn't
work. Imagine doing it in C, you would end up with something like:
(consider it being K&R C, no prototypes needed, that way you save the
#include directive)
main() { printf("main () { printf(\"main() { printf(\\\"main() ...
ad infinitum.
The program can be seen analog to the compression problem: the "data"
is what's the argument to printf(), the "header" is the program logic
around it. Now, how would you establish a quine? Following your
argumentation, you can't, since the data the quine should actually
output would include the "header" (program code) which the quine
itself equally needs. It's basically the same problem!
However, quines are possible. This is an example of a quine in C:
char*f="char*f=%c%s%c;main(){printf(f,34,f,34,10);}%c";main(){printf(f,34,f,34,10);}
If you compile that bit and run it, it outputs the following:
char*f="char*f=%c%s%c;main(){printf(f,34,f,34,10);}%c";main(){printf(f,34,f,34,10);}
Amazing, isn't it? As you see, it's not that trivial, but it's
entirely possible.
The goal is now to achieve the same in ZIP: a ZIP file which outputs
(after unpacking) an exact copy of itself. Of course it would be a
*hack*, but that's the challenge!
The argument with your cups is invalid, since we are talking about
mathematics and computer science. As stated above, following your
argument with the cups quince would be equally impossible: the cups
would be the argument to printf, the packaging the code around it.
Look, you said the following:
> But, my money is still on "not possible" for a format that
> compresses a message and then adds bytes of information to the
> front.
Well, a quine does exactly that and suffers from exactly the same
problem: you have a message, the message that gets output, and extra
bytes of information not only added to the front, but most likely
(depending on the program language) also to the end of the
message. That extra bytes of information would in this case be the
actual program logic, in a ZIP it's header information, CRC, central
ZIP file directory and the like.
If you still believe that is impossible (without stating a valid,
mathematical proof) then you truly didn't understand what we're
talking about here.
Julien
Przemyslaw Brojewski
: On Thu, 24 Jul 2003 05:06:06 +0000, Raymond Wan wrote:
: [SNIP - waffle about cups and saucers or something]
: I see no intrinsic reason why there should be no length-1 cycles in the
: action of any particular action upon the set of all files.
: Header or no header, this is just a simple matter of group theory.
: Maybe Floyd has something to say about it. (As in Floyd's cycle
: finding algorithm, as used in Pollard/Brent Rho, et al.)
Thanks for the pointer. Simple matter of group theory you say :)
But do zip files together with decompression operation form a group?
Definitely not, as a result of decompression can be something other
than valid zip file. But there may be a subset of them that does.
Finding such a subset is not a simple matter, though.
Przemyslaw Brojewski.
Raymond Wan
Hello Julien,
On Thu, 24 Jul 2003, Julien Oster wrote:
> Raymond Wan <rw...@student.unimelb.edu.au> writes:
> The challenge is to achieve a ZIP file which "contains" itself. Of
> course you can't achieve that by putting a ZIP within a ZIP within
> another ZIP. The challenge is a mathematical one, you have to assemble
> a ZIP file which somehow mathemagically builds up another ZIP file
> (including headers and all other overhead) which by hazard looks
> exactly the same.
Well, first of all, a well worded argument from you. Thank you!
And secondly, no, of course I don't have proof of what I said. I'm
not going to give one for something I've always claimed to be only an
opinion. While your argument is very convincing, I still have my doubts,
and yes, perhaps I don't understand the original question.
Suppose we hacked file x so that it could decompress to y. Let's
assume x = y. If we could decompress x to y, wouldn't that mean that I
could compress y to x? It is this part which I've probably missed. So,
I can compress this file and get the same file? Now, if I compressed y 10
times, say, each time, I've tacked on some kind of header, but the size of
the file has remained constant -- does this mean that I'm repeatedly
compressing the "data" part of y?!?
I could easily believe this is all possible for a given
compression algorithm, and in this case, where group theory, mathematics,
and computer science would come into play. But, for a particular
implementation of an algorithm with a specified format, I'm hesitant to
say "yes, it's possible", even though that's the safe answer. I have
doubts that zip's variant of LZ77 combined with Huffman coding actually
allows it. And no, no proof. :)
> With your argumentation, quines (as stated by someone else, quines are
> programs which output their own sourcecode) would also be
> impossible.
...
> around it. Now, how would you establish a quine? Following your
> argumentation, you can't, since the data the quine should actually
> output would include the "header" (program code) which the quine
> itself equally needs. It's basically the same problem!
The quines example was nice, though. Thanks! :) It's a similar
problem -- I compile a C program and it outputs the same program. But,
you can't reverse the process. For some reason, I think ... and still
think, that if I can decompress a file to the same file, I ought to be
able to compress that file to get the same thing -- no? That would mean,
I could compress x to a size "h + z", where h is the size of the header
and z is x in compressed form; with x = h + z.
> If you still believe that is impossible (without stating a valid,
> mathematical proof) then you truly didn't understand what we're
> talking about here.
BTW, up until a few hours ago, there was no "we" in the discussion
... just the two of us, so your response was much appreciated. Well
crafted, and very close to making me a believer. :)
But, recent replies have at least shown me one thing, though.
The original post implied a request for an opinion, and I gave it since I
didn't see many other replies. If I had known that providing an opinion
contrary to the expected response would ruffle so many feathers --
especially from the person who asked for opinions in the first place, I
wouldn't have replied to the post in the first place -- appears to have
been a waste of time. There appears to be no room for opinions, even when
they are offered as opinions and not as fact (glad I didn't make that
mistake!). :-)
Ray
Phil Carmody
> Phil Carmody <thefatphi...@yahoo.co.uk> wrote:
> : On Thu, 24 Jul 2003 05:06:06 +0000, Raymond Wan wrote:
> : [SNIP - waffle about cups and saucers or something]
>
> : I see no intrinsic reason why there should be no length-1 cycles in the
> : action of any particular action upon the set of all files.
^^^
> : Header or no header, this is just a simple matter of group theory.
> : Maybe Floyd has something to say about it. (As in Floyd's cycle
> : finding algorithm, as used in Pollard/Brent Rho, et al.)
>
> Thanks for the pointer. Simple matter of group theory you say :)
> But do zip files together with decompression operation form a group?
Nope. Notice the use of the word "set" above. Also note that a group
operation is a binary operation, and compression isn't a binary
operation. I was thinking of the group of actions on the set.
These actions, however, might well form a group under composition.
> Definitely not, as a result of decompression can be something other
> than valid zip file. But there may be a subset of them that does.
> Finding such a subset is not a simple matter, though.
I think it would be easier to find an example using a stream compressor
such as gzip (which does add a header, it's not the header that's the
problem) rather than a file compressor, as the length field really
throws you in a spin.
Phil
Vedat Hallac
> ... snip ...
Congratulations. A very well written description, indeed. It got me
thinking, from your example of the infinite program, "compressed" down to
a finite one with the trick of a substitution. I wonder whether the
substitution operation is a necessary requirement for constructing quines.
If that is so, can we safely say that LZ compressors *may* be used to
construct a quine, but not huffman encoding? My memory on arithmetic
encoding tricks me at the time, so I'll ignore its existence for this
post. :-)
Dale King
kl...@NOSPAMzenobitsSPAMNO.com says...
> DSCOTT wrote:
>
> > It of no concern
> > that zip product may deduce compression a waste of time. Also many
> > zip type of programs are such that various compression options
> > can be overridden. That said I am not sure such a file exists
> > with standard zip products that would do what he wants. I do
> > know that many bijective products do meet what he wants.
>
> What is all this fuzz about this bijective thingie? You seem to mention it a
> lot in really strange contexts :-)
To avoid repetition see the Bijective Compresion Poll thread.
--
Dale King
Camping Gaz
> For some reason, I think ... and still
> think, that if I can decompress a file to the same file, I ought to be
> able to compress that file to get the same thing -- no?
No, and listen. In our particular case there can be :
- several compressors complying with zip specification (which defines
*decompression*)
where each can possibly output a different compressed file (e.g. WinZip vs
WinRAR zips etc)
- only one and *unique* way of decompressing a file within the zip
specification
This is where this little "challenge" makes sense.
I'm pessimistic with that one because of several annoying details.
BUT so far, i've seen no trace of any valid argument towards a proof of the
impossibility within this thread...
this is a bit embarassing for a top notch comp newsgroup isn't it? :)
David A. Scott
news:bgpedl$b39$1...@news-reader3.wanadoo.fr:
>
> This is where this little "challenge" makes sense.
>
> I'm pessimistic with that one because of several annoying details.
> BUT so far, i've seen no trace of any valid argument towards a proof
> of the impossibility within this thread...
>
> this is a bit embarassing for a top notch comp newsgroup isn't it? :)
>
>
>
>
Not really since most don't care. I don't know about ZIP but there
are other compressors that would decompress the same file to the same
file in certain cases.
David A. Scott
Camping Gaz
"David A. Scott" <daVvid_...@email.com> a écrit dans le message de
news:Xns93CEBA737318H1...@130.133.1.4...
> "Camping Gaz" <p...@wanadoo.fr> wrote in
yeah of course if nobody cares, we won't go too far eh. I don't care much
either, just enough to give my 2 cents.
it's just that it could be funny.
and yes i know other compressors that can do that and more but when it's
easy it's no fun :p
this one made me think of the crafted zip file (or was it another type)
which you couldn't decompress because it would be too big for any known
storage :)
main things against the feasibility :
- checksum
- filename
and one good thing, maybe :)
- there is a finite set of zip files! well as much as the file sizes are
limited, which is the case afaik
in short bleh, it is time to place bets!
i mean, saying it's not possible and being "ready to be proved wrong" is
just ghay =)
saying to the guy asking the question that he should try is so aswell...
i think he was expecting the few leet ppl (who care, sorry) here to tell him
:
"what are the conditions for a compression scheme so that it can do that?"
Raymond Wan
On Wed, 6 Aug 2003, Camping Gaz wrote:
> in short bleh, it is time to place bets!
> i mean, saying it's not possible and being "ready to be proved wrong" is
> just ghay =)
> saying to the guy asking the question that he should try is so aswell...
Well, if you were the person who asked the original question, what
type of answer do you want? My point was that it's probably not possible
and wasting time on it isn't worth it. However, if one really wants to
find out, then yes, experimentation or rigorous proof is the only way.
That is, if no one else will do it for you, then do it yourself.
> i think he was expecting the few leet ppl (who care, sorry) here to tell him
> :
> "what are the conditions for a compression scheme so that it can do that?"
AFAIK, this is a discussion group, not a solution manual for
compression. In the absence of a concrete reply for...I think it was a
few days...then you'll either get continued silence or an opinion. If I
had known that an opinion was not wanted, I would have let the silence
continue (I think there was an earlier reply; couldn't remember what it
was, though.).
BTW, if providing an opinion to the original post is so "ghay"
(???), then what does that say about your post: an opinion to an opinion
to the original post! :-)
Ray
Camping Gaz
quickly getting back to the post that started it all,
i see that a "certainty' was asked for! :)
what came out is that nobody knows for sure
i too would like to know, i'm just curious no more no less.
i just thought about it a bit.
this NG happens to host way worse time wasting topics for sure :)
"Raymond Wan" <rw...@student.unimelb.edu.au> a écrit dans le message de
news:Pine.OSF.4.10.103080...@cassius.its.unimelb.edu.au...
>
Raymond Wan
On Thu, 7 Aug 2003, Camping Gaz wrote:
> i don't blame you in particular. giving your opinion is okay but
Ok, that's fine.
> quickly getting back to the post that started it all,
> i see that a "certainty' was asked for! :)
> what came out is that nobody knows for sure
Well, I wouldn't surprised why no one would know the answer. The
collective minds of the newsgroup still doesn't equal a compression
oracle. Many people are deep in the field and just don't read the group.
As for those that do read here, it may be the answer's not known, or as
David pointed out, it may be the problem's not interesting enough.
Upon reading it, it sounded like a problem I would think about
while uncompressing a zip file; but it wouldn't be something that I would
spend more time on. For me, it's somewhat uninteresting because the
problem is being confined to a specific compression program. Despite it's
popularity, the format is like any other format -- it's artificial. If a
particular file is found that satisfies the properties, then the format
can be changed to prevent it (in a subsequent version, though zip file
formats don't change as often as OS versions :) ). Now if we generalise
to the LZ77 algorithm, then we're getting somewhere...
> i too would like to know, i'm just curious no more no less.
> i just thought about it a bit.
Yes, it's that kind of a problem.
Ray
David A. Scott
news:Pine.OSF.4.10.103080...@cassius.its.unimelb.edu.au:
>
> Upon reading it, it sounded like a problem I would think about
> while uncompressing a zip file; but it wouldn't be something that I
> would spend more time on. For me, it's somewhat uninteresting because
> the problem is being confined to a specific compression program.
> Despite it's popularity, the format is like any other format -- it's
> artificial. If a particular file is found that satisfies the
> properties, then the format can be changed to prevent it (in a
> subsequent version, though zip file formats don't change as often as
> OS versions :) ). Now if we generalise to the LZ77 algorithm, then
> we're getting somewhere...
>
>
I think the compressor would not need to be changed. When one compresses
a file one hopes it gets samller. But sometimes they get longer and
thats life. But if it did not change size who cares. And if it stayed
exactly the same who cares the compressor did its job on it like any
other file.
Know if you wrote code that took a zip and it keep reunziping until
no more zip files you could have a porblem. But if you are only doing
this to files that was created by the reverse and started with no
zip files then it would not occur. However if you could trick someone
then you could get it to run infinitely. In which case but a counter
in loop to stop it.
Which may be easier to do is create a zip that on expansion is
another zip that expands ever time you on zip it. I suspect this
is easier far easier to do.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE "OLD VERSIOM"
http://www.jim.com/jamesd/Kong/scott19u.zip old version
My Crypto code http://radiusnet.net/crypto/archive/scott/
My Compression code http://bijective.dogma.net/
**TO EMAIL ME drop the roman "five" **
Disclaimer:I am in no way responsible for any of the statements
made in the above text. For all I know I might be drugged.
As a famous person once said "any cryptograhic
system is only as strong as its weakest link"
Raymond Wan
On 7 Aug 2003, David A. Scott wrote:
...
> Which may be easier to do is create a zip that on expansion is
> another zip that expands ever time you on zip it. I suspect this
> is easier far easier to do.
True. I guess I'm not referring to the program, but the file
format. Suppose one could find such a file with this property through
artificial means. If so, is this a fault with the file format? Well, if
this was some program that I made to have this property, then no, it's not
a fault...I purposely added this "feature" in. But, how about the zip
file format? Should the zip file format be changed to close this
loophole?
I think it would be like asking if there is an OS with a security
flaw. Why, yes...but if you report it in, one would hope that the flaw
would be fixed soon (depending on the OS in question... ;) ) and then it
wouldn't exist. But, if we ask whether or not OS' (in general) have a
flaw and under what conditions (i.e., this algorithm mixed with that
incompatiable algorithm), that seems to me like a more interesting
problem. At least when you've found the proof, there is no attempt to
fix the problem.
I'll admit, if there was time, then such an exercise would be
"fun". But yes, I'll also say that I'm probably being more naive than
other readers in this group in believing that a file format that has been
around so long should be more robust than the formats of the compression
systems I've written. Of course, a real bug occurs if an unzip program
unzips a file forever...but in this case, it's the user who is using it
wrong by dropping it into unzip repeatedly. In this sense, it wouldn't be
a true bug...like the ones found in certain OS'. :-)
Ray
David A. Scott
news:Pine.OSF.4.10.103080...@cassius.its.unimelb.edu.au
:
>
> True. I guess I'm not referring to the program, but the file
> format. Suppose one could find such a file with this property through
> artificial means. If so, is this a fault with the file format? Well,
> if this was some program that I made to have this property, then no,
> it's not a fault...I purposely added this "feature" in. But, how
> about the zip file format? Should the zip file format be changed to
> close this loophole?
>
>
If it has this loophole so what it would not be an error.
take almost any of my compressor. They for most files always
decompress to a larger file. Which can then be decompressed
over and over again to larger and larger files. Its not an
error its just what happens.
Joe
Przemyslaw Brojewski <bro...@zly.kis.p.lodz.pl> wrote in message
news:bfoivb$pnf$1...@kujawiak.man.lodz.pl...
0a_0^x+0a_1^x....=0b^x <---- Most famous trivial solution, that's
annoyingly useless for Fermat's so called last theorem.
I think it would be considered cheating to use a zerolength file.
Technically it wouldn't even decompress at all, heh, but of course you know
I'm not serious about that one.
It's quite possible to say that:
A) One ZIP decompresses to one and only one file.
B) One file can make multiple ZIPs.
C) Not all valid decompressable files can be made with PKZip etc.
D) You ignore any practical limit on filesize.
E) It's NOT proven that a file automaticly creates a different file on
unzipping.
If these are all true, then it's highly likely to at least be possible.
A=Should do this, as it's supposed to be lossless. If not true, then there
is a bug/glitch.
B=Proven(You can use multiple methods).
C=Very important. (: With the checksum+filelengths, and the beginning of a
file causing major changes in the compressed data (at least for a while),
who knows?
D=Will not matter, if E is false. May be an issue, if you want it to be
possible to even decompress it with unzippers.
E=May not be easily or even possibly proven. This is almost as hard a
problem, as going through all 2^n possiblities, looking for self referencing
ZIPs.
I don't see how there's a specific rule against this... Anyone else?
Another question, is would it be considered partially solving this
'problem', if one were allowed to use PKZIPFIX or the like?
What about a file, that leaves some extra junk on the end, that's not
considered part of the file? Would a 'virus' count (can't reproduce without
host)?
I don't care about if it's possible, so much, as I am about finding out if
it is. It's one of those frustrating problems.
I want to know one way or the other. Too bad the universe is so cruel. heh
Rasmus Møller
> E) It's NOT proven that a file automaticly creates a different file on
> unzipping.
>
> problem, as going through all 2^n possiblities, looking for self referencing
> ZIPs.
I truly believe this problem is worthy of a "grid" solution like the
SETI screensaver! Enumerate all valid ZIP-files, starting with the
smallest, assign a range of "consecutive" files to each work unit to
be tested, let the millions of benevolent PC-owners compete for a high
score of number tested ZIP files. If _this_ problem cannot passionate
the average PC-owner more than the battle against cancer or the search
for extra-terrestrial life, what can? :)
Rasmus
Joe
Rasmus Mųller <AERa...@volcanomail.com> wrote in message
news:8dbb24e7.03081...@posting.google.com...
Here's an approach to try:
Repeatedly encode a file like this:
1) Random file.
2) Compress it.
3) Mutate it.
4) Compress again, clipping after a random size.
5) Check if compressed file matches input.
6) Goto 2.
Not sure if that'll work, but it's worth a shot.
I think that you'de need to override the 'store' method in step 4, for
obvious reasons. Could even try random (method) option settings.
The mutations can be single bits/bytes, length altering (bits/bytes/etc), or
whatever you think will be most likely to work. (:
Another approach, is to do a decompression instead of a compression, on a
file that has be compressed in something like 1000 layers.
Modify the decompressor, to automaticly make the data valid (don't know if
this is possible). Might be a magic function aka fantasy aka pipedream.
If this 2nd method works, I would ask for credit on your paper. Hehe
It's probally VERY hard to prove that a ZIP can't become itself, but it only
takes one example, to prove it IS possible. LOL