 |
 |
| View previous topic :: View next topic |
| Author |
Message |
rwyoung
Joined: 12 Nov 2003
Posts: 563
Location: Lawrence, KS USA
|
|
 Posted: Tue Feb 17, 2004 11:26 am |
 |
|
Somebody check me on this...
Just for the heck of it I re-did the algorithm I posted above for 8 bit data:
| Code: | unsigned int8 bitcount1(unsigned int8 c)
{
c = (c & 0x55) + ((c >> 1) & 0x55);
c = (c & 0x33) + ((c >> 2) & 0x33);
c = (c & 0x0f) + ((c >> 4) & 0x0f);
return (c);
} |
This does work but with my copy of PCM (V3.184) it complies to 36 instructions including the function calling overhead. As "straight line" code it was 31 instructions, no loops, no jumps. Should all be single cycle instructions.
| Code: | .................... c = (c & 0x55) + ((c >> 1) & 0x55);
025C: MOVF 21,W
025D: ANDLW 55
025E: MOVWF 28
025F: BCF 03.0
0260: RRF 21,W
0261: ANDLW 55
0262: ADDWF 28,W
0263: MOVWF 21
.................... c = (c & 0x33) + ((c >> 2) & 0x33);
0264: MOVF 21,W
0265: ANDLW 33
0266: MOVWF 28
0267: RRF 21,W
0268: MOVWF 77
0269: RRF 77,F
026A: MOVLW 3F
026B: ANDWF 77,F
026C: MOVF 77,W
026D: ANDLW 33
026E: ADDWF 28,W
026F: MOVWF 21
.................... c = (c & 0x0f) + ((c >> 4) & 0x0f);
0270: MOVF 21,W
0271: ANDLW 0F
0272: MOVWF 28
0273: SWAPF 21,W
0274: MOVWF 77
0275: MOVLW 0F
0276: ANDWF 77,F
0277: MOVF 77,W
0278: ANDLW 0F
0279: ADDWF 28,W
027A: MOVWF 21
|
Neutone's sequence of if(bit_test) statements will probably run faster but it will vary with number of increments. Mine will always run same speed.
I think Neutone's is a better general solution for a microcontroller that has good bit test operations like the PIC. Still it is interesting to see how just a bunch of ANDs, SHIFTS and ADDS can do the same thing.
_________________
Rob Young
The Screw-Up Fairy may just visit you but he has crashed on my couch for the last month! |
|
 |
Neutone
Joined: 08 Sep 2003
Posts: 839
Location: Houston
|
|
| Posted: Tue Feb 17, 2004 1:18 pm |
|
|
| rwyoung wrote: | Somebody check me on this...
Neutone's sequence of if(bit_test) statements will probably run faster but it will vary with number of increments. Mine will always run same speed. |
I think the execution time is going to be fixed for the code I posted. The IF statements take 1 cycle when they don't jump and 2 when they do jump. Thats my understanding at least. I looked into doing a parity check like this and found that a better solution existed using shifts and XOR's. I found this method interesting and though somethinglike it might work for me now.
| Code: |
/***********************************************************
* Solve for parity bit on USART 2 *
***********************************************************/
/*#inline
Void Comm2_Parity(Int8 x) // Solves parity for USART 2
{ if(TX9_2) // Only solve parity if it will be used
{ #asm
bcf TX9D2 // Start by assuming even parity
btfss Comm2_Odd // Make a test for odd parity
bsf TX9D2 // Set odd parity
swapf x, W // http://www.mindhertz.com/Parity.php
xorwf x, F // http://www.mindhertz.com/Parity.php
rrf x, W // http://www.mindhertz.com/Parity.php
xorwf x, F // http://www.mindhertz.com/Parity.php
btfsc x, 2 // http://www.mindhertz.com/Parity.php
incf x, F // http://www.mindhertz.com/Parity.php
btfsc x, 0 // If bit 0 is
btg TX9D2 // Toggle
#endasm
}
}*/
|
Last edited by Neutone on Tue Feb 17, 2004 3:34 pm; edited 1 time in total |
|
|
rwyoung
Joined: 12 Nov 2003
Posts: 563
Location: Lawrence, KS USA
|
|
| Posted: Tue Feb 17, 2004 1:26 pm |
|
|
In general, doesn't parity just tell you if there is an odd or even number of 1's (or 0's)? The simple XOR & shift parity test doesn't tell you how many 1's.
Anyway still think your 8 if-test_bit version is the most efficient when you weigh code space vs speed vs readability and you want to know exactly how many 1's are in an 8 bit word.
The book "Hacker's Delight" does have some spiffy tricks for doing other things like rounding up or down to the next power of 2 (good for zero-padded FFT) and quick bit-reversal (again, good for FFT stuff). Not the cheapest book I've ever bought but a fun read and useful stuff.
_________________
Rob Young
The Screw-Up Fairy may just visit you but he has crashed on my couch for the last month! |
|
|
Douglas Kennedy
Joined: 07 Sep 2003
Posts: 755
Location: Florida
|
|
| Posted: Tue Feb 17, 2004 3:31 pm |
|
|
An improved binary search to see if one and only one bit is set in a byte b
if(b==0) goto err; /// if zero error ( no bit is set) if both the left and right nibble are non zero err
if(b>15 ) {
if (swap(b)>15) goto err; // both left and right nibbles have bits set
}
///one or more bits are in right most 4 bits either way 0000 xxxx
//now test for right 2bits left 2bits of rightmost nibble
b=b<<2; // first get it into this shape 00xx xx00
if (b >15){
if(swap(b)>15) goto err; // both left and right nibbles have bits set
}
///one or two bits are in right most 4 bits either 0000 xx00 or 0000 00xx
/// xx cannot be 11
if ((b==12) || (b==3) ) goto err;
/// its a winner only one bit was set in the byte
err:
/// it has none or more than one bit set |
|
|
|
|
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
