while switch-case

转一个 
原地址http://hi.baidu.com/nxdl/blog/item/b81856365d338ad3a3cc2bd9.html 

前几天在网上看见了一段代码，叫做“Duff's Device”，后经验证它曾出现在Bjarne的TC++PL里面：  

 void send( int * to, int * from, int count) 
          //     Duff设施，有帮助的注释被有意删去了  
 { 
          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 ); 
          }  
 }    

代码的结构显得非常巧妙，把一个switch语句和一个do-while语句糅合在了一起。而在我看过的所有关于C和C++的书中，这样的代码都 是毫无道理的。然而，无论是在VS2005还是在GCC4.1.2下，这段代码都能正确地通过编译。加上适当的main函数，它都可以正常运行。我百思不 得其解。上网去查，也没查到好答案。 

怎么办？先看看它的汇编代码吧，也许可以通过它的汇编代码看出它的意思。 

gcc -S send.cpp 

粗略地一看，汇编代码都已经上百行了，而且里面还有一个跳转表，十几个标号。一般情况下，几十行的汇编代码都已经不太好看懂了，要把这几百行汇编完全看懂，估计需要花很多时间。 

既然直接来太麻烦，那就用简便一点的方法吧： 

 #include < iostream >  
 using namespace std; 
  
 int main() 
 { 
      int n = 0 ; 
      switch (n) {  
      case 0 :  do {cout << " 0 " << endl; 
      case 1 :      cout << " 1 " << endl; 
      case 2 :       cout << " 2 " << endl; 
      case 3 :       cout << " 3 " << endl;  
              } while ( -- n > 0 );  
      }  
 }  
实验结果  
n的值 程序输出  
0       0 
        1 
        2 
        3  
------------- 
1       1 
        2 
        3  
------------ 
2       2 
        3 
        0 
        1 
        2 
        3  
------------- 
3       3 
        0 
        1 
        2 
        3 
        0 
        1 
        2 
        3  
------------- 
其他 (无输出)  

    这下终于弄清楚了。原来，那段代码的主体还是do-while循环，但这个循环的入口点并不一定是在do那里，而是由这个switch语句根据n，把循环的 入口定在了几个case标号那里。也就是说，程序的执行流程是：程序一开始顺序执行，当它执行到了switch的时候，就会根据n的值，直接跳转到 case n那里（从此，这个swicth语句就再也没有用了）。程序继续顺序执行，再当它执行到while那里时，就会判断循环条件。若为真，则while循环开 始，程序跳转到do那里开始执行循环（这时候由于已经没有了switch，所以后面的标号就变成普通标号了，即在没有goto语句的情况下就可以忽略掉这 些标号了）；为假，则退出循环，即程序中止。 

    忙活了几个小时，终于明白这段代码是怎么回事了。回想一下，自己以前也曾写过类似C的语法但比C语法简单很多的解释器，用的是递归子程序法。而如果用递归下降法来分析这段代码，是肯定会有问题的。 

至于它是怎么正确编译并运行的，这需要去研究一下C编译器，这个以后再说。现在，还是再来看看达夫设备吧。其实，这个send函数的签名就已经很具有提示性了：把from数组中的元素拷贝count个到to里面去。于是有人会说，这个工作简单，不就这样吗： 

 void my_send( int * to, int * from, int count) 
 { 
      for ( int i = 0 ; i != count; ++ i) { 
          * to ++ = * from ++ ; 
      }  
 } 

这段代码的确很简洁，也是正确的，而且生成的机器码也比send函数短很多。但是却忽略了一个因素：执行效率。计算一下就可以知 道，my_send函数里面的循环条件，即i和count的比较运算的次数，是达夫设备的8倍！在做整数赋值这种耗时很少的工作时，这种耗时相对较高的比 较工作是会大大地影响函数整体的效率的。达夫设备则是一种非常巧妙的解决办法（当然，它利用到了编译器的一些实现上的工作），而且如果把8换成更大的数的 话，效率就还可以提高！ 

它的思路是这样的：把原数组以8个int为单位分成若干个小组，复制的时候以小组为单位复制，即一次复制8个 int。也就是说，在my_send函数中以一次比较运算的代价换来1个int的复制，而在达夫设备中，却能以一次比较运算的代价换来8个int的复制。 而switch语句则是用来处理分组时剩下的不到8个的int（这些剩余的不是数组最后的，而是数组最开始的），很巧妙。 

总结：像达夫设 备这样的代码，从语言的角度来看，我个人觉得不值得我们借鉴。因为这毕竟不是“正常”的代码，至少C/C++标准不会保证这样的代码一定不会出错。另外， 这种代码估计有很多人根本都没见过，如果自己写的代码别人看不懂，这也会是一件很让人头疼的事。然而，从算法的角度来看，我觉得达夫设备是个很高效、很值 得我们去学习的东西。把一次消耗相对比较高的操作“分摊“到了多次消耗相对比较低的操作上面，就像vector<T>中实现可变长度的数组的 思想那样，节省了大量的机器资源，也大大提高了程序的效率。这是值得我们学习的。 

附 

void duff_memcpy( char* to, char* from, size_t count ) 

{ 

   size_t 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); 

   } 

}  


duff’s device，是用Tom Duff的名字来命名的。很有名的一个东西，用来优化拷贝的，据说和Rob Pike此牛还有点儿关系～！不过注意，原始的duff’s device中的to可是不变的，因为它指向一个映射到内存的寄存器。 

这是个很棒的迂回循环展开法, 由 Tom Duff 在 Lucasfilm 时所设计。它的 ``传统" 形态, 是用来复制多个字节:  
    register n = (count + 7) / 8;   /* count > 0 assumed */ 
    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); 
    } 

这里 count 个字节从 from 指向的数组复制到 to 指向的内存地址 (这是个内存映射的输出寄存器, 这也是为什么它没有被增加)。它把 swtich 语句和复制 8 个字节的循环交织在一起, 从而解决了剩余字节的处理问题 (当 count 不是 8 的倍数时)。相信不相信, 象这样的把 case 标志放在嵌套在 swtich 语句内的模块中是合法的。当他公布这个技巧给 C 的开发者和世界时, Duff 注意到 C 的 swtich 语法, 特别是 ``跌落" 行为, 一直是被争议的, 而 ``这段代码在争论中形成了某种论据, 但我不清楚是赞成还是反对"。