vm.fail
ACPI AML decompiler w/ CFG recovery and structured pseudocode
1#include "cf.h"
2
3#include "str.h"
4
5#include <stdio.h>
6#include <string.h>
7
8static int has_cfg_note(const tobi_ir *n, size_t off) {
9 for (size_t i = 0; i < n->child_len; i++) {
10 const tobi_ir *c = n->child[i];
11 if (c->kind == TOBI_IR_DIAG && c->off == off && c->str && strstr(c->str, "cfg fallback") != NULL) {
12 return 1;
13 }
14 }
15 return 0;
16}
17
18static int unclear_control(const tobi_ir *n) {
19 if (n->kind != TOBI_IR_UNKNOWN) {
20 return 0;
21 }
22 return n->raw_op == 0xa1u || n->raw_op == 0xccu || n->raw_op == 0x5b31u || n->raw_op == 0x5b32u || n->raw_op == 0u;
23}
24
25static void add_cfg_note(tobi_ir *parent, const tobi_ir *unknown) {
26 if (!parent || !unknown || has_cfg_note(parent, unknown->off)) {
27 return;
28 }
29 char msg[128];
30 (void)snprintf(msg, sizeof(msg), "cfg fallback label L_%04zx for unclear opcode 0x%x", unknown->off, unknown->raw_op);
31 tobi_ir *note = tobi_ir_new(TOBI_IR_DIAG, unknown->off, unknown->len);
32 note->raw_op = unknown->raw_op;
33 tobi_ir_set_name(note, "cfg");
34 tobi_ir_set_str(note, msg);
35 tobi_ir_add(parent, note);
36}
37
38static void add_diag_node(tobi_diag_list *diag, tobi_diag_level level, const tobi_ir *n, const char *msg) {
39 tobi_diag_add_source(diag, level, n ? n->off : 0, n ? n->source : NULL,
40 n ? n->input_index : 0, n ? n->has_source : 0, "%s", msg);
41}
42
43static void walk(tobi_ir *n, tobi_diag_list *diag, unsigned loop_depth) {
44 if (!n) {
45 return;
46 }
47 if (n->kind == TOBI_IR_IF && n->child_len < 2) {
48 add_diag_node(diag, TOBI_DIAG_ERROR, n, "if node lacks predicate or body");
49 }
50 if (n->kind == TOBI_IR_WHILE && n->child_len < 2) {
51 add_diag_node(diag, TOBI_DIAG_ERROR, n, "while node lacks predicate or body");
52 }
53 if ((n->kind == TOBI_IR_BREAK || n->kind == TOBI_IR_CONTINUE) && loop_depth == 0) {
54 tobi_diag_add_source(diag, TOBI_DIAG_WARN, n->off, n->source, n->input_index, n->has_source,
55 "%s outside loop kept as explicit statement",
56 n->kind == TOBI_IR_BREAK ? "break" : "continue");
57 }
58 size_t original_children = n->child_len;
59 unsigned child_loop_depth = loop_depth + (n->kind == TOBI_IR_WHILE ? 1u : 0u);
60 for (size_t i = 0; i < original_children; i++) {
61 if ((n->kind == TOBI_IR_BLOCK || n->kind == TOBI_IR_ROOT) && unclear_control(n->child[i])) {
62 add_cfg_note(n, n->child[i]);
63 }
64 walk(n->child[i], diag, child_loop_depth);
65 }
66}
67
68int tobi_cf_recover(tobi_ir *root, tobi_diag_list *diag) {
69 walk(root, diag, 0);
70 tobi_ir_assign_ids(root);
71 return !tobi_diag_has_error(diag);
72}
73
74static void dot_escape(tobi_sb *sb, const char *s) {
75 if (!s) {
76 return;
77 }
78 for (const char *p = s; *p; p++) {
79 if (*p == '"' || *p == '\\') {
80 tobi_sb_ch(sb, '\\');
81 }
82 if (*p == '\n' || *p == '\r') {
83 tobi_sb_ch(sb, ' ');
84 } else {
85 tobi_sb_ch(sb, *p);
86 }
87 }
88}
89
90typedef struct {
91 size_t stmt_next;
92 size_t edge_next;
93} dot_ctx;
94
95static size_t dot_stmt(tobi_sb *sb, const tobi_ir *n, dot_ctx *ctx);
96
97static void dot_edge(tobi_sb *sb, dot_ctx *ctx, size_t from, size_t to, const char *label) {
98 if (label && label[0]) {
99 size_t id = ctx->edge_next++;
100 tobi_sb_printf(sb, " e%zu [shape=box,style=\"solid\",", id);
101 tobi_sb_add(sb, "color=\"#000000\",fontcolor=\"#000000\",");
102 tobi_sb_add(sb, "fontname=\"Times-Roman\",fontsize=10,margin=\"0.06,0.03\",");
103 tobi_sb_add(sb, "height=0,width=0,label=\"");
104 dot_escape(sb, label);
105 tobi_sb_add(sb, "\"];\n");
106 tobi_sb_printf(sb, " n%zu -> e%zu [arrowhead=none, weight=2];\n", from, id);
107 tobi_sb_printf(sb, " e%zu -> n%zu [weight=2];\n", id, to);
108 return;
109 }
110 tobi_sb_printf(sb, " n%zu -> n%zu;\n", from, to);
111}
112
113static int dot_block(tobi_sb *sb, const tobi_ir *b, size_t owner, const char *edge_label, dot_ctx *ctx, size_t *last) {
114 if (!b) {
115 return 0;
116 }
117 size_t prev = owner;
118 int emitted = 0;
119 for (size_t i = 0; i < b->child_len; i++) {
120 size_t id = dot_stmt(sb, b->child[i], ctx);
121 dot_edge(sb, ctx, prev, id, i == 0 ? edge_label : "next");
122 prev = id;
123 emitted = 1;
124 }
125 if (last) {
126 *last = prev;
127 }
128 return emitted;
129}
130
131static size_t dot_stmt(tobi_sb *sb, const tobi_ir *n, dot_ctx *ctx) {
132 size_t id = ctx->stmt_next++;
133 tobi_sb_printf(sb, " n%zu [label=\"%s", id, tobi_ir_kind_name(n->kind));
134 if (n->name && n->name[0]) {
135 tobi_sb_add(sb, "\\n");
136 dot_escape(sb, n->name);
137 } else if (n->str && n->str[0]) {
138 tobi_sb_add(sb, "\\n");
139 dot_escape(sb, n->str);
140 }
141 tobi_sb_printf(sb, "\\noff=0x%zx", n->off);
142 if (n->kind == TOBI_IR_UNKNOWN) {
143 tobi_sb_printf(sb, "\\nop=0x%x", n->raw_op);
144 }
145 tobi_sb_add(sb, "\"];\n");
146 if (n->kind == TOBI_IR_METHOD && n->child_len > 0) {
147 (void)dot_block(sb, n->child[0], id, "entry", ctx, NULL);
148 } else if (n->kind == TOBI_IR_SCOPE || n->kind == TOBI_IR_DEVICE || n->kind == TOBI_IR_PROCESSOR) {
149 if (n->child_len > 0) {
150 (void)dot_block(sb, n->child[0], id, "body", ctx, NULL);
151 }
152 } else if (n->kind == TOBI_IR_IF) {
153 if (n->child_len > 1) {
154 (void)dot_block(sb, n->child[1], id, "then", ctx, NULL);
155 }
156 if (n->child_len > 2) {
157 (void)dot_block(sb, n->child[2], id, "else", ctx, NULL);
158 }
159 } else if (n->kind == TOBI_IR_WHILE) {
160 if (n->child_len > 1) {
161 size_t last = id;
162 if (dot_block(sb, n->child[1], id, "while-body", ctx, &last)) {
163 dot_edge(sb, ctx, last, id, "back");
164 }
165 }
166 }
167 return id;
168}
169
170char *tobi_cf_dot(const tobi_ir *root) {
171 tobi_sb sb;
172 tobi_sb_init(&sb);
173 tobi_sb_add(&sb, "digraph tobi_cfg {\n");
174 tobi_sb_add(&sb, " graph [rankdir=TB,bgcolor=\"#ffffff\",pad=0.18,nodesep=0.5,ranksep=0.72,");
175 tobi_sb_add(&sb, "splines=ortho,outputorder=edgesfirst];\n");
176 tobi_sb_add(&sb, " node [shape=box,style=\"solid\",color=\"#000000\",fontcolor=\"#000000\",");
177 tobi_sb_add(&sb, "fontname=\"Courier\",fontsize=12,margin=\"0.12,0.07\",penwidth=1.1];\n");
178 tobi_sb_add(&sb, " edge [color=\"#000000\",fontcolor=\"#000000\",arrowsize=0.75,penwidth=1.1];\n");
179 if (root) {
180 dot_ctx ctx = {0, 0};
181 size_t root_id = dot_stmt(&sb, root, &ctx);
182 size_t prev = root_id;
183 for (size_t i = 0; i < root->child_len; i++) {
184 size_t id = dot_stmt(&sb, root->child[i], &ctx);
185 dot_edge(&sb, &ctx, prev, id, i == 0 ? "entry" : "next");
186 prev = id;
187 }
188 }
189 tobi_sb_add(&sb, "}\n");
190 return tobi_sb_take(&sb);
191}