Remplir un fichier binaire de BITS !!!!

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 ...

Citation:

---

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:

---

1 2 3 4

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)

Par exemple :

Code:

---

1 2 3

L- V-------- 15 9B 56 68

---

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

Code:

---

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:

---

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:

---

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

---

Merci pour ta reponse.

Citation:

---

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

Citation:

---

Envoyé par ben13

Citation:

---

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.

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 ..... :roll:
de plus j'ai jamais entendu parler les opérateurs simple pipe ( | ), ou simple &

Citation:

---

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.

Citation:

---

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 ?

Citation:

---

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.

Citation:

---

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

---

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

Citation:

---

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

---

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

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

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

Citation:

---

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.)

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

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

Citation:

---

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:

---

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:

---

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:

---

1 2 3

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

---

soit

Code:

---

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 ?

Citation:

---

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

Citation:

---

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:

---

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:

---

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:

---

struct huff tab_huff[256];

---

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

Code:

---

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.

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 :)

Citation:

---

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]...

Citation:

---

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

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

Citation:

---

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...

beh g testé avec des unsigned mais ca fait pareil

je vais retester

bizarre il me sort une erreur de segmentation avec les unsigned int alors ke ca marchait avec les int ....