|
Spectrum Expert #01
31 октября 1997 |
|
A сейчас, для интересующихся,
******************************
--------- Алгоритмы ----------
******************************
Здесь собрано несколько алгоритмов, ко-
торые должен знать каждый. В следующей
статье будут другие алгоритмы.
Показанные реализации не претендуют на
лавры самых быстрых, потому что быструю
процедуру можно сделать только на част-
ных случаях, отталкиваясь от конкретной
задачи.
Итак, сегодня у нас 6 алгоритмов:
1. Умножение
2. Композиционное умножение
3. Деление
4. Композиционное деление
5. Приблизительное вычисление COS/SIN
6. Линия Брезенхема/Xopha
Почетную обязанность обьяснить принципы
работы алгоритмов взял на себя Dark т.е.
Я.
Несколько рабочих примеров лежит в фай-
ле ALGORITM. Они просто скинуты туда,
без развернутых комментариев.
Уясните для себя следующие моменты:
1. Полезно почитать учебник по математи-
ке, например производные там, интегра-
лы всяческие - зная их Вы сможете по-
строить на асме таблицу практически
любых функций. По крайней мере Вы уз-
наете много интересного, если посмот-
рите на формулы с практической точки
зрения, а не в рамках общеобразова-
тельной программы.
2. Алгоритмы композиционного умножения и
деления были рипаны из игрушек - не
мы их придумали. A что касается терми-
на "композиционноe",то его придумал Я
сам, потому, что не знал как это назы-
вается. C моей точки зрения он доста-
точно точно отражает суть происходяще-
го, а именно: операнды участвуют в по-
лучении компонентов выражения, резуль-
тат которого и является нужным нам
числом.
Под словом "композиция" Я подразуме-
ваю главным образом композицию компо-
нентов, т.е. выражение (бывает и не
такое ляпнешь.)
3. Количество тактов указано в рассчете
на Пентагон. Оно по разному считается
для Пентагона и для wait'овых машин
(а-ля Скорпион). В последнем случае
количество тактов каждой команды
округляется до четного.
min : минимальное количество тактов
мах : максимальное количество тактов
4. Не ждите от меня абсолютной достовер-
ности - Я могу ошибаться :), (особенно
в математике)
5. Наконец, не дай Бог, Я могу облажать-
ся в кодах.
6. Кое-где проскакивает синтаксис Storm
Т.A., потому что он удобен:
например,
LD ВС,HL вместо LD C,L:LD В,Н
RL A,В,C,D вместо RL A:RL В:RL C:RL D
.13 PUSH HL тиражирует строку 13 раз,
LD В,A,C,A загружает В и C из аккуму-
лятора.
ЕХА значит ЕХ AF,AF'.
NUM[ это старший байт числа NUM.
Также используются конструкции вида:
REPT N
...
ENDR
В ассемблерах, это повторение строк,
тех, что между этими скобками, N раз.
Термин "сегмент" означает участок па-
мяти, адреса каждой ячейки которого
имеют одинаковый старший байт, напри-
мер, с #8000 по #8OFF.
***************************************
1. Умножение.
За неимением аппаратного умножения при-
дется эмулировать железо программно. По-
смотрим, как это все работает в железе.
Существуют несколько способов умноже-
ния, они отличаются лишь разрядностью
регистров и направлениями сдвигов. Одна-
ко нас интересует лишь два из-за удобст-
ва реализации их на Спектруме.
Метод 1.
Умножение начиная с младших разрядов
множителя и со сдвигом суммы частичных
произведений вправо при неподвижном мно-
жимом.
-----> ----->
CF<->[ SUMMATOR ]-->[RG множителя]-┐
^ │
│<-----------------------┘
│
[RG множимого]
Перед началом операции сумматор, в кото-
ром хранится частичное произведение,
очищается.
Множитель сдвигается вправо, и если вы-
лезла единица, то множимое складывается
с частичным произведением. Потом частич-
ное произведение двигается вправо (за-
хватывая с собой и флаг переноса) и
въезжает в старший бит регистра множите-
ля. И так продолжается до обработки всех
разрядов множителя.
После завершения операции сумматор со-
держит старшую часть произведения, а ре-
гистр множителя - младшую.
Данный метод умножения удобен тем, что
использует регистры одинаковой длины, и
умножение 8*8->16 может быть реализова-
но на трех 8-битных регистрах.
; AC=C*В
MULU112 XOR A
REPT 8
RR C
JR NC,$+3
ADD A,В
RRA
ENDR
RR C
min:(8+7+4+4)*8+12=196
мах:(8+12+4)*8+12=204
MULU112 значит беззнаковое умножение
байт на байт в слово ...
Как насчет умножения 16*16->32 ?
;HLDE=DE*ВС
MULU224 LD HL,0
REPT 16
RR D,Е
JR NC,$+3
ADD HL,ВС
RR Н,L
ENDR
RR D,Е
min:(16+12+16)*16+26=730
мах:(16+7+11+16)*16+26=826
Метод 2.
Умножение, начиная со старших разрядов
множителя при сдвиге суммы частичных
произведений влево и неподвижном множи-
мом.
<-----
[ SUMMATOR ]
^ <-----
│<--[RG множителя]
│
[RG множимого]
Принцип работы практически аналогичен
предыдущему, поэтому объяснять его еще
раз не имеет смысла.
Алгоритм требует сумматор двойной длины,
при этом подразумевается, что регистр
множимого также имеет двойную длину, но
его старшая половина обнулена (чтобы
корректно работал перенос).
Множитель засовывают в старшую половину
сумматора, так как старший бит суммы
частичных произведений не сможет его ис-
казить, потому, что при первой итерации
множитель сдвигается влево на один бит,
который спасает от переполнения даже при
максимально возможных операндах.
;HL=Н*Е
MULU112 LD L,0:LD D,L
REPT 8
ADD HL,HL
JR NC,$+3
ADD HL,DE
ENDR
min:(11+12)*8+7+4=195
мах:(11+7+11)*8+7+4=243
;IXHL=IX*DE
MULU224 LD HL,0:LD ВС,HL
ADD IX,IX
JR NC,$+5
ADD HL,DE
ADC IX,ВС
REPT 15
ADD HL,HL
ADC IX,IX
JR NC,$+5
ADD HL,DE
ADC IX,ВС
ENDR
min:18+(11+15+12)*16-11=615
мах:18+(11+15+7+11+15)*16-11=951
Замечания.
1. Данные алгоритмы умножения работают
только с беззнаковыми числами. Поэтому
если вам нужно умножение со знаком, то
отрицательные числа надо предваритель-
но npoNEG'ать, а после получения ре-
зультата npoNEG'ать и его, если он
должен быть отрицательным.
2. Большую разрядность можно получить,
сложив результаты двух умножений мень-
шей разрядности.
Например, 16*8->24 можно получить так:
f=аь*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₂+2АВ+В₂, поэ-
тому, чтобы получить 2АВ надо от (A+В)₂
отнять A₂ и В₂.
На основе этого алгоритма можно постро-
ить, например, умножение 8*8->16
Вначале нам понадобится создать табли-
цу X₂, которая имеет размер 256*16 бит
и просчитывается с учетом знака числа
X, лежащего в диапазпоне от -128 до 127
Значение в точке #80 X₂=#4000.
Таблица организована так: младшие бай-
ты лежат в первом сегменте, а старшие в
следующем (т.е. по смещению 256).
Быстро сформировать такую таблицу мож-
но так:
;GEN TABLE Y.W=X*X X=(-128;127)
GENXX LD IX,TBXX
LD DE,TBXX
LD Н,Е,L,Е:LD ВС,HL
LOOP CALL SUB
LD (IX),L:INC НХ
LD (IX),Н:DEC НХ
ADD HL,ВС:INC C
ADD HL,ВС
DEC LX
INC Е
JP Р,LOOP
SUB LD A,L:LD (DE),A:INC D
LD A,Н:LD (DE),A:DEC D
RET
Процедура умножения выглядит так:
; HL= L*Е ( C=A*В )
MULS112 LD Н,TBXX[
LD C,(HL):INC Н ;A₂
LD В,(HL)
LD A,L:ADD A,Е
JP РЕ,MULS1 ;переполнение
LD L,Е
LD D,(HL):DEC Н ;В₂
LD Е,(HL)
LD L,A
LD A,(HL):INC Н ;(A+В)₂
LD Н,(HL)
LD L,A
SBC HL,ВС
SBC HL,DE
SRL Н:RR L
RET
MULS1 LD A,L:SUB Е
LD L,Е
LD D,(HL):DEC Н
LD Е,(HL)
LD L,A
LD A,(HL):INC Н
LD Н,(HL)
LD L,A
ЕХ DE,HL
ADD HL,ВС
SBC HL,DE
SRL Н:RR L
RET
min:137 (без учета RET)
мах:145 (без учета RET)
На метку MULS1 программа переходит в
случае переполнения результата сложения
чисел со знаком, и чтобы избежать оши-
бочного результата, вычисления происхо-
дит по несколько видоизмененной формуле:
C=(В₂-(A-В)₂+A₂)/2
Как видите, данная процедура весьма
быстра, особенно, если учесть, что учи-
тываются знаки обоих операндов.
Метод 2. Быстрое умножение.
Умножение производится путем вычисления
выражения: C=(В+(A/2-В/2))₂-(A/2-В/2)₂
Данная формула также выражена из формулы
квадрата суммы, но это сделано более
интересно.
Умножение 8*8->8 (старший байт от 16)
; A=A*В
MULS111 SRA A
LD L,В
SRA L
SUB L ;(A/2-В/2)
LD L,A
ADD A,В ;В+(A/2-В/2)
LD Н,TBXX2[
LD C,(HL)
LD L,A
LD A,(HL)
SUB C
min=мах:61
Если выкинуть команду LD Н,TBXX2[, то
время исполнения будет составлять 54
такта! C учетом знаков!
Здесь применена 8-битная таблица квад-
ратов. Она содержит только старший байт,
причем значения умножены на 2, т.е. в
точке #80 таблица содержит
-128*(-128)/256*2=128
GENXX2 LD IX,TBXX2
LD DE,TBXX2
LD Н,Е,L,Е:LD ВС,HL
LOOP CALL SUB
LD (IX),A
ADD HL,ВС:INC C
ADD HL,ВС
DEC LX
INC Е
JP Р,LOOP
SUB LD A,L:RLA:LD A,Н:RLA:LD (DE),A
RET
Однако есть в этой быстроте и нехорошая
сторона: полученное значение НЕ ТОЧНО.
Особенно это заметно на малых значениях,
хотя на больших значениях точность при-
емлема. В низкой точности виновата в
первую очередь 8 битная таблица квадра-
тов, хотя деление на 2 уже само по себе
означает снижение точности на 1 бит.
В примере 3DROTATE вращение реализовано
именно на основе этой процедуры. Трудно
не заметить биений вершин объекта, осо-
бенно когда вращение происходит по трем
осям, и погрешности накладываются друг
на друга. Так что выбирайте - что вам
важнее:скорость или точность ...
****************************************
Алгоритм 3: Деление
Метод 1
В обнуленный заранее сумматор (в кото-
ром хранится частичный остаток) справа
вталкивается делимое. От частичного ос-
татка вычитается делитель. Если не было
переполнения, то в регистр делимого
справа вталкивается единица, иначе зна-
чение частичного остатка восстанавлива-
ется и в регистр делимого вталкивается
ноль.
____________
перенос
┌-------------------->---------------┐
│ ┌-┐ <----- <----- │
├-о1├-[ SUMMATOR ]<-[RG делимого ]-┘
│ └-┘ ^
└------>│
┃
[RG делителя ]
После завершения операции в сумматоре
остается остаток, который можно исполь-
зовать для получениия дробной (fractio-
nal, fract) части частного, если поде-
лить его еще раз на делитель. Частное
остается в регистре делимого.
Все регистры имеют одинаковую длину.
Поэтому данный алгоритм позволяет вы-
полнять деление N/N->N, а также
(2N-1)/N->N. В последнем случае надо не
обнулять сумматор, а загрузить в него
старшие N-1 бит делимого. Я указал мак-
симальную длину операндов как 2N-1 пото-
му, что первой операцией деления явля-
ется сдвиг влево и последний бит уходит
во флаг переноса, где и теряется. Так
что из #FFO1/#FF не удастся получить
#FF, по крайней мере, теми процедурами,
которые пойдут далее.
Естественно, КОРРЕКТНЫМ результат будет
только тогда, когда начальное значение в
сумматоре МЕНьШЕ делителя:
#7Е81/#7F=#FF > #7Е<#7F усе у норме
#7F00/#7F=#100 #7F=#7F переполнение
;простенькое деление 8/8->8
; D=D/Е, A-остаток
DIVU111 LD В,8
XOR A ;обнуление "сумматора"
DIVU1 RL D
RLA
; (*) точка возможного переполнения (см.
ниже)
SUB Е
JR NC,$+3
ADD A,Е
CCF
DJNZ DIVU1
RL D
Если Вы выполняете деление 16/8 с по-
мощью этой программы (т.е. D=AD/Е), то,
если в месте комментария (*) вылезет пе-
ренос, то результат будет некорректным.
При раскрытии цикла получим:
DIVU111 XOR A
REPT 8
RL D
RLA
SUB Е
JR NC,$+3
ADD A,Е
ENDR
LD C,A ;остаток
LD A,D
RLA
CPL ;вместо CCF
;A=частное
min:(16+7+4)*8+12=236
мах:(16+12)*8+20=244
Вот примерчик деления 16(32)/16->16:
;DE=DE/ВС, HL=остаток
DIVU222 LD HL,0
REPT 16
RL Е,D
ADC HL,HL
SBC HL,ВС
JR NC,$+3
ADD HL,ВС
ENDR
LD A,Е
RLA
CPL
LD Е,A
LD A,D
RLA
CPL
LD D,A
min:(16+15+11+12)*16+10=938
мах:(16+15+15+7+11)*16+10=1034
Штука тактов, однако ...
Метод 2
В этом методе частичный остаток (внача-
ле он равен делимому и находится в ре-
гистре делимого) неподвижен, а движется
лишь делитель.
<-----
[RG частного ]<┐ [ RG делимого ]
│ ^
└-----<│
│ ------>
[ RG делителя ]
От частичного остатка отнимается дели-
тель, и если не было переполнения, то в
регистр частного вталкивается 0, иначе
частичный остаток восстанавливается и в
регистр частного вталкивается 1.
Регистры должны быть одинаковой длины,
равной длине обрабатываемого слова.
На основе метода пишут оптимизирован-
ное деление. Сущность оптимизации в том,
что происходит выполнение меньшего (на
больших числах) числа итераций.
Проиллюстрирую это на примере:
(он не тестирован и не оптимизирован)
;HL/DE=ВС,HL-остаток
;16/16=16,16
DIVW LD A,Е:OR D
RET Z
XOR A
LD C,A,В,A
ЕХ DE,HL
DIVW1 INC В
BIT 7,Н
JR NZ,DIVW2
ADD HL,HL
JP DIVW1
DIVW2 ЕХ DE,HL
DIVWЗ OR A
SBC HL,DE
JR NC,DIVWЧ
ADD HL,DE
DIVWЧ CCF
RL C,A
RR D,Е
DJNZ DIVWЗ
LD В,A
RET
В цикле DIVW1 - происходит сдвиг дели-
теля (DE) влево до тех пор, пока стар-
ший бит регистра не будет содержать
единицу. При этом, в процессе сдвига,
происходит инкрементация счетчика итера-
ций (В). Потом остается лишь выполнить
В итераций и в ВС у нас частное, в HL
остаток.
Замечания.
1. Данные алгоритмы деления работают
только с беззнаковыми числами. Поэтому
если вам нужно деление со знаком, то
посмотрите, что написано об этом в
"умножении".
2. Большую разрядность можно получить,
лишь переписав программу. По крайней
мере Я не знаю, как это можно сделать
проще.
****************************************
Алгоритм 4: Композиционное деление.
Деление C=A/В, в отличие от умножения,
производится без учета знаков операндов.
Вычисление производится по формуле:
(log A - log В)
C= 2 ₂ ₂
Функция логарифма обратна возведению в
степень:
X=а^Y => Y=Log X
а
Мы будем использовать только логарифм с
основанием 2, далее обозначаемый просто
как Log X.
Формула построена на одном из свойств
логарифма:
Log A/В= Log A-Log В
Кстати говоря, если воспользоваться
другими свойствами логарифмов, то вроде
бы можно легко извлекать корни любой
степени, что Я собираюсь сделать к сле-
дующей статье.
Начнем с формирования таблиц. Здесь их
понадобится две. Если Вы не хотите счи-
тать таблицы, можно взять готовые. Они
лежат на диске (файл DIVTABS). Первые
два сегмента - это таблица логарифма,
третий (он же последний) - таблица 2^X.
Первая (16 разрядная) - это функция
Y=Log X.
Вычисляется на бейсике просто и точно:
FOR X=1 ТО 255
LET Y=LN X/LN 2
РОКЕ A+X,Y-256*INT (Y/256)
РОКЕ A+256+X,Y/256
NEXT X
Учтите, что функция логарифма ошибочна
для нулевого значения. В таблице в этом
месте должно находиться #F000 (для пра-
вильной обработки некорректного резуль-
тата).
Вторая - это 8-битная таблица функции
Y=(2^X)-1 т.е. функция обратная логариф-
му для преобразования результата в нор-
мальное число. Причем 0<=X<1, поэтому
1<=Y<2. Как видите изменяется лишь дроб-
ная часть, а целая всегда равна единице.
Таблица вычисляется также просто:
FOR X=0 ТО 255
LET Y=2^(X/256)-1
РОКЕ A+X,Y*256+0.5
NEXT X
Процедура выглядит несколько тяжеловес-
но, но она весьма быстра.
Делим байт на байт и получаем число с
фиксированной запятой.
;DIV 8/8=8.8
;HL=Н/L (ALL UNSIGNED)
FDIVB LD A,Н
LD Н,TBLOG2[
LD Е,(HL):INC Н
LD D,(HL):LD L,A ;DE=Log L
LD A,(HL):DEC Н
ADD A,8
LD L,(HL):LD Н,A ;HL=(Log Н)^8
SBC HL,DE
JP Р,FDVB1
LD HL,0
RET
FDVB1 LD A,Н,D,A;сохраняем целую часть
LD Н,ТВ2X[
LD L,(HL):LD Н,1 ;HL=2^L
SUB 8:JR NC,FDVB2
LD A,7:SUB D;результат <0
LD ($+4),A ;L=(НL^D)>>8
JR NZ,$ ; переход изменен
.7 ADD HL,HL ; предыдущей командой
LD L,Н,Н,0
RET
FDVB2 LD A,#0F:SUB D;результат >=0
JR C,FDVB3
LD ($+4),A ;L=(HL^D)
JR NZ,$
.7 ADD HL,HL
RET
FDVB3 LD HL,-1 ;результат >#FF.FF
RET
min:177
мах:250
Min количество тактов просчитано для
результата <0 без выполнения ADD НL,НL.
A mах, для результата >=0 с выполнением
всех ADD HL,HL..
В 3DROTATE применяется эта же процеду-
ра, только она учитывает знак одного из
операндов.
Немного доработав эту процедуру, можно
производить деление большей разрядности
путем потери точности. Но так как проце-
дура адаптируется к разрядности операн-
дов, то потери точности на маленьких
числах не будет, а на больших она не
слишком заметна.
Приводить процедуру целиком считаю не-
целесообразным, если надо, её Вы найдете
в файле ALGORITM.
Приведу лишь небольшой отрывок.
;DIV 12/12=8.8
;HL(SIGN)=HL(SIGN)/DE(UNSIGN)
FDIVW LD ВС,0
ЕХ DE,HL
INC Н:DEC Н
JR Z,FDVW2
.3 INC В:SRA Н:JR Z,FDVW1:RR L
INC В:SRA Н
FDVW1 RR L
FDVW2 LD Н,TBLOG2[
LD A,(HL):INC Н
LD Н,(HL):LD L,A
ADD HL,ВС
12 разрядные данные представлены также
как и 16 разрядные (имеется в виду мес-
тоположение знакового бита), но только
числа не могут превышать диапазона, оп-
ределяемого 12 битами.
Регистр В используется в цикле упаковки
регистра HL в L, и сохраняет число сдви-
гов, или говоря иными словами, степень
двойки. После чего степень из таблицы и
полученная при упаковке складываются, и
после завершения операции восстановить
нужную разрядность не составляет труда.
Также не составит труда переделать прог-
рамму для чисел большей разрядности.
Для разрядности N(не >15) нужно только
повторить N-9 раз строку
INC В:SRA Н:JR Z,FDVW1:RR L.
Вернемся к составлению таблиц.
Что если Вы не хотите подсасывать таб-
лицы с диска, а жаждете просчитать их
на ассемблере? Например, из желания сэ-
кономить на диске 600 байтов...
Естественно, функции калькулятора мы
использовать не будем (хотя почему бы и
нет?). Вместо него мы воспользуемся про-
изводными функций.
Я потратил кучу времени на то, чтобы
получаемые таблицы соответствовали ори-
гинальным (тем, что были рипануты из иг-
рушки). Однако точного соответствия до-
биться так и не удалось.
Таблицы 2^X отличаются всего в несколь-
ких значениях да и то на единицу. A вот
таблицы логарифмов отличаются более
сильно. Особенно неточность проявляется
на малых значениях, однако потом она
практически не показывает себя. Но пусть
это вас не слишком пугает - погрешность
не превышает 1/128 и поэтому она не осо-
бо сильно сказывается на результате.
Вычисление Y=2^(X/256)-1
---------------------------
Следующее значение можно получить из те-
кущего так:
F(х+1)=F(х)*2^(1/256)
LET D=1
FOR X=0 ТО 255
РОКЕ A+X,(D-1)*256
LET D=D*1.0027113
NEXT X
Так как для представления числа
1.0027113 форматом 8.8 не обойдешься,
воспользуемся форматом 8.16. Хотя ис-
пользуется только 1.16 ...
;GEN TABLE Y.В=2^(X/256)-1 ,X=(0;1)
GEN2X LD IX,ТВ2X
LD HL,0 ;Вещ часть текущего F(х)
GN2X LD A,Н ;Округление
BIT 7,L
JR Z,$+3
INC A
LD (IX),A
XOR A
EXX
LD L,A,Н,A,Е,A
LD ВС,#00В2;(2^1/256)*#10000
EXX
LD ВС,#1801 ;Умножение 24*24->48
GN2X1 RR C,Н,L
EXX
JR NC,GN2X2
ADD HL,ВС ;AHL+=#01.00В2
ADC A,1
GN2X2 RRA:RR Н,L
EXX
DJNZ GN2X1
LD A,C:RRA ;ловим бит
EXX
LD Н,L,L,A; Вещ.часть F(х+1)
INC LX:JR NZ,GN2X
RET
Вычисление Y=Log X
---------------------------
Следующее значение можно получить из те-
кущего так:
F(х+1)=F(х)+1/((X+0.4606)*LN 2)
LET D=0
FOR X=1 ТО 255
РОКЕ A+X,(D-1)*256
LET D=D*1/((х+4606)*LN 2)
NEXT X
Откуда взялось число 0.4606 ? Это был
МЕТОД ТЫКА.
Дело в том, что Log 1=0,а Log 2=1, сле-
довательно приращение должно быть равно
единице. Дробь 1/(1*LN2)=1.442695, и по-
правочный коэффициент должен по идее
быть равным .442695. Однако кривая при
этом получается несколько больше чем на-
до. Или Я чего-то не так сделал ? Кто
знает, плиз, киньте в редакцию письмецо.
К тому же на асме, Я немного изменил
это число. Да, не забудьте, что функция
логарифма ошибочна для нулевого значе-
ния. В таблице в этом месте должно нахо-
диться #F000.
В процедуре у меня используются 24 раз-
рядные числа, биты 0-14 которых отведено
под дробую часть, а бит 15 под младший
разряд целой части и остальные разряды
(кроме старшего,который=0), тоже под це-
лую. Это сделано для того, чтобы не воз-
никло переполнения при делении (Я делаю
40/24->16). Вообще-то доверия эта проце-
дура у меня теперь не слишком вызывает,
что-то тут нечисто, так что рекомендует-
ся написать подобную самостоятельно.
;GEN TABLE Y.W=LOG2(X) ,X=(0,255)
GENLOG2 LD HL,TBLOG2
XOR A:LD Е,A,D,A
LD (HL),A : INC Н
LD (HL),#F0:DEC Н:INC L
GNLG1 LD (HL),D:INC Н
LD (HL),A:DEC Н
ЕХА:PUSH HL,DE
LD DE,#7440 ;=#00.7480
LD C,L:SRL C:RR D ;х+0.4606
LD HL,#В8AA ;1/ln 2=#01.7154
EXX ;=1.442695
XOR A
LD Н,A,L,A
LD В,#10
GNLG2 EXX
ADD HL,HL:ADC A,A ;AHL00/CDE
SBC HL,DE:SBC A,C
JR NC,GNLGЗ
ADD HL,DE:ADC A,C
GNLGЗ EXX
CCF:RL L,Н
DJNZ GNLG2
РОР DE:ЕХА
ADD HL,DE:ADC A,В ;получаем
; F(х+1)
ЕХ DE,HL
РОР HL
INC L
JR NZ,GNLG1
RET
****************************************
Алгоритм 5: Пенерация синуса/косинуса
Этот алгоритм основан на визуальной
схожести функции Y=X*X и второй части
нижнего полупериода синуса. Хочу отме-
тить, что этот алгоритм формирует лишь
визуально похожую кривую, и спутать их
можно разве что на маленьких периодах,
и когда рядом нет настоящего синуса.
Однако он вроде бы работает. По крайней
мере, в 3DROTATE применена эта процеду-
ра. Она формирует знаковую таблицу ко-
синуса со значениями от -128 до 127.
Если RRA:SRL C заменить на RRA:RR C, то
можно получить 16 битный результат,
правда, нужно будет сделать отдельный
счетчик циклов.
GENCOS LD HL,COSTB+#80
LD DE,COSTB+#FF
GNCS1 BIT 6,L
RET NZ
XOR A
LD C,L:SLI C ;обязательно SLI
LD В,C:SET 7,C
GNCS2 JR NC,$+3
ADD A,В
RRA:SRL C ;в A-старший байт
JR NZ,GNCS2
SUB #80 ;знаковая таблица
SET 7,L:LD (HL),A
RES 7,Е:LD (DE),A
CPL
SET 7,Е:LD (DE),A
RES 7,L:LD (HL),A
DEC Е
INC L
JR GNCS1
****************************************
Алгоритм 6: Линия Брезенхема/Xopha
Здесь не будет действующих примеров, за
исключением нескольких строк. Итак наша
задача - нарисовать линию, причем быст-
ро. Так как мы не можем провести идеаль-
ную линию на растре, то должны аппрокси-
мировать её последовательностью пиксе-
лей. Существует куча методов, причем са-
мых извратных, но нас интересует простой
целочисленный алгоритм. Таким алгоритма-
ми являются алгоритм Брезенхема или его
модификация - алгоритм Xopha. Кстати го-
воря, люди чаще говоря о первом, подра-
зумевают второй, потому как алгоритмы
практически идентичны.
Я классику, конечно, не читал, к сожа-
лению (или к счастью - говорят, что там
бред собаки бешеной вилами по воде пи-
сан). Но тем не менее, принцип рисования
линии состоит в том, чтобы с каждой ите-
рацией двигаться на одну точку по той
оси, проекция на которую больше (т.е. по
основной оси). По другой оси перемещение
происходит в том случае, если идеальная
линия отклонилась от текущей точки на
этой оси больше чем на полпикселя. Это
отклонение можно определить по величине,
называемой ошибкой накопления.
х1,y1 Основная ось
┌---------------->X
│ ..ОООО.........-┐
│ ......ООООО.... dy
│ ...........ОООО-┘
v ...............
Y └---dx------┘ х2,y2
Приведу проги на басике, которые де-
монстрируют оба алгоритма. (переменная Е
- это текущая ошибка накопления)
Классический алгоритм Брезенхема (нуле-
вой октант - dx>dy и Y растет)
10 LET DX=255:LET DY=175:LET Y=0
20 LET Е=DY*2-DX
30 FOR X=0 ТО DX
40 PLOT X,Y
50 IF Е>=0 THEN Е=Е+(DY*2-DX*2)
:LET Y=Y+1:GOTO 70
60 LET Е=Е+DY*2
70 NEXT X
Классический Брезенхем нам совершенно
не подходит потому, что DX*2 или DY*2
превышает размер аккумулятора, и мы
должны будем использовать регистровые
пары.
Классический алгоритм Xopha (нулевой ок-
тант)
10 LET DX=255:LET DY=175:LET Y=0
20 LET Е=DX/2
30 FOR X=0 ТО DX
40 PLOT X,Y
60 LET Е=Е-DY
50 IF Е<0 ТНЕN Е=Е+DX:LЕТ Y=Y+1
70 NЕXТ X
A вот это уже другое дело, особенно,
если учесть, что оба алгоритма дают аб-
солютно одинаковый результат.
Прекрасно, алгоритм выбран. Хорошо бы
его и реализовать на уровне.
Рисовать будем непосредственно по экра-
ну. Иногда пытаются рисовать в буфер, в
котором нет чередования строк, и для пе-
рехода на следующую строку надо доба-
вить, скажем, 32, а потом этот буфер вы-
брасывать на экран (естественно это де-
лают, если время выброса мало, по срав-
нению со временем рисования). Но поверь-
те мне, спековский экран это самое луч-
шее, что только может быть, для реализа-
ции быстрой графики и анимации! Ведь для
перехода на следующую строку достаточно
сделать INC Н, что в 3 раза быстрее, чем
ADD HL,DE!
Линия может лежать в 8 октантах.
Y
│ /
45│6/7
----┼---- X
3/2│1
/ │
Обратите внимание, что на асме, октант
0 внизу, потому что Y растет вниз, а на
басике и в других местах, всё наоборот,
так как Y растет вверх. Сразу видно, что
октанты 4,5,6,7 избыточны. Начальная и
конечная точки просто меняются местами.
Для октанта 0 (dx>dy) и 1 (dy>dx) ис-
пользуются разные процедуры. Процедура
для октанта 0 как правило быстрей.
Классическая реализация, причем довольно
оптимизированная... (нулевой октант):
HL=адрес на экране
Е=dy
D=dx
C=начальный бит
В=длина (=dx)
A'=0
A=dx/2
L0 ЕХА
L1 OR C ;копим пиксели в байте
ЕХА ;пока он не переполнится
SUB Е
JR C,L3
RRC C ;Следующий пиксель
JR C,L2
DJNZ L0
RET
L2 ЕХА ;байт исчерпан,отписываем
LD (HL),A:INC L
XOR A
DJNZ L1
RET
L3 ADD A,D
ЕХА
LD (HL),A:INC Н
LD A,Н ;переходим по Y на 1
AND 7 ;переход в другое
JR Z,L4 ;знакоместо ?
XOR A
DJNZ L1
RET
L4 LD A,L:ADD A,#20:LD L,A
JR C,$+6
LD A,Н:SUB 8:LD Н,A
XOR A
DJNZ L1
RET
Учитывая то, что процедура оптимизирова-
на на линии, близкие к горизонтальной
оси, минимум, на который мы можем рас-
считывать - 48 тактов. Причем это без
отписывания байта в память! В среднем у
подобной процедуры уходит порядка 80
тактов на пиксель.
Что тут можно ускорить? Да практически
всё! Основной тормоз в том, что програм-
ма на каждой итерации цикла проверяет,
не произошел ли выход в другое знакомес-
то как по горизонтали, так и по вертика-
ли, не говоря уже о том, не достиг ли В
нуля. Вероятность первых двух событий
12.5%, значит, что 87.5% операций пот-
рачены впустую! A последнее событие,
вообще, может возникнуть только один
раз! Зачем делать все эти проверки, ес-
ли мы пишем пиксель в конкретное место,
и знаем сколько еще пикселей можно спо-
койно обрабатывать, скажем, пока не про-
изойдет выход в соседнее знакоместо.
Осознав эти обстоятельства, Я создал
очень быстрый код, хотя можно сделать
ещё быстрее.
Я рисую внутри знакоместа, и это зна-
чит,что переход на следующую строку -
INC Н, переход на соседний пиксель -
просто другой номер бита в команде
SET х,(HL). Из проверок остается выпол-
нить только счетчик длины. Длину Я счи-
таю также в целых знакоместах, а когда
она обнулится, дорисовываю остаток. A
так как последняя точка линии может на-
ходиться в середине знакоместа, я
вставляю в код ловушку - RET после SET
в месте конечной точки линии.
В памяти создаются 4 процедуры для
всех четырех октантов. Они представляют
собой матрицы 8*8 и содержат команды ус-
тановки каждого из 64 пикселей знакомес-
та.
Для октантов 0 и 3 (dx>dy) процедура
выглядит так:
L00 SET 7,(HL) ;строка 0
SUB Е
JR C,L11A
L01 SET 6,(HL)
SUB Е
JR C,L12A
L02 ...
L10A ADD A,D
INC Н ;переход на строку 1
JP L10
L11A ADD A,D
INC Н
JP L11
L12A ...
L10 SET 7,(HL) ;строка 1
SUB Е
JR C,L21A
L11 SET 6,(HL)
SUB Е
JR C,L22A
L12 ...
При достижении нижней строки знакоместа
происходит выход в нижнее знакоместо,
после чего процедура переходит на строку
0, на следующий по горизонтали пиксель.
При этом декрементируется счетчик цик-
лов, и если он обнулился, вызывается
подпрограмма установки ловушки.
Для октантов 1 и 2 программа выглядит
так:
LLOO SET 7,(HL)
SUB Е
JR C,LL11A
INC Н
LL10 SET 7,(HL)
SUB Е
JR C,LL21A
INC Н
LL20 ...
LLO1A ADD A,D ;переход на следующий
JP LLO1 ;столбец
LL11A ADD A,D
JP LL11
LL21A ...
LLO1 SET 6,(HL)
SUB Е
JR C,LL12A
INC Н
LL11 SET 6,(HL)
SUB Е
JR C,LL22A
INC Н
LL21 ...
Всё это занимает 3 кб, что не так уж
много. Единственное что от Вас требуется
- это правильно войти в матрицу, и после
обнуления счетчика, правильно поставить
ловушку. Всё остальное программа выпол-
нит сама. Программа всегда попадает в
ловушку, хотя поначалу, меня на этот
счет терзали сомнения.
Дальнейшая оптимизация.
1. Программу можно сделать более линей-
ной и быстрой, если поменять JR C,...
на JP C,... это уменьшит время выполне-
ния на перемещениях вдоль неосновной
оси.
2. Можно не ставить ловушку, а дорисовы-
вать остаток более медленной процедурой.
SET 7,(HL)
DJNZ М1
RET
М1 SUB Е:JR NC,М2
ADD A,D
INC Н
М2 SET 6,(HL)
DJNZ М3
RET
М3 SUB Е:JR NC,М4
ADD A,D
INC Н
М4 ...
3. Можно не пересчитывать адрес при пе-
реходе в нижнее знакоместо, а брать его
из таблицы.
4. Можно оптимизировать программу на ри-
сование линий, более близких к 45 граду-
сам, нежели к горизонтальной или верти-
кальной оси.
Всё это конечно хорошо, однако ещё бо-
лее раздует программу, хотя и увеличит
производительность. Наверное, так Я и
сделаю вскоре, когда буду переписывать
сование линий, более близких к 45 граду-
сам, нежели к горизонтальной или верти-
кальной оси.
Всё это конечно хорошо, однако ещё бо-
лее раздует программу, хотя и увеличит
производительность. Наверное, так Я и
сделаю вскоре, когда буду переписывать
decruncher (он ужасен, так как мне нужно
было просто проверить идею, и Я не соби-
рался это куда-нибудь вставлять).
Больше приводить примеров этого, ес-
тественно, не буду, потому, что все это
Вы найдете в 3DROTATE (попробуйте по-
трэйсить). Насколько Я помню, настройка
входных параметров отнимает тактов,
эдак, 250, а установка ловушки около 100
(смотрел по бордюру).
Вот и всё.
До встречи в следующей статье !
----------------------------------
Other articles:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Similar articles:
В этот день... 21 November