And now, for those interested,
**************************************
--------- Algorithms ----------
**************************************
Several algorithms are collected here, which
which everyone should know. In the next
The article will contain other algorithms.
The implementations shown do not claim to be
laurels of the fastest, because fast
the procedure can only be done partially
in certain cases, starting from a specific
tasks.
So, today we have 6 algorithms:
1. Multiplication
2. Compositional multiplication
3. Division
4. Compositional division
5. Approximate calculation of COS/SIN
6. Bresenham/Xopha line
Honorable duty to explain the principles
Dark took over the work of the algorithms i.e.
I.
Several working examples are in the file.
le ALGORITM. They were just thrown there
without expandedcomments.
Understand the following points:
1. It is useful to read a textbook on mathematics
ke, for example derivatives there, integration
all kinds of knowledge - knowing them you can
practically build a table on ASMA
any functions. At least you know
you will find a lot of interesting things if you look
look at formulas from a practical point of view
vision, and not within the framework of general education
body of the program.
2. Algorithms for compositional multiplication and
divisions were ripped from toys - not
we came up with them. And as for the thermal
to "compositional", then I came up with it
myself, because I didn’t know what it was called
is happening. From my point of view, he is sufficient
accurately reflects the essence of what is happening -
th, namely: the operands participate in the
obtaining the components of the expression, the result
which is what we need
number.
By the word "composition" I mean -
I create mainly the composition of the composition
nentov, i.e. expression (sometimes not
you'll blurt that out.)
3. The number of cycles is indicated in the calculation
to the Pentagon. It is considered differently
for the Pentagon and for wait machines
(a la Scorpio). In the latter case
number of clock cycles of each command
rounded to even.
min : minimum number of clock cycles
max: maximum number of ticks
4. Do not expect absolute reliability from me
news - I could be wrong :), (especially
in mathematics)
5. Finally, God forbid, I might screw up-
in codes.
6. Storm syntax is missing here and there
T.A., because it is convenient:
for example,
LD ВС,HL instead of LD C,L:LD В,Н
RL A,B,C,D instead of RL A:RL B:RL C:RL D
.13 PUSH HL replicates the line 13 times,
LD B,A,C,A loads B and C from the battery
lator.
EXA means EX AF,AF'.
NUM[ is the high byte of the number NUM.
Constructions of the form are also used:
REPT N
...
ENDR
In assemblers, this is the repetition of lines,
those between these brackets, N times.
The term "segment" means a section of pa-
memory, the addresses of each cell of which
have the same high byte, for example
measures, from #8000 to #8OFF.
************************************************
1. Multiplication.
In the absence of hardware multiplication,
You can emulate hardware in software. By-
Let's see how it all works in hardware.
There are several ways to multiply
niya, they differ only in bit depth
registers and shift directions. One-
We are only interested in two because of convenience
va implementation of them on the Spectrum.
Method 1.
Multiplication starting from the least significant digits
multiplier and with a shift of the sum of partial
products to the right for a fixed set
bench press
-----> ----->
CF<->[ SUMMATOR ]-->[RG multiplier]-┐
^ │
│<-----------------------┘
│
[RG multiplicand]
Before starting the operation, the adder, in which
rum is stored partial work,cleared.
The multiplier shifts to the right, and if you-
if one climbed, then the multiplicand is added
with partial product. Then partly
the new product moves to the right (behind
grabbing the carry flag with you) and
enters the most significant bit of the multiplier register
la. And so on until everyone is processed
multiplier digits.
After the operation is completed, the adder
holds the senior part of the work, and re-
multiplier hyster - minor.
This multiplication method is convenient because
uses registers of the same length, and
multiplication 8*8->16 can be implemented
but on three 8-bit registers.
; AC=C*V
MULU112 XOR A
REPT 8
RR C
JR NC,$+3
ADD A,B
RRA
ENDR
RR C
min:(8+7+4+4)*8+12=196
max:(8+12+4)*8+12=204
MULU112 means unsigned multiplication
byte per byte per word...
How about multiplying 16*16->32?
;HLDE=DE*ВС
MULU224 LD HL,0
REPT 16
RR D,E
JR NC,$+3
ADD HL,VS
RR H,L
ENDR
RR D,E
min:(16+12+16)*16+26=730
max:(16+7+11+16)*16+26=826
Method 2.
Multiplication, starting with the most significant digits
multiplier when shifting the sum of partial
products to the left and a fixed multiplicity
mom.
<-----
[SUMMATOR]
^ <-----
│<--[RG multiplier]
│
[RG multiplicand]
The operating principle is almost the same
the previous one, so explain it further
times it doesn't make sense.
The algorithm requires a double-length adder,
this implies that the register
the multiplicand also has double length, but
its higher half is reset to zero (so that
the transfer worked correctly).
The multiplier is put in the higher half
adder, since the most significant bit of the sum
partial products will not be able to use it
say, because at the first iteration
the multiplier is shifted to the left by one bit,
which saves from overflow even with
maximum possible operands.
;HL=H*E
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. These multiplication algorithms work
only with unsigned numbers. Therefore
if you need signed multiplication then
negative numbers must be pre-
but npoNEG, and after receiving the re-
the result is npoNEG and him, if he
must be negative.
2. Higher bit depth can be obtained by
adding the results of two multiplications less
neck digits.
For example, 16*8->24 can be obtained like this:
f=аь*c , where a is the most significant byte
b-low byte
dd = a*c
ee = b*c
dddddddd dddddddd 00000000
+ 00000000 eeeeeeee eeeeeeee
----------------------------
ffffffff ffffffff ffffffff
3. Multiplication can be somewhat accelerated by
if the ranges of values are known.
Indeed, if we know that
example, the most significant 3 bits of the multiplier - well -
whether, whycheck this every time?
Just move the multiplier to the left
(for the second method) to these same 3
bit and do only 5 iterations of multiplying
nia. Obviously, the result is also necessary
shift 3 bits to the left.
************************************************
2. Compositional multiplication
Multiplication C=A*B is carried out taking into account
signs of both operands. I know 2
formulas. They are absolutely equivalent and not
depend on the bit depth of the operands.
Method 1. Exact multiplication
Multiplication is done by calculating
expressions: C=((A+B)₂-A₂-B₂)/2, which
formed from the formulas of the abbreviated clever-
marriages, namely:
Square of the sum (A+B)₂=A₂+2AB+B₂, poe-
In order to get2AByou need from (A+B)₂
subtract A₂ and B₂.
Based on this algorithm, it is possible to construct
For example, multiplication 8*8->16
First we need to create a table
tsu X₂, which has a size of 256*16 bits
and is calculated taking into account the sign of the number
X, lying in the range from -128 to 127
Value at point #80 X₂=#4000.
The table is organized as follows: junior buys
you lie in the first segment, and the elders in
next (i.e. at offset 256).
You can quickly create such a table
but like this:
;GEN TABLE Y.W=X*X X=(-128;127)
GENXX LD IX,TBXX
LD DE,TBXX
LD H,E,L,E:LD BC,HL
LOOP CALL SUB
LD (IX),L:INC НХ
LD (IX),Н:DEC НХ
ADD HL,SUN:INC C
ADD HL,VS
DEC LX
INC EJP P,LOOP
SUB LD A,L:LD (DE),A:INC D
LD A,Н:LD (DE),A:DEC D
RET
The multiplication procedure looks like this:
; HL= L*E ( C=A*B )
MULS112 LD N,TBXX[
LD C,(HL):INC N ;A₂
LD B,(HL)
LD A,L:ADD A,E
JP PE,MULS1 ;overflow
LD L,E
LD D,(HL):DEC N ;B₂
LD E,(HL)
LD L,A
LD A,(HL):INC N ;(A+B)₂
LD H,(HL)
LD L,A
SBC HL,VS
SBC HL,DE
SRL H:RR L
RET
MULS1 LD A,L:SUB E
LD L,E
LD D,(HL):DEC N
LD E,(HL)
LD L,ALD A,(HL):INC N
LD H,(HL)
LD L,A
EX DE,HL
ADD HL,VS
SBC HL,DE
SRL Н:RR L
RET
min:137 (excluding RET)
max:145 (excluding RET)
At the MULS1 label the program goes to
in case of overflow of the addition result
signed numbers, and to avoid mistakes
end result, calculations of the
dit according to a slightly modified formula:
C=(В₂-(A-В)₂+A₂)/2
As you can see, this procedure is very
fast, especially considering that you learn
The signs of both operands are revealed.
Method 2. Fast multiplication.
Multiplication is done by calculating
expressions: C=(B+(A/2-B/2))₂-(A/2-B/2)₂
This formula is also expressed from the formula
squareamounts, but it's done more
interesting.
Multiplication 8*8->8 (high byte from 16)
; A=A*B
MULS111 SRA A
LD L,B
SRA L
SUB L ;(A/2-B/2)
LD L,A
ADD A,B ;B+(A/2-B/2)
LD H,TBXX2[
LD C,(HL)
LD L,A
LD A,(HL)
SUB C
min=max:61
If you throw out the command LD Н,TBXX2[, then
execution time will be 54
tact! Taking into account the signs!
An 8-bit quad table is used here.
ratov. It contains only the high byte,
and the values are multiplied by 2, i.e. in
point #80 table contains
-128*(-128)/256*2=128
GENXX2 LD IX,TBXX2LD DE,TBXX2
LD H,E,L,E:LD BC,HL
LOOP CALL SUB
LD(IX),A
ADD HL,SUN:INC C
ADD HL,VS
DEC LX
INC E
JP P,LOOP
SUB LD A,L:RLA:LD A,H:RLA:LD (DE),A
RET
However, there is also a bad side to this speed.
side: the resulting value is NOT EXACT.
This is especially noticeable at low values,
although at large values the accuracy is
landma. Low accuracy is to blame
first of all 8 bit quad table
Comrade, although division by 2 is already in itself
means a decrease in precision by 1 bit.
In the 3DROTATE example, rotation is implemented
precisely on the basis of this procedure. Difficult
not to notice the beating of the object’s vertices, especially
especially when rotation occurs in three
axes, and the errors overlap
on a friend. So choose what you want
more important: speed or accuracy...
************************************************
Algorithm 3: Division
Method 1
In the pre-zeroed adder (in which
rum is stored partial balance) on the right
the dividend is pushed. From partial
the divisor is subtracted. If it wasn't
overflow, then into the dividend register
a unit is pushed from the right, otherwise
the reduction of the partial remainder of the restoration
is expressed and pushed into the dividend register
zero.
____________
transfer
┌-------------------->---------------┐
│ ┌-┐ <----- <----- │
├-о1├-[ SUMMATOR ]<-[RG dividend ]-┘
│ └-┘ ^
└------>│
┃
[RG divider]
After the operation in the adder is completed
there remains a remainder thatcan be used
call to receive fractional (fractio-
nal, fract) parts of the quotient, if divided
pour it again onto the divider. Private
remains in the dividend register.
All registers have the same length.
Therefore, this algorithm allows you to
complete division N/N->N, and also
(2N-1)/N->N. In the latter case it is not necessary
reset the adder and load it into it
high N-1 bits of the dividend. I indicated the poppy
the maximum length of the operands as 2N-1 poto-
we know that the first division operation is
there is a shift to the left and the last bit is gone
into the carry flag, where it is lost. Yes
what can't be obtained from #FFO1/#FF
#FF, at least with those procedures
which will come next.
Naturally, the result will be CORRECT
only when the initial value is in
adder LESS divisor:
#7E81/#7F=#FF > #7E<#7F everything is normal
#7F00/#7F=#100 #7F=#7F overflow
;simple division 8/8->8
; D=D/E, A-residue
DIVU111 LD V,8
XOR A ;zeroing the "adder"
DIVU1 RL D
R.L.A.
; (*) point of possible overflow (see.
below)
SUB E
JR NC,$+3
ADD A,E
CCF
DJNZ DIVU1
RL D
If you do 16/8 division with -
power of this program (i.e. D=AD/E), then
if in the place of the comment (*) there is a pe-
renos, the result will be incorrect.
When expanding the loop we get:
DIVU111 XOR A
REPT 8
RL D
R.L.A.
SUB E
JR NC,$+3
ADD A,E
ENDR
LD C,A ;remainder
LD A,D
R.L.A.
CPL instead of CCF
;A=quotient
min:(16+7+4)*8+12=236
max:(16+12)*8+20=244
Here is an example of division 16(32)/16->16:
;DE=DE/BC, HL=remainder
DIVU222 LD HL,0
REPT 16
RL E,D
ADC HL,HL
SBC HL,VS
JR NC,$+3
ADD HL,VS
ENDR
LD A,E
R.L.A.
CPL
LD E,A
LD A,D
R.L.A.
CPL
LD D,A
min:(16+15+11+12)*16+10=938
max:(16+15+15+7+11)*16+10=1034
A thing of measures, however...Method 2
In this method, the partial remainder (initially
le it is equal to the dividend and is in re-
hyster of the dividend) is motionless, but moves
just a divisor.
<-----
[RG quotient]<┐ [RG dividend]
│ ^
└-----<│
│ ------>
[RG divider]
The division is subtracted from the partial remainder
tel, and if there was no overflow, then in
The quotient register is pushed to 0, otherwise
the partial balance is restored and in
the quotient register is pushed to 1.
The registers must be the same length,
equal to the length of the processed word.
Based on the method they write optimized
new division. The essence of optimization is
what happens is the execution of less (on
large numbers) number of iterations.
Let me illustrate this with an example:
(it is not tested and notоптимизирован)
;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) влево до тех пор, пока стар-
ший бит регистра не будет содержать
единицу. При этом, в процессе сдвига,
the iterator counter is incremented
tions (B). Then all that remains is to execute
In iterations and in BC we have the quotient, in HL
remainder.
Notes.
1. These division algorithms work
only with unsigned numbers. Therefore
if you need signed division then
look what is written about it in
"multiplication".
2. Higher bit depth can be obtained by
just by rewriting the program. At least
at least I don't know how to do this
simpler.
************************************************
Algorithm 4: Compositional division.
Division C=A/B, as opposed to multiplication,
is performed without taking into account the signs of the operands.
The calculation is made according toformula:
(log A - log B)
C= 2 ₂ ₂
The logarithm function is the inverse of raising to
degree:
X=a^Y => Y=Log X
a
We will only use the logarithm with
base 2, hereafter denoted simply
like Log X.
The formula is based on one of the properties
logarithm:
Log A/B= Log A-Log B
By the way, if you use
other properties of logarithms, then like
you could easily extract the roots of any
degree, what am I going to do next?
next article.
Let's start by creating tables. Here they are
you will need two. If you don't want to count
If you need tables, you can take ready-made ones. They
are on disk (DIVTABS file). First
two segments are a logarithm table,
the third (aka the last) - table 2^X.
The first (16-bit) is the function
Y=Log X.It can be calculated simply and accurately in BASIC:
FOR X=1 TO 255
LET Y=LN X/LN 2
ROKE A+X,Y-256*INT (Y/256)
ROKE A+256+X,Y/256
NEXT X
Please note that the logarithm function is erroneous
for zero value. In the table in this
#F000 should be located (for right
correct processing of incorrect results
tata).
The second is an 8-bit function table
Y=(2^X)-1 i.e. inverse logarithmic function
mu to convert the result to normal
small number. Moreover, 0<=X<1, therefore
1<=Y<2. As you can see, only the fraction changes
part, and the whole is always equal to one.
The table is also calculated simply:
FOR X=0 TO 255
LET Y=2^(X/256)-1
ROKE A+X,Y*256+0.5
NEXT X
The procedure looks somewhat heavy-handed
but, butshe's quite fast.
Divide byte by byte and get number c
fixed point.
;DIV 8/8=8.8
;HL=Н/L (ALL UNSIGNED)
FDIVB LD A,H
LD Н,TBLOG2[
LD E,(HL):INC N
LD D,(HL):LD L,A ;DE=Log L
LD A,(HL):DEC N
ADD A,8
LD L,(HL):LD Н,A ;HL=(Log Н)^8
SBC HL,DE
JP P,FDVB1
LD HL,0
RET
FDVB1 LD A,H,D,A;save the whole part
LD N,TV2X[
LD L,(HL):LD Н,1 ;HL=2^L
SUB 8:JR NC,FDVB2
LD A,7:SUB D;result <0
LD ($+4),A ;L=(НL^D)>>8
JR NZ,$ ; transition changed
.7 ADD HL,HL ; previous command
LD L,H,H,0
RET
FDVB2 LD A,#0F:SUB D;result >=0
JR C,FDVB3LD ($+4),A ;L=(HL^D)
JR NZ,$
.7 ADD HL,HL
RET
FDVB3 LD HL,-1 ;result >#FF.FF
RET
min:177
max:250
Min number of cycles calculated for
result <0 without performing ADD НL,НL.
A max, for result >=0 with execution
all ADD HL,HL..
3DROTATE uses the same procedure
ra, only it takes into account the sign of one of
operands
By slightly modifying this procedure, you can
perform division of larger digits
by loss of accuracy. But since the process
the fool adapts to the bit capacity of the opera-
dov, then loss of accuracy on small
there won’t be numbers, but on large ones it won’t
too noticeable.
I don’t think it’s appropriate to give the entire procedure.
appropriate, if necessary, you will find it
in the file ALGORITM.
I will give only a small excerpt.
;DIV 12/12=8.8
;HL(SIGN)=HL(SIGN)/DE(UNSIGN)
FDIVW LD BC,0
EX DE,HL
INC Н:DEC Н
JR Z,FDVW2
.3 INC B:SRA H:JR Z,FDVW1:RR L
INC B:SRA N
FDVW1RR L
FDVW2 LD Н,TBLOG2[
LD A,(HL):INC N
LD H,(HL):LD L,A
ADD HL,VS
12-bit data is also presented
as well as 16-bit (meaning month-
sign bit position), but only
numbers cannot exceed the range op-
defined by 12 bits.
Register B is used in the packing loop
register HL in L, and saves the shift number
gov, or in other words, the degree
deuces. After which the degree from the table and
received during packaging are folded, and
restore after the operation is completed
the required bit depth is not difficult.
It will also not be difficult to remake the program
frame for larger numbers.
For bit depth N(not>15) only needed
repeat line N-9 times
INC В:SRA Н:JR Z,FDVW1:RR L.
Let's return to compiling tables.
What if you don't want to suck on a pill?
faces from the disk, but you want to count them
in assembler? For example, out of desire to se-
save 600 bytes on disk...
Naturally, the functions of the calculator we
We won’t use it (although why not
no?). Instead, we will use pro-
derived functions.
I spent a lot of time trying to
the resulting tables corresponded to the original
ginal (those that were ripped from games)
Rushki). However, exact correspondence is up to
It was not possible to fight.
Tables 2^X differ by only a few
any values, and even then by one. And here
tables of logarithms differ more
strongly. The inaccuracy is especially evident
at small values, but then it
practically does not show itself. But let
it doesn't scare you too much - error
does not exceed 1/128 and therefore it is not particularly
it greatly affects the result.
Calculation Y=2^(X/256)-1
---------------------------
The following value can be obtained from the
Tabernacle like this: F(x+1)=F(x)*2^(1/256)
LET D=1
FOR X=0 TO 255
ROKE A+X,(D-1)*256
LET D=D*1.0027113
NEXT X
Since to represent a number
1.0027113 you can’t get by with 8.8 format,
Let's use the 8.16 format. Although
only uses 1.16...
;GEN TABLE Y.В=2^(X/256)-1 ,X=(0;1)
GEN2X LD IX,TV2X
LD HL,0 ;Thing part of the current F(x)
GN2X LD A,H ;Rounding
BIT 7,L
JR Z,$+3
INC A
LD(IX),A
XOR A
EXX
LD L,A,H,A,E,A
LD BC,#00B2;(2^1/256)*#10000
EXX
LD BC,#1801 ;Multiply 24*24->48
GN2X1 RR C,H,L
EXX
JR NC,GN2X2ADD HL,SUN ;AHL+=#01.00B2
ADC A,1
GN2X2 RRA:RR Н,L
EXX
DJNZ GN2X1
LD A,C:RRA ;catch the bit
EXX
LD H,L,L,A; Real part F(x+1)
INC LX:JR NZ,GN2X
RET
Calculation Y=Log X
---------------------------
The following value can be obtained from the
Tabernacle like this:
F(x+1)=F(x)+1/((X+0.4606)*LN 2)
LET D=0
FOR X=1 TO 255
ROKE A+X,(D-1)*256
LET D=D*1/((x+4606)*LN 2)
NEXT X
Where did the number 0.4606 come from? It was
POKE METHOD.
The fact is that Log 1=0, and Log 2=1, therefore
Therefore, the increment must be equal to
unit. Fraction 1/(1*LN2)=1.442695, andthe correction factor should in theory
be equal to .442695. However, the curve at
this turns out to be somewhat more than
up to Or did I do something wrong? Who
knows, please send a letter to the editor.
In addition, on ASMA, I changed it a little
this is the number. Yes, don't forget that the function
logarithm is wrong for zero value
nia. In the table in this place there should be
go #F000.
In my procedure I use 24 times -
row numbers, bits 0-14 of which are allocated
under the fractional part, and bit 15 under the least significant
digit of the integer part and other digits
(except for the eldest, which = 0), also under the
luyu. This is done so as not to
no overflow on division (I do
40/24->16). In fact, this process of trust
the fool doesn’t appeal to me too much now,
something is fishy here, so I recommend-
I want to write something like this myself.
;GEN TABLE Y.W=LOG2(X) ,X=(0.255)
GENLOG2 LD HL,TBLOG2
XOR A:LD E,A,D,A
LD (HL),A : INC N
LD (HL),#F0:DEC H:INC L
GNLG1 LD (HL),D:INC Н
LD (HL),A:DEC N
EXA:PUSH HL,DE
LD DE,#7440;=#00.7480
LD C,L:SRL C:RR D ;x+0.4606
LD HL,#V8AA ;1/ln 2=#01.7154
EXX ;=1.442695
XOR A
LD N,A,L,A
LD B,#10
GNLG2 EXX
ADD HL,HL:ADC A,A ;AHL00/CDE
SBC HL,DE:SBC A,C
JR NC,GNLGZ
ADD HL,DE:ADC A,C
GNLGZ EXX
CCF:RL L,H
DJNZ GNLG2
ROR DE:EHA
ADD HL,DE:ADC A,B ;we get
; F(x+1)
EH DE,HL
ROR HL
INC L
JR NZ,GNLG1
RET
*******************************************
Algorithm 5: Sine/Cosine Penetration
This algorithm is based on visual
similarities of the function Y=X*X and the second part
of the lowerhalf-cycle of sine. I want to note
It should be noted that this algorithm only generates
visually similar curve, and confuse them
It’s possible only for short periods,
and when there is no real sinus nearby.
However, it seems to work. At least
At least in 3DROTATE this procedure is applied
ra. It forms a signed table of co-
sine with values from -128 to 127.
If RRA:SRL C is replaced by RRA:RR C, then
you can get a 16-bit result,
however, you will need to make a separate one
cycle counter.
GENCOS LD HL,COSTB+#80
LD DE,COSTB+#FF
GNCS1 BIT 6,L
RET NZ
XOR A
LD C,L:SLI C ;required SLI
LD B,C:SET 7,C
GNCS2 JR NC,$+3
ADD A,B
RRA:SRL C ;in A-high byte
JR NZ,GNCS2
SUB #80 ;sign table
SET 7,L:LD (HL),A
RES 7,E:LD (DE),A
CPL
SET 7,E:LD (DE),A
RES 7,L:LD (HL),A
DEC E
INC LJR GNCS1
************************************************
Algorithm 6: Bresenham/Xopha line
There will be no working examples here, for
except for a few lines. So our
the task is to draw a line, and quickly
ro. Since we cannot conduct an ideal
line on the raster, then you should approximate
pixelate it with a sequence of pixels
lei. There are a lot of methods, and most
we are perverted, but we are interested in simple
integer algorithm. So the algorithm is
we are Bresenham's algorithm or his
modification - Xopha algorithm. By the way...
when speaking, people often talk about the first, sub-
they assume the second one, because algorithms
almost identical.
I, of course, haven’t read the classics, unfortunately
luck (or fortunately - they say that there
the raving of a mad dog with a pitchfork through the water
san). But nevertheless, the principle of drawing
line is that with each ite-
walkie-talkie move one point along that
axis, the projection on which is greater (i.e. along
main axis). Movement on another axis
occurs when ideal
linedeviated from the current point by
this axis is more than half a pixel. This
deviation can be determined by the value
called accumulation error.
x1,y1 Main axis
┌---------------->X
│ ..OOOO.........-┐
│ ......OOOOOO.... dy
│ ..........OOOO-┘
v ...............
Y └---dx------┘ x2,y2
I will give programs on bass, which are
both algorithms are monsters. (variable E
- this is the current accumulation error)
Classic Bresenham algorithm (zero-
howling octant - dx>dy and Y is growing)
10 LET DX=255:LET DY=175:LET Y=0
20 LET E=DY*2-DX
30 FOR X=0 TO DX
40 PLOT X,Y
50 IF E>=0 THEN E=E+(DY*2-DX*2)
:LET Y=Y+1:GOTO 70
60 LET E=E+DY*2
70 NEXT X
Classic Bresenham is perfect for us
not suitable because DX*2 or DY*2
exceeds the battery size and we
we will have to use register
couples.
Classic Xopha algorithm (zero approx.
tant)
10 LET DX=255:LET DY=175:LET Y=0
20 LET E=DX/2
30 FOR X=0 TO DX
40 PLOT X,Y
60 LET E=E-DY
50 IF E<0 TNEN E=E+DX:LET Y=Y+1
70 NEXT X
But this is another matter, especially
if we take into account that both algorithms give ab-
absolutely the same result.
Great, the algorithm has been selected. It would be nice
and implement it at the level.
We will draw directly on the screen
well. Sometimes they try to draw into the buffer, in
which there is no alternation of lines, and for pe-
to move to the next line you need to add
set, say, 32, and then select this buffer
throw on the screen (naturally this is de-
bark if the release time is short, compared
over time of drawing). But believe me-
to me, the Specov screen is the best
neck, whatever it can be, forimplemented
tions of fast graphics and animation! After all, for
moving to the next line is enough
do INC H, which is 3 times faster than
ADD HL,DE!
The line can lie in 8 octants.
Y
│ /
45│6/7
----┼---- X
3/2│1
/ │
Please note that on asma, octant
0 is below because Y is growing downwards, and at
Basik and other places, it’s the other way around,
as Y grows upward. It is immediately obvious that
octants 4,5,6,7 are redundant. Initial and
the endpoints are simply swapped.
For octant 0 (dx>dy) and 1 (dy>dx) use
different procedures are used. Procedure
for octant 0 is usually faster.
Classic implementation, and quite
optimized... (zero octant):
HL=address on screen
E=dy
D=dx
C=start bit
B=length(=dx)
A'=0
A=dx/2
L0 EXA
L1 OR C ; save pixels in a byte
EXA ;until it overflows
SUB E
JR C,L3
RRC C ;Next pixel
JR C,L2
DJNZ L0
RET
L2 EXA;byte exhausted, unsubscribe
LD (HL),A:INC L
XOR A
DJNZ L1
RET
L3 ADD A,D
EXA
LD (HL),A:INC N
LD A,H ;move along Y to 1
AND 7 ;go to another
JR Z,L4;is this a familiar place?
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
Considering that the procedure is optimized
on on lines close to horizontal
axis, the minimum to which we can expand
read - 48 clock cycles. And this without
writing a byte into memory! On average
This procedure takes about 80
clock cycles per pixel.
What can be speeded up here? Yes practically
that's it! The main obstacle is that the program
Ma checks at each iteration of the loop,
did you enter into another acquaintance?
then both horizontally and vertically
whether, not to mention whether B has not reached
zero. Probability of the first two events
12.5% means that 87.5% of transactions are
wasted! A last event,
in general, only one can arise
once! Why do all these checks?
whether we write a pixel to a specific location,
and we know how many more pixels can be used
calmly process, let’s say, until it’s finished
there will be an exit to a nearby familiar place.
Realizing these circumstances, I created
very fast code,although it can be done
even faster.
I draw inside a familiar place, and this means
read that goes to the next line -
INC N, move to adjacent pixel -
just a different bit number in the command
SET x,(HL). The only checks left to do are
thread only length counter. I count the length
I also melt into entire familiar places, and when
it will reset to zero, I’ll finish drawing the rest. A
since the last point of the line can
walking in the middle of a familiar place, I
I insert a trap into the code - RET after SET
at the end point of the line.
4 procedures are created in memory for
all four octants. They represent
are 8*8 matrices and contain commands for
The settings of each of the 64 pixels are familiar
ta.
For octants 0 and 3 (dx>dy) procedure
looks like this:
L00 SET 7,(HL) ;line 0
SUB E
JR C,L11A
L01 SET 6,(HL)
SUB E
JR C,L12A
L02...
L10A ADD A,D
INC N ;go to line 1JP L10
L11A ADD A,D
INC N
JP L11
L12A...
L10 SET 7,(HL) ;line 1
SUB E
JR C,L21A
L11 SET 6,(HL)
SUB E
JR C,L22A
L12 ...
When reaching the bottom line of the familiarity
there is an exit to the lower familiarity,
after which the procedure goes to the line
0, to the next horizontal pixel.
In this case, the cycle counter is decremented.
catch, and if it is reset to zero, it is called
trap setting routine.
For octants 1 and 2 the program looks like
like this:
LLOO SET 7,(HL)
SUB E
JR C,LL11A
INC N
LL10 SET 7,(HL)
SUB EJR C,LL21A
INC Н
LL20 ...
LLO1A ADD A,D ;
JP LLO1 ;this
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 ...
Since this is 3 years ago, that's it
много. Единственное что от Вас требуется
- This is the first time I've seen this, and it
snowflake snowflake, snowflake snow
Color. Pages Other Brand Website Personal Blog
нит сама. The price of the snowflake в
ловушку, хотя поначалу, мея на тот
счет терзали сомнения.Further optimization.
1. The program can be made more linear
new and fast if you change JR C,...
on JP C,... this will reduce execution time
research on movements along the non-main
axes.
2. You don’t have to put a trap, but before drawing
Discard the remainder using a slower procedure.
SET 7,(HL)
DJNZ M1
RET
M1 SUB E:JR NC,M2
ADD A,D
INC Н
M2 SET 6,(HL)
DJNZ M3
RET
M3 SUB E:JR NC,M4
ADD A,D
INC N
M4...
3. No need to recalculateaddress upon re-
going to the lower familiar place, and take it
from the table.
4. You can optimize the program based on
drawing lines closer to 45 degrees
itself, rather than to horizontal or vertical
cal axis.
All this is of course good, but even more
will further bloat the program, although it will increase
productivity. That's probably how I am
I'll do it soon when I rewrite it
poking lines closer to 45 degrees
itself, rather than to horizontal or vertical
cal axis.
All this is of course good, but even more
will further bloat the program, although it will increase
productivity. That's probably how I am
I'll do it soon when I rewrite it
decruncher (he's terrible because I need
it was just to test the idea, and I didn't
I was trying to insert this somewhere).
Give more examples of this, es-
Naturally, I won’t, because all this
You will find in 3DROTATE (try it here)
trace). As far as I remember, the setting
input parameters takes clock cycles,
something like 250, and installing a trap is about 100
(looked along the curb).
That's all.
Tosee you in the next article!
----------------------------------
Share your thoughts about the article