From 83dccba3a9b6c18d6fe7b6f30794a16336803962 Mon Sep 17 00:00:00 2001 From: Cyrille Bagard Date: Thu, 15 Oct 2015 19:18:31 +0000 Subject: Detected loops as introduced in the book "Compilers: Principles, Techniques, and Tools". git-svn-id: svn://svn.gna.org/svn/chrysalide/trunk@596 abbe820e-26c8-41b2-8c08-b7b2b41f8b0a --- ChangeLog | 16 ++ src/analysis/disass/area.c | 6 +- src/analysis/disass/loop.c | 595 +++++++++++++++++++++++++++++++++++++++++++++ src/arch/arm/context.c | 2 + src/common/bits.c | 194 ++++++++++++++- src/common/bits.h | 25 +- 6 files changed, 826 insertions(+), 12 deletions(-) diff --git a/ChangeLog b/ChangeLog index 7964745..f5894ff 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,19 @@ +15-10-15 Cyrille Bagard + + * src/analysis/disass/area.c: + Add more checks. + + * src/analysis/disass/loop.c: + Detect loops as introduced in the book + "Compilers: Principles, Techniques, and Tools". + + * src/arch/arm/context.c: + Add one extra check. + + * src/common/bits.c: + * src/common/bits.h: + Define more features for bit fields. + 15-10-14 Cyrille Bagard * src/analysis/disass/area.c: diff --git a/src/analysis/disass/area.c b/src/analysis/disass/area.c index b45e7fc..de2c742 100644 --- a/src/analysis/disass/area.c +++ b/src/analysis/disass/area.c @@ -554,6 +554,8 @@ bool load_code_from_mem_area(mem_area **list, size_t *count, size_t *index, cons diff = compute_vmpa_diff(&prev, &pos); + assert(diff == 4 || diff == 2); /* FIXME */ + init_mrange(&range, &prev, diff); g_arch_instruction_set_range(instr, &range); @@ -840,7 +842,7 @@ void fill_mem_area(mem_area **list, size_t *count, size_t *index, const GLoadedB copy_vmpa(&start, get_mrange_addr(&area->range)); advance_vmpa(&start, i); - if (area->exec && get_virt_addr(&start) % 2 == 0) + if (area->exec && get_virt_addr(&start) % 4/*2 - FIXME */ == 0) { refresh = load_code_from_mem_area(list, count, index, binary, ctx, &start, info); @@ -1396,6 +1398,8 @@ static bool insert_extra_symbol_into_mem_areas(mem_area **list, size_t *count, G /* Si le symbole est construit avec une localisation partielle, on complète ! */ if (get_phy_addr(&sym_pos) == VMPA_NO_PHYSICAL || get_virt_addr(&sym_pos) == VMPA_NO_VIRTUAL) { + assert(false); + diff = compute_vmpa_diff(&area_pos, &sym_pos); copy_vmpa(&sym_pos, &area_pos); diff --git a/src/analysis/disass/loop.c b/src/analysis/disass/loop.c index 5f97981..d9a3f2d 100644 --- a/src/analysis/disass/loop.c +++ b/src/analysis/disass/loop.c @@ -24,6 +24,592 @@ #include "loop.h" +#include +#include + + +#include "../../common/bits.h" + + + +/* Description de noeud, en référence à "Compilers: Principles, Techniques, and Tools" */ +typedef struct _dragon_node +{ + GArchInstruction *first; /* Arrivée d'un lien (début) */ + GArchInstruction *last; /* Départ d'un lien (fin) */ + + bitfield_t *bits; /* Représentation par masque */ + +} dragon_node; + + +/* Définition des blocs d'allocation */ +#define NODE_ALLOC_SIZE 100 + + +/* Dénombre le nombre de noeuds présents dans une routine. */ +static dragon_node *create_dragon_nodes(const GArchProcessor *, const instr_coverage *, const mrange_t *, const vmpa2t *, size_t *); + +/* Termine l'initialisation de noeuds trouvés dans une routine. */ +static void define_mask_for_nodes(dragon_node *, size_t); + +/* Supprime de la mémoire tous les noeuds détectés. */ +static void delete_dragon_nodes(dragon_node *, size_t); + +/* Recherche un noeud selon son intruction de départ. */ +static dragon_node *find_node_for_instruction(dragon_node *, size_t, bool, const GArchInstruction *); + +/* Détermine toute la chaîne hiérarchique de domination. */ +static void compute_all_dominators(dragon_node *, size_t); + +/* Matérialise les liens de retour arrière en tant que boucles. */ +static void detect_back_edges(dragon_node *, size_t); + +/* Suit un flot d'exécution à la recherche de boucles. */ +static void track_loops_in_code(const GArchProcessor *, const instr_coverage *, const mrange_t *, const vmpa2t *, memfield_t *); + + + +/****************************************************************************** +* * +* Paramètres : proc = ensemble d'instructions à parcourir. * +* coverage = zone de couverture où rechercher des instructions.* +* range = zone de couverture de la routine analysée. * +* start = adresse du début de l'analyse. * +* count = taille de la liste de noeuds retournés. [OUT] * +* * +* Description : Dénombre le nombre de noeuds présents dans une routine. * +* * +* Retour : Liste de noeuds initialisés de façon incomplète. * +* * +* Remarques : - * +* * +******************************************************************************/ + +static dragon_node *create_dragon_nodes(const GArchProcessor *proc, const instr_coverage *coverage, const mrange_t *range, const vmpa2t *start, size_t *count) +{ + dragon_node *result; /* Liste à créer et renvoyer */ + size_t allocated; /* Dimensionnement en mémoire */ + GArchInstruction *last; /* Mémorisation du passé */ + GArchInstruction *iter; /* Boucle de parcours */ + const mrange_t *irange; /* Emplacement d'instruction */ + InstructionLinkType *types; /* Type de lien entre instr. */ + size_t scount; /* Nombre de liens de dest. */ + size_t i; /* Boucle de parcours */ + dragon_node *new; /* Nouvel élément à créer */ + + result = NULL; + *count = 0; + + allocated = 0; + + for (last = NULL, iter = g_arch_processor_find_covered_instr_by_address(proc, coverage, start); + iter != NULL; + last = iter, iter = g_arch_instruction_get_next_iter(iter /* FIXME : list*/, iter, ~0)) + { + /* L'instruction sort-elle des clous ? */ + + irange = g_arch_instruction_get_range(iter); + + if (!mrange_contains_mrange(range, irange)) + break; + + /* Analyse des sources */ + + if (result == NULL) + { + (*count)++; + + if (*count >= allocated) + { + allocated += NODE_ALLOC_SIZE; + result = (dragon_node *)realloc(result, allocated * sizeof(dragon_node)); + } + + new = &result[*count - 1]; + + new->first = iter; + + } + else + { + scount = g_arch_instruction_get_sources(iter, NULL, &types); + if (scount == 0) continue; + + for (i = 0; i < scount; i++) + switch (types[i]) + { + case ILT_EXEC_FLOW: + case ILT_JUMP: + case ILT_CASE_JUMP: + case ILT_JUMP_IF_TRUE: + case ILT_JUMP_IF_FALSE: + + if (*count > 0) + result[*count - 1].last = last; + + (*count)++; + i = scount; + + if (*count >= allocated) + { + allocated += NODE_ALLOC_SIZE; + result = (dragon_node *)realloc(result, allocated * sizeof(dragon_node)); + } + + new = &result[*count - 1]; + + new->first = iter; + + break; + + default: + break; + + } + + } + + } + + if (*count > 0) + result[*count - 1].last = last; + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : nodes = liste de noeuds détectés dans une routine. * +* count = taille de cette liste de noeuds à traiter. * +* * +* Description : Termine l'initialisation de noeuds trouvés dans une routine. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void define_mask_for_nodes(dragon_node *nodes, size_t count) +{ + size_t i; /* Boucle de parcours */ + + for (i = 0; i < count; i++) + nodes[i].bits = create_bit_field(count, i > 0); + + set_in_bit_field(nodes[0].bits, 0, 1); + +} + + +/****************************************************************************** +* * +* Paramètres : nodes = liste de noeuds détectés dans une routine. * +* count = taille de cette liste de noeuds à traiter. * +* * +* Description : Supprime de la mémoire tous les noeuds détectés. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void delete_dragon_nodes(dragon_node *nodes, size_t count) +{ + size_t i; /* Boucle de parcours */ + + for (i = 0; i < count; i++) + delete_bit_field(nodes[i].bits); + + free(nodes); + +} + + +/****************************************************************************** +* * +* Paramètres : nodes = liste de noeuds détectés dans une routine. * +* count = taille de cette liste de noeuds à parcourir. * +* final = précise si l'instruction visée est la première. * +* instr = instruction à retrouver en tant que début de noeud. * +* * +* Description : Recherche un noeud selon son intruction de départ. * +* * +* Retour : Noeud trouvé ou NULL si aucune trouvaille. * +* * +* Remarques : - * +* * +******************************************************************************/ + +static dragon_node *find_node_for_instruction(dragon_node *nodes, size_t count, bool final, const GArchInstruction *instr) +{ + dragon_node *result; /* Résultat des recherches */ + const mrange_t *irange; /* Emplacement d'instruction */ + + int find_node_from_range(const mrange_t *range, const dragon_node *node) + { + int status; /* Bilan à retourner */ + const mrange_t *nrange; /* Emplacement de noeud */ + + nrange = g_arch_instruction_get_range(final ? node->last : node->first); + + status = cmp_mrange(range, nrange); + + return status; + + } + + irange = g_arch_instruction_get_range(instr); + + result = bsearch(irange, nodes, count, sizeof(dragon_node), (__compar_fn_t)find_node_from_range); + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : nodes = liste de noeuds détectés dans une routine. * +* count = taille de cette liste de noeuds à traiter. * +* * +* Description : Détermine toute la chaîne hiérarchique de domination. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void compute_all_dominators(dragon_node *nodes, size_t count) +{ + bitfield_t *inter; /* Intersection de dominations */ + bool changed; /* Note un changement qq part */ + size_t k; /* Boucle de parcours #1 */ + dragon_node *node; /* Noeud à traiter */ + dragon_node *predecessor; /* Noeud prédécesseur direct */ + GArchInstruction **srcs; /* Instructions d'origine */ + InstructionLinkType *types; /* Type de lien entre instr. */ + size_t scount; /* Nombre de liens de source */ + size_t i; /* Boucle de parcours #2 */ + + inter = create_bit_field(count, false); + + do + { + changed = false; + + for (k = 1; k < count; k++) + { + node = &nodes[k]; + + set_all_in_bit_field(inter); + + scount = g_arch_instruction_get_sources(node->first, &srcs, &types); + assert(scount > 0); + + for (i = 0; i < scount; i++) + switch (types[i]) + { + case ILT_EXEC_FLOW: + case ILT_JUMP: + case ILT_CASE_JUMP: + case ILT_JUMP_IF_TRUE: + case ILT_JUMP_IF_FALSE: + + predecessor = find_node_for_instruction(nodes, count, true, srcs[i]); + + + printf(" -- finding pred @ 0x%08x -> 0x%08x :: %p\n", + (unsigned int)g_arch_instruction_get_range(node->first)->addr.virtual, + (unsigned int)g_arch_instruction_get_range(srcs[i])->addr.virtual, + predecessor); + + + + if (predecessor == NULL) break; + + and_bit_field(inter, predecessor->bits); + break; + + default: + break; + + } + + set_in_bit_field(inter, k, 1); + + if (!is_bit_field_equal_to(node->bits, inter)) + { + copy_bit_field(node->bits, inter); + changed = true; + } + + } + + } + while (changed); + + delete_bit_field(inter); + +} + + + +/****************************************************************************** +* * +* Paramètres : nodes = liste de noeuds détectés dans une routine. * +* count = taille de cette liste de noeuds à traiter. * +* * +* Description : Matérialise les liens de retour arrière en tant que boucles. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void detect_back_edges(dragon_node *nodes, size_t count) +{ + size_t k; /* Boucle de parcours #1 */ + dragon_node *node; /* Noeud à traiter */ + GArchInstruction **dests; /* Instr. visée par une autre */ + InstructionLinkType *types; /* Type de lien entre lignes */ + size_t dcount; /* Nombre de liens de dest. */ + size_t i; /* Boucle de parcours #2 */ + dragon_node *target; /* Noeud référencé à tester */ + size_t id; /* Indice du bit associé */ + + + + printf("-----------------------------------------------------------------\n"); + + for (k = 0; k < count; k++) + { + node = &nodes[k]; + + printf("#[ node %zu ]# @ 0x%08x / 0x%08x - mask = 0x%08lx\n", k, + (unsigned int)g_arch_instruction_get_range(node->first)->addr.virtual, + (unsigned int)g_arch_instruction_get_range(node->last)->addr.virtual, + gfw(node->bits)); + + } + + printf("\n"); + + + + for (k = 1; k < count; k++) + { + node = &nodes[k]; + + dcount = g_arch_instruction_get_destinations(node->last, &dests, &types, NULL); + if (dcount == 0) continue; + + for (i = 0; i < dcount; i++) + switch (types[i]) + { + case ILT_EXEC_FLOW: + case ILT_JUMP: + case ILT_CASE_JUMP: + case ILT_JUMP_IF_TRUE: + case ILT_JUMP_IF_FALSE: + + target = find_node_for_instruction(nodes, count, false, dests[i]); + if (target == NULL) break; + + id = (target - nodes); + + if (test_in_bit_field(node->bits, id, 1)) + { + + printf("BACKEDGE :: 0x%08lx -> 0x%08lx\n", + (unsigned int)g_arch_instruction_get_range(node->last)->addr.virtual, + (unsigned int)g_arch_instruction_get_range(dests[i])->addr.virtual); + + + /* status = */g_arch_instruction_change_link(node->last, dests[i], types[i], ILT_LOOP); + + + } + + break; + + default: + break; + + } + + } + +} + + + +/****************************************************************************** +* * +* Paramètres : proc = ensemble d'instructions à parcourir. * +* coverage = zone de couverture où rechercher des instructions.* +* range = zone de couverture de la routine analysée. * +* start = adresse du début de l'analyse. * +* flow = ensemble des jalons de l'exécution du code. * +* * +* Description : Suit un flot d'exécution à la recherche de boucles. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void track_loops_in_code(const GArchProcessor *proc, const instr_coverage *coverage, const mrange_t *range, const vmpa2t *start, memfield_t *flow) +{ + dragon_node *nodes; /* Liste des noeuds détectés */ + size_t count; /* Taille de cette liste */ + + nodes = create_dragon_nodes(proc, coverage, range, start, &count); + assert(nodes != NULL); + + printf("nodes count :: %d\n", (int)count); + + define_mask_for_nodes(nodes, count); + + compute_all_dominators(nodes, count); + + detect_back_edges(nodes, count); + + delete_dragon_nodes(nodes, count); + +} + + +/****************************************************************************** +* * +* Paramètres : proc = ensemble d'instructions à relier. * +* routines = prototypes existants à insérer. * +* count = quantité de ces prototypes. * +* statusbar = barre de statut avec progression à mettre à jour.* +* id = identifiant du message affiché à l'utilisateur. * +* * +* Description : Détecte les boucles dans du code machine. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +void detect_loops_in_code(const GArchProcessor *proc, GBinRoutine **routines, size_t count, GtkExtStatusBar *statusbar, bstatus_id_t id) +{ + size_t i; /* Boucle de parcours */ + const mrange_t *range; /* Couverture d'une routine */ + const vmpa2t *start; /* Adresse de départ */ + const instr_coverage *coverage; /* Instructions couvertes */ + memfield_t *flow; /* Flot d'exécution à suivre */ + + //for (i = 286; i == 286; i++) + for (i = 0; i < count; i++) + { + + + range = g_binary_routine_get_range(routines[i]); + start = get_mrange_addr(range); + + + printf("====== '%s' @ 0x%08x\n", + g_binary_routine_get_name(routines[i]), + start->virtual); + + + coverage = g_arch_processor_find_coverage_by_address(proc, start); + + flow = NULL;//create_mem_field(range); + track_loops_in_code(proc, coverage, range, start, flow); + //delete_mem_field(flow); + + gtk_extended_status_bar_update_activity(statusbar, id, (i + 1) * 1.0 / count); + + } + + + printf("done\n\n"); + //exit(0); + + +} + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +//////////////////////////////////////////////////////////////////////////////////////////////////////////// +//////////////////////////////////////////////////////////////////////////////////////////////////////////// +//////////////////////////////////////////////////////////////////////////////////////////////////////////// +//////////////////////////////////////////////////////////////////////////////////////////////////////////// +//////////////////////////////////////////////////////////////////////////////////////////////////////////// +//////////////////////////////////////////////////////////////////////////////////////////////////////////// +//////////////////////////////////////////////////////////////////////////////////////////////////////////// +//////////////////////////////////////////////////////////////////////////////////////////////////////////// +//////////////////////////////////////////////////////////////////////////////////////////////////////////// +//////////////////////////////////////////////////////////////////////////////////////////////////////////// +//////////////////////////////////////////////////////////////////////////////////////////////////////////// +//////////////////////////////////////////////////////////////////////////////////////////////////////////// +//////////////////////////////////////////////////////////////////////////////////////////////////////////// +//////////////////////////////////////////////////////////////////////////////////////////////////////////// +//////////////////////////////////////////////////////////////////////////////////////////////////////////// +//////////////////////////////////////////////////////////////////////////////////////////////////////////// + + + +#if 0 + + #include #include #include @@ -193,6 +779,8 @@ void detect_loops_in_code(const GArchProcessor *proc, GBinRoutine **routines, si for (i = 0; i < count; i++) { + + range = g_binary_routine_get_range(routines[i]); start = get_mrange_addr(range); @@ -207,3 +795,10 @@ void detect_loops_in_code(const GArchProcessor *proc, GBinRoutine **routines, si } } + + + + + + +#endif diff --git a/src/arch/arm/context.c b/src/arch/arm/context.c index 386f21a..b54de42 100644 --- a/src/arch/arm/context.c +++ b/src/arch/arm/context.c @@ -267,6 +267,8 @@ void _g_arm_context_define_encoding(GArmContext *ctx, virt_t addr, unsigned int selected = find_disass_arm_area(ctx->areas, addr, 0, ctx->acount - 1); + assert(ctx->areas[selected].start != addr || ctx->areas[selected].marker == marker); + /* S'agit-il d'une redéfinition ? */ if (ctx->areas[selected].start == addr) ctx->areas[selected].marker = marker; diff --git a/src/common/bits.c b/src/common/bits.c index 1bd90f4..d451100 100644 --- a/src/common/bits.c +++ b/src/common/bits.c @@ -37,6 +37,7 @@ struct _bitfield_t { size_t length; /* Nombre de bits représentés */ + size_t requested; /* Nombre de mots alloués */ void *tail; /* Limite du tableau de bits */ @@ -46,7 +47,7 @@ struct _bitfield_t /* Crée un champ de bits initialisé à zéro. */ -static bitfield_t *_create_bit_field(size_t, size_t); +static bitfield_t *_create_bit_field(size_t, bool, size_t); /* Crée une copie de champ de bits initialisé à zéro. */ static bitfield_t *_create_bit_field_from(const bitfield_t *, size_t); @@ -64,6 +65,7 @@ static bitfield_t *_dup_bit_field(const bitfield_t *, size_t); /****************************************************************************** * * * Paramètres : length = nom de bits du champ à représenter. * +* state = état initial de chaque des bits. * * extra = espace mémoire supplémentaire à ajouter au final. * * * * Description : Crée un champ de bits initialisé à zéro. * @@ -74,7 +76,7 @@ static bitfield_t *_dup_bit_field(const bitfield_t *, size_t); * * ******************************************************************************/ -static bitfield_t *_create_bit_field(size_t length, size_t extra) +static bitfield_t *_create_bit_field(size_t length, bool state, size_t extra) { bitfield_t *result; /* Création à retourner */ size_t requested; /* Nombre de mots à allouer */ @@ -88,10 +90,14 @@ static bitfield_t *_create_bit_field(size_t length, size_t extra) result = (bitfield_t *)malloc(base + extra); result->length = length; + result->requested = requested; result->tail = ((char *)result) + base; - memset(result->bits, 0, requested * sizeof(unsigned long)); + if (state) + set_all_in_bit_field(result); + else + reset_all_in_bit_field(result); return result; @@ -101,6 +107,7 @@ static bitfield_t *_create_bit_field(size_t length, size_t extra) /****************************************************************************** * * * Paramètres : length = nom de bits du champ à représenter. * +* state = état initial de chaque des bits. * * * * Description : Crée un champ de bits initialisé à zéro. * * * @@ -110,9 +117,9 @@ static bitfield_t *_create_bit_field(size_t length, size_t extra) * * ******************************************************************************/ -bitfield_t *create_bit_field(size_t length) +bitfield_t *create_bit_field(size_t length, bool state) { - return _create_bit_field(length, 0); + return _create_bit_field(length, state, 0); } @@ -132,7 +139,7 @@ bitfield_t *create_bit_field(size_t length) static bitfield_t *_create_bit_field_from(const bitfield_t *field, size_t extra) { - return _create_bit_field(field->length, extra); + return _create_bit_field(field->length, false, extra); } @@ -177,6 +184,28 @@ void delete_bit_field(bitfield_t *field) /****************************************************************************** * * +* Paramètres : dest = champ de bits à modifier. * +* src = champ de bits à utiliser pour l'opération. * +* * +* Description : Copie un champ de bits dans un autre. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +void copy_bit_field(bitfield_t *dest, const bitfield_t *src) +{ + assert(dest->length == src->length); + + memcpy(dest->bits, src->bits, dest->requested * sizeof(unsigned long)); + +} + + +/****************************************************************************** +* * * Paramètres : field = champ de bits à dupliquer. * * extra = espace mémoire supplémentaire à ajouter au final. * * * @@ -193,7 +222,7 @@ static bitfield_t *_dup_bit_field(const bitfield_t *field, size_t extra) bitfield_t *result; /* Copie à retourner */ size_t requested; /* Nombre de mots à allouer */ - result = _create_bit_field(field->length, extra); + result = _create_bit_field(field->length, false, extra); requested = field->length / sizeof(unsigned long); if (field->length % sizeof(unsigned long) != 0) requested++; @@ -227,6 +256,44 @@ bitfield_t *dup_bit_field(const bitfield_t *field) /****************************************************************************** * * * Paramètres : field = champ de bits à modifier. * +* * +* Description : Bascule à 0 un champ de bits dans son intégralité. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +void reset_all_in_bit_field(bitfield_t *field) +{ + memset(field->bits, 0u, field->requested * sizeof(unsigned long)); + +} + + +/****************************************************************************** +* * +* Paramètres : field = champ de bits à modifier. * +* * +* Description : Bascule à 1 un champ de bits dans son intégralité. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +void set_all_in_bit_field(bitfield_t *field) +{ + memset(field->bits, ~0u, field->requested * sizeof(unsigned long)); + +} + + +/****************************************************************************** +* * +* Paramètres : field = champ de bits à modifier. * * first = indice du premier bit à traiter. * * count = nombre de bits à marquer. * * * @@ -263,6 +330,56 @@ void set_in_bit_field(bitfield_t *field, size_t first, size_t count) /****************************************************************************** * * +* Paramètres : dest = champ de bits à modifier. * +* src = champ de bits à utiliser pour l'opération. * +* * +* Description : Réalise une opération ET logique entre deux champs de bits. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +void and_bit_field(bitfield_t *dest, const bitfield_t *src) +{ + size_t i; /* Boucle de parcours */ + + assert(dest->length == src->length); + + for (i = 0; i < dest->requested; i++) + dest->bits[i] &= src->bits[i]; + +} + + +/****************************************************************************** +* * +* Paramètres : dest = champ de bits à modifier. * +* src = champ de bits à utiliser pour l'opération. * +* * +* Description : Réalise une opération OU logique entre deux champs de bits. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +void or_bit_field(bitfield_t *dest, const bitfield_t *src) +{ + size_t i; /* Boucle de parcours */ + + assert(dest->length == src->length); + + for (i = 0; i < dest->requested; i++) + dest->bits[i] |= src->bits[i]; + +} + + +/****************************************************************************** +* * * Paramètres : field = champ de bits à modifier. * * first = indice du premier bit à traiter. * * count = nombre de bits à marquer. * @@ -303,6 +420,64 @@ bool test_in_bit_field(bitfield_t *field, size_t first, size_t count) } +/****************************************************************************** +* * +* Paramètres : a = premier champ de bits à comparer. * +* b = second champ de bits à comparer. * +* * +* Description : Indique si deux champs de bits sont identiques ou non. * +* * +* Retour : true si les champs de bits sont égaux ou false sinon. * +* * +* Remarques : - * +* * +******************************************************************************/ + +bool is_bit_field_equal_to(const bitfield_t *a, const bitfield_t *b) +{ + bool result; /* Résultat à retourner */ + size_t i; /* Boucle de parcours */ + size_t remaining; /* Nombre de bits restants */ + + if (a->length != b->length) + return false; + + result = true; + + for (i = 0; i < (a->requested - 1) && result; i++) + result = (a->bits[i] == b->bits[i]); + + if (result) + { + remaining = a->length % sizeof(unsigned long); + + if (remaining == 0) + result = (a->bits[i] == b->bits[i]); + + else + { + remaining = (1 << (remaining + 1)) - 1; + + result = ((a->bits[i] & remaining) == (b->bits[i] & remaining)); + + } + + } + + return result; + +} + + + + +unsigned long gfw(const bitfield_t *field) +{ + return field->bits[0]; + +} + + /* ---------------------------------------------------------------------------------- */ /* CHAMPS LIES À UNE ZONE MEMOIRE */ @@ -312,6 +487,7 @@ bool test_in_bit_field(bitfield_t *field, size_t first, size_t count) /****************************************************************************** * * * Paramètres : range = espace mémoire à couvrir. * +* state = état initial de chaque des bits. * * * * Description : Crée un champ de bits couvrant une zone mémoire. * * * @@ -321,11 +497,11 @@ bool test_in_bit_field(bitfield_t *field, size_t first, size_t count) * * ******************************************************************************/ -memfield_t *create_mem_field(const mrange_t *range) +memfield_t *create_mem_field(const mrange_t *range, bool state) { bitfield_t *result; /* Création à retourner */ - result = _create_bit_field(get_mrange_length(range), sizeof(vmpa2t)); + result = _create_bit_field(get_mrange_length(range), state, sizeof(vmpa2t)); copy_vmpa((vmpa2t *)result->tail, get_mrange_addr(range)); diff --git a/src/common/bits.h b/src/common/bits.h index 6eeb19c..0e8ef65 100644 --- a/src/common/bits.h +++ b/src/common/bits.h @@ -37,7 +37,7 @@ typedef struct _bitfield_t bitfield_t; /* Crée un champ de bits initialisé à zéro. */ -bitfield_t *create_bit_field(size_t); +bitfield_t *create_bit_field(size_t, bool); /* Crée une copie de champ de bits initialisé à zéro. */ bitfield_t *create_bit_field_from(const bitfield_t *); @@ -45,15 +45,36 @@ bitfield_t *create_bit_field_from(const bitfield_t *); /* Supprime de la mémoire un champ de bits donné. */ void delete_bit_field(bitfield_t *); +/* Copie un champ de bits dans un autre. */ +void copy_bit_field(bitfield_t *, const bitfield_t *); + /* Crée une copie d'un champ de bits classique. */ bitfield_t *dup_bit_field(const bitfield_t *); +/* Bascule à 0 un champ de bits dans son intégralité. */ +void reset_all_in_bit_field(bitfield_t *); + +/* Bascule à 1 un champ de bits dans son intégralité. */ +void set_all_in_bit_field(bitfield_t *); + /* Bascule à 1 une partie d'un champ de bits. */ void set_in_bit_field(bitfield_t *, size_t, size_t); +/* Réalise une opération ET logique entre deux champs de bits. */ +void and_bit_field(bitfield_t *, const bitfield_t *); + +/* Réalise une opération OU logique entre deux champs de bits. */ +void or_bit_field(bitfield_t *, const bitfield_t *); + /* Détermine si un bit est à 1 dans un champ de bits. */ bool test_in_bit_field(bitfield_t *, size_t, size_t); +/* Indique si deux champs de bits sont identiques ou non. */ +bool is_bit_field_equal_to(const bitfield_t *, const bitfield_t *); + + + +unsigned long gfw(const bitfield_t *); /* ------------------------- CHAMPS LIES À UNE ZONE MEMOIRE ------------------------- */ @@ -64,7 +85,7 @@ typedef struct _bitfield_t memfield_t; /* Crée un champ de bits couvrant une zone mémoire. */ -memfield_t *create_mem_field(const mrange_t *); +memfield_t *create_mem_field(const mrange_t *, bool); /* Crée une copie de champ de bits couvrant une zone mémoire. */ memfield_t *create_mem_field_from(const memfield_t *); -- cgit v0.11.2-87-g4458