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 engineeri…

Accepted Answer

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)`

Having trouble determining constants in this assembly code

Solution

Problem