Remplir un fichier binaire de BITS !!!!

**ben13** · 19/12/2004, 12h11

Salut a tous.
Je suis nouveau ici et je nécessite votre aide en C pour un projet d'info (je suis en 2e année de license), je n'ai donc pas trop droit au C++ .....

voila je me suis tordu le cerveau dans tous les sens mais je vois pas comment je peut remplir un fichier binaire avec des bits, sachant que le C ne propose aucun type de moins d'un octet....

Pourquoi des bits et pas des 0 ou des 1 codés sur un octet (en char par ex)? et beh tout simplement parce qu'il s'agit d'un algo de compression texte et que si je fait ca mon fichier compressé sera plus lourd que la source .....

Merci a tous d'avance pour votre aide ...

**Emmanuel Delahaye** · 19/12/2004, 12h33

Envoyé par ben13

voila je me suis tordu le cerveau dans tous les sens mais je vois pas comment je peut remplir un fichier binaire avec des bits, sachant que le C ne propose aucun type de moins d'un octet....

Pourquoi des bits et pas des 0 ou des 1 codés sur un octet (en char par ex)? et beh tout simplement parce qu'il s'agit d'un algo de compression texte et que si je fait ca mon fichier compressé sera plus lourd que la source .....

Soit tu considères que chaque byte prend la valeur 0 ou 1 (mais ce n'est effectivement pas très économe), soit tu considères que chaque byte porte 8 bits. Les bytes (unsigned char) mis bout à bout forment alors une séquence de bits (ou un tableau de bits) facilement adressable moyennant un calcul trivial.

Exemple : je veux mettre la séquence '100110110101011001101' dans un fichier (ou flux) de bytes :

Il suffit de grouper les bits par paquets de 8 en partant de la gauche (MSB en tête)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

ce qui donne

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

9B 56 68

Il faut bien sûr quelque part une info (en tête, selon le principe Longueur, Valeur) qui indique le nombre de bits (ici 21, soit $15)

Par exemple :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
L-  V--------
15 9B 56 68

Si le format supporte des types mixtes, un format TLV est envisageable :
Par exemple :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
00 = Bit
01 = Octet
etc.
 
T-  L-  V--------
00 15 9B 56 68

Si un codage de la longueur sur 1 octet (0-255) ne suffit pas, on peut décider de faire le codage de la longueur sur 2 octets (MSB en tête)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
T-  L----  V--------
00 00 15 9B 56 68

On peut aussi réduire le nombre de bits pour les types (16 types = 4 bits MSB) et utiliser les LSB pour la longueur (000-FFF):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
TL---  V--------
00 15 9B 56 68
 
----[0]---- ----[1]----
7654 3210 7654 3210
Type  Longueur-------
0000  0000 0001 0101
Bit     015

**ben13** · 19/12/2004, 12h59

Merci pour ta reponse.

Il suffit de grouper les bits par paquets de 8 en partant de la gauche (MSB en tête)
Code:

1001 1011
0101 0110
0110 1000

ce qui donne
Code:
9B 56 68

Il faut bien sûr quelque part une info (en tête, selon le principe Longueur, Valeur) qui indique le nombre de bits (ici 21, soit $15)

mais ici comment tu fais pour passer de la sequence de bits au code en hexa .... pke il faudra que je puisse revenir en arriere apres ....

merci

**Emmanuel Delahaye** · 19/12/2004, 13h09

Envoyé par ben13

Il suffit de grouper les bits par paquets de 8 en partant de la gauche (MSB en tête)
Code:

1001 1011
0101 0110
0110 1000

ce qui donne
Code:
9B 56 68

Il faut bien sûr quelque part une info (en tête, selon le principe Longueur, Valeur) qui indique le nombre de bits (ici 21, soit $15)

mais ici comment tu fais pour passer de la sequence de bits au code en hexa .... pke il faudra que je puisse revenir en arriere apres ....

merci

Il n'y a pas de 'code hexa'. La représentation interne est binaire. Il suffit de positionner les bits des bytes avec les opérateurs bits (&, |, << etc.)

Fait ce que tu peux et montre ton code.

**ben13** · 19/12/2004, 13h40

serieux j'ai pas tout compris mais je vais essayer de voir

mon cas est peut etre un tantiné plu simple car mes bits représentent un chemin dans un tas et la hauteur de ce tas est maximum de log2 (256) soit 8.

donc mes mots ne depasseront pas 8 bits

en fait tu me propose de prendre mon mot (qui mesure de 1 a 8 bits), et de mettre dans le fichier la taille de ce mot ( donc 1 a 8 ) puis le mot....

mais la je tourne en rond pke si je mais la taille de ce mot dans le fichier je vais devoir la coder en int (non???) et donc ca me boufe encore 4 octets ou du moins 1 si je la mets en char

dsl si j'ai l'air de rien comprendre mais c'est pas evident pour moi .....

de plus j'ai jamais entendu parler les opérateurs simple pipe ( | ), ou simple &

**Emmanuel Delahaye** · 19/12/2004, 14h30

Envoyé par ben13

mon cas est peut etre un tantiné plu simple car mes bits représentent un chemin dans un tas et la hauteur de ce tas est maximum de log2 (256) soit 8.

donc mes mots ne depasseront pas 8 bits

Donc un byte contenant une valeur de 0 à 255 suffit. Il suffit de mettre dans le byte la valeur voulue (0 à 255) et le tour est joué. Je ne vois pas trop où est le problème... Ensuite, tu mets le byte dans le fichier et c'est tout.

en fait tu me propose de prendre mon mot (qui mesure de 1 a 8 bits), et de mettre dans le fichier la taille de ce mot ( donc 1 a 8 ) puis le mot....

Je ne sais pas si la taille est nécessaire... C'est pour un codage Huffman ?

mais la je tourne en rond pke si je mais la taille de ce mot dans le fichier je vais devoir la coder en int (non???) et donc ca me boufe encore 4 octets ou du moins 1 si je la mets en char

Si la taille ne dépasse pas 1-8, 3 bits suffisent si on code 'taille - 1', soit 0-7. Ca tient dans un char.

dsl si j'ai l'air de rien comprendre mais c'est pas evident pour moi .....

Si tu expliquais exactement ce que tu veux faire, avec un exemple de données à encoder, on y verrais plus clair...

de plus j'ai jamais entendu parler les opérateurs simple pipe ( | ), ou simple &

C'est dans ton livre de C : 'Bitwise operators'

**ben13** · 19/12/2004, 15h00

bon je vais plus detailler alors.

effectivement c'est huffman.

j'ai fait mon tableau de correspondance caractere / code binaire.

maintenant je dois lire mon fichier texte, et pour chaque caractere lui associer son code bianaire, puis ecrire ce code dans un nouveau fichier.

alors j'ai ouvert un fichier en mode binaire, et j'ai mis des 0 et des 1 dedans avec fwrite. quand j'ouvre le fichier (je tourne sous unix), j'ai des <nul> et des <soh> qui correspondent a 0 et 1 je pense.

le prob c'est que si j'ai un fichier qui contient mettons 10 <nul> ou <soh> il fait 10 octets (ce qui est normal puisque dans fwrite j'ai mis 1 en taille et que les tailles sont en octets...), mais moi je voudrais qu'il fasse 10 bits !!!!!!!

voila

**ben13** · 19/12/2004, 15h04

j'ai oublié un truc.

tu m'as dit de prendre mon code 8 bits, de lui associé un entier entre 0 et 255 et ca prendra un octet. je suis d'accord le prob c'est que dans mon cas, le code 00001010 est différent du code 1010 (puisque le code represente un chemin dans le tas) donc je peux pas faire comme ca

**Emmanuel Delahaye** · 19/12/2004, 16h25

Envoyé par ben13

effectivement c'est huffman.

j'ai fait mon tableau de correspondance caractere / code binaire.

maintenant je dois lire mon fichier texte, et pour chaque caractere lui associer son code binaire, puis ecrire ce code dans un nouveau fichier.

alors j'ai ouvert un fichier en mode binaire, et j'ai mis des 0 et des 1 dedans avec fwrite. quand j'ouvre le fichier (je tourne sous unix), j'ai des <nul> et des <soh> qui correspondent a 0 et 1 je pense.

le prob c'est que si j'ai un fichier qui contient mettons 10 <nul> ou <soh> il fait 10 octets (ce qui est normal puisque dans fwrite j'ai mis 1 en taille et que les tailles sont en octets...), mais moi je voudrais qu'il fasse 10 bits !!!!!!!

Impossible. Un fichier fait un nombre entier d'octet. C'est immuable. Pour 10 bits, il faut 2 octets.

Le codage de Huffman est fait pour des transmission 'bit', et non pour des flux d'octet's

Par contre, comme je te l'ai expliqué au début, tu peux mettre la taille (nombre de bits de la bitstring) dans un octet (0-255), et dans les autres, la chaine de bits en commençant par le 1er en [0].7

Chaine de 10 bits :
0110100101

Longueur 10 : 0A
8 premiers bits : 01101001 = 69
2 suivants : 01 + 6 bits de 'padding' à 0 (ou 1, peu importe, disons 0) : 01000000 = 40

La flux de bytes est donc : 0A 69 40

Si la longueur d'un bit stream ne dépasse pas 127 ou 63 etc., on peut peut être gagner quelques bits sur le format de la longueur, et récupérer quelques bits pour les données...

La longueur est codée sur 6 bits (0-63)
Longueur 10 : 0A = 0000 1010, soit 001010xx
Suivent les 2 premiets bits de données : 01
Ce qui fait un premier octet 0010 1001 = 29

Les 8 bits suivants : 1010 0101, soit A5
Pas de padding (octet plein), ce qui donne 29 A5. On a gangné un octet (mais la chaine ne peut pas faire plus de 63 bits, voir 64 si on encode 1-64 en 0-63.)

**ben13** · 19/12/2004, 16h31

ok donc si j'ai bien compris je suis obligé d'utiliser un octet pour coder la longueur de la chaine puis un autre pour coder la chaine (puisque ma chaine fera tjs moins de 8 bits), ce qui m'oblige a utiliser 2 octets par chaine...

mais a ce moment la j'utilise pas la propriété du tas qui permet que aucun des codes soit le prefixe d'un autre ..... je suis sur qu'avec cette propriété ya un moyen de se passer de la longueur de la chaine...

en fait il fodrai que je mette quelque part (temporairement) la chaine totale (de tout le fichier) puis que je la coupe en paquets de 8 bits puis que je foute ces paquets dans le fichier sous forme d'octet...

tu pense que ca peut marcher ca ???

ps : merci encore pour ton aide

**ben13** · 19/12/2004, 16h50

pendant que j'y suis

si jamais je fais ca, j'ai une question purement synthaxique.

pour chacun des caracteres presents dans le texte, j'ai une structure dans laquelle figure un int (taille du code binaire) et un tableau d'int (code binaire de ce caractere composé donc unquement de 0 et de 1)

imaginont que je foute dans un fichier temporaire la suite des codes qui correspont au fichier texte que je veux coder

je vais me retrouver dans mon fichier temporaire avec des 0 et des 1

maintenant je dois les prendres 8 par 8 et en faire un nombre compris entre 0 et 255. jai bien suivi mes cours sur la numération (

) mais je suis obligé de me taper un algo avec les puissances de 2 ???? ya pas une fonction standard qui peut me convertir une suite de huit 0 et 1 en un entier ????????

et pareil dans l'autre sens ?????

merci

**Emmanuel Delahaye** · 19/12/2004, 16h58

Envoyé par ben13

ok donc si j'ai bien compris je suis obligé d'utiliser un octet pour coder la longueur de la chaine puis un autre pour coder la chaine (puisque ma chaine fera tjs moins de 8 bits), ce qui m'oblige a utiliser 2 octets par chaine...

Pas forcément. On peut compresser du moment qu'on attribue une taille fixe à la taille. Disons que 0-7 signifie 1 à 8. La chaine commence par un bloc de 3 bits qui indique la taille du caractère suivant par exemple :

Mettons que le dictionnaire dise:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
'e' : 0
'a' : 1
i: 00
u: 01
'd' : 10
'l' : 11

etc

Pour coder "duel", on fait

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
   taille code
d 01      10
u 01      01
e 00       0
l 01      11

Ce qui donne une séquence

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
2 'd' 2 'u' 1 'e' 2 'l'
01 10 01 01 00 0 01 11

soit

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
0110 0101 0000 111x
 
95 0E (avec x=0)

soit 4 caractères en 2 octets, c'est pas trop mal non ?

en fait il faudrai que je mette quelque part (temporairement) la chaine totale (de tout le fichier) puis que je la coupe en paquets de 8 bits puis que je foute ces paquets dans le fichier sous forme d'octet...

tu pense que ca peut marcher ca ???

Oui, mais le codage 'à la volée' est aussi possible. C'est séquentiel et assez simple. Fait l'essai...

Je vois mal comment coder du Huffman sans passer la taille de chaque 'pseudo-caractères', puisque celle-ci est variable... Par contre, on peut décoreller la chaine de bits qui est de largeur variable, du flux d'octets qui est de taille fixe. Le flux d'octets est simplement le 'tranporteur' du flux de bits. Seuls un nombre variable de bits (1 à 7) sont 'perdus' dans le dernier octet

**Emmanuel Delahaye** · 19/12/2004, 17h09

Envoyé par ben13

pendant que j'y suis

si jamais je fais ca, j'ai une question purement syntaxique.

pour chacun des caracteres presents dans le texte, j'ai une structure dans laquelle figure un int (taille du code binaire) et un tableau d'int (code binaire de ce caractere composé donc unquement de 0 et de 1)

C'est pas une bonne conception. Lorsque tu fais l'analyse du bloc de données, tu en déduis un code et une (taille) pour chaque caractères :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
0 (1)
1 (1)
00 (2)
01 (2)
10 (2)
11 (2)
etc.

Comme la taille de chaque code est connue, il suffit de placer la valeur du code directement dans un int, et c'est bon.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
struct huff
{
   unsigned size;
   unsigned value;
};

Ensuite, on crée un tableau de 256 membres (l'index correspond par exemple aux valeurs du caractère 0 à 255),

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

struct huff tab_huff[256];

<edit> était 255 </edit>
Exemples (basés sur le scrabble en français)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
 'e' : 
tab_huff['e'].size = 1;
tab_huff['e'].val = 0;
...
'w' : 
tab_huff['w'].size = 7;
tab_huff['w'].val = 0x7F; /* 1111111 */

Chaque caractère sert d'index au tableau, et on a donc accès aux informations de codage directement.

**ben13** · 19/12/2004, 17h14

le tableau que j'ai fait a cette structure

bon ecoute je vais essayer differents trucs et je te tiens au courant

merci pour tout et a tres bientot

**Emmanuel Delahaye** · 19/12/2004, 17h18

Envoyé par ben13

le tableau que j'ai fait a cette structure

Quelle structure ? Pour savoir de quoi tu parles, il faut apprendre à utiliser le bouton [Citer]...

**ben13** · 19/12/2004, 17h25

Ensuite, on crée un tableau de 256 membres (l'index correspond par exemple aux valeurs du caractère 0 à 255),
Code:
struct huff tab_huff[255];

Exemples (basés sur le scrabble en français)
Code:

'e' :
tab_huff['e'].size = 1;
tab_huff['e'].val = 0;
...
'w' :
tab_huff['w'].size = 7;
tab_huff['w'].val = 0x7F; /* 1111111 */

Chaque caractère sert d'index au tableau, et on a donc accès aux informations de codage directement.

ce tableau la

mon tableau de correspondance je l'ai bien fait comme ca

**ben13** · 19/12/2004, 19h29

bon je suis parti dans mon idee et voila ce que j'ai fait

j'ai mon fichier avec des 0 et des 1(qui sont des int pour l'instant), ce fichier je l'ai bien evidement construit avec mon tableau de correspondance et a partir d'un fichier texte "a compresser"

je lis ce fichier par blocs de 8 entiers que je mets dans un tableau d'int de taille 8 donc.

ensuite, a partir de ce tableau, j'effectue la conversion de ces 8 "pseudo bits" en un int avec l'algo des puissances de 2

ca me donne donc un int (j'ai vérifié ca marche)

mais jai un petit prob c'est que cet int, qui est en fait un char, il me le donne de la facon suivante :
- en positif si compris entre 0 et 127
- en negatif si compris entre 128 et 255 (en faisant un espece de modulo cad 255 = -1 par ex)

voila tu peux me dire si ca pose un prob ca ?????

merci

**Emmanuel Delahaye** · 19/12/2004, 19h32

Envoyé par ben13

mais jai un petit prob c'est que cet int, qui est en fait un char, il me le donne de la facon suivante :
- en positif si compris entre 0 et 127
- en negatif si compris entre 128 et 255 (en faisant un espece de modulo cad 255 = -1 par ex)

voila tu peux me dire si ca pose un prob ca ?????

Ben oui. Je recommande l'emploi de unsigned int pour la manip...