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 char *dot_namespace(const tobi_ns *ns, tobi_graph_labels labels) {
318 tobi_sb sb;
319 tobi_sb_init(&sb);
320 tobi_sb_add(&sb, "digraph tobi_namespace {\n");
321 dot_common_attrs(&sb);
322 if (labels == TOBI_GRAPH_LABEL_NONE) {
323 tobi_sb_add(&sb, " n0 [label=\"\"];\n");
324 } else {
325 tobi_sb_add(&sb, " n0 [label=\"namespace\\n\\\\\"];\n");
326 }
327 if (ns) {
328 for (size_t i = 0; i < ns->len; i++) {
329 const tobi_ns_ent *e = &ns->items[i];
330 tobi_sb_printf(&sb, " n%zu [label=\"", i + 1u);
331 if (labels != TOBI_GRAPH_LABEL_NONE) {
332 tobi_sb_add(&sb, tobi_ns_kind_name(e->kind));
333 if (e->name && e->name[0]) {
334 tobi_sb_add(&sb, "\\n");
335 dot_label_value(&sb, e->name, labels);
336 }
337 if (e->path && e->path[0]) {
338 tobi_sb_add(&sb, "\\n");
339 dot_label_value(&sb, e->path, labels);
340 }
341 tobi_sb_printf(&sb, "\\noff=0x%zx", e->off);
342 if (labels == TOBI_GRAPH_LABEL_FULL) {
343 if (e->owner && e->owner[0]) {
344 tobi_sb_add(&sb, "\\nowner=");
345 dot_label_value(&sb, e->owner, labels);
346 }
347 if (e->target && e->target[0]) {
348 tobi_sb_add(&sb, "\\ntarget=");
349 dot_label_value(&sb, e->target, labels);
350 }
351 tobi_sb_printf(&sb, "\\nargs=%u flags=0x%x", e->args, e->flags);
352 if (e->external) {
353 tobi_sb_add(&sb, "\\nexternal=true");
354 }
355 if (e->has_region_range) {
356 tobi_sb_printf(&sb, "\\nregion=0x%llx+0x%llx",
357 (unsigned long long)e->region_offset,
358 (unsigned long long)e->region_len);
359 }
360 if (e->has_source && e->source) {
361 tobi_sb_add(&sb, "\\nsource=");
362 dot_label_value(&sb, e->source, labels);
363 }
364 }
365 }
366 tobi_sb_add(&sb, "\"];\n");
367 }
368 for (size_t i = 0; i < ns->len; i++) {
369 const tobi_ns_ent *e = &ns->items[i];
370 size_t parent = 0;
371 size_t found = 0;
372 if (e->owner && ns_index(ns, e->owner, &found)) {
373 parent = found + 1u;
374 }
375 tobi_sb_printf(&sb, " n%zu -> n%zu;\n", parent, i + 1u);
376 if (e->target && ns_index(ns, e->target, &found)) {
377 tobi_sb_printf(&sb, " n%zu -> n%zu [style=dashed,arrowhead=vee];\n", i + 1u, found + 1u);
378 }
379 }
380 }
381 tobi_sb_add(&sb, "}\n");
382 return tobi_sb_take(&sb);
383}
384
385char *tobi_cf_dot(const tobi_ir *root) {
386 return dot_cfg(root, TOBI_GRAPH_LABEL_SHORT);
387}
388
389char *tobi_graph_dot(const tobi_ir *root, const tobi_ns *ns, tobi_graph_kind kind) {
390 return tobi_graph_dot_labels(root, ns, kind, TOBI_GRAPH_LABEL_SHORT);
391}
392
393char *tobi_graph_dot_labels(const tobi_ir *root, const tobi_ns *ns, tobi_graph_kind kind,
394 tobi_graph_labels labels) {
395 switch (kind) {
396 case TOBI_GRAPH_AST:
397 return dot_ast(root, labels);
398 case TOBI_GRAPH_NAMESPACE:
399 return dot_namespace(ns, labels);
400 case TOBI_GRAPH_CFG:
401 default:
402 return dot_cfg(root, labels);
403 }
404}