Discussion :

[fred61]

Bonjour,

Je suis en train d'étudier la compression Huffman et comment l'adapter en C et il y a un point que je ne comprend pas.

Mon problème est de savoir comment je vais écrire dans mon fichier compressé après avoir fait mon arbre, en effet en c il n'est possible d'écrire dans un fichier binaire que 8 bits par 8 bits, et pas bits par bits, alors comment faire pour inscrire un 'e' (qui ne sera composé seulement de 3 bits 101) dans mon fichier compressé ?

J'espère que j'ai été assez clair.

Si vous pouvez m'éclairer ?
Merci.

[ram-0000]

Dans ce cas, effectivement, tu ne peux pas écrire les 3 bits.

Donc tu les gardes quelques part et tu traites le caractères suivants en ajoutant les bits du caractère suivant à ces 3 bits. Dès que tu as 8 bits, tu les écris, tu supprimes les 8 bits écrit de ta mémoire et tu continues.

Bien sûr, il faut gérer les cas un peu plus spéciaux

Code :

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

1
2
3
4
caractère ==> 3 bits ==> 0 + 3 = 3 bits en attente
caractère ==> 9 bits ==> 3 + 9 = 12 bits en attente ==> ecrire 8 bits, reste 4 bits
caractère ==> 5 bits ==> 4 + 5 = 9 bits en attente ==> ecrire 8 bits, reste 1 bits
...

[fred61]

Et le mieux pour stocker les bits en attentes, c'est d'utiliser un champs de bits ? ou il y a une meilleur solution ?

[wadabush]

Champ de bits ou bien tu peux t'amuser avec les decalages et les |. Je pense que niveau performance, ca doit s'equivaloir (ca se dit ca? )

[ram-0000]

Champ de bits ou bien tu peux t'amuser avec les decalages et les |.

Je jouerai plutôt avec les opérateurs de décalage (<<, >>) et les opérateurs logiques (&, |). J'ai peut que tu te prennes la tête pour rien avec les champs de bits.

... ca doit s'equivaloir (ca se dit ca?

PS, je viens de vérifier, le verbe equivaloir existe bien dans le Larousse

[Mac LAK]

L'idéal est quand même d'avoir, au minimum, un buffer de 8 bits (un char) en sortie, dans lequel tu "pousses" les bits un par un par décalages successifs et masquage. Quand l'octet-buffer est plein, tu l'écris sur le disque (ou vers un autre buffer plus gros, si les performances sont un souci), et tu recommences à zéro.
Les champs de bits, c'est vraiment pas une bonne idée pour faire ce genre d'opération, par contre, je te le déconseille.

Solution déjà testée et validée en Ada, langage infiniment plus restrictif que le C, et qui n'a pas bronché d'un poil face à cette méthode...

[plxpy]

Pour info, vous opposez une méthode utilisant un buffer de n char (n*8 bits) avec décalages à droite, à gauche et utilisation des masques et une autre utilisant des "champs de bits".

Si je vois parfaitement à quoi correspond la première méthode, celle que j'aurais utilisée "naturellement", je ne vois pas à quoi fait référence la deuxième. Qu'entendez-vous par "champs de bits" ?

[Mac LAK]

Qu'entendez-vous par "champs de bits" ?

Ça :

Code C :

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

1
2
3
4
5
6
7
8
9
10
typedef struct {
    char bit0 : 1 ;
    char bit1 : 1 ;
    char bit2 : 1 ;
    char bit3 : 1 ;
    char bit4 : 1 ;
    char bit5 : 1 ;
    char bit6 : 1 ;
    char bit7 : 1 ;
} char_bitfield ;

[plxpy]

Ok, merci. J'avais pris le terme "champs" de façon générale, et pas comme "champs d'une structure".

[Mac LAK]

Ok, merci. J'avais pris le terme "champs" de façon générale, et pas comme "champs d'une structure".

C'est le terme consacré en C : "bitfields" en anglais, "champs de bits" en français. Quand tu verras ces termes dans une discussion C/C++, c'est très rarement autre chose que les structures dans le genre de l'exemple ci-dessus... Et quand c'est autre chose, c'est en général précisé explicitement.

[plxpy]

Dans le cadre des bits, je ne suis pas tout à fait d'accord.

"A bit field is a common idiom used in computer programming to store a set of Boolean datatype flags compactly, as a series of bits. The bit field is stored in an integral type of known, fixed bit-width." (wikipedia)

Autant le terme "champ", dans tout autre contexte, m'aurait, évidemment, fait penser à un champ d'une structure, autant là ça pouvait porter à confusion. Mais c'est du détail.

[Mac LAK]

"A bit field is a common idiom used in computer programming to store a set of Boolean datatype flags compactly, as a series of bits. The bit field is stored in an integral type of known, fixed bit-width." (wikipedia)

Ce qui est exactement ce dont on parle : les données sont bien une série de bits compacts (pas d'espace entre les divers bits), et c'est stocké dans un type intégral connu de taille fixe (un "char" dans l'exemple ci-dessus)...

[wadabush]

J'aurais une question concernant ces bits fields.

Ce qui est exactement ce dont on parle : les données sont bien une série de bits compacts (pas d'espace entre les divers bits), et c'est stocké dans un type intégral connu de taille fixe (un "char" dans l'exemple ci-dessus)...

Est-ce que la chose suivante est tout le temps vraie?

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
typedef struct {
    char bit0 : 1 ;
    char bit1 : 1 ;
    char bit2 : 1 ;
    char bit3 : 1 ;
    char bit4 : 1 ;
    char bit5 : 1 ;
    char bit6 : 1 ;
    char bit7 : 1 ;
} char_bitfield ;

Si je caste le premier element de mon champ de bits en char, je retrouve la valeur du char correspondant a mon champ de bit?

Pour moi la reponse est non, et depend tres serieusement du compilo. Des commentaires?

[Mac LAK]

Si je caste le premier element de mon champ de bits en char, je retrouve la valeur du char correspondant a mon champ de bit?

Non : si tu castes le champ lui-même (struct.bit0), tu n'obtiendras que la valeur 0 ou 1, étendue au nombre de bits correspondant au type destination (ex : 32 classiquement avec un cast (int)). Tu ne retrouverais la valeur du char que si tu castes la structure elle-même, ou que tu la couples avec un char dans une union bien sûr.

Pour moi la reponse est non, et depend tres serieusement du compilo. Des commentaires?

En fonction du compilateur et de l'endianness de la cible, le premier bit déclaré n'est pas forcément le même bit dans l'octet. Il y a des inversions entre GCC / Big-endian et Visual / Little-endian, par exemple, j'ai déjà eu la farce... Ce qui rend l'écriture de telles structures hautement dépendant de la plate-forme et du compilateur, et donc en général fortement déconseillé en dehors des couches très bas niveau.
Pour être honnête, en dehors des bouts de code tapant dans des registres / ports I/O et des protocoles réseau, je n'ai jamais vu de nécessité impérative d'utiliser les bitfields... Or, justement, ces deux types de code sont inextricablement liés à la machine et/ou au compilateur / OS...

Par contre, l'insertion des bits par des décalages / masques, elle, est toujours portable sans restriction tant que tu ne sérialises pas (à ce moment, l'endianness peut jouer si tu travailles sur plus de 8 bits). Mais en restant sur un flux d'octet, même l'endianness n'a plus aucun impact.

Toutefois, en théorie, l'accès par un bitfield est plus rapide que par des décalages / masques manuels, car le compilateur peut utiliser des trucs assez immondes pour optimiser l'accès (ex : décalage bourrin de la valeur et test direct du flag Carry), tout particulièrement en lecture. Comme souvent, tu dois donc trancher entre performances maximales et portabilité...
De plus, dans ce cas particulier du codage de Huffman, je trouve le code avec les décalages plus agréable à lire que celui via les bitfields, car ce dernier ne permet pas l'accès via des boucles et impose des séries hideuses de "switch" assez moches ou l'utilisation de macros encore plus moches...

[wadabush]

Ok merci de l'eclaircicement.

Je n'ai en effet vu l'emploi de ces bit fields seulement dans des couches plateformes dependant, ce qui confirme ce que tu viens de dire!