Link to home
Start Free TrialLog in
Avatar of lecos
lecos

asked on

matrix assembly problem

Fill the blanks of the corresponding C source code.

struct matrix_entry {

    .... a;
    .... b;
    int  c;
    .... d;
 
   };


struct matrix_entry matrix[2][5];

int return_entry (int i, int j){

return matrix[i][j].c ;

}
 
complete the above definition of matrix_entry so that the following assembly code could be generated
from it on a linux/x86 machine:


return entry:

1     pushl     %ebp
2     movl      %esp,  %ebp
3     movl      8(%ebp) , %eax
4     leal     (%eax, %eax ,4) , %eax
5     addl      12(%ebp), %eax
6     sall      $4 , %eax
7     movl      matrix + 4(%eax), %eax
8     movl      %ebp , % esp
9     popl      %ebp
      ret      

consider
         size    alignment  (bytes)
char       1         1
short      2         2
int        4         4
double     8         4
Avatar of Infinity08
Infinity08
Flag of Belgium image

As usual, you should start by figuring out what each instruction does, and how it corresponds to the C code.
Avatar of lecos
lecos

ASKER


this is my rought understanding of this questions, please make some comments. I have an exam tomorrow , and i think i learn more from looking at examples. thank you.

return entry:

1     pushl     %ebp
2     movl      %esp,  %ebp
3     movl      8(%ebp) , %eax                       //  i is stored in %eax  //
4     leal     (%eax, %eax ,4) , %eax            //     %eax = 5i //
5     addl      12(%ebp), %eax                      //     %eax = j + 5i //
6     sall      $4 , %eax                                     //   %eax =  16 ( j + 5i)  //
7     movl      matrix + 4(%eax), %eax          // not sure what is happening here....explain plz , I don't know how to deduct the                  
8     movl      %ebp , % esp                                                byte size of a ,  b , c , d  //  
9     popl      %ebp                                             // i believe that the %eax will return the value of "d " //
      ret      





struct matrix_entry {

    .... a;
    .... b;
    int  c;
    .... d;
 
   };


struct matrix_entry matrix[2][5];   ( this is a matrix  of 2 X 5 )

int return_entry (int i, int j){          ( these 2 values will be called inside this function)

return matrix[i][j].c ;                     ( i have no clue where the value "c" is coming from , how is it obtained?)

}






>> 7     movl      matrix + 4(%eax), %eax          // not sure what is happening here....explain plz , I don't know how to deduct the        

matrix is the base address of the array.
4(%eax) is the same as *(4 + %eax).

Combined that would give something like *(matrix + eax + 4)


>> 9     popl      %ebp                                             // i believe that the %eax will return the value of "d " //

It will most definitely return the data member c of the matrix_entry object at position (i, j) in the array.

Given that knowledge, you should be able to derive the sizes of each of the data members.

Start by figuring out what the size of the struct is.
Avatar of lecos

ASKER

>> 7     movl      matrix + 4(%eax), %eax          // not sure what is happening here....explain plz , I don't know how to deduct the        

matrix is the base address of the array.
4(%eax) is the same as *(4 + %eax).

Combined that would give something like *(matrix + eax + 4)


>> 9     popl      %ebp                                             // i believe that the %eax will return the value of "d " //

It will most definitely return the data member c of the matrix_entry object at position (i, j) in the array.

Given that knowledge, you should be able to derive the sizes of each of the data members.

Start by figuring out what the size of the struct is.


@@@ the size of the array is 4 bytes but I really dont know how to derive the size of the struct.

where is "d" located???  
>> @@@ the size of the array is 4 bytes

Why do you think the size of the array is 4 bytes ?

The size of the array = 2 * 5 * sizeof(struct matrix_entry)


>> where is "d" located???  

What do you mean ? 'd' is the fourth data member of the matrix_entry struct :

>> struct matrix_entry {
>> 
>>     .... a;
>>     .... b;
>>     int  c;
>>     .... d;                     <------------ Right here
>> 
>>    };
Avatar of lecos

ASKER

>> @@@ the size of the array is 4 bytes

Why do you think the size of the array is 4 bytes ?

The size of the array = 2 * 5 * sizeof(struct matrix_entry)

isn't the size of the array 2 X 5(2 rows , 5 columns) ?  where is the sizeof (struct matrix_entry)


>> where is "d" located???  

What do you mean ? 'd' is the fourth data member of the matrix_entry struct :

>> struct matrix_entry {
>> 
>>     .... a;
>>     .... b;
>>     int  c;
>>     .... d;                     <------------ Right here
>> 
>>    };

well , I meant that I dont know how to come up with the size of "d". Is this value expressed anywhere in the assembly code ?  I really struggling visualizing how the struct and array are working.
If you know of a website with similar examples or good definitions please let me know.By the way. thanks for the help and patience. = )
 
>> isn't the size of the array 2 X 5(2 rows , 5 columns) ?  where is the sizeof (struct matrix_entry)

there are 2 * 5 items in the array, and each item in the array has a size sizeof(struct matrix_entry). So, that gives a total array size of 2 * 5 * sizeof(struct matrix_entry).


>> well , I meant that I dont know how to come up with the size of "d".

The first step, as I said earlier, is to figure out the size of the entire struct, ie. sizeof(struct matrix_entry)


>> Is this value expressed anywhere in the assembly code ?

Not directly, no. But there is enough information provided to derive it.


>> I really struggling visualizing how the struct and array are working.

Ok. Let's start with a struct. A struct is a group of values (with a certain type), in a certain order.
These values are laid out inside the struct as follows :

(a) the first value begins right at the start of the struct, and has a certain size (corresponding to the size of its type).
(b) any subsequent value is located after the previous value, with possible alignment considerations. For example, if the value has to be 4-byte aligned, it means it has to start at a memory address that is a multiple of 4.

The total size of the struct is the sum of all sizes of its members, plus any padding between the members, and at the end of the struct (for alignment considerations).

Next, an array is simpler. There is no padding in an array. All items in the array are simply placed in memory one after the other, in row major order. Row major order means that the first row is placed in memory first, then the second row, etc.


You might want to read up on structs and arrays to get a better understanding.

        http://cplusplus.com/doc/tutorial/structures/
        http://cplusplus.com/doc/tutorial/arrays/
Avatar of lecos

ASKER

alright, let me see if I got this right.


>> isn't the size of the array 2 X 5(2 rows , 5 columns) ?  where is the sizeof (struct matrix_entry)

there are 2 * 5 items in the array, and each item in the array has a size sizeof(struct matrix_entry). So, that gives a total array size of 2 * 5 * sizeof(struct matrix_entry).

OK , SO  I GET THAT AN ITEM IN THE ARRAY WILL HAVE THE SIZE OF (a +b+c+d)


>> well , I meant that I dont know how to come up with the size of "d".

The first step, as I said earlier, is to figure out the size of the entire struct, ie. sizeof(struct matrix_entry)


I SUPPOSE I NEED TO FIND THE TOTAL VALUE FROM THE CODE.


>>.Ok. Let's start with a struct. A struct is a group of values (with a certain type), in a certain order.
These values are laid out inside the struct as follows :

(a) the first value begins right at the start of the struct, and has a certain size (corresponding to the size of its type).
(b) any subsequent value is located after the previous value, with possible alignment considerations. For example, if the value has to be 4-byte aligned, it means it has to start at a memory address that is a multiple of 4.


The total size of the struct is the sum of all sizes of its members, plus any padding between the members, and at the end of the struct (for alignment considerations).

OK, I GET THIS TOO.  IN THIS CASE THE STRUCT HAS THE VALUES a , b, c and d.  I UNDERSTAND THE PADDING CONCEPT AS WELL.


Next, an array is simpler. There is no padding in an array. All items in the array are simply placed in memory one after the other, in row major order. Row major order means that the first row is placed in memory first, then the second row, etc.

OK, I HAVE A BASIC UNDERSTANDING OF ARRAYS AND STRUCTS NOW. BUT IM STILL HAVING PROBLEMS WITH THIS.



return entry:

1     pushl     %ebp
2     movl      %esp,  %ebp
3     movl      8(%ebp) , %eax                       //  i is stored in %eax  //
4     leal     (%eax, %eax ,4) , %eax            //     %eax = 5i //
5     addl      12(%ebp), %eax                      //     %eax = j + 5i //
6     sall      $4 , %eax                                     //   %eax =  16 ( j + 5i)  //
7     movl      matrix + 4(%eax), %eax          //      %eax = *(matrix + 16(j +5i) + 4)    ,  Not completely sure what this tells me                                                                                                                                                        

                                                                                                                                                                         please explain //


8     movl      %ebp , % esp                                        

9     popl      %ebp                                             //  the value of "c" will be returned here    //
      ret      



>> OK , SO  I GET THAT AN ITEM IN THE ARRAY WILL HAVE THE SIZE OF (a +b+c+d)

You also have to add any padding between them, as well as at the end of the struct, to ensure alignment requirements.


>> I SUPPOSE I NEED TO FIND THE TOTAL VALUE FROM THE CODE.

Yes. It is there in your first analysis (see your post http:#31783450).


>> %eax = *(matrix + 16(j +5i) + 4)

That's correct. And together with the extra information in the question, this is all you need to know to figure out all needed sizes.

The formula is the calculation to get to the exact address of the 'c' member of the struct at position 'j' on row 'i' in the 'matrix' array.

Maybe it's useful to try to derive this formula yourself (forget about the above formula for a second). Suppose you have the base address of the 'matrix' array. How would you get the address of the 'c' member of the struct at position 'j' on row 'i' in the 'matrix' array ? What formula would you use ?
Avatar of lecos

ASKER

OK..... i think I got it now.


%eax = *(matrix + 16(j +5i) + 4).................the size of the items in the array is 16 bytes.


from &D [i] [j] = Xd + L (Ci + j                so L = 16 bytes  


 >>  7   movl      matrix + 4(%eax), %eax          //      %eax = *(matrix + 16(j +5i) + 4)    

from here i think you can tell that the offset for  "c"  will be 4 bytes. But Im not completely sure.

please explain this , if possible



So if  offsett of c = 4 bytes , then a and b could be 2 char with padding or 2 short , "d" will be a double. Then the addition will result in 16 bytes total.                                                                                                                                                  
ASKER CERTIFIED SOLUTION
Avatar of Infinity08
Infinity08
Flag of Belgium image

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
Avatar of lecos

ASKER



Hey thanks for the help , and all the comments. I'm feeling much better about this test i have tomorrow.
You should. You seem to have a good grasp of what's going on behind the scenes. Go ace that test ! ;)