Find the dimensions of an array from assembly code

Question

I always seem to get these types of questions wrong. I figure out the correct values, but I always have them reversed. For this problem the correct answer is H = 15 and J = 7 but I had them reversed as usual...

Can someone walk me through their thought process of how to solve these questions?

Array indexing.
Consider the C code below, where H and J are constants declared with
#define
.
int array1[H][J];

int array2[J][H];

void copy_array(int x, int y) {

array2[y][x] = array1[x][y];

}

Suppose the above C code generates the following x86-64 assembly code:
# On entry:
# %edi = x
# %esi = y
#
copy_array:

movslq %edi,%rdi

movslq %esi,%rsi

movq %rsi, %rdx

salq $4, %rdx

subq %rsi, %rdx

addq %rdi, %rdx

leaq 0(,%rdi,8), %rax

subq %rdi, %rax

addq %rsi, %rax

movl array1(,%rax,4), %eax

movl %eax, array2(,%rdx,4)

ret

What are the values of H and J ?

Thank you!

Answer 1

Adding comments will always help. The "trick" is that computing the addresses of the array elements must involve multiplying by the 2d array row length. You just need to figure out those multipliers:

# On entry:
# %edi = x
# %esi = y
copy_array:
movslq %edi,%rdi           ; %rdi = x
movslq %esi,%rsi           ; %rsi = y
movq %rsi, %rdx            ; %rdx = y
salq $4, %rdx              ; %rdx *= 16
subq %rsi, %rdx            ; %rdx -= y (so now %rdx = 15 * y)
addq %rdi, %rdx            ; %rdx += x (so now %rdx = 15 * y + x)
leaq 0(,%rdi,8), %rax      ; %rax = 8 * x
subq %rdi, %rax            ; %rax -= x (so now %rax = 7 * x)
addq %rsi, %rax            ; %rax += y (so now %rax = 7 * x + y)
movl array1(,%rax,4), %eax ; %rax = array1[7 * x + y]
movl %eax, array2(,%rdx,4) ; array2[15 * y + x] = %rax
ret

Now since C arrays are stored in row major order, the rows of array1 must be 7 elements long (i.e. the array has 7 columns) and those of array2 are 15 (i.e. it has 15 columns). This means J = 7 and H = 15 as you said in your question.

Answer 2

C and C++ do not pass information about the array (other than its address) to functions.

Many other programming languages pass array descriptors.

H and J cannot be determined by the function being called.

If you're looking for the specific values in this specific instance, then this code is designed to be a puzzler; deliberately obscured assembly language.

You need to walk though every instruction and figure out what is being done.

For example this sequence look like it multiplies the contents if rsi by 15.

movq %rsi, %rdx

salq $4, %rdx

subq %rsi, %rdx

Go through line by line. This code is not designed for programming but as some kind of test.