 |
 |
| View previous topic :: View next topic |
| Author |
Message |
asmboy
Joined: 20 Nov 2007
Posts: 2128
Location: albany ny
|
| nearest power of two algorithm |
 Posted: Tue May 21, 2013 1:11 pm |
 |
|
I recently updated an OLD piece of CCS code to get more needed speed.
This extracts the exact or NEAREST (lesser) power of two from an unsigned int8 'x'.
The output range is 0-7.
I used to use the second approach , until just creating the first. ( which smokes it - especially if the input x=1 ) due to the rough bit_test() function.
Is there a better way that can do it more deterministically ? ie: in a fixed
execution time for ANY input x ??
| Code: |
unsigned int8 pow2( unsigned int8 x){
#bit high = x.7
unsigned int y=7; if (!x) return 0;
while ( !high) {
x <<=1;
y--;
}
return y; }
unsigned int8 pow2a( unsigned int8 x){
unsigned int y=7; if (!x) return 0;
while (y){
if ( bit_test(x,y) ) break;
--y;
}
return y; }
|
|
|
 |
Ttelmah
Joined: 11 Mar 2010
Posts: 19539
|
|
| Posted: Tue May 21, 2013 1:58 pm |
|
|
The PIC itself does not have a bit test function using a variable.
So, the bit test version is done by 'building' a bit mask, by taking a value, and then rotating it the required number of bits. Hence the sloth.
Your rotating a mask version is therefore a lot quicker, since the same mask is re-used each time round, with just a single rotation.
Funnily you should be able to go even quicker by being more bulky, with something like:
| Code: |
unsigned int8 pow2( unsigned int8 x)
{
if (bit_test(x,7)) return 7;
if (bit_test(x,6)) return 6;
if (bit_test(x,5)) return 5;
if (bit_test(x,4)) return 4;
if (bit_test(x,3)) return 3;
if (bit_test(x,2)) return 2;
if (bit_test(x,1)) return 1;
return 0;
}
|
The reason is that the PIC does have a fixed bit test and branch instruction. However the saving would be tiny.
Now, you could make this give fixed times, by coding like:
| Code: |
unsigned int8 pow2( unsigned int8 x)
{
if (bit_test(x,7))
{
delay_cycles(30);
return 7;
}
if (bit_test(x,6))
{
delay_cycles(25);
return 6;
}
//........
|
You would have to adjust the delays to get the timings correct. Delaying the returns from the high bits to match the lower ones. With a bit of thought the bit test, and delay, could be written as a macro.
You could use a similar approach on the rotation mask code, by just adding something like delay_us(y*6); before the return. Again you'd need to calculate the timing needed.
As a 'comment', you really need to return the value as signed, and set the return to -1 as an 'error' flag, if no bit is set, or test your incoming value for being '0', before calling the function. With the code you show, you get zero returned for both zero, and one (zero'th bit set).
Best Wishes |
|
|
asmboy
Joined: 20 Nov 2007
Posts: 2128
Location: albany ny
|
| power of two |
| Posted: Tue May 21, 2013 3:49 pm |
|
|
thank you very much
as is: i have other dependent code that would
not be happy with signed rets....
i return 0 as the no bits set - as an initial test -
before any other - since i
am legacy style stuck expecting that as the no bits reply
and i now am satisfied that there probably is no faster deterministic
approach than you kindly showed
thanks again
donald |
|
|
|
|
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 vote in polls in this forum
|
Powered by phpBB © 2001, 2005 phpBB Group
|
FAQ 
Search
Register
Profile 
Log in to check your private messages 
Log in
