Mercurial > repo
comparison interps/adjust/adjust.c @ 996:859f9b4339e6
<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 } |