BZ2 compression software - Standard format

View previous topic View next topic Go down

BZ2 compression software - Standard format

Post  Yann on Wed 24 Dec - 19:49

BZ2 is a compression engine completely compatible with the original BZ from Mika Heiskannen and its evolution BZ49.

BZ2 objectives are to compress & decode faster than BZ, while achieving at the same time higher compression ratio. Thanks to full compatibility, BZ2 and BZ1 can decode each other, making BZ2 an interesting upgrade path if you are using BZ-compressed strings.

Current Version : BZ2 2010, binaries for HP48,49&50

Changelog :
- Great increase in decoder speed
- new BZ2.speed version, extremely fast and using very little memory

You can select your speed/compression ratio depending on your usage.
BZ2.speed is nearly instantaneous, but has lower compression performance.
BZ2 has identical compression to original BZ, but is twice faster.
BZ2.max does compress more than BZ.
All BZ2 versions produce BZ-compatible compressed strings.

Benchmark Comparison :
HP49G
See Detailed Results
Update1 Comparison
BZ49BZ2.max
BZ2.normal
BZ2.speed
Memory Req.
11 KB
9 KB
9 KB
3 KB
Compression Ratio
1.80
+3%
+0%
-12%
Encoding Speed
1.00 KB/s
x1.5
x2
x6
Decoding Speed
15.7 KB/s
x2
x2
x2
You may also download the benchmark suite, and check the results with your own calculator.


Last edited by Yann on Thu 24 Mar - 3:08; edited 44 times in total

Yann
Admin

Number of posts : 174
Registration date : 2008-05-01

http://phantasie.tonempire.net

Back to top Go down

Version History

Post  Yann on Sun 28 Dec - 7:54

Update 2
BZ2 Update2, binaries for HP48,49&50
- Corrected a (rare) bug in the max & normal versions

Update 1
BZ2 Update1, binaries for HP48,49&50
- Improved Compression speed (+20%)
- Improved decoding speed (+5%)
- Less memory requirement (-20%)
- Smaller binary size (-10%)
- Correction : "ON" key correctly detected on HP48S serie
Final Release
BZ2 final, binaries for HP48,49&50
Beta 2
BZ2 beta 2, binaries for HP48,49&50
- Improved compression speed
- Introduce BZ2.max compression ratio
Beta 1
BZ2 beta 1, binaries for HP48,49&50
Initial Release


Last edited by Admin on Tue 7 Sep - 23:46; edited 7 times in total

Yann
Admin

Number of posts : 174
Registration date : 2008-05-01

http://phantasie.tonempire.net

Back to top Go down

HP49 Benchmarks

Post  Yann on Sun 28 Dec - 10:16

Summary
HP49G
2010 Benchmark
BZ49
BZ2.speed
BZ2.normal
BZ2.max
Compression Ratio
1.80
1.58
1.80
1.85
Encoding Speed
1.00 KB/S
6.36 KB/S
1.97 KB/S
1.47 KB/S
Decoding Speed
15.7 KB/S
30.2 KB/S
29.8 KB/S
30.8 KB/S
Tested on an emulated HP49G ROM 1.24, using Emu48 v1.45

You may also download the benchmark suite, and check the results with your own
calculator.


Detailed results : 2010

Source/Prog Raw DataBZ49BZ2.speed
BZ2.normalBZ2.max







Text





StringListSize1659,51265,51398.5
1265,51260
small
strings
Decodems138ms68ms
71ms70ms
compresss1,3s0.33s
0,69s0,80s







HLP49's H04Size82725270,56080
5270,55185,5

Decodems627ms318ms
340ms329ms

compresss7,4s1.41s
4,04s
5,45s







HTML Size 34229 10917,5 13172.5
10917,5 10749,5

Decode ms 1371ms 802ms
795ms 768ms

compress s 25,9s 3.09s
12,6s 17,0s







Pictures





City Pic. Size 1098 322,5 399
322,5 299,5
B&W Grob Decode ms 68ms 42.5ms
33ms 32ms

compress s 2,8s 0.125s
1,35s
5.97s







Font 1 Size 2048 1326,5 1539
1326,5 1283
CellGrob Decode ms 188ms 102ms
100ms 93ms

compress s 2s 0.38s
1,07s
2,08s







Joe Size 12554 2052 3686
2052 1931,5
Greyscale
animation
Decode ms 336ms 262ms
190ms 176ms
compress s 10s 0.94s
3.97s
8,58s







RPL





Bmenu Size 281 219,5 228
219,5 216,5
UserRPL Decode ms 30ms
13ms
13ms 13ms

compress s 0,4s 0.07s
0,115s 0,125s







Combat Size 2599 1458 1652
1458 1413
SysRPL Decode ms 184,5ms 94ms
90ms 84ms

compress s 2,12s 0.42s
1,08s 1,43s







TreeBrowser Size 23899,5 14594,5 16334
14594,5 14403,5
SysRPL
Library
Decode ms 1385ms 714ms
768ms 744ms
compress s 21,6s 3.72s
12s
14.9s







ASM





USAG49Size18581655,51713
1655,51643
ASMDecodems105ms47ms
54ms53ms

compresss1,4s0.38s
0,85s
0,93s







NosySize76466516,56974
6516,5 6458

Decodems449ms208ms
245ms238ms

compresss8,1s1.56s
4,79s
5,8s







BeaubourgSize1505679658898
79657793
GameDecodems754ms442ms
417ms404ms

compresss29,1s2.05s
13,3s
41,4s









Last edited by Admin on Sat 11 Sep - 4:31; edited 14 times in total

Yann
Admin

Number of posts : 174
Registration date : 2008-05-01

http://phantasie.tonempire.net

Back to top Go down

Re: BZ2 compression software - Standard format

Post  stfox on Wed 7 Jan - 13:30

Bonjour,

bravo et merci de continuer à faire vivre cette petite calculatrice.
Les résultats avec votre compresseur BZ2 sont exceptionnels,
c'est un domaine qui m'interesse depuis peu, et je m'amuse aussi
à en écrire un mais pour l'instant les résultats sont .. catastrophiques ... lol
Faut que j'en apprenne un peu plus sur les autres algo que lz77.

Fournissez-vous les sources de bz2, ou alors pouvez-vous m'expliquer
comment il fonctionne, quels sont les algo utilisés, qu'est-ce qui fait qu'il
soit si rapide et plus efficace ?

C'est un domaine vraiment passionnant Smile

stfox

Number of posts : 13
Registration date : 2009-01-07

Back to top Go down

Re: BZ2 compression software - Standard format

Post  Yann on Wed 7 Jan - 14:03

Bonjour

En général, je fournis les sources mais avec beaucoup de retard, une fois qu'elles sont stabilisées seulement, ce qui n'est pas encore tout à fait le cas pour BZ2.
Un autre compresseur qui seras probablement stable plus tôt, c'est LZD, ou au minimum son décompresseur ULZ. Le décompresseur est souvent plus simple à lire, et plus clair pour comprendre la logique du format employé.
A court termes, tu peux aussi récupérer les source du BZ original sur HPCalc.org. Elles sont complètes et fonctionnelles.

Mais pour être honnête, je n'ai pas réussi à les lire et à les comprendre avant d'avoir fini mon propre compresseur. La marche à gravir est assez élevée.
Du coup, je te recommande de continuer à faire tes propres expérimentations, même si au début les résultats ne sont pas extras (mon premier compresseur ... augmentait la taille des fichiers Very Happy ) car c'est ce qui te permettra de te poser les bonnes questions. Une fois que tu auras trouvé tes propres réponses, tu pourras les comparer aux autres codes, et là tu auras moyen d'en profiter. Un compresseur bien optimisé, c'est un monstre de complexité. Il y a trop de choses à comprendre d'un seul coup.

Pour débuter sur les compresseurs, il y a pas mal de tutorial sur le net qui aident bien pour mettre le pied à l'étrier. Lz77 est effectivement assez classique, mais pourquoi pas LZP, encore plus simple ? LZW, assez différent ? Un petit Huffman statique pour commencer ? Ensuite, une fois les premières marches franchies, il existe des forums spécialisés. Pour ma part, je vais souvent lire :
http://encode.ru/forum/
Bon, le niveau est assez hardu, mais une fois qu'on est dans le bain, c'est ce genre de discussions qui permet de progresser.

Qu'est ce qui rend BZ2 plus rapide que BZ ?
Et bien il y a plusieurs points, qui chacun apportent leur pierre à l'édifice.
Bon là je risque de parler chinois, mais pour résumer les sujets :
- Un comparateur de chaîne plus rapide
- Une stratégie d'allocation mémoire plus efficace
- Un Hash plus dispersant
- Diverses améliorations de codes, qui permettent de diminuer le nombre de registres utilisés et du coup le nombre de "swap" de données dans l'algorithme
- Un comparateur incrémental plutôt efficace pour les modes "normal" et "max" (non présent dans BZ)
- Dans le decodeur, des fonctions de bit i/o spécialisées pour traiter les cas les plus fréquents (en fait, plus de 90% des cas).

Mais il y a d'autres améliorations possibles. En particulier, LZD utilise une simple chaine descendante pour la recherche de match, alors que BZ utilise une double chaine remontante. Et selon mes calculs, la méthode de LZD est plus rapide (bon, l'adaptation est assez hardue...). Un "flexible parsing" permettrait un meilleur taux de compression au prix d'une grosse augmentation de temps de calcul, etc.

Bref, comme tu l'as fait remarquer, c'est un sujet passionnant, et il reste encore quelques trucs à trouver...

Yann
Admin

Number of posts : 174
Registration date : 2008-05-01

http://phantasie.tonempire.net

Back to top Go down

Re: BZ2 compression software - Standard format

Post  stfox on Wed 7 Jan - 16:49

Merci pour ta réponse détaillées Wink

En effet, je vais peut-être suivre ton conseil, car en surfant un peu,
je me rend compte qu'il existe une multitude d'algorithmes,
et qu'un compresseur efficace combine un bon algo de compression
avec un bon algo d'encodage ou/et de tri, bref c'est loin de ce que je m'imaginais,
c'est-à-dire un lz77 optimisé lol

merci pour le lien également, je vais regarder ca.

Connais-tu l'algo PPM ?
Il semblerai qu'il soit parmis les plus efficace, si ce n'est le plus efficace aujourd'hui,
j'avais envie de commencer par implémenter un autre algo que lz77, et pourquoi pas
celui là .. Enfin, peut-être que je changerai d'avis quand j'aurais vu sont contenu
théorique Laughing
Mais si tu as un avis éclairé sur cet algo, je suis preneur, je ne sais pas trop vers
le(les)quels m'orienter..

Dernière petite question (personnelle), pourquoi avoir choisi la HP48 ?
Pour ma part, je suis tombé dedans quand j'étais au collège, et depuis,
j'en suis toujours amoureux même si j'en ai moins l'utilité.
Ecrire des prog en C sur pc, c'est nettement plus convivial lol

Edit : à priori, vu la consommation de mémoire, PPM n'est franchement pas
approprié pour la HP Laughing

stfox

Number of posts : 13
Registration date : 2009-01-07

Back to top Go down

Re: BZ2 compression software - Standard format

Post  Yann on Wed 7 Jan - 19:02

Il y a deux grandes familles de compresseurs :

- La compression par dictionnaire, parmi lesquels on trouve les fenêtres glissantes (LZ77/LZSS) ou fixes (LZOP) mais également les dictionnaires statiques, ou auto-générés (LZW).

- L'encodage de l'Entropie, parmi lesquels on a Huffman, et on avance jusqu'à la compression arithmétique. PPM en fait partie, et ajoute essentiellement l'idée d'exploiter la notion de "contexte".


Question puissance et performance, la seconde famille est très très loin devant la méthode par dictionnaire. Et c'est à la fois l'avantage ET l'inconvénient.
La plupart des compresseurs modernes pratiquent les 2 méthodes, avec une bonne passe en fenêtre glissante, puis un complément par Entropie (Huffman notamment). C'est le cas de Zip, de 7z, et globalement de presque tous les compresseurs "normaux", avec un bon compromis performance/puissance.

Ensuite, dans la catégorie ésotérique, on a des compresseurs ultra-rapides, donc sans entropie, mais qui compressent moins bien, et parmi lesquels se trouvent d'ailleurs BZ2 et LZD.
Et à l'inverse, on a des monstres, qui fonctionnent à l'entropie "pur", tels PAQ, qui ont les meilleures performances, mais également des temps de compression et de décompression absolument hors normes (pour tout dire, inutilisables).

Ou est le bon compromis ?
Ben en fait, il n'y en a pas qu'un. L'idée, c'est qu'on peut faire un choix sur ce qui nous intéresse.

LZD par exemple, est développé avant tout pour avoir des vitesses de décompression ultra-rapides, l'idée de base étant de fabriquer des exécutables compressés mais qui s'exécutent avec un délais tellement court qu'ils ont l'air non compressés. Mission accomplie, mais il faut faire des concessions sur le format, donc moins bonne compression sur les gros fichiers par exemple.

eLZD.VF est conçu pour une vitesse de compression très rapide, pour être le plus "transparent" possible. C'est utile par exemple pour de la compression "à la volée", pour des transmissions par exemple. Evidemment, le taux de compression s'en ressent.

TNT, c'est la meilleure compression "utilisable" sur HP48. Donc compresse mieux que BZ, mais plus lent, surtout en décompression. C'est un choix.

Pour BZ2, c'est plus facile, on a une "cible fixe", BZ, et on essaie de la battre sur tous les fronts simultanément. Là c'est un gain "pur". Mission accomplie, mais il a fallu d'abord que BZ existe pour avoir une référence à battre.

Tu l'as compris, la HP48, c'est pas un PC moderne, et du coup, ça oblige à penser aux compresseurs "rapides" et peu gourmands. Et c'est tout l'intérêt. L'idée était de choisir une plate forme volontairement restreinte, parce qu'elle oblige à rester simple. LZD est mon premier compresseur, BZ2 mon second, donc pas de quoi "se la ramener", tout ceci est très récent et relativement simple.

Une fois les bases acquises, on peut songer à aller plus loin...


Last edited by Yann on Sat 26 Mar - 0:04; edited 1 time in total

Yann
Admin

Number of posts : 174
Registration date : 2008-05-01

http://phantasie.tonempire.net

Back to top Go down

Re: BZ2 compression software - Standard format

Post  stfox on Thu 8 Jan - 11:34

Merci pour cette belle introduction aux techniques de compressions, on voit
que tu connais bien le sujet Smile

Je pense que je vais m'orienter dans un premier temps vers du LZW ou LZMA
pour avoir quelque chose de plus efficace que lz77, l'améliorer et ensuite
pourquoi pas y ajouter une couche d'entropie, à terme j'aimerai
me rapprocher de l'efficacité d'un winrar par exemple, c'est déjà
un très beau défit bounce

Mais petite question, lorsqu'on a déjà un code bien développé en LZ,
est-ce que vouloir ajouter une couche d'algo d'encodage de l'entropie
demande à revoir complètement son code LZ ou bien, l'entropie
intervient en supplément ?
Parce que les 2 ajoutés, les temps de calculs doivent devenir important !!
Pourtant les logiciels sont quand même très rapide dans l'ensemble scratch

stfox

Number of posts : 13
Registration date : 2009-01-07

Back to top Go down

Re: BZ2 compression software - Standard format

Post  Yann on Thu 8 Jan - 12:19

Il est normalement relativement aisé de rajouter un codeur d'entropie après une première passe en LZ. Là dessus, on peut choisir de faire plus ou moins compliqué, séparer les flux, ajouter des contextes, brefs, les possibilités sont infinies, mais au plus simple, il n'y a "presque rien à faire", c'est juste un deuxième traitement après le premier, comme un pipe.

Ce qu'il faut comprendre, c'est que sur un format donné, on peut choisir le niveau de temps de calcul qu'on y passe. Entre les traitements les plus simples et les plus compliqués, on a des facteurs énormes, jusqu'à plusieurs milliers, surtout en entropie.
La plupart des compresseurs "établis" ont été mis au point il y a de nombreuses années, et ils étaient pensés pour être utilisables sur les machines de l'époque. Forcément, avec l'augmentation considérable des performances, ils ont l'air aujourd'hui très rapide.

Il y a donc aujourd'hui plus de choix possibles, mais on peut toujours choisir des algorithmes rapides.

Les compresseurs les plus performants (PAQ) utilisent des réseaux de neurones pour simuler une intelligence articielle prédictive. Comme tu peux t'en douter, c'est énorme en termes de complexité, donc de temps de calcul.
A l'autre bout de l'échelle, un petit Huffman statique, c'est ultra rapide : on faisait déjà ça sur des ordinateurs 8bits des années 80.

Donc bon, quand on dit "Entropie", on ne fait que citer un type de traitement, mais c'est pas vraiment significatif du temps qu'on va y passer.

Yann
Admin

Number of posts : 174
Registration date : 2008-05-01

http://phantasie.tonempire.net

Back to top Go down

Re: BZ2 compression software - Standard format

Post  stfox on Fri 9 Jan - 10:53

Pour en revenir à BZ, si je suppose bien, pour augmenter le taux
de compression entre la version 'Speed' et 'Max', j'imagine
que tu as dû simplement augmenter la taille du dictionnaire,
car le taux augmente peu, comparé aux temps de calculs
qui décroît bien plus fortement.

Alors, est-ce qu'il est envisageable, pour améliorer le taux
de compression, que tu utilise un algo d'encodage de l'entropie
comme le fait TNT ?

Car vu les excellentes performance de ta version de BZ,
tu peux te permettre d'y ajouter une couche ?
Quitte à ce que BZ ne soit plus BZ, vu qu'il ne sera plus compatible Laughing

BZ utilise l'algo LZ77 ou LZ78 ?

Car j'ai beau chercher, je ne trouve pas de solution
pour améliorer le taux de compression de LZ77
sans passer par le codage de l'entropie ou passer
à LZ78 ou LZW. Crying or Very sad
Par contre des améliorations sur la rapidité, ca on en trouve.
Mon prog de compression fonctionne bien, mais il donne
de moins bon taux que BZ, pourtant comme il fonctionne
sur PC pour l'instant, je peux me permettre de lui
donner un dictionnaire très important.
Donc, quelle est l'astuce dans BZ qui améliore le taux de LZ77 ? Question
Je précise que j'utilise l'encodage des expressions et des symboles
au bit prêt, tout comme BZ, Offset sur 9 à 16bits, et longueur de 4 à 5bits.
Je n'utilise pas encore les tables de Hashage, mais si j'ai bien compris
ca n'est utilise que pour la rapidité de recherche des match, et
non pour l'efficacité de compression.

Voilà, j'ai fini pour l'instant ma liste de questions lol
En tout cas, je te remercie d'avoir pris à chaque fois le temps
de m'apporter des réponses aussi précises et interessantes Wink


Edit : C'est quoi un comparateur incrémental ?

stfox

Number of posts : 13
Registration date : 2009-01-07

Back to top Go down

Re: BZ2 compression software - Standard format

Post  Yann on Fri 9 Jan - 13:41

Wow, je vois que tu fais de rapides progrès vu la nature de tes questions Smile


> Pour en revenir à BZ, si je suppose bien, pour augmenter le taux
> de compression entre la version 'Speed' et 'Max', j'imagine
> que tu as dû simplement augmenter la taille du dictionnaire,
> car le taux augmente peu, comparé aux temps de calculs
> qui décroît bien plus fortement.

En augmentant la taille de la fenêtre (ou du dictionnaire), cela aurait pour effet de casser la compatibilité avec les anciens décodeurs. Hors BZ2 a pour objectif de rester compatible.

J'ai choisi une autre direction : je passe donc plus de temps de calcul sur le "parsing".
Les algorithmes comme LZ77 ont cette particularité qu'ils permettent de représenter le même fichier de plusieurs façons différentes; et toutes ne sont pas aussi efficace.

Pour rentrer dans le vif du sujet, j'utilise une technique appelée "Deep lazy matching", et j'augmente le niveau de profondeur entre les versions normal & max.
Il y a des effets secondaires en employant cette techniques, qui augmentent avec la profondeur, donc on ne peut pas aller trop loin. Ensuite, il faut passer au "flexible parsing", qui coûte beaucoup plus de temps de calcul.

Alors là, j'ai peut-être parlé chinois, mais bon, avec Google, je suis sûr que tu trouveras pleins de docs pour comprendre ces mécanismes. C'est comme ça que j'ai procédé d'ailleurs, donc je sais qu'il y a quelques tutoriaux très efficaces.


> Alors, est-ce qu'il est envisageable, pour améliorer le taux
> de compression, que tu utilise un algo d'encodage de l'entropie
> comme le fait TNT ?

A ma connnaissance, et selon la documentation de TNT, il n'y a pas d'encodage d'entropie dans TNT; il est plutôt question d'une version modifiée de l'Elias Gamma Code, une façon de coder des nombres utilisant un nombre variable de bits (Il y a un bon article sur Wikipedia). Donc les petits nombres utilisent moins de bits que les grands nombres.

Bon, je n'ai pas encore pris le temps de décompiler TNT pour voir comment il fonctionne réellement (il n'y a pas de code source public à ma connaissance), donc je ne suis pas en mesure de te "garantir" ce qu'il y a dans TNT.
Je comptais garder cette étape pour plus tard, mais peut-être devrai-je me dépêcher un peu pour répondre à tes questions Razz


> Car vu les excellentes performance de ta version de BZ,
> tu peux te permettre d'y ajouter une couche ?
> Quitte à ce que BZ ne soit plus BZ, vu qu'il ne sera plus compatible Laughing

Et bien c'est toute la question. La compatibilité, c'est un choix.
Si je devais faire un compresseur non compatible, à mon avis, il faudrait qu'il présente des performances bien plus élevées que BZ (et donc maintenant que BZ2) pour être intéressant.

Dans ce cas, je suis d'accord, probablement qu'il faudrait ajouter une petite couche
d'entropie de type Huffman; mais tout ceci reste à planifier/coder.
Le mieux serait de commencer par une bonne architecture logicielle, avant de se lancer.


> BZ utilise l'algo LZ77 ou LZ78 ?

LZ77.
LZ78 est très très différent, même s'il s'agit aussi d'une méthode par dictionnaire.
Le dictionnaire est alors "créé" et indexé en fonction du flux entrant, et il existe de nombreuses variantes sur la façon de procéder.
De fait, LZ78 impose que le décodeur effectue le même travail d'indexation que l'encodeur; il consomme donc de la mémoire et du temps à cette tâche.
En décompression, LZ78 est donc forcément perdant face à LZ77.


> Car j'ai beau chercher, je ne trouve pas de solution
> pour améliorer le taux de compression de LZ77
> sans passer par le codage de l'entropie ou passer
> à LZ78 ou LZW. Crying or Very sad

Il y a certes les méthodes de parsing qui permettent d'améliorer le taux de compression au prix des performances, mais bon, il y a une limite. On ne gagne que quelques %, guère mieux. Et plus on essaye de grapiller, plus c'est cher en temps de calcul.
Au final, on a plus vite fait d'ajouter un codage d'entropie, qui sera beaucoup plus efficace et plus rapide.

Honnêtement, la seule raison valable de passer du temps sur le parsing à mon avis, c'est de rester compatible avec les anciens décodeurs.


> (...) quelle est l'astuce dans BZ qui améliore le taux de LZ77 ? Question
> Je précise que j'utilise l'encodage des expressions et des symboles
> au bit prêt, tout comme BZ, Offset sur 9 à 16bits, et longueur de 4 à 5bits.

Euh, là je sais pas, BZ ne fait pourtant rien de particulier.

On peut toutefois remarquer que le SATURN est un processeur 4 bits, alors que la plupart des ordinateurs, et notamment le PC, fonctionnent sur la base d'octets.
C'est significatif pour un compresseur : cela signifie que l'unité de base est le "nibble" (4 bits) et non l'octet (8 bits).
Alors ensuite, cela dépend des données compressées; s'il s'agit de texte, l'octet sera plus performant; mais s'il s'agit de programmes pour calculatrice HP48, alors le nibble sera plus performant. C'est selon...


> Edit : C'est quoi un comparateur incrémental ?

Mmmh, là c'est de l'optimisation pure,
il faut avoir la "vision" d'un processeur Saturn, et je ne saurais prétendre que cela reste utile sur PC.

Bien que l'unité de base soit le nibble de 4 bits, les registres Saturn font 64 bits tout de même, soit 16 nibbles. C'est utile pour les comparaisons, car cela permet de faire des tests sur 16 symboles d'un coup. C'est relativement rare comme possibilité.

BZ utilise cette méthode, et travaille donc sur des comparaisons 16 par 16.
Pour ma part, j'ai choisi une méthode de comptage plus complexe, mais finalement payante. L'idée est d'initialiser la taille de la fenêtre de comparaison en utilisant les résultats précédents. Je commence donc toujours mes tests avec "meilleur résultat précédent + 1" comme largeur de fenêtre. Ensuite je progresse moins vite que BZ, mais c'est souvent inutile de taper directement 16 symboles, car généralement, on fera 1 2 ou 3 symboles de mieux. Au final, c'est payant puisqu'on gagne environ 5% de performances rien que sur cette technique.

Voilà, tout ceci est lié à la taille relativement large des registres de travail du processeur Saturn. Je suppose qu'on pourrait utiliser la même méthode avec des registres MMX ou SSE sur PC, puisqu'ils sont également très larges (jusqu'à 128 bits si j'ai bien suivi).

Yann
Admin

Number of posts : 174
Registration date : 2008-05-01

http://phantasie.tonempire.net

Back to top Go down

Re: BZ2 compression software - Standard format

Post  stfox on Fri 9 Jan - 17:00

Merci, venant de quelqu'un qui maitrise comme toi le sujet,
ca m'encourage beaucoup. Smile

Mais pour l'instant, et depuis Lundi, je n'ai plus rien codé,
car en fait je ne sais pas vers quel algo m'orienter, et
donc j'essaye d'avoir une vision d'ensemble, mais c'est très compliqué
car il y a beaucoup de techniques d'optimisation pour chaque
type d'algo ... Shocked

Je voudrai faire tout de suite le bon choix dans l'algo LZ de base,
pour ne pas devoir tout recommenser à cause d'un mauvais choix de base.

Donc pour l'instant j'ai une idée générale des choses, mais j'en suis
pas encore à l'implémentation, donc t'as largement le temps
de nous pondre entre temps un TNT2 avant que je te pose des questions
plus pointues Razz

Celà dit, rien que pour le plaisir d'avoir un compresseur haute performance
sur ma petite hp48, je te retiens pas d'avancer un peu plus vite
si tu insiste lol!

Je vais réfléchir à tout ce que tu m'as écrit, car si toi il te faut
quleques minutes pour me répondre, moi il me faut plutôt la journée
le temps de décripter Very Happy

stfox

Number of posts : 13
Registration date : 2009-01-07

Back to top Go down

Re: BZ2 compression software - Standard format

Post  Yann on Fri 9 Jan - 21:34

J'avais prévu de le faire un jour, alors c'est juste en pressant le rythme, que je viens de décompiler TNT; et c'est une grosse surprise. Car la documentation a le don de suggérer une fausse piste, en employant un ton volontairement restrictif :

TNT-Packer is an LZ77 class compressor. It uses a modified LZSS algorithm and a
modified Elias Gamma Code to encod matches and litteral sequences. (...)
Use of any part of the TNT-Packer library code is not allowed for any purpose, except,
of course, when used directly from the TNT-Packer library. You may not reproduce
or modify any part of the TNT-Packer library code without prior written permission from the author.

On a donc l'impression d'un code "original", d'un algorithme "genuine", qui justifie une telle restriction d'emploi par l'auteur, pas d'une vulgaire copie d'un code public. Et pourtant, c'est bien à cette seconde définition qu'appartient TNT : ce n'est ni plus ni moins qu'une variante de BZ, avec une seule modification, le passage d'un codage des longueurs de match d'un trigramme peu optimisé de BZ à un code gamma d'Elias plus efficace.
A la décompilation, c'est une véritable parodie : les instructions sont rigoureusement les mêmes, mêmes registres, mêmes allocations, mêmes inefficacités. Tout est strictement pareil.

Alors, je dois dire que je suis sensiblement déçu. Pas tellement que TNT soit basé sur BZ, mais plutôt que l'auteur ait tenté de le masquer, en prétendant avoir produit un code original, alors qu'il est à 95% le travail de Mika Heiskannen. C'est pour le moins assez peu éthique.

Si on veut voir les choses d'un côté positif, cela prouve d'une part que l'Elias Gamma Code est efficace. D'autres part, on en déduit également que créer un TNT2 serait assez simple. Il suffirait de reprendre BZ2, de changer la partie qui code le matchlength, et c'est parti.

Pourquoi pas. Je suis un peu gêné par le terme "TNT", maintenant que j'ai appris que le code provenait en fait de BZ. Je réfléchirai donc à comment faire plus tard, si l'envie me prend...

Yann
Admin

Number of posts : 174
Registration date : 2008-05-01

http://phantasie.tonempire.net

Back to top Go down

Re: BZ2 compression software - Standard format

Post  stfox on Mon 12 Jan - 11:12

Waw !!! Quelle nouvelle ! Je suis très franchement décus Mad
D'abord par le fait que l'auteur se soit acaparé le travail de quelqu'un
d'autre, et aussi parce qu'il y'aura moins à apprendre de ce programme Crying or Very sad
Quelque part, on pouvait peut-être s'en douter, car les performances
tant au niveau du taux de compression, comme de la vitesse se suivent
quand même de très prêt. Mais tu viens de montrer que ceci explique celà Laughing

En tout cas, je vois que tu ne trenne pas ! Impressionant Razz

La bonne nouvelle dans tout ca, c'est que tu devrais très facilement
appliquer les optimisations de BZ sur TNT (ou l'inverse), ce qui m'interesse
fortement en tant qu'utilisateur dans un premier temps Smile

stfox

Number of posts : 13
Registration date : 2009-01-07

Back to top Go down

Re: BZ2 compression software - Standard format

Post  Sponsored content Today at 6:00


Sponsored content


Back to top Go down

View previous topic View next topic Back to top

- Similar topics

 
Permissions in this forum:
You cannot reply to topics in this forum