path: root/src/analysis/scan/patterns/tokens/atom.c

/* 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 <http://www.gnu.org/licenses/>.
 */


#include "atom.h"


#include <assert.h>
#include <malloc.h>
#include <math.h>



/**
 * Remplacement des fonctions de <ctypes.h> 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;

}