Отслеживание программы сборки NCR MASM

Question

Я пропустил сессию, когда наш лектор объяснил это..

Я знаю формулы для NCR

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

Я не слежу за 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                

---

### РЕДАКТИРОВАНИЕ ###
Я на самом деле получил эти коды от одного из моих одноклассников, которые посетили сессию...
В коде есть некоторые ошибки... Предложите способ выполнения NCR на ассемблере ИЛИ исправьте эту ошибку...

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 относительно обратного адреса)

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

Это не так ("равно как и я" равно 0), и 0 во всех случаях в ret подтверждает, что он правильно обрабатывает локальный стек.

Заключение, его подпись:

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

куда ax а также dx вероятно не используются (но они все еще нестабильны). А соглашение о вызовах - это пользовательский чистый регистр с одним жестко заданным параметром 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) в канонической формуле согласно комментарию 62556150. Если мы заменим n=N-1, это станет: (n+1,R) -> [(n+1-R)*ncr(n+1,R-1)]/R что выглядит хорошо (первый аргумент никогда не меняется)... так что процедура на самом деле вычисляет nCr(n-1,r),

Выбор пройти n+1 должно быть потому что n входит только в формулу как n+1Таким образом, этим мы экономим циклы при каждом его увеличении.