Chinaunix

标题: switch-case 非常规用法拾零 (1. 绝无原创 2. 非常重视代码规范者勿入) [打印本页]
作者: vupiggy    时间: 2010-12-17 00:25
标题: switch-case 非常规用法拾零 (1. 绝无原创 2. 非常重视代码规范者勿入)
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    时间: 2010-12-17 00:25
本帖最后由 vupiggy 于 2010-12-16 17:31 编辑

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

下面一段小程序：

  2. do {
  3.     *to++ = *from++;
  4. } while (--count > 0);
复制代码
这段程序最让大牛们不爽的是，每拷贝一个字节就需要完成和拷贝字节同量级甚
至更耗时的减法及比较操作，一个可能的优化是减少循环次数，即在一次减法和
比较之后批处理拷贝几个字节，可能的代码如下：

  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 大叔巧妙的解决余数问题，代码如下：

  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    时间: 2010-12-17 00:26
本帖最后由 vupiggy 于 2010-12-16 17:31 编辑

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

2.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 也无济于事。一个可行的方案是：

  2. int function(void) {
  3.     static int i, state;

  5.     switch(state) {
  6.         case 0: goto LABEL0;
  7.         case 1: goto LABEL1;
  8.     }

  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 段可以置于块内的特点，上面的函
数可以改写成：

  2. int function(void) {
  3.     static int i, state = 0;

  5.     switch (state) {
  6.         case 0: /* start of function */

  8.         for (i = 0; i < 10; i++) {
  9.             state = 1; /* so we will come back to "case 1" */
  10.             return i;

  12.             case 1:; /* resume control straight after the return */
  13.         }
  14.     }
  15. }
复制代码
再进一步提高代码可读性，使用几个宏：

  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 }

  6. int function(void) {
  7.     static int i;

  9.     crBegin;

  11.     for (i = 0; i < 10; i++)
  12.         crReturn(1, i);

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

  2. #define crReturn(x) do { state=__LINE__; return x; case __LINE__:; } while (0)
复制代码
搞掂晒，程序员的重要品质就是能偷懒就偷懒，能不手工(眼工)做的就不做。

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

  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. }
复制代码

  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 的地方继续执行，否则就不
叫协作了。采用引子里提到的三个宏构建一个状态机即可完美解决协作需求：

  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    时间: 2010-12-17 00:28
3 后记

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

题外话，这个版事实上大多在讨论和 C/C++ 本身无关的话题，诸如网络编程，系
统编程，多线程多进程一类的其实都和 C/C++ 没什么关系。是不是可以考虑增加
系统编程子版面，有关系统调用，同步，socket 编程的都丢过去。另外，orz，
真不好意思，前两天我自己就把一个 Makefile 相关的东东丟在这个版里而不是
它本来应该在的shell版。
作者: flw    时间: 2010-12-17 10:13
coroutine 这个解决方案真牛！
作者: OwnWaterloo    时间: 2010-12-17 11:32
本帖最后由 OwnWaterloo 于 2010-12-17 11:33 编辑

我感觉这方案没能解决。

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    时间: 2010-12-17 12:28
这些代码非常漂亮,
为什么要说不尊重代码规范呢??
作者: action08    时间: 2010-12-17 12:32
不明白为什么有的coder喜欢用宏


这玩意玩不起,,,太强大了
作者: bluesea666    时间: 2010-12-17 14:20
对简单的应用， 搞那么复杂不如直接在外部写一个for循环。
对复杂的应用， 这种方案又不具备范化的可能。
OwnWaterloo 发表于 2010-12-17 11:32



    学习了.
作者: asdmonster    时间: 2010-12-17 14:32
mark下
作者: gvim    时间: 2010-12-17 14:50
牛X。语法都清楚，能玩出来就是牛
作者: wenkai169    时间: 2010-12-17 15:13
感谢能阅读这么好的文章，虽然作者也说这种风格对未加训练的团队（也就是大家不熟悉这种太灵活的用法，或者你的队友和你不在同一个层次）不好。但这在驱动上也够用了。
作者: xiaobenniao514    时间: 2010-12-17 15:21
玩得不错，不过一般代码用来阅读和维护的
作者: ydfgic    时间: 2010-12-17 17:01
switch case 的方法见到过，就是将一个完整的函数分割成多个部分的小函数的时候，这个手法很用
作者: haodahaozi    时间: 2010-12-17 23:55
mark 研究下
作者: vupiggy    时间: 2010-12-18 00:37
本帖最后由 vupiggy 于 2010-12-17 17:45 编辑

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

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

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

  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

使用方式：

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

  14.     crBegin(ssh->do_ssh_init_crstate);
复制代码
2. 提供一种机制区分yield和return —— 没有解决

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

  2. crReturn(EOF);
  3. crFinish;
复制代码
即告知调用者一次任务完成，cfFinish则开始善后，结束这个routine的生命周期。在putty里实际使用的代码像下面这样：

  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    时间: 2010-12-18 05:07
16楼 发表于 2010-12-18 00:37
本帖最后由 vupiggy 于 2010-12-17 17:45 编辑

这个……  你怎么做到的……
作者: OwnWaterloo    时间: 2010-12-18 05:09
标题: 关于非static的case， 能给出一个完整的例子么？
将下面这个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    时间: 2010-12-18 05:14
标题: RC4加密程序
本帖最后由 OwnWaterloo 于 2010-12-18 05:17 编辑

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流， 算法如下：

  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;

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

  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++完整实现

  2. #include <stdio.h>
  3. #include <algorithm>

  5. // 为了代码的可读性， 稍微用了一点C++的东西
  6. // 代码中有说明

  8. typedef struct
  9. {
  10.       unsigned i, j;
  11.       unsigned char s[256];
  12. } rc4_t;

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

  27. unsigend rc4_next(rc4_t* self)
  28. {
  29.       unsigend& i = self->i;
  30.       unsigend& j = self->j;
  31.       unsigend char* S = self->s;

  33.       // 使用引用是为了下面几行置换代码短一些
  34.       i = (i+1) % 256;
  35.       j = (j+S[i]) % 256;
  36.       std::swap(S[i], S[j]);

  38.       return S[ (S[i]+S[j]) % 256 ];
  39. }

  41. int main(void)
  42. {
  43.       // 为了简单， 硬编码， 且没有任何错误处理
  44.       FILE* a = fopen("a", "rb");
  45.       FILE* b = fopen("b", "wb");
  46.       rc4_t g;

  48.       rc4_ctor(&g, "1212", 4);
  49.       for (int c; c=getc(a), c!=EOF;)
  50.             putc( c ^ rc4_next(&g, b) );

  52.       fclose(b);
  53.       fclose(a);
  54.       return 0;
  55. }

复制代码
对比两种实现， 我觉得使用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    时间: 2010-12-18 05:29
标题: C下实现coroutine的库
C下实现coroutine的库 —— 不需要用户去考虑如何设置状态机， 保存context的方案—— 是有的。
coroutine的wiki页面应该就有介绍一些， 我没仔细研究。
用thread肯定可以实现， 但那代价太大， 只有理论上的价值。

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

coroutine的api。

  2. // coroutine.h

  4. typedef struct
  5. {
  6.       void* fiber_;
  7.       void (*f_)(void* x);
  8.       void* x_;
  9.       void* y_;
  10.       void* caller_;
  11. } coroutine_t;

  13. // 这是因为win32 fiber的限制
  14. // 每个使用fiber的thread必须首先做一些工作
  15. int   coroutine_init(void);

  17. int   coroutine_create(coroutine_t* self, void (*f)(void* x), void* x);
  18. // C没有垃圾收集等东西， 所以需要手动释放资源
  19. void  coroutine_destory(coroutine_t* self);

  21. // resume返回yield的参数
  22. void* coroutine_resume(coroutine_t* self);
  23. void  coroutine_yield(void* val);

  25. // 同lua coroutine.running
  26. void* coroutine_running(void);

复制代码
那么， lua的例子就可以改写为：

  2. // lua_example.c

  4. #include <stdio.h>

  6. #include "coroutine.h"

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

  15. int main(void)
  16. {
  17.       coroutine_t c1, c2;

  19.       coroutine_init();

  21.       coroutine_create(&c1, f, 0);
  22.       coroutine_create(&c2, f, 0);

  24.       printf("coroutine1 %p\n", (void*)&c1);
  25.       printf("coroutine2 %p\n", (void*)&c2);

  27.       coroutine_resume(&c1);
  28.       coroutine_resume(&c2);
  29.       coroutine_resume(&c2);
  30.       coroutine_resume(&c1);

  32.       coroutine_destory(&c2);
  33.       coroutine_destory(&c1);

  35.       return 0;
  36. }
复制代码
使用coroutine的rc4：

  2. // rc4.cpp

  4. #include <stdio.h>
  5. #include <string.h>
  6. #include <algorithm>

  8. #include "coroutine.h"

  10. void rc4_stream(void* arg)
  11. {
  12.       unsigned char* key = (unsigned char*)arg;
  13.       unsigned char S[256];

  15.       for (unsigned i=0; i<256; ++i)
  16.             S[i] = i;

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

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

  33. int main(void)
  34. {
  35.       FILE* a = fopen("a", "rb");
  36.       FILE* b = fopen("b", "wb");
  37.       coroutine_t g;

  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语言缺了哪些东西。

  2. // coroutine.c

  4. #define _WIN32_WINNT 0x0400
  5. #include <windows.h>

  7. #include "coroutine.h"

  9. int  coroutine_init()
  10. {
  11.       return ConvertThreadToFiber(0) != 0;
  12. }

  14. void* coroutine_running(void)
  15. {
  16.       return GetFiberData();
  17. }

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

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

  35. void  coroutine_destory(coroutine_t* self)
  36. {
  37.       DeleteFiber(self->fiber_);
  38. }

  40. void* coroutine_resume(coroutine_t* self)
  41. {
  42.       self->caller_ = GetCurrentFiber();
  43.       SwitchToFiber(self->fiber_);
  44.       return self->y_;
  45. }

  47. void coroutine_yield(void* val)
  48. {
  49.       coroutine_t* self = (coroutine_t*)GetFiberData();
  50.       self->y_ = val;
  51.       SwitchToFiber(self->caller_);
  52. }
复制代码
作者: OwnWaterloo    时间: 2010-12-18 05:36
先说coroutine的状态

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

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

  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);
范化的解决办法就是：


  3. typedef struct
  4. {
  5.       char const* key;
  6.       size_t len;
  7. } rc4_arg_t;

  9. void rc4_stream(void* x)
  10. {
  11.       rc4_arg_t* arg = (rc4_arg_t*)x;
  12.       rc4_stream(arg->key, arg->len);
  13. }

  15. rc4_arg_t arg = { "1212", 4 };
  16. coroutine_create( ..., &arg);
复制代码
实际代码中只是取巧使用strlen来减少一个参数。
对更一般的例子， 就必须迂回一次。


最后看yield的返回值

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

所有的这些加起来， 得到的结果就是在C中使用coroutine会非常麻烦， 能避免，就尽量避免。
作者: OwnWaterloo    时间: 2010-12-18 05:58
本帖最后由 OwnWaterloo 于 2010-12-18 06:08 编辑

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

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

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

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


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


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

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

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

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

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



欢迎光临 Chinaunix (http://bbs.chinaunix.net/) Powered by Discuz! X3.2