How does Duff’s device work?

by

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++.

More Related Contents:

  1. C: Why is counter not resetting to 0 in for loop [closed]
  2. In a function with return type void, what is the meaning of the statement return;
  3. Why is the output of this program 0? [closed]
  4. C: What is the output of the following code? And please explain [duplicate]
  5. With arrays, why is it the case that a[5] == 5[a]?
  6. #pragma pack effect
  7. Why does strncpy not null terminate?
  8. What is a “callback” in C and how are they implemented?
  9. Is there a standard function in C that would return the length of an array?
  10. Proper usage of realloc()
  11. How is malloc() implemented internally? [duplicate]
  12. C pointers : pointing to an array of fixed size
  13. How can I simplify this working Binary Search code in C?
  14. Tokenizing strings in C
  15. C program to check little vs. big endian [duplicate]
  16. Getting each individual digit from a whole integer
  17. Why doesn’t scanf need an ampersand for strings and also works fine in printf (in C)?
  18. How can I create a dynamically sized array of structs?
  19. GCC fatal error: stdio.h: No such file or directory
  20. Type of #define variables
  21. Strings and character with printf
  22. Why doesn’t GCC optimize structs?
  23. Classic C. Using pipes in execvp function, stdin and stdout redirection
  24. Writing to a closed, local TCP socket not failing
  25. convert an integer number into an array
  26. Why fork() twice [duplicate]
  27. Providing/passing argument to signal handler
  28. Compiler changes printf to puts
  29. What can cause a “Resource temporarily unavailable” on sock send() command
  30. In C, is it good form to use typedef for a pointer?

Leave a Comment