使用汇编寻址三角矩阵内存的算法
algorithm of addressing a triangle matrices memory using assembly
我在 ASM 中使用 NASM
做一个关于帕斯卡三角形的项目
所以在项目中你需要计算第0行到第63行的帕斯卡三角形
我的第一个问题是计算结果存放在哪里->内存
第二个问题我在内存中使用什么类型的存储，为了理解我的意思我有3种方式首先声明一个完整矩阵所以会像这样
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
这种做法就像手工一样，
class 中的一些其他人尝试使用宏
但我不明白
到目前为止还不错
让我们转到我用过的最后一个
这就像第一个，但我使用 triangle matrices ，怎么样，
通过仅声明我需要的内存量
所以要存储 Pascal 三角形的第 0 行到第 63 行，它会给我一个三角形矩阵，因为我在每一个新行中添加一个单元格
我已经为三角矩阵分配了 2080 个双字，这是怎么回事？？
按 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
我给每个数字1个双字
okey 现在我们已经创建了内存来存储结果让我们开始计算
first# 在帕斯卡三角形中，行 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) 已满，因为正如我在上面的解释中所说，它只包含一个（拖）值
所以这两个伪代码将使我的矩形在内存中看起来像 :
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 代码来打破它吗？
TL:DR: 你只需要顺序遍历数组，所以你不必计算索引。见第二部分。
要随机访问index into a (lower) triangular matrix, row r starts after a triangle of size r-1. A triangle of size n has n*(n+1)/2 total elements, using Gauss's formula for the sum of numbers from 1 to n-1。所以大小为 r-1 的三角形有 (r-1)*r/2 个元素。一旦我们知道行开始的地址，在一行中索引一列当然是微不足道的。
每个 DWORD 元素都是 4 个字节宽，我们可以在乘法中处理缩放，因为 并将结果放在不同的寄存器中。我们将 n*(n-1)/2 elements * 4 bytes / elem 简化为 n*(n-1) * 2 bytes.
以上推理适用于基于 1 的索引，其中第 1 行有 1 个元素。如果我们想要 zero-based 索引，我们必须通过在计算之前将行索引加 1 来对此进行调整，因此我们需要三角形的大小
有 r+1 - 1 行，因此 r*(r+1)/2 * 4 bytes。将线性数组索引放入三角形有助于快速double-check公式
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
第 4 行，我们称为 "row 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?). If not, use a RIP-relative LEA to get the triangle base address in a register, and add that to rsi*4. 只能有 3 个组件，当其中一个是常量时。但是 是 这里的情况您的静态 triangle，因此我们可以通过对列使用缩放索引，将基数用作计算的行偏移量，将实际数组地址用作位移来充分利用。
计算三角形
这里的技巧是你只需要顺序循环;您不需要随机访问给定的 row/column.
您在写下一行的同时阅读了一行。 当您到达一行的末尾时，下一个元素是下一行的开始。随着行的向下移动，源指针和目标指针之间的距离会越来越远，因为目的地总是提前一整行。而且你知道一行的长度=行号，所以你实际上可以使用行计数器作为偏移量。
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.
保留space并将每一行标记为row0、row1等的%rep块来自，比IMO 的另一个答案。
你标记了这个 NASM，所以我使用它，因为我熟悉它。您在问题中使用的语法是 MASM（直到最后一次编辑）。主要逻辑在 MASM 中是相同的，但请记住，您需要 OFFSET 三角形来立即获取地址，而不是从中加载。
我使用 x86-64 因为 32 位已经过时，但我避免了太多的寄存器，因此如果需要，您可以轻松地将其移植到 32 位。如果你把它放在一个函数而不是 stand-alone 程序中，不要忘记 save/restore call-preserved 寄存器。
展开内部循环可以节省一些复制寄存器的指令，以及循环开销。这是一个稍微优化的实现，但我主要将其限制为使代码 更简单 以及更小/更快的优化。 （除了可能使用指针增量而不是索引。）让它变得如此干净和简单花了一些时间。 :P
不同的数组索引方式在不同的 CPU 上会更快。例如可能对内部循环中的负载使用索引寻址模式（相对于 dst），因此只需要一个指针增量。但是如果你想让它 运行 快，SSE2 或 AVX2 vpaddd 可能不错。使用 palignr 混排可能有用，但也可能是未对齐的加载而不是某些混排，尤其是对于 AVX2 或 AVX512。
但无论如何，这是我的版本；我不是想按照你的方式来写，你需要为你的作业写你自己的。我正在为未来的读者写作，他们可能会了解 x86 上的效率。 （另请参阅 the x86 tag wiki 中的性能部分。）
我是怎么写的:
我从头开始写代码，但很快意识到 off-by-one 错误会很棘手，我不想用循环内分支的愚蠢方式来编写特殊代码案例。
最终的帮助是为内部循环的指针编写前条件和 post 条件的注释。这清楚地表明我需要使用 eax=0 而不是 eax=1 进入循环并将 eax 存储为循环内的第一个操作，或类似的东西。
显然每个源值只需要读取一次，所以我不想编写读取 [rsi] 和 [rsi+4] 之类的内部循环。此外，这会使边界条件变得更难（当e non-existant 值必须读作 0).
我花了一些时间来决定我是否要在寄存器中为行长度或行号设置一个实际的计数器，然后我才最终对整个三角形使用 end-pointer。在我完成之前并不明显，使用纯指针增量/比较将节省这么多指令（并且当上限是 build-time 常量时的寄存器，如 end_triangle），但效果很好.
我在 ASM 中使用 NASM
做一个关于帕斯卡三角形的项目所以在项目中你需要计算第0行到第63行的帕斯卡三角形
我的第一个问题是计算结果存放在哪里->内存
第二个问题我在内存中使用什么类型的存储，为了理解我的意思我有3种方式首先声明一个完整矩阵所以会像这样
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
这种做法就像手工一样，
class 中的一些其他人尝试使用宏
到目前为止还不错
让我们转到我用过的最后一个 这就像第一个，但我使用 triangle matrices ，怎么样， 通过仅声明我需要的内存量
所以要存储 Pascal 三角形的第 0 行到第 63 行，它会给我一个三角形矩阵，因为我在每一个新行中添加一个单元格
我已经为三角矩阵分配了 2080 个双字，这是怎么回事？？ 按 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
我给每个数字1个双字
okey 现在我们已经创建了内存来存储结果让我们开始计算
first# 在帕斯卡三角形中，行 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) 已满，因为正如我在上面的解释中所说，它只包含一个（拖）值
所以这两个伪代码将使我的矩形在内存中看起来像 :
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 代码来打破它吗？
TL:DR: 你只需要顺序遍历数组，所以你不必计算索引。见第二部分。
要随机访问index into a (lower) triangular matrix, row r starts after a triangle of size r-1. A triangle of size n has n*(n+1)/2 total elements, using Gauss's formula for the sum of numbers from 1 to n-1。所以大小为 r-1 的三角形有 (r-1)*r/2 个元素。一旦我们知道行开始的地址，在一行中索引一列当然是微不足道的。
每个 DWORD 元素都是 4 个字节宽，我们可以在乘法中处理缩放，因为 n*(n-1)/2 elements * 4 bytes / elem 简化为 n*(n-1) * 2 bytes.
以上推理适用于基于 1 的索引，其中第 1 行有 1 个元素。如果我们想要 zero-based 索引，我们必须通过在计算之前将行索引加 1 来对此进行调整，因此我们需要三角形的大小
有 r+1 - 1 行，因此 r*(r+1)/2 * 4 bytes。将线性数组索引放入三角形有助于快速double-check公式
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
第 4 行，我们称为 "row 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?). If not, use a RIP-relative LEA to get the triangle base address in a register, and add that to rsi*4. triangle，因此我们可以通过对列使用缩放索引，将基数用作计算的行偏移量，将实际数组地址用作位移来充分利用。
计算三角形
这里的技巧是你只需要顺序循环;您不需要随机访问给定的 row/column.
您在写下一行的同时阅读了一行。 当您到达一行的末尾时，下一个元素是下一行的开始。随着行的向下移动，源指针和目标指针之间的距离会越来越远，因为目的地总是提前一整行。而且你知道一行的长度=行号，所以你实际上可以使用行计数器作为偏移量。
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.
保留space并将每一行标记为row0、row1等的%rep块来自
你标记了这个 NASM，所以我使用它，因为我熟悉它。您在问题中使用的语法是 MASM（直到最后一次编辑）。主要逻辑在 MASM 中是相同的，但请记住，您需要 OFFSET 三角形来立即获取地址，而不是从中加载。
我使用 x86-64 因为 32 位已经过时，但我避免了太多的寄存器，因此如果需要，您可以轻松地将其移植到 32 位。如果你把它放在一个函数而不是 stand-alone 程序中，不要忘记 save/restore call-preserved 寄存器。
展开内部循环可以节省一些复制寄存器的指令，以及循环开销。这是一个稍微优化的实现，但我主要将其限制为使代码 更简单 以及更小/更快的优化。 （除了可能使用指针增量而不是索引。）让它变得如此干净和简单花了一些时间。 :P
不同的数组索引方式在不同的 CPU 上会更快。例如可能对内部循环中的负载使用索引寻址模式（相对于 dst），因此只需要一个指针增量。但是如果你想让它 运行 快，SSE2 或 AVX2 vpaddd 可能不错。使用 palignr 混排可能有用，但也可能是未对齐的加载而不是某些混排，尤其是对于 AVX2 或 AVX512。
但无论如何，这是我的版本；我不是想按照你的方式来写，你需要为你的作业写你自己的。我正在为未来的读者写作，他们可能会了解 x86 上的效率。 （另请参阅 the x86 tag wiki 中的性能部分。）
我是怎么写的:
我从头开始写代码，但很快意识到 off-by-one 错误会很棘手，我不想用循环内分支的愚蠢方式来编写特殊代码案例。
最终的帮助是为内部循环的指针编写前条件和 post 条件的注释。这清楚地表明我需要使用 eax=0 而不是 eax=1 进入循环并将 eax 存储为循环内的第一个操作，或类似的东西。
显然每个源值只需要读取一次，所以我不想编写读取 [rsi] 和 [rsi+4] 之类的内部循环。此外，这会使边界条件变得更难（当e non-existant 值必须读作 0).
我花了一些时间来决定我是否要在寄存器中为行长度或行号设置一个实际的计数器，然后我才最终对整个三角形使用 end-pointer。在我完成之前并不明显，使用纯指针增量/比较将节省这么多指令（并且当上限是 build-time 常量时的寄存器，如 end_triangle），但效果很好.