Asked  7 Months ago    Answers:  5   Viewed   15 times

I've read the article on Wikipedia on the Duff's device, and I don't get it. I am really interested, but I've read the explanation there a couple of times and I still don't get it how the Duff's device works.

What would a more detailed explanation be?



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

Tuesday, June 1, 2021
answered 7 Months ago

It is a small world, as the code indicates I posted that code at another forum around 10 years ago having seen it somewhere else - I think on John Walkenbach's old web site

It is important to note that this code protection applies to worksheet protection only - not to Excel's file open or VBA passwords.

  • One example of this write-up in full is here (screenshot below)
  • googling excel sheet protection “test” and “zzyw” gives other references such as this from Tom Urtis

enter image description here

Wednesday, June 30, 2021
answered 6 Months ago

Trac and Redmine both support integration with Git. It looks more or less exactly the same as the Subversion support. The bug tracker follows one repo as the benevolent dictator repo, it doesn't have to care about all the other clones around the place.

One thing I do think is worth mentioning is that any bug tracker needs to support git branches properly. Working on branches is such an important part of the Git methodology, it needs to be supported in the bug tracker. Redmine can do this through a patch, but last I looked (about a month ago), it wasn't in the main source tree (you could only follow master).

Other useful features would be a graphical representation of how branches are created and merged, similar to how gitk looks. I don't know of any bug tracker that does this kind of visualisation.

EDIT by Corey Trager. I copy/pasted @Squelch's answer here (I upvoted @Squelch too):

Due to the distributed nature of Git against the centralized nature of SVN, it is quite possible for every user or copy of the repository to have different branches. The exisitnig trackers typically have a local copy of the repository that is used as a central reference ("benevolent dictator") that can be regarded as the working copy for all users.

It is quite feasible for users to have a different branch structure in their local copy from that of the tracker. They might choose to keep some private, pull only the branches from the remote that they are interested in, or push a new branch to the remote (tracker). Users can even share branches between themselves that the remote may never see.

The bug tracker can really only reference repositories it has access to. Commonly this is local to the tracker, but it is also possible to pull from repositories remote to the tracker, and far harder to manage. If it is accessing a remote, it can only track branches that it has knowledge of, and there is not really a method of initiating this task apart from a scheduled task. This also assumes that users are serving their local copy too.

As you have already noted, a scheduled task, or an event hook can be used to update the tracker using the commit log for details. These details can then be matched to the tracker issues for viewing as required and noted above.

In short, the tracker will typically see whatever changes are made on the branches it currently has access to. With a hook these changes are seen immediately including the creation of a new branch. It will not see or track changes made to users (offline) repositories until they push those changes.

END OF @Squelch

Sunday, August 1, 2021
answered 5 Months ago

The duff's device comment should explain the background well enough, so I ll try to explain this very case:

The switch checks the last 2 bits of c, and jumps to the respective case-statement inside the while loop. The code below the case statement is also executed. Control then reaches the end of the while loop, so it jumps to the beginning again to check if the condition is still true. If it is, all the statements inside the loop are executed, and the loop is repeated until the condition is false. The initial switch usually ensures that c will be a multiple of 4 when the while loop runs for the first time.

Edit: duff's device on Wikipedia. Adding link to make more obvious what I meant with "the duff's device comment". Please consider upvoting interjay's comment should you upvote this answer.

Monday, August 16, 2021
answered 4 Months ago

The code doesn't appear to be Undefined Behavior. Therefore any optimizations are not allowed to produce any effects which would affect the behavior of the code.

Note: Related to this kind of code, one thing you are not allowed to do is "goto" over definitions of local variables. But this code doesn't do that, so no problem.

Another note: If you have this kind of code in a "real" (not toy, experiment, obfuscation exercise etc) program, you should really refactor it into something which doesn't elicit quite so many WTFs from anybody reading the code.

Wednesday, November 10, 2021
answered 4 Weeks ago
Only authorized users can answer the question. Please sign in first, or register a free account.
Not the answer you're looking for? Browse other questions tagged :