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

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

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

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

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

What PIC device?

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

Quote:

Originally Posted by towlerg

What PIC device?

It´s a PIC18F45K80

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

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

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

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

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

Except he wants the fastest not the easiest.

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

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

Code:

;**************************************************************** ;* 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.

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

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

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

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

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

Quote:

Originally Posted by towlerg

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

Code:

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

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

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

Quote:

Originally Posted by 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

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

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

Quote:

Originally Posted by Archangel

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.

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

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.

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

Quote:

Originally Posted by 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)
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,

Code:

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

1 Attachment(s)

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

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

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

Quote:

Originally Posted by 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?
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,

Code:

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

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

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.

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

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

George

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

Quote:

Originally Posted by towlerg

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.

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

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.

1 Attachment(s)

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

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.

Code:

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.

Attachment 7725

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

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

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

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.

Code:

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

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

Or rotate left until carry is set:

Code:

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.

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

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.

Code:

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

1 Attachment(s)

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

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.

Attachment 7732

Here is the code that I used to test with.

Code:

'**************************************************************** '* 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

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

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.

Code:

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

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

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.