Email: Password: Remember Me | Create Account (Free)

Back to Subject List

Old thread has been locked -- no new posts accepted in this thread
???
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.
}


List of 6 messages in thread
TopicAuthorDate
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      

Back to Subject List