Leçon 4

Hexadecimal

  • Durant la semaine 0, nous avons appris le système binaire, un système de comptage avec des 0 et des 1.
  • Durant la semaine 2, nous avons parlé de la mémoire et de la façon dont chaque octet possède une adresse, ou identifiant, pour que nous puissions référencer l’endroit où nos variables sont réellement stockées.
  • Il s’avère que, par convention, les adresses pour la mémoire utilisent le système de comptage hexadécimal, dans lequel il y a 16 chiffres : 0-9 et A-F.

  • Rappelons que, en binaire, chaque chiffre correspondait à une puissance de 2 :

      128 64 32 16  8  4  2  1
    1  1  1  1  1  1  1  1
    • Avec 8 bits, nous pouvons compter jusqu’à 255.

  • Il s’avère qu’en hexadécimal, nous pouvons parfaitement compter jusqu’à 8 bits binaires avec seulement 2 chiffres :

      16^1 16^0
     F    F
    • Ici, « F » est une valeur de 15 en décimal, et chaque place est une puissance de 16. Donc le premier « F » est 16^1 _ 15 = 240, plus le deuxième « F » avec une valeur de 16^0 _ 15 = 15, pour un total de 255.

  • Et « 0A » est la même chose que 10 en décimal, et « 0F » la même chose que 15. « 10 » en hexadécimal serait 16, et nous le prononcerions « un zéro en hexadécimal » plutôt que « dix », pour éviter toute confusion.

  • Le système de couleurs RVB utilise également traditionnellement l’hexadécimal pour décrire la quantité de chaque couleur. Par exemple, « 000000 » en hexadécimal signifie 0 pour chaque couleur rouge, verte et bleue, pour une couleur noire. Et « FF0000 » serait 255, ou la quantité la plus élevée possible, de rouge. Avec des valeurs différentes pour chaque couleur, nous pouvons représenter des millions de couleurs différentes.
  • À l’écrit, nous pouvons aussi indiquer qu’une valeur est en hexadécimal en la faisant précéder de « 0x », comme dans « 0x10 », où la valeur est égale à 16 en décimal, par opposition à 10.

Pointeurs

  • Nous pouvons créer une valeur n et l'imprimer :

      #include <stdio.h>

  int main(void)
  {
      int n = 50;
      printf("%i\n", n);
  }

  • Dans la mémoire de notre ordinateur, il y a maintenant 4 octets quelque part qui ont la valeur binaire 50, étiquetés n : grille représentant des octets, avec quatre boîtes ensemble contenant 50 avec un petit n en dessous

  • Il s'avère qu'avec les milliards d'octets en mémoire, ces octets pour la variable n commencent à une adresse unique qui pourrait ressembler à 0x12345678.

  • En C, nous pouvons réellement voir l'adresse avec l'opérateur &, qui signifie « obtenir l'adresse de cette variable » :

      #include <stdio.h>

  int main(void)
  {
      int n = 50;
      printf("%p\n", &n);
  }
    • Et dans l'IDE CS50, nous pourrions voir une adresse comme 0x7ffe00b3adbc, où il s'agit d'un emplacement spécifique dans la mémoire du serveur.

  • L'adresse d'une variable est appelée un pointeur, que nous pouvons considérer comme une valeur qui « pointe » vers un emplacement en mémoire. L'opérateur * nous permet « d'aller » à l'emplacement vers lequel pointe un pointeur.

  • Par exemple, nous pouvons imprimer *&n, où nous « allons » à l'adresse de n, et cela imprimera la valeur de n, 50, puisque c'est la valeur à l'adresse de n :

      #include <stdio.h>

  int main(void)
  {
      int n = 50;
      printf("%i\n", *&n);
  }

  • Nous devons également utiliser l'opérateur * (d'une manière malheureusement déroutante) pour déclarer une variable que nous voulons être un pointeur :

      #include <stdio.h>

  int main(void)
  {
     int n = 50;
     int *p = &n;
     printf("%p\n", p);
  }
    • Ici, nous utilisons int *p pour déclarer une variable, p, qui a le type de *, un pointeur, vers une valeur de type int, un entier. Ensuite, nous pouvons imprimer sa valeur (quelque chose comme 0x12345678), ou imprimer la valeur à son emplacement avec printf("%i\n", *p);.

  • Dans la mémoire de notre ordinateur, les variables pourraient ressembler à ceci : grille représentant des octets, avec quatre boîtes ensemble contenant 50 avec un petit 0x12345678 en dessous, et huit boîtes ensemble contenant 0x12345678 avec un petit p en dessous

    • Nous avons un pointeur, p, avec l'adresse d'une variable.
  • Nous pouvons maintenant faire abstraction de la valeur réelle des adresses, car elles seront différentes lorsque nous déclarerons des variables dans nos programmes, et simplement penser à p comme « pointant vers » une valeur : une boîte contenant p pointant vers une boîte plus petite contenant 50
  • Supposons que nous ayons une boîte aux lettres étiquetée « 123 », avec le numéro « 50 » à l'intérieur. La boîte aux lettres serait int n, car elle stocke un entier. Nous pourrions avoir une autre boîte aux lettres avec l'adresse « 456 », à l'intérieur de laquelle se trouve la valeur « 123 », qui est l'adresse de notre autre boîte aux lettres. Ce serait int *p, puisqu'il s'agit d'un pointeur vers un entier.
  • Grâce à la possibilité d'utiliser des pointeurs, nous pouvons créer différentes structures de données, ou différentes manières d'organiser les données en mémoire que nous verrons la semaine prochaine.
  • De nombreux systèmes informatiques modernes sont « 64 bits », ce qui signifie qu'ils utilisent 64 bits pour adresser la mémoire. Un pointeur fera donc 8 octets, soit deux fois plus qu'un entier de 4 octets.

string

  • On pourrait avoir une variable string s pour un nom tel que EMMA et pouvoir accéder à chaque caractère avec s[0] et ainsi de suite :
    cases côte à côte, contenant : E étiqueté s[0], M étiqueté s[1], M étiqueté s[2], A étiqueté s[3], \0 étiqueté s[4]
  • Mais il s’avère que chaque caractère est stocké en mémoire dans un octet avec une adresse donnée, et s est en fait juste un pointeur avec l’adresse du premier caractère :
    case contenant 0x123 étiqueté s, cases côte à côte contenant E étiqueté 0x123, M étiqueté 0x124, M étiqueté 0x125, A étiqueté 0x126, \0 étiqueté 0x127
  • Et puisque s est juste un pointeur vers le début, seul le \0 indique la fin de la chaîne.
  • En fait, la CS50 Library définit une string avec typedef char *string, qui dit juste que nous voulons nommer un nouveau type, string, comme un char *, ou un pointeur vers un caractère.

  • Imprimons une chaîne :

      #include <cs50.h>
  #include <stdio.h>

  int main(void)
  {
      string s = "EMMA";
      printf("%s\n", s);
  }

  • C’est familier, mais nous pouvons simplement dire :

      #include <stdio.h>

  int main(void)
  {
      char *s = "EMMA";
      printf("%s\n", s);
  }
    • Cela imprimera également EMMA.

  • Avec printf("%p\n", s);, nous pouvons imprimer s comme sa valeur en tant que pointeur, comme 0x42ab52. (printf sait aller à l’adresse et imprimer la chaîne entière lorsque nous utilisons %s et transmettons s, même si s pointe uniquement vers le premier caractère.)

  • Nous pouvons également essayer printf("%p\n", &s[0]);, qui est l’adresse du premier caractère de s, et c’est exactement la même chose que d’imprimer s. Et l'impression de &s[1], &s[2] et &s[3] nous donne les adresses qui sont les caractères suivants en mémoire après &s[0], comme 0x42ab53, 0x42ab54 et 0x42ab55, exactement un octet après l'autre.
  • Et enfin, si on essaie de printf("%c\n", *s);, on obtient un seul caractère E, puisqu'on va à l'adresse contenue dans s, qui contient le premier caractère de la chaîne.
  • En fait, s[0], s[1] et s[2] sont réellement mappés directement sur *s, *(s+1) et *(s+2), puisque chacun des caractères suivants se trouve juste à l'adresse de l'octet suivant.

Comparer et copier

  • Examinons compare0 :

      #include <cs50.h>
  #include <stdio.h>

  int main(void)
  {
      // Obtenir deux entiers
      int i = get_int("i : ");
      int j = get_int("j : ");

      // Comparer les entiers
      if (i == j)
      {
          printf("Identique\n");
      }
      else
      {
          printf("Différent\n");
      }
  }
    • Nous pouvons compiler et exécuter ce code, et notre programme fonctionne comme prévu : si les deux entiers sont identiques, le résultat est « Identique », et s'ils sont différents, le résultat est « Différent ».

  • Dans compare1, nous constatons que des valeurs de chaîne identiques font que notre programme affiche « Différent » :

      #include <cs50.h>
  #include <stdio.h>

  int main(void)
  {
      // Obtenir deux chaînes
      string s = get_string("s : ");
      string t = get_string("t : ");

      // Comparer les adresses des chaînes
      if (s == t)
      {
          printf("Identique\n");
      }
      else
      {
          printf("Différent\n");
      }
  }
    • Compte tenu de ce que nous savons à présent sur les chaînes, cela est logique parce que chaque variable de « chaîne » pointe vers un emplacement différent en mémoire, où est stocké le premier caractère de chaque chaîne. Ainsi, même si les valeurs des chaînes sont identiques, l'affichage sera toujours « Différent ».
    • Par exemple, notre première chaîne peut être à l'adresse 0x123, notre seconde à l'adresse 0x456, et s sera 0x123 et t sera 0x456, donc ces valeurs seront différentes.
    • Et get_string, pendant tout ce temps, n'a renvoyé qu'un char *, ou un pointeur vers le premier caractère d'une chaîne provenant de l'utilisateur.

  • Essayons à présent de copier une chaîne :

      #include <cs50.h>
  #include <ctype.h>
  #include <stdio.h>

  int main(void)
  {
      string s = get_string("s : ");

      string t = s;

      t[0] = toupper(t[0]);

      // Afficher la chaîne deux fois
      printf("s : %s\n", s);
      printf("t : %s\n", t);
  }
    • Nous obtenons une chaîne s, et copions la valeur de s dans t. Ensuite, nous mettons en majuscule la première lettre dans t.
    • Mais lorsque nous exécutons notre programme, nous constatons que s et t sont à présent tous les deux en majuscules.
    • Dans la mesure où nous définissons s et t avec les mêmes valeurs, ils sont en réalité des pointeurs vers le même caractère, et nous venons donc de mettre en majuscule le même caractère !

  • Pour effectuer une véritable copie d'une chaîne, nous devons fournir un effort un peu plus important :

      #include <cs50.h>
  #include <ctype.h>
  #include <stdio.h>
  #include <string.h>

  int main(void)
  {
      char *s = get_string("s : ");

      char *t = malloc(strlen(s) + 1);

      for (int i = 0, n = strlen(s); i < n + 1; i++)
      {
          t[i] = s[i];
      }

      t[0] = toupper(t[0]);

      printf("s : %s\n", s);
      printf("t : %s\n", t);
  }
    • Nous créons une nouvelle variable, t, de type char *, avec char *t. À présent, nous souhaitons la faire pointer vers un nouveau bloc de mémoire suffisamment volumineux pour stocker la copie de la chaîne. Avec malloc, nous pouvons allouer un certain nombre d'octets en mémoire (qui ne sont pas déjà utilisés pour stocker d'autres valeurs), et nous faisons passer le nombre d'octets que nous souhaiterions. Nous connaissons déjà la longueur de s, nous ajoutons donc 1 pour le caractère null de terminaison. Ainsi, notre dernière ligne de code est char *t = malloc(strlen(s) + 1);.
    • Ensuite, nous copions chaque caractère, un à la fois, et à présent, nous pouvons mettre en majuscule uniquement la première lettre de t. Et nous utilisons i < n + 1, car nous souhaitons en réalité atteindre n, afin de garantir de copier le caractère de terminaison dans la chaîne.
    • Nous pouvons également utiliser la fonction de bibliothèque strcpy avec strcpy(t, s) à la place de notre boucle pour copier la chaîne s dans t. Pour être clair, le concept d'une « chaîne » vient du langage C et est bien pris en charge ; les seules roulettes d'entraînement de CS50 sont le type string à la place de char * et la fonction get_string.

  • Si nous ne copions pas le caractère null de terminaison, \0, et essayons d'imprimer notre chaîne t, printf continuera et imprimera les valeurs inconnues, ou indésirables, que nous avons en mémoire, jusqu'à atteindre un \0, ou s'arrêtera complètement, dans la mesure où notre programme pourrait se mettre à essayer de lire de la mémoire qui ne lui appartient pas !

valgrind

  • Il s'avère qu'après avoir terminé avec la mémoire que nous avons allouée avec malloc, nous devrions appeler free (comme dans free(t)), ce qui indique à notre ordinateur que ces octets ne sont plus utiles à notre programme, permettant ainsi à ces octets en mémoire d'être réutilisés.
  • Si nous continuions à exécuter notre programme et à allouer de la mémoire avec malloc, mais que nous ne libérions jamais la mémoire après l'avoir utilisée, nous aurions une fuite de mémoire, ce qui ralentirait notre ordinateur et utiliserait de plus en plus de mémoire jusqu'à ce que notre ordinateur manque de mémoire.
  • valgrind est un outil en ligne de commande que nous pouvons utiliser pour exécuter notre programme et vérifier s'il présente des fuites de mémoire. Nous pouvons exécuter valgrind sur notre programme ci-dessus avec help50 valgrind ./copy et constater, à partir du message d'erreur, que la ligne 10 montre que nous avons alloué de la mémoire que nous n'avons jamais libérée (ou "perdue").
  • Ainsi, à la fin, nous pouvons ajouter une ligne free(t), ce qui ne changera pas le fonctionnement de notre programme, mais ne générera plus d'erreurs avec valgrind.

  • Regardons le fichier memory.c :

      // http://valgrind.org/docs/manual/quick-start.html#quick-start.prepare

  #include <stdlib.h>

  void f(void)
  {
      int *x = malloc(10 * sizeof(int));
      x[10] = 0;
  }

  int main(void)
  {
      f();
      return 0;
  }
    • Il s'agit d'un exemple provenant de la documentation de valgrind (valgrind est un véritable outil, tandis que help50 a été spécialement écrit pour nous aider dans ce cours).
    • La fonction f alloue suffisamment de mémoire pour 10 entiers et stocke l'adresse dans un pointeur appelé x. Ensuite, nous essayons de définir la 11ème valeur de x avec x[10] à 0, ce qui dépasse le tableau de mémoire que nous avons alloué pour notre programme. Cela s'appelle un dépassement de tampon, où nous dépassons les limites de notre tampon, ou tableau, et accédons à une mémoire inconnue.

  • valgrind nous indiquera également qu'il y a une "Écriture invalide de taille 4" pour la ligne 8, où nous essayons en effet de modifier la valeur d'un entier (de taille 4 octets).

  • Et pendant tout ce temps, la bibliothèque CS50 a libéré la mémoire qu'elle a allouée dans get_string, lorsque notre programme se termine !

Inversion

  • Nous avons deux boissons colorées, violette et verte, chacune dans une tasse. Nous voulons intervertir les boissons entre les deux tasses, mais nous ne pouvons pas le faire sans une troisième tasse dans laquelle verser d'abord une des boissons.

  • Maintenant, disons que nous voulons intervertir les valeurs de deux entiers.

      void swap(int a, int b)
  {
      int tmp = a;
      a = b;
      b = tmp;
  }

  • Avec une troisième variable à utiliser comme espace de stockage temporaire, nous pouvons le faire assez facilement, en mettant a dans tmp, puis b dans a, et enfin la valeur d'origine de a, maintenant dans tmp, dans b.

  • Mais, si nous essayions d'utiliser cette fonction dans un programme, nous ne verrions aucun changement :

      #include <stdio.h>

  void swap(int a, int b);

  int main(void)
  {
      int x = 1;
      int y = 2;

      printf("x est %i, y est %i\n", x, y);
      swap(x, y);
      printf("x est %i, y est %i\n", x, y);
  }

  void swap(int a, int b)
  {
      int tmp = a;
      a = b;
      b = tmp;
  }

  • Il s'avère que la fonction swap obtient ses propres variables, a et b lorsqu'elles sont passées, qui sont des copies de x et y, et donc changer ces valeurs ne change pas x et y dans la fonction main.

Disposition en mémoire

  • Dans la mémoire de notre ordinateur, les différents types de données qui doivent être stockés pour notre programme sont organisés dans différentes sections : Grille avec sections, du haut vers le bas : code machine, globales, tas (avec flèche pointant vers le bas), pile (avec flèche pointant vers le haut)
    • La section de code machine est le code binaire de notre programme compilé. Lorsque nous exécutons notre programme, ce code est chargé dans la « partie supérieure » de la mémoire.
    • Les globales sont des variables globales que nous déclarons dans notre programme ou d’autres variables partagées auxquelles tout notre programme peut accéder.
    • La section heap est une zone vide dans laquelle malloc peut obtenir de la mémoire libre, pour que notre programme puisse l’utiliser.
    • La section stack est utilisée par des fonctions de notre programme lorsqu’elles sont appelées. Par exemple, notre fonction main est tout en bas de la pile et possède les variables locales x et y. Lorsque la fonction swap est appelée, elle possède son propre cadre ou tranche de mémoire qui se trouve au-dessus de la mémoire de main, avec les variables locales a, b et tmp : Section de pile avec (a, b, tmp) au-dessus de (x, y)
      • Une fois que la fonction swap renvoie, la mémoire qu’elle utilisait est libérée pour l’appel de fonction suivant, et nous perdons tout ce que nous avons fait, mis à part les valeurs renvoyées, et notre programme revient à la fonction qui a appelé swap.
      • Par conséquent, en transmettant les adresses de x et y de main à swap, nous pouvons réellement modifier les valeurs de x et y : Section de pile avec (a, b, tmp) au-dessus de (x, y), et a pointant vers x et b pointant vers y

  • En transmettant l’adresse de x et de y, notre fonction swap peut réellement fonctionner :

      #include <stdio.h>

  void swap(int *a, int *b) ;

  int main(void)
  {
      int x = 1 ;
      int y = 2 ;

      printf("x est %i, y est %i\n", x, y) ;
      swap(&x, &y) ;
      printf("x est %i, y est %i\n", x, y) ;
  }

  void swap(int *a, int *b)
  {
      int tmp = *a ;
      *a = *b ;
      *b = tmp ;
  }
    • Les adresses de x et de y sont transmises dans main à swap, et nous utilisons la syntaxe int *a pour déclarer que notre fonction swap prend des pointeurs. Nous enregistrons la valeur de x dans tmp en suivant le pointeur a, puis nous prenons la valeur de y en suivant le pointeur b et nous la stockons dans l’emplacement vers lequel a pointe (x). Enfin, nous stockons la valeur de tmp dans l’emplacement pointé par b (y), et nous avons terminé.

  • Si nous appelons malloc trop souvent, nous aurons un dépassement de segment, où nous finissons par dépasser notre segment. Ou bien, si nous avons trop de fonctions appelées, nous aurons un dépassement de pile, où notre pile a également trop de cadres de mémoire allouée. Et ces deux types de dépassement sont généralement appelés dépassements de tampon, après quoi notre programme (ou ordinateur entier) peut planter.

get_int

  • Nous pouvons implémenter get_int nous-mêmes avec une fonction de la bibliothèque C, scanf :

```

include

int main(void) { int x; printf("x : "); scanf("%i", &x); printf("x : %i\n", x); } ```

  • scanf prend un format, %i, donc l'entrée est « scannée » pour ce format, ainsi que l'adresse en mémoire où nous voulons que cette entrée aille. Mais scanf ne vérifie pas beaucoup les erreurs, donc nous n'obtiendrons peut-être pas un entier.

  • Nous pouvons essayer d'obtenir une chaîne de la même manière :

```

include

int main(void) { char *s = NULL; printf("s : "); scanf("%s", s); printf("s : %s\n", s); } ```

  • Mais nous n'avons en fait alloué aucune mémoire pour s (s est NULL, ou ne pointe vers rien), donc nous pourrions vouloir appeler char s[5] pour allouer un tableau de 5 caractères pour notre chaîne. Ensuite, s sera traité comme un pointeur dans scanf et printf.
  • Maintenant, si l'utilisateur tape une chaîne d'une longueur de 4 ou moins, notre programme fonctionnera en toute sécurité. Mais si l'utilisateur tape une chaîne plus longue, scanf pourrait essayer d'écrire au-delà de la fin de notre tableau dans une mémoire inconnue, provoquant la soudaine perte de contrôle de notre programme.

Fichiers

  • Avec la possibilité d'utiliser des pointeurs, nous pouvons également ouvrir des fichiers :

```

include

include

include

int main(void) { // Ouvrir le fichier FILE *file = fopen("phonebook.csv", "a");

  // Obtenir des chaînes de l'utilisateur
  char *name = get_string("Nom : ");
  char *number = get_string("Numéro : ");

  // Imprimer (écrire) des chaînes dans le fichier
  fprintf(file, "%s,%s\n", name, number);

  // Fermer le fichier
  fclose(file);

} ```

  • fopen est une nouvelle fonction que nous pouvons utiliser pour ouvrir un fichier. Elle retournera un pointeur vers un nouveau type, FILE, à partir duquel nous pouvons lire et écrire. Le premier argument est le nom du fichier et le second argument est le mode dans lequel nous souhaitons ouvrir le fichier (r pour lecture, w pour écriture et a pour ajout).
  • Après avoir obtenu des chaînes, nous pouvons utiliser fprintf pour imprimer dans un fichier.

  • Finalement, nous fermons le fichier avec fclose.

  • Nous pouvons désormais créer nos propres fichiers CSV (valeurs séparées par des virgules), comme de mini-tableurs, par programmation.

JPEG

  • Nous pouvons aussi écrire un programme qui ouvre un fichier et qui nous dit si c'est un fichier JPEG (une image) :

      #include <stdio.h>

  int main(int argc, char *argv[])
  {
      // Vérifie l'utilisation
      if (argc != 2)
      {
          return 1;
      }

      // Ouvre le fichier
      FILE *file = fopen(argv[1], "r");
      if (!file)
      {
          return 1;
      }

      // Lit les trois premiers octets
      unsigned char bytes[3];
      fread(bytes, 3, 1, file);

      // Vérifie les trois premiers octets
      if (bytes[0] == 0xff && bytes[1] == 0xd8 && bytes[2] == 0xff)
      {
          printf("Peut-être\n");
      }
      else
      {
          printf("Non\n");
      }

      // Ferme le fichier
      fclose(file);
  }

  • Maintenant, si on exécute ce programme avec ./jpeg brian.jpg, notre programme va essayer d'ouvrir le fichier que nous spécifions (en vérifiant qu'on obtient un fichier non-NULL), et lit les trois premiers octets du fichier avec fread.

  • On peut comparer les trois premiers octets (en hexadécimal) aux trois octets requis pour commencer un fichier JPEG. S'ils sont identiques, alors notre fichier est probablement un fichier JPEG (bien que d'autres types de fichiers peuvent aussi commencer par ces octets). Mais si les octets ne sont pas les mêmes, alors on sait que ce n'est définitivement pas un fichier JPEG.

  • On peut utiliser ces capacités pour lire et écrire des fichiers, en particulier des images, et de les modifier en changeant les octets qu'ils contiennent, dans le problème de cette semaine !