+HCU papers

Little essay about the various methods and viewpoints of crunching
~ version June 1998 ~
by Joa

---

Courtesy of fravia's page of reverse engineering

---

Here is the second part of Joa's essay.
See also the first part (Introduction)

Joa's work is extremely clear and will guide and help you to understand these matters, that for obvious reasons no real reverser should ever underestimate. My advice: read, re-read and then -once you have understood the basis- search the web and deepen (and then contribute :-)

Little essay about the various methods and viewpoints of crunching.

Part II: Propability and Crunching (Huffman isn't the only way)



By Joa Koester (JoKo2000@HotMail.Com) 
This essay is free to be copied and read and spread as long as
you are decent enough to leave my name in it. 
If you have corrections, comments, better examples than the ones used 
in this essay, etc. - drop me a line.


OK, let's dive into the world of crunchers and munchers...

In the Intro i told you that crunching is a process of reducing
the SPACE data needs to be stored, but not the MEANING (the
informations transmitted in the symbols).
The meter 'Entropy' is used here like in the physics. The more
entropy a symbol has, the LESS information is transmitted thru it.
Less information compared to the whole of all symbols, that is.
This means of course there is a lot of redundancy in it - meaning
a big 'crunch me, crunch me' for us. So we should concentrate
on the symbols that have a very high entropy. How we calculate
an entropy for our means depends on the data we want to crunch
and with which algorithm we want to crunch it.
I also told you that a certain student called Huffman once came
up with an algorithm to compress data. His idea is based on the
fact that in data (escpecially speech) some symbols happen 
to be more often than others. Here one overstated example:

aaaaaaaaaabbbbbcccdd

What we have here is a algorithm based on propability. That means
that some symbols are not transmitted in the way they used to be,
because the algorithm will create new symbols in respect to the
propabilities of the symbols. Some of these new symbols will be
shorter. And those lesser apperaring symbols will be transformed
into longer symbols:

Before:

a = 61h = %0110 0001
b = 62h = %0110 0010
c = 63h = %0110 0011
d = 64h = %0110 0100

and 

after:

????

How do we compute such a new symbol table? OK, before we explore
this algorithm let me change the data from ASCII to the lower
nibble. That should be enough to explain the algorithm:

Before:

a = %0001
b = %0010
c = %0011
d = %0100

and we have the propability:

a = 10
b =  5
c =  3 
d =  2
   ===
    20 zero != NULL) )
         knot = knot->zero
      else 
         if (knot->one != NULL) ) knot = knot->one

      if (knot.one == NULL) //is enough. knot.zero is NULL, too
         //symbol found. great. To the output with it
         symbol = knot.symbol
      end if
    end while   
    Do_Outpur_Char(symbol);
end while

Done. 


         
Hm, i have another little problem...

What is it, Watson?


I did as you told me. Took a table of 256 longs, counted the 256 chars,
sorted them and let the computer calculate an optimized Huffman-tree.
But all i got was a tree with all leaves having a length of 8 - all chars
are encoded with 8 bits and there is no crunching in that. What happened?

Ah, Dr. Watson,
you did not remember my sentence about Entropy. This file you examined
had all bytes nearly equally spread all over the length of the file.
So -statisticalwise- the file is equalized. No surprises here. With 
a Huffman-tree, which considers the whole file you won't get any 
crunching here, i fear.

But what do i do now?

Well, there are three scenarios that will satisfy your desire:
- We use a different algorithm
- We use a brutal tree
- We use an adapting technique

??? Tell me about the brutal tree.

Ok, i got this one from the 1001 Packer from the C64 (Anyone ringing a 
bell? 1001 Crew? No? Where are the old days gone to...)
They used a tree i just can label 'brutal tree'. Here's the idea:
When we have the case that we have data that is so equal that no
Huffman-tree will help us, we help us ourself. We take all the
Bytecounters and sort them. Then we create a table of the 256 chars
ordered by the sorted table, so that the still most frequent
chars appear on the top. Now we have the 256 possible bytes sorted.
So far so good.
Lets think about a byte. How do we read a byte? Isn't it:

#33 = $21 = %0010 0001  ?

What, if we we would change our view of the binary to a 2 + 6:

#33 = $21 = %00 100001

Our 256 chars would now be represented as 4 (00, 01, 10, 11) blocks
of 6 bits. What if we now 'huffman' these first two bits to:

0
10
110
111

So that we would have %0 100001 instead of %00 100001. Every byte that
is in the first 64Byteblock is coded with 7 bits, while the others
are coded either with 8 or with 9 bits. We can only hope that there
are enough bytes in the file to outweigh the two 9bit-chars. But it is
amazing how this little trick works. And the speed. It's so easy to
implement it and it is so fast. Even on the C64 it took only fractals of
a second to decode a programm as big as the main memory area (other 
packers took several seconds for the same size).


Wow, cool. But what about your different algorithms 
and this 'adapting technique' ?


Well, this is another story and will be told in the next chapter...




I hope you enjoyed this chapter. 
There will be more - i promise.
Just have a little patience.

Greetings from a programmer

Joa

---

In the meantime, after having read Joa's work above, you may enjoy a look at a huffer and a unhuffer, both written in C some time a go, and donated to the world, by Shaun Case... once you are done studying it, may be you'll want to have a look also at sixpack another more advanced (adaptive Huffman encoding) compresser, written in C as well, by Philip Gage, for a data compression competition some time ago... since this code includes SIX different algorhitms, I believe it could be useful for readers as 'passage' to the next part of Joa's essay (if Joa doesn't agree with me I'll kill these links of course).

---

homepage links anonymity +ORC students' essays academy database
tools counter measures cocktails antismut bots wars search_forms mail_fravia
Is reverse engineering legal?