path: root/src/disasm.cpp

/* SPDX-License-Identifier: Unlicense
 */

#include "disasm.h"
#include "m68k.h"
#include "debug.h"

#include <cassert>
#include <cerrno>
#include <cinttypes>
#include <cstring>

void DisasmNode::AddReferencedBy(const uint32_t address_from, const ReferenceType ref_type)
{
    ReferenceRecord *node = new ReferenceRecord{nullptr, ref_type, address_from};
    ASSERT(node);
    if (this->last_ref_by) {
        this->last_ref_by->next = node;
    } else {
        ASSERT(nullptr == this->ref_by);
        this->ref_by = node;
    }
    this->last_ref_by = node;
}

DisasmNode::~DisasmNode()
{
    ReferenceRecord *ref{this->ref_by};
    while (ref) {
        ReferenceRecord *prev = ref;
        ref = ref->next;
        delete prev;
    }
    ref_by = nullptr;
    last_ref_by = nullptr;
}

DisasmNode &DisasmMap::insertNode(uint32_t address, NodeType type)
{
    if (IsInstruction(type)) {
        address = AlignInstructionAddress(address);
    }
    auto *node = findNodeByAddress(address);
    if (node) {
        // Instruction nodes take precedence over data nodes. If a node that
        // was previously accessed only as data now turns out to be an
        // instruction, then it must become an instruction node.
        // XXX: Traced data must not be classified as instruction. But the
        // traced data support is yet to come.
        if (IsInstruction(type) && !IsInstruction(node->type)) {
            if (0 == (node->size & 1) && 0 == (node->address & 1)) {
                *const_cast<NodeType*>(&node->type) = type;
                // Make sure it is OpCode::kNone so it will be properly disassembled
                node->op = Op{};
            }
        }
        return *node;
    }
    if (IsInstruction(type) && _map[address + 1]) {
        // Sorry, can't do instruction here. Only 1 byte of data could fit.
        node = new DisasmNode(DisasmNode::DataRaw8(address, 0));
        ASSERT(node->size == 1);
    } else {
        node = new DisasmNode(DisasmNode::Simple(type, address));
    }
    ASSERT(node);
    // Spread across the size
    for (size_t o = 0; o < node->size; o++) {
        ASSERT(_map[address + o] == nullptr || _map[address + o] == node);
        _map[address + o] = node;
    }
    return *node;
}

DisasmNode &DisasmMap::insertNodeQuickPeek(uint32_t address, NodeType type)
{
    ASSERT(IsInstruction(type));
    address = AlignInstructionAddress(address);
    auto *node = findNodeByAddress(address);
    if (node) {
        // Instruction nodes take precedence over data nodes. If a node that
        // was previously accessed only as data now turns out to be an
        // instruction, then it must become an instruction node.
        // XXX: Traced data must not be classified as instruction. But the
        // traced data support is yet to come.
        if (IsInstruction(type) && !IsInstruction(node->type)) {
            if (0 == (node->size & 1) && 0 == (node->address & 1)) {
                *const_cast<NodeType*>(&node->type) = type;
                // Make sure it is OpCode::kNone so it will be properly disassembled
                node->op = Op{};
            }
        }
        return *node;
    }
    node = new DisasmNode(DisasmNode::Simple(type, address));
    ASSERT(node);
    // Spread across the size
    for (size_t o = 0; o < node->size; o++) {
        ASSERT(_map[address + o] == nullptr || _map[address + o] == node);
        _map[address + o] = node;
    }
    return *node;
}

DisasmNode *DisasmMap::mergeNodes(DisasmNode *primary, DisasmNode *secondary)
{
    ASSERT(primary->address < secondary->address);
    ASSERT(primary->address + primary->size >= secondary->address);
    ASSERT(primary->address + primary->size >= secondary->address + secondary->size);
    ReferenceNode *rnode{secondary->ref_by};
    while (rnode) {
        for (size_t i = 0; i < rnode->refs_count; i--) {
            primary->AddReferencedBy(rnode->refs[i].address, rnode->refs[i].type);
        }
        ReferenceNode *prev = rnode;
        rnode = rnode->next;
        delete prev;
    }
    if (secondary.ref_kinds & kRef1Mask) {
        DisasmNode *node = _map[secondary.ref1_addr];
        ASSERT(node);
        node->RemoveReferencedBy(secondary.ref1_addr);
    }
    if (secondary.ref_kinds & kRef2Mask) {
        DisasmNode *node = _map[secondary.ref2_addr];
        ASSERT(node);
        node->RemoveReferencedBy(secondary.ref2_addr);
    }
    secondary->ref_by = secondary->last_ref_by = nullptr;
    delete secondary;
    return primary;
}

DisasmNode &DisasmMap::insertReferencedBy(
        const uint32_t by_addr,
        const uint32_t ref_addr,
        const NodeType type,
        const ReferenceType ref_type)
{
    auto &ref_node = insertNode(ref_addr, type);
    ref_node.AddReferencedBy(by_addr, ref_type);
    return ref_node;
}

void DisasmMap::InsertNode(uint32_t address, NodeType type)
{
    ASSERT(_type == DisasmMapType::kTraced);
    insertNode(address, type);
}

constexpr SymbolType SymbolTypeFromElf32SymbolType(const ELF::Symbol32Type &t)
{
    if (t == ELF::Symbol32Type::kObject) {
        return SymbolType::kObject;
    }
    if (t == ELF::Symbol32Type::kFunc) {
        return SymbolType::kFunction;
    }
    return SymbolType::kNone;
}

static int cmpsym(const void *p1, const void *p2)
{
    const Symbol *sym1 = reinterpret_cast<const Symbol *>(p1);
    const Symbol *sym2 = reinterpret_cast<const Symbol *>(p2);
    if (sym1->address == sym2->address) {
        return strcmp(sym1->name, sym2->name);
    }
    return sym1->address < sym2->address ? -1 : 1;
}

bool DisasmMap::ApplySymbolsFromElf(const ELF::Image &elf)
{
    const ELF::SectionHeader32 symtab = elf.GetSectionHeaderByName(".symtab");
    if (!symtab.IsValid()) {
        fprintf(stderr, "Warning: \".symtab\" is invalid, skipping symbols\n");
        return true;
    }
    FILE *symtab_stream = open_memstream(reinterpret_cast<char**>(&_symtab), &_symtab_size);
    if (symtab_stream == nullptr) {
        const int err = errno;
        fprintf(stderr,
                "open_memstream() for symtab failed: Error (%d): \"%s\"\n",
                err, strerror(err));
        return false;
    }
    const Symbol null_symbol{};
    if (null_symbol.name != nullptr && *null_symbol.name != '\0') {
        const size_t ret = fwrite(
                &null_symbol, sizeof null_symbol, 1, symtab_stream);
        ASSERT(ret == 1), (void)ret;
    }
    const size_t nentries = symtab.size/symtab.entsize;
    for (size_t i = 0; i < nentries; i++) {
        const ELF::Symbol32 elfsym = elf.GetSymbolByIndex(i);
        const bool has_proper_type = (elfsym.type() == ELF::Symbol32Type::kNoType) ||
            (elfsym.type() == ELF::Symbol32Type::kObject) ||
            (elfsym.type() == ELF::Symbol32Type::kFunc);
        if (has_proper_type) {
            // XXX: Is it possible that it may have binding other than
            // Symbol32Bind::kGlobal when it is kFunc?
            // XXX: Yes, it is possible. It may be kLocal or kWeak for sure.
            const auto type = SymbolTypeFromElf32SymbolType(elfsym.type());
            const auto symbol = Symbol{elfsym.value, type, elfsym.name, elfsym.size};
            if (symbol.name != nullptr && *symbol.name != '\0') {
                const size_t ret = fwrite(&symbol, sizeof symbol, 1, symtab_stream);
                ASSERT(ret == 1), (void) ret;
            }
        }
    }
    // No more symbols are going to be added further, so it may be closed now.
    fclose(symtab_stream);
    // The RenderNodeDisassembly() function expects the symbol table to be
    // sorted.
    qsort(_symtab, symbolsCount(), sizeof *_symtab, cmpsym);
    return true;
}

void DisasmMap::ConsumeTraceTable(TraceTable &&tt)
{
    this->_tt = static_cast<TraceTable &&>(tt);
    const size_t nodes_count = _tt.NodesCount();
    for (size_t n = 0; n < nodes_count; n++) {
        const auto &node = _tt.Node(n);
        if (node.kind == TraceNodeKind::kPc) {
            if (node.address % 2) {
                fprintf(stderr,
                        "Error: Uneven PC values are not supported "
                        "(got PC=0x%08" PRIu32 "), exiting\n",
                        node.address);
                exit(1);
            } else if (static_cast<unsigned long>(node.address) > kRomSizeBytes) {
                fprintf(stderr,
                        "Error: PC values > 4MiB are not supported "
                        "(got PC=0x%08" PRIu32 "), exiting\n",
                        node.address);
                exit(1);
            }
            insertNode(node.address, NodeType::kTracedInstruction);
        }
    }
}

static constexpr bool IsNextLikelyAnInstruction(const Op &op)
{
    return (op.opcode != OpCode::kNone &&
            op.opcode != OpCode::kRaw &&
            op.opcode != OpCode::kRaw8 &&
            !IsBRA(op) &&
            op.opcode != OpCode::kJMP &&
            op.opcode != OpCode::kRTS &&
            op.opcode != OpCode::kRTE &&
            op.opcode != OpCode::kSTOP);
}

void DisasmMap::disasmProper(
        const DataView &code, const Settings &s, size_t at, bool nested)
{
    // Some of logic of this function is covered by integration tests in
    // `test_walk_and_follow_jumps.bash`.
    bool inside_code_span = nested;
    for (at = AlignInstructionAddress(at); at < code.size;) {
        DisasmNode *node = _map[at];
        if (!node) {
            if (!inside_code_span) {
                at += kInstructionSizeStepBytes;
                continue;
            }
            node = &insertNode(at, NodeType::kTracedInstruction);
        }
        ASSERT(node->address == at);
        const bool perform_disasm = node->IsYetToBeHandled(_type) || inside_code_span;
        if (perform_disasm) {
            node->Disasm(code, s);
            if (!canBeAllocated(*node)) {
                node->DisasmAsRaw(code);
            }
            // Spread across the size
            const size_t size = node->size;
            const size_t address = node->address;
            for (size_t o = 0; o < size; o++) {
                ASSERT(_map[address + o] == nullptr || _map[address + o] == node);
                _map[address + o] = node;
            }
        }
        inside_code_span = s.walk && IsNextLikelyAnInstruction(node->op);
        at += node->size;
        // NOTE: There is not much information about a reference passed further,
        // so just don't add a reference of immediate if s.imm_labels is not
        // enabled.
        const bool has_ref1 = (node->ref_kinds & kRef1ImmMask)
            ? s.imm_labels
            : (node->ref_kinds & kRef1Mask);
        const bool has_code_ref1 = node->ref1_addr < code.size && has_ref1;
        if (has_code_ref1) {
            const NodeType type = (node->ref_kinds & (kRef1ReadMask | kRef1WriteMask))
                ? NodeType::kRefData : NodeType::kRefInstruction;
            const auto ref_type = ReferenceTypeFromRefKindMask1(node->ref_kinds);
            auto &ref_node = insertReferencedBy(
                    node->address, node->ref1_addr, type, ref_type);
            if (ref_node.IsYetToBeHandled(_type)) {
                if (s.follow_jumps) {
                    disasmProper(code, s, ref_node.address, true);
                } else {
                    ref_node.DisasmAsRaw(code);
                }
            }
        }
        const bool has_ref2 = (node->ref_kinds & kRef2Mask);
        const bool has_code_ref2 = (has_ref2 && node->ref2_addr < code.size);
        if (has_code_ref2) {
            const NodeType type = (node->ref_kinds & (kRef2ReadMask | kRef2WriteMask))
                ? NodeType::kRefData : NodeType::kRefInstruction;
            const auto ref_type = ReferenceTypeFromRefKindMask2(node->ref_kinds);
            auto &ref_node = insertReferencedBy(
                    node->address, node->ref2_addr, type, ref_type);
            if (ref_node.IsYetToBeHandled(_type)) {
                if (s.follow_jumps) {
                    disasmProper(code, s, ref_node.address, true);
                } else {
                    ref_node.DisasmAsRaw(code);
                }
            }
        }
        if (nested && !inside_code_span) {
            return;
        }
    }
}

void DisasmMap::disasmQuickPeek(const DataView &code, const Settings &s)
{
    for (size_t at = 0; at < code.size;) {
        // QuickPeek mode goes always aligned by 2.
        ASSERT((at & 1u) == 0);
        DisasmNode *node = &insertNodeQuickPeek(at, NodeType::kTracedInstruction);
        node->Disasm(code, s);
        if ((node->size & 1) != 0) {
            fprintf(stderr, "at=%zx, size=%zu ", at, node->size);
            fprintf(stderr, "type=%u ", static_cast<unsigned>(node->type));
            fprintf(stderr, "opcode=%u\n", static_cast<unsigned>(node->op.opcode));
            ASSERT((node->size & 1) == 0);
        }
        // Spread across the size and merge if an intersection encountered
        const size_t address = node->address;
        const auto size = node->size;
        for (size_t i = 0; i < size; i++) {
            auto *const ptr = _map[node->address + i];
            if (ptr != nullptr && ptr != node) {
                node = mergeNodes(node, ptr);
            }
            _map[address + i] = node;
        }
        at += node->size;
        // NOTE: There is not much information about a reference passed further,
        // so just don't add a reference of immediate if s.imm_labels is not
        // enabled.
        const bool has_ref1 = (node->ref_kinds & kRef1ImmMask)
            ? s.imm_labels
            : (node->ref_kinds & kRef1Mask);
        const bool has_code_ref1 = node->ref1_addr < code.size && has_ref1;
        if (has_code_ref1) {
            const NodeType type = (node->ref_kinds & (kRef1ReadMask | kRef1WriteMask))
                ? NodeType::kRefData : NodeType::kRefInstruction;
            const auto ref_type = ReferenceTypeFromRefKindMask1(node->ref_kinds);
            insertReferencedBy(node->address, node->ref1_addr, type, ref_type);
        }
        const bool has_ref2 = (node->ref_kinds & kRef2Mask);
        const bool has_code_ref2 = (has_ref2 && node->ref2_addr < code.size);
        if (has_code_ref2) {
            const NodeType type = (node->ref_kinds & (kRef2ReadMask | kRef2WriteMask))
                ? NodeType::kRefData : NodeType::kRefInstruction;
            const auto ref_type = ReferenceTypeFromRefKindMask2(node->ref_kinds);
            insertReferencedBy(node->address, node->ref2_addr, type, ref_type);
        }
    }
}

DisasmMap::~DisasmMap()
{
    ASSERT(_map != nullptr);
    for (size_t i = 0; i < kRomSizeBytes; i++) {
        auto *const node = _map[i];
        if (!node) {
            continue;
        }
        const auto size = node->size;
        for (size_t o = 0; o < size; o++) {
            ASSERT(_map[i + o] == node);
            _map[i + o] = nullptr;
        }
        delete node;
        i += size - 1;
    }
    free(_map);
    if (_symtab != nullptr) {
        free(_symtab);
    }
}