Architecture des systèmes informatiques
Le binaire : données numériques et textuelles
Le binaire
Tout décrire avec 2 symboles différents : 0 et 1
Ce choix est corrélé avec la physique :
I Un transistor est en mode passant ou bloquant.
I On voit du courant dans une piste ou pas.
I Un condensateur est chargé ou déchargé.
I Le pixel(0,0) du fax est imprimé en noir ou pas.
I Un interrupteur est fermé ou ouvert
L’ordinateur pourrait être analogique ou quantique, l’histoire et la
technique ont poussé l’informatique vers la stratégie du numérique
et du binaire (philosophie de tout encoder avec des nombres).
Le binaire
I Dans un ordinateur, toute information est codée en binaire
avec des bits.
I Un bit peut prendre que deux valeurs possibles 0 ou 1.
I Nos mémoires (vive et morte) sont des énormes vecteurs de
bits.
I Tout cela est abstrait et n’aura que le sens que l’on veut bien y
donner.
I Un octet, composé de 8 bits, est l’atome de nos ordinateurs
d’aujourd’hui.
I Un octet n’a pas de sens intrinsèque, il a le sens que
l’utilisateur ou le programme veut bien lui donner :
I (Aucun sens) : 01100001
I (casté en int) : le chiffre 97 (ici en base 10)
I (casté en char) : ‘a’, la première lettre de l’alphabet latin
I (canal rouge d’un pixel) : 97/255 légèrement rouge
I ...
Le binaire
Pourquoi faire un tel choix vers les chiffres pour tout encoder ?
I L’apparition du transistor et les outils électroniques.
I La connaissance et la maîtrise des chiffres.
I L’algorithmique existante (plusieurs millénaires de
connaissances).
I Un dégradé de couleurs peut devenir une suite d’entiers
croissante.
I Une superposition d’images noir et blanc devient un calcul de
max pixel par pixel.
Nos ordinateurs basés sur les transistors, manipulant des données
binaires, ont encore de beaux jours devant eux. Les ordinateurs
quantiques ne sont pas près. . .
Un long chemin d’interprétation
Comment sont utilisées les informations binaires quand :
I On navigue sur internet ?
I On compile un programme C ?
I On fait un triple frag sur Counter Strike ?
Ça dépasse nos capacités d’appréhension aujourd’hui. . . Toutefois,
même les programmes les plus complexes, comme les jeux 3D temps
réel, restent des assemblages de briques de base (moteurs physiques,
rendus graphiques, son numérique, acquisition et événements) dont
on peut comprendre les traitements binaires.
Les nombres positifs
L’interprétation la plus simple. . .
La suite de bits est vue comme un chiffre en base deux.
01100001
0 ∗ 128 + 1 ∗ 64 + 1 ∗ 32 + 0 ∗ 16 + 0 ∗ 8 + 0 ∗ 4 + 0 ∗ 2 + 1 ∗ 1
64 + 32 + 1
97
Les nombres positifs
Compter en base 2 n’est pas vraiment naturel, les nombres arabes et
la base 10 sont aujourd’hui nos standards pour manipuler les
chiffres. . .
Ça reste possible :
0, 1, 10, 11, 100, 101, 110, 111, 1000, 1001, 1010, 1011, 1100,
1101, 1110, 1111, 10000
132 ↔ 10000100
Les nombres positifs en C
En C, les nombres positifs classiques sont décrits par les types
suivants :
unsigned char : nombre positif sur 1 octet (0 ↔ 255)
unsigned short : nombre positif sur 2 octets (0 ↔ 65535)
unsigned int : nombre positif sur 4 octets (0 ↔ 4294967295)
unsigned long int : nombre positif sur 8 octets
(0 ↔ 18446744073709551615)
En Python, c’est différent. . .
nborie@bayer$ python3
Python 3.6.7 (default, Oct 22 2018, 11:32:17)
[GCC 8.2.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> 2**1000
1071508607186267320948425049060001810561404811705533607443750388 \
3703510511249361224931983788156958581275946729175531468251871452 \
8569231404359845775746985748039345677748242309854210746050623711 \
4187795418215304647498358194126739876755916554394607706291457119 \
6477686542167660429831652624386837205668069376
I En Python, la taille des entiers n’est pas bornée (realloc
intempestif ???). C’est très pratique. . .
I L’arithmétique des entiers C va globalement 20 fois plus vite
que l’arithmétique des entiers Python.
I Le monde idéal n’existe pas. Toute stratégie contient des
concessions. . .
Les nombres négatifs
C’est moins drôle et moins naturel. . . On utilise une transformation
appelée le complément à deux.
Pour représenter un négatif :
I On prend son analogue positif (sans le signe moins).
I On prend l’écriture du nombre positif en binaire.
I On inverse les bits (0 ↔ 1), appelé complément à un.
I On rajoute 1.
Ainsi, on a fait un complément à un auquel on a ajouté un, ceci
donne le complément à deux.
Les nombres négatifs
Exemple : −73
−73 → 73 → 64 + 8 + 1 → 0100 1001 → 1011 0110 → 1011 0111
1011 0111 → 128 + 32 + 16 + 4 + 2 + 1 → 183.
int main(int argc, char* argv[]){
char c = -73;
unsigned char uc = c;
printf("c : %d\n", c);
printf("uc : %u\n", uc);
return 0;
}
nborie@bayer$ gcc -o test -Wall -ansi c_a_deux.c
nborie@bayer$ ./test
c : -73
uc : 183
Les nombres négatifs
Mais où est-on allé chercher un truc aussi tordu ?
I Utilisation des mêmes circuits logiques que ceux des positifs.
I L’algorithme de l’addition (addition bit à bit et propagation des
retenues) fonctionne pour le complément à deux mais pas pour
la stratégie bit de signe.
I Il ne se passe rien au niveau du binaire. . . L’ordinateur ne sait
pas s’il stocke des positifs ou des négatifs, ce sont les
traitements et programmes qui décident (gain énorme
d’efficacité).
I Transformations uniquement appliquées à l’affichage :
I printf(“%d”, data); affiche la donnée binaire comme un nombre
en base 10 avec complément à deux si le bit de poids fort est
activé
I printf(“%u”, data); affiche la donnée binaire comme un nombre
positif en base 10
I printf(“%c”, data); affiche le caractère associé à la donnée
binaire en suivant la bijection donnée par le code ASCII.
Et en Python ?
En C et en Unix, on veut des performances. On veut utiliser 100%
de la puissance de calcul et ne pas perdre de temps avec des
simplications qui pourraient ralentir la machine.
En Python, on veut manipuler les objets très simplement. On n’est
moins préoccupé par les performances, on veut écrire les choses
rapidement et de manière concise.
nborie@bayer:~$ python3
Python 3.6.7 (default, Oct 22 2018, 11:32:17)
[GCC 8.2.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> c = 73
>>> type(c)
<class 'int'>
>>> c = 'I'
>>> type(c)
<class 'str'>
Et en Python ?
Python décompose de la même manière en base 2 pour sûr ! Python
utilise lui aussi la table ASCII. Par contre, on ne voit pas apparaître
de complément à deux (il peut y en avoir quand même. . . ).
>>> c = 73
>>> bin(c)
'0b1001001'
>>> c = 'I'
>>> bin(c)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: 'str' object cannot be interpreted as an integer
>>> ord(c)
73
>>> bin(ord(c))
'0b1001001'
>>> c = -73
>>> bin(c)
'-0b1001001'
Conversion de bases
Base 10 vers une base b :
POUR ALLER DE LA BASE 10 VERS UNE BASE b, IL FAUT
DIVISER SUCCESSIVEMENT PAR b ET LIRE LES
RÉSULTATS À L’ENVERS.
Bonne année, joyeuses Pâques, le cours est fini ! C’est la seule
chose à retenir mais vraiment à retenir !
Exemple : 3412 en base 7
3412 = 487 * 7 + 3
487 = 69 * 7 + 4
69 = 9 * 7 + 6
9=1*7+2
3412 en base 10 vaut 12643 en base 7.
Conversion de bases
De toute base b vers la base 10 :
ON FAIT COMME SI LE NOMBRE ÉTAIT UN POLYNÔME
EN X ET ON ÉVALUE EN X = b.
Encore une fois, une seule recette à retenir. . .
Exemple : 12634 de la base 7 vers la base 10
P(X ) = 1 ∗ X 4 + 2 ∗ X 3 + 6 ∗ X 2 + 4 ∗ X + 3
P(7) = 1 ∗ 74 + 2 ∗ 73 + 6 ∗ 72 + 4 ∗ 7 + 3
P(7) = 2401 + 2 ∗ 343 + 6 ∗ 49 + 4 ∗ 7 + 3
P(7) = 2401 + 686 + 294 + 28 + 3
P(7) = 3412
12634 en base 7 vaut 3412 en base 10.
Un coup en binaire
Décomposition de 345 en binaire :
345 = 172 * 2 + 1
172 = 86 * 2 + 0
86 = 43 * 2 + 0
43= 21 * 2 + 1
21 = 10 * 2 + 1
10 = 5 * 2 + 0
5=2*2+1
2=1*2+0
345 en base 10 vaut 101011001 en base 2
P(X ) = 1∗X 8 +0∗X 7 +1∗X 6 +0∗X 5 +1∗X 4 +1∗X 3 +0∗X 2 +0∗X +1
P(X ) = X 8 + X 6 + X 4 + X 3 + 1
P(2) = 28 + 26 + 24 + 23 + 1
P(2) = 256 + 64 + 16 + 8 + 1
P(2) = 345
101011001 en base 2 s’écrit 345 en base 10
Conversions simplifiées
Dans certains cas, les conversions de base peuvent se simplifier. En
fait, cela arrive précisément lorsque l’on convertit entre deux bases
b1 et b2 puissance l’une de l’autre.
binaire : 2
octal : 8 = 23
hexadécimal : 16 = 24
Typiquement, pour aller du binaire à l’hexadécimal, il faut grouper
les bits par 4. Pour aller de l’octal au binaire, chaque symbole de
l’octal doit être remplacé par une séquence de 3 bits.
Les puissances de deux sont les plus célèbres mais ces conventions
simplifiées existent par exemple entre la base 3 et 27
(car 33 = 27).
Conversion simplifiée binaire hexadécimale
0 0000 8 1000
1 0001 9 1001
2 0010 A 1010
3 0011 B 1011
4 0100 C 1100
5 0101 D 1101
6 0110 E 1110
7 0111 F 1111
Flux binaire :
1010100100010110101011010101010011101010100010100101
1010|1001|0001|0110|1010|1101|0101|0100|1110|1010|1000|1010|0101
Flux hexadécimal correspondant:
A916AD54EA8A5
Le côté compact de l’hexadécimal le rend pratique pour les données
binaires, couleurs, adresses mémoires, etc. . .
Les nombres flottants
Les nombres flottant sont des représentations binaires de certains
nombres réels.
Structuration binaire des flottants doubles :
signe exp mantisse
x yyyyyyyyyyy zzzzzzzzzzzz....z
1 bit 11 bits 52 bits
±1 0 - 2047 2**52 valeurs
I signe : plus ou moins un
I exp - 1023 : L’exposant est recentré pour varier de -1023 à
1024
I mantisse : Log10 (253 ) = 15.954... (15 ou 16 chiffres
significatifs en base 10)
I flottant final : (−1)signe ∗ mantisse ∗ 10exp−1023
Les caractères ASCII
Les caractères n’existent pas. . . Du moins en binaire.
Encore une fois, il s’agit de normes définissant des bijections entre
un jeu de symboles (lettres, chiffres, ponctuations, . . . ) et des
séquences binaires.
La plus célèbre : Le jeu ASCII
30 40 50 60 70 80 90 100 110 120
0 ( 2 < F P Z d n x
1 ) 3 = G Q [ e o y
2 * 4 > H R \ f p z
3 ! + 5 ? I S ] g p {
4 " , 6 @ J T ˆ h r |
5 # - 7 A K U _ i s }
6 $ . 8 B L V ‘ j t ∼
7 % / 9 C M W a k u SUP
8 & 0 : D N X b l v
9 ’ 1 ; E O Y c m w
Les caractères ASCII
C’est une bijection d’une série d’actions et symboles vers des
séquences binaires de 1 octet aujourd’hui.
I 0 - 30 : action pour les vieilles imprimantes à aiguilles ou à roue
I 33 - 126 : caractères imprimables
I 128 - 255 : on sort d’ASCII
I Si on est juste, on ne doit pas dire ‘a’ est en bijection avec 97.
I On devrait dire : le code ASCII fait correspondre la séquence
0110 0001 avec la première lettre de l’alphabet latin en
minuscule : ‘a’.
Les caractères ASCII
int main(int argc, char* argv[]){
char c = 97; /* gcc décompose en binaire ce 97 sur 1 octect */
printf("%d\n", c); /* %d fabrique un nombre en base 10 */
printf("%o\n", c); /* %o fabrique un nombre en octal */
printf("%x\n", c); /* %x fabrique un nombre en hexadécimal */
printf("%c\n", c); /* %c va chercher la correspondance dans ASCII */
return 0;
}
nborie@bayer$ gcc -o test char_bin.c -Wall -ansi
nborie@bayer$ ./test
97
141
61
a
Du début à la fin du programme, la variable automatique c
contenait la donnée binaire 0110 0001. Ce sont les printf qui ont
forcé les différentes interprétations et affichages.
Les caractères ASCII
I Pour des raisons de commodité avec les entrées/sorties, on a
appris la base 10 et l’alphabet latin à nos ordinateurs.
I En interne, ces derniers ne voient que le binaire.
I En entrées et sorties des broches de votre CPU, l’information
reste binaire.
I Les primitives processeurs sont décrites par des mots binaires.
I Les fonctionnalités des jeux d’instructions sont indexées par des
mots binaires.
I Les fabriquants fournissent aussi les programmes permettant de
générer du code binaire exécutable par la machine à partir d’un
code relativement human-readable.
I Compilateur NASM : code bas niveau en ASCII –> données
binaires exécutables par un CPU x86
ASCII en Python
En python, la sémantique est toujours plus forte. La philosophie de
Python est de fournir des objets et fonctionnalités de haut niveau.
On ne voit pas souvent les données binaires sous-jacentes en Python
(mais elles sont là, pour sûr). Aussi les bijections sont explicitement
implémentées et certaines sont des built-in.
I ord : bijection caractères 7−→ entiers
I chr : bijection entiers 7−→ caractères
I bin : entiers 7−→ chaîne de caractères décrivant du binaire
I int(_, 2) : chaîne de caractères décrivant du binaire 7−→ entiers
Dans tous les cas, ici, on ne voit pas le vrai binaire décrivant les
objets (Python est permissif mais types primitifs sont sécurisés).
ASCII en Python
nborie@bayer:~$ python3
Python 3.6.7 (default, Oct 22 2018, 11:32:17)
[GCC 8.2.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> ord('a')
97
>>> [chr(97), chr(98), chr(99)]
['a', 'b', 'c']
>>> import random
>>> z = [Link](1, 127)
>>> z, chr(z), z == ord(chr(z))
(29, '\x1d', True)
>>> z = [Link](1, 127)
>>> z, chr(z), z == ord(chr(z))
(68, 'D', True)
>>> bin(625136)
'0b10011000100111110000'
>>> int('0b10011000100111110000', 2)
625136
ASCII en Python
Python3 supporte l’UTF-8 de base. . . Quelle violence! La bijection
entre jeux de caractères et certains entiers est en fait beaucoup plus
large que l’ASCII.
>>> [ord('ç'), ord('é'), ord('ß')]
[231, 233, 223]
>>> [chr(231), chr(233), chr(223)]
['ç', 'é', 'ß']
>>> [ord('n, '), ord('œ')]
[326, 339]
>>> [chr(326), chr(339)]
['n, ', 'œ']
Retour sur le système
I Informatique = information + automatique
I Si l’information est une succession de bits, on pourrait presque
résumer l’informatique à programmer des traitements
automatiques sur des suites de bits.
I C’est réducteur mais terriblement vrai. . .
I Une grande partie des commandes shell et systèmes basiques
consiste en de la manipulation basique de chaîne d’octets.
I grep, cat, cut, sed, tee, less, more, diff, awk, echo, expr, head,
tail, join, sort, uniq, tr, wc, nl, strings
I Ces commandes sont les primitives de nos éditeurs. . .
I Les premiers compilateurs (ceux d’aujourd’hui optimisent au
delà de l’humain. . . ) ne faisaient que des remplacements de
chaînes.
Fonctionnalités textuelles primordiales
I Statistique et comptage (wc)
I Découpage et extraction (cut)
I Recherche dans une chaîne (grep)
I Substitution de motifs (sed -e “s/X/Y/g”)
I Tri lexico-ascii (sort)
I Suppression des doublons consécutifs (uniq)
I Sauvegarder un log dans un fichier (tee)
I Multi-fonctions (sed et awk)
Les deux derniers proposent d’innombrables possibilités. . . Les
maîtriser totalement et retenir toutes leurs fonctionnalités n’est pas
raisonnable, on se servira des plus fondamentales.