On Fri, 22 Dec 2000, James Newton wrote:
> Thanks Scott (and Andy). I thought that looked like the old xor swap trick,
> but somehow I just couldn't wrap my mind around WHY it was being used. With
> your comments it begins to make sense. Now if I could just figure out how
> you guys dream up these things... <GRIN> Wow. Divide 16 bits by a constant
> (15) in *11* cycles.
>
> Nik, here is a perfect example of a need for a database for the multiply (or
> divide) by a constant code generator. You can look at the incoming
> parameters, search a table and say "The following machine generated code
> will produce the correct result in x cycles, but there is hand optimized
> code (also listed below) that appears to meet your needs which is only y
> cycles.
BTW, you should be aware that Nik's generator is more accurate than what Dmitry
and I generated. The algorithm is based on this formula:
1/(A+B) ~= B/A - (B/A)^2 + (B/A)^3 + ...
Dmitry and I computed the first two terms, Nik does all three in the generator.
The error is on the order of 1/16/16/16 = 2E-4
For example:
suppose you wanted to divide 65535 by 15. The exact answer is 4369. However,
using Dmitry's code you'd get: 4350. Nik's produces: 4365 (I think).
But a slight mod will improve Dmitry's
{Quote hidden}> > ;high=a.b , low=c.d
> >
> > movlw 0xF0
> > andwf low,F ;c.0
> > andwf high,W ;a.0
>
> ; at this point, the low nibble of `low' is zero
> ; W contains the high nibble of `high'
>
> >
> > xorwf high,W ;a.0^a.b
> ; now W contains low nibble of high, namely 0x0b
> ; W ^ high
> ; 0xa0 ^ 0xab => 0x0b
>
> > xorwf high,F ;a.0
> ;Now the lower nibble of a is cleared.
> ; W ^ high
> ; 0x0b ^ 0xab => 0xa0 and this is stored back in high
>
> > xorwf high,W ;a.b
> ;Now W contains the original value of high
> ; W ^ high
> ; 0x0b ^ 0xa0 => 0xab
>
> >
> > swapf low,F ;0.c
> > swapf high,F ;0.a
> >
> > addwf low,F ;0.c + a.b
> > skpnc
> > incf high,F ;0.a + carry
movf high,w
addwf low,f
skpnc
incf high,f
This modification will yield the result: 4366
>
> Scott, this is a good example of the need for an open source C compiler that
> also checks a library of routines to find the best possible code for the
> parameters (if they are known). Over time, an awesome library of optimized
> code will pile up.
True. At some point Nik will integrate his code generator into SDCC.
Scott
--
http://www.piclist.com hint: To leave the PICList
.....piclist-unsubscribe-requestKILLspam
@spam@mitvma.mit.edu
