Dmitry's algorithms:
| CODE |
list p=16C64,t=ON,c=132,n=80,st=off radix dec include "P16C64.INC" buffer0 equ 0x20 bits_counted equ 0x21 a_byte equ 0x23 ORG 0 ;Reset Vector GOTO Main ORG 4 ;Interrupt Vector CLRF a_byte Main INCF a_byte,F MOVF a_byte,W CALL RR_bitcount MOVF a_byte,W CALL TC_bitcount MOVF a_byte,W CALL bitcount MOVF a_byte,W CALL look_up_bits goto Main ;***************************************************** ;RR_bitcount ; Brute force shift and count. RR_bitcount MOVWF buffer0 CLRF bits_counted RR1 CLRC RRF buffer0,F ;Get LSB and put in the carry SKPNC ;If LSB (i.e. C) is set INCF bits_counted,F ;then count it MOVF buffer0,F SKPZ GOTO RR1 RETURN ;***************************************************** ;TC_bitcount ; Test and Count ; Inputs: W - contains the byte whose bits need counting ; Outputs: bits_counted - # of bits that were set in W ;Memory Used: buffer0 ; ; 19 words, 20 cycles TC_bitcount MOVWF buffer0 CLRF bits_counted BTFSC buffer0,0 INCF bits_counted,F BTFSC buffer0,1 INCF bits_counted,F BTFSC buffer0,2 INCF bits_counted,F BTFSC buffer0,3 INCF bits_counted,F BTFSC buffer0,4 INCF bits_counted,F BTFSC buffer0,5 INCF bits_counted,F BTFSC buffer0,6 INCF bits_counted,F BTFSC buffer0,7 INCF bits_counted,F RETURN ;***************************************************** ;bitcount ; ; This algorithm loops one time for each bit that is set. ;It's based on an algorithm that deletes the right most ;bit in a byte. If the byte is 'b' then the algorithm is: ; b = b & (b-1) ; for example if ; b = xxxx1000 ; b-1 = xxxx0111 ; b & (b-1) = xxxx0000 ;The right most bit of b is deleted ; ;This algorithm comes from a book titled "Efficient C", by ;Thomas Plum and Jim Brodie. They credit Kernighan and Ritchie ;for the original insight. ; ; Inputs: W - contains the byte whose bits need counting ; Outputs: bits_counted - # of bits that were set in W ;Memory Used: buffer0 ; ; 9 words, 6 cycles min, 71 max bitcount MOVWF buffer0 ;Save a copy CLRF bits_counted ; BC1 MOVF buffer0,W ;Get the byte. (affects Z too) SKPNZ ;If no more bits are set RETURN ; then we're done INCF bits_counted,F ;Found a bit DECF buffer0,F ;"b-1" ANDWF buffer0,F ;b = b & (b-1) Delete right most bit GOTO BC1 ;***************************************************** ;look_up_bits ; ; 25 words, 20 cycles look_up_bits MOVWF buffer0 CALL look_up MOVWF bits_counted SWAPF buffer0,W CALL look_up ADDWF bits_counted,F RETURN look_up ANDLW 0x0f ADDWF PCL,F RETLW 0 ;0 RETLW 1 ;1 RETLW 1 ;2 RETLW 2 ;3 RETLW 1 ;4 RETLW 2 ;5 RETLW 2 ;6 RETLW 3 ;7 RETLW 1 ;8 RETLW 2 ;9 RETLW 2 ;a RETLW 3 ;b RETLW 2 ;c RETLW 3 ;d RETLW 3 ;e RETLW 4 ;f END |