blob: c4a72ca5277eee0320ada2415a59ff14872eb343 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
|
/* 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
{
/**
* Champs renseignés dans g_acism_backend_setup_for().
*/
const uint8_t *atoms; /* Motif remarquable */
size_t len; /* Nombre d'octets considérés */
/**
* Champs renseignés dans g_acism_backend_build_trie().
*/
bool is_first; /* Première instance rencontrée*/
union
{
uint32_t coverage[2]; /* Départ et quantité de suivis*/
struct
{
size_t first_source; /* Indice de première source */
uint32_t index; /* Position dans la liste */
};
};
} acism_source_t;
#define SOURCE_COVERAGE_START 0
#define SOURCE_COVERAGE_COUNT 1
#define SOURCE_COVERAGE_END 1
/* 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
#define ROOT_STATE_INDEX 0
/* 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 */
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;
#if __LONG_WIDTH__ < 64
/* Cellule du tableau compressé final */
typedef struct _acism_state_t
{
union
{
/* Indice 0 */
struct
{
unsigned int match : 1; /* Correspondance ici */
unsigned int unused : 4; /* Espace encore disponible */
unsigned int atom_size : 3; /* Taille d'atome représenté */
unsigned int suffix : 1; /* Correspondance ailleurs */
};
/* Indice 1 et + */
unsigned int code : 9; /* Position depuis la base */
};
unsigned int index : 23; /* Indice de saut */
} acism_state_t;
#else
/* Cellule du tableau compressé final */
typedef union _acism_state_t
{
/* Indice 0 */
struct
{
uint8_t match : 1; /* Correspondance ici */
uint8_t single_source : 1; /* Unique source à notifier */
uint8_t atom_size; /* Indice de saut */
uint8_t suffix : 1; /* Correspondance ailleurs */
};
/* Indice 1 et + */
uint32_t code; /* Position depuis la base */
/* Tous */
struct
{
uint32_t any; /* Saut de bits */
uint32_t index; /* Indice de saut */
};
} acism_state_t;
#endif
/* 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 */
uint32_t *coverages; /* Bornes de suivi de positions*/
};
/* 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 */
|
