diff options
| author | Cyrille Bagard <nocbos@gmail.com> | 2023-01-30 06:59:35 (GMT) |
|---|---|---|
| committer | Cyrille Bagard <nocbos@gmail.com> | 2023-01-30 06:59:35 (GMT) |
| commit | db3b204dd7a71b2f74a4e69b2159a96e3ab66614 (patch) | |
| tree | 34174311b7ac504f03a10a889ada7f28db7a06c0 /src/analysis/scan/patterns/backends | |
| parent | 34ee1bfca78e8423cfa29329fdc756569d6b1960 (diff) | |
Save an initial version of rost.
Diffstat (limited to 'src/analysis/scan/patterns/backends')
| -rw-r--r-- | src/analysis/scan/patterns/backends/Makefile.am | 27 | ||||
| -rw-r--r-- | src/analysis/scan/patterns/backends/acism-int.h | 160 | ||||
| -rw-r--r-- | src/analysis/scan/patterns/backends/acism.c | 1295 | ||||
| -rw-r--r-- | src/analysis/scan/patterns/backends/acism.h | 59 | ||||
| -rw-r--r-- | src/analysis/scan/patterns/backends/bitap-int.h | 118 | ||||
| -rw-r--r-- | src/analysis/scan/patterns/backends/bitap.c | 2766 | ||||
| -rw-r--r-- | src/analysis/scan/patterns/backends/bitap.h | 59 |
7 files changed, 4484 insertions, 0 deletions
diff --git a/src/analysis/scan/patterns/backends/Makefile.am b/src/analysis/scan/patterns/backends/Makefile.am new file mode 100644 index 0000000..672b7ff --- /dev/null +++ b/src/analysis/scan/patterns/backends/Makefile.am @@ -0,0 +1,27 @@ + +noinst_LTLIBRARIES = libanalysisscanpatternsbackends.la + + +libanalysisscanpatternsbackends_la_SOURCES = \ + acism-int.h \ + acism.h acism.c \ + bitap-int.h \ + bitap.h bitap.c + +# Cf. https://www.gnu.org/software/automake/manual/html_node/Per_002dObject-Flags.html + +AM_CFLAGS = $(LIBGOBJ_CFLAGS) + + + +#AM_CFLAGS:=$(filter-out -O2,$(AM_CFLAGS)) + + +#bitap.lo: AM_CFLAGS += -Ofast -march=native -falign-functions=1 -falign-jumps=1 -falign-loops=1 -falign-labels=1 #-mavx512bw +#bitap.lo: AM_CFLAGS += -O3 -march=native -falign-functions=1 -falign-jumps=1 -falign-loops=1 -falign-labels=1 #-mavx512bw +bitap.lo: AM_CFLAGS += -g -march=native -mno-vzeroupper -falign-functions=1 -falign-jumps=1 -falign-loops=1 -falign-labels=1 + + +devdir = $(includedir)/chrysalide/$(subdir:src/%=core/%) + +dev_HEADERS = $(libanalysisscanpatternsbackends_la_SOURCES:%c=) diff --git a/src/analysis/scan/patterns/backends/acism-int.h b/src/analysis/scan/patterns/backends/acism-int.h new file mode 100644 index 0000000..57c3c73 --- /dev/null +++ b/src/analysis/scan/patterns/backends/acism-int.h @@ -0,0 +1,160 @@ + +/* Chrysalide - Outil d'analyse de fichiers binaires + * acism-int.h - prototypes internes pour la méthode de recherche basée sur l'algorithme Aho-Corasick Interleaved State-transition Matrix + * + * Copyright (C) 2022 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/>. + */ + + +#ifndef _ANALYSIS_SCAN_PATTERNS_BACKENDS_ACISM_INT_H +#define _ANALYSIS_SCAN_PATTERNS_BACKENDS_ACISM_INT_H + + +#include "acism.h" + + +#include <stdint.h> + + +#include "../backend-int.h" +#include "../../../../common/bits.h" + + + +//#define __USE_BYTE_FREQ +//#define __SORT_BEFORE_BITMASK + + +#define ACSIM_ATOM_SIZE 7 + + + +/* Définition d'une portion de cible */ +typedef struct _acism_source_t +{ + const uint8_t *atoms; /* Motif remarquable */ + size_t len; /* Nombre d'octets considérés */ + + patid_t pid; /* Identifiant de suivi */ + +} acism_source_t; + +/* Etude de la fréquence des octets pour attribution des codes */ +typedef struct _acism_freq_rank_t +{ + unsigned int frequency; /* Occurrences d'un octet */ + uint8_t rank; /* Valeur dudit octet */ + +} acism_freq_rank_t; + +/* Identifiant unique pour une valeur 8 bits donnée (max 257) */ +typedef uint16_t acism_code_t; + +#define MIN_ACISM_CODE 0 +#define MAX_ACISM_CODE 0xffff + +/* Noeud de l'arborescence brute */ +typedef struct _acism_trie_node_t +{ + struct _acism_trie_node_t *parent; /* Noeud parent pour remontée */ + struct _acism_trie_node_t *sibling; /* Noeud de même niveau suivant*/ + struct _acism_trie_node_t *child; /* Noeud de lecture suivant */ + struct _acism_trie_node_t *suffix_link; /* Retour en cas d'échec */ + + bin_t data; /* Donnée brute représentée */ + acism_code_t code; /* Identifiant du noeud */ + + patid_t pid; /* Identifiant de suivi */ + + acism_code_t min_child_code; /* Plus petit code suivant */ + acism_code_t max_child_code; /* Plus grand code suivant */ + size_t children_count; /* Nombre de codes suivants */ + + size_t matched_atom; /* Indice de correspondance */ + + size_t state_index; /* Indice de le tableau final */ + +} acism_trie_node_t; + +/* Cellule du tableau compressé final */ +typedef union _acism_state_t +{ + uint32_t raw; /* Valeur brute */ + + struct + { + union + { + /* Indice 0 */ + struct + { + unsigned int match : 1; /* Correspondance ici */ + unsigned int suffix : 1; /* Correspondance ailleurs */ + unsigned int unused : 4; /* Espace encore disponible */ + unsigned int atom_size : 3; /* Taille d'atome représenté */ + }; + + /* Indice 1 et + */ + unsigned int code : 9; /* Position depuis la base */ + + }; + + unsigned int index : 23; /* Indice de saut */ + + }; + +} acism_state_t; + +/* Méthode de recherche basée sur l'algorithme Acism (instance) */ +struct _GAcismBackend +{ + GEngineBackend parent; /* A laisser en premier */ + +#ifdef __USE_BYTE_FREQ + acism_code_t codes_for_bytes[256]; /* Traduction octets -> codes */ + acism_code_t codes_count; /* Quantité de traductions */ +#endif + + acism_source_t *sources; /* Liste de motifs remarquables*/ + size_t sources_count; /* Quantité de ces motifs */ + + size_t nchars; /* Taille cumulée des motifs */ + +#ifdef __USE_BYTE_FREQ + acism_freq_rank_t frequencies[256]; /* Fréquences des octets */ +#endif + + acism_trie_node_t *nodes; /* Liste de noeuds */ + size_t nodes_used; /* Nombre de noeuds utilisés */ + + bitfield_t *bitmap_usage; /* Localisation des usages */ + acism_state_t *states; /* Tableau de transitions */ + patid_t *pids; /* Identifiants de motifs */ + +}; + +/* Méthode de recherche basée sur l'algorithme Acism (classe) */ +struct _GAcismBackendClass +{ + GEngineBackendClass parent; /* A laisser en premier */ + +}; + + + +#endif /* _ANALYSIS_SCAN_PATTERNS_BACKENDS_ACISM_INT_H */ diff --git a/src/analysis/scan/patterns/backends/acism.c b/src/analysis/scan/patterns/backends/acism.c new file mode 100644 index 0000000..12339f2 --- /dev/null +++ b/src/analysis/scan/patterns/backends/acism.c @@ -0,0 +1,1295 @@ + +/* Chrysalide - Outil d'analyse de fichiers binaires + * acism.c - méthode de recherche basée sur l'algorithme Aho-Corasick Interleaved State-transition Matrix + * + * Copyright (C) 2022 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 "acism.h" + + +#include <assert.h> +#include <stdlib.h> +#include <string.h> + + +#include "acism-int.h" +#include "../../../../common/sort.h" + + + +/* ---------------------- IMPLANTATION D'UNE NOUVELLE APPROCHE ---------------------- */ + + +/* Initialise la classe des méthodes basée sur Bitmap. */ +static void g_acism_backend_class_init(GAcismBackendClass *); + +/* Initialise une instance de méthodes basée sur Bitmap. */ +static void g_acism_backend_init(GAcismBackend *); + +/* Supprime toutes les références externes. */ +static void g_acism_backend_dispose(GAcismBackend *); + +/* Procède à la libération totale de la mémoire. */ +static void g_acism_backend_finalize(GAcismBackend *); + + + +/* --------------------- IMPLEMENTATION DES FONCTIONS DE CLASSE --------------------- */ + + +/* Indique la taille maximale des suites d'octets recherchées. */ +size_t g_acism_backend_get_atom_max_size(const GAcismBackend *); + +/* Intègre un motif limité de contenu à rechercher. */ +static patid_t g_acism_backend_setup_for(GAcismBackend *, GScanContext *, const uint8_t *, size_t); + +/* Inscrit dans le moteur une chaîne de caractères à rechercher. */ +static patid_t g_acism_backend_enroll_plain_pattern(GAcismBackend *, GScanContext *, const uint8_t *, size_t); + +#ifdef __USE_BYTE_FREQ + +/* Compare un niveau de fréquence avec un autre. */ +static int compare_byte_frequencies(const acism_freq_rank_t *, const acism_freq_rank_t *); + +/* Détermine les identifiants de chaque valeur 8 bits utile. */ +static void g_acism_backend_define_codes(GAcismBackend *); + +#endif + +/* Construit l'arborescence de noeuds de lecture. */ +static void g_acism_backend_build_trie(GAcismBackend *); + +/* Construit l'arborescence de noeuds de lecture. */ +static void g_acism_backend_build_suffix_links(GAcismBackend *); + +#ifdef __SORT_BEFORE_BITMASK + +/* Compare des noeuds selon l'espace de codes couvert. */ +static int compare_node_according_to_code_range(const acism_trie_node_t **, const acism_trie_node_t **); + +#endif + +/* Organise la convertion de l'arborescence en tableau. */ +static void g_acism_backend_prepare_interleave_array(GAcismBackend *); + +/* Compresse l'arborescence dans un tableau de position. */ +static void g_acism_backend_build_interleave_array(GAcismBackend *); + +/* Met en ordre les derniers détails avant un premier scan. */ +static void g_acism_backend_warm_up(GAcismBackend *); + +/* Parcours un contenu binaire à la recherche de motifs. */ +static void g_acism_backend_run_scan(const GAcismBackend *, GScanContext *, GBinContent *); + +/* Affiche les caractéristques d'un noeud et de ses enfants. */ +static void visit_and_output_node(const acism_trie_node_t *, unsigned int); + +/* Imprime quelques faits quant aux éléments mis en place. */ +static void g_acism_backend_output_stats(const GAcismBackend *); + + + +/* ---------------------------------------------------------------------------------- */ +/* IMPLANTATION D'UNE NOUVELLE APPROCHE */ +/* ---------------------------------------------------------------------------------- */ + + +/* Indique le type défini pour un moteur de recherche pour données. */ +G_DEFINE_TYPE(GAcismBackend, g_acism_backend, G_TYPE_ENGINE_BACKEND); + + +/****************************************************************************** +* * +* Paramètres : klass = classe à initialiser. * +* * +* Description : Initialise la classe des méthodes basée sur Bitmap. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void g_acism_backend_class_init(GAcismBackendClass *klass) +{ + GObjectClass *object; /* Autre version de la classe */ + GEngineBackendClass *backend; /* Version de classe parente */ + + object = G_OBJECT_CLASS(klass); + + object->dispose = (GObjectFinalizeFunc/* ! */)g_acism_backend_dispose; + object->finalize = (GObjectFinalizeFunc)g_acism_backend_finalize; + + backend = G_ENGINE_BACKEND_CLASS(klass); + + backend->get_max_size = (get_backend_atom_max_size_fc)g_acism_backend_get_atom_max_size; + backend->enroll_plain = (enroll_plain_into_backend_fc)g_acism_backend_enroll_plain_pattern; + backend->warm_up = (warm_up_backend_fc)g_acism_backend_warm_up; + backend->run_scan = (run_backend_scan_fc)g_acism_backend_run_scan; + backend->output = (output_backend_stats_fc)g_acism_backend_output_stats; + +} + + +/****************************************************************************** +* * +* Paramètres : backend = instance à initialiser. * +* * +* Description : Initialise une instance de méthodes basée sur Bitmap. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void g_acism_backend_init(GAcismBackend *backend) +{ +#ifdef __USE_BYTE_FREQ + size_t i; /* Boucle de parcours #1 */ + acism_freq_rank_t *iter; /* Boucle de parcours #2 */ +#endif + +#ifdef __USE_BYTE_FREQ + memset(backend->codes_for_bytes, 0, 256 * sizeof(acism_code_t)); +#endif + + backend->nchars = 0; + +#ifdef __USE_BYTE_FREQ + for (i = 0, iter = backend->frequencies; i < 256; i++, iter++) + { + iter->frequency = 0; + iter->rank = i; + } +#endif + +} + + +/****************************************************************************** +* * +* Paramètres : backend = instance d'objet GLib à traiter. * +* * +* Description : Supprime toutes les références externes. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void g_acism_backend_dispose(GAcismBackend *backend) +{ + G_OBJECT_CLASS(g_acism_backend_parent_class)->dispose(G_OBJECT(backend)); + +} + + +/****************************************************************************** +* * +* Paramètres : backend = instance d'objet GLib à traiter. * +* * +* Description : Procède à la libération totale de la mémoire. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void g_acism_backend_finalize(GAcismBackend *backend) +{ + G_OBJECT_CLASS(g_acism_backend_parent_class)->finalize(G_OBJECT(backend)); + +} + + +/****************************************************************************** +* * +* Paramètres : - * +* * +* Description : Crée une méthode de recherche basée sur l'algorithme Acism. * +* * +* Retour : Méthode mise en place. * +* * +* Remarques : - * +* * +******************************************************************************/ + +GEngineBackend *g_acism_backend_new(void) +{ + GAcismBackend *result; /* Structure à retourner */ + + result = g_object_new(G_TYPE_ACISM_BACKEND, NULL); + + return G_ENGINE_BACKEND(result); + +} + + + +/* ---------------------------------------------------------------------------------- */ +/* IMPLEMENTATION DES FONCTIONS DE CLASSE */ +/* ---------------------------------------------------------------------------------- */ + + +/****************************************************************************** +* * +* Paramètres : backend = moteur de recherche à consulter. * +* * +* Description : Indique la taille maximale des suites d'octets recherchées. * +* * +* Retour : Valeur strictement positive. * +* * +* Remarques : - * +* * +******************************************************************************/ + +size_t g_acism_backend_get_atom_max_size(const GAcismBackend *backend) +{ + size_t result; /* Taille à faire connaître */ + + result = ACSIM_ATOM_SIZE; + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : backend = moteur de recherche à préparer. * +* context = contexte de l'analyse à mener. * +* plain = chaîne de caractères classique à intégrer. * +* len = taille de cette chaîne. * +* * +* Description : Intègre un motif limité de contenu à rechercher. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static patid_t g_acism_backend_setup_for(GAcismBackend *backend, GScanContext *context, const uint8_t *pattern, size_t len) +{ + patid_t result; /* Identifiant à retourner */ + size_t i; /* Boucle de parcours */ + int ret; /* Bilan d'une comparaison */ + acism_source_t *source; /* Définition à mémoriser */ + + result = INVALID_PATTERN_ID; + + /*Recherche d'un motif déjà sollicité */ + + /** + * '\x00\x00\x00\x00abcd1234' '\x01\x01\x01\x01abcd1234' peuvent en effet + * constituer deux cibles différentes, mais elles comportent normalement + * la même séquence atomique à rechercher : 'abcd1234'. + */ + + for (i = 0; i < backend->sources_count; i++) + { + source = backend->sources + i; + + if (source->len != len) + continue; + + ret = memcmp(source->atoms, pattern, len); + + if (ret == 0) + { + result = source->pid; + break; + } + + } + + /* Introduction d'un nouveau motif au besoin */ + + if (result == INVALID_PATTERN_ID) + { + backend->sources = realloc(backend->sources, ++backend->sources_count * sizeof(acism_source_t)); + + source = &backend->sources[backend->sources_count - 1]; + + source->atoms = pattern; + source->len = len; + + result = g_scan_context_get_new_pattern_id(context); + source->pid = result; + + backend->nchars += len; + +#ifdef __USE_BYTE_FREQ + for (i = 0; i < len; i++) + backend->frequencies[pattern[i]].frequency++; +#endif + + } + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : backend = moteur de recherche à manipuler. * +* context = contexte de l'analyse à mener. * +* plain = chaîne de caractères classique à intégrer. * +* len = taille de cette chaîne. * +* * +* Description : Inscrit dans le moteur une chaîne de caractères à rechercher.* +* * +* Retour : Bilan de l'opération. * +* * +* Remarques : - * +* * +******************************************************************************/ + +static patid_t g_acism_backend_enroll_plain_pattern(GAcismBackend *backend, GScanContext *context, const uint8_t *plain, size_t len) +{ + patid_t result; /* Identifiant à retourner */ + + assert(len <= ACSIM_ATOM_SIZE); + + /** + * Le traitement différé des chaînes à rechercher permet deux choses : + * - la construction d'une table de permutation ; + * - le décompte des noeuds à allouer (en une seule fois). + * + * Si l'intention du premier point est louable (densifier les champs de bits + * pour allouer moins et tenir plus facilement dans le cache du CPU), la + * permetutation est extrèmement coûteuse pendant la phase de scan + * (une lecture supplémentaire par octet de données scannées). + * + * Le second point reste valable (à priori). + * + * L'appel à la fonction g_acism_backend_setup_for() demeure donc, et l'arbre + * est construit dans un second temps. La distinction de cette fonction avec + * la procédure d'enrôlement permet potentiellement d'étuer une bascule à + * moindre coût un jour. + */ + + result = g_acism_backend_setup_for(backend, context, plain, len); + + return result; + +} + + +#ifdef __USE_BYTE_FREQ + + +/****************************************************************************** +* * +* Paramètres : a = premier élément à comparer. * +* b = second élément à comparer. * +* * +* Description : Compare un niveau de fréquence avec un autre. * +* * +* Retour : Bilan de la comparaison. * +* * +* Remarques : - * +* * +******************************************************************************/ + +static int compare_byte_frequencies(const acism_freq_rank_t *a, const acism_freq_rank_t *b) +{ + int result; /* Bilan à retourner */ + + /** + * Afin d'obtenir les plus grosses fréquences en premier, + * l'ordre de comparaison est inversé : b < a ? + */ + + result = sort_unsigned_long(b->frequency, a->frequency); + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : backend = moteur de recherche à préparer. * +* * +* Description : Détermine les identifiants de chaque valeur 8 bits utile. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void g_acism_backend_define_codes(GAcismBackend *backend) +{ + size_t i; /* Boucle de parcours #1 */ + acism_freq_rank_t *iter; /* Boucle de parcours #2 */ + + /** + * La redistribution des valeurs d'octet va permettre de compacter + * par la suite les masques de cellules utilisées pour construire + * le plus petit tableau des états. + * + * L'idée est de grouper le plus possible les états (représentés + * par un indice) autour de l'état 0. + */ + + qsort(backend->frequencies, 256, sizeof(acism_freq_rank_t), (__compar_fn_t)compare_byte_frequencies); + + /* 0 == racine */ + backend->codes_count++; + +#if 0 + for (i = 0, iter = backend->frequencies; i < 256; i++, iter++) + { + if (iter->frequency == 0) + break; + + backend->codes_for_bytes[iter->rank] = backend->codes_count++; + + } +#else + for (i = 0; i < 256; i++) + backend->codes_for_bytes[i] = backend->codes_count++; +#endif + +} + + +#endif + + +/****************************************************************************** +* * +* Paramètres : backend = moteur de recherche à préparer. * +* * +* Description : Construit l'arborescence de noeuds de lecture. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void g_acism_backend_build_trie(GAcismBackend *backend) +{ + size_t i; /* Boucle de parcours #1 */ + acism_trie_node_t *next; /* Prochain noeud disponible */ + acism_trie_node_t *node; /* Tête de parcours */ + acism_source_t *source; /* Définition à mémoriser */ + size_t k; /* Boucle de parcours #2 */ + acism_code_t code; /* Identifiant de symbole */ + acism_trie_node_t *parent; /* Sauvegarde d'un accès */ + + backend->nodes = calloc(backend->nchars + 1, sizeof(acism_trie_node_t)); + + for (i = 0; i < (backend->nchars + 1); i++) + { + backend->nodes[i].min_child_code = MAX_ACISM_CODE; + backend->nodes[i].max_child_code = MIN_ACISM_CODE; + } + + next = backend->nodes + 1; + + for (i = 0; i < backend->sources_count; i++) + { + node = backend->nodes; + + source = &backend->sources[i]; + + for (k = 0; k < source->len && node->child != NULL; k++) + { +#ifdef __USE_BYTE_FREQ + code = backend->codes_for_bytes[source->atoms[k]]; +#else + code = 1 + source->atoms[k]; +#endif + + /* Insertion d'un nouveau noeud au début des enfants */ + if (code < node->child->code) + { + next->parent = node; + next->suffix_link = node; + next->data = source->atoms[k]; + next->code = code; + + next->sibling = node->child; + node->child = next++; + + if (code < node->min_child_code) node->min_child_code = code; + if (code > node->max_child_code) node->max_child_code = code; + node->children_count++; + + node = node->child; + + k++; + break; + + } + + parent = node; + + /* Recherche du point d'insertion idéal */ + for (node = node->child; + node->sibling != NULL && code >= node->sibling->code; + node = node->sibling); + + /* Si le noeud idéal n'existe pas, insertion ordonnée */ + if (code > node->code) + { + next->parent = parent; + next->suffix_link = parent; + next->data = source->atoms[k]; + next->code = code; + + next->sibling = node->sibling; + node->sibling = next++; + + if (code < parent->min_child_code) parent->min_child_code = code; + if (code > parent->max_child_code) parent->max_child_code = code; + parent->children_count++; + + node = node->sibling; + + k++; + break; + + } + + } + + /* Creéation d'une nouvelle branche avec le reliquat */ + for (; k < source->len; k++) + { +#ifdef __USE_BYTE_FREQ + code = backend->codes_for_bytes[source->atoms[k]]; +#else + code = 1 + source->atoms[k]; +#endif + + next->parent = node; + next->suffix_link = node; + next->data = source->atoms[k]; + next->code = code; + + node->child = next++; + + if (code < node->min_child_code) node->min_child_code = code; + if (code > node->max_child_code) node->max_child_code = code; + node->children_count++; + + node = node->child; + + } + + node->matched_atom = i + 1; + + } + + backend->nodes_used = next - backend->nodes; + +} + + +/****************************************************************************** +* * +* Paramètres : backend = moteur de recherche à préparer. * +* * +* Description : Construit l'arborescence de noeuds de lecture. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void g_acism_backend_build_suffix_links(GAcismBackend *backend) +{ + size_t max_pos; /* Tête de lecture finale */ + acism_trie_node_t **stack; /* Pile des noeuds à traiter */ + size_t rd_pos; /* Tête de lecture */ + size_t wr_pos; /* Tête d'écriture */ + acism_trie_node_t *node; /* Noeud à traiter */ + acism_trie_node_t *parent; /* Noeud parent de la chaîne */ + acism_trie_node_t *iter; /* Boucle de parcours */ + + max_pos = backend->nodes_used; + + stack = calloc(max_pos, sizeof(acism_trie_node_t *)); + + /* Initialisation du parcours */ + + rd_pos = 0; + wr_pos = 0; + + stack[wr_pos++] = &backend->nodes[0]; + + assert(backend->nodes->sibling == NULL); + + /* Traitement manuel de démarrage pour éviter une condition en [0] */ + + for (iter = backend->nodes->child; iter != NULL; iter = iter->sibling) + stack[wr_pos++] = iter; + + rd_pos++; + + /* Suivi des liens déjà en place */ + + while (rd_pos < max_pos) + { + assert(rd_pos < wr_pos); + + node = stack[rd_pos++]; + + /* Remontée jusqu'à la découverte d'un lien d'intérêt */ + + for (parent = node->suffix_link; parent != NULL; parent = parent->suffix_link) + { + for (iter = parent->child; iter != NULL; iter = iter->sibling) + if (iter->code == node->code && iter != node) + { + node->suffix_link = iter; + break; + } + + if (iter != NULL) + break; + + } + + if (parent == NULL /* && node != &backend->nodes [0] */) + node->suffix_link = backend->nodes; + + /* Inscription des noeuds suivants */ + + for (iter = node->child; iter != NULL; iter = iter->sibling) + stack[wr_pos++] = iter; + + } + + /* Sortie propre */ + + free(stack); + +} + + +#ifdef __SORT_BEFORE_BITMASK + + +/****************************************************************************** +* * +* Paramètres : a = premier élément à comparer. * +* b = second élément à comparer. * +* * +* Description : Compare des noeuds selon l'espace de codes couvert. * +* * +* Retour : Bilan de la comparaison. * +* * +* Remarques : - * +* * +******************************************************************************/ + +static int compare_node_according_to_code_range(const acism_trie_node_t **a, const acism_trie_node_t **b) +{ + int result; /* Bilan à retourner */ + const acism_trie_node_t *_a; /* Autre vision de l'élément #1*/ + const acism_trie_node_t *_b; /* Autre vision de l'élément #1*/ + acism_code_t range_a; /* Espacement des codes #1 */ + acism_code_t range_b; /* Espacement des codes #2 */ + + result = 0; + + _a = *a; + _b = *b; + + if (_a->child == NULL) + result = (_b->child == NULL ? 0 : 1); + + else if (_b->child == NULL) + result = (_a->child == NULL ? 0 : -1); + + else + { + assert(_a->min_child_code <= _a->max_child_code); + range_a = _a->max_child_code - _a->min_child_code; + + assert(_b->min_child_code <= _b->max_child_code); + range_b = _b->max_child_code - _b->min_child_code; + + result = sort_unsigned_long(range_b, range_a); + + if (result == 0) + result = sort_unsigned_long(_b->children_count, _a->children_count); + + + + + } + + return result; + +} + + +#endif + + +#if 1 + + +/****************************************************************************** +* * +* Paramètres : backend = moteur de recherche à préparer. * +* * +* Description : Organise la convertion de l'arborescence en tableau. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void g_acism_backend_prepare_interleave_array(GAcismBackend *backend) +{ +#ifdef __SORT_BEFORE_BITMASK + acism_trie_node_t **list; /* Liste de noeuds alloués */ +#endif + size_t i; /* Boucle de parcours #1 */ + size_t last_free_state; /* Dernier emplacement dispo. */ + size_t full_size; /* Cartographie entière */ + bitfield_t *global_usage; /* Cartographie des usages */ + bitfield_t *usage; /* Cartographie locale */ + acism_trie_node_t *node; /* Noeud en cours de traitement*/ + acism_trie_node_t *iter; /* Boucle de parcours #2 */ + size_t free_state; /* Emplacement libre trouvé */ + bool found; /* Bilan de recherche */ + + size_t bsum; + + /* Préparation de la liste de noeuds à inscrire */ + +#ifdef __SORT_BEFORE_BITMASK + + list = calloc(backend->nodes_used, sizeof(acism_trie_node_t *)); + + for (i = 0; i < backend->nodes_used; i++) + list[i] = backend->nodes + i; + + qsort(list + 1, backend->nodes_used - 1, sizeof(acism_trie_node_t *), + (__compar_fn_t)compare_node_according_to_code_range); + +#endif + + /* Insertion des noeuds dans l'ordre prévu */ + + last_free_state = 257; + full_size = last_free_state + 257; + global_usage = create_bit_field(full_size, false); + + bsum = 0; + + usage = create_bit_field(257, false); + + for (i = 0; i < backend->nodes_used; i++) + { +#ifdef __SORT_BEFORE_BITMASK + node = list[i]; +#else + node = backend->nodes + i; +#endif + + /* Préparation du masque du noeud */ + + reset_all_in_bit_field(usage); + + set_in_bit_field(usage, 0, 1); + + for (iter = node->child; iter != NULL; iter = iter->sibling) + set_in_bit_field(usage, iter->code, 1); + + assert(popcount_for_bit_field(usage) == (node->children_count + 1)); + + /* Recherche d'une position idéale */ + + if (i == 0) + free_state = 0; + + else + for (free_state = 1; free_state < last_free_state; free_state++) + { + found = test_zeros_within_bit_field(global_usage, free_state, usage); + if (found) break; + } + + /* Suivi global */ + + assert(!test_in_bit_field(global_usage, free_state)); + + or_bit_field_at(global_usage, usage, free_state); + + bsum += node->children_count + 1; + assert(popcount_for_bit_field(global_usage) == bsum); + + node->state_index = free_state; + + if ((free_state + 257) > last_free_state) + { + last_free_state += 257; + full_size += 257; + resize_bit_field(&global_usage, full_size); + } + + } + + /* Sotie encadrée */ + + backend->bitmap_usage = global_usage; + + delete_bit_field(usage); + +#ifdef __SORT_BEFORE_BITMASK + free(list); +#endif + +} + + +#else + + +/****************************************************************************** +* * +* Paramètres : backend = moteur de recherche à préparer. * +* * +* Description : Organise la convertion de l'arborescence en tableau. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void g_acism_backend_prepare_interleave_array(GAcismBackend *backend) +{ + size_t max_pos; /* Tête de lecture finale */ + acism_trie_node_t **stack; /* Pile des noeuds à traiter */ + size_t last_free_state; /* Dernier emplacement dispo. */ + size_t full_size; /* Cartographie entière */ + bitfield_t *global_usage; /* Cartographie des usages */ + bitfield_t *usage; /* Cartographie locale */ + size_t rd_pos; /* Tête de lecture */ + size_t wr_pos; /* Tête d'écriture */ + acism_trie_node_t *node; /* Noeud à traiter */ + acism_trie_node_t *iter; /* Boucle de parcours */ + size_t free_state; /* Emplacement libre trouvé */ + bool found; /* Bilan de recherche */ + + max_pos = backend->nodes_used; + + stack = calloc(max_pos, sizeof(acism_trie_node_t *)); + + last_free_state = 257; + full_size = last_free_state + 257; + global_usage = create_bit_field(full_size, false); + + usage = create_bit_field(257, false); + + /* Initialisation du parcours */ + + rd_pos = 0; + wr_pos = 0; + + stack[wr_pos++] = &backend->nodes[0]; + + assert(backend->nodes->sibling == NULL); + + /* Traitement manuel de démarrage pour éviter une condition en [0] */ + + set_in_bit_field(global_usage, 0, 1); + + for (iter = backend->nodes->child; iter != NULL; iter = iter->sibling) + { + set_in_bit_field(global_usage, iter->code, 1); + stack[wr_pos++] = iter; + } + + rd_pos++; + + /* Suivi des liens déjà en place */ + + while (rd_pos < max_pos) + { + assert(rd_pos < wr_pos); + + node = stack[rd_pos++]; + + /* Préparation du masque du noeud et inscription des noeuds suivants */ + + reset_all_in_bit_field(usage); + + set_in_bit_field(usage, 0, 1); + + for (iter = node->child; iter != NULL; iter = iter->sibling) + { + set_in_bit_field(usage, iter->code, 1); + stack[wr_pos++] = iter; + } + + assert(popcount_for_bit_field(usage) == (node->children_count + 1)); + + /* Recherche d'une position idéale */ + + for (free_state = 1; free_state < last_free_state; free_state++) + { + found = test_zeros_within_bit_field(global_usage, free_state, usage); + if (found) break; + } + + /* Suivi global */ + + assert(!test_in_bit_field(global_usage, free_state)); + + or_bit_field_at(global_usage, usage, free_state); + + node->state_index = free_state; + + if ((free_state + 257) > last_free_state) + { + last_free_state += 257; + full_size += 257; + resize_bit_field(&global_usage, full_size); + } + + } + + /* Sotie encadrée */ + + backend->bitmap_usage = global_usage; + + delete_bit_field(usage); + + free(stack); + +} + + +#endif + + +/****************************************************************************** +* * +* Paramètres : backend = moteur de recherche à préparer. * +* * +* Description : Compresse l'arborescence dans un tableau de position. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void g_acism_backend_build_interleave_array(GAcismBackend *backend) +{ + size_t maxsize; /* Taille maximale du tableau */ + size_t i; /* Boucle de parcours #1 */ + acism_trie_node_t *node; /* Noeud à transcrire */ + acism_state_t *base; /* Base d'une série de cellules*/ + acism_trie_node_t *iter; /* Sous-noeud à inscrire #2 */ + acism_trie_node_t *child; /* Sous-noeud à inscrire #3 */ + uint16_t offset; /* Décalage local */ + + maxsize = get_bit_field_size(backend->bitmap_usage); + + backend->states = calloc(maxsize, sizeof(acism_state_t)); + backend->pids = calloc(maxsize, sizeof(patid_t)); + + for (i = 0; i < backend->nodes_used; i++) + { + node = &backend->nodes[i]; + base = backend->states + node->state_index; + + assert(base[0].code == 0); + assert(base[0].index == 0); + + if (node->matched_atom > 0) + { + base[0].match = 1; + base[0].atom_size = backend->sources[node->matched_atom - 1].len; + + backend->pids[node->state_index] = backend->sources[node->matched_atom - 1].pid; + + for (iter = node->parent->suffix_link; iter != NULL; iter = iter->suffix_link) + { + for (child = iter->child; child != NULL; child = child->sibling) + if (child->code == node->code && child->matched_atom > 0) + break; + + if (child != NULL) + { + base[0].suffix = 1; + break; + } + + } + + } + base[0].index = i == 0 ? 0 : node->suffix_link->state_index; + + for (child = node->child; child != NULL; child = child->sibling) + { + offset = child->code; + + assert(base[offset].code == 0); + assert(base[offset].index == 0); + + base[offset].code = child->code; + base[offset].index = child->state_index; + + } + + } + +} + + +/****************************************************************************** +* * +* Paramètres : backend = moteur de recherche à préparer. * +* * +* Description : Met en ordre les derniers détails avant un premier scan. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void g_acism_backend_warm_up(GAcismBackend *backend) +{ +#ifdef __USE_BYTE_FREQ + + /** + * Attribue un identifiant unique pour chaque octet présent dans les + * motifs recherchés. + */ + g_acism_backend_define_codes(backend); + +#endif + + /** + * Construit une arborescence de lecture à partir des différents + * octets présents dans les motifs. + */ + g_acism_backend_build_trie(backend); + + /** + * Met en place les liens suivis en cas d'échec de correspondance + * lors de la lecture d'un octet supplémentaire. + */ + g_acism_backend_build_suffix_links(backend); + + /** + * Conversion de l'arborescence en tableau plat et compressé. + */ + + g_acism_backend_prepare_interleave_array(backend); + + g_acism_backend_build_interleave_array(backend); + +} + + +/****************************************************************************** +* * +* Paramètres : backend = moteur de recherche à manipuler. * +* context = lieu d'enregistrement des résultats. * +* content = données binaires à analyser. * +* * +* Description : Parcours un contenu binaire à la recherche de motifs. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void g_acism_backend_run_scan(const GAcismBackend *backend, GScanContext *context, GBinContent *content) +{ + phys_t dlen; /* Quantité de données */ + vmpa2t pos; /* Point de départ ciblé */ + const bin_t *data; /* Données à analyser */ +#ifdef __USE_BYTE_FREQ + acism_code_t *codes_for_bytes; +#endif + acism_state_t *root; /* Racine de l'arborescence */ + acism_state_t *state; /* Tête de lecture courante */ + phys_t i; /* Boucle de parcours #1 */ + acism_code_t code; /* Code du caractère courant */ + acism_state_t *next; /* Prochaine tête à valider */ + acism_state_t *iter; /* Boucle de parcours #2 */ + acism_state_t *test; /* Test de validité alternative*/ + + dlen = g_binary_content_compute_size(content); + + g_binary_content_compute_start_pos(content, &pos); + data = g_binary_content_get_raw_access(content, &pos, dlen); + + /* Suivi via l'arborescence aplatie */ + +#ifdef __USE_BYTE_FREQ + codes_for_bytes = backend->codes_for_bytes; +#endif + + root = backend->states; + + state = root; + + for (i = 0; i < dlen; i++) + { +#ifdef __USE_BYTE_FREQ + code = 1 + codes_for_bytes[data[i]]; +#else + code = 1 + data[i]; +#endif + + /* Déplacement de la tête de lecture dans l'arborescence */ + + retry: + + next = state + code; + + if (next->code == code) + next = root + next->index; + + else if (state != root) + { + state = root + state->index; + goto retry; + } + + else + continue; + + /* Remontée d'éventuels résultats */ + + if (next->match) + { + g_scan_context_register_atom_match(context, + backend->pids[next - root], + i + 1 - next->atom_size); + + if (next->suffix) + { + for (iter = root + state->index; ; iter = root + iter->index) + { + test = iter + code; + + if (test->code == code) + { + test = root + test->index; + + if (test->match) + { + assert(test->atom_size < next->atom_size); + + g_scan_context_register_atom_match(context, + backend->pids[test - root], + i + 1 - test->atom_size); + + } + + } + + if (iter == root) + break; + + } + + } + + + } + + /* Bascule au caractère suivant */ + + state = next; + + } + +} + + +/****************************************************************************** +* * +* Paramètres : node = noeud d'arborescence à traiter. * +* level = profondeur courante. * +* * +* Description : Affiche les caractéristques d'un noeud et de ses enfants. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void visit_and_output_node(const acism_trie_node_t *node, unsigned int level) +{ + unsigned int i; /* Boucle de parcours #1 */ + acism_trie_node_t *iter; /* Boucle de parcours #2 */ + + for (i = 0; i < level; i++) + printf(" "); + + printf(" '%c' (code=%hhu)\n", node->data, node->code); + + for (iter = node->child; iter != NULL; iter = iter->sibling) + visit_and_output_node(iter, level + 1); + +} + + +/****************************************************************************** +* * +* Paramètres : backend = moteur de recherche à consulter. * +* * +* Description : Imprime quelques faits quant aux éléments mis en place. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void g_acism_backend_output_stats(const GAcismBackend *backend) +{ + printf("nodes used: %zu\n", backend->nodes_used); + + printf("full_size: %zu (real: %zu)\n", + get_bit_field_size(backend->bitmap_usage), + popcount_for_bit_field(backend->bitmap_usage)); + + visit_and_output_node(backend->nodes, 0); + +} diff --git a/src/analysis/scan/patterns/backends/acism.h b/src/analysis/scan/patterns/backends/acism.h new file mode 100644 index 0000000..837022a --- /dev/null +++ b/src/analysis/scan/patterns/backends/acism.h @@ -0,0 +1,59 @@ + +/* Chrysalide - Outil d'analyse de fichiers binaires + * acism.h - prototypes pour la méthode de recherche basée sur l'algorithme Aho-Corasick Interleaved State-transition Matrix + * + * Copyright (C) 2022 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/>. + */ + + +#ifndef _ANALYSIS_SCAN_PATTERNS_BACKENDS_ACISM_H +#define _ANALYSIS_SCAN_PATTERNS_BACKENDS_ACISM_H + + +#include <glib-object.h> +#include <stdbool.h> + + +#include "../backend.h" + + + +#define G_TYPE_ACISM_BACKEND g_acism_backend_get_type() +#define G_ACISM_BACKEND(obj) (G_TYPE_CHECK_INSTANCE_CAST((obj), G_TYPE_ACISM_BACKEND, GAcismBackend)) +#define G_IS_ACISM_BACKEND(obj) (G_TYPE_CHECK_INSTANCE_TYPE((obj), G_TYPE_ACISM_BACKEND)) +#define G_ACISM_BACKEND_CLASS(klass) (G_TYPE_CHECK_CLASS_CAST((klass), G_TYPE_ACISM_BACKEND, GAcismBackendClass)) +#define G_IS_ACISM_BACKEND_CLASS(klass) (G_TYPE_CHECK_CLASS_TYPE((klass), G_TYPE_ACISM_BACKEND)) +#define G_ACISM_BACKEND_GET_CLASS(obj) (G_TYPE_INSTANCE_GET_CLASS((obj), G_TYPE_ACISM_BACKEND, GAcismBackendClass)) + + +/* Méthode de recherche basée sur l'algorithme Acism (instance) */ +typedef struct _GAcismBackend GAcismBackend; + +/* Méthode de recherche basée sur l'algorithme Acism (classe) */ +typedef struct _GAcismBackendClass GAcismBackendClass; + + +/* Indique le type défini pour un moteur de recherche pour données. */ +GType g_acism_backend_get_type(void); + +/* Crée une méthode de recherche basée sur l'algorithme Acism. */ +GEngineBackend *g_acism_backend_new(void); + + + +#endif /* _ANALYSIS_SCAN_PATTERNS_BACKENDS_ACISM_H */ diff --git a/src/analysis/scan/patterns/backends/bitap-int.h b/src/analysis/scan/patterns/backends/bitap-int.h new file mode 100644 index 0000000..83ecc17 --- /dev/null +++ b/src/analysis/scan/patterns/backends/bitap-int.h @@ -0,0 +1,118 @@ + +/* Chrysalide - Outil d'analyse de fichiers binaires + * bitap-int.h - prototypes internes pour la méthode de recherche basée sur l'algorithme Bitap + * + * Copyright (C) 2022 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/>. + */ + + +#ifndef _ANALYSIS_SCAN_PATTERNS_BACKENDS_BITAP_INT_H +#define _ANALYSIS_SCAN_PATTERNS_BACKENDS_BITAP_INT_H + + +#include "bitap.h" + + +#include <immintrin.h> + + +#include "../backend-int.h" +#include "../../../../common/cpu.h" + + + +#define BITAP_ATOM_SIZE 7 + + +/* Suivi d'un groupe de chaînes */ +typedef struct _grouped_strings_avx2_t +{ + __m256i pattern_masks[256]; /* Programmation de détections */ + __m256i found_masks; /* Masques multiples d'alerte */ + + __m256i R; /* Résultats courants */ + + size_t m[32]; /* Taille des chaînes */ + + patid_t found_id[32]; /* Indice des résultats */ + + size_t available; /* Nombre de places disponibles*/ + size_t used; /* Quantité de places utilisées*/ + +} grouped_strings_avx2_t; + +/* Suivi de l'ensemble de chaînes */ +typedef struct _group_manager_avx2_t +{ + grouped_strings_avx2_t **strings_8; /* Chaînes de taille 8 max */ + size_t count_8; /* Quantité de ces chaînes */ + +} group_manager_avx2_t; + + +/* Suivi d'un groupe de chaînes */ +typedef struct _grouped_strings_avx512_t +{ + __m512i pattern_masks[256]; /* Programmation de détections */ + __m512i found_masks; /* Masques multiples d'alerte */ + + __m512i R; /* Résultats courants */ + + size_t m[64]; /* Taille des chaînes */ + + patid_t found_id[64]; /* Indice des résultats */ + + size_t used; /* Quantité de places utilisées*/ + size_t available; /* Nombre de places disponibles*/ + +} grouped_strings_avx512_t; + +/* Suivi de l'ensemble de chaînes */ +typedef struct _group_manager_avx512_t +{ + grouped_strings_avx512_t **strings_8; /* Chaînes de taille 8 max */ + size_t count_8; /* Quantité de ces chaînes */ + +} group_manager_avx512_t; + + +/* Méthode de recherche basée sur l'algorithme Bitap (instance) */ +struct _GBitapBackend +{ + GEngineBackend parent; /* A laisser en premier */ + + CPUSMIDFeature optimization; /* Mode de calculs */ + + union + { + group_manager_avx2_t manager_avx2; /* Gestionnaire pour AVX2 */ + group_manager_avx512_t manager_avx512;/* Gestionnaire pour AVX-512 */ + }; + +}; + +/* Méthode de recherche basée sur l'algorithme Bitap (classe) */ +struct _GBitapBackendClass +{ + GEngineBackendClass parent; /* A laisser en premier */ + +}; + + + +#endif /* _ANALYSIS_SCAN_PATTERNS_BACKENDS_BITAP_INT_H */ diff --git a/src/analysis/scan/patterns/backends/bitap.c b/src/analysis/scan/patterns/backends/bitap.c new file mode 100644 index 0000000..bd80fb0 --- /dev/null +++ b/src/analysis/scan/patterns/backends/bitap.c @@ -0,0 +1,2766 @@ + +/* Chrysalide - Outil d'analyse de fichiers binaires + * bitap.c - méthode de recherche basée sur l'algorithme Bitap + * + * Copyright (C) 2022 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 "bitap.h" + + +#include <alloca.h> +#include <assert.h> +#include <sys/mman.h> +#include <sched.h> + + +#include "bitap-int.h" +#include "../../../../core/logs.h" +//#include "../../matches/bytes.h" + + + +/* ---------------------- IMPLANTATION D'UNE NOUVELLE APPROCHE ---------------------- */ + + +/* Initialise la classe des méthodes basée sur Bitmap. */ +static void g_bitap_backend_class_init(GBitapBackendClass *); + +/* Initialise une instance de méthodes basée sur Bitmap. */ +static void g_bitap_backend_init(GBitapBackend *); + +/* Supprime toutes les références externes. */ +static void g_bitap_backend_dispose(GBitapBackend *); + +/* Procède à la libération totale de la mémoire. */ +static void g_bitap_backend_finalize(GBitapBackend *); + + + +/* --------------------- IMPLEMENTATION DES FONCTIONS DE CLASSE --------------------- */ + + +/* Indique la taille maximale des suites d'octets recherchées. */ +size_t g_bitap_backend_get_atom_max_size(const GBitapBackend *); + +/* Inscrit dans le moteur une chaîne de caractères à rechercher. */ +static patid_t g_bitap_backend_enroll_plain_pattern(GBitapBackend *, GScanContext *, const uint8_t *, size_t); + +/* Parcours un contenu binaire à la recherche de motifs. */ +static void g_bitap_backend_run_scan(const GBitapBackend *, GScanContext *, GBinContent *); + +/* Imprime quelques faits quant aux éléments mis en place. */ +static void g_bitap_backend_output_stats(const GBitapBackend *); + + + +/* ---------------------- OPTIMISATIONS POUR ARCHITECTURE AVX2 ---------------------- */ + + +/* Indique la valeur portée par une expression rationnelle. */ +static void extend_grouped_strings_avx2(grouped_strings_avx2_t ***, size_t *); + +/* Inscrit dans le moteur une chaîne de caractères à rechercher. */ +static patid_t enroll_plain_pattern_avx2(GBitapBackend *, GScanContext *, const bin_t *, size_t); + +/* Parcours un contenu binaire à la recherche de motifs. */ +static void run_scan_avx2(const GBitapBackend *, GScanContext *, GBinContent *); + + + + + +/* --------------------- OPTIMISATIONS POUR ARCHITECTURE AVX512 --------------------- */ + + +/* Indique la valeur portée par une expression rationnelle. */ +static void extend_grouped_strings_avx512(grouped_strings_avx512_t ***, size_t *); + +/* Inscrit dans le moteur une chaîne de caractères à rechercher. */ +static patid_t enroll_plain_pattern_avx512(GBitapBackend *, GScanContext *, const bin_t *, size_t); + +/* Parcours un contenu binaire à la recherche de motifs. */ +static void run_scan_avx512(const GBitapBackend *, GScanContext *, GBinContent *); + + + + + +/* ---------------------------------------------------------------------------------- */ +/* IMPLANTATION D'UNE NOUVELLE APPROCHE */ +/* ---------------------------------------------------------------------------------- */ + + +/* Indique le type défini pour un moteur de recherche pour données. */ +G_DEFINE_TYPE(GBitapBackend, g_bitap_backend, G_TYPE_ENGINE_BACKEND); + + +/****************************************************************************** +* * +* Paramètres : klass = classe à initialiser. * +* * +* Description : Initialise la classe des méthodes basée sur Bitmap. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void g_bitap_backend_class_init(GBitapBackendClass *klass) +{ + GObjectClass *object; /* Autre version de la classe */ + GEngineBackendClass *backend; /* Version de classe parente */ + + object = G_OBJECT_CLASS(klass); + + object->dispose = (GObjectFinalizeFunc/* ! */)g_bitap_backend_dispose; + object->finalize = (GObjectFinalizeFunc)g_bitap_backend_finalize; + + backend = G_ENGINE_BACKEND_CLASS(klass); + + backend->get_max_size = (get_backend_atom_max_size_fc)g_bitap_backend_get_atom_max_size; + backend->enroll_plain = (enroll_plain_into_backend_fc)g_bitap_backend_enroll_plain_pattern; + backend->run_scan = (run_backend_scan_fc)g_bitap_backend_run_scan; + backend->output = (output_backend_stats_fc)g_bitap_backend_output_stats; + +} + + +/****************************************************************************** +* * +* Paramètres : backend = instance à initialiser. * +* * +* Description : Initialise une instance de méthodes basée sur Bitmap. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void g_bitap_backend_init(GBitapBackend *backend) +{ + +} + + +/****************************************************************************** +* * +* Paramètres : backend = instance d'objet GLib à traiter. * +* * +* Description : Supprime toutes les références externes. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void g_bitap_backend_dispose(GBitapBackend *backend) +{ + G_OBJECT_CLASS(g_bitap_backend_parent_class)->dispose(G_OBJECT(backend)); + +} + + +/****************************************************************************** +* * +* Paramètres : backend = instance d'objet GLib à traiter. * +* * +* Description : Procède à la libération totale de la mémoire. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void g_bitap_backend_finalize(GBitapBackend *backend) +{ + G_OBJECT_CLASS(g_bitap_backend_parent_class)->finalize(G_OBJECT(backend)); + +} + + +/****************************************************************************** +* * +* Paramètres : - * +* * +* Description : Crée une méthode de recherche basée sur l'algorithme Bitap. * +* * +* Retour : Méthode mise en place. * +* * +* Remarques : - * +* * +******************************************************************************/ + +GEngineBackend *g_bitap_backend_new(void) +{ + GBitapBackend *result; /* Structure à retourner */ + + result = g_object_new(G_TYPE_BITAP_BACKEND, NULL); + + return G_ENGINE_BACKEND(result); + +} + + + +/* ---------------------------------------------------------------------------------- */ +/* IMPLEMENTATION DES FONCTIONS DE CLASSE */ +/* ---------------------------------------------------------------------------------- */ + + +/****************************************************************************** +* * +* Paramètres : backend = moteur de recherche à consulter. * +* * +* Description : Indique la taille maximale des suites d'octets recherchées. * +* * +* Retour : Valeur strictement positive. * +* * +* Remarques : - * +* * +******************************************************************************/ + +size_t g_bitap_backend_get_atom_max_size(const GBitapBackend *backend) +{ + size_t result; /* Taille à faire connaître */ + + result = BITAP_ATOM_SIZE; + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : backend = moteur de recherche à manipuler. * +* context = contexte de l'analyse à mener. * +* plain = chaîne de caractères classique à intégrer. * +* len = taille de cette chaîne. * +* * +* Description : Inscrit dans le moteur une chaîne de caractères à rechercher.* +* * +* Retour : Bilan de l'opération. * +* * +* Remarques : - * +* * +******************************************************************************/ + +static patid_t g_bitap_backend_enroll_plain_pattern(GBitapBackend *backend, GScanContext *context, const uint8_t *plain, size_t len) +{ + patid_t result; /* Identifiant à retourner */ + + + + result = INVALID_PATTERN_ID; + + + + + if (0) + + result = enroll_plain_pattern_avx2(backend, context, plain, len); + + else + + result = enroll_plain_pattern_avx512(backend, context, plain, len); + + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : backend = moteur de recherche à manipuler. * +* context = lieu d'enregistrement des résultats. * +* content = données binaires à analyser. * +* * +* Description : Parcours un contenu binaire à la recherche de motifs. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void g_bitap_backend_run_scan(const GBitapBackend *backend, GScanContext *context, GBinContent *content) +{ + cpu_set_t old_mask; /* Cartographie des CPU #1 */ + int ret; /* Bilan d'un appel */ + unsigned int cpu; /* Processeur courant */ + cpu_set_t new_mask; /* Cartographie des CPU #2 */ + + ret = sched_getaffinity(0, sizeof(cpu_set_t), &old_mask); + + if (ret != 0) + { + LOG_ERROR_N("sched_getaffinity"); + goto exit; + } + + ret = getcpu(&cpu, NULL); + + if (ret != 0) + { + LOG_ERROR_N("get_cpu"); + goto exit; + } + + CPU_ZERO(&new_mask); + CPU_SET(cpu, &new_mask); + + ret = sched_setaffinity(0, sizeof(cpu_set_t), &new_mask); + + if (ret != 0) + { + LOG_ERROR_N("sched_setaffinity"); + goto exit; + } + + + + if (0) + + run_scan_avx2(backend, context, content); + + else + + run_scan_avx512(backend, context, content); + + + exit: + + ; + +} + + +/****************************************************************************** +* * +* Paramètres : backend = moteur de recherche à consulter. * +* * +* Description : Imprime quelques faits quant aux éléments mis en place. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void g_bitap_backend_output_stats(const GBitapBackend *backend) +{ + printf("hello here!\n"); + +} + + + +/* ---------------------------------------------------------------------------------- */ +/* OPTIMISATIONS POUR ARCHITECTURE AVX2 */ +/* ---------------------------------------------------------------------------------- */ + + +/** + * Cf. https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html#techs=AVX,AVX2 + */ + + +/****************************************************************************** +* * +* Paramètres : strings = ensemble de groupes constitués. [OUT] * +* count = nombre de groupes courant. [OUT] * +* * +* Description : Indique la valeur portée par une expression rationnelle. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void extend_grouped_strings_avx2(grouped_strings_avx2_t ***strings, size_t *count) +{ + grouped_strings_avx2_t *new; /* Zone supplémentaire */ + size_t i; /* Boucle de parcours */ + + /* Définition d'un nouvel élément vierge */ + + new = aligned_alloc(256, sizeof(grouped_strings_avx2_t)); + + for (i = 0; i < 256; i++) + new->pattern_masks[i] = _mm256_set1_epi8(~0); + + new->found_masks = _mm256_set1_epi8(~0); + + new->R = _mm256_set1_epi8(~1); + + for (i = 0; i < 32; i++) + { + new->m[i] = 0; + + new->found_id[i] = INVALID_PATTERN_ID; + + } + + new->available = 32; + new->used = 0; + + /* Inscription */ + + *strings = realloc(*strings, ++(*count) * sizeof(grouped_strings_avx2_t *)); + + (*strings)[*count - 1] = new; + +} + + +/****************************************************************************** +* * +* Paramètres : backend = moteur de recherche à manipuler. * +* context = contexte de l'analyse à mener. * +* plain = chaîne de caractères classique à intégrer. * +* plen = taille de cette chaîne. * +* * +* Description : Inscrit dans le moteur une chaîne de caractères à rechercher.* +* * +* Retour : Indice de résultats pour le motif. * +* * +* Remarques : - * +* * +******************************************************************************/ + +static patid_t enroll_plain_pattern_avx2(GBitapBackend *backend, GScanContext *context, const bin_t *plain, size_t plen) +{ + patid_t result; /* Identifiant à retourner */ + grouped_strings_avx2_t ***strings; /* Groupe de chaînes visé */ + size_t *count; /* Taille de ce groupe */ + grouped_strings_avx2_t *last; /* Dernier groupe à remplir */ + size_t n; /* Indice dans le groupe */ + size_t i; /* Boucle de parcours */ + __m256i *letter; /* Lettre à marquer */ + + /* Sélection du groupe de travail adéquat */ + + strings = &backend->manager_avx2.strings_8; + count = &backend->manager_avx2.count_8; + + /* Préparation de la place nécessaire */ + + if (*count == 0) + { + extend_grouped_strings_avx2(strings, count); + + last = (*strings)[0]; + + } + + else + { + last = (*strings)[*count - 1]; + + if (last->used == last->available) + { + extend_grouped_strings_avx2(strings, count); + last = (*strings)[*count - 1]; + } + + } + + /* Intégration d'une nouvelle chaîne */ + + n = last->used++; + + last->m[n] = plen; + + result = g_scan_context_get_new_pattern_id(context); + + last->found_id[n] = result; + + ((uint8_t *)&last->found_masks)[n] = (1 << plen); + + for (i = 0; i < plen; i++) + { + letter = last->pattern_masks + plain[i]; + ((uint8_t *)letter)[n] &= ~(1 << i); + } + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : backend = moteur de recherche à manipuler. * +* context = lieu d'enregistrement des résultats. * +* content = données binaires à analyser. * +* * +* Description : Parcours un contenu binaire à la recherche de motifs. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void run_scan_avx2(const GBitapBackend *backend, GScanContext *context, GBinContent *content) +{ + const group_manager_avx2_t *manager; /* Accès simplifié */ + phys_t dlen; /* Quantité de données */ + vmpa2t pos; /* Point de départ ciblé */ + const bin_t *data; /* Données à analyser */ + + register __m256i zero asm("ymm11"); /* Constante 0 sur 256 bits */ + size_t k; /* Boucle de parcours #1 */ + grouped_strings_avx2_t group; /* Copie pour accès locaux */ + + register __m256i R asm("ymm12"); /* Résultats courants */ + register __m256i found_masks asm("ymm10"); /* Vérifications accélérées */ + + //__m256i pre_shift_mask; /* Préparation de décalage */ + //phys_t i; /* Boucle de parcours #2 */ + + + + + const bin_t *iter; + const bin_t *maxiter; + //phys_t i; /* Boucle de parcours #2 */ + + volatile register __m256i xxxx; /* Test de correspondances */ + + + __m256i test; /* Test de correspondances */ + __m256i test2; /* Test de correspondances */ + __m256i status; /* Statut d'une comparaison */ + + int masks[10]; + + int mask; /* Masque d'accès rapide */ + size_t j; /* Boucle de parcours #3 */ + + + int ret; + + //return; + + /* Initialisations diverses */ + + manager = &backend->manager_avx2; + + dlen = g_binary_content_compute_size(content); + + g_binary_content_compute_start_pos(content, &pos); + data = g_binary_content_get_raw_access(content, &pos, dlen); + + zero = _mm256_set1_epi16(0); + + asm volatile ("nop;nop;nop;nop;nop;nop;nop;nop;nop;"); + + xxxx = _mm256_set1_epi8(~1); + + asm volatile ("nop;nop;nop;nop;nop;nop;nop;nop;nop;"); + + /* Recherches des chaînes de moins de 8 caractères */ + + printf(" --- manager->count_8: %zu\n", manager->count_8); + + ret = 0; + + for (k = 0; k < manager->count_8; k++) + { + memcpy(&group, manager->strings_8[k], sizeof(grouped_strings_avx2_t)); + + //printf(" --- group.used: %zu\n", group.used); + + + asm volatile + ( + /* + * R = _mm256_set1_epi8(~1); + * + */ + + "movabs $0xfefefefefefefefe, %%rax ; " + "vpbroadcastq %%rax, %[STATE] ; " + + /* + * + */ + + "vmovdqa %[FOUND_SRC], %[FOUND_DST] ; " + + : [STATE] "=v"(R), + [FOUND_DST] "=v"(found_masks) + : [FOUND_SRC] "m"(group.found_masks) + : "memory", "rax" + + ); + + + + + //pre_shift_mask = _mm256_set1_epi8(0xef); + + maxiter = data + dlen; + + + + for (iter = data; (iter + 10) < maxiter; iter += 10) + { + + //printf("--- %llx <-> %c\n", (unsigned long long)(iter - data), *iter); + + + asm volatile + ( +#if 0 + + /* + * R = _mm256_or_si256(R, group.pattern_masks[data[i]]); + * + * Latency : 1-9 + * Throughput : 0.5 + * #Uops : 1-2 + * Port Usage : 1*p015+1*p23 + * + */ + + "vpor %[PATTERN], %[STATE], %[STATE] ; " + +#else + + /* + * %ymm = group.pattern_masks[data[i]]; + * + * Latency : 5-8 + * Throughput : 0.5 + * #Uops : 1 + * Port Usage : 1*p23 + * + */ + + "vmovdqa %[PATTERN0], %%ymm0 ; " + "vmovdqa %[PATTERN1], %%ymm1 ; " + "vmovdqa %[PATTERN2], %%ymm2 ; " + "vmovdqa %[PATTERN3], %%ymm3 ; " + "vmovdqa %[PATTERN4], %%ymm4 ; " + "vmovdqa %[PATTERN5], %%ymm5 ; " + "vmovdqa %[PATTERN6], %%ymm6 ; " + "vmovdqa %[PATTERN7], %%ymm7 ; " + "vmovdqa %[PATTERN7], %%ymm8 ; " + "vmovdqa %[PATTERN7], %%ymm9 ; " + + /* + * R = _mm256_or_si256(R, %ymm); + * + * Latency : 1 + * Throughput : 0.33 + * #Uops : 1 + * Port Usage : 1*p015 + * + */ + + "vpor %%ymm0, %[STATE], %[STATE] ; " + +#endif + + /* + * R = _mm256_add_epi8(R, R); + * + * Latency : 1 + * Throughput : 0.3 + * #Uops : 1 + * Port Usage : 1*p015 + * + */ + + "vpaddb %[STATE], %[STATE], %[STATE] ; " + + /* + * test = _mm256_and_si256(R, group.found_masks); + * + * Latency : 1 + * Throughput : 0.33 + * #Uops : 1 + * Port Usage : 1*p015 + * + */ + + "vpand %[FOUND], %[STATE], %%ymm0 ; " + + /* Déroulemets... */ + + "vpor %%ymm1, %[STATE], %[STATE] ; " + "vpaddb %[STATE], %[STATE], %[STATE] ; " + + "vpor %%ymm2, %[STATE], %[STATE] ; " + "vpaddb %[STATE], %[STATE], %[STATE] ; " + + "vpor %%ymm3, %[STATE], %[STATE] ; " + "vpaddb %[STATE], %[STATE], %[STATE] ; " + + "vpor %%ymm4, %[STATE], %[STATE] ; " + "vpaddb %[STATE], %[STATE], %[STATE] ; " + + "vpor %%ymm5, %[STATE], %[STATE] ; " + "vpaddb %[STATE], %[STATE], %[STATE] ; " + + "vpor %%ymm6, %[STATE], %[STATE] ; " + "vpaddb %[STATE], %[STATE], %[STATE] ; " + + "vpor %%ymm7, %[STATE], %[STATE] ; " + "vpaddb %[STATE], %[STATE], %[STATE] ; " + + "vpor %%ymm8, %[STATE], %[STATE] ; " + "vpaddb %[STATE], %[STATE], %[STATE] ; " + + "vpor %%ymm9, %[STATE], %[STATE] ; " + "vpaddb %[STATE], %[STATE], %[STATE] ; " + + "vpand %[FOUND], %[STATE], %%ymm1 ; " + "vpand %[FOUND], %[STATE], %%ymm2 ; " + "vpand %[FOUND], %[STATE], %%ymm3 ; " + "vpand %[FOUND], %[STATE], %%ymm4 ; " + "vpand %[FOUND], %[STATE], %%ymm5 ; " + "vpand %[FOUND], %[STATE], %%ymm6 ; " + "vpand %[FOUND], %[STATE], %%ymm7 ; " + "vpand %[FOUND], %[STATE], %%ymm8 ; " + "vpand %[FOUND], %[STATE], %%ymm9 ; " + + + + + + /* + * status = _mm256_cmpeq_epi8(test, zero); + * + * Latency : 1 + * Throughput : 0.5 + * #Uops : 1 + * Port Usage : 1*p01 + * + */ + + "vpcmpeqb %%ymm0, %[NUL], %%ymm0 ; " + + /* + * mask = _mm256_movemask_epi8(status); + * + * Latency : <5 + * Throughput : 1 + * #Uops : 1 + * Port Usage : 1*p0 + * + */ + + "vpmovmskb %%ymm0, %[MASK0] ; " + + + + + + "vpcmpeqb %%ymm1, %[NUL], %%ymm1 ; " + "vpcmpeqb %%ymm2, %[NUL], %%ymm2 ; " + "vpcmpeqb %%ymm3, %[NUL], %%ymm3 ; " + "vpcmpeqb %%ymm4, %[NUL], %%ymm4 ; " + "vpcmpeqb %%ymm5, %[NUL], %%ymm5 ; " + "vpcmpeqb %%ymm6, %[NUL], %%ymm6 ; " + "vpcmpeqb %%ymm7, %[NUL], %%ymm7 ; " + "vpcmpeqb %%ymm8, %[NUL], %%ymm8 ; " + "vpcmpeqb %%ymm9, %[NUL], %%ymm9 ; " + + + "vpmovmskb %%ymm1, %[MASK1] ; " + "vpmovmskb %%ymm2, %[MASK2] ; " + "vpmovmskb %%ymm3, %[MASK3] ; " + "vpmovmskb %%ymm4, %[MASK4] ; " + "vpmovmskb %%ymm5, %[MASK5] ; " + "vpmovmskb %%ymm6, %[MASK6] ; " + "vpmovmskb %%ymm7, %[MASK7] ; " + "vpmovmskb %%ymm8, %[MASK8] ; " + "vpmovmskb %%ymm9, %[MASK9] ; " + + + + + + + + + + + //"vmovdqa %%ymm7, %[OUTPUT] ; " + + //"vmovdqa %%ymm8, %[OUTPUT2] ; " + + : [STATE] "+v"(R), + [OUTPUT] "=v"(test), + [OUTPUT2] "=v"(test2), + [MASK0] "=r"(mask), + [MASK1] "=r"(mask), + [MASK2] "=r"(mask), + [MASK3] "=r"(mask), + [MASK4] "=r"(mask), + [MASK5] "=r"(mask), + [MASK6] "=r"(mask), + [MASK7] "=r"(mask), + [MASK8] "=r"(mask), + [MASK9] "=r"(mask), + [NUL] "+v"(zero) + : [PATTERN0] "m"(group./*manager->strings_8[k]->*/pattern_masks[*iter]), + [PATTERN1] "m"(group./*manager->strings_8[k]->*/pattern_masks[*(iter + 1)]), + [PATTERN2] "m"(group./*manager->strings_8[k]->*/pattern_masks[*(iter + 2)]), + [PATTERN3] "m"(group./*manager->strings_8[k]->*/pattern_masks[*(iter + 3)]), + [PATTERN4] "m"(group./*manager->strings_8[k]->*/pattern_masks[*(iter + 4)]), + [PATTERN5] "m"(group./*manager->strings_8[k]->*/pattern_masks[*(iter + 5)]), + [PATTERN6] "m"(group./*manager->strings_8[k]->*/pattern_masks[*(iter + 6)]), + [PATTERN7] "m"(group./*manager->strings_8[k]->*/pattern_masks[*(iter + 7)]), + [PATTERN8] "m"(group./*manager->strings_8[k]->*/pattern_masks[*(iter + 8)]), + [PATTERN9] "m"(group./*manager->strings_8[k]->*/pattern_masks[*(iter + 9)]), + [FOUND] "v"(found_masks) + : "memory", "ymm0", "ymm1", "ymm2", "ymm3", "ymm4", "ymm5", "ymm6", "ymm7", "ymm8", "ymm9" + + ); + + + /* + printf(" test: %02hhx %02hhx %02hhx %02hhx %02hhx %02hhx %02hhx %02hhx ... %02hhx %02hhx %02hhx %02hhx\n", + ((uint8_t *)&test)[0], + ((uint8_t *)&test)[1], + ((uint8_t *)&test)[2], + ((uint8_t *)&test)[3], + ((uint8_t *)&test)[4], + ((uint8_t *)&test)[5], + ((uint8_t *)&test)[6], + ((uint8_t *)&test)[7], + ((uint8_t *)&test)[16], + ((uint8_t *)&test)[17], + ((uint8_t *)&test)[18], + ((uint8_t *)&test)[19]); + + printf(" test2: %02hhx %02hhx %02hhx %02hhx %02hhx %02hhx %02hhx %02hhx ... %02hhx %02hhx %02hhx %02hhx\n", + ((uint8_t *)&test2)[0], + ((uint8_t *)&test2)[1], + ((uint8_t *)&test2)[2], + ((uint8_t *)&test2)[3], + ((uint8_t *)&test2)[4], + ((uint8_t *)&test2)[5], + ((uint8_t *)&test2)[6], + ((uint8_t *)&test2)[7], + ((uint8_t *)&test2)[16], + ((uint8_t *)&test2)[17], + ((uint8_t *)&test2)[18], + ((uint8_t *)&test2)[19]); + */ + +#if 0 + //printf(" > %c\n", data[i]); + + R = _mm256_or_si256(R, group.pattern_masks[*iter]); + + //printf("group pattern: %hhx\n", *((uint8_t *)&group.pattern_masks[data[i]])); + + //printf("R: %hhx\n", *((uint8_t *)&R)); + + //R = _mm256_and_si256(R, pre_shift_mask); + + //printf("R after and: %hhx\n", *((uint8_t *)&R)); + + R = _mm256_add_epi8(R, R); + //R = _mm256_slli_si256(R, 1); + + //printf("R after shift: %hhx\n", *((uint8_t *)&R)); + + test = _mm256_and_si256(R, group.found_masks); + +#if 1 + status = _mm256_cmpeq_epi8(test, zero); + + mask = _mm256_movemask_epi8(status); +#else + //mask = _mm256_movemask_epi8(test) ^ 0xffffffff; + mask = _mm256_movemask_epi8(test); +#endif + + +#endif + + + //printf(" mask : %x\n", mask); + + if (mask != 0) + for (j = 0; j < group.used; j++) + { + if ((mask & 0x1) == 1) + { + //assert((i + 1) >= group.m[j]); + + g_scan_context_register_atom_match(context, + group.found_id[j], + (iter - data) + 1 - group.m[j]); + + } + + mask >>= 1; + + } + + } + + + + + +#if 0 + for (; iter < maxiter; iter++) + { + + //printf("--- %llx <-> %c\n", (unsigned long long)(iter - data), *iter); + + + asm volatile + ( + /* + * R = _mm256_or_si256(R, group.pattern_masks[data[i]]); + * + * Latency : 1 + * Throughput : 0.33 + * #Uops : 1 + * Port Usage : 1*p015 + * + */ + + "vpor %[PATTERN], %[STATE], %[STATE] ; " + + /* + * R = _mm256_add_epi8(R, R); + * + * Latency : 1 + * Throughput : 0.3 + * #Uops : 1 + * Port Usage : 1*p015 + * + */ + + "vpaddb %[STATE], %[STATE], %[STATE] ; " + + /* + * test = _mm256_and_si256(R, group.found_masks); + * + * Latency : 1 + * Throughput : 0.33 + * #Uops : 1 + * Port Usage : 1*p015 + * + */ + + "vpand %[FOUND], %[STATE], %%ymm7 ; " + + /* + * status = _mm256_cmpeq_epi8(test, zero); + * + * Latency : 1 + * Throughput : 0.5 + * #Uops : 1 + * Port Usage : 1*p01 + * + */ + + "vpcmpeqb %%ymm7, %[NUL], %%ymm8 ; " + + /* + * mask = _mm256_movemask_epi8(status); + * + * Latency : <5 + * Throughput : 1 + * #Uops : 1 + * Port Usage : 1*p0 + * + */ + + "vpmovmskb %%ymm8, %[MASK0] ; " + + + //"vmovdqa %%ymm7, %[OUTPUT] ; " + + //"vmovdqa %%ymm8, %[OUTPUT2] ; " + + : [STATE] "+v"(R), + [OUTPUT] "=v"(test), + [OUTPUT2] "=v"(test2), + [MASK0] "=r"(mask), + [NUL] "+v"(zero) + : [PATTERN] "m"(group./*manager->strings_8[k]->*/pattern_masks[*iter]), + [FOUND] "v"(found_masks) + : "memory", "ymm7", "ymm8" + + ); + + + /* + printf(" test: %02hhx %02hhx %02hhx %02hhx %02hhx %02hhx %02hhx %02hhx ... %02hhx %02hhx %02hhx %02hhx\n", + ((uint8_t *)&test)[0], + ((uint8_t *)&test)[1], + ((uint8_t *)&test)[2], + ((uint8_t *)&test)[3], + ((uint8_t *)&test)[4], + ((uint8_t *)&test)[5], + ((uint8_t *)&test)[6], + ((uint8_t *)&test)[7], + ((uint8_t *)&test)[16], + ((uint8_t *)&test)[17], + ((uint8_t *)&test)[18], + ((uint8_t *)&test)[19]); + + printf(" test2: %02hhx %02hhx %02hhx %02hhx %02hhx %02hhx %02hhx %02hhx ... %02hhx %02hhx %02hhx %02hhx\n", + ((uint8_t *)&test2)[0], + ((uint8_t *)&test2)[1], + ((uint8_t *)&test2)[2], + ((uint8_t *)&test2)[3], + ((uint8_t *)&test2)[4], + ((uint8_t *)&test2)[5], + ((uint8_t *)&test2)[6], + ((uint8_t *)&test2)[7], + ((uint8_t *)&test2)[16], + ((uint8_t *)&test2)[17], + ((uint8_t *)&test2)[18], + ((uint8_t *)&test2)[19]); + */ + +#if 0 + //printf(" > %c\n", data[i]); + + R = _mm256_or_si256(R, group.pattern_masks[*iter]); + + //printf("group pattern: %hhx\n", *((uint8_t *)&group.pattern_masks[data[i]])); + + //printf("R: %hhx\n", *((uint8_t *)&R)); + + //R = _mm256_and_si256(R, pre_shift_mask); + + //printf("R after and: %hhx\n", *((uint8_t *)&R)); + + R = _mm256_add_epi8(R, R); + //R = _mm256_slli_si256(R, 1); + + //printf("R after shift: %hhx\n", *((uint8_t *)&R)); + + test = _mm256_and_si256(R, group.found_masks); + +#if 1 + status = _mm256_cmpeq_epi8(test, zero); + + mask = _mm256_movemask_epi8(status); +#else + //mask = _mm256_movemask_epi8(test) ^ 0xffffffff; + mask = _mm256_movemask_epi8(test); +#endif + + +#endif + + + //printf(" mask : %x\n", mask); + + if (mask != 0) + for (j = 0; j < group.used; j++) + { + if ((mask & 0x1) == 1) + { + //assert((i + 1) >= group.m[j]); + + g_scan_context_register_atom_match(context, + group.found_id[j], + (iter - data) + 1 - group.m[j]); + + } + + mask >>= 1; + + } + + } + +#endif + + + } + + +} + + + + + + + + + + + + + + +#if 0 + + +#if 0 + +/****************************************************************************** +* * +* Paramètres : backend = moteur de recherche à manipuler. * +* context = lieu d'enregistrement des résultats. * +* content = données binaires à analyser. * +* * +* Description : Parcours un contenu binaire à la recherche de motifs. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void run_scan_avx2(const GBitapBackend *backend, GScanContext *context, GBinContent *content) +{ + const group_manager_avx2_t *manager; /* Accès simplifié */ + + grouped_strings_avx2_t groups[10]; /* Copie pour accès locaux */ + + + phys_t dlen; /* Quantité de données */ + vmpa2t pos; /* Point de départ ciblé */ + const bin_t *data; /* Données à analyser */ + __m256i zero; /* Constante 0 sur 256 bits */ + size_t k; /* Boucle de parcours #1 */ + + grouped_strings_avx2_t group; /* Copie pour accès locaux */ + __m256i R; /* Résultats courants */ + __m256i pre_shift_mask; /* Préparation de décalage */ + phys_t i; /* Boucle de parcours #2 */ + __m256i test; /* Test de correspondances */ + __m256i status; /* Statut d'une comparaison */ + int mask; /* Masque d'accès rapide */ + size_t j; /* Boucle de parcours #3 */ + + uint32_t leaves; + int ret; + + + phys_t old_i; + phys_t p; + + //return; + + /* Initialisations diverses */ + + manager = &backend->manager_avx2; + + dlen = g_binary_content_compute_size(content); + + g_binary_content_compute_start_pos(content, &pos); + data = g_binary_content_get_raw_access(content, &pos, dlen); + + zero = _mm256_set1_epi16(0); + + /* Recherches des chaînes de moins de 8 caractères */ + + printf(" --- manager->count_8: %zu\n", manager->count_8); + + ret = 0; + + //for (k = 0; k < manager->count_8; k++) + // memcpy(&groups[k], manager->strings_8[k], sizeof(grouped_strings_avx2_t)); + + + for (i = 0; i < dlen; ) + { + + //printf(" --- %llx\n", (unsigned long long)i); + + p = i + 4096; + + if (p > dlen) + p = dlen; + + old_i = i; + + printf("old_i: %llx\n", (unsigned long long)old_i); + + for (k = 0; k < manager->count_8; k++) + { + + group = *manager->strings_8[k]; + + R = group.R; + + for (i = old_i ; i < p; i++) + { + + //group = &groups[k]; + + //printf(" k: %zu i: %llx\n", k, (unsigned long long)i); + + //R = group.R;//_mm256_set1_epi8(~1); + + R = _mm256_or_si256(R, group.pattern_masks[data[i]]); + + R = _mm256_add_epi8(R, R); + + test = _mm256_and_si256(R, group.found_masks); + +#if 0 + status = _mm256_cmpeq_epi8(test, zero); + + mask = _mm256_movemask_epi8(status); +#else + //mask = _mm256_movemask_epi8(test) ^ 0xffffffff; + mask = _mm256_movemask_epi8(test); +#endif + + if (mask != 0xffffffff) + { + leaves = group.leaves; + + for (j = 0; j < group.used; j++) + { + if ((mask & 0x1) == 0) + { + if (leaves & 0x1) //group.leaves & (1u << j)) + ;//define_full_match_avx2(backend, context, content, &group, j, i + 1); + + } + + mask >>= 1; + + leaves >>= 1; + + } + + } + + group.R = R;//_mm256_set1_epi8(~1); + + memcpy(manager->strings_8[k], &group, sizeof(grouped_strings_avx2_t)); + + } + + + } + + } + + printf("oh: %d\n", ret); + + +} + + +#else + + + +/****************************************************************************** +* * +* Paramètres : backend = moteur de recherche à manipuler. * +* context = lieu d'enregistrement des résultats. * +* content = données binaires à analyser. * +* * +* Description : Parcours un contenu binaire à la recherche de motifs. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void run_scan_avx2(const GBitapBackend *backend, GScanContext *context, GBinContent *content) +{ + const group_manager_avx2_t *manager; /* Accès simplifié */ + phys_t dlen; /* Quantité de données */ + vmpa2t pos; /* Point de départ ciblé */ + const bin_t *data; /* Données à analyser */ + __m256i zero; /* Constante 0 sur 256 bits */ + size_t k; /* Boucle de parcours #1 */ + grouped_strings_avx2_t group; /* Copie pour accès locaux */ + __m256i R; /* Résultats courants */ + __m256i pre_shift_mask; /* Préparation de décalage */ + phys_t i; /* Boucle de parcours #2 */ + __m256i test; /* Test de correspondances */ + __m256i status; /* Statut d'une comparaison */ + int mask; /* Masque d'accès rapide */ + size_t j; /* Boucle de parcours #3 */ + + uint32_t leaves; + int ret; + + //return; + + /* Initialisations diverses */ + + manager = &backend->manager_avx2; + + dlen = g_binary_content_compute_size(content); + + g_binary_content_compute_start_pos(content, &pos); + data = g_binary_content_get_raw_access(content, &pos, dlen); + + zero = _mm256_set1_epi16(0); + + /* Recherches des chaînes de moins de 8 caractères */ + + printf(" --- manager->count_8: %zu\n", manager->count_8); + + ret = 0; + + for (k = 0; k < manager->count_8; k++) + { + memcpy(&group, manager->strings_8[k], sizeof(grouped_strings_avx2_t)); + + //printf(" --- group.used: %zu\n", group.used); + + R = _mm256_set1_epi8(~1); + + //pre_shift_mask = _mm256_set1_epi8(0xef); + + for (i = 0; i < dlen; ++i) + { + //printf(" > %c\n", data[i]); + + R = _mm256_or_si256(R, group.pattern_masks[data[i]]); + + //printf("group pattern: %hhx\n", *((uint8_t *)&group.pattern_masks[data[i]])); + + //printf("R: %hhx\n", *((uint8_t *)&R)); + + //R = _mm256_and_si256(R, pre_shift_mask); + + //printf("R after and: %hhx\n", *((uint8_t *)&R)); + + R = _mm256_add_epi8(R, R); + //R = _mm256_slli_si256(R, 1); + + //printf("R after shift: %hhx\n", *((uint8_t *)&R)); + + test = _mm256_and_si256(R, group.found_masks); + +#if 0 + status = _mm256_cmpeq_epi8(test, zero); + + mask = _mm256_movemask_epi8(status); +#else + //mask = _mm256_movemask_epi8(test) ^ 0xffffffff; + mask = _mm256_movemask_epi8(test); +#endif + + if (mask != 0xffffffff) + { + leaves = group.leaves; + + for (j = 0; j < group.used; j++) + { + if ((mask & 0x1) == 0) + { + //assert((i + 1) >= group.m[j]); + + if (leaves & 0x1) //group.leaves & (1u << j)) + define_full_match_avx2(backend, context, content, &group, j, i + 1); + //else + //{ + // ret++; + //printf("%x\n", (unsigned int)i + 1); + //} + //else + // g_scan_context_register_sub_match(context, group.found_id[j], i + 1 - group.m[j]); + + } + + mask >>= 1; + + leaves >>= 1; + + } + + } + + } + + } + + printf("oh: %d\n", ret); + + /* Recherches des chaînes de moins de 16 caractères */ + + for (k = 0; k < manager->count_16; k++) + { + memcpy(&group, manager->strings_16[k], sizeof(grouped_strings_avx2_t)); + + R = _mm256_set1_epi16(~1); + + for (i = 0; i < dlen; ++i) + { + R = _mm256_or_si256(R, group.pattern_masks[data[i]]); + R = _mm256_slli_epi16(R, 1); + + test = _mm256_and_si256(R, group.found_masks); + + status = _mm256_cmpeq_epi16(test, zero); + + mask = _mm256_movemask_epi8(status); + + if (mask != 0) + for (j = 0; j < group.used; j++) + { + if (mask & 0x3) + { + assert((i + 1) >= group.m[j]); + + if (group.leaves & (1llu << j)) + define_full_match_avx2(backend, context, content, &group, j, i + 1); + else + ;//g_scan_context_register_sub_match(context, group.found_id[j], i + 1 - group.m[j]); + + } + + mask >>= 2; + + } + + } + + } + +} + +#endif + + + +#endif + + + + + + + + + + + + + + + + + + + +/* ---------------------------------------------------------------------------------- */ +/* OPTIMISATIONS POUR ARCHITECTURE AVX512 */ +/* ---------------------------------------------------------------------------------- */ + + +/** + * Cf. https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html#techs=AVX_512 + * - https://agner.org/optimize/ + * - https://uops.info/table.html + */ + + +/****************************************************************************** +* * +* Paramètres : strings = ensemble de groupes constitués. [OUT] * +* count = nombre de groupes courant. [OUT] * +* * +* Description : Indique la valeur portée par une expression rationnelle. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void extend_grouped_strings_avx512(grouped_strings_avx512_t ***strings, size_t *count) +{ + grouped_strings_avx512_t *new; /* Zone supplémentaire */ + size_t i; /* Boucle de parcours */ + + /* Définition d'un nouvel élément vierge */ + + new = aligned_alloc(0x1000, sizeof(grouped_strings_avx512_t)); + + for (i = 0; i < 256; i++) + new->pattern_masks[i] = _mm512_set1_epi8(~0); + + new->found_masks = _mm512_set1_epi8(~0); + + new->R = _mm512_set1_epi8(~1); + + for (i = 0; i < 64; i++) + { + new->m[i] = 0; + + new->found_id[i] = INVALID_PATTERN_ID; + + } + + new->available = 64; + new->used = 0; + + /* Inscription */ + + *strings = realloc(*strings, ++(*count) * sizeof(grouped_strings_avx512_t *)); + + (*strings)[*count - 1] = new; + +} + + +/****************************************************************************** +* * +* Paramètres : backend = moteur de recherche à manipuler. * +* context = contexte de l'analyse à mener. * +* plain = chaîne de caractères classique à intégrer. * +* plen = taille de cette chaîne. * +* * +* Description : Inscrit dans le moteur une chaîne de caractères à rechercher.* +* * +* Retour : Indice de résultats pour le motif. * +* * +* Remarques : - * +* * +******************************************************************************/ + +static patid_t enroll_plain_pattern_avx512(GBitapBackend *backend, GScanContext *context, const bin_t *plain, size_t plen) +{ + patid_t result; /* Identifiant à retourner */ + grouped_strings_avx512_t ***strings; /* Groupe de chaînes visé */ + size_t *count; /* Taille de ce groupe */ + grouped_strings_avx512_t *last; /* Dernier groupe à remplir */ + size_t n; /* Indice dans le groupe */ + size_t i; /* Boucle de parcours */ + __m512i *letter; /* Lettre à marquer */ + + /* Sélection du groupe de travail adéquat */ + + strings = &backend->manager_avx512.strings_8; + count = &backend->manager_avx512.count_8; + + /* Préparation de la place nécessaire */ + + if (*count == 0) + { + extend_grouped_strings_avx512(strings, count); + + last = (*strings)[0]; + + } + + else + { + last = (*strings)[*count - 1]; + + if (last->used == last->available) + { + extend_grouped_strings_avx512(strings, count); + last = (*strings)[*count - 1]; + } + + } + + /* Intégration d'une nouvelle chaîne */ + + n = last->used++; + + last->m[n] = plen; + + result = g_scan_context_get_new_pattern_id(context); + + last->found_id[n] = result; + + ((uint8_t *)&last->found_masks)[n] = (1 << plen); + + for (i = 0; i < plen; i++) + { + letter = last->pattern_masks + plain[i]; + ((uint8_t *)letter)[n] &= ~(1 << i); + } + + return result; + +} + + + + + +/****************************************************************************** +* * +* Paramètres : backend = moteur de recherche à manipuler. * +* context = lieu d'enregistrement des résultats. * +* content = données binaires à analyser. * +* * +* Description : Parcours un contenu binaire à la recherche de motifs. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void run_scan_avx512(const GBitapBackend *backend, GScanContext *context, GBinContent *content) +{ + const group_manager_avx512_t *manager; /* Accès simplifié */ + phys_t dlen; /* Quantité de données */ + vmpa2t pos; /* Point de départ ciblé */ + const bin_t *data; /* Données à analyser */ + + //register __m512i zero asm("zmm19"); /* Constante 0 sur 512 bits */ + + //__m512i shift8_mask; /* Masque pour décalage manuel */ + + + size_t k; /* Boucle de parcours #1 */ + /*__attribute__((aligned(0x1000)))*/ grouped_strings_avx512_t group; /* Copie pour accès locaux */ + //void *grpptr; + //grouped_strings_avx512_t *_group; /* Copie pour accès locaux */ + + int ret; + + + register __m512i R asm("zmm28"); /* Résultats courants */ + register __m512i found_masks asm("zmm21"); /* Vérifications accélérées */ + + + register __mmask64 test_mask asm("k6"); + + + register const bin_t *iter asm("rsi"); + register const bin_t *maxiter/* asm("rdi")*/; + //phys_t i; /* Boucle de parcours #2 */ + + + //__m512i test; + + __mmask64 mask; /* Masque d'accès rapide */ + size_t j; /* Boucle de parcours #3 */ + + + /* Initialisations diverses */ + + manager = &backend->manager_avx512; + + dlen = g_binary_content_compute_size(content); + + g_binary_content_compute_start_pos(content, &pos); + data = g_binary_content_get_raw_access(content, &pos, dlen); + + + + /* Recherches des chaînes de moins de 8 caractères */ + + //asm volatile ("nop; nop; nop; nop; nop; nop; nop; "); + + //zero = _mm512_set1_epi8(0); + + //asm volatile ("nop; nop; nop; nop; nop; nop; nop; "); + + //shift8_mask = _mm512_set1_epi8(0x7f); + + + +#define WORK_ON_COPY + + for (k = 0; k < manager->count_8; k++) + { +#ifdef WORK_ON_COPY + memcpy(&group, manager->strings_8[k], sizeof(grouped_strings_avx512_t)); + +#else + + grpptr = alloca(sizeof(grouped_strings_avx512_t) + 0x1000); + + _group = grpptr + 0x1000 - (((unsigned long)grpptr) % 0x1000); + + //_group = manager->strings_8[k]; + + memcpy(_group, manager->strings_8[k], sizeof(grouped_strings_avx512_t)); + + ret = mlock(_group, sizeof(grouped_strings_avx512_t)); + + printf("ret = %d\n", ret); +#endif + + + + //printf(" --- group %p -- used: %zu (sz: %zu)\n", &group, group.used, sizeof(grouped_strings_avx512_t)); + //printf(" --- group.used: %zu (sz: %zu)\n", group.used, sizeof(grouped_strings_avx512_t)); + + + asm volatile + ( + /* + * R = _mm512_set1_epi8(~1); + * + */ + + "movabs $0xfefefefefefefefe, %%rax ; " + "vpbroadcastq %%rax, %[STATE] ; " + + "movabs $0xffffffffffffffff, %%rax ; " + "kmovq %%rax, %[KMASK] ; " + + /* + * + */ + + "vmovdqa64 %[FOUND_SRC], %[FOUND_DST] ; " + + : [STATE] "=v"(R), + [KMASK] "=Yk"(test_mask), + [FOUND_DST] "=v"(found_masks) +#ifdef WORK_ON_COPY + : [FOUND_SRC] "m"(group.found_masks) +#else + : [FOUND_SRC] "m"(_group->found_masks) +#endif + : "memory", "rax" + + ); + + + + + + + + //for (i = 0; i < dlen; i++) + + maxiter = data + dlen; + + for (iter = data; iter < maxiter; iter++) + { + + //printf("--- %llx <-> %c\n", (unsigned long long)(iter - data), *iter); + + + asm volatile goto + ( + /* + * R = _mm512_or_si512(R, group.pattern_masks[*iter]); + * + * Latency : 1-9 + * Throughput : 0.5 + * #Uops : 1-2 + * Port Usage : 1*p05+1*p23 + * + */ + + "vpord %[PATTERN], %[STATE], %[STATE] ; " + + /* + * R = _mm512_add_epi8(R, R); + * + * Latency : 1 + * Throughput : 0.5 + * #Uops : 1 + * Port Usage : 1*p05 + * + */ + + "vpaddb %[STATE], %[STATE], %[STATE] ; " + + /* + * mask = _mm512_test_epi8_mask(R, group.found_masks); + * + * Latency : 3 + * Throughput : 1 + * #Uops : 2 + * Port Usage : 1*p23+1*p5 + * + */ + + /****************************** + * Version 0 + + ******************/ + + //"vptestmb %[FOUND], %[STATE], %%k7 ; " + + /****************************** + * Version 1 + + "vmovdqa64 %[STATE], %%zmm12 ; " + + "vptestmb %[FOUND], %%zmm12, %%k7 ; " + + ******************/ + + /****************************** + * Version 2 + + "vpandd %[STATE], %[FOUND], %%zmm12 ; " + + "vpcmpneqb %[NUL], %%zmm12, %%k7 ; " + + ******************/ + + + "vmovdqa64 %[STATE], %%zmm12 ; " + + "vptestmb %[FOUND], %%zmm12, %%k7 ; " + + + "ktestq %[KMASK], %%k7 ; " + + "jc %l[next_iter] ; " + + + + + + /* + * (suite) + * + * Latency : 3 + * Throughput : 1 + * #Uops : 1 + * Port Usage : 1*p5 + * + */ + + "kmovq %%k7, %[MASK0] ; " + + //"vmovdqa64 %%zmm12, %[OUTPUT] ; " + + //"nop; nop; nop; nop; nop; nop; nop; nop; " + //"nop; nop; nop; nop; nop; nop; nop; nop; " + + : [STATE] "+v"(R), + //[OUTPUT] "=v"(test), + [MASK0] "=r"(mask) + //[NUL] "=v"(zero) +#ifdef WORK_ON_COPY + : [PATTERN] "m"(group.pattern_masks[*iter]), +#else + : [PATTERN] "m"(_group->pattern_masks[*iter]), +#endif + [FOUND] "v"(found_masks), + [KMASK] "Yk"(test_mask) + : "memory", "k7", "zmm12" + : next_iter + + ); + + + + + /* + printf(" found mask: %hhx %hhx %hhx %hhx %hhx %hhx %hhx %hhx\n", + ((uint8_t *)&group.found_masks)[0], + ((uint8_t *)&group.found_masks)[1], + ((uint8_t *)&group.found_masks)[2], + ((uint8_t *)&group.found_masks)[3], + ((uint8_t *)&group.found_masks)[4], + ((uint8_t *)&group.found_masks)[5], + ((uint8_t *)&group.found_masks)[6], + ((uint8_t *)&group.found_masks)[7]); + + + printf(" test: %hhx %hhx %hhx %hhx %hhx %hhx %hhx %hhx\n", + ((uint8_t *)&test)[0], + ((uint8_t *)&test)[1], + ((uint8_t *)&test)[2], + ((uint8_t *)&test)[3], + ((uint8_t *)&test)[4], + ((uint8_t *)&test)[5], + ((uint8_t *)&test)[6], + ((uint8_t *)&test)[7]); + + + printf(" -> mask: 0x%llx\n", (unsigned long long)mask); + */ + + +#ifdef WORK_ON_COPY + + //if (mask != 0xffffffffffffffffllu) + for (j = 0; j < group.used; j++) + { + if ((mask & 0x1) == 0) + { + //assert((i + 1) >= group.m[j]); + + g_scan_context_register_atom_match(context, + group.found_id[j], + (iter - data) + 1 - group.m[j]); + + } + + mask >>= 1; + + } + +#else + +# error "WEFEF" + + if (mask != 0xffffffffffffffffllu) + for (j = 0; j < _group->used; j++) + { + if ((mask & 0x1) == 0) + { + //assert((i + 1) >= group.m[j]); + + g_scan_context_register_atom_match(context, + _group->found_id[j], + (iter - data) + 1 - _group->m[j]); + + } + + mask >>= 1; + + } + +#endif + + + next_iter: + + //; + + //iter++; + + } + + } + +} + + + + + + + + + + + +#if 0 + + + + + + + + + + + +/****************************************************************************** +* * +* Paramètres : backend = moteur de recherche à manipuler. * +* context = lieu d'enregistrement des résultats. * +* content = données binaires à analyser. * +* * +* Description : Parcours un contenu binaire à la recherche de motifs. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void run_scan_avx512____good_asm_perfs(const GBitapBackend *backend, GScanContext *context, GBinContent *content) +{ + const group_manager_avx512_t *manager; /* Accès simplifié */ + phys_t dlen; /* Quantité de données */ + vmpa2t pos; /* Point de départ ciblé */ + const bin_t *data; /* Données à analyser */ + + + //__m512i shift8_mask; /* Masque pour décalage manuel */ + + + size_t k; /* Boucle de parcours #1 */ + grouped_strings_avx512_t group; /* Copie pour accès locaux */ + + register __m512i found_masks asm("zmm21"); /* Vérifications accélérées */ + + + //register volatile __m512i zero/* asm("zmm19")*/; /* Constante 0 sur 512 bits */ + register __m512i R asm("zmm28"); /* Résultats courants */ + + //int counter; + + const bin_t *iter; + const bin_t *maxiter; + //phys_t i; /* Boucle de parcours #2 */ + + + __m512i test; + + __mmask64 mask; /* Masque d'accès rapide */ + size_t j; /* Boucle de parcours #3 */ + + + //register __m512i z30 asm("zmm30"); + + + //return; + + + //counter = 0; + + //return; + + /* Initialisations diverses */ + + manager = &backend->manager_avx512; + + dlen = g_binary_content_compute_size(content); + + g_binary_content_compute_start_pos(content, &pos); + data = g_binary_content_get_raw_access(content, &pos, dlen); + + /* Recherches des chaînes de moins de 8 caractères */ + + printf(" --- manager512->count_8: %zu\n", manager->count_8); + + asm volatile ("nop; nop; nop; nop; nop; nop; nop; "); + + //zero = _mm512_set1_epi8(0); + + asm volatile ("nop; nop; nop; nop; nop; nop; nop; "); + + //shift8_mask = _mm512_set1_epi8(0x7f); + + + for (k = 0; k < manager->count_8; k++) + { + memcpy(&group, manager->strings_8[k], sizeof(grouped_strings_avx512_t)); + + + + + //printf(" --- group %p -- used: %zu (sz: %zu)\n", &group, group.used, sizeof(grouped_strings_avx512_t)); + //printf(" --- group.used: %zu (sz: %zu)\n", group.used, sizeof(grouped_strings_avx512_t)); + + + asm volatile + ( + /* + * R = _mm512_set1_epi8(~1); + * + */ + + "movabs $0xfefefefefefefefe, %%rax ; " + "vpbroadcastq %%rax, %[STATE] ; " + + /* + * + */ + + "vmovdqa64 %[FOUND_SRC], %[FOUND_DST] ; " + + : [STATE] "=v"(R), + [FOUND_DST] "=v"(found_masks) + : [FOUND_SRC] "m"(group.found_masks) + : "memory", "rax" + + ); + + + + + + + + //for (i = 0; i < dlen; i++) + + maxiter = data + dlen; + + for (iter = data; iter < maxiter; iter++) + { + + //printf("--- %llx <-> %c\n", (unsigned long long)(iter - data), *iter); + + + asm volatile + ( + + /* + * R = _mm512_or_si512(R, group.pattern_masks[*iter]); + * + * Latency : 1-9 + * Throughput : 0.5 + * #Uops : 1-2 + * Port Usage : 1*p05+1*p23 + * + */ + + "vpord %[PATTERN], %[STATE], %[STATE] ; " + + /* + * R = _mm512_add_epi8(R, R); + * + * Latency : 1 + * Throughput : 0.5 + * #Uops : 1 + * Port Usage : 1*p05 + * + */ + + "vpaddb %[STATE], %[STATE], %[STATE] ; " + + /* + * mask = _mm512_test_epi8_mask(R, group.found_masks); + * + * Latency : 3 + * Throughput : 1 + * #Uops : 2 + * Port Usage : 1*p23+1*p5 + * + */ + + /****************************** + * Version 0 + + ******************/ + + "vptestmb %[FOUND], %[STATE], %%k7 ; " + + /****************************** + * Version 1 + + "vmovdqa64 %[STATE], %%zmm12 ; " + + "vptestmb %[FOUND], %%zmm12, %%k0 ; " + + ******************/ + + /****************************** + * Version 2 + + "vpandd %[STATE], %[FOUND], %%zmm12 ; " + + "vpcmpneqb %[NUL], %%zmm12, %%k7 ; " + + ******************/ + + /* + * (suite) + * + * Latency : 3 + * Throughput : 1 + * #Uops : 1 + * Port Usage : 1*p5 + * + */ + + "kmovq %%k7, %[MASK0] ; " + + //"vmovdqa64 %%zmm12, %[OUTPUT] ; " + + //"nop; nop; nop; nop; nop; nop; nop; nop; " + //"nop; nop; nop; nop; nop; nop; nop; nop; " + + : [STATE] "+v"(R), + [OUTPUT] "=v"(test), + [MASK0] "=r"(mask)/*, + [NUL] "+v"(zero)*/ + : [PATTERN] "v"(group.pattern_masks[*iter]), + [FOUND] "v"(found_masks) + : "memory", "k0", "zmm12" + + ); + + + + + /* + printf(" found mask: %hhx %hhx %hhx %hhx %hhx %hhx %hhx %hhx\n", + ((uint8_t *)&group.found_masks)[0], + ((uint8_t *)&group.found_masks)[1], + ((uint8_t *)&group.found_masks)[2], + ((uint8_t *)&group.found_masks)[3], + ((uint8_t *)&group.found_masks)[4], + ((uint8_t *)&group.found_masks)[5], + ((uint8_t *)&group.found_masks)[6], + ((uint8_t *)&group.found_masks)[7]); + + + printf(" test: %hhx %hhx %hhx %hhx %hhx %hhx %hhx %hhx\n", + ((uint8_t *)&test)[0], + ((uint8_t *)&test)[1], + ((uint8_t *)&test)[2], + ((uint8_t *)&test)[3], + ((uint8_t *)&test)[4], + ((uint8_t *)&test)[5], + ((uint8_t *)&test)[6], + ((uint8_t *)&test)[7]); + + + printf(" -> mask: 0x%llx\n", (unsigned long long)mask); + */ + +#if 0 + + /* + printf(" R: %hhx %hhx %hhx %hhx %hhx %hhx %hhx %hhx\n", + ((uint8_t *)&R)[0], + ((uint8_t *)&R)[1], + ((uint8_t *)&R)[2], + ((uint8_t *)&R)[3], + ((uint8_t *)&R)[4], + ((uint8_t *)&R)[5], + ((uint8_t *)&R)[6], + ((uint8_t *)&R)[7]); + + printf(" found mask: %hhx %hhx %hhx %hhx %hhx %hhx %hhx %hhx\n", + ((uint8_t *)&group.found_masks)[0], + ((uint8_t *)&group.found_masks)[1], + ((uint8_t *)&group.found_masks)[2], + ((uint8_t *)&group.found_masks)[3], + ((uint8_t *)&group.found_masks)[4], + ((uint8_t *)&group.found_masks)[5], + ((uint8_t *)&group.found_masks)[6], + ((uint8_t *)&group.found_masks)[7]); + */ + + /* + + printf(" test: %hhx %hhx %hhx %hhx %hhx %hhx %hhx %hhx\n", + ((uint8_t *)&test)[0], + ((uint8_t *)&test)[1], + ((uint8_t *)&test)[2], + ((uint8_t *)&test)[3], + ((uint8_t *)&test)[4], + ((uint8_t *)&test)[5], + ((uint8_t *)&test)[6], + ((uint8_t *)&test)[7]); + + */ + +#endif + + + + + +# define TEST_MASK 0xffffffffffffffffllu +# define TEST_BIT 0 + + + //printf("mask: %llx\n", (unsigned long long)mask); + + + if (mask != TEST_MASK) + { + //printf("mask: %llx\n", (unsigned long long)mask); + + //counter++; + //printf("Ouhc: %p - %x\n", &group, *((uint8_t *)&mask)); + //printf("Ouhc: %x\n", 1); + //asm("vzeroupper;"); + //printf("Ouhc: %hhx\n", R[0]); + for (j = 0; j < group.used; j++) + { + if ((mask & 0x1) == TEST_BIT) + { + //assert((i + 1) >= group.m[j]); + + //printf(">> FOUND %zu @ %x !!!!!!!!!!!!!!\n", j, (unsigned int)i + 1); + printf(">> FOUND %zu @ %x !!!!!!!!!!!!!!\n", j, (unsigned int)(iter - data) + 1); + + + } + + mask >>= 1; + //printf("> mask: %llx\n", (unsigned long long)mask); + + } + + + + } + + + + } + + //printf("%hhx\n", ((uint8_t *)&R)[0], ((uint8_t *)&mask)[0]); + + } + + //printf("counter=%d\n", counter); + + +} + + + + +/****************************************************************************** +* * +* Paramètres : backend = moteur de recherche à manipuler. * +* context = lieu d'enregistrement des résultats. * +* content = données binaires à analyser. * +* * +* Description : Parcours un contenu binaire à la recherche de motifs. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void run_scan_avx512_best_test(const GBitapBackend *backend, GScanContext *context, GBinContent *content) +{ + const group_manager_avx512_t *manager; /* Accès simplifié */ + phys_t dlen; /* Quantité de données */ + vmpa2t pos; /* Point de départ ciblé */ + const bin_t *data; /* Données à analyser */ + + + //__m512i shift8_mask; /* Masque pour décalage manuel */ + + + size_t k; /* Boucle de parcours #1 */ + grouped_strings_avx512_t group; /* Copie pour accès locaux */ + + //register __m512i zero; /* Constante 0 sur 512 bits */ + register __m512i R; /* Résultats courants */ + + //int counter; + + const bin_t *iter; + const bin_t *maxiter; + //phys_t i; /* Boucle de parcours #2 */ + + + //__m512i test; + + __mmask64 mask; /* Masque d'accès rapide */ + size_t j; /* Boucle de parcours #3 */ + + //return; + + + //counter = 0; + + //return; + + /* Initialisations diverses */ + + manager = &backend->manager_avx512; + + dlen = g_binary_content_compute_size(content); + + g_binary_content_compute_start_pos(content, &pos); + data = g_binary_content_get_raw_access(content, &pos, dlen); + + /* Recherches des chaînes de moins de 8 caractères */ + + printf(" --- manager512->count_8: %zu\n", manager->count_8); + + //zero = _mm512_set1_epi8(0); + + //shift8_mask = _mm512_set1_epi8(0x7f); + + + + for (k = 0; k < manager->count_8; k++) + { + memcpy(&group, manager->strings_8[k], sizeof(grouped_strings_avx512_t)); + + //printf(" --- group %p -- used: %zu (sz: %zu)\n", &group, group.used, sizeof(grouped_strings_avx512_t)); + //printf(" --- group.used: %zu (sz: %zu)\n", group.used, sizeof(grouped_strings_avx512_t)); + + R = _mm512_set1_epi8(~1); + + + + /* vpord zmm, zmm, zmm : latence 1, 1*p05 */ + //R = _mm512_or_si512(R, group.pattern_masks[data[0]]); + + //for (i = 0; i < dlen; i++) + + maxiter = data + dlen; + + for (iter = data; iter < maxiter; iter++) + { + + //printf("--- %llx <-> %c\n", (unsigned long long)(iter - data), *iter); + + + //R = _mm512_or_si512(R, group.pattern_masks[data[i]]); + R = _mm512_or_si512(R, group.pattern_masks[*iter]); + + +#if 1 + /* vpaddb zmm, zmm, zmm : latence 1, 1*p05 */ + R = _mm512_add_epi8(R, R); +#else + /* vpandd zmm, zmm, zmm : latence 1, 1*p5 */ + R = _mm512_and_si512(R, shift8_mask); + /* vpslldq zmm, zmm, imm8 : latence 1, 1*p5 */ + R = _mm512_bslli_epi128(R, 1); + +#endif + + /* + printf(" R: %hhx %hhx %hhx %hhx %hhx %hhx %hhx %hhx\n", + ((uint8_t *)&R)[0], + ((uint8_t *)&R)[1], + ((uint8_t *)&R)[2], + ((uint8_t *)&R)[3], + ((uint8_t *)&R)[4], + ((uint8_t *)&R)[5], + ((uint8_t *)&R)[6], + ((uint8_t *)&R)[7]); + + printf(" found mask: %hhx %hhx %hhx %hhx %hhx %hhx %hhx %hhx\n", + ((uint8_t *)&group.found_masks)[0], + ((uint8_t *)&group.found_masks)[1], + ((uint8_t *)&group.found_masks)[2], + ((uint8_t *)&group.found_masks)[3], + ((uint8_t *)&group.found_masks)[4], + ((uint8_t *)&group.found_masks)[5], + ((uint8_t *)&group.found_masks)[6], + ((uint8_t *)&group.found_masks)[7]); + */ + +#if 1 + /* vptestmb k, zmm, zmm : latence 3, 1*p5 */ + mask = _mm512_test_epi8_mask(R, group.found_masks); + + + //test = _mm512_add_epi64(R, zero); + + //mask = _mm512_test_epi8_mask(test, group.found_masks); + + + + + +# define TEST_MASK 0xffffffffffffffffllu +# define TEST_BIT 0 + + /* comparaison : != */ + + +#else + /* vpandd zmm, zmm, zmm : latence 1, 1*p05 */ + test = _mm512_and_si512(R, group.found_masks); + + + printf(" test: %hhx %hhx %hhx %hhx %hhx %hhx %hhx %hhx\n", + ((uint8_t *)&test)[0], + ((uint8_t *)&test)[1], + ((uint8_t *)&test)[2], + ((uint8_t *)&test)[3], + ((uint8_t *)&test)[4], + ((uint8_t *)&test)[5], + ((uint8_t *)&test)[6], + ((uint8_t *)&test)[7]); + + /* vpmovb2m k, zmm : latence 3 (au lieu de 1 !?), 1*p0 */ + //mask = _mm512_movepi8_mask(test); + +# define TEST_MASK 0 +# define TEST_BIT 0 + + + //test = _mm512_popcnt_epi8(test); + +#endif + + + //printf(" final mask: %16llx\n", (unsigned long long)mask); + + + + //R = _mm512_or_si512(R, group.pattern_masks[data[i + 1]]); + +#if 1 + + + if (mask != TEST_MASK) + { + //counter++; + //printf("Ouhc: %p - %x\n", &group, *((uint8_t *)&mask)); + printf("Ouhc: %p\n", &group); + //printf("Ouhc: %hhx\n", R[0]); + for (j = 0; j < group.used; j++) + { + if ((mask & 0x1) == TEST_BIT) + { + //assert((i + 1) >= group.m[j]); + + //printf(">> FOUND %zu @ %x !!!!!!!!!!!!!!\n", j, (unsigned int)i + 1); + printf(">> FOUND %zu @ %x !!!!!!!!!!!!!!\n", j, (unsigned int)(iter - data) + 1); + + + } + + mask >>= 1; + + } + + + + } + + +#else + + if (_mm512_reduce_or_epi64(test) != 0) + { + for (j = 0; j < group.used; j++) + { + if (((uint8_t *)&test)[j] == 0) + { + //assert((i + 1) >= group.m[j]); + + printf(">> FOUND %zu @ %x !!!!!!!!!!!!!!\n", j, (unsigned int)i + 1); + + } + + + } + + } + +#endif + + + } + + //printf("%hhx\n", ((uint8_t *)&R)[0], ((uint8_t *)&mask)[0]); + + } + + //printf("counter=%d\n", counter); + + +} + + + + + +static void run_scan_avx512__saved(const GBitapBackend *backend, GScanContext *context, GBinContent *content) +{ + const group_manager_avx512_t *manager; /* Accès simplifié */ + phys_t dlen; /* Quantité de données */ + vmpa2t pos; /* Point de départ ciblé */ + const bin_t *data; /* Données à analyser */ + + + __m512i shift8_mask; /* Masque pour décalage manuel */ + + + size_t k; /* Boucle de parcours #1 */ + grouped_strings_avx512_t group; /* Copie pour accès locaux */ + + + __m512i R; /* Résultats courants */ + + //int counter; + + phys_t i; /* Boucle de parcours #2 */ + + + __m512i test; + + __mmask64 mask; /* Masque d'accès rapide */ + size_t j; /* Boucle de parcours #3 */ + + + + //counter = 0; + + //return; + + /* Initialisations diverses */ + + manager = &backend->manager_avx512; + + dlen = g_binary_content_compute_size(content); + + g_binary_content_compute_start_pos(content, &pos); + data = g_binary_content_get_raw_access(content, &pos, dlen); + + /* Recherches des chaînes de moins de 8 caractères */ + + printf(" --- manager512->count_8: %zu\n", manager->count_8); + + + + shift8_mask = _mm512_set1_epi8(0x7f); + + + for (k = 0; k < manager->count_8; k++) + { + memcpy(&group, manager->strings_8[k], sizeof(grouped_strings_avx512_t)); + + //printf(" --- group %p -- used: %zu (sz: %zu)\n", &group, group.used, sizeof(grouped_strings_avx512_t)); + //printf(" --- group.used: %zu (sz: %zu)\n", group.used, sizeof(grouped_strings_avx512_t)); + + R = _mm512_set1_epi8(~1); + + /* vpord zmm, zmm, zmm : latence 1, 1*p05 */ + R = _mm512_or_si512(R, group.pattern_masks[data[0]]); + + for (i = 0; i < dlen; i++) + { + + /* + printf("--- %llx <-> %c\n", (unsigned long long)i, data[i]); + + printf(" R: %hhx %hhx %hhx %hhx\n", + ((uint8_t *)&R)[0], + ((uint8_t *)&R)[1], + ((uint8_t *)&R)[2], + ((uint8_t *)&R)[3]); + + printf(" mask: %hhx %hhx %hhx %hhx\n", + ((uint8_t *)&group.pattern_masks[data[i]])[0], + ((uint8_t *)&group.pattern_masks[data[i]])[1], + ((uint8_t *)&group.pattern_masks[data[i]])[2], + ((uint8_t *)&group.pattern_masks[data[i]])[3]); + */ + + //R = _mm512_or_si512(R, group.pattern_masks[data[i]]); + + /* + printf(" R: %hhx %hhx %hhx %hhx\n", + ((uint8_t *)&R)[0], + ((uint8_t *)&R)[1], + ((uint8_t *)&R)[2], + ((uint8_t *)&R)[3]); + */ + +#if 1 + /* vpaddb zmm, zmm, zmm : latence 1, 1*p05 */ + R = _mm512_add_epi8(R, R); +#else + /* vpandd zmm, zmm, zmm : latence 1, 1*p5 */ + R = _mm512_and_si512(R, shift8_mask); + /* vpslldq zmm, zmm, imm8 : latence 1, 1*p5 */ + R = _mm512_bslli_epi128(R, 1); + +#endif + +#if 1 + /* vptestmb k, zmm, zmm : latence 3, 1*p5 */ + mask = _mm512_test_epi8_mask(R, group.found_masks); +#else + test = _mm512_and_si512(R, group.found_masks); + test = _mm512_popcnt_epi8(test); + +#endif + + /* + printf(" found mask: %hhx %hhx %hhx %hhx\n", + ((uint8_t *)&group.found_masks)[0], + ((uint8_t *)&group.found_masks)[1], + ((uint8_t *)&group.found_masks)[2], + ((uint8_t *)&group.found_masks)[3]); + + printf(" final mask: %16llx\n", (unsigned long long)mask); + */ + + + R = _mm512_or_si512(R, group.pattern_masks[data[i + 1]]); + +#if 1 + + if (mask != 0xffffffffffffffffllu) + { + //counter++; + //printf("Ouhc: %p - %x\n", &group, *((uint8_t *)&mask)); + //printf("Ouhc: %p\n", &group); + for (j = 0; j < group.used; j++) + { + if ((mask & 0x1) == 0) + { + //assert((i + 1) >= group.m[j]); + + printf(">> FOUND %zu @ %x !!!!!!!!!!!!!!\n", j, (unsigned int)i + 1); + + + } + + mask >>= 1; + + } + + + + } + + +#else + + if (_mm512_reduce_or_epi64(test) != 0) + { + for (j = 0; j < group.used; j++) + { + if (((uint8_t *)&test)[j] == 0) + { + //assert((i + 1) >= group.m[j]); + + printf(">> FOUND %zu @ %x !!!!!!!!!!!!!!\n", j, (unsigned int)i + 1); + + } + + + } + + } + +#endif + + + } + + //printf("%hhx\n", ((uint8_t *)&R)[0], ((uint8_t *)&mask)[0]); + + } + + //printf("counter=%d\n", counter); + + +} +#endif + + + diff --git a/src/analysis/scan/patterns/backends/bitap.h b/src/analysis/scan/patterns/backends/bitap.h new file mode 100644 index 0000000..1cb384c --- /dev/null +++ b/src/analysis/scan/patterns/backends/bitap.h @@ -0,0 +1,59 @@ + +/* Chrysalide - Outil d'analyse de fichiers binaires + * bitap.h - prototypes pour la méthode de recherche basée sur l'algorithme Bitap + * + * Copyright (C) 2022 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/>. + */ + + +#ifndef _ANALYSIS_SCAN_PATTERNS_BACKENDS_BITAP_H +#define _ANALYSIS_SCAN_PATTERNS_BACKENDS_BITAP_H + + +#include <glib-object.h> +#include <stdbool.h> + + +#include "../backend.h" + + + +#define G_TYPE_BITAP_BACKEND g_bitap_backend_get_type() +#define G_BITAP_BACKEND(obj) (G_TYPE_CHECK_INSTANCE_CAST((obj), G_TYPE_BITAP_BACKEND, GBitapBackend)) +#define G_IS_BITAP_BACKEND(obj) (G_TYPE_CHECK_INSTANCE_TYPE((obj), G_TYPE_BITAP_BACKEND)) +#define G_BITAP_BACKEND_CLASS(klass) (G_TYPE_CHECK_CLASS_CAST((klass), G_TYPE_BITAP_BACKEND, GBitapBackendClass)) +#define G_IS_BITAP_BACKEND_CLASS(klass) (G_TYPE_CHECK_CLASS_TYPE((klass), G_TYPE_BITAP_BACKEND)) +#define G_BITAP_BACKEND_GET_CLASS(obj) (G_TYPE_INSTANCE_GET_CLASS((obj), G_TYPE_BITAP_BACKEND, GBitapBackendClass)) + + +/* Méthode de recherche basée sur l'algorithme Bitap (instance) */ +typedef struct _GBitapBackend GBitapBackend; + +/* Méthode de recherche basée sur l'algorithme Bitap (classe) */ +typedef struct _GBitapBackendClass GBitapBackendClass; + + +/* Indique le type défini pour un moteur de recherche pour données. */ +GType g_bitap_backend_get_type(void); + +/* Crée une méthode de recherche basée sur l'algorithme Bitap. */ +GEngineBackend *g_bitap_backend_new(void); + + + +#endif /* _ANALYSIS_SCAN_PATTERNS_BACKENDS_BITAP_H */ |