Cartouche

Barème

Règlement

La réalisation de cet exercice est assujettie aux règles en vigueur dans l’école en matière de triche et de normalisation. Tricher vous expose à de graves sanctions.

Vous devez respecter les règles de normalisation suivantes : https://git.ecole-89.com/eriizu/coding_style/src/branch/main/norm.md

Le non-respect de la norme vous fera perdre une partie ou la totalité des points qui auraient pu être acquis, sur l’ensemble du rendu.

Instructions de rendu

Respectez à la lettre les noms de fichiers et leur emplacement dans le dépôt de rendu. S’il vous est demandé de rendre un fichier nommé hello.c sans qu’un nom de dossier soit précisé : rendez un fichier hello.c à la racine de votre dépôt.

La présence d’une étoile * signifie que le nom du fichier peut être n’importe lequel dès lors qu’il porte l’extension ou l’affixe (préfixe/suffixe) demandée. Elle signifie aussi qu’il est possible de rendre plusieurs fichiers.

La présence d’une double étoile ** signifie que les fichiers peuvent être placés n’importe où dans un dossier, y compris dans des sous-dossiers.

Pensez à faire des commits et des push fréquemment. Autrement nous ne pouvons pas vous aider à retrouver vos fichiers perdus.

Fonctions autorisées et interdites

Par défaut, toute fonction système (comme write) ou fonction des bibliothèques (comme printf ou puts) sont interdites.

À chaque exercice vous sera donné une liste de fonction autorisées, le cas échéant.

Tests unitaires

Vous devez rendre un fichier de test unitaire pour chaque fonction demandée.

Correction du code source en C

Chaque exercice sera compilé indépendamment avec les options -Wall -Wextra -Werror ainsi que votre libstu.

Synopsis

Après avoir vu comment manipuler des données juste en copiant et en déplaçant des octets, on va aller encore plus plus loin. On va manipuler la plus petite unité possible : le bit.

Pour rappel, un octet est composé de 8 bits qui peuvent chacun valoir 0 ou 1, vrai ou faux.

Pour certaines informations, on a pas besoin d’un int, d’un short ou même d’un char tout entier. On peut se contenter de quelques bits. Ça nous permet d’être particulièrement économe en mémoire tout en en comprenant davantage sur comment les données sont encodés non pas au niveau des octets mais au niveau le plus bas : celui des bits.

Mais avant ça on va voir des outils qui nous permettent d’éviter les forêts de if dans nos programmes, les tables de décision.

Théorie : tables de décisions

Introduction

Vous avez surement déjà eu une situation où vous ressentiez le besoin d’écrire tout pleins de if else if ... ; problème : la norme vous l’empêche.

Pourtant il y a plein de situations valables dans lesquelles on pourrait avoir besoin de if else if ... à plus de quatre branches. Mais cette interdiction est présente pour éviter les situations ou une forêt de if rendrait le code trop difficile à lire.

Un exemple parfait c’est lorsque vous aviez du programmer votre algorithme pour sortir du labyrinthe dans le Projet 3 • Maze. Lorsque vous avez associé à chaque direction une valeur x et y à employer ou une fonction à appeler.

Prenons un exemple que l’on a déjà vu : une fonction qui associe un caractère à une opération :

int res;

res = 0;
if (op == '+') {
	res = a + b;
} else if (op == '-') {
	res = a - b;
} else if (op == '*') {
	res = a * b;
} else if (op == '/') {
	res = a / b;
} else if (op == '%') {
	res = a % b;
}
return res;

Il existe une autre manière d’exprimer cette forêt de if que la norme n’autorise pas, c’est les switch case.

int match_op_switch(char op, int a, int b)
{
    int res;

    res = 0;
    switch (op) {
    case '+':
        res = a + b;
        break;
    case '-':
        res = a - b;
        break;
    case '*':
        res = a * b;
        break;
    case '/':
        res = a / b;
        break;
    case '%':
        res = a % b;
    }
    return res;
}

Étonnamment, ça demande plus de lignes pour faire la même chose. On retrouve le même désavantage que chaque cas rend la fonction plus longue, ce qui signifie que dans un programme qui évolue, cette fonction de décision peut devenir de pire en pire.

En réalité avec seulement un caractère à match contre un autre, la fonction n’est pas difficile à lire, mais c’est en étudiant un cas simple que l’on peut découvrir les outils qui vont suivre, afin d’être prêts lorsqu’on en aura vraiment besoin (lors des projets qui suivent).

Pointeur sur fonction

Premier point nouveau : on peut stocker un pointeur vers une fonction dans une variable, un tableau ou encore un champ de structure.

La syntaxe pour déclarer une variable comme étant un pointeur sur fonction est la suivante :

int add(int a, int b)
{
	return a + b;
}

int sub(int a, int b)
{
	return a - b;
}

int main(void)
{
	int (*fptr)(int a, int b);

	fptr = add;
	printf("%d\n", fptr(100, 13));
	fptr = sub;
	printf("%d\n", fptr(100, 13));
	return 0;
}

La syntaxe se découpe donc ainsi type_de_retour (*nom_de_la_variable)(types_et_nom_des_params).

Table de correspondance

Avec une structure et un tableau sur cette structure on peut fabriquer une table de correspondances entre un caractère, une chaîne de caractères, un nombre, un élément d’énumération ou n’importe quoi et un pointeur sur fonction à appeler. On peut même stocker dans la structure des arguments à utiliser lors de l’appel à la fonction.

La structure aurait alors le rôle d’une ligne de notre table : on veillera à inclure “row” dans son nom.

Ainsi, pour nos opérations on peut construire la table et la structure suivante :

struct op_table_row {
	char symbol;
	int (*fptr)(int a, int b);
};

const struct op_table_row OP_TABLE[] = {
	{'+', add},
	{'-', sub},
	{'*', mul},
	{'/', divide},
	{'%', mod},
};

Maintenant pour effectuer notre opération, nous n’avons plus besoin d’une série de if ou d’un switch case. On peut utiliser une boucle. On peut déterminer la taille (en nombre d’éléments) d’un tableau déclaré avec des crochets avec un sizeof(le_tableau) / sizeof(un_element_du_tableau)

const unsigned int OP_TABLE_LEN = sizeof(OP_TABLE) / sizeof(struct op_table_row);

int run_op(char op, int a, int b)
{
    unsigned int idx;

    idx = 0;
    while (idx < OP_TABLE_LEN) {
        if (OP_TABLE[idx].symbol == op)
            return OP_TABLE[idx].fptr(a, b);
        idx += 1;
    }
    return 0;
}

Maintenant, si on veut que notre programme gère d’avantage d’opérations on peut simplement en ajouter à la liste :

const struct op_table_row OP_TABLE[] = {
	{'+', add},
	{'-', sub},
	{'*', mul},
	{'/', divide},
	{'%', mod},
	{'p', stu_pow},
	{'^', logical_xor},
	{'&', logical_and},
	{'|', logical_or},
};

Cela s’avère même plus simple que de modifier le code de la fonction run_op.

Exercice : mini calculatrice

Fichiers à rendre : mini_calculator.c, mini_calculator.h Fonctions autorisées : write

Écrivez le programme mini_calculator. Il a besoin de trois arguments. Le premier argument est un caractère qui correspond à l’opération à faire :

• +, -, *, /, % pour les opérations classiques
• p pour mettre le premier nombre à la puissance passée en deuxième nombre

Les deux autres arguments sont deux nombre entiers.

Le programme affiche le résultat de l’opération sur sa sortie standard.

Contrainte, vous devez passer par un table de décision pour sélectionner la bonne opération.

Exemple d’exécution :

$ make -C ../libstu && cp ../libstu/libstu.a .
$ gcc -Wall -Wextra -I../libstu/include mini_calculator.c libstu.a -o mini_calculator
$ ./mini_calculator
usage: ./mini_calculator operator operand_1 operand_2
$ ./mini_calculator + 100 13
113
$ ./mini_calculator "*" 50 4 # guillements nécessaire pour l'étoile
200
$ ./mini_calculator / 100 5
20

Exercice : + verbes

Fichiers à rendre : mini_calculator2.c, mini_calculator2.h Fonctions autorisées : write

Ajoutez à votre mini_calculator la possibilité de faire une opération en utilisant les verbes :

• add
• sub
• mul
• div
• mod
• pow

Sans pour autant retirer la possibilité d’utiliser les opérateurs.

$ ./mini_calculator + 100 13
113
$ ./mini_calculator add 100 13
113

Contrainte : vous devez utiliser la même table de décision que pour les symboles, vous pouvez adapter les champs des rows de votre table de décision. Vous avez le droit d’avoir plusieurs lignes qui font référence à la même fonction.

Exercice : + somme

Fichiers à rendre : mini_calculator3.c, mini_calculator3.h Fonctions autorisées : write, malloc, free

Ajoutez à votre mini_calculator la possibilité de faire des sommes et des moyennes avec un nombre variable d’arguments.

Utilisez les verbes et symboles :

• sum, s pour les sommes
• avg, a pour les moyennes

Contrainte : vous devez utiliser la même table de décision que pour les autres opérations, vous pouvez :

• adapter les paramètres de toutes vos fonctions ;
• adapter les champs des lignes de votre table de décision.

Exercice : girouette

Fichiers à rendre : coords.c, coords.h, coords.test.c

Mettez la structure et l’énumération suivantes dans coords.h

struct coords_2i {
	int x;
	int y;
};

enum cardinal_direction {
	NORTH,
	SOUTH,
	EAST,
	WEST,
	NORTH_EAST,
	NORTH_WEST,
	SOUTH_EAST,
	SOUTH_WEST,
};

Implémentez la fonction suivante :

void move_towards(struct coords_2i *pos,
                  enum cardinal_direction direction,
                  int distance);

Elle modifie pos en fonction de la distance et de la direction donnée. Vous devez utiliser une table de décision.

Écrivez aussi les tests de votre fonction dans coords.test.c

Exemple : si vous recevez la position $(5,5)$ et la direction NORTH, vous devez modifier la position pour qu’elle contienne $(5,4)$.

Théorie bitshift et masques

Littéraux

En C et en programmation en général, quand on a besoin d’un nombre particulier on peut simplement l’écrire.

int a;

a = 12;

12 dans cet exemple c’est un littéral. Un nombre littéral en base 10 (aussi appelé decimal ou juste dec en anglais).

Maintenant, il est aussi possible d’exprimer des nombres dans d’autres bases en utilisant un préfixe :

• 0b pour un nombre en binaire (base 2 – chiffres 0 et 1 – flag %b sur printf)
• 0 pour un nombre en octal (base 8 – chiffres de 0 à 7-- flag %o sur printf)
• 0x pour un nombre en hexadécimal (base 16 – chiffres de 0 à F – flag %x sur printf)

Ainsi :

• 0xF donne 15 en base 10
• 011 donne 9 en base 10
• 0b100 donne 4 en base 10

bitshift

Sur un nombre en binaire, on peut avoir besoin de déplacer les bits vers la gauche ou vers la droite. Pour ce faire on utilise les opérateurs << et >>.

Exemple :

#include <stdio.h>

int main(void)
{
    int nb;
    int nb_shifted;

    nb = 0b111;
    printf("before shift:\n%o\t%09b\n\n", nb, nb);
    nb_shifted = nb << 3;
    printf("after left shift:\n%o\t%09b\n\n", nb_shifted, nb_shifted);
    nb_shifted = nb_shifted << 3;
    printf("after left shift 2:\n%o\t%09b\n\n", nb_shifted, nb_shifted);
    nb_shifted = nb_shifted >> 6;
    printf("after right shift:\n%o\t%09b\n\n", nb_shifted, nb_shifted);
}

$ ./a.out
before shift:
7       000000111

after left shift:
70      000111000

after left shift 2:
700     111000000

after right shift:
7       000000111

Opérateurs logiques

Si vous avez fait de l’algèbre de Boole au lycée, vous avez surement une idée de la direction dans laquelle nous allons.

En C nous avons les opérateurs suivants pour travailler sur les bits d’un nombre :

• lhs & rhs ET logique entre tous les bits du lhs et rhs ;
• lhs | rhs OU logique entre tous les bits des opérandes ;
• lhs ^ rhs OU exclusif logique entre les nombres ;
• ~rhs NON logique sur un seul nombre.

Masques

Celle qui va le plus nous intéresser aujourd’hui c’est le & logique et la technique du bitmask.

Par exemple : si dans un nombre on veut vérifier que le premier bit est a 1 on peut faire :

int is_first_bit_set(int nb)
{
	if (nb & 0b1) {
		puts("first bit is set");
	} else {
		puts("first bit is not set");
	}
}

Mais pourquoi est-ce que cela marche ainsi ?

Mettons on reçoit 0b101101 en nombre dans nb : l’opération avec 0b1 donne :

	0101101
      &	0000001
	-------
	0000001

On a donc une valeur différente de 0 donc la condition passe.

Si on reçoit 0b1111110 :

	1111110
      &	0000001
	-------
	0000000

Tous les bits finissent à 0 donc la condition ne passe pas.

Si on veut vérifier le deuxième bit :

int is_second_bit_set(int nb)
{
	if (nb & 0b10) {
		puts("first bit is set");
	} else {
		puts("first bit is not set");
	}
}

Et ainsi de suite…

Exemples de situations dans lesquelles on utilise des masques :

• Le mode d’un fichier (Vous vous souvenez des valeurs du genre 644 qui accordent certaines permissions sur des fichiers à certaines personnes ? C’est en fait une série de masques.)
• Les arguments d’appels systèmes qui peuvent adopter pleins de comportements différents à la demande comme open.2.

Activer un bit avec un masque

#define MY_MASK 0b010
int main(void)
{
	char nb;

	nb = 0b101;
	nb = nb | MY_MASK;
	printf("%b\n", nb);
	// affiche 00000111

Chaque bit du nombre final est à 1 si il y a un bit a 1 dans nb ou dans le masque.

	000000010 (masque)
      |	000000101 (nb)
	---------
	000000111

Désactiver un bit avec un masque

Mettons on a le masque suivant 0b010 et on a un char qui contient 0b111. Si on veut désactiver le bit du masque on peut faire la chose suivante :

#define MY_MASK 0b010
int main(void)
{
	char nb;

	nb = 0b111;
	nb = nb & ~MY_MASK;
	printf("%b\n", nb);
	// affiche 00000101
}

On prend le complément du masque avec l’opérateur ~. Ça nous donne une valeur où tout les bits sont set sauf celui qui l’était dans le masque.

      ~	00000010 (masque)
	--------
	11111101 (complément du masque)

Si on fait un ET logique entre nb et ce complément, tous les bits set dans nb le resterons sauf celui qui est set dans le masque original.

	111111101 (complément du masque)
      &	000000111 (nb)
	---------
	000000101

Chaque bit du nombre résultant vaut 1 si les bits à la même position dans le complément du masque et dans nb sont tous les deux à 1.

Exemple complet

#include <stdio.h>

#define STATE_BURN      0b00001
#define STATE_FREEZE    0b00010
#define STATE_PARA      0b00100
#define STATE_POISON	0b01000
#define STATE_SLEEP     0b10000

struct pokemon {
    const char *name;
    int hp;
    int states;
};

void pkmn_init(struct pokemon *p, const char *name)
{
    p->name = name;
    p->hp = 100;
    p->states = 0;
}

void pkmn_state_set(struct pokemon *p, int state)
{
    p->states = p->states | state;
}

void pkmn_state_unset(struct pokemon *p, int state)
{
    p->states = p->states & ~state;
}

int main(void)
{
    struct pokemon pika;

    pkmn_init(&pika, "greg");
    pkmn_state_set(&pika, STATE_BURN);
    pkmn_state_set(&pika, STATE_PARA);
    pkmn_state_set(&pika, STATE_SLEEP);
    puts("SXPFB (state initials or x for poison)");
    printf("%05b\n", pika.states);
    pkmn_state_unset(&pika, STATE_SLEEP);
    printf("%05b\n", pika.states);
}

Théorie : mode d’un fichier

Lorsque vous faites un ls -l vous pouvez apercevoir une suite de lettres qui ressemble à ceci : -rw-r--r--.

Les lettres affichées dépendent du mode du fichier. Le mode d’un fichier encore plusieurs informations :

• les droits en lecture, écriture, exécution pour le propriétaire du fichier ;
• les droits en lecture, écriture, exécution pour le groupe propriétaire du fichier ;
• les droits en lecture, écriture, exécution pour toutes les autres personnes ;
• le type du fichier ; et
• d’autres informations qui ne nous intéressent pas pour le moment (le sticky/set-group-id/set-user-id).

Toutes ces informations sont encodées sur un seul int et on peut y accéder en le découpant bit à bit. Cet int on peut l’obtenir ainsi :

#include <sys/stat.h>
#include <stdio.h>

int main(void)
{
    struct stat stat_data;

    stat("fichier.txt", &stat_data);
    printf("%b\n", stat_data.st_mode);
    printf("%o\n", stat_data.st_mode);
}

Exemple d’exécution :

$ ./a.out
1000000110100100
100644
$ ls -l fichier.txt
.rw-r--r-- 0 eriizu 2024-02-08 09:33 hello

On remarque une correlation entre le nombre en binaire et la chaîne que nous donne ls, mettons les côte à côte pour comparer :

1000000 110100100
        rw-r--r--

On y voit quels bits doivent être a un pour que r, w ou x s’affichent. En d’autre terme, on voit quels bits contrôlent si le propriétaire du fichier, le groupe ou les autres ont le droit de lire, écrire ou exécuter ce fichier.

Exercice : puis-je ? pouvons-nous ? peuvent-ils ?

Fichiers à rendre : perm.c, perm.h Fonctions autorisées : stat, write

Écrivez un programme qui prend en argument :

• le nom d’un fichier ;
• “user”, “group” ou “other” ;
• “execute”, “write” ou “read”.

Votre programme doit afficher sur la sortie standard “yes” ou “no” en fonction de si l’utilisateur propriétaire, le groupe ou les autres peuvent lire, écrire ou exécuter le fichier dont le nom est passé en premier argument.

Exercice : chaîne mode de fichier

Fichiers à rendre : mode_str.c, mode_str.h Fonctions autorisées : stat, malloc, free, write

Écrivez un programme qui prend en argument :

• le nom d’un fichier

Votre programme doit afficher la chaîne rwx comme le fait ls pour le fichier passé en argument (sans le premier point ou premier tiret).

Exemple :

$ ls -l hello.txt
-rw-r--r-- 1 eriizu wheel 0  8 févr. 09:33 hello
$ ./a.out hello.txt
rw-r--r--