Find free interleaving indexes for the ACISM backend using a dedicated search.

3 files changed, 318 insertions, 45 deletions

diff --git a/src/analysis/scan/patterns/backends/acism.c b/src/analysis/scan/patterns/backends/acism.c
index d517168..aa462a7 100644
--- a/src/analysis/scan/patterns/backends/acism.c
+++ b/src/analysis/scan/patterns/backends/acism.c
@@ -813,13 +813,16 @@ static void g_acism_backend_prepare_interleave_array(GAcismBackend *backend)
     size_t last_free_state;                 /* Dernier emplacement dispo.  */
     size_t full_size;                       /* Cartographie entière        */
     bitfield_t *global_usage;               /* Cartographie des usages     */
+#ifndef NDEBUG
+    size_t pops[3];                         /* Décomptes individuels       */
+    size_t bsum;                            /* Somme de tous les bits      */
+#endif
     bitfield_t *usage;                      /* Cartographie locale         */
     acism_trie_node_t *node;                /* Noeud en cours de traitement*/
+    size_t highest;                         /* Poids du bit le plus fort   */
     acism_trie_node_t *iter;                /* Boucle de parcours #2       */
+    size_t first_freedom_word;              /* Premier mot avec des dispos.*/
     size_t free_state;                      /* Emplacement libre trouvé    */
-    bool found;                             /* Bilan de recherche          */
-
-    size_t bsum;
 
     /* Préparation de la liste de noeuds à inscrire */
 
@@ -841,8 +844,16 @@ static void g_acism_backend_prepare_interleave_array(GAcismBackend *backend)
     full_size = last_free_state + 257;
     global_usage = create_bit_field(full_size, false);
 
+#ifndef NDEBUG
+
+    pops[0] = 0;
+    pops[1] = 0;
+    pops[2] = 0;
+
     bsum = 0;
 
+#endif
+
     usage = create_bit_field(257, false);
 
     for (i = 0; i < backend->nodes_used; i++)
@@ -855,26 +866,49 @@ static void g_acism_backend_prepare_interleave_array(GAcismBackend *backend)
 
         /* Préparation du masque du noeud */
 
+        truncate_bit_field(&usage, 257);
+
         reset_all_in_bit_field(usage);
 
         set_in_bit_field(usage, 0, 1);
 
+#ifndef NDEBUG
+        pops[0]++;
+#endif
+
+        highest = 0;
+
         for (iter = node->child; iter != NULL; iter = iter->sibling)
+        {
             set_in_bit_field(usage, iter->code, 1);
 
+#ifndef NDEBUG
+            pops[0]++;
+#endif
+
+            if (iter->code > highest)
+                highest = iter->code;
+
+        }
+
+#ifndef NDEBUG
+        pops[1] += popcount_for_bit_field(usage);
+#endif
+
         assert(popcount_for_bit_field(usage) == (node->children_count + 1));
 
+        truncate_bit_field(&usage, ++highest);
+
         /* Recherche d'une position idéale */
 
         if (i == 0)
+        {
+            first_freedom_word = 0;
             free_state = 0;
+        }
 
         else
-            for (free_state = 1; free_state < last_free_state; free_state++)
-            {
-                found = test_zeros_within_bit_field(global_usage, free_state, usage);
-                if (found) break;
-            }
+            free_state = find_interleaving_index_for_acism(global_usage, usage, &first_freedom_word);
 
         /* Suivi global */
 
@@ -882,8 +916,10 @@ static void g_acism_backend_prepare_interleave_array(GAcismBackend *backend)
 
         or_bit_field_at(global_usage, usage, free_state);
 
+#ifndef NDEBUG
         bsum += node->children_count + 1;
         assert(popcount_for_bit_field(global_usage) == bsum);
+#endif
 
         node->state_index = free_state;
 
@@ -898,6 +934,15 @@ static void g_acism_backend_prepare_interleave_array(GAcismBackend *backend)
 
     /* Sotie encadrée */
 
+#ifndef NDEBUG
+
+    pops[2] = popcount_for_bit_field(global_usage);
+
+    assert(pops[0] == pops[1]);
+    assert(pops[0] == pops[2]);
+
+#endif
+
     backend->bitmap_usage = global_usage;
 
     delete_bit_field(usage);
@@ -934,10 +979,10 @@ static void g_acism_backend_prepare_interleave_array(GAcismBackend *backend)
     bitfield_t *usage;                      /* Cartographie locale         */
     size_t rd_pos;                          /* Tête de lecture             */
     size_t wr_pos;                          /* Tête d'écriture             */
+    size_t first_freedom_word;              /* Premier mot avec des dispos.*/
     acism_trie_node_t *node;                /* Noeud à traiter             */
     acism_trie_node_t *iter;                /* Boucle de parcours          */
     size_t free_state;                      /* Emplacement libre trouvé    */
-    bool found;                             /* Bilan de recherche          */
 
     max_pos = backend->nodes_used;
 
@@ -970,6 +1015,8 @@ static void g_acism_backend_prepare_interleave_array(GAcismBackend *backend)
 
     rd_pos++;
 
+    first_freedom_word = 0;
+
     /* Suivi des liens déjà en place */
 
     while (rd_pos < max_pos)
@@ -994,11 +1041,7 @@ static void g_acism_backend_prepare_interleave_array(GAcismBackend *backend)
 
         /* Recherche d'une position idéale */
 
-        for (free_state = 1; free_state < last_free_state; free_state++)
-        {
-            found = test_zeros_within_bit_field(global_usage, free_state, usage);
-            if (found) break;
-        }
+        free_state = find_interleaving_index_for_acism(global_usage, usage, &first_freedom_word);
 
         /* Suivi global */
 
diff --git a/src/common/bits.c b/src/common/bits.c
index a037078..1ded7a2 100644
--- a/src/common/bits.c
+++ b/src/common/bits.c
@@ -38,7 +38,9 @@
 struct _bitfield_t
 {
     size_t length;                          /* Nombre de bits représentés  */
-    size_t requested;                       /* Nombre de mots alloués      */
+
+    size_t allocated_words;                 /* Nombre de mots alloués      */
+    size_t used_words;                      /* Nombre de mots utilisés     */
 
     bool default_state;                     /* Etat d'initialisation       */
 
@@ -73,18 +75,20 @@ static bool test_state_within_bit_field(const bitfield_t *, size_t, const bitfie
 static bitfield_t *_create_bit_field(size_t length)
 {
     bitfield_t *result;                     /* Création à retourner        */
-    size_t requested;                       /* Nombre de mots à allouer    */
+    size_t needed;                          /* Nombre de mots à allouer    */
     size_t base;                            /* Allocation de base en octets*/
 
-    requested = length / (sizeof(unsigned long) * 8);
-    if (length % (sizeof(unsigned long) * 8) != 0) requested++;
+    needed = length / (sizeof(unsigned long) * 8);
+    if (length % (sizeof(unsigned long) * 8) != 0) needed++;
 
-    base = sizeof(bitfield_t) + requested * sizeof(unsigned long);
+    base = sizeof(bitfield_t) + needed * sizeof(unsigned long);
 
     result = (bitfield_t *)malloc(base);
 
     result->length = length;
-    result->requested = requested;
+
+    result->allocated_words = needed;
+    result->used_words = needed;
 
     return result;
 
@@ -140,7 +144,7 @@ bitfield_t *dup_bit_field(const bitfield_t *field)
 
     result = _create_bit_field(field->length);
 
-    memcpy(result->bits, field->bits, result->requested * sizeof(unsigned long));
+    memcpy(result->bits, field->bits, result->used_words * sizeof(unsigned long));
 
     return result;
 
@@ -183,7 +187,45 @@ 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));
+    memcpy(dest->bits, src->bits, dest->used_words * sizeof(unsigned long));
+
+}
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : field  = champ de bits à modifier. [OUT]                     *
+*                length = nouveau nombre de bits du champ à représenter.      *
+*                                                                             *
+*  Description : Réduit ou étend la taille d'un champ en évitant l'allocation.*
+*                                                                             *
+*  Retour      : -                                                            *
+*                                                                             *
+*  Remarques   : Les éventuels bits supplémentaires ou disparus ne sont pas   *
+*                (ré)initialisés.                                             *
+*                                                                             *
+******************************************************************************/
+
+void truncate_bit_field(bitfield_t **field, size_t length)
+{
+    bitfield_t *_field;                     /* Commodité d'accès           */
+    size_t needed;                          /* Nombre de mots à allouer    */
+
+    _field = *field;
+
+    needed = length / (sizeof(unsigned long) * 8);
+    if (length % (sizeof(unsigned long) * 8) != 0) needed++;
+
+    if (needed <= _field->allocated_words)
+    {
+        _field->length = length;
+
+        _field->used_words = needed;
+
+    }
+
+    else
+        resize_bit_field(field, length);
 
 }
 
@@ -204,7 +246,7 @@ void copy_bit_field(bitfield_t *dest, const bitfield_t *src)
 void resize_bit_field(bitfield_t **field, size_t length)
 {
     bitfield_t *_field;                     /* Commodité d'accès           */
-    size_t requested;                       /* Nombre de mots à allouer    */
+    size_t needed;                          /* Nombre de mots à allouer    */
     size_t base;                            /* Allocation de base en octets*/
     size_t remaining;                       /* Nombre de derniers bits     */
     size_t last;                            /* Dernier mot utilisé         */
@@ -217,18 +259,18 @@ void resize_bit_field(bitfield_t **field, size_t length)
     {
         /* Redimensionnement */
 
-        requested = length / (sizeof(unsigned long) * 8);
-        if (length % (sizeof(unsigned long) * 8) != 0) requested++;
+        needed = length / (sizeof(unsigned long) * 8);
+        if (length % (sizeof(unsigned long) * 8) != 0) needed++;
 
-        base = sizeof(bitfield_t) + requested * sizeof(unsigned long);
-
-        *field = realloc(_field, base);
-        _field = *field;
+        base = sizeof(bitfield_t) + needed * sizeof(unsigned long);
 
         /* Initialisation, si nécessaire */
 
         if (_field->length < length)
         {
+            *field = realloc(_field, base);
+            _field = *field;
+
             last = _field->length / (sizeof(unsigned long) * 8);
             remaining = _field->length % (sizeof(unsigned long) * 8);
 
@@ -245,7 +287,7 @@ void resize_bit_field(bitfield_t **field, size_t length)
 
             }
 
-            for (i = last; i < requested; i++)
+            for (i = last; i < needed; i++)
             {
                 if (_field->default_state)
                     _field->bits[i] = ~0ul;
@@ -258,7 +300,9 @@ void resize_bit_field(bitfield_t **field, size_t length)
         /* Actualisation des tailles */
 
         _field->length = length;
-        _field->requested = requested;
+
+        _field->allocated_words = needed;
+        _field->used_words = needed;
 
     }
 
@@ -326,12 +370,12 @@ int compare_bit_fields(const bitfield_t *a, const bitfield_t *b)
         else
             final = (1 << final) - 1;
 
-        for (i = 0; i < a->requested && result == 0; i++)
+        for (i = 0; i < a->used_words && result == 0; i++)
         {
             val_a = a->bits[i];
             val_b = b->bits[i];
 
-            if ((i + 1) == a->requested)
+            if ((i + 1) == a->used_words)
             {
                 val_a &= final;
                 val_b &= final;
@@ -366,7 +410,7 @@ int compare_bit_fields(const bitfield_t *a, const bitfield_t *b)
 
 void reset_all_in_bit_field(bitfield_t *field)
 {
-    memset(field->bits, 0u, field->requested * sizeof(unsigned long));
+    memset(field->bits, 0u, field->used_words * sizeof(unsigned long));
 
 }
 
@@ -385,7 +429,7 @@ void reset_all_in_bit_field(bitfield_t *field)
 
 void set_all_in_bit_field(bitfield_t *field)
 {
-    memset(field->bits, ~0u, field->requested * sizeof(unsigned long));
+    memset(field->bits, ~0u, field->used_words * sizeof(unsigned long));
 
 }
 
@@ -483,7 +527,7 @@ void and_bit_field(bitfield_t *dest, const bitfield_t *src)
 
     assert(dest->length == src->length);
 
-    for (i = 0; i < dest->requested; i++)
+    for (i = 0; i < dest->used_words; i++)
         dest->bits[i] &= src->bits[i];
 
 }
@@ -508,7 +552,7 @@ void or_bit_field(bitfield_t *dest, const bitfield_t *src)
 
     assert(dest->length == src->length);
 
-    for (i = 0; i < dest->requested; i++)
+    for (i = 0; i < dest->used_words; i++)
         dest->bits[i] |= src->bits[i];
 
 }
@@ -545,14 +589,13 @@ void or_bit_field_at(bitfield_t *dest, const bitfield_t *src, size_t first)
     remaining = (first + src->length) % (sizeof(unsigned long) * 8);
 
     if ((first + src->length) % (sizeof(unsigned long) * 8) > 0)
-        last_iter = src->requested;
+        last_iter = src->used_words;
     else
-        last_iter = src->requested - 1;
-
+        last_iter = src->used_words - 1;
 
     for (i = 0; i <= last_iter; i++)
     {
-        if (i < src->requested)
+        if (i < src->used_words)
             word = src->bits[i] << offset;
         else
             word = 0;
@@ -736,7 +779,7 @@ static bool test_state_within_bit_field(const bitfield_t *field, size_t first, c
     else
         finalcut = (1lu << remaining) - 1;
 
-    for (i = 0; i < mask->requested && result; i++)
+    for (i = 0; i < mask->used_words && result; i++)
     {
         windex = start + i;
 
@@ -746,7 +789,7 @@ static bool test_state_within_bit_field(const bitfield_t *field, size_t first, c
         else
         {
             word = field->bits[windex] >> offset;
-            if ((windex + 1) < field->requested)
+            if ((windex + 1) < field->used_words)
                 word |= field->bits[windex + 1] << (sizeof(unsigned long) * 8 - offset);
         }
 
@@ -756,7 +799,7 @@ static bool test_state_within_bit_field(const bitfield_t *field, size_t first, c
 
         test &= bitmask;
 
-        if ((i + 1) == mask->requested)
+        if ((i + 1) == mask->used_words)
         {
             bitmask &= finalcut;
             test &= finalcut;
@@ -824,6 +867,128 @@ bool test_ones_within_bit_field(const bitfield_t *field, size_t first, const bit
 /******************************************************************************
 *                                                                             *
 *  Paramètres  : field = champ de bits à consulter.                           *
+*                extra = champ de bits à placer.                              *
+*                                                                             *
+*  Description : Recherche l'indice idéal pour placer un champ dans un autre. *
+*                                                                             *
+*  Retour      : Position du premier bit à insérer.                           *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+size_t find_interleaving_index_for_acism(const bitfield_t *field, const bitfield_t *extra, size_t *first)
+{
+    size_t result;                          /* Dimension à retourner       */
+    size_t i;                               /* Boucle de parcours #1       */
+    const unsigned long *bits;              /* Itérateurs sur les bits     */
+    size_t init_k;                          /* Point de départ optimal     */
+    size_t k;                               /* Boucle de parcours #2       */
+    unsigned long mask;                     /* Valeur à comparer           */
+    size_t j;                               /* Boucle de parcours #3       */
+
+    /**
+     * La procédure s'appuie sur deux particularité du contexte d'exécution (scan ACISM) :
+     *    - il y a toujours au moins 257 bits (taille maximale du champs "extra") libres
+     *      en fin de champs "field" ;
+     *    - le premier bit du champ "extra" est toujours fixé à 1.
+     */
+
+    result = 0;
+
+    for (i = *first; i < field->used_words; i++)
+    {
+        /* S'il ne reste plus aucune place */
+        if (field->bits[i] != ~0lu)
+            break;
+    }
+
+    *first = i;
+
+    bits = field->bits + i;
+
+    for (; i < field->used_words; i++, bits++)
+    {
+        /* S'il ne reste plus aucune place */
+        if (*bits == ~0lu)
+            continue;
+
+        init_k = __builtin_ffsl(~*bits) - 1;
+
+        for (k = init_k; k < __WORDSIZE; k++)
+        {
+            /**
+             * Le champs de bits à placer ne comporte pas forcément au moins
+             * 32/64 bits, mais les bits non comptabilisés du mot sont toujours
+             * initialisés à zéro.
+             *
+             * Aucune prise en compte particulière d'un champ de petite taille
+             * n'est donc à réaliser ici.
+             */
+
+            mask = (extra->bits[0] << k);
+
+            /* Si tous les bits nécessaires au début sont libres... */
+            if ((*bits & mask) == 0)
+            {
+                for (j = 1; j < extra->used_words; j++)
+                {
+                    if (k == 0)
+                        mask = extra->bits[j];
+
+                    else
+                    {
+                        /* Portion du mot courant */
+                        mask = (extra->bits[j] << k);
+
+                        /* Relicat du mot précédent */
+                        mask |= (extra->bits[j - 1] >> (__WORDSIZE - k));
+
+                    }
+
+                    if (mask == 0)
+                        continue;
+
+                    if ((bits[j] & mask) != 0)
+                        break;
+
+                }
+
+                if (j == extra->used_words)
+                {
+                    /* Eventuelle dernière bribe débordant sur un dernier mot ? */
+                    if (k > 0)
+                    {
+                        mask = (extra->bits[j - 1] >> (__WORDSIZE - k));
+
+                        if ((bits[j] & mask) != 0)
+                            continue;
+
+                    }
+
+                    result = i * __WORDSIZE + k;
+                    goto found;
+
+                }
+
+            }
+
+        }
+
+    }
+
+ found:
+
+    assert(result > 0);
+
+    return result;
+
+}
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : field = champ de bits à consulter.                           *
 *                                                                             *
 *  Description : Détermine le nombre de bits à 1 dans un champ.               *
 *                                                                             *
@@ -844,7 +1009,7 @@ size_t popcount_for_bit_field(const bitfield_t *field)
 
     remaining = field->length;
 
-    for (i = 0; i < field->requested; i++)
+    for (i = 0; i < field->used_words; i++)
     {
         value = field->bits[i];
 
@@ -866,3 +1031,55 @@ size_t popcount_for_bit_field(const bitfield_t *field)
     return result;
 
 }
+
+
+#if 0
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : field = champ de bits à consulter.                           *
+*                                                                             *
+*  Description : Imprime sur la sortie standard la valeur représentée.        *
+*                                                                             *
+*  Retour      : -                                                            *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+void output_bit_field(const bitfield_t *field)
+{
+    size_t i;                               /* Boucle de parcours #1       */
+    unsigned long value;                    /* Valeur masquée à traiter    */
+    size_t k;                               /* Boucle de parcours #2       */
+
+    printf("[len=%zu] \n", field->length);
+
+#define MAX_BITS (sizeof(unsigned long) * 8)
+
+    for (i = 0; i < field->used_words; i++)
+    {
+        value = field->bits[i];
+
+        if (i > 0)
+            printf("| ");
+
+        for (k = 0; k < MAX_BITS; k++)
+        {
+            if ((i * MAX_BITS + k) >= field->length)
+                break;
+
+            printf("%c", value & (1lu << k) ? '1' : '.');
+
+            if ((k + 1) % 8 == 0)
+                printf(" ");
+
+        }
+
+    }
+
+    printf("\n");
+
+}
+
+#endif
diff --git a/src/common/bits.h b/src/common/bits.h
index 58fa0fe..8f67d3d 100644
--- a/src/common/bits.h
+++ b/src/common/bits.h
@@ -45,6 +45,9 @@ void delete_bit_field(bitfield_t *);
 /* Copie un champ de bits dans un autre. */
 void copy_bit_field(bitfield_t *, const bitfield_t *);
 
+/* Réduit ou étend la taille d'un champ en évitant l'allocation. */
+void truncate_bit_field(bitfield_t **, size_t);
+
 /* Redimensionne un champ de bits. */
 void resize_bit_field(bitfield_t **, size_t);
 
@@ -90,9 +93,19 @@ bool test_zeros_within_bit_field(const bitfield_t *, size_t, const bitfield_t *)
 /* Teste l'état à 1 de bits selon un masque de bits. */
 bool test_ones_within_bit_field(const bitfield_t *, size_t, const bitfield_t *);
 
+/* Recherche l'indice idéal pour placer un champ dans un autre. */
+size_t find_interleaving_index_for_acism(const bitfield_t *, const bitfield_t *, size_t *);
+
 /* Détermine le nombre de bits à 1 dans un champ. */
 size_t popcount_for_bit_field(const bitfield_t *);
 
+#if 0
+
+/* Imprime sur la sortie standard la valeur représentée. */
+void output_bit_field(const bitfield_t *);
+
+#endif
+
 
 
 #endif  /* _COMMON_BITS_H */