Compression RLE - Page 3

Il y a quand même un avantage à séparer les plans et compter les bits : comme après des 0 viennent des 1, et inversement, il n'y a pas besoin d'indiquer la valeur de ce qui est répété, c'est la position du compteur qui indique le bit répété (les octets en position paire codent les 0, ceux en position impaire, les 1).
Exemple : 0|42|53|255|0|50 42 “1”, 53 “0”, 305 “1” (soit 400 pixels dont ce n'est qu'un seul des 2 plans).
Cependant, on ne peut pas se contenter de juxtaposer les 2 listes obtenues (1 par plan) qui, d'ailleurs, n'ont pas forcément la même taille, il faut un header pour indiquer la séparation entre les 2 listes.
Si l'exemple donné représente le premier plan (celui des bits de poids fort des pixels), le second plan pourra être : 23|17|255|0|25|50|0|30.
Si l'entête est le codage sur 2 octets de la taille du premier plan (soit au moins 65'535 pixels codables, le pire des cas étant un plan 1|1|1|1...) en big-endian (ordre du 68k), ça donne : 0|6|0|42|53|255|0|50|23|17|255|0|25|50|0|30 16 octets pour 400 pixels, c'est vraiment pas mal.
Comme je l'ai déjà dit en ./40 (entre autres), le travail en plans séparés et bit à bit donne, je pense, la meilleure compression possible.
MAIS encore faut-il compresser les 400 pixels initiaux en ces 16 octets, et réciproquement décompresser ces 16 octets en 400 pixels.
Et là, je vous souhaite bien du courage (Asm rulez !!!)

Sa ne vaus pas u bon vieux LZ77 ^^


Je me demande si du huffman ne serait pas bien aussi pour des images..

Oui, c'est certainement utilisable, mais il faut juste voir si tu veux un dictionnaire pour chaque image ou un dictionnaire pour chaque groupe de x images. Histoire de gagner un peu plus de place, on utiliserait la dèrnière possibilité mentionnée, mais ça doit être passablement long de générer le dictionnaire, et je ne sais pas le temps que ça prendrait pour décoder une image de la sorte...

Huffman est plutôt pas mal. Je ne sais pas ce qui existe sur TI pour compresser en Huffman pur, alors mon conseil très personnel, si tu veux évaluer la performance de cet algo sur tes images, c'est d'utiliser Einstein. Il compresse et décompresse en 2 clics. Par contre je ne pourrai pas te filer le code, j'ai perdu la source en 2004.
Après, si tu es séduit par l'algo et que tu veux de l'aide, je peux tenter de recoder tout ça. C'était une cinquantaine de lignes de C je crois.

Cela dit, tu constateras que Huffman est relativement lent par rapport à du RLE. Pour faire des tests plus précis, tu peux (dé)compresser plusieurs fichiers d'affilée en les sélectionnant puis en faisant F3/Décompresser.

huffman lent ? c'est un des algo de décompression les plus rapides (bcp bcp plus rapide que du LZ77 par exemple, ou tout format basé sur des fenetres & dico)

(d'ailleurs a mon avis la du LZ77 pour du NVG ou du N&B marcherais mieux en B&B que en octet par octet, ne serait-ce que a cause de la taille qui est deja petite, et puis ça doit pouvoir etre optimisable vu que certain motifs doivent facilement ce repeter. A mon avis trouver/faire un algo qui compresse bien pour des images en N&B doit etre assez simple)

LZH serait encore mieux ^^

Godzil, t'as pas lu toute ma phrase :

Cela dit, tu constateras que Huffman est relativement
lent par rapport à du RLE.

Alalah ces vieux, ils ont une trop mauvaise vue

j'en suis pas sur justement que ça soit bien plus lent...

Roooh !!! J'ai dit "relativement", pas "bien"
Après ça dépend, si il fait du RLE bit à bit ou sur des octets. Je veux bien affirmer qu'un RLE sur des octets est beaucoup plus rapide qu'Huffman.

Il me semble avoir encore un début de compresseur rle/lz77/huffman en C pour Ti; ça date pas mal et le code n'en est que davantage à ne surtout pas prendre comme exemple, et ça n'est pas un projet fini (en particulier il y a une histoire de corruption des fichiers .ASM lors de la décompression, mais c'est tellement loin que j'ai toutes les chances de raconter n'importe quoi si je détaille ^^). Quoiqu'il en soit pour des fichiers quelconques ça devrait à peu près fonctionner, et donc si ça t'intéresse pour des benchs ou autres tests, ça doit pouvoir se retrouver

Pollux a fait un algo de dé/compression on-calc d'une performance et d'une rapidité surprenantes (supérieures à TT Pack). Tu le trouveras peut-être dans les sources de GTC.

Perso je teste déjà ce que je peux faire moi-même avant d'aller voir le travail déjà fait par les autres.

Il existe un algo de décompression Capcom utilisé dans la plupart des jeux GBA. Il utilise la méthode LZSS et marche rapidement. Mais j'ai que le code du décompresseur.
Bon y a toujours moyen facilement de coder le compresseur. En tout cas si tu peux me donner quelques images je pourrais les compresser avec différentes méthodes et voir ainsi celle qui semblerait le mieux adaptée aux TI.

Tu trouveras un dossier que j'ai fait ainsi que différentes méthodes de compression dans un programme sur http://www.tigen.org/index.php?module=archives_pws catégorie tutoriaux. (bon faut pas trop regarder les fautes d'orthographes. ^^).

Il y a d'énormes chances que le format LZW soit le plus adapté aux images sur TI en terme de taux de compression.

> Pollux a fait un algo de dé/compression on-calc d'une performance et d'une rapidité surprenantes (supérieures à TT Pack)
C'est tout à fait possible, mais formulés qualitativement, tes propos sont invérifiables, car tu n'as pas précisé de quel ttunpack tu parles (et peut-être que tes connaissances ne sont pas à jour...):
* la version petite, seule version supportée par TIGCC, pour les lanceurs spécifiques de programme. Moins de 200 octets, moins de 30 KO/s (la vitesse était trois fois pire, à une époque...).
* la version rapide: environ trois fois plus grosse, trois à quatre fois plus rapide.

ttpack ne tourne effectivement pas on-calc, et il s'en faut de beaucoup (mémoire nécessaire: 128 KB + 15 * size_of_input, éventuellement réductible à 64 KB + 15 * size_of_input).


Kevin préfère qu'il y ait plusieurs lanceurs spécifiques (pstarter). Comme ça, l'utilisateur bête peut lancer directement son programme, plutôt que d'avoir à faire un truc très difficile comme ttstart("..."). Autrement dit, ça multiplie le nombre d'exemplaires du code du lanceur, et pour compenser, il faut optimiser taille à fond (les programmes des autres, pas les siens...), quitte à ce que ça ait un impact significatif sur la vitesse (dont personne n'a besoin, de toute façon, comme vous le savez tous très bien).
Je préfère qu'il y ait un seul lanceur générique. Même en prenant la routine rapide de décompression, un ttstart générique est (de mémoire) ~700 octets plus petit que deux pstarters spécifiques (~1300 octets vs. 2*~1000 octets). De plus, ça ne fait qu'un seul lanceur à updater, en cas de changement de HW (problème réellement posé lors de l'arrivée des 89T - mais cet argument n'est plus valable depuis qu'on sait qu'il n'y aura plus de nouvelles TI-68k).

Pourquoi tu n'essaies pas GTC ? Je crois que le décompresseur de Pollux est à la fois petit et rapide, mais tu pourrais vérifier par toi-même (il est dans la version pour PC). Si la licence le permet, ou bien en négociant avec Pollux pour assouplir la licence, vous pourriez peut-être en faire le nouveau système de package officiel de TIGCC.

Pour essayer GTC, il faut que je télécharge la dernière version sur le site de Pollux. Je sais que je l'ai dans les bookmarks de Firefox, mais Firefox sous Windows ^^
Le problème de GTC, c'est que sur le plan technique, c'est un concurrent a priori intéressant à TIGCC... 0.94. Depuis (ça fait longtemps !), TIGCC a eu le linker amélioré. Franchement, ce linker-optimiseur change énormément de choses par rapport à TIGCC 0.94-: citons la maintenabilité du code de startup, l'optimisation des références, etc. Ca, c'est un fait que tu refuses manifestement de reconnaître, cf. le flame que tu as déclenché dans topics/101204-super-mario-68k-tres-belle-adaptation-sur-ti-8992v200

Bien sûr, GTC a lui aussi un peu évolué depuis la dernière fois que je l'ai essayé (il me semble qu'à l'époque, certains bouts de son code de startup utilisaient le ghost space). J'avais écrit quelques trucs à Pollux.
De plus, c'est une lapalissade, mais TIGCC est un GCC modifié. Et j'utilise / fais utiliser aux autres programmeurs des finesses non portables de TIGCC que GTC n'a a priori pas (-freg-relative-an, certains __attribute__, etc.). Par conséquent, GTC n'est pas compatible avec certains des programmes que je maintiens, et il y a peu d'incitation pour moi et les autres programmeurs à les rendre compatibles avec GTC.


Maintenant, au sujet du changement de système de compression de TIGCC... Il faut savoir que Kevin n'intègre même pas ses propres contributions à TIGCC (grayscale 3 plans, notamment), sans parler des contributions des autres (des dizaines de documentations de fonctions d'AMS auparavant plus ou moins inconnues, faites par myself). Cela depuis 2001-2002 (aussi bien le grayscale 3 plans que mes contributions). Par conséquent, je serais très surpris qu'il change le système de compression

Ce n'est pas techniquement difficile d'intégrer la décompression de Pollux dans ttstart/pstarter - si elle fonctionne de la même façon que les trois ou quatre autres décompressions supportées, naturellement . Mais le fait est que la base installée de TTPack (dérivé de PuCrunch) sur les TI-68k surpasse de loin celle de n'importe quel autre système de compression. Vu que la plate-forme va disparaître, il me semble très bizarre de changer maintenant le système de compression. Ceci même s'il était techniquement meilleur - c'est à dire dans l'esprit de Kevin, strictement plus petit, la vitesse n'ayant à peu près aucune importance pour lui.

[EDIT: rajouté quelques mots]

Exact, j'avais oublié...

Plusieurs programmeurs, dont Jesse Frey et myself, ont apporté de multiples améliorations aux routines de grayscale 2 plans. Améliorations applicables à la version de TIGCCLIB qui s'embête à choisir des planes non consécutifs sur HW1, et aussi à la routine 3 plans.

Autre exemple: ces jours-ci, je lui ai suggéré une trivialité dans le support de EXECUTE_IN_GHOST_SPACE (en fait, j'ai vu par la suite que j'avais déjà fait un truc mieux que ça dans ttstart, en utilisant dbxx):
(archive/enter_ghost_space_2.s)
add.l #0x12000,%a0
add.l #0x18000,%d0
jbra .L3
.even
.L7:
addq.l #2,%a0
.L3:
cmp.l %a0,%d0
jbls .L4
cmp.l #0xDEADDEAD,(%a0)
jbne .L7
.L4:
tst.w 4(%a0)

à optimiser en
add.l #(0x12000-2),%a0
add.l #0x18000,%d0
.L7:
addq.l #2,%a0
cmp.l %a0,%d0
jbls .L4
cmp.l #0xDEADDEAD,(%a0)
jbne .L7
.L4:
tst.w 4(%a0)

Il m'a répondu que valider que ça ne casse rien allait lui prendre environ 1 heure, tout ça pour économiser 2 octets, et que par conséquent la priorité n'était pas très haute...



Je lui ai (re ?)posé la question de ce qui lui manquait pour intégrer ne serait-ce que ses propres contributions à TIGCC(LIB&DOC). Les TI-68k vont disparaître à moyen terme, le passage des TI-68k aux Nspire (avant qu'on documente à fond les Nspire) donne une occasion de vider le sac des contributions et améliorations en attente...
(Note to self: c'est également valable pour les programmes de TICT, d'ailleurs: même s'il y a peu de contributions et améliorations en attente, faudrait finir ce changement de licence, et faire des releases officielles )

Manifestement, TIGCC manque de manpower. Sur le plan technique, nous sommes un certain nombre à pouvoir faire de la revue de doc ou de code. Sur le plan humain, c'est un poil mieux qu'à une époque, mais il reste difficile de communiquer avec Kevin, sur un certain nombre de sujets, parce que ses idées sont bien arrêtées et peu consensuelles...


[EDIT: et on risque de prendre une fessée, parce qu'on est off-topic, et je sais que c'est moi qui ai commencé ]

Lionel Debroux (./80) :
[EDIT: et on risque de prendre une fessée, parce qu'on est off-topic, et je sais que c'est moi qui ai commencé ]

J'allais te le faire remarquer ...

(Le temps n'est plus à se tapper dessus, mais plutôt au travail communautaire en équipe).

(c'était déjà comme ça il y a 7 ans )

> Toi aussi t'es d'accord avec ça?
D'accord avec quoi ? Faire deux plans non consécutifs ?

En fait, dans mon post "aux routines grayscale 2 plans" est un reste de reformulation partielle de mon post avant de le poster. Ca désignait la routine de grayscale 2 plans de TIGCCLIB, et la routine modifiée pour avoir toujours deux plans consécutifs (routine dans ExtGraph), mais pas Grib.

(+1000 à ./83 et ./84, mais vous savez très bien que pour ce qui est de TIGCC tout entier, ça fait longtemps qu'il n'y a pas eu de travail communautaire... et que si son unique mainteneur-dictateur n'est pas plus ouvert à ce que font les autres, ça ne va pas s'arranger...
Moi, j'ai fait du communautaire, que ce soit avec les fonctions inconnues d'AMS ou ExtGraph, par exemple...)

On va pas relancer le débat, de toutes façons, le nombre de développeurs se compte sur les doigts d'une poignée de mains, c'est pas comme s'il y avait un réel enjeu (autre que le défi, le travail bien fait, etc) à maintenir encore TIGCC. Ah j'oubliais les boîtes indiennes qui veulent des gens qui savent bosser avec TIGCC. Bref, le futur, c'est la nspire. Et pour l'instant, je ne me sens pas les capacités d'aller taper là-dedans, et en plus c'est pas le sujet

> Bref, le futur, c'est la nspire
Clairement, mais ça n'empêche pas ce que j'ai écrit à ./80: "Les TI-68k vont disparaître à moyen terme, le passage des TI-68k aux Nspire (avant qu'on documente à fond les Nspire) donne une occasion de vider le sac des contributions et améliorations en attente..."

C'est clair, et meme s'il n'y a plus grand monde à realeser sur 68K, je pense qu'il y en a un peu plus qu'on ne le pense qui code sur ces plateforme

Tout à fait.
Mais je ne suis pas sûr que la Voyage 200 disparaisse. C'est le seul modèle parmi tous à avoir un clavier QWERTY.