switch-case 非常规用法拾零 (1. 绝无原创 2. 非常重视代码规范者勿入)

vupiggy

0. 前言
以下介绍的两个大牛都是利用了 switch 语句中的 case 部分可以置于一个
block (通常是 if{} 或 while{} 块)中， switch 语句执行一个直接跳转进入该
block，进入该 block 的条件有时候被有意地忽略。

全文思路和代码绝无原创之处，只是略加整理了一下。更详细的请看提供的链接。
希望高手老鸟们指出错误不足并给出更深入的分析，如果能提出比例子更漂亮的
方案就太棒了(我感觉可以用回调函数一类的方法实现协作过程，不过还没细想)。

代码规范的讨论就请免了，Simon Taham 在文章里说了一段话挺有趣：

Any coding standard which insists on syntactic clarity at the expense
of algorithmic clarity should be rewritten. If your employer fires you
for using this trick, tell them that repeatedly as the security staff
drag you out of the building. hahaha

vupiggy

1. Duff's device (原创 Tom Duff)
http://en.wikipedia.org/wiki/Duff%27s_device

下面一段小程序：

1. 
   
2. do {
   
3.     *to++ = *from++;
   
4. } while (--count > 0);
   

复制代码

这段程序最让大牛们不爽的是，每拷贝一个字节就需要完成和拷贝字节同量级甚
至更耗时的减法及比较操作，一个可能的优化是减少循环次数，即在一次减法和
比较之后批处理拷贝几个字节，可能的代码如下：

1. 
   
2. do {
   
3.     *to++ = *from++;
   
4.     *to++ = *from++;
   
5.     *to++ = *from++;
   
6.     *to++ = *from++;
   
7.     *to++ = *from++;
   
8.     *to++ = *from++;
   
9.     *to++ = *from++;
   
10.     *to++ = *from++;
    
11. } while ((count -= 8) > 0);
    

复制代码

这段代码是错的，当且仅当 count 被 8 整除才工作，这个思路总体是正确的，
但最大的挑战是如何处理余数。Tom 大叔巧妙的解决余数问题，代码如下：

1. 
   
2. int n = (count + 7) / 8;
   
3. switch (count % 8) {
   
4.         case 0:        do {  *to++ = *from++;
   
5.         case 7:              *to++ = *from++;
   
6.         case 6:              *to++ = *from++;
   
7.         case 5:              *to++ = *from++;
   
8.         case 4:              *to++ = *from++;
   
9.         case 3:              *to++ = *from++;
   
10.         case 2:              *to++ = *from++;
    
11.         case 1:              *to++ = *from++;
    
12.                        } while (--n > 0);
    
13. }
    

复制代码

过程一开始，switch 语句计算余数，直接跳转到对应 case 地址，妙处就在除了
case 0，所有的 case 都在 do {} while() 中，第一次拷贝 count % 8 个
字节，之后逻辑由 do {} while() 循环负责，一次循环拷贝 8 个字节直至结束。

注： 例子其实是 Stroustrup 的新手友好版本而不是 Tom 大叔的原始版本，但
是非常接近。这个版本可以再精简一点点，抛弃变量 n，将 while(--n > 0) 改
为

1. while ((count -= 8) > 0)

复制代码

vupiggy

2. Simon Tatham's Coroutines in C (原创 putty的作者 Simon Tatham)
这位牛牛要解决的问题复杂一些，即所谓“协作过程”(coroutine)问题。
http://www.chiark.greenend.org.uk/~sgtatham/coroutines.html

2.1 引子
考虑如下函数：

1. 
   
2. int function(void) {
   
3.     int i;
   
4.     for (i = 0; i < 10; i++)
   
5.         return i;   /* won't work, but wouldn't it be nice? */
   
6. }
   

复制代码

以上函数的本意是向调用者依次返回从0到9，很显然结果是每一次都返回了0，
将 i 声明为 static 也无济于事。一个可行的方案是：

1. 
   
2. int function(void) {
   
3.     static int i, state;
   
4. 
   
5.     switch(state) {
   
6.         case 0: goto LABEL0;
   
7.         case 1: goto LABEL1;
   
8.     }
   
9. 
   
10.     /* start of function */
    
11. LABEL0:
    
12.     for (i = 0; i < 10; i++) {
    
13.         state = 1;
    
14.         return i;
    
15. LABEL1:; /* Resume control straight after return */
    
16.     }
    
17. }
    

复制代码

以上代码最严重的问题是当有多点返回的时候，程序员要手工维护跳转的标签及
一一对应的 case 段。利用上面提到的 case 段可以置于块内的特点，上面的函
数可以改写成：

1. 
   
2. int function(void) {
   
3.     static int i, state = 0;
   
4. 
   
5.     switch (state) {
   
6.         case 0: /* start of function */
   
7. 
   
8.         for (i = 0; i < 10; i++) {
   
9.             state = 1; /* so we will come back to "case 1" */
   
10.             return i;
    
11. 
    
12.             case 1:; /* resume control straight after the return */
    
13.         }
    
14.     }
    
15. }
    

复制代码

再进一步提高代码可读性，使用几个宏：

1. 
   
2. #define crBegin static int state=0; switch(state) { case 0:
   
3. #define crReturn(i,x) do { state=i; return x; case i:; } while (0)
   
4. #define crFinish }
   
5. 
   
6. int function(void) {
   
7.     static int i;
   
8. 
   
9.     crBegin;
   
10. 
    
11.     for (i = 0; i < 10; i++)
    
12.         crReturn(1, i);
    
13. 
    
14.     crFinish;
    
15. }
    

复制代码

这下看上去像一个“正常”的 C 程序了吧 还有一个小问题，程序员还要自己想
法保证 crReturn() 的第一个参数是唯一的，烦！接着 hack，把这个宏定义成
这个样子利用编译器来帮我们保证参数唯一：

1. 
   
2. #define crReturn(x) do { state=__LINE__; return x; case __LINE__:; } while (0)
   

复制代码

搞掂晒，程序员的重要品质就是能偷懒就偷懒，能不手工(眼工)做的就不做。

2.2 协作过程
在编写 putty 的过程中，这个大牛发明了上述用法来解决所谓协作过程的问题。
考虑以下两个例程：

1. 
   
2. /* Decompression code */
   
3. int decompressor(void) {
   
4.     while (1) {
   
5.         c = getchar();
   
6.         if (c == EOF)
   
7.             break;
   
8.         if (c == 0xFF) {
   
9.             len = getchar();
   
10.             c = getchar();
    
11.             while (len--)
    
12.                 emit(c);
    
13.         } else
    
14.             emit(c);
    
15.     }
    
16.     emit(EOF);
    
17. }
    

复制代码

1. 
   
2. /* Parser code */
   
3. void parser(int c) {
   
4.     while (1) {
   
5.         c = getchar();
   
6.         if (c == EOF)
   
7.             break;
   
8.         if (isalpha(c)) {
   
9.             do {
   
10.                 add_to_token(c);
    
11.                 c = getchar();
    
12.             } while (isalpha(c));
    
13.             got_token(WORD);
    
14.         }
    
15.         add_to_token(c);
    
16.         got_token(PUNCT);
    
17.     }
    
18. }
    

复制代码

姑且把解压例程理解为生产者而语法解析例程为消费者，如果不考虑使用管道，
多线程等重量级解决方案，那么必然有函数调用关系，姑且是认为解析例程调用
解压例程，也就是把解析例程中的每一个 getchar() 替换成 decompressor()，
并把 decompressor() 中的每一个 emit 替换成 return。但是问题来了，每一
次调进 decompressor 以后，总是从头开始执行，这不满足要求，正确的行为应
该是每次调进 decompressor() 都从上一次 return 的地方继续执行，否则就不
叫协作了。采用引子里提到的三个宏构建一个状态机即可完美解决协作需求：

1. 
   
2. int decompressor(void) {
   
3.     static int c, len;
   
4.     crBegin;
   
5.     while (1) {
   
6.         c = getchar();
   
7.         if (c == EOF)
   
8.             break;
   
9.         if (c == 0xFF) {
   
10.             len = getchar();
    
11.             c = getchar();
    
12.             while (len--)
    
13.                 crReturn(c);
    
14.         } else
    
15.             crReturn(c);
    
16.     }
    
17.     crReturn(EOF);
    
18.     crFinish;
    
19. }
    

复制代码

用 cpp 来预处理一下可以帮助理解。

vupiggy

3 后记

向大牛们致敬，他们的奇思妙想给我们带来了无尽的乐趣，引用一句俗得不能再俗
的话和各位同好共勉：have a lot of fun

题外话，这个版事实上大多在讨论和 C/C++ 本身无关的话题，诸如网络编程，系
统编程，多线程多进程一类的其实都和 C/C++ 没什么关系。是不是可以考虑增加
系统编程子版面，有关系统调用，同步，socket 编程的都丢过去。另外，orz，
真不好意思，前两天我自己就把一个 Makefile 相关的东东丟在这个版里而不是
它本来应该在的shell版。

vupiggy

策略和机制分离。我的理解是：机制部分应该只涵盖利用 switch-case 的语法特性来实现跳转，至于如何使用这个机制统统属于策略。像文中那么简单的例子只是为了说明机制可以工作。

我感觉这方案没能解决。
...
1. 保存执行的context —— 用static， 并带来static的各种问题
OwnWaterloo 发表于 2010-12-17 04:32

通过传入指向 context 的指针可以解决。在 putty 的实现代码里实际上使用的就是非 static 变量版本：
定义：

1. 
   
2. #define crBegin(v) { int *crLine = &v; switch (v) { case 0:;
   
3. #define crState(t) \
   
4.     struct t *s; \
   
5.     if (!ssh->t) ssh->t = snew(struct t); \
   
6.     s = ssh->t;
   

复制代码

注：snew 可以看作 malloc

使用方式：

1. 
   
2. static int do_ssh_init(Ssh ssh, unsigned char c)
   
3. {
   
4.     struct do_ssh_init_state {
   
5.         int vslen;
   
6.         char version[10];
   
7.         char *vstring;
   
8.         int vstrsize;
   
9.         int i;
   
10.         int proto1, proto2;
    
11.     };
    
12.     crState(do_ssh_init_state);
    
13. 
    
14.     crBegin(ssh->do_ssh_init_crstate);
    

复制代码

2. 提供一种机制区分yield和return —— 没有解决

利用返回值可以区分。function() 函数是错了，那是写程序人的错，没有处理循环体结束的情况，但并不代表这种机制不提供这个能力。decompressor() 最后的

1. 
   
2. crReturn(EOF);
   
3. crFinish;
   

复制代码

即告知调用者一次任务完成，cfFinish则开始善后，结束这个routine的生命周期。在putty里实际使用的代码像下面这样：

1. 
   
2. #define crFinish(z)        } *crLine = 0; return (z); }
   

复制代码

充其量， 这方案仅仅是让语法稍微好看那么一点。

对简单的应用， 搞那么复杂不如直接在外部写一个for循环。
对复杂的应用， 这种方案又不具备范化的可能。

充其量这个词用得有一定侮辱性。Simon Tatham 老哥听了可能会有点不爽，不过我不会告诉他

好吧，没有人否认这种 Coroutine 的实现有很大的局限性，但是对于一些非常特定情况，譬如说中不溜的应用，过程调用层比较深，而各个过程的内部状态又比较复杂，譬如网络协议，则个方案有一定实用性。像 putty 的需求，就不是在外部多写一个个 for 或者是 while 可以解决的了。

我没找到其它的 C 下实现 coroutine 的方案，这是 C 自身特点所限，stack based function。用汇编做栈切换当然可以完美解决，“but on the other hand it beats having to write the stack switcher separately for every different platform and compiler on which I plan to run my code. Porting is more than enough hassle as it is...”--- Simon Tatham

另外就是 Tom Duff 自己其实也独立给出过这个 trick。