The Work That Never Happens

There is a twelve-line function in the Quake III source that computes an inverse square root by lying to the hardware about what a number is. It carries the comments "evil floating point bit level hacking" and "what the fuck?" It is the most quoted fragment of game code ever written. John Carmack did not write it.

the denial

In April 2004, Carmack answered an email about it. "Not me, and I don't think it is Michael. Terje Matheson perhaps?" The best current attribution is Greg Walsh, an Ardent and Xerox PARC veteran, who described writing it himself.¹ The function ships in code/game/q_math.c, lines 552 to 568, both comments intact. The denial is on the record. The myth is not.

Why the myth persists is the interesting part. The hack compresses into legend: one magic constant, 0x5f3759df, one Newton step, a profane comment. It is genius in the shape of a punchline. The actual artifacts resist that shape. They are architectural, spread across files, and most of them do their work by making other work not happen. The record keeps the wrong souvenir.

the flicker

Quake, 1996. The engine's entire animated lighting system is twelve text strings, and they do not live in engine C. They live in QuakeC, in world.qc, inside worldspawn:²

QW/progs/world.qc, lines 307-337 (excerpt)

// 0 normal
lightstyle(0, "m");
// 1 FLICKER (first variety)
lightstyle(1, "mmnmmommommnonmmonqnmmo");
// 3 CANDLE (first variety)
lightstyle(3, "mmmmmaaaaammmmmaaaaaabcdefgabcdefg");
// 4 FAST STROBE
lightstyle(4, "mamamamamama");
// 9 SLOW STROBE
lightstyle(9, "aaaaaaaazzzzzzzz");
// 10 FLUORESCENT FLICKER
lightstyle(10, "mmamammmmammamamaaamammma");

Each letter a through z is a brightness step. Every frame, the client runs this:

WinQuake/r_light.c, line 33

void R_AnimateLight (void)
{
	int			i,j,k;
// light animations
// 'm' is normal light, 'a' is no light, 'z' is double bright
	i = (int)(cl.time*10);
	for (j=0 ; j<MAX_LIGHTSTYLES ; j++)
	{
		if (!cl_lightstyle[j].length)
		{
			d_lightstylevalue[j] = 256;
			continue;
		}
		k = i % cl_lightstyle[j].length;
		k = cl_lightstyle[j].map[k] - 'a';
		k = k*22;
		d_lightstylevalue[j] = k;
	}
}

That is the whole system. Time is the only input; flicker emerges from indexing a string. The lightmap builder multiplies every surface's light values by the result, so a fluorescent tube gutters and a candle breathes with zero per-frame geometry work. Twelve strings and five lines of code, and every light in the level animates forever.

the scroll

Commander Keen, 1990. The EGA card could not redraw a 320 by 200 screen fast enough to scroll smoothly, so Carmack moved scrolling into the hardware: the CRTC start register for coarse shifts, the Horizontal Pel Panning register for sub-byte shifts. Scrolling cost zero pixel writes. When the virtual screen reached its edge, the engine jolted: it compared tile IDs between the current and recentered states and redrew only the ones that had changed. Forty tiles out of two hundred fifty. Sixteen percent of the screen.³

Keen 4 through 6 dropped the jolt entirely. Keep panning, redraw only the leading edge of tiles, and let the screen wrap around at the 64K aperture edge. It worked on the hardware's luck: on later cards with more video memory, the wrap did not happen and scrolling fell into uninitialized memory. Carmack, 2020: "just keep panning and redrawing the leading edge, letting the screen wrap around at the 64k aperture edge."

The honest ledger flags this one. Keen's source was never released, so no snippet is verifiable. The attribution is historical: Sanglard's reconstruction, Romero's account of the overnight build at Softdisk in September 1990, Tom Hall recreating Mario's first level as Dangerous Dave in Copyright Infringement. But the shape is unmistakable: make the redraw proportional to what changed, not to the size of the screen. Every modern compositor does this now.

the ray

Wolfenstein 3D, 1992. "I was 21 years old when I wrote most of the code." One ray per screen column across a 64 by 64 grid, all in 16.16 fixed point. No floating point unit, no division. Precomputed steps per quadrant, interleaved vertical and horizontal grid walks until a wall tile is hit, and the fractional intercept becomes the texture column. The inner loop is assembly, and the quadrant setup is self-modifying code: the jump opcode is patched in place, so the march carries no branch overhead for direction.⁴

WOLFSRC/WL_DR_A.ASM, AsmRefresh, the inner ray march

; CORE LOOP!
vertentry:
 test [BYTE tilemap+si],0ffh ; tilehit = *((byte *)tilemap+xspot);
 jnz hitvert
passvert:
 mov [BYTE spotvis+si],1
 add bx,[xtilestep]
 mov ax,[WORD ystep]
 add [WORD yintercept],ax
 adc dx,[WORD ystep+2]
 mov si,bx
 shl si,6
 add si,dx ; xspot = (xtile<<6)+yinttile
 jmp vertcheck

Seventy frames per second of textured 3D on a machine with no graphics processor, from integer arithmetic and a jump table. Carmack's own retrospective names the decision: ray casting was the pragmatic choice, because he was not yet experienced enough to write a polygon engine. The constraint did the designing.

the tree

Doom, 1993. The level is a binary space partition, and rendering it is one recursive function:⁵

linuxdoom-1.10/r_bsp.c, line 552

void R_RenderBSPNode (int bspnum)
{
    node_t*	bsp;
    int		side;

    // Found a subsector?
    if (bspnum & NF_SUBSECTOR)
    {
	if (bspnum == -1)
	    R_Subsector (0);
	else
	    R_Subsector (bspnum&(~NF_SUBSECTOR));
	return;
    }

    bsp = &nodes[bspnum];

    // Decide which side the view point is on.
    side = R_PointOnSide (viewx, viewy, bsp);

    // Recursively divide front space.
    R_RenderBSPNode (bsp->children[side]);

    // Possibly divide back space.
    if (R_CheckBBox (bsp->bbox[side^1]))
	R_RenderBSPNode (bsp->children[side^1]);
}

One cross product per node decides which side the viewpoint is on. The near side is drawn unconditionally. The far side is visited only if its bounding box survives a constant-time occlusion test. Painter's algorithm with no depth buffer: a 33 MHz 486 never draws what it cannot see.

Floors and ceilings get the same treatment. R_FindPlane merges every subsector sharing a height, a texture, and a light level into one flat surface, drawn as horizontal spans in the gaps the walls leave behind. The merge table holds 128 entries, which is why an ambitious map dies with "R_FindPlane: no more visplanes."

the cache and the edge

Quake, 1996. Two data structures do the heavy lifting, and the honest ledger splits the credit. Carmack designed the architecture; Michael Abrash implemented it, including the x86 assembly, and wrote the definitive documentation. Abrash, in the Black Book: "John faced several fundamental design issues while architecting Quake."⁶

The surface cache composites each visible surface's texture and lightmap exactly once, into reusable memory keyed on texture, light values, and mip level. Lighting is decoupled from polygon vertices, so lightmap detail is free. The edge list collects every potentially visible polygon edge once per frame and scans them into spans with zero overdraw. This pair is the whole answer to how Quake ran on a 486.

the bit vector

Quake II, 1997. Every cluster in the map stores a run-length-encoded bit vector of the clusters potentially visible from it. Decoding it is fifteen lines:⁷

qcommon/cmodel.c, line 1530

void CM_DecompressVis (byte *in, byte *out)
{
	...
	do
	{
		if (*in)
		{
			*out_p++ = *in++;
			continue;
		}

		c = in[1];
		in += 2;
		if ((out_p - out) + c > row)
		{
			c = row - (out_p - out);
			Com_DPrintf ("warning: Vis decompression overrun\n");
		}
		while (c)
		{
			*out_p++ = 0;
			c--;
		}
	} while (out_p - out < row);

A quadratic visibility problem becomes a pointer lookup. If a cluster has no visibility data, the decoder fills the row with ones: everything is visible, the safe default. The renderer never tests a polygon it cannot see.

the reverse

Doom 3 era, early 2000. Classic stencil shadow volumes count depth passes and break when the camera sits inside the volume, because the near plane clips the geometry. The reverse counts depth failures instead: back faces increment the stencil where hidden behind geometry, front faces decrement. Mathematically identical. The failure case becomes impossible, so there is nothing to fix geometrically.⁸

The name is the community's, coined after his .plan post, not his. Creative Labs had filed a patent on the same technique in 1999, and id licensed it for the retail game. The GPL release does not contain the original: the README states plainly that the depth-fail method is not included, and the repo ships his 2011 rewrite instead. His summary of the rewrite: "the workaround added four lines of code and changed two. This demonstrates the idiocy of the patent." The patent expired in October 2019.

the abolition

Now the pattern is visible. None of these make the work fast. They delete it.

Scrolling is done by hardware registers, so the redraw is proportional to change. Lighting animation is a string indexed by time, so there is no per-frame lighting computation. Visibility is precomputed and decoded, so the renderer tests nothing it cannot see. Draw order is one cross product per node. Shadows are redefined so the broken case cannot occur.

This is the actual signature, and it explains why the legend misfires. A deletion leaves no souvenir. There is no constant to quote from a string lookup, no profanity in a tree walk. The myth needs genius in the shape of a punchline, so it picked the one artifact built like one. That one is not his.

coda

The famous comment is "what the fuck?" It survives because it is quotable, and it belongs to a function its supposed author denied writing. The real corpus is quieter. Somewhere in it, a fluorescent tube is still guttering because a letter in a string says so, and a 486 is still not drawing what it cannot see. The work that never happens is the work he did.