Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
260 lines (237 sloc) 8.32 KB
// for more details see
// https://dhconnelly.com/advent-of-code-2019-commentary.html#intcode-reverse-engineering
// set the stack pointer to after the program data
[ 0] adjrel imm(424)
// call procedure C with ret=11 and arg0=X
// halt if X < 0
[ 2] read rel(1)
[ 4] mul imm(11) imm(1) rel(0)
[ 8] jmpnot imm(0) imm(282)
// call procedure B with ret=18 and arg0=X
// 221 <- abs(X)
[ 11] add imm(18) imm(0) rel(0)
[ 15] jmpnot imm(0) imm(259)
[ 18] add imm(0) rel(1) pos(221)
// call procedure C with ret=31 and arg0=Y
// halt if Y < 0
[ 22] read rel(1)
[ 24] mul imm(31) imm(1) rel(0)
[ 28] jmpnot imm(0) imm(282)
// call procedure B with ret=38 and arg0=Y
// Y = abs(Y)
[ 31] mul imm(1) imm(38) rel(0)
[ 35] jmpif imm(1) imm(259)
// call procedure D with ret=57 and arg0=1, arg1=1, arg2=abs(Y)
// because pos(23) = 1
// = Y
// 222 <- Y
[ 38] mul imm(1) pos(23) rel(2)
[ 42] add imm(0) rel(1) rel(3)
[ 46] add imm(0) imm(1) rel(1)
[ 50] add imm(0) imm(57) rel(0)
[ 54] jmpnot imm(0) imm(303)
[ 57] mul rel(1) imm(1) pos(222)
// call procedure A with ret=80 and arg0=259, arg1=X, arg2=X, arg3=X
// = 259(X, X, X) = abs(X)
[ 61] add pos(221) imm(0) rel(3)
[ 65] mul imm(1) pos(221) rel(2)
[ 69] mul imm(259) imm(1) rel(1)
[ 73] add imm(80) imm(0) rel(0)
[ 77] jmpif imm(1) imm(225)
// call procedure D with ret=91 and arg0=X, arg1=149, arg2=X
// = 149x^2
// -> 223
[ 80] mul imm(1) imm(149) rel(2)
[ 84] add imm(0) imm(91) rel(0)
[ 88] jmpif imm(1) imm(303)
[ 91] mul rel(1) imm(1) pos(223)
// call procedure A
// with ret=118, arg0=225, arg1=225, arg2=259, arg3=^
// call A(A, A, B, Y)
// = A(A, B, Y)
// = A(B, Y)
// = B(Y)
// = abs(Y)
[ 95] mul pos(222) imm(1) rel(4)
[ 99] mul imm(259) imm(1) rel(3)
[ 103] mul imm(225) imm(1) rel(2)
[ 107] mul imm(225) imm(1) rel(1)
[ 111] add imm(118) imm(0) rel(0)
[ 115] jmpif imm(1) imm(225)
// call D with ret=133 and Y, 127, Y
// = 127y^2
[ 118] mul imm(1) pos(222) rel(3)
[ 122] add imm(0) imm(127) rel(2)
[ 126] mul imm(133) imm(1) rel(0)
[ 130] jmpif imm(1) imm(303)
// x0 = -above = -127y^2
// += 149x^2
// 223 <- 149x^2 - 127y^2
[ 133] mul rel(1) imm(-1) rel(1)
[ 137] add pos(223) rel(1) rel(1)
[ 141] mul imm(1) imm(148) rel(0)
[ 145] jmpnot imm(0) imm(259)
[ 148] add rel(1) imm(0) pos(223)
// call A with ret=195 and arg0=303, arg1=14, arg2=Y, arg3=X
// = D(14, Y, X)
// rel(4) = X
// = 14yx
[ 152] add pos(221) imm(0) rel(4)
// rel(3) = Y
[ 156] mul pos(222) imm(1) rel(3)
// rel(2) = 14
[ 160] mul imm(14) imm(1) rel(2)
// *224 <- *303-2 = 301
[ 164] add pos(132) imm(-2) pos(224)
// *224 <- *224 * 2 = 602
[ 168] mul pos(224) imm(2) pos(224)
// *224 <- *224 + 3 = 605
[ 172] add pos(224) imm(3) pos(224)
// *132 <- *132 * -1 = -303
[ 176] mul pos(132) imm(-1) pos(132)
// *224 <- *224 + *132 = 605 - 303 = 302
[ 180] add pos(224) pos(132) pos(224)
// rel(1) = *224 + 1 = 303
[ 184] add pos(224) imm(1) rel(1)
// rel(0) = 195
[ 188] add imm(195) imm(0) rel(0)
[ 192] jmpnot imm(0) pos(108)
// call D with ret=214 and arg0=1, arg1=(14yx < 149x^2-127y^2), arg2=-1
[ 195] lt rel(1) pos(223) rel(2)
[ 199] mul imm(1) pos(23) rel(1)
[ 203] add imm(0) imm(-1) rel(3)
[ 207] mul imm(214) imm(1) rel(0)
[ 211] jmpnot imm(0) imm(303)
// maybe |149x^2-127y^2| < 14yx ?
// print ret+1
[ 214] add imm(1) rel(1) rel(1)
[ 218] print rel(1)
[ 220] halt
// data section for the above
[ 221] [0] // X
[ 222] [0] // Y
[ 223] [0] // 149x^2 if x < 149 then 149x^2 - 127y^2
[ 224] [0] // 127y^2 if y < 127 then scratch
// calling convention for procedure with N parameters:
// push ret and arguments 1..N onto the stack, in that order.
// retrieve return value from rel+1
// procedure will move stack pointer forward by N+K, where
// K is the number of locals to be used, then pop the stack
// by moving it back by N+K and jump to rel(=ret). the return
// value will be at rel+1.
// ==========================================================
// procedure A (4 params):
// pos(249) <- arg0
// push arg1
// push arg2
// push arg3
// call procedure arg0 with ret=250, arg1, arg2, arg3
// return the return value
// =>
// return arg0(arg1, arg2, arg3)
[ 225] adjrel imm(5)
[ 227] mul rel(-4) imm(1) pos(249)
[ 231] mul imm(1) rel(-3) rel(1)
[ 235] add rel(-2) imm(0) rel(2)
[ 239] add rel(-1) imm(0) rel(3)
[ 243] mul imm(1) imm(250) rel(0)
[ 247] jmpif imm(1) imm(225) // 225 -> arg0, see above
[ 250] mul imm(1) rel(1) rel(-4)
[ 254] adjrel imm(-5)
[ 256] jmpnot imm(0) rel(0)
// ==========================================================
// procedure B (1 params, 1 local):
// x0 = 2 * (arg0 > 0 ? 1 : 0) - 1
// return x0 * arg0
// =>
// return abs(arg0)
[ 259] adjrel imm(3)
[ 261] lt imm(0) rel(-2) rel(-1)
[ 265] mul rel(-1) imm(2) rel(-1)
[ 269] add rel(-1) imm(-1) rel(-1)
[ 273] mul rel(-1) rel(-2) rel(-2)
[ 277] adjrel imm(-3)
[ 279] jmpif imm(1) rel(0)
// ==========================================================
// procedure C:
// x0 = arg0 < 0
// if !x0: goto 294
// print(0)
// halt
// 294: arg0 *= 1
// return
// =>
// if x0 < 0:
// print(0)
// halt
// return x0
[ 282] adjrel imm(3)
[ 284] lt rel(-2) imm(0) rel(-1)
[ 288] jmpnot rel(-1) imm(294)
[ 291] print imm(0)
[ 293] halt
[ 294] mul rel(-2) imm(1) rel(-2)
[ 298] adjrel imm(-3)
[ 300] jmpnot imm(0) rel(0)
// procedure D (3 params, 1 local):
// arg0, arg1, arg2:
// if
// if arg1 >= arg0:
// goto 346
[ 303] adjrel imm(5)
[ 305] lt rel(-3) rel(-4) rel(-1)
[ 309] jmpnot rel(-1) imm(346)
// if arg0 > arg1:
[ 312] add rel(-4) rel(-3) rel(-4)
[ 316] mul rel(-3) imm(-1) rel(-1)
[ 320] add rel(-4) rel(-1) rel(2)
[ 324] mul rel(2) imm(-1) rel(-1)
[ 328] add rel(-4) rel(-1) rel(1)
[ 332] add imm(0) rel(-2) rel(3)
[ 336] add imm(343) imm(0) rel(0)
[ 340] jmpnot imm(0) imm(303)
[ 343] jmpnot imm(0) imm(415)
// if arg0 <= arg1
// x0 = arg2 < arg1
// if !x0: goto 387
// => if arg1 <= arg2: goto 387
[ 346] lt rel(-2) rel(-3) rel(-1)
[ 350] jmpnot rel(-1) imm(387)
// if arg2 < arg1:
// arg1 += arg2 (from 88: 199)
[ 353] add rel(-3) rel(-2) rel(-3)
// local0 = -arg2
[ 357] mul rel(-2) imm(-1) rel(-1)
// call proc D with arg0, arg2, arg1
// third arg: arg1 + local0 = arg1+arg2-arg2 = arg1
[ 361] add rel(-3) rel(-1) rel(3)
// local0 = third arg * -1 = -arg1
[ 365] mul rel(3) imm(-1) rel(-1)
// second arg: arg1 + local0 = arg1+arg2 - arg1 = arg2
[ 369] add rel(-3) rel(-1) rel(2)
// first arg: arg0
[ 373] add imm(0) rel(-4) rel(1)
// set ret=384
[ 377] mul imm(1) imm(384) rel(0)
[ 381] jmpnot imm(0) imm(303)
// jump to 415 (return)
[ 384] jmpif imm(1) imm(415)
// if arg1 <= arg2:
// arg0 *= -1 (from 27: -1) (from 88: -50)
[ 387] mul rel(-4) imm(-1) rel(-4)
// arg0 += arg1 (from 27: 0) (from 88: 0)
[ 391] add rel(-4) rel(-3) rel(-4)
// arg2 *= arg1 (from 27: Y) (from 88: x * 149 = 7450)
[ 395] mul rel(-3) rel(-2) rel(-2)
// arg0 *= arg2 (from 27: 0) (from 88: 0)
[ 399] mul rel(-2) rel(-4) rel(-4)
// arg1 *= arg2 (from 27: Y) (from 88: x * x * 149 = 149x^2)
[ 403] mul rel(-3) rel(-2) rel(-3)
// arg2 = -arg0 (from 27: 0) (from 88: 0)
[ 407] mul rel(-4) imm(-1) rel(-2)
// x0 = arg1 + arg2 (from 27: Y) (from 88: 149x^2)
[ 411] add rel(-3) rel(-2) rel(1)
// return x0 = arg1 + arg2 (from 27: Y) (from 88: 149x^2)
[ 415] mul imm(1) rel(1) rel(-4)
[ 419] adjrel imm(-5)
[ 421] jmpnot imm(0) rel(0)
You can’t perform that action at this time.