跟踪 MASM 的 NCR 汇编程序

Question

我们的讲师解释的时候我错过了session..

我知道 NCR 的公式

NCR = N! / (R! * (N-R)!)

我没有关注 NCR PROC，因为没有找到阶乘，并且那里正在进行一些令人毛骨悚然的递归工作。非常感谢您的帮助。

print macro str
    lea dx,msg
    mov ah,09h
    int 21h
endm

.model small
.data
    n dw 15
    r dw 6
    ncr dw 1
    msg db "The NCR is : ","$"
.code
     start: mov ax,@data
            mov ds,ax

            mov bx,n
            mov cx,r
            inc bx
            call ncr1
            print msg          
            mov ax,ncr
            call display

            mov ah,4ch
            int 21h

          ncr1 proc
                cmp cx,00      
                  je l1
                push cx         
                dec cx
                call ncr1        
                mov ax,bx       
                pop cx          
                sub ax,cx       
                mul ncr         
                div cx          
                mov ncr,ax      
              l1 : ret
          ncr1 endp

          display proc
                aam
                add ax,3030h
                mov bx,ax
                mov dl,bh
                mov ah,02h
                int 21h
                mov dl,bl
                mov ah,02h
                int 21h                
             ret
      display endp

end start

Answer 1

好的，我在展示如何分析汇编代码块时看到了一些重用价值，所以就在这里。

我们在这里处理一个子例程，一段应该相对自主的代码。

所以，首先，让我们确定它对程序的原始影响：它的输入、输出和对 sp 的影响 - 即它的 调用约定 和签名.

它使用哪些不是由它设置的实体？

ncr1 proc
    cmp cx,00    # <-- cx
      je l1
    push cx
    dec cx
    call ncr1
    mov ax,bx    # <--bx
    pop cx
    sub ax,cx
    mul ncr      # <--ncr
    div cx
    mov ncr,ax
  l1 : ret
ncr1 endp

它修改了哪些实体之后不恢复？

ncr1 proc
    cmp cx,00
      je l1
    push cx      # cx->local_stack[-2]
    dec cx       # -->cx? (overridden)
    call ncr1
    mov ax,bx
    pop cx       # local_stack[-2]->cx => cx restored
                 # (the next step is actually needed to deduce push/pop
                 # correspondence so they should be done in parallel)
    sub ax,cx
    mul ncr      # -->ax,dx
    div cx
    mov ncr,ax   # -->ncr
  l1 : ret
ncr1 endp

仅标记对实体的最后更改（因为它们优先于之前的更改）。

它对 sp 有任何净影响吗？（数字是当前 sp 相对于 return 地址）

ncr1 proc
    cmp cx,00
      je l1
    push cx     #-2
    dec cx
    call ncr1   #delta is same as self
    mov ax,bx
    pop cx      #0
    sub ax,cx
    mul ncr
    div cx
    mov ncr,ax
  l1 : ret      #without an argument, only cleans the return address
ncr1 endp

它没有（所以 "same as self" 是 0），并且 0 在所有情况下 ret 确认它正确处理本地堆栈。

最后，它的签名是：

ncr1 (cx,bx,ncr) -> ax,dx,ncr

其中 ax 和 dx 可能未被使用（但它们仍然是 volatile）。调用约定是 custom pure register 和一个硬编码的 in/out 参数。

现在，剩下的就是跟踪每个实体在任何时候拥有的物理价值和概念价值：

ncr1 proc  --initially: bx=N, cx=R (metavariables)
    cmp cx,00    # if R==0:
      je l1      #   ret (ax,dx,ncr unchanged)
    push cx      #[-2]=R
    dec cx       #cx=R-1
    call ncr1    #ncr1(N,R-1) -> ax,dx,ncr(probably the result)
    mov ax,bx    #ax=N
    pop cx       #cx=[-2]=R
    sub ax,cx    #ax=N-R
    mul ncr      #dx:ax=(N-R)*ncr = (N-R)*ncr1(N,R-1)
    div cx       #ax=[(N-R)*ncr1(N,R-1)]/R
    mov ncr,ax   #ncr=[(N-R)*ncr1(N,R-1)]/R
  l1 : ret
ncr1 endp        # -> ax,dx,ncr(the result, now we're sure)

这里是：程序计算 (N,R) -> [(N-R)*ncr1(N,R-1)]/R，其中 N=bx、R=cx，结果是 ncr（已变异）。

这看起来很可疑：根据，(N-R) 在规范公式中应为 (N+1-R)。如果我们替换 n=N-1，它会变成：(n+1,R) -> [(n+1-R)*ncr(n+1,R-1)]/R 看起来没问题（第一个参数永远不会改变）...所以该过程实际上计算 nCr(n-1,r).

选择传n+1肯定是因为n只作为n+1进入公式，所以这样，我们每次增加它都节省了周期。

跟踪 MASM 的 NCR 汇编程序

Tracing a NCR assembly program of MASM

assembly

masm

x86-16