/* Chrysalide - Outil d'analyse de fichiers binaires
* bits.c - manipulation d'un champ de bits quelconque
*
* Copyright (C) 2015 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 Foobar. If not, see .
*/
#include "bits.h"
#include
#include
#include
#include
/* ----------------------------- CHAMPS DE BITS SIMPLES ----------------------------- */
/* Champ de bits simple */
struct _bitfield_t
{
size_t length; /* Nombre de bits représentés */
size_t requested; /* Nombre de mots alloués */
void *tail; /* Limite du tableau de bits */
GMutex mutex; /* Garantie d'atomicité */
unsigned long bits[0]; /* Mémoire d'accès associée */
};
/* Crée un champ de bits initialisé à zéro. */
static bitfield_t *_create_bit_field(size_t, bool, size_t);
/* Crée une copie de champ de bits initialisé à zéro. */
static bitfield_t *_create_bit_field_from(const bitfield_t *, bool, size_t);
/* Crée une copie d'un champ de bits classique. */
static bitfield_t *_dup_bit_field(const bitfield_t *, size_t);
/* ---------------------------------------------------------------------------------- */
/* CHAMPS DE BITS SIMPLES */
/* ---------------------------------------------------------------------------------- */
/******************************************************************************
* *
* Paramètres : length = nom de bits du champ à représenter. *
* state = état initial de chaque des bits. *
* extra = espace mémoire supplémentaire à ajouter au final. *
* *
* 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, bool state, size_t extra)
{
bitfield_t *result; /* Création à retourner */
size_t requested; /* Nombre de mots à allouer */
size_t base; /* Allocation de base en octets*/
requested = length / sizeof(unsigned long);
if (length % sizeof(unsigned long) != 0) requested++;
base = sizeof(bitfield_t) + requested * sizeof(unsigned long);
result = (bitfield_t *)malloc(base + extra);
result->length = length;
result->requested = requested;
result->tail = ((char *)result) + base;
g_mutex_init(&result->mutex);
if (state)
set_all_in_bit_field(result);
else
reset_all_in_bit_field(result);
return result;
}
/******************************************************************************
* *
* Paramètres : length = nom 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)
{
return _create_bit_field(length, state, 0);
}
/******************************************************************************
* *
* Paramètres : field = champde bits à prendre pour modèle. *
* state = état initial de chaque des bits. *
* extra = espace mémoire supplémentaire à ajouter au final. *
* *
* Description : Crée une copie de champ de bits initialisé à zéro. *
* *
* Retour : Champ de bits mis en place. *
* *
* Remarques : - *
* *
******************************************************************************/
static bitfield_t *_create_bit_field_from(const bitfield_t *field, bool state, size_t extra)
{
return _create_bit_field(field->length, state, extra);
}
/******************************************************************************
* *
* Paramètres : field = champde bits à prendre pour modèle. *
* state = état initial de chaque des bits. *
* *
* Description : Crée une copie de champ de bits initialisé à zéro. *
* *
* Retour : Champ de bits mis en place. *
* *
* Remarques : - *
* *
******************************************************************************/
bitfield_t *create_bit_field_from(const bitfield_t *field, bool state)
{
return _create_bit_field_from(field, state, 0);
}
/******************************************************************************
* *
* 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)
{
g_mutex_clear(&field->mutex);
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->requested * sizeof(unsigned long));
}
/******************************************************************************
* *
* Paramètres : field = champ de bits à dupliquer. *
* extra = espace mémoire supplémentaire à ajouter au final. *
* *
* Description : Crée une copie d'un champ de bits classique. *
* *
* Retour : Champ de bits mis en place. *
* *
* Remarques : - *
* *
******************************************************************************/
static bitfield_t *_dup_bit_field(const bitfield_t *field, size_t extra)
{
bitfield_t *result; /* Copie à retourner */
size_t requested; /* Nombre de mots à allouer */
result = _create_bit_field(field->length, false, extra);
requested = field->length / sizeof(unsigned long);
if (field->length % sizeof(unsigned long) != 0) requested++;
memcpy(result->bits, field->bits, requested * sizeof(unsigned long));
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)
{
return _dup_bit_field(field, 0);
}
/******************************************************************************
* *
* 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->requested * sizeof(unsigned long));
}
/******************************************************************************
* *
* 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->requested * sizeof(unsigned long));
}
/******************************************************************************
* *
* 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_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 / (sizeof(unsigned long) * 8);
remaining = i % (sizeof(unsigned long) * 8);
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 de façon atomique une partie d'un champ de bits. *
* *
* Retour : true si la zone traitée était entièrement vierge. *
* *
* Remarques : - *
* *
******************************************************************************/
bool set_atomic_in_bit_field(bitfield_t *field, size_t first, size_t count)
{
bool result; /* Bilan à retourner */
size_t start; /* Mot de départ */
size_t end; /* Mot d'arrivée */
size_t remaining; /* Nombre de bits restants */
unsigned long mask; /* Nouvelle valeur à insérer */
unsigned long oldval; /* Ancienne valeur présente */
start = first / (sizeof(unsigned long) * 8);
end = (first + count - 1) / (sizeof(unsigned long) * 8);
if (start == end)
{
remaining = first % (sizeof(unsigned long) * 8);
assert(count > 0 && count <= (sizeof(unsigned long) * 8));
if (count == 64)
{
assert(remaining == 0);
mask = ~0lu;
}
else
{
mask = (1lu << count) - 1;
mask <<= remaining;
}
/**
* Pour une raison inconnue, l'appel suivant est parfois sans effet :
*
* oldval = g_atomic_pointer_or(&field->bits[start], mask);
*
* On bascule donc dans l'équivalent plus long à exécuter...
*/
g_mutex_lock(&field->mutex);
oldval = field->bits[start];
field->bits[start] |= mask;
g_mutex_unlock(&field->mutex);
result = ((oldval & mask) == 0);
assert(test_in_bit_field(field, first, count));
}
else
{
g_mutex_lock(&field->mutex);
result = !test_in_bit_field(field, first, count);
if (result)
set_in_bit_field(field, first, count);
g_mutex_unlock(&field->mutex);
}
return result;
}
/******************************************************************************
* *
* 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->requested; 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->requested; i++)
dest->bits[i] |= src->bits[i];
}
/******************************************************************************
* *
* Paramètres : field = champ de bits à modifier. *
* first = indice du premier bit à traiter. *
* count = nombre de bits à marquer. *
* *
* 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 first, size_t count)
{
bool result; /* Valeur retrouvée à renvoyer */
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);
result = true;
for (i = first; i < last && result; i++)
{
index = i / (sizeof(unsigned long) * 8);
remaining = i % (sizeof(unsigned long) * 8);
result = field->bits[index] & (1ul << remaining);
}
return result;
}
/******************************************************************************
* *
* Paramètres : a = premier champ de bits à comparer. *
* b = second champ de bits à comparer. *
* *
* Description : Indique si deux champs de bits sont identiques ou non. *
* *
* Retour : true si les champs de bits sont égaux ou false sinon. *
* *
* Remarques : - *
* *
******************************************************************************/
bool is_bit_field_equal_to(const bitfield_t *a, const bitfield_t *b)
{
bool result; /* Résultat à retourner */
size_t i; /* Boucle de parcours */
size_t remaining; /* Nombre de bits restants */
if (a->length != b->length)
return false;
result = true;
for (i = 0; i < (a->requested - 1) && result; i++)
result = (a->bits[i] == b->bits[i]);
if (result)
{
remaining = a->length % sizeof(unsigned long);
if (remaining == 0)
result = (a->bits[i] == b->bits[i]);
else
{
remaining = (1 << (remaining + 1)) - 1;
result = ((a->bits[i] & remaining) == (b->bits[i] & remaining));
}
}
return result;
}
unsigned long gfw(const bitfield_t *field)
{
return field->bits[0];
}
#if 0
/* ---------------------------------------------------------------------------------- */
/* CHAMPS LIES À UNE ZONE MEMOIRE */
/* ---------------------------------------------------------------------------------- */
/******************************************************************************
* *
* Paramètres : range = espace mémoire à couvrir. *
* state = état initial de chaque des bits. *
* *
* Description : Crée un champ de bits couvrant une zone mémoire. *
* *
* Retour : Champ de bits mis en place. *
* *
* Remarques : - *
* *
******************************************************************************/
memfield_t *create_mem_field(const mrange_t *range, bool state)
{
bitfield_t *result; /* Création à retourner */
result = _create_bit_field(get_mrange_length(range), state, sizeof(vmpa2t));
copy_vmpa((vmpa2t *)result->tail, get_mrange_addr(range));
return (memfield_t *)result;
}
/******************************************************************************
* *
* Paramètres : range = espace mémoire à couvrir. *
* *
* Description : Crée une copie de champ de bits couvrant une zone mémoire. *
* *
* Retour : Champ de bits mis en place. *
* *
* Remarques : - *
* *
******************************************************************************/
memfield_t *create_mem_field_from(const memfield_t *field)
{
bitfield_t *result; /* Création à retourner */
result = _create_bit_field_from((bitfield_t *)field, false, sizeof(vmpa2t));
copy_vmpa((vmpa2t *)result->tail, (vmpa2t *)field->tail);
return (memfield_t *)result;
}
/******************************************************************************
* *
* Paramètres : field = champ de bits à effacer. *
* *
* Description : Supprime de la mémoire un champ de bits donné. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
void delete_mem_field(memfield_t *field)
{
delete_bit_field((bitfield_t *)field);
}
/******************************************************************************
* *
* Paramètres : field = champ de bits à dupliquer. *
* *
* Description : Crée une copie d'un champ de bits couvrant une zone mémoire. *
* *
* Retour : Champ de bits mis en place. *
* *
* Remarques : - *
* *
******************************************************************************/
memfield_t *dup_mem_field(const memfield_t *field)
{
bitfield_t *result; /* Création à retourner */
result = _dup_bit_field((bitfield_t *)field, sizeof(vmpa2t));
copy_vmpa((vmpa2t *)result->tail, (vmpa2t *)field->tail);
return (memfield_t *)result;
}
/******************************************************************************
* *
* Paramètres : field = champ de bits à modifier. *
* addr = emplacement en mémoire à traiter. *
* *
* Description : Bascule à 1 un bit d'un champ de bits. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
void set_in_mem_field(memfield_t *field, const vmpa2t *addr)
{
vmpa2t *start; /* Adresse de début */
phys_t offset; /* Décallage de départ */
start = (vmpa2t *)field->tail;
assert(cmp_vmpa(start, addr) <= 0);
offset = compute_vmpa_diff(start, addr);
set_in_bit_field((bitfield_t *)field, offset, 1);
}
/******************************************************************************
* *
* Paramètres : field = champ de bits à modifier. *
* addr = emplacement en mémoire à tester. *
* *
* 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_mem_field(memfield_t *field, const vmpa2t *addr)
{
bool result; /* Valeur retrouvée à renvoyer */
vmpa2t *start; /* Adresse de début */
phys_t offset; /* Décallage de départ */
start = (vmpa2t *)field->tail;
assert(cmp_vmpa(start, addr) <= 0);
offset = compute_vmpa_diff(start, addr);
result = test_in_bit_field((bitfield_t *)field, offset, 1);
return result;
}
#endif