4 ms·

Reminds me of a sarcastic response from my classmate back in my undergrad Signals class... the professor showed us a sample black-and-white photo and asked (rat

by tribune 11y ago

Reminds me of a sarcastic response from my classmate back in my undergrad Signals class... the professor showed us a sample black-and-white photo and asked (rather rhetorically) how we would represent it using as few bits as possible. Classmate said he would build a machine that only displays that image, and give it an On/Off switch - a whole image with only 1 Bit!

TeMPOraL 11y ago
And this is the crucial insight. An image, or a game, does not contain all its data in those bytes you have stored in its file. A lot of information is spread around in the environment. It's one of the main ways demo-makers can cram so much content into so little space - they pull as much stuff from the environment as it's possible (and allowed by contest rules). To give an example: one of the most basic tricks, if you're allowed to use OpenGL and WinAPI, is to use WGL to render your system fonts into 3D shapes[0]. This allows you to get a lot of 3D models from just the few bytes it takes to call wglUseFontOutlines()[1]. You may think that there isn't anything interesting in a basic font, but - even forgetting about Unicode - every Windows has Wingdings... (Or look into the good old .EMF[2] format, which was basically direct encoding of Windows GDI calls.) For much more in-depth discussion on where exactly information is stored, be sure to read GEB[3], if you haven't already. [0] - https://www.youtube.com/watch?v=iri5CgLglkk https://www.youtube.com/watch?v=iri5CgLglkk - 1/10th size of Mario! [1] - https://msdn.microsoft.com/en-us/library/windows/desktop/dd374393%28v=vs.85%29.aspx https://msdn.microsoft.com/en-us/library/windows/desktop/dd3... [2] - https://en.wikipedia.org/wiki/Windows_Metafile https://en.wikipedia.org/wiki/Windows_Metafile [3] - https://en.wikipedia.org/wiki/G%C3%B6del,_Escher,_Bach https://en.wikipedia.org/wiki/G%C3%B6del,_Escher,_Bach
- pavel_lishin 11y ago
  > And this is the crucial insight. An image, or a game, does not contain all its data in those bytes you have stored in its file. A lot of information is spread around in the environment. This is also an argument I've heard about growing people new bodies to transfer into (like Old Man's War) or digitizing humans (like the Singularity); apparently, a sample of DNA isn't enough to create a whole new person. You need, at least, a womb.
  - TeMPOraL 11y ago
    This also ties back to the Reflections on Trusting Trust[0]. Living things are not made in a single factory, but are akin to the compilers compiling compilers. It's interesting to ask just how many things about us are not expressed in the DNA at all, but instead propagated implicitly by the replication mechanisms, Ken-Thompson-style. [0] - http://fermatslibrary.com/s/reflections-on-trusting-trust http://fermatslibrary.com/s/reflections-on-trusting-trust
- RDeckard 11y ago
  This is text-book Kolmogorov complexity. https://en.wikipedia.org/wiki/Kolmogorov_complexity https://en.wikipedia.org/wiki/Kolmogorov_complexity
iso8859-1 11y ago
Why have not zero bits then? http://www.dangermouse.net/esoteric/lenpeg.html http://www.dangermouse.net/esoteric/lenpeg.html
- deathanatos 11y ago
  > Why have not zero bits then? LenPEG 2 contains a bug that will cause it to corrupt images. Let's say I have a custom compression algorithm (as allowed by LenPEG 2), let's call it "SurprisedBabyPEG"; it's steps are: 1. Is the image the "surprised baby gif"? If yes, write an empty file. 2. Otherwise, encode the input as PNG, and write that to the file as output. LenPEG 2 allows us to choose an encoding algorithm: > 2. Prompt the user to ask what other algorithm to use (GIF, JPEG, PNG, etc). Take the surprised baby gif, and feed it as input to LenPEG 2. It's not Lenna, so step 1 fails. We proceed with step 2, and it prompts us for an encoding algorithm; we choose "SurprisedBabyPEG". > 3. Use the user-suggested algorithm to compress the image and write it. SurprisedBabyPEG outputs the empty file; this is the same output as if we run Lenna through LenPEG 2; on decompression of our surprised baby, Lenna is incorrectly output. (This bug is correctable, and also affects LenPEG 3.) Also, (grep "`./smr`" < input || cat lenna) | xv - The linked smr.c does not link. This reminds me how you can communicate any finite sequence of octets across a network connection with only a two bits.
  - jychang 11y ago
    Doesn't this bug affect LenPEG 1 then? An compression algo that returns "surprised baby gif" if it has a file with first bet set to 1... would match LenPEG 1.

by tribune 11y ago

TeMPOraL 11y ago

And this is the crucial insight. An image, or a game, does not contain all its data in those bytes you have stored in its file. A lot of information is spread around in the environment. It's one of the main ways demo-makers can cram so much content into so little space - they pull as much stuff from the environment as it's possible (and allowed by contest rules). To give an example: one of the most basic tricks, if you're allowed to use OpenGL and WinAPI, is to use WGL to render your system fonts into 3D shapes[0]. This allows you to get a lot of 3D models from just the few bytes it takes to call wglUseFontOutlines()[1]. You may think that there isn't anything interesting in a basic font, but - even forgetting about Unicode - every Windows has Wingdings... (Or look into the good old .EMF[2] format, which was basically direct encoding of Windows GDI calls.) For much more in-depth discussion on where exactly information is stored, be sure to read GEB[3], if you haven't already. [0] - https://www.youtube.com/watch?v=iri5CgLglkk https://www.youtube.com/watch?v=iri5CgLglkk - 1/10th size of Mario! [1] - https://msdn.microsoft.com/en-us/library/windows/desktop/dd374393%28v=vs.85%29.aspx https://msdn.microsoft.com/en-us/library/windows/desktop/dd3... [2] - https://en.wikipedia.org/wiki/Windows_Metafile https://en.wikipedia.org/wiki/Windows_Metafile [3] - https://en.wikipedia.org/wiki/G%C3%B6del,_Escher,_Bach https://en.wikipedia.org/wiki/G%C3%B6del,_Escher,_Bach

pavel_lishin 11y ago
> And this is the crucial insight. An image, or a game, does not contain all its data in those bytes you have stored in its file. A lot of information is spread around in the environment. This is also an argument I've heard about growing people new bodies to transfer into (like Old Man's War) or digitizing humans (like the Singularity); apparently, a sample of DNA isn't enough to create a whole new person. You need, at least, a womb.
- TeMPOraL 11y ago
  This also ties back to the Reflections on Trusting Trust[0]. Living things are not made in a single factory, but are akin to the compilers compiling compilers. It's interesting to ask just how many things about us are not expressed in the DNA at all, but instead propagated implicitly by the replication mechanisms, Ken-Thompson-style. [0] - http://fermatslibrary.com/s/reflections-on-trusting-trust http://fermatslibrary.com/s/reflections-on-trusting-trust
RDeckard 11y ago
This is text-book Kolmogorov complexity. https://en.wikipedia.org/wiki/Kolmogorov_complexity https://en.wikipedia.org/wiki/Kolmogorov_complexity

iso8859-1 11y ago

Why have not zero bits then? http://www.dangermouse.net/esoteric/lenpeg.html http://www.dangermouse.net/esoteric/lenpeg.html

deathanatos 11y ago
> Why have not zero bits then? LenPEG 2 contains a bug that will cause it to corrupt images. Let's say I have a custom compression algorithm (as allowed by LenPEG 2), let's call it "SurprisedBabyPEG"; it's steps are: 1. Is the image the "surprised baby gif"? If yes, write an empty file. 2. Otherwise, encode the input as PNG, and write that to the file as output. LenPEG 2 allows us to choose an encoding algorithm: > 2. Prompt the user to ask what other algorithm to use (GIF, JPEG, PNG, etc). Take the surprised baby gif, and feed it as input to LenPEG 2. It's not Lenna, so step 1 fails. We proceed with step 2, and it prompts us for an encoding algorithm; we choose "SurprisedBabyPEG". > 3. Use the user-suggested algorithm to compress the image and write it. SurprisedBabyPEG outputs the empty file; this is the same output as if we run Lenna through LenPEG 2; on decompression of our surprised baby, Lenna is incorrectly output. (This bug is correctable, and also affects LenPEG 3.) Also, (grep "`./smr`" < input || cat lenna) | xv - The linked smr.c does not link. This reminds me how you can communicate any finite sequence of octets across a network connection with only a two bits.
- jychang 11y ago
  Doesn't this bug affect LenPEG 1 then? An compression algo that returns "surprised baby gif" if it has a file with first bet set to 1... would match LenPEG 1.