diff options
Diffstat (limited to 'src/analysis/scan/patterns/backends/acism.c')
| -rw-r--r-- | src/analysis/scan/patterns/backends/acism.c | 468 |
1 files changed, 344 insertions, 124 deletions
diff --git a/src/analysis/scan/patterns/backends/acism.c b/src/analysis/scan/patterns/backends/acism.c index 97f8561..53bad11 100644 --- a/src/analysis/scan/patterns/backends/acism.c +++ b/src/analysis/scan/patterns/backends/acism.c @@ -37,10 +37,10 @@ /* ---------------------- IMPLANTATION D'UNE NOUVELLE APPROCHE ---------------------- */ -/* Initialise la classe des méthodes basée sur Bitmap. */ +/* Initialise la classe des méthodes basée sur ACISM. */ static void g_acism_backend_class_init(GAcismBackendClass *); -/* Initialise une instance de méthodes basée sur Bitmap. */ +/* Initialise une instance de méthodes basée sur ACISM. */ static void g_acism_backend_init(GAcismBackend *); /* Supprime toutes les références externes. */ @@ -58,10 +58,10 @@ static void g_acism_backend_finalize(GAcismBackend *); 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); +static void g_acism_backend_setup_for(GAcismBackend *, const uint8_t *, size_t, uint32_t [2]); /* 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); +static bool g_acism_backend_enroll_plain_pattern(GAcismBackend *, const uint8_t *, size_t, uint32_t [2]); #ifdef __USE_BYTE_FREQ @@ -93,7 +93,13 @@ static void g_acism_backend_prepare_interleave_array(GAcismBackend *); 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 *); +static bool g_acism_backend_warm_up(GAcismBackend *); + +/* Récupère les identifiants finaux pour un motif recherché. */ +static patid_t g_acism_backend_build_plain_pattern_id(const GAcismBackend *, const uint32_t [2]); + +/* Détermine le nombre d'identifiants constitués. */ +static size_t g_acism_backend_count_plain_pattern_ids(const GAcismBackend *); /* Parcours un contenu binaire à la recherche de motifs. */ static void g_acism_backend_run_scan(const GAcismBackend *, GScanContext *); @@ -119,7 +125,7 @@ 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. * +* Description : Initialise la classe des méthodes basée sur ACISM. * * * * Retour : - * * * @@ -142,6 +148,8 @@ static void g_acism_backend_class_init(GAcismBackendClass *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->build_id = (build_backend_plain_pattern_id_fc)g_acism_backend_build_plain_pattern_id; + backend->count_ids = (count_backend_plain_pattern_ids_fc)g_acism_backend_count_plain_pattern_ids; backend->run_scan = (run_backend_scan_fc)g_acism_backend_run_scan; backend->output = (output_backend_stats_fc)g_acism_backend_output_stats; @@ -152,7 +160,7 @@ static void g_acism_backend_class_init(GAcismBackendClass *klass) * * * Paramètres : backend = instance à initialiser. * * * -* Description : Initialise une instance de méthodes basée sur Bitmap. * +* Description : Initialise une instance de méthodes basée sur ACISM. * * * * Retour : - * * * @@ -217,6 +225,21 @@ static void g_acism_backend_dispose(GAcismBackend *backend) static void g_acism_backend_finalize(GAcismBackend *backend) { + if (backend->sources != NULL) + free(backend->sources); + + if (backend->nodes != NULL) + free(backend->nodes); + + if (backend->bitmap_usage != NULL) + delete_bit_field(backend->bitmap_usage); + + if (backend->states != NULL) + free(backend->states); + + if (backend->coverages != NULL) + free(backend->coverages); + G_OBJECT_CLASS(g_acism_backend_parent_class)->finalize(G_OBJECT(backend)); } @@ -277,9 +300,9 @@ size_t g_acism_backend_get_atom_max_size(const GAcismBackend *backend) /****************************************************************************** * * * Paramètres : backend = moteur de recherche à préparer. * -* context = contexte de l'analyse à mener. * -* plain = chaîne de caractères classique à intégrer. * +* pattern = chaîne de caractères classique à intégrer. * * len = taille de cette chaîne. * +* tmp_id = identifiants temporaires vers le motif. [OUT] * * * * Description : Intègre un motif limité de contenu à rechercher. * * * @@ -289,74 +312,54 @@ size_t g_acism_backend_get_atom_max_size(const GAcismBackend *backend) * * ******************************************************************************/ -static patid_t g_acism_backend_setup_for(GAcismBackend *backend, GScanContext *context, const uint8_t *pattern, size_t len) +static void g_acism_backend_setup_for(GAcismBackend *backend, const uint8_t *pattern, size_t len, uint32_t tmp_id[2]) { - patid_t result; /* Identifiant à retourner */ - size_t i; /* Boucle de parcours */ - int ret; /* Bilan d'une comparaison */ + size_t current; /* Indice de source courante */ 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'. + * Les motifs '\x00\x00\x00\x00abcd1234' et '\x01\x01\x01\x01abcd1234' + * peuvent constituer deux cibles différentes, mais ils comportent + * normalement la même séquence atomique à rechercher : 'abcd1234'. + * + * Chaque motif 'abcd1234' proposé est enregistré ici, et se verra in fine + * attribuer un identifiant propre. Le regroupement des motifs identiques + * et la constitution des identifiants finaux sont réalisés au moment de la + * construction de l'arborescence de recherche. */ - for (i = 0; i < backend->sources_count; i++) - { - source = backend->sources + i; + /* Pré-inscription pour l'extérieur */ - if (source->len != len) - continue; + current = backend->sources_count; - ret = memcmp(source->atoms, pattern, len); + tmp_id[0] = current; + tmp_id[1] = 0; /* Non utilisé */ - 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)); + /* Inscription en interne */ - source = &backend->sources[backend->sources_count - 1]; + backend->sources = realloc(backend->sources, ++backend->sources_count * sizeof(acism_source_t)); - source->atoms = pattern; - source->len = len; + source = &backend->sources[current]; - result = g_scan_context_get_new_pattern_id(context); - source->pid = result; + source->atoms = pattern; + source->len = len; - backend->nchars += len; + backend->nchars += len; #ifdef __USE_BYTE_FREQ - for (i = 0; i < len; i++) - backend->frequencies[pattern[i]].frequency++; + 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. * +* tmp_id = identifiants temporaires vers le motif. [OUT] * * * * Description : Inscrit dans le moteur une chaîne de caractères à rechercher.* * * @@ -366,12 +369,14 @@ static patid_t g_acism_backend_setup_for(GAcismBackend *backend, GScanContext *c * * ******************************************************************************/ -static patid_t g_acism_backend_enroll_plain_pattern(GAcismBackend *backend, GScanContext *context, const uint8_t *plain, size_t len) +static bool g_acism_backend_enroll_plain_pattern(GAcismBackend *backend, const uint8_t *plain, size_t len, uint32_t tmp_id[2]) { - patid_t result; /* Identifiant à retourner */ + bool result; /* Bilan à retourner */ assert(len <= ACSIM_ATOM_SIZE); + result = true; + /** * Le traitement différé des chaînes à rechercher permet deux choses : * - la construction d'une table de permutation ; @@ -390,7 +395,7 @@ static patid_t g_acism_backend_enroll_plain_pattern(GAcismBackend *backend, GSca * moindre coût un jour. */ - result = g_acism_backend_setup_for(backend, context, plain, len); + g_acism_backend_setup_for(backend, plain, len, tmp_id); return result; @@ -460,7 +465,6 @@ static void g_acism_backend_define_codes(GAcismBackend *backend) /* 0 == racine */ backend->codes_count++; -#if 0 for (i = 0, iter = backend->frequencies; i < 256; i++, iter++) { if (iter->frequency == 0) @@ -469,10 +473,6 @@ static void g_acism_backend_define_codes(GAcismBackend *backend) 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 } @@ -501,6 +501,7 @@ static void g_acism_backend_build_trie(GAcismBackend *backend) size_t k; /* Boucle de parcours #2 */ acism_code_t code; /* Identifiant de symbole */ acism_trie_node_t *parent; /* Sauvegarde d'un accès */ + uint32_t current_start; /* Indice de gestionnaire */ backend->nodes = calloc(backend->nchars + 1, sizeof(acism_trie_node_t)); @@ -518,6 +519,8 @@ static void g_acism_backend_build_trie(GAcismBackend *backend) source = &backend->sources[i]; + /* Parcours des noeuds contenus */ + for (k = 0; k < source->len && node->child != NULL; k++) { #ifdef __USE_BYTE_FREQ @@ -579,36 +582,91 @@ static void g_acism_backend_build_trie(GAcismBackend *backend) } - /* Creéation d'une nouvelle branche avec le reliquat */ - for (; k < source->len; k++) + /* Si un atome (partiellement ?) identique a déjà été inscrit */ + if (k == source->len) + { + /** + * L'atome déjà inscrit est plus long, et on se trouve ici dans le + * parcours de l'arborescence qui mène à sa conclusion, sans + * inscription d'une fin de parcours au point courant. + */ + if (node->matched_atom == 0) + goto register_leaf; + + /** + * Rattachement au motif strictement identique. + */ + else + { + assert(backend->sources[node->matched_atom - 1].is_first); + + source->is_first = false; + source->first_source = node->matched_atom - 1; + source->index = backend->sources[source->first_source].coverage[SOURCE_COVERAGE_COUNT]++; + + } + + } + + else { + /* 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]]; + code = backend->codes_for_bytes[source->atoms[k]]; #else - code = 1 + source->atoms[k]; + code = 1 + source->atoms[k]; #endif - next->parent = node; - next->suffix_link = node; - next->data = source->atoms[k]; - next->code = code; + 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->child = next++; + node = node->child; - 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; + register_leaf: - } + node->matched_atom = i + 1; - node->matched_atom = i + 1; + source->is_first = true; + source->coverage[SOURCE_COVERAGE_COUNT] = 1; + + } } backend->nodes_used = next - backend->nodes; + /* Construction des bases pour identifiants */ + + current_start = 0; + + for (i = 0; i < backend->sources_count; i++) + { + source = &backend->sources[i]; + + if (source->is_first) + { + source->coverage[SOURCE_COVERAGE_START] = current_start; + + current_start += source->coverage[SOURCE_COVERAGE_COUNT]; + + } + + } + + assert(current_start == backend->sources_count); + } @@ -743,9 +801,6 @@ static int compare_node_according_to_code_range(const acism_trie_node_t **a, con if (result == 0) result = sort_unsigned_long(_b->children_count, _a->children_count); - - - } return result; @@ -780,13 +835,16 @@ static void g_acism_backend_prepare_interleave_array(GAcismBackend *backend) size_t last_free_state; /* Dernier emplacement dispo. */ size_t full_size; /* Cartographie entière */ bitfield_t *global_usage; /* Cartographie des usages */ +#ifndef NDEBUG + size_t pops[3]; /* Décomptes individuels */ + size_t bsum; /* Somme de tous les bits */ +#endif bitfield_t *usage; /* Cartographie locale */ acism_trie_node_t *node; /* Noeud en cours de traitement*/ + size_t highest; /* Poids du bit le plus fort */ acism_trie_node_t *iter; /* Boucle de parcours #2 */ + size_t first_freedom_word; /* Premier mot avec des dispos.*/ size_t free_state; /* Emplacement libre trouvé */ - bool found; /* Bilan de recherche */ - - size_t bsum; /* Préparation de la liste de noeuds à inscrire */ @@ -808,8 +866,16 @@ static void g_acism_backend_prepare_interleave_array(GAcismBackend *backend) full_size = last_free_state + 257; global_usage = create_bit_field(full_size, false); +#ifndef NDEBUG + + pops[0] = 0; + pops[1] = 0; + pops[2] = 0; + bsum = 0; +#endif + usage = create_bit_field(257, false); for (i = 0; i < backend->nodes_used; i++) @@ -822,26 +888,49 @@ static void g_acism_backend_prepare_interleave_array(GAcismBackend *backend) /* Préparation du masque du noeud */ + truncate_bit_field(&usage, 257); + reset_all_in_bit_field(usage); set_in_bit_field(usage, 0, 1); +#ifndef NDEBUG + pops[0]++; +#endif + + highest = 0; + for (iter = node->child; iter != NULL; iter = iter->sibling) + { set_in_bit_field(usage, iter->code, 1); +#ifndef NDEBUG + pops[0]++; +#endif + + if (iter->code > highest) + highest = iter->code; + + } + +#ifndef NDEBUG + pops[1] += popcount_for_bit_field(usage); +#endif + assert(popcount_for_bit_field(usage) == (node->children_count + 1)); + truncate_bit_field(&usage, ++highest); + /* Recherche d'une position idéale */ if (i == 0) + { + first_freedom_word = 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; - } + free_state = find_interleaving_index_for_acism(global_usage, usage, &first_freedom_word); /* Suivi global */ @@ -849,8 +938,10 @@ static void g_acism_backend_prepare_interleave_array(GAcismBackend *backend) or_bit_field_at(global_usage, usage, free_state); +#ifndef NDEBUG bsum += node->children_count + 1; assert(popcount_for_bit_field(global_usage) == bsum); +#endif node->state_index = free_state; @@ -865,6 +956,15 @@ static void g_acism_backend_prepare_interleave_array(GAcismBackend *backend) /* Sotie encadrée */ +#ifndef NDEBUG + + pops[2] = popcount_for_bit_field(global_usage); + + assert(pops[0] == pops[1]); + assert(pops[0] == pops[2]); + +#endif + backend->bitmap_usage = global_usage; delete_bit_field(usage); @@ -901,10 +1001,10 @@ static void g_acism_backend_prepare_interleave_array(GAcismBackend *backend) bitfield_t *usage; /* Cartographie locale */ size_t rd_pos; /* Tête de lecture */ size_t wr_pos; /* Tête d'écriture */ + size_t first_freedom_word; /* Premier mot avec des dispos.*/ 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; @@ -937,6 +1037,8 @@ static void g_acism_backend_prepare_interleave_array(GAcismBackend *backend) rd_pos++; + first_freedom_word = 0; + /* Suivi des liens déjà en place */ while (rd_pos < max_pos) @@ -961,11 +1063,7 @@ static void g_acism_backend_prepare_interleave_array(GAcismBackend *backend) /* 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; - } + free_state = find_interleaving_index_for_acism(global_usage, usage, &first_freedom_word); /* Suivi global */ @@ -1016,6 +1114,8 @@ static void g_acism_backend_build_interleave_array(GAcismBackend *backend) 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*/ + uint32_t *coverage; /* Couverture des inscriptions */ + acism_source_t *source; /* Définition originelle */ acism_trie_node_t *iter; /* Sous-noeud à inscrire #2 */ acism_trie_node_t *child; /* Sous-noeud à inscrire #3 */ uint16_t offset; /* Décalage local */ @@ -1023,7 +1123,7 @@ static void g_acism_backend_build_interleave_array(GAcismBackend *backend) maxsize = get_bit_field_size(backend->bitmap_usage); backend->states = calloc(maxsize, sizeof(acism_state_t)); - backend->pids = calloc(maxsize, sizeof(patid_t)); + backend->coverages = calloc(maxsize, 2 * sizeof(uint32_t)); for (i = 0; i < backend->nodes_used; i++) { @@ -1035,10 +1135,17 @@ static void g_acism_backend_build_interleave_array(GAcismBackend *backend) if (node->matched_atom > 0) { + source = &backend->sources[node->matched_atom - 1]; + base[0].match = 1; - base[0].atom_size = backend->sources[node->matched_atom - 1].len; + base[0].single_source = source->coverage[SOURCE_COVERAGE_COUNT] == 1 ? 1 : 0; + base[0].atom_size = backend->sources[node->matched_atom - 1].len - 1; + + coverage = &backend->coverages[node->state_index * 2]; - backend->pids[node->state_index] = backend->sources[node->matched_atom - 1].pid; + coverage[SOURCE_COVERAGE_START] = source->coverage[SOURCE_COVERAGE_START]; + coverage[SOURCE_COVERAGE_END] = coverage[SOURCE_COVERAGE_START] \ + + source->coverage[SOURCE_COVERAGE_COUNT]; for (iter = node->parent->suffix_link; iter != NULL; iter = iter->suffix_link) { @@ -1055,6 +1162,7 @@ static void g_acism_backend_build_interleave_array(GAcismBackend *backend) } } + base[0].index = i == 0 ? 0 : node->suffix_link->state_index; for (child = node->child; child != NULL; child = child->sibling) @@ -1080,14 +1188,18 @@ static void g_acism_backend_build_interleave_array(GAcismBackend *backend) * * * Description : Met en ordre les derniers détails avant un premier scan. * * * -* Retour : - * +* Retour : Bilan de l'opération. * * * * Remarques : - * * * ******************************************************************************/ -static void g_acism_backend_warm_up(GAcismBackend *backend) +static bool g_acism_backend_warm_up(GAcismBackend *backend) { + bool result; /* Bilan à retourner */ + + result = true; + #ifdef __USE_BYTE_FREQ /** @@ -1101,6 +1213,10 @@ static void g_acism_backend_warm_up(GAcismBackend *backend) /** * Construit une arborescence de lecture à partir des différents * octets présents dans les motifs. + * + * Les couvertures des futurs tableaux de correspondances sont + * établies au passage, ouvrant la voie aux définitions d'identifiant + * pour les motifs enregistrés. */ g_acism_backend_build_trie(backend); @@ -1118,6 +1234,76 @@ static void g_acism_backend_warm_up(GAcismBackend *backend) g_acism_backend_build_interleave_array(backend); + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : backend = moteur de recherche à manipuler. * +* tmp_id = identifiants temporaires vers le motif. [OUT] * +* * +* Description : Récupère les identifiants finaux pour un motif recherché. * +* * +* Retour : Identifiant constitué ou INVALID_PATTERN_ID en cas d'échec. * +* * +* Remarques : - * +* * +******************************************************************************/ + +static patid_t g_acism_backend_build_plain_pattern_id(const GAcismBackend *backend, const uint32_t tmp_id[2]) +{ + patid_t result; /* Identifiant à retourner */ + acism_source_t *source; /* Motif d'origine concerné */ + acism_source_t *reference; /* Renvoi vers un même motif */ + + assert(tmp_id[0] < backend->sources_count); + + /** + * L'indicateur tmp_id[1] n'est pas utilisé ici. + */ + + source = backend->sources + tmp_id[0]; + + if (source->is_first) + result = source->coverage[SOURCE_COVERAGE_START]; + + else + { + reference = backend->sources + source->first_source; + + assert(source->index < reference->coverage[SOURCE_COVERAGE_COUNT]); + + result = reference->coverage[SOURCE_COVERAGE_START] + source->index; + + } + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : backend = moteur de recherche à manipuler. * +* * +* Description : Détermine le nombre d'identifiants constitués. * +* * +* Retour : Quantité de gestionnaires de suivi à prévoir. * +* * +* Remarques : - * +* * +******************************************************************************/ + +static size_t g_acism_backend_count_plain_pattern_ids(const GAcismBackend *backend) +{ + size_t result; /* Quantité à retourner */ + + result = backend->sources_count; + + return result; + } @@ -1141,15 +1327,20 @@ static void g_acism_backend_run_scan(const GAcismBackend *backend, GScanContext vmpa2t pos; /* Point de départ ciblé */ const bin_t *data; /* Données à analyser */ #ifdef __USE_BYTE_FREQ - acism_code_t *codes_for_bytes; + acism_code_t codes_for_bytes[256]; /* Copie des codes d'accès */ #endif acism_state_t *root; /* Racine de l'arborescence */ - acism_state_t *state; /* Tête de lecture courante */ + uint32_t *coverages; /* Bornes de suivi de positions*/ + unsigned int 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*/ + unsigned int next; /* Prochaine tête à valider */ + acism_state_t next_state; /* Prochaine tête à valider */ + uint32_t k; /* Boucle de parcours #2 */ + uint32_t final_k; /* Dernier indice à traiter */ + unsigned int iter; /* Boucle de parcours #3 */ + acism_state_t test_state; /* Test de validité alternative*/ + acism_state_t sub_state; /* Test de validité alternative*/ content = g_scan_context_get_content(context); @@ -1161,18 +1352,20 @@ static void g_acism_backend_run_scan(const GAcismBackend *backend, GScanContext /* Suivi via l'arborescence aplatie */ #ifdef __USE_BYTE_FREQ - codes_for_bytes = backend->codes_for_bytes; + memcpy(&codes_for_bytes, backend->codes_for_bytes, 256 * sizeof(acism_code_t)); #endif root = backend->states; if (root == NULL) goto done; - state = root; + coverages = backend->coverages; + + state = ROOT_STATE_INDEX; for (i = 0; i < dlen; i++) { #ifdef __USE_BYTE_FREQ - code = 1 + codes_for_bytes[data[i]]; + code = codes_for_bytes[data[i]]; #else code = 1 + data[i]; #endif @@ -1183,12 +1376,15 @@ static void g_acism_backend_run_scan(const GAcismBackend *backend, GScanContext next = state + code; - if (next->code == code) - next = root + next->index; + if (root[next].code == code) + { + next = root[next].index; + next_state = root[next]; + } - else if (state != root) + else if (state != ROOT_STATE_INDEX) { - state = root + state->index; + state = root[state].index; goto retry; } @@ -1197,35 +1393,59 @@ static void g_acism_backend_run_scan(const GAcismBackend *backend, GScanContext /* Remontée d'éventuels résultats */ - if (next->match) + if (next_state.match) { - g_scan_context_register_atom_match(context, - backend->pids[next - root], - i + 1 - next->atom_size); + k = coverages[next * 2 + SOURCE_COVERAGE_START]; + + if (next_state.single_source) + g_scan_context_store_atom_match_end(context, k, i); + //g_umem_slice_put_uint64(matches[0/*k*/], i - next_state.atom_size); - if (next->suffix) + else { - for (iter = root + state->index; ; iter = root + iter->index) + final_k = coverages[next * 2 + SOURCE_COVERAGE_END]; + + for (; k < final_k; k++) + g_scan_context_store_atom_match_end(context, k, i); + //g_umem_slice_put_uint64(matches[0/*k*/], i - next_state.atom_size); + + } + + if (next_state.suffix) + { + for (iter = root[state].index; ; iter = root[iter].index) { - test = iter + code; + test_state = root[iter + code]; - if (test->code == code) + if (test_state.code == code) { - test = root + test->index; + sub_state = root[test_state.index]; - if (test->match) + if (sub_state.match) { - assert(test->atom_size < next->atom_size); + assert(sub_state.atom_size < next_state.atom_size); + + k = coverages[test_state.index * 2 + SOURCE_COVERAGE_START]; + + if (sub_state.single_source) + g_scan_context_store_atom_match_end(context, k, i); + //g_umem_slice_put_uint64(matches[0/*k*/], i - sub_state.atom_size); + + else + { + final_k = coverages[test_state.index * 2 + SOURCE_COVERAGE_END]; + + for (; k < final_k; k++) + g_scan_context_store_atom_match_end(context, k, i); + //g_umem_slice_put_uint64(matches[0/*k*/], i - sub_state.atom_size); - g_scan_context_register_atom_match(context, - backend->pids[test - root], - i + 1 - test->atom_size); + } } } - if (iter == root) + if (iter == ROOT_STATE_INDEX) break; } |