| ??? 03/23/04 10:49 Read: times |
#67257 - RE: Counting bits in C Responding to: ???'s previous message |
Just in case anybody is interested, here are a couple of population count functions I have had lying around for some time.
The first (fast) version uses a look-up table. The second (compact) version is a bit more interesting, I hope that you can follow my cryptic comments to see how it works. Either function can be readilly adapted to find the population of any number of bytes.
//
// Fast Long Population Count
//
// Author: Graham Cole
//
// Input: l - 32-bit word in R4/R5/R6/R7.
//
// Output: Returns number of bits set to 1 in the argument.
//
#pragma ASM
$REGUSE _fast_long_population_count( A, B, R3, R7, DPH, DPL )
#pragma ENDASM
unsigned char fast_long_population_count( long unsigned int l )
{
l = l; // Suppress unused variable warning - optimised out.
#pragma ASM
nibble_mask SET R3 ;
;
MOV nibble_mask,#0x0F ;
;
MOV DPTR,#nibble_population_count_table
;
MOV A,R7 ; Process LS byte first.
SWAP A ;
ANL A,nibble_mask ; MS nibble.
MOVC A,@A+DPTR ;
XCH A,R7 ;
;
ANL A,nibble_mask ; LS nibble.
MOVC A,@A+DPTR ;
ADD A,R7 ;
MOV R7,A ;
;
MOV A,R6 ; Process next LS byte.
SWAP A ;
ANL A,nibble_mask ; MS nibble.
MOVC A,@A+DPTR ;
ADD A,R7 ;
MOV R7,A ;
;
MOV A,R6 ;
ANL A,nibble_mask ; LS nibble.
MOVC A,@A+DPTR ;
ADD A,R7 ;
MOV R7,A ;
;
MOV A,R5 ; Process next LS byte.
SWAP A ;
ANL A,nibble_mask ; MS nibble.
MOVC A,@A+DPTR ;
ADD A,R7 ;
MOV R7,A ;
;
MOV A,R5 ;
ANL A,nibble_mask ; LS nibble.
MOVC A,@A+DPTR ;
ADD A,R7 ;
MOV R7,A ;
;
MOV A,R4 ; Process MS byte.
SWAP A ;
ANL A,nibble_mask ; MS nibble.
MOVC A,@A+DPTR ;
ADD A,R7 ;
MOV R7,A ;
;
MOV A,R4 ;
ANL A,nibble_mask ; LS nibble.
MOVC A,@A+DPTR ;
ADD A,R7 ;
;
MOV R7,A ; Return with result in R7.
;
RET ;
nibble_population_count_table:
DB 0 ;0000 = 0
DB 1 ;0001 = 1
DB 1 ;0010 = 1
DB 2 ;0011 = 2
DB 1 ;0100 = 1
DB 2 ;0101 = 2
DB 2 ;0110 = 2
DB 3 ;0111 = 3
DB 1 ;1000 = 1
DB 2 ;1001 = 2
DB 2 ;1010 = 2
DB 3 ;1011 = 3
DB 2 ;1100 = 2
DB 3 ;1101 = 3
DB 3 ;1110 = 3
DB 4 ;1111 = 4
#pragma ENDASM
return( B );
}
//
// Compact Long Population Count
//
// Author: Graham Cole
//
// Input: l - 32-bit word in R4/R5/R6/R7.
//
// Output: Returns number of bits set to 1 in the argument.
//
// Function: Compute population count, l is destroyed in process.
//
// Notes: Call ?compact_long_population_count to process l in
// data memory pointed to by R0. Byte order does not matter.
// Avoids need for look-up table at the expense of speed.
//
#pragma ASM
$REGUSE _compact_long_population_count( A, R0, R1, R3, R4, R5, R6, R7 )
#pragma ENDASM
unsigned char compact_long_population_count( long unsigned int l )
{
l = l; // Suppress unused variable warning - optimised out.
#pragma ASM
pointer SET R0 ;
loop_counter SET R1 ;
population SET R3 ;
;
MOV A,PSW ;Get the base address of
ANL A,#0x18 ; the current register bank.
ORL A,#0x04 ;Point to register R4.
MOV pointer,A ;R0 is a pointer to R4.
;
?compact_long_population_count: ;
;
MOV population,#0x00 ;
;
MOV loop_counter,#0x04 ;Iterate for registers R4/R5/R6/R7
;
?clpc_loop: ;
;
MOV A,@pointer ;Acc = abcdefgh
ANL A,#0x55 ;Acc = 0b0d0f0h
XCH A,@pointer ;
RL A ;
ANL A,#0x55 ;Acc = 0a0c0d0g
ADD A,@pointer ;Acc = lmnopqrs
MOV @pointer,A ;
ANL A,#0x33 ;Acc = 00no00rs
XCH A,@pointer ;
RL A ;
RL A ;
ANL A,#0x33 ;Acc = 00lm00pq
ADD A,@pointer ;Acc = 0tuv0wxy
MOV @pointer,A ;
ANL A,#0x0F ;Acc = 00000wxy
XCH A,@pointer ;
SWAP A ;
ANL A,#0x0F ;Acc = 00000tuv
ADD A,@pointer ;Acc = population_of_byte.
ADD A,population ;
MOV population,A ;population = population + population_of_byte.
;
INC pointer ;
DJNZ loop_counter,?clpc_loop
MOV A,population ;
MOV R7,A ;
;
RET ;
#pragma ENDASM
return( 0 ); // Dummy return.
}
|
| Topic | Author | Date |
| Counting bits in C | 01/01/70 00:00 | |
| RE: Counting bits in C | 01/01/70 00:00 | |
| RE: Counting bits in C | 01/01/70 00:00 | |
| RE: Counting bits in C | 01/01/70 00:00 | |
| RE: Counting bits in C | 01/01/70 00:00 | |
RE: Counting bits in C | 01/01/70 00:00 |



