Сборник по задачам и примерам Assembler

       

Деление (N+М)-разрядного беззнакового целого на число размером М байт



Деление (N+М)-разрядного беззнакового целого на число размером М байт

ПРОГРАММА div_unsign_NM

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

;div_unsign_NM.asm - программа на ассемблере деления (N+M)-разрядного беззнакового целого на число размером N байт

;(порядок - старший байт по младшему адресу (не Intel))

;Вход: U и V - u=um+n-1..+u1u0 - делимое; v=vn-1…v1v0-

;делитель, m - длина делимого;n - длина делителя; b=256 -

;основание системы счисления.

;Выход: q=qmqm-1…q1q0 - частное, r=rn-1…r1r0 - остаток.

;Ограничения: vn-1№0 OR 0ffh; N>1.

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

masm

model small,c



.data

;значения в u и v нужно внести

u0 db 0 ;дополнительный старший байт делимого для нормализации

u db 1fh,0c3h,12h,0ffh ;делимое

m=$-u ;длина в байтах значения u

v0 db 0 ;для компенсирующего сложения 0vn-1…v1v0

v db 3fh,50h ;делитель

n=$-v ;длина в байтах значения v

mm=m-n

w db m+1 dup (0) ;для промежуточных вычислений

q db mm dup (0) ;частное

qq dw 0 ;частичное частное ;qq db 0

rr dw 0 ;частичный остаток

r db n dup (0) ;остаток

d db 0

temp dw 0

temp_r db n dup (0)

borrow db 0 ;факт заема на шаге D4

k db 0 ;перенос 0 Ј k < 255

b dw 100h ;размер машинного слова

carry db 0

.stack 256

.486

.code

calc_complement_r proc

dec cx

mov si,cx

neg byte ptr [bx][si] ;дополнение первого байта

cmp byte ptr [bx][si],0 ;operand=0 - особый случай

jne short $+3

stc ;установить cf, так как есть перенос

jcxz @@exit_cycl ;для однозначного числа

@@cycl: dec si

not byte ptr [bx][si]

adc byte ptr [bx][si],0

loop @@cycl

@@exit_cycl: ret

calc_complement_r endp

mul_unsign_NM macro u,i,v,j,w

local m2,m4,m6

push si

;очистим w

push ds

pop es

xor al,al

lea di,w

mov cx,i+j

rep stosb

;m1

mov bx,j-1 ;j=0..m-1

mov cx,j

m2:

push cx ;вложенные циклы

cmp v[bx],0

je m6

;m3

mov si,i-1 ;i=0..n-1

mov cx,i

mov k,0

m4:

mov al,u[si]

mul byte ptr v[bx]

xor dx,dx

mov dl,w[bx+si+1]

add ax,dx

xor dx,dx


mov dl,k

add ax,dx ;t=(ax) ? временная переменная

push dx

xor dx,dx

div b ;t mod b

mov ah,dl

pop dx

mov k,al

mov w[bx+si+1],ah

;m5

dec si

loop m4

mov al,k

mov w[bx],al

m6:

dec bx

pop cx

loop m2

pop si

endm

sub_sign_N macro minuend,deduction,N

local cycl,m1

; старший байт по младшему адресу

push si

mov cl,N

mov si,N-1

cycl: mov al,deduction[si]

sbb minuend[si],al

; jnc m1

; neg minuend[si]

m1: dec si

loop cycl

pop si

endm

add_unsign_N macro carry,summand_1,summand_2,N

local cycl,end_p

mov cl,N

mov si,N-1

cycl: mov al,summand_2[si]

adc summand_1[si],al

dec si

loop cycl

jnc end_p

adc carry,0

end_p: nop

endm

div_sign_N macro u,N,v,w,r

local m1

;старший байт по младшему адресу

mov r,0

lea si,u ;j=0

xor di,di ;j=0

mov cx,N

xor dx,dx

xor bx,bx

m1: mov ax,256 ;основание с.с.

mul word ptr r ;результат в dx:ax

mov bl,[si]

add ax,bx

div v

;сформировать результат:

mov w[di],al ;частное

mov r,ah ;остаток в r

inc si

inc di

loop m1

;если нужно - получим модуль (уберите знаки комментария)

; mov cx,N ;длина операнда

; lea bx,w

; call calc_abs_r

endm

div_unsign_NM proc

;НАЧ_ПРОГ

;//шаг 1 - нормализация:

;D1 - нормализация

;d:=b/(v[n-1]+1)

xor ax,ax

mov dl,v

inc dl ;vn-1+1

mov ax,b

div dl

mov d,al ;d=b/(v1+1)

;u[n+m…0]:=u[n+m-1…0]*d

mul_unsign_NM u,m,d,1,w

cld

push ds

pop es

lea si,w

lea di,u0

mov cx,m+1

rep movsb

;v[n-1…0]:=v[n-1…0]*d

mul_unsign_NM v,n,d,1,w

cld

push ds

pop es

lea si,w+1

lea di,v

mov cx,n

rep movsb

;//шаг 2 - начальная установка j:

;mm:=m-n; j:=mm

;D2:

mov si,0 ;n=0 (? n=n+m)

;D3:

@@m7:

;//шаг 3 - вычислить частичное частное qq :

;qq:=(u[j+n]*b+u[j+n-1]) / v[n-1]

;rr:=(u[j+n]*b+u[j+n-1]) MOD v[n-1]

@@m1: xor ax,ax

mov al,u0[si]

mul b

shl eax,16

shrd eax,edx,16 ;результат умножения в eax

xor edx,edx

mov dl,u0[si+1]

add eax,edx

shld edx,eax,16 ;восстановили пару dx:ax для деления

xor bx,bx

mov bl,v ;v->bx

div bx

mov qq,ax

mov rr,dx

@@m2:

;проверим выполнение неравенства:



;ДЕЛАТЬ ПОКА tf

;НАЧ_БЛОК_1

;ЕСЛИ qq==b OR qq*v[n-2] > b*rr+ u[j+n-1] ТО

;НАЧ_БЛОК_2

;qq:=qq-1

;rr:=rr+v[n-1]

;ЕСЛИ rrіb ТО tf:=FALSE

;КОН_БЛОК_2

;ИНАЧЕ tf:=FALSE

;КОН_БЛОК_1

@@m4:

mov ax,qq

cmp ax,b ;qq<>b

je @@m9 ;на qq=qq-1

;qq*vn-2>b*rr+uj+n-2

mul v+1 ;qq*vn-2

mov temp,ax ;temp=vn-2*qq

xor ax,ax

mov ax,b

mul rr

xor dx,dx

mov dl,u0[si+2]

add ax,dx

cmp temp,ax ;qq*vn-2 > b*rr+uj+n-2

jna @@m8

@@m9:

dec qq

xor ax,ax

mov al,v

add rr,ax

jmp @@m4

@@m8:

@@m3:

;D4

;//шаг 4 - умножить и вычесть:

;u[j+n…j]:=u[j+n…j]-qq*v[n-1…0]

mul_unsign_NM v,n,qq,1,w

mov bx,si

push si

sub_sign_N u0[bx],w,<n+1> ;v<->w

;ЕСЛИ u[j+n…j]<0 ТО ;запоминаем факт заема, получаем дополнение

;НАЧ_БЛОК_3

;borrow:=1

;u[j+n…j]:=calc_complement_r(u[j+n…j])

;КОН_БЛОК_3

jnc @@m5 ;переход, если нет заема (результат положительный)

mov borrow,1 ;запоминаем факт заема, получаем дополнение

pop si

lea bx,u0[si]

mov cx,n+1

call calc_complement_r

;D5

;//шаг 5 - проверка остатка:

;q[j]:=qq

@@m5: mov ax,qq

mov q[si],al

;ЕСЛИ borrow<>1 ТО

cmp borrow,1 ; был заем на шаге D4 ??

jne @@m6

;НАЧ_БЛОК_4

;//шаг 6 - компенсирующее сложение:

;q[j]:= q[j]-1

;u[j+n…j]:=u[j+n…j]+v[n-1…0]

;КОН_БЛОК_4

;D6 - компенсирующее сложение

mov borrow,0 ;сбросим факт заема

dec q[si]

mov bx,si

push si

add_unsign_N carry,u0[bx],v0,<n+1> ;перенос не нужен

;D7

;//шаг 7 - цикл по j:

;j:=j-1

@@m6: pop si

inc si

;ЕСЛИ jі0 ТО ПЕРЕЙТИ_НА @@m7

cmp si,mm

jle @@m7

;D8 - денормализация

;//шаг 8 - денормализация:

;//вычислим остаток:

;r[n-1…0]:=u[n-1…0]/d

mov bx,si

div_sign_N u0[bx],N,d,r,temp_r

ret

;//q[m…0] - частное, r[n-1…0] ? астаток

;КОН_ПРОГ

div_unsign_NM endp

main:

mov dx,@data

mov ds,dx

call div_unsign_NM

mov ax,4c00h

int 21h

end main

Программа не работает, если первый байт делителя равен 0f fh. Сам алгоритм не изменяется, а проблема устраняется просто — необходимо лишь в нужных местах программы поменять разрядность операндов.

Порядок следования байтов делимого неестествен для микропроцессора Intel. Программу деления многобайтных двоичных чисел с порядком следования байтов «младший байт по младшему адресу» оставляем вам в качестве упражнения.

 

Содержание раздела