Crunching Algorithms?
category: general [glöplog]
Still learning demo programming / demotool stuff. Can you guys point me towards some of the more common crunching algorithms? I heard someone say that it's kind of like lossless compression for music, but I have no idea what people are actually using for 4ks and the like.
I'm very confused by the questions - are you looking for a compressor for your 4ks?
Or good old UPX for the bigger stuff.
Or just don't care for the actually bigger stuff.
Or just don't care about the size and focus on the content instead.
Hello baordog !
Yes, most size-restrained demo use a packer to try to gain a few bytes off their exe.
The basic idea of a packer is quite simple: You compress your original exe, then you are going to put the compressed binary an another exe that contain an decompressor that will decromrpess and run the original exe at runtime.
The main idea may be simple, but making one that will efficiently compress a binary is quite complicated. Most modern compressor use a PAQ-based compression algorithm.
If you are interested to learn more, ryg had made a series of blog posts about kkrunchy, a packer for 64k demos. here.
More recently, Ferris has been working on his own packer for Logicoma. You could maybe ask him for more resource.
A fair warning though, making a packer is very time consuming. If your objective is to make a demo, you should probably use one that already exist (kkrunchy, crinkler, UPX).
Also, demos don't *have to be* size-restricted. A lot of very famous demos are not size-restricted, some ASD demo weight more than a hundred megabytes :) . If you are still learning about demo making, the easier path is probably to start your first one without any-constraint and then working you way from here. Learning is an iterative process, if you try to do everything at the same time, you might end up achieving nothing (talking from experience!).
Yes, most size-restrained demo use a packer to try to gain a few bytes off their exe.
The basic idea of a packer is quite simple: You compress your original exe, then you are going to put the compressed binary an another exe that contain an decompressor that will decromrpess and run the original exe at runtime.
The main idea may be simple, but making one that will efficiently compress a binary is quite complicated. Most modern compressor use a PAQ-based compression algorithm.
If you are interested to learn more, ryg had made a series of blog posts about kkrunchy, a packer for 64k demos. here.
More recently, Ferris has been working on his own packer for Logicoma. You could maybe ask him for more resource.
A fair warning though, making a packer is very time consuming. If your objective is to make a demo, you should probably use one that already exist (kkrunchy, crinkler, UPX).
Also, demos don't *have to be* size-restricted. A lot of very famous demos are not size-restricted, some ASD demo weight more than a hundred megabytes :) . If you are still learning about demo making, the easier path is probably to start your first one without any-constraint and then working you way from here. Learning is an iterative process, if you try to do everything at the same time, you might end up achieving nothing (talking from experience!).
TS said nothing about the platform which means the answer is more complicated.
4k's are just 4096 bytes, which roughly means you can stick sixteen small 256 byte intros in them. Let's say you then plan your intro and make a list of how much space you want to invest in for each module:
1. 256 bytes for texture-generation
2. 128 bytes for sound-gen
3. 128 bytes for music-note pattern-generation
4. 512 bytes for 3D-object generation
5. 128 byte for polyfiller routine
6. 64 byte for music-player
then you are left with 2880 byte for the actual intro.
(Ok this was a rough list, but the idea is there)
Since many of these modules can be optimized you can save more bytes for the actual demo.
As the list shows above, if you were to code on DOS, a compressor would much likely be a waste of space. The idea (that have been a long tradition since the early 2000's) is to proceduraly generate your textures, music and so on. Most of it is generated not stored, or packed and decrunched. If you're coding for Windows Crinkler is the thing nowadays, because working around the PE-header, calling functions throught DLL's and such stuff in assembler is a pain (atleast for me), it takes some time to figure it out, and then even optimizing anything can cause difficulties. I heard you are better of with compression because of shading-language (scripting and so on). So it all depends on the platform.
4k's are just 4096 bytes, which roughly means you can stick sixteen small 256 byte intros in them. Let's say you then plan your intro and make a list of how much space you want to invest in for each module:
1. 256 bytes for texture-generation
2. 128 bytes for sound-gen
3. 128 bytes for music-note pattern-generation
4. 512 bytes for 3D-object generation
5. 128 byte for polyfiller routine
6. 64 byte for music-player
then you are left with 2880 byte for the actual intro.
(Ok this was a rough list, but the idea is there)
Since many of these modules can be optimized you can save more bytes for the actual demo.
As the list shows above, if you were to code on DOS, a compressor would much likely be a waste of space. The idea (that have been a long tradition since the early 2000's) is to proceduraly generate your textures, music and so on. Most of it is generated not stored, or packed and decrunched. If you're coding for Windows Crinkler is the thing nowadays, because working around the PE-header, calling functions throught DLL's and such stuff in assembler is a pain (atleast for me), it takes some time to figure it out, and then even optimizing anything can cause difficulties. I heard you are better of with compression because of shading-language (scripting and so on). So it all depends on the platform.
Unless you're interested in very low-level "invisible" programming, compression and "crunchers" are not a good starting point. If you want to make an exe with minimal tool/framework/infrastructure programming, check out Compofiller Studio http://www.kameli.net/compofillerstudio/
LOL ÄKSDEE
http://www.kameli.net/compofillerstudio/
http://www.kameli.net/compofillerstudio/
Quote:
As the list shows above, if you were to code on DOS, a compressor would much likely be a waste of space.
I don't think the list shows that a compressor would be a waste of space? Could you elaborate, and perhaps point to some famous DOS 4k intros that are uncompressed or didn't benefit from compression?
"Crunching" is Commodore 64 lingo. "Compression" is the correct term, "packing" is sometimes used. And yes, you certainly benefit from it for DOS 4ks.
In C64, I used a cruncher and it wasn't a waste of time, there was a lot to gain, of course I also did all the normal things people do on 4ks, writting in asm, generating procedurally things (unless it's a small logo or font or tiny music/player already provided) but the cruncher was itself small too I guess.
Also on CPC mainly in 4ks.
Take a look at in4k for Windows + some general 4k development info.
Quote:
Still learning demo programming / demotool stuff. Can you guys point me towards some of the more common crunching algorithms? I heard someone say that it's kind of like lossless compression for music, but I have no idea what people are actually using for 4ks and the like.
I am thinking there is a more fundamental answer to this question (or rather, the implicit question behind it) which might not be obvious from the replies so far:
When you make a 4k, it is unimportant how big your code and data is. What matters is how "compression-friendly" it is, i.e. how big it is after the cruncher has sunk its teeth into it.
Compression friendliness has to do (mainly) with regularity. The compressor recognizes patterns in the data which allows it to represent the data in a more compact form. Thus, you will want to structure your data in such a way that it exhibits the kind of patterns that the compressor can recognize.
Compressors work in different ways (although Crinkler and kkrunchy are very similar) and are able to recognize different kinds of patterns. However, there are some general approaches that are usually beneficial:
- Repetition is good. Data which is the same or almost the same as previous data gets compressed very well. Thus, it can often be smaller to duplicate some code than to run a loop a few times or call a function in only a few places. Beware, though, if you are not writing assembly by hand, that the compiler might use different registers and/or instruction scheduling for each copy, making them not quite the same after all.
- Similar values are good. When you have an increasing sequence of numbers (say, the positions of notes in your music), store the differences between them (known as delta coding). This will make the values smaller and thus more similar.
- Grouping similar data together is good. If you have, say, a position (delta coded) and a tone for each note in your music, it can often be smaller to separate them into two lists rather than having them interleaved. This should of course be weighed against the resulting increase in complexity of the code that reads the data.
So the answer to "what people are actually using for 4ks and the like" is really that they are making their code and data easily digestible for the cruncher. Both Crinkler and kkrunchy have compression report features (visualizing how well the various parts of the intro compress) to help with that.
Quote:
"Crunching" is Commodore 64 lingo.
It might have started there, but it is certainly not exclusive to C64 by now (that is, during the last three decades). I would say that "crunching" is a well-established demoscene term for compressing code and data at production time with built-in runtime decompression. A specific use case of data compression.
Quote:
"Crunching" is Commodore 64 lingo. "Compression" is the correct term, "packing" is sometimes used. And yes, you certainly benefit from it for DOS 4ks.
packing is c64 lingo aswell (level packers) but compressor was also used. you're out of luck.
