1

所以我有这个我应该解决的问题，我花了几个小时试图找出最好的方法来做到这一点，谷歌并没有太多帮助。

问题是创建一个子例程，它给出一个单词列表，然后添加另一个列表作为输出。它基本上是一种处理大量数字的方法。

我的代码适用于单词中的进位标志，但对于从一个完整单词到另一个单词的进位标志，它不起作用。第一个 16 位字（下例中的 0005）是一个标志，用于告诉我的子程序有多少字。

例如，给定以下输入，

//si     0005 0000 EEEE DDDD CCCC BBBB
//di     0005 0000 1111 2222 3333 4445

当预期的输出是：

0005 0001 0000 0000 0000 0000

我的代码产生：

0005 0000 FFFF FFFF FFFF 0000

我相信我理解为什么大部分情况会发生这种情况，但不确定解决此问题的最佳方法。我需要一种在不同数据块之间传递 1 的低成本方法。

;---------------------------------------
; ADD Subroutine
;---------------------------------------
    .data

    bxx dw 0000h                        ;
    cxx dw 0000h                        ;

    .code
;---------------------------------------
addx:                                   ;
    mov bxx, bx                         ;save incoming register
    mov cxx, cx                         ;save incoming register
    mov bx, si                          ;move n to bl - acts as a cursor
loopAdd:                                ;loop point
    mov cx, [si+bx]                     ;move word at point si+bx into register cx
    ADC [di+bx], cx                     ;add with carry  
    sub bx, 0002h;                      ;decrement cursor by a full word
    cmp bx, 0000h                       ;bx == 0?
    jg loopAdd                          ;no? jump to loop point
end:                                    ;
    mov bx, bxx                         ;return register to original state
    mov cx, cxx                         ;return register to original state
    ret                                 ;return
;---------------------------------------
4

3 回答 3

2

您必须保存上一次迭代的进位标志。

尝试这个：

;---------------------------------------
; ADD Subroutine
;---------------------------------------
    .data

    bxx dw 0000h                        ;
    cxx dw 0000h                        ;

    .code
;---------------------------------------
addx:                                   ;
    mov bxx, bx                         ;save incoming register
    mov cxx, cx                         ;save incoming register
    mov bx, si                          ;move n to bl - acts as a cursor
    clc                                 ;clear carry flag
    pushf                               ;save flag register
loopAdd:                                ;loop point
    mov cx, [si+bx]                     ;move word at point si+bx into register cx
    popf                                ;restore saved flag register
    ADC [di+bx], cx                     ;add with carry
    pushf                               ;save flag register
    sub bx, 0002h;                      ;decrement cursor by a full word
    jg loopAdd                          ;if the result is positive, jump to loop point
end:                                    ;
    popf                                ;remove saved flag register from the stack
    mov bx, bxx                         ;return register to original state
    mov cx, cxx                         ;return register to original state
    ret                                 ;return
;---------------------------------------

请注意，cmp bx, 0000h不需要，因为除了cmp只修改标志并且不存储计算值，因此您可以直接查看结果。subcmpsub

于 2016-03-03T08:26:00.740 回答
2

OP 说他想要一个低成本的解决方案来保留迭代之间的进位。@MikeCAT 有一个解决方案；@PeterCordes 提出了一些改进建议。

在进行多精度算术时，您可以获得另一个非常好的改进，假设您的多精度值是“大”（包含许多单词值），并且将内部循环展开 N 次，避免循环计数/进位标志损坏展开部分。（如果您的多精度算术不是非常多，则不需要很多优化）。

我在这里修改了@MikeCAT 的答案，假设展开应该是 8 次迭代。

代码有 3 个部分：确定如何处理 8 个单词的片段，以展开的方式处理片段，然后在主展开循环中有效地处理多个 8 个单词的块。

对于 OP 的 5 个单词的示例，此例程永远不会到达完整的展开循环。对于大型多字值，它确实如此，我希望这个例程可能非常快。

[以下代码未经测试。]

;---------------------------------------
; ADD Subroutine
;   si = pointer to count word of 1st multiprecision value
;   di = pointer to count word of 2nd multiprecision value
;   assert: si->count == di ->count
;   preserves si, di; exits with carry from addition
;---------------------------------------
sizeofword equ 2
;---------------------------------------
add_multiple: ; destroys ax, si, di
    push cx                             ;save incoming register
    mov  cx, [si]
    lea  si, sizeofword[si+cx]          ; find least significant word  
    lea  di, sizeofword[di+cx]

; determine entry point into unrolled loop by taking counter modulo 8
    mov cx, si                          ;move n to bl - acts as a cursor
    shr cl, 1 
    jc  add_xx1
    je  done                            ; edge case: 0 words in value
add_xx0:
    shr cl, 1
    jc  add_x10
add_x00:
    shr cl, 1
    jnc add_000                         ; note carry flag is clear                         
;   clc                                
;   jmp add_100
    mov  ax, 0[si]                      
    add  0[di], ax                      ; do 1st add without carry
    lea  si, -1[si]
    lea  di, -1[di]
    jmp  add_011

add_x10:
    shr cl, 1
    jnc add_010
;   clc
;   jmp add_110
    mov  ax, 0[si]
    add  0[di], ax
    lea  si, -1[si]
    lea  di, -1[di]
    jmp  add_101

add_x01:
    shr cl, 1
    jnc add_001
;   clc
;   jmp add_101
    mov  ax, 0[si]
    adc  0[di], ax
    lea  si, -1[si]
    lea  di, -1[di]
    jmp  add_100

add_xx1:
    shr cl, 1
    jnc add_x01
add_x11:
    shr cl, 1
    jnc add_011
;   clc
;   jmp add_111

; the following code adds a fragment of an 8 word block
add_111: ; carry bit has value to propagate
    mov  ax, 0[si]         
;   adc  0[di], ax
    add  0[di], ax                             ; no carry in on 1st add
    lea  si, -1[si]
    lea  di, -1[di]
add_110:
    mov  ax, 0[si]
    adc  0[di], ax
    lea  si, -1[si]
    lea  di, -1[di]
add_101:
    mov  ax, 0[si]
    adc  0[di], ax
    lea  si, -1[si]
    lea  di, -1[di]
add_100:
    mov  ax, 0[si]
    adc  0[di], ax
    lea  si, -1[si]
    lea  di, -1[di]
add_011:
    mov  ax, 0[si]
    adc  0[di], ax
    lea  si, -1[si]
    lea  di, -1[di]
add_010:
    mov  ax, 0[si]
    adc  0[di], ax
    lea  si, -1[si]
    lea  di, -1[di]
add_001:
    mov  ax, 0[si]
    adc  0[di], ax
    lea  si, -1[si]
    lea  di, -1[di]
add_000:
    mov  ax, 0[si]
    adc  0[di], ax
    dec   cx                     ; does not disturb carry
    lea  si, -1[si]
    lea  di, -1[di]
    je    done

; unrolled loop here; very low overhead
add_8words: ; carry bit has value to propagate
    mov  ax, 0[si]
    adc  0[di], ax
    mov  ax, -1[si]
    adc  -1[di], ax
    mov  ax, -2[si]
    adc  -2[di], ax
    mov  ax, -3[si]
    adc  -3[di], ax
    mov  ax, -4[si]
    adc  -4[di], ax
    mov  ax, -5[si]
    adc  -5[di], ax
    mov  ax, -6[si]
    adc  -6[di], ax
    mov  ax, -7[si]
    adc  -7[di], ax
    dec   cx
    lea   si, -8[si]
    lea   di, -8[di]
    jne   add_8word
done: pop  cx
    ret

;---------------------------------------

序列

    mov  ax, 0[si]
    adc  0[di], ax
    lea  si, -1[si]
    lea  di, -1[di]

建议也许使用单字块移动指令作为替代：

    std                          ; want to step backward
    ...
    lods
    adc  ax, 0[di]
    stos
    ...
    cld
    ret

对代码进行适当的调整，留给读者。

我编写的循环或 LODS/STOS 版本是否更快是需要仔细测量的。

于 2016-03-03T10:30:10.710 回答
2

如果您想要快速的多精度加法，请尽可能使用 64 位代码。直接将每条指令的宽度提高 4 倍，速度提高了 4 倍。在 386 兼容的 CPU 上，即使在 16 位模式下，您也可以使用 32 位指令和寄存器，这将使您获得 2 倍的加速。

将 Ira 的展开建议更进一步

  • 将循环开销减少一lea
  • 避免adc使用内存目标，这在英特尔上很慢。

    ... set up for the unrolled loop, with Ira's setup code
    ; di = dst pointer
    ; bx = src-dst, so bx+di = src
add_8words: ; carry bit has value to propagate
    ;sahf   ; another way to avoid a partial-flag stall while looping
    mov  ax, 0[bx+di]
    adc  ax, 0[di]
    mov  0[di], ax
    mov  ax, -1[bx+di]
    adc  ax, -1[di]
    mov  -1[di], ax
    mov  ax, -2[bx+di]
    adc  ax, -2[di]
    mov  -2[di], ax
    mov  ax, -3[bx+di]
    adc  ax, -3[di]
    mov  -3[di], ax
    mov  ax, -4[bx+di]
    adc  ax, -4[di]
    mov  -4[di], ax
    mov  ax, -5[bx+di]
    adc  ax, -5[di]
    mov  -5[di], ax
    mov  ax, -6[bx+di]
    adc  ax, -6[di]
    mov  -6[di], ax
    mov  ax, -7[bx+di]
    adc  ax, -7[di]
    mov  -7[di], ax

    lea   di, -8[di]
    ; lahf
    ; put the flag-setting insn next to the branch for potential macro-fusion
    dec   cx             ; causes a partial-flag stall, but only once per 8 adc
    jne   add_8word

adc这应该在 Intel Broadwell 和 AMD K8 上通过 Bulldozer以几乎每个时钟（减去循环开销）运行。（我忘记了 k8/k10 是否每个时钟可以执行两次加载。如果不能，那将是瓶颈）。根据Agner Fog 的表格，在 Intel 上使用adc内存目标并不好，但在 AMD 上很好。英特尔 Haswell 及更早版本将受到. （Broadwell 制作和单 uop 指令，利用 Haswell 中添加的 3 依赖 uop 支持，因此 FMA 可以是单 uop 指令）。adcadccmov

insn 可能会在部分注册停顿非常糟糕的loop旧 CPU 上胜出，但避免部分标志停顿的其他方法可能比慢速loop指令更好。

使用 dest-source 技巧可以减少递减指针的循环开销。负载中的 2 寄存器寻址模式不需要微熔断，因为无论如何纯mov负载都是单个 uop。商店确实需要微熔断，因此您应该更喜欢商店的单寄存器寻址模式。Haswell 在 port7 上的额外存储地址单元只能处理简单的寻址模式，而2-register 寻址模式不能 micro-fuse。

另请参阅在某些 CPU 上紧密循环中的 ADC/SBB 和 INC/DEC 问题，以获取有关多精度 adc 循环的信息以及关于 Core2 与 SnB CPU 的部分标志停顿性能的一些实验。

在这里循环的另一种方法是 lea si, -1[si]// mov cx, si。jcxz16位很烂，你不能[cx]在有效地址中使用。

于 2016-03-03T11:27:52.157 回答