Создание подпрограммы преобразования 128-разрядного СЧ в УЧ
Содержание
Введение
Анализ
Блок-схема основной программы.
Линейная схема основной программы.
Верификация
. Без ветвлений
. С ветвлением
. Цикла
Сети Петри.
Операционная семантика
Заключение.
Приложение. Листинг программы
Введение
Подпрограмма преобразования 128-разрядного СЧ в
УЧ.
Анализ
В окончательной версии программы реализован ввод
с клавиатуры числа, длиной не более 128 символов, проверка его на корректность
ввода, преобразование из символьного представления в УЧ, размещение полученного
числа в выделенной оперативной памяти.
Tabl db '0123456789' -
таблица для проверки корректности ввода данных
flag db 0 -
искусственный флаг
dlina_1 db 0 -
хранит длину числа dw 0 - буфер_SEG1 dw 0 -
хранит адрес блока выделенной ОП для числа
Блок-схема основной программы
Линейная схема основной программы
. СТАРТ (x)
// x
- число, введенное с клавиатуры
. ЕСЛИ P(x),
то на 2, иначе на 4
2. x1=f1(x)
3. x2=f2(x1)
. СТОП (x2)
Расшифровка символов, использующихся в данной
схеме:
Переменные:
x, x1,
x2.
Функциональные символы:
- операция перевода числа во
внутреннее представление
- операция перевода в УЧ
Предикатные символы:
P - ‘Если
числа введены корректно’
Cпециальные
символы:
старт, стоп, если.
Аксиоматическая семантика
Множества
Z- множество целых
чисел
- множество регистров
множество меток
Операции
+ сложить
вычесть
неравно
= равно
:= присвоить
выполнить действия за стрелкой,
если выполняются условия до стрелки
@ обратиться по адресу
( ) извлечь содержимое
& логическое
и
…: ax, ax ;(ax)=0 bx,
bx ;(bx)=0 si, si ;(si)=0
mov al, a+1 ;
(al)=(@(a1)+1) si, ax ;(si)=(ax) di,
di ;(di)=0 di, si ;(di)=(si)
xor ax, ax ;(ax)=0 di ;
(di)t = (di)(t-1)-1
…proc bp ;
((sp):=(sp)-2)&((@(ss)+(@(sp)))=(bp)) bp, sp ;(bp)=(sp) ax ;
((sp):=(sp)-2)&((@(ss)+(@(sp)))=(ax)) ah, 0 ;(ah)=0 al,
2 ;(al)=2
int 10h ;
(sp)t=(sp)(t-1)-2, (sp)=(Flags), (sp)t=(sp)(t-1)-2, (sp)=(ip), (ip)=(132)
pop ax ;((ax)=(@(ss)+(@(sp))))&((sp):=(sp)+2) bp ;((bp)=(@(ss)+(@(sp))))&((sp):=(sp)+2)
ret ;
RET
ClrScr
endp
Верификация
. Без ветвлений
mov ax, di S1 a1[si],al S2 si S3
Иcпользуем
метод обратной волны:
. С ветвлением
cmp si,0
je Konec al,bl
…
Konec: bx,bx bl,dlina_1
Для доказательства того, что
(si>0)
(si=0)
{ if si=0
then al=al-bl else bx=0}
(bx=0)
Необходимо доказать три условия
истинности:
1) без побочных эффектов (si>0)
2) ((si>0)(si=0))
& (si>0) {al=al-bl} (al=al-blbx=0)
((si>0)(si=0))
& (si>0) ( al-bl =
al-bl bx=0) True
) ((si>0)(si=0))
& (si=0) {bx=0} (al=al-blbx=0)
((si>0)(si=0))
& (si=0) (al=al-bl0=0)
True True
. Цикла
dlina_1=число введенных
знаков
dlina_2=число
введенных знаков
;(dlina_1>dlina_2)
…= dlina_2 bl,dlina_1
metka: di es,BLOCK_SEG1
… di,bx metkadi,2cl,adg:al,buf3[di]di
…LViv
P = di >
0 
bx > 0=
(di!=bx)= (di=bx)
S = (es=BLOCK_SEG1 di=di+1)=
(bx-di)= (bx > 0)
di = bx
Покажем, что цикл всегда
завершается, и продемонстрируем истинность следующих утверждений:
1) P->Inv
di > 0 bx > 0 bx > 0 True
2) Inv
{B} Inv
bx>0 {di!=bx}
bx>0 True
3) Inv B {S} Inv
bx>0 di!=bx {es
= BLOCK_SEG1 di=di+1} bx>0>0 {es=BLOCK_SEG1} bx>0
bx>0
-> bx>0 True
) Inv
!B = Q>0
di=bx ->
di=bx True
) D=
B Inv {S} D <
(bx-di=) (di!=bx) (bx>0)
{es = BLOCK_SEG1 di=di+1}(bx-di<)
(bx-di=) (di!=bx) (bx>0)
-> bx - (di+1)< True
) D =
{B} D<= - di = {di!=bx} bx-di<=- di = -> bx - di <=
True
) D=0
Inv ->
!Bdi=0 bx>0
-> !!(di=bx)di=0 bx>0
-> di=bx True
Сети Петри
Для построения сети Петри была выбрана основная
программа
Операционная семантика
Для написания операционной семантики
была выбрана команда dec.
Будем использовать одну ленту L1 и алфавит
{0,1,#}.
L1:
1. q0101R1q01
2. q0111R1q01
3. q01#1L1q11
4. q1101q2111
5. q2111L1q11
6. q1111q3101
7. q11Top1R1q31
q3 - состояние, при
котором выполняется остановка работы данной машины Тьюринга
Заключение
В результате проделанной работы были изучены
основы программирования на языке Ассемблер, операционная семантика, проведена
верификация линейного участка подпрограммы, участков с ветвлением и циклом,
изучены сети Петри, составлена схема подпрограммы. Также была изучена работа с
упакованными десятичными числами.
Приложение. Листинг программы
программа вычисление линейный
графический
Вычитание 2х УДЦ с произвольным количеством
разрядов
Prog1 segment cs:Prog1,
ds:Prog1 db 'Vvedite 1-e chislo$' db 'Vvedite 2-e
chislo$' db 'Rezyltat:$'db '0$' db 'oshibka vvoda!$' db 102 ;для
1го числа 0 db 100 dup(0) db 102 ;для
2го числа
db 0 db 100 dup(0) db '0123456789' db '
$'db ' $'
flag db 0_1 db 0 ;хранит
длину 1го числа_2 db 0 ;хранит длину 2го числа
zz dw 0
buf dw 0_SEG1 dw 0 ;хранит
адрес блока выделенной ОП для первого числа_SEG2 dw 0 ;хранит адрес
блока выделенной ОП для второго числа dw 0 ;хранит адрес
блока выделенной ОП для результата
Proc1 proc cs ds
call ClrScr
;############################################################
;Ввод чисел и перевод их в нужную форму
;############################################################
;Курсор влево вверх dx,dx
push dx CXY zz
; Вывод сообщения s1 на экран dx,
s1 ah, 09H 21H
;Курсор на следующую строку
mov dh,1 dl,dl dx
call CXY zz
; Ввод первого числа
mov ah, 0AH dx,
a
int 21H
;Проверка на длину числа
cmp a+1, 0 L1 eoj: a+1,
101 L2 eoj
L2:
;Курсор на следующую строку dh,2
xor dl,dl dx CXY
pop zz
;Проверка правильности ввода 1го числа
mov bl,a+1 ch,
ch
xor si, si: di,
di
mov al, a1[si]: al,
Tabl[di]
je c3 di di,
10 c4
jne c2: si si,
bx c5
jne c1: Error:
; Вывод сообщения s2 на экран
lea dx, s2 ah,
09H
int 21H
;На след строку курсор
mov dh,3 dl,dl dx
call CXY zz
; Ввод второго числа
mov ah, 0AH dx,
b
int 21H
;Проверка на длину числа
cmp b+1, 0 L3 eoj: b+1,
101 L4 eoj
L4:
;На след строку курсор
mov dh,4
xor dl,dl dx CXY
pop zz
;Проверка правильности ввода 2го числа
xor bx, bx bl,
b+1 ch, ch si, si: di, di al,
b1[si]: al, Tabl[di]
je c8 di di,
10 c9
jne c7: si si,
bx c10
jne c6: Error:
;Проверка. Если числа равны по длине то найти
наибольшее.
;Если числа равны то вывести 0 на экран
;Если второе число меньше первого то выставить
флаг и поставить знак "-"
xor ax,ax
xor bx,bx
xor di,di al,a+1 bl,b+1 ax,bx c11 c12: al,a+1 di,ax w3 al,a1[di] bl,b1[di] ax,bx
je w1 c12 w2:
inc di c11: znak,'-' flag,1 c12: dx,
s3 ah, 09H 21H dx, NULL ah, 09H 21H eoj
c12:
;Приведение чисел во внутреннее представление
;1е число к виду 01 02 03 04 05 ax,
ax
xor si,
si
xor bx,
bx
mov bl, a+1: di,
di al, a1[si]
e2: al, Tabl[di] e3 di di,
10 e2
e3: ax, di a1[si],al
inc si si,
bx e4
jne e1
;перевод к виду 01 23 45
e4: ax, ax bx,
bx
xor si, si al, a+1 si,
ax di, di di, si ax, ax di si, 2
mov a1[2],'#': si,
1
jne e5 r1: ;если
число из 1го символа
jmp r2: si si
mov al, a1[si] ;умножаем n число
на 10
mov bl, 10h bl si
mov bl, a1[si] ;прибавляем к
получившемуся n+1 элемент и пишем в diый
add al, bl a1[si],
0 si a1[si], 0 a1[di], al di
cmp si, 1 e6 e6 e5: al,
a+2
mov a1[di], al ax,ax al,a+1 ax,2 r2 a+2,
0 ax,3
je r2 a+3, 0
;2е число к (01 02 03 04 05):
r2:
xor ax,
ax
xor si,
si
xor bx, bx bl,
b+1
e7: di, di al,
b1[si]: al, Tabl[di] e9 di di,
16 e8
e9: ax, di b1[si],al si
cmp si, bx e10 e7
;к виду 01 23 45: ax, ax
xor bx,
bx
xor si,
si
mov al, b+1 si, ax di,
di di, si ax, ax
dec di si, 2 ob3
jne ob4: ;если
число из 2х символов(на всякий случай чистим b1[2])
mov b1[2],0: si,
1 e11
je r3: ;если
число из 1го символа
jmp r4: si si
mov al, b1[si] ;умножаем n число
на 10
mov bl, 10h bl si
mov bl, b1[si] ;прибавляем к
получившемуся n+1 элемент и пишем в diый
add al, bl b1[si],
0 si b1[si], 0 b1[di], al di
cmp si, 1 e12 e12 e11: al,
b+2
mov b1[di], al ax,ax al,b+1 ax,2
je r4 b+2, 0 ax,3 r4
mov b+3, 0:
;Сохраняем длины чисел
xor ax,axal,a+1 dlina_1,alal,b+1
mov dlina_2,al
;############################################################
;Выделение памяти и запись чисел в выделенную
память
;############################################################
;Выделяем память под первое число bx,zseg
;получаем # параграфа конца программы + 1 ax,es ;получаем
# параграфа начала программы bx,ax ;вычисляем
размер программы в параграфах ah,4AH ;номер
функции 21H ;освобождаем память ah,48H ;номер
функции bx,128 ;требуем 128 параграфа 21H ;пытаемся
отвести блок BLOCK_SEG1,ax ;сохраняем адрес блока
;запись первого числа ax,ax
xor di,di si,si
mov al,a+1 si,ax ax,ax si es,
BLOCK_SEG1 ;пишем в
es адрес
блока
cmp si,0 Zap_sim1 Zap1
Zap_sim1: al,a1[si]
mov es:[di],al Zap2
Zap1: al,a1[si]
mov es:[di],al di si si,0 Zap2
jne Zap1:
;Выделяем память под второе число bx,zseg
;получаем # параграфа конца программы + 1 bx,128 ax,es
;получаем # параграфа начала программы bx,ax ;вычисляем
размер программы в параграфах ah,4AH ;номер
функции 21H ;освобождаем память ah,48H ;номер
функции bx,128 ;требуем 128 параграфа 21H ;пытаемся
отвести блок BLOCK_SEG2,ax ;сохраняем адрес блока
;запись второго числа ax,ax
xor di,di si,si
mov al,b+1 si,ax ax,ax si es,
BLOCK_SEG2 ;пишем в
es адрес
блока
cmp si,0 Zap_sim2 Zap3_sim2: al,b1[si] es:[di],al Zap4: al,b1[si] es:[di],al di si si,0 Zap4 Zap3:
;выделяем память под результат bx,zseg
;получаем # параграфа конца программы + 1 bx,256 ax,es
;получаем # параграфа начала программы bx,ax
;вычисляем размер программы в параграфах ah,4AH
;номер функции 21H ;освобождаем память ah,48H
;номер функции bx,128 ;требуем 128 параграфа 21H
;пытаемся отвести блок REZ,ax ;сохраняем
адрес блока
;############################################################
;Подготовка к вычитанию и вычитание
;############################################################
;работа с числами al,dlina_1 bl,dlina_2 al,bl ;проверка
на длину числа
je ss1 ss2 ss3
ss1: ;если
равны по длине al, flag
cmp al,0 Nachalo ss1_1
ss1_1: al,dlina_1 bl,dlina_2 dlina_1,bl dlina_2,al
mov es,BLOCK_SEG1 buf,es es,BLOCK_SEG2 BLOCK_SEG1,es es,buf BLOCK_SEG2,es
jmp Nachalo: znak,'-' ss1_1::
;Вычитание di,di si,si ax,ax al,dlina_2 si,ax
call vsub ;вызов вычитания
;Вывод ответа ax, ax
xor bx, bx al,dlina_1
mov di, ax es,REZ es:[di],0 viv1 vivod1: di es:[di],0
je viv1 dx,
s3 ah, 09H 21H dx, znak ah, 09H 21H: al,
es:[di] al, 4 al, 30h simvol, al dx,
simvol ah, 09H 21H al, es:[di] al,
0FH al, 30h simvol, al dx, simvol ah,
09H
int 21H di,0 vivod2
dec di vivod1:
;############################################################
;Освобождение выделенной памяти после вычитания
;############################################################
;---освобождаем 1й блок ax,
BLOCK_SEG1 ;получаем стартовый адрес блока es, ax ;помещаем
его в ES ah, 49H ;номер требуемой функции 21H ;освобождаем
блок памяти
;---освобождаем 2й блок ax,
BLOCK_SEG2 ;получаем стартовый адрес блока es, ax ;помещаем
его в ES ah, 49H ;номер требуемой функции 21H ;освобождаем
блок памяти
;---освобождаем блок результата ax,
REZ ;получаем стартовый адрес блока es, ax ;помещаем
его в ES ah, 49H ;номер требуемой функции 21H ;освобождаем
блок памяти
;Конец программы
eoj: mov ah, 4CH 21H endp
;Функция
"Вычитание"proc: es,BLOCK_SEG1 al,es:[di] ;
в
al разряд
первого
числа
mov es,BLOCK_SEG2 bl,es:[di] ;в
bl разряд
второго
числа
jc V2 ;
jc - был ли займ, если да то v3 si,0 ;проверка
на конец числа Konec al,bl ;
вычитание с займом ;
коррекция es,REZ es:[di],al ;
сохранение результата
inc di si V1
V2: al,bl es,REZ es:[di],al di
dec si V1: bx,bx bl,dlina_1
mov es,REZ es:[di],al di,bx m: di es,BLOCK_SEG1 al,es:[di] es,REZ es:[di],al di,bx metka
m:
ret
vsub
endp
;вывод ошибки и переход к концу программы(eoj)
Error
proc
lea
dx, er
mov
ah, 09H21Heojendp
;Очистка экрана
ClrScr procbpbp, spaxah, 0al,
210haxbp
retendp
;Установка курсора в нужное положение на экране
CXY procbpbp, spaxbxdxbh, 0ah, 2dx,
[bp + 4]10hdxbxaxbpendp
Prog1 endsSEGMENTENDS proc1