PASM: Faster Search of LONG table?
SRLM
Posts: 5,045
I have an array called data_register with preloaded values in it (ie, loaded in from spin before cog launch). I also have a single variable called um6_address. All values will be less than $90. I need to compare um6_address with each element in data_register, and somehow map that to the coresponding (by index) value in data_address.
I've come up with two versions, one linear and one looped.
I would like a version that can have any number of values (say, perhaps, 32 registers to compare against). The code has to be fast, and less than approximately 40 instructions in execution time. If it's any longer then it messes with the timing sensitive rx/tx code.
Specifically, I currently have O(n) solutions, and I would like something faster.
The only improvement that I can think of is to create an array of $90 registers, and use um6_address to index into it. This has the advantage of taking only a few instructions (~5?), but it takes 144 precious longs in the cog (and hub!).
So, I'm wondering if anybody has another solution that will fit.
Simple solution (constant time, not scalable):
Looping version (non constant time, not scalable):
I'm attaching the code in case it proves useful, but note that it expects an external serial device to be streaming the data.
data_register long 0[16] 'The UM6 register to watch for (note: the max, 16, is hardcoded above...) data_address long 0[16] 'The HUB address to store the received long (4 bytes) to
I've come up with two versions, one linear and one looped.
I would like a version that can have any number of values (say, perhaps, 32 registers to compare against). The code has to be fast, and less than approximately 40 instructions in execution time. If it's any longer then it messes with the timing sensitive rx/tx code.
Specifically, I currently have O(n) solutions, and I would like something faster.
The only improvement that I can think of is to create an array of $90 registers, and use um6_address to index into it. This has the advantage of taking only a few instructions (~5?), but it takes 144 precious longs in the cog (and hub!).
So, I'm wondering if anybody has another solution that will fit.
Simple solution (constant time, not scalable):
cmp um6_address, data_register + 0 wz
if_z wrlong data_bytes_result, data_address + 0
cmp um6_address, data_register + 1 wz
if_z wrlong data_bytes_result, data_address + 1
cmp um6_address, data_register + 2 wz
if_z wrlong data_bytes_result, data_address + 2
cmp um6_address, data_register + 3 wz
if_z wrlong data_bytes_result, data_address + 3
...
Looping version (non constant time, not scalable):
'Test for the various packet types (Fast(?) version)
{ Input:
data_count - number of added registers
data_register[n] - register addresses to watch for
um6_address - received address to search with
Output:
data_offset - index of matching address, $FF if not found
}
movs :state_7_loop, #data_register-1
mov data_offset, data_count 'DEBUG:TO_DO: Make it so that the 8 is changeable...
'Selected 8 because too many instructions here will make it unable to
'receive the bits (it hangs...)
add data_offset, #1
add :state_7_loop, data_offset 'Set the loop index to the last (based on constant in previous instruction) instruction
nop 'Can't modify the next instruction
:state_7_loop cmp um6_address, 0-0 wz 'Test received address and the address in memory. Same?
if_nz sub :state_7_loop, #1 'If different, decrement to next address
if_nz djnz data_offset, #:state_7_loop 'If different, decrement index. If there's still more to check, jump
'Add this point
' data_offset - index+1 of matching address
if_z sub data_offset, #1 'Because counter is +1 from the actual index (so it works with djnz)
if_nz mov data_offset, #$FF '$FF indicates no register match found
I'm attaching the code in case it proves useful, but note that it expects an external serial device to be streaming the data.
Comments
-Phil
You don't even need that, just have the long array in Hub RAM - code is then something like
mov temp, um6_address shl temp, #2 ' convert to byte address offset for hub add temp, hub_array ' address of hub array wrlong data_bytes_result, temp