/* Chrysalide - Outil d'analyse de fichiers binaires
* bits.c - manipulation d'un champ de bits quelconque
*
* Copyright (C) 2015-2019 Cyrille Bagard
*
* This file is part of Chrysalide.
*
* Chrysalide is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 3 of the License, or
* (at your option) any later version.
*
* Chrysalide is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with Chrysalide. If not, see <http://www.gnu.org/licenses/>.
*/
#include "bits.h"
#include <assert.h>
#include <glib.h>
#include <malloc.h>
#include <string.h>
#include "asm.h"
#include "leb128.h"
/* Champ de bits simple */
struct _bitfield_t
{
size_t length; /* Nombre de bits représenté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 */
unsigned long bits[0]; /* Mémoire d'accès associée */
};
/* Taille des mots intégrés */
#define BF_WORD_BIT_SIZE (sizeof(unsigned long) * 8)
#define BF_WORD_BYTE_SIZE sizeof(unsigned long)
/* Crée un champ de bits initialisé à zéro. */
static bitfield_t *_create_bit_field(size_t);
/* Détermine si un ensemble de bits est homogène dans un champ. */
static bool test_state_in_bit_field(const bitfield_t *, size_t, size_t, bool);
/* Teste l'état de bits selon un masque de bits. */
static bool test_state_within_bit_field(const bitfield_t *, size_t, const bitfield_t *, bool);
/******************************************************************************
* *
* Paramètres : length = nom de bits du champ à représenter. *
* *
* Description : Crée un champ de bits initialisé à zéro. *
* *
* Retour : Champ de bits mis en place. *
* *
* Remarques : - *
* *
******************************************************************************/
static bitfield_t *_create_bit_field(size_t length)
{
bitfield_t *result; /* Création à retourner */
size_t needed; /* Nombre de mots à allouer */
size_t base; /* Allocation de base en octets*/
needed = length / BF_WORD_BIT_SIZE;
if (length % BF_WORD_BIT_SIZE != 0) needed++;
base = sizeof(bitfield_t) + needed * BF_WORD_BYTE_SIZE;
result = malloc(base);
result->length = length;
result->allocated_words = needed;
result->used_words = needed;
return result;
}
/******************************************************************************
* *
* Paramètres : length = nombre de bits du champ à représenter. *
* state = état initial de chaque des bits. *
* *
* Description : Crée un champ de bits initialisé. *
* *
* Retour : Champ de bits mis en place. *
* *
* Remarques : - *
* *
******************************************************************************/
bitfield_t *create_bit_field(size_t length, bool state)
{
bitfield_t *result; /* Création à retourner */
result = _create_bit_field(length);
result->default_state = state;
if (state)
set_all_in_bit_field(result);
else
reset_all_in_bit_field(result);
return result;
}
/******************************************************************************
* *
* Paramètres : field = champ de bits à dupliquer. *
* *
* Description : Crée une copie d'un champ de bits classique. *
* *
* Retour : Champ de bits mis en place. *
* *
* Remarques : - *
* *
******************************************************************************/
bitfield_t *dup_bit_field(const bitfield_t *field)
{
bitfield_t *result; /* Copie à retourner */
result = _create_bit_field(field->length);
memcpy(result->bits, field->bits, result->used_words * BF_WORD_BYTE_SIZE);
return result;
}
/******************************************************************************
* *
* Paramètres : field = champ de bits à effacer. *
* *
* Description : Supprime de la mémoire un champ de bits donné. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
void delete_bit_field(bitfield_t *field)
{
free(field);
}
/******************************************************************************
* *
* Paramètres : dest = champ de bits à modifier. *
* src = champ de bits à utiliser pour l'opération. *
* *
* Description : Copie un champ de bits dans un autre. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
void copy_bit_field(bitfield_t *dest, const bitfield_t *src)
{
assert(dest->length == src->length);
memcpy(dest->bits, src->bits, dest->used_words * BF_WORD_BYTE_SIZE);
}
/******************************************************************************
* *
* 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 / BF_WORD_BIT_SIZE;
if (length % BF_WORD_BIT_SIZE != 0) needed++;
if (needed <= _field->allocated_words)
{
_field->length = length;
_field->used_words = needed;
}
else
resize_bit_field(field, length);
}
/******************************************************************************
* *
* Paramètres : field = champ de bits à modifier. [OUT] *
* length = nouveau nombre de bits du champ à représenter. *
* *
* Description : Redimensionne un champ de bits. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
void resize_bit_field(bitfield_t **field, size_t length)
{
bitfield_t *_field; /* Commodité d'accès */
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é */
unsigned long mask; /* Masque d'initialisation */
size_t i; /* Boucle de parcours */
_field = *field;
if (_field->length != length)
{
/* Redimensionnement */
needed = length / BF_WORD_BIT_SIZE;
if (length % BF_WORD_BIT_SIZE != 0) needed++;
base = sizeof(bitfield_t) + needed * BF_WORD_BYTE_SIZE;
/* Initialisation, si nécessaire */
if (_field->length < length)
{
*field = realloc(_field, base);
_field = *field;
last = _field->length / BF_WORD_BIT_SIZE;
remaining = _field->length % BF_WORD_BIT_SIZE;
if (remaining != 0)
{
mask = (1ul << remaining) - 1;
if (_field->default_state)
_field->bits[last] |= ~mask;
else
_field->bits[last] &= mask;
last++;
}
for (i = last; i < needed; i++)
{
if (_field->default_state)
_field->bits[i] = ~0ul;
else
_field->bits[i] = 0ul;
}
}
/* Actualisation des tailles */
_field->length = length;
_field->allocated_words = needed;
_field->used_words = needed;
}
}
/******************************************************************************
* *
* Paramètres : field = champ de bits à consulter. *
* *
* Description : Indique la taille d'un champ de bits donné. *
* *
* Retour : Taille du champ de bits. *
* *
* Remarques : - *
* *
******************************************************************************/
size_t get_bit_field_size(const bitfield_t *field)
{
size_t result; /* Dimension à retourner */
result = field->length;
return result;
}
/******************************************************************************
* *
* Paramètres : a = premier champ à analyser. *
* b = second champ à analyser. *
* *
* Description : Compare deux champs de bits entre eux. *
* *
* Retour : Bilan de la comparaison. *
* *
* Remarques : - *
* *
******************************************************************************/
int compare_bit_fields(const bitfield_t *a, const bitfield_t *b)
{
int result; /* Bilan à retourner */
unsigned long final; /* Masque de la partie finale */
size_t i; /* Boucle de parcours */
unsigned long val_a; /* Valeur d'un mot de A */
unsigned long val_b; /* Valeur d'un mot de B */
result = 0;
if (a->length > b->length)
result = 1;
else if (a->length < b->length)
result = -1;
else
{
final = a->length % BF_WORD_BIT_SIZE;
if (final == 0)
final = ~0lu;
else
final = (1 << final) - 1;
for (i = 0; i < a->used_words && result == 0; i++)
{
val_a = a->bits[i];
val_b = b->bits[i];
if ((i + 1) == a->used_words)
{
val_a &= final;
val_b &= final;
}
if (val_a > val_b)
result = 1;
else if (val_a < val_b)
result = -1;
}
}
return result;
}
/******************************************************************************
* *
* Paramètres : field = champ de bits à modifier. *
* *
* Description : Bascule à 0 un champ de bits dans son intégralité. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
void reset_all_in_bit_field(bitfield_t *field)
{
memset(field->bits, 0u, field->used_words * BF_WORD_BYTE_SIZE);
}
/******************************************************************************
* *
* Paramètres : field = champ de bits à modifier. *
* *
* Description : Bascule à 1 un champ de bits dans son intégralité. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
void set_all_in_bit_field(bitfield_t *field)
{
memset(field->bits, ~0u, field->used_words * BF_WORD_BYTE_SIZE);
}
/******************************************************************************
* *
* Paramètres : field = champ de bits à modifier. *
* first = indice du premier bit à traiter. *
* *
* Description : Bascule à 0 une partie d'un champ de bits. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
void reset_in_bit_field(bitfield_t *field, size_t first)
{
size_t index; /* Cellule de tableau visée */
size_t remaining; /* Nombre de bits restants */
assert(first < field->length);
index = first / BF_WORD_BIT_SIZE;
remaining = first % BF_WORD_BIT_SIZE;
field->bits[index] &= ~(1ul << remaining);
}
/******************************************************************************
* *
* Paramètres : field = champ de bits à modifier. *
* first = indice du premier bit à traiter. *
* count = nombre de bits à marquer. *
* *
* Description : Bascule à 0 une partie d'un champ de bits. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
void reset_multi_in_bit_field(bitfield_t *field, size_t first, size_t count)
{
size_t last; /* Point d'arrêt de la boucle */
size_t i; /* Boucle de parcours */
size_t index; /* Cellule de tableau visée */
size_t remaining; /* Nombre de bits restants */
last = first + count;
assert(last <= field->length);
for (i = first; i < last; i++)
{
index = i / BF_WORD_BIT_SIZE;
remaining = i % BF_WORD_BIT_SIZE;
field->bits[index] &= ~(1ul << remaining);
}
}
/******************************************************************************
* *
* Paramètres : field = champ de bits à modifier. *
* first = indice du premier bit à traiter. *
* *
* Description : Bascule à 1 une partie d'un champ de bits. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
void set_in_bit_field(bitfield_t *field, size_t first)
{
size_t index; /* Cellule de tableau visée */
size_t remaining; /* Nombre de bits restants */
assert(first < field->length);
index = first / BF_WORD_BIT_SIZE;
remaining = first % BF_WORD_BIT_SIZE;
field->bits[index] |= (1ul << remaining);
}
/******************************************************************************
* *
* Paramètres : field = champ de bits à modifier. *
* first = indice du premier bit à traiter. *
* count = nombre de bits à marquer. *
* *
* Description : Bascule à 1 une partie d'un champ de bits. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
void set_multi_in_bit_field(bitfield_t *field, size_t first, size_t count)
{
size_t last; /* Point d'arrêt de la boucle */
size_t i; /* Boucle de parcours */
size_t index; /* Cellule de tableau visée */
size_t remaining; /* Nombre de bits restants */
last = first + count;
assert(last <= field->length);
for (i = first; i < last; i++)
{
index = i / BF_WORD_BIT_SIZE;
remaining = i % BF_WORD_BIT_SIZE;
field->bits[index] |= (1ul << remaining);
}
}
/******************************************************************************
* *
* Paramètres : dest = champ de bits à modifier. *
* src = champ de bits à utiliser pour l'opération. *
* *
* Description : Réalise une opération ET logique entre deux champs de bits. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
void and_bit_field(bitfield_t *dest, const bitfield_t *src)
{
size_t i; /* Boucle de parcours */
assert(dest->length == src->length);
for (i = 0; i < dest->used_words; i++)
dest->bits[i] &= src->bits[i];
}
/******************************************************************************
* *
* Paramètres : dest = champ de bits à modifier. *
* src = champ de bits à utiliser pour l'opération. *
* *
* Description : Réalise une opération OU logique entre deux champs de bits. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
void or_bit_field(bitfield_t *dest, const bitfield_t *src)
{
size_t i; /* Boucle de parcours */
assert(dest->length == src->length);
for (i = 0; i < dest->used_words; i++)
dest->bits[i] |= src->bits[i];
}
/******************************************************************************
* *
* Paramètres : dest = champ de bits à modifier. *
* src = champ de bits à utiliser pour l'opération. *
* first = point de départ pour l'opération à réaliser. *
* *
* Description : Réalise une opération OU logique entre deux champs de bits. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
void or_bit_field_at(bitfield_t *dest, const bitfield_t *src, size_t first)
{
size_t start; /* Mot de départ dans le champ */
size_t offset; /* Décalage des mots à basculer*/
size_t remaining; /* Taille du dernier tronçon */
size_t last_iter; /* Dernière itération à mener */
size_t i; /* Boucle de parcours */
unsigned long word; /* Mot reconstituté à tester */
assert((first + src->length) <= dest->length);
start = first / BF_WORD_BIT_SIZE;
offset = first % BF_WORD_BIT_SIZE;
remaining = (first + src->length) % BF_WORD_BIT_SIZE;
if ((first + src->length) % BF_WORD_BIT_SIZE > 0)
last_iter = src->used_words;
else
last_iter = src->used_words - 1;
for (i = 0; i <= last_iter; i++)
{
if (i < src->used_words)
word = src->bits[i] << offset;
else
word = 0;
if (i > 0 && offset > 0)
word |= src->bits[i - 1] >> (BF_WORD_BIT_SIZE - offset);
if (i == last_iter && remaining > 0)
word &= (1ul << remaining) - 1;
dest->bits[start + i] |= word;
}
}
/******************************************************************************
* *
* Paramètres : field = champ de bits à consulter. *
* n = indice du bit à traiter. *
* *
* Description : Détermine si un bit est à 1 dans un champ de bits. *
* *
* Retour : true si le bit correspondant est à l'état haut. *
* *
* Remarques : - *
* *
******************************************************************************/
bool test_in_bit_field(const bitfield_t *field, size_t n)
{
bool result; /* Valeur retrouvée à renvoyer */
size_t index; /* Cellule de tableau visée */
size_t remaining; /* Nombre de bits restants */
assert(n < field->length);
index = n / BF_WORD_BIT_SIZE;
remaining = n % BF_WORD_BIT_SIZE;
result = field->bits[index] & (1ul << remaining);
return result;
}
/******************************************************************************
* *
* Paramètres : field = champ de bits à consulter. *
* n = indice du bit à traiter. *
* *
* Description : Détermine si un bit est à 1 dans un champ puis le définit. *
* *
* Retour : true si le bit correspondant était déjà à l'état haut. *
* *
* Remarques : - *
* *
******************************************************************************/
bool test_and_set_in_bit_field(bitfield_t *field, size_t n)
{
bool result; /* Valeur retrouvée à renvoyer */
size_t index; /* Cellule de tableau visée */
size_t remaining; /* Nombre de bits restants */
unsigned long *bits; /* Accès mis en commun */
assert(n < field->length);
index = n / BF_WORD_BIT_SIZE;
remaining = n % BF_WORD_BIT_SIZE;
bits = field->bits + index;
result = *bits & (1ul << remaining);
*bits |= (1ul << remaining);
return result;
}
/******************************************************************************
* *
* Paramètres : field = champ de bits à modifier. *
* first = indice du premier bit à traiter. *
* count = nombre de bits à marquer. *
* state = état global à retrouver idéalement. *
* *
* Description : Détermine si un ensemble de bits est homogène dans un champ. *
* *
* Retour : true si les bits correspondants sont à l'état indiqué. *
* *
* Remarques : - *
* *
******************************************************************************/
static bool test_state_in_bit_field(const bitfield_t *field, size_t first, size_t count, bool state)
{
size_t last; /* Point d'arrêt de la boucle */
size_t i; /* Boucle de parcours */
size_t index; /* Cellule de tableau visée */
size_t remaining; /* Nombre de bits restants */
bool current; /* Etat d'un bit donné */
assert(count > 0);
last = first + count;
for (i = first; i < last; i++)
{
index = i / BF_WORD_BIT_SIZE;
remaining = i % BF_WORD_BIT_SIZE;
current = field->bits[index] & (1ul << remaining);
if (current != state) break;
}
return (i == last);
}
/******************************************************************************
* *
* Paramètres : field = champ de bits à consulter. *
* first = indice du premier bit à traiter. *
* count = nombre de bits à analyser. *
* *
* Description : Détermine si un ensemble de bits est à 0 dans un champ. *
* *
* Retour : true si les bits correspondants sont à l'état bas. *
* *
* Remarques : - *
* *
******************************************************************************/
bool test_none_in_bit_field(const bitfield_t *field, size_t first, size_t count)
{
bool result; /* Valeur retrouvée à renvoyer */
result = test_state_in_bit_field(field, first, count, false);
return result;
}
/******************************************************************************
* *
* Paramètres : field = champ de bits à consulter. *
* first = indice du premier bit à traiter. *
* count = nombre de bits à analyser. *
* *
* Description : Détermine si un ensemble de bits est à 1 dans un champ. *
* *
* Retour : true si les bits correspondants sont à l'état haut. *
* *
* Remarques : - *
* *
******************************************************************************/
bool test_all_in_bit_field(const bitfield_t *field, size_t first, size_t count)
{
bool result; /* Valeur retrouvée à renvoyer */
result = test_state_in_bit_field(field, first, count, true);
return result;
}
/******************************************************************************
* *
* Paramètres : field = champ de bits à modifier. *
* first = indice du premier bit à traiter. *
* mask = second champ de bits à tester logiquement. *
* state = état global à retrouver idéalement. *
* *
* Description : Teste l'état de bits selon un masque de bits. *
* *
* Retour : true si les bits visés sont tous à l'état indiqué. *
* *
* Remarques : - *
* *
******************************************************************************/
static bool test_state_within_bit_field(const bitfield_t *field, size_t first, const bitfield_t *mask, bool state)
{
bool result; /* Bilan à retourner */
size_t start; /* Mot de départ dans le champ */
size_t offset; /* Décalage des mots à testter */
size_t remaining; /* Taille du dernier tronçon */
unsigned long finalcut; /* Limitation du mot final */
size_t i; /* Boucle de parcours */
size_t windex; /* Indice du mot courant */
unsigned long word; /* Mot reconstituté à tester */
unsigned long bitmask; /* Masque à appliquer */
unsigned long test; /* Valeur résultante du test */
/**
* Si un masque est à appliquer avec débordement, les bits débordés sont considérés
* comme initialisés à la valeur par défaut.
*/
if ((first + mask->length) > field->length)
{
assert(mask->length > 0);
result = (state == field->default_state);
if (!result) goto done;
if (first >= field->length)
goto done;
}
else
result = true;
start = first / BF_WORD_BIT_SIZE;
offset = first % BF_WORD_BIT_SIZE;
remaining = mask->length % BF_WORD_BIT_SIZE;
if (remaining == 0)
finalcut = ~0lu;
else
finalcut = (1lu << remaining) - 1;
for (i = 0; i < mask->used_words && result; i++)
{
windex = start + i;
if (offset == 0)
word = field->bits[windex];
else
{
word = field->bits[windex] >> offset;
if ((windex + 1) < field->used_words)
word |= field->bits[windex + 1] << (BF_WORD_BIT_SIZE - offset);
}
bitmask = mask->bits[i];
test = word ^ bitmask;
test &= bitmask;
if ((i + 1) == mask->used_words)
{
bitmask &= finalcut;
test &= finalcut;
}
result = (state ? test == 0 : test == bitmask);
}
done:
return result;
}
/******************************************************************************
* *
* Paramètres : field = champ de bits à modifier. *
* first = indice du premier bit à traiter. *
* mask = second champ de bits à tester logiquement. *
* *
* Description : Teste l'état à 0 de bits selon un masque de bits. *
* *
* Retour : true si les bits visés sont à l'état bas. *
* *
* Remarques : - *
* *
******************************************************************************/
bool test_zeros_within_bit_field(const bitfield_t *field, size_t first, const bitfield_t *mask)
{
bool result; /* Valeur retrouvée à renvoyer */
result = test_state_within_bit_field(field, first, mask, false);
return result;
}
/******************************************************************************
* *
* Paramètres : field = champ de bits à modifier. *
* first = indice du premier bit à traiter. *
* mask = second champ de bits à tester logiquement. *
* *
* Description : Teste l'état à 1 de bits selon un masque de bits. *
* *
* Retour : true si les bits visés sont à l'état haut. *
* *
* Remarques : - *
* *
******************************************************************************/
bool test_ones_within_bit_field(const bitfield_t *field, size_t first, const bitfield_t *mask)
{
bool result; /* Valeur retrouvée à renvoyer */
result = test_state_within_bit_field(field, first, mask, true);
return result;
}
/******************************************************************************
* *
* Paramètres : field = champ de bits à consulter. *
* prev = indice rapporté avec une itération précédente. *
* *
* Description : Recherche un prochain bit défini dans un champ de bits. *
* *
* Retour : Position d'un bit à 1 ou taille du champ si plus aucun. *
* *
* Remarques : - *
* *
******************************************************************************/
size_t find_next_set_in_bit_field(const bitfield_t *field, const size_t *prev)
{
size_t result; /* Indice à retourner */
size_t i; /* Boucle de parcours */
unsigned long word; /* Espace de travail courant */
size_t last_pos; /* Position précédente locale */
int found; /* Bian de recherche locale */
/* Travaux sur le premier mot, nécessitant potentiellement un masque */
if (prev == NULL)
{
i = 0;
word = field->bits[0];
}
else
{
i = *prev / BF_WORD_BIT_SIZE;
if (i >= field->used_words)
{
result = field->length;
goto nothing_to_do;
}
word = field->bits[i];
last_pos = *prev % BF_WORD_BIT_SIZE;
if ((last_pos + 1) == BF_WORD_BIT_SIZE)
goto next_word;
word &= ~((1lu << (last_pos + 1)) - 1);
}
found = __builtin_ffsl(word);
if (found > 0)
{
result = i * BF_WORD_BIT_SIZE + found - 1;
goto done;
}
/* Extension aux autres mots suivantes au besoin */
next_word:
result = field->length;
for (i++; i < field->used_words; i++)
{
found = __builtin_ffsl(field->bits[i]);
if (found > 0)
{
result = i * BF_WORD_BIT_SIZE + found - 1;
/**
* Validation des bornes finales, pour le dernier mot.
*/
if (result > field->length)
result = field->length;
goto done;
}
}
/* Sortie */
done:
nothing_to_do:
return result;
}
/******************************************************************************
* *
* Paramètres : field = champ de bits à consulter. *
* extra = champ de bits à placer. *
* first = mémorisation d'un point de départ entre appels. [OUT]*
* *
* 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. *
* *
* Retour : Valeur positive ou nulle. *
* *
* Remarques : - *
* *
******************************************************************************/
size_t popcount_for_bit_field(const bitfield_t *field)
{
size_t result; /* Quantité à renvoyer */
size_t remaining; /* Nombre de bits restants */
size_t i; /* Boucle de parcours */
unsigned long value; /* Valeur masquée à traiter */
result = 0;
remaining = field->length;
for (i = 0; i < field->used_words; i++)
{
value = field->bits[i];
if (remaining < BF_WORD_BIT_SIZE)
value &= (1lu << remaining) - 1;
#if __WORDSIZE == 64
result += popcount_64(value);
#elif __WORDSIZE == 32
result += popcount_32(value);
#else
# error "Unkown word size"
#endif
remaining -= BF_WORD_BIT_SIZE;
}
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);
for (i = 0; i < field->used_words; i++)
{
value = field->bits[i];
if (i > 0)
printf("| ");
for (k = 0; k < BF_WORD_BIT_SIZE; k++)
{
if ((i * BF_WORD_BIT_SIZE + k) >= field->length)
break;
printf("%c", value & (1lu << k) ? '1' : '.');
if ((k + 1) % 8 == 0)
printf(" ");
}
}
printf("\n");
}
#endif
/******************************************************************************
* *
* Paramètres : fd = flux ouvert en lecture. *
* length = éventuelle indication de la taille du champ ? *
* def_state = éventuelle indication de l'état par défaut ? *
* endian = ordre des bits dans la source. *
* *
* Description : Restaure un champ de bits depuis un flux ouvert. *
* *
* Retour : Adresse du champs de bits mis en place, NULL en cas d'échec. *
* *
* Remarques : - *
* *
******************************************************************************/
bitfield_t *load_bit_field(int fd, const size_t *length, const bool *def_state, SourceEndian endian)
{
bitfield_t *result; /* Structure à retourner */
size_t final_length; /* Nombre de bits représentés */
uleb128_t leb128_value; /* Valeur LEB128 chargée */
bool status; /* Bilan d'une lecture */
bool final_default_state; /* Etat d'initialisation */
uint8_t u8_value; /* Valeur sur 8 bits chargée */
size_t i; /* Boucle de parcours */
result = NULL;
if (length != NULL)
final_length = *length;
else
{
status = load_uleb128(&leb128_value, fd);
if (!status) goto exit;
final_length = leb128_value;
}
if (def_state != NULL)
final_default_state = *def_state;
else
{
status = load_u8(fd, &u8_value);
if (!status) goto exit;
final_default_state = !!u8_value;
}
result = _create_bit_field(final_length);
result->default_state = final_default_state;
for (i = 0; i < result->used_words; i++)
{
status = load_uleb128(&leb128_value, fd);
if (status)
result->bits[i] = leb128_value;
else
{
delete_bit_field(result);
result = NULL;
break;
}
}
exit:
return result;
}
/******************************************************************************
* *
* Paramètres : field = champ de bits à consulter. *
* fd = flux ouvert en écriture. *
* skip_len = saute la sauvegarde de la taille du champ ? *
* skip_def = saute la sauvegarde de l'état par défaut ? *
* endian = ordre des bits dans la source. *
* *
* Description : Sauvegarde un champ de bits dans un flux ouvert. *
* *
* Retour : Bilan de l'opération : true en cas de succès, false sinon. *
* *
* Remarques : - *
* *
******************************************************************************/
bool store_bit_field(const bitfield_t *field, int fd, bool skip_len, bool skip_def, SourceEndian endian)
{
bool result; /* Bilan à retourner */
size_t i; /* Boucle de parcours */
if (skip_len)
result = true;
else
{
result = store_uleb128((const uleb128_t []) { field->length }, fd);
if (!result) goto exit;
}
if (skip_def)
result = true;
else
{
result = store_u8(fd, field->default_state);
if (!result) goto exit;
}
for (i = 0; i < field->used_words; i++)
{
result = store_uleb128((const uleb128_t []) { field->bits[i] }, fd);
if (!result)
break;
}
exit:
return result;
}