
   ßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßß
   Û	 Û    Û  Û ÛÛÛÛÛ     Compression (Part I)     ÛÛÛÛÛ Û  Û    Û	  Û
   Û	 Û    Û  Û ÛÛÛÛÛ			      ÛÛÛÛÛ Û  Û    Û	  Û
   Û	 Û    Û  Û ÛÛÛÛÛ  - The Huffman  Algorithm -  ÛÛÛÛÛ Û  Û    Û	  Û
   Û	 Û    Û  Û ÛÛÛÛÛ			      ÛÛÛÛÛ Û  Û    Û	  Û
   Û	 Û    Û  Û ÛÛÛÛÛ     by  Lord Julus / 29A     ÛÛÛÛÛ Û  Û    Û	  Û
   Û	 Û    Û  Û ÛÛÛÛÛ			      ÛÛÛÛÛ Û  Û    Û	  Û
   Û	 Û    Û  Û ÛÛÛÛÛ	 january 2000	      ÛÛÛÛÛ Û  Û    Û	  Û
   ÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜ



		  ³ /
     ÚÄÄÄÄÄÄÄÄÄÄÄÄùÄÄ
     ³	Foreword  ³
   ÄÄùÄÄÄÄÄÄÄÄÄÄÄÄÙ
   / ³

	Hello  people, and welcome to the first breath in the so talked about
 Y2K...  It looks to me that everything worked out just fine, so I decided to
 move my butt and start writing something again, after quite a while.

	You  might  consider  this  article  off-topic	a little to the virus
 writing field, but actually the things are not at all like that. The raising
 Win32	programming  and  the  little ways of stealthing the code withing the
 portable  executable  generated  a quest for inserting within the PE without
 modifying  the size of the file. This was done by many authors in many ways,
 like  overwriting  a  useless	section  or  hiding  in the slack space which
 remains  after the rounding to disk alignment. Others choosed however to use
 a  compression algorithm to shrink a portion of the file and insert into the
 remaining  space. This was done for example by JackyQwerty in the Redemption
 virus	with  his  JQCoding algorithm, or by Vecna in Babylonia. The examples
 are probably many but this was just to show you the link...

	Now,  in  the  world  there  exist  many compression algorithms, ones
 better  than  others.	From  them  a  few  raised  as of being recognized by
 everybody  as	the  best  ones. Let me tell you a few: Lev-Zimpel algorithms
 (also known as LZ), Shano-Fano algorithms, Running Length algorithm, Huffman
 algorithm.  It is very hard to say which is the best because it depends very
 much  of the raw data it works on. However, as a starter I decided to phocus
 myself on the Huffman algorithm. Unfortunately this is not quite the best of
 them  as  it  gives lower compression ratios than most of the LZ algorithms.
 But, still it is a very interesting algorithm and it deserves all attention.

	So,  in  this  article	I  will  present  the basic theory behind the
 Huffman  algorithm  with  examples, and then show you how I implemented this
 method  in  one of my latest release: Lord Julus' Huffman Compression Engine
 (LJHCE32).


		³ /
     ÚÄÄÄÄÄÄÄÄÄÄùÄÄ
     ³	Theory	³
   ÄÄùÄÄÄÄÄÄÄÄÄÄÙ
   / ³

	The  Huffman  algorithm  is  based  on the following idea: define the
 characters (which are normally coded on 8 bits) on less or more bits so that
 on  average  the  total  number of bits will be smaller. So, this algorithm,
 unlike  others,  doesn't  work on strings, but on characters and this is why
 it's results are not very good.

	The  first idea anyone would have is to encode each of the characters
 that  appear in the input buffer with the least bits possible. Let's imagine
 such an encoding:

	A = 1
	B = 0
	C = 01
	D = 10
	E = 11, etc...

	However,  this	is  a non-decodable codification, because an encoding
 like 111101 can be decoded as AAAAC, or EEC, or EAABA, etc... So, this shows
 that a special method must be used to obtain a good decodable code. Actually
 the  real  problem  does not come from the way the code looks like, but from
 the  fact that they are not unique defined from one side or another and this
 would require a mark to be set between them so that at decompression you can
 know  which  code is which. Of course using a separator between the codes is
 out of the question. Another method must be found.

	Here is the first example that comes into my mind of unique codes:

	A = 1
	B = 01
	C = 001
	D = 0001

	If you want to encode the string ABCDAABC you get:

	10100100011101001

	If  you  read  bit  by	bit  you  can remove the bits as they match a
 combination  in  the  definition  table  above...  Of course, this is just a
 simple  example  that	shows  you one of the important assets of the huffman
 codes	and that is the unique form when read from left to right. The idea is
 to compare each bit of the encrypted code and match it with all of the codes
 in  the  definition  table.  Once you matched one code you can be absolutely
 sure  that  it's  the	one,  because  they  are  not repeating in the inside
 structure.

	Of  course,  this is the very first of the problem, how to get unique
 codes. The  other part of the problem is each character which code should it
 have?

	Here  we come to the second of the huffman's algorithm ideas and that
 is the percentage of appareance. Let us consider the following string:

	AABCEDAAABCDEAABCCCCDAA

	Let's see how many times each character appears in the string:

	A - 9
	B - 3
	C - 6
	D - 3
	E - 2
    ----------
    Total - 23

	Now,  let's  transform	each appareance into a percentage relative to
 the total, following the formula:

	appareance * 100
	----------------
	     total


	A -  39.13%
	B -  13.04%
	C -  26.09%
	D -  13.04%
	E -   8.70%
    ---------------
    Total - 100.00%

	The  next  step  is  to  order	our  characters  descending  with the
 percentage of appareance. After this we will be moving on with the following
 idea: we add the last two smallest values and we obtain a composite position
 with  a  percentage  equal  to  the  sum  of  the last two. We rearrange the
 positions descending and we keep on going until we reach 100%:

 ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ>
 ÚÄÄÄÄÄÄÄÄÄÄÄÄÂÄÄÄÄÄÄÄÄÄÄÄÄÄÂÄÄÄÄÄÄÄÄÄÄÄÄÄÄÂÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÂÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿
 ³  Phase 1   ³ Phase 2     ³ Phase 3	   ³ Phase 4	   ³ Phase 5	  ³
 ÃÄÄÄÄÄÄÄÄÄÄÄÄÅÄÄÄÄÄÄÄÄÄÄÄÄÄÅÄÄÄÄÄÄÄÄÄÄÄÄÄÄÅÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÅÄÄÄÄÄÄÄÄÄÄÄÄÄÄ´
 ³ A - 39.13% ³ A  - 39.13% ³ A   - 39.13% ³ BCDE - 60.87% ³ ABCDE - 100% ³
 ³ C - 26.09% ³ C  - 26.09% ³ BDE - 34.78% ³ A	  - 39.13% ÃÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ
 ³ B - 13.04% ³ DE - 21.74% ³ C   - 26.09% ÃÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ
 ³ D - 13.04% ³ B  - 13.04% ÃÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ
 ³ E -	8.70% ÃÄÄÄÄÄÄÄÄÄÄÄÄÄÙ
 ÀÄÄÄÄÄÄÄÄÄÄÄÄÙ

	Now,  we  are  very  advanced  inside the algorithm and we are almost
 reaching  the end. Now, all we need to do is to associate some bits with the
 characters and this is done by selecting from each phase the last two values
 and  give a 0 to the smaller one and a 1 to the highest one (not considering
 the last phase which gives 100%):

 ÚÄÄÄÄÄÄÄÄÄÄÂÄÄÄÄÄÄÄÄÄÄÂÄÄÄÄÄÄÄÄÄÄÄÂÄÄÄÄÄÄÄÄÄÄÄÄÄ¿
 ³  D -  1  ³  DE - 1  ³  BDE - 1  ³  BCDE -  1  ³
 ³  E -  0  ³  B  - 0  ³  C   - 0  ³  A    -  0  ³
 ÀÄÄÄÄÄÄÄÄÄÄÁÄÄÄÄÄÄÄÄÄÄÁÄÄÄÄÄÄÄÄÄÄÄÁÄÄÄÄÄÄÄÄÄÄÄÄÄÙ

	And  now,  let's  read	the  codes.  Start  from  the end towards the
 beginning  and  wherever you see the character add the specified code to it.
 We get:

		A = 0
		B = 110
		C = 10
		D = 1111
		E = 1110

	Ok, that's it!! We got our huffman codes!!

	After  all  this  is  done  we just need to take the input buffer and
 instead  of each character store it's code. Let's use the above codification
 and compress the string: AABCEDAAABCDEAABCCCCDAA

	00110101110111100011010111111100011010101010111100

	Dividing it into bytes we get:

	00110101 = 35h
	11011110 = DEh
	00110101 = 35h
	11111100 = FCh
	01101010 = 6Ah
	10101111 = AFh
	00______ = 00h

	So  we	compressed  a  23  bytes  length string into a 7 bytes length
 string. That's a 58% compression ratio.

	This  looks  a	little bit too easy, right? Yep... And I will explain
 why  in  a  second... You noticed above how we encoded each character with a
 code  and  did  you  notice  how  their size was variable? Then, how can use
 decode  the  compressed  string?  Answer:  we	*must*	save  the  characters
 definitions  into  the  compressed output buffer. This is one of the biggest
 problem...  how  to  store the definition table without affecting the output
 too  much?  Anyway, before looking into that, lets see how we can decompress
 our string:

	00110101110111100011010111111100011010101010111100

	We  start  from  left. We say: 0, is it in the definition table? Yes,
 it's  A.  We output A and delete the 0. Next bit, 0 again... Next bit: 1. Is
 it  in  the definition table? No! Read one more: 11. Is it in the definition
 table? No, read one more: 110. Is it in the definition table? Yes! It's a B,
 output the B and go on. Briefly:

	00110101110111100011010111111100011010101010111100
	AAB  C E   D   AAAB  C D   E   AAB  C C C C D	AA

	Easy decompression!! Now let's phocus a little on the data structures
 we need to use in order to implement such an algorithm.


			 ³ /
     ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄùÄÄ
     ³	Data structures  ³
   ÄÄùÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ
   / ³

	Ok, before going to the data structures themselfes, let's try and see
 what  do we really need to store. First of all we are working on an alphabet
 made  up  from maximum 256 characters. For each character we must store it's
 code (1 byte), it's percentage of appareance (which we will discuss later- 1
 double  word).  Also,	note  that  after each phase the composite codes grow
 until	the last step, where they form that total alphabet... This would make
 us  need  a  huge  matrix  of 256*256*9 = 589824 bytes!!!! Of course that is
 totaly bad!

	Let's see the structures used:

	element struc
		value dd ?
		start dd ?
	element ends
	element_size equ size element

	list struc
	     char db ?
	     next dd ?
	list ends
	list_size equ size list

	The  first  structure  has  two  definitions.  'value' represents the
 percentage  of  appeareance  and 'start' is a pointer to an element from the
 second  structure. The second structure holds the character definition and a
 pointer to the next character. To define them it goes like this:

       chars label
	I=0
	REPT 256
	   db I 	  ; character ascii code
	   dd 0 	  ; null pointer in the beginning
	   I=I+1
	ENDM

	To define the huffman codes we simply write:

	huffman element 256 dup(<0>)

	The  size  of  the  data so far is then 256*13 = 3328 bytes. A little
 decrease,  right?  Ok,  the  above  structures  will be used to generate the
 huffman tree. We need one more structure to store the actual huffman codes:

	huffman_code struc
		     code     dw ?
		     huff_len dw 0
	huffman_code ends
	huffman_size equ size huffman_code

	codes huffman_code 256 dup(<0>)

	As  you  can see the huffman code is stored on a maximum 16 bits. The
 next  value  represents  the  length  of  the code. This adds up 256*4= 1024
 bytes, making our data total = 4352.

	For the beginning we will have the data set as follows:

	huffman table	       chars table
	value:0, start:------> char:0  , next=0
	value:0, start:------> char:1  , next=0
	...
	value:0, start:------> char:255, next=0

	This  being  initialized,  we read the input buffer from beginning to
 the  end  and increment the value coresponding to each position. After doing
 so,  we transform the number of appareances into percent. This is the reason
 why  we  need	to store the length ona double word, because when calculating
 the percent we must use all decimals so we need to use the FPU:

	fild dword ptr [value]	  ; load the value
	fild dword ptr [_100]	  ; load 100
	fmul			  ; multiply
	fild dword ptr [length]   ; load length
	fdiv			  ; divide
	fstp dword ptr [value]	  ; and store the floating number

	After  doing  so, we sort the first matrix descending. Let's consider
 our example above:

	A -  39.13%
	B -  13.04%
	C -  26.09%
	D -  13.04%
	E -   8.70%


	huffman table		   chars table
	value:39.13, start:------> char:'A', next=0
	value:26.09, start:------> char:'C', next=0
	value:13.04, start:------> char:'B', next=0
	value:13.04, start:------> char:'D', next=0
	value: 8.70, start:------> char:'E', next=0

	So,  we  have  each pointer pointing the right character in the other
 matrix (beware that you don't need to rearange the second matrix as you work
 on  pointers  to  it's elements; you just arranged the pointers in the first
 matrix).

	Then, this is how the first phase looks like:

	huffman table		   chars table
	value:39.13, start:------> char:'A', next=0
	value:26.09, start:------> char:'C', next=0
	value:21.74, start:------> char:'D', next:---->char:'E',next=0
	value:13.04, start:------> char:'B', next=0

	So, we added the values of the last two elements, reordered the first
 matrix  and  made  the  'next'  pointer of the first of them pointing to the
 second  element, basically creating a chain within the second list. We go on
 with the next phase:

 huffman table		    chars table
 value:39.13, start:------> char:'A', next=0
 value:34.78, start:------> char:'D', next->char:'E',next->char:'B',next=0
 value:26.09, start:------> char:'C', next=0

	And the final phase:

 huffman table		    chars table
 value:60.87  start:------> char:'D', next->
				      char:'E', next->
						char:'B', next->
							  char:'C',next=0
 value:39.13, start:------> char:'A', next=0


	As  we	went  so  far, I hope you got the image: we have two parallel
 arrays,  one  holding	the  percentage and a pointer to the first character.
 Each character is either alone or end of list and thus it's pointer is null,
 or  is  followed  by  other characters and thus it's pointer points the next
 character.  At  every	phase you simply have to locate the last two items in
 the  first  list  and then follow the path with characters until you reach a
 null  pointer.  For the higher percentage you must set a 1 and for the lower
 one  you  must  set a 0. The setting occurs in the third matrix defined: the
 huffman_codes	matrix.  For  each  character  you  set  the specific bit and
 increase  the length. Beware that you must add the bits in the leftward part
 of the code.

	Ok,  this was the hard part: generating the huffman tree and creating
 the  codes. From here it goes very simple: just read each character from the
 input buffer and output the corresponding huffman code to the output buffer.
 This  is  done  easily  using an algorithm that concatenates variable length
 nibbles.

	Already  you  noticed,	probably, a weakness in the huffman encoding:
 the  need  to	read  the input buffer twice, once to get the percentages and
 once to actually compress.

	Also,  please  note  that  in order to be able to decompress you must
 store at the beginning of the compressed data all the informations required.
 For the beginning you should store:

	       sign	       dw 0  ; a file signature
	       ver	       dw 0  ; the version of the compressor
	       orig_size       dd 0  ; the original file size
	       comp_size       dd 0  ; the compressed file size
	       file_crc        dd 0  ; the crc of the file
	       dic_size        dw 0  ; the dictionary size

	After  this  the dictionary itself should follow. My way was to store
 each  character  followed  by	it's code length and then by the code itself.
 This provides an easy way of reading the dictionary at decompression.

	These  are the basic structure needed to create a huffman compression
 without  being forced to use big ammounts of memory. This algorithm, however
 is far less optimal then the LZ family, where first of all one pass over the
 input	buffer	is  enough and there is no need to store information like the
 dictionary.  However,	this  algorithm  is  usefull  most  of the times when
 combined with other LZ methods (like ARJ or PKZip do).

	Furthuremore  let's  take a look at some of the most important coding
 parts	of  a  huffman	compression  algorithm, as I coded them in my LJHCE32
 compression engine.


		   ³ /
     ÚÄÄÄÄÄÄÄÄÄÄÄÄÄùÄÄ
     ³	Coding it  ³
   ÄÄùÄÄÄÄÄÄÄÄÄÄÄÄÄÙ
   / ³

	While  coding a compression algorithm there are a few goals that come
 without saying:

	1.Best compression
	2.Good speed in compression
	3.Almost unnoticeable at decompression

	Also,  the  decompression  routine should be as small as possible (in
 the idea of creating a self-extractor).

	In  order  to have a good compression speed one of the most important
 part is the sorting algorithm. In my code I used a bubble sorting algorithm,
 which works pretty good.

	An  almost  unnoticeable  decompressor	is  the  one which manages to
 locate  the  codes  as  quick as possible. A good routine is needed, though,
 when	checking  the  input  data  and  matching  it  with  the  dictionary.
 Unfortunately	in my LJHCE32 I used a not so optimized algorithm and most of
 the  times  the  decompression lasts more than the compression (which is not
 normal). I will upgrade it in a newer version.

	Also,  your  routines  must take care of all errors that might occure
 and  return  the proper error code. The compression routine should notice if
 the  output  is bigger than the input and act accordingly. The decompression
 routine  should  check the integrity of the huffman table and codes and also
 check if the CRC of the decompressed data matches the initial one.

	For  the  complete  implementation  check out the source code for the
 LJHCE32 compression engine.


		    ³ /
     ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄùÄÄ
     ³	Final word  ³
   ÄÄùÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ
   / ³


	I  do  consider  that compression is a great tool that helps in virus
 writing. This is because you get more from one shot: you get the encryption,
 you get more available space, the decoding is very difficult unless you know
 exactly  the  decompression  algorithm.  I  think  everybody should consider
 writing  compression  engines	and use them in their codes. As far as I know
 there	already  exist a few available freeware libs with compression engines
 which are pretty good, like ApLib, for example.

	If  somebody  manages to write a compression engine using the huffman
 algorithm please send it over to me to... I am always eager for new stuff...

	All the Best,

				   ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿
				   ³	Lord Julus/29A (Jan.2000)   ³Û
				   ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙÛ
				     ßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßß
                                     