Quickest way to get highest set bit on port in to a variable?

[bmoe79]

Hi.
I have eight sensors with digital output connected to a port and now I want to in the quickest way get only the highest set bit in to a variable.

if port = 110000
I want var = 000000

if port = 001111
I want var = 001000

So how can I do this in quickest(least amount of clock cycles) possible way?

Regards
/Matias

[Archangel]

look at NCD command to do what you asked, checkout AND && for your example, search for MASK: http://www.picbasic.co.uk/forum/show...highlight=mask
or you could use a lookup table

[towlerg]

What PIC device?

[bmoe79]

What PIC device?

It´s a PIC18F45K80

[towlerg]

sorry can't write PIC assembler but something like

WReg= 8
Rotate Left f through Carry, 1
jump on carry, done
dec WReg
Rotate Left f through Carry, 1
jump on carry, done
etc...

or maybe BTFSC - BitTest, skip if clear

George

[Charlie]

To repeat, look up NCD in the manual. I think it does what you want.

[towlerg]

Except he wants the fastest not the easiest.

[HenrikOlsson]

This is what the NCD routine looks like in the pbppic18.lib file when stripping out the non runtime stuff:

;****************************************************************
;* NCD        : Priority encode                                 *
;*                                                              *
;* Input      : R0 = 16 bit value                               *
;* Output     : W = bit number                                  *
;*                                                              *
;* Notes      :                                                 *
;****************************************************************

NCD     clrf    R0 + 1
NCDL    movwf   R0
        movlw   17              ; Set result
ncdloop addlw   -1              ; Count down result - sets C so loop will end
        rlcf    R0, F           ; Shift upper bit to carry
        rlcf    R0 + 1, F
        bnc     ncdloop         ; If carry set then done
        goto    DUNN

I'll say what I usually say which is that I pretty much suck at assembly language stuff but that looks pretty tight to me. Obviously the execution time will vary depending on how many times it has to iterate thru the loop before it finds a bit that is set. Then there are helper macros which puts the byte/Word in question into the correct register (R0) and so on, if interested they are in the pbppic18.mac file.

Is there a faster way? Perhaps but I'd give NCD a try and get some performance data on that first - otherwise you don't know what to beat (or if you even need to beet it) - IMHO of course.

/Henrik.

[rsocor01]

Like Archangel mentioned above, you should also try the LOOKUP command. This command takes only a few cycles to execute.

[towlerg]

Henric, never the less, not as quick as 8 rotates and 8 jump on carry in-line. Worst case, with no bits set in the target thats only 16 cycles.

rscor01, I didn't realize LOOKUP would do that. How would that go?

George

[rsocor01]

rscor01, I didn't realize LOOKUP would do that. How would that go?

Nevermind. You would need too many entries in the LOOKUP constant fields. That would be 64 entries to be precise since your variable PORT has 6 bits. It will be something like this

LOOKUP MyPort, [0,1,2,2,3,3,3,3,4,........], MyVar

Still, it might be faster than NCD, but I don't know.

[Archangel]

Henric, never the less, not as quick as 8 rotates and 8 jump on carry in-line. Worst case, with no bits set in the target thats only 16 cycles.

rscor01, I didn't realize LOOKUP would do that. How would that go?

George

lookdown2 index, >= [%00000000,%00000001,%00000010],temp

[rsocor01]

lookdown2 index, >= [%00000000,%00000001,%00000010],temp

Nice! Very clever indeed . I have never used this command before, but now I can see it's potential.

[Tabsoft]

I may be wrong but I don't think this will work.
LOOKDOWN2 Search,{Test}[Value{,Value...}],Var

Lookdown2 compares the value of "Search" with the values in the list from left to right (index values 0 up to 255) with the "Test" comparison.

So if "Search" = 5 and "Test" = "=>" then using your values for the Value in the list, the logic tests should look like this.
(Values: 0, 1, 2, 4, 8, 16, 32, 64, 128) bits 0-7
Test 1: is 5 => 0? : Yes, (0 will be stored in Var)
The testing would stop right here for every value of "Search" (0-255) for bytes (0-65535) for words because the "Search" value will always be greater than or equal 0 (unless you're using Long variables)

Maybe I'm wrong?

As I see it, to use Lookdown2 you would still need to enter all the values from 0 to 255 inclusive into the list.
And "Test" would need to be set to "="
Lookdown2 supports up to 85 values in the list or up to 256 when using a PIC18.

[rsocor01]

I may be wrong but I don't think this will work.
LOOKDOWN2 Search,{Test}[Value{,Value...}],Var

Lookdown2 compares the value of Search with the values in the list from left to right (index values 0 up to 255) with the "Test" comparison.

So if Search = 5 and Test = "=>" then using your values for the Value in the list, the logic tests should look like this.
(Values: 0, 1, 2, 4, 8, 16, 32, 64, 128)
Test 1: is 5 => 0? : Yes, (0 will be stored in Var)
The testing would stop right here for every value of Search (0-255) for bytes (0-65535) for words.

Maybe I'm wrong?

As I see it, to use Lookdown2 you would still need to enter all the values from 0 to 255 inclusive into the list.
And
Lookdown2 supports up to 85 values in the list or up to 256 when using a PIC18.

No, I don't think that you are wrong. I think there is a minor change that needs to be done to Dave's code,

lookdown2 index, <= [%00000000,%00000001,%00000010,%00000100,%00001000,%00010000,%00100000,%01000000,%10000000,255],temp

[Tabsoft]

Thanks for the feedback.

I still think there are issues with this approach.
I ran a test and printed the output.
I ran a For/Next loop from 0 to 255.
e.g.
For i = 0 to 255
Lookdown2 i, <= [%00000000,%00000001,%00000010,%00000100,%00001000, %00010000,%00100000,%01000000,%10000000,%11111111], j
Next i

The output resulted in 247 wrong values out of 256.

I am attaching the output here.

Again, perhaps I'm wrong and missing something?
Lookdown2.pdf

[rsocor01]

Thanks for the feedback.

I still think there are issues with this approach.
I ran a test and printed the output.
I ran a For/Next loop from 0 to 255.
e.g.
For i = 0 to 255
Lookdown2 i, <= [%00000000,%00000001,%00000010,%00000100,%00001000, %00010000,%00100000,%01000000,%10000000,%11111111], j
Next i

The output resulted in 247 wrong values out of 256.

I am attaching the output here.

Again, perhaps I'm wrong and missing something?
Attachment 7724

Yes, you are right. We should always use truth tables just to make sure it is correct. We were just giving Matias a general idea. Try this now,

For i = 0 to 255
Lookdown2 i, <= [%00000000,%00000001,%00000011,%00000111,%00001111, %00011111,%00111111,%01111111,%11111111], j
Next i

[Tabsoft]

Thanks. That works great.

To find the port pin state using this, you would just need to decrement the return value by 1 if the value is >0 ( same for NCD).

When I get some time I will run this against NCD and check the instruction cycles to see which is quicker.

Thanks again.

[towlerg]

Not wishing to be rude, but how can 255 iterations be quicker than NCD or the in-line assembler equivalent?

George

[rsocor01]

Not wishing to be rude, but how can 255 iterations be quicker than NCD or the in-line assembler equivalent?

George

The 255 iterations is just to test the LOOKDOWN2 command line.

[Archangel]

As I see it, . . . . you only need 8 iterations with lookdown and using < or > as it jumps to the first "iteration" that tests as true.

[Tabsoft]

For those who are curios as to the testing results of NCD vs. Lookdown2 in the context of this discussion.
I ran the following code in the MPLAB Simulator.

NCDSUB:
    for i = 0 to 255
	mystatus = i
	''Start MPLAB SIM Stopwatch
    	mybyte = NCD mystatus
    	''Stop MPLAB SIM Stopwatch
	next i
    lcdout $FE,1,"NCD: ", idec mybyte
    pause 500
    
    return
    
LOOKSUB:

    for i = 0 to 255
	mystatus = i
	''Start MPLAB SIM Stopwatch
    	lookdown2 mystatus, <= [%00000000, %00000001, %00000011, %00000111, %00001111, %00011111, %00111111, %01111111, %11111111], mybyte
    	''Stop MPLAB SIM Stopwatch
    next i
        
    lcdout,1, "Lookdown: ", idec mybyte
    pause 500

    return

and here are the results.

[Archangel]

Lookdown2 makes 2x code over lookup, have you tested to confirm? Thanks

[Art]

Best I can think of is 3 assembler instructions, but more time than 3 cycles of course.
Copy the port value to a byte, count how many times you shift the byte right until the byte is zero.

If those times are for a single value,
I think it would be better than either example to check each bit in a verbose fashion still in the compiler.

bytevar var byte ‘ buffer byte for port
bitnum var byte ‘ output bit number that was set

bytevar = porta


btfsc		_bytevar		,07
goto labelone
btfsc		_bytevar		,06
goto labeltwo
btfsc		_bytevar		,05

......

[Art]

Or rotate left until carry is set:

bitcount var byte
bytebuff var byte

NCD8:
bytebuff = portX
clrf	_bitcount
bcf	status	,C
findbit:
incf	_bitcount
rrf	_bytebuff
btfss	status	,C
goto findbit
return

It’s been a while for asm, and might not work straight up, but enough to get the idea.
findbit: is currently an endless loop if the port is zero, so you’d need to check for zero at the beginning.

[Art]

Ok,
In the listing he’s rotating left. I would think that would result in quicker times for the lower values.
I’m pretty sure there’s an error in my asm, as the example uses a different instruction to rotate with carry.
This is the same thing in BASIC but rotating right so the higher values should be found faster.
I’d be interested to enter a race with it.. just not sure some lines are converted the way I’d want them to.

workword var word
workbyte var workword.byte0 ‘ 1st byte
bitcarry var workword.8 ‘ 9th bit
bitcount var byte


NCD8:
bitcount = 8 ‘ mov l to w & w to f
workbyte = portX ‘ mov l to w & w to f

if workbyte = 0 then ‘ portX was zero
goto whatawaste
endif

inloop:
bitcount = bitcount - 1 ‘ decf
workword = workword << 1 ‘ 2 x rrf with carry

if bitcarry = 0 then ‘ btfss
goto inloop ‘ goto
endif
return

whatawaste:
bitcount = 0 ‘ bsf
return

[Tabsoft]

Short of resorting to inline ASM and potentially having to deal with bank issues, etc., I put together the suggestions here on this thread and ran the execution tests.
I captured the results in the table below.



Here is the code that I used to test with.

'****************************************************************
'*  Name    : NCDTest.pbp                                       *
'*  Author  : TABSoft                                           *
'*  Notice  : Copyright (c) 2015 TABSoft                        *
'*          : All Rights Reserved                               *
'*  Date    : 3/3/2015                                          *
'*  Version : 1.0                                               *
'*  Notes   :                                                   *
'*          :                                                   *
'****************************************************************

'*****PIC MCU Configuration Fuses (MPASM)*****
#IF __PROCESSOR__ = "18F4620"
    #CONFIG
        CONFIG OSC = ECIO6            ; EC oscillator, port function on RA6
        ;CONFIG OSC = INTIO67	      ; Internal oscillator block, port function on RA6 and RA7
        ;CONFIG  WDT = OFF             ; WDT disabled (control is placed on the SWDTEN bit)
        CONFIG  FCMEN = OFF           ; Fail-Safe Clock Monitor disabled
        CONFIG  IESO = OFF            ; Oscillator Switchover mode disabled
        CONFIG  PWRT = OFF            ; PWRT disabled
        CONFIG  BOREN = SBORDIS       ; Brown-out Reset enabled in hardware only (SBOREN is disabled)
        CONFIG  BORV = 3              ; Minimum setting
        CONFIG  WDT = ON              ; WDT enabled
        CONFIG  WDTPS = 512           ; 1:512
        CONFIG  CCP2MX = PORTC        ; CCP2 input/output is multiplexed with RC1
        CONFIG  PBADEN = OFF          ; PORTB<4:0> pins are configured as digital I/O on Reset
        CONFIG  LPT1OSC = OFF         ; Timer1 configured for higher power operation
        CONFIG  MCLRE = ON            ; MCLR pin enabled; RE3 input pin disabled
        CONFIG  STVREN = ON           ; Stack full/underflow will cause Reset
        CONFIG  LVP = OFF             ; Single-Supply ICSP disabled
        CONFIG  XINST = OFF           ; Instruction set extension and Indexed Addressing mode disabled (Legacy mode)
        CONFIG  DEBUG = OFF           ; Background debugger disabled, RB6 and RB7 configured as general purpose I/O pins
        CONFIG  CP0 = OFF             ; Block 0 (000800-003FFFh) not code-protected
        CONFIG  CP1 = OFF             ; Block 1 (004000-007FFFh) not code-protected
        CONFIG  CP2 = OFF             ; Block 2 (008000-00BFFFh) not code-protected
        CONFIG  CP3 = OFF             ; Block 3 (00C000-00FFFFh) not code-protected
        CONFIG  CPB = OFF             ; Boot block (000000-0007FFh) not code-protected
        CONFIG  CPD = OFF             ; Data EEPROM not code-protected
        CONFIG  WRT0 = OFF            ; Block 0 (000800-003FFFh) not write-protected
        CONFIG  WRT1 = OFF            ; Block 1 (004000-007FFFh) not write-protected
        CONFIG  WRT2 = OFF            ; Block 2 (008000-00BFFFh) not write-protected
        CONFIG  WRT3 = OFF            ; Block 3 (00C000-00FFFFh) not write-protected
        CONFIG  WRTC = OFF            ; Configuration registers (300000-3000FFh) not write-protected
        CONFIG  WRTB = OFF            ; Boot Block (000000-0007FFh) not write-protected
        CONFIG  WRTD = OFF            ; Data EEPROM not write-protected
        CONFIG  EBTR0 = OFF           ; Block 0 (000800-003FFFh) not protected from table reads executed in other blocks
        CONFIG  EBTR1 = OFF           ; Block 1 (004000-007FFFh) not protected from table reads executed in other blocks
        CONFIG  EBTR2 = OFF           ; Block 2 (008000-00BFFFh) not protected from table reads executed in other blocks
        CONFIG  EBTR3 = OFF           ; Block 3 (00C000-00FFFFh) not protected from table reads executed in other blocks
        CONFIG  EBTRB = OFF           ; Boot Block (000000-0007FFh) not protected from table reads executed in other blocks

    #ENDCONFIG
#else
    #ERROR "This program requires a PIC 18F4620 MCU"
#endif

OSCCON = $60  ' Set PIC to 4Mhz & ECIO Clock Mode

 DEFINE OSC 4
 ADCON0.0 = 0  ' A/D Converter module is disabled   
   ADCON1 = $0F  ' %0000 1111 AN2=VSS, AN3=VDD, AN12-0 = Digital 
   ADCON2 = $00  ' %0000 0000
    TRISB = %11111111 ' Set PORTB as input
INTCON2.7 = 0 ' Enable PORTB pullups
    TRISC = TRISC & %11011111   ' Set PORTC pin directions (pin5 output to RTC VCC2)

i var byte
mybyte var byte
mystatus var byte
workword var word
workbyte var workword.byte0 ' 1st byte
bitcarry var workword.8 ' 9th bit
bitcount var byte
bytArray var byte[9]

bytArray[0] = 0
bytArray[1] = 1
bytArray[2] = 2
bytArray[3] = 4
bytArray[4] = 8
bytArray[5] = 16
bytArray[6] = 32
bytArray[7] = 64
bytArray[8] = 128

'*****Define LCD registers and bits*****
define LCD_BITS      4  
define LCD_LINES     2  ' Set to number of lines for the LCD
Define LCD_DREG      PORTD
Define LCD_DBIT      4  
Define LCD_RSREG     PORTE
Define LCD_RSBIT     0
Define LCD_EREG      PORTE
Define LCD_EBIT      1
define LCD_RWREG     PORTE
define LCD_RWBIT     2
define LCD_COMMANDUS 1500
define LCD_DATAUS    44


'*****Initialize LCD*****
   Low LATE.2  		    ' LCD R/W line low (W)
   Pause 500       	  ' Wait .5 second for LCD to Initialize




mainloop:
    do
        for i = 0 to 8
			workword.byte1 = 0
			workbyte = bytArray[i]		
			gosub NCD8
		next i
        for i = 0 to 8
			workword.byte1 = 0
			workbyte = bytArray[i]		
			gosub NEWNCD8
		next i
        for i = 0 to 8
			mystatus = bytArray[i]		
			gosub checkbit8
		next i
        for i = 0 to 8
			mystatus = bytArray[i]		
			gosub checkbit8ztest
		next i
		for i = 0 to 8        
			mystatus = bytArray[i]
			gosub NCDSUB
        next i
		for i = 0 to 8
			mystatus = bytArray[i]
			gosub LOOKSUB
        next i
		pause 500
            
    loop


NCD8:
' Input: workword (including workbyte)
'Return: bitcount
'Locals: bitcarry
' Notes: If workbyte = 0 then bitcount is set to 0
'       otherwise bitcount = bitnumber (0-7)

    bitcount = 8 ' mov l to w & w to f

    if workbyte = 0 then ' portX was zero
        bitcount = 0
        return
    endif

inloop:
    bitcount = bitcount - 1 ' decf
    workword = workword << 1 ' 2 x rrf with carry
    
    if bitcarry = 0 then 'btfss
        goto inloop ' goto
    endif
	
return

NEWNCD8:
' Input: workword (including workbyte)
'Return: bitcount
'Locals: bitcarry
' Notes: If workbyte = 0 then bitcount is set to 0
'        otherwise bitcount = bitnumber (0-7)

	if workbyte = 0 then 'portX was zero
		bitcount = 0
		return
	endif
	
	bitcount = 8	

	do
		bitcount = bitcount - 1
		workword = workword << 1
	loop while bitcarry = 0

	return
			

checkbit8:
' Input: mystatus
'Return: bitcount
'Locals: none (direct bittest of mystatus
' Notes: If mystatus = 0 then bitcount is not changed
'        otherwise bitcount = bitnumber (0-7) (can be changed to any byte value)
	   
       if mystatus.7 = 1 then
	       bitcount = 7
	       return
       endif
	   if mystatus.6 = 1 then
	       bitcount = 6
	       return
       endif
	   if mystatus.5 = 1 then
	       bitcount = 5
	       return
       endif
	   if mystatus.4 = 1 then
	       bitcount = 4
	       return
       endif
	   if mystatus.3 = 1 then
	       bitcount = 3
	       return
       endif
	   if mystatus.2 = 1 then
	       bitcount = 2
	       return
       endif
	   if mystatus.1 = 1 then
	       bitcount = 1
	       return
       endif
	   if mystatus.0 = 1 then
	       bitcount = 0
	       return
       endif
	
	   return

checkbit8ztest:
' Input: mystatus
'Return: bitcount
'Locals: none (direct bittest of mystatus)
' Notes: If mystatus = 0 then bitcount is not changed (can be changed to any byte value)
'       otherwise bitcount = bitnumber (0-7) (can be changed to any byte value)
	   
       if mystatus = 0 then
			return
       endif			   
       if mystatus.7 = 1 then
	       bitcount = 7
	       return
       endif
	   if mystatus.6 = 1 then
	       bitcount = 6
	       return
       endif
	   if mystatus.5 = 1 then
	       bitcount = 5
	       return
       endif
	   if mystatus.4 = 1 then
	       bitcount = 4
	       return
       endif
	   if mystatus.3 = 1 then
	       bitcount = 3
	       return
       endif
	   if mystatus.2 = 1 then
	       bitcount = 2
	       return
       endif
	   if mystatus.1 = 1 then
	       bitcount = 1
	       return
       endif
	   if mystatus.0 = 1 then
	       bitcount = 0
	       return
       endif
	
	   return


NCDSUB:
' Input: mystatus
'Return: mybyte
'Locals: none (direct bittest of mystatus)
' Notes: If mystatus = 0 then mybyte is not changed
'        otherwise mybyte = bitnumber (1-8) 

    mybyte = NCD mystatus
	
    return
    
LOOKSUB:
' Input: mystatus
'Return: mybyte
'Locals: none (direct bittest of mystatus)
' Notes: If mystatus = 0 then mybyte set to 0
'        otherwise mybyte = bitnumber (1-8) 

    lookdown2 mystatus, <= [%00000000, %00000001, %00000011, %00000111, %00001111, %00011111, %00111111, %01111111, %11111111], mybyte
    
    return

end

[Art]

Lol well I’m not the only one up late & can’t sleep

Still I’m sure rsocor01’s original snippet would beat them all,
and the NCD command could be used to generate all the lookup table,
just that it’s going to be impractical to use a 255/256 byte table for every purpose.

LOOKUP MyPort, [0,1,2,2,3,3,3,3,4,........], MyVar

[Tabsoft]

You're right Art, the LOOKUP method is quicker, but not by much versus the direct bit test method (checkbit8).
The real difference is that LOOKUP is a constant 27 instruction cycles since it is just a table lookup.
The downside as you and others state is the storage space of the table of 256 entries.
When you compile with the 256 entry LOOKUP table it consumes 556 codewords (973 bytes) of code space which is probably not worth the minor reduction in execution time.

The direct bit test (checkbit8 routine) does have variability in the performance based upon the input value (0-255) but if you look at the Max/Min execution time it is
(Max: 37 Min:10 Avg: 25) instruction cycles.

So comparing the two, worst case is that checkbit8 would be 10 inst cycles slower and best case is that checkbit8 would be 17 inst cycles faster and on average across the full (0-255) range checkbit8 is 2 inst cycles faster.
And checkbit8 only adds 116 codewords (203 bytes).

For these reasons my choice would be checkbit8 over the other options, except maybe pure ASM for those who are inclined.