import argparse
import os
import visualizer
from charTable import CharTable
from charTable import get_move_addrs
from graph import Graph
from memoryReader import MemoryReader
from navigator import Navigator
from routing import (
    payload_at_0x80011b8e4,
    payload_at_0x800c0030,
)
from menu_constants import hira_to_kata_arrow, hira_alt_up_index

from bad_addresses import (
    no_no_addrs,
    all_no_no_indices,
    hira_no_no_indices,
    kata_no_no_indices,
    latin_no_no_indices,
    hira_most_no_no_indices,
    hira_all_no_no_indices,
)

BIN_FILE = "saveMenuNoInitHira_j.bin"
BIN_DIR = os.path.join("..", "saveStates")
DEFAULT_BIN = os.path.join(BIN_DIR, BIN_FILE)


def generate_ace(mem, weighted):
    # have to start with the kata menu (hira and english can't make it to bifurcate the nop)
    graph_dict = {}
    graph_dict["hira"] = Graph.from_char_table(
        CharTable(mem, table_id=0),
        no_no_addrs=no_no_addrs,
        no_no_indices=hira_no_no_indices,
        weighted_graph=weighted,
    )
    graph_dict["kata"] = Graph.from_char_table(
        CharTable(mem, table_id=1),
        no_no_addrs=no_no_addrs,
        no_no_indices=kata_no_no_indices,
        weighted_graph=weighted,
    )
    graph_dict["latin"] = Graph.from_char_table(
        CharTable(mem, table_id=2),
        no_no_addrs=no_no_addrs,
        no_no_indices=latin_no_no_indices,
        weighted_graph=weighted,
    )

    # TODO(Lazy) could it be possible to rewrite memory to be able to navigate back from 0x0C? Have to load a new mem/bin dump here
    # mem_post = MemoryReader("../saveStates/hira_post_0x34.bin")
    graph_dict["hira_terminal"] = Graph.from_char_table(
        CharTable(mem, table_id=0),
        no_no_addrs=[0x000B7E44],
        no_no_indices=hira_most_no_no_indices,
        remove_terminal_subgraphs=False,
        weighted_graph=weighted,
    )

    graph_dict["kata_terminal"] = Graph.from_char_table(
        CharTable(mem, table_id=1),
        no_no_addrs=[0x000B7E44],
        no_no_indices=hira_most_no_no_indices,
        remove_terminal_subgraphs=False,
        weighted_graph=weighted,
    )

    graph_dict["latin_terminal"] = Graph.from_char_table(
        CharTable(mem, table_id=0),
        no_no_addrs=[0x000B7E44],
        no_no_indices=hira_most_no_no_indices,
        remove_terminal_subgraphs=False,
        weighted_graph=weighted,
    )

    nav = Navigator(graph_dict, "hira")
    payload_at_0x80011b8e4(nav)
    #payload_at_0x800c0030(nav)
    print(nav.input_tracker.gen_debug_string(metadata_required=True))
    print('\n')
    print(nav.gen_tas(True))

    # TODO(Lazy) expose visualization options
    # used_edges = nav.input_tracker.get_used_edges()
    # print(graph_dict)
    # print(used_edges)
    # graph_infos = visualizer.gen_graph_infos(graph_dict, used_edges)
    # visualizer.visualize(graph_infos, visualizer.CursorLocation("hira", 61), show=True, save=True)
    # cursor_locs = nav.input_tracker.get_cursor_locations()
    # visualizer.visualize(graph_infos, cursor_locs[1], "test", save=True)
    # visualizer.gen_movement_gif(graph_infos, cursor_locs, "main_route_low_res")


# TODO(Lazy) move this to it's own file?
def debug_node(index: int, table: int, mem: MemoryReader):
    debug_graph = Graph.from_char_table(
        CharTable(mem, table_id=table, cursor_index=index),
        search_depth=4,
        weighted_graph=True,
    )
    debug_char_table = CharTable(
        mem,
        table_id=table,
        cursor_index=index,
        alt_up_movement=False,
    )

    get_move_addrs(debug_char_table, cursor_index=index)
    nodes = debug_graph.get_all_nodes()
    for node in nodes:
        if node.switch_case in [1, 2]:
            print(node)

def parse_args():
    parser = argparse.ArgumentParser()
    parser.add_argument(
        "--bin",
        "-b",
        type=str,
        default=DEFAULT_BIN,
        help="The location of the binary file used (relative to ../saveStates)", #TODO(Lazy) this should maybe be less hacky
    )
    parser.add_argument(
        "--weighted",
        "-w",
        action="store_true",
        help="Generate a weighted graph where multiple inputs cost exponentially more." \
            "Better suited for humans where fewer multiple directional inputs are desired." \
            "WARNING: If this is a new route, this will almost assuredly require debug work.",
    )

    ## debug args
    parser.add_argument(
        "--debug_index",
        "-dn",
        type=int,
        default=None,
        help="Prints out helpful information about a given index. If no --debug_table is specified 0/hira will be used",
    )
    parser.add_argument(
        "--debug_table",
        "-dt",
        type=int,
        default=0,
        help="Provides a way to specify which table to use when debugging an index. REQUIRES --debug_index (-dn)",
    )
    args = parser.parse_args()
    return args

def main():
    args = parse_args()

    mem = MemoryReader(args.bin)
    if args.debug_index is not None:
        debug_node(args.debug_index, args.debug_table, mem)
    else:
        generate_ace(mem, args.weighted)

if __name__ == "__main__":
    main()
tools/ace.py
lazycurler/CrashBashResearchACE
from charTable import CharTable
from memoryReader import MemoryReader
from charTable import get_move_addrs, get_move_datas


def addrs():
    one_mem = MemoryReader("../saveStates/coco_nom.bin")
    two_mem = MemoryReader("../saveStates/hardware.bin")

    #debug_graph = Graph.from_char_table(CharTable(debug_mem, table_id=0, cursor_index=96))#, search_depth=10)
    one_char_table = CharTable(one_mem, table_id=0, alt_up_movement=False)
    two_char_table = CharTable(two_mem, table_id=0, alt_up_movement=False)

    one_addrs = []
    two_addrs = []
    for index in range(-2500, 500):
        one_addrs.extend(get_move_addrs(one_char_table, index, False))
        two_addrs.extend(get_move_addrs(two_char_table, index, False))

    one_addrs = sorted(set(one_addrs))
    two_addrs = sorted(set(two_addrs))
    #for (one_addr, two_addr) in zip(one_addrs, two_addrs):
    #    #print(f"0x{one_addr:08X}", f"0x{one_addr:08X}")
    #    print(f"0x{one_addr[0]:08X}", f"0x{two_addr[0]:08X}", f"{one_addr[1]}", f"{two_addr[1]}")

    difference_result = set(one_addrs).symmetric_difference(set(two_addrs))
    addrs_difference_result = list(difference_result)

    #print("diff", len(addrs_difference_result))
    ones = list(set(one_addrs) - set(two_addrs))
    twos = list(set(two_addrs) - set(one_addrs))
    info = []
    for (ones, twos) in zip(ones, twos):
        one_info = f"1 | {ones[2]}) 0x{ones[0]:08X}", f"{ones[1]}"
        two_info = f"2 | {twos[2]}) 0x{twos[0]:08X}", f"{twos[1]}"
        info.append(one_info)
        info.append(two_info)
    info = sorted(info)
    for msg in info:
        print(msg)



def main():
    addrs()

if __name__ == "__main__":
    main()
tools/addr_diff.py
lazycurler/CrashBashResearchACE
import mips
from dataclasses import dataclass

PRIMARY_OPCODE_BITMASK = 0xFC000000
PRIMARY_OPCODE_START_BIT = 26
RS_BITMASK = 0x03E00000
RS_START_BIT = 21
RT_BITMASK = 0x001F0000
RT_START_BIT = 16
RD_BITMASK = 0x0000F800
RD_START_BIT = 11
SH_BITMASK = 0x000007C0
SH_START_BIT = 6
FUNC_BITMASK = 0x0000003E
FUNC_START_BIT = 0
IMM_BITMASK = 0x0000FFFF
IMM_START_BIT = 0
JUMP_ADDR_MASK = 0x03FFFFFF
JUMP_ADDR_START_BIT = 0

# TODO(Lazy) base class?

class RegisterEncoding():
    def __init__(self, word):
        self.op = (word & PRIMARY_OPCODE_BITMASK) >> PRIMARY_OPCODE_START_BIT
        self.rs = (word & RS_BITMASK) >> RS_START_BIT
        self.rd = (word & RD_BITMASK) >> RD_START_BIT
        self.rt = (word & RT_BITMASK) >> RT_START_BIT
        self.sh = (word & SH_BITMASK) >> SH_START_BIT
        self.func = (word & FUNC_BITMASK) >> FUNC_START_BIT

    def get_op(self):
        if self.op == 0x0: # "special" opcode that needs more decoding
            _op = mips.secondary_opcodes[self.func]
        else:
            _op = mips.opcodes[self.op]
        return _op

    def str_as_dst(self):
        _op = self.get_op()
        return f"{_op} {mips.registers[self.rd]}, {mips.registers[self.rs]}, {mips.registers[self.rt]}"

    def str_as_st(self):
        _op = self.get_op()
        return f"{_op} {mips.registers[self.rs]}, {mips.registers[self.rt]}"

    def str_as_d(self):
        _op = self.get_op()
        return f"{_op} {mips.registers[self.rd]}"

    def str_as_dts(self):
        _op = self.get_op()
        return f"{_op} {mips.registers[self.rd]}, {mips.registers[self.rt]}, {mips.registers[self.rs]}"

    def str_as_dth(self):
        _op = self.get_op()
        return f"{_op} {mips.registers[self.rd]}, {mips.registers[self.rt]}, {mips.registers[self.sh]}"

    def str_as_s(self):
        _op = self.get_op()
        return f"{_op} {mips.registers[self.rs]}"

    def str_as_generic(self):
        _op = self.get_op()
        return f"{_op} \
                rs: {mips.registers[self.rs]}, \
                rt: {mips.registers[self.rt]}, \
                rd: {mips.registers[self.rd]}, \
                sh: {mips.registers[self.sh]}, \
                func: {mips.registers[self.func]}"

    def __str__(self):
        _op = self.get_op()
        subtype = mips.register_subtype.get(_op, "")
        if subtype == "dst":
            asm_str = self.str_as_dst()
        elif subtype == "st":
            asm_str = self.str_as_st()
        elif subtype == "d":
            asm_str = self.str_as_d()
        elif subtype == "dts":
            asm_str = self.str_as_dts()
        elif subtype == "dth":
            asm_str = self.str_as_dth()
        elif subtype == "ds":
            asm_str = self.str_as_s()
        else:
            asm_str = "INVALID"#self.str_as_generic()
        return asm_str

class ImmediateEncoding():
    def __init__(self, word):
        self.op = (word & PRIMARY_OPCODE_BITMASK) >> PRIMARY_OPCODE_START_BIT
        self.rs = (word & RS_BITMASK) >> RS_START_BIT
        self.rt = (word & RT_BITMASK) >> RT_START_BIT
        self.imm = (word & IMM_BITMASK) >> IMM_START_BIT

    def get_op(self):
        return mips.opcodes.get(self.op, None)

    def str_as_tsi(self):
        _op = self.get_op()
        return f"{_op} {mips.registers[self.rt]}, {mips.registers[self.rs]}, 0x{self.imm:04X}"

    def str_as_ti(self):
        _op = self.get_op()
        return f"{_op} {mips.registers[self.rt]}, {mips.registers[self.imm]}"

    def str_as_tis(self):
        _op = self.get_op()
        return f"{_op} {mips.registers[self.rt]}, 0x{self.imm:04X}({mips.registers[self.rs]})"

    def str_as_generic(self):
        _op = self.get_op()
        return f"{_op} \
                rs: {mips.registers[self.rs]}, \
                rt: {mips.registers[self.rt]}, \
                imm: {mips.registers[self.imm]}"

    def __str__(self):
        _op = self.get_op()
        subtype = mips.immediate_subtype[_op]
        if subtype == "tsi":
            asm_str = self.str_as_tsi()
        elif subtype == "ti":
            asm_str = self.str_as_ti()
        elif subtype == "tis":
            asm_str = self.str_as_tis()
        else:
            asm_str = self.str_as_generic()
        return asm_str


class JumpEncoding():
    def __init__(self, word, pc=0x0):
        self.op = (word & PRIMARY_OPCODE_BITMASK) >> PRIMARY_OPCODE_START_BIT
        self.pc = pc
        self.op = (word & PRIMARY_OPCODE_BITMASK) >> PRIMARY_OPCODE_START_BIT
        self.addr = (word & JUMP_ADDR_MASK) >> JUMP_ADDR_START_BIT

    def __str__(self):
        _op = mips.opcodes[self.op]
        _addr = self.addr << 2
        _pc = self.pc & 0xF0000000
        return f"{_op} 0x{(_addr + _pc):08X}"


# TODO(Lazy) This class is likely a placeholder for a subfile since it's (so far) stateless
class Disassembler():
    #def decode_register(word: int):
    # don't care about coprocessor (or unaligned loads/stores) right now
    # TODO(Lazy) If you care about the coprocessor, open a PR
    DONT_CARE_STRS = ["cop", "lwc", "swc", "n/a", "lwl", "lwr", "swl", "swr"]

    @staticmethod
    def to_asm(word: int) -> str:
        asm_str = ""

        opcode = (word & PRIMARY_OPCODE_BITMASK) >> PRIMARY_OPCODE_START_BIT
        # TODO(Lazy) this should be safer
        opcode_str = mips.opcodes[opcode]

        asm_str = "n/a"
        skip = False
        for dc in Disassembler.DONT_CARE_STRS:
            if dc in opcode_str:
                skip = True
        if not skip:
            encoding_type = mips.encoding_type[opcode_str]
        else:
            encoding_type = "n/a"

        #if encoding_type != "i":
        #    return "n/a"

        if encoding_type == "j":
            # TODO(Lazy) what about not immediates
            asm_str = f"{JumpEncoding(word)}"
        elif encoding_type == "r":
            # TODO(Lazy) what about not immediates
            asm_str = f"{RegisterEncoding(word)}"
        elif encoding_type == "i":
            # TODO(Lazy) what about not immediates
            asm_str = f"{ImmediateEncoding(word)}"
        elif encoding_type == "special":
            # all "special" encodings are really just variants of register
            asm_str = f"{RegisterEncoding(word)}"
        else:
            #TODO(Lazy) throw error or otherwise complain
            pass
        return asm_str

def main():
    #print(Disassembler.to_asm(0x0c00a955)) # jal     FUN_8002a554
    #print(Disassembler.to_asm(0x10400025)) # beq     v0,zero,LAB_8007b498
    #print(Disassembler.to_asm(0x3c158005)) # _lui    s5,0x8005
    #print(Disassembler.to_asm(0x3413d0ff)) # ori     s3,zero,0xd0ff
    #print(Disassembler.to_asm(0x241200ff)) # li      s2,0xff
    #print(Disassembler.to_asm(0x00481021)) # addu    v0,v0,t0

    #print(Disassembler.to_asm(0x00000001))
    #print(Disassembler.to_asm(0x02000000))
    #print(Disassembler.to_asm(0x20000000))
    #print(Disassembler.to_asm(0x3B000000))
    # TODO(Lazy) I should at least connect this to the opcode finder...
    #ops = [0x00, 0x03, 0x0C, 0x11, 0x20, 0x31, 0x32, 0x33, 0x34, 0x36, 0x37, 0x38, 0x39, 0x41, 0x42, 0x43, 0x44, 0x45, 0x46, 0x47, 0x48, 0x49, 0x4A, 0x4B, 0x4C, 0x4D, 0x4E, 0x4F, 0x50, 0x51, 0x52, 0x53, 0x54, 0x55, 0x56, 0x57, 0x58, 0x59, 0x5A, 0x6F, 0x80, 0x81, 0x82, 0x83, 0x84, 0x85, 0x86, 0x87, 0x88, 0x89, 0x8A, 0x8B, 0x8C, 0x8D, 0x8E, 0x8F, 0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97, 0x98, 0x99, 0x9A, 0x9B, 0x9C, 0x9D, 0x9E, 0x9F, 0xA0, 0xA1, 0xA2, 0xA3, 0xA4, 0xA5, 0xA6, 0xA7, 0xA8, 0xA9, 0xAA, 0xAB, 0xAC, 0xAD, 0xAE, 0xAF, 0xB0, 0xB1, 0xB3, 0xB4, 0xB5, 0xB6, 0xB7, 0xB8, 0xB9, 0xBA, 0xBB, 0xBD, 0xBE, 0xBF, 0xC0, 0xC1, 0xC2, 0xC3, 0xC4, 0xC5, 0xC6, 0xC7, 0xC8, 0xC9, 0xCA, 0xCB, 0xCC, 0xCD, 0xCE, 0xCF, 0xD0, 0xD1, 0xD2, 0xD3, 0xD4, 0xD5, 0xD6, 0xD7, 0xD8, 0xD9, 0xDA, 0xDB, 0xDC, 0xDD, 0xDE, 0xDF, 0xE0, 0xE1, 0xE2, 0xE3, 0xE4, 0xE5, 0xE6, 0xE7, 0xE8, 0xE9, 0xEA, 0xEB, 0xEC, 0xEF, 0xF0, 0xF1, 0xF2, 0xF3, 0xF4, 0xF5, 0xF6, 0xF7, 0xF8,]
    #ops = [0x00, 0x03, 0x20, 0x31, 0x32, 0x33, 0x34, 0x36, 0x37, 0x38, 0x39, 0x41, 0x42, 0x43, 0x44, 0x45, 0x46, 0x47, 0x48, 0x49, 0x4A, 0x4B, 0x4C, 0x4D, 0x4E, 0x4F, 0x50, 0x51, 0x52, 0x53, 0x54, 0x55, 0x56, 0x57, 0x58, 0x59, 0x5A, 0x6F, 0x80, 0x81, 0x82, 0x83, 0x84, 0x85, 0x86, 0x87, 0x88, 0x89, 0x8A, 0x8B, 0x8C, 0x8D, 0x8E, 0x8F, 0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97, 0x98, 0x99, 0x9A, 0x9B, 0x9C, 0x9D, 0x9E, 0x9F, 0xA0, 0xA1, 0xA2, 0xA3, 0xA4, 0xA5, 0xA6, 0xA7, 0xA8, 0xA9, 0xAA, 0xAB, 0xAC, 0xAD, 0xAE, 0xAF, 0xB0, 0xB1, 0xB3, 0xB4, 0xB5, 0xB6, 0xB7, 0xB8, 0xB9, 0xBA, 0xBB, 0xBD, 0xBE, 0xBF, 0xC0, 0xC1, 0xC2, 0xC3, 0xC4, 0xC5, 0xC6, 0xC7, 0xC8, 0xC9, 0xCA, 0xCB, 0xCC, 0xCD, 0xCE, 0xCF, 0xD0, 0xD1, 0xD2, 0xD3, 0xD4, 0xD5, 0xD6, 0xD7, 0xD8, 0xD9, 0xDA, 0xDB, 0xDC, 0xDD, 0xDE, 0xDF, 0xE0, 0xE1, 0xE2, 0xE3, 0xE4, 0xE5, 0xE6, 0xE7, 0xE8, 0xE9, 0xEA, 0xEB, 0xEC, 0xEF, 0xF0, 0xF1, 0xF2, 0xF3, 0xF4, 0xF5, 0xF6, 0xF7, 0xF8,]
    #ops = [ 0x00, 0x03, 0x11, 0x20, 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39, 0x41, 0x42, 0x43, 0x44, 0x45, 0x46, 0x47, 0x48, 0x49, 0x4A, 0x4B, 0x4C, 0x4D, 0x4E, 0x4F, 0x50, 0x51, 0x52, 0x53, 0x54, 0x55, 0x56, 0x57, 0x58, 0x59, 0x5A, 0x6F, 0x80, 0x81, 0x82, 0x83, 0x84, 0x85, 0x86, 0x87, 0x88, 0x8A, 0x8B, 0x8C, 0x8D, 0x8E, 0x8F, 0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97, 0x98, 0x99, 0x9A, 0x9B, 0x9C, 0x9D, 0x9E, 0x9F, 0xA0, 0xA1, 0xA2, 0xA3, 0xA4, 0xA5, 0xA6, 0xA7, 0xA8, 0xA9, 0xAA, 0xAB, 0xAC, 0xAD, 0xAE, 0xAF, 0xB0, 0xB1, 0xB3, 0xB4, 0xB5, 0xB6, 0xB7, 0xB8, 0xB9, 0xBA, 0xBB, 0xBD, 0xBE, 0xBF, 0xC0, 0xC1, 0xC2, 0xC3, 0xC4, 0xC5, 0xC6, 0xC7, 0xC8, 0xC9, 0xCA, 0xCB, 0xCC, 0xCD, 0xCE, 0xCF, 0xD0, 0xD1, 0xD2, 0xD3, 0xD4, 0xD5, 0xD6, 0xD7, 0xD8, 0xD9, 0xDA, 0xDB, 0xDC, 0xDD, 0xDE, 0xDF, 0xE0, 0xE1, 0xE2, 0xE3, 0xE4, 0xE5, 0xE6, 0xE7, 0xE8, 0xE9, 0xEA, 0xEB, 0xEC, 0xEF, 0xF0, 0xF1, 0xF2, 0xF3, 0xF4, 0xF5, 0xF6, 0xF7, 0xF8]
    #ops = [ 0x00, 0x03, 0x11, 0x20, 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39, 0x41, 0x42, 0x43, 0x44, 0x45, 0x46, 0x47, 0x48, 0x49, 0x4A, 0x4B, 0x4C, 0x4D, 0x4E, 0x4F, 0x50, 0x51, 0x52, 0x53, 0x54, 0x55, 0x56, 0x57, 0x58, 0x59, 0x5A, 0x6F, 0x80, 0x81, 0x82, 0x83, 0x84, 0x85, 0x86, 0x87, 0x88, 0x8A, 0x8B, 0x8D, 0x8E, 0x8F, 0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97, 0x98, 0x99, 0x9B, 0x9C, 0x9D, 0x9E, 0x9F, 0xA0, 0xA1, 0xA2, 0xA3, 0xA4, 0xA5, 0xA6, 0xA7, 0xA8, 0xA9, 0xAA, 0xAB, 0xAC, 0xAD, 0xAE, 0xAF, 0xB0, 0xB1, 0xB3, 0xB4, 0xB5, 0xB6, 0xB7, 0xB8, 0xB9, 0xBA, 0xBB, 0xBD, 0xBE, 0xBF, 0xC0, 0xC1, 0xC2, 0xC3, 0xC4, 0xC5, 0xC6, 0xC7, 0xC8, 0xC9, 0xCA, 0xCB, 0xCC, 0xCD, 0xCE, 0xCF, 0xD0, 0xD1, 0xD2, 0xD3, 0xD4, 0xD5, 0xD6, 0xD7, 0xD8, 0xD9, 0xDA, 0xDB, 0xDC, 0xDD, 0xDE, 0xDF, 0xE0, 0xE1, 0xE2, 0xE3, 0xE4, 0xE5, 0xE6, 0xE7, 0xE8, 0xE9, 0xEA, 0xEB, 0xEC, 0xEF, 0xF0, 0xF1, 0xF2, 0xF3, 0xF4, 0xF5, 0xF6, 0xF7, 0xF8]
    ops = [0x00, 0x03, 0x11, 0x20, 0x30, 0x31, 0x33, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39, 0x41, 0x42, 0x43, 0x44, 0x45, 0x46, 0x47, 0x48, 0x49, 0x4A, 0x4B, 0x4C, 0x4D, 0x4E, 0x4F, 0x50, 0x51, 0x52, 0x53, 0x54, 0x55, 0x56, 0x57, 0x58, 0x59, 0x5A, 0x6F, 0x80, 0x81, 0x82, 0x83, 0x84, 0x85, 0x86, 0x87, 0x88, 0x8A, 0x8B, 0x8D, 0x8F, 0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97, 0x98, 0x99, 0x9B, 0x9C, 0x9D, 0x9E, 0x9F, 0xA0, 0xA1, 0xA2, 0xA3, 0xA4, 0xA5, 0xA6, 0xA7, 0xA8, 0xA9, 0xAA, 0xAB, 0xAC, 0xAD, 0xAE, 0xAF, 0xB0, 0xB1, 0xB3, 0xB4, 0xB5, 0xB6, 0xB7, 0xB8, 0xB9, 0xBA, 0xBB, 0xBD, 0xBE, 0xC0, 0xC1, 0xC2, 0xC3, 0xC4, 0xC5, 0xC6, 0xC7, 0xC8, 0xC9, 0xCA, 0xCB, 0xCC, 0xCD, 0xCE, 0xCF, 0xD0, 0xD1, 0xD2, 0xD3, 0xD4, 0xD5, 0xD6, 0xD7, 0xD8, 0xD9, 0xDA, 0xDB, 0xDC, 0xDD, 0xDE, 0xDF, 0xE0, 0xE1, 0xE3, 0xE4, 0xE5, 0xE6, 0xE7, 0xE8, 0xE9, 0xEA, 0xEB, 0xEC, 0xEF, 0xF0, 0xF1, 0xF2, 0xF3, 0xF4, 0xF5, 0xF6, 0xF7, 0xF8]
    for op in ops:
    #for op in [0x00, 0x03]:
        for b1 in ops:
            #op_str = f"{hex(op)} -> {Disassembler.to_asm(op << 24 | thing << b1)}"
            #word = op << 24 | b1
            word = op << 24 | b1 << 16
            op_str = f"0x{word:08X} -> {Disassembler.to_asm(word)}"
            #if "sll" in op_str:
            #    print(op_str)
            #if "n/a" not in op_str:
            #    print(op_str)
            if "lw" in op_str or "xor" in op_str or "add" in op_str or "sw" in op_str:
                print(op_str)
            #for b2 in ops:
            #    for b3 in ops:
            #        word = op << 24 | b1 << 16 | b2 << 8 | b3
            #        op_str = f"0x{word:08X} -> {Disassembler.to_asm(word)}"
            #        if "n/a" not in op_str:
            #            print(op_str)
            #        #if "add" in op_str and ", gp" in op_str:
            #        #if "addi" in op_str:
            #        #    print(op_str)


if __name__ == "__main__":
    main()
tools/asm.py
lazycurler/CrashBashResearchACE
no_no_addrs = [
    0x000B7EE4, # alt up movement
    0X000B7E44, # uncontrollable left movement
]

# TODO(Lazy) This list assume bifurcated nops
# Finding the actual problem adders and moving them into no_no_addrs would be best
all_no_no_indices = [
    -2462,
    -2423,
    -2422,
    -2421,
    -2420,
    -2419,
    -2418,
    -2417,
    -2416,
    -2415,
    -2414,
    -2413,
    -2412,
    -2411,
    -2410,
    -2409,
    -2408,
    -2407,
    -2406,
    -2405,
    -2404,
    -2403,
    -2402,
    -2401,
    -2400,
    -2399,
    -2398,
    -2397,
    -2396,
    -2395,
    -2394,
    -2393,
    -2392,
    -2391,
    -2390,
    -2389,
    -2388,
    -2387,
    -2386,
    -2385,
    -2384,
    -2383,
    -2382,
    -2381,
    -2380,
    -2379,
    -2378,
    -2377,
    -2376,
    -2375,
    -2374,
    -2373,
    -2372,
    -2371,
    -2370,
    -2369,
    -2368,
    -2367,
    -2366,
    -2365,
    -2364,
    -2363,
    -2362,
    -2361,
    -2360,
    -2359,
    -2358,
    -2357,
    -2356,
    -2355,
    -2354,
    -2353,
    -2352,
    -2351,
    -2350,
    -2349,
    -2348,
    -2347,
    -2346,
    -2345,
    -2344,
    -2343,
    -2342,
    -2341,
    -2340,
    -2339,
    -2338,
    -2337,
    -2336,
    -2335,
    -2334,
    -2333,
    -2332,
    -2331,
    -2330,
    -2329,
    -2328,
    -2327,
    -2326,
    -2325,
    -2324,
    -2323,
    -2322,
    -2321,
    -2320,
    -2319,
    -2318,
    -2317,
    -2316,
    -2315,
    -2314,
    -2313,
    -2312,
    -2311,
    -2310,
    -2309,
    -2308,
    -2307,
    -2306,
    -2305,
    -2304,
    -2303,
    -2302,
    -2301,
    -2300,
    -2299,
    -2298,
    -2297,
    -2296,
    -2295,
    -2294,
    -2293,
    -2292,
    -2291,
    -2290,
    -2289,
    -2288,
    -2287,
    -2286,
    -2285,
    -2284,
    -2283,
    -2282,
    -2281,
    -2280,
    -2279,
    -2278,
    -2277,
    -2276,
    -2275,
    -2274,
    -2273,
    -2272,
    -2271,
    -2270,
    -2269,
    -2268,
    -2267,
    -2266,
    -2265,
    -2264,
    -2263,
    -2262,
    -2261,
    -2260,
    -2259,
    -2258,
    -2257,
    -2256,
    -2255,
    -2254,
    -2253,
    -2252,
    -2251,
    -2250,
    -2249,
    -2248,
    -2247,
    -2246,
    -2245,
    -2244,
    -2243,
    -2242,
    -2241,
    -2240,
    -2239,
    -2238,
    -2237,
    -2236,
    -2235,
    -2234,
    -2233,
    -2232,
    -2231,
    -2230,
    -2229,
    -2228,
    -2227,
    -2226,
    -2225,
    -2224,
    -2223,
    -2222,
    -2221,
    -2220,
    -2219,
    -2218,
    -2217,
    -2216,
    -2215,
    -2214,
    -2213,
    -2212,
    -2211,
    -2210,
    -2209,
    -2208,
    -2207,
    -2206,
    -2205,
    -2204,
    -2203,
    -2202,
    -2201,
    -2200,
    -2199,
    -2198,
    -2197,
    -2196,
    -2195,
    -2194,
    -2193,
    -2192,
    -2191,
    -2190,
    -2189,
    -2188,
    -2187,
    -2186,
    -2185,
    -2184,
    -2183,
    -2182,
    -2181,
    -2180,
    -2179,
    -2178,
    -2177,
    -2176,
    -2175,
    -2174,
    -2173,
    -2172,
    -2171,
    -2170,
    -2169,
    -2168,
    -2167,
    -2166,
    -2165,
    -2164,
    -2163,
    -2162,
    -2161,
    -2160,
    -2159,
    -2158,
    -2157,
    -2156,
    -2155,
    -2154,
    -2153,
    -2152,
    -2151,
    -2150,
    -2149,
    -2148,
    -2147,
    -2146,
    -2145,
    -2144,
    -2143,
    -2142,
    -2141,
    -2140,
    -2139,
    -2138,
    -2137,
    -2136,
    -2135,
    -2134,
    -2133,
    -2132,
    -2131,
    -2130,
    -2129,
    -2128,
    -2127,
    -2126,
    -2125,
    -2124,
    -2123,
    -2122,
    -2121,
    -2120,
    -2119,
    -2118,
    -2117,
    -2116,
    -2115,
    -2114,
    -2113,
    -2107,
    -2102,
    -2101,
    -2100,
    -2099,
    -2098,
    -2097,
    -2096,
    -2095,
    -2013,
    -1672,
    -1666,
    -1658,
    -1634,
    -1578,
    -1527,
    -1525,
    -1434,
    -1402,
    -1385,
    -1366,
    -1358,
    -1355,
    -1335,
    -1326,
    -1319,
    -1317,
    -1306,
    -1300,
    -1265,
    -1221,
    -1210,
    -1198,
    -1195,
    -1141,
    -1137,
    -1125,
    -1065,
    -1064,
    -1054,
    -1047,
    -1045,
    -1032,
    -1005,
    -1004,
    -997,
    -996,
    -993,
    -981,
    -949,
    -943,
    -938,
    -719,
    -391,
    -372,
    -312,
    -309,
    -297,
    -261,
    -255,
    -248,
    -245,
    -242,
    -236,
    -235,
    -234,
    -232,
    -226,
    -222,
    -219,
    -218,
    -217,
    -214,
    -213,
    -212,
    -211,
    -208,
    -192,
    -189,
    -188,
    -185,
    -182,
    -180,
    -178,
    -168,
    -164,
    -162,
    -160,
    -158,
    -154,
    -151,
    -135,
    -117,
    -115,
    -111,
    -108,
    -107,
    -104,
    -84,
    -62,
    335,
    336,
    337,
    341,
    344,
    346,
    347,
    353,
    354,
    355,
    357,
    358,
    359,
    363,
    366,
    367,
    369,
    370,
    372,
    373,
    453,
    468,
]


hira_no_no_indices = [
    -1,  # destroys the linked list that displays the letter and runs the code
    #26,  # liable to have their movement information screwed up by a needed 0x30 byte (could be worked around in the future)
    #34,  # liable to have their movement information screwed up
    #64,  # liable to have their movement information screwed up
    #68,  # this is also the exit? # liable to have their movement information screwed up
    #74,  # liable to have their movement information screwed up
    #94,  # liable to have their movement information screwed up


    109, # breaks payload execution?
    110, # has it's movement info broken on the way to 0x38
    25, # breaks linked list/payload execution
    26, # -16 screws up its movement
    -126, # -33 screw up its movement
    84, # breaks payload execution since characters aren't rendered
    59, # breaks linked list/payload execution
    -14, # 47 has its movement screwed up
    -4, # breaks movement for 154
    -9, # breaks movement for 104
    -13, # breaks movement for 64
    -22, # screws up movement for 94

    -39, # breaks kata -265
    -27, # breaks kata -145

    74, # inserting (selecting with "o") at -12 breaks movement at 74

    #10,# TODO(Lazy) why does this appear to break linked list? It should be fine

    #154, # ?
    #-157, # missed terminal subgraph?
    #-126, # ?

    -109, # breaks credits, kinda?
]
hira_no_no_indices.extend(all_no_no_indices)

kata_no_no_indices = [
     25, # ?
    -43, # ?
    -69, # ?
     59, # breaks LL
    -80, # causes the first 0x30 bytes to be rewritten on insert (may want to look into this later...)
    -85, # causes frame drops in Bizhawk?

    -105, # breaks inserts?
    -106, # breaks inserts?
]
kata_no_no_indices.extend(all_no_no_indices)

latin_no_no_indices = [
        26,  # liable to have their movement information screwed up
        36,  # liable to have their movement information screwed up
        68,  # liable to have their movement information screwed up
        152,  # ?
        153,  # ?

        25, # destroys the linked list that displays the letters and runs the code
        67, # destroys something that causes the code not to be run

        182, # noops out own code ?

        -284,
        -1071,

        # testing to avoid credits crash
        #-114,
        #-115,
        #-116,
        #-34,
        #-31,
]
latin_no_no_indices.extend(all_no_no_indices)

hira_most_no_no_indices = [-1, -109]
hira_most_no_no_indices.extend(all_no_no_indices)

hira_all_no_no_indices = []
hira_all_no_no_indices.extend(all_no_no_indices)
tools/bad_addresses.py
lazycurler/CrashBashResearchACE
from ctypes import c_int, c_ubyte
from nodeInfo import NodeInfo
from typing import List

CURSOR_INDEX_ADDR=0xc11d4
CUR_CHAR_TABLE=0xc11d8
CURSOR_TABLE_ADDR=0xbb724
CHAR_TABLE_PTR_ADDR=0xbb398
CHAR_INFO_LUT=0x5c670

# helpers for CharTable
def add32BitNumbers(a, b):
    res = a + b
    if res > 2**32:
        res = res - 2^32
    return res

def lShift32BitNumber(num, amount):
    res = num * (2**amount)
    if res > 2**32:
        res = res - 2**32
    return res

# interface for accessing various bytes/words of the character table(s) both in and out of "bounds"
class CharTable():
    def __init__(self, mem, table_id=0, cursor_index=0, alt_up_movement=False):
        self.mem = mem
        self.table_id = table_id
        self.cursor_index = cursor_index
        self.alt_up_movement = alt_up_movement

    # gets the current table index - aka charTableAddr + cursorLoc
    # this also takes the table id into account
    def get_table_index(self, offset=0):
        char_table_addr = self.mem.r32u(CHAR_TABLE_PTR_ADDR + self.table_id*5*4)
        return char_table_addr + (self.cursor_index * 0x10 + offset)

    # for determining what the result of the switch case might be (if "X" or "O" was pressed)
    def get_switch_case(self):
        addr = self.get_table_index(8)
        return self.mem.r16u(addr)

    # check for dakuten/handakuten case (as seen in the insertCharacter function)
    # TODO(Lazy) verify this is correct
    def is_modifier_char(self, input_char=None):
        if input_char is None:
            input_char = self.get_insert_byte()
        input_char = int(c_ubyte(input_char).value)
        always_zero_maybe = 0
        #return ((self.mem.r8u(CHAR_INFO_LUT + input_char + 0x100*self.table_id) & 2) != 0)
        return ((self.mem.r8u(CHAR_INFO_LUT + input_char + 0x100*always_zero_maybe) & 2) != 0)

    # assuming the 0th case (cursor over a regular character) what byte would be added to the save name str
    def get_insert_byte(self):
        ptr = self.get_table_index(4)
        addr = self.mem.r32u(ptr)
        #print(f"ptr: 0x{ptr:08X}, addr: 0x{addr:08X}")
        return self.mem.r8u(addr)

    # TODO(Lazy) should alt be an option or should this return a tuple?
    def get_nop_addr(self, alt=False):
        if alt:
            index=self.cursor_index
            offset=lShift32BitNumber(index, 2)
            offset=add32BitNumbers(offset, index)
            offset=lShift32BitNumber(offset, 2)
            #offset=add32BitNumbers(offset, index) this is the line that gets NOP'd out
            offset=lShift32BitNumber(offset, 3)
        else:
            offset = self.cursor_index*0xa8
        return add32BitNumbers(CURSOR_TABLE_ADDR, offset)

    def get_node_info(self, vert_id):
        insert_byte = 0
        modifier = False
        hazard = True
        try:
            # it's possible for this check to access invalid memory
            insert_byte = self.get_insert_byte()
            modifier = self.is_modifier_char()
            hazard = False # if the lookup didn't cause an exception then no problem/hazard
        except IndexError:
            # hacky, but this isn't production :p
            pass

        return NodeInfo(vert_id,
                        self.get_nop_addr(),
                        self.get_nop_addr(alt=True),
                        modifier,
                        self.cursor_index,
                        insert_byte,
                        self.get_switch_case(),
                        hazard,
                        self.is_dead_end())

    def get_left_move_index(self):
        addr = self.get_table_index(0xa)
        #print(hex(addr))
        return self.mem.r8s(addr)

    def get_right_move_index(self):
        addr = self.get_table_index(0xb)
        return self.mem.r8s(addr)

    def get_up_move_index(self, combo_move=False):
        # multi_move True when this up is pressed in combo with another button
        if self.alt_up_movement:
            if combo_move:
                return -1
            else:
                return add32BitNumbers(self.cursor_index, self.cursor_index)
        addr = self.get_table_index(0xc)
        #print(hex(addr))
        return self.mem.r8s(addr)

    def get_down_move_index(self):
        addr = self.get_table_index(0xd)
        return self.mem.r8s(addr)

    def move_l(self):
        self.cursor_index += self.get_left_move_index()

    def move_r(self):
        self.cursor_index += self.get_right_move_index()

    def move_u(self):
        if self.alt_up_movement:
            self.cursor_index = self.get_up_move_index()
        else:
            self.cursor_index += self.get_up_move_index()

    def move_d(self):
        self.cursor_index += self.get_down_move_index()

    def move_lu(self):
        self.cursor_index += self.get_left_move_index() + self.get_up_move_index(combo_move=True)

    def move_ld(self):
        self.cursor_index += self.get_left_move_index() + self.get_down_move_index()

    def move_ru(self):
        self.cursor_index += self.get_right_move_index() + self.get_up_move_index(combo_move=True)

    def move_rd(self):
        self.cursor_index += self.get_right_move_index() + self.get_down_move_index()

    def move_lr(self):
        self.cursor_index += self.get_left_move_index() + self.get_right_move_index()

    def move_ud(self):
        # not a combo move since it's first and thus the register isn't stale (in the same way)
        self.cursor_index += self.get_up_move_index() + self.get_down_move_index()

    def move_lru(self):
        self.cursor_index += self.get_left_move_index() + self.get_right_move_index() + self.get_up_move_index(combo_move=True)

    def move_rud(self):
        self.cursor_index += self.get_right_move_index() + self.get_up_move_index(combo_move=True) + self.get_down_move_index()

    def move_lrd(self):
        self.cursor_index += self.get_left_move_index() + self.get_right_move_index() + self.get_down_move_index()

    def move_lud(self):
        self.cursor_index += self.get_left_move_index() + self.get_up_move_index(combo_move=True) + self.get_down_move_index()

    def move_lrud(self):
        self.cursor_index += self.get_left_move_index() + self.get_right_move_index() + self.get_up_move_index(combo_move=True) + self.get_down_move_index()

    def get_move_options(self):
        return [("L", self.move_l),
                ("R", self.move_r),
                ("U", self.move_u),
                ("D", self.move_d),
                ("LU", self.move_lu),
                ("LD", self.move_ld),
                ("RU", self.move_ru),
                ("RD", self.move_rd),
                ("LR", self.move_lr),
                ("UD", self.move_ud),
                ("LRU", self.move_lru),
                ("RUD", self.move_rud),
                ("LRD", self.move_lrd),
                ("LUD", self.move_lud),
                ("LRUD", self.move_lrud),
                ]

    def is_dead_end(self):
        dead_end = True
        starting_index = self.cursor_index
        for _, move_func in self.get_move_options():
            old_index = self.cursor_index
            move_func()
            if self.cursor_index != old_index:
                dead_end = False
                break
        self.cursor_index = starting_index
        return dead_end

# below are some older functions used for testing/debugging

def get_base_opcodes(mem, debug=False):
    # technically this will include a few characters that aren't selectable, but I'll live with that for now
    ops = []
    for table, size in [(0, 63), (1, 62), (2, 36)]:
        char_table_addr = mem.r32u(CHAR_TABLE_PTR_ADDR + table*5*4)
        for cursor_index in range(size):
            ptr = char_table_addr + cursor_index * 0x10 + 4
            addr = mem.r32u(ptr)
            char = mem.r8u(addr)
            #print(f"{table} | {cursor_index:<2} | 0x{hex(char)[2:4].zfill(2)} | {hex(addr)}")
            ops.append(char)
    ops.sort()
    ops = [*set(ops)]
    if debug:
        for op in ops:
            print(hex(op))
    return ops

def get_routes(char_table,
               seen=None,
               path="",
               search_depth=3,
               neg_limit=c_int(0xffffee26).value,
               pos_limit=c_int(0x7fffffff).value):
    if seen is None:
        seen = {}
    if search_depth <= 0:
        return {char_table.cursor_index: path}

    for move_dir, move_func in char_table.get_move_options():
        old_index = char_table.cursor_index
        move_func()
        cur_index = char_table.cursor_index
        cur_path = f"{path}->{move_dir}"
        if cur_index not in seen and (neg_limit <= cur_index <= pos_limit):
            seen[cur_index] = cur_path
            seen.update(get_routes(char_table, seen, cur_path, search_depth-1))
        char_table.cursor_index = old_index

    return seen

def get_move_addrs(char_table: CharTable, cursor_index=None, debug=True) -> List[int]:
    old_cursor_index = None
    if cursor_index is not None:
        old_cursor_index = char_table.cursor_index
        char_table.cursor_index = cursor_index

    l = char_table.get_table_index(0xa)
    r = char_table.get_table_index(0xb)
    u = char_table.get_table_index(0xc)
    d = char_table.get_table_index(0xd)
    l_d = char_table.get_left_move_index() + cursor_index
    r_d = char_table.get_right_move_index() + cursor_index
    u_d = char_table.get_up_move_index() + cursor_index
    d_d = char_table.get_down_move_index() + cursor_index
    if debug:
        print("l", hex(l))
        print("u", hex(u))
        print("r", hex(r))
        print("d", hex(d))

    if old_cursor_index is not None:
        char_table.cursor_index = old_cursor_index

    return [(l, l_d, cursor_index), (r, r_d, cursor_index), (u, u_d, cursor_index), (d, d_d, cursor_index)]

def get_move_datas(char_table: CharTable, cursor_index=None, debug=True) -> List[int]:
    old_cursor_index = None
    if cursor_index is not None:
        old_cursor_index = char_table.cursor_index
        char_table.cursor_index = cursor_index

    l = char_table.get_left_move_index()
    r = char_table.get_right_move_index()
    u = char_table.get_up_move_index()
    d = char_table.get_down_move_index()
    if debug:
        print("l", hex(l))
        print("u", hex(u))
        print("r", hex(r))
        print("d", hex(d))

    if old_cursor_index is not None:
        char_table.cursor_index = old_cursor_index

    return [l, r, u, d]
tools/charTable.py
lazycurler/CrashBashResearchACE
from ctypes import c_int
from collections import deque
from dataclasses import dataclass
from nodeInfo import NodeInfo
from typing import List, Tuple
from subgraphTools import remove_all_terminal_subgraphs
import igraph as ig
import matplotlib.pyplot as plt
import sys
import struct
sys.setrecursionlimit(10000)

@dataclass
class Move:
    src_index: int # current cursor index before the move
    dst_index: int # future cursor index after the move
    direction: str # string representing the inputs required for this move

class Graph:
    def __init__(self, graph=None):
        if graph is None:
            self.graph = ig.Graph(directed=True)
        else:
            self.graph = graph

    @classmethod
    def from_char_table(cls, char_table, no_no_addrs=[], no_no_indices=[], search_depth=9999, remove_terminal_subgraphs=True, weighted_graph=False):
        verts, edges = Graph.gen_graph_data(char_table, search_depth=search_depth, no_no_addrs=no_no_addrs, no_no_indices=no_no_indices)
        return cls.from_verts_and_edges(verts, edges, remove_terminal_subgraphs, use_weights=weighted_graph)

    @classmethod
    def from_verts_and_edges(cls, verts, edges, remove_terminal_subgraphs=True, use_weights=False):
        actual_edges, directions, weights, = [], [], []
        for src, dst, direction in edges:
            weight = 1
            if use_weights:
                weight = 10**(len(direction)-1) # logarithmically increase weights - one button 1, two 10, etc
            weights.append(weight)
            #actual_edges.append((src.vert, dst.vert, weight))
            actual_edges.append((src.vert, dst.vert))
            directions.append(direction)
            # TODO(Lazy) make weight choices an argument?

        num_verts = len(verts)
        graph = ig.Graph(num_verts, actual_edges, directed=True)
        names, nop_addrs, alt_nop_addrs, modifiers, inserted_bytes, cases, dead_ends, hazards = [], [], [], [], [], [], [], []
        for vert in verts:
            names.append(vert.cursor_index)
            nop_addrs.append(f"0x{vert.nop_addr:08X}")
            alt_nop_addrs.append(f"0x{vert.alt_nop_addr:08X}")
            modifiers.append(vert.is_modifier)
            inserted_bytes.append(f"0x{vert.byte:02X}")
            cases.append(vert.switch_case)
            hazards.append(vert.hazard)
            dead_ends.append(vert.dead_end)
        graph.vs["name"]  = names
        graph.vs["nop_addr"]  = nop_addrs
        graph.vs["alt_nop_addr"]  = alt_nop_addrs
        graph.vs["modifier"] = modifiers
        graph.vs["byte"] = inserted_bytes
        graph.vs["case"] = cases
        graph.vs["hazard"] = hazards
        graph.vs["dead_end"] = dead_ends
        graph.es["direction"] = directions
        graph.es["weight"] = weights
        # this prevents navigating to an area from which there is no return
        if remove_terminal_subgraphs:
            _ = remove_all_terminal_subgraphs(graph)
        return cls(graph)

    @staticmethod
    def gen_graph_data(char_table,
                       seen=None,
                       search_depth=3,
                       neg_limit=c_int(0xffffee26).value,
                       pos_limit=c_int(0x7fffffff).value,
                       no_no_addrs=[],
                       no_no_indices=[]):

        verts = []
        edges = []
        if seen is None:
            seen = {}
            first_node = char_table.get_node_info(0)
            seen[first_node.cursor_index] = first_node
            verts.append(first_node)
        if search_depth <= 0:
            return verts, edges

        for move_dir, move_func in char_table.get_move_options():
            old_node = seen[char_table.cursor_index]
            # try to move in a direction e.g. press left or press right, up, and down
            move_func()

            # verify the resulting location is within the allowable range
            #TODO(Lazy) more verbose way to ignore nodes/indices
            if neg_limit <= char_table.cursor_index <= pos_limit and char_table.cursor_index not in no_no_indices:
                # note the resulting location and store the information in the directed graph
                cur_index = char_table.cursor_index

                if cur_index > 500 or cur_index < -2400:
                    char_table.cursor_index = old_node.cursor_index
                    continue

                if cur_index not in seen:
                    # TODO(Lazy) this is super hacky...
                    try:
                        cur_node = char_table.get_node_info(len(seen))
                    except struct.error:
                        print(cur_index)
                        char_table.cursor_index = old_node.cursor_index
                        continue
                else:
                    cur_node = seen[cur_index]

                if cur_node.nop_addr in no_no_addrs or cur_node.alt_nop_addr in no_no_addrs:
                    char_table.cursor_index = old_node.cursor_index
                    continue

                edges.append((old_node, cur_node, move_dir))

                if cur_node.cursor_index not in seen:
                    verts.append(cur_node)
                    seen[cur_node.cursor_index] = cur_node
                    # continue with this depth first search
                    new_verts, new_edges = Graph.gen_graph_data(char_table,
                                                                seen,
                                                                search_depth-1,
                                                                no_no_addrs=no_no_addrs,
                                                                no_no_indices=no_no_indices)
                    verts += new_verts
                    edges += new_edges

            # restore the cursor position before trying to move in a different direction
            char_table.cursor_index = old_node.cursor_index

        return verts, edges

    @staticmethod
    def node_from_vert(vert: ig.Vertex) -> NodeInfo:
        return NodeInfo(vert.index,
                        vert["nop_addr"],
                        vert["alt_nop_addr"],
                        vert["modifier"],
                        vert["name"],
                        vert["byte"],
                        vert["case"],
                        vert["hazard"],
                        vert["dead_end"])

    def vert_from_vert_index(self, index: int) -> ig.Vertex:
        return self.graph.vs[index]

    def node_from_vert_index(self, index: int) -> NodeInfo:
        return self.node_from_vert(self.vert_from_vert_index(index))

    def add_vertex(self, node: NodeInfo):
        self.graph.add_vertex(name=str(node.cursor_index), byte=f"0x{node.byte:02X}", case=(node.switch_case))

    def add_edge(self, src: NodeInfo, dst: NodeInfo, dir):
        self.graph.add_edge(str(src.cursor_index), str(dst.cursor_index), dir=dir)

    # It really feels like I'm not doing things the "igraph" way...
    def vert_from_cursor_index(self, cursor_index: int):
        # getting the first vert from the vertex sequence is chill (the indices[0] part)
        # since there can only be one vertex for each cursor index
        return self.vert_from_vert_index(self.graph.vs.select(name_eq=cursor_index).indices[0])

    def vert_from_nop_addr(self, nop_addr: str):
        nop_addr.upper() # all letters in the hex string must be uppercase
        # similar to the cursor index variant, only one nop_addr is unique per node
        return self.vert_from_vert_index(self.graph.vs.select(nop_addr_eq=nop_addr).indices[0])

    def vert_from_alt_nop_addr(self, alt_nop_addr: str):
        alt_nop_addr.upper() # all letters in the hex string must be uppercase
        # similar to the cursor index variant, only one nop_addr is unique per node
        return self.vert_from_vert_index(self.graph.vs.select(alt_nop_addr_eq=alt_nop_addr).indices[0])

    def get_moves(self, start: ig.Vertex, finish: ig.Vertex, debug=False) -> List[Move]:
        edge_path = self.graph.get_shortest_path(start, to=finish, mode=ig.OUT, weights=self.graph.es["weight"], output="epath")
        directions = []
        for eid in edge_path:
            edge = self.graph.es[eid]
            source_vert = self.graph.vs[edge.source]
            target_vert = self.graph.vs[edge.target]
            direction = edge["direction"]
            directions.append(Move(src_index=source_vert['name'], direction=direction, dst_index=target_vert['name']))
            if debug:
                print(f"{direction:4} {target_vert['name']:6}  {target_vert['byte']}")

        #if debug:
        #    path = self.graph.get_shortest_path(start, to=finish, mode=ig.OUT, weights=self.graph.es["weight"], output="vpath")
        #    print(self.graph.vs[path[0]]["name"], self.graph.vs[path[0]]["byte"])
        #    for i in range(1, len(path)):
        #        print(directions[i-1], self.graph.vs[path[i]]["name"], self.graph.vs[path[i]]["byte"], self.graph.es[eid]["weight"])
        return directions

    def is_safe_to_insert(self, cursor_index, dead_ends_allowed=False):
        node = self.node_from_vert(self.vert_from_cursor_index(cursor_index))
        return (node.switch_case == 0 and not node.hazard and (dead_ends_allowed or not node.dead_end))

    def visualize(self, show=True, save=False):
        fix, ax = plt.subplots()

        # TODO(Lazy) option for this? useful for graph debugging
        #self.graph.vs["label"] = self.graph.vs["byte"] # use resulting inserted byte as a vertex label
        #self.graph.vs["label"] = self.graph.vs["name"] # use resulting inserted byte as a vertex label
        #self.graph.es["label"] = self.graph.es["direction"]

        # TODO(Lazy) This needs a once over before being exposed
        # Right now it's in an indeterminate state used for generating the graphs for the writeup
        visual_style = {}
        #visual_style["vertex_size"] = 0.4
        visual_style["vertex_size"] = 0.10
        #visual_style["vertex_label_size"] = 20
        visual_style["edge_width"] = 0.3
        visual_style["edge_arrow_size"] = 0.004
        #ig.plot(self.graph, target=ax, edge_label=self.graph.es["label"], **visual_style)
        #ig.plot(self.graph, target=ax, edge_label=self.graph.es["weight"], **visual_style)
        import random
        random.seed(52) # make sure the layout never changes
        layout = self.graph.layout("fruchterman_reingold")

        #TODO(Lazy) REMOVE DEBUG
        #text_style = {}
        #text_style["ha"] = "center"
        #text_style["va"] = "center"
        #text_style["multialignment"] = "left"
        #text_style["transform"] = plt.gcf().transFigure
        #text_style["fontsize"] = 24
        #ig.plot(self.graph, layout=layout, target=ax, **visual_style)
        #plt.title(f"Vertices: {len(self.graph.vs)}\n Edges: {len(self.graph.es)}", **text_style, y=0.90)
        #text_style["fontsize"] = 32
        #text_style["va"] = "top"
        #plt.suptitle("Hiragana - Fully Pruned", **text_style)

        if show:
            plt.show()

    # some nice info functions
    def get_all_opcodes(self, dead_ends_allowed=False):
        ops = []
        for vert in self.graph.vs:
            node = Graph.node_from_vert(vert)
            opcode = node.byte
            if node.switch_case == 0 and not node.hazard and (True if dead_ends_allowed else not node.dead_end):
                ops.append(opcode)

        # remove duplicates and sort
        ops = [*set(ops)]
        ops.sort()

        return ops

    def get_all_indices(self):
        indices = []
        for vert in self.graph.vs:
            node = Graph.node_from_vert(vert)
            indices.append(node.cursor_index)

        # remove duplicates and sort
        indices.sort()

        return indices


    def get_all_cases(self):
        cases = []
        for vert in self.graph.vs:
            node = Graph.node_from_vert(vert)
            cases.append(node.switch_case)

        # remove duplicates and sort
        cases.sort()

        return cases

    def get_all_byte_addrs(self, char_table):
        addrs = []
        for vert in self.graph.vs:
            node = Graph.node_from_vert(vert)
            try:
                addrs.append(char_table.mem.r32u(node.cursor_index))
            except:
                continue

        # remove duplicates and sort
        addrs.sort()

        return addrs

    # TODO(Lazy) this could be more generic... e.g. match a node instead of a byte
    # TODO(Lazy) there's probably a way to do this with igraph too :(
    def bfs_byte_search(self, byte, start_index, depth_limit, dead_ends_allowed=False) -> NodeInfo:
        # returns the NodeInfo of the closest node with that byte or None if not found
        closest_node = None
        start_vert = self.graph.vs.select(name_eq=start_index).indices[0]
        queue = deque([start_vert])
        seen = {start_vert: True}
        nodes_left_in_cur_depth = 1

        def _add_neighbors(index):
            nonlocal nodes_left_in_cur_depth, seen, depth_limit
            # still haven't found desired byte - add the nearest neighbors (not yet seen) to the queue
            neighbors = self.graph.neighbors(index, mode="out")
            for neighbor in neighbors:
                if neighbor not in seen:
                    seen[neighbor] = True
                    queue.append(neighbor)
            # check if depth limit has been reached and it's time to bail on this search
            if nodes_left_in_cur_depth <= 0:
                depth_limit -= 1
                nodes_left_in_cur_depth = len(queue)

        while len(queue) > 0:# and depth_limit >= 0:
            cur_vert_index = queue.popleft()
            cur_node = self.node_from_vert_index(cur_vert_index)
            nodes_left_in_cur_depth -= 1
            if cur_node.byte == byte and self.is_safe_to_insert(cur_node.cursor_index):
                # this is our desired byte
                closest_node = cur_node
                break
            else:
                #print("No good: ", cur_node, 'safe', self.is_safe_to_insert(cur_node.cursor_index))
                #print(cur_node.byte, cur_node.byte == byte, byte)
                _add_neighbors(cur_vert_index)
                if depth_limit < 0:
                    break

        #if self.debug:
        #if True:
        #    seen_nodes = [self.node_from_vert_index(index) for index in seen.keys()]
        #    seen_tuples = [(node.byte, node.cursor_index, self.is_safe_to_insert(node.cursor_index)) for node in seen_nodes]
        #    seen_tuples.sort()
        #    print("Just got done looking for: ", byte)
        #    for seen_tuple in seen_tuples:
        #        print("saw (index, byte): ", seen_tuple)

        return closest_node

    def get_closest_node_from_byte(self, byte, cur_index=0, depth_limit=999, dead_ends_allowed=False, debug=False) -> ig.Vertex:
        # get's the node that contains the requested byte
        # returns None if not found
        # TODO(Lazy) is this wrapper needed? should an error be thrown?
        if isinstance(byte, int):
            byte = f"0x{byte:02X}"
        node = self.bfs_byte_search(byte, cur_index, depth_limit, dead_ends_allowed)
        if node is not None:
            #if debug:
            #    print(node)
            return node
        else:
            return None

    # TODO(Lazy) this should probably be moved
    # TODO(Lazy) this could be done in a more graph forward way
    def get_all_nodes_from_byte(self, byte):
        if isinstance(byte, int):
            byte = f"0x{byte:02X}"
        nodes = []
        for vert in self.graph.vs:
            node = Graph.node_from_vert(vert)
            if node.switch_case == 0 and node.byte == byte:
                nodes.append(node)
        return nodes

    def get_all_nodes(self):
        nodes = []
        for vert in self.graph.vs:
            node = Graph.node_from_vert(vert)
            nodes.append(node)
        return nodes

    def pretty_print_weighted_graph(self):
        print("Vertices:")
        for vertex in self.graph.vs:
            print(f"{vertex.index}: {vertex['name']}, {vertex['byte']}")

        print("\nEdges:")
        for edge in self.graph.es:
            source = self.graph.vs[edge.source]['name']
            target = self.graph.vs[edge.target]['name']
            weight = edge['weight']
            print(f"{source} --({weight})--> {target}")

tools/graph.py
lazycurler/CrashBashResearchACE
import struct

CURSOR_INDEX_ADDR=0xc11d4
CUR_CHAR_TABLE=0xc11d8
CURSOR_TABLE_ADDR=0xbb724
CHAR_TABLE_PTR_ADDR=0xbb398
CHAR_INFO_LUT=0x5c670

# TODO(Lazy) Load Word Left? unaligned (really any load)

class MemoryReader():
    def __init__(self, bin_file):
        with open(bin_file, "rb") as dump:
            mem = dump.read()
        self.mem = mem

    @staticmethod
    def remap_addr(addr):
        # emulate the memory mirrors essentially mapping
        # 0x00000000, 0x80000000, and 0xA0000000 together
        # aka KUSEG, KSEG0, KSEG1
        top_nibble = addr >> 28
        if top_nibble == 0x8 or top_nibble == 0xA:
            addr = (addr & 0x0FFFFFFF)
        return addr

    @staticmethod
    def valid_addr(addr):
        addr = MemoryReader.remap_addr(addr)
        # this may not strictly be true, but this is the max size of ram dumps from bizhawk
        return addr <= 0x1FFFFC

    def r8u(self, addr):
        addr = self.remap_addr(addr)
        return struct.unpack('B', bytearray([self.mem[addr]]))[0]

    def r8s(self, addr):
        addr = self.remap_addr(addr)
        return struct.unpack('b', bytearray([self.mem[addr]]))[0]

    def r16u(self, addr):
        addr = self.remap_addr(addr)
        start, stop = addr, addr+2
        return struct.unpack('H', bytearray(self.mem[start:stop]))[0]

    def r16s(self, addr):
        addr = self.remap_addr(addr)
        start, stop = addr, addr+2
        return struct.unpack('h', bytearray(self.mem[start:stop]))[0]

    def r32u(self, addr):
        addr = self.remap_addr(addr)
        start, stop = addr, addr+4
        return struct.unpack('I', bytearray(self.mem[start:stop]))[0]

    def r32s(self, addr):
        addr = self.remap_addr(addr)
        start, stop = addr, addr+4
        return struct.unpack('i', bytearray(self.mem[start:stop]))[0]


def toHex(val, nbits=32):
    return f"0x{((val + (1 << nbits)) % (1 << nbits)):08X}"

# useful tools that didn't fit elsewhere so no live here
def find_address_within_range(mem: MemoryReader, desired_addr, start_addr):
    print("desired", hex(desired_addr))
    print("start", hex(start_addr))
    found = []
    desired_addr = MemoryReader.remap_addr(desired_addr)
    start_addr = MemoryReader.remap_addr(start_addr)
    min_start_addr = start_addr - 0x8000
    max_start_addr = start_addr + 0x7FFF
    min_data_addr = desired_addr - 0x8000
    max_data_addr = desired_addr + 0x7FFF
    for addr in range(min_start_addr, max_start_addr, 4):
        data = MemoryReader.remap_addr(mem.r32u(addr))
        if min_data_addr <= data <= max_data_addr:
            addr_offset = toHex(addr - start_addr)
            data_offset = toHex(data - desired_addr)
            print(f"{addr_offset}({toHex(start_addr)}) == {toHex(data)}")
            print(f"{data_offset}({toHex(data)}) == ?\n")
            addr |= 0x80000000
            found.append(addr)
    return found

def find_address_with_upper(mem: MemoryReader, desired_upper, start_addr):
    found = []
    desired_upper = MemoryReader.remap_addr(desired_upper)
    start_addr = MemoryReader.remap_addr(start_addr)
    min_start_addr = start_addr - 0x8000
    max_start_addr = start_addr + 0x7FFF
    for addr in range(min_start_addr, max_start_addr, 4):
        data = MemoryReader.remap_addr(mem.r32u(addr))
        #if MemoryReader.remap_addr(data) ^ MemoryReader.remap_addr(desired_upper) == 0:
        #    #print(toHex(min_start_addr), toHex(addr), toHex(max_start_addr), toHex(min_data_addr), toHex(data), toHex(max_data_addr), toHex((addr - start_addr)), toHex(data - desired_addr))
        #    addr |= 0x80000000
        #    found.append(addr)
        found.append((toHex(data), toHex(addr)))
    return found

tools/memoryReader.py
lazycurler/CrashBashResearchACE
hira_to_kata_arrow = 0x42
hira_to_latin_arrow = 0x41
kata_to_latin_arrow = 0x42
kata_to_hira_arrow = 0x41
latin_to_hira_arrow = 0x27
latin_to_kata_arrow = 0x26
kata_zero = -186
kata_space = 20 # -18, 20, -23, 46, -49, 51, 63
kata_hex_34 = -81
kata_hex_0c = -226
hana_hi = 0x12
handakuten_ee = 0x19
hira_exit = 0x44
kata_exit = 0x44
kata_insertable_ee = -305
hira_insertable_ee = -236
latin_insertable_ee = -194
hira_alt_up_index = -90
tools/menu_constants.py
lazycurler/CrashBashResearchACE
# source https://psx-spx.consoledev.net/cpuspecifications/
opcodes = {
    0x00: "special",
    0x01: "bcondz",
    0x02: "j",
    0x03: "jal",
    0x04: "beq",
    0x05: "bne",
    0x06: "blez",
    0x07: "bgtz",
    0x08: "addi",
    0x09: "addiu",
    0x0A: "slti",
    0x0B: "sltiu",
    0x0C: "andi",
    0x0D: "ori",
    0x0E: "xori",
    0x0F: "lui",
    0x10: "cop0",
    0x11: "cop1",
    0x12: "cop2",
    0x13: "cop3",
    0x14: "n/a",
    0x15: "n/a",
    0x16: "n/a",
    0x17: "n/a",
    0x18: "n/a",
    0x19: "n/a",
    0x1A: "n/a",
    0x1B: "n/a",
    0x1C: "n/a",
    0x1D: "n/a",
    0x1E: "n/a",
    0x1F: "n/a",
    0x20: "lb",
    0x21: "lh",
    0x22: "lwl",
    0x23: "lw",
    0x24: "lbu",
    0x25: "lhu",
    0x26: "lwr",
    0x27: "n/a",
    0x28: "sb",
    0x29: "sh",
    0x2A: "swl",
    0x2B: "sw",
    0x2C: "n/a",
    0x2D: "n/a",
    0x2E: "swr",
    0x2F: "n/a",
    0x30: "lwc0",
    0x31: "lwc1",
    0x32: "lwc2",
    0x33: "lwc3",
    0x34: "n/a",
    0x35: "n/a",
    0x36: "n/a",
    0x37: "n/a",
    0x38: "swc0",
    0x39: "swc1",
    0x3A: "swc2",
    0x3B: "swc3",
    0x3C: "n/a",
    0x3D: "n/a",
    0x3E: "n/a",
    0x3F: "n/a",
}

secondary_opcodes = {
    0x00: "sll",
    0x01: "n/a",
    0x02: "srl",
    0x03: "sra",
    0x04: "sllv",
    0x05: "n/a",
    0x06: "srlv",
    0x07: "srav",
    0x08: "jr",
    0x09: "jalr",
    0x0A: "n/a",
    0x0B: "n/a",
    0x0C: "syscall",
    0x0D: "break",
    0x0E: "n/a",
    0x0F: "n/a",
    0x10: "mfhi",
    0x11: "mthi",
    0x12: "mflo",
    0x13: "mtlo",
    0x14: "n/a",
    0x15: "n/a",
    0x16: "n/a",
    0x17: "n/a",
    0x18: "mult",
    0x19: "multu",
    0x1A: "div",
    0x1B: "divu",
    0x1C: "n/a",
    0x1D: "n/a",
    0x1E: "n/a",
    0x1F: "n/a",
    0x20: "add",
    0x21: "addu",
    0x22: "sub",
    0x23: "subu",
    0x24: "and",
    0x25: "or",
    0x26: "xor",
    0x27: "nor",
    0x28: "n/a",
    0x29: "n/a",
    0x2A: "slt",
    0x2B: "sltu",
    0x2C: "n/a",
    0x2D: "n/a",
    0x2E: "n/a",
    0x2F: "n/a",
    0x30: "n/a",
    0x31: "n/a",
    0x32: "n/a",
    0x33: "n/a",
    0x34: "n/a",
    0x35: "n/a",
    0x36: "n/a",
    0x37: "n/a",
    0x38: "n/a",
    0x39: "n/a",
    0x3A: "n/a",
    0x3B: "n/a",
    0x3C: "n/a",
    0x3D: "n/a",
    0x3E: "n/a",
    0x3F: "n/a",
}

registers = {
    0:  "zero",
    1:  "at",
    2:  "v0",
    3:  "v1",
    4:  "a0",
    5:  "a1",
    6:  "a2",
    7:  "a3",
    8:  "t0",
    9:  "t1",
    10: "t2",
    11: "t3",
    12: "t4",
    13: "t5",
    14: "t6",
    15: "t7",
    16: "s0",
    17: "s1",
    18: "s2",
    19: "s3",
    20: "s4",
    21: "s5",
    22: "s6",
    23: "s7",
    24: "t8",
    25: "t9",
    26: "k0",
    27: "k1",
    28: "gp",
    29: "sp",
    30: "fp",
    31: "ra",
}

# source: http://www.cburch.com/cs/330/reading/mips-ref.pdf
# r == register, i == immediate, j == jump
encoding_type = {
    "add": "r",
    "sub": "r",
    "addi": "i",
    "addu": "r",
    "subu": "r",
    "addiu": "i",
    "mult": "r",
    "div": "r",
    "multu": "r",
    "divu": "r",
    "mfhi": "r",
    "mflo": "r",
    "and": "r",
    "or": "r",
    "nor": "r",
    "xor": "r",
    "andi": "i",
    "ori": "i",
    "xori": "i",
    "sll": "r",
    "srl": "r",
    "sra": "r",
    "sllv": "r",
    "srlv": "r",
    "srav": "r",
    "slt": "r",
    "sltu": "r",
    "slti": "i",
    "sltiu": "i",
    "j": "j",
    "jal": "j",
    "jr": "r",
    "jalr": "r",
    "beq": "i",
    "bne": "i",
    "syscall": "r",
    "special": "r", # all "special" encodings are really just a variant of register
    "lui": "i",
    "lb": "i",
    "lbu": "i",
    "lh": "i",
    "lhu": "i",
    "lw": "i",
    "sb": "i",
    "sh": "i",
    "sw": "i",
    "ll": "i",
    "sc": "i",
}

# source: http://www.cburch.com/cs/330/reading/mips-ref.pdf
# how to disassemble the register use
register_subtype = {
    "add": "dst", # op rd, rs, rt
    "sub": "dst",
    "addu": "dst",
    "subu": "dst",
    # ----------
    "mult": "st", # op rs, rt
    "div": "st",
    "multu": "st",
    "divu": "st",
    "mfhi": "d", # op rd
    "mflo": "d",
    # ----------
    "and": "dst",
    "or": "dst",
    "nor": "dst",
    "xor": "dst",
    # ----------
    "sll": "dth", # op rd, rt, sh
    "srl": "dth",
    "sra": "dth",
    "sllv": "dts", # op rd, rt, rs
    "srlv": "dts",
    "srav": "dts",
    # ----------
    "slt": "dst",
    "sltu": "dst",
    # ----------
    "jr": "s", # op rs
    "jalr": "s",
    "syscall": "syscall", # a mess
}

immediate_subtype = {
    "addi": "tsi", # op rt, rs, imm
    "addiu": "tsi",
    "andi": "tsi",
    "ori": "tsi",
    "xori": "tsi",
    "slti": "tsi",
    "sltiu": "tsi",
    "beq": "tsi",
    "bne": "tsi",
    "lui": "ti", # op rt, imm
    "lb": "tis", # op rt, imm(rs)
    "lbu": "tis",
    "lh": "tis",
    "lhu": "tis",
    "lw": "tis",
    "sb": "tis",
    "sh": "tis",
    "sw": "tis",
    "ll": "tis",
    "sc": "tis",
}

#TODO(Lazy) special decoding

class MIPS():
    pass
#TODO(Lazy)?
tools/mips.py
lazycurler/CrashBashResearchACE
from charTable import CharTable
from graph import Graph
from typing import Dict, List
import tracker

#TODO (Lazy) debug should be a member variable, not per function

class Navigator:
    def __init__(self, graph_dict: Dict[str, Graph], starting_graph: str):
        self.graph_dict = graph_dict
        self.starting_graph = starting_graph
        self.cur_graph = self.graph_dict[starting_graph]
        self.cursor_index = 0
        self.input_tracker = tracker.InputTracker(self.starting_graph)

    def add_graph_from_char_table(self, name: str, char_table: CharTable):
        assert isinstance(name, str)
        self.graph_dict[name] = Graph.from_char_table(char_table)

    def switch_current_graph(self, name: str, new_index: int=None):
        assert isinstance(name, str)
        self.cur_graph = self.graph_dict[name]
        if new_index:
            self.cursor_index = new_index

    def go_to_cursor_index(self, index: int, debug=False):
        start = self.cur_graph.vert_from_cursor_index(self.cursor_index)
        finish = self.cur_graph.vert_from_cursor_index(index)
        moves = self.cur_graph.get_moves(start, finish, debug)
        self.input_tracker.add_moves(moves)
        self.cursor_index = self.cur_graph.node_from_vert(finish).cursor_index

    def select_index(self,
                     index: int,
                     count: int=1,
                     byte_selected: bool=None,
                     table_change: str=None,
                     comment: str=None,
                     debug: bool=False):
        self.go_to_cursor_index(index, debug)
        self.input_tracker.press_circle(count=count,
                                        byte_selected=byte_selected,
                                        table_change=table_change,
                                        comment=comment)

    def select_table_change(self, index: int, table_name: str, debug=False):
        self.go_to_cursor_index(index, debug)
        self.input_tracker.press_circle(count=1,
                                        byte_selected=None,
                                        table_change=table_name)
        self.switch_current_graph(table_name)

    def go_to_nop_addr(self, nop_addr: str, debug: bool=False):
        start = self.cur_graph.vert_from_cursor_index(self.cursor_index)
        finish = self.cur_graph.vert_from_nop_addr(nop_addr)
        moves = self.cur_graph.get_moves(start, finish, debug)
        self.input_tracker.add_moves(moves)
        self.cursor_index = self.cur_graph.node_from_vert(finish).cursor_index

    def go_to_alt_nop_addr(self, alt_nop_addr: str, debug: bool=False):
        start = self.cur_graph.vert_from_cursor_index(self.cursor_index)
        finish = self.cur_graph.vert_from_alt_nop_addr(alt_nop_addr)
        moves = self.cur_graph.get_moves(start, finish, debug)
        self.input_tracker.add_moves(moves)
        self.cursor_index = self.cur_graph.node_from_vert(finish).cursor_index

    def go_to_nearest_byte(self, byte: int, depth_limit=999, dead_ends_allowed: bool=False, debug: bool=False):
        start = self.cur_graph.vert_from_cursor_index(self.cursor_index)
        finish_node = self.cur_graph.get_closest_node_from_byte(byte, self.cursor_index, depth_limit, dead_ends_allowed, debug)
        assert finish_node is not None, f'Unable to find a node containing 0x{byte:02X}'
        finish = self.cur_graph.vert_from_vert_index(finish_node.vert)
        if debug:
            print(f"Getting moves from: {self.cur_graph.node_from_vert(start)} to {self.cur_graph.node_from_vert(finish)}")
        moves = self.cur_graph.get_moves(start, finish, debug)
        self.input_tracker.add_moves(moves)
        self.cursor_index = self.cur_graph.node_from_vert(finish).cursor_index

    def select_nearest_byte(self, byte: int, count: int=1, depth_limit=999, dead_ends_allowed: bool=False, comment: str=None, debug: bool=False):
        self.go_to_nearest_byte(byte, depth_limit, dead_ends_allowed, debug)
        self.input_tracker.press_circle(count=count, byte_selected=byte, comment=comment)

    # this is essentially just a greedy bfs search of the bytes needed
    # TODO(Lazy) for bytes with multiple nodes, pathing could be improved to pick the "best" series of nodes
    # for a given set of instructions. I'm 99.9% sure this is an NP (complete?) problem
    def write_code(self, instructions: List[int], debug=False):
        def _debug(count, byte):
            if debug:
                print(f"Current index: {self.cursor_index}")
                print(f"Locating Byte 0 of instruction {count}: 0x{byte:02X}")

        for count, instruction in enumerate(instructions):
            byte0 = instruction & 0x000000FF
            byte1 = (instruction & 0x0000FF00) >> 8
            byte2 = (instruction & 0x00FF0000) >> 16
            byte3 = (instruction & 0xFF000000) >> 24
            _debug(count, byte0) if debug else None
            self.select_nearest_byte(byte0)
            _debug(count, byte1) if debug else None
            self.select_nearest_byte(byte1)
            _debug(count, byte2) if debug else None
            self.select_nearest_byte(byte2)
            _debug(count, byte3) if debug else None
            self.select_nearest_byte(byte3)

        if debug:
            print("Done writing a section of code...")

    # TODO(Lazy) maybe return count?
    def gen_tas(self, count: bool=False, compress: bool=True):
        if compress:
            self.input_tracker.compress()
        if count:
            print(len(self.input_tracker.meta_inputs))
        return f"\n\n\n{self.input_tracker.gen_tas_studio_string()}"

    # TODO(Lazy) add typing
    def reset(self, starting_graph=None):
        self.cursor_index = 0
        self.input_tracker.inputs.clear()
        if starting_graph:
            self.cur_graph = self.graph_dict[starting_graph]
tools/navigator.py
lazycurler/CrashBashResearchACE
from dataclasses import dataclass

@dataclass
class NodeInfo():
    #TODO(Lazy) should these be strings?
    vert: int # hacky way to keep track of which vertex this is associated with
    nop_addr: int # the address that will be NOP'd if the cursor is here
    alt_nop_addr: int # the address that will be NOP'd if the index math is changed (NOP'd) effectively resulting in a bifurcated NOP stream
    is_modifier: int # whether the would be inserted character is treated as a "modified" character aka (han)dakuten
    cursor_index: int # the location of the blinking, player-controlled, cursor. Starts at 0 which is the upper left corner of the menu
    byte: int # the byte that would be inserted (assuming the user pressed "X" and valid switch case)
    switch_case: int # the resulting action if a user was to press "X" at this index
    hazard: bool # Some lookups result in invalid memory access - whether or not "byte" is valid
    dead_end: bool # If False, node has at least one outgoing edge (to another node). If True, you can never leave; Hotel California.
tools/nodeInfo.py
lazycurler/CrashBashResearchACE
from typing import List
from navigator import Navigator
from menu_constants import * #NOSONAR
# yes, I know this is bad - as the name implies the module is just filled with constants related to the save menu
# this is a cheap hack to avoid circular dependency and avoid a lot of extra typing/noise
from tracker import Input


bifurcate_nop = "0x000B7E0C"
mod_up_movement = "0x000B7EE4"
change_write_loc = "0x000B7D64"
no_insert_nop = "0x000B80C4"
negative_char_count = "0x000B83E4"

nop_level_check_code = [
    # code to NOP out the desired addr aka make the level check function always return True/1
    #0x314A0000, # andi t2, t2, 0x0000   # t2 = 0x00000000 # t2 should be blank by default, no need to zero
    0x3942B5BA, # xori v0, t2, 0xB5BA   # v0 = 0x0000B5BA
    0x03823020, # add  a2, gp, v0       # a2 = 0x8007B48A
    0xACCA00BA, # sw   t2, 0x00BA(a2)   # 0x8007B544 = 0
]

jr_ra_code = [
    0x03E8E888, # jr   $ra
]

save_state_exit_code = [
    # code to exit without saving - write 0x2 to 0x8000BB6A0 (enter name state machine addr)
    0x8F8F8F20, # lw    t7, -0x70E0(gp) # t7 = 0x000C7350
    # 0x3842B5B8, # xori  v0, v0, 0xB5B8  # v0 = 0x00000002
    0x3843B5B8, # xori  v1, v0, 0xB5B8  # v1 = 0x00000002
    # TODO(Lazy) might be able to save an xor here somehow TBD
    # 0x39EF6F00, # xori  t7, t7, 0x6F00  # t7 = 0x000C1C50
    0x39EFF800, # xori  t7, t7, 0xF800  # t7 = 0x000C8B50
    0x39EF8B00, # xori  t7, t7, 0x8B00  # t7 = 0x000C0050
    # TODO(Lazy) duplicate?
    0xADE3B650, # sw    v0, -0x49B0(t7) # 0x000B66A0 = v0
    0xADE3B650, # sw    v1, -0x49B0(t7) # 0x000B66A0 = v1
]

# NOTE(Lazy) At the time of writing this comment, this destroys paging right (left still works)
def write_reserved_bytes(nav: Navigator):
    # 0x22 and 0x26 are the two addresses from which inserted bytes can be read
    # 0x22 - 0x18 = 0xA == 10
    # insert 10 characters
    # this could be optimized - both in character selection and path to said character
    nav.select_index(hana_hi)       # 0x18
    nav.select_index(hana_hi)       # 0x19
    nav.select_index(hana_hi)       # 0x1a
    nav.select_index(hana_hi)       # 0x1b
    nav.select_index(hana_hi)       # 0x1c
    nav.select_index(hana_hi)       # 0x1d
    nav.select_index(handakuten_ee) # 0x1e
    nav.select_index(hana_hi)       # 0x1f
    nav.select_index(handakuten_ee) # 0x20
    nav.select_index(hana_hi)       # 0x21
    nav.go_to_nop_addr(change_write_loc)
    nav.select_index(handakuten_ee)       # 0x22
    nav.select_index(kata_exit)


def old_v1(nav: Navigator):
    # TODO(Lazy) not sure if I need to go to kata? So many possibilities for optimization...
    nav.select_table_change(hira_to_kata_arrow, "kata")
    nav.go_to_alt_nop_addr(mod_up_movement)
    nav.switch_current_graph("kata_alt_up")
    #nav.select_index(0)
    #nav.switch_current_graph("kata_alt_up")
    nav.select_index(kata_insertable_ee)
    nav.go_to_nop_addr(write_near_0_nop)
    #for _ in range(1):
    #    nav.select_index(kata_insertable_ee, True)
    #nav.select_index(kata_to_latin_arrow, True)
    #nav.switch_current_graph("latin_alt_up")
    #nav.go_to_nop_addr(write_near_0_nop)
    #nav.select_index(0)
    print(nav.gen_tas(count=True))

def old_v2(nav: Navigator):
    nav.select_table_change(hira_to_kata_arrow, "kata")
    nav.select_index(kata_zero, count=0x1B)
    # write the actual code
    bytes_written = inject_payload(nav, nop_level_check_code)
    bytes_written += inject_payload(nav, jr_ra_code)

    # move from 0x800C007C
    #bytes_written = 0
    nav.select_index(kata_zero, count=0x48-bytes_written)
    nav.select_index(kata_hex_34)
    nav.select_index(kata_zero)
    nav.select_index(kata_hex_0c)
    #nav.select_index(kata_to_hira_arrow) # have to switch to clear out the nasty code we wrote
    nav.select_index(kata_exit)
    print(nav.gen_tas(True))


def write_to_0x800c0019_on_init_setup(nav: Navigator):
    # Change write offset to the 0x800c0000 region
    nav.select_table_change(hira_to_kata_arrow, "kata")
    nav.go_to_nop_addr(change_write_loc)
    nav.go_to_nop_addr(bifurcate_nop)
    nav.go_to_alt_nop_addr(negative_char_count)
    #nav.select_index(hira_exit)
    nav.select_index(kata_exit)
    #print(nav.gen_tas(True))


def negative_char_count_on_init_setup(nav: Navigator):
    nav.select_table_change(hira_to_kata_arrow, "kata")
    nav.input_tracker.add_metadata_comment('Traveling to NOP the "NOP Bifurcation" address')
    nav.go_to_nop_addr(bifurcate_nop)
    nav.input_tracker.add_metadata_comment('Traveling to alt NOP the "Negative Starting Character Count" address')
    nav.go_to_alt_nop_addr(negative_char_count)
    #nav.select_index(hira_exit)
    nav.go_to_cursor_index(kata_exit) # let menuing press circle


def inject_payload(nav: Navigator, payload: List[int]) -> int:
    nav.write_code(payload)
    return len(payload * 4) # bytes written


def rest_of_the_owl(nav: Navigator):
    # move from 0x800C0019 to 0x800C0034
    nav.select_nearest_byte(0, count=0x1B)

    # inject the payload
    bytes_written = inject_payload(nav, nop_level_check_code)   # enable going to any level
    bytes_written += inject_payload(nav, save_state_exit_code)  # force exit save menu when code is run
    bytes_written += inject_payload(nav, jr_ra_code)

    # move from 0x800C007C
    nav.select_nearest_byte(0x00, count=0x48-bytes_written)
    nav.select_nearest_byte(0x34)
    nav.select_nearest_byte(0x00)
    nav.input_tracker.add_table_change("hira_terminal")
    nav.switch_current_graph("hira_terminal")
    nav.select_nearest_byte(0x0C) # writing the 0x0C will cause the code to execute and thus leave the menu


def solution_with_payload_at_0x80011b8e4(nav: Navigator):
    # move into the first full word
    nav.input_tracker.add_metadata_comment("Injecting Payload")
    nav.input_tracker.press_circle(3)

    # inject the payload counting the bytes written to determine how much filler to inject
    bytes_written = inject_payload(nav, nop_level_check_code)   # enable going to any level
    bytes_written += inject_payload(nav, jr_ra_code)

    # make sure the branch/jump delay slot won't crash us (this will be 0x03030303) which is effectively a nop
    nav.input_tracker.press_circle(4)

    # change the write location to be in the 0x800c0000 region
    nav.input_tracker.add_metadata_comment("Switching to 0x800c000 Region to setup function pointer")
    nav.select_table_change(hira_to_kata_arrow, "kata") # TODO(Lazy) might be able to find something closer
    nav.go_to_nop_addr(change_write_loc)

    # move to where function pointer will be accessed
    nav.input_tracker.add_metadata_comment("Moving to new AnimationNode function pointer")
    nav.input_tracker.press_circle(0x34-bytes_written)

    # write the (function) pointer that points at the payload
    nav.input_tracker.add_metadata_comment("Writing new AnimationNode function pointer")
    nav.select_nearest_byte(0xE4)
    nav.select_nearest_byte(0xB8)
    nav.select_nearest_byte(0x11)
    nav.select_nearest_byte(0x00) # could be 0x80 if it matters, maybe even 0x20?

    # make the next node pointer be NULL marking the end of the linked list
    nav.input_tracker.add_metadata_comment("Moving to existing AnimationNode function pointer")
    nav.input_tracker.press_circle(0x24)

    # sneak through the function pointer for the current node
    nav.input_tracker.add_metadata_comment("Sneaking through existing AnimationNode function pointer")
    nav.select_nearest_byte(0x34)
    nav.select_nearest_byte(0x51)
    nav.select_nearest_byte(0x03)
    nav.select_nearest_byte(0x00)

    # trigger code execution by change the pointer to the next node to be earlier the list
    nav.input_tracker.add_metadata_comment("Executing Payload")
    nav.select_nearest_byte(0x00)

    # change pointer to next node to 0x800C0000 causing the above function pointer to used
    nav.input_tracker.press_circle(4)
    nav.select_index(-70) # hacky cancel and exit


def leave_save_menu_and_reenter(nav: Navigator):
    tracker = nav.input_tracker
    tracker.add_inputs(Input(up=True, circle=True), count=2, comment="Exit the save menu")
    tracker.add_inputs(Input(up=True), count=98, comment="Walk towards the save menu")
    tracker.add_inputs(Input(up=True, circle=True), count=2, comment="Enter save menu")
    tracker.add_inputs(Input(), count=21, comment="Wait to be able to go through the final menu")
    tracker.press_circle(table_change="hira")
    nav.switch_current_graph("hira") # having re-entered the menu, reset back to the default graph
    nav.cursor_index = 0


def leave_save_menu_and_select_level_5(nav: Navigator):
    tracker = nav.input_tracker
    tracker.add_inputs(Input(up=True, left=True), count=34, comment="Walk left towards the level selector")
    tracker.add_inputs(Input(up=True), count=62, comment="Walk up into the level selector")
    tracker.add_inputs(Input(up=True, circle=True), count=2, comment="Walk into the level selector and select the first option (should be 5 now)")

def payload_at_0x80011b8e4(nav: Navigator):
    negative_char_count_on_init_setup(nav)
    leave_save_menu_and_reenter(nav)
    solution_with_payload_at_0x80011b8e4(nav)
    leave_save_menu_and_select_level_5(nav)

# TODO(Lazy) this route has succumb to bitrot :(
def payload_at_0x800c0030(nav: Navigator):
    write_to_0x800c0019_on_init_setup(nav)
    leave_save_menu_and_reenter(nav)
    rest_of_the_owl(nav)
    leave_save_menu_and_select_level_5(nav)
tools/routing.py
lazycurler/CrashBashResearchACE
import igraph as ig
import matplotlib.pyplot as plt

# The entirety of this function was written by ChatGPT, thanks bud!
# Apparently it's a modified version of Tarjan's Algorithm
def find_terminal_subgraphs(graph):
    # Counter for assigning unique indices during depth-first search
    index_counter = [0]
    # Stack to keep track of vertices in the depth-first search
    stack = []
    # Lowlink values for vertices
    lowlink = {}
    # Indices assigned to vertices during depth-first search
    index = {}
    # List to store the identified terminal subgraphs
    terminal_subgraphs = []

    def strongconnect(vertex):
        # Assign index and lowlink values to the vertex
        index[vertex] = index_counter[0]
        lowlink[vertex] = index_counter[0]
        index_counter[0] += 1
        stack.append(vertex)

        # Traverse the outgoing edges of the vertex
        neighbors = graph.neighbors(vertex, mode='OUT')
        for neighbor in neighbors:
            # Recursive call for unvisited neighbors
            if neighbor not in index:
                strongconnect(neighbor)
                # Update the lowlink value of the vertex based on the neighbor
                lowlink[vertex] = min(lowlink[vertex], lowlink[neighbor])
            # Check if the neighbor is on the stack, indicating a back edge in a cycle
            elif neighbor in stack:
                # Update the lowlink value of the vertex based on the neighbor's index
                lowlink[vertex] = min(lowlink[vertex], index[neighbor])

        # Check if the vertex is a root of a strongly connected component
        if lowlink[vertex] == index[vertex]:
            # Create a new subgraph for the terminal subgraph
            subgraph = set()
            while True:
                # Pop vertices from the stack and add them to the subgraph
                top = stack.pop()
                subgraph.add(top)
                # Stop when the root vertex is reached
                if top == vertex:
                    break
            # Add the subgraph to the list of terminal subgraphs
            terminal_subgraphs.append(subgraph)

    # Perform depth-first search for each unvisited vertex in the graph
    for vertex in graph.vs:
        if vertex.index not in index:
            strongconnect(vertex.index)

    return terminal_subgraphs

# This was also written by ChatGPT
def remove_vertices(graph, indices_to_remove):
    edges_to_remove = []
    for index in indices_to_remove:
        # Get the incident edges of the vertex
        edges_to_remove.extend(graph.incident(index, mode="ALL"))

    # Delete the edges associated with the vertices
    graph.delete_edges(edges_to_remove)

    # Delete the vertices
    graph.delete_vertices(indices_to_remove)

# This one was written by me, Lazycurler. Easy after ChatGPT did the hard part lol
def remove_all_terminal_subgraphs(graph):
    subgraphs = find_terminal_subgraphs(graph)
    sorted_subgraphs = sorted(subgraphs, key=len, reverse=True)
    #print(sorted_subgraphs)
    remove_me = sorted_subgraphs[1:]
    #print("Removing the following terminal subgraphs: ", remove_me)
    #print("Keeping: ", sorted_subgraphs[0])
    indices_to_remove = [element for s in remove_me for element in s]
    remove_vertices(graph, indices_to_remove)
    return remove_me


def main():
    # Example usage
    graph = ig.Graph(directed=True)
    graph.add_vertices(7)
    graph.add_edges([(0, 1), (1, 2), (2, 3), (3, 4), (4, 0), (4, 5), (5, 6)])

    print("Before removal:")
    print(graph)

    _, ax = plt.subplots()
    ig.plot(graph, target=ax)
    plt.show()

    remove_all_terminal_subgraphs(graph)

    print("After removal:")
    print(graph)

    _, ax = plt.subplots()
    ig.plot(graph, target=ax)
    plt.show()

if __name__ == "__main__":
    main()
tools/subgraphTools.py
lazycurler/CrashBashResearchACE
from dataclasses import dataclass
from typing import Dict, List, Optional, Tuple
from graph import Move
from copy import deepcopy
from visualizer import CursorLocation

@dataclass
class Input:
    up: bool = False       # U
    down: bool = False     # D
    left: bool = False     # L
    right: bool = False    # R
    triangle: bool = False # T
    cross: bool = False    # X
    square: bool = False   # Q
    circle: bool = False   # O
    # TODO(Lazy) Add other buttons in the future
    ALL_INPUT_LINE = "|    0,....|  128,  128,  128,  128,UDLR..TXQO.......|"
    NO_INPUT_LINE  = "|    0,....|  128,  128,  128,  128,.................|"

    @classmethod
    def from_str(cls, string):
        up = "U" in string
        down = "D" in string
        left = "L" in string
        right = "R" in string
        triangle = "T" in string
        cross = "X" in string
        square = "Q" in string
        circle = "O" in string
        return cls(up, down, left, right, triangle, cross, square, circle,)

    def tas_str(self) -> str:
        # Note, currently all analog directions are set to "no movement"
        u = "U" if self.up else "."
        d = "D" if self.down else "."
        l = "L" if self.left else "."
        r = "R" if self.right else "."
        t = "T" if self.triangle else "."
        x = "X" if self.cross else "."
        q = "Q" if self.square else "."
        o = "O" if self.circle else "."

        return f"|    0,....|  128,  128,  128,  128,{u}{d}{l}{r}..{t}{x}{q}{o}.......|"

    def direction_str(self) -> str:
        u = "U" if self.up else ""
        d = "D" if self.down else ""
        l = "L" if self.left else ""
        r = "R" if self.right else ""
        return f"{u}{d}{l}{r}"

    def is_directional(self) -> bool:
        return len(self.direction_str()) > 0

    def is_selection(self) -> bool:
        return (self.circle or self.cross)

    def is_blank(self) -> bool:
        return not (self.up \
            and self.down \
            and self.left \
            and self.right \
            and self.triangle \
            and self.cross \
            and self.square \
            and self.circle)

    def is_pure_directional(self) -> bool:
        return self.is_directional() and not self.is_selection()

    def is_pure_selection(self) -> bool:
        return self.is_selection() and not self.is_directional()


@dataclass
class Metadata():
    src_index: Optional[int] = None # current index before this input is registered
    dst_index: Optional[int] = None # future index after this input is registered
    byte_selected: Optional[int] = None
    table_change: Optional[str] = None # used to mark what table is currently being used
    comment: Optional[str] = None # any other meta information desired

    def is_none(self):
        return (self.src_index is None \
                and self.dst_index is None \
                and self.byte_selected is None \
                and self.table_change is None \
                and self.comment is None)

@ dataclass
class MetaInput():
    input: Input
    metadata: Optional[Metadata] = None


class InputTracker():
    BLANK_INPUT=Input.from_str(Input.NO_INPUT_LINE)
    BLANK_META_INPUT = MetaInput(BLANK_INPUT)

    def __init__(self, start_table):
        self.meta_inputs = []
        self.start_table = start_table

    def add_blank(self, count:int=1):
        for _ in range(count):
            self.meta_inputs.append(self.BLANK_META_INPUT)

    def add_inputs(self, an_input: Input, count=1, comment=None):
        meta_input = MetaInput(an_input, Metadata(comment=comment))
        self.meta_inputs.append(meta_input)
        if count > 1:
            meta_input = MetaInput(an_input)
            for _ in range(count-1):
                self.meta_inputs.append(meta_input)

    def add_input_list(self, inputs: List[Input]):
        self.meta_inputs += [MetaInput(an_input) for an_input in inputs]

    def add_meta_input(self, meta_input: MetaInput):
        self.meta_inputs.append(meta_input)

    def add_meta_input_list(self, meta_inputs: List[MetaInput]):
        self.meta_inputs += meta_inputs

    def add_input_from_strings(self, directions: List[str]):
        new_input = []
        for direction in directions:
            action = (Input.from_str(direction))
            new_input.append(action)
            new_input.append(action)
            new_input.append(Input.NO_INPUT_LINE)
            new_input.append(Input.NO_INPUT_LINE)
        self.add_input_list(new_input)

    def add_moves(self, moves: List[Move]):
        for move in moves:
            an_input = Input.from_str(move.direction)
            # only add the meta information to the first set of input for a given move
            self.meta_inputs.append(MetaInput(an_input, Metadata(move.src_index, move.dst_index)))
            self.meta_inputs.append(MetaInput(an_input))
            # insert two blank frames
            # the game needs two frames before it can process the same input again
            self.add_blank(2)

    def press_circle(self, count:int=1, byte_selected: int=None, table_change:str=None, comment: str=None):
        metadata_full = Metadata(byte_selected=byte_selected, table_change=table_change, comment=comment)
        metadata_byte = Metadata(byte_selected=byte_selected)
        circle_with_full_data = MetaInput(Input.from_str("O"), metadata_full)
        circle_with_byte = MetaInput(Input.from_str("O"), metadata_byte)
        circle = MetaInput(Input.from_str("O"))

        # add initial circle press with full metadata
        self.meta_inputs.append(circle_with_full_data)
        self.meta_inputs.append(circle)
        self.add_blank(2)

        # add additional presses with minimal metadata
        for _ in range(count-1):
            self.meta_inputs.append(circle_with_byte)
            self.meta_inputs.append(circle)
            self.add_blank(2)

    def add_metadata_comment(self, comment: str):
        assert len(self.meta_inputs) > 0, "To add a comment to the last entry there must be at least 1 entry"
        last_input = deepcopy(self.meta_inputs[-1])
        if last_input.metadata is None:
            last_input.metadata = Metadata(comment=comment)
        else:
            last_input.metadata.comment = comment
        self.meta_inputs[-1] = last_input

    def add_table_change(self, table: str):
        assert len(self.meta_inputs) > 0, "To add a table change to the last entry there must be at least 1 entry"
        last_input = deepcopy(self.meta_inputs[-1])
        if last_input.metadata is None:
            last_input.metadata = Metadata(table=table)
        else:
            last_input.metadata.table = table
        self.meta_inputs[-1] = last_input

    def get_used_edges(self) -> Dict[str, List[Tuple[int, int]]]:
        used_edges = {}
        cur_table = self.start_table
        used_edges[cur_table] = []

        # find all the edges used for each table
        for meta_input in self.meta_inputs:
            metadata = meta_input.metadata
            if metadata is None:
                continue

            # check for a table change and verify used_edges contains this table
            table = metadata.table_change
            if table is not None and table != "":
                cur_table = table
                if cur_table not in used_edges:
                    used_edges[cur_table] = []

            # add the index for the current input to the current table
            if metadata.src_index is not None or metadata.dst_index is not None:
                assert metadata.src_index is not None, "src None: Both src and dst index must not be None to compute edges"
                assert metadata.dst_index is not None, "dst None: Both src and dst index must not be None to compute edges"
                used_edges[cur_table].append((metadata.src_index, metadata.dst_index))

        # remove duplicates form each of the list of used edges
        for seen_table in used_edges.keys():
            used_edges[seen_table] = list(set(used_edges[seen_table]))

        return used_edges

    def get_cursor_locations(self) -> List[CursorLocation]:
        cursor_locations = []
        old_table = self.start_table
        old_index = None
        cur_table = self.start_table
        cur_index = None
        last_byte = None
        last_direction = ""
        context_info = ""

        for meta_input in self.meta_inputs:
            direction = meta_input.input.direction_str()
            metadata = meta_input.metadata
            if metadata is not None:
                if metadata.table_change is not None:
                    cur_table = metadata.table_change
                    cur_index = None
                if metadata.src_index is not None:
                    cur_index = metadata.src_index
                if metadata.byte_selected is not None:
                    last_byte = metadata.byte_selected
                if direction != "":
                    last_direction = direction
                if metadata.comment is not None:
                    context_info = metadata.comment

            if cur_index is not None:
                cursor_locations.append(CursorLocation(cur_table, cur_index, last_byte, last_direction, context_info))
                old_table = cur_table
                old_index = cur_index
            else:
                # in the transition to the next table but don't yet know the new index
                cursor_locations.append(CursorLocation(old_table, old_index, None, last_direction, context_info))

        return cursor_locations

    def compress(self, debug: bool=False):
        # removes blank frames between movements that don't share any buttons
        # extremely hacky as this is the end of the project for me and I'm running out of steam here
        compressed_inputs = []
        def _remove_middle_inputs():
            del compressed_inputs[-2]
            del compressed_inputs[-2]
            if debug:
                print(i, curr_direction, prev_direction)

        for i, meta_input in enumerate(self.meta_inputs):
            compressed_inputs.append(meta_input)
            if i < 4:
                continue
            curr_input = self.meta_inputs[i].input
            pre0_input = self.meta_inputs[i-1].input
            pre1_input = self.meta_inputs[i-2].input
            pre2_input = self.meta_inputs[i-3].input

            # detect a set of 4 inputs where:
            # the first is a movement
            # there is a two frame break
            # followed by another movement
            if (curr_input.is_directional()
                and pre0_input.is_blank()
                and pre1_input.is_blank()
                and pre2_input.is_directional()):

                curr_direction = curr_input.direction_str()
                prev_direction = pre2_input.direction_str()
                if not set(curr_direction).intersection(set(pre2_input.direction_str())):
                    _remove_middle_inputs()

            # alternatively compress unrelated directional and selection inputs
            if ((curr_input.is_pure_selection()
                and pre0_input.is_blank()
                and pre1_input.is_blank()
                and pre2_input.is_pure_directional())
                or
               (curr_input.is_pure_directional()
                and pre0_input.is_blank()
                and pre1_input.is_blank()
                and pre2_input.is_pure_selection())):
                _remove_middle_inputs()

        self.meta_inputs = compressed_inputs

    def gen_tas_studio_string(self) -> str:
        return "\n".join([meta_input.input.tas_str() for meta_input in self.meta_inputs]) + "\n\n\n\n"

    # TODO(Lazy) May wish to add file read/write support in the future
    # TODO(Lazy) Reduce cognitive complexity of this function someday
    def gen_debug_string(self, metadata_required: bool=True, all_frames: bool=False) -> str:
        line_separator ="|-----------------------------|\n"
        def safe_str(s: str):
            return "" if s is None else s

        def add_table_break(table: str):
            table_str = line_separator
            table_str += f"| Table Change: {table}\n"
            table_str += line_separator
            return table_str

        debug_str = ""
        debug_str += add_table_break(self.start_table)
        debug_str += "| move |  from |  to   | byte |\n"
        debug_str += "|------|-------|-------|------|\n"

        for meta_input in self.meta_inputs:
            input_str, src, dst, byte, table, comment = "", "", "", "", "", ""
            metadata = meta_input.metadata
            check_circle = False
            no_data = True

            # check for any directional input
            if meta_input.input is not None:
                input_str = meta_input.input.direction_str()

            # make sure this entry contains useful debug information
            if (metadata is not None and not metadata.is_none()):
                no_data = False
                # check to see if a character is being inserted at this location
                selected_byte = metadata.byte_selected
                if metadata.byte_selected is not None:
                    check_circle = True
                    byte = f"0x{selected_byte:02X}"
                src = safe_str(metadata.src_index)
                dst = safe_str(metadata.dst_index)
                table = safe_str(metadata.table_change)
                if table != "":
                    debug_str += add_table_break(table)
                comment = safe_str(metadata.comment)
            # no metadata available
            elif not metadata_required or all_frames:
                check_circle = True

            if (check_circle or all_frames) and meta_input.input.circle:
                input_str += "O"
                no_data = False

            if no_data and not all_frames:
                continue

            debug_str += f"| {input_str:<4} | {src:5} | {dst:5} | {byte:4} | {comment}\n"

        debug_str += line_separator
        debug_str += f"| Frames: {len(self.meta_inputs):5}{'':15}|\n"
        debug_str += line_separator
        return debug_str
tools/tracker.py
lazycurler/CrashBashResearchACE
from typing import Dict, List, Optional, Tuple
import igraph as ig
import matplotlib.pyplot as plt
from graph import Graph
import random
from dataclasses import dataclass
from PIL import Image
import glob
import os

@dataclass
class GraphInfo():
    table_name: str
    movement_graph: Graph
    ig_graph: ig.Graph
    used_edges: List[Tuple[int, int]]
    subgraph_map: Dict[int, int]

def gen_graph_infos(graph_dict: Dict[str, ig.Graph],  used_edges: Dict[str, List[Tuple[int, int]]]) -> List[GraphInfo]:
    graph_info = []
    for name, movement_graph in graph_dict.items():
        if name in used_edges:
            ig_graph, subgraph_map = create_subgraph(movement_graph, used_edges[name])
            graph_info.append(GraphInfo(name, movement_graph, ig_graph, used_edges[name], subgraph_map))
    return graph_info

def create_subgraph(movement_graph: Graph, used_edges: List[Tuple[int, int]]):
    original_graph = movement_graph.graph
    subgraph = ig.Graph(directed=original_graph.is_directed())

    # extract a list of relevant vertices
    selected_vert_indices = set()
    for edge in used_edges:
        src_vert = movement_graph.vert_from_cursor_index(edge[0]).index
        dst_vert = movement_graph.vert_from_cursor_index(edge[1]).index
        selected_vert_indices.add(src_vert)
        selected_vert_indices.add(dst_vert)

    # create mapping between original vertex indices and subgraph vertex indices
    vertex_mapping = {}
    vertices_list = []
    for v in selected_vert_indices:
        vertices_list.append(v)
        original_vertex = original_graph.vs[v]
        subgraph_vertex = subgraph.add_vertex(**original_vertex.attributes())
        vertex_mapping[v] = subgraph_vertex.index

    # remove duplicate vertex indices
    vertices_list = list(set(vertices_list))

    # add edges from the original graph that are between the specified vertices
    seen_edges = set() # track which connections have been created between vertices to prevent multiple connections
    for edge in original_graph.es():
        src_cursor_index = movement_graph.node_from_vert_index(edge.source).cursor_index
        dst_cursor_index = movement_graph.node_from_vert_index(edge.target).cursor_index
        pair = (src_cursor_index, dst_cursor_index)
        # this is a hacky way to prevent multiple edges between nodes
        # multiple edges are actually correct, but for the sake of keeping the graph clean they are ignored
        if pair in used_edges and pair not in seen_edges:
            seen_edges.add(pair)
            subgraph.add_edge(vertex_mapping[edge.source], vertex_mapping[edge.target], **edge.attributes())

    return subgraph, vertex_mapping

@dataclass
class CursorLocation():
    table_name: str
    index: int
    last_byte: int
    last_move: str
    context_info: str

# TODO(Lazy) split out the gif generation?
# TODO(Lazy) nail down framerate
# TODO(Lazy) add frame count
def gen_movement_gif(graphs:List[GraphInfo],
                     cursor_locs:List[CursorLocation],
                     route_name:str,
                     frame_durations:List[float]=[(1/60 * 1000), (1/30 * 1000), 500, 1000]): # default to ingame movement speed
                     #frame_durations:List[float]=[(1/60 * 1000)]): # default to ingame movement speed
    for frame, cursor_loc in enumerate(cursor_locs):
        last_byte = cursor_loc.last_byte
        print(last_byte)
        last_byte_str = "" if last_byte is None else f"0x{last_byte:02X}"
        info_text = f"Table:     {cursor_loc.table_name.capitalize()}\n" \
                    f"Index:     {cursor_loc.index}\n" \
                    f"Last Byte: {last_byte_str}\n" \
                    f"Last Move: {cursor_loc.last_move}\n" \
                    f"Frame:     {frame}"
        visualize(graphs=graphs,
                  cursor_loc=cursor_loc,
                  route_name=route_name,
                  show=False,
                  save=True,
                  file_number=frame,
                  subtitle=cursor_loc.context_info,
                  center_text=info_text)

    # Create the frames
    frames = []
    imgs = sorted(glob.glob(f"../graphs/{route_name}*.png"), key=os.path.getmtime)
    for i in imgs:
        new_frame = Image.open(i)
        frames.append(new_frame)

    for frame_duration in frame_durations:
        # Save into a GIF file that loops forever
        # seems like it's actually every 250 ms not every 1000ms (hence the /4.0)
        frames[0].save(f"../graphs/{route_name}_{int(frame_duration)}.gif", format="GIF",
                    append_images=frames[1:],
                    save_all=True,
                    duration=frame_duration, loop=0)


# TODO(Lazy) this should be exposed (in?)directly via argparse/ace.py but may need a once over
def visualize(graphs:List[GraphInfo],
              cursor_loc:CursorLocation,
              route_name:str,
              show: bool=True,
              save: bool=False,
              file_number:str="",
              subtitle:str="",
              center_text:str=""):
    visual_style = {}
    visual_style["bbox"] = (4000, 4000)
    visual_style["margin"] = 400
    visual_style["vertex_size"] = 1.5
    visual_style["vertex_label_size"] = 13
    visual_style["edge_width"] = 0.5
    visual_style["edge_arrow_size"] = 0.04
    #visual_style["edge_lable_dist"] = 1.5

    # the following is actually the sub title since the above is the super(?) title
    fig, axs = plt.subplots(1, len(graphs), sharey='row', figsize=(16, 9))
    fig.subplots_adjust(hspace = .5, wspace=.001)
    random.seed(62) # make sure the layout never changes
    for ax, graph_info in zip(axs, graphs):
        ig_graph = graph_info.ig_graph
        #ig_graph.vs["label"] = ig_graph.vs["name"]
        #print(ig_graph.es["direction"])
        #ig_graph.es["label"] = ig_graph.es["direction"]
        ig_graph.vs["color"] = ["aliceblue"]
        if cursor_loc is not None and graph_info.table_name == cursor_loc.table_name:
            original_vertex_id = graph_info.movement_graph.vert_from_cursor_index(cursor_loc.index).index
            color_index = graph_info.subgraph_map[original_vertex_id]
            ig_graph.vs[color_index]["color"] = "steelblue4"
        layout = ig_graph.layout("fruchterman_reingold")
        ax.set_title(f"{graph_info.table_name.capitalize()} Character Table", y=-0.1, fontsize=24)
        #ax.patch.set_edgecolor('grey')
        #ax.patch.set_linewidth('2')
        ig.plot(ig_graph, target=ax, layout=layout, **visual_style)

    plt.suptitle("Cursor Navigation Path", fontsize=24)
    text_style = {}
    text_style["ha"] = "center"
    text_style["va"] = "center"
    text_style["multialignment"] = "left"
    text_style["transform"] = plt.gcf().transFigure
    text_style["family"] = "monospace"
    text_style["fontsize"] = 24
    plt.text(0.50, 0.90, subtitle, **text_style)
    text_style["fontsize"] = 16
    plt.text(0.50, 0.80, center_text, **text_style)
    #plt.text(0.10, 0.05, "Centered Left Text", **text_style)
    #plt.text(0.90, 0.05, "Centered Right Text", **text_style)


    if save:
        print(f"saving: {file_number}")
        plt.savefig(f"../graphs/{route_name}{file_number}.png", dpi=100)

    if show:
        plt.show()

    plt.close("all")
tools/visualizer.py
lazycurler/CrashBashResearchACE