笨办法学C 翻译程序员

笨办法学C 练习23:认识达夫设备

2016-06-11  本文已影响71人  布客飞龙

练习23:认识达夫设备

原文:Exercise 23: Meet Duff's Device

译者:飞龙

这个练习是一个脑筋急转弯,我会向你介绍最著名的C语言黑魔法之一,叫做“达夫设备”,以“发明者”汤姆·达夫的名字命名。这一强大(或邪恶?)的代码中,几乎你学过的任何东西都被包装在一个小的结构中。弄清它的工作机制也是一个好玩的谜题。

C的一部分乐趣来源于这种神奇的黑魔法,但这也是使C难以使用的地方。你最好能够了解这些技巧,因为他会带给你关于C语言和你计算机的深入理解。但是,你应该永远都不要使用它们,并总是追求简单易读的代码。

达夫设备由汤姆·达夫“发现”(或创造),它是一个C编译器的小技巧,本来不应该能够正常工作。我并不想告诉你做了什么,因为这是一个谜题,等着你来思考并尝试解决。你需要运行这段代码,之后尝试弄清它做了什么,以及为什么可以这样做。

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


int normal_copy(char *from, char *to, int count)
{
    int i = 0;

    for(i = 0; i < count; i++) {
        to[i] = from[i];
    }

    return i;
}

int duffs_device(char *from, char *to, int count)
{
    {
        int n = (count + 7) / 8;

        switch(count % 8) {
            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);
        }
    }

    return count;
}

int zeds_device(char *from, char *to, int count)
{
    {
        int n = (count + 7) / 8;

        switch(count % 8) {
            case 0:
            again: *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++;
                    if(--n > 0) goto again;
        }
    }

    return count;
}

int valid_copy(char *data, int count, char expects)
{
    int i = 0;
    for(i = 0; i < count; i++) {
        if(data[i] != expects) {
            log_err("[%d] %c != %c", i, data[i], expects);
            return 0;
        }
    }

    return 1;
}


int main(int argc, char *argv[])
{
    char from[1000] = {'a'};
    char to[1000] = {'c'};
    int rc = 0;

    // setup the from to have some stuff
    memset(from, 'x', 1000);
    // set it to a failure mode
    memset(to, 'y', 1000);
    check(valid_copy(to, 1000, 'y'), "Not initialized right.");

    // use normal copy to 
    rc = normal_copy(from, to, 1000);
    check(rc == 1000, "Normal copy failed: %d", rc);
    check(valid_copy(to, 1000, 'x'), "Normal copy failed.");

    // reset
    memset(to, 'y', 1000);

    // duffs version
    rc = duffs_device(from, to, 1000);
    check(rc == 1000, "Duff's device failed: %d", rc);
    check(valid_copy(to, 1000, 'x'), "Duff's device failed copy.");

    // reset
    memset(to, 'y', 1000);

    // my version
    rc = zeds_device(from, to, 1000);
    check(rc == 1000, "Zed's device failed: %d", rc);
    check(valid_copy(to, 1000, 'x'), "Zed's device failed copy.");

    return 0;
error:
    return 1;
}

这段代码中我编写了三个版本的复制函数:

normal_copy

使用普通的for循环来将字符从一个数组复制到另一个。

duffs_device

这个就是成为“达夫设备”的脑筋急转弯,以汤姆·达夫的名字命名。这段有趣的邪恶代码应归咎于他。

zeds_device

“达夫设备”的另一个版本,其中使用了goto来让你发现一些线索,关于duffs_device中奇怪的do-while做了什么。

在往下学习之前仔细了解这三个函数,并试着自己解释代码都做了什么。

你会看到什么

这个程序没有任何输出,它只会执行并退出。你应当在Valgrind下运行它并确保没有任何错误。

解决谜题

首先需要了解的一件事,就是C对于它的一些语法是弱检查的。这就是你可以将do-while的一部分放入switch语句的一部分的原因,并且在其它地方的另一部分还可以正常工作。如果你观察带有goto again的我的版本,它实际上更清晰地解释了工作原理,但要确保你理解了这一部分是如何工作的。

第二件事是switch语句的默认贯穿机制可以让你跳到指定的case,并且继续运行知道switch结束。

最后的线索是count % 8以及顶端对n的计算。

现在,要理解这些函数的工作原理,需要完成下列事情:

为什么写成这样?

当你弄明白它的实际工作原理时,最终的问题是:问什么要把代码写成这样?这个小技巧的目的是手动编程“循环展开”。大而长的循环会非常慢,所以提升速度的一个方法就是找到循环中某个固定的部分,之后在循环中复制代码,序列化地展开。例如,如果你知道一个循环会执行至少20次,你就可以将这20次的内容直接写在源代码中。

达夫设备通过将循环展开为8个迭代块,来完成这件事情。这是个聪明的办法,并且可以正常工作。但是目前一个好的编译器也会为你完成这些。你不应该这样做,除非少数情况下你证明了它的确可以提升速度。

附加题

上一篇下一篇

猜你喜欢

热点阅读