summaryrefslogtreecommitdiff
path: root/src/analysis/scan/patterns/backends
diff options
context:
space:
mode:
authorCyrille Bagard <nocbos@gmail.com>2023-01-30 06:59:35 (GMT)
committerCyrille Bagard <nocbos@gmail.com>2023-01-30 06:59:35 (GMT)
commitdb3b204dd7a71b2f74a4e69b2159a96e3ab66614 (patch)
tree34174311b7ac504f03a10a889ada7f28db7a06c0 /src/analysis/scan/patterns/backends
parent34ee1bfca78e8423cfa29329fdc756569d6b1960 (diff)
Save an initial version of rost.
Diffstat (limited to 'src/analysis/scan/patterns/backends')
-rw-r--r--src/analysis/scan/patterns/backends/Makefile.am27
-rw-r--r--src/analysis/scan/patterns/backends/acism-int.h160
-rw-r--r--src/analysis/scan/patterns/backends/acism.c1295
-rw-r--r--src/analysis/scan/patterns/backends/acism.h59
-rw-r--r--src/analysis/scan/patterns/backends/bitap-int.h118
-rw-r--r--src/analysis/scan/patterns/backends/bitap.c2766
-rw-r--r--src/analysis/scan/patterns/backends/bitap.h59
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 */