include "tios.h"
	xdef	_library
	xdef	complib@0000
	xdef	complib@0001
	xdef	complib@0002
	xdef	complib@0003
	xdef	complib@0004
	xdef	complib@0005
;-----------------------------------------------------------------
;structure de l'archive : 00 01 pour nb de fichiers de hufflibs
;			  XX XX nLenght 
;                         XX XX position de l'addresse de depart
;                         XX XX position du bit de depart
;                         XX XX taille du fichier extrait 
;-----------------------------------------------------------------
complib@0000:
Temp_cmem:
	movem.l		a0-a6/d1-d7,-(a7)
	move.l		#$1000,-(a7)
Test_mem:
	jsr		tios::HeapAlloc
	lea		4(a7),a7
	tst.l		d0
	beq		Out_Of_Mem
	move.w		d0,-(a7)
	jsr    		tios::HeapFree
 	lea    		2(a7),a7
Out_Of_Mem:
	movem.l		(a7)+,a0-a6/d1-d7
	rts
;-----------------------------------------------------------------
complib@0001:
Temp_emem:
	movem.l 	a0-a6/d1-d7,-(a7)
 	move.l		#1140,-(a7)
	bra		Test_mem

;-----------------------------------------------------------------
complib@0002:
Eval_cmem:
	movem.l		a0-a6/d1-d7,-(a7)
	move.w		d0,Lenght
	move.l		a0,origin
	bsr		Temp_cmem
	tst.l		d0
	beq		Out_Of_Mem
	bsr		Evaluation_frequences
	move.w		d4,d7
	move.w		arbre_h,-(a7)
	jsr    		tios::HeapFree
 	lea    		2(a7),a7
	clr.l		d0
	move.w		d7,d0
	movem.l		(a7)+,a0-a6/d1-d7
	rts

;-----------------------------------------------------------------
complib@0003:
Eval_emem:
	move.w		8(a0),d0
	rts
;-----------------------------------------------------------------
complib@0004:
Compress:
	movem.l		a0-a6/d1-d7,-(a7)
	move.w		d0,Lenght
	move.l		a0,origin
	move.l		a1,cible
	bsr		Temp_cmem
	tst.l		d0
	beq		Out_Of_Mem
	bsr		Evaluation_frequences
	bsr		Compression
	move.w		#1,d0
	movem.l		(a7)+,a0-a6/d1-d7
	rts
;-----------------------------------------------------------------
complib@0005:
Extract:
	movem.l		a0-a6/d1-d7,-(a7)	
	bsr		Extraction
	movem.l		(a7)+,a0-a6/d1-d7
	rts
;-----------------------------------------------------------------
Evaluation_frequences:
	move.l		#$200,-(a7)
	jsr		tios::HeapAlloc
	lea		4(a7),a7
	move.w		d0,tab_handle
	tios::DEREF	 d0,a1
	bsr		Clr_Handle
	move.l		a1,tab_addr
	move.l		#$200,-(a7)
	jsr		tios::HeapAlloc
	lea		4(a7),a7
	move.w		d0,tab_handle2
	tios::DEREF	 d0,a1
	bsr		Clr_Handle
	move.l		a1,tab_addr2
	move.l		tab_addr,a2
	move.l		origin,a0
	move.w		Lenght,d2
	subq.w		#1,d2
	clr.l		d7
Boucle_de_construction_Tab_de_freq:
	clr.w		d0
	move.b		0(a0,d2.w),d0
	lsl.w		#1,d0
	tst.w		0(a1,d0.w)
	bne		Non_vide
	addq.w		#1,d7
Non_vide:
	add.w		#1,0(a1,d0.w)
	add.w		#1,0(a2,d0.w)
	dbra		d2,Boucle_de_construction_Tab_de_freq
	move.w		d7,nLenght	
	move.l		#$400,-(a7)
	jsr		tios::HeapAlloc
	lea		4(a7),a7
	move.w		d0,freq_h
	tios::DEREF	d0,a1
	move.l		a1,freq_a
	move.l		tab_addr2,a0
	clr.w		d1
Creation_freq:
	move.w		#$FFFF,d2		
	clr.w		d3
	clr.w		d0
Recherche_Freq:
	move.w		0(a0,d0.w),d4
	tst.w		d4
	beq		Plus_petite
	cmp.w		d4,d2
	bls		Plus_petite
	move.w		d0,d3		
	move.w		d4,d2
Plus_petite:
	addq.w		#2,d0
	cmp.w		#$200,d0
	bne		Recherche_Freq
	tst.w		0(a0,d3.w)
	beq		Fin_de_Creation_Freq
	clr.b		(a1)+
	move.w		d3,d4
	lsr.w		#1,d4
	move.b		d4,(a1)+		
	move.w		0(a0,d3.w),(a1)+
	clr.w		0(a0,d3.w)
	bra		Creation_freq
Fin_de_Creation_Freq:
	move.w  	tab_handle2(PC),-(a7)
 	jsr    		tios::HeapFree
 	lea    		2(a7),a7
	move.l		#$3FC,-(a7)
	jsr		tios::HeapAlloc
	lea		4(a7),a7
	move.w		d0,noeuds_h
	tios::DEREF	d0,a1
	move.l		a1,noeuds_a
	clr.l		d6				;d6 = arbre en construction
	move.w		nLenght,d7			;d7 = nombre de branches -1
	move.l		freq_a,a0
	subq.w		#1,d7
Creation_des_noeuds:
	move.w		(a0)+,(a1)+
	move.w		(a0)+,d0
	move.w		(a0),(a1)+
	add.w		2(a0),d0
	subq.b		#1,d7
	clr.b		d2
	clr.w		d3
Rang_Boucle:
	cmp.w		6(a0,d3.w),d0			
	bls		Bien_ranger
	move.l		4(a0,d3.w),0(a0,d3.w)
	addq.b		#1,d2
	addq.w		#4,d3
	cmp.b		d2,d7			; .B ?
	bhi		Rang_Boucle
Bien_ranger:
	move.w		d6,0(a0,d3.w)
	bset.w		#15,0(a0,d3.w)
	move.w		d0,2(a0,d3.w)
	add.w		#1,d6		
	cmp.w		#1,d7
	bne		Creation_des_noeuds		; d6 = nb de noeuds
	move.w		(a0)+,(a1)+
	move.w		2(a0),(a1)+
	move.w		freq_h(PC),-(a7)
	jsr		tios::HeapFree
	lea		2(a7),a7
	move.l		#$3FE,-(a7)
	jsr		tios::HeapAlloc
	lea		4(a7),a7
	move.w		d0,arbre_h
	tios::DEREF	d0,a1
	move.l		a1,arbre_a
	move.l		noeuds_a,a0			
	move.l		a1,a4
	move.w		nLenght,d7
	lsl.w		#2,d7
	subq.w		#2,d7
	add.w		d7,a4
	sub.w		#6,d7
	move.w		d7,d0
	bra		Debut_Arbre
Creation_Arbre:
	move.w		0(a0,d0.w),d0
	bclr.w		#15,d0
	beq		Fin_de_branche
	lsl.w		#2,d0
Debut_Arbre:
	move.w		d0,d1
	addq.w		#2,d1
	move.l		a1,-(a7)
	move.w		d1,-(a7)
	adda.l		#2,a1
	bra		Creation_Arbre
Fin_de_branche:
	move.w		d0,(a1)+
	cmp.l		a1,a4
	ble		Fin_de_Creation_Arbre
	move.w		(a7)+,d0
	move.l		(a7)+,a2
	move.l		arbre_a,d2
	move.l		a1,d1
	sub.l		d2,d1
	bset.w		#15,d1
	move.w		d1,0(a2)
	bra		Creation_Arbre
Fin_de_Creation_Arbre:
	move.w  	noeuds_h(PC),-(a7)
 	jsr    		tios::HeapFree
 	lea    		2(a7),a7
	move.l		arbre_a,a2
	move.w		d7,d6
	addq.w		#6,d6
	clr.l		d4
	move.l		tab_addr,a0
	move.w		#$FF,d0
Freq_non_nulle:
	move.w		d0,d1
	lsl.w		#1,d1
	tst.w		0(a0,d1.w)
	beq		Freq_vide
	move.w		d6,d2
	clr.l		d7
Trouve_debut_arbre:
	subq.w		#2,d2
	cmp.w		0(a2,d2.w),d0
	bne		Trouve_debut_arbre
Cherche_branche:
	move.w		d2,d3
	subq.w		#2,d3
	btst.b		#7,0(a2,d3.w)
	bne		Bonne_branche
	clr.w		d3
	bset.w		#15,d2
Loop_cherche_branche:
	cmp.w		0(a2,d3.w),d2				
	bne		Pas_branche
Bonne_branche:
	add.b		#1,d7
	tst.w		d3
	beq		Trouver
	move.w		d3,d2
	bra		Cherche_branche
Pas_branche:
	addq.w		#2,d3
	bra		Loop_cherche_branche				
Trouver:
	clr.l		d5
	move.w		0(a0,d1.w),d5
	mulu.l		d5,d7
	add.l		d7,d4
Freq_vide:
	dbra		d0,Freq_non_nulle
	move.w  	tab_handle(PC),-(a7)
 	jsr    		tios::HeapFree
 	lea    		2(a7),a7
	clr.l		d7
	move.w		nLenght,d7
	lsl.w		#1,d7
	subq.w		#1,d7
	add.l		d7,d4
	move.b		d4,d7
	and.b		#%00000111,d7
	lsr.l		#3,d4
	add.w		#10,d4
	clr.l		d0
	move.w		nLenght,d0
	add.l		d0,d4
	tst.b		d7
	beq		Pas_dexces            ;d4 = longueur total du texte compresse
	addq.l		#1,d4
	subq.b		#1,d7
	rts
Pas_dexces:
	move.b		#7,d7
	rts

Compression:	
	move.l		#$600,-(a7)
	jsr		tios::HeapAlloc
	lea		4(a7),a7
	move.w		d0,tableH
	tios::DEREF	d0,a4
	move.l		a4,a5
	move.l		a5,a6
	adda.l		#$200,a6
	move.w		#$3F,d0
Clear_table:
	clr.l		(a5)+
	dbra		d0,Clear_table
	move.l		cible,a1
	move.l		a1,a3
	move.w		#1,(a3)+
	clr.w		d0
	move.w		nLenght,d0
	move.w		d0,(a3)+
	move.w		d0,d1
	subq.w		#1,d0
	lsr.w		#2,d0
	addq.w		#1,d0
	add.w		d1,d0
	add.w		#9,d0
	move.w		d0,(a3)+
	lsl.w		#1,d1
	subq.w		#1,d1
	and.b		#%111,d1
	clr.b		(a3)+
	move.b		d1,(a3)+
	clr.l		d5
	move.w		Lenght,d5
	move.w		d5,(a3)+		
	add.l		d4,a1
	suba.l		#1,a1
	move.l		origin,a0
	move.l		arbre_a,a2
	add.l		d5,a0
	subq.w		#1,d5
	clr.w		d0
Compression_des_donnees:
	move.b		-(a0),d0
	tst.b		0(a4,d0.w)
	beq		Nouvel_octet
	move.w		d0,d1
	lsl.w		#2,d1
	clr.w		d4
	move.b		0(a4,d0.w),d4
	move.l		0(a6,d1.w),a3
	move.b		0(a5,d0.w),d1
Copy_octet:
	btst.b		d1,(a3)
	beq		Copy_octet_nul
	bset.b		d7,(a1)
	bra		Fin_Copy_octet
Copy_octet_nul:
	bclr.b		d7,(a1)
Fin_Copy_octet:
	tst.b		d7
	bne		No_Shift_source
	bset.b		#3,d7
	suba.l		#1,a1
No_Shift_source:
	tst.b		d1
	bne		No_Shift_origine
	bset.b		#3,d1
	suba.l		#1,a3
No_Shift_origine:
	subq.b		#1,d7
	subq.b		#1,d1
	dbra		d4,Copy_octet
	bra		Fin_de_compression
Nouvel_octet:
	clr.b		d4
	move.w		d0,d1
	lsl.w		#2,d1
	move.l		a1,0(a6,d1.w)
	move.b		d7,0(a5,d0.w)
	move.w		d6,d2
Trouve_debut_compression:
	subq.w		#2,d2
	cmp.w		0(a2,d2.w),d0
	bne		Trouve_debut_compression
Cherche_droit:
	move.w		d2,d3
	subq.w		#2,d3
	btst.b		#7,0(a2,d3.w)
	beq		Cherche_gauche
	bclr.b		d7,(a1)
	bra		Trouver_origine
Cherche_gauche:
	clr.w		d3
	bset.w		#15,d2
Loop_cherche_gauche:
	cmp.w		0(a2,d3.w),d2
	bne		Pas_gauche
	bset.b		d7,(a1)
Trouver_origine:
	tst.b		d7
	bne		No_Shift
	bset.b		#3,d7
	suba.l		#1,a1
No_Shift:
	subq.b		#1,d7
	tst.w		d3
	beq		Fin_arbre
	addq.b		#1,d4
	move.w		d3,d2
	bra		Cherche_droit
Pas_gauche:
	addq.w		#2,d3
	bra		Loop_cherche_gauche	
Fin_arbre:
	move.b		d4,0(a4,d0.w)
Fin_de_compression:
	dbra		d5,Compression_des_donnees
	clr.l		d1
	move.w		nLenght,d1
	lsl.w		#2,d1
	subq.w		#4,d1
	move.l		cible,a0
	clr.l		d2
	move.w		nLenght,d2
	adda.l		#10,a0
	add.l		d2,a0
Compression_arbre:
	btst.b		#7,0(a2,d1.w)
	bne		T_branche
	move.b		1(a2,d1.w),-(a0)
	bclr.b		d7,(a1)
Loop_Compression_arbre:
	tst.b		d7
	bne		No_Shift_arbre
	bset.b		#3,d7
	suba.l		#1,a1
No_Shift_arbre:
	subq.b		#1,d7
	tst.w		d1
	beq		Fin_de_compression_arbre
	subq.w		#2,d1
	bra		Compression_arbre
T_branche:
	bset.b		d7,(a1)
	bra		Loop_Compression_arbre
Fin_de_compression_arbre:
	move.w  	arbre_h(PC),-(a7)
 	jsr    		 tios::HeapFree
 	lea    		 2(a7),a7
	move.w		tableH(PC),-(a7)
	jsr		tios::HeapFree
	lea		2(a7),a7
	rts
	


Extraction:
	movem.l 	a0-a6/d1-d7,-(a7)
 	move.l  	#1024,-(a7)
	jsr 		tios::HeapAlloc
	addq	 	#4,sp
	tst.l		d0
	beq		Out_Of_Mem
	movem.l 	(a7)+,a0-a6/d1-d7
 	move.w  	d0,tableH
 	tios::DEREF 	d0,a6
 	move.l  	a0,a2
	move.w  	(a2)+,d2
 	clr.w	 	d3
MultiFiles:
 	move.w  	(a2)+,d0
 	move.l  	a2,a3
 	mulu	 	#6,d2
	add.w	 	d2,a3
	mulu	 	#6,d3
 	add.w	 	d3,a2
 	move.w  	d0,d6
 	subq	 	#1,d6
 	move.l  	a3,a4
 	add.w	 	d0,a4
 	clr.l	 	d0
 	clr.l	 	d1
UncrunchTree:
 	btst.b  	d1,(a4)
 	beq 		NoBranch
 	move.w  	d0,-(a7)
 	addq	 	#2,d0
NextTreeBit:
 	addq	 	#1,d1
 	bclr	 	#3,d1
 	beq 		UncrunchTree
 	addq	 	#1,a4
 	bra 		UncrunchTree
NoBranch:
 	clr.b	 	0(a6,d0)
 	move.b  	(a3)+,1(a6,d0)
 	addq	 	#2,d0
 	tst.w	 	d6
 	beq 		TreeBuilt
 	move.w  	(a7)+,d2
 	move.w  	d0,0(a6,d2)
 	bset.b  	#7,0(a6,d2)
 	dbra	 	d6,NextTreeBit
TreeBuilt:
 	move.w  	(a2)+,d0
 	add.w	 	d0,a0
 	move.w  	(a2)+,d3
 	move.w  	(a2),d7
 	subq	 	#1,d7
UncrunchData:
 	clr.l	 	d1
CheckTree:
 	move.w  	0(a6,d1),d2
 	bclr	 	#15,d2
 	beq 		EndOfBranch
 	btst.b  	d3,(a0)
 	bne 		RightBranch
 	addq	 	#2,d1
 	bra 		NextDataBit
RightBranch:
 	move.w  	d2,d1
NextDataBit:
 	addq	 	#1,d3
 	bclr	 	#3,d3
 	beq 		CheckTree
 	addq	 	#1,a0
 	bra 		CheckTree
EndOfBranch:
 	move.b  	d2,(a1)+
Repeat:
 	dbra	 	d7,UncrunchData
 	move.w  	tableH(PC),-(a7)
 	jsr 		tios::HeapFree
 	addq	 	#2,a7
	move.w		#1,d0
 	rts


;SUBROUTINES----------------------------------------------------------

Clr_Handle: ;a1 points to handle
	move.w	#$7F,d0			
	move.l	a1,a2
Clr_Handle_Loop:
	clr.l	(a2)+
	dbra	d0,Clr_Handle_Loop
	rts


	
;DATAS----------------------------------------------------------------

Lenght		dc.w	0
origin		dc.l	0
cible		dc.l	0
tab_handle	dc.w	0
tab_addr	dc.l	0
tab_handle2	dc.w	0
tab_addr2	dc.l	0
nLenght		dc.w	0
arbre_h		dc.w	0
arbre_a		dc.l	0
freq_h		dc.w	0
freq_a		dc.l	0
noeuds_h	dc.w	0
noeuds_a	dc.l	0
tableH	   	dc.w 	0	

_library	dc.b	"complib",0
 end