summaryrefslogtreecommitdiff
path: root/src/common
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/common
parent5056bed107331457e703ae69d61b15434940acd1 (diff)
Find free interleaving indexes for the ACISM backend using a dedicated search.
Diffstat (limited to 'src/common')
-rw-r--r--src/common/bits.c279
-rw-r--r--src/common/bits.h13
2 files changed, 261 insertions, 31 deletions
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 */