API tools faq
paste
Advertisement
presto8

C solution for Synacor OSCON challenge

presto8
Jul 20th, 2012
439
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 11.76 KB | None | 0 0
raw download clone embed print report
  1. /*
  2. VM implementation for http://challenge.synacor.com
  3. By Preston Hunt | @presto8 | www.prestonhunt.com | me@prestonhunt.com
  4. Released 2012-07-20 into the public domain
  5. Thanks to @topaz2078 and @synacor for a great challenge at #oscon 2012.
  6.  
  7. Compiling
  8. =========
  9.  
  10. Recommended way to compile:
  11. gcc -g -Wall -Werror -o main main.c
  12.  
  13. Debugging
  14. =========
  15. There is not a lot of error checking in this program. Debugging with gdb is
  16. recommended in the event of a segmentation fault.
  17. gdb ./main
  18.  
  19. Running
  20. =======
  21. Emulator output is sent to stderr. It is low-level debugging and verbose. It is
  22. recommended to redirect it to a file or to /dev/null.
  23.  
  24. Recommended invocation:
  25. ./main 2>vmlog
  26.  
  27. This will allow interactive use on stdin and stdout, but you can still view
  28. the VM log by "tailf vmlog" in another window.
  29.  
  30. Default operation is to load the challenge.bin and boot the VM from scratch.
  31. Use special command "!s" at the VM prompt to save the VM. It can then be
  32. restored as shown below.
  33.  
  34. */
  35.  
  36. #include <stdio.h>
  37. #include <stdlib.h>
  38. #include <string.h>
  39.  
  40. struct {
  41.     short prog[50000];
  42.     short stack[500];
  43.     short reg[8];
  44.     short* pc;
  45.     short* sp;
  46.     long prog_size;
  47. } G;
  48.  
  49. short teleporter;
  50.  
  51. void halt(void)
  52. {
  53.     fprintf(stderr, "halt\n");
  54.     fflush(stdout);
  55.     fflush(stderr);
  56.     exit(0);
  57. }
  58.  
  59. void _halt(short a, short b, short c)
  60. {
  61.     halt();
  62. }
  63.  
  64. void reset_vm(void)
  65. {
  66.     memset(&G, 0, sizeof(G));
  67.     G.pc = G.prog;
  68.     G.sp = G.stack;
  69. }
  70.  
  71. void save_vm(const char* fname)
  72. {
  73.     FILE* fp = fopen(fname, "wb");
  74.     fwrite(&G, sizeof(G), 1, fp);
  75.     fclose(fp);
  76.     fprintf(stderr, "dumped vm to %s\n", fname);
  77. }
  78.  
  79. void restore_vm(const char* fname)
  80. {
  81.     FILE* fp = fopen(fname, "rb");
  82.     fread(&G, sizeof(G), 1, fp);
  83.     fclose(fp);
  84.     fprintf(stderr, "restored vm from %s\n", fname);
  85. }
  86.  
  87. void read_file(const char* fname)
  88. {
  89.     reset_vm();
  90.  
  91.     FILE* fp = fopen(fname, "rb");
  92.     if (!fp) {
  93.         fprintf(stderr, "couldn't open %s\n", fname);
  94.         halt();
  95.     }
  96.     G.prog_size = fread(G.prog, sizeof(G.prog[0]), sizeof(G.prog)/sizeof(G.prog[0]), fp);
  97.     fclose(fp);
  98. }
  99.  
  100. int to_reg(short a)
  101. {
  102.     if (a >= 0) {
  103.         fprintf(stderr, "CRITICAL %d should be <0\n", a);
  104.         halt();
  105.     }
  106.  
  107.     a += 32768;
  108.     return a;
  109. }
  110.  
  111. int get_pc(void)
  112. {
  113.     return *G.pc++;
  114. }
  115.  
  116. short fix_range(short a)
  117. {
  118.     return a >= 0 ? a : a + 32768;
  119. }
  120.  
  121. int get_pc_addr(void)
  122. {
  123.     short pc_addr = G.pc - G.prog;
  124.     return pc_addr;
  125. }
  126.  
  127. int get_reg(short a)
  128. {
  129.     return G.reg[to_reg(a)];
  130. }
  131.  
  132. int to_arg(short a)
  133. {
  134.     return a >= 0 ? a : get_reg(a);
  135. }
  136.  
  137. void out(short a, short ignore1, short ignore2)
  138. {
  139.     static char buf[1000];
  140.     static int bufi;
  141.  
  142.     a = to_arg(a);
  143.     fputc(a, stdout);
  144.     buf[bufi++ % 1000] = a;
  145.     /*buf[bufi++ % 1000] = 0;*/
  146.     fprintf(stderr, "out: %c", a);
  147.     /*fprintf(stderr, "out %d: %s", a, buf);*/
  148. }
  149.  
  150. void set(short a, short b)
  151. {
  152.     a = to_reg(a);
  153.     b = to_arg(b);
  154.     fprintf(stderr, "set #%d -> r%d", b, a);
  155.     G.reg[a] = b;
  156. }
  157.  
  158. void _set(short a, short b, short ignore)
  159. {
  160.     set(a, b);
  161. }
  162.  
  163. void in(short a, short ignore1, short ignore2)
  164. {
  165.     a = to_reg(a);
  166.     G.reg[7] = teleporter; // for teleporter
  167.     fprintf(stderr, "in %d> ", a);
  168.     int c = getchar();
  169.  
  170.     if (c == '!') {
  171.         int c = getchar();
  172.         if (c == 'q') halt();
  173.         if (c == 's') {
  174.             save_vm("vm.dump");
  175.             return;
  176.         }
  177.         return;
  178.     }
  179.  
  180.     fprintf(stderr, "[read %d]\n", c);
  181.     G.reg[a] = c;
  182. }
  183.  
  184. void jump(short addr)
  185. {
  186.     fprintf(stderr, "jump to %d", addr);
  187.     G.pc = &G.prog[addr];
  188. }
  189.  
  190. void _jump(short a, short b, short c)
  191. {
  192.     jump(a);
  193. }
  194.  
  195. void jt(short a, short b, short c)
  196. {
  197.     a = to_arg(a);
  198.     b = to_arg(b);
  199.     fprintf(stderr, "jt %d %d -> ", a, b);
  200.  
  201.     if (a > 0) {
  202.         jump(b);
  203.     } else {
  204.         fprintf(stderr, "(no jump)");
  205.     }
  206. }
  207.  
  208. void jf(short a, short b, short c)
  209. {
  210.     a = to_arg(a);
  211.     b = to_arg(b);
  212.     fprintf(stderr, "jf %d %d -> ", a, b);
  213.  
  214.     if (!a) {
  215.         jump(b);
  216.     } else {
  217.         fprintf(stderr, "(no jump)");
  218.     }
  219. }
  220.  
  221. void add(short a, short b, short c)
  222. {
  223.     b = to_arg(b);
  224.     c = to_arg(c);
  225.     fprintf(stderr, "add %d + %d -> ", b, c);
  226.     short ans = b + c;
  227.     set(a, fix_range(ans));
  228. }
  229.  
  230. void mult(short a, short b, short c)
  231. {
  232.     b = to_arg(b);
  233.     c = to_arg(c);
  234.     fprintf(stderr, "mult %d * %d -> ", b, c);
  235.     short ans = b * c;
  236.     set(a, fix_range(ans));
  237. }
  238.  
  239. void mod(short a, short b, short c)
  240. {
  241.     b = to_arg(b);
  242.     c = to_arg(c);
  243.     fprintf(stderr, "mod %d mod %d -> ", b, c);
  244.     short ans = b % c;
  245.     set(a, ans);
  246. }
  247.  
  248. void eq(short a, short b, short c)
  249. {
  250.     b = to_arg(b);
  251.     c = to_arg(c);
  252.     fprintf(stderr, "eq %d == %d -> ", b, c);
  253.     set(a, b == c);
  254. }
  255.  
  256. void and(short a, short b, short c)
  257. {
  258.     b = to_arg(b);
  259.     c = to_arg(c);
  260.     fprintf(stderr, "and %d & %d -> ", b, c);
  261.     set(a, b & c);
  262. }
  263.  
  264. void not(short a, short b, short c)
  265. {
  266.     b = to_arg(b);
  267.     fprintf(stderr, "not !%d -> ", b);
  268.     short ans = ~b;
  269.     set(a, fix_range(ans));
  270. }
  271.  
  272. void rmem(short a, short b, short ignore)
  273. {
  274.     b = to_arg(b);
  275.     short b_ = G.prog[b];
  276.     fprintf(stderr, "rmem (A%d)#%d -> ", b, b_);
  277.     set(a, b_);
  278. }
  279.  
  280. void wmem(short a, short b, short ignore)
  281. {
  282.     a = to_arg(a);
  283.     b = to_arg(b);
  284.     fprintf(stderr, "wmem #%d -> (A%d)", b, a);
  285.     G.prog[a] = b;
  286. }
  287.  
  288. void push(short a)
  289. {
  290.     a = to_arg(a);
  291.     fprintf(stderr, "push %d", a);
  292.     *G.sp++ = a;
  293. }
  294.  
  295. void _push(short a, short b, short c)
  296. {
  297.     push(a);
  298. }
  299.  
  300. void call(short a, short ignore1, short ignore2)
  301. {
  302.     a = to_arg(a);
  303.     fprintf(stderr, "call %d -> ", a);
  304.     push(get_pc_addr());
  305.     fprintf(stderr, " -> ");
  306.     jump(a);
  307. }
  308.  
  309. void ret(short ignore1, short ignore2, short ignore3)
  310. {
  311.     short a = *--G.sp;
  312.     fprintf(stderr, "ret %d -> ", a);
  313.     /*exit(1);*/
  314.     jump(a);
  315. }
  316.  
  317. void or(short a, short b, short c)
  318. {
  319.     b = to_arg(b);
  320.     c = to_arg(c);
  321.     fprintf(stderr, "or %d | %d -> ", b, c);
  322.     set(a, b | c);
  323. }
  324.  
  325. void gt(short a, short b, short c)
  326. {
  327.     b = to_arg(b);
  328.     c = to_arg(c);
  329.     fprintf(stderr, "gt %d > %d -> ", b, c);
  330.     set(a, b > c);
  331. }
  332.  
  333. void pop(short a, short b, short c)
  334. {
  335.     a = to_reg(a);
  336.     G.reg[a] = *--G.sp;
  337.     fprintf(stderr, "pop r%d=%d", a, G.reg[a]);
  338. }
  339.  
  340. void noop(short a, short b, short c)
  341. {
  342. }
  343.  
  344. struct ophandle {
  345.     short opcode;
  346.     char* label;
  347.     int args;
  348.     void (*fn_execute)(short a, short b, short c);
  349.     //void (*fn_disassemble)();
  350. } opcode_map[] = {
  351.     { 0   , "HALT" , 0, _halt } ,
  352.     { 1   , "SET"  , 2, _set }  ,
  353.     { 2   , "PUSH" , 1, _push } ,
  354.     { 3   , "POP"  , 1, pop }  ,
  355.     { 4   , "EQ"   , 3, eq }   ,
  356.     { 5   , "GT"   , 3, gt }   ,
  357.     { 6   , "JUMP" , 1, _jump } ,
  358.     { 7   , "JT"   , 2, jt }   ,
  359.     { 8   , "JF"   , 2, jf }   ,
  360.     { 9   , "ADD"  , 3, add }  ,
  361.     { 10  , "MULT" , 3, mult } ,
  362.     { 11  , "MOD"  , 3, mod }  ,
  363.     { 12  , "AND"  , 3, and }  ,
  364.     { 13  , "OR"   , 3, or }   ,
  365.     { 14  , "NOT"  , 2, not }  ,
  366.     { 15  , "RMEM" , 2, rmem } ,
  367.     { 16  , "WMEM" , 2, wmem } ,
  368.     { 17  , "CALL" , 1, call } ,
  369.     { 18  , "RET"  , 0, ret }  ,
  370.     { 19  , "OUT"  , 1, out }  ,
  371.     { 20  , "IN"   , 1, in }   ,
  372.     { 21  , "NOOP" , 0, noop } ,
  373.     { 100 , NULL   , 0, NULL }
  374. };
  375.  
  376. void print_arg(short a)
  377. {
  378.     if (a < 0) { // reg
  379.         int rnum = to_reg(a);
  380.         fprintf(stderr, "r%d(%d)", rnum, G.reg[rnum]);
  381.     } else {
  382.         fprintf(stderr, "%d", a);
  383.     }
  384. }
  385.  
  386. void handle_opcode(int opcode)
  387. {
  388.     short a = *G.pc;
  389.     short b = *(G.pc+1);
  390.     short c = *(G.pc+2);
  391.  
  392.     fprintf(stderr, "a="); print_arg(a);
  393.     fprintf(stderr, " b="); print_arg(b);
  394.     fprintf(stderr, " c="); print_arg(c);
  395.     fprintf(stderr, "\n\t");
  396.  
  397.     if (opcode < 0 || opcode > 21) {
  398.         fprintf(stderr, "Invalid opcode\n");
  399.         exit(1);
  400.     }
  401.  
  402.     struct ophandle* oph = &opcode_map[opcode];
  403.     G.pc += oph->args;
  404.     oph->fn_execute(a, b, c);
  405.  
  406.     fprintf(stderr, "\n");
  407. }
  408.  
  409. void hacks(void);
  410.  
  411. int main(int argc, const char *argv[])
  412. {
  413.     if (1) {
  414.         read_file("challenge.bin");
  415.         fprintf(stderr, "read %ld words (%ld bytes per word)\n", G.prog_size, sizeof(G.prog[0]));
  416.     } else {
  417.         /*restore_vm("after_boot.vm");*/
  418.         restore_vm("ruins.vm");
  419.     }
  420.  
  421.     if (argc >= 2) {
  422.         teleporter = atoi(argv[1]);
  423.         fprintf(stderr, "using teleporter value: %d\n", teleporter);
  424.         fprintf(stdout, "using teleporter value: %d\n", teleporter);
  425.     }
  426.  
  427.     while (1) {
  428.         int pc_addr = get_pc_addr();
  429.         hacks();
  430.         int op = get_pc();
  431.         fprintf(stderr, "PC=%d ", pc_addr);
  432.         handle_opcode(op);
  433.     }
  434.  
  435.     fprintf(stderr, "aborted\n");
  436.  
  437.     return 0;
  438. }
  439.  
  440.  
  441. /*
  442.  * NOTE: SPOILERS below. Do not read if you are still working on the challenge.
  443.  *
  444.  * These are my notes from the challenge. They are incomplete, rough, and
  445.  * contain spoilers.
  446.  */
  447.  
  448. /* Don't read this function "hacks" if you are still working on the teleporter */
  449. void hacks(void)
  450. {
  451.     /*if (pc_addr == 5473) break;*/ // right before testing transporter
  452.     /*G.prog[5473] = 7; // change jf -> jt*/
  453.     /*G.prog[5494] = 18; // change to ret to avoid transporter checksum*/
  454.     /*G.prog[6049] = 18; // change to ret to avoid transporter checksum*/
  455.     /*if (pc_addr == 1522) break;*/
  456.     /*if (pc_addr == 5494) break; // start of transporter checksum*/
  457. }
  458.  
  459. #if 0
  460.  
  461. Walk-through up to teleporter
  462. =============================
  463. These are the commands starting after a fresh boot all the way to the ruins:
  464. take tablet
  465. use tablet
  466. doorway
  467. north
  468. north
  469. north
  470. bridge
  471. continue
  472. down
  473. east
  474. take empty lantern
  475. west
  476. west
  477. passage
  478. ladder
  479. west
  480. south
  481. north
  482. take can
  483. use can
  484. use lantern
  485. west
  486. ladder
  487. darkness
  488. continue
  489. west
  490. west
  491. west
  492. west
  493. north
  494. take red coin
  495. north
  496. west
  497. take blue coin
  498. up
  499. take shiny coin
  500. down
  501. east
  502. east
  503. take concave coin
  504. down
  505. take corroded coin
  506. up
  507. west
  508. use blue coin
  509. use red coin
  510. use shiny coin
  511. use concave coin
  512. use corroded coin
  513. north
  514. take teleporter
  515. use teleporter
  516.  
  517. Maze hints
  518. ==========
  519. You are in a maze of twisty little passages, all dimly lit by more bioluminescent moss.  There is a ladder here leading up.
  520. EAST
  521.  
  522. You are in a twisty maze of little passages, all alike.
  523.  
  524. You are in a maze of little twisty passages, all alike.
  525. NORTH
  526.  
  527. You are in a little maze of twisty passages, all alike.
  528. NOT NORTH
  529. SOUTH
  530.  
  531. You are in a maze of twisty little passages, all alike.
  532. WEST
  533.  
  534. You are in a twisty alike of little passages, all maze.
  535. NORTH
  536.  
  537.  
  538. Coins challenge
  539. ===============
  540. 9   2   5   7   3   399
  541. blue    red shiny   concave corroded   
  542.  
  543.  
  544. Trying to reverse engineering the checksum algorithm
  545. ====================================================
  546. PC=1522 subroute to print letter
  547.  
  548. PC=1480 subroute to print a string?
  549. PC=1725 subroute state machine?
  550. PC=5494 subroute to check transporter code
  551. PC=6049 start of checksum
  552.   if r0 > 0 then jump to PC=6057
  553. PC=6057
  554.   if r1 > 0 then jump to PC=6070
  555. PC=6070
  556.   push r0 on stack
  557.   decrements r1 by 1
  558.   if r1 >0, jumps to PC=6070
  559.   if r1 <=0, subtracts 1 from r0 and puts key in r1, jumps to 6049 again
  560.  
  561.   PC=6070
  562.  
  563. r0=4
  564. r1=1
  565. r2=3
  566.  
  567. 6076: r1 = func_6049(4,1,1)
  568. 6078: r1 = r0
  569.  
  570. func_6049(r0, r1,r8) {
  571.     if (r0 == 0) { //6049
  572.         return 1 + r1; //6052
  573.     }
  574.  
  575.     if (r1 > 0) { //6057
  576.         r0 + func_6049(r0, r1-1, r8); //6070
  577.     } else { //6060
  578.         r1 = func_6049(r0-1, r8, r8);
  579.     }
  580. }
  581.  
  582. 6052:
  583. r0 = r1 + 1
  584. ret 6069: ret 6078:
  585. r1 = r0
  586. r0 = pop
  587. r0 = r0 + r1
  588.  
  589. func_6049(4, 1, r8=5)
  590.  
  591. f(4,1,1)
  592. 4 + f(4,0,1)
  593. f(3,1,1)
  594. 3 + f(3,0,1)
  595. f(2,1,1)
  596. 2 + f(2,0,1)
  597. f(1,1,1)
  598. 1 + f(1,0,1)
  599.   f(0,1,1)
  600.   ret 1+r1 = 1+1 = 2
  601.     r1 = r0
  602.  r0 = r0 - 1
  603. r1 = 1
  604. r1 = r1 - 1
  605.  
  606. #endif
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!