??? 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 |