summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/analysis/scan/patterns/backends/acism.c71
-rw-r--r--src/common/bits.c279
-rw-r--r--src/common/bits.h13
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 */
generated by cgit v0.11.2-87-g4458 at 2024-12-27 12:39:47 (GMT)