/* Chrysalide - Outil d'analyse de fichiers binaires
* atom.c - détermination d'atomes à partir de motifs
*
* 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 .
*/
#include "atom.h"
#include
#include
#include
/**
* Remplacement des fonctions de dans support des locales.
*/
#define IS_CH_LETTER(ch) (('A' <= ch && ch <= 'Z') || ('a' <= ch && ch <= 'z'))
#define MAKE_CH_UPPER(ch) (ch & 0xdf)
#define MAKE_CH_LOWER(ch) (ch | 0x20)
/******************************************************************************
* *
* Paramètres : ch = octet dont la valeur est à analyser. *
* seen = suivi des octets déjà rencontrés. [OUT] *
* uniq = volume d'octets originaux à actualiser. [OUT] *
* letters = nombre de lettres rencontrées. [OUT] *
* *
* Description : Note l'intêret de rechercher un octet particulier. *
* *
* Retour : Note positive ou négative. *
* *
* Remarques : - *
* *
******************************************************************************/
int rate_byte_quality(bin_t ch, uint8_t *seen, size_t *uniq, size_t *letters)
{
int result; /* Note à retourner */
switch (ch)
{
case 0x00:
case 0x20:
case 0x90:
case 0xcc:
case 0xff:
result = 12;
break;
case 'A' ... 'Z':
case 'a' ... 'z':
if (letters == NULL)
result = 20;
else
{
result = 18;
(*letters)++;
}
break;
default:
result = 20;
break;
}
if (seen[ch]++ == 0)
(*uniq)++;
return result;
}
/******************************************************************************
* *
* Paramètres : ch = octet dont la valeur est à analyser. *
* seen = suivi des octets déjà rencontrés. [OUT] *
* uniq = volume d'octets originaux à actualiser. [OUT] *
* letters = nombre de lettres rencontrées. [OUT] *
* *
* Description : Annihile l'intêret de rechercher un octet particulier. *
* *
* Retour : Note positive ou négative. *
* *
* Remarques : - *
* *
******************************************************************************/
int unrate_byte_quality(bin_t ch, uint8_t *seen, size_t *uniq, size_t *letters)
{
int result; /* Note à retourner */
switch (ch)
{
case 0x00:
case 0x20:
case 0x90:
case 0xcc:
case 0xff:
result = 12;
break;
case 'A' ... 'Z':
case 'a' ... 'z':
if (letters == NULL)
result = 20;
else
{
result = 18;
assert(*letters > 0);
(*letters)--;
}
break;
default:
result = 20;
break;
}
if (--seen[ch] == 0)
{
assert(*uniq > 0);
(*uniq)--;
}
return result;
}
/******************************************************************************
* *
* Paramètres : rating = note d'évaluation courante. *
* uniq = volume d'octets originaux relevés. *
* max = nombre d'octets considérés à la base. *
* *
* Description : Termine la notation d'un ensemble d'octets. *
* *
* Retour : Note positive ou négative. *
* *
* Remarques : - *
* *
******************************************************************************/
int finish_quality_rating(int rating, size_t uniq, size_t max)
{
int result; /* Note à retourner */
bool bad; /* Indice de mauvaise qualité */
if (uniq == 1)
{
bad = (rating % 12) == 0;
result = (bad ? -10 * max : 2);
}
else
result = uniq * 2;
result += rating;
return result;
}
/******************************************************************************
* *
* Paramètres : raw = définition de la bribe à enregistrer. *
* maxsize = taille max. des atomes (mise en commun optimisée). *
* atom = informations de suivi constituées. [OUT] *
* letters = nombre de lettres rencontrées. [OUT] *
* *
* Description : Détermine la portion idéale de recherche. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
void find_best_atom(const sized_binary_t *raw, size_t maxsize, tracked_scan_atom_t *atom, size_t *letters)
{
size_t i; /* Boucle de parcours #1 */
bin_t ch; /* Octets à étudier */
size_t best_letters; /* Mémorisation de décompte */
size_t *ptr_letters; /* Pointeur vers le décompte */
int raw_rating; /* Notation brute de séquence */
uint8_t seen[256]; /* Mémorisation des passages */
size_t uniq; /* Nombre d'octets originaux */
const bin_t *last; /* Dernier caractère étudié */
int best_rating; /* Meilleur notation obtenue */
size_t max_loop; /* Limitation des itérations */
size_t k; /* Boucle de parcours #2 */
size_t local_letters; /* Décompte courant des lettres*/
int local_rating; /* Notation courante */
const bin_t *first; /* Premier caractère étudié */
/* Si la chaîne fournie est plus petite que la taille d'un atome... */
if (raw->len <= maxsize)
{
atom->pos = 0;
atom->len = raw->len;
atom->rem = 0;
atom->fast_check = true;
if (letters != NULL)
{
*letters = 0;
for (i = 0; i < raw->len; i++)
{
ch = raw->data[i];
if (IS_CH_LETTER(ch))
(*letters)++;
}
}
}
/* ... ou si une sélection doit s'opérer */
else
{
/* Etablissement d'une mesure de référence à la position 0 */
atom->pos = 0;
atom->len = maxsize;
ptr_letters = (letters != NULL ? &best_letters : NULL);
best_letters = 0;
raw_rating = 0;
memset(seen, 0, sizeof(seen));
uniq = 0;
last = raw->static_bin_data;
for (k = 0; k < maxsize; k++)
raw_rating += rate_byte_quality(*last++, seen, &uniq, ptr_letters);
best_rating = finish_quality_rating(raw_rating, uniq, maxsize);
/* Parcours du reste du contenu */
max_loop = (raw->len - maxsize);
ptr_letters = (letters != NULL ? &local_letters : NULL);
local_letters = best_letters;
local_rating = best_rating;
first = raw->static_bin_data;
for (i = 0; i < max_loop; i++)
{
raw_rating += rate_byte_quality(*last++, seen, &uniq, ptr_letters);
raw_rating -= unrate_byte_quality(*first++, seen, &uniq, ptr_letters);
local_rating = finish_quality_rating(raw_rating , uniq, maxsize);
if (local_rating > best_rating)
{
atom->pos = i + 1;
best_letters = local_letters;
best_rating = local_rating;
}
}
/* Conclusion */
atom->rem = raw->len - atom->pos - maxsize;
atom->fast_check = false;
if (letters != NULL)
*letters = best_letters;
}
assert((atom->fast_check && atom->pos == 0 && atom->rem == 0)
|| (!atom->fast_check && (atom->pos != 0 || atom->rem != 0)));
}
/******************************************************************************
* *
* Paramètres : src = chaîne ed référence à dupliquer. *
* atom = préselection opérée en amont. *
* count = nombre de lettres présentes. *
* *
* Description : Etablit la liste des cas de figures ignorant la casse. *
* *
* Retour : Liste de toutes les combinaisons possibles. *
* *
* Remarques : - *
* *
******************************************************************************/
sized_binary_t *make_atoms_case_insensitive(const sized_binary_t *src, const tracked_scan_atom_t *atom, size_t count)
{
sized_binary_t *result; /* Liste à retourner */
size_t i; /* Boucle de parcours #1 */
size_t replaced; /* 2^(alternatives créées) */
#ifndef NDEBUG
size_t check; /* Validation du compte max. */
#endif
bin_t ch; /* Octet à recopier */
size_t k; /* Boucle de parcours #2 */
size_t divisor; /* Taille de la découpe */
size_t quotient; /* Reste de la position */
/* Création du réceptacle */
result = malloc(count * sizeof(tracked_scan_atom_t));
assert(src->len == (atom->pos + atom->len + atom->rem));
for (i = 0; i < count; i++)
{
result[i].data = malloc(src->len);
result[i].len = src->len;
memcpy(result[i].data, src->data, atom->pos);
memcpy(&result[i].data[atom->pos + atom->len], &src->data[atom->pos + atom->len], atom->rem);
}
/* Remplissage */
replaced = 2;
#ifndef NDEBUG
check = 1;
#endif
for (i = atom->pos; i < (atom->pos + atom->len); i++)
{
ch = src->data[i];
if (IS_CH_LETTER(ch))
{
for (k = 0; k < count; k++)
{
divisor = count / replaced;
quotient = k / divisor;
if ((quotient % 2) == 0)
result[k].data[i] = MAKE_CH_UPPER(ch);
else
result[k].data[i] = MAKE_CH_LOWER(ch);
}
replaced *= 2;
#ifndef NDEBUG
check *= 2;
assert(check <= count);
#endif
}
else
for (k = 0; k < count; k++)
result[k].data[i] = ch;
}
assert(check == count);
return result;
}
/******************************************************************************
* *
* Paramètres : bytes = octets partiels avec leur masque à interpréter. *
* len = quantité d'octets à interpréter. *
* produced = nombre de contenus générés. [OUT] *
* *
* Description : Etablit la liste des cas de figures avec des octets partiels.*
* *
* Retour : Liste de toutes les combinaisons possibles. *
* *
* Remarques : - *
* *
******************************************************************************/
sized_binary_t *make_atoms_from_masked_bytes(const masked_byte_t *bytes, size_t len, size_t *produced)
{
sized_binary_t *result; /* Liste à retourner */
size_t seq_len; /* Taille de séquence retenue */
size_t repeat_times; /* Répétitions pour remplissage*/
sized_binary_t *maxiter; /* Borne de fin de parcours */
size_t i; /* Boucle de parcours #1 */
sized_binary_t *iter; /* Boucle de parcours #2 */
size_t j; /* Boucle de parcours #3 */
size_t k; /* Boucle de parcours #4 */
seq_len = (len > MASK_MAX_LEN_FOR_ATOMS ? MASK_MAX_LEN_FOR_ATOMS : len);
/**
* Si l'usage de la fonction pow() disparaît, la bibliothèque m
* peut être retirée de libchrysacore_la_LDFLAGS dans le Makefile
* principal.
*/
repeat_times = pow(16, seq_len - 1);
*produced = 16 * repeat_times;
/* Création du réceptacle */
result = malloc(*produced * sizeof(tracked_scan_atom_t));
maxiter = result + *produced;
/* Remplissage */
for (i = 0; i < seq_len; i++)
{
for (iter = result; iter < maxiter; )
{
for (j = 0; j < 16; j++)
{
assert(bytes[i].mask == 0x0f || bytes[i].mask == 0xf0);
for (k = 0; k < repeat_times; k++)
{
if (i == 0)
{
iter->data = malloc(seq_len);
iter->len = seq_len;
}
if (bytes[i].mask == 0x0f)
iter->data[i] = bytes[i].value | (j << 4);
else
iter->data[i] = bytes[i].value | j;
iter++;
}
}
}
repeat_times /= 16;
}
return result;
}
/******************************************************************************
* *
* Paramètres : raw = définition de la bribe à enregistrer. *
* backend = moteur de recherche à préchauffer. *
* atom = informations de suivi constituées. [OUT] *
* *
* Description : Amorce l'insertion de l'atome déterminé d'une série d'octets.*
* *
* Retour : Bilan de l'opération à renvoyer. *
* *
* Remarques : - *
* *
******************************************************************************/
bool enroll_prepared_atom(const sized_binary_t *raw, GEngineBackend *backend, tracked_scan_atom_t *atom)
{
bool result; /* Statut à retourner */
const bin_t *data; /* Données à rechercher */
data = raw->static_bin_data + atom->pos;
result = g_engine_backend_enroll_plain_pattern(backend, data, atom->len, atom->tmp_id);
return result;
}
/******************************************************************************
* *
* Paramètres : atom = informations de suivi constituées. [OUT] *
* backend = moteur de recherche à préchauffer. *
* *
* Description : Récupère un identifiant final pour un atome d'octets. *
* *
* Retour : Bilan de l'opération à renvoyer. *
* *
* Remarques : - *
* *
******************************************************************************/
bool build_atom_pattern_id(tracked_scan_atom_t *atom, GEngineBackend *backend)
{
bool result; /* Statut à retourner */
atom->pid = g_engine_backend_build_plain_pattern_id(backend, atom->tmp_id);
result = (atom->pid != INVALID_PATTERN_ID);
return result;
}