How Duff’s Device Works

I like C, but I have to admit that, sometimes, “The Old Man of Programming” can be a bit of a killjoy. This is one of the most exciting eras in computer history, but lately, C’s acting like he doesn’t evenwant to have a good time. While the cool kids like Ruby and Haskell are living it up, C’s over in the corner obsessing over bits and bytes and memory alignment and pointers and the stack and machine architecture and unreachable allocations and multiple indirections…and it’s…kind of a buzzkill. You want to tell him, “Dude! Lighten up! This is supposed to be fun!”

But of course C can’t relax. He’s holding the entire computing universe on his shoulders, after all. It’s not turtles all the way down — it’s turtles all the way down, then C. Not a lot of room for fun underneath that, is there?

Is there?

Well. Here’s the secret: C does let loose sometimes. And after being bottled up for so long, when the release finally does come, it’s pretty much an F5 of crazy.

Take for example a little thing called Duff’s Device:

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);
	}
}

Okay, what you have here is your basic switch statement merged with a do loop. Pretty messed up, right? And just to be clear: this is totally valid C.

Huh?

If we look at the Jargon File entry, we see that the purpose of Duff’s Device is to continuously copy data into a memory-mapped video register. Unfortunately, there’s no explanation of how it works, other than a brief mention of C’s default fall-through property. Call me crazy, but fall-through is about the only part of Duff’s Device that actually makes sense. What about the fact that there’s a friggin do loop embedded in a switch statement? Or the fact that case labels are, in turn, embedded inside the do? This thing is so caught up in itself it makes a teenager seem reflective.

However, since I started working on Tenacious C, I’ve gotten real intimate with the C grammar, and with C in general, and I can report to you that Duff’s Device isn’t as horrific as it appears. In fact, the reason it’s so shocking is because most people don’t really understand switch statements in C.

Switch Statements In General

If you’re like me, you’ve always visualized a switch as a glorified if-then-else block.

It makes sense to say that…

        switch(x) {
        case 1:
                printf("something1\n");
                break;
        case 2:
                printf("something2\n");
        case 3:
                printf("something3\n");
                break;
        case 4:
                printf("something4\n");
                break;
        }

…is pretty much equivalent to:

        if(x == 1)
                printf("something1\n");
        else if(x == 2 || x == 3)
        {
                if(x == 2)
                        printf("something2\n");
                 printf("something3\n");
        }
        else if(x == 4)
                printf("something4\n");

Right? You can see with your own eyes that the two statements produce the same result. I even omitted a break to ensure that our old friend Mr. Fall-Through didn’t break (har, har) the model. For workaday programming, this is a perfectly valid way of thinking about a switch.

But it breaks down in Duff’s Device.

If you’re in the “switch as if-then-else” frame of mind when you see Duff’s Device, your brain will try to overlay a do loop over an if-then-else block. But your brain will resist, because what it’s trying to do is impossible…and that’s where a lot of the confusion over Duff’s Device arises from.

Switch Statements In C

Here’s how a switch really works.

You type this…

        switch(x) {
        case 1:
                printf("something1\n");
                break;
        case 2:
                printf("something2\n");
        case 3:
                printf("something3\n");
                break;
        case 4:
                printf("something4\n");
                break;
        }

        if(x==1) goto label_case1;
        if(x==2) goto label_case2;
        if(x==3) goto label_case3;
        if(x==4) goto label_case4;
        goto label_finish;

        label_case1:
                printf("something1\n");
                goto label_finish;
        label_case2:
                printf("something2\n");
        label_case3:
                printf("something3\n");
                goto label_finish;
        label_case4:
                printf("something4\n");
                goto label_finish;

        label_finish:
                /* continue with the rest of the program */

See how that works? To C, a switch is really a bank of cascading gotos. That’s why case labels have to be constant, because C generates goto labels from them at compile time. And unlike an if-then-else block, goto labels can easily be intertwined with a do loop. In fact, let’s go ahead and rewrite Duff’s Device using this model:

send(short *to, short *from, int count)
{
	int n=(count+7)/8;

        if(count%8 == 0) goto label_case0;
        if(count%8 == 1) goto label_case1;
        if(count%8 == 2) goto label_case2;
        if(count%8 == 3) goto label_case3;
        if(count%8 == 4) goto label_case4;
        if(count%8 == 5) goto label_case5;
        if(count%8 == 6) goto label_case6;
        if(count%8 == 7) goto label_case7;

	label_case0:	do{	*to = *from++;
	label_case7:		*to = *from++;
	label_case6:		*to = *from++;
	label_case5:		*to = *from++;
	label_case4:		*to = *from++;
	label_case3:		*to = *from++;
	label_case2:		*to = *from++;
	label_case1:		*to = *from++;
		}while( --n>0);
}

Sweet! The switch is gone, the control flows in a way that makes sense, and the do loop runs without any problems. So…case closed, right?

Almost.

C — An Old Man, But A Liberal At Heart

You remember at the top, I had two questions about Duff’s Device:

1. How do you embed a friggin do loop inside a switch statement?
2. How are case labels, in turn, embedded inside the do?

Well, we just answered question two. (They’re not case labels per se, but goto labels.)

Question one is trickier. Question one depends on familiarity with a certain quirk of the C language. As far as I know, no other high level language in existence, with the exception of C++, gives you the freedom C does to cram whatever the hell you want inside a switch. The only demand C makes is that the switch statement be followed by a statement. What’s a statement? Let’s look at the grammar:

statement
	: labeled_statement
	| compound_statement
	| expression_statement
	| selection_statement
	| iteration_statement
	| jump_statement
	;

So you can have a labeled statement (a single case or goto label), a compound statement (any number of statements enclosed by braces. This is by far the most common), an expression statement (any random expression, for instance an assignment), a selection statement (an if statement), an iteration statement (for, while, do), or a jump statement (goto, break, continue, return).

Duff’s device employs a do loop inside a switch.

switch(x)        /* notice that enclosing braces aren't necessary */
do{
        ....
}while(x > 100);

But just for fun we can try a for loop…

int y;
switch(x)        /* notice that enclosing braces aren't necessary */
for(y=x; y<10; y++{
        ....
}

...or an if statement.

int a;
int b;
switch(x)        /* notice that enclosing braces aren't necessary */
        if(a == b)
        {
        ....
        }

Try compiling those examples. You'll see they work. (Obviously, you'll have to replace the ellipses with real code.) Now, is this something you'll ever use in practice? Well, Tom Duff found a use for it. So who knows? But I'm leaning toward...nah.

Conclusion

So there you have it. Duff's Device is a truly bizarre programming construct, made possible by C's leniency when it comes to switch statements, and by the cascading-goto nature of the switch itself. Any questions, feel free to ask in the comments.

Hat tip: thanks to Mike Gleen for catching a small bug in the example code.

Source: