Infinite complexity in 4096 bytes | Hacker News Reader

Infinite complexity in 4096 bytes

creativeapplications.net

363 pointscageface76 comments

I'm pretty proud of my programming skills. I've worked in everything from assembly to JavaScript, JIT compilers to websites to large-scale, fault-tolerant distributed systems. etc. etc.

But demoscene programming is still the one thing that leaves me totally in awe, feeling like I wouldn't even know where to start to achieve what these guys pull off. Even if I could imagine fitting all those drawing and sound generation routines into 4k, how on earth would you script the whole thing in that little space? How would you encode and execute the sequence of camera paths, music events, and synchronize light flashes with the music? And make it consistent in time, as opposed to depending on the speed of the CPU? I just can't even imagine what the main loop would look like.

Have to start when you're young =) I'm in the same place as you. Pretty sure if I started doing it when I was 10, it'd be self-obvious by the time I turned 12.

Don't be intimidated! There are a lot of things you don't know about how to make demoscene-style programs, and the reason you don't know them is probably because you haven't tried to learn them yet. I'm pretty sure that if you start learning when you're n, a lot of things will seem self-evident when you're n+2.

Here's a series of really good blog posts from someone who decides to make a shiny procedurally-generated city. The result is an amazing how-did-he-do-that demo, but the steps he went through and the way he thought about the problem are understandable.

http://www.shamusyoung.com/twentysidedtale/?p=2940

This is a really great (well written, entertaining, informative, inspiring) series of articles about a guy programming just for the joy of it! Thanks for posting.

For a general discussion of synchronisation, Martti Nurmikari gave a talk at Assembly last year

http://thedemoscene.tumblr.com/post/8659078065/martti-nurmik...

Alcatraz use an interesting system based on Clang and llvm to export all that from Maya as source code

http://thedemoscene.tumblr.com/post/22588846914/digi-alcatra...

Excellent links, thanks!

On a C64, you disable interrupts, pull out your trusty table of opcodes, and can time everything down to a single clock cycle.

Same here. 4096 bytes is just 64 lines of 64 characters. These guys are brilliant.

Well, ASCII characters use only 7 bits (the high bit is unset), so it's really ~73 lines of 64 characters. And if you limit to alphanumeric that's only 95 symbols, so 172 lines of 64 characters. :)

Synchronizing with the music is easy if you generate the music yourself.

Yeah - I thought I was doing fairly well back in the 70s when I wrote a (lossless) half-tone compression routine that got ~50% compression when there was only enough core [and some of the machines it ran on uses actual core] to hold one scan line. This stuff is amazing.

Just recently, in fact a new method came along: those raymarchers that many modern 4k intros are, are essentially a single pixel shader. The C code draws a single quad that fills the screen two-dimensionally, and calls the shader. The shader computes a colour for each pixel for each frame, on the GPU, using relatively simple math to describe the scene (geometric shapes, like intersections of spheres and cubes, for instance. or fractals, like in the OP).

This means that instead of learning sizecoding, the opengl/d3d pipeline, mesh uploading, textures, getting along with the video bus speed, index buffers, geometry shaders, and so on, and so on, you can just learn GLSL and how a raymarcher works. Much like 20 years ago, getting something on screen quickly became easy again. It's not as easy as Processing, but it's not too far off either.

For example, check out this video[1] about the Russian demogroup Quite (who made the amazing 4k intro "cdak"[2]. The video briefly shows (scroll to 20 minutes) how unc starts with the shader instead of with the C code, using vvvv[3], a tool for live prototyping realtime graphics. They only turn the non-shader parts of the vvvv "code" (block diagrams and envelopes) into C code when the intro starts looking like it's going to be releaseable. With such an approach, you get motivated real fast; focus on getting something on screen, worry about getting into a demoparty compo later.

Or just don't worry about the C version at all, and make something cool that you'll never be able to pull off with any animation studio, and put it on vimeo :-)

Oh, also check out this Pouet thread [4] about how Quite made "cdak" (but first see the intro!). It's one of those things that make you even more amazed when you get it.

[1] http://www.youtube.com/watch?v=tuoRpEMfEHY

[2] http://www.pouet.net/prod.php?which=55758 | http://www.youtube.com/watch?v=RCh3Q08HMfs

[3] http://vvvv.org/

[4] http://www.pouet.net/topic.php?which=7909&page=1&x=2...

Cool, but I think my favourite 4k demo is still Elevated, which is much less obviously procedural. (http://www.youtube.com/watch?v=_YWMGuh15nE)

Bloody hell, that's brilliant. That's really 4k?!? The intro gave me chills. I wish the geometry were less obviously faceted, but the texturing is astonishing.

Of course the OP is brilliant too. Kudos to all these guys!

iq has a presentation on the techinques used

http://iquilezles.org/www/material/function2009/function2009...

that was also my favorite... but this one is at least on par. gosh, and only 4k.

TBC does some great ones. Although Receptor is my fav -- http://www.youtube.com/watch?v=0UOpWfX6gw8

Something to keep in mind is that these groups spend months building a world in these 4096 bytes. These aren't weekend hack jobs. Near the end they may be hacking off individual notes from the music, or letters from the credits to fit within their byte budget.

Very little of modern programming can replicate what it was like to work on old systems outside of these kinds of competitions.

For those interested in the music side of these productions, many of the composers use this to write the music. http://4klang.untergrund.net/

If you are not familiar with 4k intros, you may wonder how things are organized at the executable level to achieve this kind of packing-performance. Probably the most important and essential aspect of 4k-64k intros is the compressor. Have a look here: http://code4k.blogspot.de/2010/12/crinkler-secrets-4k-intro-...

I've always wondered how they managed to pack so much information into so small a space. Obviously it's all algorithms which generates everything at run time. But still, it's very impressive!

Or ~4096 bytes of Kolmogorov complexity...

Yes, its not literally "infinite complexity in 4096 bytes", but I think poetic license is entirely justified here... it is a sort of visual poetry after all.

Technically it's only 4096 bytes given all the other infrastructure the code accesses. Which is quite a bit.

Well, colour me impressed.

Interesting side note: demos tend to use music with pentatonic (ambient) or whole-tone (dreamy) scales. They’re easy to harmonise, which makes it easy to procedurally generate decent-sounding music.

When watching demoscenes these days I find myself always waiting for the dubstep 'drop'. Sadly I think modern music is starting to spoil this sort of thing for me.

Easily forgotten, a lot of today's demos' complexity lies behind API calls to graphics drivers and OS system calls, whose implementations don't count to the byte limit.

Because Amiga demos never exploited the way low res CRT displays looked or used the SID chip right?

For the record, the SID chip was used in Commodore 64, while Amiga had the Paula chip for sound output.

Variations of this comment are made on just about any story about 4kB intros.

This is not a very interesting point to me because of how it forgets that in any case, software never exist into a vacuum, and hardware is needed for it. And that hardware does perform a great deal of duties.

The subtext often is that for some reason it's less noble or impressive to code against APIs. However hardware also is a sort of API of its own. Even on a ZX-81.

I understand why this always comes up, but in this particular case it's particularly 'un-useful'. I can tell you exactly what API calls he makes: on boot he makes API calls the equivalent of PlayGigantic3MinuteWav(), InitOpenGL(), Compile2Shaders(), and then each frame he calls DrawFullScreenQuad() (twice, once to an offscreen texture, once to the screen), and Flip().

All the magic of the demo is in the synth (pure x86 fpu code) for the music, and the sphere tracer / camera choices / colors / fractal equation, for which precisely 0 'API' is used.

Put another way, the really amazing thing these days is that we have hardware (cpu, gpu) capable of so many FLOPS that you can do brute force things like sphere tracing complex fractals. the goal, seen in this light, of the demoscene, is to expose the wonder of all that power in visually interesting or arty ways.

Seriously, you couldn't have picked a worse example of someone 'leaning on an api'. :)

Just like early PC 4k's used the BIOS/DOS interrupt routines which were not counted either. And before that, there were all these custom purpose built chips for doing graphics and audio synthesis.

When making 4k intros for Linux (may apply to other platforms) you have to do your own startup and runtime linking code because otherwise the executable will go over the limit before it does anything. Because of this, you will have to minimize the amount of libraries you use and the amount of functions you use. The name of every function you use must be included as a string in the (uncompressed) binary. So even though you can use peripheral libraries, there is an incentive to minimize the amount of library functions you use.

And what are the libraries that are used? You need to get something on the screen, so many demos use SDL or similar, like this:

  SDL_Init(...);
  SDL_SetVideoMode(width, height, 32, SDL_FULL_SCREEN);

instead of:

  xor eax, eax
  mov al, 13h
  int 10h  ; I wonder if I still remember this correctly

The former is not much easier (or harder) than the latter but the latter is simply impossible with a modern computer.

Then there's OpenGL and Direct3D, which are used to talk with the GPU. These days a GPU is basically a method of drawing triangles really really fast. But it draws only triangles and you have to program all the lighting and whatnot. Then there are fancy shader tricks you can do, but they're not (a lot) easier than it was when poking pixels directly to video memory.

It's arguably easier to do 3d graphics using a GPU than writing your own triangle fillers and perspective correct texture mappers. But this is a double edged sword. Getting shit done with triangles only is a constraint that did not exist back in the pixel pushing days.

And finally, audio. Writing a software synth consumes quite a big chunk of your byte budget. Back in the day, there were dedicated synth chips in computers, from the SID to the OPL-3 in SoundBlasters and Ad-Libs. Programming them was not super easy either, but I'd guess it takes a few bytes less than writing a PCM-emitting synth from scratch and sending that data to the sound output.

So what you say is correct, library implementations don't count to the byte limit. But if your message is that it makes stuff easier and it was 2000% more hardcore in the 1990's with DOS, I disagree.

Yeah, I think you got the int 10h right (not sure I remember this as well)

But then came VESA which was a little bit more complex and of course, screen sizes bigger than a segment (ouch)

About audio, IMHO it's much easier now, dealing with those interrupt handlers and dma controllers wasn't easy. Of course, once the library worked it was ok.

> Yeah, I think you got the int 10h right (not sure I remember this as well)

10h is correct. The contents of ax register might not be. Is the graphics mode (13h) supposed to be in the al or ah part? That I can't remember.

> But then came VESA which was a little bit more complex and of course, screen sizes bigger than a segment (ouch)

Yeah, early VESA Bios extensions were hairy. With VBE 2.0 you can get a simple linear framebuffer with a high resolution quite easily.

> About audio, IMHO it's much easier now, dealing with those interrupt handlers and dma controllers wasn't easy. Of course, once the library worked it was ok.

Interrupt handlers and DMA controllers were used for PCM audio. I agree that writing that stuff by hand was harder than doing it today with libraries. And you'd still have to write the PCM-emitting synth.

But chip synths were generally programmed with simpler memory mapped I/O and they did the actual audio synthesis for you, not only PCM output.

    mov ax, 13h
    int 10h

You are correct. And using a mov to ax rather than xor+mov to al is counter-intuitively one byte smaller (there's one more byte of immediate value in the former). Every byte counts!

(I tested using "nasm -f bin")

However, in .coms you could assume that AX was 0 upon entry and skip the XOR.

Gosh, some guys are so easily hurt by a fact. And what "subtext" you read in my comment. Terrible.

As a matter of fact, demo producers are offered more and more API choices. Compare what you had to accomplish with tinkering around with bare-metal BIOS interrupts in the 90s, compared to a full-fledged DirectX API including GPU-raytraycing almost out-of-the-box.

I dunno about hurt blah blah blah but could you explain how exactly the 'modern API choices' provide 'GPU-raytraycing almost out-of-the-box'? if you search for ray tracing in opengl/directx/webgl, you will find no mention of ray-tracing, and for good reason: they don't provide it 'out of the box'.

The ray tracing going on in this demo has nothing to do with the APIs he is using; indeed, that demo could be implemented, pixel perfect, on any platform with floating point arithmetic. it just uses the 'advanced api' to display the resulting image on the screen...

now, the point you make is still a valid one, in that we have more api's than before, but this demo is not an example of using such apis. Better 'grey area 4k' examples that would support your point, are the ones that (for example), loaded the general midi file from windows, and used it as a source of samples (that was a trend a few years ago); or the ones that make use of D3DX's truetype font->extruded mesh routine, to create almost all their geometry out of extruded Arial letters. In both cases, these are such ingenious hacks that despite being in the 'grey area', and definitely (ab)using data available in the host OS, they represent such crazed creativity you can't help but admire them.

either way, such tricks were not used here; you're just seeing the result of a very large number of multiply-add instructions, artfully composed; and that's nothing to do with 'demo producers making more and more API choices'

Oh look, it's this old chestnut again.

So what? 100% of the information that makes Demo 1 different from Demo 2 lives inside that 4k. 0% of the creativity that makes demos actually inspiring lives in the OS or graphics drivers.

You should probably exercise a disassembler on the code for a bit and come away enlightened.

The technique used here is raymarching. Relevant thread on pouet: http://pouet.net/topic.php?which=7920

Yeah and there's many WebGL samples of this awesome technique:

http://www.postronic.org/h3/pid65.html

http://y-alice.blogspot.com/2012/04/final-submission.html

One pointlessly bouncy (but fun to make) experiment I ported from desktop GL to WebGL a short while ago:

http://glsl.heroku.com/e#2417

Set quality to 4 or 8 as fast as you can unless you already got one of them 2014 GPUs.

That being said, none of those are 4K =)

Does this give anyone else the sense that with amazing processors we have available that we're being really wasteful with these bloated apps we currently have?

I mean if these guys are able to do this in 4K, what else could be done in operating system terms if we achieved that same level of excellence?

These demos rely on the OS to access sound & graphics, they could not reach the fidelity they do without the OS hiding away much of the file size. You could not do a 4K demo if you had to include the infrastructure to load a modern graphics driver & OpenGL/DX libraries. They are also only small in terms of package size. This demo for example uses about 550MB of RAM while running(Win7x64).

Right, but you could do pretty impressive stuff even on a VIC-20.

That's not true in the least. We used to do 4K's in dos. Which was a glorified executable loader.

Once your program started executing you were on your own, graphics, sound, memory management, everything. People still managed to get the first level of descent into 4K.

I didn't say you could not make a 4K demo at all. I said you could not make one if you had to include an OS, drivers & DX/OpenGL libraries that most modern 4K demos rely on. You could probably make something like this demo in DOS, but it probably would look nowhere near as pretty.

My point was that modern 4K demos are still fun, but they should not be looked at as though they are great examples of efficient uses of resources. You have to watch out for Man on the Moon Syndrome where people start asking "Why can we get infinite 3D fractal explorations in 4K of space, but Ruby's binary is 10MB!!?".

4K demos in DOS didn't look anything like these modern ones, they were much simpler. They were still very impressive for the time, but the grandparent-post's point is valid.

If you wrote a 4K DOS demo today against modern hardware you wouldn't be able to reach anywhere near the look of these other demos which sit ontop of OpenGL/D3D/Win32 etc, because you'd need to build the equivalent of those API's functionalities into your demo.

Stuff like this: http://en.wikipedia.org/wiki/.kkrieger

The lossless 60 fps high definition video capture is currently unavailable (traffic limit). Any mirrors (or torrent would probably be a pretty good idea)?

YouTube 1080p version seems to have pretty terrible quality.

This seriously begs for a torrent.

This one? http://www.youtube.com/watch?v=0w_xEUoK79o It was uploaded in 2048x1526 resolution, so anything less than that will be downsampled by Youtube.

Somewhat humorous that the full resolution demo of a 4k intro is too large to handle on the server. Just post the source

Not only are there 4-kilobyte demos, there are also 256-byte demos.

http://dang.posterous.com/256-byte-demos

http://www.pouet.net/search.php?what=256+bytes&type=prod...

I once spent hours looking for an internet archive or community of demo scene files / artists. There doesn't seem to be one out there in the eyes of google. Can anyone familiar with this art form please provide links to your your underground hangout? :)

http://www.pouet.net is the only I'm aware of.

[edit] maybe http://scene.org also ?

This is a very thorough list of the most famous (read:best) and most influential demos: https://news.ycombinator.com/item?id=3840830

www.pouet.net

www.demoscene.tv

www.scene.org

http://www.scenemusic.net/demovibes/

I understand lots of the scene is still active on IRC if you hunt around.

pouet.net, #coders on ircnet, or just visit a demoparty in your area.

The entire 4k competition from that party is here

http://www.youtube.com/watch?v=bdG-5Fhnx-I

well worth the watch...

German hartverdrahtet -> hardwired / hardcoded but also 'wired hearts' (the opening shot and the primitive the scene appears to be made out of)

"Herz" is the German word for heart. Do you mean that "hart" sounds like the English word "heart"?

Yes, it looked like a play on words. In dutch (halfway between English and German) it literally means heart.

Here's my first 4k production: http://www.youtube.com/watch?v=sBcwQCBpEiE

If you want to play with this type of code right now in your browser, check this out... http://glsl.heroku.com/e#2431.0

Note that if you crave this kind of world of limited resources and ingenuity for packing things very small, it still exists in a professional setting in hard real-time embedded systems.

I heard a story at my company about fixing a bug a couple years ago. Memory was full, so in order to do that, the engineers rewrote the UI messages to allow the extra instructions to fit into memory.

What a piece of art!

it's things like this that remind me how sucky my "skills" actually are

Demoscene!

I was an intern at a game company last year. I showed the CEO some of the stuff that is going on in the demoscene. He got really worried and told me to not show that to any of his staff. He was afraid that it intimidates his highly paid coders and designers. I found that rather disturbing. How are you going to kill Hollywood if you are afraid of algorithms?

Any game coder worth his salt knows fractals. Many veterans from the demoscene ended up in the game industry at some point. In the 90s most wizkids dreamt of living off making games, and many demosceners made intros to cracked games.

Good game coders like Carmack have little to feel intimidated about.

Your point is good but saying that Carmack shouldn't feel intimidated is probably not helpful. ;)

As a coder I too feel intimidated by these impossible 4 KB Demos. It is also important to remind oneself that the optimizations to do this stuff are mostly meaningless for making a game. You are mostly constrained by time in a project, and shouldn't distract oneself in being cute with neat tricks.

What you can do within severe constraints can be very impressive.

Particular impressive results may not fit into severe constraints.

Do not confuse the two.

Even a small "that's great, but it needs to do..." can change 4KB into 4GB.

The funny thing is that many game programmers I know grew up watching demos if not making them. Who hasn't seen at least one Future Crew demo?

s/intimidate/inspire/g

Reply on news.ycombinator.com