/* Chrysalide - Outil d'analyse de fichiers binaires
* virtual.c - encapsulation graphique des blocs virtuels
*
* 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 "virtual.h"
#include
#include
#include
#include "flow.h"
#include "../node-int.h"
/* ----------------------- MANIPULATION DES PORTES VERTICALES ----------------------- */
/* Etendue verticale d'un lien */
typedef struct _reserved_vspan
{
unsigned int r1; /* Départ d'une ligne */
unsigned int r2; /* Arrivée de cette même ligne */
} reserved_vspan;
/* Lignes de liens verticales au sein d'un même groupe */
typedef struct _vert_links
{
reserved_vspan *vspans; /* Lignes sans chevauchement */
size_t count; /* Nombre de ces lignes */
} vert_links;
/* Initialise les futures portées d'un même niveau. */
static void init_vertical_links(vert_links *);
/* Regarde si des portées verticales se chevauchent ou non. */
static bool is_intersection_with_vertical_spans(const vert_links *, const reserved_vspan *);
/* Ajoute une réservation à un ensemble de portées verticales. */
static void extend_vertical_links_spans(vert_links *, const reserved_vspan *);
/* ---------------------- REPRESENTATIONS DES GROUPES LOGIQUES ---------------------- */
/* Représentation d'un étage */
typedef struct _virtual_level
{
unsigned int rank; /* Rang associé à l'étage */
GGraphNode **children; /* Noeuds englobés */
size_t count; /* Quantité de ces noeuds */
} virtual_level;
/* Encapsulation graphique d'un bloc virtuel (instance) */
struct _GVirtualNode
{
GGraphNode parent; /* A laisser en premier */
GVirtualBlock *block; /* Bloc virtuel associé */
GGraphNode **children; /* Noeuds englobés */
size_t count; /* Quantité de ces noeuds */
virtual_level *levels; /* Différents étages de noeuds */
size_t lcount; /* Nombre de ces étages */
vert_links *left_padding; /* Espace à gauche pour liens */
vspan_slot_t left_count; /* Nombre de largeurs réservées*/
vert_links *right_padding; /* Espace à droite pour liens */
vspan_slot_t right_count; /* Nombre de largeurs réservées*/
};
/* Encapsulation graphique d'un bloc virtuel (classe) */
struct _GVirtualNodeClass
{
GGraphNodeClass parent; /* A laisser en premier */
};
/* Initialise la classe des encapsulations de blocs virtuels. */
static void g_virtual_node_class_init(GVirtualNodeClass *);
/* Initialise une encapsulation de bloc virtuel. */
static void g_virtual_node_init(GVirtualNode *);
/* Supprime toutes les références externes. */
static void g_virtual_node_dispose(GVirtualNode *);
/* Procède à la libération totale de la mémoire. */
static void g_virtual_node_finalize(GVirtualNode *);
/* Fournit le rang du noeud dans le graphique. */
static unsigned int g_virtual_node_get_rank(const GVirtualNode *);
/* Réinitialise la position d'un noeud d'encapsulation. */
static void g_virtual_node_reset_position(GVirtualNode *);
/* Définit les abscisses relatives du contenu d'un noeud. */
static void g_virtual_node_prepare_x_line(GVirtualNode *, GGraphNode *);
/* Applique une position finale au noeud. */
static void g_virtual_node_apply_position(GVirtualNode *);
/* Définit les abscisses relatives du contenu d'un noeud. */
static void g_virtual_node_apply_x_line(GVirtualNode *);
/* Met à jour la largeur interne du noeud. */
static void g_virtual_node_compute_width(GVirtualNode *);
/* Altère la position du noeud d'encapsulation. */
static void g_virtual_node_set_position(GVirtualNode *, gint);
/* Parcourt tous les blocs d'instructions dans un ordre donné. */
static bool g_virtual_node_visit_flow_nodes(GVirtualNode *, graph_node_visitor_cb, void *);
/* Recherche le noeud contenant un autre noeud. */
static GGraphNode *g_virtual_node_find_container(GVirtualNode *, GGraphNode *);
/* ---------------------------------------------------------------------------------- */
/* MANIPULATION DES PORTES VERTICALES */
/* ---------------------------------------------------------------------------------- */
/******************************************************************************
* *
* Paramètres : links = liste à initialiser. *
* *
* Description : Initialise les futures portées d'un même niveau. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void init_vertical_links(vert_links *links)
{
links->vspans = NULL;
links->count = 0;
}
/******************************************************************************
* *
* Paramètres : links = liste de portées déjà en place. *
* vspan = nouvelle portée à insérer quelque part. *
* *
* Description : Regarde si des portées verticales se chevauchent ou non. *
* *
* Retour : true si les portées peuvent cohabiter, false sinon. *
* *
* Remarques : - *
* *
******************************************************************************/
static bool is_intersection_with_vertical_spans(const vert_links *links, const reserved_vspan *vspan)
{
bool result; /* Bilan d'analyse à retourner */
size_t i; /* Boucle de parcours */
result = false;
for (i = 0; i < links->count && !result; i++)
{
if (vspan->r1 < links->vspans[i].r1)
result = vspan->r2 >= links->vspans[i].r1;
else if (vspan->r1 > links->vspans[i].r2)
result = vspan->r2 <= links->vspans[i].r2;
else
{
result = links->vspans[i].r1 < vspan->r1 && vspan->r1 < links->vspans[i].r2;
result |= links->vspans[i].r1 < vspan->r2 && vspan->r2 < links->vspans[i].r2;
}
}
return result;
}
/******************************************************************************
* *
* Paramètres : spans = liste de portées déjà en place. *
* vspan = nouvelle portée à insérer quelque part. *
* *
* Description : Ajoute une réservation à un ensemble de portées verticales. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void extend_vertical_links_spans(vert_links *links, const reserved_vspan *new)
{
links->vspans = (reserved_vspan *)realloc(links->vspans,
++links->count * sizeof(reserved_vspan));
if (new->r1 <= new->r2)
links->vspans[links->count - 1] = *new;
else
{
links->vspans[links->count - 1].r1 = new->r2;
links->vspans[links->count - 1].r2 = new->r1;
}
}
/* ---------------------------------------------------------------------------------- */
/* REPRESENTATIONS DES GROUPES LOGIQUES */
/* ---------------------------------------------------------------------------------- */
/* Indique le type définit par la GLib pour l'encapsulation d'un bloc virtuel. */
G_DEFINE_TYPE(GVirtualNode, g_virtual_node, G_TYPE_GRAPH_NODE);
/******************************************************************************
* *
* Paramètres : klass = classe à initialiser. *
* *
* Description : Initialise la classe des encapsulations de blocs virtuels. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_virtual_node_class_init(GVirtualNodeClass *klass)
{
GObjectClass *object; /* Autre version de la classe */
GGraphNodeClass *node_class; /* Version parente de la classe*/
object = G_OBJECT_CLASS(klass);
node_class = G_GRAPH_NODE_CLASS(klass);
object->dispose = (GObjectFinalizeFunc/* ! */)g_virtual_node_dispose;
object->finalize = (GObjectFinalizeFunc)g_virtual_node_finalize;
node_class->get_rank = (get_node_rank_fc)g_virtual_node_get_rank;
node_class->reset_pos = (node_reset_pos_fc)g_virtual_node_reset_position;
node_class->prepare_x = (node_prepare_x_fc)g_virtual_node_prepare_x_line;
node_class->apply_pos = (node_apply_pos_fc)g_virtual_node_apply_position;
node_class->set_pos = (node_set_pos_fc)g_virtual_node_set_position;
node_class->visit = (visit_flow_nodes_fc)g_virtual_node_visit_flow_nodes;
node_class->contain = (find_container_fc)g_virtual_node_find_container;
}
/******************************************************************************
* *
* Paramètres : node = instance à initialiser. *
* *
* Description : Initialise une encapsulation de bloc virtuel. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_virtual_node_init(GVirtualNode *node)
{
}
/******************************************************************************
* *
* Paramètres : node = instance d'objet GLib à traiter. *
* *
* Description : Supprime toutes les références externes. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_virtual_node_dispose(GVirtualNode *node)
{
size_t i; /* Boucle de parcours */
g_object_unref(G_OBJECT(node->block));
for (i = 0; i < node->count; i++)
g_object_unref(G_OBJECT(node->children[i]));
if (node->children != NULL)
free(node->children);
G_OBJECT_CLASS(g_virtual_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_virtual_node_finalize(GVirtualNode *node)
{
G_OBJECT_CLASS(g_virtual_node_parent_class)->finalize(G_OBJECT(node));
}
/******************************************************************************
* *
* Paramètres : block = bloc virtuel représenté graphiquement. *
* *
* Description : Encapsule graphiquement un bloc virtuel. *
* *
* Retour : Adresse de la structure mise en place. *
* *
* Remarques : - *
* *
******************************************************************************/
GGraphNode *g_virtual_node_new(GVirtualBlock *block)
{
GVirtualNode *result; /* Structure à retourner */
result = g_object_new(G_TYPE_VIRTUAL_NODE, NULL);
g_object_ref(G_OBJECT(block));
result->block = block;
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_virtual_node_get_rank(const GVirtualNode *node)
{
/* BUG_ON(node->count == 0) */
return g_graph_node_get_rank(node->children[0]);
}
/******************************************************************************
* *
* Paramètres : node = noeud graphique à manipuler. *
* *
* Description : Réinitialise la position d'un noeud d'encapsulation. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_virtual_node_reset_position(GVirtualNode *node)
{
size_t i; /* Boucle de parcours */
for (i = 0; i < node->count; i++)
g_graph_node_reset_position(node->children[i]);
}
/******************************************************************************
* *
* 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 : - *
* *
******************************************************************************/
static void g_virtual_node_prepare_x_line(GVirtualNode *node, GGraphNode *nodes)
{
size_t i; /* Boucle de parcours */
for (i = 0; i < node->count; i++)
g_graph_node_prepare_x_line(node->children[i], nodes);
}
/******************************************************************************
* *
* Paramètres : node = noeud d'encapsulation à traiter. *
* *
* Description : Applique une position finale au noeud. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_virtual_node_apply_position(GVirtualNode *node)
{
gint min; /* Valeur minimale rencontrée */
size_t i; /* Boucle de parcours */
gint x_pos; /* Nouvelle position #1 */
gint offset; /* Décallage à faire suivre */
g_virtual_node_apply_x_line(node);
/* Collecte de l'ensemble des positions */
min = 0;
for (i = 0; i < node->count; i++)
{
g_graph_node_get_position(node->children[i], &x_pos, NULL);
min = MIN(min, x_pos);
}
/* Espace pour les liens remontants */
if (node->left_count > 0)
offset = EDGE_SLOT_HORIZ_MARGIN + EDGE_HORIZONTAL_MIN_SEP * (node->left_count - 1);
else
offset = 0;
/* Ajout du décallage le plus grand */
offset += -min;
/* Traitement des sous-noeuds */
for (i = 0; i < node->count; i++)
{
/* BUG_ON(node->children[i]->alloc.x != UNINITIALIZED_NODE_POS); */
g_graph_node_get_position(node->children[i], &x_pos, NULL);
printf(" == vapply == %p : %d + %d -> %d\n",
node->children[i], x_pos, offset, (int)(x_pos + offset));
x_pos += offset;
g_graph_node_set_x_position(node->children[i], x_pos);
}
g_virtual_node_compute_width(node);
}
/******************************************************************************
* *
* Paramètres : node = noeud d'encapsulation à traiter. *
* *
* Description : Définit les abscisses relatives du contenu d'un noeud. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_virtual_node_apply_x_line(GVirtualNode *node)
{
size_t i; /* Boucle de parcours #1 */
virtual_level *level; /* Accès rapide */
size_t j; /* Boucle de parcours #2 */
gint width_sum; /* Largeur d'un étage traité */
gint x_pos; /* Abscisse à attribuer */
for (i = 0; i < node->lcount; i++)
{
level = &node->levels[i];
/* Si l'ensemble de l'étage doit être centré */
if (level->children[0]->pending_flag == PPF_NONE)
{
width_sum = 0;
for (j = 0; j < level->count; j++)
{
assert(level->children[j]->pending_flag == PPF_NONE);
g_graph_node_apply_position(level->children[j]);
width_sum += level->children[j]->alloc.width;
}
width_sum += NODE_HORIZONTAL_MARGIN * (level->count - 1);
x_pos = - width_sum / 2;
for (j = 0; j < level->count; j++)
{
g_graph_node_set_x_position(level->children[j], x_pos);
x_pos += level->children[j]->alloc.width + NODE_HORIZONTAL_MARGIN;
}
}
/* On traite les noeuds individuellement */
else
{
void _apply_rel_position(GGraphNode *child)
{
switch (node->children[0]->pending_flag)
{
case PPF_LEFT_NODE:
if (!g_graph_node_has_x_position(child->pending_pos.left_node))
_apply_rel_position(child->pending_pos.left_node);
break;
case PPF_RIGHT_NODE:
if (!g_graph_node_has_x_position(child->pending_pos.right_node))
_apply_rel_position(child->pending_pos.right_node);
break;
default:
break;
}
g_graph_node_apply_position(child);
}
for (j = 0; j < level->count; j++)
if (!g_graph_node_has_x_position(level->children[j]))
_apply_rel_position(level->children[j]);
}
}
}
/******************************************************************************
* *
* Paramètres : node = noeud graphique à mettre à jour. *
* *
* Description : Met à jour la largeur interne du noeud. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_virtual_node_compute_width(GVirtualNode *node)
{
GGraphNode *base; /* Accès rapides */
size_t i; /* Boucle de parcours */
GGraphNode *child; /* Raccourci confortable */
base = G_GRAPH_NODE(node);
/* Largeur maximale des niveaux */
base->alloc.width = 0;
for (i = 0; i < node->lcount; i++)
{
child = node->levels[i].children[node->levels[i].count - 1];
base->alloc.width = MAX(base->alloc.width, child->alloc.x + child->alloc.width);
}
/* Bordures gauche et droite */
if (node->left_count > 0)
{
base->alloc.width += EDGE_SLOT_HORIZ_MARGIN;
base->alloc.width += (node->left_count - 1) * EDGE_HORIZONTAL_MIN_SEP;
}
if (node->right_count > 0)
{
base->alloc.width += EDGE_SLOT_HORIZ_MARGIN;
base->alloc.width += (node->right_count - 1) * EDGE_HORIZONTAL_MIN_SEP;
}
}
/******************************************************************************
* *
* Paramètres : node = noeud graphique à manipuler. *
* x = éventuelle abscisse à intégrer. *
* *
* Description : Altère la position du noeud d'encapsulation. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_virtual_node_set_position(GVirtualNode *node, gint x)
{
GGraphNode *base; /* Autre version de l'instance */
gint offset; /* Décallage à faire suivre */
size_t i; /* Boucle de parcours */
gint x_pos; /* Nouvelle position #1 */
base = G_GRAPH_NODE(node);
if (base->alloc.x == UNINITIALIZED_NODE_POS)
offset = x;
else
offset = x - base->alloc.x;
for (i = 0; i < node->count; i++)
{
/* BUG_ON(node->children[i]->alloc.x != UNINITIALIZED_NODE_POS); */
g_graph_node_get_position(node->children[i], &x_pos, NULL);
x_pos += offset;
g_graph_node_set_x_position(node->children[i], x_pos);
}
}
/******************************************************************************
* *
* 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_virtual_node_visit_flow_nodes(GVirtualNode *node, graph_node_visitor_cb callback, void *data)
{
bool result; /* Bilan à retourner */
size_t i; /* Boucle de parcours */
result = callback(G_GRAPH_NODE(node), GVS_ENTER, data);
for (i = 0; i < node->count && result; i++)
result = g_graph_node_visit_nodes(node->children[i], callback, data);
if (result)
result = callback(G_GRAPH_NODE(node), GVS_EXIT, data);
return result;
}
/******************************************************************************
* *
* Paramètres : nodes = noeud à consulter. *
* 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 : - *
* *
******************************************************************************/
static GGraphNode *g_virtual_node_find_container(GVirtualNode *node, GGraphNode *target)
{
GGraphNode *result; /* Trouvaille à retourner */
size_t i; /* Boucle de parcours */
result = NULL;
for (i = 0; i < node->count && result == NULL; i++)
{
if (node->children[i] == target)
result = G_GRAPH_NODE(node);
else
result = g_graph_node_find_container(node->children[i], target);
}
return result;
}
/******************************************************************************
* *
* Paramètres : node = noeud d'encapsulation à compléter. *
* child = sous-noeud à insérer. *
* *
* Description : Ajoute un noeud au groupe courant. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
void g_virtual_node_add_child(GVirtualNode *node, GGraphNode *child)
{
unsigned int rank; /* Rang de l'enfant */
virtual_level *level; /* Niveau d'intégration */
size_t i; /* Boucle de parcours */
/* Liste globale */
node->children = (GGraphNode **)realloc(node->children,
++node->count * sizeof(GGraphNode *));
node->children[node->count - 1] = child;
g_object_ref(G_OBJECT(child));
/* Intégration dans l'étage correspondant */
rank = g_graph_node_get_rank(child);
level = NULL;
for (i = 0; i < node->lcount && level == NULL; i++)
if (node->levels[i].rank == rank)
level = &node->levels[i];
if (level == NULL)
{
node->levels = (virtual_level *)realloc(node->levels,
++node->lcount * sizeof(virtual_level));
level = &node->levels[node->lcount - 1];
level->rank = rank;
level->children = NULL;
level->count = 0;
}
level->children = (GGraphNode **)realloc(level->children,
++level->count * sizeof(GGraphNode *));
level->children[level->count - 1] = child;
}
/******************************************************************************
* *
* Paramètres : node = noeud d'encapsulation à consulter. *
* *
* Description : Compte le nombre de noeuds contenus dans le groupe courant. *
* *
* Retour : Quantité normalement non nulle. *
* *
* Remarques : - *
* *
******************************************************************************/
size_t g_virtual_node_count_children(const GVirtualNode *node)
{
return node->count;
}
/******************************************************************************
* *
* Paramètres : node = noeud d'encapsulation à consulter. *
* index = indice du sous-bloc recherché. *
* *
* Description : Renvoie un des noeuds contenus dans le groupe courant. *
* *
* Retour : Un des blocs du groupe. *
* *
* Remarques : - *
* *
******************************************************************************/
GGraphNode *g_virtual_node_get_child(const GVirtualNode *node, size_t index)
{
if (index >= node->count)
return NULL;
else
return node->children[index];
}
/******************************************************************************
* *
* Paramètres : node = groupe de noeuds à mettre à jour. *
* r1 = début de la portée à réserver. *
* r2 = fin de la portée à réserver. *
* left = désignation de la zone à traiter. *
* *
* Description : Réserve une portion de largeur pour un lien. *
* *
* Retour : Indice de la largeur adaptée et réservée. *
* *
* Remarques : - *
* *
******************************************************************************/
vspan_slot_t g_virtual_node_reserve_span(GVirtualNode *node, unsigned int r1, unsigned int r2, bool left)
{
vspan_slot_t result; /* Identifiant à retourner */
reserved_vspan vspan; /* Portée à constituer */
vert_links **list; /* Liste à parcourir */
vspan_slot_t *count; /* Taille de cette liste */
vspan.r1 = r1;
vspan.r2 = r2;
if (left)
{
list = &node->left_padding;
count = &node->left_count;
}
else
{
list = &node->right_padding;
count = &node->right_count;
}
for (result = 0; result < *count; result++)
if (!is_intersection_with_vertical_spans(&(*list)[result], &vspan))
break;
if (result == *count)
{
*list = (vert_links *)realloc(*list, ++(*count) * sizeof(vert_links));
init_vertical_links(&(*list)[result]);
}
extend_vertical_links_spans(&(*list)[result], &vspan);
return result;
}
/******************************************************************************
* *
* Paramètres : node = conteneur de noeuds à consulter. *
* slot = numérod de la réservation. *
* left = désignation de la zone à traiter. *
* *
* Description : Fournit la position horizontale obtenue par réservation. *
* *
* Retour : Abscisse à utiliser. *
* *
* Remarques : - *
* *
******************************************************************************/
gint g_virtual_node_get_x_for_vspan_slot(const GVirtualNode *node, vspan_slot_t slot, bool left)
{
gint result; /* Position à retourner */
GtkAllocation alloc; /* Taille totale requise */
alloc = G_GRAPH_NODE(node)->alloc;
if (left)
{
/*BUG_ON(slot >= node->left_count) */
result = -(node->left_count - 1) * EDGE_HORIZONTAL_MIN_SEP/* + EDGE_SLOT_HORIZ_MARGIN*/;
result += (slot * EDGE_HORIZONTAL_MIN_SEP/* + EDGE_SLOT_HORIZ_MARGIN*/);
result += alloc.x;
}
else
{
/*BUG_ON(slot >= node->right_count) */
result = /*EDGE_SLOT_HORIZ_MARGIN + */slot * EDGE_HORIZONTAL_MIN_SEP;
result += alloc.x + alloc.width/* - EDGE_SLOT_HORIZ_MARGIN*/;
if (node->right_count > 0)
result -= (node->right_count - 1) * EDGE_HORIZONTAL_MIN_SEP;
/* On pense à la largeur du trait... */
result -= 2;
}
return result;
}