Magical C Language, Loop Un-Rolling and Duffs Device

After so many years of working with C language. It always Surprises me. Today I came across Duff’s Device. It is really a cleaver technique.
Suppose you want to copy a buffer of 100 bytes, typical code you will write will have following construct

for ( int i = 0; i < 100; i++ ) {
    *dest++ = *source++
}

There are bunch of instruction involves here, Compare Instruction, Increment Instruction …
But important thing is this all is done for 100 times.

Duff’s Device is intelligent method of solving this following as given in following code.

#include <stdio.h>
#include <string.h>

#define SIZE 10000

void duffsDevice(const char *source, char *destination, int length) {
  int numberOfPass = 0;
  int n = (length + 7) / 8;
  switch (length % 8) {
    case 0:
      do {
        *destination++ = *source++; 
        case 7:   *destination++ = *source++; 
        case 6:   *destination++ = *source++; 
        case 5:   *destination++ = *source++; 
        case 4:   *destination++ = *source++; 
        case 3:   *destination++ = *source++; 
        case 2:   *destination++ = *source++; 
        case 1:   *destination++ = *source++; 
      } while (numberOfPass++,--n > 0);
  }

  printf("Number of Loops = %d\n", numberOfPass);

}


int main(int argc, char** argv) {
  char source[SIZE + 1] = { 'a' };
  char destination[SIZE + 1] = { 'c' };

  memset(source, 'x', SIZE);
  memset(source, 'z', SIZE);

  printf("Source = [%s]\n", source);

  memcpy(destination, source, SIZE);

  duffsDevice(source, destination, SIZE);
  destination[SIZE] = '\0';

  printf("Destination = [%s]\n", destination);
}

For copying 10000 bytes it take only 1250 loops.

Advertisements