Mercurial > repo

comparison interps/adjust/adjust.c @ 996:859f9b4339e6

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
<Gregor> tar xf egobot.tar.xz
author HackBot
date Sun, 09 Dec 2012 19:30:08 +0000
parents
children
comparison
equal deleted inserted replaced
995:6883f5911eb7 996:859f9b4339e6
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
4 #include <assert.h>
5
6 typedef unsigned char cell;
7
8 cell *read_arbitrary_length_string(FILE *fp);
9 void run(cell **code, int lines, int maxline);
10
11 int main(int argc, char *argv[])
12 {
13 cell **code;
14 FILE *src;
15 int codespace, codelines = 0, maxline = 0;
16
17 if (argc != 2)
18 {
19 fprintf(stderr, "Incorrect invocation\n");
20 return 1;
21 }
22
23 src = fopen(argv[1], "r");
24 if (src == NULL)
25 {
26 fprintf(stderr, "Unreadable file\n");
27 return 2;
28 }
29
30 codespace = 10;
31 code = malloc(codespace * sizeof(cell*));
32 if (!code)
33 return 3;
34
35 for (;;)
36 {
37 int len;
38 if (codelines == codespace)
39 {
40 codespace *= 2;
41 code = realloc(code, codespace * sizeof(cell*));
42 if (!code)
43 return 4;
44 }
45 code[codelines] = read_arbitrary_length_string(src);
46 if (code[codelines] == NULL)
47 break;
48 len = strlen(code[codelines]);
49 if (len > maxline)
50 maxline = len;
51 codelines++;
52 }
53 fclose(src);
54
55 run(code, codelines, maxline);
56 free(code);
57 return 0;
58 }
59
60 cell *addmem(cell *mem, int cursize, int newsize)
61 {
62 mem = realloc(mem, newsize);
63 if (!mem)
64 {
65 fprintf(stderr, "Out of memory\n");
66 exit(-1);
67 }
68 memset(&mem[cursize], 0, newsize - cursize);
69 return mem;
70 }
71
72 /* For 2 <= n <= 126, next[n] = n / gpf[n]. */
73 cell next[127] =
74 {
75 0, 0, 1, 1, 2, 1, 2, 1,
76 4, 3, 2, 1, 4, 1, 2, 3,
77 8, 1, 6, 1, 4, 3, 2, 1,
78 8, 5, 2, 9, 4, 1, 6, 1,
79 16, 3, 2, 5, 12, 1, 2, 3,
80 8, 1, 6, 1, 4, 9, 2, 1,
81 16, 7, 10, 3, 4, 1, 18, 5,
82 8, 3, 2, 1, 12, 1, 2, 9,
83 32, 5, 6, 1, 4, 3, 10, 1,
84 24, 1, 2, 15, 4, 7, 6, 1,
85 16, 27, 2, 1, 12, 5, 2, 3,
86 8, 1, 18, 7, 4, 3, 2, 5,
87 32, 1, 14, 9, 20, 1, 6, 1,
88 8, 15, 2, 1, 36, 1, 10, 3,
89 16, 1, 6, 5, 4, 9, 2, 7,
90 24, 11, 2, 3, 4, 25, 18
91 };
92
93 /* For 2 <= n <= 126, gpf[n] is n's greatest prime factor. */
94 cell gpf[127] =
95 {
96 0, 0, 2, 3, 2, 5, 3, 7,
97 2, 3, 5, 11, 3, 13, 7, 5,
98 2, 17, 3, 19, 5, 7, 11, 23,
99 3, 5, 13, 3, 7, 29, 5, 31,
100 2, 11, 17, 7, 3, 37, 19, 13,
101 5, 41, 7, 43, 11, 5, 23, 47,
102 3, 7, 5, 17, 13, 53, 3, 11,
103 7, 19, 29, 59, 5, 61, 31, 7,
104 2, 13, 11, 67, 17, 23, 7, 71,
105 3, 73, 37, 5, 19, 11, 13, 79,
106 5, 3, 41, 83, 7, 17, 43, 29,
107 11, 89, 5, 13, 23, 31, 47, 19,
108 3, 97, 7, 11, 5, 101, 17, 103,
109 13, 7, 53, 107, 3, 109, 11, 37,
110 7, 113, 19, 23, 29, 13, 59, 17,
111 5, 11, 61, 41, 31, 5, 7
112 };
113
114 cell bitsset[256] =
115 {
116 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
117 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
118 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
119 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
120 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
121 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
122 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
123 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
124 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
125 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
126 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
127 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
128 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
129 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
130 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
131 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
132 };
133
134 #define LEFT 0
135 #define UP_LEFT 1
136 #define UP 2
137 #define UP_RIGHT 3
138 #define RIGHT 4
139 #define DOWN_RIGHT 5
140 #define DOWN 6
141 #define DOWN_LEFT 7
142
143 #define RIGHT135(d) ((d) = right135((d)))
144 #define RIGHT90(d) ((d) = right90((d)))
145 #define RIGHT45(d) ((d) = right45((d)))
146 #define LEFT45(d) ((d) = left45((d)))
147 #define LEFT90(d) ((d) = left90((d)))
148 static inline int right135(int dir) { return (dir+3)%8; }
149 static inline int right90(int dir) { return (dir+2)%8; }
150 static inline int right45(int dir) { return (dir+1)%8; }
151 static inline int left45(int dir) { return (dir-1)%8; }
152 static inline int left90(int dir) { return (dir-2)%8; }
153 static inline void movefwd(int *x, int *y, int dir, int steps)
154 {
155 if (dir == LEFT || dir == UP_LEFT || dir == DOWN_LEFT)
156 *x -= steps;
157 else if (dir == RIGHT || dir == UP_RIGHT || dir == DOWN_RIGHT)
158 *x += steps;
159 if (dir == UP || dir == UP_LEFT || dir == UP_RIGHT)
160 *y -= steps;
161 else if (dir == DOWN || dir == DOWN_LEFT || dir == DOWN_RIGHT)
162 *y += steps;
163 }
164 #ifdef UNSAFE
165 static inline void checkmove(int x, int y, int w, int h) {}
166 #else
167 static inline void checkmove(int x, int y, int w, int h)
168 {
169 if (x < 0 || y < 0 || x >= w || y >= h)
170 {
171 fprintf(stderr, "Out of bounds\n");
172 exit(-1);
173 }
174 }
175 #endif
176 static inline void push(cell val, cell **pstack, int *items, int *space)
177 {
178 if (*items == *space)
179 {
180 *pstack = addmem(*pstack, *space, 2**space);
181 *space *= 2;
182 }
183 (*pstack)[(*items)++] = val;
184 }
185 static inline int pop(cell *stack, int *items)
186 {
187 if (*items == 0)
188 return -1;
189 return stack[--(*items)];
190 }
191 static inline int peek(cell *stack, int items)
192 {
193 if (items == 0)
194 return -1;
195 return stack[items - 1];
196 }
197
198 void run(cell **code, int lines, int maxline)
199 {
200 cell acc, *stack1 = NULL, *stack2 = NULL;
201 int stack1size = 10, stack2size = 10;
202 int stack1pos = 0, stack2pos = 0;
203 int dir = UP_RIGHT, codex, codey;
204 int i, *lengths;
205
206 stack1 = addmem(stack1, 0, stack1size);
207 stack2 = addmem(stack2, 0, stack2size);
208 acc = 0;
209 codex = 0;
210 codey = lines - 1;
211
212 lengths = malloc(sizeof(int) * lines);
213 for (i = 0; i < lines; i++)
214 lengths[i] = strlen(code[i]);
215
216 for (;;)
217 {
218 cell c;
219 if (codex >= lengths[codey])
220 c = '!'; /* lines are padded with ! */
221 else
222 {
223 c = code[codey][codex];
224 #ifndef UNSAFE
225 if (c < 32 || c > 126)
226 {
227 fprintf(stderr, "Invalid character\n");
228 exit(-1);
229 }
230 #endif
231 }
232
233 /* run the commands */
234 for (; c > 1; c = next[(size_t) c]) switch(gpf[(size_t) c])
235 {
236 case 2:
237 {
238 cell tmp;
239 tmp = (acc & 7) << 5;
240 acc >>= 3;
241 acc |= tmp;
242 break;
243 }
244 case 3:
245 {
246 int s1, s2;
247 s1 = peek(stack1, stack1pos);
248 s2 = peek(stack2, stack2pos);
249 if (s2 < s1)
250 {
251 push(acc, &stack2,
252 &stack2pos, &stack2size);
253 LEFT45(dir);
254 movefwd(&codex, &codey, dir, 1);
255 break;
256 }
257 push(acc, &stack1, &stack1pos, &stack1size);
258 if (s2 == s1)
259 {
260 RIGHT45(dir);
261 movefwd(&codex, &codey, dir, 1);
262 break;
263 }
264 if (acc)
265 LEFT90(dir);
266 else
267 RIGHT135(dir);
268 movefwd(&codex, &codey, dir, 1);
269 break;
270 }
271 case 5:
272 {
273 if (acc & 1)
274 acc--;
275 else
276 acc++;
277 break;
278 }
279 case 7:
280 {
281 movefwd(&codex, &codey, dir,
282 bitsset[(size_t) acc]);
283 break;
284 }
285 case 11:
286 {
287 int s1, s2;
288 s1 = peek(stack1, stack1pos);
289 s2 = peek(stack2, stack2pos);
290 if (s1 > s2)
291 acc = pop(stack1, &stack1pos);
292 else if (s2 == -1)
293 acc = 0;
294 else
295 acc = pop(stack2, &stack2pos);
296 break;
297 }
298 case 13:
299 {
300 int s2;
301 s2 = pop(stack2, &stack2pos);
302 if (s2 != -1)
303 putchar(s2);
304 break;
305 }
306 case 17:
307 case 19:
308 {
309 int ch;
310 if (gpf[(size_t) c] == 17)
311 ch = getchar();
312 else
313 ch = pop(stack2, &stack2pos);
314 if (ch < 0 || ch > 255) /* empty stack/EOF */
315 {
316 int steps = 0;
317 if (acc & (1<<2))
318 RIGHT90(dir);
319 steps += (acc & (1<<3));
320 steps += (acc & (1<<4));
321 steps += (acc & (1<<7));
322 movefwd(&codex, &codey, dir, steps);
323 break;
324 }
325 push(ch, &stack1, &stack1pos, &stack1size);
326 break;
327 }
328 case 23:
329 {
330 acc <<= 5;
331 break;
332 }
333 case 29:
334 {
335 int s1, s2, steps = 2;
336 if (acc != 0)
337 break;
338 LEFT45(dir);
339 s1 = peek(stack1, stack1pos);
340 s2 = peek(stack2, stack2pos);
341 if (s2 < s1)
342 steps++;
343 movefwd(&codex, &codey, dir, steps);
344 RIGHT45(dir);
345 break;
346 }
347 case 31:
348 {
349 movefwd(&codex, &codey, dir, 1);
350 break;
351 }
352 case 37:
353 {
354 int s1, s2;
355 s1 = peek(stack1, stack1pos);
356 s2 = peek(stack2, stack2pos);
357 if (s1 == s2)
358 break;
359 if (s1 < s2)
360 push(s1, &stack2, &stack2pos,
361 &stack2size);
362 else
363 push(s2, &stack1, &stack1pos,
364 &stack1size);
365 break;
366 }
367 case 41:
368 {
369 int s1, s2;
370 s1 = peek(stack1, stack1pos);
371 s2 = peek(stack2, stack2pos);
372 if (s1 == s2)
373 break;
374 if (s1 > s2)
375 pop(stack1, &stack1pos);
376 else
377 pop(stack2, &stack2pos);
378 break;
379 }
380 case 43:
381 {
382 acc >>= 1;
383 if (!acc)
384 {
385 movefwd(&codex, &codey, dir, 1);
386 LEFT90(dir);
387 }
388 break;
389 }
390 case 47:
391 {
392 int s1, s2;
393 s1 = peek(stack1, stack1pos);
394 s2 = peek(stack2, stack2pos);
395 if (s1 == s2)
396 break;
397 if (s1 < s2)
398 acc = pop(stack1, &stack1pos);
399 else
400 acc = pop(stack2, &stack2pos);
401 break;
402 }
403 case 53:
404 {
405 int s1, s2;
406 s1 = peek(stack1, stack1pos);
407 s2 = peek(stack2, stack2pos);
408 if (s1 < s2)
409 {
410 cell tmp;
411 tmp = acc & 0xf0;
412 if (acc & 1)
413 tmp |= 8;
414 if (acc & 2)
415 tmp |= 4;
416 if (acc & 4)
417 tmp |= 2;
418 if (acc & 8)
419 tmp |= 1;
420 acc = tmp;
421 }
422 else
423 {
424 cell tmp;
425 tmp = acc & 0x0f;
426 if (acc & 16)
427 tmp |= 128;
428 if (acc & 32)
429 tmp |= 64;
430 if (acc & 64)
431 tmp |= 32;
432 if (acc & 128)
433 tmp |= 16;
434 acc = tmp;
435 }
436 break;
437 }
438 case 59:
439 {
440 int n;
441 n = bitsset[(size_t) acc] % 8;
442 while(n--)
443 RIGHT45(dir);
444 break;
445 }
446 case 61:
447 {
448 cell *tmps;
449 int tmp;
450 tmps = stack1;
451 stack1 = stack2;
452 stack2 = tmps;
453 tmp = stack1size;
454 stack1size = stack2size;
455 stack2size = tmp;
456 tmp = stack1pos;
457 stack1pos = stack2pos;
458 stack2pos = tmp;
459 break;
460 }
461 case 67:
462 goto quit;
463 default:
464 acc = gpf[(size_t) c];
465 }
466
467 movefwd(&codex, &codey, dir, 1);
468 checkmove(codex, codey, maxline, lines);
469 }
470
471 quit:
472 free(lengths);
473 free(stack1);
474 free(stack2);
475 }
476
477 cell *read_arbitrary_length_string(FILE *fp)
478 {
479 cell *p = NULL, *q;
480 int size = 50;
481
482 if ((p = malloc(size)) == NULL)
483 return NULL;
484 if (fgets(p, size, fp) == NULL)
485 return NULL;
486
487 while ((q = strchr(p, '\n')) == NULL)
488 {
489 size *= 2;
490 if ((p = realloc(p, size)) == NULL)
491 return NULL;
492 if (fgets(&p[size/2-1], size/2+1, fp) == NULL)
493 return NULL; /* invalid; file must end with newline */
494 }
495
496 *q = '\0';
497 return p;
498 }