summaryrefslogtreecommitdiff
path: root/src/analysis/scan/patterns
diff options
context:
space:
mode:
authorCyrille Bagard <nocbos@gmail.com>2024-02-06 01:25:11 (GMT)
committerCyrille Bagard <nocbos@gmail.com>2024-02-06 01:25:11 (GMT)
commitcb97f097d9e7b9bc338fdec8689b45ab40c905c4 (patch)
tree9b77950e7a7fc28cb7e3cfcf36cbc270bcd8aeba /src/analysis/scan/patterns
parent5056bed107331457e703ae69d61b15434940acd1 (diff)
Find free interleaving indexes for the ACISM backend using a dedicated search.
Diffstat (limited to 'src/analysis/scan/patterns')
-rw-r--r--src/analysis/scan/patterns/backends/acism.c71
1 files changed, 57 insertions, 14 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 */