0

I have to use the assembly code to find the value of P. How do I read this? I am not quite sure how to begin. If anyone could help me by either going through it step by step or just explaining it to me. Either way would be a big help

in C:

#define P ?
#define Q ?
int mat1[P][Q];
int mat2[Q][P];
void copy_element( int i, int j) {
     mat1[ i ][ j ] = mat2[ j ][ i ];

in assembly:

copy_element:
    movslq %edi, %rdi
    movslq %esi, %rsi
    movq   %rsi, %rax
    salq   $4, %rax
    subq   %rsi, %rax
    addq   %rdi, %rax
    movl   mat2(,%rax,4), %ecx
    leaq   (%rdi, %rdi, 4), %rdx
    leaq   0(, %rdx, 4), %rax
    addq   %rax, %rsi
    movl   %ecx, mat1,(,%rsi,4)
    ret

My full try:

copy_element:
    movslq %edi, %rdi             ?(rdi = i)
    movslq %esi, %rsi             (rsi = j)
    movq   %rsi, %rax             (rax = j)
    salq   $4, %rax               (rax = 16j)
    subq   %rsi, %rax             (rax = 15j)
    addq   %rdi, %rax             (rax = 15j + i)?
    movl   mat2(,%rax,4), %ecx    (ecx = 60j + 4i)?
    leaq   (%rdi, %rdi, 4), %rdx  (rdx = 5i)
    leaq   0(, %rdx, 4), %rax     (rax = 20i)? or maybe (rax = 15j + 21i)?
    addq   %rax, %rsi             (rsi = j + 20i)
    movl   %ecx, mat1,(,%rsi,4)   what?? (? = 64j + 80i)
    ret

P = 60 and Q = 80?

or are they P = 15 and Q = 20?

of course both could be wrong

(I am sorry if this question is bothersome or if I didn't do something correctly.)

BOB
  • 1
  • 5
  • Well, do you understand the instructions? Comment the lines with what they do. Work out the formula then compare with the layout of arrays. – Jester Nov 04 '22 at 18:08
  • @Jester I am very bad at assembly unfortunately :/. I understand leaq, addq, and subq and only when it's basic with like three lines of assembly code. – BOB Nov 04 '22 at 18:13
  • You might want to double check that assembly code, looks like there are 1 or 2 typos. For example, we don't `leaq` into `ecx`. That's not only a size mismatch, but the wrong register, thinking it should be `rdx`. – Erik Eidt Nov 04 '22 at 18:21
  • @ErikEidt thanks, I have now fixed hopefully everything. Still don't understand much but thanks for the answer and comment :) – BOB Nov 04 '22 at 18:28
  • Can you figure our what factor is used for muliplying `j` for the `mat2` expression? It is doing a fancy shift and subtract sequence! Start with the shift alone: what does that multiply by? – Erik Eidt Nov 04 '22 at 18:31
  • My guess would be rsi = j, then rax = j, then you shift with 4 (don't know what that does), you take one j of the shifted variable and then add i to it? then you move the newest version of j, multiplied by 4, to %ecx. Thats what I got @ErikEidt – BOB Nov 04 '22 at 18:38
  • Yes, it is doing `(j<<4)-j`. That shift multiplies by a power of 2. So study such shifting and then you'll have something like `j×?-j` left to reason out. – Erik Eidt Nov 04 '22 at 18:41
  • @ErikEidt So I get 15j. Then I have to addq rdi or i (I think) to it. So rax = 15j + i? – BOB Nov 04 '22 at 18:44
  • Duplicate of [Reverse engineer array dimensions from code indexing int arrays?](https://stackoverflow.com/q/69847322) (except for the exact numbers), but it was only answered in comments. Near duplicate of [Finding the dimensions of an array through assembly](https://stackoverflow.com/q/39550678) and [Reverse engineer array dimensions / struct layout from compiler asm output?](https://stackoverflow.com/q/33603082) (although that one spends time on struct layout). Also [Reverse engineering and interpreting assembly code](https://stackoverflow.com/q/67732896) – Peter Cordes Nov 04 '22 at 19:18
  • @PeterCordes Is my try on the right track? That P = 15 and Q = 20 or am I wrong – BOB Nov 04 '22 at 19:30
  • @Jester perhaps? Can anyone shed some light on this situation? I have been trying for long but still have no idea what the answer is – BOB Nov 05 '22 at 16:57
  • Since you have accepted Erik's answer we assumed you solved the problem. – Jester Nov 05 '22 at 17:16
  • @Jester I am new here and I am adjusting to the rules and format of this site. I have not solved the problem. I have no idea if the answer is P = 15 and Q = 20 or 60 and 80 or something completely else. If someone could give me the answer so I can go through it and understand why the answer is what it is I could perhaps understand Assembly a bit more – BOB Nov 05 '22 at 17:25
  • Yes you got the P=15 and Q=20 right. Any questions still? – Jester Nov 05 '22 at 17:49
  • Thank you very much. I have been trying this for hours since I posted this yesterday. I have been just so confused but I am glad that I understand this correctly, if only the bare minimum. Since you asked does the "leaq 0(, %rdx, 4), %rax" (line 10) give rax a new value. I assume so since 15 and 20 is correct. I was just wondering if it overwrites the previous value or adds on? – BOB Nov 05 '22 at 17:54
  • It overwrites `rax`. – Jester Nov 05 '22 at 17:58

2 Answers2

1

The mat1 expression is on the left of the = sign, meaning it is the target of the assignment, while the mat2 expression is fetching the value to be used in that assignment.

We know that mat1 will be a memory write, and that first it will have to do a memory read for mat2.

We also know that for mat2 it needs to compute(j×P+i)×4, and for mat1, (i×Q+j)×4.

We also know that i is in edi and j is in esi upon function entry.

These facts and the assembly code are sufficient to reason out P and Q.

Erik Eidt
  • 23,049
  • 2
  • 29
  • 53
0

not an answer but enable optimizations to remove the noise. Also change int indexes to the correct type size_t

        imulq   $100, %rdi, %rax
        addq    %rsi, %rax
        imulq   $10, %rsi, %rsi
        addq    %rdi, %rsi
        movl    mat2(,%rsi,4), %edx
        movl    %edx, mat1(,%rax,4)
        ret

https://godbolt.org/z/hb54f1x6x

or

        leaq    (%rsi,%rsi,4), %rdx
        leaq    (%rdi,%rdi,4), %rax
        leaq    (%rdi,%rdx,2), %rdx
        leaq    (%rax,%rax,4), %rax
        movl    mat2(,%rdx,4), %edx
        leaq    (%rsi,%rax,4), %rax
        movl    %edx, mat1(,%rax,4)
        ret
0___________
  • 60,014
  • 4
  • 34
  • 74
  • I think the OP has the assembly output, but not the values of P and Q, which they're trying to find by looking at the assembler. – psmears Nov 04 '22 at 19:20
  • @psmears: Correct. This would only help to simplify the 2nd asm block in the question, where they're compiling their C attempt into asm to compare against the original asm. But those were already compiled with some optimization level, since they don't spill/reload their incoming stack args. Using the same compiler with the same `-O1` or something will make asm that's actually the same if you get the right answer. (Or more similar if it's a different GCC version). – Peter Cordes Nov 04 '22 at 19:25
  • @psmears yhea, you're right I am only trying to find the value of p and q. My answer atm is p = 15 and Q = 20. I am an absolute noob when it comes to assembly. I did well in datalab but got lost in assembly. – BOB Nov 04 '22 at 20:38