Sprite crunching

A Commodore 64 sprite is 21 lines tall, and once the VIC-II has started drawing one it will not stop until all 21 are done. That rule is what limits sprite multiplexing: a sprite cannot be reused lower down the screen until it has finished. Sprite crunching breaks the rule. Clear a sprite’s Y-expand bit on one particular clock cycle of a raster line and the chip’s internal sprite counter jumps to a new value: sometimes forwards, sometimes backwards, and only occasionally by the usual three bytes. Chain the jumps carefully and a sprite can end after 17 lines, or loop over the same four lines for as long as you like.

Linus Åkesson, who built a whole demo part on it in 2016, called it “perhaps the most bizarre VIC chip bug discovered to this day” and noted that “many programmers consider it to be too complicated to be useful in practice”. The Codebase64 wiki puts it more bluntly: “This is nothing you do if you don’t really need it.”

How the VIC-II counts its way through a sprite

Christian Bauer’s 1996 description of the VIC-II sets out the machinery, with cycle numbers for the PAL 6569. Each sprite’s 63 bytes of data are read three bytes per raster line. Two 6-bit counters keep the place: MCBASE holds the offset of the row being displayed, and MC is loaded from it at the end of each line and counts up by one as each of the three bytes is fetched. One expansion flip-flop per sprite decides whether MCBASE moves on:

1. While the sprite’s bit in $D017, the Y-expand register, is clear, the flip-flop is held set.
2. In cycle 55, near the end of the line, the flip-flop is inverted if the bit is set.
3. In cycles 15 and 16 of the next line, MCBASE advances by three, but only if the flip-flop is set. When MCBASE reaches 63 the sprite’s DMA is switched off and it ends.

An unexpanded sprite therefore steps 0, 3, 6 … 60, 63: 21 lines. A Y-expanded sprite only advances on every other line, so each row appears twice. Sprite stretching works by flipping the bit at a harmless point in the line so that a row repeats again.

Crunching hits the same machinery at the one moment that is not harmless. The sprite’s bit must be set and its flip-flop reset, so the chip is about to leave MCBASE where it is. If the program clears the bit on cycle 15, the flip-flop becomes set while that decision is half made. Bauer noticed that MCBASE then advanced by only one instead of three, so every later row was read one byte out of step. Åkesson gives the general rule: MCBASE receives “the following very peculiar value”:

((MC | MCBASE) & $15) | ((MC & MCBASE) & $2A)

At that point in the line MC is three ahead of MCBASE, so the new offset mixes the old and new values bit by bit, alternately ORed and ANDed. From offset 0 the result is 1, which is Bauer’s case. From $0F it is $17, a jump of 8. From $1E it is $15, a jump of 9 back. From $3D it is $15, 40 bytes back. The VICE emulator uses the same expression in its VIC-II code.

The program then sets the bit again before cycle 55 if it wants to crunch on the next line too, or leaves it clear to let the sprite carry on normally.

Why a crunched sprite does not stop

The VIC-II switches a sprite off only when MCBASE equals 63 exactly. A normal sprite lands on 63 because it moves in steps of three from 0. As the Codebase64 page explains, a crunch that adds “anything not dividable by 3” leaves the counter on $3D or $3E instead; on the next line it passes 63, wraps round to $00 or $01, and “the sprite will continue to be displayed for some 21 more lines”. To end early, a crunched sprite has to reach $3B and crunch there, or reach $3C and finish normally.

The graphics have to follow the counter. A sprite whose counter goes 0, 3 … $0F, then jumps to $17, reads its eighth line from bytes $17 to $19, which straddle two of the 21 normal rows. The artist’s pixels must be laid out in memory to match the planned route, with unused bytes left where the route skips them.

Pasi Ojala met the effect while writing about sprite stretching for the online magazine C= Hacking, and in March 1993 dismissed it: “I don’t think the distorted counter effect can be used for anything”.

Crossbow’s map

The first known use had come earlier still. In Rutig Banan, the Fairlight demo that won at Light Bålsta Party on 5 November 1989, Pernod crunched once, on a sprite’s third line, with a jump of −1. The sprite then missed its end and was drawn almost three times over. According to the Codebase64 wiki, Y-expanding it and switching graphics banks gave “~120 lines of sprite area to play with”.

Crossbow of Crest took the trick apart. In the demo Krestage (April 1997) he included what Codebase64 calls “exact documentation of what happens on each value of the sprite-graphics-counter when triggering the glitch, hand-haxxored by Crossbow himself”, a table of 64 jumps. Finding “the (probably) shortest path through the table, he managed to shrink the sprites from 21 lines to 17”. He used it to fit more sprites on screen: the scene’s list of records credits Krestage with 144 sprites, against 112 for unshortened ones. Åkesson explains that Crossbow named the effect sprite crunch because he used it to crunch sprites, “make them shorter”, so that the hardware could be reused sooner. HCL of Booze Design suggested “sprite scrambling”, which Åkesson notes “hasn’t caught on”.

The route is short to follow. Starting from 0, the sprite runs normally to $0F, crunches to $17, runs to $29, crunches to $2D and then to $35, runs to $3B and crunches to 63: 17 lines, with only four of them crunched. A commenter on Rutig Banan’s CSDb page made the same count: “just 4 lines of crunching is enough to make the sprite 17 pixels high”. Working through the published table confirms that no route starting from offset 0 ends in fewer lines.

The Codebase64 page that reprints the table ends by inviting someone to beat it: “Can you make a sprite smaller than 17 lines and beat Crossbow? ;D”

Loops instead of endings

The answer turned out to be: do not start from zero. Åkesson points out that 17 is the minimum only “under the assumption that we always have to begin at start”. A sprite whose graphics begin at offset $15 can run normally through $15, $18 and $1B to $1E, crunch there back to $15, and repeat those four lines indefinitely. Booze Design’s Edge of Disgrace (2008) used that four-line loop in a plasma made of 4×4-pixel blocks: instead of writing $D017 twice on every line as a stretcher would, it writes it “twice every 4 lines, saving some life supporting cycles”.

Åkesson went further in Lunatico, which came second at X’2016 on 30 October 2016. Starting from offset $35, he found loops of 1, 13, 14, 17, 18, 19, 20 and 21 lines. The greetings part of the demo draws columns of letters at heights of 14, 17, 19 and 21 lines, and works out which sprites to crunch on each line by reading the sprite-to-background collision register: the rightmost pixel of each sprite row is set where a crunch is due, and a thin stripe of hidden background pixels turns those pixels into collision bits, eight sprites at a time. He called the result Massively Interleaved Sprite Crunch.

See also

• Sprite stretching: the same flip-flop, flipped where it is safe
• Sprite multiplexing
• Stable raster: the cycle-exact timing this needs
• VIC-II
• Crest
• Edge of Disgrace