/* 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 Chrysalide.  If not, see <http://www.gnu.org/licenses/>.
 */


#include "bits.h"


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



/* Champ de bits simple */
struct _bitfield_t
{
    size_t length;                          /* Nombre de bits représentés  */
    size_t requested;                       /* Nombre de mots alloués      */

    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);

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



/******************************************************************************
*                                                                             *
*  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 requested;                       /* 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++;

    base = sizeof(bitfield_t) + requested * sizeof(unsigned long);

    result = (bitfield_t *)malloc(base);

    result->length = length;
    result->requested = requested;

    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);

    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->requested * sizeof(unsigned long));

    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->requested * sizeof(unsigned long));

}


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

    if (result == 0)
    {
        final = a->length % sizeof(unsigned long);

        if (final == 0)
            final = ~0lu;
        else
            final = (1 << final) - 1;

        for (i = 0; i < a->requested && result == 0; i++)
        {
            val_a = a->bits[i];
            val_b = b->bits[i];

            if ((i + 1) == a->requested)
            {
                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->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 à 0 une partie d'un champ de bits.                   *
*                                                                             *
*  Retour      : -                                                            *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

void reset_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 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  : 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 à 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 / (sizeof(unsigned long) * 8);
    remaining = n % (sizeof(unsigned long) * 8);

    result = field->bits[index] & (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 / (sizeof(unsigned long) * 8);
        remaining = i % (sizeof(unsigned long) * 8);

        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;

}