/* Chrysalide - Outil d'analyse de fichiers binaires
* cluster.c - mise en place de graphiques
*
* Copyright (C) 2016-2017 Cyrille Bagard
*
* This file is part of Chrysalide.
*
* Chrysalide 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.
*
* Chrysalide 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 Chrysalide. If not, see <http://www.gnu.org/licenses/>.
*/
#include "cluster.h"
#include <assert.h>
#include <malloc.h>
#include <stdlib.h>
#include <string.h>
#include "../gtkblockdisplay.h"
#include "../gtkbufferdisplay.h"
#include "../gtkdisplaypanel.h"
#include "../../common/sort.h"
#include "../../glibext/gbinarycursor.h" // REMME
#include "../../glibext/gloadedpanel.h"
/* Définition du tracé d'un lien */
typedef struct _incoming_edge
{
InstructionLinkType type; /* Complexité du tracé */
const size_t *hslot; /* Couche horizontale réservée */
GdkPoint y; /* Position des décrochages */
GdkPoint end; /* Point d'arrivée final */
GGraphEdge *edge; /* Lien complet en préparation */
GGraphCluster *origin; /* Bloc de départ du lien */
const size_t *leaving_index; /* Indice du point de départ */
} incoming_edge;
/* Détails sur le départ d'un lien */
typedef struct _leaving_edge
{
GdkPoint start; /* Point de départ d'un lien */
size_t index; /* Indice sur ligne de départ */
} leaving_edge;
/* Réservation pour les lignes horizontales */
typedef struct _hspace_booking
{
gint start; /* Abscisse de départ de ligne */
size_t index; /* Indice de rangée verticale */
} hspace_booking;
/* Découpage vertical */
typedef struct _graph_rank
{
unsigned int level; /* Niveau des blocs */
hspace_booking **right2left; /* Réservations de D -> G */
size_t r2l_count; /* Quantité de ces réservations*/
hspace_booking **left2right; /* Réservations de G -> D */
size_t l2r_count; /* Quantité de ces réservations*/
GGraphCluster **clusters; /* Ensembles de blocs */
size_t count; /* Nombre de ces ensembles */
} graph_rank;
/* Mise en disposition de blocs en graphique (instance) */
struct _GGraphCluster
{
GObject parent; /* A laisser en premier */
size_t *parent_index; /* Indice du lien au départ */
////////////////////////////////////////
gint top_margin[2]; /* Espaces gauches et droites */
gint left_margin; /* Espaces remontant à gauche */
gint right_margin; /* Espaces remontant à droite */
////////////////////////////////////////
incoming_edge **top_anchors; /* Accroches supérieures */
size_t ta_count; /* Quantité de ces accroches */
GBasicBlock *block; /* Bloc d'origine représenté */
GtkWidget *display; /* Vue graphique associée */
GtkAllocation alloc; /* Emplacement final du bloc */
leaving_edge **bottom_anchors; /* Accroches inférieures */
size_t ba_count; /* Quantité de ces accroches */
bool has_straight; /* Présence d'une ligne droite */
unsigned int straight_level; /* Rang atteint en ligne droite*/
size_t straight_index; /* Indice du lien vertical */
graph_rank *ranks; /* Répartition verticale */
size_t ranks_count; /* Nombre de divisions */
};
/* Mise en disposition de blocs en graphique (classe) */
struct _GGraphClusterClass
{
GObjectClass parent; /* A laisser en premier */
};
/* Espace minimal horizontal entre les blocs */
#define HORIZONTAL_MARGIN 20
/* Espace minimal vertical entre les blocs */
#define VERTICAL_MARGIN 15
/* Espace minimal entre les liens */
#define LINK_MARGIN 10
/* Initialise la classe des mises en disposition graphique. */
static void g_graph_cluster_class_init(GGraphClusterClass *);
/* Initialise une mise en disposition de blocs en graphique. */
static void g_graph_cluster_init(GGraphCluster *);
/* Supprime toutes les références externes. */
static void g_graph_cluster_dispose(GGraphCluster *);
/* Procède à la libération totale de la mémoire. */
static void g_graph_cluster_finalize(GGraphCluster *);
/* Complète un graphique avec un sous-ensemble de blocs. */
static void g_graph_cluster_add_sub(GGraphCluster *, GGraphCluster *, GBasicBlock *);
/* Organisation la disposition d'un ensemble de blocs basiques. */
static void g_graph_cluster_dispatch_x(GGraphCluster *);
/* Détermine une position pour un ensemble de blocs basiques. */
//static void g_graph_cluster_set_x(GGraphCluster *, gint);
/* Décalle vers la droite un ensemble de blocs basiques. */
static void g_graph_cluster_offset_x(GGraphCluster *, gint);
/* Décalle vers le bas un ensemble de blocs basiques. */
static void g_graph_cluster_set_y(GGraphCluster *, gint);
/* Recherche le bloc basique à l'extrémité d'un lien. */
//static GGraphCluster *g_graph_cluster_find_lower_dest_cluster(const GGraphCluster *, const GArchInstruction *);
/* Met en place les embryons de liens nécessaires. */
static void g_graph_cluster_define_links(GGraphCluster *, GHashTable *);
/* Calcule l'abscisse d'un lien à son départ d'un bloc. */
static gint g_graph_cluster_compute_leaving_link_position(const GGraphCluster *, size_t);
/* Détermine les abscisses de tous les liens en place. */
static void g_graph_cluster_compute_link_x_positions(GGraphCluster *);
/* Réserve de l'espace vertical pour les lignes horizontales. */
static void g_graph_cluster_book_hspace_for_links(GGraphCluster *);
/* Détermine les ordonnées de tous les liens en place. */
static void g_graph_cluster_compute_link_y_positions(GGraphCluster *);
/* Applique les positions calculées pour chaque lien graphique. */
static void g_graph_cluster_resolve_links(const GGraphCluster *);
/* Indique le type définit par la GLib pour les mises en disposition graphique. */
G_DEFINE_TYPE(GGraphCluster, g_graph_cluster, G_TYPE_OBJECT);
/******************************************************************************
* *
* Paramètres : klass = classe à initialiser. *
* *
* Description : Initialise la classe des mises en disposition graphique. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_graph_cluster_class_init(GGraphClusterClass *klass)
{
GObjectClass *object; /* Autre version de la classe */
object = G_OBJECT_CLASS(klass);
object->dispose = (GObjectFinalizeFunc/* ! */)g_graph_cluster_dispose;
object->finalize = (GObjectFinalizeFunc)g_graph_cluster_finalize;
}
/******************************************************************************
* *
* Paramètres : cluster = instance à initialiser. *
* *
* Description : Initialise une mise en disposition de blocs en graphique. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_graph_cluster_init(GGraphCluster *cluster)
{
}
/******************************************************************************
* *
* Paramètres : cluster = instance d'objet GLib à traiter. *
* *
* Description : Supprime toutes les références externes. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_graph_cluster_dispose(GGraphCluster *cluster)
{
g_object_unref(G_OBJECT(cluster->block));
g_object_unref(G_OBJECT(cluster->display));
G_OBJECT_CLASS(g_graph_cluster_parent_class)->dispose(G_OBJECT(cluster));
}
/******************************************************************************
* *
* Paramètres : cluster = instance d'objet GLib à traiter. *
* *
* Description : Procède à la libération totale de la mémoire. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_graph_cluster_finalize(GGraphCluster *cluster)
{
G_OBJECT_CLASS(g_graph_cluster_parent_class)->finalize(G_OBJECT(cluster));
}
/******************************************************************************
* *
* Paramètres : binary = binaire charger dont le code est à représenter.*
* list = ensemble de blocs basiques à manipuler. *
* index = indice du bloc principal à mettre en place. *
* highlighted = gestionnaire de surbrillance pour segments. *
* *
* Description : Construit un graphique à partir de blocs basiques. *
* *
* Retour : Adresse de la structure mise en place. *
* *
* Remarques : - *
* *
******************************************************************************/
GGraphCluster *g_graph_cluster_new(GLoadedBinary *binary, const GBlockList *list, size_t index, segcnt_list *highlighted)
{
GGraphCluster *result; /* Structure à retourner */
vmpa2t first; /* Début d'un groupe de lignes */
vmpa2t last; /* Fin d'un groupe de lignes */
GLineCursor *___tmp_first;
GLineCursor *___tmp_last;
GBufferCache *cache; /* Tampon brut à découper */
GBufferView *view; /* Partie affichée du tampon */
GtkRequisition requisition; /* Taille à l'écran actuelle */
result = g_object_new(G_TYPE_GRAPH_CLUSTER, NULL);
/* Encapsulation du bloc d'entrée */
result->block = g_block_list_get_block(list, index);
g_object_ref(G_OBJECT(result->block));
result->display = gtk_block_display_new();
gtk_widget_show(result->display);
g_loaded_panel_set_content(G_LOADED_PANEL(result->display), G_LOADED_CONTENT(binary));
gtk_block_display_override_view_index(GTK_BLOCK_DISPLAY(result->display), BVW_GRAPH);
gtk_display_panel_show_border(GTK_DISPLAY_PANEL(result->display), true);
/* Restriction au bloc basique */
g_basic_block_get_boundary_addresses(result->block, &first, &last);
///////////////////////
___tmp_first = g_binary_cursor_new();
g_binary_cursor_update(G_BINARY_CURSOR(___tmp_first), &first);
___tmp_last = g_binary_cursor_new();
g_binary_cursor_update(G_BINARY_CURSOR(___tmp_last), &last);
///////////////////////
cache = g_loaded_binary_get_disassembled_cache(binary);
view = g_buffer_view_new(cache, highlighted);
g_buffer_view_restrict(view, ___tmp_first, ___tmp_last);
gtk_buffer_display_set_view(GTK_BUFFER_DISPLAY(result->display), view);
/* Détermination d'une position initiale centrée */
gtk_widget_get_preferred_size(result->display, NULL, &requisition);
result->alloc.x = -requisition.width / 2;
result->alloc.y = 0;
result->alloc.width = requisition.width;
result->alloc.height = requisition.height;
printf("BLOCK INIT :: %d <> %d\n", result->alloc.x, result->alloc.width);
return result;
}
/******************************************************************************
* *
* Paramètres : cluster = graphique de blocs à compléter. *
* sub = sous-ensemble à intégrer. *
* block = bloc basique de départ du sous-ensemble. *
* *
* Description : Complète un graphique avec un sous-ensemble de blocs. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_graph_cluster_add_sub(GGraphCluster *cluster, GGraphCluster *sub, GBasicBlock *block)
{
unsigned int level; /* Niveau du nouvel ensemble */
size_t i; /* Boucle de parcours */
graph_rank new; /* Nouvel étage à insérer */
graph_rank *rank; /* Nouvel étage à compléter */
level = g_basic_block_get_rank(block);
for (i = 0; i < cluster->ranks_count; i++)
if (cluster->ranks[i].level == level)
break;
if (i == cluster->ranks_count)
{
new.level = level;
new.right2left = NULL;
new.r2l_count = 0;
new.left2right = NULL;
new.l2r_count = 0;
new.clusters = (GGraphCluster **)calloc(1, sizeof(GGraphCluster *));
new.count = 1;
new.clusters[0] = sub;
int cmp_graph_rank(const graph_rank *a, const graph_rank *b)
{
if (a->level < b->level)
return -1;
else if (a->level > b->level)
return 1;
else
return 0;
}
cluster->ranks = qinsert(cluster->ranks, &cluster->ranks_count,
sizeof(graph_rank), (__compar_fn_t)cmp_graph_rank, &new);
}
else
{
rank = &cluster->ranks[i];
rank->count++;
rank->clusters = (GGraphCluster **)realloc(rank->clusters,
sizeof(GGraphCluster *) * rank->count);
rank->clusters[rank->count - 1] = sub;
}
}
/******************************************************************************
* *
* Paramètres : cluster = graphique de blocs à manipuler. *
* *
* Description : Organisation la disposition d'un ensemble de blocs basiques. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_graph_cluster_dispatch_x(GGraphCluster *cluster)
{
size_t k; /* Boucle de parcours #1 */
const graph_rank *rank; /* Accès confortable au rang */
size_t j; /* Boucle de parcours #2 */
gint start; /* Position initiale de départ */
size_t rcount; /* Nombre d'ensembles présents */
size_t mid; /* Position centrale de départ */
/**
* A ce point, tous les blocs parents sont placés.
* On est donc en mesure de réorganiser les points d'arrivée
* des liens afin d'éviter les croisements : un lien qui vient
* de la gauche ne doit pas arriver tout à droite !
*/
int compare_incoming_edges(const incoming_edge **a, const incoming_edge **b)
{
int result; /* Bilan à retourner */
gint pos_a; /* Point de départ pour A */
gint pos_b; /* Point de départ pour B */
pos_a = g_graph_cluster_compute_leaving_link_position((*a)->origin, *(*a)->leaving_index);
pos_b = g_graph_cluster_compute_leaving_link_position((*b)->origin, *(*b)->leaving_index);
if (pos_a < pos_b)
result = -1;
else if (pos_a > pos_b)
result = 1;
else
result = 0;
return result;
}
qsort(cluster->top_anchors, cluster->ta_count, sizeof(incoming_edge *), (__compar_fn_t)compare_incoming_edges);
/**
* Il est désormais temps de placer tous les blocs de code inférieurs.
*/
void place_sub(GGraphCluster **iter, size_t loop, gint base, int dir)
{
size_t i; /* Boucle de parcours #2 */
GtkAllocation needed; /* Taille requise */
assert(dir == -1 || dir == 1);
for (i = 0; i < loop; i++, iter += dir)
{
g_graph_cluster_dispatch_x(*iter);
g_graph_cluster_compute_needed_alloc(*iter, &needed);
if (dir > 0)
g_graph_cluster_offset_x(*iter, base - needed.x);
else
g_graph_cluster_offset_x(*iter, base - needed.x - needed.width);
base += dir * (needed.width + HORIZONTAL_MARGIN);
}
}
for (k = 0; k < cluster->ranks_count; k++)
{
rank = &cluster->ranks[k];
/* Répartition autour d'une ligne verticale */
if (cluster->has_straight)
{
start = g_graph_cluster_compute_leaving_link_position(cluster, cluster->straight_index);
if (rank->level < cluster->straight_level)
{
/* Répartition à gauche du lien */
for (j = rank->count; j > 0; j--)
if (*rank->clusters[j - 1]->parent_index < cluster->straight_index)
break;
start -= HORIZONTAL_MARGIN / 2;
place_sub(rank->clusters, j, start, -1);
/* Répartition à droite du lien */
for (j = 0; j < rank->count; j++)
if (*rank->clusters[j]->parent_index > cluster->straight_index)
break;
start += HORIZONTAL_MARGIN;
place_sub(rank->clusters + j, rank->count - j, start, 1);
}
}
/* Répartition homogène */
else
{
rcount = rank->count;
if (rcount % 2 == 1)
{
if (rcount > 1)
{
mid = rcount / 2;
start = rank->clusters[mid]->alloc.x - HORIZONTAL_MARGIN;
place_sub(rank->clusters + mid - 1, mid, start, -1);
start *= -1;
place_sub(rank->clusters + mid + 1, mid, start, 1);
}
else
g_graph_cluster_dispatch_x(rank->clusters[0]);
}
else
{
mid = rcount / 2 - 1;
start = - HORIZONTAL_MARGIN / 2;
place_sub(rank->clusters + mid, mid + 1, start, -1);
start *= -1;
place_sub(rank->clusters + mid + 1, mid + 1, start, 1);
}
}
}
}
/******************************************************************************
* *
* Paramètres : cluster = graphique de blocs à actualiser. *
* x = position finale sur l'axe des abscisses. *
* *
* Description : Détermine une position pour un ensemble de blocs basiques. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
/*
static void g_graph_cluster_set_x(GGraphCluster *cluster, gint x)
{
g_graph_cluster_offset_x(cluster, -cluster->alloc.x);
g_graph_cluster_offset_x(cluster, x);
}
*/
/******************************************************************************
* *
* Paramètres : cluster = graphique de blocs à actualiser. *
* offset = décalage à appliquer. *
* *
* Description : Décalle vers la droite un ensemble de blocs basiques. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_graph_cluster_offset_x(GGraphCluster *cluster, gint offset)
{
size_t i; /* Boucle de parcours #1 */
size_t j; /* Boucle de parcours #2 */
cluster->alloc.x += offset;
for (i = 0; i < cluster->ranks_count; i++)
for (j = 0; j < cluster->ranks[i].count; j++)
g_graph_cluster_offset_x(cluster->ranks[i].clusters[j], offset);
}
/******************************************************************************
* *
* Paramètres : cluster = graphique de blocs à actualiser. *
* base = position ordonnée à appliquer. *
* *
* Description : Décalle vers le bas un ensemble de blocs basiques. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_graph_cluster_set_y(GGraphCluster *cluster, gint base)
{
size_t i; /* Boucle de parcours #1 */
const graph_rank *rank; /* Accès simplifié à la rangée */
gint max; /* Hauteur maximale rencontrée */
size_t j; /* Boucle de parcours #2 */
GGraphCluster *sub; /* Sous-ensemble traité */
GtkAllocation alloc; /* Allocation courante */
cluster->alloc.y = base;
base += cluster->alloc.height;
for (i = 0; i < cluster->ranks_count; i++)
{
rank = &cluster->ranks[i];
/* On ajoute l'espace vertical pour les lignes horizontales */
if (rank->r2l_count > rank->l2r_count)
max = rank->r2l_count;
else
max = rank->l2r_count;
base += VERTICAL_MARGIN;
/**
* Comme les liens purement verticaux n'entrainent pas de réservation,
* il n'y a potentiellement pas toujours d'espace à ajouter.
*/
if (max > 0)
base += ((max - 1) * LINK_MARGIN);
/* On ajoute l'espace requis pour l'affichage des blocs */
base += VERTICAL_MARGIN;
max = 0;
for (j = 0; j < rank->count; j++)
{
sub = rank->clusters[j];
g_graph_cluster_set_y(sub, base);
g_graph_cluster_compute_needed_alloc(sub, &alloc);
if ((alloc.y + alloc.height) > max)
max = alloc.y + alloc.height;
}
base = max;
}
}
/******************************************************************************
* *
* Paramètres : cluster = encapsulation à consulter. *
* alloc = emplacement idéal pour l'affichage. *
* *
* Description : Détermine l'emplacement requis d'un ensemble de blocs. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
void g_graph_cluster_compute_needed_alloc(const GGraphCluster *cluster, GtkAllocation *alloc)
{
GtkAllocation needed; /* Taille requise */
size_t i; /* Boucle de parcours */
size_t rcount; /* Nombre d'ensembles présents */
*alloc = cluster->alloc;
for (i = 0; i < cluster->ranks_count; i++)
{
rcount = cluster->ranks[i].count;
switch (rcount)
{
case 1:
g_graph_cluster_compute_needed_alloc(cluster->ranks[i].clusters[0], &needed);
if (needed.x < alloc->x)
{
alloc->width += (alloc->x - needed.x);
alloc->x = needed.x;
}
if ((needed.x + needed.width) > (alloc->x + alloc->width))
alloc->width += needed.x + needed.width - alloc->x - alloc->width;
/* La hauteur maximale n'est présente qu'avec le dernier morceau */
if ((i + 1) == cluster->ranks_count)
{
if ((needed.y + needed.height) > (alloc->y + alloc->height))
alloc->height += needed.y + needed.height - alloc->y - alloc->height;
}
break;
default:
assert(rcount >= 2);
g_graph_cluster_compute_needed_alloc(cluster->ranks[i].clusters[0], &needed);
if (needed.x < alloc->x)
{
alloc->width += (alloc->x - needed.x);
alloc->x = needed.x;
}
/* La hauteur maximale n'est présente qu'avec le dernier morceau */
if ((i + 1) == cluster->ranks_count)
{
if ((needed.y + needed.height) > (alloc->y + alloc->height))
alloc->height += needed.y + needed.height - alloc->y - alloc->height;
}
g_graph_cluster_compute_needed_alloc(cluster->ranks[i].clusters[rcount - 1], &needed);
if ((needed.x + needed.width) > (alloc->x + alloc->width))
alloc->width += needed.x + needed.width - alloc->x - alloc->width;
/* La hauteur maximale n'est présente qu'avec le dernier morceau */
if ((i + 1) == cluster->ranks_count)
{
if ((needed.y + needed.height) > (alloc->y + alloc->height))
alloc->height += needed.y + needed.height - alloc->y - alloc->height;
}
break;
}
}
}
/******************************************************************************
* *
* Paramètres : cluster = encapsulation à traiter. *
* display = support de destination finale. *
* *
* Description : Dispose chaque noeud sur la surface de destination donnée. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
void g_graph_cluster_place(GGraphCluster *cluster, GtkGraphDisplay *display)
{
size_t i; /* Boucle de parcours #1 */
size_t j; /* Boucle de parcours #2 */
g_object_ref(G_OBJECT(cluster->display));
gtk_graph_display_put(display, cluster->display, &cluster->alloc);
for (i = 0; i < cluster->ta_count; i++)
{
g_object_ref(G_OBJECT(cluster->top_anchors[i]->edge));
gtk_graph_display_add_edge(display, cluster->top_anchors[i]->edge);
}
for (i = 0; i < cluster->ranks_count; i++)
for (j = 0; j < cluster->ranks[i].count; j++)
g_graph_cluster_place(cluster->ranks[i].clusters[j], display);
}
//////////////////////////////////////////////////////////
/******************************************************************************
* *
* Paramètres : cluster = graphique de blocs à consulter ou remonter. *
* first = première instruction du bloc basique recherché. *
* *
* Description : Recherche le bloc basique à l'extrémité d'un lien. *
* *
* Retour : Bloc graphique de destination pour un lien ou NULL si échec. *
* *
* Remarques : - *
* *
******************************************************************************/
#if 0
static GGraphCluster *g_graph_cluster_find_lower_dest_cluster(const GGraphCluster *cluster, const GArchInstruction *first)
{
GGraphCluster *result; /* Trouvaille à retourner */
size_t i; /* Boucle de parcours #1 */
const graph_rank *rank; /* Confort d'accès */
size_t j; /* Boucle de parcours #2 */
GArchInstruction *instr; /* Instruction à comparer */
result = NULL;
for (i = 0; i < cluster->ranks_count && result == NULL; i++)
{
rank = &cluster->ranks[i];
for (j = 0; j < rank->count && result == NULL; j++)
{
g_basic_block_get_boundary(rank->clusters[j]->block, &instr, NULL);
if (instr == first)
result = rank->clusters[j];
}
}
return result;
}
#endif
/******************************************************************************
* *
* Paramètres : cluster = graphique de blocs à actualiser. *
* all = table regroupant tous les groupes créés. *
* *
* Description : Met en place les embryons de liens nécessaires. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_graph_cluster_define_links(GGraphCluster *cluster, GHashTable *all)
{
unsigned int level; /* Niveau du nouvel ensemble */
GArchInstruction *last; /* Dernière instruction du bloc*/
size_t dcount; /* Nombre de liens de dest. */
size_t i; /* Boucle de parcours #1 */
instr_link_t *dest; /* Instr. visée par une autre */
GGraphCluster *target; /* Bloc ciblé par un lien */
leaving_edge *leaving; /* Point de départ d'un lien */
unsigned int target_level; /* Rang du bloc ciblé */
size_t j; /* Boucle de parcours #2 */
size_t k; /* Boucle de parcours #3 */
incoming_edge *incoming; /* Définitions d'arrivée */
/* Au niveau du bloc courant */
level = g_basic_block_get_rank(cluster->block);
g_basic_block_get_boundary(cluster->block, NULL, &last);
g_arch_instruction_lock_dest(last);
dcount = g_arch_instruction_count_destinations(last);
for (i = 0; i < dcount; i++)
{
dest = g_arch_instruction_get_destination(last, i);
switch (dest->type)
{
case ILT_EXEC_FLOW:
case ILT_JUMP:
case ILT_CASE_JUMP:
case ILT_JUMP_IF_TRUE:
case ILT_JUMP_IF_FALSE:
target = G_GRAPH_CLUSTER(g_hash_table_lookup(all, dest->linked));
assert(target != NULL);
/* Point de départ */
leaving = (leaving_edge *)calloc(1, sizeof(leaving_edge));
cluster->bottom_anchors = (leaving_edge **)realloc(cluster->bottom_anchors,
++cluster->ba_count * sizeof(leaving_edge *));
cluster->bottom_anchors[cluster->ba_count - 1] = leaving;
/* Est-ce un lien qui doit être vertical ? */
/* FIXME : trop de boucles ! */
target_level = -1;
for (j = 0; j < cluster->ranks_count && target_level == -1; j++)
for (k = 0; k < cluster->ranks[j].count && target_level == -1; k++)
if (cluster->ranks[j].clusters[k] == target)
{
target_level = cluster->ranks[j].level;
if (target_level > (level + 1) && target_level > cluster->straight_level)
{
cluster->has_straight = true;
cluster->straight_level = target_level;
cluster->straight_index = cluster->ba_count - 1;
}
}
/* Point d'arrivée */
incoming = (incoming_edge *)calloc(1, sizeof(incoming_edge));
target->top_anchors = (incoming_edge **)realloc(target->top_anchors,
++target->ta_count * sizeof(incoming_edge *));
target->top_anchors[target->ta_count - 1] = incoming;
/* Etablissement d'un embryon de lien */
leaving->index = cluster->ba_count - 1;
incoming->type = dest->type;
if (incoming->type == ILT_JUMP_IF_TRUE)
incoming->edge = g_graph_edge_new_true(&leaving->start, &incoming->y, &incoming->end);
else if (incoming->type == ILT_JUMP_IF_FALSE)
incoming->edge = g_graph_edge_new_false(&leaving->start, &incoming->y, &incoming->end);
else
incoming->edge = g_graph_edge_new(&leaving->start, &incoming->y, &incoming->end);
incoming->origin = cluster;
incoming->leaving_index = &leaving->index;
/* FIXME : trop de boucles ! */
target_level = -1;
for (j = 0; j < cluster->ranks_count && target_level == -1; j++)
for (k = 0; k < cluster->ranks[j].count && target_level == -1; k++)
if (cluster->ranks[j].clusters[k] == target)
{
target_level = 0;
target->parent_index = &leaving->index;
}
break;
case ILT_LOOP:
/* TODO */
//assert(false);
break;
default:
break;
}
}
g_arch_instruction_unlock_dest(last);
/* Déplacement d'un éventuel lien central */
if (cluster->has_straight)
{
size_t center;
leaving_edge *tmp;
if (cluster->ba_count % 2 == 0)
center = cluster->ba_count / 2 - 1;
else
center = cluster->ba_count / 2;
if (cluster->straight_index < center)
{
tmp = cluster->bottom_anchors[cluster->straight_index];
memmove(cluster->bottom_anchors + cluster->straight_index,
cluster->bottom_anchors + cluster->straight_index + 1,
(center - cluster->straight_index) * sizeof(leaving_edge *));
cluster->bottom_anchors[center] = tmp;
for (i = cluster->straight_index; i <= center; i++)
cluster->bottom_anchors[i]->index = i;
cluster->straight_index = center;
}
else if (cluster->straight_index > center)
{
tmp = cluster->bottom_anchors[cluster->straight_index];
memmove(cluster->bottom_anchors + center + 1,
cluster->bottom_anchors + center,
(cluster->straight_index - center) * sizeof(leaving_edge *));
cluster->bottom_anchors[center] = tmp;
for (i = center; i <= cluster->straight_index ; i++)
cluster->bottom_anchors[i]->index = i;
cluster->straight_index = center;
}
}
/* Propagation de la mise en place */
for (i = 0; i < cluster->ranks_count; i++)
for (j = 0; j < cluster->ranks[i].count; j++)
g_graph_cluster_define_links(cluster->ranks[i].clusters[j], all);
}
/******************************************************************************
* *
* Paramètres : cluster = graphique de blocs à consulter. *
* index = indice du lien à considérer. *
* *
* Description : Calcule l'abscisse d'un lien à son départ d'un bloc. *
* *
* Retour : Abscisse à attribuer à un départ de lien. *
* *
* Remarques : - *
* *
******************************************************************************/
static gint g_graph_cluster_compute_leaving_link_position(const GGraphCluster *cluster, size_t index)
{
gint result; /* Position à retourner */
gint mid_x; /* Abscisse centrale */
size_t half; /* Indice de répartition égale */
assert(index < cluster->ba_count);
mid_x = cluster->alloc.x + (cluster->alloc.width / 2);
half = cluster->ba_count / 2;
if (cluster->ba_count % 2 == 1)
{
if (index < half)
result = mid_x - (half - index) * LINK_MARGIN;
else if (index == half)
result = mid_x;
else
result = mid_x + (index - half) * LINK_MARGIN;
}
else
{
if (index < half)
result = mid_x - LINK_MARGIN / 2 - (half - index - 1) * LINK_MARGIN;
else
result = mid_x + LINK_MARGIN / 2 + (index - half) * LINK_MARGIN;
}
return result;
}
/******************************************************************************
* *
* Paramètres : cluster = graphique de blocs à actualiser. *
* *
* Description : Détermine les abscisses de tous les liens en place. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_graph_cluster_compute_link_x_positions(GGraphCluster *cluster)
{
gint mid_x; /* Abscisse centrale */
size_t i; /* Boucle de parcours #1 */
size_t half; /* Indice de répartition égale */
GdkPoint *pt; /* Point à actualiser */
size_t j; /* Boucle de parcours #2 */
mid_x = cluster->alloc.x + (cluster->alloc.width / 2);
/* Du côté des départs... */
if (cluster->ba_count > 0)
for (i = 0; i < cluster->ba_count; i++)
{
pt = &cluster->bottom_anchors[i]->start;
pt->x = g_graph_cluster_compute_leaving_link_position(cluster, i);
}
/* Du côté des arrivées... */
if (cluster->ta_count > 0)
{
half = cluster->ta_count / 2;
if (cluster->ta_count % 2 == 1)
{
for (i = half; i > 0; i--)
{
pt = &cluster->top_anchors[i - 1]->end;
pt->x = mid_x - (half - i + 1) * LINK_MARGIN;
}
cluster->top_anchors[half]->end.x = mid_x;
for (i = half + 1; i < cluster->ta_count; i++)
{
pt = &cluster->top_anchors[i]->end;
pt->x = mid_x + (i - half) * LINK_MARGIN;
}
}
else
{
for (i = half; i > 0; i--)
{
pt = &cluster->top_anchors[i - 1]->end;
pt->x = mid_x - LINK_MARGIN / 2 - (half - i) * LINK_MARGIN;
}
for (i = half; i < cluster->ta_count; i++)
{
pt = &cluster->top_anchors[i]->end;
pt->x = mid_x + LINK_MARGIN / 2 + (half - i) * LINK_MARGIN;
}
}
}
/* Propagation des déterminations */
for (i = 0; i < cluster->ranks_count; i++)
for (j = 0; j < cluster->ranks[i].count; j++)
g_graph_cluster_compute_link_x_positions(cluster->ranks[i].clusters[j]);
}
/******************************************************************************
* *
* Paramètres : cluster = graphique de blocs à traiter. *
* *
* Description : Réserve de l'espace vertical pour les lignes horizontales. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_graph_cluster_book_hspace_for_links(GGraphCluster *cluster)
{
size_t i; /* Boucle de parcours #1 */
graph_rank *rank; /* Rangée à manipuler */
size_t j; /* Boucle de parcours #2 */
GGraphCluster *sub; /* Bloc inférieur à manipuler */
size_t k; /* Boucle de parcours #3 */
gint x1; /* Abscisse de départ de lien */
gint x2; /* Abscisse d'arrivée de lien */
hspace_booking *new; /* Nouvelle réservation */
for (i = 0; i < cluster->ranks_count; i++)
{
rank = &cluster->ranks[i];
/* Enregistrement des besoins */
for (j = 0; j < rank->count; j++)
{
sub = rank->clusters[j];
for (k = 0; k < sub->ta_count; k++)
{
g_graph_edge_get_x_borders(sub->top_anchors[k]->edge, &x1, &x2);
if (x1 > x2)
{
new = (hspace_booking *)calloc(1, sizeof(hspace_booking));
new->start = x1;
sub->top_anchors[k]->hslot = &new->index;
int compare_right_to_left(const hspace_booking **a, const hspace_booking **b)
{
int result; /* Bilan à retourner */
if ((*a)->start > (*b)->start)
result = -1;
else if ((*a)->start < (*b)->start)
result = 1;
else
{
assert(false);
result = 0;
}
return result;
}
rank->right2left = qinsert(rank->right2left, &rank->r2l_count,
sizeof(hspace_booking *),
(__compar_fn_t)compare_right_to_left, &new);
}
else if (x1 < x2)
{
new = (hspace_booking *)calloc(1, sizeof(hspace_booking));
new->start = x1;
sub->top_anchors[k]->hslot = &new->index;
int compare_left_to_right(const hspace_booking **a, const hspace_booking **b)
{
int result; /* Bilan à retourner */
if ((*a)->start < (*b)->start)
result = -1;
else if ((*a)->start > (*b)->start)
result = 1;
else
{
assert(false);
result = 0;
}
return result;
}
rank->left2right = qinsert(rank->left2right, &rank->l2r_count,
sizeof(hspace_booking *),
(__compar_fn_t)compare_left_to_right, &new);
}
else
sub->top_anchors[k]->hslot = NULL;
}
}
/* Définition des couches */
for (j = 0; j < rank->r2l_count; j++)
rank->right2left[j]->index = j;
for (j = 0; j < rank->l2r_count; j++)
rank->left2right[j]->index = j;
/* Propagation des déterminations */
for (j = 0; j < rank->count; j++)
g_graph_cluster_book_hspace_for_links(rank->clusters[j]);
}
}
/******************************************************************************
* *
* Paramètres : cluster = graphique de blocs à actualiser. *
* *
* Description : Détermine les ordonnées de tous les liens en place. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_graph_cluster_compute_link_y_positions(GGraphCluster *cluster)
{
gint y; /* Ordonnée d'application */
size_t i; /* Boucle de parcours #1 */
incoming_edge *incoming; /* Raccourci pour le confort */
size_t j; /* Boucle de parcours #2 */
/* Du côté des départs... */
if (cluster->ba_count > 0)
{
y = cluster->alloc.y + cluster->alloc.height;
for (i = 0; i < cluster->ba_count; i++)
cluster->bottom_anchors[i]->start.y = y;
}
/* Du côté des arrivées... */
if (cluster->ta_count > 0)
{
y = cluster->alloc.y;
for (i = 0; i < cluster->ta_count; i++)
{
incoming = cluster->top_anchors[i];
incoming->end.y = y;
incoming->y.y = incoming->end.y - VERTICAL_MARGIN;
if (incoming->hslot != NULL)
incoming->y.y -= *incoming->hslot * LINK_MARGIN;
}
}
/* Propagation des déterminations */
for (i = 0; i < cluster->ranks_count; i++)
for (j = 0; j < cluster->ranks[i].count; j++)
g_graph_cluster_compute_link_y_positions(cluster->ranks[i].clusters[j]);
}
/******************************************************************************
* *
* Paramètres : cluster = graphique de blocs à consulter. *
* *
* Description : Applique les positions calculées pour chaque lien graphique. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_graph_cluster_resolve_links(const GGraphCluster *cluster)
{
size_t i; /* Boucle de parcours #1 */
size_t j; /* Boucle de parcours #2 */
for (i = 0; i < cluster->ta_count; i++)
g_graph_edge_resolve(cluster->top_anchors[i]->edge);
for (i = 0; i < cluster->ranks_count; i++)
for (j = 0; j < cluster->ranks[i].count; j++)
g_graph_cluster_resolve_links(cluster->ranks[i].clusters[j]);
}
/* Liste de blocs restants à traiter */
typedef struct _pending_blocks
{
size_t count; /* Taille de la liste */
GBasicBlock *list[0]; /* Liste de blocs à traiter */
} pending_blocks;
/* Met en place un ensemble de blocs sous forme graphique. */
static GGraphCluster *setup_graph_clusters(GLoadedBinary *, const GBlockList *, size_t , segcnt_list *, pending_blocks *, GHashTable *);
/******************************************************************************
* *
* Paramètres : binary = binaire charger dont le code est à représenter.*
* list = ensemble de blocs basiques à manipuler. *
* index = indice du bloc principal à mettre en place. *
* highlighted = gestionnaire de surbrillance pour segments. *
* pending = liste de blocs restant à traiter. [OUT] *
* all = table regroupant tous les groupes créés. *
* *
* Description : Met en place un ensemble de blocs sous forme graphique. *
* *
* Retour : Ensemble de blocs mis en place. *
* *
* Remarques : - *
* *
******************************************************************************/
static GGraphCluster *setup_graph_clusters(GLoadedBinary *binary, const GBlockList *list, size_t index, segcnt_list *highlighted, pending_blocks *pending, GHashTable *all)
{
GGraphCluster *result; /* Instance nouvelle à renvoyer*/
GBasicBlock *block; /* Bloc à manipuler */
GArchInstruction *first; /* Première instruction du bloc*/
GArchInstruction *last; /* Dernière instruction du bloc*/
#ifndef NDEBUG
gboolean new; /* Bloc déjà traité ? */
#endif
size_t dcount; /* Nombre de liens de dest. */
size_t i; /* Boucle de parcours #1 */
instr_link_t *dest; /* Instr. visée par une autre */
GBasicBlock *target; /* Bloc ciblé par un lien */
size_t j; /* Boucle de parcours #2 */
bool changed; /* Un ajout a été effectué ? */
const bitfield_t *dominators; /* Blocs dominant ce même bloc */
size_t next; /* Indice du prochain bloc */
GGraphCluster *sub; /* Sous-ensemble à intégrer */
result = g_graph_cluster_new(binary, list, index, highlighted);
block = g_block_list_get_block(list, index);
g_basic_block_get_boundary(block, &first, &last);
#ifndef NDEBUG
new = g_hash_table_insert(all, first, result);
assert(new);
#else
g_hash_table_insert(all, first, result);
#endif
/* Détermination des blocs suivants */
g_arch_instruction_lock_dest(last);
dcount = g_arch_instruction_count_destinations(last);
for (i = 0; i < dcount; i++)
{
dest = g_arch_instruction_get_destination(last, i);
switch (dest->type)
{
case ILT_EXEC_FLOW:
case ILT_JUMP:
case ILT_CASE_JUMP:
case ILT_JUMP_IF_TRUE:
case ILT_JUMP_IF_FALSE:
target = g_block_list_find_by_starting_instr(list, dest->linked);
/**
* Les sauts ne se font pas toujours à l'intérieur d'une même fonction.
* Par exemple sous ARM :
*
* 00008358 <call_gmon_start>:
* ....
* 8362: f7ff bfcf b.w 8304 <_init+0x38>
* ....
*
*/
printf(" NEW BLK :: %d -> %p\n", dest->type, target);
if (target != NULL)
{
for (j = 0; j < pending->count; j++)
if (pending->list[j] == target)
break;
if (j == pending->count)
{
/**
* Il faut vérifier ici si la destination n'a pas déjà été
* empruntée, sauf peine de faire réagir l'assertion plus
* haut au moment de l'insertion.
*
* Le type de code à problème est le suivant :
*
* ...
* if (...)
* ...
* ...
*
* Le code suivant le bloc conditionnel a deux origines,
* qui vont chacune poursuivre le traitement vers ce code
* commun.
*
* Et comme les origines ne sont pas dominantes, on utilise
* la table globale.
*/
if (!g_hash_table_contains(all, dest->linked))
{
assert((pending->count + 1) < g_block_list_count_blocks(list));
pending->list[pending->count++] = target;
printf(" --push-- %d -> %p\n", dest->type, target);
}
}
do
{
size_t k;
printf(" --stack-- ");
for (k = 0; k < pending->count; k++)
printf("%p ", pending->list[k]);
printf("\n");
}
while (0);
}
break;
default:
break;
}
}
g_arch_instruction_unlock_dest(last);
/* Intégration de tous les blocs en attente */
do
{
changed = false;
for (i = 0; i < pending->count && !changed; i++)
{
block = pending->list[i];
dominators = g_basic_block_get_domination(block);
if (test_in_bit_field(dominators, index))
{
/* Dépilement */
changed = true;
if ((i + 1) < pending->count)
memmove(&pending->list[i], &pending->list[i + 1],
(pending->count - i - 1) * sizeof(GBasicBlock *));
pending->count--;
/* Intégration */
next = g_block_list_get_index(list, block);
assert(next < g_block_list_count_blocks(list));
printf(" --pop-- block=%p index=%zu\n", block, next);
sub = setup_graph_clusters(binary, list, next, highlighted, pending, all);
g_graph_cluster_add_sub(result, sub, block);
}
}
}
while (changed);
return result;
}
/******************************************************************************
* *
* Paramètres : blocXXXXXXXXXXXXXXXXXXXXks = ensemble des blocs basiques déjà découpés. *
* views = morceaux de codXXXXXXXXXXXXXXXXXxe à afficher de façon organisée. *
* count = quantité de ces morceaux de code.XXXXXXXXXXXXXXXXXX *
* *
* Description : Construit un graphique à partir de blocs basiques. *
* *
* Retour : Adresse de la structure mise en place. *
* *
* Remarques : - *
* *
******************************************************************************/
GGraphCluster *bootstrap_graph_cluster(GLoadedBinary *binary, const GBlockList *list, segcnt_list *highlighted)
{
GGraphCluster *result; /* Structure à retourner */
GHashTable *all; /* Collection des créations */
size_t count; /* Taille de la liste de blocs */
pending_blocks *pending; /* Suivi des blocs à traiter */
GtkAllocation needed; /* Taille requise */
all = g_hash_table_new(NULL, NULL);
count = g_block_list_count_blocks(list);
pending = (pending_blocks *)calloc(1, sizeof(pending_blocks) + count * sizeof(GBasicBlock *));
#if 0
do
{
size_t i;
GBasicBlock *block;
const bitfield_t *domination;
GArchInstruction *first; /* Première instruction du bloc*/
GArchInstruction *last; /* Dernière instruction du bloc*/
printf("DBG // count : %zu\n", count);
for (i = 0; i < count; i++)
{
block = g_block_list_get_block(list, i);
domination = g_basic_block_get_domination(block);
g_basic_block_get_boundary(block, &first, &last);
printf("DBG // block [%zu] @ 0x%08x : 0x%08lx -- rank = %u\n",
i,
(unsigned int)first->range.addr.virtual,
gfw(domination), g_basic_block_get_rank(block));
}
fflush(NULL);
}
while (0);
void show_tree(GGraphCluster *cluster, int depth)
{
int i;
GArchInstruction *first;
size_t j;
size_t k;
printf("TREE | ");
for (i = 0; i < depth; i++)
printf(" ");
g_basic_block_get_boundary(cluster->block, &first, NULL);
printf("cluster @ 0x%08x\n", (unsigned int)first->range.addr.virtual);
for (j = 0; j < cluster->ranks_count; j++)
{
printf("TREE | ");
for (i = 0; i < depth; i++)
printf(" ");
printf(" + rank %u +\n", cluster->ranks[j].level);
for (k = 0; k < cluster->ranks[j].count; k++)
show_tree(cluster->ranks[j].clusters[k], depth + 1);
}
}
#endif
result = setup_graph_clusters(binary, list, 0, highlighted, pending, all);
free(pending);
g_graph_cluster_define_links(result, all);
//show_tree(result, 0);
//printf("--------------\n");
/* Positionnements dans l'espace */
g_graph_cluster_dispatch_x(result);
/* Réajustement vers la droite */
g_graph_cluster_compute_needed_alloc(result, &needed);
g_graph_cluster_offset_x(result, -needed.x);
/* Application finale sur les liens */
g_graph_cluster_compute_link_x_positions(result);
g_graph_cluster_book_hspace_for_links(result);
g_graph_cluster_set_y(result, 0);
g_graph_cluster_compute_link_y_positions(result);
g_graph_cluster_resolve_links(result);
g_hash_table_unref(all);
return result;
}