TNT2 compression software - High compression ratio

After looking into the code of TNT, and discovering that it was a rip of BZ, it became quite straightforward to create a fully TNT-compatible compressor, starting from the BZ2 "core".
A simple modification is done to meet TNT format, a different encoding of "length" field, named Elias-Gamma-Code, with positive compression effect but more computation needed.
Whereas this software should be called TNT2, or BZ2 with Elias Gamma Code, is up to debate. I decided to keep the TNT2 name to underline the full compatibility of the new version with its older sibling.

Current version : TNT2 v1.1 "final" for HP48, 49 & 50

Benchmark Results :

HP49G Comparison	TNT1.11	TNT2		BZ2.max
Memory Req.	27KB(*)	9KB		9KB
Compression Ratio	2.25	+3.1%		-0.5%
Compression Speed	0.96 KB/s	+25%		+50%
Decoding Speed	11.7 KB/s	+45%		+130%

(*) TNT1 can decrease its memory usage to 7KB, but compression speed drops sharply

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

Older versions :
TNT2 v1.0 "final" for HP48, 49 & 50
TNT2 Bêta2 for HP48, 49 & 50
TNT2 Bêta1 for HP48, 49 & 50

Bravo bravo bravo

Ca me plait tout ca

Mais au vu de ce que tu annonce comme perfs, tu as pris comme base TNT1 alors ?
Et non pas BZ1 ?
Pourtant ca avait l'air plus simple de partir de BZ2 vu qu'il y a plus
de différence BZ1->BZ2 que BZ1->TNT1

Je suis parti de BZ2, et plus précisément de BZ2.max.
Pour plus de vitesse, je pourrais utiliser BZ2.normal, ou même BZ2.speed, au prix du taux de compression.

La seule modification concerne le codage des matchlength, qui passe en Elias Gamma Code. Pour le décodeur, c'est fondamental, d'où les performances très différentes par rapport à UBZ2.
En revanche, pour l'encodeur, le temps de calcul est en fait avalé ailleurs. Le codage Elias a un effet secondaire, qui est plus important que le codage lui-même : le "Minimum Match Length" passe de 6 symboles à 4 symboles.
C'est (très) bon pour le taux de compression, mais je perds donc l'avantage de mon optimisation "hash dispersant" introduite dans BZ2. Cela entraine des tests supplémentaires et des "faux positifs" qui allongent les temps de calcul.

Le traitement du cas particulier "4 symboles" nécessitant un bout de code supplémentaire dédié, je me suis contenté de démarrer à 5 symboles, comme ça il n'y avait aucune modification. Mon taux de compression "de base" est donc moins bon que TNT1, mais on le rattrape avec le parsing plus évolué de BZ2.max.
Il y a un effet secondaire agréable à cette stratégie : les archives sont plus rapides à décoder (environ +10%), car les segments sont plus longs.

Pour l'instant, j'en suis resté là. Cela permet aussi d'illustrer que TNT2 est une variante à peine retouchée de BZ2.

Pour plus de compression, je pourrais ajouter le traitement du cas particulier des "4 symboles", au prix de la vitesse de compression et surtout de décompression.
L'idée pour l'instant, est que je pourrais améliorer la vitesse de BZ2, et rendre instantanément cette amélioration disponible sur TNT2.

En l'état, TNT2 fonctionne déjà correctement. Les "tortures tests" réagissent bien. Si tu veux une pré-version pour voir le résultat sur ta calculatrice, il y a moyen.

Oui, ca m'interesse bien d'être un bêta testeur lol
Je te donne mon mail si tu le publis pas sur ton site : <EDIT : effacé>

Ca montre en tout cas que le 'hash dispersant' est vraiment efficace !!!
D'ailleurs, quand tu dis 'hash dispersant' tu veux parler d'une fonction de Hash qui rend
la table de hashage plus uniforme ? (Oui je sais, j'utilise des termes de novice )

Et pourquoi le fait que le nombre de symboles diminue t'empèche d'utiliser le 'hash dispersant' ?

Dommage que toutes les optimisations ne sont pas forcément compatibles entre elles

> quand tu dis 'hash dispersant' tu veux parler d'une fonction de Hash qui rend
> la table de hashage plus uniforme ?

Oui, c'est tout à fait ça

> Et pourquoi le fait que le nombre de symboles diminue t'empèche d'utiliser le
> 'hash dispersant' ?

C'est mathématique, avec moins de matière, il y a moins de possibilité de distinguer les différences. Par exemple, avec un Hash sur 4 symboles significatifs, je ne peux plus distinguer les 2 séquences suivantes : "ABCDEF" "ABCD12".
Bien sûr, ces différences seront repérées au comptage, mais c'est autant de temps de perdu à faire une comparaison de chaine inutile.

> Je te donne mon mail si tu le publis pas sur ton site :
Parfait, je t'envoie ça ce soir par email.
Je me suis permis d'éditer ton message pour limiter l'impact des robots qui ramassent automatiquement les adresses email dans les forums pour leur envoyer du "pourriel". J'ai bien reçu ton adresse

Bonjour

Il y a 2 "manques" à l'actuelle version "alpha 2".
Tout d'abord, les archives créées par TNT2 peuvent être décodées par UTNT2, ou par UTNT1, mais elles ne peuvent pas être décodées par TNT2, car je n'ai pas encore intégré la totalité du décodeur. Ce sera corrigé dans la prochaine version.

Ensuite, ils ne peuvent pas non plus être décodés par la librairie TNT1, car celle-ci gère la notion de "checksum d'entête" qui est curieusement absente du décodeur UTNT1. En conséquence, TNT1 ne reconnait pas les chaînes créées par TNT2 et les compresse de nouveau.
Trouver la formule du Checksum était assez ardu, car la librairie TNT1 comporte de nombreuses "astuces de programmation" dont le seul but est de casser le fonctionnement normal des Librairies Splitters et des Codes Disassembler (comme Jazz) afin d'empêcher la lecture du code. Il faut donc de sacré connaissances en SysRPL sur les Librairies, ainsi qu'en code assembleur ASM, pour pouvoir les comprendre, puis les "débrouiller" à la main.
On peut dire que l'auteur a fait le nécessaire pour cacher le fonctionnement de son programme (on sait maintenant pourquoi). Mais bon, au final, j'ai pu retrouver le code du checksum et l'émuler sera assez simple.

La gestion du checksum (création et contrôle) sera donc présente dans la prochaine version, qui, à priori, devrait être disponible ce soir.

Salut,

oui, effectivement, en voulant décompiler l'autre jour, je me suis apperçu également
de ces 'anomalies' dans la librairie et les codes asm, avec des appel en début
de code pour modifier directement PC notament, mais j'ai pas était plus loin
J'ai pu m'en sortir avec des XLIB RCL

Même si l'auteur est un usurpateur, il s'y connait bien quand même lol

Par contre, je ne savais pas que UTNT1 et la librairie n'était pas les mêmes

Le checksum est fait en ASM, ou simplement par un appel système ?

> Le checksum est fait en ASM, ou simplement par un appel système ?

Le Checksum est fait en ASM par un appel système
Un GOSBVL vers une routine pré-intégrée à la ROM.
Mais ensuite, le résultat est modifié par une formule; c'est cette formule qu'il fallait décrypter.

> Je me suis apperçu également
> de ces 'anomalies' dans la librairie et les codes asm, avec des appel en début
> de code pour modifier directement PC notament

C'est exactement ça. La manipulation directe de PC permet de cacher un code SysRPL en l'encapsulant comme s'il s'agissait d'ASM, ce qui plante bien évidemment le désassembleur. Ça n'a aucune autre fonction que de planter la lecture du code.
Cette astuce est employée absolument partout, ce qui rend l'exercice assez laborieux.


> Par contre, je ne savais pas que UTNT1 et la librairie n'était pas les mêmes

Effectivement; je suppose que le code de UTNT1 a été à l'origine "extrait" de l'objet SELF, créé par la librairie TNT. Le programme de décompression est alors intégré dans l'objet résultat.
L'auteur a donc pensé qu'en supprimant la vérification du CheckSum, il rendait l'objet SELF plus petit.
Cela permet également de gagner en performance, puisqu'on saute l'étape "vérification".

En contrepartie, cela signifie que UTNT n'est pas du tout protégé. Il est capable de tenter de décompresser n'importe quoi, avec les conséquences que l'on peut deviner sur la mémoire de la calculatrice