娱乐一下,介绍一种语言——brainfuck

chzCPU

好,不错

cjaizss

最新的优化,一般说来,运算效率可能比之前最后一个提高%50甚至更多。(因为一个程序中一般都有数据复制或者累计的动作，而bf中都是通过反复循环仿真出来的)

1. 
   
2. /*bf.c*/
   
3. #include <stdio.h>
   
4. #include <stdlib.h>
   
5. #include <string.h>
   
6. char s[30000]={0};
   
7. char code[100000];
   
8. int len = 0;
   
9. int  stack[100];
   
10. int stack_len=0;
    
11. #ifndef DEBUG
    
12. #define DEBUG 0
    
13. #endif
    
14. int main(int argc,char**argv)
    
15. {
    
16.         char c;
    
17.         int i,j,k,left_flag,left_offset,x=0;
    
18.         int x1,x2,x3,x4;
    
19.         int m,n;
    
20.         FILE* f;
    
21.         char* p=s+10000;
    
22.         if(argc==2) {
    
23.                 f=fopen(argv[1],"r");
    
24.                 if(f==NULL) {
    
25.                         perror("fopen");
    
26.                                 return 1;
    
27.                 }
    
28.                 len=fread(code,1,sizeof(code),f);
    
29.                 if(len==0&&len==sizeof(code)) {
    
30.                         return 4;
    
31.                 }
    
32.         } else return 2;
    
33. 
    
34.         /*optimization*/
    
35.         /*We can prove that n is never greater than m.So we can use the same memory*/
    
36.         for(m=0,n=0,c=0,j=0,left_flag=0;m<len;m++) {
    
37.                 switch(code[m]) {
    
38.                         case '+':
    
39.                                 switch (j) {
    
40.                                         case 1:
    
41.                                                 code[n++]='>';
    
42.                                                 break;
    
43.                                         case -1:
    
44.                                                 code[n++]='<';
    
45.                                                 break;
    
46.                                         case 0:
    
47.                                                 break;
    
48.                                         default:
    
49.                                                 code[n++]='p';
    
50.                                                 code[n++]=j;
    
51.                                                 break;
    
52.                                 }
    
53.                                 j=0;
    
54.                                 c++;
    
55.                                 break;
    
56.                         case '-':
    
57.                                 switch (j) {
    
58.                                         case 1:
    
59.                                                 code[n++]='>';
    
60.                                                 break;
    
61.                                         case -1:
    
62.                                                 code[n++]='<';
    
63.                                                 break;
    
64.                                         case 0:
    
65.                                                 break;
    
66.                                         default:
    
67.                                                 code[n++]='p';
    
68.                                                 code[n++]=j;
    
69.                                                 break;
    
70.                                 }
    
71.                                 j=0;
    
72.                                 c--;
    
73.                                 break;
    
74.                         case '>':
    
75.                                 switch (c) {
    
76.                                         case ((char)1):
    
77.                                                 code[n++]='+';
    
78.                                                 break;
    
79.                                         case ((char)(-1)):
    
80.                                                 code[n++]='-';
    
81.                                                 break;
    
82.                                         case ((char)0):
    
83.                                                 break;
    
84.                                         default:
    
85.                                                 code[n++]='a';
    
86.                                                 code[n++]=c;
    
87.                                                 break;
    
88.                                 }
    
89.                                 c=0;
    
90.                                 j++;
    
91.                                 if(j==0x7f) {
    
92.                                         code[n++]='p';
    
93.                                         code[n++]=0x7f;
    
94.                                         j=0;
    
95.                                 }
    
96.                                 break;
    
97.                         case '<':
    
98.                                 switch (c) {
    
99.                                         case ((char)1):
    
100.                                                 code[n++]='+';
     
101.                                                 break;
     
102.                                         case ((char)(-1)):
     
103.                                                 code[n++]='-';
     
104.                                                 break;
     
105.                                         case ((char)0):
     
106.                                                 break;
     
107.                                         default:
     
108.                                                 code[n++]='a';
     
109.                                                 code[n++]=c;
     
110.                                                 break;
     
111.                                 }
     
112.                                 c=0;
     
113.                                 j--;
     
114.                                 if(j==-128) {
     
115.                                         code[n++]='p';
     
116.                                         code[n++]=-128;
     
117.                                         j=0;
     
118.                                 }
     
119.                                 break;
     
120.                         case '.':
     
121.                         case ',':
     
122.                         case '[':
     
123.                                 switch (c) {
     
124.                                         case ((char)1):
     
125.                                                 code[n++]='+';
     
126.                                                 break;
     
127.                                         case ((char)(-1)):
     
128.                                                 code[n++]='-';
     
129.                                                 break;
     
130.                                         case ((char)0):
     
131.                                                 break;
     
132.                                         default:
     
133.                                                 code[n++]='a';
     
134.                                                 code[n++]=c;
     
135.                                                 break;
     
136.                                 }
     
137.                                 c=0;
     
138.                                 switch (j) {
     
139.                                         case 1:
     
140.                                                 code[n++]='>';
     
141.                                                 break;
     
142.                                         case -1:
     
143.                                                 code[n++]='<';
     
144.                                                 break;
     
145.                                         case 0:
     
146.                                                 break;
     
147.                                         default:
     
148.                                                 code[n++]='p';
     
149.                                                 code[n++]=j;
     
150.                                                 break;
     
151.                                 }
     
152.                                 j=0;
     
153.                                 code[n++]=code[m];
     
154.                                 if(code[m]=='[') {
     
155.                                         left_flag=1;
     
156.                                         left_offset=n;
     
157.                                 }
     
158.                                 break;
     
159.                         case ']':
     
160.                                 switch (c) {
     
161.                                         case ((char)1):
     
162.                                                 code[n++]='+';
     
163.                                                 break;
     
164.                                         case ((char)(-1)):
     
165.                                                 code[n++]='-';
     
166.                                                 break;
     
167.                                         case ((char)0):
     
168.                                                 break;
     
169.                                         default:
     
170.                                                 code[n++]='a';
     
171.                                                 code[n++]=c;
     
172.                                                 break;
     
173.                                 }
     
174.                                 c=0;
     
175.                                 switch (j) {
     
176.                                         case 1:
     
177.                                                 code[n++]='>';
     
178.                                                 break;
     
179.                                         case -1:
     
180.                                                 code[n++]='<';
     
181.                                                 break;
     
182.                                         case 0:
     
183.                                                 break;
     
184.                                         default:
     
185.                                                 code[n++]='p';
     
186.                                                 code[n++]=j;
     
187.                                                 break;
     
188.                                 }
     
189.                                 j=0;
     
190.                                 if(n-1>=0&&n-2>=0&&code[n-2]=='['&&(code[n-1]=='+'||code[n-2]=='-')) {
     
191.                                         code[n-2]='0';
     
192.                                         n--;
     
193.                                 } else {
     
194.                                         code[n++]=code[m];
     
195.                                         if(left_flag) {
     
196.                                                 for(i=left_offset,x1=x2=x3=0,x4=n+1;i<n;i++) {
     
197.                                                         switch(code[i]) {
     
198.                                                                 case '+':
     
199.                                                                         if(x2==0) {
     
200.                                                                                 if(x3) {
     
201.                                                                                         i=n;
     
202.                                                                                         break;
     
203.                                                                                 }
     
204.                                                                                 x3=1;
     
205.                                                                                 break;
     
206.                                                                         }
     
207.                                                                         code[x4++] = 0x80|(x2&0x7f);
     
208.                                                                         code[x4++] = 1;
     
209.                                                                         break;
     
210.                                                                 case '-':
     
211.                                                                         if(x2==0) {
     
212.                                                                                 if(x3) {
     
213.                                                                                         i=n;
     
214.                                                                                         break;
     
215.                                                                                 }
     
216.                                                                                 x3=-1;
     
217.                                                                                 break;
     
218.                                                                         }
     
219.                                                                         code[x4++] = 0x80|(x2&0x7f);
     
220.                                                                         code[x4++] = -1;
     
221.                                                                         break;
     
222.                                                                 case 'a':
     
223.                                                                         if(x2==0)
     
224.                                                                                 i=n;//quit
     
225.                                                                         code[x4++] = 0x80|(x2&0x7f);
     
226.                                                                         if(code[i+1]==(char)0x80) {
     
227.                                                                                 i=n;//quit
     
228.                                                                                 break;
     
229.                                                                         }
     
230.                                                                         code[x4++] = code[i+1];
     
231.                                                                         i++;
     
232.                                                                         break;
     
233.                                                                 case 'p':
     
234.                                                                         x2+=(unsigned char)code[i++];
     
235.                                                                         if(x2>63||x2<-64) {
     
236.                                                                                 i=n;//quit
     
237.                                                                         }
     
238.                                                                         break;
     
239.                                                                 case '<':
     
240.                                                                         x2--;
     
241.                                                                         if(x2>63||x2<-64) {
     
242.                                                                                 i=n;//quit
     
243.                                                                         }
     
244.                                                                         break;
     
245.                                                                 case '>':
     
246.                                                                         x2++;
     
247.                                                                         if(x2>63||x2<-64) {
     
248.                                                                                 i=n;//quit
     
249.                                                                         }
     
250.                                                                         break;
     
251.                                                                 case ']':
     
252.                                                                         if(!x3||x2) {
     
253.                                                                                 break;/***It can not be optimized******/
     
254.                                                                         }
     
255.                                                                         if(x3==-1) {
     
256.                                                                                 memcpy(&code[left_offset-1],&code[n+1],x4-n-1);
     
257.                                                                                 code[x4-n-1+left_offset-1]='0';
     
258.                                                                                 n=x4-n-1+left_offset-1+1;
     
259.                                                                                 /***Then, i must be greater than n*******/
     
260.                                                                         } else {
     
261.                                                                                 for(x1=left_offset-1,x2=n+1;x2<x4;x1+=2,x2+=2) {
     
262.                                                                                         code[x1]=code[x2];
     
263.                                                                                         code[x1+1]=-code[x2+1];
     
264.                                                                                 }
     
265.                                                                                 code[x4-n-1+left_offset-1]='0';
     
266.                                                                                 n=x4-n-1+left_offset-1+1;
     
267.                                                                                 /***Then, i must be greater than n*******/
     
268.                                                                         }
     
269.                                                                         break;
     
270.                                                                 /*
     
271.                                                                 case '[':
     
272.                                                                 case '.':
     
273.                                                                 case ',':*/
     
274.                                                                 default:
     
275.                                                                         i=n;//quit
     
276.                                                                         break;
     
277.                                                         }/*swtich(code[i])*/
     
278.                                                 }/*for(i=left_offset,x1=x2=x3=x4=0;i<n;i++)*/
     
279.                                         } else {
     
280.                                         }
     
281.                                 }
     
282.                                 left_flag=0;
     
283.                                 break;
     
284.                         default:
     
285.                                 break;
     
286.                 }/*switch(code[m])*/
     
287.         }/*for(m=0,n=0,c=0,j=0,left_flag=0;m<len;m++)*/
     
288.         len=n;
     
289.         setbuf(stdout,NULL);
     
290. #if DEBUG>2
     
291.         for(i=0;i<len;i++)
     
292.                 putchar(code[i]);
     
293.         return 0;
     
294. #endif
     
295.         i=0;
     
296.         while(i<len) {
     
297.                 switch(code[i]) {
     
298.                         case '0':
     
299.                                 *p=0;
     
300.                                 break;
     
301.                         case 'a':
     
302.                                 i++;
     
303.                                 *p+=(signed char)code[i];
     
304.                                 break;
     
305.                         case 'p':
     
306.                                 i++;
     
307.                                 p+=(signed char)code[i];
     
308.                                 break;
     
309.                         case '+':
     
310.                                 (*p)++;
     
311.                                 break;
     
312.                         case '-':
     
313.                                 (*p)--;
     
314.                                 break;
     
315.                         case '>':
     
316.                                 p++;
     
317.                                 break;
     
318.                         case '<':
     
319.                                 p--;
     
320.                                 break;
     
321.                         case '.':
     
322.                                 putchar((int)(*p));
     
323.                                 //printf("put:%hd\n",*p);
     
324.                                 break;
     
325.                         case ',':
     
326.                                 *p=getchar();
     
327.                                 break;
     
328.                         case '[':
     
329.                                 if(*p) {
     
330.                                         stack[stack_len++]=i;
     
331.                                 } else {
     
332.                                         for(k=i,j=0;k<len;k++) {
     
333.                                                 //if(code[k]=='a'||code[k]=='p'||code[k]&0x80) {
     
334.                                                 /**replaced by*****/
     
335.                                                 if((unsigned char)code[k]>=(unsigned char)'a') {
     
336.                                                         k++;
     
337.                                                         continue;
     
338.                                                 }
     
339.                                                 code[k]=='['&&j++;
     
340.                                                 code[k]==']'&&j--;
     
341.                                                 if(j==0)break;
     
342.                                         }
     
343.                                         if(j==0)
     
344.                                                 i=k;
     
345.                                         else {
     
346.                                                 fprintf(stderr,"%s:%d\n",__FILE__,__LINE__);
     
347.                                                 return 3;
     
348.                                         }
     
349.                                 }
     
350.                                 break;
     
351.                         case ']':
     
352.                                 if(*p) {
     
353.                                         i=stack[stack_len - 1];
     
354.                                         #if DEBUG>0
     
355.                                         if(code[i] != '[') {
     
356.                                                 fprintf(stderr,"%s:%d\n",__FILE__,__LINE__);
     
357.                                                 return 0;
     
358.                                         }
     
359.                                         #endif
     
360.                                 } else {
     
361.                                         stack_len--;
     
362.                                 }
     
363.                                 break;
     
364.                         default:
     
365.                                 #if DEBUG>1
     
366.                                 if(code[i]&0x80)break;
     
367.                                 #endif
     
368.                                 p[(signed char)(code[i]&(code[i]&0x40?0xff:0x7f))]+=*p*((signed char)code[i+1]);
     
369.                                 i++;
     
370.                                 break;
     
371.                 }
     
372.                 i++;
     
373.                 //x++;
     
374.                 //printf("%d : i=%d\n",x,i);
     
375.         }
     
376.         return 0;
     
377. }
     
378. 
     

复制代码

[ 本帖最后由 cjaizss 于 2008-6-9 18:03 编辑 ]

cjaizss

以下为最新的解释器优化39楼的自举编译器所生成的过程代码：

1. 
   
2. linux-0gt0:/tmp/ch/a2 # gcc -DDEBUG=3 bf.c -o bf
   
3. linux-0gt0:/tmp/ch/a2 # ./bf bf2c.bf | od -c
   
4. 0000000   a   #   .   a   F   .   a 005   .   a 365   .   a  \t   .   a
   
5. 0000020  \t   .   a 357   .   +   .   a 273   .   a 034   .   a   7   .
   
6. 0000040   +   .   a 360   .   a 005   .   a 006   .   a 277   .   a   :
   
7. 0000060   .   a 326   .   a 314   .   a 031   .   a   F   .   a 005   .
   
8. 0000100   a 365   .   a  \t   .   a  \t   .   a 357   .   +   .   a 273
   
9. 0000120   .   a 034   .   a   7   .   +   .   a 360   .   a  \b   .   a
   
10. 0000140 375   .   a 371   .   a 314   .   a   :   .   a 326   .   a 314
    
11. 0000160   .   a 031   .   a   A   .   +   .   +   .   a 003   .   a 005
    
12. 0000200   .   a 367   .   a 273   .   a   !   .   a 337   .   a  \v   .
    
13. 0000220   .   -   .   a   F   .   a 313   .   a 317   .   a 031   .   a
    
14. 0000240   A   .   +   .   +   .   a 003   .   a 005   .   a 367   .   a
    
15. 0000260 273   .   a   "   .   a 336   .   a  \n   .   a   F   .   a 315
    
16. 0000300   .   a   *   .   a 376   .   a 017   .   a 357   .   a 005   .
    
17. 0000320   a 371   .   a 021   .   a 266   .   +   .   a 022   .   a 317
    
18. 0000340   .   a 031   .   a   A   .   +   .   +   .   a 003   .   a 005
    
19. 0000360   .   a 367   .   a 273   .   a   #   .   a 335   .   a  \r   .
    
20. 0000400   .   a 375   .   a   F   .   a 313   .   a 317   .   a 031   .
    
21. 0000420   a   A   .   +   .   +   .   a 003   .   a 005   .   a 367   .
    
22. 0000440   a 273   .   a   $   .   a 334   .   a   P   .   a 005   .   -
    
23. 0000460   .   a 357   .   a 005   .   a 371   .   a 021   .   a 266   .
    
24. 0000500   a 002   .   a   F   .   a 271   .   a 022   .   a 317   .   a
    
25. 0000520 031   .   a   A   .   +   .   +   .   a 003   .   a 005   .   a
    
26. 0000540 367   .   a 273   .   a   %   .   a 333   .   a   P   .   a 275
    
27. 0000560   .   .   a 016   .   a 317   .   a 031   .   a   A   .   +   .
    
28. 0000600   +   .   a 003   .   a 005   .   a 367   .   a 273   .   a   &
    
29. 0000620   .   a 332   .   a   P   .   a 273   .   .   a 020   .   a 317
    
30. 0000640   .   a 031   .   a   A   .   +   .   +   .   a 003   .   a 005
    
31. 0000660   .   a 367   .   a 273   .   a   '   .   a 331   .   a   W   .
    
32. 0000700   a 361   .   +   .   a 003   .   a 371   .   a 303   .   a 002
    
33. 0000720   .   a   F   .   a 271   .   a   R   .   a 217   .   a 031   .
    
34. 0000740   a   A   .   +   .   +   .   a 003   .   a 005   .   a 367   .
    
35. 0000760   a 273   .   a   (   .   a 330   .   a   ]   .   a 215   .   a
    
36. 0001000   Y   .   a 005   .   a 371   .   a 021   .   a 256   .   a   R
    
37. 0001020   .   a 351   .   a 331   .   a 374   .   .   .   .   a   -   .
    
38. 0001040   a 340   .   a   >   .   a 265   .   a   M   .   a 276   .   a
    
39. 0001060   .   .   a 005   .   a 006   .   a 254   .   a   M   .   a 364
    
40. 0001100   .   a  \b   .   a 005   .   a 272   .   a   N   .   a 371   .
    
41. 0001120   a 372   .   a 373   .   a 305   .   a   R   .   a 350   .   a
    
42. 0001140 005   .   a 371   .   a 021   .   a 270   .   a   F   .   a 315
    
43. 0001160   .   a   5   .   a 271   .   a 006   .   -   .   .   .   .   a
    
44. 0001200  \v   .   a 317   .   .   p 002   +   [   ,   +   [   [   -   p
    
45. 0001220 002   +   >   +   >   +   >   +   >   +   >   +   >   +   >   +
    
46. 0001240   p 367   ]   +   p 002   a 324   [   <   0   +   >   -   ]   <
    
47. 0001260   -   [   a   B   .   0   a  \t   .   0   ]   p 002   a 323   [
    
48. 0001300   p 376   0   +   p 002   -   ]   p 376   -   [   a   C   .   0
    
49. 0001320   a  \t   .   0   ]   p 003   a 322   [   p 375   0   +   p 003
    
50. 0001340   -   ]   p 375   -   [   a   D   .   0   a  \t   .   0   ]   p
    
51. 0001360 004   a 321   [   p 374   0   +   p 004   -   ]   p 374   -   [
    
52. 0001400   a   E   .   0   a  \t   .   0   ]   p 005   a 303   [   p 373
    
53. 0001420   0   +   p 005   -   ]   p 373   -   [   a   F   .   0   a  \t
    
54. 0001440   .   0   ]   p 006   a 301   [   p 372   0   +   p 006   -   ]
    
55. 0001460   p 372   -   [   a   G   .   0   a  \t   .   0   ]   p  \a   a
    
56. 0001500 244   [   p 371   0   +   p  \a   -   ]   p 371   -   [   a   H
    
57. 0001520   .   0   a  \t   .   0   ]   p  \b   a 242   [   p 370   0   +
    
58. 0001540   p  \b   -   ]   p 370   -   [   a   I   .   0   a  \t   .   0
    
59. 0001560   ]   ]   <   ]   0   a   r   .   a 363   .   a 017   .   +   .
    
60. 0001600   a 375   .   a 374   .   a 262   .   a 020   .   a  \v   .   a
    
61. 0001620   B   .   0   a  \n   .
    
62. 0001626
    

复制代码

cjaizss

又为查找匹配的右方括号建立了"cache",可是这几乎没用，因为在我的解释器里，只有第一次遇到该循环（就是遇到左中括号）的时候因*p==0才不得不找到所匹配的右中括号，以便找到下一个执行点，而这种情况少见。一般时候都是靠右边括号来判断是否跳出循环，而回到该循环体的首部是借助左边括号入栈，所以很快。
但我还是给出了这个"cache",
编译可以定义USE_MATCH_TABLE宏以便加入这个结构，也可以定义cache深度MAX_DEPTH（我并不希望它无限，虽然可以办到，但那样反而不好，不定义则默认为2）
例如
gcc -DUSE_MATCH_TABLE -DMAX_DEPTH=1 bf.c -o bf -O2

1. 
   
2. /*bf.c*/
   
3. #include <stdio.h>
   
4. #include <stdlib.h>
   
5. #include <string.h>
   
6. char s[30000]={0};
   
7. char code[100000];
   
8. int len = 0;
   
9. int  stack[100];
   
10. int stack_len=0;
    
11. #ifndef DEBUG
    
12. #define DEBUG 0
    
13. #endif
    
14. #ifdef USE_MATCH_TABLE
    
15. #if (!defined(MAX_DEPTH)) || MAX_DEPTH<=0
    
16. #define MAX_DEPTH 2
    
17. #endif
    
18. typedef struct _match_des_t{
    
19.         int left_offset;
    
20.         int right_offset;
    
21.         struct _match_des_t* next;
    
22. }match_des_t;
    
23. typedef struct {
    
24.         int depth;
    
25.         match_des_t* first;
    
26. }  match_table_t;
    
27. match_table_t match_table[256]={{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0},{.depth=0}
    
28. };
    
29. static inline int search_match(int left)
    
30. {
    
31.         int i;
    
32.         match_des_t* pmatch_des;
    
33.         match_table_t* pmatch_table=&match_table[left&0xff];
    
34.         if(pmatch_table->depth==0)
    
35.                 return 0;
    
36.         for(i=0,pmatch_des=pmatch_table->first;i<pmatch_table->depth;i++) {
    
37.                 if(pmatch_des->left_offset==left)
    
38.                         return pmatch_des->right_offset;
    
39.                 pmatch_des=pmatch_des->next;
    
40.         }
    
41.         return 0;
    
42. }
    
43. static inline void add_match(int left,int right)
    
44. {
    
45.         match_des_t* pmatch_des;
    
46.         match_table_t* pmatch_table=&match_table[left&0xff];
    
47.         switch(pmatch_table->depth) {
    
48.                 case 0:
    
49.                         pmatch_table->first=malloc(sizeof(match_des_t));
    
50.                         if(pmatch_table->first==NULL) {
    
51.                                 fprintf(stderr,"%s:%d\n",__FILE__,__LINE__);
    
52.                                 exit(6);
    
53.                         }
    
54.                         pmatch_table->first->left_offset=left;
    
55.                         pmatch_table->first->right_offset=right;
    
56.                         pmatch_table->depth=1;
    
57.                         break;
    
58.                 case MAX_DEPTH:
    
59.                         pmatch_table->first->left_offset=left;
    
60.                         pmatch_table->first->right_offset=right;
    
61.                         break;
    
62.                 default:
    
63.                         pmatch_des = pmatch_table->first;
    
64.                         pmatch_table->first=malloc(sizeof(match_des_t));
    
65.                         if(pmatch_table->first==NULL) {
    
66.                                 fprintf(stderr,"%s:%d\n",__FILE__,__LINE__);
    
67.                                 exit(6);
    
68.                         }
    
69.                         pmatch_table->first->left_offset=left;
    
70.                         pmatch_table->first->right_offset=right;
    
71.                         pmatch_table->first->next=pmatch_des;
    
72.                         pmatch_table->depth++;
    
73.                         break;
    
74.         }
    
75. }
    
76. #endif
    
77. int main(int argc,char**argv)
    
78. {
    
79.         char c;
    
80.         int i,j,k,left_flag,left_offset,x=0;
    
81.         int x1,x2,x3,x4;
    
82.         int m,n;
    
83.         FILE* f;
    
84.         char* p=s+10000;
    
85.         if(argc==2) {
    
86.                 f=fopen(argv[1],"r");
    
87.                 if(f==NULL) {
    
88.                         perror("fopen");
    
89.                                 return 1;
    
90.                 }
    
91.                 len=fread(code,1,sizeof(code),f);
    
92.                 if(len==0&&len==sizeof(code)) {
    
93.                         return 4;
    
94.                 }
    
95.         } else return 2;
    
96. 
    
97.         /*optimization*/
    
98.         /*We can prove that n is never greater than m.So we can use the same memory*/
    
99.         for(m=0,n=0,c=0,j=0,left_flag=0;m<len;m++) {
    
100.                 switch(code[m]) {
     
101.                         case '+':
     
102.                                 switch (j) {
     
103.                                         case 1:
     
104.                                                 code[n++]='>';
     
105.                                                 break;
     
106.                                         case -1:
     
107.                                                 code[n++]='<';
     
108.                                                 break;
     
109.                                         case 0:
     
110.                                                 break;
     
111.                                         default:
     
112.                                                 code[n++]='p';
     
113.                                                 code[n++]=j;
     
114.                                                 break;
     
115.                                 }
     
116.                                 j=0;
     
117.                                 c++;
     
118.                                 break;
     
119.                         case '-':
     
120.                                 switch (j) {
     
121.                                         case 1:
     
122.                                                 code[n++]='>';
     
123.                                                 break;
     
124.                                         case -1:
     
125.                                                 code[n++]='<';
     
126.                                                 break;
     
127.                                         case 0:
     
128.                                                 break;
     
129.                                         default:
     
130.                                                 code[n++]='p';
     
131.                                                 code[n++]=j;
     
132.                                                 break;
     
133.                                 }
     
134.                                 j=0;
     
135.                                 c--;
     
136.                                 break;
     
137.                         case '>':
     
138.                                 switch (c) {
     
139.                                         case ((char)1):
     
140.                                                 code[n++]='+';
     
141.                                                 break;
     
142.                                         case ((char)(-1)):
     
143.                                                 code[n++]='-';
     
144.                                                 break;
     
145.                                         case ((char)0):
     
146.                                                 break;
     
147.                                         default:
     
148.                                                 code[n++]='a';
     
149.                                                 code[n++]=c;
     
150.                                                 break;
     
151.                                 }
     
152.                                 c=0;
     
153.                                 j++;
     
154.                                 if(j==0x7f) {
     
155.                                         code[n++]='p';
     
156.                                         code[n++]=0x7f;
     
157.                                         j=0;
     
158.                                 }
     
159.                                 break;
     
160.                         case '<':
     
161.                                 switch (c) {
     
162.                                         case ((char)1):
     
163.                                                 code[n++]='+';
     
164.                                                 break;
     
165.                                         case ((char)(-1)):
     
166.                                                 code[n++]='-';
     
167.                                                 break;
     
168.                                         case ((char)0):
     
169.                                                 break;
     
170.                                         default:
     
171.                                                 code[n++]='a';
     
172.                                                 code[n++]=c;
     
173.                                                 break;
     
174.                                 }
     
175.                                 c=0;
     
176.                                 j--;
     
177.                                 if(j==-128) {
     
178.                                         code[n++]='p';
     
179.                                         code[n++]=-128;
     
180.                                         j=0;
     
181.                                 }
     
182.                                 break;
     
183.                         case '.':
     
184.                         case ',':
     
185.                         case '[':
     
186.                                 switch (c) {
     
187.                                         case ((char)1):
     
188.                                                 code[n++]='+';
     
189.                                                 break;
     
190.                                         case ((char)(-1)):
     
191.                                                 code[n++]='-';
     
192.                                                 break;
     
193.                                         case ((char)0):
     
194.                                                 break;
     
195.                                         default:
     
196.                                                 code[n++]='a';
     
197.                                                 code[n++]=c;
     
198.                                                 break;
     
199.                                 }
     
200.                                 c=0;
     
201.                                 switch (j) {
     
202.                                         case 1:
     
203.                                                 code[n++]='>';
     
204.                                                 break;
     
205.                                         case -1:
     
206.                                                 code[n++]='<';
     
207.                                                 break;
     
208.                                         case 0:
     
209.                                                 break;
     
210.                                         default:
     
211.                                                 code[n++]='p';
     
212.                                                 code[n++]=j;
     
213.                                                 break;
     
214.                                 }
     
215.                                 j=0;
     
216.                                 code[n++]=code[m];
     
217.                                 if(code[m]=='[') {
     
218.                                         left_flag=1;
     
219.                                         left_offset=n;
     
220.                                 }
     
221.                                 break;
     
222.                         case ']':
     
223.                                 switch (c) {
     
224.                                         case ((char)1):
     
225.                                                 code[n++]='+';
     
226.                                                 break;
     
227.                                         case ((char)(-1)):
     
228.                                                 code[n++]='-';
     
229.                                                 break;
     
230.                                         case ((char)0):
     
231.                                                 break;
     
232.                                         default:
     
233.                                                 code[n++]='a';
     
234.                                                 code[n++]=c;
     
235.                                                 break;
     
236.                                 }
     
237.                                 c=0;
     
238.                                 switch (j) {
     
239.                                         case 1:
     
240.                                                 code[n++]='>';
     
241.                                                 break;
     
242.                                         case -1:
     
243.                                                 code[n++]='<';
     
244.                                                 break;
     
245.                                         case 0:
     
246.                                                 break;
     
247.                                         default:
     
248.                                                 code[n++]='p';
     
249.                                                 code[n++]=j;
     
250.                                                 break;
     
251.                                 }
     
252.                                 j=0;
     
253.                                 if(n-1>=0&&n-2>=0&&code[n-2]=='['&&(code[n-1]=='+'||code[n-2]=='-')) {
     
254.                                         code[n-2]='0';
     
255.                                         n--;
     
256.                                 } else {
     
257.                                         code[n++]=code[m];
     
258.                                         if(left_flag) {
     
259.                                                 for(i=left_offset,x1=x2=x3=0,x4=n+1;i<n;i++) {
     
260.                                                         switch(code[i]) {
     
261.                                                                 case '+':
     
262.                                                                         if(x2==0) {
     
263.                                                                                 if(x3) {
     
264.                                                                                         i=n;
     
265.                                                                                         break;
     
266.                                                                                 }
     
267.                                                                                 x3=1;
     
268.                                                                                 break;
     
269.                                                                         }
     
270.                                                                         code[x4++] = 0x80|(x2&0x7f);
     
271.                                                                         code[x4++] = 1;
     
272.                                                                         break;
     
273.                                                                 case '-':
     
274.                                                                         if(x2==0) {
     
275.                                                                                 if(x3) {
     
276.                                                                                         i=n;
     
277.                                                                                         break;
     
278.                                                                                 }
     
279.                                                                                 x3=-1;
     
280.                                                                                 break;
     
281.                                                                         }
     
282.                                                                         code[x4++] = 0x80|(x2&0x7f);
     
283.                                                                         code[x4++] = -1;
     
284.                                                                         break;
     
285.                                                                 case 'a':
     
286.                                                                         if(x2==0)
     
287.                                                                                 i=n;//quit
     
288.                                                                         code[x4++] = 0x80|(x2&0x7f);
     
289.                                                                         if(code[i+1]==(char)0x80) {
     
290.                                                                                 i=n;//quit
     
291.                                                                                 break;
     
292.                                                                         }
     
293.                                                                         code[x4++] = code[i+1];
     
294.                                                                         i++;
     
295.                                                                         break;
     
296.                                                                 case 'p':
     
297.                                                                         x2+=(unsigned char)code[i++];
     
298.                                                                         if(x2>63||x2<-64) {
     
299.                                                                                 i=n;//quit
     
300.                                                                         }
     
301.                                                                         break;
     
302.                                                                 case '<':
     
303.                                                                         x2--;
     
304.                                                                         if(x2>63||x2<-64) {
     
305.                                                                                 i=n;//quit
     
306.                                                                         }
     
307.                                                                         break;
     
308.                                                                 case '>':
     
309.                                                                         x2++;
     
310.                                                                         if(x2>63||x2<-64) {
     
311.                                                                                 i=n;//quit
     
312.                                                                         }
     
313.                                                                         break;
     
314.                                                                 case ']':
     
315.                                                                         if(!x3||x2) {
     
316.                                                                                 break;/***It can not be optimized******/
     
317.                                                                         }
     
318.                                                                         if(x3==-1) {
     
319.                                                                                 memcpy(&code[left_offset-1],&code[n+1],x4-n-1);
     
320.                                                                                 code[x4-n-1+left_offset-1]='0';
     
321.                                                                                 n=x4-n-1+left_offset-1+1;
     
322.                                                                                 /***Then, i must be greater than n*******/
     
323.                                                                         } else {
     
324.                                                                                 for(x1=left_offset-1,x2=n+1;x2<x4;x1+=2,x2+=2) {
     
325.                                                                                         code[x1]=code[x2];
     
326.                                                                                         code[x1+1]=-code[x2+1];
     
327.                                                                                 }
     
328.                                                                                 code[x4-n-1+left_offset-1]='0';
     
329.                                                                                 n=x4-n-1+left_offset-1+1;
     
330.                                                                                 /***Then, i must be greater than n*******/
     
331.                                                                         }
     
332.                                                                         break;
     
333.                                                                 /*
     
334.                                                                 case '[':
     
335.                                                                 case '.':
     
336.                                                                 case ',':*/
     
337.                                                                 default:
     
338.                                                                         i=n;//quit
     
339.                                                                         break;
     
340.                                                         }/*swtich(code[i])*/
     
341.                                                 }/*for(i=left_offset,x1=x2=x3=x4=0;i<n;i++)*/
     
342.                                         } else {
     
343.                                         }
     
344.                                 }
     
345.                                 left_flag=0;
     
346.                                 break;
     
347.                         default:
     
348.                                 break;
     
349.                 }/*switch(code[m])*/
     
350.         }/*for(m=0,n=0,c=0,j=0,left_flag=0;m<len;m++)*/
     
351.         len=n;
     
352.         setbuf(stdout,NULL);
     
353. #if DEBUG>2
     
354.         for(i=0;i<len;i++)
     
355.                 putchar(code[i]);
     
356.         return 0;
     
357. #endif
     
358.         i=0;
     
359.         while(i<len) {
     
360.                 switch(code[i]) {
     
361.                         case '0':
     
362.                                 *p=0;
     
363.                                 break;
     
364.                         case 'a':
     
365.                                 i++;
     
366.                                 *p+=(signed char)code[i];
     
367.                                 break;
     
368.                         case 'p':
     
369.                                 i++;
     
370.                                 p+=(signed char)code[i];
     
371.                                 break;
     
372.                         case '+':
     
373.                                 (*p)++;
     
374.                                 break;
     
375.                         case '-':
     
376.                                 (*p)--;
     
377.                                 break;
     
378.                         case '>':
     
379.                                 p++;
     
380.                                 break;
     
381.                         case '<':
     
382.                                 p--;
     
383.                                 break;
     
384.                         case '.':
     
385.                                 putchar((int)(*p));
     
386.                                 //printf("put:%hd\n",*p);
     
387.                                 break;
     
388.                         case ',':
     
389.                                 *p=getchar();
     
390.                                 break;
     
391.                         case '[':
     
392.                                 if(*p) {
     
393.                                         stack[stack_len++]=i;
     
394.                                 } else {
     
395.                                         #ifdef USE_MATCH_TABLE
     
396.                                         if(x1=search_match(i)) {
     
397.                                                 i=x1;
     
398.                                                 break;
     
399.                                         }
     
400.                                         #endif
     
401.                                         for(k=i,j=0;k<len;k++) {
     
402.                                                 //if(code[k]=='a'||code[k]=='p'||code[k]&0x80) {
     
403.                                                 /**replaced by*****/
     
404.                                                 if((unsigned char)code[k]>=(unsigned char)'a') {
     
405.                                                         k++;
     
406.                                                         continue;
     
407.                                                 }
     
408.                                                 code[k]=='['&&j++;
     
409.                                                 code[k]==']'&&j--;
     
410.                                                 if(j==0)break;
     
411.                                         }
     
412.                                         if(j==0) {
     
413.                                                 #ifdef USE_MATCH_TABLE
     
414.                                                 add_match(i,k);
     
415.                                                 #endif
     
416.                                                 i=k;
     
417.                                         }
     
418.                                         else {
     
419.                                                 fprintf(stderr,"%s:%d\n",__FILE__,__LINE__);
     
420.                                                 return 3;
     
421.                                         }
     
422.                                 }
     
423.                                 break;
     
424.                         case ']':
     
425.                                 if(*p) {
     
426.                                         i=stack[stack_len - 1];
     
427.                                         #if DEBUG>0
     
428.                                         if(code[i] != '[') {
     
429.                                                 fprintf(stderr,"%s:%d\n",__FILE__,__LINE__);
     
430.                                                 return 0;
     
431.                                         }
     
432.                                         #endif
     
433.                                 } else {
     
434.                                         stack_len--;
     
435.                                 }
     
436.                                 break;
     
437.                         default:
     
438.                                 #if DEBUG>1
     
439.                                 if(code[i]&0x80)break;
     
440.                                 #endif
     
441.                                 p[(signed char)(code[i]&(code[i]&0x40?0xff:0x7f))]+=*p*((signed char)code[i+1]);
     
442.                                 i++;
     
443.                                 break;
     
444.                 }
     
445.                 i++;
     
446.                 //x++;
     
447.                 //printf("%d : i=%d\n",x,i);
     
448.         }
     
449.         return 0;
     
450. }
     

复制代码

[ 本帖最后由 cjaizss 于 2008-6-10 13:13 编辑 ]

aaxron

强强.
楼主好样的

run_xiao2000

[   如果指针指向的这个字节，则进入循环节
]   回到匹配的 ...

问个弱弱的问题，[,]操作没搞懂什么意思？呵呵

cjaizss

[ /*在这里判断指针当前所指字节是否为0，如果不为0，则进入循环节，否则跳到A*/
..............循环节
]
.............../*A*/

run_xiao2000

++++++++++[>++++++++++[>+<-]<-]>>-.+++++++.---------.++++++++.

果然够brainfuck,看了十分钟，拿笔在草稿纸上画了画才搞懂，这个嵌套的循环！

run_xiao2000

for(k=i,j=0;k<len;k++) {
                                                code[k]=='['&&j++;
                                                code[k]==']'&&j--;
                                                if(j==0)break;
                                        }

这段看了半天也看不懂，只知道是找"["匹配的"]"

drunkedfish

不是一般的强