/* Chrysalide - Outil d'analyse de fichiers binaires
* pending.c - consolidation de correspondances partielles
*
* Copyright (C) 2023 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 "pending.h"
#include <malloc.h>
#include <stdlib.h>
#include <string.h>
#include "../../../common/sort.h"
/* ------------------------- MEMORISATION D'UNE ZONE BORNEE ------------------------- */
/* Compare deux couvertures bornées de correspondances. */
static int compare_match_area(const match_area_t *, const match_area_t *);
/* -------------------- CONSERVATION DE CORRESPONDANCES ETABLIES -------------------- */
#define PENDING_ALLOC_SIZE 10
/* ---------------------------------------------------------------------------------- */
/* MEMORISATION D'UNE ZONE BORNEE */
/* ---------------------------------------------------------------------------------- */
/******************************************************************************
* *
* Paramètres : allocator = allocateur dédié à l'ensemble de zones. *
* start = point de départ d'une nouvelle correspondance. *
* length = taille de la zone couverte. *
* *
* Description : Crée une nouvelle structure de suivi de correspondance. *
* *
* Retour : Structure initialisée mise en place. *
* *
* Remarques : - *
* *
******************************************************************************/
static match_area_t *create_match_area(GUMemCache *allocator, phys_t start, phys_t length)
{
match_area_t *result; /* Zone à retourner */
result = g_umem_cache_alloc(allocator);
DL_LIST_ITEM_INIT(&result->link);
result->start = start;
result->end = start + length;
assert(matches->content_start <= result->start);
assert(result->end <= matches->content_end);
result->ttl = 1;
result->has_mod_path = false;
return result;
}
/******************************************************************************
* *
* Paramètres : allocator = allocateur dédié à l'ensemble de zones. *
* start = point de départ d'une nouvelle correspondance. *
* length = taille de la zone couverte. *
* index = indice de construction pour le motif concerné. *
* *
* Description : Crée une nouvelle structure de suivi de correspondance. *
* *
* Retour : Structure initialisée mise en place. *
* *
* Remarques : - *
* *
******************************************************************************/
static match_area_t *create_match_area_with_path(GUMemCache *allocator, phys_t start, phys_t length, size_t index)
{
match_area_t *result; /* Zone à retourner */
result = g_umem_cache_alloc(allocator);
DL_LIST_ITEM_INIT(&result->link);
result->start = start;
result->end = start + length;
assert(matches->content_start <= result->start);
assert(result->end <= matches->content_end);
result->ttl = 1;
result->mod_path_index = index;
result->has_mod_path = true;
return result;
}
/******************************************************************************
* *
* Paramètres : area = zone de suivi à supprimer. *
* allocator = allocateur dédié à l'ensemble de zones. *
* *
* Description : Supprime une structure de suivi de correspondance. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void delete_match_area(match_area_t *area, GUMemCache *allocator)
{
// TODO : assert(alone)
g_umem_cache_free(allocator, area);
}
/******************************************************************************
* *
* Paramètres : a = pointeur vers la première zone à analyser. *
* b = pointeur vers la seconde zone à analyser. *
* *
* Description : Compare deux couvertures bornées de correspondances. *
* *
* Retour : Bilan de la comparaison. *
* *
* Remarques : - *
* *
******************************************************************************/
static int compare_match_area(const match_area_t *a, const match_area_t *b)
{
int result; /* Bilan à renvoyer */
result = sort_unsigned_long_long(a->start, b->start);
if (result == 0)
result = sort_unsigned_long_long(a->end, b->end);
if (result == 0)
result = sort_unsigned_long_long(a->ttl, b->ttl);
if (result == 0)
result = sort_unsigned_long_long(a->has_mod_path, b->has_mod_path);
if (result == 0)
result = sort_unsigned_long_long(a->mod_path_index, b->mod_path_index);
return result;
}
/* ---------------------------------------------------------------------------------- */
/* CONSERVATION DE CORRESPONDANCES ETABLIES */
/* ---------------------------------------------------------------------------------- */
/******************************************************************************
* *
* Paramètres : matches = suivi de correspondances à initialiser. *
* start = première position du contenu (souvent 0). *
* end = position de fin du contenu. *
* *
* Description : Initialise une structure de consolidation de correspondances.*
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
void init_pending_matches(pending_matches_t *matches, const phys_t *start, const phys_t *end)
{
matches->content_start = *start;
matches->content_end = *end;
matches->allocator = NULL;
matches->areas = NULL;
matches->allocated = 0;
matches->used = 0;
matches->initialized = false;
matches->abort = false;
}
/******************************************************************************
* *
* Paramètres : dest = suivi de correspondances à initialiser. [OUT] *
* src = suivi de correspondances à copier. *
* *
* Description : Copie une structure de consolidation de correspondances. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
void copy_pending_matches(pending_matches_t *dest, const pending_matches_t *src)
{
dest->content_start = src->content_start;
dest->content_end = src->content_end;
dest->areas = malloc(src->used * sizeof(match_area_t));
dest->allocated = src->used;
dest->used = src->used;
memcpy(dest->areas, src->areas, src->used * sizeof(match_area_t));
dest->initialized = src->initialized;
dest->abort = src->abort;
}
/******************************************************************************
* *
* Paramètres : dest = suivi de correspondances à initialiser. [OUT] *
* src = suivi de correspondances à copier. *
* *
* Description : Fusionne une structure de consolidation avec une autre. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
void merge_pending_matches(pending_matches_t *dest, const pending_matches_t *src)
{
if ((dest->used + src->used) > dest->allocated)
{
dest->allocated += src->used;
dest->areas = realloc(dest->areas, dest->allocated * sizeof(match_area_t));
}
memcpy(&dest->areas[dest->used], src->areas, src->used * sizeof(match_area_t));
dest->used += src->used;
dest->initialized |= src->initialized;
dest->abort |= src->abort;
}
/******************************************************************************
* *
* Paramètres : matches = suivi de correspondances à purger. *
* *
* Description : Libère la mémoire utilisée par une consolidation. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
void exit_pending_matches(pending_matches_t *matches)
{
if (matches->areas != NULL)
free(matches->areas);
}
/******************************************************************************
* *
* Paramètres : matches = suivi de correspondances à consulter. *
* *
* Description : Dénombre les correspondances établies jusque là. *
* *
* Retour : Quantité de correspondances complètes jusqu'à présent. *
* *
* Remarques : - *
* *
******************************************************************************/
size_t count_pending_matches(const pending_matches_t *matches)
{
size_t result; /* Quantité à renvoyer */
result = matches->used;
return result;
}
/******************************************************************************
* *
* Paramètres : matches = suivi de correspondances à consulter. *
* count = nombre de correspondances en attente. [OUT] *
* *
* Description : Fournit la liste des correspondances établies à présent. *
* *
* Retour : Liste de correspondances en lecture seule. *
* *
* Remarques : - *
* *
******************************************************************************/
match_area_t * const *get_all_pending_matches(const pending_matches_t *matches, size_t *count)
{
match_area_t * const *result; /* Série à renvoyer */
result = &matches->areas;
*count = matches->used;
return result;
}
/******************************************************************************
* *
* Paramètres : matches = suivi de correspondances à compléter. *
* start = point de départ d'une nouvelle correspondance. *
* length = taille de la zone couverte. *
* *
* Description : Ajoute au suivi la définition d'une nouvelle correspondance. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
void add_pending_match(pending_matches_t *matches, phys_t start, phys_t length)
{
match_area_t *area; /* Nouvelle zone à intégrer */
area = create_match_area(matches->allocator, start, length);
dl_list_add_tail(area, &matches->areas, match_area_t, link);
matches->used++;
}
/******************************************************************************
* *
* Paramètres : matches = suivi de correspondances à compléter. *
* start = point de départ d'une nouvelle correspondance. *
* length = taille de la zone couverte. *
* index = indice de construction pour le motif concerné. *
* *
* Description : Ajoute au suivi la définition d'une nouvelle correspondance. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
void add_pending_match_with_path(pending_matches_t *matches, phys_t start, phys_t length, size_t index)
{
match_area_t *area; /* Nouvelle zone à intégrer */
area = create_match_area_with_path(matches->allocator, start, length, index);
dl_list_add_tail(area, &matches->areas, match_area_t, link);
matches->used++;
}
/******************************************************************************
* *
* Paramètres : matches = suivi de correspondances à compléter. *
* target = indice de la zone de correspondance concernée. *
* start = nouvelle position initiale de la zone couverte. *
* *
* Description : Etend une zone couverte dans le suivi des correspondances. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
void extend_pending_match_beginning(pending_matches_t *matches, size_t target, phys_t start)
{
match_area_t *area; /* Zone à actualiser */
assert(target < matches->used);
area = &matches->areas[target];
if (area->ttl == 0)
{
assert(matches->content_start <= start);
area->start = start;
area->ttl = 1;
}
else
{
assert(area->ttl == 1);
add_pending_match(matches, start, area->end - start);
}
}
/******************************************************************************
* *
* Paramètres : matches = suivi de correspondances à compléter. *
* target = indice de la zone de correspondance concernée. *
* length = taille de la zone couverte supplémentaire. *
* *
* Description : Etend une zone couverte dans le suivi des correspondances. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
void extend_pending_match_ending(pending_matches_t *matches, size_t target, phys_t end)
{
match_area_t *area; /* Zone à actualiser */
assert(target < matches->used);
area = &matches->areas[target];
if (area->ttl == 0)
{
assert(end <= matches->content_end);
area->end = end;
area->ttl = 1;
}
else
{
assert(area->ttl == 1);
add_pending_match(matches, area->start, end - area->start);
}
}
/******************************************************************************
* *
* Paramètres : matches = suivi de correspondances à modifier. *
* *
* Description : Réinitialisation à 0 tous les TTL de correspondances. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
void reset_pending_matches_ttl(pending_matches_t *matches)
{
size_t i; /* Boucle de parcours */
assert(matches->initialized);
for (i = 0; i < matches->used; i++)
matches->areas[i].ttl = 0;
}
/******************************************************************************
* *
* Paramètres : matches = suivi de correspondances à modifier. *
* *
* Description : Retire toutes les correspondances sans issue pour l'analyse. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
void purge_pending_matches(pending_matches_t *matches)
{
match_area_t *del_start; /* Départ d'une zone morte */
match_area_t *del_end; /* Fin d'une zone morte */
size_t del_remaining; /* Nombre de valides ensuite */
size_t del_count; /* Nombre d'éléments à effacer */
size_t i; /* Boucle de parcours */
assert(matches->initialized);
/**
* Note : le code original était le suivant :
*
* for (i = matches->used; i > 0; i--)
* if (matches->areas[i - 1].ttl == 0)
* {
* memmove(&matches->areas[i - 1], &matches->areas[i], (matches->used - i) * sizeof(match_area_t));
* matches->used--;
* }
*
* Pour éviter les appels à memmove(), un déplacement par blocs est désormais visée.
*/
del_start = NULL;
del_end = NULL;
del_count = 0;
del_remaining = 0;
/* Suppression en bloc si possible */
for (i = matches->used; i > 0; i--)
{
if (matches->areas[i - 1].ttl == 0)
{
del_start = &matches->areas[i - 1];
if (del_end == NULL)
{
del_end = del_start;
del_remaining = matches->used - i;
}
del_count++;
}
else
{
if (del_start != NULL)
{
assert(&matches->areas[i] == del_start);
if (del_remaining > 0)
memmove(del_start, del_end + 1, del_remaining * sizeof(match_area_t));
assert(matches->used > del_count);
matches->used -= del_count;
del_start = NULL;
del_end = NULL;
del_count = 0;
del_remaining = 0;
}
}
}
/* Dernier traitement au besoin */
if (del_start != NULL)
{
assert(&matches->areas[0] == del_start);
if (del_remaining > 0)
memmove(del_start, del_end + 1, del_remaining * sizeof(match_area_t));
assert(matches->used >= del_count);
matches->used -= del_count;
}
/* Bilan */
matches->abort = (matches->used == 0);
}
/******************************************************************************
* *
* Paramètres : matches = suivi de correspondances à finaliser. *
* *
* Description : Trie les correspondances et retire tous les doublons. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
void sort_and_filter_pending_matches(pending_matches_t *matches)
{
match_area_t *last; /* Dernière zone conservée */
size_t i; /* Boucle de parcours */
match_area_t *cur; /* Zone courante dans l'analyse*/
if (matches->used > 0)
{
qsort(matches->areas, matches->used, sizeof(match_area_t), (__compar_fn_t)compare_match_area);
last = &matches->areas[0];
for (i = 1; i < matches->used; i++)
{
cur = &matches->areas[i];
if (last->start != cur->start || last->end != cur->end)
{
if ((cur - last) > 1)
{
memmove(last + 1, cur, (matches->used - i) * sizeof(match_area_t));
matches->used -= (cur - last + 1);
}
last = cur;
}
}
cur = &matches->areas[matches->used - 1];
if (last != cur)
matches->used = last - matches->areas + 1;
}
}