/* Chrysalide - Outil d'analyse de fichiers binaires
* il.h - mise en place d'un langage intermédiaire
*
* Copyright (C) 2012-2017 Cyrille Bagard
*
* This file is part of Chrysalide.
*
* Chrysalide is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 3 of the License, or
* (at your option) any later version.
*
* Chrysalide is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with Foobar. If not, see .
*/
#include "il.h"
#include
#include "../blocks/flow.h"
#include "../blocks/virtual.h"
#include "../../decomp/expr/block.h"
#include "../../decomp/expr/immediate.h"
#include "../../decomp/instr/ite.h"
#include "../../decomp/instr/keyword.h"
#include "../../decomp/instr/switch.h"
/* --------------------- GESTION DES CONTEXTES DE DECOMPILATION --------------------- */
/* Détermine les registres utilisés avant leur initialisation. */
static bool track_used_registers(GFlowBlock *, BlockFollowPosition, GRAccessList **);
/* Etablit le relévé des allocations de registre. */
static void setup_awaited_regs_allocation(const GInstrBlock *, vmpa_t);
/* Etablit la liste de tous les allocations attendues. */
static bool merge_all_awaited_regs(GInstrBlock *, BlockVisitOrder, GRAccessList *);
/* Met en place un contexte adapté aux sous-blocs d'un bloc. */
static GDecContext *create_new_context_for_sub_block(GDecContext *, GInstrBlock *, GHashTable *);
/* -------------------------- ENCADREMENT DES INSTRUCTIONS -------------------------- */
/* Retrouve et rassemble les instructions décompilées. */
static GDecInstruction *merge_decompiled_instructions(GDecInstruction *, GDecInstruction *);
/* Procède à la décompilation d'un bloc déterminé. */
static GDecInstruction *decompiled_instructions_block(GFlowBlock *, GDecContext *);
/* Procède à la décompilation d'un ensemble de blocs déterminé. */
static GDecInstruction *decompiled_instructions_blocks(GVirtualBlock *, GDecContext *);
/* Procède à la décompilation d'un bloc basique quelconque. */
static GDecInstruction *decompiled_basic_block(GInstrBlock *, GDecContext *);
/* --------------------------- DECOMPILATIONS SPECIFIQUES --------------------------- */
/* Procède à la décompilation des éléments d'un 'if then else'. */
static void build_ite_branches(GITEInstruction *, GFlowBlock *, GDecContext *);
/* Termine le traitement d'un cas de 'switch'. */
static void close_case_decomp_instructions(GDecInstruction *, GInstrBlock *, GArchInstruction **, size_t, size_t);
/* Procède à la décompilation des éléments d'un 'switch'. */
static void build_switch_branches(GSwitchInstruction *, GFlowBlock *, GDecContext *);
/* ---------------------------------------------------------------------------------- */
/* GESTION DES CONTEXTES DE DECOMPILATION */
/* ---------------------------------------------------------------------------------- */
/******************************************************************************
* *
* Paramètres : block = bloc d'instructions visité. *
* pos = indication sur la position du parcours. *
* needed = suivi de l'usage des registres entre les blocs. *
* *
* Description : Détermine les registres utilisés avant leur initialisation. *
* *
* Retour : true pour mener un parcours complet. *
* *
* Remarques : - *
* *
******************************************************************************/
static bool track_used_registers(GFlowBlock *block, BlockFollowPosition pos, GRAccessList **needed)
{
GRAccessList *old; /* Ancienne liste remplacée */
const GRAccessList *accesses; /* Accès divers aux registres */
size_t count; /* Taille d'un parcours */
GRAccessList *awaited; /* Satisfactions des besoins */
reg_access *access; /* Accès à un registre */
size_t i; /* Boucle de parcours */
reg_access *found; /* Besoin trouvé ou non */
switch (pos)
{
case BFP_ENTER:
g_object_set_data(G_OBJECT(block), "needed_regs", *needed);
break;
case BFP_FOLLOW:
*needed = g_raccess_list_new();
break;
case BFP_BACK:
old = *needed;
*needed = G_RACCESS_LIST(g_object_get_data(G_OBJECT(block), "needed_regs"));
g_raccess_list_merge(*needed, old);
g_object_unref(G_OBJECT(old));
break;
case BFP_EXIT:
g_object_set_data(G_OBJECT(block), "needed_regs", NULL);
accesses = g_flow_block_list_regs_accesses(block);
count = g_raccess_list_count(accesses);
awaited = g_flow_block_list_awaited_regs(block);
for (i = 0; i < count; i++)
{
access = g_raccess_list_get(accesses, i);
/* Enregistrement des contributions possibles */
found = g_raccess_list_find(*needed, access->reg);
if (found != NULL)
{
/**
* Si un autre bloc avait déjà un besoin, on ne prend note
* qu'une seule fois !
*/
if (g_raccess_list_find(awaited, access->reg) == NULL)
g_raccess_list_add(awaited, access);
g_raccess_list_delete(*needed, found);
}
/* Ajoute les besoins du bloc */
if (access->first_access == RAT_READ)
g_raccess_list_add(*needed, access);
}
/*
do
{
vmpa_t start, end;
g_flow_block_get_boundary_addresses(block, &start, &end);
printf(" -> flow (%d) : 0x%08x - 0x%08x | needed = %zu - provided = %zu\n",
pos, start, end,
g_raccess_list_count(*needed), g_raccess_list_count(awaited));
}
while (0);
*/
break;
}
return true;
}
/******************************************************************************
* *
* Paramètres : list = ensemble des instructions d'assemblage à traiter. *
* start = adresse de départ de la routine visée. *
* *
* Description : Etablit le relévé des allocations de registre. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void setup_awaited_regs_allocation(const GInstrBlock *list, vmpa_t start)
{
GInstrBlock *first; /* Bloc de départ du flot */
GRAccessList *needed; /* Registres inter-blocs */
first = g_instr_block_find_by_addr(list, start, true);
needed = g_raccess_list_new();
g_flow_block_follow(G_FLOW_BLOCK(first), list, BFP_ENTER | BFP_EXIT | BFP_EXIT,
(flow_block_follow_cb)track_used_registers, &needed);
g_object_unref(G_OBJECT(needed));
}
/******************************************************************************
* *
* Paramètres : block = bloc d'instructions concerné par la visite. *
* order = position dans la visite. *
* list = liste à compléter. *
* *
* Description : Etablit la liste de tous les allocations attendues. *
* *
* Retour : true pour parcourir tous les blocs. *
* *
* Remarques : - *
* *
******************************************************************************/
static bool merge_all_awaited_regs(GInstrBlock *block, BlockVisitOrder order, GRAccessList *list)
{
const GRAccessList *awaited; /* Registres conséquents */
if (G_IS_FLOW_BLOCK(block))
{
awaited = g_flow_block_list_regs_accesses(G_FLOW_BLOCK(block));
g_raccess_list_merge(list, awaited);
}
return true;
}
/******************************************************************************
* *
* Paramètres : ctx = contexte de décompilation courant. *
* block = block regroupant les branches de division. *
* shared = liste des allocations passées de registres attendus.*
* *
* Description : Met en place un contexte adapté aux sous-blocs d'un bloc. *
* *
* Retour : Nouveau contexte près à emploi. *
* *
* Remarques : - *
* *
******************************************************************************/
static GDecContext *create_new_context_for_sub_block(GDecContext *ctx, GInstrBlock *block, GHashTable *shared)
{
GDecContext *result; /* Contexte à retourner */
GRAccessList *list; /* Allocations attendues */
result = g_dec_context_dup(ctx);
list = g_raccess_list_new();
g_instr_block_visit(block, (instr_block_visitor_cb)merge_all_awaited_regs, list);
g_dec_context_set_awaited(result, list);
g_object_unref(G_OBJECT(list));
g_dec_context_set_shared_allocs(result, shared);
return result;
}
/* ---------------------------------------------------------------------------------- */
/* ENCADREMENT DES INSTRUCTIONS */
/* ---------------------------------------------------------------------------------- */
/******************************************************************************
* *
* Paramètres : group = groupe d'instructions à compléter ou constituer. *
* list = liste d'instructions à intégrer. *
* *
* Description : Retrouve et rassemble les instructions décompilées. *
* *
* Retour : Groupe fourni ou nouveau groupe créé pour l'occasion. *
* *
* Remarques : - *
* *
******************************************************************************/
static GDecInstruction *merge_decompiled_instructions(GDecInstruction *group, GDecInstruction *list)
{
GExprBlock *block; /* Autre vision du groupe */
GDecInstruction *iter; /* Boucle de parcours */
if (group == NULL) block = NULL;
else block = G_EXPR_BLOCK(group);
for (iter = list;
iter != NULL;
iter = g_dec_instruction_get_next_iter(list, iter))
{
if (block == NULL)
block = G_EXPR_BLOCK(g_expr_block_new(iter));
else
g_expr_block_add_item(block, iter);
}
return G_DEC_INSTRUCTION(block);
}
/******************************************************************************
* *
* Paramètres : block = ensemble des instructions d'assemblage à traiter. *
* ctx = contexte de soutien à associer à l'opération. *
* *
* Description : Procède à la décompilation d'un bloc déterminé. *
* *
* Retour : Instructions créées et enregistrées, ou NULL si erreur. *
* *
* Remarques : - *
* *
******************************************************************************/
static GDecInstruction *decompiled_instructions_block(GFlowBlock *block, GDecContext *ctx)
{
GArchInstruction *instrs; /* Liste d'instructions natives*/
GArchInstruction *first; /* Première instruction du lot */
vmpa_t max; /* Adresse de fin du bloc */
GArchInstruction *iter; /* Boucle de parcours #1 */
GDecInstruction *decomp; /* Dernier résultat de décomp. */
instrs = NULL; // FIXME g_flow_block_get_all_instructions_list(block);
g_flow_block_get_boundary(block, &first, NULL);
g_flow_block_get_boundary_addresses(block, NULL, &max);
max++;
/* Décompilation du corps du bloc */
for (iter = first;
iter != NULL;
iter = g_arch_instruction_get_next_iter(instrs, iter, max))
{
decomp = g_arch_instruction_decompile(iter, ctx);
}
/* Post-traitement selon les types de lien */
/* if ... then ... else ... */
if (G_IS_ITE_INSTRUCTION(decomp))
build_ite_branches(G_ITE_INSTRUCTION(decomp), block, ctx);
/* switch ... case ... */
else if (G_IS_SWITCH_INSTRUCTION(decomp))
build_switch_branches(G_SWITCH_INSTRUCTION(decomp), block, ctx);
/* Renvoi des instructions mises en place */
return g_dec_context_get_decomp_instrs(ctx);
}
/******************************************************************************
* *
* Paramètres : block = ensemble des instructions d'assemblage à traiter. *
* ctx = contexte de soutien à associer à l'opération. *
* *
* Description : Procède à la décompilation d'un ensemble de blocs déterminé. *
* *
* Retour : Instructions créées et enregistrées, ou NULL si erreur. *
* *
* Remarques : - *
* *
******************************************************************************/
static GDecInstruction *decompiled_instructions_blocks(GVirtualBlock *block, GDecContext *ctx)
{
GDecInstruction *result; /* Instructions à renvoyer */
size_t count; /* Nombre de sous-blocs */
size_t i; /* Boucle de parcours */
GInstrBlock *sub_block; /* Sous-bloc à traiter */
GDecInstruction *dinstrs; /* Instructions décompilées */
result = NULL;
count = g_virtual_block_count_children(block);
for (i = 0; i < count; i++)
{
sub_block = g_virtual_block_get_child(block, i);
/**
* Les groupes de blocs sont forcément rattachés à une instruction,
* donc ils sont décompilés depuis ces instructions, pas ici.
*/
if (!G_IS_FLOW_BLOCK(sub_block)) continue;
/* FIXME */
//g_dec_context_set_decomp_instrs(ctx, NULL);
dinstrs = decompiled_instructions_block(G_FLOW_BLOCK(sub_block), ctx);
//result = merge_decompiled_instructions(result, dinstrs);
}
result = merge_decompiled_instructions(result, dinstrs);
return result;
}
/******************************************************************************
* *
* Paramètres : block = ensemble des instructions d'assemblage à traiter. *
* ctx = contexte de soutien à associer à l'opération. *
* *
* Description : Procède à la décompilation d'un bloc basique quelconque. *
* *
* Retour : Instructions créées et enregistrées, ou NULL si erreur. *
* *
* Remarques : - *
* *
******************************************************************************/
static GDecInstruction *decompiled_basic_block(GInstrBlock *block, GDecContext *ctx)
{
GDecInstruction *result; /* Instructions à retourner */
if (G_IS_VIRTUAL_BLOCK(block))
result = decompiled_instructions_blocks(G_VIRTUAL_BLOCK(block), ctx);
else
{
result = decompiled_instructions_block(G_FLOW_BLOCK(block), ctx);
if (!G_IS_EXPR_BLOCK(result))
result = merge_decompiled_instructions(NULL, result);
}
return result;
}
/******************************************************************************
* *
* Paramètres : routine = routine dont le corps est à traiter. *
* format = format du binaire contenant les instructions. *
* proc = architecture du code machine. *
* *
* Description : Procède à la décompilation d'une routinée déterminée. *
* *
* Retour : Instructions créées ou NULL si erreur. *
* *
* Remarques : - *
* *
******************************************************************************/
GDecInstruction *decompiled_routine_instructions(GBinRoutine *routine, GExeFormat *format, GArchProcessor *proc)
{
GDecInstruction *result; /* Instructions à retourner */
GDecContext *context; /* Contexte pour la décompil. */
GInstrBlock *blocks; /* Blocs basiques de routine */
context = g_arch_processor_get_decomp_context(proc);
g_dec_context_set_info(context, routine, format);
blocks = g_binary_routine_get_basic_blocks(routine);
setup_awaited_regs_allocation(blocks, g_binary_routine_get_address(routine));
result = decompiled_basic_block(blocks, context);
g_object_unref(context);
return result;
}
/* ---------------------------------------------------------------------------------- */
/* DECOMPILATIONS SPECIFIQUES */
/* ---------------------------------------------------------------------------------- */
/******************************************************************************
* *
* Paramètres : decomp = instruction 'if ... then ... else' à compléter. *
* block = ensemble des instructions d'assemblage traitées. *
* ctx = contexte de soutien à associer à l'opération. *
* *
* Description : Procède à la décompilation des éléments d'un 'if then else'. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void build_ite_branches(GITEInstruction *decomp, GFlowBlock *block, GDecContext *ctx)
{
GArchInstruction *last; /* Dernière instruction du lot */
GInstrBlock *sub_parent; /* Groupe des sous-branches */
GHashTable *sub_shared; /* Allocations communes */
GDecContext *sub_ctx; /* Sous-contexte pour branche */
GDecInstruction *true_dinstr; /* Décompilation 'cond vraie' */
GDecInstruction *false_dinstr; /* Décompilation 'cond fausse' */
GArchInstruction *next; /* Instruction de branchement */
vmpa_t next_addr; /* Adresse de cette instruct° */
GInstrBlock *next_block; /* Sous-bloc basique direct */
g_flow_block_get_boundary(block, NULL, &last);
sub_parent = g_instr_block_get_links_block(G_INSTR_BLOCK(block));
sub_shared = g_hash_table_new_full((GHashFunc)g_arch_register_hash,
(GEqualFunc)NULL,//g_arch_register_equal,
g_object_unref, g_object_unref);
true_dinstr = NULL;
false_dinstr = NULL;
/* Branche 'true' */
next = g_arch_instruction_get_given_destination(last, ILT_JUMP_IF_TRUE);
if (next != NULL)
{
g_arch_instruction_get_location(next, NULL, NULL, &next_addr);
next_block = g_instr_block_find_by_addr(sub_parent, next_addr, false);
if (next_block != NULL)
{
sub_ctx = create_new_context_for_sub_block(ctx, next_block, sub_shared);
true_dinstr = decompiled_basic_block(next_block, sub_ctx);
g_dec_context_spread_allocated_shared_regs(ctx, sub_ctx);
g_object_unref(G_OBJECT(sub_ctx));
}
g_object_unref(G_OBJECT(next));
}
/* Branche 'false' */
next = g_arch_instruction_get_given_destination(last, ILT_JUMP_IF_FALSE);
if (next != NULL)
{
g_arch_instruction_get_location(next, NULL, NULL, &next_addr);
next_block = g_instr_block_find_by_addr(sub_parent, next_addr, false);
if (next_block != NULL)
{
sub_ctx = create_new_context_for_sub_block(ctx, next_block, sub_shared);
false_dinstr = decompiled_basic_block(next_block, sub_ctx);
g_dec_context_spread_allocated_shared_regs(ctx, sub_ctx);
g_object_unref(G_OBJECT(sub_ctx));
}
g_object_unref(G_OBJECT(next));
}
g_ite_instruction_set_branches(decomp, true_dinstr, false_dinstr);
g_hash_table_unref(sub_shared);
}
/******************************************************************************
* *
* Paramètres : case_dinstr = instructions d'un cas de 'switch' décompilées. *
* case_block = bloc d'instructions assembleur correspondantes.*
* cases = listes des instructions des différents cas. *
* current = indice du cas courant. *
* ccount = nombre de cas présents dans le 'switch'. *
* *
* Description : Termine le traitement d'un cas de 'switch'. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void close_case_decomp_instructions(GDecInstruction *case_dinstr, GInstrBlock *case_block, GArchInstruction **cases, size_t current, size_t ccount)
{
vmpa_t *cases_addr; /* Adresses des cas du 'switch'*/
size_t i; /* Boucle de parcours #1 */
GInstrBlock **leafs; /* Blocs terminaux du cas */
size_t lcount; /* Nombre de blocs terminaux */
vmpa_t common_addr; /* Adresse commune de suite */
bool is_common; /* Suite commune ? */
GArchInstruction *last; /* Dernière instruction de bloc*/
size_t dcount; /* Nombre de liens de dest. */
size_t j; /* Boucle de parcours #2 */
instr_link_t *dest; /* Instr. visée par une autre */
vmpa_t addr; /* Adresse d'une instruction */
bool jump_to_case; /* Suite dans le cas suivant ? */
/* Etablit la liste des adresses des cas */
cases_addr = (vmpa_t *)calloc(ccount, sizeof(vmpa_t));
for (i = 0; i < ccount; i++)
g_arch_instruction_get_location(cases[i], NULL, NULL, &cases_addr[i]);
/* Récupère la (les) fin(s) du cas présent */
leafs = NULL;
lcount = 0;
g_instr_block_list_leafs_blocks(case_block, &leafs, &lcount);
/* Procède à une première analyse de la suite */
common_addr = VMPA_MAX;
is_common = true;
for (i = 0; i < lcount && is_common; i++)
{
g_flow_block_get_boundary(G_FLOW_BLOCK(leafs[i]), NULL, &last);
g_arch_instruction_lock_dest(last);
dcount = g_arch_instruction_count_destinations(last);
for (j = 0; j < dcount && is_common; j++)
{
dest = g_arch_instruction_get_destination(last, j);
g_arch_instruction_get_location(dest->linked, NULL, NULL, &addr);
if (common_addr == VMPA_MAX)
common_addr = addr;
else
is_common = (common_addr == addr);
}
g_arch_instruction_unlock_dest(last);
}
/* La sortie du cas est unique ! */
if (is_common)
{
if (common_addr == VMPA_MAX)
goto ecdi_exit;
jump_to_case = false;
for (i = 0; i < ccount && !jump_to_case; i++)
if (i != current)
jump_to_case = (cases_addr[i] == common_addr);
if (!jump_to_case)
g_expr_block_add_item(G_EXPR_BLOCK(case_dinstr), g_keyword_instruction_new(DKW_BREAK));
}
/* ... ou il faut suivre les différentes branches... */
else
{
/* TODO */
}
ecdi_exit:
free(cases_addr);
}
/******************************************************************************
* *
* Paramètres : decomp = instruction 'switch' à compléter. *
* block = ensemble des instructions d'assemblage traitées. *
* ctx = contexte de soutien à associer à l'opération. *
* *
* Description : Procède à la décompilation des éléments d'un 'switch'. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void build_switch_branches(GSwitchInstruction *decomp, GFlowBlock *block, GDecContext *ctx)
{
#if 0
GArchInstruction *last; /* Dernière instruction du lot */
GInstrBlock *sub_parent; /* Groupe des sous-branches */
GHashTable *sub_shared; /* Allocations communes */
GDecContext *sub_ctx; /* Sous-contexte pour branche */
vmpa_t next_addr; /* Adresse de cette instruct° */
GInstrBlock *next_block; /* Sous-bloc basique direct */
GArchInstruction **dests; /* Instr. visée par une autre */
link_extra_info *info; /* Compléments pour les liens */
size_t dcount; /* Nombre de liens de dest. */
size_t i; /* Boucle de parcours #2 */
GDecInstruction *case_dinstr; /* Décompilation 'case' */
GDecExpression *case_value; /* Valeur d'aiguillage */
g_flow_block_get_boundary(block, NULL, &last);
sub_parent = g_instr_block_get_links_block(G_INSTR_BLOCK(block));
sub_shared = g_hash_table_new_full((GHashFunc)g_arch_register_hash,
(GEqualFunc)g_arch_register_equal,
g_object_unref, g_object_unref);
dcount = g_arch_instruction_get_destinations(last, &dests, NULL, &info);
for (i = 0; i < dcount; i++)
{
g_arch_instruction_get_location(dests[i], NULL, NULL, &next_addr);
next_block = g_instr_block_find_by_addr(sub_parent, next_addr, false);
if (next_block != NULL)
{
sub_ctx = create_new_context_for_sub_block(ctx, next_block, sub_shared);
case_dinstr = decompiled_basic_block(next_block, sub_ctx);
g_dec_context_spread_allocated_shared_regs(ctx, sub_ctx);
g_object_unref(G_OBJECT(sub_ctx));
close_case_decomp_instructions(case_dinstr, next_block, dests, i, dcount);
g_expr_block_set_border_behavior(G_EXPR_BLOCK(case_dinstr), BBB_FORCE_OFF);
if (info[i].imm != NULL)
{
case_value = G_DEC_EXPRESSION(g_imm_expression_new(info[i].imm));
g_switch_instruction_add_case(G_SWITCH_INSTRUCTION(decomp),
case_value, case_dinstr, next_addr);
}
else g_switch_instruction_set_default_case(G_SWITCH_INSTRUCTION(decomp),
case_dinstr);
}
}
g_hash_table_unref(sub_shared);
#endif
}