1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/sourcepawn/decompiler/code_analyzer.cpp Tue Sep 23 21:20:40 2008 -0700
1.3 @@ -0,0 +1,1142 @@
1.4 +#include <assert.h>
1.5 +#include <string.h>
1.6 +#include <stdlib.h>
1.7 +#include "decompiler.h"
1.8 +#include "code_analyzer.h"
1.9 +#include "platform_util.h"
1.10 +
1.11 +struct Block;
1.12 +
1.13 +#define PCM_BRANCH_TARGET (1<<0)
1.14 +#define PCM_OPCODE (1<<1)
1.15 +#define PCM_HAS_BLOCK (1<<2)
1.16 +#define PCM_NUM_BITS 3
1.17 +
1.18 +#define NEXT_OP(cip, op) cip += (dc->opdef[op].params + 1) * sizeof(cell_t)
1.19 +
1.20 +struct Edge
1.21 +{
1.22 + Edge *next;
1.23 + Block *target;
1.24 + uint32_t ip;
1.25 +};
1.26 +
1.27 +struct Block
1.28 +{
1.29 + cell_t ip_start;
1.30 + cell_t ip_end;
1.31 + Edge *edge_list;
1.32 + Edge *final_edge;
1.33 + Block *next_in_table;
1.34 +};
1.35 +
1.36 +struct ControlFlowGraph
1.37 +{
1.38 + int err;
1.39 + unsigned int max_blocks;
1.40 + unsigned int max_edges;
1.41 + unsigned int used_blocks;
1.42 + unsigned int used_edges;
1.43 + Block *blocks;
1.44 + Edge *edges;
1.45 + Block *entry;
1.46 + FunctionInfo *func;
1.47 +};
1.48 +
1.49 +static FunctionInfo *sp_InferFuncPrototype(sp_decomp_t *dc, uint32_t code_addr, bool is_public)
1.50 +{
1.51 + sp_tag_t *pTag;
1.52 + sp_file_t *plugin;
1.53 + FunctionInfo *info;
1.54 + sp_fdbg_symbol_t *sym;
1.55 +
1.56 + plugin = dc->plugin;
1.57 + info = new FunctionInfo;
1.58 + memset(info, 0, sizeof(FunctionInfo));
1.59 +
1.60 + info->code_addr = code_addr;
1.61 +
1.62 + if ((sym = Sp_FindFunctionSym(plugin, code_addr)) != NULL)
1.63 + {
1.64 + Sp_Format(info->name, sizeof(info->name), "%s", plugin->debug.stringbase + sym->name);
1.65 + if (sym->tagid != 0)
1.66 + {
1.67 + info->tag = Sp_FindTag(plugin, sym->tagid);
1.68 + }
1.69 + }
1.70 + else
1.71 + {
1.72 + Sp_Format(info->name, sizeof(info->name), "function_%x", code_addr);
1.73 + for (uint32_t i = 0; i < plugin->num_publics; i++)
1.74 + {
1.75 + if (plugin->publics[i].code_offs == code_addr)
1.76 + {
1.77 + Sp_Format(info->name,
1.78 + sizeof(info->name),
1.79 + "%s",
1.80 + plugin->publics[i].name);
1.81 + break;
1.82 + }
1.83 + }
1.84 + }
1.85 + info->sym = sym;
1.86 + info->is_public = is_public;
1.87 +
1.88 +
1.89 + /* Search for all locals */
1.90 + {
1.91 + uint32_t i;
1.92 + uint8_t *cursor;
1.93 +
1.94 + cursor = (uint8_t *)plugin->debug.symbols;
1.95 + for (i = 0; i < plugin->debug.syms_num; i++)
1.96 + {
1.97 + sym = (sp_fdbg_symbol_t *)cursor;
1.98 +
1.99 + if (sym->ident == SP_SYM_VARIABLE
1.100 + || sym->ident == SP_SYM_REFARRAY
1.101 + || sym->ident == SP_SYM_REFERENCE
1.102 + || sym->ident == SP_SYM_ARRAY)
1.103 + {
1.104 + if (code_addr >= sym->codestart
1.105 + && code_addr < sym->codeend
1.106 + && sym->addr >= 0xC
1.107 + && (sym->addr & 0x3) == 0
1.108 + && ((sym->addr - 0xC) >> 2) < SP_MAX_EXEC_PARAMS
1.109 + && sym->vclass == 1)
1.110 + {
1.111 + unsigned int num;
1.112 +
1.113 + num = (sym->addr - 0xC) >> 2;
1.114 + info->known_args[num].sym = sym;
1.115 + if (num + 1 > info->num_known_args)
1.116 + {
1.117 + info->num_known_args = num + 1;
1.118 + }
1.119 + }
1.120 + }
1.121 +
1.122 + cursor += sizeof(sp_fdbg_symbol_t);
1.123 + if (sym->dimcount > 0)
1.124 + {
1.125 + cursor += sizeof(sp_fdbg_arraydim_t) * sym->dimcount;
1.126 + }
1.127 + }
1.128 + }
1.129 +
1.130 + /* Map all arguments into place. */
1.131 + for (unsigned int i = 0; i < info->num_known_args; i++)
1.132 + {
1.133 + if ((sym = info->known_args[i].sym) == NULL)
1.134 + {
1.135 + continue;
1.136 + }
1.137 + if (sym->tagid != 0 && (pTag = Sp_FindTag(plugin, sym->tagid)) != NULL)
1.138 + {
1.139 + info->known_args[i].tag = pTag;
1.140 + }
1.141 + info->known_args[i].name = plugin->debug.stringbase + sym->name;
1.142 +
1.143 + if (sym->dimcount > 0)
1.144 + {
1.145 + info->known_args[i].dims =
1.146 + (sp_fdbg_arraydim_t *)((char *)sym + sizeof(sp_fdbg_symbol_t));
1.147 + }
1.148 + }
1.149 +
1.150 + return info;
1.151 +}
1.152 +
1.153 +static FunctionInfo *sp_GetFuncPrototype(sp_decomp_t *dc,
1.154 + uint32_t code_addr,
1.155 + bool known,
1.156 + bool is_public = false);
1.157 +static FunctionInfo *sp_GetFuncPrototype(sp_decomp_t *dc,
1.158 + uint32_t code_addr,
1.159 + bool known,
1.160 + bool is_public)
1.161 +{
1.162 + FunctionInfo *func;
1.163 +
1.164 + func = dc->funcs;
1.165 + while (func != NULL)
1.166 + {
1.167 + if (func->code_addr == code_addr)
1.168 + {
1.169 + return func;
1.170 + }
1.171 + func = func->next;
1.172 + }
1.173 +
1.174 + /* See if this is public. */
1.175 + if (!known)
1.176 + {
1.177 + is_public = false;
1.178 + for (unsigned int i = 0; i < dc->plugin->num_publics; i++)
1.179 + {
1.180 + if (dc->plugin->publics[i].code_offs == code_addr)
1.181 + {
1.182 + is_public = true;
1.183 + break;
1.184 + }
1.185 + }
1.186 + }
1.187 +
1.188 + func = sp_InferFuncPrototype(dc, code_addr, is_public);
1.189 + func->next = dc->funcs;
1.190 + dc->funcs = func;
1.191 +
1.192 + return func;
1.193 +}
1.194 +
1.195 +static void sp_CacheLocals(sp_decomp_t *dc, FunctionInfo *info)
1.196 +{
1.197 + sp_file_t *plugin;
1.198 + sp_fdbg_symbol_t *sym;
1.199 +
1.200 + plugin = dc->plugin;
1.201 +
1.202 + /* Search for all locals */
1.203 + {
1.204 + uint32_t i;
1.205 + uint8_t *cursor;
1.206 +
1.207 + cursor = (uint8_t *)plugin->debug.symbols;
1.208 + for (i = 0; i < plugin->debug.syms_num; i++)
1.209 + {
1.210 + sym = (sp_fdbg_symbol_t *)cursor;
1.211 +
1.212 + if ((sym->codestart >= info->code_addr && sym->codestart < info->code_end)
1.213 + && (sym->codeend <= info->code_end && sym->codeend >= info->code_addr)
1.214 + && sym->vclass == 1)
1.215 + {
1.216 + info->num_known_vars++;
1.217 + }
1.218 +
1.219 + cursor += sizeof(sp_fdbg_symbol_t);
1.220 + if (sym->dimcount > 0)
1.221 + {
1.222 + cursor += sizeof(sp_fdbg_arraydim_t) * sym->dimcount;
1.223 + }
1.224 + }
1.225 + }
1.226 +
1.227 + /* Map all locals into place. */
1.228 + if (info->num_known_vars)
1.229 + {
1.230 + uint32_t i, num;
1.231 + uint8_t *cursor;
1.232 +
1.233 + num = 0;
1.234 + info->known_vars = new FuncVar[info->num_known_vars];
1.235 + memset(info->known_vars, 0, sizeof(FuncVar) * info->num_known_vars);
1.236 +
1.237 + cursor = (uint8_t *)plugin->debug.symbols;
1.238 + for (i = 0; i < plugin->debug.syms_num; i++)
1.239 + {
1.240 + sym = (sp_fdbg_symbol_t *)cursor;
1.241 +
1.242 + if (sym->ident == SP_SYM_VARIABLE
1.243 + || sym->ident == SP_SYM_REFARRAY
1.244 + || sym->ident == SP_SYM_REFERENCE
1.245 + || sym->ident == SP_SYM_ARRAY)
1.246 + {
1.247 + /* Detect all function variables. */
1.248 + if ((sym->codestart >= info->code_addr && sym->codestart < info->code_end)
1.249 + && (sym->codeend <= info->code_end && sym->codeend >= info->code_addr)
1.250 + && sym->vclass == 1)
1.251 + {
1.252 + assert(num < info->num_known_vars);
1.253 + info->known_vars[num].sym = sym;
1.254 + info->known_vars[num].name = plugin->debug.stringbase + sym->name;
1.255 + info->known_vars[num].tag =
1.256 + (sym->tagid == 0) ? NULL : Sp_FindTag(plugin, sym->tagid);
1.257 + info->known_vars[num].dims =
1.258 + (sym->dimcount == 0)
1.259 + ? NULL
1.260 + : (sp_fdbg_arraydim_t *)(cursor + sizeof(sp_fdbg_symbol_t));
1.261 + num++;
1.262 + }
1.263 + }
1.264 +
1.265 + cursor += sizeof(sp_fdbg_symbol_t);
1.266 + if (sym->dimcount > 0)
1.267 + {
1.268 + cursor += sizeof(sp_fdbg_arraydim_t) * sym->dimcount;
1.269 + }
1.270 + }
1.271 +
1.272 + assert(num == info->num_known_vars);
1.273 + }
1.274 +}
1.275 +
1.276 +static void sp_PrintFunctionPrototype(PrintBuffer *printer, sp_decomp_t *dc, FunctionInfo *func)
1.277 +{
1.278 + FuncVar *var;
1.279 +
1.280 + if (func->is_public)
1.281 + {
1.282 + printer->Append("public ");
1.283 + }
1.284 + if (func->tag != NULL)
1.285 + {
1.286 + printer->Append("%s:", func->tag->name);
1.287 + }
1.288 + printer->Append("%s(", func->name);
1.289 +
1.290 + for (unsigned int i = 0; i < func->num_known_args; i++)
1.291 + {
1.292 + var = &func->known_args[i];
1.293 + if (var->sym == NULL)
1.294 + {
1.295 + printer->Append("unknown_arg_%d%s, ", i, i == func->num_known_args - 1 ? "" : ",");
1.296 + continue;
1.297 + }
1.298 + if (var->sym->ident == SP_SYM_REFERENCE)
1.299 + {
1.300 + printer->Append("&");
1.301 + }
1.302 + if (var->tag != NULL)
1.303 + {
1.304 + printer->Append("%s:", var->tag->name);
1.305 + }
1.306 + printer->Append("%s", var->name);
1.307 +
1.308 + if (var->sym->dimcount > 0)
1.309 + {
1.310 + sp_fdbg_arraydim_t *dims =
1.311 + (sp_fdbg_arraydim_t *)((char *)var->sym + sizeof(sp_fdbg_symbol_t));
1.312 +
1.313 + for (uint16_t j = 0; j < var->sym->dimcount; j++)
1.314 + {
1.315 + if (dims[j].size == 0)
1.316 + {
1.317 + printer->Append("[]");
1.318 + }
1.319 + else
1.320 + {
1.321 + printer->Append("[%d]", dims[j].size);
1.322 + }
1.323 + }
1.324 + }
1.325 +
1.326 + if (i != func->num_known_args - 1)
1.327 + {
1.328 + printer->Append(", ");
1.329 + }
1.330 + }
1.331 +
1.332 + printer->Append(")");
1.333 +}
1.334 +
1.335 +void sp_DebugExprTree(PrintBuffer *buffer, BaseNode *node, bool is_stmt=false)
1.336 +{
1.337 + switch (node->op)
1.338 + {
1.339 + case OP_CALL:
1.340 + {
1.341 + CallNode *call = (CallNode *)node;
1.342 +
1.343 + buffer->Append("%s(", call->func->name);
1.344 + for (unsigned int i = 0; i < call->argc; i++)
1.345 + {
1.346 + sp_DebugExprTree(buffer, call->args[i], false);
1.347 + }
1.348 + buffer->Append(")");
1.349 + break;
1.350 + }
1.351 + case _OP_VAR:
1.352 + {
1.353 + VarNode *var_node = (VarNode *)node;
1.354 + buffer->Append("%s", var_node->var->name);
1.355 + break;
1.356 + }
1.357 + case _OP_NEW:
1.358 + {
1.359 + DeclNode *d_node = (DeclNode *)node;
1.360 +
1.361 + if (d_node->expr == NULL)
1.362 + {
1.363 + buffer->Append("decl ");
1.364 + sp_DebugExprTree(buffer, d_node->var, true);
1.365 + }
1.366 + else
1.367 + {
1.368 + buffer->Append("new ");
1.369 + sp_DebugExprTree(buffer, d_node->var, true);
1.370 + buffer->Append(" = ");
1.371 + sp_DebugExprTree(buffer, d_node->expr, true);
1.372 + }
1.373 +
1.374 + break;
1.375 + }
1.376 + case _OP_STMT:
1.377 + case OP_RETN:
1.378 + {
1.379 + StmtNode *u_node = (StmtNode *)node;
1.380 +
1.381 + while (u_node != NULL)
1.382 + {
1.383 + buffer->Append("\t");
1.384 + if (u_node->op == OP_RETN)
1.385 + {
1.386 + buffer->Append("return ");
1.387 + }
1.388 + sp_DebugExprTree(buffer, u_node->node, true);
1.389 + buffer->Append(";\n");
1.390 + u_node = u_node->next;
1.391 + }
1.392 + break;
1.393 + }
1.394 + case _OP_CONST:
1.395 + {
1.396 + ConstNode *c_node = (ConstNode *)node;
1.397 +
1.398 + buffer->Append("%d", c_node->val);
1.399 +
1.400 + break;
1.401 + }
1.402 + case OP_ADD:
1.403 + case OP_ADD_C:
1.404 + case OP_SMUL:
1.405 + case OP_SMUL_C:
1.406 + case OP_SDIV:
1.407 + case OP_SUB_ALT:
1.408 + case _OP_STORE:
1.409 + case _OP_MODULO:
1.410 + {
1.411 + BinOpNode *bin_node = (BinOpNode *)node;
1.412 +
1.413 + if (!is_stmt)
1.414 + {
1.415 + buffer->Append("(");
1.416 + }
1.417 + sp_DebugExprTree(buffer, bin_node->left);
1.418 +
1.419 + switch (node->op)
1.420 + {
1.421 + case OP_ADD:
1.422 + case OP_ADD_C:
1.423 + {
1.424 + buffer->Append(" + ");
1.425 + break;
1.426 + }
1.427 + case OP_SMUL:
1.428 + case OP_SMUL_C:
1.429 + {
1.430 + buffer->Append(" * ");
1.431 + break;
1.432 + }
1.433 + case _OP_STORE:
1.434 + {
1.435 + buffer->Append(" = ");
1.436 + break;
1.437 + }
1.438 + case OP_SUB_ALT:
1.439 + {
1.440 + buffer->Append(" - ");
1.441 + break;
1.442 + }
1.443 + case OP_SDIV:
1.444 + {
1.445 + buffer->Append(" / ");
1.446 + break;
1.447 + }
1.448 + case _OP_MODULO:
1.449 + {
1.450 + buffer->Append(" % ");
1.451 + break;
1.452 + }
1.453 + }
1.454 +
1.455 + sp_DebugExprTree(buffer, bin_node->right, node->op == _OP_STORE);
1.456 + if (!is_stmt)
1.457 + {
1.458 + buffer->Append(")");
1.459 + }
1.460 +
1.461 + break;
1.462 + }
1.463 + }
1.464 +}
1.465 +
1.466 +void sp_DebugPrint(FunctionInfo *info, sp_decomp_t *dc, BaseNode *node)
1.467 +{
1.468 + PrintBuffer buffer;
1.469 +
1.470 + sp_PrintFunctionPrototype(&buffer, dc, info);
1.471 + buffer.Append("\n{\n");
1.472 + sp_DebugExprTree(&buffer, node, true);
1.473 + buffer.Append("}\n");
1.474 + buffer.Dump(stdout);
1.475 +}
1.476 +
1.477 +#define PCODE_VAL(pcode, offs) *(cell_t *)((char *)(pcode)+(offs))
1.478 +#define PCODE_PARAM(pcode, offs, num) *(cell_t *)((char *)(pcode)+(offs)+((num)*sizeof(cell_t)))
1.479 +
1.480 +FuncVar *sp_FindGraphVar(FunctionInfo *func, ucell_t cip, cell_t sp, cell_t stack)
1.481 +{
1.482 + if (stack >= 0xC)
1.483 + {
1.484 + if ((stack & 0x3) != 0)
1.485 + {
1.486 + return NULL;
1.487 + }
1.488 + stack -= 0xC;
1.489 + stack >>= 2;
1.490 + if (stack >= SP_MAX_EXEC_PARAMS)
1.491 + {
1.492 + return NULL;
1.493 + }
1.494 + if (func->known_args[stack].sym == NULL)
1.495 + {
1.496 + return NULL;
1.497 + }
1.498 + return &func->known_args[stack];
1.499 + }
1.500 + else if (stack < 0)
1.501 + {
1.502 + FuncVar *var;
1.503 +
1.504 + if (stack < sp)
1.505 + {
1.506 + return NULL;
1.507 + }
1.508 +
1.509 + for (unsigned int i = 0; i < func->num_known_vars; i++)
1.510 + {
1.511 + var = &func->known_vars[i];
1.512 +
1.513 + if (cip >= var->sym->codestart
1.514 + && cip <= var->sym->codeend
1.515 + && stack == var->sym->addr)
1.516 + {
1.517 + return var;
1.518 + }
1.519 + }
1.520 +
1.521 + return NULL;
1.522 + }
1.523 + else
1.524 + {
1.525 + return NULL;
1.526 + }
1.527 +}
1.528 +
1.529 +#define CHECK_VALUE(v) \
1.530 + assert(v != NULL); \
1.531 + if (v == NULL) { \
1.532 + err = SP_ERROR_INVALID_INSTRUCTION; \
1.533 + goto return_error; \
1.534 + }
1.535 +
1.536 +void *operator new(size_t size, ControlFlowGraph *graph)
1.537 +{
1.538 + return malloc(size);
1.539 +}
1.540 +
1.541 +void *operator new[](size_t size, ControlFlowGraph *graph)
1.542 +{
1.543 + return malloc(size);
1.544 +}
1.545 +
1.546 +void operator delete(void *mem, ControlFlowGraph *graph)
1.547 +{
1.548 + free(mem);
1.549 +}
1.550 +
1.551 +void operator delete[](void *mem, ControlFlowGraph *graph)
1.552 +{
1.553 + free(mem);
1.554 +}
1.555 +
1.556 +#define MAX_STACK_ENTRIES 256
1.557 +
1.558 +struct StackEntry
1.559 +{
1.560 + StackEntry()
1.561 + {
1.562 + }
1.563 + StackEntry(cell_t d, BaseNode *e) : depth(d), expr(e)
1.564 + {
1.565 + }
1.566 + cell_t depth;
1.567 + BaseNode *expr;
1.568 +};
1.569 +
1.570 +int sp_AnalyzeGraph(sp_decomp_t *dc, ControlFlowGraph *graph)
1.571 +{
1.572 + int err;
1.573 + cell_t sp;
1.574 + Block *block;
1.575 + cell_t *pcode;
1.576 + cell_t cip, cip_end;
1.577 + StmtNode *root, *rtemp;
1.578 + StmtNode *root_tail;
1.579 + BaseNode *pri, *alt;
1.580 + FunctionInfo *func, *tfunc;
1.581 + cell_t p1, p2, op;
1.582 + FuncVar *v1, *v2;
1.583 + unsigned int stack_entries = 0;
1.584 + StackEntry eval_stack[MAX_STACK_ENTRIES];
1.585 +
1.586 + /* Init everything.
1.587 + * Stack pointer starts off at 0.
1.588 + */
1.589 + sp = 0;
1.590 + pri = NULL;
1.591 + alt = NULL;
1.592 + root = NULL;
1.593 + func = graph->func;
1.594 + block = graph->entry;
1.595 + pcode = (cell_t *)dc->plugin->pcode;
1.596 +
1.597 + cip = block->ip_start;
1.598 + cip_end = block->ip_end;
1.599 +
1.600 + root_tail = root = new (graph) StmtNode(_OP_STMT, NULL, NULL);
1.601 +
1.602 + while (cip < cip_end)
1.603 + {
1.604 + op = PCODE_VAL(pcode, cip);
1.605 +
1.606 + switch (op)
1.607 + {
1.608 + case OP_PROC:
1.609 + case OP_BREAK:
1.610 + {
1.611 + break;
1.612 + }
1.613 + case OP_CALL:
1.614 + {
1.615 + p1 = PCODE_PARAM(pcode, cip, 1);
1.616 + tfunc = sp_GetFuncPrototype(dc, p1, false);
1.617 + CHECK_VALUE(tfunc);
1.618 +
1.619 + /* Sanity checks, :TODO: runtime checks later. */
1.620 + assert(stack_entries >= 1);
1.621 +
1.622 + ConstNode *cnode;
1.623 + cnode = (ConstNode *)eval_stack[stack_entries-1].expr;
1.624 + stack_entries--;
1.625 +
1.626 + /* Sanity checks, :TODO: runtime checks later. */
1.627 + assert(cnode->op == _OP_CONST);
1.628 + assert(cnode->val >= 0);
1.629 + assert(cnode->val == tfunc->num_known_args);
1.630 + assert(unsigned int(cnode->val) <= stack_entries);
1.631 +
1.632 + cell_t argc = cnode->val;
1.633 + BaseNode **nodes = new (graph) BaseNode *[cnode->val];
1.634 + for (cell_t argno = 0; argno < cnode->val; argno++, stack_entries--)
1.635 + {
1.636 + nodes[argno] = eval_stack[stack_entries-1].expr;
1.637 + }
1.638 +
1.639 + sp += (cnode->val + 1) * sizeof(cell_t);
1.640 + assert(sp <= 0);
1.641 +
1.642 + pri = new (graph) CallNode(tfunc, nodes, cnode->val);
1.643 +
1.644 + break;
1.645 + }
1.646 + case OP_CONST_PRI:
1.647 + {
1.648 + p1 = PCODE_PARAM(pcode, cip, 1);
1.649 + pri = new (graph) ConstNode(p1);
1.650 + break;
1.651 + }
1.652 + case OP_PUSH_C:
1.653 + {
1.654 + p1 = PCODE_PARAM(pcode, cip, 1);
1.655 +
1.656 + /* Adjust stack pointer. */
1.657 + sp -= sizeof(cell_t);
1.658 +
1.659 + if ((v1 = sp_FindGraphVar(func, cip, sp, sp)) == NULL)
1.660 + {
1.661 + /* Add a new stack entry. */
1.662 + assert(stack_entries < MAX_STACK_ENTRIES);
1.663 + eval_stack[stack_entries++] = StackEntry(sp, new ConstNode(p1));
1.664 + }
1.665 + else
1.666 + {
1.667 + assert(v1->new_stmt == NULL);
1.668 + if (v1->new_stmt == NULL)
1.669 + {
1.670 + v1->new_stmt = new (graph) DeclNode(
1.671 + new (graph) VarNode(v1),
1.672 + new (graph) ConstNode(p1));
1.673 + rtemp = new (graph) StmtNode(
1.674 + _OP_STMT,
1.675 + v1->new_stmt,
1.676 + NULL);
1.677 + root_tail->next = rtemp;
1.678 + root_tail = rtemp;
1.679 + }
1.680 + }
1.681 + break;
1.682 + }
1.683 + case OP_PUSH_S:
1.684 + {
1.685 + p1 = PCODE_PARAM(pcode, cip, 1);
1.686 + v1 = sp_FindGraphVar(func, cip, sp, p1);
1.687 + CHECK_VALUE(v1);
1.688 +
1.689 + /* Adjust stack pointer. */
1.690 + sp -= sizeof(cell_t);
1.691 +
1.692 + /* Right now, don't allow aliasing or overflows. */
1.693 + assert(sp_FindGraphVar(func, cip, sp, sp) == NULL);
1.694 + assert(stack_entries < MAX_STACK_ENTRIES);
1.695 +
1.696 + /* Add a new stack entry. */
1.697 + eval_stack[stack_entries++] = StackEntry(sp, new (graph) VarNode(v1));
1.698 + break;
1.699 + }
1.700 + case OP_PUSH_PRI:
1.701 + {
1.702 + CHECK_VALUE(pri);
1.703 +
1.704 + /* Adjust stack pointer. */
1.705 + sp -= sizeof(cell_t);
1.706 +
1.707 + /* Right now, don't allow aliasing or overflows. */
1.708 + assert(sp_FindGraphVar(func, cip, sp, sp) == NULL);
1.709 + assert(stack_entries < MAX_STACK_ENTRIES);
1.710 +
1.711 + /* Add a new stack entry. */
1.712 + eval_stack[stack_entries++] = StackEntry(sp, pri);
1.713 + break;
1.714 + }
1.715 + case OP_POP_ALT:
1.716 + {
1.717 + assert(stack_entries > 0);
1.718 + assert(eval_stack[stack_entries - 1].depth == sp);
1.719 +
1.720 + alt = eval_stack[--stack_entries].expr;
1.721 + sp += sizeof(cell_t);
1.722 + assert(sp <= 0);
1.723 + break;
1.724 + }
1.725 + case OP_STACK:
1.726 + {
1.727 + p1 = PCODE_PARAM(pcode, cip, 1);
1.728 + sp += p1;
1.729 + assert(sp <= 0);
1.730 + if (p1 < 0)
1.731 + {
1.732 + /* Find if we should track a new variable declaration. */
1.733 + v1 = sp_FindGraphVar(func, cip, sp, sp);
1.734 + CHECK_VALUE(v1);
1.735 + assert(v1->new_stmt == NULL);
1.736 + if (v1->new_stmt == NULL)
1.737 + {
1.738 + v1->new_stmt = new (graph) DeclNode(
1.739 + new (graph) VarNode(v1),
1.740 + NULL);
1.741 + rtemp = new (graph) StmtNode(
1.742 + _OP_STMT,
1.743 + v1->new_stmt,
1.744 + NULL);
1.745 + root_tail->next = rtemp;
1.746 + root_tail = rtemp;
1.747 + }
1.748 + assert(abs(p1) >> 2 == 1);
1.749 + }
1.750 + else
1.751 + {
1.752 + /* Erase anything left over on the evaluation stack. */
1.753 + while (stack_entries > 0
1.754 + && eval_stack[stack_entries - 1].depth < sp)
1.755 + {
1.756 + assert(0);
1.757 + stack_entries--;
1.758 + }
1.759 + }
1.760 + break;
1.761 + }
1.762 + case OP_ZERO_PRI:
1.763 + {
1.764 + pri = new (graph) ConstNode(0);
1.765 + break;
1.766 + }
1.767 + case OP_MOVE_ALT:
1.768 + {
1.769 + CHECK_VALUE(pri);
1.770 + alt = pri;
1.771 + break;
1.772 + }
1.773 + case OP_LOAD_S_PRI:
1.774 + {
1.775 + p1 = PCODE_PARAM(pcode, cip, 1);
1.776 + v1 = sp_FindGraphVar(func, cip, sp, p1);
1.777 + CHECK_VALUE(v1);
1.778 + pri = new (graph) VarNode(v1);
1.779 + break;
1.780 + }
1.781 + case OP_LOAD_S_ALT:
1.782 + {
1.783 + p1 = PCODE_PARAM(pcode, cip, 1);
1.784 + v1 = sp_FindGraphVar(func, cip, sp, p1);
1.785 + CHECK_VALUE(v1);
1.786 + alt = new (graph) VarNode(v1);
1.787 + break;
1.788 + }
1.789 + case OP_STOR_S_PRI:
1.790 + {
1.791 + p1 = PCODE_PARAM(pcode, cip, 1);
1.792 + v1 = sp_FindGraphVar(func, cip, sp, p1);
1.793 + CHECK_VALUE(v1);
1.794 + CHECK_VALUE(pri);
1.795 + rtemp = new (graph) StmtNode(
1.796 + _OP_STMT,
1.797 + new (graph) BinOpNode(_OP_STORE, new (graph) VarNode(v1), pri),
1.798 + NULL);
1.799 + root_tail->next = rtemp;
1.800 + root_tail = rtemp;
1.801 +
1.802 + /**
1.803 + * We create a varnode to simulate a load here.
1.804 + * This helps accidental duplication of the expression tree.
1.805 + */
1.806 + pri = new (graph) VarNode(v1);
1.807 + break;
1.808 + }
1.809 + case OP_LOAD_S_BOTH:
1.810 + {
1.811 + p1 = PCODE_PARAM(pcode, cip, 1);
1.812 + p2 = PCODE_PARAM(pcode, cip, 2);
1.813 + v1 = sp_FindGraphVar(func, cip, sp, p1);
1.814 + v2 = sp_FindGraphVar(func, cip, sp, p2);
1.815 + CHECK_VALUE(v1);
1.816 + CHECK_VALUE(v2);
1.817 + pri = new (graph) VarNode(v1);
1.818 + alt = new (graph) VarNode(v2);
1.819 + break;
1.820 + }
1.821 + case OP_ADD:
1.822 + case OP_SMUL:
1.823 + {
1.824 + CHECK_VALUE(pri);
1.825 + CHECK_VALUE(alt);
1.826 + pri = new (graph) BinOpNode(op, pri, alt);
1.827 + break;
1.828 + }
1.829 + case OP_SUB_ALT:
1.830 + {
1.831 + CHECK_VALUE(pri);
1.832 + CHECK_VALUE(alt);
1.833 + pri = new (graph) BinOpNode(op, alt, pri);
1.834 + break;
1.835 + }
1.836 + case OP_SDIV:
1.837 + {
1.838 + CHECK_VALUE(pri);
1.839 + CHECK_VALUE(alt);
1.840 + pri = new (graph) BinOpNode(OP_SDIV, pri, alt);
1.841 + alt = new (graph) BinOpNode(_OP_MODULO, pri, alt);
1.842 + break;
1.843 + }
1.844 + case OP_SDIV_ALT:
1.845 + {
1.846 + CHECK_VALUE(pri);
1.847 + CHECK_VALUE(alt);
1.848 + pri = new (graph) BinOpNode(OP_SDIV, alt, pri);
1.849 + alt = new (graph) BinOpNode(_OP_MODULO, alt, pri);
1.850 + break;
1.851 + }
1.852 + case OP_ADD_C:
1.853 + case OP_SMUL_C:
1.854 + {
1.855 + p1 = PCODE_PARAM(pcode, cip, 1);
1.856 + CHECK_VALUE(pri);
1.857 + pri = new (graph) BinOpNode(op, pri, new (graph) ConstNode(p1));
1.858 + break;
1.859 + }
1.860 + case OP_RETN:
1.861 + {
1.862 + CHECK_VALUE(pri);
1.863 + rtemp = new (graph) StmtNode(op, pri, NULL);
1.864 + root_tail->next = rtemp;
1.865 + root_tail = rtemp;
1.866 + break;
1.867 + }
1.868 + default:
1.869 + {
1.870 + assert(0);
1.871 + break;
1.872 + }
1.873 + }
1.874 +
1.875 + NEXT_OP(cip, op);
1.876 + }
1.877 +
1.878 + sp_DebugPrint(graph->func, dc, root->next);
1.879 +
1.880 + return SP_ERROR_NONE;
1.881 +
1.882 +return_error:
1.883 + return err;
1.884 +}
1.885 +
1.886 +#undef CHECK_FUNCVAR
1.887 +
1.888 +inline Block *sp_BlockFromMap(sp_decomp_t *dc, ControlFlowGraph *graph, cell_t cip)
1.889 +{
1.890 + cell_t val;
1.891 +
1.892 + assert(PCODE_VAL(dc->pcode_map, cip) & PCM_HAS_BLOCK);
1.893 +
1.894 + val = PCODE_VAL(dc->pcode_map, cip);
1.895 + val >>= PCM_NUM_BITS;
1.896 +
1.897 + assert(val >= 0 && val < (cell_t)graph->used_blocks);
1.898 +
1.899 + return &graph->blocks[val];
1.900 +}
1.901 +
1.902 +void sp_InsertBlock(sp_decomp_t *dc, unsigned int index, cell_t cip)
1.903 +{
1.904 + cell_t val;
1.905 +
1.906 + val = PCODE_VAL(dc->pcode_map, cip);
1.907 +
1.908 + assert(!(val & PCM_HAS_BLOCK));
1.909 + assert(index < 0x20000000);
1.910 +
1.911 + val |= PCM_HAS_BLOCK;
1.912 + val |= index << 3;
1.913 +
1.914 + PCODE_VAL(dc->pcode_map, cip) = val;
1.915 +}
1.916 +
1.917 +static Block *sp_BuildBlocks(sp_decomp_t *dc, ControlFlowGraph *graph, cell_t cip)
1.918 +{
1.919 + cell_t op;
1.920 + bool is_branch;
1.921 + cell_t target;
1.922 + Block *block;
1.923 + Edge *edge_tail;
1.924 + Block *outgoing;
1.925 + cell_t cip_end;
1.926 + cell_t *pcode;
1.927 +
1.928 + target = 0;
1.929 + cip_end = graph->func->code_end;
1.930 + pcode = (cell_t *)dc->plugin->pcode;
1.931 +
1.932 + if (PCODE_VAL(dc->pcode_map, cip) & PCM_HAS_BLOCK)
1.933 + {
1.934 + return sp_BlockFromMap(dc, graph, cip);
1.935 + }
1.936 +
1.937 + /* We can't add a new block if we hit our limit. */
1.938 + assert(graph->used_blocks < graph->max_blocks);
1.939 + if (graph->used_blocks >= graph->max_blocks)
1.940 + {
1.941 + return NULL;
1.942 + }
1.943 +
1.944 + edge_tail = NULL;
1.945 +
1.946 + /* Reserve a new block. */
1.947 + block = &graph->blocks[graph->used_blocks++];
1.948 + block->ip_start = cip;
1.949 +
1.950 + /* Enter us into the map. */
1.951 + sp_InsertBlock(dc, graph->used_blocks - 1, cip);
1.952 +
1.953 + /* Walk the code. */
1.954 + while (cip < cip_end)
1.955 + {
1.956 + /* Check whether this is the start of a new block. */
1.957 + if (cip != block->ip_start
1.958 + && (PCODE_VAL(dc->pcode_map, cip) & PCM_BRANCH_TARGET))
1.959 + {
1.960 + block->ip_end = cip;
1.961 + if ((outgoing = sp_BuildBlocks(dc, graph, cip)) == NULL)
1.962 + {
1.963 + return NULL;
1.964 + }
1.965 + /* :TODO: add edge */
1.966 + return block;
1.967 + }
1.968 +
1.969 + is_branch = false;
1.970 + op = PCODE_VAL(pcode, cip);
1.971 + NEXT_OP(cip, op);
1.972 +
1.973 + if (is_branch)
1.974 + {
1.975 + /* Check that branch offsets go to valid instructions. */
1.976 + if (!(PCODE_VAL(dc->pcode_map, target) & PCM_OPCODE))
1.977 + {
1.978 + graph->err = SP_ERROR_INVALID_INSTRUCTION;
1.979 + return NULL;
1.980 + }
1.981 +
1.982 + /* Get our target block. */
1.983 + if ((outgoing = sp_BuildBlocks(dc, graph, target)) == NULL)
1.984 + {
1.985 + return NULL;
1.986 + }
1.987 + /* :TODO: add edge */
1.988 + }
1.989 + else if (op == OP_RETN /* :TODO: || op == OP_RET*/)
1.990 + {
1.991 + block->ip_end = cip;
1.992 + return block;
1.993 + }
1.994 + }
1.995 +
1.996 + graph->err = SP_ERROR_INVALID_INSTRUCTION;
1.997 +
1.998 + return NULL;
1.999 +}
1.1000 +
1.1001 +
1.1002 +int Sp_DecompFunction(sp_decomp_t *dc, uint32_t code_addr, bool is_public)
1.1003 +{
1.1004 + int err;
1.1005 + cell_t op;
1.1006 + ucell_t cip;
1.1007 + cell_t *pcode;
1.1008 + ucell_t cip_end;
1.1009 + sp_file_t *plugin;
1.1010 + FunctionInfo *func;
1.1011 + ControlFlowGraph graph;
1.1012 +
1.1013 + func = NULL;
1.1014 + plugin = dc->plugin;
1.1015 + memset(&graph, 0, sizeof(graph));
1.1016 +
1.1017 + if (code_addr >= plugin->pcode_size)
1.1018 + {
1.1019 + err = SP_ERROR_INVALID_INSTRUCTION;
1.1020 + goto return_error;
1.1021 + }
1.1022 +
1.1023 + pcode = (cell_t *)plugin->pcode;
1.1024 +
1.1025 + if (PCODE_VAL(pcode, code_addr) != OP_PROC)
1.1026 + {
1.1027 + err = SP_ERROR_INVALID_INSTRUCTION;
1.1028 + goto return_error;
1.1029 + }
1.1030 +
1.1031 + cip = code_addr + sizeof(cell_t);
1.1032 +
1.1033 + /* See if we have an existing function stored. */
1.1034 + func = sp_GetFuncPrototype(dc, code_addr, true, is_public);
1.1035 +
1.1036 + while (cip < plugin->pcode_size)
1.1037 + {
1.1038 + op = PCODE_VAL(pcode, cip);
1.1039 + if (op >= OP_TOTAL || op < 0)
1.1040 + {
1.1041 + err = SP_ERROR_INVALID_INSTRUCTION;
1.1042 + }
1.1043 + if (dc->opdef[op].name == NULL)
1.1044 + {
1.1045 + err = SP_ERROR_INVALID_INSTRUCTION;
1.1046 + }
1.1047 + if (op == OP_PROC)
1.1048 + {
1.1049 + break;
1.1050 + }
1.1051 + NEXT_OP(cip, op);
1.1052 + }
1.1053 + cip_end = cip;
1.1054 +
1.1055 + func->code_end = cip_end;
1.1056 +
1.1057 + /* Now we can cache all local vars. */
1.1058 + sp_CacheLocals(dc, func);
1.1059 +
1.1060 + /**
1.1061 + * Make the entry point as the first block.
1.1062 + * It needs to be flagged as well so it doesn't get double counted.
1.1063 + */
1.1064 + memset(&PCODE_VAL(dc->pcode_map, code_addr), 0, cip_end - code_addr);
1.1065 +
1.1066 + graph.max_blocks = 1;
1.1067 + graph.func = func;
1.1068 + PCODE_VAL(dc->pcode_map, code_addr) |= PCM_BRANCH_TARGET;
1.1069 +
1.1070 + /* Walk the code. */
1.1071 + {
1.1072 + cell_t target;
1.1073 + bool is_branch;
1.1074 +
1.1075 + target = 0;
1.1076 + cip = code_addr;
1.1077 + while (cip < cip_end)
1.1078 + {
1.1079 + /* Get opcode */
1.1080 + op = PCODE_VAL(pcode, cip);
1.1081 + /* Mark as not a branch */
1.1082 + is_branch = false;
1.1083 + /* Make sure we know this is a valid target */
1.1084 + PCODE_VAL(dc->pcode_map, cip) |= PCM_OPCODE;
1.1085 +
1.1086 + if (is_branch)
1.1087 + {
1.1088 + /**
1.1089 + * Keep track of where branches are and how many blocks we need.
1.1090 + */
1.1091 + if (!(PCODE_VAL(dc->pcode_map, target) & PCM_BRANCH_TARGET))
1.1092 + {
1.1093 + PCODE_VAL(dc->pcode_map, target) |= PCM_BRANCH_TARGET;
1.1094 + graph.max_blocks++;
1.1095 +
1.1096 + /**
1.1097 + * If we're creating a new block, estimate that we need to create a new edge
1.1098 + * as well.
1.1099 + */
1.1100 + graph.max_edges++;
1.1101 + }
1.1102 +
1.1103 + /**
1.1104 + * In this algorithm, jumps do not terminate a block unless they are unconditional.
1.1105 + * This reduces the number of blocks and edges.
1.1106 + *
1.1107 + * A property of this is that jumps are edges, so the number of edges is identical
1.1108 + * to the number of jumps.
1.1109 + */
1.1110 + graph.max_edges++;
1.1111 + }
1.1112 +
1.1113 + NEXT_OP(cip, op);
1.1114 + }
1.1115 + }
1.1116 +
1.1117 + /* Initialize memory needed for the graph. */
1.1118 + graph.blocks = new Block[graph.max_blocks];
1.1119 + memset(graph.blocks, 0, sizeof(Block) * graph.max_blocks);
1.1120 +
1.1121 + if (graph.max_edges != 0)
1.1122 + {
1.1123 + graph.edges = new Edge[graph.max_edges];
1.1124 + memset(graph.edges, 0, sizeof(Edge) * graph.max_edges);
1.1125 + }
1.1126 +
1.1127 + if ((graph.entry = sp_BuildBlocks(dc, &graph, code_addr)) == NULL)
1.1128 + {
1.1129 + if ((err = graph.err) == SP_ERROR_NONE)
1.1130 + {
1.1131 + err = SP_ERROR_ABORTED;
1.1132 + }
1.1133 + goto return_error;
1.1134 + }
1.1135 +
1.1136 + if ((err = sp_AnalyzeGraph(dc, &graph)) == NULL)
1.1137 + {
1.1138 + goto return_error;
1.1139 + }
1.1140 +
1.1141 + return SP_ERROR_NONE;
1.1142 +
1.1143 +return_error:
1.1144 + return err;
1.1145 +}
