Examen

Vérifiez que vous avez acquis les connaissances nécessaires en C.

Compilation

Pointeurs

Exercices de manipulation de pointeurs.

Simple

int i = 42;
int *p = &i;

Allocation dynamique

int *t = malloc(10 * sizeof(int));

Rendre un pointeur

On vous demande de créer pour un utilisateur final une fonction nommée donne_tableau qui rend un tableau composé d'entiers.

La taille du tableau n'est pas connue a priori et peut changer d'un appel à l'autre (le tableau peut être modifié par d'autres utilisateurs sur le réseau par exemple) mais vous avez à votre disposition deux fonctions auxiliaires, inconnues de l'utilisateur final :

1. int donne_taille(); qui renvoie la taille du tableau,
2. int donne_valeur(size_t i); qui donne l'élément d'index i du tableau.

Pour vos tests et pour le rendu, vous pourrez implémenter ces deux fonctions par des stubs (méthodes minimales pour répondre au problème) comme ceux-ci :

int donne_taille() {
  return 10;
}

int donne_valeur(size_t i) {
  return (int)i;
}

Si l'utilisateur final ne connaît ni donne_taille ni de donne_valeur, la fonction donne_tableau doit obligatoirement rendre deux informations :

• le tableau d'entier
• sa taille

I faut donc pouvoir rendre 2 informations à l'utilisateur final alors que l'on ne peut en renvoyer qu'une avec un retour de fonction (return). La seconde information à donner à l'utilisateur final doit donc être rendue via un pointeur et il y a plusieurs façons de faire.

On vous demande d'écrire la fonction donne_tableau selon différentes manières de rendre les deux données nécessaires. Le corps de la fonction donne_tableau est ci-après :

XXX donne_tableau(XXX) {

  XXX

  // si on a un tableau t d'entier
  for (size_t i=0 ; i < donne_taille() ; i++) {
    t[i] = donne_valeur(i);
  }

  return XXX
}

On vous demande de remplir les XXX par le code nécessaire pour répondre à la question. Vous accompagnerez chaque implémentation d'un petit programme main illustrant son utilisation.

L'utilisateur final ne possède aucune information sur la taille du tableau à rendre et s'en remet à vous pour tout faire. Les versions 2, 3 et 4 de donne_tableau doivent donc créer le tableau en allouant de la mémoire avec un malloc.

Base16

On vous demande d'implémenter l'encodage/décodage en Base16, variante de l'encodage/décodage en base64 :

L'idée de ce type de codage est de convertir un flux de bytes (comme une image par exemple) en un flux de caractères ASCII. Le format texte étant plus facilement transportable via le web (ou le mail) qu'un flux binaire, ce moyen de transmission est encore très populaire.

On a le schéma suivant :

flux binaire entrée      transmission       flux binaire sortie
00011101110101101001 ->      bnngj       ->  00011101110101101

L'encodage en base16 associe à un groupe de 4bits successifs une lettre de l'alphabet entre a et p (16 lettres).

Si on utilise la table char *T = "abcdefghijklmnop", le flux binaire 00011101110101101001 est encodé de droite à gauche par les caractères :

1. 1001 binaire vaut 9 en décimal : on encode avec 'j' (T[9])
2. 0110 binaire vaut 6 en décimal : on encode avec 'g' (T[6])
3. 1101 binaire vaut 13 en décimal : on encode avec 'n' (T[13])
4. 1101 binaire vaut 13 en décimal : on encode avec 'n' (T[13])
5. 0001 binaire vaut 1 en décimal : on encode avec 'b' (T[1])
6. l'encodage final vaut : 'bnngj'

Le décodage de fait avec une fonction associant un entier à chaque lettre du code.

size_t decode(char c)

Vous allez vous focaliser sur les chaînes de caractères qui sont, en utf-8, des flux de char. Un char faisant 8b, chaque char est encodé en base16 par 2 lettres.

En utf-8, certains caractères sont codés sur 7b (les caractères ASCII), donc 1 byte, par exemple 'A' qui vaut l'entier' 65 ; d'autres sur 16b, comme 'é' qui est codé sur le tableau de 2 bytes [195, 169] ; d'autres sur encore plus, comme '好' qui est encodé sur le tableau de 3 bytes [229, 165, 189].

Vous pouvez vous en rendre compte en utilisant la fonction strlen :

Lorsque l'on utilise chaque char séparément pour un encodage en utf-8, il faut faire un peu attention car même si un char est codé sur 8 bits, il peut être considéré comme signé ou non. Comme nous avons besoin de considérer qu'un char est non signé pour rendre compte des caractères encodés sur plusieurs bytes : il nous faut convertir chaque char en entier non signé avant utilisation.

Dans son standard c23, le C définit un type pour cela, char8_t, mais il n'est pas sûr que vous l'ayez déjà. Pour s'éviter tout soucis, définissez son type dans votre code :

typedef unsigned char char8_t;

Et utilisez-le à chaque fois que vous devrez travailler avec un char d'une chaîne utf-8 sous la forme d'un entier (vous convertissant ce char en char8_t).

char8_t x;
for (size_t i=0 ; i < strlen(s) ; i ++) {
   x = (char8_t)s[i];
}

À chaque char8_t de la chaîne sera associé deux lettres, l'une correspondant aux 4 bits de poids faible (ceux encodant $2^0$ à $2^3$), l'autre aux 4 bits de poids fort (ceux encodant $2^4$ à $2^7$).

Par exemple le char correspondant à 'A' vaut 65 en char8_t donc $01000001$ en binaire :

• ses 4 bits de poids faible valent : $0001$
• ses 4 bits de poids fort valent : $0100$

Prendre les 4 bits de poids fort et les 4 bits de poids faible d'un char8_t peut se faire en utilisant des comparateurs de bits :

size_t faible(char8_t c);

size_t fort(char8_t c);

On peut maintenant associer à chaque char une chaîne de caractères composée des deux caractères.

void encode_char(char *sortie, char8_t c);

Vous pouvez maintenant écrire la fonction terminale :

char *encode_base16(char *s);

Pour terminer, il vous reste à implémenter le décodage. On va procéder en deux temps.

char8_t decode_char(char *cs);

La fonction précédente doit vous permettre d'écrire facilement la fonction qui décode :

char *decode_base16(char *s);

Vérifiez bien que tout fonctionne :