Any recommendations for transposing arrays?
jrullan
Posts: 168
I'm working on porting an old project to the P2 and it relies on transposing an array of longs (32 bits long integers) into an array of bytes (I know it's odd). See below:
The resulting byte array order could be either as shown or having b00 to be the msb.
I wonder if there are any instructions among the PASM instruction set that facilitates doing this in the least amount of cycles possible.
The resulting byte array order could be either as shown or having b00 to be the msb.
I wonder if there are any instructions among the PASM instruction set that facilitates doing this in the least amount of cycles possible.
Comments
There's RCZR/RCZL that can shift two bits into the status flags at once, I guess.
But, maybe you could send the 8 longs to 8 smartpins and them shift it out while you read the in?
Might require jumpers to 8 other pins...
See post by rogloh below.
pub transpose(p_longs, p_bytes) | lidx, lwork, bidx, bwork org rd_hub setq #8-1 ' read 8 longs from hub rdlong old, p_longs mov lidx, #0 ' long index (0..7) / bit # .loop1 alts lidx, #old ' get long from old table mov lwork, 0-0 mov bidx, #0 ' bit index (0..31) / byte # .loop2 testb lwork, bidx wc ' get lwork.[bidx] into C altgb bidx, #new ' get byte from new table getbyte bwork bitc bwork, lidx ' update altsb bidx, #new ' put it back setbyte bwork incmod bidx, #31 wc ' next bit of current long if_nc jmp #.loop2 incmod lidx, #7 wc ' next long if_nc jmp #.loop1 wr_hub setq #8-1 ' write 8 longs (32 bytes) to hub wrlong new, p_bytes ret old long 0[8] ' treat as 8 longs new long 0[8] ' treat as 32 bytes endApproach:
Read in your 8 longs to obtain source data first to 8 consecutive registers.
Then do 8 x ROLNIBs into an accumulator, followed by a SPLITB then the long is complete.
Repeat this 8 times in total for all data, advancing where you source the nibble from in the ROLNIBs and using different output register accumulators.
Write back the 8 longs of accumulated data as a burst.
An example code snippet is below. If you can't afford them all unrolled in COGRAM space, consider HUB-exec which should be almost as fast because of no branching.
@rogloh,
from the P2ASM spreadsheet I see that the instruction rolnib has this description:
ROLNIB D,{#}S,#N Rotate-left nibble N of S into D. D = {D[27:0], S.NIBBLE[N]).I guess my question is when it refers to S.NIBBLE[N], the index N refers to the index of nibbles within the long, or a nibble starting at bit N?
I can see how the first 9 instructions work, but the second group of instructions doesn't seem to achieve the same result unless N is the bit index within the long instead of the nibble index.
Another approach as suggested by @Wuerfel_21, and I think is also @JonnyMac's approach could be to use the testb/bitc instructions:
These would take 32 clocks per D byte, unrolled it would take 1024 clocks for the 8 longs to be transposed.
[TypoEdit]ROLNIB does take nibble #N from the source (not bit #N). What is the pattern that you wish to follow after the first 8 bits?
I have assumed you are translating more bits from the original 8x32 bit longs to generate output data in this sequence:
then then etc
If that is not the pattern you were after, what is the rest of the output byte pattern after the first byte? Your original post does not show all the details.
In @rogloh's approach the 9 instructions produce four bytes of output at a time which is why only 8 sequences of 9 instructions are needed.
The code is already unrolled, taking 76 longs for the code and a further 18 longs of working memory. Ignoring transfers to and from hubram it takes 72 instructions (144 clocks) to transpose the array of bits.
@rogloh and @AJL ,
Yes that's exactly what I'm looking for!!!
I think that what I'm struggling with is understanding how splitb works. I could follow the description up to the first 8 bits:
SPLITB D - Split every 4th bit of D into bytes. D = {D[31], D[27], D[23], D[19], ...D[12], D[8], D[4], D[0]}.Do you know if this is documented better in another place?
In any case this definitely looks like the best approach!
Wow! Thank you for your time and kindness. I definitely need to test this directly on the P2.
http://forums.parallax.com/discussion/comment/1479691/#Comment_1479691
Wow! I am a visual person myself, that definitely helps!!! Thank you again @rogloh. Can't wait to see the final Propeller 2 manual.
An idea for a future P2+ or P3: ALTGN applies to multiple consecutive GETNIB/ROLNIB instructions if D[31]=1. Similarly for other ALTSx & ALTGx. The eight ROR instructions above could be replaced by one ALTGN and one nibble increment.
What was SEUSSF supposed to be for? That's a strange looking one...
pub obfuscate(value, i) : result org mov result, value rep #1, i ' valid range is 1..31 seussf result end pub recover(value, i) : result org mov result, value neg i, i add i, #32 rep #1, i seussf result endYou are right @Rayman, it is genius.
Thank you all for your input. Here I am attaching an example for testing it out. Might be useful to someone out there.
{ Long-to-byte Transposition Example Test Code First of all the recognitions: http://forums.parallax.com/discussion/172489/any-recommendations-for-transposing-arrays @rogloh, @jonnymac, @Wuerfel_21, @Rayman, @TonyB_, @AJL } CON DELAY = 125 VAR long leds long number long src[8] byte dest[32] byte i PUB public_method_name() src[0] := %00010000_00000000_01000000_00000001 src[1] := %00101000_00000000_10100000_00000010 src[2] := %01000100_00000001_00010000_00000100 src[3] := %10000010_00000010_00001000_00001000 src[4] := %00000001_00000100_00000100_00010000 src[5] := %00000000_10001000_00000010_00100000 src[6] := %00000000_01010000_00000001_01000000 src[7] := %00000000_00100000_00000000_10000000 leds := 0 addpins 7 dira.[leds]~~ transpose(@src,@dest) repeat repeat i FROM 0 TO 31 on(dest[i]) waitms(DELAY) off() waitms(DELAY) PRI on(cnt) ORG MOV OUTA,cnt END PRI off() ORG MOV OUTA,#0 END PRI transpose(srcAddress,destAddress) ORG SETQ #8-1 RDLONG s_array,srcAddress ROLNIB d_array+0, s_array+7, #0 ROLNIB d_array+0, s_array+6, #0 ROLNIB d_array+0, s_array+5, #0 ROLNIB d_array+0, s_array+4, #0 ROLNIB d_array+0, s_array+3, #0 ROLNIB d_array+0, s_array+2, #0 ROLNIB d_array+0, s_array+1, #0 ROLNIB d_array+0, s_array+0, #0 SPLITB d_array+0 ROLNIB d_array+1, s_array+7, #1 ROLNIB d_array+1, s_array+6, #1 ROLNIB d_array+1, s_array+5, #1 ROLNIB d_array+1, s_array+4, #1 ROLNIB d_array+1, s_array+3, #1 ROLNIB d_array+1, s_array+2, #1 ROLNIB d_array+1, s_array+1, #1 ROLNIB d_array+1, s_array+0, #1 SPLITB d_array+1 ROLNIB d_array+2, s_array+7, #2 ROLNIB d_array+2, s_array+6, #2 ROLNIB d_array+2, s_array+5, #2 ROLNIB d_array+2, s_array+4, #2 ROLNIB d_array+2, s_array+3, #2 ROLNIB d_array+2, s_array+2, #2 ROLNIB d_array+2, s_array+1, #2 ROLNIB d_array+2, s_array+0, #2 SPLITB d_array+2 ROLNIB d_array+3, s_array+7, #3 ROLNIB d_array+3, s_array+6, #3 ROLNIB d_array+3, s_array+5, #3 ROLNIB d_array+3, s_array+4, #3 ROLNIB d_array+3, s_array+3, #3 ROLNIB d_array+3, s_array+2, #3 ROLNIB d_array+3, s_array+1, #3 ROLNIB d_array+3, s_array+0, #3 SPLITB d_array+3 ROLNIB d_array+4, s_array+7, #4 ROLNIB d_array+4, s_array+6, #4 ROLNIB d_array+4, s_array+5, #4 ROLNIB d_array+4, s_array+4, #4 ROLNIB d_array+4, s_array+3, #4 ROLNIB d_array+4, s_array+2, #4 ROLNIB d_array+4, s_array+1, #4 ROLNIB d_array+4, s_array+0, #4 SPLITB d_array+4 ROLNIB d_array+5, s_array+7, #5 ROLNIB d_array+5, s_array+6, #5 ROLNIB d_array+5, s_array+5, #5 ROLNIB d_array+5, s_array+4, #5 ROLNIB d_array+5, s_array+3, #5 ROLNIB d_array+5, s_array+2, #5 ROLNIB d_array+5, s_array+1, #5 ROLNIB d_array+5, s_array+0, #5 SPLITB d_array+5 ROLNIB d_array+6, s_array+7, #6 ROLNIB d_array+6, s_array+6, #6 ROLNIB d_array+6, s_array+5, #6 ROLNIB d_array+6, s_array+4, #6 ROLNIB d_array+6, s_array+3, #6 ROLNIB d_array+6, s_array+2, #6 ROLNIB d_array+6, s_array+1, #6 ROLNIB d_array+6, s_array+0, #6 SPLITB d_array+6 ROLNIB d_array+7, s_array+7, #7 ROLNIB d_array+7, s_array+6, #7 ROLNIB d_array+7, s_array+5, #7 ROLNIB d_array+7, s_array+4, #7 ROLNIB d_array+7, s_array+3, #7 ROLNIB d_array+7, s_array+2, #7 ROLNIB d_array+7, s_array+1, #7 ROLNIB d_array+7, s_array+0, #7 SPLITB d_array+7 SETQ #8-1 WRLONG d_array,destAddress d_array long 0[8] s_array long 0[8] ENDOh, ok. Thanks. Will test it later tonight.
When the SEUSSF/SEUSSR subject was mentionned during yesterday's meeting, I'd tried to link the following 2015' thread into the live chat session, but then my entire place went dark-mode, due to a sudden city-wide power outage, and I lost my connection, during ~30 minutes or so.
On return, I forgot to repeat the post. Corrected now...
[url=" https://forums.parallax.com/discussion/162238/what-are-your-expectations-regarding-seussf-and-seussr"] https://forums.parallax.com/discussion/162238/what-are-your-expectations-regarding-seussf-and-seussr[/url]
We certainly owe Chip, Seairth and Heater a good use-case for those two instructions.