Tuesday, October 11, 2005

Duff's Device

I thought I was quite good in C. Duff's Device got me wrong! Check the wikipedia page for details; the original post is here. This is what it is, in brief.


Consider the following function in C to copy count integers from from to to:

void copy (int *from, int *to, int count)
{
do {
*(to ++) = *(from ++);
} while (- - count > 0);
}

This requires count comparisons. One way to cut down on the number of comparisons is to use partial loop unrolling:

void copy (int *from, int *to, int count)
{
int n = count/8;
int rem = count % 8;

// copy rem times
do {
*(to ++) = *(from ++);
} while (- - rem- > 0);

// copy 8*n times
do {
*(to ++) = *(from ++);
*(to ++) = *(from ++);
*(to ++) = *(from ++);
*(to ++) = *(from ++);
*(to ++) = *(from ++);
*(to ++) = *(from ++);
*(to ++) = *(from ++);
*(to ++) = *(from ++);
} while (- - n > 0);
}


Tom Duff had this ingenious idea of exploiting case-fall-through behaviour of C switch-case statement to write a smaller code:

void copy (int *from, int *to, int count)
{
int n=(count+7)/8;
int rem = count % 8;
switch(rem){
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);
}


While you are trying to understand whats going on, let me answer the first question covering your mind, Yes! This is a prefectly legal C (even more, legal C++).

2 comments:

Siddhartha Saha said...

What happened to good ol' memcpy?

dBera said...

From Duff's reply in comp.lang.c,
...
To clear up a few points:

1. The point of the device is to express general loop unrolling directly in C. People who have posted saying `just use memcpy' have missed the point, as have those who have criticized it using various machine-dependent memcpy implementations as support. In fact, the example in the message (duff's original example was copying an array of shorts into an IO data register) is not implementable as memcpy, nor is any computer likely to have an memcpy-like idiom that implements it.
...

Post a Comment