16.5 Multidimensional arrays

多维数组和线性数组在本质上是一样的。 因为计算机内存是线性的，它是一维数组。但是一维数组可以很容易用来表现多维的。 比如数组a[3][4]元素可以放置在一维数组的12个单元中：

  1. [0][0]
  2. [0][1]
  3. [0][2]
  4. [0][3]
  5. [1][0]
  6. [1][4]
  7. [1][5]
  8. [1][6]
  9. [2][0]
  10. [2][7]
  11. [2][8]
  12. [2][9]

该二维数组在内存中用一维数组索引表示为：

123
4567
891011

为了计算我们需要的元素地址，首先，第一个索引乘以4（矩阵宽度），然后加上第二个索引。这种被称为行优先，C/C++和Python常用这种方法。行优先的意思是：先写入第一行，接着是第二行，…，最后是最后一行。 另一种方法就是列优先，主要用在FORTRAN,MATLAB,R等。列优先的意思是：先写入第一列，然后是第二列，…，最后是最后一列。 多维数组与此类似。 我们看个例子：

Listing 16.4: simple example

  1. #include <stdio.h>
  3. int a[10][20][30];
  5. void insert(int x, int y, int z, int value)
  6. {
  7.     a[x][y][z]=value;
  8. };

16.5.1 x86

MSVC 2010：

Listing 16.5: MSVC 2010

  1. _DATA   SEGMENT
  2. COMM    _a:DWORD:01770H
  3. _DATA   ENDS
  4. PUBLIC  _insert
  5. _TEXT   SEGMENT
  6. _x$ = 8         ; size = 4
  7. _y$ = 12        ; size = 4
  8. _z$ = 16        ; size = 4
  9. _value$ = 20    ; size = 4
  10. _insert     PROC
  11.     push    ebp
  12.     mov     ebp, esp
  13.     mov     eax, DWORD PTR _x$[ebp]
  14.     imul    eax, 2400                   ; eax=600*4*x
  15.     mov     ecx, DWORD PTR _y$[ebp]
  16.     imul    ecx, 120                    ; ecx=30*4*y
  17.     lea     edx, DWORD PTR _a[eax+ecx]  ; edx=a + 600*4*x + 30*4*y
  18.     mov     eax, DWORD PTR _z$[ebp]
  19.     mov     ecx, DWORD PTR _value$[ebp]
  20.     mov     DWORD PTR [edx+eax*4], ecx  ; *(edx+z*4)=value
  21.     pop     ebp
  22.     ret     0
  23. _insert ENDP
  24. _TEXT ENDS

多维数组计算索引公式：address=6004x+304y+4z。因为int类型为32-bits（4字节），所以要乘以4。

Listing 16.6: GCC 4.4.1

  1.         public insert
  2. insert  proc near
  3. x       = dword ptr 8
  4. y       = dword ptr 0Ch
  5. z       = dword ptr 10h
  6. value   = dword ptr 14h
  7.         push    ebp
  8.         mov     ebp, esp
  9.         push    ebx
  10.         mov     ebx, [ebp+x]
  11.         mov     eax, [ebp+y]
  12.         mov     ecx, [ebp+z]
  13.         lea     edx, [eax+eax] ; edx=y*2
  14.         mov     eax, edx ; eax=y*2
  15.         shl     eax, 4 ; eax=(y*2)<<4 = y*2*16 = y*32
  16.         sub     eax, edx ; eax=y*32 - y*2=y*30
  17.         imul    edx, ebx, 600 ; edx=x*600
  18.         add     eax, edx ; eax=eax+edx=y*30 + x*600
  19.         lea     edx, [eax+ecx] ; edx=y*30 + x*600 + z
  20.         mov     eax, [ebp+value]
  21.         mov     dword ptr ds:a[edx*4], eax ; *(a+edx*4)=value
  22.         pop     ebx
  23.         pop     ebp
  24.         retn
  25. insert  endp

GCC使用的不同的计算方法。为计算第一个操作值30y，GCC没有使用乘法指令。GCC的做法是：(???? + ????) ≪ 4 − (???? + ????) = (2????) ≪ 4 − 2???? = 2 ・ 16 ・ ???? − 2???? = 32???? − 2???? = 30????。因此30y的计算仅使用加法和移位操作，这样速度更快。

16.5.2 ARM + Non-optimizing Xcode (LLVM) + thumb mode

Listing 16.7: Non-optimizing Xcode (LLVM) + thumb mode

  1. _insert
  3. value       = -0x10
  4. z           = -0xC
  5. y           = -8
  6. x           = -4
  8. ; allocate place in local stack for 4 values of int type
  9. SUB         SP, SP, #0x10
  10. MOV         R9, 0xFC2 ; a
  11. ADD         R9, PC
  12. LDR.W       R9, [R9]
  13. STR         R0, [SP,#0x10+x]
  14. STR         R1, [SP,#0x10+y]
  15. STR         R2, [SP,#0x10+z]
  16. STR         R3, [SP,#0x10+value]
  17. LDR         R0, [SP,#0x10+value]
  18. LDR         R1, [SP,#0x10+z]
  19. LDR         R2, [SP,#0x10+y]
  20. LDR         R3, [SP,#0x10+x]
  21. MOV         R12, 2400
  22. MUL.W       R3, R3, R12
  23. ADD         R3, R9
  24. MOV         R9, 120
  25. MUL.W       R2, R2, R9
  26. ADD         R2, R3
  27. LSLS        R1, R1, #2 ; R1=R1<<2
  28. ADD         R1, R2
  29. STR         R0, [R1] ; R1 - address of array element
  30. ; deallocate place in local stack, allocated for 4 values of int type
  31. ADD         SP, SP, #0x10
  32. BX          LR

非优化的LLVM代码在栈中保存了所有变量，这是冗余的。元素地址的计算我们通过公式已经找到了。

16.5.3 ARM + Optimizing Xcode (LLVM) + thumb mode

Listing 16.8: Optimizing Xcode (LLVM) + thumb mode

  1. _insert
  2. MOVW        R9, #0x10FC
  3. MOV.W       R12, #2400
  4. MOVT.W      R9, #0
  5. RSB.W       R1, R1, R1,LSL#4    ; R1 - y. R1=y<<4 - y = y*16 - y = y*15
  6. ADD         R9, PC ; R9 = pointer to a array
  7. LDR.W       R9, [R9]
  8. MLA.W       R0, R0, R12, R9     ; R0 - x, R12 - 2400, R9 - pointer to a. R0=x*2400 + ptr to a
  9. ADD.W       R0, R0, R1,LSL#3    ; R0 = R0+R1<<3 = R0+R1*8 = x*2400 + ptr to a + y*15*8 =
  10.                                 ; ptr to a + y*30*4 + x*600*4
  11. STR.W       R3, [R0,R2,LSL#2]   ; R2 - z, R3 - value. address=R0+z*4 =
  12.                                 ; ptr to a + y*30*4 + x*600*4 + z*4
  13. BX          LR

这里的小技巧没有使用乘法，使用移位、加减法等。 这里有个新指令RSB（逆向减法），该指令的意义是让第一个操作数像SUB第二个操作数一样可以应用LSL#4附加操作。 “LDR.W R9, [R9]”类似于x86下的LEA指令（B.6.2），这里什么都没有做，是冗余的。显然，编译器没有优化它。 # 位域

很多函数参数的输入标志使用了位域。当然，可以使用bool类型来替代，只是有点浪费。