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版。

flw

coroutine 这个解决方案真牛！

OwnWaterloo

我感觉这方案没能解决。

1. coroutine的目的是为了在特定点挂起， 并在随后（按挂起时的状态）恢复执行

挂起时的状态需要保存， 而例子中， 是保存在static变量中。

2. static变量的问题

使用static变量， 就带有static变量的所有坏处 —— 当然， 这不是重点。
重点是， 无法建立2个coroutine。

举个lua的例子：

function f()
  print('step1')
  coroutine.yield()
  print('step2)
end

可以同时创建1个以上的corotuine：

c1 = coroutine.create(f)
c2 = coroutine.create(f)

并且按任意顺序执行2个coroutine中的4个step， 比如：
coroutine.resume(c1) -- 执行第1个的step1
coroutine.resume(c2) -- 执行第2个的step1
coroutine.resume(c2) -- 执行第2个的step2
coroutine.resume(c1) -- 执行第1个的step1

用static来保存context显然做不到这点。

例子中的decompressor和parser因为static的限制， 都是一次性的。
一个进程中， decompressor只能使用一次。


3. coroutine可以在挂起时， 可以顺带返回一个值。

这样， coroutine就可以用于实现generator。
但这同时需要有一个方法， 判断coroutine是否执行完毕。

还是以lua举例：

function g()
  coroutine.yield()
  coroutine.yield(12)
  coroutine.yield(3,26)
end

c = coroutine.create(g)
=coroutine.resume(c) --> true
=coroutine.resume(c) --> true, 12
=coroutine.resume(c) --> true, 3, 26
=coroutine.resume(c) --> false —— 执行完毕

lua是可以返回多个值， 所以利用第1个返回值来代表coroutine是否执行完毕。
python也可以返回多个值。  但我印象中， python是通过抛出异常来表示coroutine执行完毕。

总之， 需要一种方式来表示coroutine是yield还是return。


例子显然也做不到这点， function产生10个返回值之后， 结果是什么？
如果我没看错， 结果应该是跳出for循环， 执行到switch的尾 } ， 然后函数在没有return的情况下返回。
这是否是未定义行为我忘了， 但至少得不到一个确定的返回值。



综上， coroutine的关键点：
1. 保存执行的context —— 用static， 并带来static的各种问题
2. 提供一种机制区分yield和return —— 没有解决
这个方案都没能很好解决。

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

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

action08

这些代码非常漂亮,
为什么要说不尊重代码规范呢??

action08

不明白为什么有的coder喜欢用宏


这玩意玩不起,,,太强大了

bluesea666

对简单的应用， 搞那么复杂不如直接在外部写一个for循环。
对复杂的应用， 这种方案又不具备范化的可能。
OwnWaterloo 发表于 2010-12-17 11:32

    学习了.

asdmonster

mark下