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