Detected loops as introduced in the book "Compilers: Principles, Techniques, and Tools".

git-svn-id: svn://svn.gna.org/svn/chrysalide/trunk@596 abbe820e-26c8-41b2-8c08-b7b2b41f8b0a

6 files changed, 826 insertions, 12 deletions

diff --git a/ChangeLog b/ChangeLog
index 7964745..f5894ff 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,19 @@
+15-10-15  Cyrille Bagard <nocbos@gmail.com>
+
+	* src/analysis/disass/area.c:
+	Add more checks.
+
+	* src/analysis/disass/loop.c:
+	Detect loops as introduced in the book
+	"Compilers: Principles, Techniques, and Tools".
+
+	* src/arch/arm/context.c:
+	Add one extra check.
+
+	* src/common/bits.c:
+	* src/common/bits.h:
+	Define more features for bit fields.
+
 15-10-14  Cyrille Bagard <nocbos@gmail.com>
 
 	* src/analysis/disass/area.c:
diff --git a/src/analysis/disass/area.c b/src/analysis/disass/area.c
index b45e7fc..de2c742 100644
--- a/src/analysis/disass/area.c
+++ b/src/analysis/disass/area.c
@@ -554,6 +554,8 @@ bool load_code_from_mem_area(mem_area **list, size_t *count, size_t *index, cons
 
         diff = compute_vmpa_diff(&prev, &pos);
 
+        assert(diff == 4 || diff == 2); /* FIXME */
+
         init_mrange(&range, &prev, diff);
 
         g_arch_instruction_set_range(instr, &range);
@@ -840,7 +842,7 @@ void fill_mem_area(mem_area **list, size_t *count, size_t *index, const GLoadedB
             copy_vmpa(&start, get_mrange_addr(&area->range));
             advance_vmpa(&start, i);
 
-            if (area->exec && get_virt_addr(&start) % 2 == 0)
+            if (area->exec && get_virt_addr(&start) % 4/*2 - FIXME */ == 0)
             {
                 refresh = load_code_from_mem_area(list, count, index, binary, ctx, &start, info);
 
@@ -1396,6 +1398,8 @@ static bool insert_extra_symbol_into_mem_areas(mem_area **list, size_t *count, G
     /* Si le symbole est construit avec une localisation partielle, on complète ! */
     if (get_phy_addr(&sym_pos) == VMPA_NO_PHYSICAL || get_virt_addr(&sym_pos) == VMPA_NO_VIRTUAL)
     {
+        assert(false);
+
         diff = compute_vmpa_diff(&area_pos, &sym_pos);
 
         copy_vmpa(&sym_pos, &area_pos);
diff --git a/src/analysis/disass/loop.c b/src/analysis/disass/loop.c
index 5f97981..d9a3f2d 100644
--- a/src/analysis/disass/loop.c
+++ b/src/analysis/disass/loop.c
@@ -24,6 +24,592 @@
 #include "loop.h"
 
 
+#include <assert.h>
+#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;
+
+
+/* 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);
+
+/* Suit un flot d'exécution à la recherche de boucles. */
+static void track_loops_in_code(const GArchProcessor *, const instr_coverage *, const mrange_t *, const vmpa2t *, memfield_t *);
+
+
+
+/******************************************************************************
+*                                                                             *
+*  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);
+
+}
+
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : nodes = liste de noeuds détectés dans une routine.           *
+*                count = taille de cette liste de noeuds à traiter.           *
+*                                                                             *
+*  Description : Matérialise les liens de retour arrière en tant que boucles. *
+*                                                                             *
+*  Retour      : -                                                            *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+static void detect_back_edges(dragon_node *nodes, size_t count)
+{
+    size_t k;                               /* Boucle de parcours #1       */
+    dragon_node *node;                      /* Noeud à traiter             */
+    GArchInstruction **dests;               /* Instr. visée par une autre  */
+    InstructionLinkType *types;             /* Type de lien entre lignes   */
+    size_t dcount;                          /* Nombre de liens de dest.    */
+    size_t i;                               /* Boucle de parcours #2       */
+    dragon_node *target;                    /* Noeud référencé à tester    */
+    size_t id;                              /* Indice du bit associé       */
+
+
+
+    printf("-----------------------------------------------------------------\n");
+
+    for (k = 0; k < count; k++)
+    {
+        node = &nodes[k];
+
+        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));
+
+    }
+
+    printf("\n");
+
+
+
+    for (k = 1; k < count; k++)
+    {
+        node = &nodes[k];
+
+        dcount = g_arch_instruction_get_destinations(node->last, &dests, &types, NULL);
+        if (dcount == 0) continue;
+
+        for (i = 0; i < dcount; 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:
+
+                    target = find_node_for_instruction(nodes, count, false, dests[i]);
+                    if (target == NULL) break;
+
+                    id = (target - nodes);
+
+                    if (test_in_bit_field(node->bits, 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(dests[i])->addr.virtual);
+
+
+                        /* status = */g_arch_instruction_change_link(node->last, dests[i], types[i], ILT_LOOP);
+
+
+                    }
+
+                    break;
+
+                default:
+                    break;
+
+            }
+
+    }
+
+}
+
+
+
+/******************************************************************************
+*                                                                             *
+*  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.                    *
+*                flow     = ensemble des jalons de l'exécution du code.       *
+*                                                                             *
+*  Description : Suit un flot d'exécution à la recherche de boucles.          *
+*                                                                             *
+*  Retour      : -                                                            *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+static void track_loops_in_code(const GArchProcessor *proc, const instr_coverage *coverage, const mrange_t *range, const vmpa2t *start, memfield_t *flow)
+{
+    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);
+    assert(nodes != NULL);
+
+    printf("nodes count :: %d\n", (int)count);
+
+    define_mask_for_nodes(nodes, count);
+
+    compute_all_dominators(nodes, count);
+
+    detect_back_edges(nodes, count);
+
+    delete_dragon_nodes(nodes, count);
+
+}
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : proc      = ensemble d'instructions à relier.                *
+*                routines  = prototypes existants à insérer.                  *
+*                count     = quantité de ces prototypes.                      *
+*                statusbar = barre de statut avec progression à mettre à jour.*
+*                id        = identifiant du message affiché à l'utilisateur.  *
+*                                                                             *
+*  Description : Détecte les boucles dans du code machine.                    *
+*                                                                             *
+*  Retour      : -                                                            *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+void detect_loops_in_code(const GArchProcessor *proc, GBinRoutine **routines, size_t count, GtkExtStatusBar *statusbar, bstatus_id_t id)
+{
+    size_t i;                               /* Boucle de parcours          */
+    const mrange_t *range;                  /* Couverture d'une routine    */
+    const vmpa2t *start;                    /* Adresse de départ           */
+    const instr_coverage *coverage;         /* Instructions couvertes      */
+    memfield_t *flow;                       /* Flot d'exécution à suivre   */
+
+    //for (i = 286; i == 286; i++)
+    for (i = 0; i < count; i++)
+    {
+
+
+        range = g_binary_routine_get_range(routines[i]);
+        start = get_mrange_addr(range);
+
+
+        printf("====== '%s' @ 0x%08x\n",
+               g_binary_routine_get_name(routines[i]),
+               start->virtual);
+
+
+        coverage = g_arch_processor_find_coverage_by_address(proc, start);
+
+        flow = NULL;//create_mem_field(range);
+        track_loops_in_code(proc, coverage, range, start, flow);
+        //delete_mem_field(flow);
+
+        gtk_extended_status_bar_update_activity(statusbar, id, (i + 1) * 1.0 / count);
+
+    }
+
+
+    printf("done\n\n");
+    //exit(0);
+
+
+}
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+////////////////////////////////////////////////////////////////////////////////////////////////////////////
+////////////////////////////////////////////////////////////////////////////////////////////////////////////
+////////////////////////////////////////////////////////////////////////////////////////////////////////////
+////////////////////////////////////////////////////////////////////////////////////////////////////////////
+////////////////////////////////////////////////////////////////////////////////////////////////////////////
+////////////////////////////////////////////////////////////////////////////////////////////////////////////
+////////////////////////////////////////////////////////////////////////////////////////////////////////////
+////////////////////////////////////////////////////////////////////////////////////////////////////////////
+////////////////////////////////////////////////////////////////////////////////////////////////////////////
+////////////////////////////////////////////////////////////////////////////////////////////////////////////
+////////////////////////////////////////////////////////////////////////////////////////////////////////////
+////////////////////////////////////////////////////////////////////////////////////////////////////////////
+////////////////////////////////////////////////////////////////////////////////////////////////////////////
+////////////////////////////////////////////////////////////////////////////////////////////////////////////
+////////////////////////////////////////////////////////////////////////////////////////////////////////////
+////////////////////////////////////////////////////////////////////////////////////////////////////////////
+
+
+
+#if 0
+
+
 #include <malloc.h>
 #include <stdlib.h>
 #include <string.h>
@@ -193,6 +779,8 @@ void detect_loops_in_code(const GArchProcessor *proc, GBinRoutine **routines, si
 
     for (i = 0; i < count; i++)
     {
+
+
         range = g_binary_routine_get_range(routines[i]);
         start = get_mrange_addr(range);
 
@@ -207,3 +795,10 @@ void detect_loops_in_code(const GArchProcessor *proc, GBinRoutine **routines, si
     }
 
 }
+
+
+
+
+
+
+#endif
diff --git a/src/arch/arm/context.c b/src/arch/arm/context.c
index 386f21a..b54de42 100644
--- a/src/arch/arm/context.c
+++ b/src/arch/arm/context.c
@@ -267,6 +267,8 @@ void _g_arm_context_define_encoding(GArmContext *ctx, virt_t addr, unsigned int
 
     selected = find_disass_arm_area(ctx->areas, addr, 0, ctx->acount - 1);
 
+    assert(ctx->areas[selected].start != addr || ctx->areas[selected].marker == marker);
+
     /* S'agit-il d'une redéfinition ? */
     if (ctx->areas[selected].start == addr)
         ctx->areas[selected].marker = marker;
diff --git a/src/common/bits.c b/src/common/bits.c
index 1bd90f4..d451100 100644
--- a/src/common/bits.c
+++ b/src/common/bits.c
@@ -37,6 +37,7 @@
 struct _bitfield_t
 {
     size_t length;                          /* Nombre de bits représentés  */
+    size_t requested;                       /* Nombre de mots alloués      */
 
     void *tail;                             /* Limite du tableau de bits   */
 
@@ -46,7 +47,7 @@ struct _bitfield_t
 
 
 /* Crée un champ de bits initialisé à zéro. */
-static bitfield_t *_create_bit_field(size_t, size_t);
+static bitfield_t *_create_bit_field(size_t, bool, size_t);
 
 /* Crée une copie de champ de bits initialisé à zéro. */
 static bitfield_t *_create_bit_field_from(const bitfield_t *, size_t);
@@ -64,6 +65,7 @@ static bitfield_t *_dup_bit_field(const bitfield_t *, size_t);
 /******************************************************************************
 *                                                                             *
 *  Paramètres  : length = nom de bits du champ à représenter.                 *
+*                state  = état initial de chaque des bits.                    *
 *                extra  = espace mémoire supplémentaire à ajouter au final.   *
 *                                                                             *
 *  Description : Crée un champ de bits initialisé à zéro.                     *
@@ -74,7 +76,7 @@ static bitfield_t *_dup_bit_field(const bitfield_t *, size_t);
 *                                                                             *
 ******************************************************************************/
 
-static bitfield_t *_create_bit_field(size_t length, size_t extra)
+static bitfield_t *_create_bit_field(size_t length, bool state, size_t extra)
 {
     bitfield_t *result;                     /* Création à retourner        */
     size_t requested;                       /* Nombre de mots à allouer    */
@@ -88,10 +90,14 @@ static bitfield_t *_create_bit_field(size_t length, size_t extra)
     result = (bitfield_t *)malloc(base + extra);
 
     result->length = length;
+    result->requested = requested;
 
     result->tail = ((char *)result) + base;
 
-    memset(result->bits, 0, requested * sizeof(unsigned long));
+    if (state)
+        set_all_in_bit_field(result);
+    else
+        reset_all_in_bit_field(result);
 
     return result;
 
@@ -101,6 +107,7 @@ static bitfield_t *_create_bit_field(size_t length, size_t extra)
 /******************************************************************************
 *                                                                             *
 *  Paramètres  : length = nom de bits du champ à représenter.                 *
+*                state  = état initial de chaque des bits.                    *
 *                                                                             *
 *  Description : Crée un champ de bits initialisé à zéro.                     *
 *                                                                             *
@@ -110,9 +117,9 @@ static bitfield_t *_create_bit_field(size_t length, size_t extra)
 *                                                                             *
 ******************************************************************************/
 
-bitfield_t *create_bit_field(size_t length)
+bitfield_t *create_bit_field(size_t length, bool state)
 {
-    return _create_bit_field(length, 0);
+    return _create_bit_field(length, state, 0);
 
 }
 
@@ -132,7 +139,7 @@ bitfield_t *create_bit_field(size_t length)
 
 static bitfield_t *_create_bit_field_from(const bitfield_t *field, size_t extra)
 {
-    return _create_bit_field(field->length, extra);
+    return _create_bit_field(field->length, false, extra);
 
 }
 
@@ -177,6 +184,28 @@ void delete_bit_field(bitfield_t *field)
 
 /******************************************************************************
 *                                                                             *
+*  Paramètres  : dest = champ de bits à modifier.                             *
+*                src  = champ de bits à utiliser pour l'opération.            *
+*                                                                             *
+*  Description : Copie un champ de bits dans un autre.                        *
+*                                                                             *
+*  Retour      : -                                                            *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+void copy_bit_field(bitfield_t *dest, const bitfield_t *src)
+{
+    assert(dest->length == src->length);
+
+    memcpy(dest->bits, src->bits, dest->requested * sizeof(unsigned long));
+
+}
+
+
+/******************************************************************************
+*                                                                             *
 *  Paramètres  : field = champ de bits à dupliquer.                           *
 *                extra = espace mémoire supplémentaire à ajouter au final.    *
 *                                                                             *
@@ -193,7 +222,7 @@ static bitfield_t *_dup_bit_field(const bitfield_t *field, size_t extra)
     bitfield_t *result;                     /* Copie à retourner           */
     size_t requested;                       /* Nombre de mots à allouer    */
 
-    result = _create_bit_field(field->length, extra);
+    result = _create_bit_field(field->length, false, extra);
 
     requested = field->length / sizeof(unsigned long);
     if (field->length % sizeof(unsigned long) != 0) requested++;
@@ -227,6 +256,44 @@ bitfield_t *dup_bit_field(const bitfield_t *field)
 /******************************************************************************
 *                                                                             *
 *  Paramètres  : field = champ de bits à modifier.                            *
+*                                                                             *
+*  Description : Bascule à 0 un champ de bits dans son intégralité.           *
+*                                                                             *
+*  Retour      : -                                                            *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+void reset_all_in_bit_field(bitfield_t *field)
+{
+    memset(field->bits, 0u, field->requested * sizeof(unsigned long));
+
+}
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : field = champ de bits à modifier.                            *
+*                                                                             *
+*  Description : Bascule à 1 un champ de bits dans son intégralité.           *
+*                                                                             *
+*  Retour      : -                                                            *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+void set_all_in_bit_field(bitfield_t *field)
+{
+    memset(field->bits, ~0u, field->requested * sizeof(unsigned long));
+
+}
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : field = champ de bits à modifier.                            *
 *                first = indice du premier bit à traiter.                     *
 *                count = nombre de bits à marquer.                            *
 *                                                                             *
@@ -263,6 +330,56 @@ void set_in_bit_field(bitfield_t *field, size_t first, size_t count)
 
 /******************************************************************************
 *                                                                             *
+*  Paramètres  : dest = champ de bits à modifier.                             *
+*                src  = champ de bits à utiliser pour l'opération.            *
+*                                                                             *
+*  Description : Réalise une opération ET logique entre deux champs de bits.  *
+*                                                                             *
+*  Retour      : -                                                            *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+void and_bit_field(bitfield_t *dest, const bitfield_t *src)
+{
+    size_t i;                               /* Boucle de parcours          */
+
+    assert(dest->length == src->length);
+
+    for (i = 0; i < dest->requested; i++)
+        dest->bits[i] &= src->bits[i];
+
+}
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : dest = champ de bits à modifier.                             *
+*                src  = champ de bits à utiliser pour l'opération.            *
+*                                                                             *
+*  Description : Réalise une opération OU logique entre deux champs de bits.  *
+*                                                                             *
+*  Retour      : -                                                            *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+void or_bit_field(bitfield_t *dest, const bitfield_t *src)
+{
+    size_t i;                               /* Boucle de parcours          */
+
+    assert(dest->length == src->length);
+
+    for (i = 0; i < dest->requested; i++)
+        dest->bits[i] |= src->bits[i];
+
+}
+
+
+/******************************************************************************
+*                                                                             *
 *  Paramètres  : field = champ de bits à modifier.                            *
 *                first = indice du premier bit à traiter.                     *
 *                count = nombre de bits à marquer.                            *
@@ -303,6 +420,64 @@ bool test_in_bit_field(bitfield_t *field, size_t first, size_t count)
 }
 
 
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : a = premier champ de bits à comparer.                        *
+*                b = second champ de bits à comparer.                         *
+*                                                                             *
+*  Description : Indique si deux champs de bits sont identiques ou non.       *
+*                                                                             *
+*  Retour      : true si les champs de bits sont égaux ou false sinon.        *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+bool is_bit_field_equal_to(const bitfield_t *a, const bitfield_t *b)
+{
+    bool result;                            /* Résultat à retourner        */
+    size_t i;                               /* Boucle de parcours          */
+    size_t remaining;                       /* Nombre de bits restants     */
+
+    if (a->length != b->length)
+        return false;
+
+    result = true;
+
+    for (i = 0; i < (a->requested - 1) && result; i++)
+        result = (a->bits[i] == b->bits[i]);
+
+    if (result)
+    {
+        remaining = a->length % sizeof(unsigned long);
+
+        if (remaining == 0)
+            result = (a->bits[i] == b->bits[i]);
+
+        else
+        {
+            remaining = (1 << (remaining + 1)) - 1;
+
+            result = ((a->bits[i] & remaining) == (b->bits[i] & remaining));
+
+        }
+
+    }
+
+    return result;
+
+}
+
+
+
+
+unsigned long gfw(const bitfield_t *field)
+{
+    return field->bits[0];
+
+}
+
+
 
 /* ---------------------------------------------------------------------------------- */
 /*                           CHAMPS LIES À UNE ZONE MEMOIRE                           */
@@ -312,6 +487,7 @@ bool test_in_bit_field(bitfield_t *field, size_t first, size_t count)
 /******************************************************************************
 *                                                                             *
 *  Paramètres  : range = espace mémoire à couvrir.                            *
+*                state = état initial de chaque des bits.                     *
 *                                                                             *
 *  Description : Crée un champ de bits couvrant une zone mémoire.             *
 *                                                                             *
@@ -321,11 +497,11 @@ bool test_in_bit_field(bitfield_t *field, size_t first, size_t count)
 *                                                                             *
 ******************************************************************************/
 
-memfield_t *create_mem_field(const mrange_t *range)
+memfield_t *create_mem_field(const mrange_t *range, bool state)
 {
     bitfield_t *result;                     /* Création à retourner        */
 
-    result = _create_bit_field(get_mrange_length(range), sizeof(vmpa2t));
+    result = _create_bit_field(get_mrange_length(range), state, sizeof(vmpa2t));
 
     copy_vmpa((vmpa2t *)result->tail, get_mrange_addr(range));
 
diff --git a/src/common/bits.h b/src/common/bits.h
index 6eeb19c..0e8ef65 100644
--- a/src/common/bits.h
+++ b/src/common/bits.h
@@ -37,7 +37,7 @@ typedef struct _bitfield_t bitfield_t;
 
 
 /* Crée un champ de bits initialisé à zéro. */
-bitfield_t *create_bit_field(size_t);
+bitfield_t *create_bit_field(size_t, bool);
 
 /* Crée une copie de champ de bits initialisé à zéro. */
 bitfield_t *create_bit_field_from(const bitfield_t *);
@@ -45,15 +45,36 @@ bitfield_t *create_bit_field_from(const bitfield_t *);
 /* Supprime de la mémoire un champ de bits donné. */
 void delete_bit_field(bitfield_t *);
 
+/* Copie un champ de bits dans un autre. */
+void copy_bit_field(bitfield_t *, const bitfield_t *);
+
 /* Crée une copie d'un champ de bits classique. */
 bitfield_t *dup_bit_field(const bitfield_t *);
 
+/* Bascule à 0 un champ de bits dans son intégralité. */
+void reset_all_in_bit_field(bitfield_t *);
+
+/* Bascule à 1 un champ de bits dans son intégralité. */
+void set_all_in_bit_field(bitfield_t *);
+
 /* Bascule à 1 une partie d'un champ de bits. */
 void set_in_bit_field(bitfield_t *, size_t, size_t);
 
+/* Réalise une opération ET logique entre deux champs de bits. */
+void and_bit_field(bitfield_t *, const bitfield_t *);
+
+/* Réalise une opération OU logique entre deux champs de bits. */
+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);
 
+/* Indique si deux champs de bits sont identiques ou non. */
+bool is_bit_field_equal_to(const bitfield_t *, const bitfield_t *);
+
+
+
+unsigned long gfw(const bitfield_t *);
 
 
 /* ------------------------- CHAMPS LIES À UNE ZONE MEMOIRE ------------------------- */
@@ -64,7 +85,7 @@ typedef struct _bitfield_t memfield_t;
 
 
 /* Crée un champ de bits couvrant une zone mémoire. */
-memfield_t *create_mem_field(const mrange_t *);
+memfield_t *create_mem_field(const mrange_t *, bool);
 
 /* Crée une copie de champ de bits couvrant une zone mémoire. */
 memfield_t *create_mem_field_from(const memfield_t *);