Commissioned for this museum · after Tom Duff's device, Lucasfilm, 1983

The Loop That Starts in the Middle

C·1983·23 lines·687 bytes

/*
 * Copy `count` shorts to a memory-mapped output register.
 *
 * Tom Duff, Lucasfilm, 1983. The loop is unrolled eight times to cut the
 * cost of the test at the bottom -- and the leftover, the count modulo
 * eight, is dealt with by jumping into the middle of the unrolled body.
 */
void send(short *to, short *from, int count)
{
    int n = (count + 7) / 8;

    switch (count % 8) {
    case 0: do { *to = *from++;
    case 7:      *to = *from++;
    case 6:      *to = *from++;
    case 5:      *to = *from++;
    case 4:      *to = *from++;
    case 3:      *to = *from++;
    case 2:      *to = *from++;
    case 1:      *to = *from++;
               } while (--n > 0);
    }
}

Curator’s note

Read it once and it looks like a mistake. A switch opens, and the first case opens a do loop — and then the remaining cases appear *inside* that loop, interleaved with its body. The braces do not nest the way the indentation suggests, and most people's first reaction is that this cannot possibly be a legal program.

It is legal, and it is legal for a dull reason. C says a case label may sit in front of any statement anywhere inside the switch, including a statement that happens to be in the middle of a loop. The switch jumps to a label; the loop then runs as a loop, from wherever the jump landed. Two ordinary mechanisms, put together in a way nobody intended.

What it buys is the cost of the test at the bottom of a copying loop. Copy one short at a time and you pay for --n > 0 once per short. Unroll the body eight times and you pay it once per eight — but then you have to deal with the remainder, and the usual way is a second little loop before or after the big one. Duff's arrangement deals with the remainder by *entering* the unrolled body partway down, so the leftovers happen on the first pass and every pass after that is a full eight.

Tom Duff wrote it at Lucasfilm in 1983 and said of it: "This code forms some sort of argument in that debate, but I'm not sure whether it's for or against."

Checked, for every count from one to two hundred: it copies exactly that many.