prev up next   top/contents search

comp.lang.c FAQ list · Question 20.35

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

prev up next   contents search
about this FAQ list   about eskimo   search   feedback   copyright

Hosted by Eskimo North