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

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

<b>Программирование</b> - реализация на ассемблере Z80: умножение, композиционное деление, вычисление COS/SIN, рисование линии Брезенхема/Хорна.
                                        
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
(смотрел по бордюру).                   
                                        
                                        
             Вот и всё.                 
     До встречи в следующей статье !    
   ----------------------------------   



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

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

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

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

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М.


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

Похожие статьи:
Infotek - Реклама и объявления.
Профессиональный подход - Алгоритмы построения и прохождения Лабиринтов.
Пользователям - Как распечатывать статьи из журналов на Скорпионе.
PartyZone - Chaos Constructions'o1 ZX results.
Информация - о телефонии г.Москвы после нового года.

В этот день...   2 декабря