From 24096140aaa73db9e982db4437bc42a013812658 Mon Sep 17 00:00:00 2001
From: Cyrille Bagard <nocbos@gmail.com>
Date: Fri, 31 Mar 2017 19:25:54 +0200
Subject: Handled many special cases of binary portion inclusion to get a clean
 tree.

---
 ChangeLog                 |   6 ++
 src/glibext/gbinportion.c | 212 +++++++++++++++++++++++++++++++++++-----------
 src/glibext/gbinportion.h |   9 +-
 3 files changed, 176 insertions(+), 51 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index c1fd565..2080976 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,9 @@
+17-03-31  Cyrille Bagard <nocbos@gmail.com>
+
+	* src/glibext/gbinportion.c:
+	* src/glibext/gbinportion.h:
+	Handle many special cases of binary portion inclusion to get a clean tree.
+
 17-03-30  Cyrille Bagard <nocbos@gmail.com>
 
 	* src/analysis/disass/area.c:
diff --git a/src/glibext/gbinportion.c b/src/glibext/gbinportion.c
index 542936a..caaec43 100644
--- a/src/glibext/gbinportion.c
+++ b/src/glibext/gbinportion.c
@@ -56,6 +56,7 @@ struct _GBinPortion
     size_t lcount;                          /* Quantité de ces lignes      */
 
     mrange_t range;                         /* Emplacement dans le code    */
+    bool continued;                         /* Suite d'une découpe ?       */
 
     PortionAccessRights rights;             /* Droits d'accès              */
 
@@ -173,6 +174,8 @@ static void g_binary_portion_init(GBinPortion *portion)
     portion->text = NULL;
     portion->lcount = 0;
 
+    portion->continued = false;
+
 }
 
 
@@ -310,30 +313,6 @@ int g_binary_portion_compare(const GBinPortion **a, const GBinPortion **b)
 
 /******************************************************************************
 *                                                                             *
-*  Paramètres  : a = premières informations à consulter.                      *
-*                b = secondes informations à consulter.                       *
-*                                                                             *
-*  Description : Détermine si une portion est comprise dans une autre.        *
-*                                                                             *
-*  Retour      : Bilan : -1 (a < b), 0 (b € a) ou 1 (a > b).                  *
-*                                                                             *
-*  Remarques   : -                                                            *
-*                                                                             *
-******************************************************************************/
-
-int g_binary_portion_is_included(const GBinPortion **a, const GBinPortion **b)
-{
-    int result;                             /* Bilan à retourner           */
-
-    result = mrange_includes_mrange(&(*b)->range, &(*a)->range);
-
-    return result;
-
-}
-
-
-/******************************************************************************
-*                                                                             *
 *  Paramètres  : portion = description de partie à mettre à jour.             *
 *                desc    = nom à donner à la partie.                          *
 *                                                                             *
@@ -372,6 +351,9 @@ void g_binary_portion_set_desc(GBinPortion *portion, const char *desc)
     {
         portion->desc = strdup(desc);
 
+        if (portion->continued)
+            portion->desc = stradd(portion->desc, _(" (continued)"));
+
         /* Constitution du rendu */
 
         portion->text = calloc(4, sizeof(char *));
@@ -451,6 +433,46 @@ const mrange_t *g_binary_portion_get_range(const GBinPortion *portion)
 
 /******************************************************************************
 *                                                                             *
+*  Paramètres  : portion = portion dont la définition est à metre à jour.     *
+*                                                                             *
+*  Description : Définit la nature de la portion en terme d'originalité.      *
+*                                                                             *
+*  Retour      : -                                                            *
+*                                                                             *
+*  Remarques   : L'action ne modifie aucunement la description courante.      *
+*                C'est le changement de description qui s'appuie sur la       *
+*                notée ici.                                                   *
+*                                                                             *
+******************************************************************************/
+
+void g_binary_portion_mark_as_continued(GBinPortion *portion, bool continued)
+{
+    portion->continued = continued;
+
+}
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : portion = portion dont la définition est à consulter.        *
+*                                                                             *
+*  Description : Indique la nature de la portion en terme d'originalité.      *
+*                                                                             *
+*  Retour      : true si la portion est la suite d'une portion découpée.      *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+bool g_binary_portion_is_continuation(const GBinPortion *portion)
+{
+    return portion->continued;
+
+}
+
+
+/******************************************************************************
+*                                                                             *
 *  Paramètres  : portion = description de partie à mettre à jour.             *
 *                rights  = droits d'accès de la partie.                       *
 *                                                                             *
@@ -678,29 +700,51 @@ void g_binary_portion_include(GBinPortion *portion, GBinPortion *sub)
 {
     bool found;                             /* Zone d'accueil trouvée ?    */
     size_t best;                            /* Meilleur point d'insertion  */
-    size_t i;                               /* Boucle de parcours          */
-    GBinPortion *tmp;                       /* Sauvegarde temporaire       */
+    size_t missed;                          /* Indice de zone à déplacer   */
+    const mrange_t *brange;                 /* Raccourci de confort d'usage*/
+    vmpa2t end;                             /* Fin de la zone commune      */
+    phys_t overlapping;                     /* Taille de la zone commune   */
+    bool continued;                         /* Suite d'une découpe ?       */
+    GBinPortion *left_part;                 /* Partie intégrable           */
+    GBinPortion *right_part;                /* Partie restante             */
+
+    int g_binary_portion_is_included(const GBinPortion **a, const GBinPortion **b)
+    {
+        int result;                         /* Bilan à retourner           */
+
+        result = mrange_includes_mrange(&(*b)->range, &(*a)->range);
+
+        return result;
+
+    }
 
     found = bsearch_index(&sub, portion->subs, portion->count, sizeof(GBinPortion *),
                           (__compar_fn_t)g_binary_portion_is_included, &best);
 
     if (!found)
-        portion->subs = qinsert(portion->subs, &portion->count, sizeof(GBinPortion *),
-                                (__compar_fn_t)g_binary_portion_compare, &sub);
-
-    else
     {
         /**
-         * On prend ici en compte le genre de situations suivantes :
+         * On se prépare à réaliser une insertion au niveau courant. Mais des
+         * portions précédentes sont peut-être à déplacer dans la nouvelle zone :
+         *
+         *   EXIDX          0x001178 0x00009178 0x00009178 0x00008 0x00008 R   0x4
+         *   PHDR           0x000034 0x00008034 0x00008034 0x00120 0x00120 R E 0x4
+         *   INTERP         0x000154 0x00008154 0x00008154 0x00019 0x00019 R   0x1
+         *   LOAD           0x000000 0x00008000 0x00008000 0x01184 0x01184 R E 0x8000
+         *
+         * On refait donc une passe sur toutes les sous-portions du niveau.
+         *
+         * Cette approche a le mérite de traiter également et naturellement les
+         * sections définies dans le désordre :
          *
          *   [21] .bss                NOBITS          00088240 07823c 0018c8 00  WA  0   0  8
          *   [22] __libc_freeres_ptrs NOBITS          00089b08 07823c 000018 00  WA  0   0  4
          *   [23] .comment            PROGBITS        00000000 07823c 000022 01  MS  0   0  1
          *
-         * Pendant le désassemblage, la procédure n'aime pas trop les intersections
-         * de zones mémoire.
+         * Quant aux cas de figure où les portions sont identiques, l'ordre d'appel
+         * induit l'ordre d'inclusion.
          *
-         * Par contre, on évite quand même les cas de figure où les portions sont identiques :
+         * Cela concerne par exemple les zones de données :
          *
          *   En-têtes de section:
          *     [Nr] Nom               Type            Adr      Décala.Taille ES Fan LN Inf Al
@@ -712,36 +756,108 @@ void g_binary_portion_include(GBinPortion *portion, GBinPortion *sub)
          *     ...
          *     LOAD           0x000098 0x00010098 0x00010098 0x0000c 0x0000c RW  0x8000
          *
-         * Ici l'ordre original doit être conservé !
          */
 
-        if (mrange_includes_mrange(&sub->range, &portion->subs[best]->range) == 0
-            && cmp_mrange(&sub->range, &portion->subs[best]->range) != 0)
+        int g_binary_portion_track_missed_inclusion(const GBinPortion **a, const GBinPortion **b)
+        {
+            int result;                     /* Bilan à retourner           */
+
+            result = mrange_includes_mrange(&(*a)->range, &(*b)->range);
+
+            return result;
+
+        }
+
+        do
         {
-            tmp = portion->subs[best];
+            found = bsearch_index(&sub, portion->subs, portion->count, sizeof(GBinPortion *),
+                                  (__compar_fn_t)g_binary_portion_track_missed_inclusion, &missed);
 
-            for (i = portion->count; i > 0; i--)
+            if (found)
             {
-                tmp = portion->subs[i - 1];
+                g_binary_portion_include(sub, portion->subs[missed]);
 
-                if (mrange_includes_mrange(&sub->range, &tmp->range) == 0)
-                {
-                    portion->subs = _qdelete(portion->subs, &portion->count, sizeof(GBinPortion *), i - 1);
-                    g_binary_portion_include(sub, tmp);
-                }
+                portion->subs = _qdelete(portion->subs, &portion->count, sizeof(GBinPortion *), missed);
 
             }
 
-            portion->subs = qinsert(portion->subs, &portion->count, sizeof(GBinPortion *),
-                                    (__compar_fn_t)g_binary_portion_compare, &sub);
+        }
+        while (found);
+
+        /**
+         * Il peut arriver que certaines portions débordent de leur zone d'inclusion :
+         *
+         *   [24] .bss              NOBITS          00012088 002084 000044 00  WA  0   0  8
+         *   [25] .ARM.attributes   ARM_ATTRIBUTES  00000000 002084 000037 00      0   0  1
+         *   [26] .shstrtab         STRTAB          00000000 0020bb 0000ed 00      0   0  1
+         *
+         * Afin de respecter une certaine cohérence dans l'arbre des portions, on choisit
+         * de découper la portion qui déborde.
+         */
+
+        int g_binary_portion_track_partial_inclusion(const GBinPortion **a, const GBinPortion **b)
+        {
+            int result;                     /* Bilan à retourner           */
+
+            result = cmp_mrange_with_vmpa(&(*b)->range, get_mrange_addr(&(*a)->range));
+
+            return result;
+
+        }
+
+        found = bsearch_index(&sub, portion->subs, portion->count, sizeof(GBinPortion *),
+                              (__compar_fn_t)g_binary_portion_track_partial_inclusion, &best);
+
+        if (found)
+        {
+            brange = &portion->subs[best]->range;
+
+            compute_mrange_end_addr(brange, &end);
+            overlapping = compute_vmpa_diff(get_mrange_addr(&sub->range), &end);
+
+            continued = g_binary_portion_is_continuation(sub);
+
+            /* Partie contenue */
+
+            left_part = g_binary_portion_new(sub->code, get_mrange_addr(&sub->range), overlapping);
+
+            g_binary_portion_set_desc(left_part, sub->desc);
+            g_binary_portion_mark_as_continued(left_part, continued);
+            g_binary_portion_set_rights(left_part, sub->rights);
+
+            /* Partie qui déborde... */
+
+            right_part = g_binary_portion_new(sub->code, &end, get_mrange_length(&sub->range) - overlapping);
+
+            if (!continued)
+                g_binary_portion_mark_as_continued(right_part, true);
+
+            g_binary_portion_set_desc(right_part, sub->desc);
+
+            if (continued)
+                g_binary_portion_mark_as_continued(right_part, true);
+
+            g_binary_portion_set_rights(right_part, sub->rights);
+
+            /* Inclusions des parties */
+
+            g_binary_portion_include(portion, left_part);
+            g_binary_portion_include(portion, right_part);
+
+            g_object_unref(G_OBJECT(sub));
 
         }
 
         else
-            g_binary_portion_include(portion->subs[best], sub);
+            portion->subs = qinsert(portion->subs, &portion->count, sizeof(GBinPortion *),
+                                    (__compar_fn_t)g_binary_portion_compare, &sub);
 
     }
 
+    /* Poursuite de l'inclusion dans la sous-portion adaptée... */
+    else
+        g_binary_portion_include(portion->subs[best], sub);
+
 }
 
 
diff --git a/src/glibext/gbinportion.h b/src/glibext/gbinportion.h
index a1ec105..27e7dc5 100644
--- a/src/glibext/gbinportion.h
+++ b/src/glibext/gbinportion.h
@@ -84,9 +84,6 @@ GBinPortion *g_binary_portion_new(const char *, const vmpa2t *, phys_t);
 /* Etablit la comparaison ascendante entre deux portions. */
 int g_binary_portion_compare(const GBinPortion **, const GBinPortion **);
 
-/* Détermine si une portion est comprise dans une autre. */
-int g_binary_portion_is_included(const GBinPortion **, const GBinPortion **);
-
 /* Attribue une description humaine à une partie de code. */
 void g_binary_portion_set_desc(GBinPortion *, const char *);
 
@@ -96,6 +93,12 @@ const char *g_binary_portion_get_desc(const GBinPortion *);
 /* Fournit l'emplacement d'une partie de code binaire. */
 const mrange_t *g_binary_portion_get_range(const GBinPortion *);
 
+/* Définit la nature de la portion en terme d'originalité. */
+void g_binary_portion_mark_as_continued(GBinPortion *, bool);
+
+/* Indique la nature de la portion en terme d'originalité. */
+bool g_binary_portion_is_continuation(const GBinPortion *);
+
 /* Définit les droits associés à une partie de code. */
 void g_binary_portion_set_rights(GBinPortion *, PortionAccessRights);
 
-- 
cgit v0.11.2-87-g4458