From 9895df71ae6ea14e09478cc243227b7b3a2139a3 Mon Sep 17 00:00:00 2001
From: Cyrille Bagard <nocbos@gmail.com>
Date: Sat, 26 Mar 2016 20:56:04 +0100
Subject: Extracted the logic of code nodes for better processing.

---
 ChangeLog                       |  16 ++
 src/analysis/disass/Makefile.am |   1 +
 src/analysis/disass/dragon.c    | 541 ++++++++++++++++++++++++++++++++++++++++
 src/analysis/disass/dragon.h    |  81 ++++++
 src/analysis/disass/loop.c      | 366 +++------------------------
 src/common/bits.c               |   2 +-
 src/common/bits.h               |   2 +-
 7 files changed, 675 insertions(+), 334 deletions(-)
 create mode 100644 src/analysis/disass/dragon.c
 create mode 100644 src/analysis/disass/dragon.h

diff --git a/ChangeLog b/ChangeLog
index 234f547..dc07b31 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,19 @@
+16-03-26  Cyrille Bagard <nocbos@gmail.com>
+
+	* src/analysis/disass/Makefile.am:
+	Add the 'dragon.[ch]' files to libanalysisdisass_la_SOURCES.
+
+	* src/analysis/disass/dragon.c:
+	* src/analysis/disass/dragon.h:
+	New entries: extract the logic of code nodes for better processing.
+
+	* src/analysis/disass/loop.c:
+	Update code.
+
+	* src/common/bits.c:
+	* src/common/bits.h:
+	Mark bit fields as constant when needed.
+
 16-03-24  Cyrille Bagard <nocbos@gmail.com>
 
 	* src/gui/editem.c:
diff --git a/src/analysis/disass/Makefile.am b/src/analysis/disass/Makefile.am
index 54b0fa5..3231749 100644
--- a/src/analysis/disass/Makefile.am
+++ b/src/analysis/disass/Makefile.am
@@ -4,6 +4,7 @@ noinst_LTLIBRARIES = libanalysisdisass.la
 libanalysisdisass_la_SOURCES =			\
 	area.h area.c						\
 	disassembler.h disassembler.c		\
+	dragon.h dragon.c					\
 	fetch.h fetch.c						\
 	limit.h limit.c						\
 	links.h links.c						\
diff --git a/src/analysis/disass/dragon.c b/src/analysis/disass/dragon.c
new file mode 100644
index 0000000..2fcf830
--- /dev/null
+++ b/src/analysis/disass/dragon.c
@@ -0,0 +1,541 @@
+
+/* Chrysalide - Outil d'analyse de fichiers binaires
+ * dragon.c - capacités apportées par la lecture du livre du dragon
+ *
+ * Copyright (C) 2016 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 <http://www.gnu.org/licenses/>.
+ */
+
+
+#include "dragon.h"
+
+
+#include <assert.h>
+#include <malloc.h>
+
+
+
+/* ---------------------------- ENCAPSULATION DES NOEUDS ---------------------------- */
+
+
+/* Description de noeud, en référence à "Compilers: Principles, Techniques, and Tools" */
+struct _dragon_node
+{
+    GArchInstruction *first;                /* Arrivée d'un lien (début)   */
+    GArchInstruction *last;                 /* Départ d'un lien (fin)      */
+
+    bitfield_t *bits;                       /* Représentation par masque   */
+
+};
+
+
+/* Définition des blocs d'allocation */
+#define NODE_ALLOC_SIZE 100
+
+
+/* Dénombre le nombre de noeuds présents dans une routine. */
+static dragon_node *create_dragon_nodes(const GArchProcessor *, const instr_coverage *, const mrange_t *, const vmpa2t *, size_t *);
+
+/* Supprime de la mémoire tous les noeuds détectés. */
+static void delete_dragon_nodes(dragon_node *, size_t);
+
+/* Termine l'initialisation de noeuds trouvés dans une routine. */
+static void init_mask_for_nodes(dragon_node *, size_t);
+
+
+
+/* ---------------------------- ENCAPSULATION DES NOEUDS ---------------------------- */
+
+
+/* Concentration de tous les efforts */
+struct _dragon_knight
+{
+    dragon_node *nodes;                     /* Noeuds mis en place         */
+    size_t count;                           /* Taille de la liste          */
+
+};
+
+
+
+/* ---------------------------------------------------------------------------------- */
+/*                            DECOUPAGES DE CODE EN NOEUDS                            */
+/* ---------------------------------------------------------------------------------- */
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : proc     = ensemble d'instructions à parcourir.              *
+*                coverage = zone de couverture où rechercher des instructions.*
+*                range    = zone de couverture de la routine analysée.        *
+*                start    = adresse du début de l'analyse.                    *
+*                count    = taille de la liste de noeuds retournés. [OUT]     *
+*                                                                             *
+*  Description : Dénombre le nombre de noeuds présents dans une routine.      *
+*                                                                             *
+*  Retour      : Liste de noeuds initialisés de façon incomplète.             *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+static dragon_node *create_dragon_nodes(const GArchProcessor *proc, const instr_coverage *coverage, const mrange_t *range, const vmpa2t *start, size_t *count)
+{
+    dragon_node *result;                    /* Liste à créer et renvoyer   */
+    size_t allocated;                       /* Dimensionnement en mémoire  */
+    GArchInstruction *last;                 /* Mémorisation du passé       */
+    GArchInstruction *iter;                 /* Boucle de parcours          */
+    const mrange_t *irange;                 /* Emplacement d'instruction   */
+    InstructionLinkType *types;             /* Type de lien entre instr.   */
+    size_t scount;                          /* Nombre de liens de dest.    */
+    size_t i;                               /* Boucle de parcours          */
+    dragon_node *new;                       /* Nouvel élément à créer      */
+
+    result = NULL;
+    *count = 0;
+
+    allocated = 0;
+
+    for (last = NULL, iter = g_arch_processor_find_covered_instr_by_address(proc, coverage, start);
+         iter != NULL;
+         last = iter, iter = g_arch_instruction_get_next_iter(iter /* FIXME : list*/, iter, ~0))
+    {
+        /* L'instruction sort-elle des clous ? */
+
+        irange = g_arch_instruction_get_range(iter);
+
+        if (!mrange_contains_mrange(range, irange))
+            break;
+
+        /* Analyse des sources */
+
+        if (result == NULL)
+        {
+            (*count)++;
+
+            if (*count >= allocated)
+            {
+                allocated += NODE_ALLOC_SIZE;
+                result = (dragon_node *)realloc(result, allocated * sizeof(dragon_node));
+            }
+
+            new = &result[*count - 1];
+
+            new->first = iter;
+
+        }
+        else
+        {
+            scount = g_arch_instruction_get_sources(iter, NULL, &types);
+            if (scount == 0) continue;
+
+            for (i = 0; i < scount; i++)
+                switch (types[i])
+                {
+                    case ILT_EXEC_FLOW:
+                    case ILT_JUMP:
+                    case ILT_CASE_JUMP:
+                    case ILT_JUMP_IF_TRUE:
+                    case ILT_JUMP_IF_FALSE:
+
+                        if (*count > 0)
+                            result[*count - 1].last = last;
+
+                        (*count)++;
+                        i = scount;
+
+                        if (*count >= allocated)
+                        {
+                            allocated += NODE_ALLOC_SIZE;
+                            result = (dragon_node *)realloc(result, allocated * sizeof(dragon_node));
+                        }
+
+                        new = &result[*count - 1];
+
+                        new->first = iter;
+
+                        break;
+
+                    default:
+                        break;
+
+                }
+
+        }
+
+    }
+
+    if (*count > 0)
+        result[*count - 1].last = last;
+
+    return result;
+
+}
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : nodes = liste de noeuds détectés dans une routine.           *
+*                count = taille de cette liste de noeuds à traiter.           *
+*                                                                             *
+*  Description : Supprime de la mémoire tous les noeuds détectés.             *
+*                                                                             *
+*  Retour      : -                                                            *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+static void delete_dragon_nodes(dragon_node *nodes, size_t count)
+{
+    size_t i;                               /* Boucle de parcours          */
+
+    for (i = 0; i < count; i++)
+        delete_bit_field(nodes[i].bits);
+
+    free(nodes);
+
+}
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : nodes = liste de noeuds détectés dans une routine.           *
+*                count = taille de cette liste de noeuds à traiter.           *
+*                                                                             *
+*  Description : Termine l'initialisation de noeuds trouvés dans une routine. *
+*                                                                             *
+*  Retour      : -                                                            *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+static void init_mask_for_nodes(dragon_node *nodes, size_t count)
+{
+    size_t i;                               /* Boucle de parcours          */
+
+    for (i = 0; i < count; i++)
+        nodes[i].bits = create_bit_field(count, i > 0);
+
+    set_in_bit_field(nodes[0].bits, 0, 1);
+
+}
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : node  = noeud de code à considérer.                          *
+*                first = instruction de départ à renseigner ou NULL. [OUT]    *
+*                last  = instruction d'arrivée à renseigner ou NULL. [OUT]    *
+*                                                                             *
+*  Description : Fournit les instructions bornant un noeud de code.           *
+*                                                                             *
+*  Retour      : -                                                            *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+void get_dragon_node_bounding_instructions(dragon_node *node, GArchInstruction **first, GArchInstruction **last)
+{
+    if (first != NULL)
+        *first = node->first;
+
+    if (last != NULL)
+        *last = node->last;
+
+}
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : nodes = liste de noeuds détectés dans une routine.           *
+*                                                                             *
+*  Description : Fournit un noeud particulier à partir d'une liste.           *
+*                                                                             *
+*  Retour      : Noeud ciblé.                                                 *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+dragon_node *get_dragon_node(dragon_node *nodes, size_t index)
+{
+    return nodes + index;
+
+}
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : nodes = liste de noeuds détectés dans une routine.           *
+*                node  = noeud ciblé au sein de cette liste.                  *
+*                                                                             *
+*  Description : Fournit l'indice d'un noeud particulier à partir d'une liste.*
+*                                                                             *
+*  Retour      : Indice du noeud ciblé.                                       *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+size_t get_dragon_node_index(dragon_node *nodes, dragon_node *node)
+{
+    return node - nodes;
+
+}
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : nodes = liste de noeuds détectés dans une routine.           *
+*                count = taille de cette liste de noeuds à parcourir.         *
+*                final = précise si l'instruction visée est la première.      *
+*                instr = instruction à retrouver en tant que début de noeud.  *
+*                                                                             *
+*  Description : Recherche un noeud selon son intruction de départ.           *
+*                                                                             *
+*  Retour      : Noeud trouvé ou NULL si aucune trouvaille.                   *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+dragon_node *find_node_for_instruction(dragon_node *nodes, size_t count, bool final, const GArchInstruction *instr)
+{
+    dragon_node *result;                    /* Résultat des recherches     */
+    const mrange_t *irange;                 /* Emplacement d'instruction   */
+
+    int find_node_from_range(const mrange_t *range, const dragon_node *node)
+    {
+        int status;                         /* Bilan à retourner           */
+        const mrange_t *nrange;             /* Emplacement de noeud        */
+
+        nrange = g_arch_instruction_get_range(final ? node->last : node->first);
+
+        status = cmp_mrange(range, nrange);
+
+        return status;
+
+    }
+
+    irange = g_arch_instruction_get_range(instr);
+
+    result = bsearch(irange, nodes, count, sizeof(dragon_node), (__compar_fn_t)find_node_from_range);
+
+    return result;
+
+}
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : nodes = liste de noeuds détectés dans une routine.           *
+*                count = taille de cette liste de noeuds à traiter.           *
+*                                                                             *
+*  Description : Détermine toute la chaîne hiérarchique de domination.        *
+*                                                                             *
+*  Retour      : -                                                            *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+void compute_all_dominators(dragon_node *nodes, size_t count)
+{
+    bitfield_t *inter;                      /* Intersection de dominations */
+    bool changed;                           /* Note un changement qq part  */
+    size_t k;                               /* Boucle de parcours #1       */
+    dragon_node *node;                      /* Noeud à traiter             */
+    dragon_node *predecessor;               /* Noeud prédécesseur direct   */
+    GArchInstruction **srcs;                /* Instructions d'origine      */
+    InstructionLinkType *types;             /* Type de lien entre instr.   */
+    size_t scount;                          /* Nombre de liens de source   */
+    size_t i;                               /* Boucle de parcours #2       */
+
+    inter = create_bit_field(count, false);
+
+    do
+    {
+        changed = false;
+
+        for (k = 1; k < count; k++)
+        {
+            node = &nodes[k];
+
+            set_all_in_bit_field(inter);
+
+            scount = g_arch_instruction_get_sources(node->first, &srcs, &types);
+            assert(scount > 0);
+
+            for (i = 0; i < scount; i++)
+                switch (types[i])
+                {
+                    case ILT_EXEC_FLOW:
+                    case ILT_JUMP:
+                    case ILT_CASE_JUMP:
+                    case ILT_JUMP_IF_TRUE:
+                    case ILT_JUMP_IF_FALSE:
+
+                        predecessor = find_node_for_instruction(nodes, count, true, srcs[i]);
+
+
+                        printf("  -- finding pred @ 0x%08x -> 0x%08x :: %p\n",
+                               (unsigned int)g_arch_instruction_get_range(node->first)->addr.virtual,
+                               (unsigned int)g_arch_instruction_get_range(srcs[i])->addr.virtual,
+                               predecessor);
+
+
+
+                        if (predecessor == NULL) break;
+
+                        and_bit_field(inter, predecessor->bits);
+                        break;
+
+                    default:
+                        break;
+
+                }
+
+            set_in_bit_field(inter, k, 1);
+
+            if (!is_bit_field_equal_to(node->bits, inter))
+            {
+                copy_bit_field(node->bits, inter);
+                changed = true;
+            }
+
+        }
+
+    }
+    while (changed);
+
+    delete_bit_field(inter);
+
+}
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : node = noeud représentant une portion de code à consulter.   *
+*                                                                             *
+*  Description : Fournit la liste des noeuds dominés par un noeud.            *
+*                                                                             *
+*  Retour      : Champ de bits en place.                                      *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+const bitfield_t *get_domination_bits(const dragon_node *node)
+{
+    return node->bits;
+
+}
+
+
+
+
+
+
+/* ---------------------------------------------------------------------------------- */
+/*                              ENCAPSULATION DES NOEUDS                              */
+/* ---------------------------------------------------------------------------------- */
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : proc     = ensemble d'instructions à parcourir.              *
+*                coverage = zone de couverture où rechercher des instructions.*
+*                range    = zone de couverture de la routine analysée.        *
+*                start    = adresse du début de l'analyse.                    *
+*                                                                             *
+*  Description : Attaque la complexité d'un code en créant des noeuds.        *
+*                                                                             *
+*  Retour      : Définition d'un complexe de noeuds établis.                  *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+dragon_knight *begin_dragon_knight(const GArchProcessor *proc, const instr_coverage *coverage, const mrange_t *range, const vmpa2t *start)
+{
+    dragon_knight *result;                  /* Données à retourner         */
+    dragon_node *nodes;                     /* Noeuds mis en place         */
+    size_t count;                           /* Nombre de ces noeuds        */
+
+    result = NULL;
+
+    nodes = create_dragon_nodes(proc, coverage, range, start, &count);
+
+    if (nodes != NULL)
+    {
+        init_mask_for_nodes(nodes, count);
+
+        result = (dragon_knight *)calloc(1, sizeof(dragon_knight));
+
+        result->nodes = nodes;
+        result->count = count;
+
+    }
+
+    return result;
+
+}
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : knight = données représentant une complexité traitée.        *
+*                                                                             *
+*  Description : Supprime de la mémoire les données d'une complexité de code. *
+*                                                                             *
+*  Retour      : -                                                            *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+void end_dragon_knight(dragon_knight *knight)
+{
+    delete_dragon_nodes(knight->nodes, knight->count);
+
+    free(knight);
+
+}
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : knight = données représentant une complexité à considérer.   *
+*                nodes  = noeuds de code associés à récupérer. [OUT]          *
+*                count  = taille de cette liste de noeuds. [OUT]              *
+*                                                                             *
+*  Description : Fournit les éléments utiles à un traitement de blocs de code.*
+*                                                                             *
+*  Retour      : -                                                            *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+void get_dragon_knight_content(dragon_knight *knight, dragon_node **nodes, size_t *count)
+{
+    *nodes = knight->nodes;
+    *count = knight->count;
+
+}
diff --git a/src/analysis/disass/dragon.h b/src/analysis/disass/dragon.h
new file mode 100644
index 0000000..c6f6fd5
--- /dev/null
+++ b/src/analysis/disass/dragon.h
@@ -0,0 +1,81 @@
+
+/* Chrysalide - Outil d'analyse de fichiers binaires
+ * dragon.h - prototypes pour les capacités apportées par la lecture du livre du dragon
+ *
+ * Copyright (C) 2016 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 <http://www.gnu.org/licenses/>.
+ */
+
+
+#ifndef _ANALYSIS_DISASS_DRAGON_H
+#define _ANALYSIS_DISASS_DRAGON_H
+
+
+#include "../../arch/processor.h"
+#include "../../common/bits.h"
+
+
+
+/* -------------------------- DECOUPAGES DE CODE EN NOEUDS -------------------------- */
+
+
+/* Description de noeud, en référence à "Compilers: Principles, Techniques, and Tools" */
+typedef struct _dragon_node dragon_node;
+
+
+/* Fournit les instructions bornant un noeud de code. */
+void get_dragon_node_bounding_instructions(dragon_node *, GArchInstruction **, GArchInstruction **);
+
+/* Fournit un noeud particulier à partir d'une liste. */
+dragon_node *get_dragon_node(dragon_node *, size_t);
+
+/* Fournit l'indice d'un noeud particulier à partir d'une liste. */
+size_t get_dragon_node_index(dragon_node *, dragon_node *);
+
+/* Recherche un noeud selon son intruction de départ. */
+dragon_node *find_node_for_instruction(dragon_node *, size_t, bool, const GArchInstruction *);
+
+/* Détermine toute la chaîne hiérarchique de domination. */
+void compute_all_dominators(dragon_node *, size_t);
+
+/* Fournit la liste des noeuds dominés par un noeud. */
+const bitfield_t *get_domination_bits(const dragon_node *);
+
+
+
+
+
+
+/* ---------------------------- ENCAPSULATION DES NOEUDS ---------------------------- */
+
+
+/* Concentration de tous les efforts */
+typedef struct _dragon_knight dragon_knight;
+
+
+/* Attaque la complexité d'un code en créant des noeuds. */
+dragon_knight *begin_dragon_knight(const GArchProcessor *, const instr_coverage *, const mrange_t *, const vmpa2t *);
+
+/* Supprime de la mémoire les données d'une complexité de code. */
+void end_dragon_knight(dragon_knight *);
+
+/* Fournit les éléments utiles à un traitement de blocs de code. */
+void get_dragon_knight_content(dragon_knight *, dragon_node **, size_t *);
+
+
+
+#endif  /* _ANALYSIS_DISASS_DRAGON_H */
diff --git a/src/analysis/disass/loop.c b/src/analysis/disass/loop.c
index 94916f7..dd0b661 100644
--- a/src/analysis/disass/loop.c
+++ b/src/analysis/disass/loop.c
@@ -28,39 +28,14 @@
 #include <malloc.h>
 
 
-#include "../../common/bits.h"
-
-
-
-/* Description de noeud, en référence à "Compilers: Principles, Techniques, and Tools" */
-typedef struct _dragon_node
-{
-    GArchInstruction *first;                /* Arrivée d'un lien (début)   */
-    GArchInstruction *last;                 /* Départ d'un lien (fin)      */
-
-    bitfield_t *bits;                       /* Représentation par masque   */
-
-} dragon_node;
+#include "dragon.h"
 
 
-/* Définition des blocs d'allocation */
-#define NODE_ALLOC_SIZE 100
 
 
-/* Dénombre le nombre de noeuds présents dans une routine. */
-static dragon_node *create_dragon_nodes(const GArchProcessor *, const instr_coverage *, const mrange_t *, const vmpa2t *, size_t *);
 
-/* Termine l'initialisation de noeuds trouvés dans une routine. */
-static void define_mask_for_nodes(dragon_node *, size_t);
 
-/* Supprime de la mémoire tous les noeuds détectés. */
-static void delete_dragon_nodes(dragon_node *, size_t);
 
-/* Recherche un noeud selon son intruction de départ. */
-static dragon_node *find_node_for_instruction(dragon_node *, size_t, bool, const GArchInstruction *);
-
-/* Détermine toute la chaîne hiérarchique de domination. */
-static void compute_all_dominators(dragon_node *, size_t);
 
 /* Matérialise les liens de retour arrière en tant que boucles. */
 static void detect_back_edges(dragon_node *, size_t);
@@ -70,294 +45,6 @@ static void track_loops_in_code(const GArchProcessor *, const instr_coverage *,
 
 
 
-/******************************************************************************
-*                                                                             *
-*  Paramètres  : proc     = ensemble d'instructions à parcourir.              *
-*                coverage = zone de couverture où rechercher des instructions.*
-*                range    = zone de couverture de la routine analysée.        *
-*                start    = adresse du début de l'analyse.                    *
-*                count    = taille de la liste de noeuds retournés. [OUT]     *
-*                                                                             *
-*  Description : Dénombre le nombre de noeuds présents dans une routine.      *
-*                                                                             *
-*  Retour      : Liste de noeuds initialisés de façon incomplète.             *
-*                                                                             *
-*  Remarques   : -                                                            *
-*                                                                             *
-******************************************************************************/
-
-static dragon_node *create_dragon_nodes(const GArchProcessor *proc, const instr_coverage *coverage, const mrange_t *range, const vmpa2t *start, size_t *count)
-{
-    dragon_node *result;                    /* Liste à créer et renvoyer   */
-    size_t allocated;                       /* Dimensionnement en mémoire  */
-    GArchInstruction *last;                 /* Mémorisation du passé       */
-    GArchInstruction *iter;                 /* Boucle de parcours          */
-    const mrange_t *irange;                 /* Emplacement d'instruction   */
-    InstructionLinkType *types;             /* Type de lien entre instr.   */
-    size_t scount;                          /* Nombre de liens de dest.    */
-    size_t i;                               /* Boucle de parcours          */
-    dragon_node *new;                       /* Nouvel élément à créer      */
-
-    result = NULL;
-    *count = 0;
-
-    allocated = 0;
-
-    for (last = NULL, iter = g_arch_processor_find_covered_instr_by_address(proc, coverage, start);
-         iter != NULL;
-         last = iter, iter = g_arch_instruction_get_next_iter(iter /* FIXME : list*/, iter, ~0))
-    {
-        /* L'instruction sort-elle des clous ? */
-
-        irange = g_arch_instruction_get_range(iter);
-
-        if (!mrange_contains_mrange(range, irange))
-            break;
-
-        /* Analyse des sources */
-
-        if (result == NULL)
-        {
-            (*count)++;
-
-            if (*count >= allocated)
-            {
-                allocated += NODE_ALLOC_SIZE;
-                result = (dragon_node *)realloc(result, allocated * sizeof(dragon_node));
-            }
-
-            new = &result[*count - 1];
-
-            new->first = iter;
-
-        }
-        else
-        {
-            scount = g_arch_instruction_get_sources(iter, NULL, &types);
-            if (scount == 0) continue;
-
-            for (i = 0; i < scount; i++)
-                switch (types[i])
-                {
-                    case ILT_EXEC_FLOW:
-                    case ILT_JUMP:
-                    case ILT_CASE_JUMP:
-                    case ILT_JUMP_IF_TRUE:
-                    case ILT_JUMP_IF_FALSE:
-
-                        if (*count > 0)
-                            result[*count - 1].last = last;
-
-                        (*count)++;
-                        i = scount;
-
-                        if (*count >= allocated)
-                        {
-                            allocated += NODE_ALLOC_SIZE;
-                            result = (dragon_node *)realloc(result, allocated * sizeof(dragon_node));
-                        }
-
-                        new = &result[*count - 1];
-
-                        new->first = iter;
-
-                        break;
-
-                    default:
-                        break;
-
-                }
-
-        }
-
-    }
-
-    if (*count > 0)
-        result[*count - 1].last = last;
-
-    return result;
-
-}
-
-
-/******************************************************************************
-*                                                                             *
-*  Paramètres  : nodes = liste de noeuds détectés dans une routine.           *
-*                count = taille de cette liste de noeuds à traiter.           *
-*                                                                             *
-*  Description : Termine l'initialisation de noeuds trouvés dans une routine. *
-*                                                                             *
-*  Retour      : -                                                            *
-*                                                                             *
-*  Remarques   : -                                                            *
-*                                                                             *
-******************************************************************************/
-
-static void define_mask_for_nodes(dragon_node *nodes, size_t count)
-{
-    size_t i;                               /* Boucle de parcours          */
-
-    for (i = 0; i < count; i++)
-        nodes[i].bits = create_bit_field(count, i > 0);
-
-    set_in_bit_field(nodes[0].bits, 0, 1);
-
-}
-
-
-/******************************************************************************
-*                                                                             *
-*  Paramètres  : nodes = liste de noeuds détectés dans une routine.           *
-*                count = taille de cette liste de noeuds à traiter.           *
-*                                                                             *
-*  Description : Supprime de la mémoire tous les noeuds détectés.             *
-*                                                                             *
-*  Retour      : -                                                            *
-*                                                                             *
-*  Remarques   : -                                                            *
-*                                                                             *
-******************************************************************************/
-
-static void delete_dragon_nodes(dragon_node *nodes, size_t count)
-{
-    size_t i;                               /* Boucle de parcours          */
-
-    for (i = 0; i < count; i++)
-        delete_bit_field(nodes[i].bits);
-
-    free(nodes);
-
-}
-
-
-/******************************************************************************
-*                                                                             *
-*  Paramètres  : nodes = liste de noeuds détectés dans une routine.           *
-*                count = taille de cette liste de noeuds à parcourir.         *
-*                final = précise si l'instruction visée est la première.      *
-*                instr = instruction à retrouver en tant que début de noeud.  *
-*                                                                             *
-*  Description : Recherche un noeud selon son intruction de départ.           *
-*                                                                             *
-*  Retour      : Noeud trouvé ou NULL si aucune trouvaille.                   *
-*                                                                             *
-*  Remarques   : -                                                            *
-*                                                                             *
-******************************************************************************/
-
-static dragon_node *find_node_for_instruction(dragon_node *nodes, size_t count, bool final, const GArchInstruction *instr)
-{
-    dragon_node *result;                    /* Résultat des recherches     */
-    const mrange_t *irange;                 /* Emplacement d'instruction   */
-
-    int find_node_from_range(const mrange_t *range, const dragon_node *node)
-    {
-        int status;                         /* Bilan à retourner           */
-        const mrange_t *nrange;             /* Emplacement de noeud        */
-
-        nrange = g_arch_instruction_get_range(final ? node->last : node->first);
-
-        status = cmp_mrange(range, nrange);
-
-        return status;
-
-    }
-
-    irange = g_arch_instruction_get_range(instr);
-
-    result = bsearch(irange, nodes, count, sizeof(dragon_node), (__compar_fn_t)find_node_from_range);
-
-    return result;
-
-}
-
-
-/******************************************************************************
-*                                                                             *
-*  Paramètres  : nodes = liste de noeuds détectés dans une routine.           *
-*                count = taille de cette liste de noeuds à traiter.           *
-*                                                                             *
-*  Description : Détermine toute la chaîne hiérarchique de domination.        *
-*                                                                             *
-*  Retour      : -                                                            *
-*                                                                             *
-*  Remarques   : -                                                            *
-*                                                                             *
-******************************************************************************/
-
-static void compute_all_dominators(dragon_node *nodes, size_t count)
-{
-    bitfield_t *inter;                      /* Intersection de dominations */
-    bool changed;                           /* Note un changement qq part  */
-    size_t k;                               /* Boucle de parcours #1       */
-    dragon_node *node;                      /* Noeud à traiter             */
-    dragon_node *predecessor;               /* Noeud prédécesseur direct   */
-    GArchInstruction **srcs;                /* Instructions d'origine      */
-    InstructionLinkType *types;             /* Type de lien entre instr.   */
-    size_t scount;                          /* Nombre de liens de source   */
-    size_t i;                               /* Boucle de parcours #2       */
-
-    inter = create_bit_field(count, false);
-
-    do
-    {
-        changed = false;
-
-        for (k = 1; k < count; k++)
-        {
-            node = &nodes[k];
-
-            set_all_in_bit_field(inter);
-
-            scount = g_arch_instruction_get_sources(node->first, &srcs, &types);
-            assert(scount > 0);
-
-            for (i = 0; i < scount; i++)
-                switch (types[i])
-                {
-                    case ILT_EXEC_FLOW:
-                    case ILT_JUMP:
-                    case ILT_CASE_JUMP:
-                    case ILT_JUMP_IF_TRUE:
-                    case ILT_JUMP_IF_FALSE:
-
-                        predecessor = find_node_for_instruction(nodes, count, true, srcs[i]);
-
-
-                        printf("  -- finding pred @ 0x%08x -> 0x%08x :: %p\n",
-                               (unsigned int)g_arch_instruction_get_range(node->first)->addr.virtual,
-                               (unsigned int)g_arch_instruction_get_range(srcs[i])->addr.virtual,
-                               predecessor);
-
-
-
-                        if (predecessor == NULL) break;
-
-                        and_bit_field(inter, predecessor->bits);
-                        break;
-
-                    default:
-                        break;
-
-                }
-
-            set_in_bit_field(inter, k, 1);
-
-            if (!is_bit_field_equal_to(node->bits, inter))
-            {
-                copy_bit_field(node->bits, inter);
-                changed = true;
-            }
-
-        }
-
-    }
-    while (changed);
-
-    delete_bit_field(inter);
-
-}
-
 
 
 /******************************************************************************
@@ -377,6 +64,8 @@ static void detect_back_edges(dragon_node *nodes, size_t count)
 {
     size_t k;                               /* Boucle de parcours #1       */
     dragon_node *node;                      /* Noeud à traiter             */
+    const bitfield_t *dominators;           /* Liste de dominateurs        */
+    GArchInstruction *last;                 /* Instruction finale de noeud */
     GArchInstruction **dests;               /* Instr. visée par une autre  */
     InstructionLinkType *types;             /* Type de lien entre lignes   */
     size_t dcount;                          /* Nombre de liens de dest.    */
@@ -390,24 +79,33 @@ static void detect_back_edges(dragon_node *nodes, size_t count)
 
     for (k = 0; k < count; k++)
     {
-        node = &nodes[k];
+        GArchInstruction *first;
+
+        node = get_dragon_node(nodes, k);
+
+        dominators = get_domination_bits(node);
+
+        get_dragon_node_bounding_instructions(node, &first, &last);
+
 
         printf("#[ node %zu ]#  @ 0x%08x / 0x%08x  -  mask = 0x%08lx\n", k,
-               (unsigned int)g_arch_instruction_get_range(node->first)->addr.virtual,
-               (unsigned int)g_arch_instruction_get_range(node->last)->addr.virtual,
-               gfw(node->bits));
+               (unsigned int)g_arch_instruction_get_range(first)->addr.virtual,
+               (unsigned int)g_arch_instruction_get_range(last)->addr.virtual,
+               gfw(dominators));
 
     }
 
     printf("\n");
 
-
-
     for (k = 1; k < count; k++)
     {
-        node = &nodes[k];
+        node = get_dragon_node(nodes, k);
+
+        dominators = get_domination_bits(node);
 
-        dcount = g_arch_instruction_get_destinations(node->last, &dests, &types, NULL);
+        get_dragon_node_bounding_instructions(node, NULL, &last);
+
+        dcount = g_arch_instruction_get_destinations(last, &dests, &types, NULL);
         if (dcount == 0) continue;
 
         for (i = 0; i < dcount; i++)
@@ -422,17 +120,17 @@ static void detect_back_edges(dragon_node *nodes, size_t count)
                     target = find_node_for_instruction(nodes, count, false, dests[i]);
                     if (target == NULL) break;
 
-                    id = (target - nodes);
+                    id = get_dragon_node_index(nodes, target);
 
-                    if (test_in_bit_field(node->bits, id, 1))
+                    if (test_in_bit_field(dominators, id, 1))
                     {
 
                         printf("BACKEDGE :: 0x%08lx -> 0x%08lx\n",
-                               (unsigned int)g_arch_instruction_get_range(node->last)->addr.virtual,
+                               (unsigned int)g_arch_instruction_get_range(last)->addr.virtual,
                                (unsigned int)g_arch_instruction_get_range(dests[i])->addr.virtual);
 
 
-                        /* status = */g_arch_instruction_change_link(node->last, dests[i], types[i], ILT_LOOP);
+                        /* status = */g_arch_instruction_change_link(last, dests[i], types[i], ILT_LOOP);
 
 
                     }
@@ -468,25 +166,29 @@ static void detect_back_edges(dragon_node *nodes, size_t count)
 
 static void track_loops_in_code(const GArchProcessor *proc, const instr_coverage *coverage, const mrange_t *range, const vmpa2t *start, memfield_t *flow)
 {
+    dragon_knight *knight;                  /* Complexité de code posée    */
     dragon_node *nodes;                     /* Liste des noeuds détectés   */
     size_t count;                           /* Taille de cette liste       */
 
-    nodes = create_dragon_nodes(proc, coverage, range, start, &count);
+    knight = begin_dragon_knight(proc, coverage, range, start);
 
+    if (knight == NULL) return;
 
-    if (nodes == NULL) return;
+    assert(knight != NULL);
 
-    assert(nodes != NULL);
 
-    printf("nodes count :: %d\n", (int)count);
 
-    define_mask_for_nodes(nodes, count);
+    get_dragon_knight_content(knight, &nodes, &count);
+
+
+    printf("nodes count :: %d\n", (int)count);
 
     compute_all_dominators(nodes, count);
 
     detect_back_edges(nodes, count);
 
-    delete_dragon_nodes(nodes, count);
+
+    end_dragon_knight(knight);
 
 }
 
diff --git a/src/common/bits.c b/src/common/bits.c
index b08dcb4..90cb098 100644
--- a/src/common/bits.c
+++ b/src/common/bits.c
@@ -460,7 +460,7 @@ void or_bit_field(bitfield_t *dest, const bitfield_t *src)
 *                                                                             *
 ******************************************************************************/
 
-bool test_in_bit_field(bitfield_t *field, size_t first, size_t count)
+bool test_in_bit_field(const bitfield_t *field, size_t first, size_t count)
 {
     bool result;                            /* Valeur retrouvée à renvoyer */
     size_t last;                            /* Point d'arrêt de la boucle  */
diff --git a/src/common/bits.h b/src/common/bits.h
index 074aac4..6d8ea5b 100644
--- a/src/common/bits.h
+++ b/src/common/bits.h
@@ -70,7 +70,7 @@ void and_bit_field(bitfield_t *, const bitfield_t *);
 void or_bit_field(bitfield_t *, const bitfield_t *);
 
 /* Détermine si un bit est à 1 dans un champ de bits. */
-bool test_in_bit_field(bitfield_t *, size_t, size_t);
+bool test_in_bit_field(const bitfield_t *, size_t, size_t);
 
 /* Indique si deux champs de bits sont identiques ou non. */
 bool is_bit_field_equal_to(const bitfield_t *, const bitfield_t *);
-- 
cgit v0.11.2-87-g4458