# Fountain OOO REliving

Provided file is [fountain-ooo-relive](https://pastebin.com/raw/ncHEVjuw)

Theme hints at Game of Life, comment in file hints that it can be opened with Golly (a Game of Life engine). It's a really big pattern with some gridlike sections and some labels indicating that it's a computer - opcodes, RAM and ROM, etc.

But zoom in further and each pixel turns out to be made of many smaller pixels in standard Game of Life layouts. These form [OTCA Metapixels](https://www.conwaylife.com/wiki/OTCA_metapixel). Each is 2048x2048 Life cells and they can simulate the Game of Life itself, or any other similar ruleset. But something's a little different - different metapixels have different rulesets and they don't form a complete grid.

Some research into the architecture of the computer this is all being used to simulate (the names of the opcodes like "MLZ" etc make good search terms) turns up the [Quest for Tetris](https://github.com/QuestForTetris), a project to implement Tetris in Game of Life by using OTCA metapixels to build a computer which can run Tetris. A [thread](https://codegolf.stackexchange.com/questions/11880/build-a-working-game-of-tetris-in-conways-game-of-life) on Code Golf StackOverflow has a good overview of the architecture.

To play around with this more we should get it to run, but it runs very slowly because each metapixel cycle takes thousands of Life cycles and each CPU cycle takes thousands of metapixel cycles, so we should "decompile" the metapixels into single pixels in the VarLife ruleset (this is the opposite of the process Quest for Tetris used to generate the computer). `meta2varlife.lua` (run as a script within Golly) will do this by checking the pixels which program each metacell's ruleset and translating into VarLife. `Varlife.rule` (copied from Quest For Tetris) has been modified with the colors dimmed except for the "on" states which makes it much easier to read the contents of RAM and see the computer operating.

Now we can see that RAM is initially all 0 except for address 1 which has a few bits set. When we run, RAM fills up and then is modified and eventually the CPU halts. Maybe the flag is in RAM? `readram.lua` dumps the contents of RAM and we can use that to get the initial and final states (see `ram.txt`). But there's no obvious ASCII encoded text or anything like that.

The challenge is tagged as reversing so let's see what the program is doing. `readrom.lua` reads the program ROM and translates into the QFTASM assembly language (`rom.txt`), which we can run on the QFTASM [interpreter](http://play.starmaninnovations.com/qftasm/) and confirm that we get the same results there as when running in Golly. The code writes a bunch of constants into addresses 2 through 39, then subtracts a different constant XOR the value at address 1 from each of those addresses, then halts.

Since this computer has no I/O, input is done by writing directly into memory. So it seems like the value in address 1, which is never written to but is used to modify the contents of memory, is supposed to be the input, and its value affects the final value in each of the addresses 2 through 39 which the program modifies. So maybe we need to find the right value at address 1 which will end up with the flag in those addresses. We can check if we have it right because we know the flag format starts with "OOO" and it will be ASCII.

`hack.swift` simulates the program's calculations for every possible value of address 1 (it's only 16 bits so we can just brute force, no need to use some fancy solver) and filters to only those which produce valid ASCII and start with "OOO". It will quickly find the flag: `OOO{in_this_life___youre_on_your_own}`.

## Files

### meta2varlife.lua
```
local g = golly()

local getcell = g.getcell
local setcell = g.setcell

local r = g.getrect()
local x, y, width, height = r[1], r[2], r[3], r[4]

local mygrid = {}

-- bounding box is -8388608, -8388607, 10295296, 2965504
-- print('expected bounding box:', -8388608, -8388607, 10295296, 2965504)
-- print('actual bounding box: ', x, y, width, height)

-- Pixel addresses of the pixels indicating rules for a random metapixel:
-- B8 -8386412 -7094915
-- B7 -8386412 -7094905
-- B6 -8386412 -7094895
-- B5 -8386412 -7094869
-- B4 -8386412 -7094859
-- B3 -8386412 -7094849
-- B2 -8386412 -7094823
-- B1 -8386412 -7094913
-- B0 -8386412 -7094803
-- S8 -8386412 -7094913
-- S7 -8386412 -7094903
-- S6 -8386412 -7094893
-- S5 -8386393 -7094867
-- S4 -8386393 -7094857
-- S3 -8386393 -7094847
-- S2 -8386393 -7094821
-- S1 -8386393 -7094911
-- S0 -8386393 -7094801

-- rulesets for varlife: B/S (no metapixel), B1/S, B2s, B12/S1
-- So we can just check B1 and B2
-- B2 -8386412 -7094823
-- B1 -8386412 -7094913
-- take those relative to the x,y of bounding box, modulo 2048:
-- b1: (148, 1496), b2: (148, 1506)
-- now I don't really understand Varlife.rule but we can go off the colors
-- and cross-reference with the colors here:
-- http://play.starmaninnovations.com/varlife/BeeHkfCpNR
-- [not listed] 0 -> B/S dead
-- 1 255 255 255 -> B/S alive (should never happen)
-- 2 0 0 255 -> B1/S dead
-- 3 0 255 255 -> B1/S alive
-- 4 0 255 0 -> B2/S dead
-- 5 255 255 0 -> B2/S alive
-- 6 255 0 0 -> B12/S1 dead
-- 7 255 128 0 -> B12/S1 alive

-- finally some metapixels are enabled
-- one of the pixels in the center of one which is enabled is at:
-- -1754083, -7103591
-- relative to bounding box, mod 2048:
-- 1053, 920
alive_count = 0
for _y = y,y+height,2048 do
local row = {}
for _x = x,x+width,2048 do
local b1 = getcell(148 + _x, 1506 + _y)
local b2 = getcell(148 + _x, 1496 + _y)
local state = getcell(1054 + _x, 920 + _y)

-- b1=0,b2=0: 0
-- b1=1,b2=0: 2
-- b1=0,b2=1: 4
-- b1=0,b2=1: 6
-- (+1 for enabled)
state = state + b2 * 4 + b1 * 2

table.insert(row, state)
if state == 1 then
alive_count = alive_count + 1
end
end
table.insert(mygrid, row)
end

g.addlayer()
g.setrule('Varlife')

for y, row in ipairs(mygrid) do
for x, state in ipairs(row) do
setcell(x,y,state)
end
end

g.fit()
```

### Varife.rule
```
@RULE Varlife

A mixed rule game of life designed in the Quest for Tetris

The PPCG QFT (not Quantum/Quick Fourier Transform) crew, August 10, 2016

@TREE

num_states=8
num_neighbors=8
num_nodes=29
1 0 0 2 2 4 4 6 6
1 0 0 3 2 4 4 7 7
2 0 1 0 1 0 1 0 1
1 0 0 2 2 5 4 7 6
2 1 3 1 3 1 3 1 3
3 2 4 2 4 2 4 2 4
2 3 0 3 0 3 0 3 0
3 4 6 4 6 4 6 4 6
4 5 7 5 7 5 7 5 7
2 0 0 0 0 0 0 0 0
3 6 9 6 9 6 9 6 9
4 7 10 7 10 7 10 7 10
5 8 11 8 11 8 11 8 11
3 9 9 9 9 9 9 9 9
4 10 13 10 13 10 13 10 13
5 11 14 11 14 11 14 11 14
6 12 15 12 15 12 15 12 15
4 13 13 13 13 13 13 13 13
5 14 17 14 17 14 17 14 17
6 15 18 15 18 15 18 15 18
7 16 19 16 19 16 19 16 19
5 17 17 17 17 17 17 17 17
6 18 21 18 21 18 21 18 21
7 19 22 19 22 19 22 19 22
8 20 23 20 23 20 23 20 23
6 21 21 21 21 21 21 21 21
7 22 25 22 25 22 25 22 25
8 23 26 23 26 23 26 23 26
9 24 27 24 27 24 27 24 27

@COLORS

1 32 32 32
2 0 0 32
3 0 0 128
4 0 32 0
5 128 128 0
6 32 0 0
7 255 255 255
```

### readram.lua
```lua
local g = golly()

local getcell = g.getcell

-- ram is on a grid of bits 16 x 71
-- bits are spaced out 22 cells apart (x and y)
-- (16 bit word size)
-- address 0 (lowest x value) is the program counter
-- lowest y value is 1s bit
-- lowest bit of pc is at 3454,32

local words = 71
local word_size = 16
local spacing = 22
local start_x = 3454
local start_y = 32

function signedshort(n)
-- convert positive int to signed for 16-bit twos complement
if n < 0 or n >= 1<<16 then
error("Out of range: " .. n)
end
if n >= 1 << 15 then
return n - (1 << 16)
else
return n
end
end

local output = ""
for address = 0,words-1 do
local x = start_x + address * spacing
word = 0
for place = word_size-1,0,-1 do
local y = start_y + place * spacing
local bit = getcell(x, y) % 2
word = word | (bit << place)
end
output = output .. address .. ": " .. signedshort(word) .. "\n"
end

g.setclipstr(output)
g.note("RAM dump copied to clipboard")
```

### ram.txt
```

Initial RAM contents:
0: 0
1: 12292
2: 0
3: 0
4: 0
...

RAM contents after running to completion:
0: -1
1: 12292
2: 16478
3: -16288
4: 16450
5: 16490
6: -16260
7: -16289
8: -16306
9: -16253
10: -16299
11: -16264
12: 16518
13: -16274
14: -16259
15: -16298
16: 16469
17: -16296
18: -16272
19: 16464
20: 16462
21: -16278
22: 16482
23: 16488
24: -16289
25: -16266
26: 16496
27: -16258
28: -16289
29: -16272
30: 16520
31: 16510
32: 16514
33: -16257
34: -16270
35: 16510
36: 16488
37: -16287
38: 16496
39: -25917
40: 0
41: 0
42: 0
43: 44
44: 0
45: 0
46: 0
...
```

### readrom.lua
```lua
local g = golly()

local getcell = g.getcell

-- rom is a grid of instructions 58 bits high and 116 instructions wide
-- it's "upside down" - opcode at the bottom
-- grows leftwards, so first instruction is at the right
-- bits are spaced out 11 cells apart (x and y)
-- bottom right bit of ROM is at 3198,1378
local instructions = 116
local spacing = 11
local start_x = 3198
local start_y = 1378

local opcodes = {
[0] = 'MNZ',
[1] = 'MLZ',
[2] = 'ADD',
[3] = 'SUB',
[4] = 'AND',
[5] = 'OR' ,
[6] = 'XOR',
[7] = 'ANT',
[8] = 'SL' ,
[9] = 'SRL',
[10] = 'SRA',
}

local types = {
[0] = '',
[1] = 'A',
[2] = 'B',
[3] = 'C'
}

function getbit(address, bit)
local x = start_x - address * spacing
local y = start_y - bit * spacing

-- state of cell will be 0 or 2, convert to 0 or 1
return (getcell(x, y) == 0) and 0 or 1
end

function getbits(address, bottombit, count)
-- get bits for the instruction at address
-- bottombit is the bit index into the instruction
-- count is the count
-- returns as a number
local val = 0
for bit=0,count-1 do
val = val | (getbit(address, bottombit + bit) << bit)
end
return val
end

function signedshort(n)
-- convert positive int to signed for 16-bit twos complement
if n < 0 or n >= 1<<16 then
error("Out of range: " .. n)
end
if n >= 1 << 15 then
return n - (1 << 16)
else
return n
end
end

local output = ""
for address = 0,instructions-1 do
local opcode = getbits(address, 0, 4)
local arg1v = getbits(address, 4, 16)
local arg1t = getbits(address, 20, 2)
local arg2v = getbits(address, 22, 16)
local arg2t = getbits(address, 38, 2)
local arg3v = getbits(address, 40, 16)
local arg3t = getbits(address, 56, 2)

output =
output .. address .. ". " ..
opcodes[opcode] .. " " ..
types[arg1t] .. signedshort(arg1v) .. " " ..
types[arg2t] .. signedshort(arg2v) .. " " ..
types[arg3t] .. signedshort(arg3v) .. ";\n"
end

g.setclipstr(output)
g.note("ROM dump copied to clipboard")
```

### rom.txt
```
0. MLZ -1 44 43;
1. XOR 0 0 2;
2. MLZ -1 25971 2;
3. MLZ -1 14554 3;
4. MLZ -1 22445 4;
5. MLZ -1 25411 5;
6. MLZ -1 3743 6;
7. MLZ -1 13391 7;
8. MLZ -1 12059 8;
9. MLZ -1 2554 9;
10. MLZ -1 15823 10;
11. MLZ -1 5921 11;
12. MLZ -1 18009 12;
13. MLZ -1 14823 13;
14. MLZ -1 4757 14;
15. MLZ -1 7754 15;
16. MLZ -1 22480 16;
17. MLZ -1 8371 17;
18. MLZ -1 12418 18;
19. MLZ -1 22738 19;
20. MLZ -1 16499 20;
21. MLZ -1 7132 21;
22. MLZ -1 22793 22;
23. MLZ -1 22307 23;
24. MLZ -1 12485 24;
25. MLZ -1 7936 25;
26. MLZ -1 26630 26;
27. MLZ -1 15483 27;
28. MLZ -1 6471 28;
29. MLZ -1 1806 29;
30. MLZ -1 22705 30;
31. MLZ -1 25019 31;
32. MLZ -1 16442 32;
33. MLZ -1 5145 33;
34. MLZ -1 15593 34;
35. MLZ -1 23867 35;
36. MLZ -1 23738 36;
37. MLZ -1 14086 37;
38. MLZ -1 23123 38;
39. MLZ -1 0 39;
40. XOR A1 -27179 39;
41. SUB A39 A2 2;
42. XOR A1 -14018 39;
43. SUB A39 A3 3;
44. XOR A1 -22549 39;
45. SUB A39 A4 4;
46. XOR A1 -27735 39;
47. SUB A39 A5 5;
48. XOR A1 -225 39;
49. SUB A39 A6 6;
50. XOR A1 -15190 39;
51. SUB A39 A7 7;
52. XOR A1 -8339 39;
53. SUB A39 A8 8;
54. XOR A1 -1415 39;
55. SUB A39 A9 9;
56. XOR A1 -12768 39;
57. SUB A39 A10 10;
58. XOR A1 -6243 39;
59. SUB A39 A11 11;
60. XOR A1 -18725 39;
61. SUB A39 A12 12;
62. XOR A1 -13743 39;
63. SUB A39 A13 13;
64. XOR A1 -7402 39;
65. SUB A39 A14 14;
66. XOR A1 -4444 39;
67. SUB A39 A15 15;
68. XOR A1 -22495 39;
69. SUB A39 A16 16;
70. XOR A1 -12017 39;
71. SUB A39 A17 17;
72. XOR A1 -16138 39;
73. SUB A39 A18 18;
74. XOR A1 -22234 39;
75. SUB A39 A19 19;
76. XOR A1 -20283 39;
77. SUB A39 A20 20;
78. XOR A1 -5054 39;
79. SUB A39 A21 21;
80. XOR A1 -22161 39;
81. SUB A39 A22 22;
82. XOR A1 -22641 39;
83. SUB A39 A23 23;
84. XOR A1 -16096 39;
85. SUB A39 A24 24;
86. XOR A1 -4238 39;
87. SUB A39 A25 25;
88. XOR A1 -26510 39;
89. SUB A39 A26 26;
90. XOR A1 -13059 39;
91. SUB A39 A27 27;
92. XOR A1 -5726 39;
93. SUB A39 A28 28;
94. XOR A1 -2182 39;
95. SUB A39 A29 29;
96. XOR A1 -22211 39;
97. SUB A39 A30 30;
98. XOR A1 -28099 39;
99. SUB A39 A31 31;
100. XOR A1 -20296 39;
101. SUB A39 A32 32;
102. XOR A1 -7012 39;
103. SUB A39 A33 33;
104. XOR A1 -12961 39;
105. SUB A39 A34 34;
106. XOR A1 -21059 39;
107. SUB A39 A35 35;
108. XOR A1 -21210 39;
109. SUB A39 A36 36;
110. XOR A1 -14493 39;
111. SUB A39 A37 37;
112. XOR A1 -21817 39;
113. SUB A39 A38 38;
114. MLZ -1 -2 0;
115. MLZ 0 0 0;
```

### hack.swift
```swift
import Foundation

#if !swift(>=5.2)
// if your system Swift on macOS is too old try "xcrun swift"
#error("Requires Swift 5.2 or higher")
#endif

// subtrahends are the values initially loaded into memory 2 through 39
let subtrahends: [Int16] = [
25971,
14554,
22445,
25411,
3743,
13391,
12059,
2554,
15823,
5921,
18009,
14823,
4757,
7754,
22480,
8371,
12418,
22738,
16499,
7132,
22793,
22307,
12485,
7936,
26630,
15483,
6471,
1806,
22705,
25019,
16442,
5145,
15593,
23867,
23738,
14086,
23123,
]

// paddedMinuends are the values xor'd with the value in address 1
// the results are then subtracted from each memory location 2 through 39
let paddedMinuends: [Int16] = [
-27179,
-14018,
-22549,
-27735,
-225,
-15190,
-8339,
-1415,
-12768,
-6243,
-18725,
-13743,
-7402,
-4444,
-22495,
-12017,
-16138,
-22234,
-20283,
-5054,
-22161,
-22641,
-16096,
-4238,
-26510,
-13059,
-5726,
-2182,
-22211,
-28099,
-20296,
-7012,
-12961,
-21059,
-21210,
-14493,
-21817,
]

let result = (Int16.min...Int16.max).map { pad -> [UInt16] in
// pad is the input value at address 1
// try every possible value for pad
// perform the same calculation as the QFT machine
// final[i] = paddedMinuend[i] ^ pad - subtrahend[i]
zip(subtrahends, paddedMinuends).map { subtrahend, paddedMinuend in
let minuend = paddedMinuend ^ pad
return UInt16(bitPattern:minuend &- subtrahend)
}
}.filter { result in
// filter only those which produce only single-byte results
!result.contains { value in
value > UInt8.max
}
}.compactMap { result -> String? in
// convert to string (discarding any which are not valid ASCII)
let bytes = result.map { short in UInt8(short) }
return String(bytes: bytes, encoding: .ascii)
}.first { string in
// find the flag, which we know starts with "OOO"
string.hasPrefix("OOO")
}

print(result ?? "No solution")
```