Archive for the ‘Algorithm Programming’ Category

Cryptographical Analysis Tool

Tuesday, November 24th, 2009

Hello  everyone.
Recently I have “Computer Communication and Security homework” to do. They consist of many problem involving encryption/decryption algorithm. One problem let you try to decipher all the text, it’s an english prose.

vcwpc kwblm smljy glbgu gbtwj jyats
lwsgm lwjjy vcrfc rikwl qjwte fscpw
lbgqm jwscb ktpbc pqats vfwsm dvwpw
lbsfc ktrfu wtlsc brpgk cmdqj wtefs
cpgle vfmjc ncmnj cq

After seeing this kind of problem, I thought to myself, I gonna break its code in no time. Ha ha ha, you know that up until now, I even don’t break it yet.

What I start to take the approach here is as follow.
1. Character/Word analysis
2. Algorithm analysis

Up until now, working on 2 days ago, I am at the first stage.
By trying to catch the pattern of the words that most frequently appear in the english literature such as ‘the’. And similar word that you should be fimilar with. Not quite close to target now, but along the process I have created a tool to analyze the encrypted text. Note that all of programs below will operate on only plaintext.
They are
- charCount, the program to report the frequency of english plaintext character, it can report in absolute value, relative value, or percentage
- patternCountN, the program to report about the pattern found in the encrypted text, the occurrence for each pattern must be at least 2 or above in order to treat that one as significant. Also we can specify the number of maximum number of individual pattern to find in such encrypted text too.
- simpleSwap, the program to swap the character as user defined via config file.
- caesar-d, the program to decrypt the caesar algorithm, it accepts ‘key’ as parameter in order to decrypt differently with each specify key (usually from 0-25)
- testCaesar, the wrapper program to execute caesar-d program to generate report for all 25 keys possible to decrypt.

All of those programs are created with DevC++ 4.9.9.2, under gcc compiler. I use combination of C/C++ to create.
They are tested primarily on Windows 7. But it requires much less modification of codewhen porting into Ubuntu.

When working with C/C++ language I feel the power of them, and the low level in which you must do almost all the task by yourself. So you should know just everything. In fact it can’t be true. But at least it can help us out to build the firm ground right?

I included all the sourcecode which you can look at, modify, and learn by yourself later without any license!

Each program also accepts some parameters too. Just look at the comment above in the sourcecode.
I point out to you below anyway.
- charCount
   charCount [-r, -p] <input file>
   -r, will generate the result in relative frequency
   -p, will generate the result in percentage
   <input file>, is the input text file

- patternCountN
   patternCountN <input file> <output file> <N>
   <input file>, is the input text file to find patterns
   <output file>, is the output file for report to be generated
   <N>, integer number defined the maximum number of character for individual word to be find in pattern

- simpleSwap
   simpleSwap <config file> <input file>
   <config file>, is the user’s config file defined for characters to be swapped
   <input file>, is the input text file

- caesar-d
   caesar-d <input file> <k>
   <input file>, is the input text file
   <k>, is the key used in the caesar decryption algorithm (possible is in range of 0-25)

- testCaesar
   no parameter for this program.

Okay, I think you might want to have a hand on those tools already.
Please enjoy, and let me know if you like or dislike!!

Download Section
- charCount, sample of output file (copy from stdout)
- patternCountN, sample of report file
- simpleSwap, sample of config file
- caesar-d, testCeasar
- sample of encrypted text file (cut out space)

Tags: , , , , , , , , , , , , , , ,
Posted in Algorithm Programming, Journal, cryptography | 1 Comment »

Lighting 2D

Wednesday, May 13th, 2009

Have you ever wonder how to implement the lighting in the cloudy and raining day?
For me, the answer is “yes”. By jump across directly to 3d world would be a bit of difficulty, so I decide to do it in 2d first.

The behavior of the lighting in natural is complex and unpredictable, we always try to simulate those behavior in the term of graphics programing. By using the recurrsive routine to help out, we can achieve at least the close one.

Only 2 main parts to implement this thing.
First is LineDrawer, and Second is Algorithm to simulate the lighting.

Why bother do the line drawer system, isn’t it exist already in xna framework? No.
Actually the pixel drawer in XNA also doesn’t exist, but we can work around this which I will explain how to do it next.

For pixel drawer in XNA, you have to create the 1 x 1 pixel texture of white in order to be used as the texture to draw on screen. Of course, the white choosed is important, as we can tint it with other color. Thus giving us ability to draw 1 pixel color on screen.

But for line, how can we do that?
We also use the concept of pixel drawing.
Imagine you want to draw line, thus we have to put those pixels (thus 1×1 texture)  in sequence from (say) point A to point B on screen. That’s it, we just iterate the process and draw each loop with that 1×1 texture.
But with this approach we need to calculate the position for each of the texture being drawed, and lots of textures too, nonetheless it gives the most accurate of line (we may not see the different).

So what we will use instead is that, we will use only 1×1 texture for each pair of point defined the line.
We will stretch it along the x-axis for the magnitude after we know the distance between two points, and we will stretch along the y-axis for our variable line-thickness. Also we will rotate the texture too, in the case if two points are not on the same horizontal.

You can see all of this in PrimitiveLine.cs file. (The download link is below, thanks for the author for this great and very useful line drawer, I’m sorry that I can’t remember the name because it’s very long ago.)

The most notable part is here.

        ///
        /// /// Renders the primtive line object.
        /// ///
        /// ///The sprite batch to use to render the primitive line object.
        public void Render(SpriteBatch spriteBatch)
        {
            if (vectors.Count &lt; 2)
            return;            
 
            for (int i = 1; i &lt; vectors.Count; i++)
            {
                Vector2 vector1 = (Vector2)vectors[i-1];
                Vector2 vector2 = (Vector2)vectors[i];               
 
                //check for boundary
                //we dont draw anything if both vertexes are out of range
                if ((vector1.X &lt; 0 &amp;&amp; vector2.X &lt; 0) ||
                   (vector1.X &gt; width &amp;&amp; vector2.X &gt; width))
                    return;
 
                // calculate the distance between the two vectors
                float distance = Vector2.Distance(vector1, vector2);
                // calculate the angle between the two vectors
                float angle = (float)Math.Atan2((double)(vector2.Y - vector1.Y),
                    (double)(vector2.X - vector1.X));
                // stretch the pixel between the two vectors
                spriteBatch.Draw(pixel,
                    Position + vector1,
                    null,
                    Colour,
                    angle,
                    Vector2.Zero,
                    new Vector2(distance, Thickness),
                    SpriteEffects.None,
                    Depth);
            }
        }

Okay, let’s we move to the algorithm itself to simulate the lighting.

Two points defined a line

Two points defined a line

We will use the recurrsive approach here, as you see from the image above, two points defined a line.
Then if we find its middle-point, and offset its position at random for a little, and repeat this step until the length between the end point to mid point is small enough, then we will get the simulated lighting.

See it here (in Game.cs),

/// 
        /// Add the vertices to the lighting between the two end points a, and b.
        /// 
        ///
 
        ///
 
        ///
 
        private void AddLightingVertices(Vector2 a, Vector2 b, float displacement, int lindex)
        {
            if (displacement &lt; CURR_DETAIL)
            {
                //add the two end points
                lineDrawer[lindex].AddVector(a);
                lineDrawer[lindex].AddVector(b);
            }
            else
            {
                //calculate the midpoint between point a, and b
                float mid_x = (a.X + b.X) / 2.0f;
                float mid_y = (a.Y + b.Y) / 2.0f;
 
                //displace it a little
                mid_x += ((float)random.NextDouble() - 0.5f) * displacement;
                mid_y += ((float)random.NextDouble() - 0.5f) * displacement;
 
                Vector2 midPoint = new Vector2(mid_x, mid_y);
 
                //draw the line from two end points to the mid point
                AddLightingVertices(a, midPoint, displacement / 2, lindex);
                AddLightingVertices(midPoint, b, displacement / 2, lindex);
            }
        }

After this finishes you will get all the vertices ready to be drawed by line drawer.
Notice that I want the code for drawing to be clean as possible (like drawing the point at the leftmost to the rightmost), so each two end-points of lighting requires one PrimitiveLine to handle it.
Thus if you increase the number of bolt, then you need to increase the PrimitiveLine too.

Now you are ready to draw it,

protected override void Draw(GameTime gameTime)
        {
            GraphicsDevice.Clear(Color.Black);
 
            //early start of the spritebatch (to get the benefit of only one traversing of loop)
            spriteBatch.Begin(SpriteBlendMode.None, SpriteSortMode.Immediate, SaveStateMode.None);
 
            //loop through all the line of the lighting
            for (int i = 0; i &lt; NUM_BOLT; i++)
            {
                lineDrawer[i].ClearVectors();
 
                //add the point to the lighting
                AddLightingVertices(a, b, DISPLACEMENT, i);
 
                //render the lighting
                lineDrawer[i].Render(spriteBatch);
            }
 
            spriteBatch.End();
 
            //Draw the info text
            DrawInfoText(gameTime);
 
            base.Draw(gameTime);
        }

I just want to use each loop efficiently so after I add the vertices for each pair of bolt then I draw it immediately as you see above.

You’re done for this, note that you can add more settings for this app, like the number of bolt, the threshold length (to stop the recurrsive, note that for this I named it “Detail”), the displacement for the midpoint to be offset away from the line, thickness of the line.

Here is the result,
(Sorry for my quite mess post, it’s very late now, and I should go to sleep, sorry for that folks.)

Two points defined a line
Simulation starts

Low number of bolts
High number of bolts with thick line

High number of bolts!

Lighting 2D: Download

Tags: , ,
Posted in 2D Graphics, Algorithm Programming, Showcase | 4 Comments »

Fog

Sunday, April 5th, 2009
Initial test (specular highlight is enabled)
Add more buildings.

Look from another side.
Aha!!, finally.

See the effect of specular highlight at top left.

Fog is not that hard to implement, in fact it’s easy that it doesn’t pull down and doesn’t need much effort to integrate it into your code.

To do it, you just insert the following equation into your effect file, then calculate the result color as normal.

float l =  saturate((dist - fogNear) / (fogFar - fogNear) / clamp(world.y / (fogAltitude +1), 1, fogThinning))

From that equation, dist is the distance between the object’s position in world space and your camera (which is already in the world space), for other fog’s properties that are
- fogNear => the range that you will see clearly
- fogFar => how far you can look ahead (actually it’s radius from the camera’s position)
- fogAltitude => height that the fog is still effect the scene
- fogThinning => it’s just the reducer magnitude (to reduce l for even more)

Thus we get the percentage of  fog influenced in the particular pixel from that equation, l.
After that we take this l-value, to do the linear interpolation with the base color from the model (or just the color from the model, or even have previously calculated with another technique such as diffuse, specular highlight) to the fog color itself.

Now, we have the lovely mixed of both the color from fog and model’s color.

Tags:
Posted in 3D Grahphics, Algorithm Programming, Showcase | No Comments »

Priority Queue

Tuesday, February 3rd, 2009

I know when you are doing your current project, you focus on its contents.
This let your less time to be spend on building the system or algorithm that need to support them.

By facing this by myself, when I do my game project’s AI system. It need the priority queue to support the sorted messages that will be send/receive across game entities in the world.

With less time to spend on building it from scratch, I look at CodeProject. It have much resource about programming.

So I grab it a try just to build from another one this time, you see the priority queue here Priority Queue, say thanks to BenDi.

Priority Queue use the binary tree to implement, so its complexity of O(log N) is enough to attract me.
Only one feature that missed from the original one is ‘allow no duplicated values to exist’.
So I try to implement it myself by extend from that one. (More easier though)

The idea is to perform checking for the existing value in the list first before add new value into the list.
It lists here.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

            /// <summary>
            /// Push an object onto the PQ
            /// </summary>
            /// <param name="O">The new object</param>
            /// <returns>The index in the list where the object is _now_. This will change when objects are taken from or put onto the PQ.
            /// If the object is already existed in the list then return -99.</returns>
            public int Push(object O)
            {
                int p = InnerList.Count, p2;
                if (CheckValueInList(O) == -1)
                    InnerList.Add(O); // E[p] = O
                else
                    return -99;  //return, we dont do anything
                do
                {
                    if (p == 0)
                        break;
                    p2 = (p - 1) / 2;
                    if (OnCompare(p, p2) &lt; 0)
                    {
                        SwitchElements(p, p2);
                        p = p2;
                    }
                    else
                        break;
                } while (true);
                return p;
            }

You see that I call my CheckValueInList(O) before adding any new object, that method is implemented by using binary search, so the complexity is the same magnitude with binary tree thus O(log N).

This seems match you know!!

The code for CheckValueInList() is listed here.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

            // Check the existance of the specified object in the list,
            // if it's exist then return the index of the existed object, otherwise return -1
            int CheckValueInList(Object O)
            {
                //if no element
                if (InnerList.Count == 0)
                    return -1;
 
                //binary search
                int low = 0;
                int high = InnerList.Count - 1;
                int mid;
                while (low &lt;= high)
                {
                    mid = low + (high - low) / 2;
                    if (Comparer.Compare(InnerList[mid], O) &lt; 0)
                        high = mid - 1;
                    else if (Comparer.Compare(InnerList[mid], O) &gt; 0)
                        low = mid + 1;
                    else
                        return mid; // found
                }
                return -1;
            }

The psedocode for binary search algorithm can be found from Wikipedia: Binary Search.
But note that BenDi use the IComparer, so I must strict to it and use this flexible feature that he build on.

Instead you can modify the OnCompare() method to match your type of data.
OnCompare() method is listed here.

1
2
3
4
5

            // Modify the code here to accommodate the type of data being compared.
            protected virtual int OnCompare(int i, int j)
            {
                return Comparer.Compare(InnerList[i], InnerList[j]);
            }

Thus from above you may cast it to your defined type and performing the comparision.
Like this.

1
2
3
4
5
6
7
8
9
10
11
12

            // Modify the code here to accommodate the type of data being compared.
            protected virtual int OnCompare(int i, int j)
            {
                if(InnerList[i] is MyType &amp;&amp; InnerList[j] is MyType)
               {
                      MyType obj1 = (MyType)InnerList[i];
                      MyType obj2 = (MyType)InnerList[j];
                      return Comparer.Compare(obj1, obj2);
                }
                //in this case only MyType type will be compared, otherwise return return
                return -99;
            }

This case I assume that you already overload operators for MyType, and that will be flexibly used in OnCompare() method.

Download project:pqtest

Tags:
Posted in Algorithm Programming | No Comments »

The real power of xor.

Thursday, January 29th, 2009

Ok, let’s go down talk about some real programming.
This time, it is about xor (exclusive-or).

I will show some real benefit that we can gain from using it.

Imagine that you want to send some message to your friend, but you want to encrypt it, doesn’t allow anyone to easily grab out the information you send.

How we can make use of xor to apply to this case?

At first, from the mathematical sense, we all know that

x xor y xor y = x

It means that if we send some information, x, and then take the xor-operation with y. Now we can encrypt the messege and bravely send it out in the open world.

As you can suggest, if we take xor-operation again of that encrypted message with y again, we will get the real information. WOW!!!

In this point, all you need is just that y information, in which we must know between each other in order to read the real message.

(The message can be anything range from normal text, images file or byte data.)

Let’s follow my step to implement it, and assume that in this case I have an image to send to my friend.

Our image is ‘input.jpg’.

input file

From the image above, we will take its every byte to be xored with our key string “MEETMEATTOGARPARTY”.
Then we will have the encrypted image which is ready to be send.

ENCRYPTION

See the code below (Please right click and save as)
image_encrypt

From the code we can define our known key which will be known only by the two sides as I have said to you.
Or just simply said that, other end will use this key to decrypt the message just to read it.

This program is designed to accept the input file named ‘input.jpg’ and it will encrypt it and send out ‘dataen.bin’, the latter file that you will use it to send to your friend.

If you are very curious about this stuff, just try to encrypt the some image file then open it with any favourite image viewer, you cannot view your image file or you will see the heavily distort and corrupted pattern of the image file.

DECRYPTION

Let’s we turn to the decryption part.
See the code below.
image_decrypt

The same for encrypt code, and use the same key too.
After run this code, you will get the original message thus ‘input.jpg’.

Note that this is only the simple encryption/decryption algorithm, so we should increase the strength by included various and some other method too.

Get any idea?
Haxpor

Tags:
Posted in Algorithm Programming | 1 Comment »