Okay, it's yet another programming writeup. The source code for this mutant is now below this writeup, in everyone's Jargon File thing. If you know C and you're not familiar with the Device, it'd be best to have a look at that first and maybe keep it in front of you while reading the latter part of this one. If you don't know C... umm... This turns out to be less weird than it looks at first blush, but it still might not be your ideal choice for a place to start learning.

Here are some of Mr. Duff's comments on the Device, from his famous USENET post announcing it. I enjoyed them (But what about that Fermatically tantalizing "[other] revolting way to use switches", eh? Someday I'll track this guy down and beat it out of him...).

"Disgusting, no? But it compiles and runs just fine. I feel a combination of pride and revulsion at this discovery. If no one's thought of it before, I think I'll name it after myself.

"It amazes me that after 10 years of writing C there are still little corners that I haven't explored fully. (Actually, I have another revolting way to use switches to implement interrupt driven state machines but it's too horrid to go into.)

"Many people (even bwk?) have said that the worst feature of C is that switches don't break automatically before each case label. This code forms some sort of argument in that debate, but I'm not sure whether it's for or against."

I'm still contemplating the Device itself. It's worse than those brain teasers in the PCLint ads.

The first question is, what happens when you hit the while end of a do loop without having ever gotten to the do? That's what the thing will do if count is not evenly divisible by eight.

Well, think about it 1: It works, therefore it must be executing the loop as if the do had been encountered, otherwise when ((count = 15) % 8) == 7, for example, it'd copy exactly seven bytes and no more. That'd be useless when we've got count telling us to copy 15 bytes. We're just jumping into the loop in medias res; the code looks extremely weird because of all the case labels, but they're really almost irrelevant; they're just entry points into the loop, used only on the first iteration. Each time the function is called, exactly one of them is used, and that one is used only once. The labels seem more important than they are because they take up so much space on the page. It's also slightly counterintuitive to think of handling an odd number of things by starting late rather than by ending early, but that's really the only thing happening here.

The code looks scarier than it really is. Written in a language with a line goto instead of switch, this code probably wouldn't have quite the reputation it has in C becaue it would be (bizarrely enough) more readable! Heh heh heh. Then again, a concept that can be more readably expressed in Fortran than in C is an oddity, on that basis alone.

I suddenly fear that I may not be grokking, but it all makes sense to me this way (or seems to). Incidentally, it produces identical output if the do { is moved back before case 0, for what it's worth. Was that legal in K&R C (the Device dates from 1983)? I would imagine so; there's no reason why it wouldn't be, since in the compiled code that case label won't even be there. Since the same is true of do {, I can't think of any reason why it should matter in the ( count % 8 ) == 0 case. In the other cases, we don't even touch that code. So why is it where it is? Good question. I might be missing something subtle, but most probably, that's as good a place for it as any. It's a purely aesthetic decision.

1 Bear in mind the fact that this is C: do is nothing but a note to the compiler saying "the while should jump to whatever comes after me in the source". Higher-level languages might pretend that do is actually a "thing" of some kind for which code is generated, but C tells it like it is.

dub dub dub = D = dumb terminal

Duff's device n.

The most dramatic use yet seen of fall through in C, invented by Tom Duff when he was at Lucasfilm. Trying to bum all the instructions he could out of an inner loop that copied data serially onto an output port, he decided to unroll it. He then realized that the unrolled version could be implemented by interlacing the structures of a switch and a loop:

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

Shocking though it appears to all who encounter it for the first time, the device is actually perfectly valid, legal C. C's default fall through in case statements has long been its most controversial single feature; Duff observed that "This code forms some sort of argument in that debate, but I'm not sure whether it's for or against." Duff has discussed the device in detail at http://www.lysator.liu.se/c/duffs-device.html. Note that the omission of postfix ++ from *to was intentional (though confusing). Duff's device can be used to implement memory copy, but the original aim was to copy values serially into a magic IO register.

[For maximal obscurity, the outermost pair of braces above could actually be removed -- GLS]

--The Jargon File version 4.3.1, ed. ESR, autonoded by rescdsk.

Log in or register to write something here or to contact authors.