TD — Séance 6 — Pointeurs de fonctions et généricité

Déclarations, tables de dispatch, comparateurs, rappels, conteneurs génériques

TD de la séance 6 de Programmation C avancée : adresse d’une fonction, types, tables de dispatch, rappels, qsort, conteneurs génériques.

Auteur

Dr. El Hadji Bassirou TOURÉ · DMI/FST/UCAD

Objectif

Lire et écrire des types de pointeurs de fonctions, dérouler une table de dispatch relevée dans un dump, diagnostiquer des comparateurs, suivre les appels d’un qsort, raisonner sur des fonctions de rappel et lire un tableau dynamique générique en mémoire. Machine x86-64 little-endian, Linux, gcc 13, glibc 2.39 : int et float 4 octets, short 2, long, size_t et pointeurs 8 ; exécutable PIE chargé à la base 0x555555554000 (aléa désactivé). Les fonctions vg_init, vg_elem, vg_ajouter et vg_liberer sont celles du cours (VecteurG : donnees, taille, capacite, taille_elem). qsort de la glibc 2.39 (stdlib/qsort.c) trie par fusion : moitié gauche de $\lfloor n/2\rfloor$ éléments, fusion par comparaison des têtes ; tampon dans la pile jusqu’à 1024 octets, par malloc au-delà, tri indirect au-delà de 32 octets par élément, tri par tas seulement si malloc échoue (les versions 2.37 et 2.38 utilisaient un introsort).

Exercice 1 : lecture et écriture de déclarations

long *r(int, char);
void (*s)(char *);
int *(*u[5])(double);
char (*(*w)(void))[8];
void (*enregistrer(int code, void (*f)(int)))(int);
int atexit(void (*f)(void));

Lire en français chacune des six déclarations.
Donner le type de u[3], puis celui de *w, et enfin celui de (*w)().
Réécrire la déclaration de enregistrer à l’aide de typedef void (*Rappel)(int);.
Écrire les déclarations : k, pointeur vers fonction (double, double) rendant double ; actions, tableau de 3 pointeurs vers fonction (int *) rendant void ; fabrique, fonction (char) rendant un pointeur vers fonction (int) rendant int. Réécrire fabrique avec un typedef nommé Unaire.
fabrique rend l’adresse de int triple(int x) { return 3 * x; }. Que vaut fabrique('t')(7) ? actions[2] contient raz, définie par void raz(int *p) { *p = 0; }, et int x = 5; : que fait actions[2](&x) ?

Exercice 2 : la table d’un porte-monnaie électronique

Un porte-monnaie électronique applique ses opérations par une table de dispatch (soldes et montants en FCFA) :

typedef long (*Operation)(long, long);
long depot(long s, long m)
{
    return s + m;
}
long retrait(long s, long m)
{
    return m <= s ? s - m : s;
}

long commission(long s, long m)
{
    (void)m;
    return s - s / 100;
}
long bonus(long s, long m)
{
    return s + m / 20;
}
Operation menu[4] = {...};  /* 4 cases */

menu, initialisé à sa définition, est en .data ; ses 32 octets, relevés à l’exécution, sont recopiés en 0x20 (adresse abrégée). nm donne : depot 1317, retrait 1334, commission 135e, bonus 139d.

Addr	+0	+1	+2	+3	+4	+5	+6	+7
`0x20`	`34`	`53`	`55`	`55`	`55`	`55`	`00`	`00`
`0x28`	`9d`	`53`	`55`	`55`	`55`	`55`	`00`	`00`
`0x30`	`17`	`53`	`55`	`55`	`55`	`55`	`00`	`00`
`0x38`	`5e`	`53`	`55`	`55`	`55`	`55`	`00`	`00`

Retrouver la fonction rangée dans chaque case de menu, en justifiant le calcul pour menu[0].
Le solde vaut 25 000 FCFA. On applique solde = menu[code](solde, montant) pour les cinq couples (code, montant) : (2, 10 000), (0, 40 000), (1, 6 000), (3, 0), (0, 15 000). Remplir le tableau.

opération code montant fonction appelée solde après

1 2 10 000

2 0 40 000

3 1 6 000

4 3 0

5 0 15 000
Quels octets du dump faut-il modifier pour que le code 1 applique commission au lieu de bonus ?
Que se passe-t-il pour le code 4 ? Et pour un code lu au clavier sans contrôle ? Écrire la vérification à ajouter.

opération	code	montant
1	2	10 000
2	0	40 000
3	1	6 000
4	3	0
5	0	15 000

Exercice 3 : diagnostic de trois comparateurs

/* (a) */
int cmp_sup(const void *a, const void *b)
{
    return *(const int *)a > *(const int *)b;
}
int t[4] = {9, 4, 7, 1};
qsort(t, 4, sizeof t[0], cmp_sup);
int cle = 4;
int *p = bsearch(&cle, t, 4, sizeof t[0],
                 cmp_sup);

/* (b) */
int cmp_ecart(const void *a, const void *b)
{
    return (int)(*(const double *)a
                 - *(const double *)b);
}
double m[4] = {2.75, 2.5, 1.0, 2.25};
qsort(m, 4, sizeof m[0], cmp_ecart);
/* (c) */
const char *v[4] = {"Bignona", "Goudiry",
                    "Ndioum", "Bambey"};
qsort(v, 4, sizeof v[0], (Cmp)strcmp);

Cmp est int (*)(const void *, const void *). Exécutés, ces fragments donnent : (a) t trié en 1 4 7 9, mais bsearch rend l’adresse de 7 ; (b) 1.00 2.75 2.50 2.25 ; (c) v inchangé.

Pour chaque comparateur, dire quelle règle du contrat est violée, et expliquer le résultat observé. Pour (a), dérouler la recherche de bsearch (indices 0 à 3, milieu de [g, d) en $(g+d)/2$).
Pourquoi (a) donne-t-il un tableau trié par qsort de la glibc 2.39 ? Ce résultat est-il garanti ?
Écrire les trois comparateurs corrects.
Écrire un comparateur pour struct Envoi { char ville[12]; long montant; } : montant décroissant, puis ville par ordre alphabétique.

Exercice 4 : les appels d’un `qsort`

int t[7] = {14, 3, 25, 9, 30, 1, 17}; est trié par qsort(t, 7, sizeof t[0], cmp_trace), où cmp_trace affiche (x,y) à chaque appel et compare par (x > y) - (x < y).

Dessiner l’arbre des découpages.
Remplir le tableau des fusions, dans l’ordre d’exécution ; combien d’appels au total ?

fusion appels (x,y) résultat
Combien de comparaisons le tri par insertion du cours fait-il sur ce tableau ? Donner le détail par élément inséré.
Même question pour le tableau trié dans l’ordre décroissant, {30, 25, 17, 14, 9, 3, 1} : compter les appels de qsort (fusion) et de l’insertion. Conclure.

Exercice 5 : rappels et contexte

int compter_si(const int *t, size_t n,
               int (*p)(int))
{
    int k = 0;
    for (size_t i = 0; i < n; i++)
        if (p(t[i]))
            k++;
    return k;
}
void pour_chaque(const int *t, size_t n,
                 void (*f)(int, void *),
                 void *ctx)
{
    for (size_t i = 0; i < n; i++)
        f(t[i], ctx);
}

int pluvieux(int mm) { return mm >= 10; }
int sec(int mm) { return mm == 0; }
typedef struct {
    int jour;
    int max;
    int jour_max;
} Record;
void record(int mm, void *ctx)
{
    Record *r = ctx;
    if (mm > r->max) {
        r->max = mm;
        r->jour_max = r->jour;
    }
    r->jour++;
}

Relevés de pluie d’une semaine à Ziguinchor, en mm : int pluie[7] = {12, 0, 35, 4, 0, 51, 18};

Que valent compter_si(pluie, 7, pluvieux) et compter_si(pluie, 7, sec) ?
Après Record r = {0, -1, -1}; pour_chaque(pluie, 7, record, &r);, que valent les trois champs de r ? Combien de fois record est-elle appelée, et par qui ?
Écrire une fonction de rappel cumul qui, passée à pour_chaque avec l’adresse d’un int total = 0, y accumule la pluie de la semaine. Que vaut total ?
On écrit par erreur pour_chaque(pluie, 7, record, &total);. Le compilateur le signale-t-il ? Que fait record ?

Exercice 6 : un tableau générique de candidats

typedef struct { int matricule; float note; short annee; char serie; } Candidat; Un VecteurG v a été créé par vg_init(&v, sizeof(Candidat), 2), puis a reçu trois candidats. La structure est recopiée en 0x00 ; son bloc, précédé de l’en-tête de la glibc, en 0x60 (adresses abrégées : donnees y est écrit 0x60). Les octets de padding des éléments ont été remplis avec aa.

Addr	+0	+1	+2	+3	+4	+5	+6	+7
`0x00`	`60`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x08`	`03`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x10`	`04`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x18`	`0c`	`00`	`00`	`00`	`00`	`00`	`00`	`00`

Addr	+0	+1	+2	+3	+4	+5	+6	+7
`0x58`	`41`	`00`	`00`	`00`	`00`	`00`	`00`	`00`
`0x60`	`3d`	`1e`	`00`	`00`	`00`	`00`	`58`	`41`
`0x68`	`e9`	`07`	`53`	`aa`	`7a`	`1e`	`00`	`00`
`0x70`	`00`	`00`	`1c`	`41`	`e9`	`07`	`4c`	`aa`
`0x78`	`eb`	`1e`	`00`	`00`	`00`	`00`	`74`	`41`
`0x80`	`e8`	`07`	`53`	`aa`	`00`	`00`	`00`	`00`
`0x88`	`00`	`00`	`00`	`00`	`00`	`00`	`00`	`00`

Lire les quatre champs de v. Donner sizeof(Candidat), et l’offset de chaque champ.
Lire l’en-tête : taille du bloc, octets utiles, places.
Lire le candidat d’indice 1 (matricule, note — un float IEEE 754 —, année, série). Où est son octet de padding ?
Donner vg_elem(&v, 2) et la note de ce candidat.
Deux ajouts de plus : où chacun est-il copié, avec quel realloc ?
Écrire le comparateur par_note (note décroissante) et l’appel de qsort qui trie les éléments du vecteur sur place.

Exercice 7 (approfondissement) : la table de sauts d’un `switch`

int tarif(int categorie)
{
    switch (categorie) {
    case 1:
        return 150;
    case 2:
        return 300;
    case 3:
        return 75;
    case 4:
        return 600;
    case 5:
        return 1250;
    case 6:
        return 40;
    default:
        return 0;
    }
}

Sortie de objdump -d (extrait) :

1151: mov    %edi,-0x4(%rbp)
1154: cmpl   $0x6,-0x4(%rbp)
1158: ja     11a8 <tarif+0x5f>
115a: mov    -0x4(%rbp),%eax
115d: lea    0x0(,%rax,4),%rdx
1165: lea    0xe98(%rip),%rax        # 2004
116c: mov    (%rdx,%rax,1),%eax
116f: cltq
1171: lea    0xe8c(%rip),%rdx        # 2004
1178: add    %rdx,%rax
117b: notrack jmp *%rax
117e: mov    $0x96,%eax
1185: mov    $0x12c,%eax
118c: mov    $0x4b,%eax
1193: mov    $0x258,%eax
119a: mov    $0x4e2,%eax
11a1: mov    $0x28,%eax
11a8: mov    $0x0,%eax
11ad: pop    %rbp
11ae: ret

Sortie de objdump -s -j .rodata :

 2000 01000200 a4f1ffff 7af1ffff 81f1ffff  ........z.......
 2010 88f1ffff 8ff1ffff 96f1ffff 9df1ffff  ................
 2020 25642025 64202564 2025640a 00        %d %d %d %d..

Retirés de l’extrait : le prologue (endbr64, push, mov %rsp,%rbp) et le jmp 11ad qui suit chaque mov $…,%eax.

Que font cmpl $0x6 et ja ? Pourquoi une catégorie négative est-elle elle aussi envoyée vers 0x11a8 ?
La table commence en 0x2004. Combien d’entrées a-t-elle, de combien d’octets ? Calculer l’adresse visée par chaque entrée, et l’associer à son cas.
Pourquoi la table a-t-elle une entrée pour la valeur 0, et où mène-t-elle ?
Dérouler tarif(4), tarif(0), tarif(9) et tarif(-3) : instructions exécutées et valeur rendue.