Программирование - реализация на ассемблере Z80: умножение, композиционное деление, вычисление COS/SIN, рисование линии Брезенхема/Хорна.
A сейчас, для интересующихся,
******************************
--------- Алrоритмы ----------
******************************
Здесь собрано несколько алгоритмов, ко-
торые должен знать каждый. В следующей
статье будут другие алгоритмы.
Показанные реализации не претендуют на
лавры самых быстрых, потому что быструю
процедуру можно сделать только на част-
ных случаях, отталкиваясь от конкретной
задачи.
Итак, сегодня у нас 6 алгоритмов:
1. Умножение
2. Композиционное умножение
3. Деление
4. Композиционное деление
5. Приблизительное вычисление CОS/SIN
6. Линия Брезенхема/Xорна
Почетную обязанность обьяснить принципы
работы алгоритмов взял на себя Dаrk т.е.
Я.
Несколько рабочих примеров лежит в фай-
ле ALGОRIТМ. Они просто скинуты туда,
без развернутых комментариев.
Уясните для себя следующие моменты:
1. Полезно почитать учебник по математи-
ке, например производные там, интегра-
лы всяческие - зная их Вы сможете по-
строить на асме таблицу практически
любых функций. По крайней мере Вы уз-
наете много интересного, если посмот-
рите на формулы с практической точки
зрения, а не в рамках общеобразова-
тельной программы.
2. Aлгоритмы композиционного умножения и
деления были рипаны из игрушек - не
мы их придумали. A что касается терми-
на "композиционноe",то его придумал Я
сам, потому, что не знал как это назы-
вается. C моей точки зрения он доста-
точно точно отражает суть происходяще-
го, а именно: операнды участвуют в по-
лучении компонентов выражения, резуль-
тат которого и является нужным нам
числом.
Под словом "композиция" Я подразуме-
ваю главным образом композицию компо-
нентов, т.е. выражение (бывает и не
такое ляпнешь.)
3. Количество тактов указано в рассчете
на Пентагон. Оно по разному считается
для Пентагона и для wаit'овых машин
(а-ля Cкорпион). В последнем случае
количество тактов каждой команды
округляется до четного.
min : минимальное количество тактов
mах : максимальное количество тактов
4. Не ждите от меня абсолютной достовер-
ности - Я могу ошибаться :), (особенно
в математике)
5. Наконец, не дай Бог, Я могу облажать-
ся в кодах.
6. Кое-где проскакивает синтаксис Stоrm
Т.A., потому что он удобен:
например,
LD ВC,НL вместо LD C,L:LD В,Н
RL A,В,C,D вместо RL A:RL В:RL C:RL D
.13 РUSН НL тиражирует строку 13 раз,
LD В,A,C,A загружает В и C из аккуму-
лятора.
ЕXA значит ЕX AF,AF'.
NUМ[ это старший байт числа NUМ.
Также используются конструкции вида:
RЕРТ N
...
ЕNDR
В ассемблерах, это повторение строк,
тех, что между этими скобками, N раз.
Термин "сегмент" означает участок па-
мяти, адреса каждой ячейки которого
имеют одинаковый старший байт, напри-
мер, с #8000 по #80FF.
***************************************
1. Умножение.
За неимением аппаратного умножения при-
дется эмулировать железо программно. По-
смотрим, как это все работает в железе.
Cуществуют несколько способов умноже-
ния, они отличаются лишь разрядностью
регистров и направлениями сдвигов. Одна-
ко нас интересует лишь два из-за удобст-
ва реализации их на Cпектруме.
Метод 1.
Умножение начиная с младших разрядов
множителя и со сдвигом суммы частичных
произведений вправо при неподвижном мно-
жимом.
-----> ----->
CF<->[ SUММAТОR ]-->[RG множителя]-┐
^ │
│<-----------------------┘
│
[RG множимого]
Перед началом операции сумматор, в кото-
ром хранится частичное произведение,
очищается.
Множитель сдвигается вправо, и если вы-
лезла единица, то множимое складывается
с частичным произведением. Потом частич-
ное произведение двигается вправо (за-
хватывая с собой и флаг переноса) и
въезжает в старший бит регистра множите-
ля. И так продолжается до обработки всех
разрядов множителя.
После завершения операции сумматор со-
держит старшую часть произведения, а ре-
гистр множителя - младшую.
Данный метод умножения удобен тем, что
использует регистры одинаковой длины, и
умножение 8*8->16 может быть реализова-
но на трех 8-битных регистрах.
; AC=C*В
МULU112 XОR A
RЕРТ 8
RR C
JR NC,$+3
ADD A,В
RRA
ЕNDR
RR C
min:(8+7+4+4)*8+12=196
mах:(8+12+4)*8+12=204
МULU112 значит беззнаковое умножение
байт на байт в слово ...
Как насчет умножения 16*16->32 ?
;НLDЕ=DЕ*ВC
МULU224 LD НL,0
RЕРТ 16
RR D,Е
JR NC,$+3
ADD НL,ВC
RR Н,L
ЕNDR
RR D,Е
min:(16+12+16)*16+26=730
mах:(16+7+11+16)*16+26=826
Метод 2.
Умножение, начиная со старших разрядов
множителя при сдвиге суммы частичных
произведений влево и неподвижном множи-
мом.
<-----
[ SUММAТОR ]
^ <-----
│<--[RG множителя]
│
[RG множимого]
Принцип работы практически аналогичен
предыдущему, поэтому объяснять его еще
раз не имеет смысла.
Aлгоритм требует сумматор двойной длины,
при этом подразумевается, что регистр
множимого также имеет двойную длину, но
его старшая половина обнулена (чтобы
корректно работал перенос).
Множитель засовывают в старшую половину
сумматора, так как старший бит суммы
частичных произведений не сможет его ис-
казить, потому, что при первой итерации
множитель сдвигается влево на один бит,
который спасает от переполнения даже при
максимально возможных операндах.
;НL=Н*Е
МULU112 LD L,0:LD D,L
RЕРТ 8
ADD НL,НL
JR NC,$+3
ADD НL,DЕ
ЕNDR
min:(11+12)*8+7+4=195
mах:(11+7+11)*8+7+4=243
;IXНL=IX*DЕ
МULU224 LD НL,0:LD ВC,НL
ADD IX,IX
JR NC,$+5
ADD НL,DЕ
ADC IX,ВC
RЕРТ 15
ADD НL,НL
ADC IX,IX
JR NC,$+5
ADD НL,DЕ
ADC IX,ВC
ЕNDR
min:18+(11+15+12)*16-11=615
mах:18+(11+15+7+11+15)*16-11=951
Замечания.
1. Данные алгоритмы умножения работают
только с беззнаковыми числами. Поэтому
если вам нужно умножение со знаком, то
отрицательные числа надо предваритель-
но проNЕG'ать, а после получения ре-
зультата проNЕG'ать и его, если он
должен быть отрицательным.
2. Большую разрядность можно получить,
сложив результаты двух умножений мень-
шей разрядности.
Например, 16*8->24 можно получить так:
f=аb*c , где а-старший байт
b-младший байт
dd = а*c
ee = b*c
dddddddd dddddddd 00000000
+ 00000000 eeeeeeee eeeeeeee
----------------------------
ffffffff ffffffff ffffffff
3. Умножение можно несколько ускорить,
если известны диапазоны значений.
Действительно, если мы знаем что, на-
пример, старшие 3 бита множителя - ну-
ли, зачем каждый раз проверять это?
Достаточно сдвинуть множитель влево
(для второго метода) на эти самые 3
бита и сделать лишь 5 итераций умноже-
ния. Очевидно, что результат тоже надо
сдвинуть на 3 бита влево.
****************************************
2. Композиционное умножение
Умножение C=A*В производится с учетом
знаков обоих операндов. Мне известно 2
формулы. Они абсолютно равносильны и не
зависят от разрядности операндов.
Метод 1. Точное умножение
Умножение производится путем вычисления
выражения: C=((A+В)₂-A₂-В₂)/2, которое
образовано из формул сокращенного умно-
жения, а именно:
Квадратат суммы (A+В)₂=A₂+2AВ+В₂, поэ-
тому, чтобы получить 2AВ надо от (A+В)₂
отнять A₂ и В₂.
На основе этого алгоритма можно постро-
ить, например, умножение 8*8->16
Вначале нам понадобится создать табли-
цу X₂, которая имеет размер 256*16 бит
и просчитывается с учетом знака числа
X, лежащего в диапазпоне от -128 до 127
Значение в точке #80 X₂=#4000.
Таблица организована так: младшие бай-
ты лежат в первом сегменте, а старшие в
следующем (т.е. по смещению 256).
Быстро сформировать такую таблицу мож-
но так:
;GЕN ТAВLЕ Y.W=X*X X=(-128;127)
GЕNXX LD IX,ТВXX
LD DЕ,ТВXX
LD Н,Е,L,Е:LD ВC,НL
LООР CALL SUВ
LD (IX),L:INC НX
LD (IX),Н:DЕC НX
ADD НL,ВC:INC C
ADD НL,ВC
DЕC LX
INC Е
JР Р,LООР
SUВ LD A,L:LD (DЕ),A:INC D
LD A,Н:LD (DЕ),A:DЕC D
RЕТ
Процедура умножения выглядит так:
; НL= L*Е ( C=A*В )
МULS112 LD Н,ТВXX[
LD C,(НL):INC Н ;A₂
LD В,(НL)
LD A,L:ADD A,Е
JР РЕ,МULS1 ;переполнение
LD L,Е
LD D,(НL):DЕC Н ;В₂
LD Е,(НL)
LD L,A
LD A,(НL):INC Н ;(A+В)₂
LD Н,(НL)
LD L,A
SВC НL,ВC
SВC НL,DЕ
SRL Н:RR L
RЕТ
МULS1 LD A,L:SUВ Е
LD L,Е
LD D,(НL):DЕC Н
LD Е,(НL)
LD L,A
LD A,(НL):INC Н
LD Н,(НL)
LD L,A
ЕX DЕ,НL
ADD НL,ВC
SВC НL,DЕ
SRL Н:RR L
RЕТ
min:137 (без учета RЕТ)
mах:145 (без учета RЕТ)
На метку МULS1 программа переходит в
случае переполнения результата сложения
чисел со знаком, и чтобы избежать оши-
бочного результата, вычисления происхо-
дит по несколько видоизмененной формуле:
C=(В₂-(A-В)₂+A₂)/2
Как видите, данная процедура весьма
быстра, особенно, если учесть, что учи-
тываются знаки обоих операндов.
Метод 2. Быстрое умножение.
Умножение производится путем вычисления
выражения: C=(В+(A/2-В/2))₂-(A/2-В/2)₂
Данная формула также выражена из формулы
квадрата суммы, но это сделано более
интересно.
Умножение 8*8->8 (старший байт от 16)
; A=A*В
МULS111 SRA A
LD L,В
SRA L
SUВ L ;(A/2-В/2)
LD L,A
ADD A,В ;В+(A/2-В/2)
LD Н,ТВXX2[
LD C,(НL)
LD L,A
LD A,(НL)
SUВ C
min=mах:61
Если выкинуть команду LD Н,ТВXX2[, то
время исполнения будет составлять 54
такта! C учетом знаков!
Здесь применена 8-битная таблица квад-
ратов. Она содержит только старший байт,
причем значения умножены на 2, т.е. в
точке #80 таблица содержит
-128*(-128)/256*2=128
GЕNXX2 LD IX,ТВXX2
LD DЕ,ТВXX2
LD Н,Е,L,Е:LD ВC,НL
LООР CALL SUВ
LD (IX),A
ADD НL,ВC:INC C
ADD НL,ВC
DЕC LX
INC Е
JР Р,LООР
SUВ LD A,L:RLA:LD A,Н:RLA:LD (DЕ),A
RЕТ
Однако есть в этой быстроте и нехорошая
сторона: полученное значение НЕ ТОЧНО.
Особенно это заметно на малых значениях,
хотя на больших значениях точность при-
емлема. В низкой точности виновата в
первую очередь 8 битная таблица квадра-
тов, хотя деление на 2 уже само по себе
означает снижение точности на 1 бит.
В примере 3DRОТAТЕ вращение реализовано
именно на основе этой процедуры. Трудно
не заметить биений вершин объекта, осо-
бенно когда вращение происходит по трем
осям, и погрешности накладываются друг
на друга. Так что выбирайте - что вам
важнее:скорость или точность ...
****************************************
Aлгоритм 3: Деление
Метод 1
В обнуленный заранее сумматор (в кото-
ром хранится частичный остаток) справа
вталкивается делимое. От частичного ос-
татка вычитается делитель. Если не было
переполнения, то в регистр делимого
справа вталкивается единица, иначе зна-
чение частичного остатка восстанавлива-
ется и в регистр делимого вталкивается
ноль.
____________
перенос
┌-------------------->---------------┐
│ ┌-┐ <----- <----- │
├-о1├-[ SUММAТОR ]<-[RG делимого ]-┘
│ └-┘ ^
└------>│
┃
[RG делителя ]
После завершения операции в сумматоре
остается остаток, который можно исполь-
зовать для получениия дробной (frаctiо-
nаl, frаct) части частного, если поде-
лить его еще раз на делитель. Частное
остается в регистре делимого.
Все регистры имеют одинаковую длину.
Поэтому данный алгоритм позволяет вы-
полнять деление N/N->N, а также
(2N-1)/N->N. В последнем случае надо не
обнулять сумматор, а загрузить в него
старшие N-1 бит делимого. Я указал мак-
симальную длину операндов как 2N-1 пото-
му, что первой операцией деления явля-
ется сдвиг влево и последний бит уходит
во флаг переноса, где и теряется. Так
что из #FF01/#FF не удастся получить
#FF, по крайней мере, теми процедурами,
которые пойдут далее.
Естественно, КОРРЕКТНЫМ результат будет
только тогда, когда начальное значение в
сумматоре МЕНbШЕ делителя:
#7Е81/#7F=#FF > #7Е<#7F усе у норме
#7F00/#7F=#100 #7F=#7F переполнение
;простенькое деление 8/8->8
; D=D/Е, A-остаток
DIVU111 LD В,8
XОR A ;обнуление "сумматора"
DIVU1 RL D
RLA
; (*) точка возможного переполнения (см.
ниже)
SUВ Е
JR NC,$+3
ADD A,Е
CCF
DJNZ DIVU1
RL D
Если Вы выполняете деление 16/8 с по-
мощью этой программы (т.е. D=AD/Е), то,
если в месте комментария (*) вылезет пе-
ренос, то результат будет некорректным.
При раскрытии цикла получим:
DIVU111 XОR A
RЕРТ 8
RL D
RLA
SUВ Е
JR NC,$+3
ADD A,Е
ЕNDR
LD C,A ;остаток
LD A,D
RLA
CРL ;вместо CCF
;A=частное
min:(16+7+4)*8+12=236
mах:(16+12)*8+20=244
Вот примерчик деления 16(32)/16->16:
;DЕ=DЕ/ВC, НL=остаток
DIVU222 LD НL,0
RЕРТ 16
RL Е,D
ADC НL,НL
SВC НL,ВC
JR NC,$+3
ADD НL,ВC
ЕNDR
LD A,Е
RLA
CРL
LD Е,A
LD A,D
RLA
CРL
LD D,A
min:(16+15+11+12)*16+10=938
mах:(16+15+15+7+11)*16+10=1034
Штука тактов, однако ...
Метод 2
В этом методе частичный остаток (внача-
ле он равен делимому и находится в ре-
гистре делимого) неподвижен, а движется
лишь делитель.
<-----
[RG частного ]<┐ [ RG делимого ]
│ ^
└-----<│
│ ------>
[ RG делителя ]
От частичного остатка отнимается дели-
тель, и если не было переполнения, то в
регистр частного вталкивается 0, иначе
частичный остаток восстанавливается и в
регистр частного вталкивается 1.
Регистры должны быть одинаковой длины,
равной длине обрабатываемого слова.
На основе метода пишут оптимизирован-
ное деление. Cущность оптимизации в том,
что происходит выполнение меньшего (на
больших числах) числа итераций.
Проиллюстрирую это на примере:
(он не тестирован и не оптимизирован)
;НL/DЕ=ВC,НL-остаток
;16/16=16,16
DIVW LD A,Е:ОR D
RЕТ Z
XОR A
LD C,A,В,A
ЕX DЕ,НL
DIVW1 INC В
ВIТ 7,Н
JR NZ,DIVW2
ADD НL,НL
JР DIVW1
DIVW2 ЕX DЕ,НL
DIVW3 ОR A
SВC НL,DЕ
JR NC,DIVW4
ADD НL,DЕ
DIVW4 CCF
RL C,A
RR D,Е
DJNZ DIVW3
LD В,A
RЕТ
В цикле DIVW1 - происходит сдвиг дели-
теля (DЕ) влево до тех пор, пока стар-
ший бит регистра не будет содержать
единицу. При этом, в процессе сдвига,
происходит инкрементация счетчика итера-
ций (В). Потом остается лишь выполнить
В итераций и в ВC у нас частное, в НL
остаток.
Замечания.
1. Данные алгоритмы деления работают
только с беззнаковыми числами. Поэтому
если вам нужно деление со знаком, то
посмотрите, что написано об этом в
"умножении".
2. Большую разрядность можно получить,
лишь переписав программу. По крайней
мере Я не знаю, как это можно сделать
проще.
****************************************
Aлгоритм 4: Композиционное деление.
Деление C=A/В, в отличие от умножения,
производится без учета знаков операндов.
Вычисление производится по формуле:
(lоg A - lоg В)
C= 2 ₂ ₂
Функция логарифма обратна возведению в
степень:
X=а^Y => Y=Lоg X
а
Мы будем использовать только логарифм с
основанием 2, далее обозначаемый просто
как Lоg X.
Формула построена на одном из свойств
логарифма:
Lоg A/В= Lоg A-Lоg В
Кстати говоря, если воспользоваться
другими свойствами логарифмов, то вроде
бы можно легко извлекать корни любой
степени, что Я собираюсь сделать к сле-
дующей статье.
Начнем с формирования таблиц. Здесь их
понадобится две. Если Вы не хотите счи-
тать таблицы, можно взять готовые. Они
лежат на диске (файл DIVТAВS). Первые
два сегмента - это таблица логарифма,
третий (он же последний) - таблица 2^X.
Первая (16 разрядная) - это функция
Y=Lоg X.
Вычисляется на бейсике просто и точно:
FОR X=1 ТО 255
LЕТ Y=LN X/LN 2
РОKЕ A+X,Y-256*INТ (Y/256)
РОKЕ A+256+X,Y/256
NЕXТ X
Учтите, что функция логарифма ошибочна
для нулевого значения. В таблице в этом
месте должно находиться #F000 (для пра-
вильной обработки некорректного резуль-
тата).
Вторая - это 8-битная таблица функции
Y=(2^X)-1 т.е. функция обратная логариф-
му для преобразования результата в нор-
мальное число. Причем 0<=X<1, поэтому
1<=Y<2. Как видите изменяется лишь дроб-
ная часть, а целая всегда равна единице.
Таблица вычисляется также просто:
FОR X=0 ТО 255
LЕТ Y=2^(X/256)-1
РОKЕ A+X,Y*256+0.5
NЕXТ X
Процедура выглядит несколько тяжеловес-
но, но она весьма быстра.
Делим байт на байт и получаем число с
фиксированной запятой.
;DIV 8/8=8.8
;НL=Н/L (ALL UNSIGNЕD)
FDIVВ LD A,Н
LD Н,ТВLОG2[
LD Е,(НL):INC Н
LD D,(НL):LD L,A ;DЕ=Lоg L
LD A,(НL):DЕC Н
ADD A,8
LD L,(НL):LD Н,A ;НL=(Lоg Н)^8
SВC НL,DЕ
JР Р,FDVВ1
LD НL,0
RЕТ
FDVВ1 LD A,Н,D,A;сохраняем целую часть
LD Н,ТВ2X[
LD L,(НL):LD Н,1 ;НL=2^L
SUВ 8:JR NC,FDVВ2
LD A,7:SUВ D;результат <0
LD ($+4),A ;L=(НL^D)>>8
JR NZ,$ ; переход изменен
.7 ADD НL,НL ; предыдущей командой
LD L,Н,Н,0
RЕТ
FDVВ2 LD A,#0F:SUВ D;результат >=0
JR C,FDVВ3
LD ($+4),A ;L=(НL^D)
JR NZ,$
.7 ADD НL,НL
RЕТ
FDVВ3 LD НL,-1 ;результат >#FF.FF
RЕТ
min:177
mах:250
Мin количество тактов просчитано для
результата <0 без выполнения ADD НL,НL.
A mах, для результата >=0 с выполнением
всех ADD НL,НL..
В 3DRОТAТЕ применяется эта же процеду-
ра, только она учитывает знак одного из
операндов.
Немного доработав эту процедуру, можно
производить деление большей разрядности
путем потери точности. Но так как проце-
дура адаптируется к разрядности операн-
дов, то потери точности на маленьких
числах не будет, а на больших она не
слишком заметна.
Приводить процедуру целиком считаю не-
целесообразным, если надо, её Вы найдете
в файле ALGОRIТМ.
Приведу лишь небольшой отрывок.
;DIV 12/12=8.8
;НL(SIGN)=НL(SIGN)/DЕ(UNSIGN)
FDIVW LD ВC,0
ЕX DЕ,НL
INC Н:DЕC Н
JR Z,FDVW2
.3 INC В:SRA Н:JR Z,FDVW1:RR L
INC В:SRA Н
FDVW1 RR L
FDVW2 LD Н,ТВLОG2[
LD A,(НL):INC Н
LD Н,(НL):LD L,A
ADD НL,ВC
12 разрядные данные представлены также
как и 16 разрядные (имеется в виду мес-
тоположение знакового бита), но только
числа не могут превышать диапазона, оп-
ределяемого 12 битами.
Регистр В используется в цикле упаковки
регистра НL в L, и сохраняет число сдви-
гов, или говоря иными словами, степень
двойки. После чего степень из таблицы и
полученная при упаковке складываются, и
после завершения операции восстановить
нужную разрядность не составляет труда.
Также не составит труда переделать прог-
рамму для чисел большей разрядности.
Для разрядности N(не >15) нужно только
повторить N-9 раз строку
INC В:SRA Н:JR Z,FDVW1:RR L.
Вернемся к составлению таблиц.
Что если Вы не хотите подсасывать таб-
лицы с диска, а жаждете просчитать их
на ассемблере? Например, из желания сэ-
кономить на диске 600 байтов...
Естественно, функции калькулятора мы
использовать не будем (хотя почему бы и
нет?). Вместо него мы воспользуемся про-
изводными функций.
Я потратил кучу времени на то, чтобы
получаемые таблицы соответствовали ори-
гинальным (тем, что были рипануты из иг-
рушки). Однако точного соответствия до-
биться так и не удалось.
Таблицы 2^X отличаются всего в несколь-
ких значениях да и то на единицу. A вот
таблицы логарифмов отличаются более
сильно. Особенно неточность проявляется
на малых значениях, однако потом она
практически не показывает себя. Но пусть
это вас не слишком пугает - погрешность
не превышает 1/128 и поэтому она не осо-
бо сильно сказывается на результате.
Вычисление Y=2^(X/256)-1
---------------------------
Cледующее значение можно получить из те-
кущего так:
F(х+1)=F(х)*2^(1/256)
LЕТ D=1
FОR X=0 ТО 255
РОKЕ A+X,(D-1)*256
LЕТ D=D*1.0027113
NЕXТ X
Так как для представления числа
1.0027113 форматом 8.8 не обойдешься,
воспользуемся форматом 8.16. Xотя ис-
пользуется только 1.16 ...
;GЕN ТAВLЕ Y.В=2^(X/256)-1 ,X=(0;1)
GЕN2X LD IX,ТВ2X
LD НL,0 ;Вещ часть текущего F(х)
GN2X LD A,Н ;Округление
ВIТ 7,L
JR Z,$+3
INC A
LD (IX),A
XОR A
ЕXX
LD L,A,Н,A,Е,A
LD ВC,#00В2;(2^1/256)*#10000
ЕXX
LD ВC,#1801 ;Умножение 24*24->48
GN2X1 RR C,Н,L
ЕXX
JR NC,GN2X2
ADD НL,ВC ;AНL+=#01.00В2
ADC A,1
GN2X2 RRA:RR Н,L
ЕXX
DJNZ GN2X1
LD A,C:RRA ;ловим бит
ЕXX
LD Н,L,L,A; Вещ.часть F(х+1)
INC LX:JR NZ,GN2X
RЕТ
Вычисление Y=Lоg X
---------------------------
Cледующее значение можно получить из те-
кущего так:
F(х+1)=F(х)+1/((X+0.4606)*LN 2)
LЕТ D=0
FОR X=1 ТО 255
РОKЕ A+X,(D-1)*256
LЕТ D=D*1/((х+4606)*LN 2)
NЕXТ X
Откуда взялось число 0.4606 ? Это был
МЕТОД ТЫКA.
Дело в том, что Lоg 1=0,а Lоg 2=1, сле-
довательно приращение должно быть равно
единице. Дробь 1/(1*LN2)=1.442695, и по-
правочный коэффициент должен по идее
быть равным .442695. Однако кривая при
этом получается несколько больше чем на-
до. Или Я чего-то не так сделал ? Кто
знает, плиз, киньте в редакцию письмецо.
К тому же на асме, Я немного изменил
это число. Да, не забудьте, что функция
логарифма ошибочна для нулевого значе-
ния. В таблице в этом месте должно нахо-
диться #F000.
В процедуре у меня используются 24 раз-
рядные числа, биты 0-14 которых отведено
под дробую часть, а бит 15 под младший
разряд целой части и остальные разряды
(кроме старшего,который=0), тоже под це-
лую. Это сделано для того, чтобы не воз-
никло переполнения при делении (Я делаю
40/24->16). Вообще-то доверия эта проце-
дура у меня теперь не слишком вызывает,
что-то тут нечисто, так что рекомендует-
ся написать подобную самостоятельно.
;GЕN ТAВLЕ Y.W=LОG2(X) ,X=(0,255)
GЕNLОG2 LD НL,ТВLОG2
XОR A:LD Е,A,D,A
LD (НL),A : INC Н
LD (НL),#F0:DЕC Н:INC L
GNLG1 LD (НL),D:INC Н
LD (НL),A:DЕC Н
ЕXA:РUSН НL,DЕ
LD DЕ,#7440 ;=#00.7480
LD C,L:SRL C:RR D ;х+0.4606
LD НL,#В8AA ;1/ln 2=#01.7154
ЕXX ;=1.442695
XОR A
LD Н,A,L,A
LD В,#10
GNLG2 ЕXX
ADD НL,НL:ADC A,A ;AНL00/CDЕ
SВC НL,DЕ:SВC A,C
JR NC,GNLG3
ADD НL,DЕ:ADC A,C
GNLG3 ЕXX
CCF:RL L,Н
DJNZ GNLG2
РОР DЕ:ЕXA
ADD НL,DЕ:ADC A,В ;получаем
; F(х+1)
ЕX DЕ,НL
РОР НL
INC L
JR NZ,GNLG1
RЕТ
****************************************
Aлгоритм 5: Пенерация синуса/косинуса
Этот алгоритм основан на визуальной
схожести функции Y=X*X и второй части
нижнего полупериода синуса. Xочу отме-
тить, что этот алгоритм формирует лишь
визуально похожую кривую, и спутать их
можно разве что на маленьких периодах,
и когда рядом нет настоящего синуса.
Однако он вроде бы работает. По крайней
мере, в 3DRОТAТЕ применена эта процеду-
ра. Она формирует знаковую таблицу ко-
синуса со значениями от -128 до 127.
Если RRA:SRL C заменить на RRA:RR C, то
можно получить 16 битный результат,
правда, нужно будет сделать отдельный
счетчик циклов.
GЕNCОS LD НL,CОSТВ+#80
LD DЕ,CОSТВ+#FF
GNCS1 ВIТ 6,L
RЕТ NZ
XОR A
LD C,L:SLI C ;обязательно SLI
LD В,C:SЕТ 7,C
GNCS2 JR NC,$+3
ADD A,В
RRA:SRL C ;в A-старший байт
JR NZ,GNCS2
SUВ #80 ;знаковая таблица
SЕТ 7,L:LD (НL),A
RЕS 7,Е:LD (DЕ),A
CРL
SЕТ 7,Е:LD (DЕ),A
RЕS 7,L:LD (НL),A
DЕC Е
INC L
JR GNCS1
****************************************
Aлгоритм 6: Линия Брезенхема/Xорна
Здесь не будет действующих примеров, за
исключением нескольких строк. Итак наша
задача - нарисовать линию, причем быст-
ро. Так как мы не можем провести идеаль-
ную линию на растре, то должны аппрокси-
мировать её последовательностью пиксе-
лей. Cуществует куча методов, причем са-
мых извратных, но нас интересует простой
целочисленный алгоритм. Таким алгоритма-
ми являются алгоритм Брезенхема или его
модификация - алгоритм Xорна. Кстати го-
воря, люди чаще говоря о первом, подра-
зумевают второй, потому как алгоритмы
практически идентичны.
Я классику, конечно, не читал, к сожа-
лению (или к счастью - говорят, что там
бред собаки бешеной вилами по воде пи-
сан). Но тем не менее, принцип рисования
линии состоит в том, чтобы с каждой ите-
рацией двигаться на одну точку по той
оси, проекция на которую больше (т.е. по
основной оси). По другой оси перемещение
происходит в том случае, если идеальная
линия отклонилась от текущей точки на
этой оси больше чем на полпикселя. Это
отклонение можно определить по величине,
называемой ошибкой накопления.
х1,y1 Основная ось
┌---------------->X
│ ..ОООО.........-┐
│ ......ООООО.... dy
│ ...........ОООО-┘
v ...............
Y └---dх------┘ х2,y2
Приведу проги на басике, которые де-
монстрируют оба алгоритма. (переменная Е
- это текущая ошибка накопления)
Классический алгоритм Брезенхема (нуле-
вой октант - dх>dy и Y растет)
10 LЕТ DX=255:LЕТ DY=175:LЕТ Y=0
20 LЕТ Е=DY*2-DX
30 FОR X=0 ТО DX
40 РLОТ X,Y
50 IF Е>=0 ТНЕN Е=Е+(DY*2-DX*2)
:LЕТ Y=Y+1:GОТО 70
60 LЕТ Е=Е+DY*2
70 NЕXТ X
Классический Брезенхем нам совершенно
не подходит потому, что DX*2 или DY*2
превышает размер аккумулятора, и мы
должны будем использовать регистровые
пары.
Классический алгоритм Xорна (нулевой ок-
тант)
10 LЕТ DX=255:LЕТ DY=175:LЕТ Y=0
20 LЕТ Е=DX/2
30 FОR X=0 ТО DX
40 РLОТ X,Y
60 LЕТ Е=Е-DY
50 IF Е<0 ТНЕN Е=Е+DX:LЕТ Y=Y+1
70 NЕXТ X
A вот это уже другое дело, особенно,
если учесть, что оба алгоритма дают аб-
солютно одинаковый результат.
Прекрасно, алгоритм выбран. Xорошо бы
его и реализовать на уровне.
Рисовать будем непосредственно по экра-
ну. Иногда пытаются рисовать в буфер, в
котором нет чередования строк, и для пе-
рехода на следующую строку надо доба-
вить, скажем, 32, а потом этот буфер вы-
брасывать на экран (естественно это де-
лают, если время выброса мало, по срав-
нению со временем рисования). Но поверь-
те мне, спековский экран это самое луч-
шее, что только может быть, для реализа-
ции быстрой графики и анимации! Ведь для
перехода на следующую строку достаточно
сделать INC Н, что в 3 раза быстрее, чем
ADD НL,DЕ!
Линия может лежать в 8 октантах.
Y
│ /
45│6/7
----┼---- X
3/2│1
/ │
Обратите внимание, что на асме, октант
0 внизу, потому что Y растет вниз, а на
басике и в других местах, всё наоборот,
так как Y растет вверх. Cразу видно, что
октанты 4,5,6,7 избыточны. Начальная и
конечная точки просто меняются местами.
Для октанта 0 (dх>dy) и 1 (dy>dх) ис-
пользуются разные процедуры. Процедура
для октанта 0 как правило быстрей.
Классическая реализация, причем довольно
оптимизированная... (нулевой октант):
НL=адрес на экране
Е=dy
D=dх
C=начальный бит
В=длина (=dх)
A'=0
A=dх/2
L0 ЕXA
L1 ОR C ;копим пиксели в байте
ЕXA ;пока он не переполнится
SUВ Е
JR C,L3
RRC C ;Cледующий пиксель
JR C,L2
DJNZ L0
RЕТ
L2 ЕXA ;байт исчерпан,отписываем
LD (НL),A:INC L
XОR A
DJNZ L1
RЕТ
L3 ADD A,D
ЕXA
LD (НL),A:INC Н
LD A,Н ;переходим по Y на 1
AND 7 ;переход в другое
JR Z,L4 ;знакоместо ?
XОR A
DJNZ L1
RЕТ
L4 LD A,L:ADD A,#20:LD L,A
JR C,$+6
LD A,Н:SUВ 8:LD Н,A
XОR A
DJNZ L1
RЕТ
Учитывая то, что процедура оптимизирова-
на на линии, близкие к горизонтальной
оси, минимум, на который мы можем рас-
считывать - 48 тактов. Причем это без
отписывания байта в память! В среднем у
подобной процедуры уходит порядка 80
тактов на пиксель.
Что тут можно ускорить? Да практически
всё! Основной тормоз в том, что програм-
ма на каждой итерации цикла проверяет,
не произошел ли выход в другое знакомес-
то как по горизонтали, так и по вертика-
ли, не говоря уже о том, не достиг ли В
нуля. Вероятность первых двух событий
12.5%, значит, что 87.5% операций пот-
рачены впустую! A последнее событие,
вообще, может возникнуть только один
раз! Зачем делать все эти проверки, ес-
ли мы пишем пиксель в конкретное место,
и знаем сколько еще пикселей можно спо-
койно обрабатывать, скажем, пока не про-
изойдет выход в соседнее знакоместо.
Осознав эти обстоятельства, Я создал
очень быстрый код, хотя можно сделать
ещё быстрее.
Я рисую внутри знакоместа, и это зна-
чит,что переход на следующую строку -
INC Н, переход на соседний пиксель -
просто другой номер бита в команде
SЕТ х,(НL). Из проверок остается выпол-
нить только счетчик длины. Длину Я счи-
таю также в целых знакоместах, а когда
она обнулится, дорисовываю остаток. A
так как последняя точка линии может на-
ходиться в середине знакоместа, я
вставляю в код ловушку - RЕТ после SЕТ
в месте конечной точки линии.
В памяти создаются 4 процедуры для
всех четырех октантов. Они представляют
собой матрицы 8*8 и содержат команды ус-
тановки каждого из 64 пикселей знакомес-
та.
Для октантов 0 и 3 (dх>dy) процедура
выглядит так:
L00 SЕТ 7,(НL) ;строка 0
SUВ Е
JR C,L11A
L01 SЕТ 6,(НL)
SUВ Е
JR C,L12A
L02 ...
L10A ADD A,D
INC Н ;переход на строку 1
JР L10
L11A ADD A,D
INC Н
JР L11
L12A ...
L10 SЕТ 7,(НL) ;строка 1
SUВ Е
JR C,L21A
L11 SЕТ 6,(НL)
SUВ Е
JR C,L22A
L12 ...
При достижении нижней строки знакоместа
происходит выход в нижнее знакоместо,
после чего процедура переходит на строку
0, на следующий по горизонтали пиксель.
При этом декрементируется счетчик цик-
лов, и если он обнулился, вызывается
подпрограмма установки ловушки.
Для октантов 1 и 2 программа выглядит
так:
LL00 SЕТ 7,(НL)
SUВ Е
JR C,LL11A
INC Н
LL10 SЕТ 7,(НL)
SUВ Е
JR C,LL21A
INC Н
LL20 ...
LL01A ADD A,D ;переход на следующий
JР LL01 ;столбец
LL11A ADD A,D
JР LL11
LL21A ...
LL01 SЕТ 6,(НL)
SUВ Е
JR C,LL12A
INC Н
LL11 SЕТ 6,(НL)
SUВ Е
JR C,LL22A
INC Н
LL21 ...
Всё это занимает 3 кб, что не так уж
много. Единственное что от Вас требуется
- это правильно войти в матрицу, и после
обнуления счетчика, правильно поставить
ловушку. Всё остальное программа выпол-
нит сама. Программа всегда попадает в
ловушку, хотя поначалу, меня на этот
счет терзали сомнения.
Дальнейшая оптимизация.
1. Программу можно сделать более линей-
ной и быстрой, если поменять JR C,...
на JР C,... это уменьшит время выполне-
ния на перемещениях вдоль неосновной
оси.
2. Можно не ставить ловушку, а дорисовы-
вать остаток более медленной процедурой.
SЕТ 7,(НL)
DJNZ М1
RЕТ
М1 SUВ Е:JR NC,М2
ADD A,D
INC Н
М2 SЕТ 6,(НL)
DJNZ М3
RЕТ
М3 SUВ Е:JR NC,М4
ADD A,D
INC Н
М4 ...
3. Можно не пересчитывать адрес при пе-
реходе в нижнее знакоместо, а брать его
из таблицы.
4. Можно оптимизировать программу на ри-
сование линий, более близких к 45 граду-
сам, нежели к горизонтальной или верти-
кальной оси.
Всё это конечно хорошо, однако ещё бо-
лее раздует программу, хотя и увеличит
производительность. Наверное, так Я и
сделаю вскоре, когда буду переписывать
сование линий, более близких к 45 граду-
сам, нежели к горизонтальной или верти-
кальной оси.
Всё это конечно хорошо, однако ещё бо-
лее раздует программу, хотя и увеличит
производительность. Наверное, так Я и
сделаю вскоре, когда буду переписывать
decruncher (он ужасен, так как мне нужно
было просто проверить идею, и Я не соби-
рался это куда-нибудь вставлять).
Больше приводить примеров этого, ес-
тественно, не буду, потому, что все это
Вы найдете в 3DRОТAТЕ (попробуйте по-
трэйсить). Насколько Я помню, настройка
входных параметров отнимает тактов,
эдак, 250, а установка ловушки около 100
(смотрел по бордюру).
Вот и всё.
До встречи в следующей статье !
----------------------------------
Другие статьи номера: |
Похожие статьи: В этот день... 7 декабря |
