Adding more skill and spell slots to Aya

Sep 3rd, 2020 (edited)
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. The goal of this experiment is to give Aya a new skill (we'll use Maintenance) and a new spell (we'll use Last Judgement). The purpose of this pastebin is to document the process used to achieve the goal, so that others may replicate it with the necessary tools. It is not a guide to patching your own game, and will include several technical explanations to explain how things are being changed. x86 assembly knowledge is extremely important if you plan on following along, at least the basics of how the assembly language works. If you wish to follow along and repeat this experiment, you will need Cheat Engine and Ghidra, with a fully analyzed version of Labyrinth 2's ENGLISH PATCHED exe. The process of analyzing the exe will take several hours, but is vital to analyzing the code in the game.
  3. 1. Figuring out the address where skills are loaded in memory
  4. -------------------------------------------------------------
  6. Open the game and hook Cheat Engine to it, load any save file where Aya has some skill points to spare. Reset her so that all her skills reset to level 0/1. Search for variables with current value equal to 1, then level up her Wind God's Fan skill. Repeat search for value equal to 2, and keep going until you isolate the variable keeping track of that skill's level. If there are multiple matches, reset her again and check which address dropped its value to 1, there should be only one result. Right click the address and "Find out what accesses this address", then load a save file. There should be 4 hits, all of them close in memory. Choose the one with the "mov [ecx+edx],eax" instruction and "Show disassembler". Right above it there should be a call instruction, note down the instruction's hex (should be E8 xxxxF3FF), type that in Ghidra's Instruction Pattern search and find the only instance of the code containing that call.
  8. Don't bother waiting for Ghidra to decompile this function, it's a huge one and we only really care about the assembly here. Note that some instructions above the exe loads the value 0x249 into memory, which corresponds to the spell ID for Wind God's Fan. If we alter this to any other valid spell ID, the game will properly alter Aya's spell into that new spell. Using enemy spells or invalid IDs crashes the game. If we scroll further up, we see similar instructions loading values 0xf5, 0x3e, 0x86, 0x100 and 0x12f. If we search on Ghidra's string references for Aya's skill names, such as Extra Steps, we can follow the reference trail to a function that loads Extra Steps and its description into memory, with a CMP instruction that checks for 0xf5 - leading us to believe this is Extra Steps' skill ID. Repeating this process for the other skills confirms this.
  10. If we scroll down instead, we see a bunch of code that eventually leads to loadings of 0x24a, 0x24b and 0x24c in memory, Aya's other spells. Even further down, we see a CMP of a specific address in memory to 1, and below that very similar code loading values 0x197, 0x198 and 0x182 in memory. A search for Aya's awakening skills reveals these to be her awakening skills' IDs, so everything below that CMP is only loaded in when Aya is awakened. If we switch that comparison to 0, we make it so her awakening skills are always available. Switching it to 2, 3, ... will make it so you need 2, 3, ... of her awakening items to unlock the skills.
  12. 2. Understanding how the game is loading skills and spells into memory
  13. ----------------------------------------------------------------------
  15. Let's break down the code that is loading the skill Tengu's Wind into memory. We know that the code must start somewhere before 0x86 is loaded, and end somewhere after it is loaded. If we look for a pattern among how skills are loaded, we can isolate each skill's code ro look like this:
  17. 00d1f0ec b8 08 00 MOV EAX,0x8
  18. 00 00
  19. 00d1f0f1 6b c8 16 IMUL ECX,EAX,0x16
  20. 00d1f0f4 8b 55 f8 MOV EDX,dword ptr [EBP - 0x8]
  21. 00d1f0f7 8d 84 0a LEA EAX,[EDX + ECX*0x1 + 0x4fc]
  22. fc 04 00 00
  23. 00d1f0fe b9 04 00 MOV ECX,0x4
  24. 00 00
  25. 00d1f103 6b d1 00 IMUL EDX,ECX,0x0
  26. 00d1f106 c7 04 10 MOV dword ptr [EAX + EDX*0x1],0x86
  27. 86 00 00 00
  29. Note that the only differences between skills are the values in the IMUL and final MOV instructions. The value in IMUL seems to increment as we load more spells, indicating that maybe it is the skill slot corresponding to that skill. This seems to match up to the order the skills show up in, starting at 0x14. Note that the final awakening skill loads in slot 0x1b, and the first spell loads in slot 0x1e, so there should be 2 empty slots to fill with skills. We can also assume that the slot 0x22 is empty, since that's where the fifth spell would be loaded. The value in the MOV instruction is simply the skill ID.
  31. The code is very simple to understand, it is taking 8 times the skill slot, adding it to some value loaded from memory, and using that as an offset to load the skill ID. Interesting to note that the offset is given only for EAX, since EDX is guaranteed to be 0x00 as a result of an IMUL with 0x00 as an operand. The catch here for optimization is that this entire offset calculation is being repeated for each skill, when it is very clear that addresses will be near adjacent, with a fixed offset given by the slot number.
  33. But before that, we should also analyze the code that takes care of loading the spell ID in memory. Taking Wind God's Fan as an example, and using a similar pattern technique like we did for skills, we can isolate the code as:
  35. 00d1f14f b8 08 00 MOV EAX,0x8
  36. 00 00
  37. 00d1f154 6b c8 1e IMUL ECX,EAX,0x1e
  38. 00d1f157 8b 55 f8 MOV EDX,dword ptr [EBP - 0x8]
  39. 00d1f15a 8d 84 0a LEA EAX,[EDX + ECX*0x1 + 0x4fc]
  40. fc 04 00 00
  41. 00d1f161 b9 04 00 MOV ECX,0x4
  42. 00 00
  43. 00d1f166 6b d1 00 IMUL EDX,ECX,0x0
  44. 00d1f169 c7 04 10 MOV dword ptr [EAX + EDX*0x1],0x249
  45. 49 02 00 00
  46. 00d1f170 6a 01 PUSH 0x1
  47. 00d1f172 b8 08 00 MOV EAX,0x8
  48. 00 00
  49. 00d1f177 6b c8 1e IMUL ECX,EAX,0x1e
  50. 00d1f17a 8b 55 f8 MOV EDX,dword ptr [EBP - 0x8]
  51. 00d1f17d 8d 84 0a LEA EAX,[EDX + ECX*0x1 + 0x4fc]
  52. fc 04 00 00
  53. 00d1f184 b9 04 00 MOV ECX,0x4
  54. 00 00
  55. 00d1f189 c1 e1 00 SHL ECX,0x0
  56. 00d1f18c 8b 14 08 MOV EDX,dword ptr [EAX + ECX*0x1]
  57. 00d1f18f 52 PUSH EDX
  58. 00d1f190 8b 45 f8 MOV EAX,dword ptr [EBP - 0x8]
  59. 00d1f193 8b 08 MOV ECX,dword ptr [EAX]
  60. 00d1f195 8b 09 MOV ECX,dword ptr [ECX]
  61. 00d1f197 e8 d1 2e CALL thunk_FUN_01613b50
  62. f3 ff
  63. 00d1f19c ba 08 00 MOV EDX,0x8
  64. 00 00
  65. 00d1f1a1 6b ca 1e IMUL ECX,EDX,0x1e
  66. 00d1f1a4 8b 55 f8 MOV EDX,dword ptr [EBP - 0x8]
  67. 00d1f1a7 8d 8c 0a LEA ECX,[EDX + ECX*0x1 + 0x4fc]
  68. fc 04 00 00
  69. 00d1f1ae ba 04 00 MOV EDX,0x4
  70. 00 00
  71. 00d1f1b3 c1 e2 00 SHL EDX,0x0
  72. 00d1f1b6 89 04 11 MOV dword ptr [ECX + EDX*0x1],EAX
  74. The code behaves in exactly the same way as the skill loading, but with some extra stuff at the end. After loading 0x249, it performs a function call to do something, then loads another value into some address. Since we dont know what the function does, taking a guess at what is being pushed into the stack is beyond us. However, do note the game is calculating the address we have on EAX again, the code up to the SHL instruction is identical to the one used to load 0x249 in memory. That SHL instruction btw is completely useless since it has 0x00 as its second operand.
  76. After the function call, it computes ONCE AGAIN the address offset it computed just a few instructions above, but this time on EDX instead of EAX. It does this so that the value in EAX (which likely comes from the function) is stored in the address pointed to by ECX+EDX. Needless to say, this entire mess can be shortened greatly. But we're getting ahead of ourselves.
  78. 3. Optimizing the code that loads skills
  79. ----------------------------------------
  81. The code that loads a single skill can't really be optimized any further, it needs to figure out where it must load the ID in memory. However, if we are chaining a bunch of these, there is no need to compute a new offset from scratch, we can use the result from the previous load, since we know the step the addresses take is equal to 8 bytes. We know this because 0x8 is loaded in EAX for the IMUL instruction. So instead of computing all of that multiple times, we can just do:
  83. MOV EAX,0x8
  84. IMUL ECX,EAX,0x16
  85. MOV EDX,dword ptr [EBP - 0x8]
  86. LEA EAX,[EDX + ECX*0x1 + 0x4fc]
  87. MOV ECX,0x4
  88. IMUL EDX,ECX,0x0
  89. MOV dword ptr [EAX + EDX*0x1],0x12f
  90. ADD eax,0x8
  91. MOV dword ptr [EAX + EDX*0x1],0x100
  92. ADD eax,0x8
  93. MOV dword ptr [EAX + EDX*0x1],0x86
  94. ADD eax,0x8
  95. MOV dword ptr [EAX + EDX*0x1],0x3e
  96. ADD eax,0x8
  97. MOV dword ptr [EAX + EDX*0x1],0xf5
  99. To load all 5 of Aya's skills in memory. Needless to say, this uses up way less bytes than the previous mess, and because we cannot go and change every single jump and call in the rest of the program, we should pad the now useless bytes with NOPs (opcode 90). This will ensure any and all relative jumps will still work, preserving the file size.
  101. 4. Using the free space to load a new skill slot
  102. ------------------------------------------------
  104. Now that we have a sequence of NOPs between loading the last skill and the first spell, we can use these new bytes to do whatever we want! Simply replace the NOPs as needed with the code you want to run. In this example, we'll be loading the skill Maintenance in slot 0x1c, which we assumed was an empty slot above. Maintenance's skill ID is 0x101, and since we're moving 4 slots at once when chaining our loads, we should add 4*0x8 = 0x20 to EAX:
  106. MOV EAX,0x8
  107. IMUL ECX,EAX,0x16
  108. MOV EDX,dword ptr [EBP - 0x8]
  109. LEA EAX,[EDX + ECX*0x1 + 0x4fc]
  110. MOV ECX,0x4
  111. IMUL EDX,ECX,0x0
  112. MOV dword ptr [EAX + EDX*0x1],0x12f
  113. ADD eax,0x8
  114. MOV dword ptr [EAX + EDX*0x1],0x100
  115. ADD eax,0x8
  116. MOV dword ptr [EAX + EDX*0x1],0x86
  117. ADD eax,0x8
  118. MOV dword ptr [EAX + EDX*0x1],0x3e
  119. ADD eax,0x8
  120. MOV dword ptr [EAX + EDX*0x1],0xf5
  121. ADD eax,0x20
  122. MOV dword ptr [EAX + EDX*0x1],0x101
  124. If you want to apply these changes in a hex editor, look for the sequence E8 F7 F0 F3 FF, which is the function call just before the first instruction in the algorithm we're changing. Change the bytes from there on to look like this, so it matches the code above:
  126. E8 F7 F0 F3 FF CALL function offset
  127. B8 08 00 00 00 MOV EAX,0x8
  128. 6B C8 14 IMUL ECX,EAX,0x14
  129. 8B 55 F8 MOV EDX,DWORD PTR [EBP-0x8]
  130. 8D 84 0A FC 04 00 00 LEA EAX,[EDX+ECX*1+0x4FC]
  131. B9 04 00 00 00 MOV ECX,0x4
  132. 6B D1 00 IMUL EDX,ECX,0x0
  133. C7 04 10 2F 01 00 00 MOV DWORD PTR [EAX+EDX*1],0x12F
  134. 05 08 00 00 00 ADD EAX,0x8
  135. C7 04 10 00 01 00 00 MOV DWORD PTR [EAX+EDX*1],0x100
  136. 05 08 00 00 00 ADD EAX,0x8
  137. C7 04 10 86 00 00 00 MOV DWORD PTR [EAX+EDX*1],0x86
  138. 05 08 00 00 00 ADD EAX,0x8
  139. C7 04 10 3E 00 00 00 MOV DWORD PTR [EAX+EDX*1],0x3E
  140. 05 08 00 00 00 ADD EAX,0x8
  141. C7 04 10 F5 00 00 00 MOV DWORD PTR [EAX+EDX*1],0xF5
  142. 05 20 00 00 00 ADD EAX,0x20
  143. C7 04 10 01 01 00 00 MOV DWORD PTR [EAX+EDX*1],0x101
  145. 5. Optimizing the code that loads spells
  146. ----------------------------------------
  148. The code that loads a single spell can be optimized, as we saw previously. There's no need to compute the address 3 times in a row, so we can shorten the code to be like shown below. Pushing EAX into the stack before the function call, then popping it to ECX saves the third offset calculation. We can also remove the useless SHL instructions.
  150. MOV EAX,0x8
  151. IMUL ECX,EAX,0x1e
  152. MOV EDX,dword ptr [EBP - 0x8]
  153. LEA EAX,[EDX + ECX*0x1 + 0x4fc]
  154. MOV ECX,0x4
  155. IMUL EDX,ECX,0x0
  156. MOV dword ptr [EAX + EDX*0x1],0x249
  157. PUSH EAX
  158. PUSH 0x1
  159. MOV ECX,0x4
  160. MOV EDX,dword ptr [EAX + ECX*0x1]
  161. PUSH EDX
  162. MOV EAX,dword ptr [EBP - 0x8]
  163. MOV ECX,dword ptr [EAX]
  164. MOV ECX,dword ptr [ECX]
  165. CALL thunk_FUN_01613b50
  166. POP ECX
  167. MOV EDX,0x4
  168. MOV dword ptr [ECX + EDX*0x1],EAX
  170. However, we can further optimize this code if we chain it from a previous skill load. Since EAX will already have some offset calculated, we can just add to it and go straight to loading the skill ID, just like we did for chaining skill loads. If we wanted to load Wind God's Fan right after we added Maintenance, we could simply add the following to our previous skill load code, remembering we must go 2 slots over the one we placed Maintenance in:
  172. ADD eax,0x10
  173. MOV dword ptr [EAX + EDX*0x1],0x249
  174. PUSH EAX
  175. PUSH 0x1
  176. MOV ECX,0x4
  177. MOV EDX,dword ptr [EAX + ECX*0x1]
  178. PUSH EDX
  179. MOV EAX,dword ptr [EBP - 0x8]
  180. MOV ECX,dword ptr [EAX]
  181. MOV ECX,dword ptr [ECX]
  182. CALL thunk_FUN_01613b50
  183. POP ECX
  184. MOV EDX,0x4
  185. MOV dword ptr [ECX + EDX*0x1],EAX
  187. The one thing to worry about here is fixing the CALL instruction. Because we changed how many bytes there are before it, the offset is now invalid, and leaving it as is will crash the game. You need to compute the new offset manually, based on how many bytes were taken care of. The formula to use for this is as follows:
  189. [Old base address] + [Old CALL offset] = [New base address] + [New CALL offset]
  191. 6. Using the free space to load a new spell slot
  192. ------------------------------------------------
  194. We have enough space left over in our NOPs from step 4 to include a new spell in there without much effort. For this example we'll just leave the code past the NOPs as is, loading Aya's spells normally with the original algorithm that computes the offsets multiple times. We'll add Last Judgement (spell ID 0x2d5) to Aya's 5th spell slot (number 0x22), and we'll leech off the load we did for Maintenance. The final code will look like this:
  196. MOV EAX,0x8
  197. IMUL ECX,EAX,0x16
  198. MOV EDX,dword ptr [EBP - 0x8]
  199. LEA EAX,[EDX + ECX*0x1 + 0x4fc]
  200. MOV ECX,0x4
  201. IMUL EDX,ECX,0x0
  202. MOV dword ptr [EAX + EDX*0x1],0x12f
  203. ADD eax,0x8
  204. MOV dword ptr [EAX + EDX*0x1],0x100
  205. ADD eax,0x8
  206. MOV dword ptr [EAX + EDX*0x1],0x86
  207. ADD eax,0x8
  208. MOV dword ptr [EAX + EDX*0x1],0x3e
  209. ADD eax,0x8
  210. MOV dword ptr [EAX + EDX*0x1],0xf5
  211. ADD eax,0x20
  212. MOV dword ptr [EAX + EDX*0x1],0x101
  213. ADD eax,0x30
  214. MOV dword ptr [EAX + EDX*0x1],0x249
  215. PUSH EAX
  216. PUSH 0x1
  217. MOV ECX,0x4
  218. MOV EDX,dword ptr [EAX + ECX*0x1]
  219. PUSH EDX
  220. MOV EAX,dword ptr [EBP - 0x8]
  221. MOV ECX,dword ptr [EAX]
  222. MOV ECX,dword ptr [ECX]
  223. CALL thunk_FUN_01613b50
  224. POP ECX
  225. MOV EDX,0x4
  226. MOV dword ptr [ECX + EDX*0x1],EAX
  228. If you want to apply these changes in a hex editor, look for the sequence E8 F7 F0 F3 FF, just like before, which is the function call just before the first instruction in the algorithm we're changing. Change the bytes from there on to look like this, so it matches the code above, with the already fixed CALL offset for the spell being loaded:
  230. E8 F7 F0 F3 FF CALL function offset
  231. B8 08 00 00 00 MOV EAX,0x8
  232. 6B C8 14 IMUL ECX,EAX,0x14
  233. 8B 55 F8 MOV EDX,DWORD PTR [EBP-0x8]
  234. 8D 84 0A FC 04 00 00 LEA EAX,[EDX+ECX*1+0x4FC]
  235. B9 04 00 00 00 MOV ECX,0x4
  236. 6B D1 00 IMUL EDX,ECX,0x0
  237. C7 04 10 2F 01 00 00 MOV DWORD PTR [EAX+EDX*1],0x12F
  238. 05 08 00 00 00 ADD EAX,0x8
  239. C7 04 10 00 01 00 00 MOV DWORD PTR [EAX+EDX*1],0x100
  240. 05 08 00 00 00 ADD EAX,0x8
  241. C7 04 10 86 00 00 00 MOV DWORD PTR [EAX+EDX*1],0x86
  242. 05 08 00 00 00 ADD EAX,0x8
  243. C7 04 10 3E 00 00 00 MOV DWORD PTR [EAX+EDX*1],0x3E
  244. 05 08 00 00 00 ADD EAX,0x8
  245. C7 04 10 F5 00 00 00 MOV DWORD PTR [EAX+EDX*1],0xF5
  246. 05 20 00 00 00 ADD EAX,0x20
  247. C7 04 10 01 01 00 00 MOV DWORD PTR [EAX+EDX*1],0x101
  248. 05 30 00 00 00 ADD EAX,0x30
  249. C7 04 10 D5 02 00 00 MOV DWORD PTR [EAX+EDX*1],0x2D5
  250. 50 PUSH EAX
  251. 6A 01 PUSH 0x1
  252. B9 04 00 00 00 MOV ECX,0x4
  253. 8B 14 08 MOV EDX,DWORD PTR [EAX+ECX*1]
  254. 52 PUSH EDX
  255. 8B 45 F8 MOV EAX,DWORD PTR [EBP-0x8]
  256. 8B 08 MOV ECX,DWORD PTR [EAX]
  257. 8B 09 MOV ECX,DWORD PTR [ECX]
  258. E8 42 2F F3 FF CALL 0xFFF32FC8
  259. 59 POP ECX
  260. BA 04 00 00 00 MOV EDX,0x4
  261. 89 04 11 MOV DWORD PTR [ECX+EDX*1],EAX
  263. The final result will be an Aya that knows Maintenance and Last Judgement, as well as every other skill and spell she has. This procedure can be performed for every character, and with enough NOPs it should be possible for everyone to have 10 skills and 5 spells, assuming there's enough room to optimize everything. There should be if you fully optimize the entire algorithm, I stuck to a small portion of it.
RAW Paste Data Copied