path: root/src/common/bits.c

/* Chrysalide - Outil d'analyse de fichiers binaires
 * bits.c - manipulation d'un champ de bits quelconque
 *
 * Copyright (C) 2015-2017 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 <http://www.gnu.org/licenses/>.
 */


#include "bits.h"


#include <assert.h>
#include <glib.h>
#include <malloc.h>
#include <string.h>



/* ----------------------------- 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