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

gvim

牛X。语法都清楚，能玩出来就是牛

wenkai169

感谢能阅读这么好的文章，虽然作者也说这种风格对未加训练的团队（也就是大家不熟悉这种太灵活的用法，或者你的队友和你不在同一个层次）不好。但这在驱动上也够用了。

xiaobenniao514

玩得不错，不过一般代码用来阅读和维护的

ydfgic

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

haodahaozi

mark 研究下

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。

OwnWaterloo

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

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

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

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

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. }
    

复制代码