Size Coding

The version of fr-08: .the .product that won the PC 64K intro competition at The Party in December 2000 was 65,536 bytes long, exactly the limit. Nine years later Elevated flew a camera over rock, snow and water, with music, from a Windows program of no more than 4,096 bytes. In 2017 Linus Åkesson fitted a whole Commodore 64 production, music included, into 256 bytes. Size coding is the craft behind programs like these: writing to a byte limit set in advance, usually by a demo party’s competition rules, and making the most of every byte under it.

Fast facts

• What it is: writing a program to fit a fixed size, counted in bytes of the finished file.
• Common limits: 64K (65,536 bytes) and 4K (4,096 bytes) intros; 1K; 256 bytes; on MS-DOS also 128, 64 and 32 bytes.
• Early competitions: Assembly ’93 held an Amiga 40K intro competition; Assembly ’94 had separate PC 64KB and 4KB intro competitions.
• Main methods: generating content with code (procedural generation), synthesising music as the program runs, executable compression, and hand-tuned machine code.
• Tools: pucrunch and Exomizer on the C64; kkrunchy for 64K intros and Crinkler for 4K and 1K intros on Windows.

Where the limits came from

In October 1998 CU Amiga ran a feature on the Amiga demo scene. One of the sceners it quoted, Crash, traced the scene’s roots to the “small intros (cracktros) presented on the front of cracked programs” by the groups that cracked them. Demos grew to fill several disks and then hard drives, he said, but “the heritage still exists though, as groups still make intros today. The parties still hold 64K and even 4K intro compos, to see how much people can cram into a set limit. These are often great feats of programming, and some groups specialise in these and not ‘full’ demos.”

Party results show the categories settling in. Assembly ’93 ranked PC intros in a single competition but ran a separate Amiga 40K intro competition, won by Stellar. At Assembly ’94 PC intros were split into a 64KB competition, won by Prime’s AirFrame, and a 4KB one, won by Dust’s Stoned. The authors of Crinkler, a later tool for 4K intros, date size-limited competitions to “the early 1990’s (and before that as well)”.

Size categories

Other limits come and go with the parties. farbrausch’s .kkrieger, a first-person shooter, won a 96K game competition at Breakpoint 2004 at 97,280 bytes, and Revision 2026 ran an 8K intro competition. Party rules also fix the platform: A Mind Is Born had to load at $0801, the start of C64 BASIC memory, because “compo rules” said so.

Generate, don’t store

The first rule of size coding is that pictures, models and music take too much room, so the program makes them as it runs. fr-08 stores no images at all. “All the textures are generated, even those that look like photoshop,” its coder Chaos wrote. farbrausch’s tool recorded the steps the artist took, and the intro repeats them at start-up, behind a progress bar. The readme of .kkrieger put the same idea plainly: “We merely store the individual steps employed by the artists to produce their textures and meshes.”

Elevated goes further. Its landscape is a flat grid of triangles pushed up and down by a height function evaluated in a vertex shader, a sum of 16 layers of noise, each half the strength of the last. A full-screen pass then textures and lights each pixel, and another adds motion blur. The same function also gives the textures, fake soft shadows and the shake of the hand-held camera, and each camera shot costs 8 bytes: a starting point in a random texture plus speed, height and field of view. By then many 4K intros drew their scenes by ray marching, stepping a ray out from each pixel until it reaches a surface described by a distance function. Íñigo Quílez, who made Elevated’s visuals, called 2009 “the year of the raymarching”, but Elevated drew triangles and shaded each pixel afterwards. Elevated has the details.

Patterns can come from a single expression. This C line gives each pixel a colour of 1 or 0:

int colour = ((x ^ y) & 8) ? 1 : 0;

Trace it: bit 3 of x changes every 8 pixels across the screen, and bit 3 of y every 8 rows down. The exclusive OR (^) of the two is 1 where exactly one of them is set, so the result is a checkerboard of squares 8 pixels wide.

Synthesised music

Sampled sound is too big for most limits, so the music is a synthesiser plus a score. fr-08’s music was played live by kb’s software synthesiser, which Chaos described as “incapable of playing samples of any kind”. Elevated used a synthesiser written by Mentor of TBC, and 4klang, “a modular software synthesizer package intended to easily produce music for 4k intros”, was begun in 2007 by Dominik Ries (gopher) and Paul Kraus (pOWL) of the group Alcatraz. On a C64 the synthesiser is already in the machine. A Mind Is Born uses the three voices of the SID chip for kick drum and bass, melody and a drone, and its whole score is 64 bars.

Executable compression

Most size-limited programs are compressed. The file holds packed data plus a small routine that unpacks it into memory and starts it. On the C64, Pasi Ojala’s pucrunch (1998) compresses on a PC and unpacks on the C64 “with no extra memory”; the section below covers it and its successors.

On Windows, two packers written by sceners were made for exactly this job. Fabian Giesen (ryg) of farbrausch wrote kkrunchy, “a small exe packer primarily meant for 64k intros”. It rewrites x86 code before compressing it so that it packs better, and its unpacker is slow, which does not matter for a 64K intro. Giesen wrote that it had saved “a few extra kilobytes - say, 10 or so” on some intros. Quílez’s account of building his 64K intro 195/95/256 (2005) shows the rest of the workflow: compiler flags chosen to keep the C runtime out, such as /QIfist to avoid calls to _ftol(), and kkrunchy at the end. The Windows build came in under 64K; builds for other systems, without kkrunchy or those flags, were about 75 KB.

Crinkler, first released in July 2005 by Aske Simon Christensen (Blueberry of Loonies) and Rune L. H. Stubbe (Mentor of TBC), is built for 4K intros. Its manual describes what came before. Coders compressed their 4K intros with the Cabinet tool that came with Windows and renamed the result as a batch file that unpacked the program to disk, ran it and deleted it again. These tricks broke so often that groups shipped a larger “compatible” version, and “for a time, it seemed that the term ‘4k intro’ meant ‘4k on the compo machine’ intro”. Crinkler replaces the linker instead of packing its output. It compresses with context modelling, which is “extremely slow, but this is of little importance when only 4 kilobytes need to be compressed”. It imports each Windows function by a 4-byte hash of its name, and it hides part of its decompressor in parts of the EXE header that Windows ignores. Since 2015 a /TINYHEADER option has offered a smaller decompressor for 1K intros. Elevated was packed with Crinkler. The source code of Crinkler and of kkrunchy has since been published on GitHub, kkrunchy’s in farbrausch’s 2012 release of its tools.

Every byte twice

At 256 bytes and below, compression gives way to hand-written machine code in which bytes do more than one job. A Mind Is Born starts with a one-line BASIC program, 54271 SYS2225, that starts the machine code. The line number is no accident: 54271 is $D3FF in hexadecimal, a constant that the code needs stored at that very spot. The program then copies itself into zero page, and when the music ends it jumps through the reset vector, so the C64’s own start-up sequence silences the sound and brings back the C64’s start-up screen as the demo’s last scene.

HellMood’s Memories, which won the PC 256-byte competition at Revision 2020, packs a sequence of effects, from checkerboards to a ray-cast tunnel, and MIDI music into 256 bytes. It sends notes on MIDI channel 3 because the MIDI “change instrument” command for that channel is the byte $C3, which the x86 processor also reads as RET, the instruction that returns from a subroutine. One byte serves as both.

On the Commodore 64

On the Commodore 64 the discipline is documented in the authors’ own words. In summer 2001 an 8-bit minigame contest drew “thirty entries for the C64, Spectrum, Amstrad, and Atari 8-bit” in 512-byte and 2K classes, and C=Hacking issue 21 (February 2002) printed six postmortems under the title “The Art of the Minigame”. Its introduction sets out the discipline: “Whereas many of us are used to optimizing programs for cycle-efficiency, optimizing programs for byte-efficiency turns out to be very different”, and the framework is to “put stuff in zero-page, take advantage of default zero-page values, take advantage of the kernal, always know the register values, and reuse as much code as possible”. Zero-page instructions are two bytes instead of three; a zero-page location that the machine already leaves at zero saves the four bytes of LDA #0 / STA; and Mark Seelye’s “injections” put an STX zp into an earlier routine where X is known to be zero, instead of clearing the location where it is used.

Olofsson’s note on when to pack is the useful rule of thumb: “at around 700 bytes or so compression starts to make sense – pucrunch breaks even around there somewhere”. Pucrunch itself is Pasi Ojala’s 1998 design, described in C=Hacking 17 as a “Hybrid LZ77 and RLE compressor” whose decompressor “uses no extra memory”; Ojala tried a Huffman back end and dropped it when “the gain was reduced to only about 3% after accounting the extra code and the Huffman tree”. Codebase64’s 2016 benchmark, run on the files of the demo Pearl for Pigs, shows the later generation — Exomizer, Subsizer, Doynamite, ByteBoozer, Bitfire — packing to 45–48% of input against pucrunch’s 54%, with depacking speed the trade: ByteBoozer 2.0 unpacks the first test file in 22 frames, Exomizer in 58 to 79.

See also

• Demo scene
• Elevated
• fr-08: .the .product
• farbrausch
• iq
• Procedural generation
• Compression
• Run-length encoding