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

OwnWaterloo

你告诉他好了~  顺便也告诉我"充其量"应该如何翻译……

原文我很早以前就看过。 当时对coroutine理解不深， 所以肯定看得不够仔细。
再看老文， 总是缺乏耐心的……

例子当然是需要简化的， 但不能把问题的关键给简化了。
1. 生成不同的coroutine实例
2. 简化脑力计算， 更自然的表达算法
否则， 脑力计算出挂起点和context， 其实不用coroutine也可以编程了。

所以， "从他列出的代码来看"， 我的评价就是上面的， 只是让语法稍微好看一点。
简单的没必要用， 复杂的又用不上。
可能也就"中不溜秋"的应用可以玩一玩， 但朴质的写法也一定可以完成的。
至于维护性就不好说了。


你提到putty的实现代码通过传入context的指针完成以解决static（本质是多个不同coroutine实例）的问题。
能否演示一下？
希望就用上面那个lua和rc4的例子， 而putty可能相关上下文更多。
我就偷个懒， 不去深研他的原文啦~


PS： 上面的使用fiber的程序还存在一些问题。

因为rc4的例子很特殊， 是一个无限循环中不断yield， 不需要terminate的判断。
本来想再修改一下， 改为：

1. 
   
2. unsigend char rc4_stream(char const* filename, char const* key, size_t len);
   

复制代码

每次产生一个byte的密文。
也有一个很正当的需求： 因为将rc4算法对密文再执行一次恰好就得到明文， 所以这其实是一个增量"解密"程序……
用户不需要完整的明文， 只需要前面一部分， 可以调用几次rc4_stream并夺回控制权， 根据所得明文看是否需要继续解密余下密文。

同时还可以演示将参数打包到一个void*； 判断coroutine状态这些问题 —— 能体现使用coroutine不如其他语言那么爽。

但是……  我想上面的例子应该能体现coroutine避免脑力计算了。
而且， 手确实很僵啊……   银魂在等待啊……   看银魂去了……

OwnWaterloo

先说coroutine的状态

我上面的帖说coroutine必须提供一个机制来区分ternimate和yield。
lua有多返回值， 而python除了多返回值， 还有异常。

可能没说清楚， 我再说具体一点。
1. 代码中确实有个错误， 在10次调用后
2. 不是说C语言就解决不了这个问题
C确实不支持多返回值， 但需要多返回值时， C肯定有迂回的办法：

1. 
   
2. struct { T1 y1; T2 y2; } f(P x);
   
3. void f(P x, T1* y1, T2* y2);
   

复制代码

就是ugly而已。
一般情况下， 我设计api时都会尽可能不使用传出参数， 但有时候真没办法。



再看启动函数
留意上面的

1. coroutine_create( ..., void (*f)(void* x), void* x);

复制代码

结合

1. pthread_create( ..., void* (*f)(void* x), void* x);

复制代码

这是C语言另一个问题： 没有一种参数类型可以直接代表任意"函数参数"。
当需要的时候， 上面就是一个典型的迂回方式。

注意伪代码中， rc4_stream是unsigned char rc4_stream(char const* key, size_t len);
而实际代码中， rc4_stream需要是void rc4_stream(void* x);
范化的解决办法就是：

1. 
   
2. 
   
3. typedef struct
   
4. {
   
5.       char const* key;
   
6.       size_t len;
   
7. } rc4_arg_t;
   
8. 
   
9. void rc4_stream(void* x)
   
10. {
    
11.       rc4_arg_t* arg = (rc4_arg_t*)x;
    
12.       rc4_stream(arg->key, arg->len);
    
13. }
    
14. 
    
15. rc4_arg_t arg = { "1212", 4 };
    
16. coroutine_create( ..., &arg);
    

复制代码

实际代码中只是取巧使用strlen来减少一个参数。
对更一般的例子， 就必须迂回一次。


最后看yield的返回值

yield返回什么？
为了让那几个coroutine的api更范化一点， 我选择和pthread相同的， 返回void*。
若需要的返回值比void*窄， 直接通过void* 的值返回。
否则返回一个指向结构体的指针 —— 对更复杂的例子， 就需要再如此这般的迂回一次， 运气不好还需要动态分配。

所有的这些加起来， 得到的结果就是在C中使用coroutine会非常麻烦， 能避免，就尽量避免。

OwnWaterloo

C下实现coroutine的库 —— 不需要用户去考虑如何设置状态机， 保存context的方案—— 是有的。
coroutine的wiki页面应该就有介绍一些， 我没仔细研究。
用thread肯定可以实现， 但那代价太大， 只有理论上的价值。

下面我演示一个使用win32 fiber模拟coroutine的简陋方案。
因为coroutine的切换本来就是同步的， 所以可以避免使用thread和同步工具。
而且fiber的切换是用户态的， 只有10左右的机器指令。

coroutine的api。

1. 
   
2. // coroutine.h
   
3. 
   
4. typedef struct
   
5. {
   
6.       void* fiber_;
   
7.       void (*f_)(void* x);
   
8.       void* x_;
   
9.       void* y_;
   
10.       void* caller_;
    
11. } coroutine_t;
    
12. 
    
13. // 这是因为win32 fiber的限制
    
14. // 每个使用fiber的thread必须首先做一些工作
    
15. int   coroutine_init(void);
    
16. 
    
17. int   coroutine_create(coroutine_t* self, void (*f)(void* x), void* x);
    
18. // C没有垃圾收集等东西， 所以需要手动释放资源
    
19. void  coroutine_destory(coroutine_t* self);
    
20. 
    
21. // resume返回yield的参数
    
22. void* coroutine_resume(coroutine_t* self);
    
23. void  coroutine_yield(void* val);
    
24. 
    
25. // 同lua coroutine.running
    
26. void* coroutine_running(void);
    
27. 
    

复制代码

那么， lua的例子就可以改写为：

1. 
   
2. // lua_example.c
   
3. 
   
4. #include <stdio.h>
   
5. 
   
6. #include "coroutine.h"
   
7. 
   
8. void f(void* arg)
   
9. {
   
10.       printf("in %p step1\n", coroutine_running() );
    
11.       coroutine_yield(0);
    
12.       printf("in %p step2\n", coroutine_running() );
    
13. }
    
14. 
    
15. int main(void)
    
16. {
    
17.       coroutine_t c1, c2;
    
18. 
    
19.       coroutine_init();
    
20. 
    
21.       coroutine_create(&c1, f, 0);
    
22.       coroutine_create(&c2, f, 0);
    
23. 
    
24.       printf("coroutine1 %p\n", (void*)&c1);
    
25.       printf("coroutine2 %p\n", (void*)&c2);
    
26. 
    
27.       coroutine_resume(&c1);
    
28.       coroutine_resume(&c2);
    
29.       coroutine_resume(&c2);
    
30.       coroutine_resume(&c1);
    
31. 
    
32.       coroutine_destory(&c2);
    
33.       coroutine_destory(&c1);
    
34. 
    
35.       return 0;
    
36. }
    

复制代码

使用coroutine的rc4：

1. 
   
2. // rc4.cpp
   
3. 
   
4. #include <stdio.h>
   
5. #include <string.h>
   
6. #include <algorithm>
   
7. 
   
8. #include "coroutine.h"
   
9. 
   
10. void rc4_stream(void* arg)
    
11. {
    
12.       unsigned char* key = (unsigned char*)arg;
    
13.       unsigned char S[256];
    
14. 
    
15.       for (unsigned i=0; i<256; ++i)
    
16.             S[i] = i;
    
17. 
    
18.       for (size_t i=0, j=0, len=strlen((char*)key); i<256; ++i)
    
19.       {
    
20.             j = (j+S[i]+key[i%len]) % 256;
    
21.             std::swap(S[i], S[j]);
    
22.       }
    
23. 
    
24.       for (unsigned i=0, j=0; ; )
    
25.       {
    
26.             i = (i+1) % 256;
    
27.             j = (j+S[i]) % 256;
    
28.             std::swap(S[i], S[j]);
    
29.             coroutine_yield((void*)(S[ (S[i]+S[j]) % 256 ]));
    
30.       }
    
31. }
    
32. 
    
33. int main(void)
    
34. {
    
35.       FILE* a = fopen("a", "rb");
    
36.       FILE* b = fopen("b", "wb");
    
37.       coroutine_t g;
    
38. 
    
39.       coroutine_init();
    
40.       coroutine_create(&g, rc4_stream, (void*)"1212");
    
41.       for (int c; c=getc(a), c!=EOF; )
    
42.             putc((unsigned)coroutine_resume(&g) ^ c, b);
    
43.       coroutine_destory(&g);
    
44.       fclose(b);
    
45.       fclose(a);
    
46.       return 0;
    
47. }
    

复制代码

请留意一下f与rc4_stream函数的代码， 可以在心里默默的"输入"试试。
是否完全不需要考虑挂起点与context的保存， 直接实现算法就可以了？
这就是coroutine的脑力优势。

当然， 这种方案肯定有缺点。

首先肯定因为使用了win32特性而不可移植。
但可以找一些跨平台的coroutine的库， 如果它们很稳定的话。
最重要的是： C语言真的需要那些花花肠子的功能吗？
我感觉并不是所有时候都需要把C武装到牙齿， 依然用简单的C实现关键的部分， 其余部分交给胶水语言去粘就完了。
因为简单是C的目标之一， 无论怎么武装， 它都是缺这缺哪的。

下面先帖一下coroutine的实现代码， 再说关于coroutine， C语言缺了哪些东西。

1. 
   
2. // coroutine.c
   
3. 
   
4. #define _WIN32_WINNT 0x0400
   
5. #include <windows.h>
   
6. 
   
7. #include "coroutine.h"
   
8. 
   
9. int  coroutine_init()
   
10. {
    
11.       return ConvertThreadToFiber(0) != 0;
    
12. }
    
13. 
    
14. void* coroutine_running(void)
    
15. {
    
16.       return GetFiberData();
    
17. }
    
18. 
    
19. static void __stdcall coroutine_start_(void* arg)
    
20. {
    
21.       coroutine_t* self = (coroutine_t*)arg;
    
22.       self->f_(self->x_);
    
23.       SwitchToFiber(self->caller_);
    
24. }
    
25. 
    
26. int  coroutine_create(coroutine_t* self, void (*f)(void* x), void* x)
    
27. {
    
28.       self->f_ = f;
    
29.       self->x_ = x;
    
30.       self->fiber_ = CreateFiber(0, coroutine_start_, self);
    
31.       self->y_ = 0;
    
32.       return self->fiber_!=0;
    
33. }
    
34. 
    
35. void  coroutine_destory(coroutine_t* self)
    
36. {
    
37.       DeleteFiber(self->fiber_);
    
38. }
    
39. 
    
40. void* coroutine_resume(coroutine_t* self)
    
41. {
    
42.       self->caller_ = GetCurrentFiber();
    
43.       SwitchToFiber(self->fiber_);
    
44.       return self->y_;
    
45. }
    
46. 
    
47. void coroutine_yield(void* val)
    
48. {
    
49.       coroutine_t* self = (coroutine_t*)GetFiberData();
    
50.       self->y_ = val;
    
51.       SwitchToFiber(self->caller_);
    
52. }
    

复制代码

OwnWaterloo

Simon的那个例子我觉得还不够具体， 比如got_token、add_to_token什么的没有给出。
所以我换一个完整的例子， 与RC4加密有关。
RC4的描述见： http://en.wikipedia.org/wiki/RC4#Description

RC4算法大致是：
1. 通过key初始化一个长度为256的byte数组
2. 从这个byte数组中进行某种置换操作， 并输出1个byte
3. 重复步骤2， 就可以得到一个byte流
4. 将明文的byte流与3得到的byte流进行异或操作， 得到密文

1. RC4加密算法伪C语言描述

重点就是得到异或byte流， 算法如下：

1. 
   
2. unsigned char rc4_stream(char const* key, size_t len)
   
3. {
   
4.       // init S
   
5.       unsigned char S[256];
   
6.       for (unsigned i=0; i<256; ++i)
   
7.             S[i] = i;
   
8. 
   
9.       for (unsigned i=0, j=0; i<256; ++i)
   
10.       {
    
11.             j = (j+S[i]+key[i%len]) % 256;
    
12.             swap(S[i], S[j]);
    
13.       }
    
14. 
    
15.       // generate stream
    
16.       for (unsigend i=0, j=0; ; )
    
17.       {
    
18.             i = (i+1) % 256;
    
19.             j = (j+S[i]) % 256;
    
20.             swap(S[i], S[j]);
    
21.             yield(S[ (S[i]+S[j]) % 256 ]);
    
22.       }
    
23. }
    

复制代码

我想这个例子比Simon更完整与具体， 整个代码不再与任何其他事物相关。
（除了swap、 它应该不需要更多解释）。

代码里有一个C语言不支持的yield， 所以是伪C代码。
若用真正的C语言实现， 就需要保存产生stream序列的最后一个for循环中context。
具体的说， 就是S, i, j。
下面给出一个实现。

2. RC4加密， C++完整实现

1. 
   
2. #include <stdio.h>
   
3. #include <algorithm>
   
4. 
   
5. // 为了代码的可读性， 稍微用了一点C++的东西
   
6. // 代码中有说明
   
7. 
   
8. typedef struct
   
9. {
   
10.       unsigned i, j;
    
11.       unsigned char s[256];
    
12. } rc4_t;
    
13. 
    
14. void rc4_ctor(rc4_t* self, char const* key, size_t len)
    
15. {
    
16.       unsigend char* S = self->s;
    
17.       for (unsigend i=0; i<256; ++i)
    
18.             S[i] = i;
    
19.       for (unsigned i=0, j=0; i<256; ++i)
    
20.       {
    
21.             j = (j+S[i]+key[i%len]) % 256;
    
22.             std::swap(S[i], S[j]); // 懒得写一个swap了
    
23.       }
    
24.       self->i = self->j = 0;
    
25. }
    
26. 
    
27. unsigend rc4_next(rc4_t* self)
    
28. {
    
29.       unsigend& i = self->i;
    
30.       unsigend& j = self->j;
    
31.       unsigend char* S = self->s;
    
32. 
    
33.       // 使用引用是为了下面几行置换代码短一些
    
34.       i = (i+1) % 256;
    
35.       j = (j+S[i]) % 256;
    
36.       std::swap(S[i], S[j]);
    
37. 
    
38.       return S[ (S[i]+S[j]) % 256 ];
    
39. }
    
40. 
    
41. int main(void)
    
42. {
    
43.       // 为了简单， 硬编码， 且没有任何错误处理
    
44.       FILE* a = fopen("a", "rb");
    
45.       FILE* b = fopen("b", "wb");
    
46.       rc4_t g;
    
47. 
    
48.       rc4_ctor(&g, "1212", 4);
    
49.       for (int c; c=getc(a), c!=EOF;)
    
50.             putc( c ^ rc4_next(&g, b) );
    
51. 
    
52.       fclose(b);
    
53.       fclose(a);
    
54.       return 0;
    
55. }
    
56. 
    

复制代码

对比两种实现， 我觉得使用coroutine的伪代码版本更贴近算法本身。
而C/C++不支持coroutine， 不得由大脑分析出context是哪些， 并手工保存（如rc4_t）。

RC4加密， 我已经给出实现了。
而lua的那个例子， 我相信用C肯定是可以实现的。
但我认为这都不算coroutine。
理由是这些实现方式并没有体现出coroutine的任何优势， 尤其是脑力上的优势。
真正的coroutine不需要用户去考虑挂起点， 比如lua的例子， 用C实现的话要函数中设置一个状态机， 再按state去switch或者goto；
不需要用户去考虑哪些local variable是恢复执行时需要保存的context， 比如RC4中的S,i,j。

而当用户把这些状态机， context考虑清楚后， 实际上已经完成了人工实现coroutine所需要的脑力活动， 不需要coroutine也可以实现程序。
那还在程序中加入一个多数人一眼无法理解的机制做什么？ 直接按最朴质的方案做就是了。

OwnWaterloo

将下面这个lua的例子翻译为C好了：

function f() --> f分2个步骤， 可在执行完第1个步骤后挂起
  print('in', coroutine.running(), 'step1')
  --> 输出当前running只是为了下面的区分， 并不是重点
  coroutine.yield()
  print('in', coroutine.running(), 'step2')
end

c1 = coroutine.create(f) --> 建立2个coroutine
c2 = coroutine.create(f)
=c1 --> thread: 003ECC18 --> 输出coroutine的id
=c2 --> thread: 003EE738

-> 上面的coroutine.running
-> 只是为了这里能比较清楚的区分
coroutine.resume(c1) -> in      thread: 003ECC18        step1
coroutine.resume(c2) -> in      thread: 003EE738        step1
coroutine.resume(c2) -> in      thread: 003EE738        step2
coroutine.resume(c1) -> in      thread: 003ECC18        step2

OwnWaterloo

16楼 发表于 2010-12-18 00:37
本帖最后由 vupiggy 于 2010-12-17 17:45 编辑

这个……  你怎么做到的……

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。

haodahaozi

mark 研究下

ydfgic

switch case 的方法见到过，就是将一个完整的函数分割成多个部分的小函数的时候，这个手法很用