/* 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 "node-int.h"
#include "nodes/flow.h"
#include "nodes/virtual.h"
#include "../../common/extstr.h"
/* -------------------------- GESTION DES NOEUDS A L'UNITE -------------------------- */
/* Taille maximale des lignes de description de noeud */
#define NODE_DESC_LEN 128
/* 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 */
GdkScreen *screen; /* Ecran par défaut */
gint width; /* Largeur d'écran en pixels */
gint height; /* Hauteur d'écran en pixels */
gint width_mm; /* Largeur d'écran en mm. */
gint height_mm; /* Hauteur d'écran en mm. */
object = G_OBJECT_CLASS(klass);
object->dispose = (GObjectFinalizeFunc/* ! */)g_graph_node_dispose;
object->finalize = (GObjectFinalizeFunc)g_graph_node_finalize;
/* Calcul des résolutions */
screen = gdk_screen_get_default();
width = gdk_screen_get_width(screen);
height = gdk_screen_get_height(screen);
width_mm = gdk_screen_get_width_mm(screen);
height_mm = gdk_screen_get_height_mm(screen);
/**
* Il y a 2.54 centimètres, soit 25.4 millimètres, dans un pouce.
* On a donc :
*
* dpi = N pixels / (M millimètres / (25.4 millimètres / 1 pouce))
* = N pixels / (M pouces / 25.4)
* = N * 25.4 pixels / M pouces
*
*/
if (width_mm > 0 && height_mm > 0)
{
klass->dpi_x = (width * 25.4) / (double)width_mm;
klass->dpi_y = (height * 25.4) / (double)height_mm;
}
else
{
klass->dpi_x = 96;
klass->dpi_y = 96;
}
klass->dpi_x = 72;
klass->dpi_y = 72;
}
/******************************************************************************
* *
* 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_unref(G_OBJECT(node->view));
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 : view = morceau d'affichage à représenter. *
* *
* Description : Constitue un intermédiaire entre un noeud dot et du code. *
* *
* Retour : Adresse de la structure mise en place. *
* *
* Remarques : - *
* *
******************************************************************************/
GGraphNode *g_graph_node_new(GtkWidget *view)
{
GGraphNode *result; /* Structure à retourner */
result = g_object_new(G_TYPE_GRAPH_NODE, NULL);
result->view = view;
g_object_ref(G_OBJECT(view));
snprintf(result->name, NODE_NAME_LEN, "_%p", result->view);
return 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 : - *
* *
******************************************************************************/
unsigned int g_graph_node_get_rank(const GGraphNode *node)
{
return 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;
if (node->reset_pos != NULL)
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)
{
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 (node->apply_pos != NULL)
node->apply_pos(node);
switch (node->pending_flag)
{
case PPF_DIRECT_X:
g_graph_node_get_position(node->pending_rel, &x_pos, NULL);
x_pos += node->pending_pos.direct_x;
g_graph_node_set_x_position(node, x_pos);
break;
case PPF_LEFT_MARGIN:
g_graph_node_get_position(node->pending_rel, &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:
g_graph_node_get_position(node->pending_rel, &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;
node->alloc.x = ref->alloc.x - NODE_HORIZONTAL_MARGIN - node->alloc.width;
break;
case PPF_RIGHT_NODE:
ref = node->pending_pos.right_node;
node->alloc.x = ref->alloc.x + ref->alloc.width - NODE_HORIZONTAL_MARGIN;
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 (node->set_pos != NULL && x != GRAPH_HORIZONTAL_MARGIN)
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. *
* rel = éventuelle référence pour une relation relative. *
* *
* 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, GGraphNode *rel)
{
node->pending_pos = pos;
node->pending_flag = flag;
node->pending_rel = rel;
}
/******************************************************************************
* *
* 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)
{
*pos = node->pending_pos;
*flag = node->pending_flag;
}
/******************************************************************************
* *
* 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 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 (nodes->contain != NULL)
result = 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;
}
/******************************************************************************
* *
* Paramètres : node = intermédiaire à consulter. *
* rank = description pour dot à compléter. *
* *
* Description : Inscrit le noeud au rang donné. *
* *
* Retour : Description dûment complétée. *
* *
* Remarques : - *
* *
******************************************************************************/
char *g_graph_node_append_name_to_rank(const GGraphNode *node, char *rank)
{
char buffer[NODE_DESC_LEN]; /* Tampon pour les commandes */
snprintf(buffer, NODE_DESC_LEN, " %s;", node->name);
if (rank == NULL)
rank = strdup(buffer);
else
rank = stradd(rank, buffer);
return rank;
}
/******************************************************************************
* *
* Paramètres : node = intermédiaire à consulter. *
* cmds = description pour dot à compléter. *
* level = profondeur du noeud pour l'indentation. *
* *
* Description : Déclare l'intermédiaire en tant que noeud pour dot. *
* *
* Retour : Description dûment complétée. *
* *
* Remarques : - *
* *
******************************************************************************/
char *g_graph_node_register_for_dot(const GGraphNode *node, char *cmds, unsigned int level)
{
GtkRequisition requisition; /* Taille à l'écran requise */
unsigned int i; /* Boucle de parcours */
char buffer[NODE_DESC_LEN]; /* Tampon pour les commandes */
gtk_widget_get_preferred_size(node->view, NULL, &requisition);
for (i = 0; i < level; i++)
cmds = stradd(cmds, DOT_IDENT);
snprintf(buffer, NODE_DESC_LEN, "subgraph cluster%s {\n", node->name);
cmds = stradd(cmds, buffer);
for (i = 0; i < (level + 1); i++)
cmds = stradd(cmds, DOT_IDENT);
cmds = stradd(cmds, "style=invisible;\n");
for (i = 0; i < (level + 1); i++)
cmds = stradd(cmds, DOT_IDENT);
cmds = stradd(cmds, node->name);
cmds = stradd(cmds, " [shape=box, fixedsize ");
snprintf(buffer, NODE_DESC_LEN, ", width=\"%g\"",
requisition.width / G_GRAPH_NODE_GET_CLASS(node)->dpi_x);
cmds = stradd(cmds, buffer);
snprintf(buffer, NODE_DESC_LEN, ", height=\"%g\"",
requisition.height / G_GRAPH_NODE_GET_CLASS(node)->dpi_y);
cmds = stradd(cmds, buffer);
cmds = stradd(cmds, "];\n");
for (i = 0; i < level; i++)
cmds = stradd(cmds, DOT_IDENT);
cmds = stradd(cmds, "}\n");
return cmds;
}
/******************************************************************************
* *
* Paramètres : node = intermédiaire à consulter. *
* view = support de destination. *
* x = abscisse du point d'intégration. *
* y = ordonnée du point d'intégration. *
* *
* Description : Place le morceau de code de l'intermédiaire à l'écran. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
void g_graph_node_place_old(GGraphNode *node, GtkGraphView *view, gint x, gint y)
{
GtkRequisition requisition; /* Taille à l'écran actuelle */
gtk_widget_get_preferred_size(node->view, NULL, &requisition);
x -= requisition.width / 2;
y -= requisition.height / 2;
node->alloc.x = x;
node->alloc.y = y;
node->alloc.width = requisition.width;
node->alloc.height = requisition.height;
gtk_graph_view_put(view, node->view, &node->alloc);
}
/******************************************************************************
* *
* Paramètres : node = intermédiaire à consulter. *
* x = abscisse du point à relier. *
* y = ordonnée du point à relier. *
* points = liste de points à mettre à jour. [OUT] *
* count = taille de cette même liste. [OUT] *
* *
* Description : Etablit une jonction ferme avec un noeud. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
void g_graph_node_connect(const GGraphNode *node, gint x, gint y, GdkPoint **points, size_t *count)
{
const GtkAllocation *alloc; /* Emplacement du bloc rattaché*/
alloc = &node->alloc;
*points = (GdkPoint *)realloc(*points, ++(*count) * sizeof(GdkPoint));
/* Si le point est sur la gauche... */
if (x < alloc->x)
(*points)[*count - 1].x = alloc->x;
/* Ou s'il est sur la droite... */
else if (x > (alloc->x + alloc->width))
(*points)[*count - 1].x = alloc->x + alloc->width;
/* Ou s'il se trouve déjà bien placé... */
else
(*points)[*count - 1].x = x;
/* Si le point est au dessus... */
if (y < alloc->y)
(*points)[*count - 1].y = alloc->y;
/* Ou s'il est en dessous... */
else if (y > (alloc->y + alloc->height))
(*points)[*count - 1].y = alloc->y + alloc->height;
/* Ou s'il se trouve déjà bien placé... */
else
(*points)[*count - 1].y = y;
}
/* ---------------------------------------------------------------------------------- */
/* 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(GTK_BUFFER_VIEW(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. *
* *
* Description : Recherche le noeud contenant une instruction donnée. *
* *
* Retour : Noeud trouvé ou NULL. *
* *
* Remarques : - *
* *
******************************************************************************/
GGraphNode *find_node_for_instruction(GGraphNode *nodes, GArchInstruction *instr)
{
GGraphNode *result; /* Trouvaille à retourner */
struct visit_params {
GArchInstruction *instr; /* Instruction recherchée */
GGraphNode *found; /* Remontée du noeud trouvé */
} params; /* Paramètres pour le parcours */
params.instr = instr;
params.found = NULL;
bool _find_node_cb(GFlowNode *node, GNodeVisitState state, struct visit_params *params)
{
bool result;
if (state == GVS_NODE)
{
if (g_flow_node_start_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;
}
/******************************************************************************
* *
* Paramètres : nodes = liste de noeuds à parcourir. *
* count = taille de la liste. *
* addrt = adresse de début du noeud recherché. *
* *
* Description : Recherche un noeud donné dans une série de noeuds. *
* *
* Retour : Noeud trouvé ou NULL si aucun. *
* *
* Remarques : - *
* *
******************************************************************************/
GGraphNode *find_graph_node_by_start_address(GGraphNode **nodes, size_t count, const vmpa2t *addr)
{
GGraphNode *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(GTK_BUFFER_VIEW(nodes[i]->view));
g_buffer_view_get_restrictions(buffer, &start, NULL);
if (cmp_vmpa(&start, addr) == 0)
result = nodes[i];
}
return result;
}
/******************************************************************************
* *
* Paramètres : nodes = liste de noeuds à parcourir. *
* count = taille de la liste. *
* target = nom du noeud recherché. *
* *
* Description : Recherche un noeud donné dans une série de noeuds. *
* *
* Retour : Noeud trouvé ou NULL si aucun. *
* *
* Remarques : - *
* *
******************************************************************************/
GGraphNode *find_graph_node_by_name(GGraphNode **nodes, size_t count, const char *target)
{
GGraphNode *result; /* Trouvaille à remonter */
size_t i; /* Boucle de parcours */
result = NULL;
for (i = 0; i < count && result == NULL; i++)
if (strcmp(nodes[i]->name, target) == 0)
result = nodes[i];
return result;
}