Fun with Bootsectors
(or so we are
told)
The boot sector is most probably the most critical sector on disk. Even
by "disk" we mean floppy disk, hard disk, etc. it's there, containing critical
information and description on the medium the BIOS is trying to access. It
contains the number of tracks, its sizes, the medium's number of sides, sector
sizes, and then some more info.
Also, about 480 bytes of it are devoted to any extra codemight be
needed. For example, hard disks use the boot sector to load the driver into
memory, and games that don't have files use it to load the main program in
memory.
So, as you can gather (or already know, don't want to insult you :), the
bootsector is not a thing to be messed with. On contrary, it is to be taken very
seriously.
How is it then, that lots of programmers (especially game/demo
programmers) have used these 480 bytes for anything else? We've seen viruses,
antiviruses, fractals, fullscreens, games, protections, the list is endless.
While I don't claim to know the answer to this question, nevertheless I
have coded in the past a couple of bootsectors, others for competitions, others
for inclusion. The one I'm about to describe here was made for D-BUGto be
included in their game CDs. The main thing that it does is to draw a cirlce. So,
without further ado, let's have some theory!
How to draw a circle (sort of)
------------------------------
As everyone with a little more than the basic knowledge in maths will
already know, the parametric equations for drawing a circle at the centre of the
axes are:
x=cos(t)*r
y=sin(t)*r
where 0<=t<=360(or 2*pi in radians) and r is the radiusof the circle we wish
to draw. Take a look on the following figure though.
y
^
|
OOOOOO|OOOOOOO
OOOOO | OOOOO
(-y,x) POO | OOP (y,x)
OOO | OOO
O | O
OO | OO
O | O
P (-x,y) | xxxxxP (x,y)
O | xxxxxx O
O | xxxxx O
O |xxxxxx O
------------------------+---------------------------> x
O | O
O | O
O | O
P (-x,-y) | P (x,-y)
O | O
OO | OO
O | O
OOO | OOO
(-y,-x) POO | OOP (y,-x)
OOOOO | OOOOO
OOOOOO|OOOOOOO
|
As you can see, we can optimize these equations by simply observing that
we have an 8-way symmetry on the circle. So, by using these equations to
calculate point P(x,y)we immediately know the coordinates of its symmetric
points, i.e. (y,x),(x,-y),(y,-x),(-x,y),(-y,x),(-x,-y)and (-y,-x). The variable
t using this algorithm has to travel only from 0 to 45(or pi/2).
Another small osbervation is that of clipping: if we draw the circle on
the center of the screen, and we find that point (x,y) is outside the viewport,
we immediately exclude points (-x,y),(x,-y),(-x,-y) as well. The same goes for
the four other points: i.e. if (y,x)is out of the viewport, so are (-y,x),(y,-
x),(-y,-x).
Now, mathematically that will suffice, but applying these equations on
digital means (i.e. our screen), problemsarise.
The main problem of course being accuracy: where exactly is pixel
(45.3245,32.5482)for example? And where is pixel (45.7823,32.12345)? Even when
we apply rounding techniques to these two pairs of coordinates, chances are that
we will encounter graphical glitches.
Another smaller, but annoying problem is that, depending on the radius
of the circle and given a fixed accuracy on our sin/cos table, we most probably
will draw the same pixel twice or more, thus wasting processor time and possibly
adding more graphical glitches to our circle.
So if we can eliminate the accuracy problems caused by fractions, and
have a dynamically changing accuracy proportional to the radius, we will have a
sweet deal indeed. Brensenham, well known for his line routine, did exactly
that: a routine that doesn't depend on trigonometric functions, calculates
fractions using integers, and calculates only the pixels needed to be drawn.
Now, this algorithm is an approximation, but a ver good one (there is a
very small error). Its only limitationis that it's kind of progressive, i.e. to
calculate a given point you have to start from the first point being calculated
(usually residing on one of the axes) and calculate all in-between points. Thus,
it's only usable if you want to draw a whole circle, or you want to precalculate
the points.
I won't pretend that I understand the full algorithm and the mathematics
involved in it, so I will present the algorithm in a GFA BASICfriendly manner,
and will then proceed to commenting on the assembly implementation. If you need
an explanation of how and why this algorithm works, a book on computer graphics
or the web is your best bet.
cx=159 !the screen's center x coordinate (ST low resolution)
cy=199 !the screen's center y coordinate (ST low resolution)
r=50 !our radius
x=0 !our first point's x
y=r !our first point's y
e=3-2*r !a variable that decides whether to decrease y with every iteration
while (x<=y)
plot cx+x,cy+y !plot the 8 points
plot cx+y,cy+x
plot cx+x,cy-y
plot cx+y,cy-x
plot cx-x,cy+y
plot cx-y,cy+x
plot cx-x,cy-y
plot cx-y,cy-x
inc x !next x
if e>=0
dec y !decrease y only if estimator is positive
endif
e=e+4*x+2 !calculate next step of the estimator
wend
It wasn't too big, was it? And now the code in a bootsector-friendly version.
Firsly, some code to assist us while debugging stuff.
debug EQU 1 ;0=bootsector, 1=test
IFNE debug
clr.w -(SP)
move.l #-1,-(SP)
move.l (SP),-(SP)
move.w #5,-(SP)
trap #14 ;set lo rez
lea 12(SP),SP
pea start(PC)
move.w #$26,-(SP)
trap #14 ;superexec
ENDC
The whole idea for the effect is to print whatever text we want to print (or any
graphics etc. for that matter) using color 1 (which fills all 4 bitplanes) and
setting all palette colors to white except for the one that has only the last 3
planes set. Then, by clearing the first bitplane with a circle that has an
increasing radius, we make the text appear.
start: moveq #$FF,D1 ;white
moveq #7,D2
lea $FFFF8240.w,A1 ;color registers
whitepal: move.l D1,(A1)+ ;make 'em white
dbra D2,whitepal
clr.w $FFFF8240+28.w
move.w #1000/(endmsg-msg-3)-1-1,D7 ;no. of times to print msg
pea msg(PC)
move.w #9,-(SP)
print: trap #1
dbra D7,print ;keep printing till the end of screen
lea msg+1(PC),A0 ;make 'v'->'w' - discard word wrap
addq.b #1,(A0)
trap #1 ;print message for the last time
addq.l #6,SP
move.w #2,-(SP)
trap #14 ;get screen address
addq.l #2,SP
movea.l D0,A0 ;save address
move.w #0,D7 ;d7=radius
lea 100*160+80(A0),A2 ;(160,100)
IFNE debug
clr.w $FFFF8240.w
ENDC
circle: movem.l D0-D2/A0-A2,-(SP)
move.w #37,-(SP)
trap #14 ;vsync
addq.l #2,SP
movem.l (SP)+,D0-D2/A0-A2
IFNE debug
move.w #$0400,$FFFF8240.w
ENDC
move.w D7,D1 ;y=r
moveq #0,D0 ;x=0
move.w D7,D2 ;d2=e=3-2*r
add.w D2,D2
neg.w D2
addq.w #3,D2
*****************************************************************
;
; Plot routine with 8-way symmetry and clipping
; This means that, given a (x,y) pair of coordinates,
; we will draw the following pairs:
; (x,y), (-x,y), (x,-y), (-x,y), (y,x), (-y,x), (y,-x), (-y,-x)
; The clipping is done as following:
; - If (x,y) is off bounds, then so do (-x,y), (x,-y) and (-x,-y)
; The same is applied for the rest 4 pairs
;
; Note! (x,y) is top-left corner relative! We must convert
; to (160,100) relative after clipping!
;
; a0 has the screen address
; d0 has the x, while d0 has y
; It would be adviseable not to destroy these ;)
;
plot:
movea.w D7,A6 ;save d7
xyplot: cmp.w #160,D0 ;x>159?
bge yxplot ;if yes, then we are out of bounds
cmp.w #100,D1 ;y>99?
bge yxplot ;ditto
move.w D0,D3 ;d3=x
lsr.w #1,D3
and.w #~%111,D3 ;d3=(x/16)*8
move.w D1,D4 ;d4=y
mulu #160,D4 ;d4=y*160
move.w D0,D5 ;d5=x
andi.w #15,D5 ;d5=x mod 16
add.w D5,D5
move.w plottable(PC,D5.w),D7 ;get pixel
move.w plottable2(PC,D5.w),D5 ;get inverted pixel
move.w D4,D6 ;y offset...
add.w D3,D6 ;+x offset
and.w D7,0(A2,D6.w) ;plot (x,y)
move.w D3,D6 ;x offset...
sub.w D4,D6 ;-y offset
sub.w #160,D6
and.w D7,0(A2,D6.w) ;plot (x,-y)
move.w D4,D6 ;y offset...
sub.w D3,D6 ;-x offset
subq.w #8,D6
and.w D5,0(A2,D6.w) ;plot (-x,y)
move.w D4,D6 ;y offset...
add.w D3,D6 ;+x offset...
add.w #168,D6
neg.w D6 ;-(y+x offset)
and.w D5,0(A2,D6.w) ;plot (-x,-y)
bra.s yxplot
;
; A couple of notes here on the plot tables:
; Initially it was going to be a neat plot routine with a standard
; plot table (a walking 1 from bits 15 to 0). But then I found out
; that the Bresenham circle algorithm wasn't what I expected, so
; instead of a filled circle all I got was a Moire pattern!
; First thought was to kill the Moire by filling all bits. For this
; I had to create a 'left' and 'right' plot table (see how they are
; constructed below). Alas, that didn't cure the problem 100%, as
; some pixels are still not drawn (the planar system is to blame).
; So, instead of scrapping the idea I sacrifice some of the algorithm's
; accuracy by plotting one extra pixel on the right of the 'right'
; table, and on the left of the 'left' buffer. That's why we have
; $c000 instead of $8000 as an initial value on the 'left' table
; and $0003 instead of $0001 on the 'right' table. Hope I won't burn
; in hell for this (also hope most people won't notice due to the
; 50/60 fps the routines' running at!)
; Final note: commented values of 'i' should be used when we
; want to DRAW a circle (all ANDs should be replaced with ORs in the
; rest of the plot routine, too). Values of i not commented are
; used when we want to ERASE a circle (and such is our case)
;
plottable:
;i SET $C000
i SET $3FFF
REPT 16
DC.W i
;i SET i>>1+$8000
i SET i>>1
ENDR
plottable2:
;i SET 3
i SET $FFFC
REPT 16
DC.W i
;i SET i<<1+1
i SET i<<1
ENDR
yxplot: cmp.w #160,D1 ;y>159?
bge.s noyxplot ;out of bounds
cmp.w #100,D0 ;x>100?
bge.s noyxplot ;out of bounds
move.w D1,D3 ;d3=x
lsr.w #1,D3
and.w #~%111,D3 ;d3=(x/16)*8
move.w D0,D4 ;d4=y
mulu #160,D4 ;d4=y*160
move.w D1,D5 ;d5=x
andi.w #15,D5 ;d5=x mod 16
add.w D5,D5
move.w plottable(PC,D5.w),D7 ;get pixel
move.w plottable2(PC,D5.w),D5 ;get inverted pixel
move.w D4,D6 ;y offset...
add.w D3,D6 ;+x offset
and.w D7,0(A2,D6.w) ;plot (x,y)
move.w D3,D6 ;x offset...
sub.w D4,D6 ;-y offset
sub.w #160,D6
and.w D7,0(A2,D6.w) ;plot (x,-y)
move.w D4,D6 ;y offset...
sub.w D3,D6 ;-x offset
subq.w #8,D6
and.w D5,0(A2,D6.w) ;plot (-x,y)
move.w D4,D6 ;y offset...
add.w D3,D6 ;+x offset...
add.w #168,D6
neg.w D6 ;-(y+x offset)
and.w D5,0(A2,D6.w) ;plot (-x,-y)
move.w A6,D7 ;restore d7
noyxplot:
; rts
*****************************************************************
addq.w #1,D0 ;x=x+1
tst.w D2 ;e>=0?
blt.s circle3 ;nope
subq.w #1,D1 ;y=y-1
move.w D1,D3 ;d3=y
lsl.w #2,D3 ;d3=4*y
sub.w D3,D2 ;d2=e-4*y
circle3: move.w D0,D3 ;d3=x
lsl.w #2,D3 ;d3=4*x
addq.w #2,D3 ;d3=4*x+2
add.w D3,D2 ;d2=e+4*x+2
cmp.w D0,D1 ;x<=y?
bge plot ;no ,loop
addq.w #1,D7 ;r=r+1
cmp.w #188,D7 ;had enough?
bne circle ;not yet, punish me more, please :)
IFEQ debug
rts ;return to OS
ELSE
illegal
ENDC
;
; Word wrapping in VT52 mode lifted from
; "The hitchhiker's guide to the BIOS"
; (after so many years, at last I found out how
; to turn word wrapping on/off :)
;
msg: DC.B 27,'vD-BUG 179 ',0
endmsg:
END
Conclusion
After a few days that I coded and sent this bootsector for inclusion I
found a proper way to get rid of the Moireeffect that the routine introduces
(and get rid of that supid kludge!). I've read an article on the Internet about
a modified version of the Bresenham algorithm that was called "super cover
Bresenham line". This algorithm draws a few more pixels than the original, but
drawing parallel lines doesn't produce a Moire pattern. So I tried modifying the
circle algorithm in this fashion, and I did succeed making a supercover circle
routine. Alas, at the time of writing I have neither the exact line or circle
routine, but it shouldn't be too hard, after looking at the modified algorithm,
to make it on your own.
GGN for Alive, 2005-11-12
|
