6502.org Forum  Projects  Code  Documents  Tools  Forum
It is currently Sat Nov 23, 2024 5:42 am

All times are UTC




Post new topic Reply to topic  [ 10 posts ] 
Author Message
 Post subject: SQRT Program needs check
PostPosted: Wed Mar 13, 2013 5:53 pm 
Offline

Joined: Mon Mar 02, 2009 7:27 pm
Posts: 3258
Location: NC, USA
Hello, I am trying to use a square root program for circle plotting and I'm trying to use Lee Davidson's routine in 6502.org's sourcecode repository.
I'm trying it out on M. Kowalski's assembler/debugger and it doesn't seem to function correctly.

Can someone confirm this?

_________________
65Org16:https://github.com/ElEctric-EyE/verilog-6502


Top
 Profile  
Reply with quote  
PostPosted: Wed Mar 13, 2013 6:49 pm 
Offline
User avatar

Joined: Thu Dec 11, 2008 1:28 pm
Posts: 10986
Location: England
I ran it in http://biged.github.com/6502js/ and it seems OK. What test data is failing?


Top
 Profile  
Reply with quote  
PostPosted: Wed Mar 13, 2013 7:07 pm 
Offline

Joined: Mon Mar 02, 2009 7:27 pm
Posts: 3258
Location: NC, USA
It's working for me now. I think I too hurriedly reassigned variable locations and maybe they overlapped or something.
Thanks for checking!
I'll try to convert it over to 65Org16 again, now that I can watch the behavior.

_________________
65Org16:https://github.com/ElEctric-EyE/verilog-6502


Top
 Profile  
Reply with quote  
PostPosted: Wed Mar 13, 2013 7:31 pm 
Offline
User avatar

Joined: Tue Nov 16, 2010 8:00 am
Posts: 2353
Location: Gouda, The Netherlands
An integer sqrt() is fairly easy to do in hardware. Google for verilog integer sqrt for some suggestions.


Top
 Profile  
Reply with quote  
PostPosted: Thu Mar 14, 2013 1:54 am 
Offline

Joined: Mon Mar 02, 2009 7:27 pm
Posts: 3258
Location: NC, USA
I'm all about hardware plotting as you know.

But the Grey area lies in when to stop Verilog 'hardware' and when to start CPU 'software'.

It's very interesting stuff to me which is why I try to keep exacting records on my projects, whenever any progress is made.

_________________
65Org16:https://github.com/ElEctric-EyE/verilog-6502


Top
 Profile  
Reply with quote  
PostPosted: Thu Mar 14, 2013 6:42 am 
Offline
User avatar

Joined: Tue Nov 16, 2010 8:00 am
Posts: 2353
Location: Gouda, The Netherlands
One way to combine CPU and hardware for math functions is to make a table, like Garth's math tables but with a twist. Suppose you want to add an 8x8 bit multiply, but don't want to add an extra instruction. Instead, you could make a table, say from $12340000 to $1234FFFF. At every address location, you'll find the bottom two address bytes multiplied.

But instead of implementing this table with expensive memory, you fake it with a line of verilog:
Code:
out <= addr[15:8] * addr[7:0];


For sqrt function, you could make a similar table, but since a simple state machine would take a few cycles to produce the result, you would need to deassert RDY until it's done.


Top
 Profile  
Reply with quote  
PostPosted: Thu Mar 14, 2013 1:18 pm 
Offline

Joined: Fri Sep 28, 2012 12:27 pm
Posts: 25
Location: Boulogne Billancourt, France
BTW, I do not know the exact need you have beyond the requirement for drawing circles, but in case you need to draw whole circles and not arcs, then maybe you will find the source code provided here of some help (sorry about the comments in my mother language, but I think you might get the idea).
R is a 16bits quantity.

The center of the circle to draw is also given in 16bits quantities (CX+1, CX) and (CY+1, CY)
The command is able to draw a circle in the horizontal resolutions below
140 pixels, 280 pixels and 560 pixels per line, hence the times two, keep unchanged or divide by two flow paths you might find in the source (given the grafwrk memory content).
The vertical resolution is always 192 pixels per vertice on the display screen.
The DOTCALL routine is in charge of plotting a pixel on screen. It takes into account any windowing (throwing away drawing requests out of the display screen and applying any windowing you might have setup by other means).
Through not optimized at the machine code level (particularly upon the location of often used memory slots), I think this routine will be somewhat faster than using any internal computations like plain 8bit multiplications or square root computations and still does not use lookup tables so that memory footprint is kept small if that is important to you.
Whole source can be extracted from http://bgilon.free.fr/apple2/Bluesoft.do (Apple // disk image containing the source of a program I wrote in the past).

Code:
  114 * Initialisation des valeurs : X(0)=0, Y(0)=R...
  115
  116          LDA   #0
                              ===== Page 3 =====
 
  117          STA   YFRAC
  118          STA   XFRAC
  119          STA   X          X(0) = 0.
  120          STA   X+1
  121          LDA   R          Y(0) = R.
  122          STA   Y
  123          LDA   R+1
  124          STA   Y+1
  125
  126          JSR   DOTXYC
  127
  128 * Pas d'iteration si (R = 0) ou (R < 2 en COL140).
  129
  130          LDA   R+1
  131          BNE   VARX
  132          LDA   R
  133          BEQ   RETBAS
  134          LDX   GRAFWRK
  135          CPX   #5
  136          BNE   VARX
  137          CMP   #1
  138          BNE   VARX
  139 RETBAS   RTS              Retour au BASIC.
  140
  141 * Si COL140, XYBIS <- Y/2,
  142 * si BW560,  XYBIS <- Y*2,
  143 * sinon:     XYBIS <- Y.
  144
  145 VARX     LDA   Y
  146          STA   XYBIS
  147          LDA   Y+1
  148          STA   XYBIS+1
  149          LDX   GRAFWRK
  150          CPX   #5
  151          BEQ   VARXA
  152          CPX   #9
  153          BNE   VARX1
  154          ASL   XYBIS
  155          ROL   XYBIS+1
  156          JMP   VARX1
  157 VARXA    LSR   XYBIS+1
  158          ROR   XYBIS
  159
  160 * (XFRAC,X) <- (XFRAC,X) + (XYBIS,XYBIS+1).
  161
  162 * Si une carry est generee de cette addition 16 bits,
  163 * alors modification de X+1...
  164
  165 VARX1    LDA   XFRAC
  166          CLC
  167          ADC   XYBIS      Addition poids faibles...
  168          STA   XFRAC
  169          LDA   X
  170          TAX
  171          ADC   XYBIS+1     et forts.
  172          STA   X
  173          BCC   VARX2      Si pas de report,
                              ===== Page 4 =====
 
  174          INC   X+1         sinon modification de X+1
  175          JMP   VARX3       et allumage d'un nouveau point.
  176 VARX2    CPX   X          Y-a-t-il eu modification de X ?
  177          BEQ   VARY       Non.
  178 VARX3    JSR   DOTXYC
  179
  180 * Si COL140, XYBIS <- X*2,
  181 * si BW560,  XYBIS <- X/2,
  182 * sinon:     XYBIS ,- X.
  183
  184 VARY     LDA   X
  185          STA   XYBIS
  186          LDA   X+1
  187          STA   XYBIS+1
  188          LDX   GRAFWRK
  189          CPX   #5
  190          BEQ   VARYA
  191          CPX   #9
  192          BNE   VARY1
  193          LSR   XYBIS+1
  194          ROR   XYBIS
  195          JMP   VARY1
  196 VARYA    ASL   XYBIS
  197          ROL   XYBIS+1
  198
  199 * (Y,YFRAC) <- (Y,YFRAC) - (XYBIS+1,XYBIS).
  200
  201 * Si report apres cette soustraction 16 bits, alors
  202 * modification de Y+1.
  203
  204 VARY1    LDA   YFRAC      Soustraction poids faible.
  205          SEC
  206          SBC   XYBIS
  207          STA   YFRAC
  208          LDA   Y          Soustraction poids fort.
  209          TAY
  210          SBC   XYBIS+1
  211          STA   Y
  212          BCS   VARY2      Si pas de report.
  213          DEC   Y+1        Modification de Y+1
  214          JMP   VARY3      d'ou allumage du point.
  215 VARY2    CPY   Y          Y-a-t-il eu modification de Y ?
  216          BNE   VARY3      Oui: alors allumage.
  217
  218 VARY4    JMP   VARX       Nouveau point.
  219
  220 VARY3    JSR   DOTXYC     Allumage.
  221
  222          LDA   Y          Est-ce le dernier ? (Y=0).
  223          ORA   Y+1
  224          BNE   VARY4      Non: nouveau point.
  225
  226          RTS              Retour au BASIC.
  227
  228 * DOTXYC est la routine qui assure l'allumage des 4 points
  229 * de coordonnees : (CX+X,CY+Y),(CX-X,CY+Y),
  230 *                  (CX-X,CY-Y),(CX+X,CY-Y).
                              ===== Page 5 =====
 
  231
  232 DOTXYC   LDA   X
  233          CLC
  234          ADC   CX
  235          STA   ABS1
  236          PHA
  237          LDA   X+1
  238          ADC   CX+1
  239          STA   ABS1+1
  240          PHA
  241          LDA   Y
  242          CLC
  243          ADC   CY
  244          STA   ORD1
  245          LDA   Y+1
  246          ADC   CY+1
  247          STA   ORD1+1
  248
  249          JSR   DOTCALL    Allumage de (CX+X,CY+Y).
  250
  251          LDA   CX
  252          SEC
  253          SBC   X
  254          STA   ABS1
  255          LDA   CX+1
  256          SBC   X+1
  257          STA   ABS1+1
  258
  259          JSR   DOTCALL    Allumage de (CX-X,CY+Y).
  260
  261          LDA   CY
  262          SEC
  263          SBC   Y
  264          STA   ORD1
  265          LDA   CY+1
  266          SBC   Y+1
  267          STA   ORD1+1
  268
  269          JSR   DOTCALL    Allumage de (CX-X,CY-Y).
  270
  271          PLA
  272          STA   ABS1+1
  273          PLA
  274          STA   ABS1
  275
  276          JMP   DOTCALL    Allumage de (CX+X,CY-Y).

HHTHATS,
Benoît


Last edited by Benoit0123 on Thu Mar 14, 2013 4:31 pm, edited 1 time in total.

Top
 Profile  
Reply with quote  
PostPosted: Thu Mar 14, 2013 2:07 pm 
Offline

Joined: Fri Sep 28, 2012 12:27 pm
Posts: 25
Location: Boulogne Billancourt, France
Final word: here is a summary of the 6502 code above translated in a somewhat pseudo code in case you would like to easily get the picture:
draw a 90° circle arc.... from [0,R] to [R,0] (i.e. the upper right quadrant or angle from 90° to 0°)...
Code:
Legend is:
() mutibyte operation (i.e. bind, add, substract, compare, either 16 or 24bits)
[] to designate pixel coordinates

XFRAC <-0
YFRAC <-0
(X, X+1) <- (0, 0)
(Y, Y+1 <- (R, R+1)

]LOOP:
(XYBIS, XYBIS+1) <- (Y,Y+1)
(XFRAC, X, X+1) <- (XFRAC, X, X + 1) + (XYBIS, XYBIS+1, 0) * 24bits add
If OldX (i.e. X before 24bits add)<> X OR X+1 changed (i.e. incremented) THEN CALL DotXYC

(XYBIS, XYBIS+1) <- (X,X+1)
(YFRAC, Y,Y+1) <- (YFRAC, Y, Y + 1) - (XYBIS, XYBIS+1,0) * 24bits substract
If OldY (i.e. Y before 24bits substract)<> Y OR Y+1 changed (i.e. decremented) THEN CALL DotXYC:IF (Y,Y+1)= (0,0) THEN END
JMP ]LOOP

DotXYC.. sets the four pixels in a symmetry around the [CX, CY] circle center: [CX-X,CY-Y], [CX-X,CY+Y], [CX+X,CY+Y] and [CX+X,CY-Y]..

Again HTHATS,
Benoît


Last edited by Benoit0123 on Thu Mar 14, 2013 4:28 pm, edited 2 times in total.

Top
 Profile  
Reply with quote  
PostPosted: Thu Mar 14, 2013 2:27 pm 
Offline

Joined: Mon Mar 02, 2009 7:27 pm
Posts: 3258
Location: NC, USA
Thanks for sharing!

I have alot to evaluate next couple of weeks. :)


BTW, happy PI day everybody. :lol:

_________________
65Org16:https://github.com/ElEctric-EyE/verilog-6502


Top
 Profile  
Reply with quote  
PostPosted: Fri Mar 22, 2013 2:59 pm 
Offline

Joined: Fri Sep 28, 2012 12:27 pm
Posts: 25
Location: Boulogne Billancourt, France
Penultimate final word: It seems that the algorithm is similar to the one exposed here (i.e. at the URL below) for building both sinus and cosinus tables at the same time w/o any FP resource.
https://plus.google.com/108984290462000253857/posts/X2mzfRHAemP
A sample BASIC program is provided as part of the post here...

Benoît


Top
 Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 10 posts ] 

All times are UTC


Who is online

Users browsing this forum: No registered users and 29 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to: