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