papers
+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

> If you signal me, that this was understandable and want
> more, you will - i promise

Well, I do signal you that this was understandable and that I want more!
In fact I hope that you'll deal us some good cards about "their delicate and secured data" and about the "lots of algorithms" used inside the black boxes... because we want to have some more light inside all those black and dark boxes :-)


         Little essay about the various methods and viewpoints of crunching.



                                    Part I: Introduction





By Joa Koester (JoKo2000(at)hotmail(point)com) 

This essay is free to be copied and read and spread as long as

you are decent enough to let my name in it. 

If you have corrections, comments, better examples than the ones used 

in this essay, etc. - drop me a line.





But on with the essay...



as i recently visited fravia+'s page on the net, i was amazed about the 

knowledge packed together, the philosophy and the attidude contained 

in the writings. But i missed a little bit the **other side**. 

That is, us programmers, condemned to write software for banks, 

insurance companys etc., so they can make a lot of money, ripping

a lot of people of. These companies are often serious about data

hiding and are always eager to have their delicate data secured.

One way of securing data is crunching (packing) them. This has two valid 

points:



 - the data is secure (coz the crunching algorithm is not

       made public)

 - the data is more compact, meaning it can be easier transfered;

       the risk of a disc producing a read/write error, vaporising

	   personal data is definitevly lowered, when the data only

	   takes 50Kbyte on a disk rather than 200KByte (of course

	   if a read write error happens exactly in these 50KByte,

	   the file is also gone ;)



This brings us to the question:



WHAT IS CRUNCHING?





Well, a pseudo-mathematical answer would be:

everything that reduces a certain amount of data in its

SPACE, but not in it's INFORMATION (lossless crunching

that is, there are some quality (information) reducing 

algorithms out there - jpeg for example).





So we have some data IN:



AAAAACCCCCDDDDDDCCCCCefg





and we have a black box:



  /-------\

/           \

| Holy crap |

| happening |

|   here    |

-------------



and we have more or less unreadable data OUT:



@$/)!%A3yfg





So, what's the principle of the black box? 

Is there one Super-Algorithm that you are not allowed

to know ("Behold my son, tis knowledge is not 

for your eyes") ?



Of course not. There are principles. And there are lots

of algorithms, not just one.

And you ALREADY know a lot of these priciples 

from the everyday live.





When you have to cross a heavy-driven road you more or

less wait at the traffic light to become green. You stand 

there and see a red light. Maybe the light is shaped like

a standing person or a cross or something else. But it is red

and you already know that this means: Hey, stop, don't go.

If you go, you are violating three different traffic laws at least,

obstruct the cars and impose the next world war. Besides

you put your life in danger ;) 

And all this information just in the little red light on 

the other side of the street.

Are all red lights this way? No.

If you, for instance, are a musician and you are about to

record a song, you will press record & play on your 

recorder and a RED light will show up, telling you, that

you better not make thousands of mistakes and record 

what you are doing properly. The red light can be a circle,

a square, even a text, it doesn't matter. But it will be

red!!!





Dr. Watson, what do you think?



Well...

What we have here is a case of crunching:

The various informations are condensed into few different

symbols as possible. In both examples, only one symbol 

(the red light) is needed to get the MEANING (the information) 

transmitted. 



Right, Watson, right. And could we switch the information

contained in the symbols? That is, making the red light on

the recorder telling us, when to stop before a traffic light?



No. They are both red lights, that's true. But the red light

in the recorder has nothing to do with crossing a road and

the traffic light has nothing to do with us recording a song.

The CONTEXT is different. The only thing that is similar is

the color.



Hm, hm.

Condensing information (much source symbols -> less destination

symbols) and keeping the CONTEXT in mind. Sounds pretty 

good to me. 



Kind of 

	switch (context)

	{

		case traffic:

			if (red_Light) {...} else {...}

			break;



		case recording_music:

			if (red_Light) {...} else {...}

			break;



		default:

			No_Condensed_Symbols();

			break;

	}

ain't it?



In all crunching we will always have something that will 

tell us, in which context we will have to switch and because

of this we will know how the next following symbol(s) is/are 

to be interpreted.





Dr. Watson, are all interpretations dependend on only one symbol?



Hm, i would say no. There may be cases, where this is true,

but in most cases, there are more than one symbol defining

exactly, what's going on. There are crossroads where are

streets leading straight ahead and right and there are

crossroads where cars will drive left or straight ahead or

right. This will depend on which part of the crossroad the

car stands, so that the traffic for straight ahead can go

but the traffic for the right has still to wait for THEIR 

specific traffic light to switch from red to green. Another

example would be the position of the light. If the position

of the red light and the green light would be switched, 

there would be some chaos, i bet.



Sounds resonable, Watson. You say, that there are symbols

for a general context which are finetuned thru other symbols

defining the exact context to be interpreted? 



Exactly.



But what do you think how it is possible that all people

know that they have to stop on a red sign and go on a green

one?



Well, i would say that they know, because someone told them.

The parents, perhaps. Or they are taught so in the school.





In fact, to crunch and decrunch information correctly, both,

the sender and the receiver have to use the same way of 

interpreting the data. Society has ruled that a red traffic

light is a STOP. And so traffic lights will switch to red

when it is time to stop the traffic for one direction. And

on the other side YOU get taught by the society that you

better not run across the street when you have a red or else

you play 'Frogger' for real...

So put in one sentence - Both the sender and the receiver

use the same MODEL of data-interpretation.





Dr. Watson, what if i would like to crunch the information

transmitted in the red traffic light?



This would be nearly impossible. The whole meanings of 

what the traffic light means is already emitted in only

one symbol (the red light i mean now). There is a point

where the number of informations can't be reduced any

more without getting complications elsewhere. 

Imagine one would pack all three lights (red, green

and yellow) into one light that would change it's color,

depending on it's actual state. Ok, you would have less

metal, only one light to look at and less glass to clean.

The normal case would be condensed - not in interpretation

but in material. The routine of Green - Yellow - Red - 

Yello - Green... would stay. So far so good. But traffic

lights have the ability to send more complex signals also.

When, for example, there is a traffic-jam ahead and the

police notices this, they can (at least where i live) achieve

that the traffic lights green and yellow will blink together

to signal an upcoming jam so that the drivers can react to 

this signal. When all lights would be build in one case,

one would have to think of a special flashing / flashing

in a special speed or something like that. Not very

good. Especially for older drivers whose reaction times may

be slower - they would concentrate more on interpreting the

flashing signal than on the traffic itself increasing the 

risk of producing an accident. One other point would be the

shape of the light. A standing man in red and a walking man

in green would mean a complex shape of glass illuminated with

a complex circuitry. This would mean, if one part would activate

falsely, you would have, for example, a red man standing with

one green leg walking. Very confusing, eh? So condensing one thing

over the point of information content (also known as 

ENTROPY) on it's maximum leads to enlarging other parts giving

them biiiig overhead. How do we know that this process is worth

doing all this?



Well, a certain student once came up with exactly this question

and he answered it by himself: It depends on the probability of

the certain symbols. If some symbols are statistically so often

in our stream of perception (analyzing, reading buffer data, etc.)

that we can condense them enough that, even with the enlargement

of the other symbols (which but are not so often) we have an

overall crunching than it's worth it. The name of the student

was Huffman...

For example, you have:

aaaaaaaaaabbbbbcccdd (10 x a, 5 x b, 3 x c, 2 x d) 20 chars



then you would have 20 x 8 bits = 160 bits.



If you now would transmit the 'a' with 7 and the 'c' and 'd'

chars with 9 bits you would have	10 x 7 = 70

									 5 x 8 = 40

									 3 x 9 = 27

									 2 x 9 = 18

									         __

											155



So we would save 5 Bits. Not much, but better than nothing.

Of course you have to come up with an optimized coding for

these values as you wouldn't want to calculate by hand, which

char you should with which number of bits without confusing with

the handling of the other chars. But Huffman found a perfect

algorithm giving you the optimized value-table for your chars.

(but this is for the next part ;)







To condense the intro a little bit:



- To crunch is a way to transmit a certain amount of information

    in less symbols normally needed.

- How you crunch/decrunch depends on the actual context of 

	data actually received

- Both, the sender and the receiver will build up the same

	way of interpreting the data, building up the same model

- When transforming long information-symbols to shorter packages of

	symbols and thus reducing the output, we will face the case

	that there will some (hopefully seldom) symbols getting transformed

	into LONGER symbols. If we have totally random data crunching happens

	also totally random, making our affords nil. 

	That is BTW the reason why packing an already packed zip or rar 

	file is in almost all cases useless - the data written by those

	packers is nearly perfect random. 





I hope you enjoyed this intro. If you signal me, that this was 

understandable and want more, you will - i promise.



Greetings from a programmer



Joa


redhomepage redlinks red anonymity red+ORC redstudents' essays redacademy database
redtools redcounter measures redcocktails redantismut redbots wars redsearch_forms redmail_fravia
redIs reverse engineering legal?