>-------L-------!-------!-------!-------!-------!-------!-------!------------R

CPC_T v3.1  - N{cessite  128 kb

8 Mars 2004

   Fichiers : 	CPCT    .     :  Version disc.
		CPCT31FR.TXT  :  Vous etes en train de le lire.
		CPCT31EN.TXT  :  Message en anglais.         
		OVL22   .ROM  :  Version ROM.
	        	

Remarques pr{liminaires (le meilleur, parait-il)
________________________________________________

		La version ROM est int{gr{e avec DAMS-OVL v1.2, formant ainsi 
	la ROM OVL v2.2 (vous pouvez chercher @ comprendre).  
		Aussi, les notices de DAMS-OVL ont {t{ jointes @ ce pack, une 
	bonne chose de faite.
		Les ceusses ayantinstall{ DAMS-OVLremplaceront 
	avantageusement cette ROM par OVL22. Je rappelle quela RSX |BURN 
	autorise la programmation de la ROM dont elle est issue. C'est aussi 
	\a, Overlanders.


Utilisation
___________

|CPC_T,"nom" [,"newname"]

		Si "newname" est omis, le fichier compact{ sera enregistr{ 
	avec le meme nom que le fichier source.
		Attention, cette syntaxe rompt avec la logique de |REN !


		Le format "RSX" permet de lancer un compactage tout aussi 
	rapidement que s'il fallait passer par un menu et choisir un fichier 
	avec le curseur. Cependant, meme en version ROM, il ne s'agit pas 
	d'une RSX "transparente" :lanc{e avec param}tre, elle copie des 
	choses en BANK, en #BE00, en #BEB0, puis charge le fichier en #40...
		L'abscence d'interface ne doit pas laisser croire qu'on puisse 
	retrouver ses donn{es en m{moire (source, courrier intime sous 
	Protext, ...) @ la fin du compactage.
		Cette restriction provient de mon manque de courage @ jongler 
	avec Himem, Lowmem, ... (*). De toute fa\on, pour les gros fichiers, 
	il aurait bien fallu faire place nette. 

		CPC_T essaye plusieurs m{thodes. Cette premi}re phase n'est 
	qu'une simulation ! Les donn{es compact{es ne sont pas stock{es, car 
	rien ne garantit que tout rentrerait en m{moire (le logiciel aurait pu 
	etre un peu plus intelligent, en essayant de stocker quand meme, quite 
	@ {craser au fur @ et mesure la version la moins bien compact{e (*)).
		Bref, ceci explique pourquoi il faut encore attendre, une fois 
	la m{thode choisie, que le fichier soit r{ellement compact{ (Sauf pour 
	la m{thode #18 !).

(*) J'attends les facilit{s de gestion m{moire d'ANA pour introduire ce genre 
de jonglage.

	La phase de simulationest court-circuit{e par l'appui sur CONTROL au 
	lancement de la RSX (@ moins d'etre tr}s rapide, cela revient @ 
	valider la commande en appuyant sur CONTROL + RETURN au lieu de 
	RETURN) ou @ la fin du chargement.


		Venise sur le bateau, l'indication "Time" fournit une 
	mesure de la dur{ede d{compactage, en milli-secondes (ou kilo-NOP !).


Restrictions
____________

		Les fichiers BASIC ne sont pas encore g{r{s. S'il s'agit d'un 
	programme LM inclu dans un programme BASIC (qui se r{sume @ un simple 
	CALL), il vous faudra isoler le code, le compacter, et l'inclure de 
	nouveau dans un lanceur BASIC.  

		Pour l'instant, la taille maximale des fichiers est d{termin{e 
	par l'emplacement ram de l'AMSDOS. Par d{faut, cela donne A700-40 = 
	A6C0. Cette limite n'est plus v{rifi{e, et CPC_T essayera de charger 
	le fichier dans tous les cas, quite @ {craser l'AMSDOS.
		En attendant le compactage de flux, unebidouille simple est 
	envisageable : initialiser l'AMSDOS plus haut (on gagne #500 octets) ! 
	Je ne l'ai pas fait, de fa\on @ ce que la main soit rendue au BASIC en 
	cas de fichier non trouv{ (il serait embetant d'avoir @ relancer la 
	version disc pour une simple erreur de frappe, non ?).
		


Emplacement du fichier compact{
_______________________________

		CPC_T place le fichierde fa\on @ ce que la zone de 
	chevauchement (entre donn{es source et destination) soit maximale : 
	tout est calcul{ de fa\on @ ce que les donn{es compact{es {cras{es 
	soient celles qui ont d{j@ servi. Alors, charger le fichier ne 
	serait-ce qu'un octet plus bas compromet gravement le d{compactage. 
	 
		Mais ceci peut amener le fichier @ d{passer #A700, rendant son 
	chargement improbable. CPC_T tente alors deplacer le fichier en #40, 
	et s'arrete l@ si cela ne d{borde pas sur la zone destination.
		
		Sinon, CPC_T propose une relocation automatique, en ajoutant 
	un LDDR qui copiera le fichier compact{ @ l'endroit ad{quat 
	pr{c{demment {valu{ ({crasant forc{ment A700 : si vous souhaitez 
	r{cup{rer le lecteur actif, il faudra patcher).
		Attention, la manipulation {crasera {ventuellement le syst}me 
	(si la zone d{passe B100). Le LDDR est pr{c{d{ d'un DI, ce qui 
	garantit un d{compactage correct. Mais si le programme d{compact{ 
	utilise les vecteurs syst}me (ne serait-ce que pour changer les 
	couleurs), il y a de grandes chances de plantage. Peut-etre qu'une 
	prochaine version proposera de r{tablir le syst}me.
		La copie pourra meme atteindreC000. Dans ce cas, la pile est 
	enti}rement prise en charge : elle est momentan{ment plac{e @ un 
	endroit sur (juste apr}s la routine de d{compactage, elle-meme plac{e 
	@ la fin de la zone copi{e). Puis elle est replac{e en C000. L'adresse 
	de retour est pr{cieusement sauvegard{e (sauf si le fichier d'origine 
	avait une adresse d'ex{cution non nulle, auquel cas il n'y a pas de 
	retour mais un saut direct dans le programme). En revanche, les autres 
	mots de la pile ne sont pas conserv{s.
		De telles finesses permettent par exemple de lancer la version 
	compact{e du fichier principal de Ghost'n'goblins sans aucune 
	intervention. On remarquera simplement que le programmeur du jeu a 
	rabot{ certaines initialisations.
		Ceci dit, j'INSISTE une derni}re fois sur le fait qu'en cas de 
	"relocation" {crasant le syst}me (c'est @ dire atteignant #B100),  il
	devient fort probable que l'ex{cutable obtenu plante (par exemple en 
	changeant de mode par l'appel syst}me #BC0E). Ce n'est PAS un d{faut 
	de CPC_T !

		Vous pouvez sans probl}me charger votre fichier ailleurs (du 
	moment que cela respecte les contraintes de chevauchement susdites).
	EXCEPTION : cas du fichier "auto-relog{", car les adresses du LDDR 
	sont absolues.

		Le cas des fichiers {cran (en #C000) am}ne un petit 
	d{sagr{ment : la zone propos{e d{borde de #ffff. Th{oriquement 
	acceptable, il vous faudra en pratiquecharger le fichier compact{ en 
	RAM centrale, et recalculer l'adresse d'ex{cution.


La routine de d{compactage
__________________________

		Relogeable, elle n'utilise pas les registres secondaires, et 
	cohabite parfaitement avec le firmware et BASIC (d'ailleurs les 
	interruptions ne sont pas coup{es pour les m{thode #10 @ #13).
		La routine #18 coupe les interruptions, sans les r{tablir. La 
	plupart du temps, cela ne changera rien, car elle seront autoris{es de 
	nouveau au premier appel syst}me ou par le programme lui-meme. 


Comparaison avec CPC_T 2
________________________

		Il n'y a plus de signature dans le fichier. Seule la routine 
	de d{compactage et la faible taille du fichier t{moignent du doigt{ 
	d'Overlanders.
	
	M{thode 10 : Il s'agit du meme principe que la m{thode 00 (recherche 
	de chaine identique parmi les &100 derni}res donn{es d{compact{es), 
	mais impl{ment{ diff{rement : la distinction chaine / nouveau 
	caract}re ne se fait plus par un flag, mais par un octet L cod{ comme 
	suit :
	- Si L < 192, alors il s'agit d'une chaine de longueur L+3 (car les 
	chaines de longueurs 2 ne sont pas int{ressantes).
	- Si L >= 192, alors il y a L-191 nouveaux caract}res @ copier.

		Ce type de codage ne semble avantageux que lorsqu'on cherche 
	des chaines sur une plus grande fenetre - methode 12 ou 13.
		Mais les m{thodes 10 @ 13 reposent sur les memes routines, et 
	je n'ai pas jug{ n{cessaire de r{introduire la m{thode 00, car, meme 
	dans le cas o| elle serait plus efficace que la m{thode 10, elle se 
	verrait sans aucun doute surpass{ par une des autres m{thodes.

		Le gain en vitesse du compactage d{coule uniquement de 
	l'optimisation de la routine de recherche de chaine.

	M{thode 18 : le syst}me de codage des chaines devient "dynamique". On 
	codera une chaine courte et proche en 1 octet, tandis qu'une chaine 
	lointaine b{nificiera d'un codage sur 3 octets.
	La possibilit{ de se r{f{rer @ n'importe quel endroit depuis le d{but 
	du fichier a r{introduit des dur{es de compactage inadmissibles, 
	malgr{ une tentative d'optimisation. 


	
D{tails techniques
__________________

	La version 1 de CPC_T utilisait une m{thode "statistique" : les octets 
	les plus fr{quents sont cod{s avec moins de bits. Par exemple la suite 
	ABADAACAC aboutirait @ :
	A -> 0
	C -> 10
	B -> 110
	D -> 111
	
	Cependant le codage n'{tait pas optimal. La m{thode (codage de 
	Huffman) reviendra bientot, am{lior{e. 

	Cette version l@ utilise un principe de subsitution. On {crit une 
	s{quence de nouveaux caract}res ou une chaine d{j@ rencontr{e, d{finie 
	par (r{f{rence, longueur).
	Par exemple la chaine BARBAPAPA se verrait cod{e BAR (0,2) P (4, 3). 
	Le (0,2) signifie la copie de 2 caract}res @ partir de la position 0. 
	
	On cherche la plus longue chaine parmi lesNN derni}res donn{es 
	trait{es (quirepr{sentent des donn{es d{compress{es -donc 
	"disponibles"- @ l'{tape {quivalente de la d{compression).
	NN vaut #100, #200, #400 ou #800 suivant la variante (m{thodes 10, 11, 
	12, 13 respectivement). Bien sur, plus NN est petit, moins on a de 
	chance de trouver des chaines int{ressantes, mais en contrepartie le 
	codage de la r{f{rence prendra moins de bits.  

		Pour les m{thodes 10 @ 13 (c'{tait aussi le cas pour les 
	m{thodes 00 et 04), la routine de compactage ne trouve pas forc{ment 
	le meilleur codage possible. Illustration :

		Imaginons la s{quence AAAABCDEAAAAAA @ compacter.
	On obtient :	 			A (0,3) BCDE (0,4) (0,2)
	Pourtant, le codage optimal serait :	A (0,3) BCDEA (8,5)  
	Ce dilemme se rencontre @ chaque succession du meme chr. L'id{e serait 
	alors de choisir automatiquement le codage "CHR + chaine" dans un tel 
	cas, mais ce n'est pas si simple. Prenons la s{quence 
	AAAABCDEAAAAAABCD.
	Avec la m{thode actuelle : 		A (0,3) BCDE (0,4) (2,5)
	Notre id{e est ici inopportune :	A (0,3) BCDEA (8,5) (4,3)
		Bref, il ne semble pas y avoir de moyen de d{cider localement 
	du meilleur codage. 


		Quand une s{quence de caract}res n'est pas maximale (c@d que 
	sa longueur est inf{rieure au maximum codable), ce qui suit est 
	n{cessairement une chaine. A l'heure actuelle, on ne profite pas de 
	cette information, alors qu'on pourrait r{assigner les codes "s{quence 
	caract}res" @ une autre signification.  
		Remarquez, s'il vous plait, que la routine de d{compression 
	d'une telle variante serait en mesure de traiter les fichiers 
	compress{s avec la m{thode actuelle !


		Dans le meme ordre d'id{e (mais il s'agirait ici d'une 
	variante arbitraire et incompatible), apr}s une chaine de longueur non 
	maximale, on pourrait supposer que ce qui suit est toujours un 
	caract}re.
		Reste @ d{cider si cela serait statistiquement int{ressant.


Pourquoi un nouvel utilitaire de compactage ?
_____________________________________________

		C'est un domaine passionnant,notamment sur CPC, o| toute 
	am{lioration proc}de d'une vraie trouvaille. On ne peut gu}re 
	atteindre l'efficacit{ d'un archiveur (LHA, RAR, ...) : le cumul de 
	m{thodes ou les encodages trop sophistiqu{sse voient {cart{s, d'une 
	part pour des raisons de rapidit{, et d'autre par car chez nous le 
	d{compacteur est inclu dans le fichier. Quelprofit aurait-on @ gagner 
	1 ko sur un fichier, greff{ d'une routine de d{compactage de 2 ko ?  
	Ici r{side justement l'int{ret particulier du compactage sur CPC : 
	proposer des m{thodes toujours plus efficaces, sans sacrifier la 
	vitesse de d{compactage.
	Chaque nouvelle version de CPC_T montreen effet qu'on peut encore 
	gagner en taux de compactage de fa\on signicative, et ceci est une 
	premi}re r{ponse @ la question pos{e.
	
	D'autre part, tous les softs existants pr{sentent des d{fauts :
	- lenteur du compactage (Crown, CPC_T 2 & 3.1, Elmsoft's TC)
	- lenteur du d{compactage (Flower Cruncher, routine Richard Aplin)
	- corruption de fichier (Cheese ? CPC_T 2 ?)
	- taille du fichier limit{e 
	- ...
	CPC_T tend @ devenir irr{prochable.
	
	Pour l'instant, Cheese 2.2, Flower ou Elmsoft se r{v}lent plus 
	efficaces sur certains fichiers. Mais @ terme, CPC_T garantira le 
	meilleur r{sultat, ce qui {vitera d'avoir @ faire la tourn{e des 
	compacteurs. 

		Si les productions se font rares, il reste aussi quelques 
	crackers passionn{s @ qui CPC_T est d{di{. Quite @ mettre un jeu en 
	fichiers, autant le compacter. Mais le plus important est alors de ne 
	pas perdre en dur{e de d{compactage le temps gagn{ sur le chargement. 
	Ainsi, les d{plomblages de X-OR sont quasi parfaits, mais quel dommage 
	d'avoir @ patienter de longues secondes.
	        Aussi, j'insiste l@-dessus, la plus grande attention est 
	accord{e @ la rapidit{ de d{compactage (typiquement, 2 fois le temps 
	que prendrait un LDIR pour d{placer les donn{es).
		
	
		
A venir
_______

	
	- Nouvelles m{thodes de compressions (et am{lioration de celles 
	existantes).
	- D{tection de fichiers d{j@ compress{s par d'autres utilitaires, avec 
	possibilit{ de d{compresser avant de tester les m{thodes de CPCT. 
	- D{tection du type de fichier pour proposer des routines d{di{es 
	(affichage de windows OCP, etc...)
	- Gestion de "flux" de donn{es (@ partir d'un fichier ou de la 
	m{moire), permettant de compresser des fichiers plus gros que 128 ko.
	- Optimisation des routines de d{compactages.


		Attention ! Pour tout "report de bug", merci de pr{ciser si 
	vous utilisez un {mulateur, auquel cas votre descendance court un 
	danger.


Historique
__________


v3.1 (8/3/2004) : Sortie orificielle. Bugs introduits dans beta corrig{s ! 
v3.1 Beta 2 
v3.1 Beta 1  
	- Ajoute 1 m{thode par substitution (#18) :
	   fenetre #20 longueur 2 a 5, cod{ sur 1 octet.
	ou fenetre #400 longueur 3 a 18, cod{ sur 2 octets.
	ou pas de fenetre, longueur 4 a 35, cod{ sur 3 octets.
	ou 1 @ 32 nouveaux chrs.
	- Essaieen priorit{ de placer fichier compact{ au dessus de la zone 
	de d{compactage.
	- La taille du fichier n'est plus v{rifi{e (ce qui ne veut pas dire 
	que n'importe quelle taille est permise).
	

v3.0 : Apports mineurs par rapport @ la version Beta.
 	- Fichiers BASIC ou ASCII d{tect{s (et refus{s...).
	- Permet de r{utiliser CPC_T de suite (version disc). 
	- Correction d'un l{ger bug dans la d{claration RSX (version disc).
	- ESC annule lors du choix de la m{thode @ sauvegarder.
	- Autorise seulement touches Y/N comme r{ponse. 
	- Teste touche CONTROL (annulation simulation) {galement @ la fin du 
	chargement.
	
v3.0 Beta 1 : Utilise 4 m{thodes par substitution.
	10 : Fenetre #100, distinction chr/chaine via codage longueur.
	11 : Fenetre #200, idem
	12 : Fenetre #400, idem
	13 : Fenetre #400, idem

v2.0 (28/2/2000) : Utilise 2 m{thodes par substitution. Compression 
	horriblement lente pour la 2}me. D{compression tr}s rapide dans les 
	deux cas. Bon taux de compression.
	Interface BASIC faite @ la va-vite : la taille maximale des fichiers @ 
	compresser s'en ressent un peu !

v1.1 : Correction bug affichage texte anglais. 

v1.0 (1995?) :Utilise un "pseudo-codage" @ la Huffman. Temps de compression 
	honorable. D{compression horriblement lente (le fichier est 
	{ventuellement compress{ 2 fois de suite). Bon taux de compression.

                                ----***----  ----***----
                    