diff options
Diffstat (limited to 'src/analysis/scan/patterns/tokens/nodes/masked.c')
| -rw-r--r-- | src/analysis/scan/patterns/tokens/nodes/masked.c | 735 |
1 files changed, 508 insertions, 227 deletions
diff --git a/src/analysis/scan/patterns/tokens/nodes/masked.c b/src/analysis/scan/patterns/tokens/nodes/masked.c index 8765b1d..2dbdb08 100644 --- a/src/analysis/scan/patterns/tokens/nodes/masked.c +++ b/src/analysis/scan/patterns/tokens/nodes/masked.c @@ -56,16 +56,19 @@ static void g_scan_token_node_masked_finalize(GScanTokenNodeMasked *); static void g_scan_token_node_masked_visit(GScanTokenNodeMasked *, scan_tree_points_t *); /* Inscrit la définition d'un motif dans un moteur de recherche. */ -static bool g_scan_token_node_masked_enroll(GScanTokenNodeMasked *, GScanContext *, GEngineBackend *, size_t, size_t *); +static bool g_scan_token_node_masked_enroll(GScanTokenNodeMasked *, GEngineBackend *, size_t, size_t *); + +/* Récupère un identifiant final pour un atome d'octets. */ +static bool g_scan_token_node_masked_build_id(GScanTokenNodeMasked *, GEngineBackend *); /* Détermine si un contenu d'intérêt est présent à une position. */ static bool check_scan_token_node_masked_content(const masked_byte_t *, size_t, phys_t, GBinContent *); /* Transforme les correspondances locales en trouvailles. */ -static void g_scan_token_node_masked_check_forward(const GScanTokenNodeMasked *, GScanContext *, GBinContent *, pending_matches_t *, node_search_offset_t *, bool, bool *); +static void g_scan_token_node_masked_check_forward(const GScanTokenNodeMasked *, scan_node_check_params_t *, TokenNodeCheckFlags, bool *); /* Transforme les correspondances locales en trouvailles. */ -static void g_scan_token_node_masked_check_backward(const GScanTokenNodeMasked *, GScanContext *, GBinContent *, pending_matches_t *, node_search_offset_t *, bool, bool *); +static void g_scan_token_node_masked_check_backward(const GScanTokenNodeMasked *, scan_node_check_params_t *, TokenNodeCheckFlags, bool *); @@ -102,8 +105,10 @@ static void g_scan_token_node_masked_class_init(GScanTokenNodeMaskedClass *klass node = G_SCAN_TOKEN_NODE_CLASS(klass); + node->apply = (apply_scan_token_node_flags_fc)NULL; node->visit = (visit_scan_token_node_fc)g_scan_token_node_masked_visit; node->enroll = (enroll_scan_token_node_fc)g_scan_token_node_masked_enroll; + node->build_id = (build_scan_token_node_id_fc)g_scan_token_node_masked_build_id; node->check_forward = (check_scan_token_node_fc)g_scan_token_node_masked_check_forward; node->check_backward = (check_scan_token_node_fc)g_scan_token_node_masked_check_backward; @@ -124,14 +129,14 @@ static void g_scan_token_node_masked_class_init(GScanTokenNodeMaskedClass *klass static void g_scan_token_node_masked_init(GScanTokenNodeMasked *masked) { - g_scan_token_node_set_flags(G_SCAN_TOKEN_NODE(masked), STNF_PROD); - masked->bytes = NULL; masked->len = 0; masked->raw = NULL; - masked->atoms = NULL; - masked->count = 0; + masked->raw_count = 0; + + masked->enrolled_atoms = NULL; + masked->enrolled_count = 0; } @@ -174,14 +179,14 @@ static void g_scan_token_node_masked_finalize(GScanTokenNodeMasked *masked) if (masked->bytes != NULL) free(masked->bytes); - for (i = 0; i < masked->count; i++) + for (i = 0; i < masked->raw_count; i++) exit_szstr(&masked->raw[i]); if (masked->raw != NULL) free(masked->raw); - if (masked->atoms != NULL) - free(masked->atoms); + if (masked->enrolled_atoms != NULL) + free(masked->enrolled_atoms); G_OBJECT_CLASS(g_scan_token_node_masked_parent_class)->finalize(G_OBJECT(masked)); @@ -305,7 +310,6 @@ static void g_scan_token_node_masked_visit(GScanTokenNodeMasked *node, scan_tree /****************************************************************************** * * * Paramètres : node = définition de la bribe à enregistrer. * -* context = contexte de l'analyse à mener. * * backend = moteur de recherche à préchauffer. * * maxsize = taille max. des atomes (mise en commun optimisée). * * slow = niveau de ralentissement induit (0 = idéal). [OUT] * @@ -318,7 +322,7 @@ static void g_scan_token_node_masked_visit(GScanTokenNodeMasked *node, scan_tree * * ******************************************************************************/ -static bool g_scan_token_node_masked_enroll(GScanTokenNodeMasked *node, GScanContext *context, GEngineBackend *backend, size_t maxsize, size_t *slow) +static bool g_scan_token_node_masked_enroll(GScanTokenNodeMasked *node, GEngineBackend *backend, size_t maxsize, size_t *slow) { bool result; /* Statut à retourner */ bool forced; /* Inclusion dans un scan ? */ @@ -333,6 +337,8 @@ static bool g_scan_token_node_masked_enroll(GScanTokenNodeMasked *node, GScanCon { *slow += (maxsize * 2); + node->raw = make_atoms_from_masked_bytes(node->bytes, node->len, &node->raw_count); + /** * Dans le cas bien précis de l'usage de l'algorithme Bitap pour les recherches * dans le contenu binaire à analyser, on tire parti du coût nul des recherches @@ -353,19 +359,23 @@ static bool g_scan_token_node_masked_enroll(GScanTokenNodeMasked *node, GScanCon else { - node->raw = make_atoms_from_masked_byte(node->bytes[0].value, node->bytes[0].mask, &node->count); + node->enrolled_atoms = malloc(node->raw_count * sizeof(tracked_scan_atom_t)); + node->enrolled_count = node->raw_count; - node->atoms = malloc(node->count * sizeof(tracked_scan_atom_t)); - - for (i = 0; i < node->count && result; i++) + for (i = 0; i < node->enrolled_count && result; i++) { - find_best_atom(&node->raw[i], maxsize, &node->atoms[i], NULL); + find_best_atom(&node->raw[i], maxsize, &node->enrolled_atoms[i], NULL); - result = enroll_prepared_atom(&node->raw[i], context, backend, &node->atoms[i]); + /** + * Correction : si l'atome ne représente qu'une vue partielle, + * la validation rapide ne peut s'appliquer. + */ + if (node->enrolled_atoms[i].fast_check) + node->enrolled_atoms[i].fast_check = (node->enrolled_atoms[i].len == node->len); - } + result = enroll_prepared_atom(&node->raw[i], backend, &node->enrolled_atoms[i]); - node->enrolled_count = node->count; + } } @@ -378,6 +388,34 @@ static bool g_scan_token_node_masked_enroll(GScanTokenNodeMasked *node, GScanCon /****************************************************************************** * * +* Paramètres : node = définition de la bribe à peaufiner. * +* backend = moteur de recherche à préchauffer. * +* * +* Description : Récupère un identifiant final pour un atome d'octets. * +* * +* Retour : Bilan de l'opération à renvoyer. * +* * +* Remarques : - * +* * +******************************************************************************/ + +static bool g_scan_token_node_masked_build_id(GScanTokenNodeMasked *node, GEngineBackend *backend) +{ + bool result; /* Statut à retourner */ + size_t i; /* Boucle de parcours #1 */ + + result = true; + + for (i = 0; i < node->enrolled_count && result; i++) + result = build_atom_pattern_id(&node->enrolled_atoms[i], backend); + + return result; + +} + + +/****************************************************************************** +* * * Paramètres : bytes = octets partiels avec leur masque à interpréter. * * len = quantité d'octets à interpréter. * * start = point d'analyse à respecter. * @@ -419,13 +457,10 @@ static bool check_scan_token_node_masked_content(const masked_byte_t *bytes, siz /****************************************************************************** * * -* Paramètres : node = définition de la bribe à manipuler. * -* context = contexte de l'analyse à mener. * -* content = accès au contenu brut pour vérifications (optim.) * -* matches = suivi des correspondances à consolider. * -* offset = tolérance dans les positions à appliquer. * -* not = indique si les résultats doivent être inversés. * -* skip = détermine si l'analyse est différée. [OUT] * +* Paramètres : node = définition de la bribe à manipuler. * +* params = accès direct aux éléments utiles aux validations. * +* cflags = altérations de traitement à respecter. * +* skip = détermine si l'analyse est différée. [OUT] * * * * Description : Transforme les correspondances locales en trouvailles. * * * @@ -435,37 +470,36 @@ static bool check_scan_token_node_masked_content(const masked_byte_t *bytes, siz * * ******************************************************************************/ -static void g_scan_token_node_masked_check_forward(const GScanTokenNodeMasked *node, GScanContext *context, GBinContent *content, pending_matches_t *matches, node_search_offset_t *offset, bool not, bool *skip) +static void g_scan_token_node_masked_check_forward(const GScanTokenNodeMasked *node, scan_node_check_params_t *params, TokenNodeCheckFlags cflags, bool *skip) { - bool initialized; /* Initialisation du suivi ? */ #ifndef NDEBUG bool forced; /* Inclusion dans un scan ? */ #endif - size_t ocount; /* Quantité de bornes présentes*/ - node_offset_range_t * const *ranges_ptr;/* Bornes d'espace à parcourir */ size_t i; /* Boucle de parcours #1 */ const tracked_scan_atom_t *atom; /* Atome correspondant */ - size_t count; /* Quantité de bribes trouvées */ - const phys_t *found; /* Localisations des bribes */ - size_t k; /* Boucle de parcours #2 */ - phys_t new_begin; /* Nouveau départ à tester */ - size_t o; /* Boucle de parcours #3 */ - const node_offset_range_t *range; /* Bornes d'espace à parcourir */ + GUMemSlice *atoms; /* Localisations des bribes */ + const umem_slice_iter_t *aiter; /* Boucle de parcours #2 */ + match_area_t *end; /* Borne de fin de parcours */ + match_area_t *pos; /* Position courante */ bool status; /* Bilan d'une correspondance */ - size_t pcount; /* Nombre de correspondances */ - match_area_t * const *pending_ptr; /* Correspondances actuelles */ - size_t p; /* Boucle de parcours #4 */ - match_area_t *pending; /* Correspondance à traiter */ + match_area_t *area; /* Correspondance à valider */ + match_area_t *next; /* Correspondance suivante */ phys_t after; /* Espace disposible après */ - phys_t min; /* Borne minimale déterminée */ - phys_t max; /* Borne maximale déterminée */ - phys_t j; /* Boucle de parcours #5 */ + phys_t min_end; /* Fin la plus proche possible */ + phys_t max_end; /* Fin la plus éloignée trouvée*/ + bool updated; /* Existence de correspondance */ + size_t rcount; /* Quantité de bornes présentes*/ + const node_offset_range_t *ranges; /* Bornes d'espace à parcourir */ + size_t r; /* Boucle de parcours #xxxxxxxxxxxx*/ + phys_t p; /* Boucle de parcours #xxxxxxxxxxxx*/ + phys_t updated_edge; /* Nouvelle bordure de motif */ + match_area_t *new_area; /* Copie de correspondance */ + + if (0x1) printf("=================== CHECK :: %s (skip? %d)\n", __FUNCTION__, *skip); if (*skip) return; - initialized = are_pending_matches_initialized(matches); - /** * Si l'analyse arrive à un ou plusieurs octets masqués, soit il s'agit du * premier noeud, et la génération d'atomes a été forcée pour obtenir des @@ -475,61 +509,103 @@ static void g_scan_token_node_masked_check_forward(const GScanTokenNodeMasked *n */ #ifndef NDEBUG forced = (g_scan_token_node_get_flags(G_SCAN_TOKEN_NODE(node)) & STNF_MAIN); - assert((!initialized && forced) || (initialized && (!forced || not))); + assert((!params->initialized && forced) || (params->initialized && (!forced || cflags & TNCF_KEEP_DISCARDED))); #endif - ranges_ptr = get_node_search_offset_ranges(offset, &ocount); - - /* Si aucune correspondance n'a été établie */ - if (!initialized) + if (!params->initialized) { for (i = 0; i < node->enrolled_count; i++) { - atom = &node->atoms[i]; + atom = &node->enrolled_atoms[i]; - found = g_scan_context_get_atom_matches(context, atom->pid, &count); + atoms = g_scan_context_get_atom_matches(params->context, atom->pid); - for (k = 0; k < count; k++) + if (atom->fast_check) { - assert(atom->pos == 0); + for (aiter = g_umem_slice_get_iter(atoms); aiter != NULL; aiter = aiter->next) + { + end = aiter->data_end; - new_begin = found[k]; + for (pos = aiter->data; pos < end; pos++) + { + /** + * La modification de la zone d'origine est possible dans tous les cas + * car cette zone a été allouée de façon dédiée à un type de correspondances + * et ne sera pas réutilisée comme autre source de correspondance ailleurs. + */ + pos->end = pos->start + atom->len; - /** - * Si des bornes sont spécifiées, la position de l'atome est testée. - * - * Dans la pratique, cette situation (non initialisée) ne peut provenir - * que d'un espace situé dans le vide, donc couvrant un large périmètre. - * La validation a ainsi de grandes chances de passer... - * - * Le motif pouvant amener à cette situation (pas d'initialisation, - * mais à décalage à considérer) est par exemple : - * - * ~( ?? ?1 ) - * - */ - if (ocount > 0) - { - if (!does_node_search_offset_include_pos_forward(offset, 0, new_begin)) - continue; - } + if (cflags & TNCF_KEEP_DISCARDED) + { + add_tail_match_area(pos, ¶ms->kept_areas); + params->kept_count++; + } - /** - * Existe-t-il assez de place pour faire tenir le motif masqué ? - */ - if ((new_begin + node->len) > matches->content_end) - continue; + else if (cflags & TNCF_CREATE_NEW) + { + add_tail_match_area(pos, ¶ms->created_areas); + params->created_count++; + } + + else + { + assert(cflags & TNCF_UPDATE_IN_PLACE); + + add_tail_match_area(pos, ¶ms->main_areas); + params->main_count++; - status = check_scan_token_node_masked_content(node->bytes, node->len, new_begin, content); + } + + } - if ((status && !not) || (!status && not)) + } + + } + + else + { + for (aiter = g_umem_slice_get_iter(atoms); aiter != NULL; aiter = aiter->next) { - /** - * Il ne peut y avoir qu'une seule séquence d'octets à un même - * emplacement, donc le couple (start, len) enregistré est - * unique. - */ - add_pending_match(matches, new_begin, node->len); + end = aiter->data_end; + + for (pos = aiter->data; pos < end; pos++) + { + status = check_scan_token_node_masked_content(node->bytes, node->len, + pos->start, params->content); + + if (status) + { + /** + * La modification de la zone d'origine est possible dans tous les cas + * car cette zone a été allouée de façon dédiée à un type de correspondances + * et ne sera pas réutilisée comme autre source de correspondance ailleurs. + */ + pos->end = pos->start + node->len; + + if (cflags & TNCF_KEEP_DISCARDED) + { + add_tail_match_area(pos, ¶ms->kept_areas); + params->kept_count++; + } + + else if (cflags & TNCF_CREATE_NEW) + { + add_tail_match_area(pos, ¶ms->created_areas); + params->created_count++; + } + + else + { + assert(cflags & TNCF_UPDATE_IN_PLACE); + + add_tail_match_area(pos, ¶ms->main_areas); + params->main_count++; + + } + + } + + } } @@ -539,69 +615,77 @@ static void g_scan_token_node_masked_check_forward(const GScanTokenNodeMasked *n } - /* Si les correspondances en place sont à confirmer et compléter */ + /** + * Poursuite des traitements sur des correspondances déjà amorcées, impliquant + * des comparaisons entières de motifs. + */ else { - reset_pending_matches_ttl(matches); + if (0x1) printf(" LIST : %p (sz = %zu)\n", params->main_areas, params->main_count); - pending_ptr = get_all_pending_matches(matches, &pcount); - - for (p = 0; p < pcount; p++) + for_each_match_area_safe(area, ¶ms->main_areas, next) { - pending = (*pending_ptr) + p; + assert(area->end <= params->content_end); + + after = params->content_end - area->end; - assert(pending->end <= matches->content_end); + if (0x1) printf("---------- iter @ %u -> %u\n", (unsigned int)area->start, (unsigned int)area->end); + + /** + * S'il s'avère qu'il existe de multiples correspondances dans l'espace + * analysé, c'est la prise en compte d'une éventuelle avarice quant aux + * distances consommées qui va sélectionner la position d'une bribe de + * correspondance retenue. + * + * Par exemple, deux correspondances '?1 ?1 [1-3] ?2 ?2' peuvent être + * valides pour un même contenu : + * + * aa.bbb -> correspondance 'aa.bb' + * ^ + * + * aa.bbb -> correspondance 'aa..bb' + * ^ + */ - after = matches->content_end - pending->end; + min_end = params->content_end; + max_end = params->content_start; - new_begin = pending->end; + updated = false; - if (ocount > 0) + /* Souplesse dans les positions ? */ + if (offsets_exist(¶ms->offset)) { - for (o = 0; o < ocount; o++) + ranges = get_node_search_offset_ranges_2(¶ms->offset, &rcount); + + for (r = 0; r < rcount; r++) { - range = (*ranges_ptr) + o; - - /** - * Si bornes de tolérance il y a, l'espace restant est validé en - * tenant compte de ces bornes. - */ - if (!get_node_offset_range(range, node->len, after, &min, &max)) - continue; - - /** - * Une recherche des différentes correspondances amont est lancée. - */ - for (j = min; j <= max; j++) + assert(ranges[r].has_max); + assert((ranges[r].max - ranges[r].min) <= MAX_RANGE_FOR_MANUAL_CHECK); + + for (p = ranges[r].min; p <= ranges[r].max; p++) { + /** + * Si la fin d'une correspondance potentielle est trop près de + * la fin du contenu binaire et ne peut contenir le motif + * représenté, alors la corresponance est écartée sans appel. + */ + if ((p + node->len) > after) + break; + status = check_scan_token_node_masked_content(node->bytes, node->len, - new_begin + j, content); + area->end + p, params->content); - if ((status && !not) || (!status && not)) + if (status) { - /** - * S'il s'avère qu'il existe de multiples correspondances dans l'espace - * analysé, c'est la fonction extend_pending_match_ending() qui - * duplique cette correspondance, en s'appuyant sur le TTL pour - * repérer ce cas de figure. - * - * Par exemple, deux correspondances '?1 ?1 [1-3] ?2 ?2' - * sont valides pour un même contenu : - * - * aa.bbb -> correspondance 'aa.bb' - * ^ - * - * aa.bbb -> correspondance 'aa..bb' - * ^ - */ - extend_pending_match_ending(matches, p, new_begin + j + node->len); + updated_edge = area->end + p + node->len; - /** - * Comme l'extension a pu conduire à un ajout et donc à une - * réallocation de la liste, on recharge l'élément pour les - * itérations suivantes. - */ - pending = (*pending_ptr) + p; + if (updated_edge < min_end) + min_end = updated_edge; + + if (updated_edge > max_end) + max_end = updated_edge; + + updated = true; } @@ -611,55 +695,133 @@ static void g_scan_token_node_masked_check_forward(const GScanTokenNodeMasked *n } + /* Position immédiatement attendue */ else { /** * Si la fin d'une correspondance potentielle est trop près de * la fin du contenu binaire et ne peut contenir le motif - * représenté, alors la corresponance est écartée. + * représenté, alors la corresponance est écartée sans appel. */ - if (node->len > after) - continue; + if (node->len <= after) + { + status = check_scan_token_node_masked_content(node->bytes, node->len, + area->end, params->content); + + if (status) + { + updated_edge = area->end + node->len; + + min_end = updated_edge; + max_end = updated_edge; + + updated = true; + + } + + } - new_begin = pending->end; + } - status = check_scan_token_node_masked_content(node->bytes, node->len, new_begin, content); + if (updated) + { + /** + * Si seuls les rejets sont d'intérêt, les correspondances établies + * ne se voient pas mises à jours ni retirées. + */ - if ((status && !not) || (!status && not)) + if ((cflags & TNCF_KEEP_DISCARDED) == 0) { - extend_pending_match_ending(matches, p, new_begin + node->len); + if (cflags & TNCF_UPDATE_IN_PLACE) + area->end = (1 /* greedy */ ? min_end : max_end); - /** - * Comme il n'y a qu'une seule itération par correspondance, - * nul besoin de recharcher l'élément. - */ + else if (cflags & TNCF_CREATE_NEW) + { + new_area = g_umem_slice_alloc(params->allocator); + + *new_area = *area; + + new_area->end = (1 /* greedy */ ? min_end : max_end); + + add_tail_match_area(new_area, ¶ms->created_areas); + params->created_count++; + + } + +#ifndef NDEBUG + else + assert(false); +#endif } } - } + else + { + /** + * Si la liste principale doit être mise à jour... + */ - purge_pending_matches(matches); + if (cflags & TNCF_UPDATE_IN_PLACE) + { + del_match_area(area, ¶ms->main_areas); + assert(params->main_count > 0); + params->main_count--; + } + + /** + * Au cas où le rejet est d'intérêt, l'absence de correspondance + * est conservée dans une liste dédiée. + */ + + if (cflags & TNCF_KEEP_DISCARDED) + { + if (cflags & TNCF_UPDATE_IN_PLACE) + { + add_tail_match_area(area, ¶ms->kept_areas); + params->kept_count++; + } + + else if (cflags & TNCF_CREATE_NEW) + { + new_area = g_umem_slice_alloc(params->allocator); + + *new_area = *area; + + new_area->end = (1 /* greedy */ ? min_end : max_end); + + add_tail_match_area(new_area, ¶ms->kept_areas); + params->kept_count++; + + } + +#ifndef NDEBUG + else + assert(false); +#endif + + } + + } + + } } - set_pending_matches_initialized(matches); + params->initialized = true; - disable_all_ranges_in_node_search_offset(offset); + disable_all_ranges_in_node_search_offset(¶ms->offset); } /****************************************************************************** * * -* Paramètres : node = définition de la bribe à manipuler. * -* context = contexte de l'analyse à mener. * -* content = accès au contenu brut pour vérifications (optim.) * -* matches = suivi des correspondances à consolider. * -* offsets = tolérance dans les positions à appliquer. * -* not = indique si les résultats doivent être inversés. * -* skip = détermine si l'analyse est différée. [OUT] * +* Paramètres : node = définition de la bribe à manipuler. * +* params = accès direct aux éléments utiles aux validations. * +* cflags = altérations de traitement à respecter. * +* skip = détermine si l'analyse est différée. [OUT] * * * * Description : Transforme les correspondances locales en trouvailles. * * * @@ -669,26 +831,32 @@ static void g_scan_token_node_masked_check_forward(const GScanTokenNodeMasked *n * * ******************************************************************************/ -static void g_scan_token_node_masked_check_backward(const GScanTokenNodeMasked *node, GScanContext *context, GBinContent *content, pending_matches_t *matches, node_search_offset_t *offset, bool not, bool *skip) +static void g_scan_token_node_masked_check_backward(const GScanTokenNodeMasked *node, scan_node_check_params_t *params, TokenNodeCheckFlags cflags, bool *skip) { #ifndef NDEBUG bool forced; /* Inclusion dans un scan ? */ #endif - size_t pcount; /* Nombre de correspondances */ - match_area_t * const *pending_ptr; /* Correspondances actuelles */ - size_t ocount; /* Quantité de bornes présentes*/ - node_offset_range_t * const *ranges_ptr;/* Bornes d'espace à parcourir */ - size_t p; /* Boucle de parcours #1 */ - const match_area_t *pending; /* Correspondance à traiter */ - phys_t before; /* Espace disposible avant */ - phys_t new_begin; /* Nouveau départ à tester */ - size_t o; /* Boucle de parcours #2 */ - const node_offset_range_t *range; /* Bornes d'espace à parcourir */ - phys_t min; /* Borne minimale déterminée */ - phys_t max; /* Borne maximale déterminée */ - phys_t j; /* Boucle de parcours #3 */ + + + bool status; /* Bilan d'une correspondance */ + + match_area_t *area; /* Correspondance à valider */ + match_area_t *next; /* Correspondance suivante */ + phys_t before; /* Espace disposible avant */ + phys_t min_start; /* Début le plus proche trouvé */ + phys_t max_start; /* Début le plus distant trouvé*/ + bool updated; /* Existence de correspondance */ + size_t rcount; /* Quantité de bornes présentes*/ + const node_offset_range_t *ranges; /* Bornes d'espace à parcourir */ + size_t r; /* Boucle de parcours #xxxxxxxxxxxx*/ + phys_t p; /* Boucle de parcours #xxxxxxxxxxxx*/ + phys_t updated_edge; /* Nouvelle bordure de motif */ + match_area_t *new_area; /* Copie de correspondance */ + + if (0x1) printf("=================== CHECK :: %s (skip? %d)\n", __FUNCTION__, *skip); + if (*skip) return; @@ -696,7 +864,7 @@ static void g_scan_token_node_masked_check_backward(const GScanTokenNodeMasked * * En lecture à rebourd, au moins un noeud a été solicité pour analyse (lors * du sens de lecteur normal). Donc l'initialisation a déjà dû avoir lieu. */ - assert(are_pending_matches_initialized(matches)); + assert(params->initialized); /** * Si les recherches associées au noeud ont été forcées, alors les traitements @@ -707,65 +875,121 @@ static void g_scan_token_node_masked_check_backward(const GScanTokenNodeMasked * assert(!forced); #endif - reset_pending_matches_ttl(matches); - pending_ptr = get_all_pending_matches(matches, &pcount); - ranges_ptr = get_node_search_offset_ranges(offset, &ocount); - for (p = 0; p < pcount; p++) + /** + * ............. + */ + if (0) { - pending = (*pending_ptr) + p; - assert(matches->content_start <= pending->start); - before = pending->start - matches->content_start; + ; + + - new_begin = pending->start - node->len; + } + + /** + * Poursuite des traitements sur des correspondances déjà amorcées, impliquant + * des comparaisons entières de motifs. + */ + else + { + if (0x1) printf(" LIST : %p (sz = %zu)\n", params->main_areas, params->main_count); - if (ocount > 0) + for_each_match_area_safe(area, ¶ms->main_areas, next) { - for (o = 0; o < ocount; o++) + assert(params->content_start <= area->start); + + before = area->start - params->content_start; + + if (0x1) printf("---------- iter @ %u -> %u\n", (unsigned int)area->start, (unsigned int)area->end); + + /** + * Il ne peut y avoir qu'une seule séquence d'octets à un même + * emplacement. En revanche, des modificateurs peuvent construire + * possédant une même base, mais offrant des suffixes différents + * (par exemple, un marqueur nul UTF-16 final en complément). + * + * L'ensemble des combinaisons produites doit ainsi être exploré. + */ + + min_start = params->content_start; + max_start = params->content_end; + + updated = false; + + /* Souplesse dans les positions ? */ + if (offsets_exist(¶ms->offset)) { - range = (*ranges_ptr) + o; + ranges = get_node_search_offset_ranges_2(¶ms->offset, &rcount); - /** - * Si bornes de tolérance il y a, l'espace restant est validé en - * tenant compte de ces bornes. - */ - if (!get_node_offset_range(range, node->len, before, &min, &max)) + for (r = 0; r < rcount; r++) { - if (not) - extend_pending_match_beginning(matches, p, pending->start - node->len); + assert(ranges[r].has_max); + assert((ranges[r].max - ranges[r].min) <= MAX_RANGE_FOR_MANUAL_CHECK); + + for (p = ranges[r].min; p <= ranges[r].max; p++) + { + /** + * Si la fin d'une correspondance potentielle est trop près de + * la fin du contenu binaire et ne peut contenir le motif + * représenté, alors la corresponance est écartée sans appel. + */ + if ((p + node->len) > before) + break; + + status = check_scan_token_node_masked_content(node->bytes, node->len, + area->start - node->len - p, + params->content); + + if (status) + { + updated_edge = area->start - node->len - p; + + if (updated_edge > min_start) + min_start = updated_edge; + + if (updated_edge < max_start) + max_start = updated_edge; + + updated = true; - continue; + } + + } } + } + + /* Position immédiatement attendue */ + else + { /** - * Une recherche des différentes correspondances amont est lancée. + * Si la fin d'une correspondance potentielle est trop près du + * début du contenu binaire et ne peut contenir le motif + * représenté, alors la corresponance est écartée sans appel. */ - for (j = min; j <= max; j++) + if (node->len <= before) { status = check_scan_token_node_masked_content(node->bytes, node->len, - new_begin - j, content); + area->start - node->len, + params->content); - if ((status && !not) || (!status && not)) + if (status) { - /** - * S'il s'avère qu'il existe de multiples correspondances dans l'espace - * analysé, c'est la fonction extend_pending_match_beginning() qui - * duplique cette correspondance, en s'appuyant sur le TTL pour - * repérer ce cas de figure. - */ - extend_pending_match_beginning(matches, p, new_begin); + updated_edge = area->start - node->len; - /** - * Comme l'extension a pu conduire à un ajout et donc à une - * réallocation de la liste, on recharge l'élément pour les - * itérations suivantes. - */ - pending = (*pending_ptr) + p; + if (updated_edge > min_start) + min_start = updated_edge; + + if (updated_edge < max_start) + max_start = updated_edge; + + updated = true; } @@ -773,35 +997,92 @@ static void g_scan_token_node_masked_check_backward(const GScanTokenNodeMasked * } - } - - else - { - /** - * Si le début d'une correspondance potentielle est trop près du début - * du contenu binaire et ne peut contenir le motif représenté, alors - * la corresponance est écartée. - */ - if (node->len > before) + if (updated) { - if (not) - extend_pending_match_beginning(matches, p, new_begin); + /** + * Si seuls les rejets sont d'intérêt, les correspondances établies + * ne se voient pas mises à jours ni retirées. + */ + + if ((cflags & TNCF_KEEP_DISCARDED) == 0) + { + if (cflags & TNCF_UPDATE_IN_PLACE) + area->start = (1 /* greedy */ ? min_start : max_start); + + else if (cflags & TNCF_CREATE_NEW) + { + new_area = g_umem_slice_alloc(params->allocator); + + *new_area = *area; + + new_area->start = (1 /* greedy */ ? min_start : max_start); + + add_tail_match_area(new_area, ¶ms->created_areas); + params->created_count++; + + } + +#ifndef NDEBUG + else + assert(false); +#endif - continue; + } } - status = check_scan_token_node_masked_content(node->bytes, node->len, new_begin, content); + else + { + /** + * Si la liste principale doit être mise à jour... + */ + + if (cflags & TNCF_UPDATE_IN_PLACE) + { + del_match_area(area, ¶ms->main_areas); + assert(params->main_count > 0); + params->main_count--; + } + + /** + * Au cas où le rejet est d'intérêt, l'absence de correspondance + * est conservée dans une liste dédiée. + */ - if ((status && !not) || (!status && not)) - extend_pending_match_beginning(matches, p, new_begin); + if (cflags & TNCF_KEEP_DISCARDED) + { + if (cflags & TNCF_UPDATE_IN_PLACE) + { + add_tail_match_area(area, ¶ms->kept_areas); + params->kept_count++; + } + + else if (cflags & TNCF_CREATE_NEW) + { + new_area = g_umem_slice_alloc(params->allocator); + + *new_area = *area; + + new_area->start = (1 /* greedy */ ? min_start : max_start); + + add_tail_match_area(new_area, ¶ms->kept_areas); + params->kept_count++; + + } + +#ifndef NDEBUG + else + assert(false); +#endif + + } + + } } } - purge_pending_matches(matches); - - disable_all_ranges_in_node_search_offset(offset); + disable_all_ranges_in_node_search_offset(¶ms->offset); } |