
;
; Comperssion engine based on the Huffman algorithm - EvilRats produKtion!
;
;   Still under devlopment and test, Version 0.99 revision 5b
;
; 	Can support a dword as dictionary base like professional softwares
;	Speed up and many improvents to gain time , these routines are 100%
;       multitask. These routines doesn't require extra memory to work
;       but just need a buffer to acquire datas, for compression, if you are
;       not sure, better is to add 8ko to it, it will return the exact size
;       of the compressed datas... (You must respect a minimum of 8 Ko buffer,
;       else, it will GP Fault)
;
;	Ideal utilisation: 	Compressing text video datas got 60% and 80
;				Compressing executable file got 80-90%
;
;	Revision 5b is specially optimized for very large compression, I mean
;	for compressing more than 20 Ko, and not for small buffer, older 
;	revisions were quite efficient for small buffer (even on 512 bytes
;	buffer) but I don't release this version, I don't have commented it.
;       If you really want it, please mail: starzeros@hotmail.com
;
;       Ideal code placing: The code was originally coded for 32 bits,
;	utilization in 16 bit programs will slow down the compression
;	to +- 5 ko/sec... (value taken with Softice but it's so often 
;       instable..., anyway, the compression is eye visible in dos mode :[ )
;
;	With revision 5.b, you should compress only larger than 16 Ko to get
;	something serious. Else the dictionary (that will take 1Ko entirely)
;	will eat to much place. 
;
;	Unfortunately, this version of DSCE loose about 5 to 10% of compression
;	rate, but anyway, it's quite enough for vxing needs...
;
;	Test on standard memory compression:
;			453 Ko/sec with highest process priorities !!!
;			200 Ko/sec with normal process priorities
;			48 Ko/sec with lowest process priorities 
;
;       Arguments:          DarkCMP             ecx = number of bytes
;						esi = long pointer to addresses
;						edi = long pointer to buffer
;
;			    UnDkCMP	 	ecx = size of datas
;						esi = long pointer to the base
;						edi = long pointer to the base					
;
;		to get needed memory size, just get the dword at [esi+1],
;		then drop over it.
;
;	Routine size:	+- 125	for decompression (LZH decoding :)
;                          570  for compression 
;
; Revision 5 - Decompression routines reoptimized
;			- no more need of extra memory
;			- speed up because no three building on output
;			- not anymore eye visible
;			- we are loosing some percentages compression :(
;	        	- decompression routine size down to: about 125 bytes
;			- improvent for decompression speed, down to
;			84 microsecond for 50 Ko on a P133 !!!
;			(I didn't belived myself but true, 5000 Mega/sec ???)
;
; Revision 4 - Improved construction, Complete 32 bit structures
;		- Revised time critical procedure 1 (256 times speed up!)
;		- Revised time critical procedure 3 (for very large compression)
;		- A few bugs revised
;
; - I have to greet zombie for all his help during the writing of
;                                                            these routines -
;
;

DarkCMP:

pushad

push    edi                                     ; saving value for compressed
                                                ; size calculation 
mov	byte ptr [edi],'h'
mov	dword ptr [edi+1],ecx			; original size

push    esi                                     ; saving value for later
push	ecx

push	edi

lea     edi,[edi+5*256]                         ; set where we will put datas
push	edi					;+4 don't worry this is
						;for stimulated stack
xor     eax,eax					;just for coder's comprehension

push	edi
push	ecx					;+8

xor     eax,eax                                 ; making a 1024 bytes zero
mov     ecx,1024                                ; zone
repz	stosb

pop	ecx					;-8
pop	edi

mov	ebx,4

dictionarylookup:				; Time Critical Revision One

movzx   eax,byte ptr [esi]                      
mul     ebx                                     ; we are building a zone of
inc     dword ptr [edi+eax]                     ; number of frequencie
inc     esi                                     ; we inc table+ascii*4
                                                ; each time ascii encountered
loop    dictionarylookup

pop	esi					;-4
lea	edi,[esi+1025]
push	edi					;+4

mov     ax,-1

thendontstore:                                  ; we need to kill these that
inc     ax                                      ; happend 0 times
mov     byte ptr [edi],al                       ; so, put number in edi

mov     edx,dword ptr [esi]                     ; get frequency of al
cmp     edx,0                                   ; if zero, kill it
je      dontstoryindicotable

mov     dword ptr [edi+1],edx                   ; saving it
add     edi,5                                   ; next pos in table
cmp	ax,100h
je	dontstoryindicotable
inc	ecx
dontstoryindicotable:
add     esi,4                                   ; get next frequecy
cmp     ax,100h                                 ; build it
jne     thendontstore				; 1024 bytes eat

pop	edi					;-4

lea     esi,[edi+256*5]                         ; where we are going to
inc     esi                                     ; put the crescendo mode
mov     byte ptr [esi],cl                       ; but put number of entry 
inc     esi                                     ; there

mov     eax,5                                   ; multiply it
mul	ecx

add     esi,eax                                 ; esi will become edi 
sub     esi,5                                   ; later
mov	eax,1

mov     ebx,ecx                                 ; ecx equal number of items
mov	edx,1

xchg    esi,edi                                 ; here we go again

push	edi				; +8
push	ecx

setanynumber:

buildarbitrarydictionaryloop1:          ;This operation is time critical
                                        ;as 32 bit, dunno, I will may be
push    ecx                             ;rebuild it...
push    esi                             ;I made a fixup for large compression

checkforvalidone:

xor     eax,eax                         ; start at zero

buildarbitrarydictionaryloop:

cmp     eax,dword ptr [esi+1]           ; if eax is bigger then bybye
ja	thendontsetarbitrary

mov     eax,dword ptr [esi+1]           ; we set frequency in eax as biggest
mov     edx,esi                         ; and save his location

thendontsetarbitrary:

add	esi,5
loop    buildarbitrarydictionaryloop    ; it's the last of the series
                                        ;  
mov     esi,edx                         ; we get there
movsb                                   ; saving everyhting
movsd
mov     dword ptr [esi-4],0             ; we set before this one to zero
                                        ; nothing is biggest than zero :)
pop     esi                             
pop	ecx

dec	ebx
cmp     ebx,0                           ; this routine eat a lot of memory...
jne	buildarbitrarydictionaryloop1	; super highway 2561 bytes eaten

thengotothere:

pop	ecx
pop	esi				; -8

pop 	edx

mov     word ptr [edx+5],cx             ; we then set in the destination
lea     eax,[edx+7]                     ; number of entr

push	eax

makethree:                              ; now we make a three
                                        ; if ya don't understand, go read
                                        ; huffman compression egine
lea	edi,[esi+512*5+5]			; +2560 bytes eaten
lea	ebp,[edi+512*5+5]			; +1536 bytes eaten 

push	esi
push	ebp

mov     edx,ecx                                 ; edx contain number of 
                                                ; image in three
untilnothree:

push	esi
push	edi
push	ebp
mov	ebp,edx
sub	ebp,ecx
push	ecx
push    edx                                     ; saving these value for
                                                ; completing the loop
mov	ecx,edx

getfromthree:

mov	eax,ecx
shl	eax,2
add     ecx,eax                         ; multiply ecx by 5

mov	edx,ebp

mov     eax,edx                         ; multiply ecx by 5
shl	eax,2
add	edx,eax				; gain of speed from slow mul/div...

push	edi
push	ecx
repz	movsb				; copy the buffer :]
pop     ecx                             ; because we will operate on it
pop	edi

xor	ebp,ebp
xor     ebx,ebx                         ; resent constants

mov	dh,byte ptr [edi+edx]
add	edi,ecx

escalator:

push	edi
push	ecx

mov     eax,dword ptr [edi+1-5]         ; we get current

cmp     dh,byte ptr [edi-5]             ; and look if he's in the two last
jne     thendontsetthebit               ; object of the vertical three

inc     ebp                             ; if so, then update the current
ror     bx,1                            ; value for horizontal three 
jmp     thendontsetthebit3              ; correspondance (shift 1 + 0)

thendontsetthebit:

cmp     dh,byte ptr [edi-5-5]           ; look if before the last...
jne	thendontsetthebit2

inc	ebp
ror     bx,1                    
inc     bx                              ; shif 1 + 1
jmp	thendontsetthebit3

thendontsetthebit3:

mov     dh,byte ptr [edi-5-5]           ;

thendontsetthebit2:

mov     dl,byte ptr [edi-5-5]           ; make fusion of last two entries

add     eax,dword ptr [edi+1-5-5]       ; we get new entry

thenputloop:

cmp 	eax,dword ptr [edi-5+1]
jb	thenputhere

mov     esi,dword ptr [edi-5]           ; then refix all the table with the
mov	dword ptr [edi],esi
mov     esi,dword ptr [edi-5+1]         ; this value
mov	dword ptr [edi+1],esi

sub	edi,5
sub     ecx,5                           ; repeat it
cmp	ecx,0
jne     thenputloop                     ; for every value

thenputhere:

mov     byte ptr [edi],dl                 ; this is in case of the last
mov     dword ptr [edi+1],eax             ; change all the substructure
sub     edi,3                             ; of the three

thenitsfinish:

pop	ecx
pop	edi
                                          ; this is for the loop
sub	edi,5
sub     ecx,5                             
cmp	ecx,5
jne	escalator

mov	cx,bp
dec	cx
rol	bx,cl

mov	eax,ebp

pop     edx                                     ; restore datas
pop	ecx
pop	ebp
pop	edi
pop	esi

mov     byte ptr [ebp],al                       ; save this in the three
mov	word ptr [ebp+1],bx
add	ebp,3

dec	ecx
jnz     untilnothree                            ; we have to do this for
                                                ; each object of the three
mov	byte ptr [ebp],0

pop     ebp                                     ; restore data for 
pop     edx                                     ; encoding

pop	edi
pop	ecx
pop	esi

push ecx                                ; compressing a bit the corrspondance
push edi                                ; table make it working without extra
                                        ; memory...
movzx ecx,word ptr [edi-2]              ; 

dicotype2:				; build a mini char/three 

mov 	al,byte ptr [edx]		; correspondance table
mov 	byte ptr [edi],al 		; even as mini, for 24 char, it take
mov	al,byte ptr [ebp]		; 1024 caracters :(
mov	byte ptr [edi+1],al		; blah, nobody is perfect...
mov	ax,word ptr [ebp+1]		; now we concatenate the binary to the
mov	word ptr [edi+2],ax		; now we concatenate the binary to the

add	edx,5
add	ebp,3
add	edi,4

loop	dicotype2

pop	edx
pop ecx

mov word ptr [edi],-1                           ; this to make a stop for
                                                ; decompressing
inc edi
inc edi

mov dword ptr [edi],0                           ; set zero to there, reset
                                                ; values
inc edi

compressloop:

mov     al,byte ptr [esi]                       ; get current ascii in
                                                ; data to be compressed
push	ecx
push	edx

sub     edx,4                                   ; we have to start at zero
scannext01:
add	edx,4

cmp	byte ptr [edx],al
jne     scannext01                              ; loop until we get the value

xor	ecx,ecx
mov	cl,byte ptr [edx+1]
mov	dx,word ptr [edx+2]		; now we concatenate the binary to the
dec	cl				; buffer, [edi] = the pos of the bit of
ror	dx,cl
inc	cl

hereweloop:

mov	ah,8
sub	ah,byte ptr [edi]		; [edi-1]

cmp	ah,0
jne     thennoneedofimplementation      ;look if we completed a entire 8 byte

mov     word ptr [edi],0                ; then resent edi
inc     edi                             ; increment it
mov	ah,8

thennoneedofimplementation:

dec	ah
xchg	ah,cl
mov     al,byte ptr [edi-1]             ; we have to change edi-1
ror     al,cl                           ; and shift it

push	edx

and     edx,1                           ; we look if we 
add     eax,edx                         ; need to concatenate one bit
                                        ; of the three image
pop	edx

rol	al,cl
rol     dx,1                            ; set to next bye change

mov     byte ptr [edi-1],al             ; store it
inc	byte ptr [edi]

xchg    ah,cl                           
inc     ah                              ; restore the position

loop    hereweloop                      ; and then concatenate ecx eax

pop	edx
pop     ecx                             ; then compress all the datas

inc	esi

loop	compressloop

pop	edx

sub     edx,edi                         ; now get size of the compressed
neg     edx                             ; segment

;
; The memory is done such like:
;
; Off Size 	Description
; 0 - byte      068h - (0x68) - Recognizing mark
; 1 - word	Original size: Dword
; 5 - byte	Number of tree entry
; 7 - entries 
; entry (4bytes) : 	- 1 byte: ascii number
;			- 2 byte: number of bits
;			- 3 word: recognition 		
; ? - word 	0FFFFh - (0xFFFF) - reserved			/ bug fix :P
; ? - ?		compressed datas				/ file size
;

mov	dword ptr [esp+20h-4],edx
popad                                           ; return back
ret

db      '[DSCEi386]'			; Dark Side Compression Engine

---



