Shop OBEX P1 Docs P2 Docs Learn Events
Endian Puzzle — Parallax Forums

Endian Puzzle

rokickirokicki Posts: 1,000
edited 2013-04-25 18:09 in Propeller 1
Okay, here's a cute puzzle for all you propellerheads.

The Propeller stores data in its main memory in little-endian format.
Turns out for one application I need to do a byte swizzle operation,
that converts a 32-bit little-endian word to a 32-bit big-endian word.
(That is, I want the bits in the bytes to stay in the same order, but the
bytes in the word to be reversed; so $deafc089 would become
$89c0afde.)

What is the fewest number of assembly instructions that suffice?
Assume input and output can be in registers (the same or
different, your choice) and you can use as many other registers
as you need.

I want fewest instructions executed, not fewest instructions of
code.

I've got what I think is a good solution, but I'm not going to spoil
it by presenting the answer here. My instruction count is at
http://tomas.rokicki.com/proppuzzle.txt (but my solution is not
there). See what you can come up with.

Another interesting puzzle is what is the worst case bit-swizzle
in terms of required instructions.

If no one answers this post, I'll just patent the code.

Post Edited (rokicki) : 11/20/2006 11:48:07 PM GMT

Comments

  • Phil Pilgrim (PhiPi)Phil Pilgrim (PhiPi) Posts: 23,514
    edited 2006-11-21 00:20
    rokiki,

    I've PMed you with an answer that matches your instruction count. This is a great puzzle, so I didn't want to spoil it by posting my solution publicly.

    -Phil
  • rokickirokicki Posts: 1,000
    edited 2006-11-21 00:36
    Uh, embarrassing mistake here.

    My "solution" didn't work. (I misunderstood some instructions in the Propeller.) Egg on my face.

    Nonetheless, Phil was able to obtain an amazing and short solution that equalled my purported
    length. So the puzzle stands, even if I don't.

    Good going, Phil!
  • Cliff L. BiffleCliff L. Biffle Posts: 206
    edited 2006-11-21 03:26
    rokicki said...
    If no one answers this post, I'll just patent the code.

    I cracked up at this one. smile.gif

    Now, to try my hand at this.
  • Beau SchwabeBeau Schwabe Posts: 6,566
    edited 2006-11-21 04:02
    rokicki,

    You ruined my dinner...smilewinkgrin.gif... I was too busy trying to figure out something clever.

    I figured out how to do it in 6, and then I "thought" I figured out a way to do it in 4 using movi,ror,shl, and a tjnz·and then my head blew up.


    ▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
    Beau Schwabe

    IC Layout Engineer
    Parallax, Inc.
  • Cliff L. BiffleCliff L. Biffle Posts: 206
    edited 2006-11-21 04:15
    Beau Schwabe said...
    I "thought" I figured out a way to do it in 4 using movi,ror,shl, and a tjnz and then my head blew up.

    Yeah, I'm at the same place. I really feel like I oughtta be able to do this cleverly, but it's gonna wind up being a space-for-time tradeoff.

    Tom's got my solution in PM, but I'm sure Phil has totally owned me at this. smile.gif
  • cgraceycgracey Posts: 14,155
    edited 2006-11-21 05:00
    I did it in six instruction cycles with a total of 7 longs. I emailed rokicki my solution.


    ▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔


    Chip Gracey
    Parallax, Inc.
  • cgraceycgracey Posts: 14,155
    edited 2006-11-21 05:03
    rokicki said...


    Another interesting puzzle is what is the worst case bit-swizzle
    in terms of required instructions.
    Well, this would do it:

    ··· REV··· reg,#0··· 'reverse the order of all 32 bits

    ▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔


    Chip Gracey
    Parallax, Inc.
  • Phil Pilgrim (PhiPi)Phil Pilgrim (PhiPi) Posts: 23,514
    edited 2006-11-21 05:24
    Congrats, Chip!

    I had six instructions in eight longs. But upon seeing Chip's claim, and reexamining my code, I realized the second extra long isn't necessary. Rokiki has my new solution.

    -Phil

    Update: Actually, my seven doesn't include source and result registers. Chip, were you counting those in your six?

    Post Edited (Phil Pilgrim (PhiPi)) : 11/21/2006 5:28:13 AM GMT
  • cgraceycgracey Posts: 14,155
    edited 2006-11-21 05:27
    Did this have anything to do with using and ANDN instruction?
    Phil Pilgrim (PhiPi) said...
    Congrats, Chip!

    I had six instructions in eight longs. But upon seeing Chip's claim, and reexamining my code, I realized the second extra long isn't necessary. Rokiki has my new solution.

    -Phil

    Update: Actually, my seven doesn't include source and result registers. Chip, were you counting those in your six?

    Well, I had six instructions which used two working registers: the in/out register and a temporary. There was 1 extra long for a constant, making the program effectively 7 longs, though only six instructions execute.

    ▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔


    Chip Gracey
    Parallax, Inc.

    Post Edited (Chip Gracey (Parallax)) : 11/21/2006 5:31:59 AM GMT
  • Phil Pilgrim (PhiPi)Phil Pilgrim (PhiPi) Posts: 23,514
    edited 2006-11-21 05:30
    Chip,

    No, I didn't use ANDN. But it would've worked just as well in place of what I did use.

    -Phil
  • ciw1973ciw1973 Posts: 64
    edited 2006-11-21 09:08
    Yup, can't see how to do it in less than 6 instructions, so I'm glad to see that noone else has managed it either.
  • Phil Pilgrim (PhiPi)Phil Pilgrim (PhiPi) Posts: 23,514
    edited 2006-11-21 10:08
    Chip Gracey said...
    Well, I had six instructions which used two working registers: the in/out register and a temporary. There was 1 extra long for a constant, making the program effectively 7 longs, though only six instructions execute.

    Ya know, the rules didn't specify that the code had to work more than once. You could even eliminate that temporary register! smile.gif

    -Phil
  • Ym2413aYm2413a Posts: 630
    edited 2006-11-21 14:51
    Wow you guys really get into these little problems.
    I would submit my verson of the code to do it. But I'm sure you guys got me beat. lol.gif
  • rokickirokicki Posts: 1,000
    edited 2006-11-21 18:22
    Wow, that was fun!

    This posting has solutions below, so stop reading
    here if you want to keep working on it.

    My original solution was: 
    rev a,#8
rev a,#24
rev a,#8
ror a,#8
rev a,#8
ror a,#16
    but then I realized: rev zeros the
    high bits, rather than preserving them.
    Ouch.

    Phil was the first to give a correct
    six-instruction solution: 
    LTL BIG
mov big,ltl
and big,_0xf0f0
and ltl,_0x0f0f
rol big,#8
ror ltl,#8
or big,ltl
    I never thought of rotating 'around'!

    Cliff posted a similar, but different, solution,
    that cut the number of required constants: 
    swap vallong0
swap tmplong0
swap movswaptmp,swapval
ror swapval,#8
and swapval,mask
and swaptmp,mask
ror swaptmp,#8
or swapval,swaptmp
swap_retret
mask long $00FF00FF
    And then I heard from Chip himself, with this
    solution with an elegant use of andn: 
    mov y,x 'x=$01234567
rol x,#8
ror y,#8
and x,h00FF00FF
andn y,h00FF00FF
or x,y'x=$67452301
<done>
h00FF00FF long $00FF00FF
    Phil then figured out how to duplicate Cliff's and
    Chip's accomplishment, but in a totally unexpected
    way: 
    mov big,ltl
and big,_0xf0f0
xor ltl,big
rol big,#8
ror ltl,#8
or big,ltl
    Wow, it's amazing what you can do with these
    instructions!
  • Phil Pilgrim (PhiPi)Phil Pilgrim (PhiPi) Posts: 23,514
    edited 2006-11-21 18:46
    Please note that my constant named "_0xf0f0" is defined with a value of $FF00FF00. blush.gif

    -Phil
  • kuronekokuroneko Posts: 3,623
    edited 2010-09-09 04:35
    There is in fact a 5 insn solution. It's doing the work of 6 insn but the last one is for free. Value starts in phsx and ends there.
    ' incomplete teaser

        ror     phsa, #8
        mov     frqa, phsa
        and     frqa, mask
        sub     phsa, frqa
        ror     frqa, #16
                
mask    long    $00FF00FF
  • BeanBean Posts: 8,129
    edited 2010-09-09 04:45
    Rokicki,
    I fixed the tags in your post.
    I hope that is okay.

    Bean
  • KaosKiddKaosKidd Posts: 296
    edited 2010-09-09 06:19
    OK, once again I am humbled by the minds here!
    :)
    This is amazing stuff everyone!

    KK
  • Cluso99Cluso99 Posts: 18,069
    edited 2013-04-25 18:09
    Here is a new thread that asked the same question, and continued the discussion
    http://forums.parallax.com/showthread.php/147580-Any-shorter-way-to-reverse-bytes-in-long-using-only-1-extra-long-(in-pasm)?p=1179932#post1179932
Sign In or Register to comment.