Duff's device

Leonardo Herrera
Creado: 7/6/2007

Mmmmh...Como estoy medio bloqueado con una asignación de trabajo, voy a escribir algo cortito sobre programación.

En programación es usual recorrer largos búferes de datos y efectuar una operación en ellos; por ejemplo, una copia desde un búfer a otro, o escritura hacia algún device que esté "mapeado" en memoria. Por ejemplo, el siguiente código simplemente escribe el buffer "from" en pantalla:


int main(int argc, char *argv[])
{
    char *from = "0123456789ABCD";
    char *ptr;
    int i, j, l = strlen(from);

    ptr = from;
    for (i = 0; i < l; i++) {
        printf("%c", *ptr++);
    }
    printf("\n");
}

Esta expresión podría ser optimizada haciendo menos iteraciones:


int main(int argc, char *argv[])
{
    char *from = "0123456789ABCD";
    char *ptr;
    int i, j, l = strlen(from);

    ptr = from;
    for (i = 0; i < (l / 5); i++) {
        printf("%c", *ptr++);
        printf("%c", *ptr++);
        printf("%c", *ptr++);
        printf("%c", *ptr++);
        printf("%c", *ptr++);
    }
    for (j = i * 5; j < l; j++) {
        printf("%c", *ptr++);
    }
    printf("\n");
}


En este caso, el ciclo tendría menos iteraciones. En el ejemplo no es muy visible la ganancia, pero si from apuntase a un buffer muy largo la ganancia en ciclos sería importante (en realidad nunca es tan simple, pero quedemos en eso).

Esta operación (muy común cuando se programa en aparatejos de poco poder de proceso) es conocido como loop unrolling o loop unwinding. (Una vez el amigo Milenko hizo uno sin saber, no se debe ni acordar).

Hace algunos años un señor de apellido Duff propuso una monstruosidad para efectuar esta operación:


int main(int argc, char *argv[])
{
    char *from = "0123456789ABCD";
    int i, j, n, l = strlen(from);
    char *ptr;

    ptr = from;
    i = (l + 7) / 8;
    switch (l % 8) {
        case 0: do{ printf("%c", *ptr++);
        case 7:     printf("%c", *ptr++);
        case 6:     printf("%c", *ptr++);
        case 5:     printf("%c", *ptr++);
        case 4:     printf("%c", *ptr++);
        case 3:     printf("%c", *ptr++);
        case 2:     printf("%c", *ptr++);
        case 1:     printf("%c", *ptr++);
        } while (--i > 0);
    }
    printf("\n");
}

A primera vista, ese do..while metido entremedio de un switch no parece ser legal, ¿no?

Pero lo es.

La variable usada para iterar se inicializa usando división entera: en este caso, antes de entrar al switch a la variable i se le asigna (14 + 7) / 8, o sea, 2. Luego, en el switch se consulta por el resto de la división entera entre el largo (14) y 8, es decir, 6. La ejecución salta, entonces, al caso 6, donde se imprime el primer caracter, luego pasa de largo (no hay break en ningún case: esto es conocido como fallthrough) hasta el caso 5, donde se imprime el segundo caracter, y así sucesivamente, hasta el caso 1. Luego, (y aquí es donde viene la parte tránsfuga) se ejecuta la condición del while; es decir, se decrementa i en 1 (i = 1)y luego se pregunta si es el resultado es mayor a cero. Luego se vuelve al bucle (que comienza en "0") y se avanza por el buffer 8 veces; se decrementa i nuevamente (i = 0) y se pregunta si es mayor a 0. Como no es mayor, finaliza la ejecución.

Ese truco de meter un ciclo while dentro de un switch es conocido como el Duff's Device.

Este sitio es mantenido con ePublish