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_limited(tobi_sb *sb, const char *s, size_t wrap, size_t max) {
75 if (!s) {
76 return;
77 }
78 size_t col = 0;
79 size_t emitted = 0;
80 for (const char *p = s; *p; p++) {
81 if (max && emitted >= max) {
82 tobi_sb_add(sb, "\\n...");
83 return;
84 }
85 unsigned char c = (unsigned char)*p;
86 if (c == '\n' || c == '\r') {
87 tobi_sb_add(sb, "\\n");
88 col = 0;
89 continue;
90 }
91 if (wrap && col >= wrap) {
92 tobi_sb_add(sb, "\\n");
93 col = 0;
94 }
95 if (c == '"' || c == '\\') {
96 tobi_sb_ch(sb, '\\');
97 }
98 if (c < 0x20) {
99 tobi_sb_ch(sb, ' ');
100 } else {
101 tobi_sb_ch(sb, (char)c);
102 }
103 col++;
104 emitted++;
105 }
106}
107
108static void dot_escape(tobi_sb *sb, const char *s) {
109 dot_escape_limited(sb, s, 0, 0);
110}
111
112static void dot_label_text(tobi_sb *sb, const char *s) {
113 dot_escape_limited(sb, s, 28, 96);
114}
115
116typedef struct {
117 size_t stmt_next;
118 size_t edge_next;
119} dot_ctx;
120
121static size_t dot_stmt(tobi_sb *sb, const tobi_ir *n, dot_ctx *ctx);
122
123static void dot_edge(tobi_sb *sb, dot_ctx *ctx, size_t from, size_t to, const char *label) {
124 if (label && label[0]) {
125 size_t id = ctx->edge_next++;
126 tobi_sb_printf(sb, " e%zu [shape=box,style=\"solid\",", id);
127 tobi_sb_add(sb, "color=\"#000000\",fontcolor=\"#000000\",");
128 tobi_sb_add(sb, "fontname=\"Times-Roman\",fontsize=10,margin=\"0.06,0.03\",");
129 tobi_sb_add(sb, "height=0,width=0,label=\"");
130 dot_escape(sb, label);
131 tobi_sb_add(sb, "\"];\n");
132 tobi_sb_printf(sb, " n%zu -> e%zu [arrowhead=none, weight=2];\n", from, id);
133 tobi_sb_printf(sb, " e%zu -> n%zu [weight=2];\n", id, to);
134 return;
135 }
136 tobi_sb_printf(sb, " n%zu -> n%zu;\n", from, to);
137}
138
139static int dot_block(tobi_sb *sb, const tobi_ir *b, size_t owner, const char *edge_label, dot_ctx *ctx, size_t *last) {
140 if (!b) {
141 return 0;
142 }
143 size_t prev = owner;
144 int emitted = 0;
145 for (size_t i = 0; i < b->child_len; i++) {
146 size_t id = dot_stmt(sb, b->child[i], ctx);
147 dot_edge(sb, ctx, prev, id, i == 0 ? edge_label : "next");
148 prev = id;
149 emitted = 1;
150 }
151 if (last) {
152 *last = prev;
153 }
154 return emitted;
155}
156
157static void dot_ir_label(tobi_sb *sb, const tobi_ir *n) {
158 tobi_sb_add(sb, tobi_ir_kind_name(n->kind));
159 if (n->name && n->name[0]) {
160 tobi_sb_add(sb, "\\n");
161 dot_label_text(sb, n->name);
162 } else if (n->path && n->path[0]) {
163 tobi_sb_add(sb, "\\n");
164 dot_label_text(sb, n->path);
165 } else if (n->str && n->str[0]) {
166 tobi_sb_add(sb, "\\n");
167 dot_label_text(sb, n->str);
168 }
169 tobi_sb_printf(sb, "\\noff=0x%zx", n->off);
170 if (n->kind == TOBI_IR_UNKNOWN) {
171 tobi_sb_printf(sb, "\\nop=0x%x", n->raw_op);
172 }
173}
174
175static size_t dot_stmt(tobi_sb *sb, const tobi_ir *n, dot_ctx *ctx) {
176 size_t id = ctx->stmt_next++;
177 tobi_sb_printf(sb, " n%zu [label=\"", id);
178 dot_ir_label(sb, n);
179 tobi_sb_add(sb, "\"];\n");
180 if (n->kind == TOBI_IR_METHOD && n->child_len > 0) {
181 (void)dot_block(sb, n->child[0], id, "entry", ctx, NULL);
182 } else if (n->kind == TOBI_IR_SCOPE || n->kind == TOBI_IR_DEVICE || n->kind == TOBI_IR_PROCESSOR) {
183 if (n->child_len > 0) {
184 (void)dot_block(sb, n->child[0], id, "body", ctx, NULL);
185 }
186 } else if (n->kind == TOBI_IR_IF) {
187 if (n->child_len > 1) {
188 (void)dot_block(sb, n->child[1], id, "then", ctx, NULL);
189 }
190 if (n->child_len > 2) {
191 (void)dot_block(sb, n->child[2], id, "else", ctx, NULL);
192 }
193 } else if (n->kind == TOBI_IR_WHILE) {
194 if (n->child_len > 1) {
195 size_t last = id;
196 if (dot_block(sb, n->child[1], id, "while-body", ctx, &last)) {
197 dot_edge(sb, ctx, last, id, "back");
198 }
199 }
200 }
201 return id;
202}
203
204static void dot_common_attrs(tobi_sb *sb) {
205 tobi_sb_add(sb, " graph [rankdir=TB,bgcolor=\"#ffffff\",pad=0.18,nodesep=0.5,ranksep=0.72,");
206 tobi_sb_add(sb, "splines=ortho,outputorder=edgesfirst];\n");
207 tobi_sb_add(sb, " node [shape=box,style=\"solid\",color=\"#000000\",fontcolor=\"#000000\",");
208 tobi_sb_add(sb, "fontname=\"Courier\",fontsize=12,margin=\"0.12,0.07\",penwidth=1.1];\n");
209 tobi_sb_add(sb, " edge [color=\"#000000\",fontcolor=\"#000000\",arrowsize=0.75,penwidth=1.1];\n");
210}
211
212static char *dot_cfg(const tobi_ir *root) {
213 tobi_sb sb;
214 tobi_sb_init(&sb);
215 tobi_sb_add(&sb, "digraph tobi_cfg {\n");
216 dot_common_attrs(&sb);
217 if (root) {
218 dot_ctx ctx = {0, 0};
219 size_t root_id = dot_stmt(&sb, root, &ctx);
220 size_t prev = root_id;
221 for (size_t i = 0; i < root->child_len; i++) {
222 size_t id = dot_stmt(&sb, root->child[i], &ctx);
223 dot_edge(&sb, &ctx, prev, id, i == 0 ? "entry" : "next");
224 prev = id;
225 }
226 }
227 tobi_sb_add(&sb, "}\n");
228 return tobi_sb_take(&sb);
229}
230
231static size_t dot_ast_node(tobi_sb *sb, const tobi_ir *n, dot_ctx *ctx) {
232 size_t id = ctx->stmt_next++;
233 tobi_sb_printf(sb, " n%zu [label=\"", id);
234 dot_ir_label(sb, n);
235 tobi_sb_add(sb, "\"];\n");
236 for (size_t i = 0; i < n->child_len; i++) {
237 size_t child_id = dot_ast_node(sb, n->child[i], ctx);
238 tobi_sb_printf(sb, " n%zu -> n%zu;\n", id, child_id);
239 }
240 return id;
241}
242
243static char *dot_ast(const tobi_ir *root) {
244 tobi_sb sb;
245 tobi_sb_init(&sb);
246 tobi_sb_add(&sb, "digraph tobi_ast {\n");
247 dot_common_attrs(&sb);
248 if (root) {
249 dot_ctx ctx = {0, 0};
250 (void)dot_ast_node(&sb, root, &ctx);
251 }
252 tobi_sb_add(&sb, "}\n");
253 return tobi_sb_take(&sb);
254}
255
256static int ns_index(const tobi_ns *ns, const char *path, size_t *idx) {
257 if (!ns || !path) {
258 return 0;
259 }
260 for (size_t i = 0; i < ns->len; i++) {
261 if (ns->items[i].path && strcmp(ns->items[i].path, path) == 0) {
262 *idx = i;
263 return 1;
264 }
265 }
266 return 0;
267}
268
269static char *dot_namespace(const tobi_ns *ns) {
270 tobi_sb sb;
271 tobi_sb_init(&sb);
272 tobi_sb_add(&sb, "digraph tobi_namespace {\n");
273 dot_common_attrs(&sb);
274 tobi_sb_add(&sb, " n0 [label=\"namespace\\n\\\\\"];\n");
275 if (ns) {
276 for (size_t i = 0; i < ns->len; i++) {
277 const tobi_ns_ent *e = &ns->items[i];
278 tobi_sb_printf(&sb, " n%zu [label=\"%s", i + 1u, tobi_ns_kind_name(e->kind));
279 if (e->name && e->name[0]) {
280 tobi_sb_add(&sb, "\\n");
281 dot_label_text(&sb, e->name);
282 }
283 if (e->path && e->path[0]) {
284 tobi_sb_add(&sb, "\\n");
285 dot_label_text(&sb, e->path);
286 }
287 tobi_sb_printf(&sb, "\\noff=0x%zx\"];\n", e->off);
288 }
289 for (size_t i = 0; i < ns->len; i++) {
290 const tobi_ns_ent *e = &ns->items[i];
291 size_t parent = 0;
292 size_t found = 0;
293 if (e->owner && ns_index(ns, e->owner, &found)) {
294 parent = found + 1u;
295 }
296 tobi_sb_printf(&sb, " n%zu -> n%zu;\n", parent, i + 1u);
297 if (e->target && ns_index(ns, e->target, &found)) {
298 tobi_sb_printf(&sb, " n%zu -> n%zu [style=dashed,arrowhead=vee];\n", i + 1u, found + 1u);
299 }
300 }
301 }
302 tobi_sb_add(&sb, "}\n");
303 return tobi_sb_take(&sb);
304}
305
306char *tobi_cf_dot(const tobi_ir *root) {
307 return dot_cfg(root);
308}
309
310char *tobi_graph_dot(const tobi_ir *root, const tobi_ns *ns, tobi_graph_kind kind) {
311 switch (kind) {
312 case TOBI_GRAPH_AST:
313 return dot_ast(root);
314 case TOBI_GRAPH_NAMESPACE:
315 return dot_namespace(ns);
316 case TOBI_GRAPH_CFG:
317 default:
318 return dot_cfg(root);
319 }
320}