How to translate C source code into assembly instruction for a function

Converting the function source code into the assembly is not a big deal , it is just a matter of 3 simple steps:

1.) Identifying the non-executable statements within a function.

2.)Create a function symbol table and resolve all the non-executable instructions.

3.)Translate C source into assembly source.

These steps sounds to be tough but if you have basic knowledge of c language these are very easy . let us take the steps one by one considering the follwing example of small code:

view plainprint?

1. int main()  
2. {  
3. int a = 100;  
4. int b = 100;  
5. int c;  
6. c = a+b;  
7. }  

Step1: Identifying the non-executable statements within a function

To understand this step we have to know what are the non-executable statements ??
Whenever you write a program you always write them at the very beginning of you function body.yes you guessed it right the variable declarations are the ones.
we can define the non-executable statements as:

Non-executable statements are those which are not converted to the instructions to be executed by the processor. It means that they are just the memory allocation instruction which are processed by the compilers.

So, in our example we have three non-executable statements shown in the figure below.

Step2: Creating the function symbol and resolving all non-executable statements.

Function Symbol table consists of 4 values:
1.)Symbol Name
2.)Type
3.)Composition (size of data type of symbol)
4.)Offset Address

You can easily fill the symbol table as shown below for our example.

As you can see in the above table , we have taken the variable names as symbols and added their type and size in the respective columns.

After filling the table we have calculate the total size which comes out to be 12 . Basically this 12 is the size of the stackfor the function main which will be allocated when the main function will be called.

Now the last column is the offset address . Offest Addresses are allocated by the compiler. let us see how we will fill that column.

Let us take the base pointer to the stack as ebp and assume that stack grows downwards (which happens most of the tym ).

As the size of the stack is 12 and a is the first variable declared in the function so,

Variable 'a' will get the memory at -12(%ebp)  that is -12 from ebp (stack base pointer)
Variable 'b' will get the memory at -8(%ebp) because 'a' is of 4 bytes.
Variable 'c' will get the memory ar -4(%ebp) because 'b' is also of 4 bytes.

So, The final function symbol will be:

Step3: Translating C code to assembly language.

In this process whenever we have to access the variable we will replace that by the offset address given in the functionsymbol table.

To convert the function C source code into assembly we need to know one thing that is GNU compilers follows a standard which says that:

"Every function consist of 4 parts which are:
1.) Function name
2.)Pre-amble (the opening brace of function)
3.)Function-body
4.)Post-amble (the closing brace of function)"

And the same is written as the following:

Function name :

                pre-amble

                function-body

                post-amble.

Here pre-amble defines the code for the opening curly brace and
       post-amble defines the code for the closing curly brace.

Let us take a look at the both the pre-amble ,function body and post-amble small piece of code:

Pre-amble code:

view plainprint?

1. Pushl %ebp  
2. Movl %esp,%ebp  

Function-body code:

view plainprint?

1. Subl $12, %esp  
2. Movl $100, -12(%ebp)  
3. Movl $100, -8(%ebp)  
4. Movl -8(%ebp), %eax  
5. Addl -12(%ebp) , %eax  
6. Movl %eax, -4(%ebp)  

Post-amble code:

view plainprint?

1. movl %ebp, %esp  
2. popl %ebp  
3. popl %eip  

pre-amble and post-amble are the most important part to understand how the stack flow works in  function in c language,
what is the ebp ,esp and eip ?
ebp is the pointer to base address of the stack and
esp is the pointer to top address of the stack.
eip is the pointer to the current instruction to be executed .

Now let us take the instruction one by one and see what it means:

pushl %ebp :--> This instruction means push the content/value of the ebp to the top of the stack.
movl %esp,%ebp :--> This instruction means copy the content/value of the esp to the ebp that is now both the pointers points to the same location.
subl $12, %esp :-->This the first instruction of the function body and it does the job of allocating the space for the function on the stack by subtracting the total amount of space required for the function from the esp so that esp points to the top of the stack as it is defined to be.
Note:
you can also note that now there will be a difference of 12 bytes in the ebp and esp as per our example which is nothing but the space required by the function to allocate its local variables.

 movl $100 , -12(%ebp) :--> This instruction means that move the value 100 at the location 12 less than the location of ebp. that is if ebp is pointing to 1012 address location put the value 100 at 1000(1012-12).
popl %ebp --> This instruction means that pop out the contents at the top of the stack that is value at the address pointed by the esp pointer.

Rest the instruction meanings are self explanatory in corresponding to these instructions.

Full code:

view plainprint?

1. Main:  
2. Pushl %ebp  
3. Movl %esp,%ebp  
4. Subl $12, %esp  
5. Movl $100, -12(%ebp)  
6. Movl $100, -8(%ebp)  
7. Movl -8(%ebp), %eax  
8. Addl -12(%ebp) , %eax  
9. Movl %eax, -4(%ebp)  
10. movl %ebp, %esp  
11. popl %ebp  
12. popl %eip  

This is how we can convert the C code of a function to the assembly source code. The main thing to understand is the pre-amble and the post-amble .

Stack Flow in function calls in C

Today I am going to start a topic on how the stack works when we call a functions in c , how the function calls are executed internally. There are some questions which are very general in intervaiew like:

How the stack is allocated for a function ?
How the calling a function works internally ?
How stack grows when we call a function within a function ?

There are lot more questions on the same stuff. So, we will able to answer all those question after going through the full topic series of this which will be covered in consecutive posts.

So, To understand how the function call works we have to know little bit of assembly programming. Don't be afraid if you don't know the same. we don't require the expertise in that , we just require very basic knowledge.

So to start with we will first learn:

How to translate C source code into assembly instruction for a function :

Converting the function source code into the assembly is not a big deal , it is just a matter of 3 simple steps:

1.) Identifying the non-executable statements within a function.

2.)Create a function symbol table and resolve all the non-executable instructions.

3.)Translate C source into assembly source.

These steps sounds to be tough but if you have basic knowledge of c language these are very easy . let us take the steps one by one considering the follwing example of small code:

int main()
{
int a = 100;
int b = 100;
int c;
c = a+b;
}

Step1: Identifying the non-executable statements within a function

To understand this step we have to know what are the non-executable statements ??
Whenever you write a program you always write them at the very beginning of you function body.yes you guessed it right the variable declarations are the ones.
we can define the non-executable statements as:

Non-executable statements are those which are not converted to the instructions to be executed by the processor. It means that they are just the memory allocation instruction which are processed by the compilers.

So, in our example we have three non-executable statements shown in the figure below.

Step2: Creating the function symbol and resolving all non-executable statements.

Function Symbol table consists of 4 values:
1.)Symbol Name
2.)Type
3.)Composition (size of data type of symbol)
4.)Offset Address

You can easily fill the symbol table as shown below for our example.

As you can see in the above table , we have taken the variable names as symbols and added their type and size in the respective columns.

After filling the table we have calculate the total size which comes out to be 12 . Basically this 12 is the size of the stack for the function main which will be allocated when the main function will be called.

Now the last column is the offset address . Offest Addresses are allocated by the compiler. let us see how we will fill that column.

Let us take the base pointer to the stack as ebp and assume that stack grows downwards (which happens most of the tym ).

As the size of the stack is 12 and a is the first variable declared in the function so,

Variable 'a' will get the memory at -12(%ebp)  that is -12 from ebp (stack base pointer)
Variable 'b' will get the memory at -8(%ebp) because 'a' is of 4 bytes.
Variable 'c' will get the memory ar -4(%ebp) because 'b' is also of 4 bytes.

So, The final function symbol will be:

Step3: Translating C code to assembly language.

In this process whenever we have to access the variable we will replace that by the offset address given in the function symbol table.

To convert the function C source code into assembly we need to know one thing that is GNU compilers follows a standard which says that:

"Every function consist of 4 parts which are:
1.) Function name
2.)Pre-amble (the opening brace of function)
3.)Function-body
4.)Post-amble (the closing brace of function)"

And the same is written as the following:

Function name :

                pre-amble

                function-body

                post-amble.

Here pre-amble defines the code for the opening curly brace and
       post-amble defines the code for the closing curly brace.

Let us take a look at the both the pre-amble ,function body and post-amble small piece of code:

Pre-amble code:

Pushl %ebp
Movl %esp,%ebp

Function-body code:

Subl $12, %esp
Movl $100, -12(%ebp)
Movl $100, -8(%ebp)
Movl -8(%ebp), %eax
Addl -12(%ebp) , %eax
Movl %eax, -4(%ebp)

Post-amble code:

movl %ebp, %esp
popl %ebp
popl %eip

pre-amble and post-amble are the most important part to understand how the stack flow works in  function in c language,
what is the ebp ,esp and eip ?
ebp is the pointer to base address of the stack and
esp is the pointer to top address of the stack.
eip is the pointer to the current instruction to be executed .

Now let us take the instruction one by one and see what it means:

pushl %ebp :--> This instruction means push the content/value of the ebp to the top of the stack.
movl %esp,%ebp :--> This instruction means copy the content/value of the esp to the ebp that is now both the pointers points to the same location.
subl $12, %esp :-->This the first instruction of the function body and it does the job of allocating the space for the function on the stack by subtracting the total amount of space required for the function from the esp so that esp points to the top of the stack as it is defined to be.
Note:
you can also note that now there will be a difference of 12 bytes in the ebp and esp as per our example which is nothing but the space required by the function to allocate its local variables.

 movl $100 , -12(%ebp) :--> This instruction means that move the value 100 at the location 12 less than the location of ebp. that is if ebp is pointing to 1012 address location put the value 100 at 1000(1012-12).
popl %ebp --> This instruction means that pop out the contents at the top of the stack that is value at the address pointed by the esp pointer.

Rest the instruction meanings are self explanatory in corresponding to these instructions.

Full code:

Main:
Pushl %ebp
Movl %esp,%ebp
Subl $12, %esp
Movl $100, -12(%ebp)
Movl $100, -8(%ebp)
Movl -8(%ebp), %eax
Addl -12(%ebp) , %eax
Movl %eax, -4(%ebp)
movl %ebp, %esp
popl %ebp
popl %eip

This is how we can convert the C code of a function to the assembly source code. The main thing to understand is the pre-amble and the post-amble .

I will explain the significance with the example in the next post with step by step change in the stack when we execute these instruction. then it will be cleared why we are using these instruction, so stay tuned for the next post.

If you have any doubt in this , feel free to comment.

Have Fun !!!!

C Language Basic Quiz

Please Comment feedback and Queries about the questions after completing.

C Language Basic Quiz » Online Exam maker

Tower Of Hanoi Continued...

As I have described in the previous post , Here is the Recursion Tree of the Tower. If you are able to draw the recursion tree of a a problem you will be able to code that too very easily.

This Tree is self explanatory , In this we have Decomposed the 3 Disc problem into 3 steps and recursively solved the same.

So, Now we can write the Program for the same , It does not depend which programming language you use to code , the algorithm will be the same.

Tower Of Hanoi Algorithm Implementation.

#include<stdio.h>
int main()
{
int number_of_discs;
printf("Enter the Number of discs:");
scanf("%d",&number_of_discs);
printf("\n");
Towers(number_of_discs,'A','B','C');
}

void Towers(int N,char From, char To, char Via)
{
   if(N==1)
{
printf("Moving %c to %c\n ", From , To);
}
else
{
  Towers(N-1,From,Via,To);                     //(N-1,A,C,B)
  printf("Moving %c to %c\n" , From , To);    //(1,A,B,C)
  Towers(N-1,Via, To,From);                   //(N-1,C,B,A)
}

}

Tower Of Hanoi

Today I will try to explain the Tower Of Hanoi Algorithm in Full detail. I don’t want you to just mug up the 3 lines of code and pass an exam . I want you to learn How we reach to the solution. How we decompose the problem and recompose it again to get the solution which is very important to solve a problem like this. You will also learn how to apply the recursion to get the desired solution.

Tower Of Hanoi:- The problem description is as follows:

We have Three pillars/pegs and N discs of different size on One pillar/peg such that They are in Incresing order of size from top to bottom.

What we have to do?

We have to move the Discs from  Source Peg to  Destination Peg  keeping the following constraints in Mind.

Constraints:

1.)We can take one peg out at a time.

2.)We can’t place small disc below the larger one during the task.

3.)We can only use one more pillar for help to complete the solution.

Problem:

Solution:

We have described the problem the solution above. Now we have to think how to solve the same.

Let Us decompose the problem and try to solve it 

Let us Assume that we have only one Disc On peg A and We have to move the same to the Peg B.The solution is obvious , We will just pick the disc and put it on B and the problem is solved , let us see the same in Picture.

Solution of 1 disc Problem

(1,A,B,C) denotes that we have moved 1 disc from A to B using C.

SO, (1,A,B,C) solves the One Disc Problem.

Now , Let Us Assume that We have Two Disc and We have to move both disc from A to B. Let us see the solution of Two Disc Problem in Picture.

Solution Of 2 Discs problem

So, To solve 2 Disc problem we have followed the following 3 steps:

1.) (1,A,C,B)

2.) (1,A,B,C)

3.) (1,C,B,A)

Now Let us Take the 3 Disc Problem, Now we have to move the 3 discs from A to B.

Solution of 3 Disc Problem:

Now if We see The solution of 2 Disc Problem(2,A,B,C) is :

1) (1,A,C,B)  

2.) (1,A,B,C)

3.) 1(C,B,A)

So,The First 3 steps:

1.) (1,A,B,C)

2.) (1,A,C,B)

3.) (1,B,C,A)

 of the 3 disc problem is the solution of Problem (2,A,C,B)

And,The 4th Step:

4.) (1,A,B,C)

is the solution of Problem(1,A,B,C)

And the last 3 steps:

5.) (1,C,A,B)

6.) (1,C,B,A)

7.) (1,A,B,C)

is the solution of Problem(2,C,B,A)

So the solution of 3 disc problem(3,A,B,C) can be written as:

1.) (2,A,C,B)

2.) (1,A,B,C)

3.) (2,C,B,A).

and Similarly the solution of N disc problem(n,A,B,C) can be written as:

1.) (n-1,A,C,B)

2.) (1,A,B,C)

3.) (n-1,C,B,A).

So, In this way we have decomposed the problem into three parts to solve it.

Now let us say 

A-->From

B-->To

C-->Via

So the Tower of hanoid problem is (N,From,To,Via) which can be solved in three steps:

1.) (n-1,From,Via,To) -- first solve the problem of moving n-1 discs From to Via .

2.) (1,From,To,Via) -- Then solve the problem of moving 1 disc From to To.

3.) (n-1,Via,To,From) -- Then Solve the problem of moving n-1 disc from Via to To back.

We can also draw the Recursion Tree of the problem Here.

Storage Classes in C

Today I am going to explain the most important concept of C language.
If you have gone through any interview , It is quite possible that you came across the questions like:

• What do you mean by storage class in C?
• How many storage classes are there in C?
• Explain the different storage classes in C ?

So, I will be explaining the storage class concept in full detail with all its types.

Let us start by understanding What it means by a Storage class?

We know that Every variable posses the following property:

• Lifetime: Lifetime of a variable defines "till what time we can access a particular variable". 
• Scope: Scope of a variable defined "Where we can access a variable in our hundred and thousands lines of code".
• Default value: what is the default value of the variable when it is only declared that is programmer has not assigned any value to it explicitly.
• Storage place: Storage of a variable defined Where the variable is getting the memory to be accessed.

All the above properties are tied to the variables , and the specifiers consisting of these properties specify the storage class of a variable...

So, We can say that Storage class is an attribute/specifier which defines Lifetime,scope,storage and default value of a variable.

For defining different lifetime,scope,storage and default value the storage classes are categorized into 4 categories:
1.)Auto
2.)Static
3.)Extern
4.)Register

So, just by saying that this is an auto variable, a static variable , a extern variable or a register variable we are
telling about all the four properties of a variable.

Explanation of all the classes coming soon one by one.

gettid() vs pthread_self()

So we have looked at both gettid(getting the id of the thread) and the pthread_self(),Now let us join then as see the output...so the difference between then is clear...

#include<stdio.h>
#include<stdlib.h>
#include<pthread.h>
#include<linux/unistd.h>
#include<sys/syscall.h>
void* printid(void *ptr)
{
printf("The id of %s is %u\n",(char*)ptr,syscall( __NR_gettid ));
printf("The id of %s is %u\n",(char*)ptr,(unsigned int)pthread_self());
}
int main()
{
    pthread_t thread[5];
    char *msg[]={"thread1","thread2","thread3","thread4","thread5"};
    int i;
    for(i=0;i<5;i++)
    {
        pthread_create(&thread[i],NULL,printid,(void*)msg[i]);
        pthread_join(thread[i],NULL);
    }
    return 0;
}

output:

The id of thread1 is 18799

The id of thread1 is 3086543760

The id of thread2 is 18800

The id of thread2 is 3086543760

The id of thread3 is 18801

The id of thread3 is 3086543760

The id of thread4 is 18802

The id of thread4 is 3086543760

The id of thread5 is 18803

The id of thread5 is 3086543760

Explanation:

As you can see the ID generated by pthread_self() is reused by the threading implementation after the thread completion which have achieved using the join in the for loop..and the ID assigned by the kernel is unique one...

So the difference between gettid() and the pthread_self() is:

1.)POSIX thread IDs are assigned and maintained by the threading implementation. The thread ID returned by gettid() is a number (similar to a process ID) that is assigned by the kernel.

2.)ID generated by the pthread_self() can be used after the completion of the thread but  the ID genereated by the kernel can't be used even after the completion of the thread..

Getting the Thread ID In C

As we have see in the pthread_self(),the ID is implemented or maintained by threading implementation not by the kernel,so for getting the unique ID assiged by the kernel we have to use the system call...

Take a look at the example...

#include<stdio.h>
#include<stdlib.h>
#include<pthread.h>
#include<linux/unistd.h>
#include<sys/syscall.h>
void* printid(void *ptr)
{
printf("The id of %s is %u\n",(char*)ptr,syscall( __NR_gettid ));
}
int main()
{
    pthread_t thread[5];
    char *msg[]={"thread1","thread2","thread3","thread4","thread5"};
    int i;
    for(i=0;i<5;i++)
    {
        pthread_create(&thread[i],NULL,printid,(void*)msg[i]);
        pthread_join(thread[i],NULL);
    }
    return 0;
}

output:

On my system the output is:

The id of thread1 is 18622

The id of thread2 is 18623

The id of thread3 is 18624

The id of thread4 is 18625

The id of thread5 is 18626

As you can see now the IDs are different because they are assigned by the kernel not by the threading implementation...

Also look at :gettid() vs pthread_self()

pthread_self()

Getting the Thread ID..

We can get the ID of the thread by using the funciton pthread_self() on the running thread.

The main point about this function is :It uniquely identifies EXISTING threads,Here EXISTINGhas a special meaning..The meaning is pthread_self() return the value which can be reused across the program that means if you have created a thread and it completed its execution then the id of that thread can be used as the id of another thread..

Let us prove the statement that is a thread completes then the id of that thread(returned by pthread_self) can be used as the id of another thread...

#include<stdio.h>
#include<stdlib.h>
#include<pthread.h>
#include<linux/unistd.h>
#include<sys/syscall.h>
void* printid(void *ptr)
{
printf("The id of %s is %u\n",(char*)ptr,(unsigned int)pthread_self());
}
int main()
{
    pthread_t thread[5];
    char *msg[]={"thread1","thread2","thread3","thread4","thread5"};
    int i;
    for(i=0;i<5;i++)
    {
        pthread_create(&thread[i],NULL,printid,(void*)msg[i]);
        pthread_join(thread[i],NULL);
    }
    return 0;
}

output:

On my system the output is:

The id of thread1 is 3086285712

The id of thread2 is 3086285712

The id of thread3 is 3086285712

The id of thread4 is 3086285712

The id of thread5 is 3086285712

As you can see the ID's of all the thread is equal...

Explanation:I need to explain only one thing that is how to make sure that a thread completes before the execution of the next thread the answer is simple joining the thread solves our purpose..so in the for loop we create a thread then call a join so the main program waits for the thread to complete for the next iteration of the for loop..In this way we can make sure that the thread starts after the completion of the previous thread...

As the thread completes so the program can use the same ID of thread1 for the thread2 and so on....

Why so???

POSIX thread IDs are assigned and maintained by the threading implementation not by the kernel,to get the ID assigned by the kernel see here...