The Lua code snippets in the question simply import a string consisting of a long sequence of escapes, and then run the imported object. Treating the string as a binary file, we get something like:
0000000: 1b4c 7561 5100 0104 0404 0800 0000 0000 .LuaQ...........
0000010: 0000 0000 0000 0000 0000 0213 0601 0000 ................
...
The first 12 bytes are the header to compiled Lua bytecode. That means that our first step is to:
Step 1: Write a Lua Decompiler
I wasn't really satisfied with the existing tools for manipulating Lua bytecode, plus I love to learn new languages, so I wrote my own parser in Mathematica.
This took quite a while, since the documentation is not that great: I had only the source code and this document to guide me. However, it was made easier by the fact that Lua's VM operates on a very high level, has very few instructions, and uses a stack-based register scheme.
Although my code handles both version 5.1 and 5.2, the way closures are handled in 5.1 is slightly easier to understand, so that's the version that I chose to analyze.
Step 2: Analyze the Bytecode
Once the parser was written, this part actually went pretty fast. ChipperNickel
hinted that large sections of the code had no effect on the output. Even before parsing the bytecode you can tell that math.random
is used (global function names are stored as strings in the constants table) even though we know that the output is deterministic.
We start looking at the end of the instructions section of the top-level function:
249 GETGLOBAL 11 50 R11 = global("print")
250 MOVE 12 9 0 R12 = R9
251 CALL 11 2 1 R11(R12)
252 MOVE 11 4 0 R11 = R4
253 GETGLOBAL 12 51 R12 = global("io")
254 GETTABLE 12 12 308 R12 = R12["write"]
255 GETTABLE 13 10 9 R13 = R10[R9]
256 LOADK 14 53 R14 = " ("
257 MOVE 15 9 0 R15 = R9
258 LOADK 16 54 R16 = ")"
259 CONCAT 13 13 16 R13 = R13 .. R14 .. R15 .. R16
260 CALL 11 3 1 R11(R12, R13)
261 RETURN 0 1 0 return
Eliminating the intermediate assignments, we end up with:
print(R9)
R4(io.write, R10[R9] .. " (" .. R9 .. ")")
return
This matches the output format of the program perfectly (right down to the missing \n
):
1
Ace of Spades (1)
Assuming that the function in R4
actually calls io.write
and that this is not a red herring, we now know that R9
is the number of the card and R10
is a table containing a list of card names as strings. We just need to find out how R9
is calculated and what order the cards are placed in R10
.
However, I'll first take a quick detour to inspect the function in R4
, just to make sure we have everything right. R4
is last set here:
61 CLOSURE 4 3 R4 = closure(KPROTO3, R4, ...)
Thus we're looking for the third function prototype. The header of the third function lists two input parameters (matching what we've seen) and no upvalues
(which is good because it won't depend on other registers manipulated during program execution). It also occupied lines 51-58 of the source code (starting and ending line numbers are not stripped with the rest of the debugging information) so we know it's relatively short. Here is the entire instruction listing for the function:
0 NEWTABLE 2 0 0 R2 = {}
1 LOADK 3 0 R3 = 1.
2 GETGLOBAL 4 1 R4 = global("math")
3 GETTABLE 4 4 258 R4 = R4["random"]
4 LOADK 5 3 R5 = 20.
5 LOADK 6 4 R6 = 50.
6 CALL 4 3 2 R4 = R4(R5, R6)
7 LOADK 5 0 R5 = 1.
8 FORPREP 3 8 R3 -= R5; PC += 8
9 LEN 7 2 0 R7 = len(R2)
10 ADD 7 7 256 R7 = R7 + 1.
11 GETGLOBAL 8 1 R8 = global("math")
12 GETTABLE 8 8 258 R8 = R8["random"]
13 LOADK 9 5 R9 = 10.
14 LOADK 10 3 R10 = 20.
15 CALL 8 3 2 R8 = R8(R9, R10)
16 SETTABLE 2 7 8 R2[R7] = R8
17 FORLOOP 3 9 R3 += R5; if(R3 <?= R4) { R6 = R3; PC += -9 }
18 LEN 3 2 0 R3 = len(R2)
19 ADD 3 3 256 R3 = R3 + 1.
20 SETTABLE 2 3 0 R2[R3] = R0
21 LEN 3 2 0 R3 = len(R2)
22 GETTABLE 3 2 3 R3 = R2[R3]
23 MOVE 4 1 0 R4 = R1
24 TAILCALL 3 2 0 return R3(R4)
25 RETURN 3 0 0 return R3, ...
26 RETURN 0 1 0 return
Note that a function call treats the stack as empty except for the input arguments, so we start off with R0
as io.write
and R1
as the output string.
First I'll note that R2
contains a list and is not reassigned throughout the function.
Lines 18-20 append io.write
to the end of the list. Lines 21 and 22 then extract that element back out of the list. Finally, line 24 calls io.write(R1)
, which is what we suspected the output was in the first place. This means we can disregard the rest of the function.
Now we are looking for where R10
is populated and R9
is calculated. Going back a little in the top-level function we see:
120 NEWTABLE 10 0 0 R10 = {}
121 GETGLOBAL 11 26 R11 = global("table")
122 GETTABLE 11 11 283 R11 = R11["insert"]
123 MOVE 12 10 0 R12 = R10
124 LOADK 13 28 R13 = "Ace of Spades"
125 CALL 11 3 1 R11(R12, R13)
126 LOADK 11 25 R11 = 2.
127 LOADK 12 29 R12 = 10.
128 LOADK 13 14 R13 = 1.
129 FORPREP 11 7 R11 -= R13; PC += 7
130 GETGLOBAL 15 26 R15 = global("table")
131 GETTABLE 15 15 283 R15 = R15["insert"]
132 MOVE 16 10 0 R16 = R10
133 MOVE 17 14 0 R17 = R14
134 LOADK 18 30 R18 = " of Spades"
135 CONCAT 17 17 18 R17 = R17 <> R18
136 CALL 15 3 1 R15(R16, R17)
137 FORLOOP 11 8 R11 += R13; if(R11 <?= R12) { R14 = R11; PC += -8 }
138 GETGLOBAL 11 26 R11 = global("table")
139 GETTABLE 11 11 283 R11 = R11["insert"]
140 MOVE 12 10 0 R12 = R10
141 LOADK 13 31 R13 = "Jack of Spades"
142 CALL 11 3 1 R11(R12, R13)
143 GETGLOBAL 11 26 R11 = global("table")
144 GETTABLE 11 11 283 R11 = R11["insert"]
145 MOVE 12 10 0 R12 = R10
146 LOADK 13 32 R13 = "Queen of Spades"
147 CALL 11 3 1 R11(R12, R13)
148 GETGLOBAL 11 26 R11 = global("table")
149 GETTABLE 11 11 283 R11 = R11["insert"]
150 MOVE 12 10 0 R12 = R10
151 LOADK 13 33 R13 = "King of Spades"
152 CALL 11 3 1 R11(R12, R13)
153 GETGLOBAL 11 26 R11 = global("table")
154 GETTABLE 11 11 283 R11 = R11["insert"]
155 MOVE 12 10 0 R12 = R10
156 LOADK 13 34 R13 = "Ace of Diamonds"
157 CALL 11 3 1 R11(R12, R13)
Without doing a detailed analysis of this code I can see that we're creating an empty list in R10
, and then appending (with table.insert
) cards names in ascending order, with the ace first. The suit order is Spades, Diamonds, Clubs, Hearts. (Personally I would have made a doubly-nested loop, indexing into a list of suit names in the outer loop. This has the advantage of tightening up the source code while further obfuscating the bytecode.)
Looking back at the instruction just before the previous segment, we see an assignment to R9
:
111 GETGLOBAL 9 15 R9 = global("string")
112 GETTABLE 9 9 280 R9 = R9["len"]
113 GETGLOBAL 10 12 R10 = global("input")
114 CALL 9 2 2 R9 = R9(R10)
115 ADD 8 8 9 R8 = R8 + R9
116 MOVE 9 4 0 R9 = R4
117 MOVE 10 3 0 R10 = R3
118 MOVE 11 8 0 R11 = R8
119 CALL 9 3 2 R9 = R9(R10, R11)
We're calling R9
as a function, but we can see from instruction 116 that it's just our old friend KPROTO3
as R4
again. Thus we can simplify the listing to just:
R9 = R3(R8 + string.len(input))
R3
was last set in instruction 60:
60 CLOSURE 3 2 R3 = closure(KPROTO2, R3, ...)
Thus we must dive into the functions again.
The header for function 2 states that it takes one argument and has no upvalues. However, it occupies a whole 17 lines of source code. Here are the instructions (remember the argument is in R0
):
0 ADD 0 0 256 R0 = R0 + 25.
1 ADD 0 0 257 R0 = R0 + 1.
2 SUB 0 0 258 R0 = R0 - 26.
3 GETGLOBAL 1 3 R1 = global("math")
4 GETTABLE 1 1 260 R1 = R1["floor"]
5 MOVE 2 0 0 R2 = R0
6 CALL 1 2 2 R1 = R1(R2)
7 MOVE 0 1 0 R0 = R1
8 NEWTABLE 1 0 0 R1 = {}
9 LOADK 2 1 R2 = 1.
10 GETGLOBAL 3 3 R3 = global("math")
11 GETTABLE 3 3 261 R3 = R3["random"]
12 LOADK 4 6 R4 = 250.
13 LOADK 5 7 R5 = 999.
14 CALL 3 3 2 R3 = R3(R4, R5)
15 LOADK 4 1 R4 = 1.
16 FORPREP 2 6 R2 -= R4; PC += 6
17 GETGLOBAL 6 3 R6 = global("math")
18 GETTABLE 6 6 261 R6 = R6["random"]
19 LOADK 7 8 R7 = 0.
20 LOADK 8 7 R8 = 999.
21 CALL 6 3 2 R6 = R6(R7, R8)
22 SETTABLE 1 5 6 R1[R5] = R6
23 FORLOOP 2 7 R2 += R4; if(R2 <?= R3) { R5 = R2; PC += -7 }
24 LEN 2 1 0 R2 = len(R1)
25 ADD 2 2 257 R2 = R2 + 1.
26 SETTABLE 1 2 0 R1[R2] = R0
27 LOADNIL 0 0 0 R0 = nil
28 LEN 2 1 0 R2 = len(R1)
29 GETTABLE 2 1 2 R2 = R1[R2]
30 MOD 2 2 265 R2 = R2 % 52.
31 EQ 0 2 264 if(R2 == 0.) PC++
32 JMP 0 3 PC += 3
33 LOADK 2 9 R2 = 52.
34 RETURN 2 2 0 return R2
35 JMP 0 4 PC += 4
36 LEN 2 1 0 R2 = len(R1)
37 GETTABLE 2 1 2 R2 = R1[R2]
38 MOD 2 2 265 R2 = R2 % 52.
39 RETURN 2 2 0 return R2
40 RETURN 0 1 0 return
It's blatantly obvious from the first three instructions that Lua does not use an optimizing compiler. We'll treat those as a noop.
Now we go backwards, just as before. Note that there are two return statements amid a bunch of jumps. Parsing that code (instructions 28-40) nets us:
R2 = R1[len(R1)] % 52
if R2 == 0 then
return 52
else
return R1[len(R1)] % 52
end
This just returns the last element of the list R1
modulo 52
, using the smallest positive number as the representative of each equivalence class.
However, note that in instructions 24-26, R0
is appended to R1
. This means that we can simplify the code even further:
if R0 % 52 == 0 then
return 52
else
return R0 % 52
end
Since the result of this function is used to index into a list of 52 elements (the list of card names), the effect of this function is to treat the list as cyclic.
Returning to the top-level function we just need to figure out what R8
is set to. Tracing the code back I notice that at instruction 61, the entire stack consists only of function handles (excepting R0
which is not subsequently used):
1 CLOSURE 1 0 R1 = closure(KPROTO0, R1, ...)
...
3 CLOSURE 2 1 R2 = closure(KPROTO1, R2, ...)
...
60 CLOSURE 3 2 R3 = closure(KPROTO2, R3, ...)
61 CLOSURE 4 3 R4 = closure(KPROTO3, R4, ...)
Thus we can go forward from this point. I'll analyze the following instructions in sections:
62 GETGLOBAL 5 13 R5 = global("arg")
63 GETTABLE 5 5 270 R5 = R5[1.]
64 SETGLOBAL 5 12 global("input") = R5
Here we just set input = arg[1]
.
65 GETGLOBAL 5 15 R5 = global("string")
66 GETTABLE 5 5 272 R5 = R5["lower"]
67 GETGLOBAL 6 12 R6 = global("input")
68 CALL 5 2 2 R5 = R5(R6)
69 SETGLOBAL 5 12 global("input") = R5
Here we set input = string.lower(input)
.
70 GETGLOBAL 5 12 R5 = global("input")
71 SELF 5 5 273 R6 = R5; R5 = R5["gsub"]
72 LOADK 7 18 R7 = "%L"
73 LOADK 8 19 R8 = ""
74 CALL 5 4 2 R5 = R5(R6, R7, R8)
75 SETGLOBAL 5 12 global("input") = R5
Equivalent to input = input.gsub(input, "%L", "")
. This replaces all non-lowercase letters with the empty string.
76 LOADK 5 20 R5 = 0.
Initialize R5
to zero. (It will be a counter later on in the code.)
77 GETGLOBAL 6 15 R6 = global("string")
78 GETTABLE 6 6 277 R6 = R6["sub"]
79 GETGLOBAL 7 12 R7 = global("input")
80 LOADK 8 14 R8 = 1.
81 LOADK 9 14 R9 = 1.
82 CALL 6 4 2 R6 = R6(R7, R8, R9)
Here we do R6 = string.sub(input, 1, 1)
to store the first letter of the string in R6
.
83 GETGLOBAL 7 15 R7 = global("string")
84 GETTABLE 7 7 278 R7 = R7["byte"]
85 MOVE 8 6 0 R8 = R6
86 CALL 7 2 2 R7 = R7(R8)
87 SUB 7 7 279 R7 = R7 - 96.
Now we calculate R7 = string.byte(R6) - 96
. This gets the number of the first letter of the string (starting at 1
for a
).
88 LOADK 8 20 R8 = 0.
89 LOADK 9 14 R9 = 1.
90 GETGLOBAL 10 15 R10 = global("string")
91 GETTABLE 10 10 280 R10 = R10["len"]
92 GETGLOBAL 11 12 R11 = global("input")
93 CALL 10 2 2 R10 = R10(R11)
94 LOADK 11 14 R11 = 1.
Here we set up for a for-loop. These lines are equivalent to:
R8 = 0
R9 = 1
R10 = string.len(input)
R11 = 1
Now on to the for-loop itself:
95 FORPREP 9 12 R9 -= R11; PC += 12
96 MOVE 13 4 0 R13 = R4
97 MOVE 14 2 0 R14 = R2
98 GETGLOBAL 15 15 R15 = global("string")
99 GETTABLE 15 15 277 R15 = R15["sub"]
100 GETGLOBAL 16 12 R16 = global("input")
101 MOVE 17 12 0 R17 = R12
102 MOVE 18 12 0 R18 = R12
103 CALL 15 4 0 R15, ... = R15(R16, R17, R18)
104 CALL 13 0 2 R13 = R13(R14, ...)
105 TEST 13 0 0 if(R13) PC++
106 JMP 0 1 PC += 1
107 ADD 5 5 270 R5 = R5 + 1.
108 FORLOOP 9 13 R9 += R11; if(R9 <?= R10) { R12 = R9; PC += -13 }
Note that the for-loop keeps four state registers: the starting index, ending index, and step are stored in R9
-R11
, and the loop variable (I'll use i
) is stored in R12
. We can simplify to:
for i = 1, string.len(input), 1 do
R13 = R4(R2, string.sub(input, i, i))
if R13 do
R5++
end
end
Remembering what KPROTO3
(R4
) does, we can simplify further to:
for i = 1, string.len(input), 1 do
if R2(string.sub(input, i, i)) do
R5++
end
end
Thus we call KPROTO1
(R2
) on all of the letters in the string and increment R5
if the result is truthy.
Finally a calculation:
109 POW 5 5 281 R5 = R5 ** 2.
110 MUL 8 5 7 R8 = R5 * R7
With this, we have almost everything we need. The final card number is, mod 52
, the number of truthy letters in the string, squared, times the value of the first letter, plus the number of letters in the string.
The only step left is to look at function 1. Unfortunately both functions 0 and 1 have a closure on R0
, a list. Function 0 is very simple, just appending its argument minus ten to the list.
Function 1 is also rather straightforward:
0 LOADBOOL 1 0 0 R1 = False
1 LOADK 2 0 R2 = 1.
2 GETUPVAL 3 0 0 R3 = U0
3 LEN 3 3 0 R3 = length(R3)
4 LOADK 4 0 R4 = 1.
5 FORPREP 2 9 R2 -= R4; PC += 9
6 GETGLOBAL 6 1 R6 = global("string")
7 GETTABLE 6 6 258 R6 = R6["byte"]
8 MOVE 7 0 0 R7 = R0
9 CALL 6 2 2 R6 = R6(R7)
10 GETUPVAL 7 0 0 R7 = U0
11 GETTABLE 7 7 5 R7 = R7[R5]
12 EQ 0 6 7 if(R6 == R7) PC++
13 JMP 0 1 PC += 1
14 LOADBOOL 1 1 0 R1 = True
15 FORLOOP 2 10 R2 += R4; if(R2 <?= R3) { R5 = R2; PC += -10 }
16 RETURN 1 2 0 return R1
17 RETURN 0 1 0 return
It simply checks if the character code of the first character of its argument is present in R0
(referred to here as U0
, the first upvalue).
Now we need to understand what values R0
is initialized with. Instructions 5 through 59 are all sequences like:
5 MOVE 3 1 0 R3 = R1
6 LOADK 4 0 R4 = 107.
7 CALL 3 2 1 R3(R4)
This sequence appends 107
(minus 10
) to the list R0
. In addition to a bunch of junk values (junk because they're larger than the max value of a byte), the following important values are appended:
107 - 10 = 97 = 'a'
111 - 10 = 101 = 'e'
115 - 10 = 105 = 'i'
121 - 10 = 111 = 'o'
127 - 10 = 117 = 'u'
Thus, KPROTO2
considers string truthy if they start with vowels.
Step 3: Put It All Together
Although no question was explicitly stated, the implicit question is what procedure does Jason use to map phrases to cards? My answer is:
Jason counts the number of vowels in the phrase, then squares it. Then he multiplies that number by the position in the alphabet (a
is 1, z
is 26) of the phrase's first letter. Then he adds the number of letters in the phrase.
Then, starting with the deck in order, Jason moves the top card to the bottom a number of times equal to the number he calculated. Then he chooses the bottom card.
"anything other than a lowercase letter does not matter"
do you mean we should skip the uppercase letters (e.g. first letters of lines)? $\endgroup$