home *** CD-ROM | disk | FTP | other *** search
/ No Fragments Archive 10: Diskmags / nf_archive_10.iso / MAGS / CHOSNECK / CHOS2.ZIP / CHOSNECK.2ND / STUFF / DATAS.ZIP / ART48B.SCR < prev    next >
Encoding:
Text File  |  2003-12-08  |  9.2 KB  |  261 lines
  1. <head>
  2. <title="...forever...">
  3. <font=monaco10.fnt>
  4. <font=newy36.fnt>
  5. <font=time24.fnt>
  6. <image=back.raw w=256 h=256 t=-1>
  7. <buf=3832>
  8. <bgcolor=-1>
  9. <background=0> 
  10. <link_color=253>
  11. <module=console.mod>
  12. <pal=back.pal>
  13. colors:
  14. 251 - black
  15. </head>
  16. <body>
  17. <frame x=0 y=0 w=640 h=3832 b=-1 c=-1>
  18.  
  19.  
  20. - dsp arithetic ---------------------------------------------------------------
  21.  
  22. i'll just sum up a couple of  situations  that  often occur. let's start with a
  23. small one:
  24.  
  25. shifting with the dsp is a bit shitty. you're stuck with only shifting a bit at
  26. a time (1 bit in 2 cycles) which brings down performance to the good old 68000.
  27. only in cases of extreme nostalgia would we find this a preferable thing ;)
  28.  
  29.     rep #8
  30.     lsr a
  31.  
  32. this shifts a down by 8. the 'rep' takes  4 and the 'lsr' takes 2*8, so a total
  33. of 22 cycles. this is where the weirdness of dsp starts. a multiply is actually
  34. faster than shifting:
  35.  
  36. ; init
  37.     move            #>$008000,x0
  38. ; x0=scalar, x1=value to be shifted
  39.     mpy x0,x1,a                 ; a=value>>8
  40.  
  41. this takes only 6 (5?) cycles. and  if  you  use  it in a loop (x0 initialized)
  42. then only 2.
  43.  
  44. let's say you want to scale a difference.
  45.  
  46. res=s(v1-v0)
  47.  
  48. where 's' is the scaler, 'v1' and  'v0'  are end and start values respectively.
  49. you could do it like this:
  50.  
  51. ; a=v1, x0=v0, y0=s
  52.     sub x0,a                    ; a=dv=v1-v0
  53.     move            a,x1        ; x1=dv
  54.     mpy y0,x1,b                 ; b=s*dv=s(v1-v0)
  55.  
  56. hhmm.. a straightforward implementation  on  most traditional processors. still
  57. this amounts to 6 cycles. let's try a more wacky approach:
  58.  
  59. ; x1=v1, x0=v0, y0=s
  60.     mpy +x1,y0,a                ; a=s*v1
  61.     mac -x0,y0,a                ; a=s*v1-s*v0=s(v1-v0)
  62.  
  63. weirdness, by using only multiplications and  macs  you  get a 4 cycle version.
  64. and this situation does occur  in  alot  of  algorithms. for example (bi)linear
  65. interpolation.
  66.  
  67. finally, you might know  the  dsp  suffers  from  a  slow  div.  infact, a full
  68. division instruction isn't even available.  the  'div'  we  speak of is only an
  69. iteration. and doing a full 24bits division with it is no picknick.
  70.  
  71.     andi    #$FE,ccr
  72.     rep #24                     ; do 24 iterations
  73.     div x0,a                    ; perform iteration.
  74. ; a1=rest, a0=quotient
  75.  
  76. the 'rep' is 4 cycles.. the  'andi'  takes  2. then 24*2=48 cycles additionally
  77. makes 54 cycles. certainly we can't live with that.
  78.  
  79. sure you can do it faster. for instance we only want to divide 16bit numbers.
  80.  
  81. ; init
  82.     move            #>$000080,x0
  83.  
  84. ; u/v, x1=u, y1=v
  85.     mpy x0,x1,a                 ; a0=u<<8
  86.     andi    #$FE,ccr
  87.     rep #16
  88.     div y1,a
  89. ; a0=quotient
  90.  
  91. we see 16 cycles are saved but  2  (or  5 with init) additional ones are taken,
  92. resulting in a total improvement of 14  cycles. sure, that's no big change, but
  93. it's a start.
  94.  
  95. the real speedup lies in the following fact:
  96.  
  97. u/v = u * (1/v)
  98.  
  99. yeah, that's just a dumb way of representing  it you think. indeed it is ;) but
  100. it's also a little push in  the  right  direction. see the '*'? notice anything
  101. special about it? no? doh! this isn't working ;)
  102.  
  103. the '*' ofcourse denotes  multiplication  and  ofcourse  this  is a fast little
  104. operation on the dsp. but now you still  have the '/' for the division. indeed,
  105. and we need to get rid of it,  cos  otherwise indeed you have found a silly way
  106. of writing down the same thing.
  107.  
  108. how about a nice cup of precalc you  say?  and indeed why not. just make a nice
  109. table to index with your  v.  an  inverse-table  that is. just precalculate all
  110. your inverse into  it  and  you're  done.  then  assuming  the  inversetable is
  111. initialized:
  112.  
  113. ; x0=u, x1=v
  114.     move            #inverse_table,r0
  115.     move            x1,n0           ; n0=v
  116.     nop
  117.     move            x:(r0+n0),x1    ; x1=1/v
  118.     mpy x0,x1,a                     ; a=u*(1/v)=u/v
  119.  
  120. ofcourse we can kill the nop  by  overlapping with another rout where possible.
  121. but you can see the idea. it's a  whole lot faster. just one problem. the range
  122. of your 'v' is not endless. typicly  coders  have used anything from ranges 256
  123. upto 4096. enough for some cases. but for fixedpoint precision it's shit.
  124.  
  125. so what now? go back to div  iterations  for big numbers? surely that's not the
  126. ideal solution. and indeed it is not. at least not if you mind a small error in
  127. calculation. the trick is now  to  use  multiple  passes  in through your small
  128. inverse table.
  129.  
  130. let's explain this before we spill some  code.  we start here using decimals to
  131. keep it simple. let's say we only have a 10 word inverse table:
  132.  
  133. 0: -
  134. 1: 1
  135. 2: .5
  136. 3: .333..
  137. 4: .25
  138. 5: .2
  139. 6: .166..
  140. 7: .142..
  141. 8: .125
  142. 9: .111..
  143.  
  144. and now we want to calculate  1/22.  surely,  we  can't  look this up. for this
  145. trick to work we need to extend the table to twice it's range:
  146.  
  147. 0: -        10: .1
  148. 1: 1        11: .0999..
  149. 2: .5       12: .0833..
  150. 3: .333..   13: .0769..
  151. 4: .25      14: .0714..
  152. 5: .2       15: .0666..
  153. 6: .166..   16: .0625
  154. 7: .142..   17: .0588..
  155. 8: .125     18: .0555..
  156. 9: .111..   19: .0526..
  157.  
  158. we can easily see that by factorising the denominator we get:
  159.  
  160. 1/22 = 1/2 * 1/11
  161.  
  162. but ofcourse, if you know a little  about  algebra  that not all numbers can be
  163. factorised ;) so now we have to take  a step back from exact calculation and go
  164. for an approximation.
  165.  
  166. what we do is we split the  denominator  up  into digits. we now have the upper
  167. digit '2' and the lower digit '2'.  is  we  divide the denominator by the upper
  168. part:
  169.  
  170. u=denom/upper = 22/2 = 11
  171.  
  172. we can now lookup it's inverse  and  we  get 1/u=.1111.. we then also calculate
  173. the inverse of the upper digit:
  174.  
  175. v=1/upper=1/2=.5
  176.  
  177. we then multiply u*v and get .05555.. ~= 1/22 hurrah!
  178.  
  179. ofcourse taking 23 as the denominator will give a slight error! in this case:
  180.  
  181. u=23/2 = 11.5 which  will  be  rounded  or  truncated  depending on your taste.
  182. please note rounding will require an extra entry in the inverse table!
  183. we just assume truncation here..
  184. u=11
  185. v=1/2=.5
  186. u*v = .05555 > 1/23 ~= .04348
  187.  
  188. you can see you  have  a  20%  deviation  in  this  case  which is undesirable.
  189. ofcourse when using 8bit radix instead of digits, errors quickly shrink to ~1%.
  190.  
  191. here's the implementation i use for 15bit numbers:
  192.  
  193. ; Calc 1/Z.
  194. ; y:(r2):inverse table (256 entries)
  195. ; y:(r3)=1/128
  196. ; a=Z
  197.     move            a,x1        y:(r3),y1   ; x1=Z, y=1/128
  198.     mpyr    x1,y1,a                     ; a=upper=Z>>7
  199.     move            a,n2                ; n2=upper
  200.     nop
  201.     move                    y:(r2+n2),y1    ; y1=v=1/upper
  202.     mpyr    y1,x1,a                     ; a=u=Z/upper
  203.     move            a,n2                ; n2=u
  204.     nop
  205.     move                    y:(r2+n2),x1    ; x1= 1/u
  206.     mpyr    y1,x1,a                     ; a=u*v~=1/Z
  207.  
  208. as you can see this takes a total  of 20 cycles, which is a healthy improvement
  209. over the the 40 needed for  the  16  bit  division algorithm. also, please note
  210. that it can be  combined  (in  parallel)  with  other  code for efficiency. for
  211. perspectivation for instance this algorithm is definetely preferred.
  212.  
  213. anyway, it's amazing i figured this out  by  myself.  i even had to rethink the
  214. whole process when i saw the code  again.  anyway, i hope this makes clear that
  215. you can do some pretty silly stuff with the 56001.
  216.  
  217. - short -----------------------------------------------------------------------
  218.  
  219. a short bit about short  addressing  modes.  the  56001  provides alot of short
  220. modes. these are denoted by the '<'. As you might or might not know this stands
  221. for shifted up. You might know you can have 8bit short immediate data moves.
  222.  
  223.     move            #<1,a   ; a=$00.010000.000000 !
  224. (is _not_ the same as)
  225.     move            #>1,a   ; a=$00.000001.000000
  226.  
  227. ofcourse the <1 saves a program word  and executes faster, but the result isn't
  228. the same. however, try this:
  229.  
  230.     move            #<1,a1  ; a=$??.000001.??????
  231.  
  232. it saves a program word and some  cycles  just as '#<1,a', but doesn't shift it
  233. up! ofcourse you need to be careful with the contents of a2 and a0, but in some
  234. cases this can be solved in a quite simple fashion.
  235.  
  236. ofcourse the address registers r0..r7 can use similar similar addressing modes.
  237.  
  238. - conclusion ------------------------------------------------------------------
  239.  
  240. i provided alot of tips and tricks and  hope i also guided some beginners round
  241. the potential pitfalls of dsp programming. as  you might see there is alot more
  242. than meets the  eye.  but  this  is  actually  the  strength  of  the dsp. it's
  243. limitations actually force you to  optimise.  that's  the beauty of coding this
  244. little beast i think =)
  245.  
  246. - final words -----------------------------------------------------------------
  247.  
  248. if you want to know more, a  good  place  to check out is mikro.atari.org. this
  249. guy has tons of docs and also alot  about falcon programming and it's dsp. also
  250. feel  free  to  contact  me   at:  pietervdmeer@netscape.net  for  any  further
  251. questions.
  252.  
  253.  
  254. -- - --- -- -------------------------------------------------------------------
  255.  CHOSNECK 4th appearance                                           contact us:
  256.  done by the dream survivors                                 greymsb@poczta.fm
  257. ----------------------------------------------------------------- -- - --- ----
  258. </frame>
  259. </body>
  260.  
  261.