if_decompiler/
lib.rs

1/*
2
3if-decompiler - core library
4===============================
5
6Copyright (c) 2021 Dannii Willis
7MIT licenced
8https://github.com/curiousdannii/if-decompiler
9
10*/
11
12#![forbid(unsafe_code)]
13
14use std::collections::BTreeMap;
15
16use fnv::{FnvHashMap, FnvHashSet};
17use petgraph::{graph, visit};
18
19pub mod glulx;
20
21// Function data from an Inform debug file
22#[derive(Debug)]
23pub struct DebugFunctionData {
24    pub addr: u32,
25    pub len: u32,
26    pub name: String,
27}
28
29// Function safety refers to whether or not a function can be compiled and run without worrying about its locals and stack being part of the savestate
30// Unsafe functions need to be compiled such that they can be serialised and restored
31// UnsafeDynamicBranches functions have dynamic branches and need even more special care
32// SafetyTBD functions have not yet been determined. At the end of decompilation any remaining SafetyTBD functions will be assumed safe.
33#[derive(Copy, Clone, Debug, PartialEq)]
34pub enum FunctionSafety {
35    Unsafe,
36    UnsafeDynamicBranches,
37    SafetyTBD,
38}
39
40// Now a trait for generalising over our VMs
41pub trait VirtualMachine {
42    fn get_functions(&self) -> FnvHashMap<u32, FunctionSafety>;
43    fn mark_function_as_unsafe(&mut self, addr: u32);
44
45    fn mark_all_unsafe_functions(&mut self, edges: FnvHashSet<(u32, u32)>) {
46        let mut graph: graph::Graph<u32, ()> = graph::Graph::new();
47
48        // Add the graph nodes
49        let functions = self.get_functions();
50        let mut function_nodes = FnvHashMap::default();
51        let mut unsafe_functions = Vec::new();
52        for (addr, safety) in functions {
53            let node = graph.add_node(addr);
54            function_nodes.insert(addr, node);
55            if safety != FunctionSafety::SafetyTBD {
56                unsafe_functions.push(node);
57            }
58        }
59
60        // Then add the graph edges
61        graph.extend_with_edges(edges.iter().map(|(caller_addr, callee_addr)| {
62            let caller_node = function_nodes[caller_addr];
63            let callee_node = function_nodes[callee_addr];
64            // The direction must be callee->caller, as we'll change the caller's safety if the callee is unsafe
65            (callee_node, caller_node)
66        }));
67
68        // Now walk the function graph, marking each caller as Unsafe
69        let mut dfs = visit::Dfs::empty(&graph);
70        dfs.stack = unsafe_functions;
71        while let Some(node_index) = dfs.next(&graph) {
72            let addr = graph[node_index];
73            self.mark_function_as_unsafe(addr);
74        }
75    }
76}
77
78// Generic instruction functions
79pub trait VMInstruction {
80    fn addr(&self) -> u32;
81    fn does_halt(&self) -> bool;
82}
83
84// A generic basic block
85pub struct BasicBlock<I> {
86    pub label: u32,
87    pub code: Vec<I>,
88    pub branches: FnvHashSet<u32>,
89}
90
91// Calculate basic blocks
92pub fn calculate_basic_blocks<I: VMInstruction>(instructions: Vec<I>, entry_points: FnvHashSet<u32>, exit_branches: FnvHashMap<u32, Vec<u32>>) -> BTreeMap<u32, BasicBlock<I>> {
93    let mut blocks: BTreeMap<u32, BasicBlock<I>> = BTreeMap::new();
94    let mut current_block_addr = 0;
95    let mut last_instruction_halted = false;
96    for instruction in instructions {
97        let addr = instruction.addr();
98        // If we're in the middle of a block, see if we should add to it
99        if current_block_addr > 0 {
100            let current_block = blocks.get_mut(&current_block_addr).unwrap();
101            // Finish a previous block because this one starts a new one
102            if entry_points.contains(&addr) {
103                // Unless the last instruction halted, add this new instruction as a branch to the last block
104                if !last_instruction_halted {
105                    current_block.branches.insert(addr);
106                }
107                // Make a new block below
108            }
109            else {
110                // If this instruction branches, finish up the block
111                if let Some(branches) = exit_branches.get(&addr) {
112                    for branch in branches {
113                        current_block.branches.insert(*branch);
114                    }
115                    current_block_addr = 0;
116                }
117                // Add to the current block
118                last_instruction_halted = instruction.does_halt();
119                current_block.code.push(instruction);
120                // Continue so we don't make a new block
121                continue;
122            }
123        }
124        // Make a new block
125        current_block_addr = addr;
126        last_instruction_halted = instruction.does_halt();
127        let mut current_block = BasicBlock::<I> {
128            label: addr,
129            code: vec![instruction],
130            branches: FnvHashSet::default(),
131        };
132        // Add branches if we have any
133        if let Some(branches) = exit_branches.get(&addr) {
134            for branch in branches {
135                current_block.branches.insert(*branch);
136            }
137        }
138        blocks.insert(addr, current_block);
139    }
140    blocks
141}
142
143#[derive(Copy, Clone, Debug, PartialEq)]
144pub enum BranchTarget {
145    Dynamic,
146    Absolute(u32),
147    Return(u32),
148}
if_decompiler/lib.rs

if_decompiler/
lib.rs
