+HCU papers

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

---

Courtesy of fravia's page of reverse engineering

---

Well, Joa continues his fundamental paper on crunching, this is part III, enjoy!

05 June 98	Joa	~	crunchi1.htm	Little essay about the various methods and viewpoints of crunching	papers	~	fra_0126
10 June 98	Joa	~	crunchi2.htm	Little essay about the various methods and viewpoints of crunching II	papers	~	fra_0129
17 June 98	Joa	~	crunchi3.htm	Little essay about the various methods and viewpoints of crunching III	papers	~	fra_012E
17 June 98	Joa	~	crunchi4.htm	Little essay about the various methods and viewpoints of crunching IV	papers	~	fra_012F

Little essay about the various methods and viewpoints of crunching.



Part III: Adapting to the sources (Huffman revisited)







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 last chapter Dr. Watson stumbled over the problem of big

files with so many charakters in it that the frequency of all

256 possible chars are -statisticalwise- nearly the same. 

Running a Huffman-algorithm on such files leads to trees with

8bits encoding for each char - thus giving us no crunching 

efficiency.

But on the other hand everyone with a hex-editor in his 

toolbox has made the experience that files are 

somehow seperated (chunked).

Some areas seem to yield code, others appear as vast deserts of 

zeros, and again others have up- and down-counting values.

On the PC you have for example Code and Resource areas, which are

seperately created and just linked together (hence the Borland

Resource Workshop 4.5). 

But how do we take advantage of this circumstance?



Well, the key to our problem is the tree. Once it is created,

we are doomed with it, unable to change it, only able to 

encode our data with this static, inflexible tree, right?



Not quite! If we could adjust our tree to the actual data somehow,

we would be able to generate several trees in the runtime, each

tree nearly optimized for the actual data coming up. But how do

we adjust our tree? And what about the decoder? And how do we

build up the first tree?



Yes, the first tree. What about it? We are about to be flexible, right?

Could we take the pain of the first data not perfectly encoded?

What, if we could? What, if we would build up a tree with all

frequencies set to one? Each symbol would be written with 8 bits.

But the more we would read from the file, the more we would adapt

to the data read and the more we could cope with sudden changes in

the data flow.



so the basic idea would be:



Cruncher:

initialize_tree_with_all_frequencies_to_1

while not eof

{

    read char c

    encode c, Output

    frequencyarray[c]++

    adapt tree, c

}



Decruncher:

initialize_tree_with_all_frequencies_to_1

Mychar = 0

while Mychar != EOF

{

    Mychar = decode(Input) //read symbol to the next symbol

    put Mychar, Output

    frequencyarray[Mychar]++

    adapt tree, Mychar

}



This would work and would be stable. Unfortunately, even programmed

in Assembler we would have to wait to many hours to crunch a simple

file. The resorting of the tree after each byte read/written eats up

to many memory-read/writes. Imagine crunching a file like

Winword '95 (Ver 7.0) with it's 3.845.120 bytes. Imagine a tree-struct

having about 20 bytes in memory. Multiply that with 257 = 5140 bytes,

not necessarily stored nearly together or array-like (so read-ahead

memory chips can't outplay their abilities). Imagine this 

5140 bytes getting sorted 3.845.120 times = 1.97639168exp10 bytes

shifted thru your memory just for Micro$oft 

(assumed you would have only 1 sorting step while building the tree)...





There must be a better way, right?



Yes, Watson, there is a better way. And it's not so difficult to implement

it for our purposes.We have to implement a watcher!



This watcher can be an intelligent algorithm or a not-so-intelligent counter

with a conditional rebuild. Let's examine the latter method first:



As long as normal files are not bigger than 4 GByte we can use a simple

32bit-integer for our counter. Let's name it "Adjustcounter".



This counter will be incremented and tested afterwards:



Cruncher:

initialize_tree_with_all_frequencies_to_1

Adjustcounter = 0

while not eof

{

    read char c

    encode c, Output



    frequencyarray[c]++



    Adjustcounter = Adjustcounter + 1

    if Adjustcounter > 4096

        adapt tree

        set all of frequencyarray[] to 1

        Adjustcounter = 0

    end if

}



Decruncher:

initialize_tree_with_all_frequencies_to_1

Mychar = 0

Adjustcounter = 0

while Mychar != EOF

{

    Mychar = decode(Input) //read symbol to the next symbol

    put Mychar, Output



    frequencyarray[c]++



    Adjustcounter = Adjustcounter + 1

    if Adjustcounter > 4096

        adapt tree

        set all of frequencyarray[] to 1

        Adjustcounter = 0

    end if

}



This will reduce our horror scenario from 1.97639168exp10 bytes

down to 4.825.175 bytes swirled thru our memory. Where i got the

4096 from, you ask? To be honest, i put it out of my hat. There is 

no special reason for it - just a page size i encountered a lot, 

that's all. If you experiment with this algorithm, try it with

other sizes. Keep book about the kinds of data you crunch and

which Re-Adjusting size gets you which results.





The other way would be an intelligent algorithm watching the 

input stream giving alarm, when the data, rendered in the tree,

is outdated by the incoming new data. How could such an algorithm

look like? Well, there are a lot of possibilities. One basic

mechanism would be:

- Have the 'best' few codes of our tree ready.

- Check the incoming byte.

- actualize a second statistic.

- compare it with the 'best' codes of our tree

  if the second statistic has no more 'best' bytes

  with the tree 'best' bytes in common, then alarm and adapt.



Let's examine the steps:

- Have the 'best' few codes of our tree ready.

That's easy: We just iterate thru our tree and keep book

of the best, say, 10 codes in a little array.

As we execute this routine only when we (re)build our tree, 

it can be written a little bit more sloppy 

(always remember: the most timeconsuming code (about 80% time) 

is consumed in only 20% of the code. So don't optimize where

it is not appropiate).



-Check the incoming byte

Well, that's easy, too. After we received the byte from

the I/O-routine, we have it ready for dinner.



-actualize a second statistic

Hm, that's not so easy. I would advise a shuffle-algorithm.

For this we initialize a 256-byte statistic array with

the accompaning char-values (array[0] = 0x00; array[1] = 0x01 etc.)

When the first byte is read, we localize it 

in this array WITH A LOOP!!!

Then we shuffle all bytes from the specific found-index 

down to index 0 one position up and insert the byte at array[0].



Here one example (array shortened to 4 entries):

array[0] = 0x00

array[1] = 0x01

array[2] = 0x02

array[3] = 0x03



incoming data: 0x02. Now we look for the byte in our array, 

fetching the INDEX. The char 0x02 is found at the position

2 in the array. Now we shuffle all bytes below one position 

up:

array[0] = 0x00  >- keeps it's value

array[1] = 0x00  >- gets overwritten

array[2] = 0x01  >- gets overwritten

array[3] = 0x03



Then we patch array-pos[0] with the char we wanted to find (0x02):

array[0] = 0x02  >- patched

array[1] = 0x00

array[2] = 0x01

array[3] = 0x03





Next byte could be a 0x02 again.

We would find it on position 0. We would shuffle all bytes from

position 0 till position 0 up by one (that is, im this case

the loop terminates immediately, as the condition is flagged

before the body of the loop could be executed) and we patch

position 0 with the byte we wanted to find (the same byte).

If you implement this algorithm this is a point where a 

little if-clause could help saving CPU-time.





Next byte could be a 0x03.

We would find it on position 3. All bytes are shuffled one 

position up from 3 till 0:

array[0] = 0x02  >- keeps it's value

array[1] = 0x02  >- gets overwritten

array[2] = 0x00  >- gets overwritten

array[3] = 0x01  >- gets overwritten



Array-Pos 0 is patched with the byte we wanted to find (0x03):

array[0] = 0x03  >- patched

array[1] = 0x02

array[2] = 0x00

array[3] = 0x01





Next byte could be a 0x02 again.

We would find it on position 1. All bytes are shuffled one 

position up from 1 till 0:

array[0] = 0x03  >- keeps it's value

array[1] = 0x03  >- gets overwritten

array[2] = 0x00  

array[3] = 0x01  



Array-Pos 0 is patched with the byte we wanted to find (0x02):

array[0] = 0x02  >- patched

array[1] = 0x03

array[2] = 0x00

array[3] = 0x01



etc.

This algorithm guarantees that the most recently appeared bytes

are in the first places of the array. With this we have our 

second statistic acualized. Note that there is a lot of counting

and memory reading going on here. This could easily lead to a

new horror-scenario here. An intelligent MemCpy, taking the 

adjacent bytes of the array into account, so copying first in

longs, then in bytes would be appropiate here.





- compare it with the 'best' codes of our tree

  if the second statistic has no more 'best' bytes

  with the tree 'best' bytes in common, then alarm and adapt.

Now, that's easy again, after having our statistic actualized

so eloquently. We just compare the first, say, each of the 10 entries of

our second statistic with the best 10 tree-entries. If there is no

more hit, we rebuild the tree anew and reset the tree-statistic.



If we calculate what amount of bytes we read/write:

3.845.120 times x adding one to a frequencyarray =     3.845.120 +



3.845.120 times x searching in the 

shufflearray  = (3.845.120 * 32). 32 because 

the most recent bytes WILL be in the front of

the array and therefore be found faster.         =   123.043.840 +



3.845.120 times x shuffling the array 

shufflearray  = (3.845.120 * 32*31).             = 3.814.359.040 +



3.845.120 times x patching the first entry       =     3.845.120 +



3.845.120 times x executing a 10*10 loop

looking for one topmost byte in the 

other topmost array (statistically leaving the

loop after the half, only 50 steps instead of

100).                                            =   192.256.000 +



(plus the resorting of the arrays and the

rebuilding of the tree. For the sake of the

demonstration this is not calculated here)



Makes =                                          ==4.137.349.120 



That is not quite 4 Gigabyte memory reading and writing here. Is this

worth the effort? You decide. I prefer the counter-method, but you'll

notice that the shuffle-to-front-algorithm can be useful for more than

this kind of work. Indeed we'll meet it again when we come to the

burrows-wheeler compression. 





I have a question.



Yes, Watson?



This adaptive technique - is it only used in combination with the

Huffman algorithm?



No, the principle of making a statistical algorithm more flexible 

thru the adaptive approach is not limited to Huffman. When we come

to the arithmetic crunching technique we'll come back to the

adaptive approach again, believe me.







But the next thing we will discuss are some non-statisticall things.



Till then...happy cracking :-)







I hope you enjoyed this chapter. 

There will be more - i promise.

Just have a little patience.



Greetings from a programmer



Joa

---

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