3.64 Multiple Dimension Array I

★★★

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

long A[R][S][T];

long store_ele(long i, long j, long k, long *dest) {
    *dest = A[i][j][k];
    return sizeof(A);
}

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

; i in %rdi, j in %rsi, k in %rdx, dest in %rcx
store_ele:
    leaq     (%rsi,%rsi,2), %rax    ; Compute 3*j
    leaq     (%rsi,%rax,4), %rax    ; Compute 13*j
    movq     %rdi, %rsi             ; Move i to %rsi
    salq     $6, %rsi               ; Compute 64*i
    addq     %rsi, %rdi             ; Compute 65*i
    addq     %rax, %rdi             ; Compute 65*i + 13*j
    addq     %rdi, %rdx             ; Compute 65*i + 13*j + k
    movq     A(,%rdx,8), %rax       ; Compute 8*(65*i + 13*j + k)
    movq     %rax, (%rcx)           ; Retrive A[i][j][k] to %rcx
    movl     $3640, %eax            ; Compute sizeof(A) = 8 * R * S * T
    ret

A. Extend Equation 3.1 from two dimensions to three to provide a formula for the location of array element A[i][j][k].

$$\&A[i][j][k]=x_d+L\cdot(i\cdot S\cdot T+j\cdot T+k)$$

B. Use your reverse engineering skills to determine the values of R, S, and T based on the assembly code.

From the code we know that S*T=65, T=13, and R*S*T=455, so S=5, T=13, and R=7.