Game: optimised machine code

[yzoer]

Been ages since I've been here but the very first thing I read was this post from Seghur. Couldn't let this challenge go, now could I? :-)

I'll cheat a bit by assuming 'a' is either 0x00000000 or 0xffffffff...

; r0 = a
; r1 = b
; r2 = c

and r1,r1,r0
andnot r2,r0
or r0,r1,r2

The way it works is that if 'a' is 0, b will become zero, as b&0 = 0. Likewise, 'c' will then become c&0xffffffff which will become 'c'. The final result is than 0|c which is this case is 'c'. If a is NOT zero, b will become b&0xffffffff and c will become c&0, in which case you'll get c. Results get written back into r0.

Yvo

[segher]

Hi Yvo,

Cheating is of course allowed, if you can get away with it
that is!

If you know that a is -1 if it isn't 0 (like in your case), you
need only _two_ instructions. Same with 1 instead of -1,
which is how you can do the a1==a2 case.

Another question is how can you transform zero/non-zero
into 0/-1? It can be done in two insns, can it be done in
one? (I don't know the answer).

[richard]

Another question is how can you transform zero/non-zero
into 0/-1? It can be done in two insns, can it be done in
one? (I don't know the answer).

I can't beat two instructions

Code: Select all

eq r1, r0, 0
sext r1, 1

Code: Select all

eq r1, r0, 0
neg r1, r1

I suspect it isn't possible to do it in one instruction. Without using eq, bt or bf, the shortest instruction sequence I can come up with is 4 instructions long (can this be improved?):

Code: Select all

// r0 is zero iff it is not negative and it is not strictly positive.
ashr r1, r0, 32
neg r2, r0
ashr r2, r2, 32
or r1, r2, r1

If you know that a is -1 if it isn't 0 (like in your case), you
need only _two_ instructions. Same with 1 instead of -1,
which is how you can do the a1==a2 case.

I can see how to use compute the result in 2 additional instructions for the -1 / 0 case, e.g.

Code: Select all

eq tmp1, a1, a2
neg tmp1, tmp1
sub tmp2, b, c
lmul tmp3, d, tmp1, tmp2, c, tmp2

This computes (b - c) + c + (b - c) * ((a1 == a2) ? -1 : 0) which simplifies to (a1 == a2) ? b : c. However I can't see how to do it in two instructions in the 1 / 0 case. Any clues?

[segher]

Another question is how can you transform zero/non-zero
into 0/-1? It can be done in two insns, can it be done in
one? (I don't know the answer).

I can't beat two instructions

Code: Select all

eq r1, r0, 0
sext r1, 1

Code: Select all

eq r1, r0, 0
neg r1, r1

That transforms zero/non-zero to -1/0, not 0/-1. Not that
this matters for the case at hand. You can do

Code: Select all

eq r1,r0,0
sub r1,r1,1

Without using eq, bt or bf, the shortest instruction sequence I can come up with is 4 instructions long (can this be improved?):

Code: Select all

// r0 is zero iff it is not negative and it is not strictly positive.
ashr r1, r0, 32
neg r2, r0
ashr r2, r2, 32
or r1, r2, r1

You can use clz to get three.

If you know that a is -1 if it isn't 0 (like in your case), you
need only _two_ instructions. Same with 1 instead of -1,
which is how you can do the a1==a2 case.

I can see how to use compute the result in 2 additional instructions for the -1 / 0 case, e.g.

Code: Select all

eq tmp1, a1, a2
neg tmp1, tmp1
sub tmp2, b, c
lmul tmp3, d, tmp1, tmp2, c, tmp2

I can't see how to do it in two instructions in the 1 / 0 case however. Any clues?

[/quote]
Cheat a bit: use one of the input regs as output reg. The
problem with lmul is that it has two input addends, as you
noticed :-)

[richard]

Here's my entry for the "Most Evil Code" category. The code computes a ? b : c. On entry a, b, c are expected to be in r0, r1, r2 respectively and at the end the result is stored in r0.

Code: Select all

.align 4
nop
ldap r11, .L666
ldw r3, r11[0]
ldc r4, 0xc
xor r4, r3, r4
bf r0, 0
stw r4, r11[0]
.L666:
mov r0, r1
stw r3, r11[0]

This entry involves self modifying code, but that's not the most evil part. Can you explain how bf instruction affects the result?

[segher]

Cute! It will misbehave if you want to run it a second
time though. Or when an interrupt happens at the right
(wrong?) spot, but there isn't much you can do about
that I suppose?

[richard]

Cute! It will misbehave if you want to run it a second
time though. Or when an interrupt happens at the right
(wrong?) spot, but there isn't much you can do about
that I suppose?

It should work when called for a second time - the code is restored to its original unmodified state by the second stw instruction. Interrupts are a problem - there is a two instruction window (starting at the first stw instruction) where an taking an interrupt would result in the code always returning c regardless of the value of a. You could disable / enable interrupts around this part of the code, but you might still get a debug interrupt.

[segher]

Oh I totally missed that second store :-)

Do you want to make the next challenge? My stash of
neat little tricks is limited...

[yzoer]

Middle of the night here but this just hit me: You can do it in one instruction (okay, two if you count the eq ), if you assume b and c are stored consecutively in memory with r2 as the base address and a is stored in r0. ( lots of cheating, I know )

eq r0, r0, #0 ; either 0 or 1
ldw r0,r2[r0]

Since the index register gets scaled automatically, this will load either b or c back into r0.

night all!

Yvo

[segher]

Nice one :-)