News Team Current issue History Online Support Download Forum @Pouet

01 - 02 - SE - 03 - 04 - 05 - 06 - 07 - 08 - 09 - 10 - 11 - 12 - 13 - 14

Alive 11
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

       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

       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:


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.


            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

       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,-

       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
       e=e+4*x+2       !calculate next step of the estimator

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

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

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

               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 ;)

               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)
;i               SET $C000
i              SET $3FFF
               REPT 16
               DC.W i
;i               SET i>>1+$8000
i               SET i>>1

;i               SET 3
i              SET $FFFC
               REPT 16
               DC.W i
;i              SET i<<1+1
i              SET i<<1

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
;               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

; 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


       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
Alive 11