/* Chrysalide - Outil d'analyse de fichiers binaires
* flow.c - encapsulation graphique des blocs d'exécution
*
* Copyright (C) 2013 Cyrille Bagard
*
* This file is part of Chrysalide.
*
* OpenIDA 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.
*
* OpenIDA 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 "flow.h"
#include
#include "../layout.h"
#include "../node-int.h"
/* Type d'un accrochage pour lien */
struct _node_slot_t
{
GArchInstruction *instr; /* Instruction liée */
size_t group_index; /* Rang dans le grp d'origine */
InstructionLinkType type; /* Type de lien à représenter */
size_t slot_index; /* Position dans l'accroche */
gint x; /* Abscisse graphique du rendu */
};
/* Encapsulation graphique d'un bloc d'exécution (instance) */
struct _GFlowNode
{
GGraphNode parent; /* A laisser en premier */
GFlowBlock *block; /* Bloc d'exécution associé */
GtkBufferView *view; /* Représentation graphique */
node_slot_t *entries; /* Positions des pts d'entrées */
size_t entries_count; /* Nombre de ces points */
node_slot_t *exits; /* Positions des pts de sorties*/
size_t exits_count; /* Nombre de ces points */
};
/* Encapsulation graphique d'un bloc d'exécution (classe) */
struct _GFlowNodeClass
{
GGraphNodeClass parent; /* A laisser en premier */
};
#define SPACE_BETWEEN_SLOT 15
/* Initialise la classe des encapsulations de bloc d'exécution. */
static void g_flow_node_class_init(GFlowNodeClass *);
/* Initialise une encapsulation de bloc d'exécution. */
static void g_flow_node_init(GFlowNode *);
/* Supprime toutes les références externes. */
static void g_flow_node_dispose(GFlowNode *);
/* Procède à la libération totale de la mémoire. */
static void g_flow_node_finalize(GFlowNode *);
/* Fournit le rang du noeud dans le graphique. */
static unsigned int g_flow_node_get_rank(const GFlowNode *);
/* Organise le contenu du noeud selon l'axe des abscisses. */
static void g_flow_node_prepare_x_line(GFlowNode *, GGraphNode *);
/* Parcourt tous les blocs d'instructions dans un ordre donné. */
static bool g_flow_node_visit_flow_nodes(GFlowNode *, graph_node_visitor_cb, void *);
/* ------------------------ GESTION DES ACCROCHES D'UN NOEUD ------------------------ */
/* Prépare les points d'entrées du noeud. */
static void g_flow_node_setup_entry_slots(GFlowNode *);
/* Prépare les points de sorties du noeud. */
static void g_flow_node_setup_exit_slots(GFlowNode *);
/* Etablit un lien entre deux noeuds graphiques. */
static node_slot_t *g_flow_node_get_slot(const GFlowNode *, bool, GArchInstruction *, size_t);
/* Localise un point d'accroche à un noeud graphique. */
static gint g_flow_node_get_slot_offset(const GFlowNode *, bool, const node_slot_t *);
/* Indique le type définit par la GLib pour l'encapsulation d'un bloc d'exécution. */
G_DEFINE_TYPE(GFlowNode, g_flow_node, G_TYPE_GRAPH_NODE);
/******************************************************************************
* *
* Paramètres : klass = classe à initialiser. *
* *
* Description : Initialise la classe des encapsulations de bloc d'exécution. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_flow_node_class_init(GFlowNodeClass *klass)
{
GObjectClass *object; /* Autre version de la classe */
object = G_OBJECT_CLASS(klass);
object->dispose = (GObjectFinalizeFunc/* ! */)g_flow_node_dispose;
object->finalize = (GObjectFinalizeFunc)g_flow_node_finalize;
}
/******************************************************************************
* *
* Paramètres : node = instance à initialiser. *
* *
* Description : Initialise une encapsulation de bloc d'exécution. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_flow_node_init(GFlowNode *node)
{
GGraphNode *base; /* Version basique */
base = G_GRAPH_NODE(node);
base->get_rank = (get_node_rank_fc)g_flow_node_get_rank;
base->prepare_x = (node_prepare_x_fc)g_flow_node_prepare_x_line;
base->visit = (visit_flow_nodes_fc)g_flow_node_visit_flow_nodes;
}
/******************************************************************************
* *
* Paramètres : node = instance d'objet GLib à traiter. *
* *
* Description : Supprime toutes les références externes. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_flow_node_dispose(GFlowNode *node)
{
size_t i; /* Boucle de parcours */
g_object_unref(G_OBJECT(node->block));
g_object_unref(G_OBJECT(node->view));
for (i = 0; i < node->entries_count; i++)
g_object_unref(G_OBJECT(node->entries[i].instr));
for (i = 0; i < node->exits_count; i++)
g_object_unref(G_OBJECT(node->exits[i].instr));
G_OBJECT_CLASS(g_flow_node_parent_class)->dispose(G_OBJECT(node));
}
/******************************************************************************
* *
* Paramètres : node = instance d'objet GLib à traiter. *
* *
* Description : Procède à la libération totale de la mémoire. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_flow_node_finalize(GFlowNode *node)
{
if (node->entries != NULL)
free(node->entries);
if (node->exits != NULL)
free(node->exits);
G_OBJECT_CLASS(g_flow_node_parent_class)->finalize(G_OBJECT(node));
}
/******************************************************************************
* *
* Paramètres : block = bloc d'exécution représenté graphiquement. *
* view = morceau d'affichage à représenter. *
* *
* Description : Encapsule graphiquement un bloc d'exécution. *
* *
* Retour : Adresse de la structure mise en place. *
* *
* Remarques : - *
* *
******************************************************************************/
GGraphNode *g_flow_node_new(GFlowBlock *block, GtkBufferView *view)
{
GFlowNode *result; /* Structure à retourner */
GtkRequisition requisition; /* Taille à l'écran actuelle */
result = g_object_new(G_TYPE_FLOW_NODE, NULL);
g_object_ref(G_OBJECT(block));
g_object_ref(G_OBJECT(view));
result->block = block;
result->view = view;
gtk_widget_show(GTK_WIDGET(result->view));
gtk_widget_size_allocate(GTK_WIDGET(result->view), (GtkAllocation []) { { 0, 0, 100, 100 } });
gtk_widget_get_preferred_size(GTK_WIDGET(result->view), NULL, &requisition);
printf("PREFERED :: (%d ; %d)\n", requisition.width, requisition.height);
G_GRAPH_NODE(result)->alloc.width = requisition.width;
G_GRAPH_NODE(result)->alloc.height = requisition.height;
g_flow_node_setup_entry_slots(result);
g_flow_node_setup_exit_slots(result);
return G_GRAPH_NODE(result);
}
/******************************************************************************
* *
* Paramètres : node = noeud graphique à consulter. *
* *
* Description : Fournit le rang du noeud dans le graphique. *
* *
* Retour : Indice supérieur ou égal à zéro. *
* *
* Remarques : - *
* *
******************************************************************************/
static unsigned int g_flow_node_get_rank(const GFlowNode *node)
{
return g_flow_block_get_rank(node->block);
}
/******************************************************************************
* *
* Paramètres : node = noeud d'encapsulation à traiter. *
* nodes = ensemble des noeuds en place. *
* *
* Description : Organise le contenu du noeud selon l'axe des abscisses. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_flow_node_prepare_x_line(GFlowNode *node, GGraphNode *nodes)
{
GGraphNode *base; /* Autre vision de l'instance */
GArchInstruction *last; /* Dernière instr. du noeud */
GFlowNode *target; /* Bloc visé par le lien */
node_slot_t *dest_slot; /* Accrochage d'arrivée */
pending_position pos; /* Position à transmettre */
GFlowNode *target_a; /* Bloc visé par le lien #a */
GFlowNode *target_b; /* Bloc visé par le lien #b */
unsigned int rank_a; /* Indice du rang associé #a */
unsigned int rank_b; /* Indice du rang associé #b */
GGraphNode *container; /* Conteneur à positionner */
base = G_GRAPH_NODE(node);
g_flow_block_get_boundary(node->block, NULL, &last);
switch (node->exits_count)
{
case 0:
break;
case 1:
if (node->exits[0].type == ILT_LOOP)
break;
target = G_FLOW_NODE(find_node_for_instruction(nodes, node->exits[0].instr));
dest_slot = g_flow_node_get_slot(target, true,
last, node->exits[0].group_index);
pos.direct_x = g_flow_node_get_slot_offset(target, true, dest_slot);
pos.direct_x = (G_GRAPH_NODE(target)->alloc.width / 2) - pos.direct_x;
if (target->entries_count == 1)
g_graph_node_set_pending_position(G_GRAPH_NODE(target), PPF_DIRECT_X, pos, base);
break;
case 2:
target_a = G_FLOW_NODE(find_node_for_instruction(nodes, node->exits[0].instr));
target_b = G_FLOW_NODE(find_node_for_instruction(nodes, node->exits[1].instr));
rank_a = g_flow_node_get_rank(target_a);
rank_b = g_flow_node_get_rank(target_b);
if (rank_a == rank_b)
break;
/* Alignement d'un bloc lié */
if (rank_a > rank_b)
{
/* Seuil vertical pour un côté */
container = g_graph_node_find_container_at_same_level(nodes,
G_GRAPH_NODE(node),
G_GRAPH_NODE(target_b));
if (container == NULL) container = G_GRAPH_NODE(target_b);
pos.left_margin = g_flow_node_get_slot_offset(node, false, &node->exits[0]);
g_graph_node_set_pending_position(container, PPF_LEFT_MARGIN, pos, base);
/* Trait vertical de l'autre côté... */
pos.direct_x = pos.left_margin;
dest_slot = g_flow_node_get_slot(target_a, true,
last, node->exits[0].group_index);
pos.direct_x -= g_flow_node_get_slot_offset(target_a, true, dest_slot);
g_graph_node_set_pending_position(G_GRAPH_NODE(target_a), PPF_DIRECT_X, pos, base);
}
else
{
/* Seuil vertical pour un côté */
container = g_graph_node_find_container_at_same_level(nodes,
G_GRAPH_NODE(node),
G_GRAPH_NODE(target_a));
if (container == NULL) container = G_GRAPH_NODE(target_a);
pos.right_margin = g_flow_node_get_slot_offset(node, false, &node->exits[1]);
g_graph_node_set_pending_position(container, PPF_RIGHT_MARGIN, pos, base);
/* Trait vertical de l'autre côté... */
pos.direct_x = pos.right_margin;
dest_slot = g_flow_node_get_slot(target_b, true,
last, node->exits[1].group_index);
pos.direct_x -= g_flow_node_get_slot_offset(target_b, true, dest_slot);
g_graph_node_set_pending_position(G_GRAPH_NODE(target_b), PPF_DIRECT_X, pos, base);
}
break;
}
}
/******************************************************************************
* *
* Paramètres : node = noeud graphique démarrant la visite. *
* callback = ensemble de blocs à parcourir. *
* data = donnée utilisateur à associer au parcours. *
* *
* Description : Parcourt tous les blocs d'instructions dans un ordre donné. *
* *
* Retour : true si le parcours a été jusqu'à son terme, false sinon. *
* *
* Remarques : - *
* *
******************************************************************************/
static bool g_flow_node_visit_flow_nodes(GFlowNode *node, graph_node_visitor_cb callback, void *data)
{
return callback(G_GRAPH_NODE(node), GVS_NODE, data);
}
/******************************************************************************
* *
* Paramètres : node = noeud graphique à consulter. *
* instr = instruction à considérer. *
* *
* Description : Précise si le noeud a pour première instruction celle donnée.*
* *
* Retour : true si la première instruction du noeud est celle indiquée. *
* *
* Remarques : - *
* *
******************************************************************************/
bool g_flow_node_start_with(const GFlowNode *node, GArchInstruction *instr)
{
GArchInstruction *first; /* Première instr. du noeud */
g_flow_block_get_boundary(node->block, &first, NULL);
/*
do
{
vmpa_t a1, a2;
g_arch_instruction_get_location(instr, NULL, NULL, &a1);
g_arch_instruction_get_location(first, NULL, NULL, &a2);
printf(" -- compare %p (0x%08lx) vs %p (0x%08lx)\n",
instr, a1, first, a2);
}
while (0);
*/
return (first == instr);
}
/******************************************************************************
* *
* Paramètres : node = noeud graphique à consulter. *
* ranks = classement à mettre à jour. *
* *
* Description : Précise la hauteur minimale requise pour un noeud. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
void g_flow_node_register_rank(const GFlowNode *node, GGraphRanks *ranks)
{
unsigned int index; /* Indice du rang associé */
index = g_flow_node_get_rank(node);
g_graph_ranks_set_min_height(ranks, index, G_GRAPH_NODE(node)->alloc.height);
}
/******************************************************************************
* *
* Paramètres : node = noeud graphique à mettre à jour. *
* ranks = classement à consulter. *
* *
* Description : Définit l'ordonnée de l'espace attribué à un noeud. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
void g_flow_node_apply_rank(GFlowNode *node, GGraphRanks *ranks)
{
unsigned int index; /* Indice du rang associé */
index = g_flow_node_get_rank(node);
G_GRAPH_NODE(node)->alloc.y = g_graph_ranks_get_y_for_rank(ranks, index);
}
/******************************************************************************
* *
* Paramètres : node = noeud graphique à mettre à jour. *
* layout = disposition globale du graphique. *
* nodes = ensemble des noeuds en place. *
* *
* Description : Etablit les liaison entre un noeud et ses suivants. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
void g_flow_node_link(GFlowNode *node, GGraphLayout *layout, GGraphNode *nodes)
{
GArchInstruction *last; /* Dernière instr. du noeud */
size_t i; /* Boucle de parcours */
GFlowNode *target; /* Bloc visé par le lien */
node_slot_t *dest_slot; /* Accrochage d'arrivée */
EdgeColor color; /* Couleur du lien à créer */
GGraphEdge *edge; /* Lien à mettre en place */
g_flow_block_get_boundary(node->block, NULL, &last);
for (i = 0; i < node->exits_count; i++)
{
target = G_FLOW_NODE(find_node_for_instruction(nodes, node->exits[i].instr));
dest_slot = g_flow_node_get_slot(target, true,
last, node->exits[i].group_index);
switch (node->exits[i].type)
{
case ILT_JUMP_IF_TRUE:
color = EGC_GREEN;
break;
case ILT_JUMP_IF_FALSE:
color = EGC_RED;
break;
case ILT_LOOP:
color = EGC_BLUE;
break;
case ILT_CATCH_EXCEPTION:
color = EGC_DASHED_GRAY;
break;
default:
color = EGC_DEFAULT;
break;
}
edge = g_graph_edge_new(node, &node->exits[i], target, dest_slot, color);
g_graph_layout_add_edge(layout, edge);
}
}
/******************************************************************************
* *
* Paramètres : node = intermédiaire à consulter. *
* view = support de destination. *
* *
* Description : Place un noeud sur son support final. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
void g_flow_node_place(const GFlowNode *node, GtkGraphView *view)
{
printf("[put] %p (%d ; %d) - (%d ; %d)\n", node,
G_GRAPH_NODE(node)->alloc.x, G_GRAPH_NODE(node)->alloc.y,
G_GRAPH_NODE(node)->alloc.width, G_GRAPH_NODE(node)->alloc.height);
gtk_graph_view_put(view, GTK_WIDGET(node->view), &G_GRAPH_NODE(node)->alloc);
}
/* ---------------------------------------------------------------------------------- */
/* GESTION DES ACCROCHES D'UN NOEUD */
/* ---------------------------------------------------------------------------------- */
/******************************************************************************
* *
* Paramètres : node = intermédiaire à compléter. *
* *
* Description : Prépare les points d'entrées du noeud. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_flow_node_setup_entry_slots(GFlowNode *node)
{
GArchInstruction *first; /* Première instr. du noeud */
GArchInstruction **instrs; /* Instr. visée par une autre */
InstructionLinkType *types; /* Type de lien entre lignes */
size_t icount; /* Nombre de liens de dest. */
size_t usable; /* Nombre de liens utiles ici */
size_t i; /* Boucle de parcours */
size_t used; /* Nombre de liens utilisés */
g_flow_block_get_boundary(node->block, &first, NULL);
icount = g_arch_instruction_get_sources(first, &instrs, &types);
usable = 0;
for (i = 0; i < icount; i++)
switch (types[i])
{
case ILT_EXEC_FLOW:
case ILT_JUMP:
case ILT_CASE_JUMP:
case ILT_JUMP_IF_TRUE:
case ILT_JUMP_IF_FALSE:
case ILT_LOOP:
case ILT_CATCH_EXCEPTION:
usable++;
break;
default:
break;
}
if (usable == 0)
{
node->entries = NULL;
node->entries_count = 0;
}
else
{
node->entries = (node_slot_t *)calloc(usable, sizeof(node_slot_t));
node->entries_count = usable;
}
used = 0;
for (i = 0; i < icount; i++)
switch (types[i])
{
case ILT_EXEC_FLOW:
case ILT_JUMP:
case ILT_CASE_JUMP:
case ILT_JUMP_IF_TRUE:
case ILT_JUMP_IF_FALSE:
case ILT_LOOP:
case ILT_CATCH_EXCEPTION:
g_object_ref(instrs[i]);
node->entries[used].instr = instrs[i];
node->entries[used].type = types[i];
node->entries[used].group_index = g_arch_instruction_compute_group_index(&instrs[i],
instrs, icount);
node->entries[used].slot_index = i;
used++;
break;
default:
break;
}
assert(used == usable);
}
/******************************************************************************
* *
* Paramètres : node = intermédiaire à compléter. *
* *
* Description : Prépare les points de sorties du noeud. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_flow_node_setup_exit_slots(GFlowNode *node)
{
GArchInstruction *last; /* Dernière instr. du noeud */
GArchInstruction **instrs; /* Instr. visée par une autre */
InstructionLinkType *types; /* Type de lien entre lignes */
size_t icount; /* Nombre de liens de dest. */
size_t usable; /* Nombre de liens utiles ici */
size_t i; /* Boucle de parcours */
size_t used; /* Nombre de liens utilisés */
g_flow_block_get_boundary(node->block, NULL, &last);
icount = g_arch_instruction_get_destinations(last, &instrs, &types, NULL);
usable = 0;
for (i = 0; i < icount; i++)
switch (types[i])
{
case ILT_EXEC_FLOW:
case ILT_JUMP:
case ILT_CASE_JUMP:
case ILT_JUMP_IF_TRUE:
case ILT_JUMP_IF_FALSE:
case ILT_LOOP:
case ILT_CATCH_EXCEPTION:
usable++;
break;
default:
break;
}
if (usable == 0)
{
node->exits = NULL;
node->exits_count = 0;
}
else
{
node->exits = (node_slot_t *)calloc(usable, sizeof(node_slot_t));
node->exits_count = usable;
}
used = 0;
for (i = 0; i < icount; i++)
switch (types[i])
{
case ILT_EXEC_FLOW:
case ILT_JUMP:
case ILT_CASE_JUMP:
case ILT_JUMP_IF_TRUE:
case ILT_JUMP_IF_FALSE:
case ILT_LOOP:
case ILT_CATCH_EXCEPTION:
g_object_ref(instrs[i]);
node->exits[used].instr = instrs[i];
node->exits[used].type = types[i];
node->exits[used].group_index = g_arch_instruction_compute_group_index(&instrs[i],
instrs, icount);
node->exits[used].slot_index = i;
used++;
break;
default:
break;
}
assert(used == usable);
}
/******************************************************************************
* *
* Paramètres : node = noeud graphique à consulter. *
* entry = indique le type d'accrochage recherché. *
* instr = instruction visée. *
* index = indice de groupe pour départager au besoin. *
* *
* Description : Etablit un lien entre deux noeuds graphiques. *
* *
* Retour : Lien graphique mis en place. *
* *
* Remarques : - *
* *
******************************************************************************/
static node_slot_t *g_flow_node_get_slot(const GFlowNode *node, bool entry, GArchInstruction *instr, size_t index)
{
node_slot_t *result; /* Emplacement à retourner */
node_slot_t *list; /* Liste à parcourir */
size_t count; /* Taille de cette liste */
size_t i; /* Boucle de parcours */
if (entry)
{
list = node->entries;
count = node->entries_count;
}
else
{
list = node->exits;
count = node->exits_count;
}
for (i = 0; i < count; i++)
{
result = list + i;
if (result->instr == instr/* && result->group_index == index*/)
break;
}
return (i == count ? NULL : result);
}
/******************************************************************************
* *
* Paramètres : node = noeud graphique à consulter. *
* entry = indique le type d'accrochage recherché. *
* slot = accroche dont l'emplacement est à définir. *
* *
* Description : Localise un point d'accroche à un noeud graphique. *
* *
* Retour : Décallage relatif pour l'accroche fournie. *
* *
* Remarques : - *
* *
******************************************************************************/
static gint g_flow_node_get_slot_offset(const GFlowNode *node, bool entry, const node_slot_t *slot)
{
gint result; /* Valeur à retourner */
node_slot_t *slots; /* Accroches à parcourir */
size_t count; /* Nombre de ces points */
gint slots_width; /* Largeur des accroches */
gint slots_left; /* Abscisse de la première */
size_t index; /* Indice de l'accroche visée */
if (entry)
{
slots = node->entries;
count = node->entries_count;
}
else
{
slots = node->exits;
count = node->exits_count;
}
slots_width = (count - 1) * SPACE_BETWEEN_SLOT;
slots_left = (G_GRAPH_NODE(node)->alloc.width - slots_width) / 2;
index = (slot - slots);
/* BUG_ON(index >= count); */
result = slots_left + index * SPACE_BETWEEN_SLOT;
return result;
}
/******************************************************************************
* *
* Paramètres : node = noeud graphique à consulter. *
* entry = indique le type d'accrochage recherché. *
* slot = accroche dont l'emplacement est à définir. *
* *
* Description : Localise un point d'accroche à un noeud graphique. *
* *
* Retour : Emplacement réservé pour l'accroche fournie. *
* *
* Remarques : - *
* *
******************************************************************************/
GdkPoint g_flow_node_get_point_from_slot(const GFlowNode *node, bool entry, const node_slot_t *slot)
{
GGraphNode *base; /* Accès rapides */
GdkPoint result; /* Position à retourner */
node_slot_t *slots; /* Accroches à parcourir */
size_t count; /* Nombre de ces points */
gint slots_width; /* Largeur des accroches */
gint slots_left; /* Abscisse de la première */
size_t index; /* Indice de l'accroche visée */
base = G_GRAPH_NODE(node);
if (entry)
{
result.y = base->alloc.y;
slots = node->entries;
count = node->entries_count;
}
else
{
result.y = base->alloc.y + base->alloc.height;
slots = node->exits;
count = node->exits_count;
}
slots_width = (count - 1) * SPACE_BETWEEN_SLOT;
slots_left = base->alloc.x + (base->alloc.width - slots_width) / 2;
index = (slot - slots)/* / sizeof(node_slot_t)*/;
/* BUG_ON(index >= count); */
result.x = slots_left + index * SPACE_BETWEEN_SLOT;
#if 0
slots_width = (count - 1) * SPACE_BETWEEN_SLOT;
slots_left = base->alloc.x + (base->alloc.width - slots_width) / 2;
index = (slot - slots)/* / sizeof(node_slot_t)*/;
/* BUG_ON(index >= count); */
result.x = slots_left + index * SPACE_BETWEEN_SLOT;
#endif
return result;
}