Двоичные числа
Прежде чем программировать,
запишите программу в псевдокодах.
Д. Ван Тассел
Сложение двоичных чисел
Сложение чисел размером 1 байт без учета знака
---------------------------------------------------------------------
:add_unsign - процедура сложения чисел размером 1 байт без учета_1 знака
;Вход: sumnand_1и summand_2 - слагаемые.
:Выход: sum_b или sum_w - значение суммы с учетом переполнения.
---------------------------------------------------------------------
.data
summand_1db ? значения в summand_1и summand_2
summandj? db ? :нужно внести
sum_w label word
sum_b db 0
carry db 0
.code
add_unsign proc
mov al ,summand_2
add al ,summand_1mov sumji.al
jnc end_p :проверка на переполнение
adc carry,0
end_p: ret
add_unsign endp
Программа учитывает возможное переполнение результата. Сложение двоичных чисел большей размерности (2/4 байта) выполняется аналогично. Для этого необходимо заменить директивы DB на DW/DD и регистр AL на АХ/ЕАХ.
Сложение чисел размером N байт без учета знака
:add_unsign_N - процедура сложения чисел размером N байт без учета знака
:Вход: summand_1 и summand_2 - слагаемые. N - длина в байтах.
:Выход: summand_1или carry+summandj. - значение суммы с учетом переполнения.
.data
summand_1db ? ;первое слагаемое
N=$-surranand_1;длина в байтах значений summand_1и summand_2
carry db 0 :перенос сложения последних байтов
summand_2 db ? :второе слагаемое
.code
add_unsign_N proc
mov cl. N
хог si.si cycl: mov al ,summand_2[si]
adc summand_l[si].al
inc si
loop cycl
jnc end_p ;проверка на переполнение
adc carry. 0
end_p: ret
add_unsign_N endp
Программа учитывает возможное переполнение результата. Сегмент данных может быть задан, например, так:
.data
summand_1db 0.34.56.78.250 ; первое слагаемое
N=$-summand_1:длина в байтах значений summand_1и summand_2
carry db 0 ;перенос сложения последних байт
summand_2 db 0.43.65.230.250 : второе слагаемое
Далее при рассмотрении программы деления многобайтных двоичных чисел нам понадобится макрокоманда сложения без учета знака чисел размером N байт (порядок следования байтов не соответствует порядку следования байтов на процессорах Intel, то есть старший байт находится по младшему адресу). Приведем ее.
Сложение без учета знака чисел размером N байт (макрокоманда)
.data
:summand_ldb ? :первое слагаемое
;N=$-summand_1,:длина в байтах значений summand_1и summand_2
;carry db 0 :перенос сложения последних байтов
;summand_2db ? ; второе слагаемое
.code
.старший байт по младшему адресу
add_unsign_N macro carry.summand_l.summand_2.N
local cycl.end_p
:add_unsign_N carry,summand_1,sunmand_2.N - макрокоманда сложения без учета знака чисел :размером N байт
:Вход: summand_1l и summanct_2 - слагаемые. N - длина в байтах.
;Порядок следования байтов - старший байт по младшему адресу (не Intel).
;Выход: summand_1или carry+summand_1- значение суммы с учетом переполнения.
mov cl.N
mov si.N-1 cycl: moval,summand_2[si]
adc summand_l[si].al
dec si
loop cycl
jnc end_p
adc carry.0
end_p: пор
endm
Сложение чисел размером 1 байт с учетом знака
---------------------------------------------------------------------
;add_sign - процедура сложения чисел размером 1 байт с учетом знака
:Вход: summand_1и summandj? - слагаемые.
:Выход: sum_b или sum_w - значение суммы в зависимости от наличия расширения знака.
---------------------------------------------------------------------
.data
sum_w label word
summandl db ? :значения в summand_1и summand_2 нужно внести
carry db 0 ; расширение знака
summand_2 db ?
.code
add_sign proc
mov al ,summand_2
add summand_l.a1
jc @@cfl_ofl
jo @<acfO_ofl
:cf=0 of=0 -> результат верный :cf"l of=0 -> результат верный r_true: jmp end__p результат -> summand_1@icfl_ofl: jno
@@cfl_of0 :cf=1 of=1 -> результат неверный
mov carry.0ffh расширение знака д.б. -1, результат ->sum_w
jmp end_p
:cf=1 of=0 -> результат верный
@@cfl_of0: jmp r_true результат -> summand_1:cf=0 of=1 -> результат неверный
@@cf0_ofl: mov carry.0 .-расширение знака д.б. =0. результат ->sum_w
jmp end_p end_p: ret add_sign endp Программа учитывает возможное переполнение результата и перенос в старшие разряды. Для этого отслеживаются условия, задаваемые флагами, и выполняются действия:
- CF=0F=0 — результат правильный и является положительным числом;
- CF=1 0F=0 — результат правильный и является отрицательным числом;
- CF=0F=1 — результат неправильный и является положительным числом, хотя правильный результат должен быть отрицательным (для корректировки необходимо увеличить размер результата в два раза и заполнить это расширение нулевым значением);
- CF=0 0F=1 — результат неправильный и является отрицательным числом, хотя правильный результат должен быть положительным (для корректировки необходимо увеличить размер результата в два раза и произвести расширение знака).
Сложение чисел со знаком большей размерности (2/4 байта) выполняется аналогично, для этого необходимо внести изменения в соответствующие фрагменты программы. В частности, необходимо заменить директивы DB на DW/DD и регистр AL на АХ/ЕАХ.
Сложение с учетом знака чисел размером N байт
---------------------------------------------------------------------
:add_sign_N - процедура сложения с учетом знака чисел размером N байт
-.Вход: summand_1и summand_2 - слагаемые. N - длина в байтах.
:Выход: summand_1или carry+summand_1- значение суммы с учетом переполнения.
---------------------------------------------------------------------
.data
summand_1db ? :первое слагаемое
N=$-summand_1:длина в байтах значений summand_1и summand_2
carry db 0 расширение знака
summand_2 db ? :второе слагаемое
.code
add_sign_N proc
mov cx.N
mov si .0-1 cycl: incsi
mov al ,summand_2[si]
adc summand_l[si].al
loop cycl
jc @@cfl_ofl
jo @(acfO_ofl
:cf=0 of=0 -> результат верный :cf=1 of=0 -> результат верный r_true:jmp end_p результат -> summand_1@@cfl_ofl:
jno?@cfl_of0 :cf=1 of-1 -> результат неверный
mov carry.0ffh расширение знака д.б. =1. результат ->sum_w
jmp end_p @@cfl_of0: :Cf»l of=0 -> результат верный
jmp r_true результат -> summand_1@0cf0_ofl: :cf=0 of=1 -> результат неверный
mov carry.0расширение знака д.б. =0. результат ->sum_w
jmp end_p end_p: ret add_sign_N endp Сегмент данных может быть задан, например, так:
.data
summand_1db 32,126,-120 ;первое слагаемое
N=$-summand_1;длина в байтах значений summand_1и sumniand_2
carry db 0 расширение знака
summand_2 db 126,125,-120 ;второе слагаемое Программа учитывает возможное переполнение результата. Обратите внимание на порядок задания значений слагаемого. Если слагаемое положительное, то проблем нет. Отрицательное слагаемое размером N байт для своего задания требует некоторых допущений. Старший байт отрицательного слагаемого задается со знаком и в процессе трансляции будет преобразован в значение, являющееся двоичным дополнением исходного значения. Остальные байты в своем исходном виде должны быть частью доbxя. Поэтому для работы с числами со знаком удобно иметь программу, которая бы выполняла вычисление значения модуля отрицательного числа и, наоборот, по значению модуля вычисляла его дополнение.
Вычисление дополнения числа размером N байт ---------------------------------------------------------------------
: calc_complement - процедура вычисления дополнения числа размером N байт
;Вход: bx - адрес операнда в памяти; сх - длина операнда.
;Порядок следования байт - младший байт по младшему адресу. ;
Выход: bx - адрес результата в памяти
---------------------------------------------------------------------
.code calc_complement proc
хог si,si
neg byte ptr [bx] дополнение первого байта
cmp byte ptr [bx],0 ;нулевой операнд - особый случай
jne short $+3
stc установить cf, так как есть перенос
dec ex
jcxz @@ml ;для однобайтного операнда
@@cycl: iпс si
not byte ptr [bx][si]
adc byte ptr [bx][si],0
loop @@cycl
@@ml: ret calc_complement endp Для значений размерностью 1/2/4 байта дополнение можно получать с помощью одной команды NEG:
neg operand
Для значений N байт необходимо реализовывать алгоритм. Дополнение первого байта необходимо вычислять с учетом того, что он может быть нулевым. Попытка получить его дополнение с помощью команды NEG обречена на провал. Флаг CF в этом случае также должен устанавливаться программно. Подумайте, почему?
Вычисление модуля числа размером N байт
---------------------------------------------------------------------
:calc_abs - процедура вычисления модуля числа размером N байт
:Вход: bx - адрес операнда в памяти; сх - длина операнда.
;Порядок следования байтов - младший байт по младшему адресу.
:Выход: bx - адрес результата в памяти.
---------------------------------------------------------------------
.code
calc_abs proc определим знак операнда
mov si.cx
dec si
test byte ptr [bx][si],80h проверяем знак операнда
jz @@exit ;число положительное
call calc_complement @@exit:ret
calc_abs endp
Вычитание двоичных чисел
Вычитание чисел размером 1 байт без учета знака
---------------------------------------------------------------------
;sub_unsign - процедура вычитания чисел размером 1 байт без учета знака
;Вход: minuend и deduction - уменьшаемое и вычитаемое.
:Выход: minuend - результат вычитания
.---------------------------------------------------------------------
.data значения в minuend и deduction нужно задать
minuend db ? уменьшаемое
deduction db ? ;вычитаемое
.code
sub_unsign proc
mov al .deduction
subminuend.al :оценить результат на случай уменьшаемое < вычитаемого
jnc end_p ; нет заема обрабатываем ситуацию заема из старшего разряда - получаем модуль (если нужно)
neg minuend end_p: ret sub_unsign endp
Программа учитывает возможное соотношение: уменьшаемое<вычитаемого. Вычитание чисел большей размерности (2/4 байта) выполняется аналогично. Необходимо заменить директивы DB на DW/DD и регистр AL на АХ/ЕАХ.
Вычитание чисел размером N байт без учета знака
---------------------------------------------------------------------
:sub_unsign_N -.процедура вычитания чисел размером N байт без учета знака
:Вход: minuend и deduction - уменьшаемое и вычитаемое, N - длина в байтах.
;Выход: minuend - значение разности.
---------------------------------------------------------------------
.data значения в minuend и deduction нужно внести
minuenddb ? уменьшаемое
N=$-minuend ;длина в байтах значений minuend и deduction '.
deduction db ? :вычитаемое
.code
sub_unsign_N proc
mov cl.N
xor si,si cycl: moval ,deduction[si]
sbbminuend[si].al
jnc @@ml
negminuendtsi] @@ml: inc si
loop cycl
ret sub_uns1gn_N endp Программа учитывает возможный заем из старших разрядов. Длина уменьшаемого должна быть не меньше длины вычитаемого, недостающие разряды вычитаемого должны быть нулевыми. В любом случае, результат — абсолютное значение.
Сегмент данных может быть задан, например, так:
.data
N equ5 ;длина в байтах значений minuend и deduction
minuenddb 30.43.65.230,250 уменьшаемое
deduction db 45.34.65.78.250 ;вычитаемое
Вычитание чисел размером 1 байт с учетом знака
---------------------------------------------------------------------
;sub_sign - процедура вычитания чисел размером 1 байт с учетом знака
;Вход: minuend и deduction - уменьшаемое и вычитаемое.
:Выход: minuend - значение разности.
---------------------------------------------------------------------
.data значения в minuend и deduction нужно внести
N equ 2 :длина в байтах результата в ситуации расширения знака для получения его модуля
minuend db ? -.уменьшаемое
carry db 0 расширение знака
deduction db ? :вычитаемое
.code
sub_sign proc
mov al .deduction
subminuend.al ;оценить результат:
jnc no_carry :нет заема обрабатываем ситуацию заема из старшего разряда - получаем модуль (если нужно)
neg minuend
jmp end_p
no_carry: jns no_sign обрабатываем ситуацию получения отрицательного результата - получаем модуль (если нужно)
neg minuend
jmp end_p
no_sign: jno no_overflow обрабатываем ситуацию переполнения - получаем модуль (если нужно).
расширить результат знаком - получаем модуль (если нужно):
mov carry.0ffh
call calc abs no_overflow:
endjr ret sub_sign endp Программа учитывает возможный заем из старших разрядов. Вычитание чисел большей размерности (2/4 байта) выполняется аналогично. Необходимо заменить директивы DB на DW/DD и регистр AL на АХ/ЕАХ. Подробности зависимости состояния флагов от результата см. в уроке 8 «Арифметические команды» учебника.
Вычитание чисел размером N байт с учетом знака ---------------------------------------------------------------------
:sub_sign_N - процедура вычитания чисел размером Н байт с учетом знака
;Вход: minuend и deduction - уменьшаемое и вычитаемое. N - длина в байтах.
:Выход: minuend - значение разности.
---------------------------------------------------------------------
.data :значения в minuend и deduction нужно внести
minuenddb ? уменьшаемое
lenjninuend=$-minuend ;длина в байтах уменьшаемого и вычитаемого
carry db 0 расширение знака
deduction db ? ;вычитаемое
.code
sub_sign_N proc
mov cx.lenjninuend
mov si.O @@ml: mov al,deduction[si]
sbb minuend[si].al
inc si
loop @@ml оценить результат:
jnc no_carry :нет заема
обрабатываем ситуацию заема из старшего разряда - получаем модуль (если нужно) N=1en_minuend+1
mov carry.0ffh
call calc_abs
jmp end_p no_carry: jns no_sign Обрабатываем ситуацию получения отрицательного результата -
:получаем модуль (если нужно) N=1en_minuend
call calc_abs
jmp end_p
no_sign: jno no_overflow
обрабатываем ситуацию переполнения - получаем модуль (если нужно) расширить результат знаком - получаем модуль (если нужно): N=1en_minuend+1
mov carry,0ffh
call catc_abs no_overflow: end_p: ret sub_sign_N endp
Описанная процедура вычисляет модуль разности и учитывает возможный заем из старших разрядов. Если вычисления модуля разности не требуется, то закомментируйте строки, содержащие команду CALL calc_abs. Подробности зависимости состояния флагов от результата см. в уроке 8 «Арифметические команды» учебника.
Сегмент данных может быть задан, например, так:
.data :значения в minuend и deduction нужно внести
minuend db 25h,0f4h,0eh уменьшаемое
len_minuend=$-minuend ;длина в сайтах уменьшаемого и вычитаемого
carry db 0 ;расширение знака
deduction db 5h,0f4h,0fh :вычитаемое
Далее при рассмотрении программы деления многобайтных двоичных чисел нам понадобится макрокоманда вычитания с учетом знака чисел размером N байт (порядок следования байт не соответствует порядку следования байтов на процессорах Intel, то есть старший байт находится по младшему адресу). Приведем ее.
Вычитание с учетом знака чисел размером N байт (макрокоманда)
sub_sign_N macro minuend.deduction.N
local cycl.ml
---------------------------------------------------------------------
;sub_sign_N minuend.deduction.N - макрокоманда вычитания
;c учетом знака чисел размером N байт
:Вход: minuend и deduction - уменьшаемое и вычитаемое. N - длина в байтах.
:Порядок следования байт - старший байт по младшему адресу (не Intel).
:Выход: minuend - значение разности.
---------------------------------------------------------------------
push si
mov cl,N
mov si.N-1 cycl: moval .deduction[si]
sbbminuend[si],al : jnc ml
: neg minuend[si] ml: dec si
loop cycl
pop si
endm
Умножение двоичных чисел
В отличие от сложения и вычитания операция умножения реализуется двумя типами команд — учитывающими и не учитывающими знаки операндов.
Умножение чисел размером 1 байт без учета знака ---------------------------------------------------------------------
:mul_unsign.asm - программа умножения чисел размером 1 байт без учета знака. ;Вход: multiplier], и multiplied - множители размером 1 байт. ;Выход: product - значение произведения.
---------------------------------------------------------------------
.data
:значения в multiplier], и multiplied нужно внести
product label word
productj label byte
multiplier! db ? :множитель 1 (младшая часть произведения)
product_h db 0 ;старшая часть произведения
multiplied db ? ;множитель 2
.code
mul_unsign proc
mov al .multiplierl
mul multiplier2 :оценить результат:
jnc по_саггу ;нет переполнения - на no_carry обрабатываем ситуацию переполнения
mov product_h.ah :старшая часть результата no_carry: mov product_l.al ;младшая часть результата
ret
mul_unsign endp main:
call mul_unsign
end main
Здесь все достаточно просто и реализуется средствами самого процессора. Проблема состоит лишь в правильном определении размера результата. Произведение чисел большей размерности (2/4 байта) выполняется аналогично. Необходимо заменить директивы DB на DW/DD, регистр AL на АХ/ЕАХ, регистр АН на DX/EDX.
Умножение чисел размером N и М байт без учета знака
Для умножения чисел размером N и М байт, существует несколько стандартных алгоритмов, описанных в литературе. В этом разделе мы рассмотрим только один из них. В его основе лежит алгоритм умножения неотрицательных целых чисел, предложенный Кнутом.
Умножение N-байтного числа на число размером М байт
ПРОГРАММА mul_unsign_NM
---------------------------------------------------------------------
//mul_unsign_NM - программа на псевдоязыке умножения N-байтного числа
//на число размером М байт
//(порядок - старший байт по младшему адресу (не Intel))
//Вход: U и V - множители размерностью N и М байт соответственно
: Ь=256 - размерность машинного слова.
//Выход: W - произведение размерностью N+M байт.
---------------------------------------------------------------------
ПЕРЕМЕННЫЕ
INT_BYTE u[n]; v[n]; w[n+m]: k=0: INT_WORD b=256: temp_word НАЧ_ПРОГ
ДЛЯ j:=M-l ДО 0 //J изменяется в диапазоне М-1..0
НАЧ_БЛОК_1
//проверка на равенство нулю очередного элемента множителя (не обязательно) ЕСЛИ v[j]==0 TO ПЕРЕЙТИ_НА тб
k:=0: i:=n-l ll\ изменяется в диапазоне N-1..0
ДЛЯ 1:=N-1 ДО О НАЧ_БЛ0К_2
//перемножаем очередные элементы множителей temp_word:=u[i]*v[j]+w[i+j+l]+k
w[i+j+l]:=temp_word MOD b //остаток от деления temp_word\b -> w[i+j+l] k:=temp_word\b //целая часть частного temp_word\b -> k
К0Н_БЛ0К_2 w[j]:=k шб:
КОН БЛОК_1 КОН_ПРОГ
:inul_unsign_NM.asm - программа на ассемблере умножения N-байтного числа на число :размером М байт (порядок - старший байт по младшему адресу (не Intel)).
.data :значения в U и V нужно внести
U db ? ;U-un.i«.UiU() - множитель_1 размерностью N байт
1-S-U :i=N
V db ? ; V"Vm.i_ViV(| - множитель_2 размерностью М байт
j=$-V :j=M
len_product=$-U
;w - результат умножения, длина N+M
W db len_product dup (0) ;1en_product=N+M
k db 0 :перенос 0 < k < 255
b dw lOOh : размер машинного слова
.code
mul_unsign_NM proc
mov bx.j-1 :ml
mov ex, j ;ДЛЯ j:=M-l ДО 0 //J изменяется в диапазоне М-1..0
m2: :НАЧ_БЛОК_1
push ex сложенные циклы
emp v[bx],0 :ЕСЛИ v[j]—0 TO ПЕРЕЙТИ_НА m6
je m6 ;m3
movsi.i-1 :i-0..n-l ;k:=0; 1:41-1 //i изменяется в диапазоне N-1.,0
mov cx.i
movk.O :ДЛЯ i:-N-l ДО О НАЧ_БЛ0К_2 m4: ://перемножаем очередные элементы множителей
mov al,u[s1] :temp_word:-u[i]*v[j]+w[i+j+l]+k
mul byte ptr v[bx]
xor dx.dx
mov dl ,w[bx+si+l]
add ax.dx
xor dx.dx
mov dl , k
add ax.dx :t=(ax) - временная переменная
:w[i+j+l]:=temp_word MOD b //остаток от деления temp_word\b -> w[i+j+l] :k:=temp_word\b //целая часть частного temp_word\b -> k
push dx
xor dx.dx
div b
mov ah.dl
popdx
mov k.al
mov w[bx+si+l].ah :m5 .
dec si
loop m4 ;КОН_БЛ0К_2
moval.k ;w[j]:=k
mov w[bx].al m6: dec bx
pop ex
loop m2 ;КОН_БЛОК_1
ret ;КОН_ПРОГ mul_unsign_NM endp main:
call mul_unsign_NM end main
В отличие от обычного умножения «в столбик» в данном алгоритме сложение частичных произведений выполняется параллельно умножению. Программа производит умножение значений в порядке — старший байт по младшему адресу. Это неестественно для микропроцессоров Intel, поэтому программу необходимо соответствующим образом изменить. Текст измененной процедуры mul_ unsign_NM_I приведен на дискете.
Процедуру умножения чисел без учета знака mul_unsign_NM удобно представить в виде макрокоманды mul_unsign_NM_r u,i ,v, j,w. Это без излишних усложнений сделает ее вызов более универсальным. При последующем рассмотрении программы деления многобайтных двоичных чисел она будет использована нами с большой пользой. Текст макрокоманды приведен на дискете. На дискете также имеется вариант этой макрокоманды mul_unsign_NM u,i ,v, j.WHa случай естественного для микропроцессоров Intel расположения операндов — младший байт по младшему адресу.
Умножение чисел размером 1 байт с учетом знака
;mul_sign.asm - программа умножения чисел размером 1 байт с учетом знака ;Вход: multiplier], и multiplied - множители со знаком размерностью 1 байт. ;Выход: product - значение произведения.
.data значения в multiplier], и multiplied нужно внести
product label word
productj label byte
multiplierl db ? ;множитель 1 (младшая часть произведения)
product_h db 0 :старшая часть произведения
multiplied db ? :множитель 2
.code
mul_sign proc
mov al.multiplierl
imul multiplied :оценить результат:
jnc no_carry :нет переполнения - на no_carry обрабатываем ситуацию переполнения
mov productji.ah :старшая часть результата, знак результата - старший бит product_h no_carry: mov productj,al :младшая часть результата, productji - расширение знвка
ret
mul_sign endp. main:
call mul_sign end main
Аналогично умножению без знака здесь также все достаточно просто и реализуется средствами самого процессора. Проблема та же — правильное определение размера результата. Произведение чисел большей размерности (2/4 байта) выполняется аналогично. Необходимо заменить директивы DB на DW/DD, регистр AL на АХ/ЕАХ, регистр АН на DX/EDX. Более того, в отличие от команды MUL команда IMLJL допускает более гибкое расположение операндов.
Умножение чисел размером N и М байт с учетом знака
Как уже не раз отмечалось, система команд микропроцессора содержит два типа команд умножения — с учетом знаков операнда (IMUL) и без него (MUL). При умножении операндов размером 1/2/4 байта учет знака производится автоматически — по состоянию старших (знаковых) битов. Если умножаются числа размером в большее количество байтов, то для получения правильного результата необходимо учитывать знаковые разряды только старших байтов. В основе программы, реализующей алгоритм умножения чисел размером N и М байт с учетом знака, лежит рассмотренная выше процедура умножения чисел произвольной размерности без учета знака.
Умножение N-байтного числа на число размером М байт с учетом знака ПРОГРАММА mul_sign_NM
//---------------------------------------------------------
//mul_sign_NM - программа на псевдоязыке умножения N-байтного числа
//на число размером М байт
//(порядок - старший байт по младшему адресу (не Intel)) //
Вход: U и V - множители со знаком размерностью N и М байт соответственно;
//Ь=256 - размерность машинного слова. //Выход: W - модуль (дополнение) произведения размерностью N+M байт.
//---------------------------------------------------------
ПЕРЕМЕННЫЕ
INTJ3YTE u[n]; //множитель 1 размерностью N байт
INT_BYTE v[n]; //:множитель 2 размерностью М байт
INT_BYTE w[n+m]: k=0://перенос 0 < k < 255
INT_BYTE sign=0: //информация о знаке
INT_WORD b=256: temp_word //b - размер машинного слова
НАЧ_ПРОГ
//определим знак результата
ЕСЛИ БИТ_7_БАЙТА((и[0] AND 80h) XOR v[0])==1 TO sign:=1
//результат будет отрицательным //получим модули сомножителей: u:-|u| v:-]v|
w:=mul_unsign_NM() //в этой точке - модуль результата //восстанавливаем знак результата ЕСЛИ sign==0 TO ПЕРЕЙТИ_НА Шт
//для отрицательного результата вычислить дополнение значения w длиной i+j w:=calc_complement_r() //в этой точке - двоичное дополнение результата @йп: КОН_ПРОГ
:mul_sign_NM.asm - программа на ассемблере умножения N-байтного числа :на число размером М байт
;(порядок - старший байт по младшему адресу (не Intel))
.data ;значения в U и V нужно внести
;Помните. что задание отрицательных многобайтных значений в ;сегменте данных должно производиться в дополнительном коде ;(и в порядке байтов - старший байт по младшему адресу)!
U db ? :множитель 1 размерностью N байт
i-$-U
V db ? ;множитель 2 размерностью М байт
J-$-V
len_product=$-U
W db len_product dup (0) результат длиной N+M байт
k db 0 ;перенос О < k < 255
b dw lOOh ;размер машинного слова
sign db 0 информация о знаке
.code
;включить описание процедур calc_complement_r. calc_abs_r. :mul_unsign_NM
mul_sign_NM ргос ;НАЧ_ПРОГ юпределим знак результата
хог ах.ах ; ЕСЛИ БИТ_7_БАЙТА((и[0] AND 80h) XOR v[0])==1 TO sign:=1
mov al.u
and al.80h
xor al.v
bt ax,7
jnc $+7
mov sign.l результат будет отрицательным
lea bx.v ;получим модули сомножителей: u:~|u|; v:=|v|
mov ex.j
call calc_abs_r
1 ea bx, u
mov ex.i
call calc_abs_r ;теперь умножаем
call mul_unsign_NM ;w:=inul_unsign_NM() ;в этой точке - модуль результата ;восстанавливаем знак результата
хог si. si
emp sign.0 :ЕСЛИ sign==0 ТО ПЕРЕЙТИ_НА №т
je @@m ://для отрицательного результата вычислить дополнение значения w длиной i+j
mov ex,i+j ;w:=calc_complement_r(); w[0]:=0-w[0]
lea bx.w
call calc_complement_r ;в этой точке - двоичное дополнение результата @@m: ret ;КОН_ПРОГ
mul_sign_NM endp main:
call mul_sign_NM end main
Процедура mul_sign_NM выполняет умножение с учетом знака исходных значений в порядке байтов — старший байт по младшему адресу. Если вы используете отрицательные значения операндов, тс для правильной работы тестовой программы в сегменте данных их необходимо задать в дополнительном коде.
В данной программе используются две новые процедуры — calc_complement_r и calc_abs_r, вычисляющие соответственно дополнение и модуль числа размером N байт. Подобные процедуры уже были разработаны и введены нами для значений, порядок следования байт которых характерен для микропроцессоров Intel. Чтобы различать эти две пары процедур, процедуры для вычисления дополнения и модуля числа размером байт с порядком следования байтов, отличным от Intel, мы назвали реверсивными.
Вычисление дополнения числа размером N байт (реверсивное)
:calc_complement_r - процедура на ассемблере вычисления дополнения числа размером N байт
:(старший байт по младшему адресу).
;Вход: регистр ВХ - адрес операнда в памяти: регистр СХ - длина операнда. ;Выход: регистр ВХ - адрес дополнения операнда в памяти.
ca1c_complement_r ргос
dec ex
mov si.ex
neg byte ptr [bx][si] дополнение первого байта
cmp byte ptr [bx][si].O :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
Для значений размерностью 1/2/4 байта дополнение можно получать с помощью одной команды NEG:
neg operand
Дополнение значений N байт вычисляет алгоритм, реализованный в процедуре calc_complement_r. Обратите внимание, что первый байт может быть нулевым, поэтому алгоритм учитывает это обстоятельство. Попытка получить его дополнение с помощью команды NE6 обречена на провал. Флаг CF в этом случае также должен устанавливаться программно. Подумайте, почему?
Вычисление модуля числа размером N байт (реверсивное)
calc_abs_r - процедура на ассемблере вычисления модуля числа размером N байт
:(старший байт по младшему адресу).
:Вход: регистр ВХ - адрес операнда в памяти: регистр СХ - длина операнда. :Выход: регистр ВХ - адрес модуля операнда в памяти.
.code
calc_abs_r proc определим знак операнда
test byte ptr [bx],80h ;проверяем знак operand
jz @@exit :число положительное
call calc_complement_r @@exit: ret calc_abs_r endp Для вычислений над операндами, порядок следования байтов которых характерен для микропроцессоров Intel, нам придется разработать еще один вариант процедуры умножения значений размерностью в произвольное количество байтов. Псевдокод и соответствующая ему программа на ассемблере mul_sign_NM_I приведены на дискете. Деление двоичных чисел
Аналогично операции умножения деление реализуется двумя типами команд — учитывающими и не учитывающими знаки операндов. Эти команды накладывают ощутимые ограничения на размерность (а соответственно и на диапазон значений) операндов. Поэтому мы рассмотрим вначале пример стандартного применения команд, после чего займемся реализацией алгоритмов деления чисел произвольной размерности.
Деление без учета знака значения размером 2 байта на значение размером 1 байт
:div_unsign.asm - программа на ассемблере деления без учета знака значения
размером 2 байта на значение размером 1 байт.
:Вход: и - делимое: v - делитель.
;Выход: w - частное, г - остаток.
.data :значения в и и v нужно внести
u dw ? :делимое
v db ? :делитель
w db 0
г db 0
.code
div_unsign proc
mov ax.u
div v сформировать результат:
mov r.ah :остаток
mov w.al :частное
ret
divjjnsign endp , main:
call div_unsign end ma in
Деление чисел большей размерности (4/8 байтов) выполняется аналогично. Необходимо заменить директивы DB на DW/DD, регистр АХ на EAX/EDX: ЕАХ, регистр AL на АХ/ЕАХ, регистр АН на DX/EDX.
Деление с учетом знака значения размером 2 байта на значение размером 1 байт
:div_sign.asm - программа на ассемблере деления с учетом знака значения
;размером 2 байта на значение размером 1 байт.
:Вход: и - делимое; v - делитель.
:Выход: w - частное, г - остаток.
.data значения в и и v нужно внести
и dw ? ;делимое
v db ? ;делитель
w db О
г db О
.code
div_sign proc
mov ax.u
idiv v сформировать результат:
mov г,ah :остаток
mov w.al ;частное
:если нужно получить модуль - уберите знаки комментария : mov cx.l ;длина операнда ; lea bx.w : call calc_abs ;или ; neg w
ret
div_sign endp main:
call div_sign
end main
Деление чисел большей размерности (4/8 байтов) выполняется аналогично. Необходимо заменить директивы DB на DW/DD, регистр АХ на EAX/EDX:EAX, регистр AL на АХ/ЕАХ, регистр АН на DX/EDX.
Деление N-разрядного беззнакового целого на одноразрядное число размером 1 байт
:div_uns1gn_N_1.asm - программа на ассемблере деления без учета знака значения
:размером N байт на значение размером 1 байт.
;Порядок следования байтов - старший байт по младшему адресу (не Intel) :Вход: и - делимое; v - делитель. :Выход: w - частное, г - остаток.
.data значения в и и v нужно внести
u db ? ;делимое
N=$-u :длина в байтах значения и
v db ? :делитель
w db N dup (0)
г dw 0 :остаток
.code
div_unsign_N_lproc
mov г.О
хог si.si ;j»0
mov cx.N
хог dx.dx
хог bx.bx @@ml: movax.256 основание с.с.
mul г результат в dx:ax
mov bl ,u[si]
add ax.bx
div v сформировать результат:
mov w[si].al :частное
shr ax.8
mov г.ах юстаток в г
inc si
1oop @@ml
ret
d i v_uns i gn_N_lendp main:
call div_unsign_N_l
end main
Сегмент данных может быть задан, например, так:
.data значения в и и v нужно внести
u db 5.6.7 :делимое
N=$-u :длина в байтах значения и
v db 15 ;делитель
w db N dup (0)
г dw 0 :остаток
В программе div_unsign_N_l.asm порядок следования байтов делимого неестествен для микропроцессора Intel. Поэтому на дискете приведен вариант программы div_unsign_N_l_I.asm, в котором эта проблема устранена.
Далее при рассмотрении программы деления многобайтных двоичных чисел нам понадобится макрокоманда divunsignN деления N-разрядного беззнакового целого на одноразрядное число размером 1 байт (порядок следования байтов не характерен для процессоров Intel, то есть старший байт находится по младшему адресу). Текст макрокоманды приведен на дискете.
Деление (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. Программу деления многобайтных двоичных чисел с порядком следования байтов «младший байт по младшему адресу» оставляем вам в качестве упражнения.
|
