/* OpenIDA - Outil d'analyse de fichiers binaires * virtual.c - encapsulation graphique des blocs virtuels * * Copyright (C) 2013 Cyrille Bagard * * This file is part of OpenIDA. * * 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 "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 ---------------------- */ /* Encapsulation graphique d'un bloc virtuel (instance) */ struct _GVirtualNode { GGraphNode parent; /* A laisser en premier */ GVirtualBlock *block; /* Bloc virtuel associé */ gint x; /* Abscisse du noeud */ gint y; /* Ordonnée du noeud */ GGraphNode **children; /* Noeuds englobés */ size_t count; /* Quantité de ces noeuds */ 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 *); /* Altère la position du noeud d'encapsulation. */ static void g_virtual_node_set_position(GVirtualNode *, gint *, gint *); /* Fournit la position du noeud d'encapsulation. */ static void g_virtual_node_get_position(const GVirtualNode *, gint *, gint *); /* Indique l'espace requis pour un noeud d'encapsulation. */ static GtkAllocation g_virtual_node_get_allocation(const GVirtualNode *); /* 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 *); /* Définit les abscisses relatives du contenu d'un noeud. */ static void g_virtual_node_setup_x_line(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 */ object = G_OBJECT_CLASS(klass); object->dispose = (GObjectFinalizeFunc/* ! */)g_virtual_node_dispose; object->finalize = (GObjectFinalizeFunc)g_virtual_node_finalize; } /****************************************************************************** * * * Paramètres : node = instance à initialiser. * * * * Description : Initialise une encapsulation de bloc virtuel. * * * * Retour : - * * * * Remarques : - * * * ******************************************************************************/ static void g_virtual_node_init(GVirtualNode *node) { GGraphNode *base; /* Version basique */ base = G_GRAPH_NODE(node); base->get_rank = (get_node_rank_fc)g_virtual_node_get_rank; base->reset_pos = (node_reset_pos_fc)g_virtual_node_reset_position; base->set_pos = (node_set_pos_fc)g_virtual_node_set_position; base->get_pos = (node_get_pos_fc)g_virtual_node_get_position; base->get_alloc = (node_get_alloc_fc)g_virtual_node_get_allocation; base->visit = (visit_flow_nodes_fc)g_virtual_node_visit_flow_nodes; base->contain = (find_container_fc)g_virtual_node_find_container; node->x = UNINITIALIZED_NODE_POS; node->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_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. * * view = morceau d'affichage à représenter. * * * * 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) { node->x = UNINITIALIZED_NODE_POS; node->y = UNINITIALIZED_NODE_POS; } /****************************************************************************** * * * Paramètres : node = noeud graphique à manipuler. * * x = éventuelle abscisse à intégrer ou NULL. * * y = éventuelle ordonnée à intégrer ou NULL. * * * * Description : Altère la position du noeud d'encapsulation. * * * * Retour : - * * * * Remarques : - * * * ******************************************************************************/ static void g_virtual_node_set_position(GVirtualNode *node, gint *x, gint *y) { gint old_x; /* Sauvegarde des abscisses */ gint old_y; /* Sauvegarde des ordonnées */ gint off_x; /* Décallage sur les abscisses */ gint off_y; /* Décallage sur les ordonnées */ gint pos_x; /* Nouvelle position #1 */ gint pos_y; /* Nouvelle position #2 */ size_t i; /* Boucle de parcours */ //if (x != NULL) printf("-- setX -- %p -> %d (old=%d)\n", node, *x, node->x); old_x = node->x; old_y = node->y; if (x != NULL) node->x = *x; if (y != NULL) node->y = *y; off_x = (old_x != UNINITIALIZED_NODE_POS && node->x != UNINITIALIZED_NODE_POS ? node->x - old_x : 0); off_y = (old_y != UNINITIALIZED_NODE_POS ? node->y - old_y : node->y); //printf("offx = %d\n", off_x); for (i = 0; i < node->count; i++) { g_graph_node_get_position(node->children[i], &pos_x, &pos_y); if (x != NULL) pos_x += off_x; g_graph_node_set_position(node->children[i], &pos_x, &pos_y); } } /****************************************************************************** * * * 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 : - * * * ******************************************************************************/ static void g_virtual_node_get_position(const GVirtualNode *node, gint *x, gint *y) { if (x != NULL) *x = node->x; if (y != NULL) *y = node->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 : - * * * ******************************************************************************/ static GtkAllocation g_virtual_node_get_allocation(const GVirtualNode *node) { GtkAllocation result; /* Valeurs à retourner */ gint margins; /* Bordures gauche et droite */ unsigned int last_rank; /* Détection de saut de rangs */ size_t vert_count; /* Quantité à la verticale */ gint rank_width; /* Largeur d'un rang donné */ gint rank_height; /* Hauteur d'un rang donné */ size_t i; /* Boucle de parcours */ GtkAllocation alloc; /* Allocation d'un sous-noeud */ result.x = node->x; result.y = node->y; result.width = 0; margins = 0; if (node->left_count > 0) { margins += EDGE_SLOT_HORIZ_MARGIN; margins += (node->left_count - 1) * EDGE_HORIZONTAL_MIN_SEP; } if (node->right_count > 0) { margins += EDGE_SLOT_HORIZ_MARGIN; margins += (node->right_count - 1) * EDGE_HORIZONTAL_MIN_SEP; } result.height = 0; last_rank = -1; vert_count = 0; rank_width = 0; rank_height = 0; for (i = 0; i < node->count; i++) { alloc = g_graph_node_get_allocation(node->children[i]); /* Prise en compte de l'étage précédent */ if (last_rank != g_graph_node_get_rank(node->children[i])) { last_rank = g_graph_node_get_rank(node->children[i]); result.width = MAX(result.width, rank_width); result.height += rank_height; rank_width = 0; rank_height = 0; vert_count++; } /* Mise à jour de l'étage courant */ if (node->x == UNINITIALIZED_NODE_POS) { rank_width += alloc.width; if (rank_width > 0) rank_width += NODE_LEFT_MARGIN; } else rank_width = MAX(alloc.x + alloc.width - node->x, rank_width); rank_height = MAX(rank_height, alloc.height); } result.width = MAX(result.width, rank_width); result.width += margins; if (vert_count > 1) result.height += (vert_count - 1) * NODE_TOP_MARGIN; return result; } /****************************************************************************** * * * 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) { node->children = (GGraphNode **)realloc(node->children, ++node->count * sizeof(GGraphNode *)); node->children[node->count - 1] = child; g_object_ref(G_OBJECT(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 = noeud d'encapsulation à traiter. * * nodes = ensemble des noeuds en place. * * * * Description : Organise le contenu du noeud selon l'axe des abscisses. * * * * Retour : - * * * * Remarques : - * * * ******************************************************************************/ void g_virtual_node_organize_x_line(GVirtualNode *node, GGraphNode *nodes) { size_t i; /* Boucle de parcours */ gint min; /* Valeur minimale rencontrée */ gint x; /* Position d'un sous-noeud */ g_virtual_node_setup_x_line(node, nodes); min = 0; for (i = 0; i < node->count; i++) { g_graph_node_get_position(node->children[i], &x, NULL); min = MIN(min, x); } node->x += GRAPH_HORIZONTAL_MARGIN; min = -min + GRAPH_HORIZONTAL_MARGIN; g_virtual_node_offset_x_line(node, min); } /****************************************************************************** * * * 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_setup_x_line(GVirtualNode *node, GGraphNode *nodes) { unsigned int rank_0; /* Rang du premier sous-noeud */ unsigned int rank_1; /* Rang du second sous-noeud */ size_t i; /* Boucle de parcours */ GGraphNode *child; /* Raccourci confortable */ gint last_pos; /* Dernière position */ GtkAllocation alloc; /* Espace pour l'affichage */ /* Si le rang d'entrée contient tous les éléments... */ if (node->count > 1) { rank_0 = g_graph_node_get_rank(node->children[0]); rank_1 = g_graph_node_get_rank(node->children[1]); if (rank_0 == rank_1) { g_graph_node_set_position(node->children[0], (gint []) { 0/*-(alloc.width / 2)*/ }, NULL); for (i = 1; i < node->count; i++) { /* Récupération de la position précédente */ child = node->children[i - 1]; g_graph_node_get_position(child, &last_pos, NULL); alloc = g_graph_node_get_allocation(child); last_pos += alloc.width + NODE_LEFT_MARGIN; /* Application sur le noeud courant */ child = node->children[i]; alloc = g_graph_node_get_allocation(child); g_graph_node_set_position(child, &last_pos, NULL); } } } for (i = 0; i < node->count; i++) { child = node->children[i]; /* Emplacement du fils */ if (!g_graph_node_has_x_position(child)) { alloc = g_graph_node_get_allocation(child); g_graph_node_set_position(child, (gint []) { -(alloc.width / 2) }, NULL); } /* Définitions éventuelles des emplacements liés */ if (G_IS_FLOW_NODE(child)) g_flow_node_organize_x_line(G_FLOW_NODE(child), nodes); else if (G_IS_VIRTUAL_NODE(child)) g_virtual_node_organize_x_line(G_VIRTUAL_NODE(child), nodes); /*else BUG_ON(1); */ } } /****************************************************************************** * * * Paramètres : node = noeud d'encapsulation à traiter. * * xoffset = valeur du décallage. * * * * Description : Procède à un décallage du contenu sur l'axe des abscisses. * * * * Retour : - * * * * Remarques : - * * * ******************************************************************************/ void g_virtual_node_offset_x_line(GVirtualNode *node, gint xoffset) { gint padding; /* Décallage supplémentaire */ size_t i; /* Boucle de parcours */ gint x; /* Position d'un sous-noeud */ GGraphNode *child; /* Raccourci confortable */ /* Espace pour les liens remontants */ if (node->left_count > 0) padding = EDGE_SLOT_HORIZ_MARGIN + EDGE_HORIZONTAL_MIN_SEP * (node->left_count - 1); else padding = 0; /* Traitement de sous-noeuds */ for (i = 0; i < node->count; i++) { child = node->children[i]; g_graph_node_get_position(child, &x, NULL); printf("+++ [%p-%d/%p] offsetting %d(%d) + (%d / %d)\n", node, g_graph_node_get_rank(G_GRAPH_NODE(node)), child, node->x, G_GRAPH_NODE(node)->pending_x, x, x + xoffset + padding); x += node->x + xoffset + padding; g_graph_node_set_position(child, &x, NULL); } } /****************************************************************************** * * * 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_virtual_node_get_allocation(node); 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; }