learn-c-the-hard-waych24.txt

   Learn C The Hard Way A Learn Code The Hard Way Book
     * Book
     * Comments
     * Video Courses
     * Related Books

   [next] [prev] [prev-tail] [tail] [up]

Chapter 24
Exercise 23: Meet Duff's Device

   This exercise is a brain teaser where I introduce you to one of the
   most famous hacks in C called "Duff's Device", named after Tom Duff the
   "inventor". This little slice of awesome (evil?) has nearly everything
   you've been learning wrapped in one tiny little package. Figuring out
   how it works is also a good fun puzzle.
     __________________________________________________________________

   Note 6: This Is Only An Exercise

   Part of the fun of C is that you can come up with crazy hacks like
   this, but this is also what makes C annoying to use. It's good to learn
   about these tricks because it gives you a deeper understanding of the
   language and your computer. But, you should never use this. Always
   strive for easy to read code.
     __________________________________________________________________

   Duff's device was "discovered" (created?) by Tom Duff and is a trick
   with the C compiler that actually shouldn't work. I won't tell you what
   it does yet since this is meant to be a puzzle for you to ponder and
   try to solve. You are to get this code running and then try to figure
   out what it does, and why it does it this way.
     __________________________________________________________________

   Source 62: ex23.c
   1  #include <stdio.h>
   2  #include <string.h>
   3  #include "dbg.h"
   4
   5
   6  int normal_copy(char *from, char *to, int count)
   7  {
   8      int i = 0;
   9
   10      for(i = 0; i < count; i++) {
   11          to[i] = from[i];
   12      }
   13
   14      return i;
   15  }
   16
   17  int duffs_device(char *from, char *to, int count)
   18  {
   19      {
   20          int n = (count + 7) / 8;
   21
   22          switch(count % 8) {
   23              case 0: do { *to++ = *from++;
   24                          case 7: *to++ = *from++;
   25                          case 6: *to++ = *from++;
   26                          case 5: *to++ = *from++;
   27                          case 4: *to++ = *from++;
   28                          case 3: *to++ = *from++;
   29                          case 2: *to++ = *from++;
   30                          case 1: *to++ = *from++;
   31                      } while(--n > 0);
   32          }
   33      }
   34
   35      return count;
   36  }
   37
   38  int zeds_device(char *from, char *to, int count)
   39  {
   40      {
   41          int n = (count + 7) / 8;
   42
   43          switch(count % 8) {
   44              case 0:
   45              again: *to++ = *from++;
   46
   47              case 7: *to++ = *from++;
   48              case 6: *to++ = *from++;
   49              case 5: *to++ = *from++;
   50              case 4: *to++ = *from++;
   51              case 3: *to++ = *from++;
   52              case 2: *to++ = *from++;
   53              case 1: *to++ = *from++;
   54                      if(--n > 0) goto again;
   55          }
   56      }
   57
   58      return count;
   59  }
   60
   61  int valid_copy(char *data, int count, char expects)
   62  {
   63      int i = 0;
   64      for(i = 0; i < count; i++) {
   65          if(data[i] != expects) {
   66              log_err("[%d] %c != %c", i, data[i], expects);
   67              return 0;
   68          }
   69      }
   70
   71      return 1;
   72  }
   73
   74
   75  int main(int argc, char *argv[])
   76  {
   77      char from[1000] = {'a'};
   78      char to[1000] = {'c'};
   79      int rc = 0;
   80
   81      // setup the from to have some stuff
   82      memset(from, 'x', 1000);
   83      // set it to a failure mode
   84      memset(to, 'y', 1000);
   85      check(valid_copy(to, 1000, 'y'), "Not initialized right.");
   86
   87      // use normal copy to
   88      rc = normal_copy(from, to, 1000);
   89      check(rc == 1000, "Normal copy failed: %d", rc);
   90      check(valid_copy(to, 1000, 'x'), "Normal copy failed.");
   91
   92      // reset
   93      memset(to, 'y', 1000);
   94
   95      // duffs version
   96      rc = duffs_device(from, to, 1000);
   97      check(rc == 1000, "Duff's device failed: %d", rc);
   98      check(valid_copy(to, 1000, 'x'), "Duff's device failed copy.");
   99
   100      // reset
   101      memset(to, 'y', 1000);
   102
   103      // my version
   104      rc = zeds_device(from, to, 1000);
   105      check(rc == 1000, "Zed's device failed: %d", rc);
   106      check(valid_copy(to, 1000, 'x'), "Zed's device failed copy.");
   107
   108      return 0;
   109  error:
   110      return 1;
   111  }
     __________________________________________________________________

   In this code I have three versions of a copy function:

   normal_copy
          Which is just a plain for-loop that copies characters from one
          array to another.

   duffs_device
          This is the brain teaser called "Duff's Device", named after Tom
          Duff, the person to blame for this delicious evil.

   zeds_device
          A version of "Duff's Device" that just uses a goto so you can
          get a clue about what's happening with the weird do-while
          placement in duffs_device.

   Study these three functions before continuing. Try to explain what's
   going on to yourself before continuing.

24.1 What You Should See

   There's no output from this program, it just runs and exits. You should
   run it under valgrind and make sure there are no errors.

24.2 Solving The Puzzle

   The first thing to understand is that C is rather loose regarding some
   of its syntax. This is why you can put half of a do-while in one part
   of a switch-statement, then the other half somewhere else and it will
   still work. If you look at my version with the goto again it's actually
   more clear what's going on, but make sure you understand how that part
   works.

   The second thing is how the default fallthrough semantics of
   switch-statements means you can jump to a particular case, and then it
   will just keep running until the end of the switch.

   The final clue is the count % 8 and the calculation of n at the top.

   Now, to solve how these functions work, do the following:

    1. Print this code out so you can write on some paper.
    2. On a piece of paper, write each of the variables in a table as they
       are when they get initialized right before the switch-statement.
    3. Follow the logic to the switch, then do the jump to the right case.
    4. Update the variables, including the to, from, and the arrays they
       point at.
    5. When you get to the while part or my goto alternative, check your
       variables and then follow the logic either back to the top of the
       do-while or to where the again label is located.
    6. Follow through this manual tracing, updating the variables, until
       you are sure you see how this flows.

24.2.1 Why Bother?

   When you've figured out how it actually works, the final question is:
   Why would you ever want to do this? The purpose of this trick is to
   manually do "loop unrolling". Large long loops can be slow, so one way
   to speed them up is to find some fixed chunk of the loop, and then just
   duplicate the code in the loop out that many times sequentially. For
   example, if you know a loop runs a minimum of 20 times, then you can
   put the contents of the loop 20 times in the source code.

   Duff's device is basically doing this automatically by chunking up the
   loop into 8 iteration chunks. It's clever and actually works, but these
   days a good compiler will do this for you. You shouldn't need this
   except in the rare case where you have proven it would improve your
   speed.

24.3 Extra Credit

    1. Never use this again.
    2. Go look at the Wikipedia entry for "Duff's Device" and see if you
       can spot the error. Compare it to the version I have here and read
       the article carefully to try to understand why the Wikipedia code
       won't work for you but worked for Tom Duff.
    3. Create a set of macros that lets you create any length device like
       this. For example, what if you wanted to have 32 case statements
       and didn't want to write out all of them? Can you do a macro that
       lays down 8 at a time?
    4. Change the main to conduct some speed tests to see which one is
       really the fastest.
    5. Read about memcpy, memmove, memset, and also compare their speed.
    6. Never use this again!

   [next] [prev] [prev-tail] [front] [up]
     __________________________________________________________________

   Please enable JavaScript to view the comments powered by Disqus.

Take An Online Video Course

   You can sign up for a video course at:

   http://www.udemy.com/learn-c-the-hard-way/

   This course is currently being built at the same time that the book is
   being built, but if you sign up now then you get early access to both
   the videos and PDF of the book.

Related Books

   You might want to check out these other books in the series:
    1. Learn Ruby The Hard Way
    2. Learn Regex The Hard Way
    3. Learn SQL The Hard Way
    4. Learn C The Hard Way
    5. Learn Python The Hard Way

   I'll be referencing other books shortly.

   Copyright 2011 Zed A. Shaw. All Rights Reserved.