algorithm - 程序集处理三角矩阵存储器的算法

Question

我在ASM做一个关于pascal三角的项目，用NASM
所以在这个项目中你需要计算从0到63的帕斯卡三角形
我的第一个问题是在哪里存储计算结果->内存
第二个问题我在内存中使用什么类型的存储，为了理解我的意思，我有三种方法，首先声明一个完整的矩阵，如下所示

memoryLabl:  resd 63*64     ; 63 rows of 64 columns each

但是这样的问题是，一半的矩阵没有被使用，这使得我的程序没有效率，所以让我们走，第二种方法是可用的
为每一行声明一个内存标签
例如：

line0: dd   1
line1: dd  1,1
line2: dd 1,2,1      ; with pre-filled data for example purposes
...
line63: resd 64      ; reserve space for 64 dword entries

这样做就像用手做一样，
类中的其他一些尝试使用宏，如您所见 here
但我不明白
到现在为止，一直都还不错
让我们看看我用过的最后一个
就像第一个，但我用的是三角形矩阵，怎么样，
只声明我需要的内存量
所以为了存储0到63行的pascal三角形，它给了我一个三角形矩阵，因为每一个新行我添加一个单元格
我已经为三角形矩阵分配了2080 dword，这是怎么回事？是吗？
以2080 dword解释：

                okey we have line0 have 1 dword /* 1 number in first line */
                             line1 have 2 dword /* 2 numbers in second line */
                             line2 have 3 dword /* 3 numbers in third line */
                             ...
                             line63 have 64 dword /* 64 numbers in final line*/
                  so in the end we have 2080   as the sum of them 

我给了每一个数字
好了，现在我们已经创建了存储结果的内存，让我们开始计算
第一个#在pascal三角形中，第0行中的所有单元格都有值1
我将用伪代码执行此操作，以便您理解我如何在第0行的所有单元格中放置一个：

s=0
for(i=0;i<64;i++):
     s = s+i
     mov dword[x+s*4],1   /* x is addresses of  triangle matrices */

帕斯卡三角形的第二部分是每行的最后一行等于1
我将使用伪代码来简化它

s=0
for(i=2;i<64;i++):
     s = s+i
     mov dword[x+s*4],1

我从i开始等于2，因为i=0（i=1）是line0（line1），而line0（line1）是full，因为正如我在上面的解释中所说，它只包含一个（tow）值
所以这两个伪代码将使我的矩形看起来像是在内存中：

1
1  1
1      1
1          1
1             1
1                 1
1                     1
1                         1
1                              1
1                                 1
...
1                                        1

现在最困难的部分是使用三角形中的这个值来填充所有三角形单元格的计算
让我们从这里开始

let's take cell[line][row]

we have cell[2][1] = cell[1][0]+cell[1][1]
and     cell[3][1]= cell[2][0]+cell[2][1]
        cell[3][2]= cell[2][1]+cell[2][2]

in **general** we have 
        cell[line][row]= cell[line-1][row-1]+cell[line-1][row]

我的问题我不能用asm指令破坏这种关系，因为我有一个
使用奇怪的三角形矩阵，有谁能帮我用关系或非常基本的伪代码或asm代码来打破它？

Answer 1

TL:DR：您只需要顺序遍历数组，这样就不必计算索引。见第二节。
要随机访问index into a (lower) triangular matrix，行r在大小为r-1的三角形之后开始。一个n大小的三角形有n*(n+1)/2总元素，使用Gauss's formula for the sum of numbers from 1 to n-1所以一个三角形的尺寸r-1有(r-1)*r/2元素一旦知道行的起始地址，在行中对列进行索引当然是微不足道的。
每个DWORD元素都有4个字节宽，我们可以在乘法过程中处理这个比例，因为lea lets us shift and add并将结果放入不同的寄存器中我们将n*(n-1)/2 elements * 4 bytes / elem简化为n*(n-1) * 2 bytes。
上面的推理适用于基于1的索引，其中行1具有1个元素。如果要在计算之前添加1行索引，那么我们需要调整为零，因此我们需要三角形的大小。
具有r+1 - 1行，因此r*(r+1)/2 * 4 bytes。它有助于将线性数组索引放入三角形中，以便快速复查公式

 0
 4   8
12  16  20
24  28  32  36
40  44  48  52  56
60  64  68  72  76  80
84  88  92  96 100  104  108

第四行，我们称之为“第3行”，从整个数组的开头开始24字节。这就是 (3+1)*(3+1-1) * 2= (3+1)*3 * 2；是的， r*(r+1)/2公式有效。

;; given a row number in EDI, and column in ESI (zero-extended into RSI)
;; load triangle[row][col] into eax

lea    ecx, [2*rdi + 2]
imul   ecx, edi                        ; ecx = r*(r+1) * 2 bytes

mov    eax, [triangle + rcx + rsi*4]

假设32位绝对寻址正常（ 32-bit absolute addresses no longer allowed in x86-64 Linux?）。如果不是，则使用RIP相对LEA获取寄存器中的 triangle基址，并将其添加到 rsi*4 x86 addressing modes当其中一个是常数时，只能有3个分量。但这里的静态 triangle就是这种情况，因此我们可以充分利用这个优势，使用列的缩放索引，并使用base作为计算的行偏移量，使用实际的数组地址作为位移。
计算三角形
这里的技巧是，您只需要按顺序循环它；您不需要随机访问给定的行/列。
你在写下面这一行的时候读了一行当到达行的末尾时，下一个元素就是下一行的开始当您沿着行向下移动时，源指针和目标指针之间的距离会越来越远，因为目标指针总是在前面整整一行。您知道行的长度=行号，所以您可以实际使用行计数器作为偏移量。

global _start
_start:
    mov  esi, triangle         ; src = address of triangle[0,0]
    lea  rdi, [rsi+4]          ; dst = address of triangle[1,0]

    mov  dword [rsi], 1      ; triangle[0,0] = 1  special case: there is no source
.pascal_row:                   ; do {
    mov  rcx, rdi               ; RCX = one-past-end of src row = start of dst row
    xor  eax, eax               ; EAX = triangle[row-1][col-1] = 0 for first iteration
    ;; RSI points to start of src row: triangle[row-1][0]
    ;; RDI points to start of dst row: triangle[row  ][0]
  .column:
     mov   edx, [rsi]           ; tri[r-1, c]           ; will load 1 on the first iteration
     add   eax, edx             ; eax = tri[r-1, c-1] + tri[r-1, c]
     mov  [rdi], eax            ; store to triangle[row, col]

     add  rdi, 4                ; ++dst
     add  rsi, 4                ; ++src
     mov  eax, edx              ; becomes col-1 src value for next iteration

     cmp  rsi, rcx
     jb   .column              ; }while(src < end_src)

    ;; RSI points to one-past-end of src row, i.e. start of next row = src for next iteration
    ;; RDI points to last element of dst row  (because dst row is 1 element longer than src row)

    mov  dword [rdi], 1        ;  [r,r] = 1   end of a row
    add  rdi, 4                ;  this is where dst-src distance grows each iteration

    cmp  rdi, end_triangle
    jb  .pascal_row

       ;;; triangle is constructed.  Set a breakpoint here to look at it with a debugger

    xor   edi,edi
    mov   eax, 231
    syscall               ; Linux sys_exit_group(0), 64-bit ABI



section .bss

; you could just as well use  resd 64*65/2
; but put a label on each row for debugging convenience.

ALIGN 16
triangle:
%assign i 0
%rep    64
    row %+ i:  resd  i + 1
%assign i i+1
%endrep
end_triangle:

我测试了这个，它工作了：在内存中正确的值，它停在正确的位置但是请注意，整数溢出发生在下一行之前如果使用64位整数（只需更改寄存器名称和偏移量，不要忘记 resd到 resq），就可以避免这种情况。64选择32是1832624140942590534=2^60.66。
用于保留空间并将每一行标记为 %rep、 row0等的 row1块来自 my answer to the question you linked about macros，比imo的另一个答案要理智得多。
你标记了这个NASM，所以这就是我使用的，因为我很熟悉它。您在问题中使用的语法是masm（直到最后一次编辑）。MASM中的主逻辑是相同的，但是请记住，您需要偏移三角形来获取作为立即数的地址，而不是从中加载。
我使用x86-64是因为32位已经过时了，但是我避免了太多的寄存器，所以如果需要的话，可以很容易地将它移植到32位。如果你把它放在一个函数而不是一个独立的程序中，不要忘记保存/恢复保留调用的寄存器。
展开内部循环可以节省一些复制寄存器的指令以及循环开销。这是一个有点优化的实现，但我主要将其局限于使代码更简单、更小/更快的优化。（除了使用指针增量代替索引）之外，还花了一段时间使它变得简洁明了。：p页
在不同的CPU上执行数组索引的不同方法会更快。例如，对于内部循环中的负载，可能使用索引寻址模式（相对于 dst），因此只需要一个指针增量但如果你想让它跑得快，SSE2或AVX2 vpaddd可能是好的。使用 palignr洗牌可能有用，但也可能是未对齐的加载，而不是某些洗牌，特别是使用AVX2或AVX512。
但不管怎样，这是我的版本；我不是想用你的方式来写，你需要为你的作业写你自己的我是为未来的读者写的，他们可能会学到一些关于x86的有效性的东西。（另请参见 the x86 tag wiki中的性能部分）
我是怎么写的：
我开始从顶部开始编写代码，但很快意识到off by one错误将是一个棘手的问题，我不想只是在特殊情况下用循环中有分支的愚蠢方式编写代码。
最终的帮助是在内部循环的指针上为pre和post条件编写注释。这说明我需要用 eax=0来进入循环，而不是用 eax=1来存储eax作为循环中的第一个操作，或者类似的东西。
显然每个源值只需要读取一次，所以我不想编写一个读取 [rsi]和 [rsi+4]或其他内容的内部循环此外，这将使边界条件变得更加困难（其中非存在值必须读取为0）。
我花了一些时间来决定是否要在一个寄存器中为行长度或行号设置一个实际的计数器，最后我只为整个三角形使用了一个结束指针在我完成之前，不明显的是使用纯指针增量/比较会保存这么多指令（当上限是构建时间常数（如 end_triangle）时会保存寄存器），但它运行得很好。