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/showthread.php?t=15086&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 :D. 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?
7724

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

7725

[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.

7732

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 :D

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.