/* Chrysalide - Outil d'analyse de fichiers binaires
* node.c - éléments de graphiques chez dot
*
* Copyright (C) 2009-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 "node.h"
#include
#include
#include
#include
#include "node-int.h"
#include "nodes/flow.h"
#include "nodes/virtual.h"
#include "../../common/extstr.h"
/* -------------------------- GESTION DES NOEUDS A L'UNITE -------------------------- */
/* Initialise la classe des intermédiaires avec les noeuds dot. */
static void g_graph_node_class_init(GGraphNodeClass *);
/* Initialise la classe des intermédiaires avec les noeuds dot. */
static void g_graph_node_init(GGraphNode *);
/* Supprime toutes les références externes. */
static void g_graph_node_dispose(GGraphNode *);
/* Procède à la libération totale de la mémoire. */
static void g_graph_node_finalize(GGraphNode *);
/* ---------------------------------------------------------------------------------- */
/* GESTION DES NOEUDS A L'UNITE */
/* ---------------------------------------------------------------------------------- */
/* Indique le type définit par la GLib pour le noeud. */
G_DEFINE_TYPE(GGraphNode, g_graph_node, G_TYPE_OBJECT);
/******************************************************************************
* *
* Paramètres : klass = classe à initialiser. *
* *
* Description : Initialise la classe des intermédiaires avec les noeuds dot. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_graph_node_class_init(GGraphNodeClass *klass)
{
GObjectClass *object; /* Autre version de la classe */
object = G_OBJECT_CLASS(klass);
object->dispose = (GObjectFinalizeFunc/* ! */)g_graph_node_dispose;
object->finalize = (GObjectFinalizeFunc)g_graph_node_finalize;
}
/******************************************************************************
* *
* Paramètres : node = instance à initialiser. *
* *
* Description : Initialise la classe des intermédiaires avec les noeuds dot. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_graph_node_init(GGraphNode *node)
{
node->alloc.x = UNINITIALIZED_NODE_POS;
node->alloc.y = UNINITIALIZED_NODE_POS;
}
/******************************************************************************
* *
* Paramètres : node = instance d'objet GLib à traiter. *
* *
* Description : Supprime toutes les références externes. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_graph_node_dispose(GGraphNode *node)
{
G_OBJECT_CLASS(g_graph_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_graph_node_finalize(GGraphNode *node)
{
G_OBJECT_CLASS(g_graph_node_parent_class)->finalize(G_OBJECT(node));
}
/******************************************************************************
* *
* Paramètres : node = noeud graphique à consulter. *
* *
* Description : Fournit le rang du noeud dans le graphique. *
* *
* Retour : Indice supérieur ou égal à zéro. *
* *
* Remarques : - *
* *
******************************************************************************/
unsigned int g_graph_node_get_rank(const GGraphNode *node)
{
return G_GRAPH_NODE_GET_CLASS(node)->get_rank(node);
}
/******************************************************************************
* *
* Paramètres : node = noeud graphique à manipuler. *
* *
* Description : Réinitialise la position d'un noeud de graphique. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
void g_graph_node_reset_position(GGraphNode *node)
{
node->alloc.x = UNINITIALIZED_NODE_POS;
node->alloc.y = UNINITIALIZED_NODE_POS;
node->pending_flag = PPF_NONE;
if (G_GRAPH_NODE_GET_CLASS(node)->reset_pos != NULL)
G_GRAPH_NODE_GET_CLASS(node)->reset_pos(node);
}
/******************************************************************************
* *
* Paramètres : node = noeud d'encapsulation à traiter. *
* nodes = ensemble des noeuds en place. *
* *
* Description : Définit les abscisses relatives du contenu d'un noeud. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
void g_graph_node_prepare_x_line(GGraphNode *node, GGraphNode *nodes)
{
G_GRAPH_NODE_GET_CLASS(node)->prepare_x(node, nodes);
}
/******************************************************************************
* *
* Paramètres : node = noeud graphique à manipuler. *
* *
* Description : Applique une position finale au noeud. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
void g_graph_node_apply_position(GGraphNode *node)
{
gint x_pos; /* Position de référence */
GGraphNode *ref; /* Accès rapide */
if (G_GRAPH_NODE_GET_CLASS(node)->apply_pos != NULL)
G_GRAPH_NODE_GET_CLASS(node)->apply_pos(node);
switch (node->pending_flag)
{
case PPF_DIRECT_X:
assert(g_graph_node_has_x_position(node->pending_pos.relative_ref));
g_graph_node_get_position(node->pending_pos.relative_ref, &x_pos, NULL);
x_pos += node->pending_pos.direct_x;
g_graph_node_set_x_position(node, x_pos);
break;
case PPF_LEFT_MARGIN:
assert(g_graph_node_has_x_position(node->pending_pos.relative_ref));
g_graph_node_get_position(node->pending_pos.relative_ref, &x_pos, NULL);
x_pos += EDGE_SLOT_HORIZ_MARGIN + node->pending_pos.left_margin;
g_graph_node_set_x_position(node, x_pos);
break;
case PPF_RIGHT_MARGIN:
assert(g_graph_node_has_x_position(node->pending_pos.relative_ref));
g_graph_node_get_position(node->pending_pos.relative_ref, &x_pos, NULL);
x_pos += node->pending_pos.right_margin;
x_pos -= (EDGE_SLOT_HORIZ_MARGIN + node->alloc.width);
g_graph_node_set_x_position(node, x_pos);
break;
case PPF_LEFT_NODE:
ref = node->pending_pos.left_node;
x_pos = ref->alloc.x - NODE_HORIZONTAL_MARGIN - node->alloc.width;
g_graph_node_set_x_position(node, x_pos);
break;
case PPF_RIGHT_NODE:
ref = node->pending_pos.right_node;
x_pos = ref->alloc.x + ref->alloc.width - NODE_HORIZONTAL_MARGIN;
g_graph_node_set_x_position(node, x_pos);
break;
default:
/* Position traitée par l'appelant */
break;
}
}
/******************************************************************************
* *
* Paramètres : node = noeud graphique à manipuler. *
* Paramètres : node = noeud graphique à manipuler. *
* x = abscisse à intégrer. *
* direct = indique un tracé direct éventuel. *
* *
* Description : Altère la position du noeud d'encapsulation. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
void g_graph_node_set_x_position(GGraphNode *node, gint x)
{
if (G_GRAPH_NODE_GET_CLASS(node)->set_pos != NULL && x != GRAPH_HORIZONTAL_MARGIN)
G_GRAPH_NODE_GET_CLASS(node)->set_pos(node, x);
node->alloc.x = x;
}
/******************************************************************************
* *
* Paramètres : node = noeud graphique à manipuler. *
* flag = nature de l'indication à intégrer. *
* pos = argument supplémentaire à venir chercher. *
* *
* Description : Prépare la position du noeud pour l'alignement des liens. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
void g_graph_node_set_pending_position(GGraphNode *node, PendingPositionFlags flag, pending_position pos)
{
if (node->pending_flag != PPF_NONE && node->pending_flag != PPF_MIDDLE_OF)
return;
node->pending_flag = flag;
node->pending_pos = pos;
}
/******************************************************************************
* *
* Paramètres : node = noeud graphique à manipuler. *
* flag = nature de l'indication à intégrer. [OUT] *
* pos = argument supplémentaire à venir chercher. [OUT] *
* *
* Description : Indique la position du noeud pour l'alignement des liens. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
void g_graph_node_get_pending_position(GGraphNode *node, PendingPositionFlags *flag, pending_position *pos)
{
*flag = node->pending_flag;
if (pos != NULL)
*pos = node->pending_pos;
}
/******************************************************************************
* *
* Paramètres : node = noeud graphique à consulter. *
* x = éventuelle abscisse à recevoir ou NULL. [OUT] *
* y = éventuelle ordonnée à recevoir ou NULL. [OUT] *
* *
* Description : Fournit la position du noeud d'encapsulation. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
void g_graph_node_get_position(const GGraphNode *node, gint *x, gint *y)
{
if (x != NULL) *x = node->alloc.x;
if (y != NULL) *y = node->alloc.y;
}
/******************************************************************************
* *
* Paramètres : node = noeud graphique à consulter. *
* *
* Description : Indique l'espace requis pour un noeud d'encapsulation. *
* *
* Retour : Espace constitué, entièrement ou non. *
* *
* Remarques : - *
* *
******************************************************************************/
GtkAllocation g_graph_node_get_allocation(const GGraphNode *node)
{
return node->alloc;
}
/******************************************************************************
* *
* 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 noeuds graphiques dans un ordre donné. *
* *
* Retour : true si le parcours a été jusqu'à son terme, false sinon. *
* *
* Remarques : - *
* *
******************************************************************************/
bool g_graph_node_visit_nodes(GGraphNode *node, graph_node_visitor_cb callback, void *data)
{
return G_GRAPH_NODE_GET_CLASS(node)->visit(node, callback, data);
}
/******************************************************************************
* *
* Paramètres : nodes = noeud au sommet de la hiérarchie. *
* target = élément à retrouver dans l'ensemble de noeuds. *
* *
* Description : Recherche le noeud contenant un autre noeud. *
* *
* Retour : Noeud trouvé ou NULL si aucun. *
* *
* Remarques : - *
* *
******************************************************************************/
GGraphNode *g_graph_node_find_container(GGraphNode *nodes, GGraphNode *target)
{
GGraphNode *result; /* Trouvaille à retourner */
result = NULL;
if (G_GRAPH_NODE_GET_CLASS(nodes)->contain != NULL)
result = G_GRAPH_NODE_GET_CLASS(nodes)->contain(nodes, target);
return result;
}
/******************************************************************************
* *
* Paramètres : nodes = noeud au sommet de la hiérarchie. *
* ref = noeud indiquant le niveau de référence. *
* target = élément à retrouver dans l'ensemble de noeuds. *
* *
* Description : Recherche le noeud contenant un autre noeud à un même niveau.*
* *
* Retour : Noeud trouvé ou NULL si aucun. *
* *
* Remarques : - *
* *
******************************************************************************/
GGraphNode *g_graph_node_find_container_at_same_level(GGraphNode *nodes, GGraphNode *ref, GGraphNode *target)
{
GGraphNode *result; /* Trouvaille à retourner */
GGraphNode *level; /* Niveau de référence */
GGraphNode *container; /* Support de la cible */
result = NULL;
level = g_graph_node_find_container(nodes, ref);
container = g_graph_node_find_container(nodes, target);
if (container == level)
result = target;
else
{
if (container == NULL)
result = NULL;
else
result = g_graph_node_find_container_at_same_level(nodes, ref, container);
}
return result;
}
/* ---------------------------------------------------------------------------------- */
/* MANIPULATION D'ENSEMBLES DE NOEUDS */
/* ---------------------------------------------------------------------------------- */
/******************************************************************************
* *
* Paramètres : views = liste de vues à parcourir. *
* count = taille de la liste. *
* addrt = adresse de début du noeud recherché. *
* *
* Description : Recherche une vue donnée dans une série de vues. *
* *
* Retour : Vue trouvée ou NULL si aucun. *
* *
* Remarques : - *
* *
******************************************************************************/
GtkBufferView *find_graph_view_by_start_address(GtkBufferView **views, size_t count, const vmpa2t *addr)
{
GtkBufferView *result; /* Trouvaille à remonter */
size_t i; /* Boucle de parcours */
GBufferView *buffer; /* Tampon d'une partie de code */
vmpa2t start; /* Adresse de départ du tampon */
result = NULL;
for (i = 0; i < count && result == NULL; i++)
{
buffer = gtk_buffer_view_get_buffer(views[i]);
g_buffer_view_get_restrictions(buffer, &start, NULL);
if (cmp_vmpa(&start, addr) == 0)
result = views[i];
}
return result;
}
/******************************************************************************
* *
* Paramètres : block = ensemble des blocs basiques déjà découpés. *
* views = morceaux de code à afficher de façon organisée. *
* count = quantité de ces morceaux de code. *
* *
* Description : Réalise une conversion de blocs en noeuds. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
GGraphNode *convert_blocks_into_nodes(GInstrBlock *block, GtkBufferView **views, size_t count)
{
GGraphNode *result; /* Instance nouvelle à renvoyer*/
vmpa2t start; /* Adresse de départ */
GtkBufferView *view; /* Vue existante à retrouver */
size_t max; /* Nombre de blocs à gérer */
size_t i; /* Boucle de parcours */
GInstrBlock *sub_block; /* Sous-bloc intégré */
GGraphNode *child; /* Conversion à mémoriser */
result = NULL;
if (G_IS_FLOW_BLOCK(block))
{
g_flow_block_get_boundary_addresses(G_FLOW_BLOCK(block), &start, NULL);
view = find_graph_view_by_start_address(views, count, &start);
result = g_flow_node_new(G_FLOW_BLOCK(block), view);
}
else if (G_IS_VIRTUAL_BLOCK(block))
{
result = g_virtual_node_new(G_VIRTUAL_BLOCK(block));
max = g_virtual_block_count_children(G_VIRTUAL_BLOCK(block));
for (i = 0; i < max; i++)
{
sub_block = g_virtual_block_get_child(G_VIRTUAL_BLOCK(block), i);
child = convert_blocks_into_nodes(sub_block, views, count);
g_virtual_node_add_child(G_VIRTUAL_NODE(result), child);
}
}
/*else BUG_ON(1); */
return result;
}
/******************************************************************************
* *
* Paramètres : nodes = noeud au sommet de la hiérarchie. *
* instr = instruction à retrouver. *
* entry = position de cette instruction : première ou dernière.*
* *
* Description : Recherche le noeud contenant une instruction donnée. *
* *
* Retour : Noeud trouvé ou NULL. *
* *
* Remarques : - *
* *
******************************************************************************/
GGraphNode *_find_node_for_instruction(GGraphNode *nodes, GArchInstruction *instr, bool entry)
{
GGraphNode *result; /* Trouvaille à retourner */
struct visit_params {
GArchInstruction *instr; /* Instruction recherchée */
bool entry; /* Première ou dernière ? */
GGraphNode *found; /* Remontée du noeud trouvé */
} params; /* Paramètres pour le parcours */
params.instr = instr;
params.entry = entry;
params.found = NULL;
bool _find_node_cb(GFlowNode *node, GNodeVisitState state, struct visit_params *params)
{
bool result;
if (state == GVS_NODE)
{
if ((params->entry && g_flow_node_start_with(node, params->instr))
|| (!params->entry && g_flow_node_end_with(node, params->instr)))
{
params->found = G_GRAPH_NODE(node);
}
result = (params->found == NULL);
}
else result = true;
return result;
}
g_graph_node_visit_nodes(nodes, (graph_node_visitor_cb)_find_node_cb, ¶ms);
result = params.found;
return result;
}