How does Duff's device work?
There are some good explanations elsewhere, but let me give it a try. (This is a lot easier on a whiteboard!) Here's the Wikipedia example with some notations.
Let's say you're copying 20 bytes. The flow control of the program for the first pass is:
int count; // Set to 20
{
int n = (count + 7) / 8; // n is now 3. (The "while" is going
// to be run three times.)
switch (count % 8) { // The remainder is 4 (20 modulo 8) so
// jump to the case 4
case 0: // [skipped]
do { // [skipped]
*to = *from++; // [skipped]
case 7: *to = *from++; // [skipped]
case 6: *to = *from++; // [skipped]
case 5: *to = *from++; // [skipped]
case 4: *to = *from++; // Start here. Copy 1 byte (total 1)
case 3: *to = *from++; // Copy 1 byte (total 2)
case 2: *to = *from++; // Copy 1 byte (total 3)
case 1: *to = *from++; // Copy 1 byte (total 4)
} while (--n > 0); // N = 3 Reduce N by 1, then jump up
// to the "do" if it's still
} // greater than 0 (and it is)
}
Now, start the second pass, we run just the indicated code:
int count; //
{
int n = (count + 7) / 8; //
//
switch (count % 8) { //
//
case 0: //
do { // The while jumps to here.
*to = *from++; // Copy 1 byte (total 5)
case 7: *to = *from++; // Copy 1 byte (total 6)
case 6: *to = *from++; // Copy 1 byte (total 7)
case 5: *to = *from++; // Copy 1 byte (total 8)
case 4: *to = *from++; // Copy 1 byte (total 9)
case 3: *to = *from++; // Copy 1 byte (total 10)
case 2: *to = *from++; // Copy 1 byte (total 11)
case 1: *to = *from++; // Copy 1 byte (total 12)
} while (--n > 0); // N = 2 Reduce N by 1, then jump up
// to the "do" if it's still
} // greater than 0 (and it is)
}
Now, start the third pass:
int count; //
{
int n = (count + 7) / 8; //
//
switch (count % 8) { //
//
case 0: //
do { // The while jumps to here.
*to = *from++; // Copy 1 byte (total 13)
case 7: *to = *from++; // Copy 1 byte (total 14)
case 6: *to = *from++; // Copy 1 byte (total 15)
case 5: *to = *from++; // Copy 1 byte (total 16)
case 4: *to = *from++; // Copy 1 byte (total 17)
case 3: *to = *from++; // Copy 1 byte (total 18)
case 2: *to = *from++; // Copy 1 byte (total 19)
case 1: *to = *from++; // Copy 1 byte (total 20)
} while (--n > 0); // N = 1 Reduce N by 1, then jump up
// to the "do" if it's still
} // greater than 0 (and it's not, so bail)
} // continue here...
20 bytes are now copied.
Note: The original Duff's Device (shown above) copied to an I/O device at the to address. Thus, it wasn't necessary to increment the pointer *to. When copying between two memory buffers you'd need to use *to++.
Does Duff's Device work in other languages?
You can do it in any language that supports computed GOTO statements (Fortran, some BASICs, etc.)
Can I use Duff's Device on an array in C?
Please, please don't use Duff's device. A thousand maintenance programmers will thank you. I used to work for a training company where someone thought it funny to introduce the device in the first ten pages of their C programming course. As an instructor it was impossible to deal with, unless (as the guy that that wrote that bit of the course apparently did) you believe in "kewl" coding.
Needless to say, I had the thing expunged from the course, ASAP.
Revising the syntax of Duff's device - Is this legal C/C++?
Looking at the C++11 Standard, the part of the code I think you're asking about would be allowed. Have you tried it?
The rule I see that's most applicable is:
Note: Usually, the substatement that is the subject of a switch is compound and
caseanddefaultlabels appear on the top-level statements contained within the (compound) substatement, but this is not required.
In fact, this means you could get rid of the braces around the do-while, and write
int n = (count + 7) / 8;
switch (count % 8) do
{
case 0: *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);
However, this line is NOT valid C++:
register n = (count + 7) / 8;
C++ does not allow default-int, the type of a variable must be specified or inferred.
Oh here, fix the number of iterations without breaking formatting:
int n = 1 + count / 8;
switch (count % 8) 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++;
case 0: ;
} while(--n > 0);
How can Duff's device code be compiled?
A simple explanation of why Duff's Device compiles is that the syntax of the switch statement isn't particularly specific about the form that the switch statement block might need to take. There are a few restrictions, and a couple of things permitted in the controlled statement that aren't permitted outside a switch (the case and default labels). But other than that, the controlled statement is just any other statement, with the likelihood that there are labels for the switch to target.
Here's the syntax from C99:
switch ( expression ) statement
Beyond the syntax, the standard imposes a few constraints:
- the controlling expression must have an integer type
- there are restrictions about where VLAs can occur in the switch statement
caselabel expressions must be integer constant expressions- there cannot be duplicate
caselabel expressions ordefaultlabels
Other than that, any construct permitted in a statement block should be permitted in the controlled statement (with the addition that case and default labels are OK). Remember that case and default are just labels that the switch jumps to based on the controlling expression and the case label expressions. As Potatoswatter says, switch is just a computed goto. So just like goto can jump into the middle of a loop, so can switch.
Also, I think that the cases where you might see a benefit from Duff's Device are pretty rare today (I think they were rare even in the 1980's). Don't forget that Tom Duff himself said the following in his description:
- "Disgusting, no?"
- "I feel a combination of pride and revulsion at this discovery."
Even more than when it was initially described, Duff's Device should be considered more of a curiosity than a tool to use.
Writing a macro for Duff's Device
Something like this:
#define LAYDUFF(x, y) \
case ((0 ## x ## y) + 1) : *to++ = *from++
#define SEVEN_AT_ONCE(x) \
LAYDUFF(x,6); \
LAYDUFF(x,5); \
LAYDUFF(x,4); \
LAYDUFF(x,3); \
LAYDUFF(x,2); \
LAYDUFF(x,1); \
LAYDUFF(x,0)
#define EIGHT_AT_ONCE(x) \
LAYDUFF(x,7); \
SEVEN_AT_ONCE(x)
int duffs_device(char *from, char *to, int count)
{
{
int n = (count + 31) / 32;
switch(count % 32) {
case 0: do { *to++ = *from++;
SEVEN_AT_ONCE(3);
EIGHT_AT_ONCE(2);
EIGHT_AT_ONCE(1);
EIGHT_AT_ONCE(0);
} while(--n > 0);
}
}
return count;
}
will expand into
case ((036) + 1) : *to++ = *from++; // = 31
...
case ((000) + 1) : *to++ = *from++; // = 1
Update:
Or, you can rewrite the first macro:
#define LAYDUFF(x, y) \
case (8 * x + y + 1) : *to++ = *from++
Which is basically the same, except that it doesn't use octal numbers.
duff device not working
you are copying from b to a, but you want to copy from a to b.
change every *a++ = *b++; to *b++ = *a++;
you can also do just memcpy(b, a, length * sizeof *a);
Related Topics
Does Throw Inside a Catch Ellipsis (...) Rethrow the Original Error in C++
What Is the Ascii Value of Eof in C
Does Std::Mutex Create a Fence
Pointers to Virtual Member Functions. How Does It Work
Understanding Region of Interest in Opencv 2.4
C++ - How to Find the Length of an Integer
Why Isn't Rvo Applied to Base Class Subobject Initialization
Long Long Implementation in 32 Bit MAChine
Same Class Name in Different C++ Files
Use of Typename Keyword with Typedef and New
How to Detect Whether Windows Is Shutting Down or Restarting
How to Enable_Shared_From_This of Both Parent and Derived