Q: What is ``Duff's Device''?
A: It's a devastatingly devious way of unrolling a loop, devised by Tom Duff while he was at Lucasfilm. In its ``classic'' form, it was used to copy bytes, and looked like this:
register n = (count + 7) / 8; /* count > 0 assumed */
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);
}
where count bytes
are to be copied
from the array pointed to by from
to the memory location pointed to by to
(which is a memory-mapped device output register,
which is why to isn't incremented).
It solves the problem of handling the leftover bytes
(when count isn't a multiple of 8)
by interleaving a
switch statement
with the loop
which copies bytes 8 at a time.
(Believe it or not, it is
legal
to have case labels buried
within blocks
nested in a switch statement
like this.
In his announcement of the technique to C's developers and the world,
Duff noted that C's switch syntax,
in particular its
``fall through''
behavior,
had long been controversial,
and that
``This code forms some sort of argument in that debate,
but I'm not sure whether it's for or against.'')
Additional links: longer explanation
Hosted by
