diff options
| -rw-r--r-- | src/analysis/scan/patterns/backends/acism.c | 71 | ||||
| -rw-r--r-- | src/common/bits.c | 279 | ||||
| -rw-r--r-- | src/common/bits.h | 13 |
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 */ |