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
116static void dot_label_text_full(tobi_sb *sb, const char *s) {
117 dot_escape_limited(sb, s, 44, 0);
118}
119
120typedef struct {
121 size_t stmt_next;
122 size_t edge_next;
123 tobi_graph_labels labels;
124} dot_ctx;
125
126static size_t dot_stmt(tobi_sb *sb, const tobi_ir *n, dot_ctx *ctx);
127
128static void dot_edge(tobi_sb *sb, dot_ctx *ctx, size_t from, size_t to, const char *label) {
129 if (label && label[0]) {
130 size_t id = ctx->edge_next++;
131 tobi_sb_printf(sb, " e%zu [shape=box,style=\"solid\",", id);
132 tobi_sb_add(sb, "color=\"#000000\",fontcolor=\"#000000\",");
133 tobi_sb_add(sb, "fontname=\"Times-Roman\",fontsize=10,margin=\"0.06,0.03\",");
134 tobi_sb_add(sb, "height=0,width=0,label=\"");
135 dot_escape(sb, label);
136 tobi_sb_add(sb, "\"];\n");
137 tobi_sb_printf(sb, " n%zu -> e%zu [arrowhead=none, weight=2];\n", from, id);
138 tobi_sb_printf(sb, " e%zu -> n%zu [weight=2];\n", id, to);
139 return;
140 }
141 tobi_sb_printf(sb, " n%zu -> n%zu;\n", from, to);
142}
143
144static int dot_block(tobi_sb *sb, const tobi_ir *b, size_t owner, const char *edge_label, dot_ctx *ctx, size_t *last) {
145 if (!b) {
146 return 0;
147 }
148 size_t prev = owner;
149 int emitted = 0;
150 for (size_t i = 0; i < b->child_len; i++) {
151 size_t id = dot_stmt(sb, b->child[i], ctx);
152 dot_edge(sb, ctx, prev, id, i == 0 ? edge_label : "next");
153 prev = id;
154 emitted = 1;
155 }
156 if (last) {
157 *last = prev;
158 }
159 return emitted;
160}
161
162static void dot_label_value(tobi_sb *sb, const char *s, tobi_graph_labels labels) {
163 if (labels == TOBI_GRAPH_LABEL_FULL) {
164 dot_label_text_full(sb, s);
165 } else {
166 dot_label_text(sb, s);
167 }
168}
169
170static void dot_ir_label(tobi_sb *sb, const tobi_ir *n, tobi_graph_labels labels) {
171 if (labels == TOBI_GRAPH_LABEL_NONE) {
172 return;
173 }
174 tobi_sb_add(sb, tobi_ir_kind_name(n->kind));
175 if (n->name && n->name[0]) {
176 tobi_sb_add(sb, "\\n");
177 dot_label_value(sb, n->name, labels);
178 } else if (n->path && n->path[0]) {
179 tobi_sb_add(sb, "\\n");
180 dot_label_value(sb, n->path, labels);
181 } else if (n->str && n->str[0]) {
182 tobi_sb_add(sb, "\\n");
183 dot_label_value(sb, n->str, labels);
184 }
185 if (labels == TOBI_GRAPH_LABEL_FULL) {
186 if (n->path && n->path[0] && (!n->name || strcmp(n->name, n->path) != 0)) {
187 tobi_sb_add(sb, "\\npath=");
188 dot_label_value(sb, n->path, labels);
189 }
190 if (n->scope && n->scope[0]) {
191 tobi_sb_add(sb, "\\nscope=");
192 dot_label_value(sb, n->scope, labels);
193 }
194 if (n->target && n->target[0]) {
195 tobi_sb_add(sb, "\\ntarget=");
196 dot_label_value(sb, n->target, labels);
197 }
198 if (n->str && n->str[0] && (n->name || n->path)) {
199 tobi_sb_add(sb, "\\nstr=");
200 dot_label_value(sb, n->str, labels);
201 }
202 if (n->has_source && n->source) {
203 tobi_sb_add(sb, "\\nsource=");
204 dot_label_value(sb, n->source, labels);
205 }
206 if (n->value) {
207 tobi_sb_printf(sb, "\\nvalue=0x%llx", (unsigned long long)n->value);
208 }
209 if (n->bit_len || n->bit_off) {
210 tobi_sb_printf(sb, "\\nbits=%llu:%llu", (unsigned long long)n->bit_off,
211 (unsigned long long)n->bit_len);
212 }
213 }
214 tobi_sb_printf(sb, "\\noff=0x%zx", n->off);
215 if (labels == TOBI_GRAPH_LABEL_FULL) {
216 tobi_sb_printf(sb, "\\nlen=%zu", n->len);
217 }
218 if (n->kind == TOBI_IR_UNKNOWN) {
219 tobi_sb_printf(sb, "\\nop=0x%x", n->raw_op);
220 }
221}
222
223static size_t dot_stmt(tobi_sb *sb, const tobi_ir *n, dot_ctx *ctx) {
224 size_t id = ctx->stmt_next++;
225 tobi_sb_printf(sb, " n%zu [label=\"", id);
226 dot_ir_label(sb, n, ctx->labels);
227 tobi_sb_add(sb, "\"];\n");
228 if (n->kind == TOBI_IR_METHOD && n->child_len > 0) {
229 (void)dot_block(sb, n->child[0], id, "entry", ctx, NULL);
230 } else if (n->kind == TOBI_IR_SCOPE || n->kind == TOBI_IR_DEVICE || n->kind == TOBI_IR_PROCESSOR) {
231 if (n->child_len > 0) {
232 (void)dot_block(sb, n->child[0], id, "body", ctx, NULL);
233 }
234 } else if (n->kind == TOBI_IR_IF) {
235 if (n->child_len > 1) {
236 (void)dot_block(sb, n->child[1], id, "then", ctx, NULL);
237 }
238 if (n->child_len > 2) {
239 (void)dot_block(sb, n->child[2], id, "else", ctx, NULL);
240 }
241 } else if (n->kind == TOBI_IR_WHILE) {
242 if (n->child_len > 1) {
243 size_t last = id;
244 if (dot_block(sb, n->child[1], id, "while-body", ctx, &last)) {
245 dot_edge(sb, ctx, last, id, "back");
246 }
247 }
248 }
249 return id;
250}
251
252static void dot_common_attrs(tobi_sb *sb) {
253 tobi_sb_add(sb, " graph [rankdir=TB,bgcolor=\"#ffffff\",pad=0.18,nodesep=0.5,ranksep=0.72,");
254 tobi_sb_add(sb, "splines=ortho,outputorder=edgesfirst];\n");
255 tobi_sb_add(sb, " node [shape=box,style=\"solid\",color=\"#000000\",fontcolor=\"#000000\",");
256 tobi_sb_add(sb, "fontname=\"Courier\",fontsize=12,margin=\"0.12,0.07\",penwidth=1.1];\n");
257 tobi_sb_add(sb, " edge [color=\"#000000\",fontcolor=\"#000000\",arrowsize=0.75,penwidth=1.1];\n");
258}
259
260static char *dot_cfg(const tobi_ir *root, tobi_graph_labels labels) {
261 tobi_sb sb;
262 tobi_sb_init(&sb);
263 tobi_sb_add(&sb, "digraph tobi_cfg {\n");
264 dot_common_attrs(&sb);
265 if (root) {
266 dot_ctx ctx = {0, 0, labels};
267 size_t root_id = dot_stmt(&sb, root, &ctx);
268 size_t prev = root_id;
269 for (size_t i = 0; i < root->child_len; i++) {
270 size_t id = dot_stmt(&sb, root->child[i], &ctx);
271 dot_edge(&sb, &ctx, prev, id, i == 0 ? "entry" : "next");
272 prev = id;
273 }
274 }
275 tobi_sb_add(&sb, "}\n");
276 return tobi_sb_take(&sb);
277}
278
279static size_t dot_ast_node(tobi_sb *sb, const tobi_ir *n, dot_ctx *ctx) {
280 size_t id = ctx->stmt_next++;
281 tobi_sb_printf(sb, " n%zu [label=\"", id);
282 dot_ir_label(sb, n, ctx->labels);
283 tobi_sb_add(sb, "\"];\n");
284 for (size_t i = 0; i < n->child_len; i++) {
285 size_t child_id = dot_ast_node(sb, n->child[i], ctx);
286 tobi_sb_printf(sb, " n%zu -> n%zu;\n", id, child_id);
287 }
288 return id;
289}
290
291static char *dot_ast(const tobi_ir *root, tobi_graph_labels labels) {
292 tobi_sb sb;
293 tobi_sb_init(&sb);
294 tobi_sb_add(&sb, "digraph tobi_ast {\n");
295 dot_common_attrs(&sb);
296 if (root) {
297 dot_ctx ctx = {0, 0, labels};
298 (void)dot_ast_node(&sb, root, &ctx);
299 }
300 tobi_sb_add(&sb, "}\n");
301 return tobi_sb_take(&sb);
302}
303
304static int ns_index(const tobi_ns *ns, const char *path, size_t *idx) {
305 if (!ns || !path) {
306 return 0;
307 }
308 for (size_t i = 0; i < ns->len; i++) {
309 if (ns->items[i].path && strcmp(ns->items[i].path, path) == 0) {
310 *idx = i;
311 return 1;
312 }
313 }
314 return 0;
315}
316
317static int ns_index_n(const tobi_ns *ns, const char *path, size_t len, size_t *idx) {
318 if (!ns || !path) {
319 return 0;
320 }
321 for (size_t i = 0; i < ns->len; i++) {
322 const char *cur = ns->items[i].path;
323 if (cur && strlen(cur) == len && strncmp(cur, path, len) == 0) {
324 *idx = i;
325 return 1;
326 }
327 }
328 return 0;
329}
330
331static int ns_index_for_ir(const tobi_ns *ns, const tobi_ir *n, tobi_ns_kind kind, size_t *idx) {
332 if (!ns || !n) {
333 return 0;
334 }
335 if (n->path && ns_index(ns, n->path, idx)) {
336 return 1;
337 }
338 if (!n->name) {
339 return 0;
340 }
341 for (size_t i = 0; i < ns->len; i++) {
342 const tobi_ns_ent *e = &ns->items[i];
343 if (e->kind == kind && e->name && strcmp(e->name, n->name) == 0 && e->off == n->off) {
344 *idx = i;
345 return 1;
346 }
347 }
348 return 0;
349}
350
351static void dot_ns_edge(tobi_sb *sb, size_t *edge_next, size_t from, size_t to, const char *style,
352 const char *label, int constraint, tobi_graph_labels labels) {
353 const char *edge_style = style && style[0] ? style : "solid";
354 if (labels != TOBI_GRAPH_LABEL_NONE && label && label[0]) {
355 size_t id = (*edge_next)++;
356 tobi_sb_printf(sb, " r%zu [shape=box,style=\"solid\",", id);
357 tobi_sb_add(sb, "color=\"#000000\",fontcolor=\"#000000\",");
358 tobi_sb_add(sb, "fontname=\"Times-Roman\",fontsize=10,margin=\"0.06,0.03\",");
359 tobi_sb_add(sb, "height=0,width=0,label=\"");
360 dot_escape(sb, label);
361 tobi_sb_add(sb, "\"];\n");
362 tobi_sb_printf(sb, " n%zu -> r%zu [style=%s,arrowhead=none", from, id, edge_style);
363 if (!constraint) {
364 tobi_sb_add(sb, ",constraint=false");
365 }
366 tobi_sb_add(sb, "];\n");
367 tobi_sb_printf(sb, " r%zu -> n%zu [style=%s,arrowhead=vee", id, to, edge_style);
368 if (!constraint) {
369 tobi_sb_add(sb, ",constraint=false");
370 }
371 tobi_sb_add(sb, "];\n");
372 return;
373 }
374 tobi_sb_printf(sb, " n%zu -> n%zu [style=%s,arrowhead=vee", from, to, edge_style);
375 if (!constraint) {
376 tobi_sb_add(sb, ",constraint=false");
377 }
378 tobi_sb_add(sb, "];\n");
379}
380
381static int target_ns_index(const tobi_ns *ns, const char *target, const char *key, size_t *idx) {
382 if (!target || !key) {
383 return 0;
384 }
385 size_t key_len = strlen(key);
386 const char *p = target;
387 while ((p = strstr(p, key)) != NULL) {
388 if (p != target && p[-1] != ' ' && p[-1] != '\t') {
389 p += key_len;
390 continue;
391 }
392 const char *value = p + key_len;
393 const char *end = value;
394 while (*end && *end != ' ' && *end != '\t' && *end != '\n' && *end != '\r') {
395 end++;
396 }
397 if (end > value && ns_index_n(ns, value, (size_t)(end - value), idx)) {
398 return 1;
399 }
400 p = end;
401 }
402 return 0;
403}
404
405static void dot_namespace_field_edges(tobi_sb *sb, size_t *edge_next, const tobi_ns *ns,
406 const tobi_ir *n, tobi_graph_labels labels) {
407 static const struct {
408 const char *key;
409 const char *label;
410 } rels[] = {
411 {"region=", "region"},
412 {"index=", "index"},
413 {"data=", "data"},
414 {"bank=", "bank"}
415 };
416 size_t from = 0;
417 if (!ns_index_for_ir(ns, n, TOBI_NS_FIELD, &from)) {
418 return;
419 }
420 for (size_t i = 0; i < sizeof(rels) / sizeof(rels[0]); i++) {
421 size_t to = 0;
422 if (target_ns_index(ns, n->target, rels[i].key, &to)) {
423 dot_ns_edge(sb, edge_next, from + 1u, to + 1u, "dotted", rels[i].label, 0, labels);
424 }
425 }
426}
427
428static void dot_namespace_ir_edges(tobi_sb *sb, size_t *edge_next, const tobi_ir *n, const tobi_ns *ns,
429 size_t current_method, tobi_graph_labels labels) {
430 if (!n || !ns) {
431 return;
432 }
433 if (n->kind == TOBI_IR_METHOD && n->path) {
434 size_t found = 0;
435 if (ns_index(ns, n->path, &found)) {
436 current_method = found;
437 }
438 }
439 if (n->kind == TOBI_IR_CALL && current_method != (size_t)-1 && n->path) {
440 size_t target = 0;
441 if (ns_index(ns, n->path, &target) && target != current_method) {
442 dot_ns_edge(sb, edge_next, current_method + 1u, target + 1u, "dashed", "call", 0, labels);
443 }
444 } else if (n->kind == TOBI_IR_FIELD_ELEM) {
445 dot_namespace_field_edges(sb, edge_next, ns, n, labels);
446 }
447 for (size_t i = 0; i < n->child_len; i++) {
448 dot_namespace_ir_edges(sb, edge_next, n->child[i], ns, current_method, labels);
449 }
450}
451
452static char *dot_namespace(const tobi_ir *root, const tobi_ns *ns, tobi_graph_labels labels) {
453 tobi_sb sb;
454 tobi_sb_init(&sb);
455 tobi_sb_add(&sb, "digraph tobi_namespace {\n");
456 dot_common_attrs(&sb);
457 if (labels == TOBI_GRAPH_LABEL_NONE) {
458 tobi_sb_add(&sb, " n0 [label=\"\"];\n");
459 } else {
460 tobi_sb_add(&sb, " n0 [label=\"namespace\\n\\\\\"];\n");
461 }
462 if (ns) {
463 for (size_t i = 0; i < ns->len; i++) {
464 const tobi_ns_ent *e = &ns->items[i];
465 tobi_sb_printf(&sb, " n%zu [label=\"", i + 1u);
466 if (labels != TOBI_GRAPH_LABEL_NONE) {
467 tobi_sb_add(&sb, tobi_ns_kind_name(e->kind));
468 if (e->name && e->name[0]) {
469 tobi_sb_add(&sb, "\\n");
470 dot_label_value(&sb, e->name, labels);
471 }
472 if (e->path && e->path[0]) {
473 tobi_sb_add(&sb, "\\n");
474 dot_label_value(&sb, e->path, labels);
475 }
476 tobi_sb_printf(&sb, "\\noff=0x%zx", e->off);
477 if (labels == TOBI_GRAPH_LABEL_FULL) {
478 if (e->owner && e->owner[0]) {
479 tobi_sb_add(&sb, "\\nowner=");
480 dot_label_value(&sb, e->owner, labels);
481 }
482 if (e->target && e->target[0]) {
483 tobi_sb_add(&sb, "\\ntarget=");
484 dot_label_value(&sb, e->target, labels);
485 }
486 tobi_sb_printf(&sb, "\\nargs=%u flags=0x%x", e->args, e->flags);
487 if (e->external) {
488 tobi_sb_add(&sb, "\\nexternal=true");
489 }
490 if (e->has_region_range) {
491 tobi_sb_printf(&sb, "\\nregion=0x%llx+0x%llx",
492 (unsigned long long)e->region_offset,
493 (unsigned long long)e->region_len);
494 }
495 if (e->has_source && e->source) {
496 tobi_sb_add(&sb, "\\nsource=");
497 dot_label_value(&sb, e->source, labels);
498 }
499 }
500 }
501 tobi_sb_add(&sb, "\"");
502 if (e->external || e->kind == TOBI_NS_EXTERNAL) {
503 tobi_sb_add(&sb, ",style=\"dashed\"");
504 }
505 tobi_sb_add(&sb, "];\n");
506 }
507 size_t edge_next = 0;
508 for (size_t i = 0; i < ns->len; i++) {
509 const tobi_ns_ent *e = &ns->items[i];
510 size_t parent = 0;
511 size_t found = 0;
512 if (e->owner && ns_index(ns, e->owner, &found)) {
513 parent = found + 1u;
514 }
515 if (e->external || e->kind == TOBI_NS_EXTERNAL) {
516 dot_ns_edge(&sb, &edge_next, parent, i + 1u, "dotted", "external", 1, labels);
517 } else {
518 tobi_sb_printf(&sb, " n%zu -> n%zu;\n", parent, i + 1u);
519 }
520 if (e->target && ns_index(ns, e->target, &found)) {
521 dot_ns_edge(&sb, &edge_next, i + 1u, found + 1u, "dashed", "alias", 0, labels);
522 }
523 }
524 dot_namespace_ir_edges(&sb, &edge_next, root, ns, (size_t)-1, labels);
525 }
526 tobi_sb_add(&sb, "}\n");
527 return tobi_sb_take(&sb);
528}
529
530char *tobi_cf_dot(const tobi_ir *root) {
531 return dot_cfg(root, TOBI_GRAPH_LABEL_SHORT);
532}
533
534char *tobi_graph_dot(const tobi_ir *root, const tobi_ns *ns, tobi_graph_kind kind) {
535 return tobi_graph_dot_labels(root, ns, kind, TOBI_GRAPH_LABEL_SHORT);
536}
537
538char *tobi_graph_dot_labels(const tobi_ir *root, const tobi_ns *ns, tobi_graph_kind kind,
539 tobi_graph_labels labels) {
540 switch (kind) {
541 case TOBI_GRAPH_AST:
542 return dot_ast(root, labels);
543 case TOBI_GRAPH_NAMESPACE:
544 return dot_namespace(root, ns, labels);
545 case TOBI_GRAPH_CFG:
546 default:
547 return dot_cfg(root, labels);
548 }
549}