Spectrum Expert #01
31 октября 1997

Программирование - реализация на ассемблере 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
(смотрел по бордюру).                   
                                        
                                        
             Вот и всё.                 
     До встречи в следующей статье !    
   ----------------------------------   



Другие статьи номера:

Оболочка - описание оболочки журнала.

Вступление - нам удалось сделать журнал абсолютно "с нуля" всего за полтора месяца, начиная с раздумий и заканчивая продажей.

От редакции - мы взваливаем на себя нелегкую ношу производства качественного и интересного спектрумовского журнала.

Enlight 1997 - А верной ли дорогой идем товарищи? Крах Enlight'97.

Интервью - Kano VS RST7: Быль о том, как не смогли понять друг друга элитные представители спектрумовской сцены.

Игры - описание игр: Bogaboo, Towdie, Delta, Score 3020, Konami Tennis, Hyper Sports, Para Academy, Run for gold, Centurions, Atrog, Little computer people.

Программирование - 3D на спектруме: вращение проволочного обьекта (без отсечения вышедших за экран линий).

Программирование - реализация на ассемблере Z80: умножение, композиционное деление, вычисление COS/SIN, рисование линии Брезенхема/Хорна.

Софт - описание нового ассемблера - Storm.

Софт - описание новшеств и доработок музыкального редактора Pro Tracker 3.31

Софт - описание музыкального редактора под "GS" RIFF ТRACKЕR'у v 2.9

Программирование - адаптация игровых программ под музыкальную карту General Sound.

Железо - GMX: видео карточка для ZS Scropion.

Железо - ZX BUS - Шина на спектруме: Кажущаяся простота синклеровского железа чрезвычайно обманчива.

Юмор - доктор Фомин спешит на помощь!

Юмор - юмористически обзор компьютерных игр.

Реклама - Наша фирма предлагает программное обеспечение для ZX-SРЕCТRUМ.


Темы: Игры, Программное обеспечение, Пресса, Аппаратное обеспечение, Сеть, Демосцена, Люди, Программирование

Похожие статьи:
Премьера - Flash Tracker Song Compiler: Кoмпилятoр для пeрeвoда рабoчeгo мoдуля в удoбoваримый вид, кoтoрый ужe мoжeт примeняться в прoграммах всякoгo рoда.
Coding - Комментарии к исходникам, опубликованным в Scenergy #1
real life - почему не дают бабы?

В этот день...   29 марта