Having trouble determining constants in this assembly code

Question

Consider the following source code, where R, S, and T are constants declared with #define:

int A[R][S][T]; 

int store_ele(int i, int j, int k, int *dest)
{ 

*dest = A[i][j][k]; 
 return sizeof(A); 

} 

In compiling this program, GCC generates the following assembly code:

i at %ebp+8, j at %ebp+12, k at %ebp+16, dest at %ebp+20 

1. movl 12(%ebp), %edx    //move j into register %edx 
2. leal (%edx, %edx, 8), %eax //move address %edx+%edx*9 into %eax
3. leal (%edx, %eax, 4), %eax //move address %edx + %eax*4 into %eax
4. imull $111, 8(%ebp), %edx //111*i goes into %edx
5. addl %edx, %eax 
6. addl 16(%ebp), %eax //add k to %eax
7. movl A(, %eax, 4), %edx //%eax*4 offset by address of A moved into %edx 
8. movl 20(%ebp), %eax 
9. movl %edx, (%eax) 
10. movl $888, %eax 

I know that the last instruction 'movl $888, %eax' says that there are 888 bytes which is equivalent to 222 ints (i * j * k). As you can see I know what each instruction is doing but I am having difficulties reverse engineering this to determine the constants that are being passed into i, j and k.

I am not expecting answers but any hints to point me in the right direction would be greatly appreciated

Answer 1

The give-away is: i * 111 = i * 3 * 37. Earlier the 2 LEA instructions combine to set eax = 37 * j. Adding k to sum: eax = 3 * 37 * i + 37 * j + k. Since int is 4 bytes, and the array size is 888 bytes, the array has 222 elements. The array dimensions are an ordering of the primes: {2,3,37}

To expand:

edx <- j
eax <- edx + 8 * edx = 9.j
eax <- edx + 4 * eax = j + 4 * 9j = 37.j

edx <- i * 111 = 3 * 37.i
eax <- eax + edx = 3 * 37.i + 37.j
eax <- eax + k = 3 * 37.i + 37.j + k

---

Clearly, (i == 2) puts us at element A[222], which is out of range. So assuming (i,j,k) corresponds to (R,S,T), we have: R = 2, where: (i < 2)

Similarly, (j == 36) yields an index of at least (36 * 37 = 1332), so it must correspond to the prime: S = 3, where: (j < 3) - which leaves: T = 37, where: (k < 37).

Therefore we have the array: A[2][3][37], where: (i < 2, j < 3, k < 37)

In general the index is: ((((i * S) + j) * T) + k), where: (i < R, j < S, k < T)