|
996
|
1 #include <stdio.h>
|
|
|
2 #include <stdlib.h>
|
|
|
3 #include <string.h>
|
|
|
4 #include <time.h>
|
|
|
5
|
|
|
6 #include "buffer.h"
|
|
|
7
|
|
|
8 #define MINTAPELEN 10
|
|
|
9 #define MAXTAPELEN 30
|
|
|
10 #define POLARITIES 4
|
|
|
11 #define RUNCOUNT (((MAXTAPELEN-MINTAPELEN) + 1) * POLARITIES)
|
|
|
12
|
|
|
13 /* parse a BFJoust program */
|
|
|
14 int parseFile(struct Buffer_char *progp)
|
|
|
15 {
|
|
|
16 int i, end, inner, iend, llen, ilen, rlen, times, rep, loc;
|
|
|
17 struct Buffer_char prog = *progp;
|
|
|
18 struct Buffer_char temp;
|
|
|
19
|
|
|
20 /* go through looking for things to expand */
|
|
|
21 for (i = 0; i < prog.bufused; i++) {
|
|
|
22 if (prog.buf[i] == '(') {
|
|
|
23 /* look for the match */
|
|
|
24 int depth = 1;
|
|
|
25 inner = iend = -1;
|
|
|
26 for (end = i + 1; end < prog.bufused && depth; end++) {
|
|
|
27 if (prog.buf[end] == '(') {
|
|
|
28 depth++;
|
|
|
29 } else if (prog.buf[end] == ')') {
|
|
|
30 depth--;
|
|
|
31 } else if (depth == 1 && prog.buf[end] == '{') {
|
|
|
32 inner = end;
|
|
|
33 } else if (depth == 1 && prog.buf[end] == '}') {
|
|
|
34 iend = end;
|
|
|
35 }
|
|
|
36 }
|
|
|
37
|
|
|
38 /* make sure it's sensible */
|
|
|
39 end--;
|
|
|
40 if (end + 2 >= prog.bufused) return 0;
|
|
|
41
|
|
|
42 /* expand it only if it includes [ or ], or is a '%' loop (which make interpretation basically impossible if unexpanded) */
|
|
|
43 llen = end - i;
|
|
|
44 if (strcspn(prog.buf + i, "[]") >= llen && prog.buf[end+1] == '*') {
|
|
|
45 continue;
|
|
|
46 }
|
|
|
47
|
|
|
48 /* check what comes next */
|
|
|
49 times = atoi(prog.buf + end + 2);
|
|
|
50 if (times < 0 || times > 10000) times = 10000;
|
|
|
51 if (prog.buf[end+1] == '*') {
|
|
|
52 llen = end - i - 1;
|
|
|
53
|
|
|
54 /* the simple case, just repeat n times */
|
|
|
55 INIT_BUFFER(temp);
|
|
|
56 temp.bufused = times * llen;
|
|
|
57 while (temp.bufsz < temp.bufused) {
|
|
|
58 EXPAND_BUFFER(temp);
|
|
|
59 }
|
|
|
60 for (rep = 0; rep < times; rep++) {
|
|
|
61 memcpy(temp.buf + rep * llen, prog.buf + i + 1, llen);
|
|
|
62 }
|
|
|
63
|
|
|
64 } else if (prog.buf[end+1] == '%') {
|
|
|
65 /* make sure there's a {} */
|
|
|
66 if (inner == -1 || iend == -1) return 0;
|
|
|
67
|
|
|
68 llen = inner - i - 1;
|
|
|
69 ilen = iend - inner - 1;
|
|
|
70 rlen = end - iend - 1;
|
|
|
71 if (llen < 0 || ilen < 0 || rlen < 0) return 0;
|
|
|
72
|
|
|
73 /* set up the buffer */
|
|
|
74 INIT_BUFFER(temp);
|
|
|
75 temp.bufused = times * llen + ilen + times * rlen;
|
|
|
76 while (temp.bufsz < temp.bufused) {
|
|
|
77 EXPAND_BUFFER(temp);
|
|
|
78 }
|
|
|
79
|
|
|
80 /* now the left */
|
|
|
81 loc = 0;
|
|
|
82 for (rep = 0; rep < times; rep++) {
|
|
|
83 memcpy(temp.buf + loc + rep * llen, prog.buf + i + 1, llen);
|
|
|
84 }
|
|
|
85 loc = times * llen;
|
|
|
86
|
|
|
87 /* the inner */
|
|
|
88 memcpy(temp.buf + loc, prog.buf + inner + 1, ilen);
|
|
|
89 loc += ilen;
|
|
|
90
|
|
|
91 /* and the right */
|
|
|
92 for (rep = 0; rep < times; rep++) {
|
|
|
93 memcpy(temp.buf + loc + rep * rlen, prog.buf + iend + 1, rlen);
|
|
|
94 }
|
|
|
95
|
|
|
96 } else {
|
|
|
97 return 0;
|
|
|
98
|
|
|
99 }
|
|
|
100
|
|
|
101 /* now copy it back into prog */
|
|
|
102 while (prog.bufsz < prog.bufused + temp.bufused + 1) {
|
|
|
103 EXPAND_BUFFER(prog);
|
|
|
104 }
|
|
|
105 memmove(prog.buf + i + temp.bufused, prog.buf + end + 1, prog.bufused - end - 1);
|
|
|
106 memcpy(prog.buf + i, temp.buf, temp.bufused);
|
|
|
107 prog.bufused = prog.bufused - end + i - 1 + temp.bufused;
|
|
|
108 WRITE_BUFFER(prog, "", 1); prog.bufused--;
|
|
|
109
|
|
|
110 FREE_BUFFER(temp);
|
|
|
111
|
|
|
112 i--;
|
|
|
113 }
|
|
|
114 }
|
|
|
115
|
|
|
116 memcpy(progp, &prog, sizeof(prog));
|
|
|
117 return 1;
|
|
|
118 }
|
|
|
119
|
|
|
120 /* returns true if this is a BF comment */
|
|
|
121 int isComment(char c)
|
|
|
122 {
|
|
|
123 return (c != '<' && c != '>' && c != '-' && c != '+' && c != '[' && c != ']' && c != '(' && c != ')' && c != '.');
|
|
|
124 }
|
|
|
125
|
|
|
126 /* run an execution step */
|
|
|
127 void runStep(struct Buffer_char prog, int *loops, int *pip,
|
|
|
128 char *tape, char *otape, int tapelen, int *tip,
|
|
|
129 int tapedir, int polarity,
|
|
|
130 struct Buffer_int *pstack, struct Buffer_int *pmax)
|
|
|
131 {
|
|
|
132 int pi = *pip;
|
|
|
133 int ti = *tip;
|
|
|
134 int reps = 0;
|
|
|
135
|
|
|
136 /* find a non-comment character */
|
|
|
137 rerun:
|
|
|
138 if (++reps > 16) return;
|
|
|
139 if (pi < 0) return;
|
|
|
140 for (; pi < prog.bufused && isComment(prog.buf[pi]); pi++);
|
|
|
141 *pip = pi;
|
|
|
142 if (pi >= prog.bufused) return;
|
|
|
143
|
|
|
144 /* run it */
|
|
|
145 switch (prog.buf[pi]) {
|
|
|
146 case '<':
|
|
|
147 ti -= tapedir;
|
|
|
148 break;
|
|
|
149
|
|
|
150 case '>':
|
|
|
151 ti += tapedir;
|
|
|
152 break;
|
|
|
153
|
|
|
154 case '-':
|
|
|
155 otape[ti] -= polarity;
|
|
|
156 break;
|
|
|
157
|
|
|
158 case '+':
|
|
|
159 otape[ti] += polarity;
|
|
|
160 break;
|
|
|
161
|
|
|
162 case '[':
|
|
|
163 if (tape[ti] == 0) {
|
|
|
164 /* first check the cache */
|
|
|
165 if (loops[pi] != -1) {
|
|
|
166 pi = loops[pi];
|
|
|
167 } else {
|
|
|
168 int depth = 1;
|
|
|
169 int opi = pi;
|
|
|
170 for (pi++; pi < prog.bufused && depth; pi++) {
|
|
|
171 switch (prog.buf[pi]) {
|
|
|
172 case '[':
|
|
|
173 depth++;
|
|
|
174 break;
|
|
|
175
|
|
|
176 case ']':
|
|
|
177 depth--;
|
|
|
178 break;
|
|
|
179 }
|
|
|
180 }
|
|
|
181 pi--;
|
|
|
182
|
|
|
183 loops[opi] = pi;
|
|
|
184 loops[pi] = opi;
|
|
|
185 }
|
|
|
186 }
|
|
|
187 break;
|
|
|
188
|
|
|
189 case ']':
|
|
|
190 if (tape[ti] != 0) {
|
|
|
191 /* check the cache */
|
|
|
192 if (loops[pi] != -1) {
|
|
|
193 pi = loops[pi];
|
|
|
194 } else {
|
|
|
195 int depth = 1;
|
|
|
196 for (pi--; pi >= 0 && depth; pi--) {
|
|
|
197 switch (prog.buf[pi]) {
|
|
|
198 case ']':
|
|
|
199 depth++;
|
|
|
200 break;
|
|
|
201
|
|
|
202 case '[':
|
|
|
203 depth--;
|
|
|
204 break;
|
|
|
205 }
|
|
|
206 }
|
|
|
207 pi++;
|
|
|
208 }
|
|
|
209 }
|
|
|
210 break;
|
|
|
211
|
|
|
212 case '(':
|
|
|
213 /* make sure this is cached */
|
|
|
214 if (loops[pi] == -1) {
|
|
|
215 int depth = 1;
|
|
|
216 int ipi;
|
|
|
217 for (ipi = pi + 1; ipi < prog.bufused && depth; ipi++) {
|
|
|
218 switch (prog.buf[ipi]) {
|
|
|
219 case '(':
|
|
|
220 depth++;
|
|
|
221 break;
|
|
|
222
|
|
|
223 case ')':
|
|
|
224 depth--;
|
|
|
225 break;
|
|
|
226 }
|
|
|
227 }
|
|
|
228 ipi--;
|
|
|
229
|
|
|
230 loops[pi] = ipi;
|
|
|
231 loops[ipi] = pi;
|
|
|
232 }
|
|
|
233
|
|
|
234 /* push the counter */
|
|
|
235 {
|
|
|
236 int count = atoi(prog.buf + loops[pi] + 2);
|
|
|
237 if (BUFFER_SPACE(*pstack) < 1) {
|
|
|
238 EXPAND_BUFFER(*pstack);
|
|
|
239 EXPAND_BUFFER(*pmax);
|
|
|
240 }
|
|
|
241 pstack->buf[pstack->bufused++] = 0;
|
|
|
242 pmax->buf[pmax->bufused++] = count;
|
|
|
243 }
|
|
|
244
|
|
|
245 /* then continue immediately */
|
|
|
246 pi++;
|
|
|
247 goto rerun;
|
|
|
248
|
|
|
249 case ')':
|
|
|
250 /* increment the counter */
|
|
|
251 if (pstack->bufused > 0) {
|
|
|
252 pstack->buf[pstack->bufused-1]++;
|
|
|
253 }
|
|
|
254
|
|
|
255 /* either reloop or don't */
|
|
|
256 if (pstack->buf[pstack->bufused-1] < pmax->buf[pstack->bufused-1]) {
|
|
|
257 pi = loops[pi];
|
|
|
258 } else {
|
|
|
259 pstack->bufused = pmax->bufused = pstack->bufused - 1;
|
|
|
260 }
|
|
|
261 pi++;
|
|
|
262 goto rerun;
|
|
|
263
|
|
|
264 case '.':
|
|
|
265 /* nop */
|
|
|
266 break;
|
|
|
267 }
|
|
|
268 pi++;
|
|
|
269
|
|
|
270 *pip = pi;
|
|
|
271 *tip = ti;
|
|
|
272 }
|
|
|
273
|
|
|
274 /* simple hashing function, same as is used in sdbm */
|
|
|
275 size_t simpleHash(size_t slen, unsigned char *str)
|
|
|
276 {
|
|
|
277 size_t hash = 0;
|
|
|
278
|
|
|
279 for (; slen > 0; slen--)
|
|
|
280 hash = (*str++) + (hash << 6) + (hash << 16) - hash;
|
|
|
281
|
|
|
282 return hash;
|
|
|
283 }
|
|
|
284
|
|
|
285 int main(int argc, char **argv)
|
|
|
286 {
|
|
|
287 struct Buffer_char lprog, rprog;
|
|
|
288 struct Buffer_int lloops, rloops;
|
|
|
289 struct Buffer_int lpstack, rpstack, lpmax, rpmax;
|
|
|
290 FILE *lfh, *rfh;
|
|
|
291 int lparse, rparse;
|
|
|
292 char *tape, *otape;
|
|
|
293 int lt, rt, tapelen;
|
|
|
294 int polarity, lpol, rpol;
|
|
|
295 int lpi, rpi;
|
|
|
296 int lwins, rwins;
|
|
|
297 int lloss, rloss;
|
|
|
298 int step;
|
|
|
299
|
|
|
300 if (argc < 3) {
|
|
|
301 fprintf(stderr, "Use: egojoust <left program> <right program>\n");
|
|
|
302 return 0;
|
|
|
303 }
|
|
|
304
|
|
|
305 /* read in the files */
|
|
|
306 INIT_BUFFER(lprog);
|
|
|
307 SF(lfh, fopen, NULL, (argv[1], "r"));
|
|
|
308 READ_FILE_BUFFER(lprog, lfh);
|
|
|
309 WRITE_BUFFER(lprog, "", 1); lprog.bufused--;
|
|
|
310
|
|
|
311 INIT_BUFFER(rprog);
|
|
|
312 SF(rfh, fopen, NULL, (argv[2], "r"));
|
|
|
313 READ_FILE_BUFFER(rprog, rfh);
|
|
|
314 WRITE_BUFFER(rprog, "", 1); rprog.bufused--;
|
|
|
315
|
|
|
316 /* parse them */
|
|
|
317 lparse = parseFile(&lprog);
|
|
|
318 rparse = parseFile(&rprog);
|
|
|
319 if (!lparse) {
|
|
|
320 if (!rparse) {
|
|
|
321 printf("Both warriors failed to parse. Tie!\n");
|
|
|
322 return 0;
|
|
|
323 } else {
|
|
|
324 printf("Left warrior failed to parse, right warrior wins!\n");
|
|
|
325 return RUNCOUNT;
|
|
|
326 }
|
|
|
327 } else if (!rparse) {
|
|
|
328 printf("Right warrior failed to parse, left warrior wins!\n");
|
|
|
329 return -RUNCOUNT;
|
|
|
330 }
|
|
|
331
|
|
|
332 /* allocate the tape */
|
|
|
333 SF(tape, malloc, NULL, (30));
|
|
|
334 SF(otape, malloc, NULL, (30));
|
|
|
335
|
|
|
336 /* prepare the caches */
|
|
|
337 INIT_BUFFER(lloops);
|
|
|
338 INIT_BUFFER(rloops);
|
|
|
339 while (lloops.bufsz < lprog.bufused) EXPAND_BUFFER(lloops);
|
|
|
340 memset(lloops.buf, -1, lprog.bufused * sizeof(int));
|
|
|
341 while (rloops.bufsz < rprog.bufused) EXPAND_BUFFER(rloops);
|
|
|
342 memset(rloops.buf, -1, rprog.bufused * sizeof(int));
|
|
|
343
|
|
|
344 INIT_BUFFER(lpstack);
|
|
|
345 INIT_BUFFER(rpstack);
|
|
|
346 INIT_BUFFER(lpmax);
|
|
|
347 INIT_BUFFER(rpmax);
|
|
|
348
|
|
|
349 /* run for each polarity, for each length from 10 to 30 */
|
|
|
350 lwins = 0;
|
|
|
351 rwins = 0;
|
|
|
352
|
|
|
353 printf("%s vs %s:\n", argv[1], argv[2]);
|
|
|
354
|
|
|
355 for (polarity = 0; polarity < POLARITIES; polarity++) {
|
|
|
356 /* set up the polarity */
|
|
|
357 if (polarity & 0x2) {
|
|
|
358 lpol = -1;
|
|
|
359 } else {
|
|
|
360 lpol = 1;
|
|
|
361 }
|
|
|
362
|
|
|
363 if (polarity & 0x1) {
|
|
|
364 rpol = -1;
|
|
|
365 } else {
|
|
|
366 rpol = 1;
|
|
|
367 }
|
|
|
368
|
|
|
369 for (tapelen = MINTAPELEN; tapelen <= MAXTAPELEN; tapelen++) {
|
|
|
370 /* make the tape */
|
|
|
371 memset(tape, 0, tapelen);
|
|
|
372 tape[0] = tape[tapelen-1] = (char) (unsigned char) 128;
|
|
|
373 lt = 0;
|
|
|
374 rt = tapelen - 1;
|
|
|
375 memcpy(otape, tape, tapelen);
|
|
|
376
|
|
|
377 /* then run */
|
|
|
378 lpi = rpi = lloss = rloss = 0;
|
|
|
379 for (step = 0; step < 100000 && lloss < 2 && rloss < 2; step++) {
|
|
|
380 /* run the left */
|
|
|
381 runStep(lprog, lloops.buf, &lpi, tape, otape, tapelen, <, 1, lpol, &lpstack, &lpmax);
|
|
|
382
|
|
|
383 /* and the right */
|
|
|
384 runStep(rprog, rloops.buf, &rpi, tape, otape, tapelen, &rt, -1, rpol, &rpstack, &rpmax);
|
|
|
385
|
|
|
386 /* commit the tape */
|
|
|
387 memcpy(tape, otape, tapelen);
|
|
|
388
|
|
|
389 /* check for loss conditions */
|
|
|
390 if (tape[0] == 0) {
|
|
|
391 lloss++;
|
|
|
392 } else {
|
|
|
393 lloss = 0;
|
|
|
394 }
|
|
|
395 if (lt < 0 || lt >= tapelen) {
|
|
|
396 fprintf(stderr, "Left ran off the tape (%d/%d)!\n", lt, tapelen);
|
|
|
397 lloss = 3;
|
|
|
398 }
|
|
|
399 if (tape[tapelen-1] == 0) {
|
|
|
400 rloss++;
|
|
|
401 } else {
|
|
|
402 rloss = 0;
|
|
|
403 }
|
|
|
404 if (rt < 0 || rt >= tapelen) {
|
|
|
405 fprintf(stderr, "Right ran off the tape (%d/%d)!\n", rt, tapelen);
|
|
|
406 rloss = 3;
|
|
|
407 }
|
|
|
408 }
|
|
|
409
|
|
|
410 /* now find the victor */
|
|
|
411 if (lloss > rloss) {
|
|
|
412 /*printf("%d/%d: %s wins!\n", polarity, tapelen, argv[2]);*/
|
|
|
413 printf(">");
|
|
|
414 rwins++;
|
|
|
415 } else if (rloss > lloss) {
|
|
|
416 /*printf("%d/%d: %s wins!\n", polarity, tapelen, argv[1]);*/
|
|
|
417 printf("<");
|
|
|
418 lwins++;
|
|
|
419 } else {
|
|
|
420 /*printf("%d/%d: Tie!\n", polarity, tapelen);*/
|
|
|
421 printf("X");
|
|
|
422 }
|
|
|
423 }
|
|
|
424
|
|
|
425 printf(" ");
|
|
|
426 }
|
|
|
427
|
|
|
428 printf("\n");
|
|
|
429
|
|
|
430 if (lwins > rwins) {
|
|
|
431 printf("%s wins\n\n", argv[1]);
|
|
|
432 } else if (rwins > lwins) {
|
|
|
433 printf("%s wins\n\n", argv[2]);
|
|
|
434 } else {
|
|
|
435 printf("Tie\n\n");
|
|
|
436 }
|
|
|
437 return rwins - lwins;
|
|
|
438 }
|
