ansaurus

Question

ARM assembly puzzle

Answer 1

A:

Something like:

mov r0,r1,lsr #31

dwelch 2010-06-02 20:30:39

That will set r0 to 1 as long as r1 has its high bit set. That's not what the OP is asking for.

Michael Madsen 2010-06-02 20:38:41

ahh, I see I was looking at the bit not the value

dwelch 2010-06-03 03:41:09

Answer 2

+3 A:

Here's a partial solution that gives the correct answer in the top bit of r0, so it is available as a shifter operand (r0 lsr #31).

; r0 = r1 & -r1
rsb r0, r1, #0
and r0, r0, r1

This works because 0 and 0x80000000 are the only numbers that retain their sign bits when negated. I'm fairly sure an exact solution is impossible.

EDIT: no, it's not impossible. See Martin's answer.

Mike Seymour 2010-06-04 11:52:04

Nice trick with the negation. Unfortunately extracting the highest bit requires the 3rd instruction (or modification of the instruction that uses the result, which's not always possible).

ivant 2010-06-04 18:12:09

I thought about this problem the whole day and I'm sure a two instruction solution is impossible as well.

Nils Pipenbrinck 2010-06-04 19:36:41

Answer 3

+5 A:

something like

SMMUL r0,r1,r1
MOV r0,r0,lsr #30

Martin 2010-06-04 23:42:06

nice answer, SMMUL has four operands, yes? maybe SMMUL r2,r0,r1,r1. I think r0 will end up with 1,2, or 3 though if the msbit of r1 is set.

dwelch 2010-06-05 01:02:37

Arm's doccumentation describes SMMUL as signed top word multiplication, so it's listed as a 3 register opcode. My thinking is: 0x80000000 x 0x80000000. gives 0x40000000 in the top word, so a 30 place shift will bring that bit30 to bit0. (No arm V6 architecture here to test it on)

Martin 2010-06-05 07:24:49

@dwelch: you're thinking of SMULL. SMMUL is an ARMv6 instruction that just gives the top 32 bits of the result.

Mike Seymour 2010-06-06 20:55:15

+1 This is correct.

Mike Seymour 2010-06-06 21:24:00

Thanks, good to know. Either way though, the upper two bits of your result can be 1, 2, or 3 depending on the other bits in r1, you still need a third instruction to orr those lower two bits together to get the result.

dwelch 2010-06-08 00:37:48

try a 3, 4, 8, bit multiplier (since a 32x32 will take you a while) and look at what happens to the upper bits of the result for the cases where the msbit of the operand is a 1. Look at 0xF times 0xF = 0xE1, both upper bits are set. 0x8 * 0x8 = 0x40 only one of the upper bits is set.

dwelch 2010-06-08 00:40:06

@dwelch: the largest result you can get from squaring a signed number is (-2^31)^2 = 2^62; any value other than 0x80000000 will give a smaller (and non-negative) result. In your 4-bit example, you're doing an unsigned multiplication; a signed multiplication will interpret 0xF as -1, giving a result of 0x01. So these two instructions do indeed give the correct result, with no need for a third.

Mike Seymour 2010-06-08 11:42:54

@Mike Seymour: That is pretty cool...0x80000000 is the only case where SMMUL takes the same number with the msbit set and the result has the msbit set. SMULL should be able to be used for pre ARMV6 cores so long as you are careful with the operands. SMULL r2,r0,r1,r1 or something like that.

dwelch 2010-06-09 03:29:59

Answer 4

A:

Tough puzzle if one wants to use "fast" instructions. I can't quite come up with a solution, but can offer a couple more 'notions':

; If goal were to have value of zero if $80000000 and something else otherwise:
  adds r0,r1,r1 ; Overflow only if $80000000
  movvc r0,#whatever

; If goal were to have value of $80000000 if $80000000 and zero otherwise
  subs r0,r1,#0  ; Overflow only if $80000000
  movvc r0,#0 ; Or whatever

; If the goal were to have value of $7FFFFFFF if $80000000 and zero otherwise
  adds r0,r1,r1,asr #31 ; Overflow only if $80000000
  movvc r0,#0

; If carry were known to be set beforehand
  addcs r0,r1,r1 ; Overflow only if $80000000 (value is 1)
  movvc r0,#0

; If register r2 were known to hold #1
  adds r0,r1,r1,asr #31
  ; If $80000000, MSB and carry set
  sbc r0,r2,r0,lsr #31

None of those is a perfect solution, but they're interesting.

supercat 2010-06-30 22:56:19

ansaurus

tags:

views:

answers:

ARM assembly puzzle

The problem:

related questions