Compression RLE - Page 5

Thibaut (./118) :
Faut dire que l'archive n'est pas accessible facilement. Faut savoir qu'elle existe, et où, pour la trouver

pstarter se trouve dans les sources de TIGCC, je ne vois pas quel endroit serait plus logique.

Bon, l'Address Error est parce que tu n'as pas mis le nom du programme correctement:

Thibaut (./106) :
J'ai donc pris les sources de pstarter, et j'ai remplacé comme il convient la chaîne à la fin :

ProgramName:
.asciz "einsppg"

Bah non, ce n'est pas comme il faut ça, la taille de cette chaîne est impaire (il y a le 0 de .asciz derrière, mais il y a aussi le .byte 0 devant pour faire un SYM_STR valide), donc il faut rajouter un .byte 0 ou .even derrière.

Mais je vais corriger ça (mettre les handles devant, comme ça on n'a pas besoin du padding à la fin).

Cette version devrait être robuste contre les Address Errors maintenant: http://tigcc-linux.cvs.sourceforge.net/*checkout*/tigcc-linux/tigcc/pstarter/pstarter.s?revision=1.2

Un grand merci à toi

Ouhh, ça discute beaucoup ici!

J'ai des problèmes d'accès à Internet ces temps-ci et mon temps de connection est des plus... limité.

Pour ce qui est de l'avancement de mes projets, j'ai presque fini mon programme de création de sprites.
J'ai intégré à ce programme la base de mon RLE adapté.
Cependant je l'ai quelque peu modifié pour mieux correspondre aux sprites (32x32 pixels dans mon cas), en stockant les suites de pixels non pas sur 8 bits (ce qui permet de stocker des suites de 255 pixels au maximum, ce qui est adapté aux images) mais sur 4 bits (ce qui permet de stocker des suites jusqu'à 15 pixels, ce qui correspond mieux aux sprites).

Grace à ce système là (pas optimisé puisque je n'ai pas, par exemple, mis en place les bandeaux permettant d'éloigner de la compression les parties "non-rentables") j'obiens une compression des sprites jusqu'à 70%, dans le cas d'images blanches ou noires. Cependant vu que je n'ai pas pu finir tout à fait mon programme je n'ai pas pu voir ce que donnait ma compressio à "grande échelle" (j'ai notamment des problèmes de décompression).

Je vous donne plus d'infos dès que possible (et si ma connection me le permet).

Nonon.
Je parle bien de bits.

Je les manipule en convertissant mes octets en binaire et vice-versa.
Cela me permet de stocker deux suites de 15 pixels maximum dans un seul octet.

lol

Bah, c'est peut-être barbare (bande d'assemblistes ) mais ça marche hein ^^.

Oui, je me suis mal exprimé.
Quand je parlais de conversion, je voulais dire que je mettais l'octet (de forme décimal) en forme binaire, et que j'opérais ainsi sur les bits.

C'est-à-dire, tu fais quoi précisément ?
Parce que comme l'a dit Martial, un octet représente simplement une donnée de la taille de 8 bits. Un octet n'a pas de "forme" (décimale ou binaire ou autre).

Et bien, quand on lit un octet dans un fichier (avec la fonction fgetc) la fonction renvoye un nombre sous forme décimal, représentant l'octet stocké en mémoire.

Je me contente juste de faire passer ce nombre décimal en binaire, faire les modifications que je souhaite effectuer au niveau du bit, puis refaire passer le nombre du binaire en décimal pour pouvoir le réenregistrer en mémoire.

Ce que Martial Demolins et Sasume voulaient dire, c'est que "faire passer ce nombre décimal en binaire" n'a pas de sens. Ces différentes bases ne sont que des représentations humaines; visuelles, si tu préfères. Pour une machine, 1010 en binaire, 10 en décimal et 12 en octal sont trois fois la même chose : seule la valeur compte, pas les chiffres que tu utilises pour l'écrire, toi, avec l'une des représentations que tu connais (binaire, octal, décimal, hexadécimal, ou n'importe quoi d'autre). Donc dans ton programme, la valeur renvoyée par fgetc n'a pas de "forme"; c'est uniquement à toi de choisir comment tu veux la considérer, mais aucune conversion ni aucune autre transformation ailleurs que dans ton esprit n'est nécessaire pour ça.

(mais si ça ne semble toujours pas clair, il y a déjà eu des explications, probablement meilleures, sur ce forum; il faudrait juste les retrouver)

Oui, je ne comprends pas moi non plus ce que tu dis Daniel. Peux-tu nous expliquer en détail ce que tu fais ?

Raaah mais c'est pas compliqué...
Au lieu d'utiliser, par exemple, 8 bytes pour représenter 01001111 (en prenant un byte par représentant), il utiliser un seul byte qui représente à lui seul les huit caractères.
Ca peut sembler très con pour les gens qui ont l'habitude de développer mais, en mon temps, j'ai aussi été très fier quand j'ai eu cette idée ^^

Nil (./137) :
il utiliser un seul byte qui représente à lui seul les huit caractères.

balèze, avec ça on doit pouvoir compresser sacrément n'importe quel fichier

(sinon ok, vu ^^)

Euhh... J'en suis plus tout à fait là quand même...
Utiliser un octet pour stocker 8 pixels (donc 8 bits), je l'ai fait depuis un certain temps.

Pour mieux expliciter ce que je fais:
Imaginons que je récupère avec la fonction "fgetc" un unsigned char. Comment puis-je voir ce nombre en tant qu'une suite de 8 bits, à part en créant moi-même cette chaine (à partir de l'unsigned char récupéré), et donc le manipuler comme tel?
S'il existe une méthode simple (autre qu'apprendre l'asm ^_^) pour lire et changer tel ou tel bit en C, alors je ne la connais pas.

Pour faire ce travail, je "place" mon nombre, lu en tant que décimal, dans un tableau de 8 caractères, ou chaque caractère représente un des bits du nombre initial.
Même si j'admet que c'est un peu louche, manipuler alors les bits devient très facile.

J'espère que mon explication n'est pas trop incompréhensible.

Merci d'accorder un peu de votre temps à mes "expériences".

Daniel Vouaux (./139) :
S'il existe une méthode simple (autre qu'apprendre l'asm ^_^) pour lire et changer tel ou tel bit en C, alors je ne la connais pas.

Au hasard... faire une opération booleenne ?

D'accord, mais je ne connais que les opérateurs de base du boléen (et encore, je les utilise, mais de là à savoir comment ils marchent exactement..) du type "et", "ou", "non"...

Je vais regarder ce que je peux trouver sur le sujet.

bah tu as juste trois opérateurs binaires en C pour réaliser des ET, OU et OU exclusifs (&, | et ^), ainsi qu'un opérateur unaire d'inversion de bits (~); à partir de là, c'est facile de tester un à un les bits d'un entier, et d'éviter du coup de stocker chacun de ses bits séparément (d'ailleurs tu faisais ça, mais sans connaître les opérateurs binaire ? )

ben peut-être qu'il faisait des divisions et des modulo ?

euh sinon Nil fais gaffe quand tu parles d'opération booléenne, a priori ça signifie (ou du moins ça peut être compris comme) opération sur des booléens, et c'est ça qu'a l'air d'avoir compris Daniel. Les opérations "bitwise" n'ont (presque) rien à voir avec les opérations sur les valeurs de vérité (enfin conceptuellement ça a à voir, mais d'un point de vue informatique ça n'a aucun rapport).

Bon je vais essayer de faire un mini topo vu qu'il n'y a pas l'air d'y avoir un lien qui traîne.
(Je prends juste des exemples, ça devrait être assez clair)

soit a qui s'écrit 01001101 en binaire. (pour le déclarer : unsigned char a = 77; (représentation décimale) ; ou, équivalent : unsigned char a = 0x4D; (représentation hexa) ; ou encore, valable *uniquement avec tigcc, ce n'est pas du C standard* : unsigned char a = 0b01001101;)

soit b qui s'écrit 10011001 en binaire.

a & b est le nombre (de 8 bits, l'octet quoi) qui a des 1 là où a *et* b ont tous deux des 1, et des 0 là où l'un des deux à un 0. Donc a & b = 00001000.
a | b est le nombre qui a des 1 là où soit a soit b a un 1, et des 0 là où ils ont tous les deux un 0. Donc a | b = 11011101.
a ^ b est le nombre qui a des 1 là où les bits de a et b sont différents et un 0 là où ils sont identiques. Donc a ^ b = 11010100.
Propriété intéressante : a ^ (a ^ b) = b, et b ^ (a ^ b) = a.
~a est le nombre qui a des 0 là où a a des 1 et réciproquement.

Ensuite tu as les opérateurs de décalage : (a >> 3) décale tous les bits de a vers la droite de 3 rangs, en rajoutant des 0 à gauche, donc (a >> 3) = 00001001 ( ce que je dis n'est valable qu'en UNSIGNED, sinon ça se comporte de façon plus compliquée).
<< fait la même chose vers la gauche, en rajoutant des 0 à droite.

Bon avec tous ces opérateurs tu peux facilement faire des opérations simples comme :
— mettre à 1 le troisième bit en partant de la droite d'un octet n : n | 0b100 (ou n | 4)
ainsi a | 0b100 = a (le troisième bit est déjà à 1) mais b | 0b100 = 10011101.
— mettre à 0 le troisième bit : n & 0b11111011
— changer la valeur du troisième bit : n ^ 0b100
— savoir si le troisième bit est à 1 ou à 0 : n & 0b100 vaudra 0 si et seulement si le bit est à 0. Donc tu peux faire un if (n & 0b100) qui s'exécutera ssi le bit est à 1.
Attention que si le bit est à 1 le résultat n'est PAS 1 (c'est le nombre où seul le bit que tu voulais tester est à 1), en l'occurrence a & 0b100 = 4. Et b & 0b100 = 0.
etc.

Sally (./143) :
euh sinon Nil fais gaffe quand tu parles d'opération booléenne, a priori ça signifie (ou du moins ça peut être compris comme) opération sur des booléens, et c'est ça qu'a l'air d'avoir compris Daniel. Les opérations "bitwise" n'ont (presque) rien à voir avec les opérations sur les valeurs de vérité (enfin conceptuellement ça a à voir, mais d'un point de vue informatique ça n'a aucun rapport).

Bah ça reste des opérations booléennes, puisqu'on travaille bit à bit, sur des informations en base 2, dans le cadre de la logique définie par l'algèbre de Boole, non ?

Auparavant, pour stocker les bits séparement, je convertissais mon nombre N de base 10 en base 2 (programme de Terminale S spé math).

En plus j'ai développé une technique personnelle très facile :

Variables:
- Le nombre décimal N à faire passer en base 2.
- Une chaine de caractères de 8 chars où stocker notre chaine de bits.

Tant que (N != 0)
{
Si (N est impair)
{
On stocke '1' dans le chaine de caractères;
N=N-1;
}
Sinon //Si N est pair
{
On stocke '0' dans le chaine de caractères;
}
N=N/2;
}

=> Notre chaine de char contient la forme binaire du nombre à l'origine sous forme décimale.

./143 > Ou, plus rapidement (en supposant, comme ça semble être le cas, que Daniel connaisse les opérations booléennes de la forme booléen opérateur booléen (avec booléen ne pouvant prendre que 2 valeur, vrai ou faux)), on peut dire que les opérations bitwise de la forme octet opérateur octet réalisent parallèlement (c'est-à-dire simultanément et indépendamment) 8 opérations booléennes booléen opérateur booléen, avec « 0 = faux » et « 1 = vrai ».
De même avec la négation bitwise négation octet qui réalise parallèlement 8 négations booléennes négation booléen.
C'est cette réalisation simultanée et indépendante des opérations bitwise sur chacun des 8 bits des octets qui fait que les propriétés booléennes^(*) (comme le « a ^ (a ^ b) = b » indiqué par Sally) se retrouvent en bitwise.

(*) Ici, je voulais donner « quelques propriétés booléennes intéressantes parmi tant d'autres », mais finalement, ça mériterait un article complet... que j'ai bien envie de faire, à la réflexion .


./145 > Je ne vois pas en quoi cette technique est « personnelle », mais j'admets que quand on travaille sur les bases de numération sans vraiment savoir ce que c'est, ça ne doit pas être trivial.

Nil > euh... c'est à base d'opérations booléennes, oui, mais quand tu fais un "&" sur deux octets ça fait 8 opérations booléennes bien distinctes en parallèle, ça n'est donc certainement pas UNE opération booléenne . Bon ça explique qu'on parle d'opérateur "booléen", bien sûr, entre gens qui se comprennent, mais face à des gens qui ne s'y connaissent pas tu risques fortement de les induire en confusion...
(edit : double cross)

./147 > Euh, c'est à moi en ./146, que tu réponds ?
Justement, je ne parle pas de « UNE opération booléenne » mais de « UNE opération bitwise » qui équivaut à « 8 opérations booléennes en parallèle ».

Sinon, j'ai vu que tu as édité pour ajouter les décalages, chose que j'allais faire, mais j'ai préféré me contenter des &|^~, puisque les décalages ne servent pas dans le cas particulier du traitement RLE (qui est le sujet du topic, je le rappelle ).

Sally (./147) :
Nil > euh... c'est à base d'opérations booléennes, oui, mais quand tu fais un "&" sur deux octets ça fait 8 opérations booléennes bien distinctes en parallèle, ça n'est donc certainement pas UNE opération booléenne .

si si : http://en.wikipedia.org/wiki/Boolean_algebra_(structure)
bref, les entiers sur 8 bits forment une algèbre de Boole de dimension 8, avec les opérateurs booléens &, | et ~ et les constantes 0 et ~0 = -1 = 255

tu dois confondre "opérateurs booléens" et "opérateurs logiques", en fait : les opérateurs booléens comprennent à la fois les opérateurs logiques (&&, || et !) et les opérateurs bitwise (&, | et ~) -- je suppose que la confusion vient du fait que quand on dit "valeur booléenne" en informatique ça veut dire uniquement "true ou false" ou encore "0 ou 1"...

oui bon ok... (tiens au début j'avais écrit « ça dépend du sens que tu donnes à “booléen” », mais je l'ai retiré apparemment ^^)
mais le fait reste que parler d'opération booléenne sans préciser ça peut laisser penser qu'il s'agit d'opérations sur les booléens, au sens « valeurs de vérité ».
(cross-édit : oui effectivement j'ai sans doute confondu (et apparemment Daniel Vouaux aussi ^^))