Is it a valid ARM immediate value?

Question

Exposition

In this challenge, I am talking about ARM assembly language. ARM is a 32-bit RISC processor; I'll use instruction set up to architecture v6.

To load a constant ("immediate") value into a register, use the MOV instruction:

MOV r8, #42

To load negative values, use the MVN instruction, with a bit-complement of the operand:

MVN r8, #41

You can't load any 32-bit value with this instruction. Acceptable values are:

• Any 8-bit value: 0...255
• Any 8-bit value, rotated right by an even number of bits, 2...30
• A bit-complement of any value as described above (a good assembler will accept such operands and turn MOV into MVN)

Challenge

Make code which determines if the given input is a valid operand for a MOV instruction.

Input

A number in the range 0...2³²-1 or -2³¹...2³¹-1, whatever is easier.

If you represent the number as a string, use decimal notation.

Output

True or false, as usual.

Examples

(some of them taken from this nice site with explanations).

True:

0x000000FF
0xffffd63f
0xFF000000
0b1010101100000000 (8 arbitrary bits, followed by even number of zeros)
0b11110000000000000000000000001111 (11111111 rotated right by 4 bits)

False:

0x000001FE
0xF000F000
0x55550000
0xfffffe01
0b10101011000000000 (8 bits but followed by odd number of zeros)
0b11110000000000000010000000001111 (too many spread-out 1-bits)

Answer 1

Rust, ⁵² 49 bytes

|n|(0..16).any(|i|(n<<33^n<<32^n*2^n)<<i*2>>41<1)

Attempt This Online!

A closure that takes an unsigned 32-bit value of type u64 and returns a bool. -3 thanks to corvus_192.

• A 32-bit value n is acceptable
• \$\Leftrightarrow\$ n has a run of 24 equal bits at an even offset, when viewed cyclically
• \$\Leftrightarrow\$ n | n << 32 has a run of 24 equal bits at an even offset, between 0 and 30 inclusive
• \$\Leftrightarrow\$ (n | n << 32) ^ ((n | n << 32) << 1) has a run of 23 zero bits at an even offset between 0 and 30 inclusive, counting from the high end
• \$\Leftrightarrow\$ n<<33^n<<32^n<<1^n has a run of 23 zero bits at an even offset between 0 and 30 inclusive, counting from the high end
• \$\Leftrightarrow\$ (n<<33^n<<32^n<<1^n)<<i>>41 is zero for some even i between 0 and 30 inclusive

Answer 2

Charcoal, 21 bytes

Ｎθ⊙ 3№×²◧⍘θ 123¹⁶×¹²ι

Attempt This Online! Will accept input in decimal by default, but also hex with 0x prefix and binary with 0b prefix. Outputs a Charcoal boolean, i.e. - for valid, nothing if not. Explanation:

Ｎθ                      First input as a number
    3                   Literal string ` 3`
  ⊙                     Any character satisfies
          θ             Input number
         ⍘              Converted to custom base
            123         Literal string ` 123`
        ◧               (Left) Padded to length
               ¹⁶      Literal integer `16` 
      ×                 Repeated by
       ²                Literal integer `2`
     №                  Contains
                    ι   Current character
                 ×      Repeated by
                  ¹²    Literal integer `12`

Answer 3

Python, 52 bytes

f=lambda n:n>4**32or 0<n%~-4**16>>8<8**8-1and f(n*4)

Attempt This Online!

Returns False for True and True for False.

How?

Uses mod 0xffffffff to get from a linear left shift to a cyclic left shift. Advantages of linear being 1) Python actually has it. 2) easier stopping criterion.

Answer 4

Go, 157 147 bytes

import."math/bits"
func f(n uint32)(r bool){F:=uint32(0xFF)
for k:=2;k<31;k+=2{j:=RotateLeft32(n,k)
if r=j<=F||^j<=F;r{return}}
return n<=F||^n<=F}

Attempt This Online!

Input is an unsigned 32-bit integer.

• -10 bytes: use a comparison rather than an equality and bitwise-and.

Explanation

import."math/bits"
func f(n uint32)(r bool){
F:=uint32(0xFF)
for k:=2;k<31;k+=2{          // rotation check
j:=RotateLeft32(n,k)         // rotate left an even number of times
if r=j<=F||^j<=&F;r{return}} // if 8-bit or its complement is 8-bit, return true
return n<=F||^n<=F}          // return if 8-bit or its complement is 8-bit

Go, 121 bytes

func f(n,k uint32)int{F:=uint32(0xFF)
if n&^F>0{k--
if k<1{return 0}
j:=n*4|n>>30
if k&1>0{j=^n}
return f(j,k)}
return 1}

Attempt This Online!

A direct port of @Arnauld's JS answer.

Answer 5

ARMv2, 32 28 bytes

Input is in R0, output is in R1 which is zero if the input is an invalid constant. CMN trick stolen from Notlikethat's answer to the Stack Overflow question linked by @PeterCordes.

VALID:  MOV R1, #-16
LOOP:   MOV R0, R0, ROR#2
        CMP R0, #256
        CMNCC R0, #256        @ compare with -256, predicated on Carry Clear
        ADDSCC R1, R1, #1     @ Add and Set flags if Carry Clear
        BCC LOOP
        MOVS R15, R14         @ return

This is ARM mode so each instruction is 4 bytes, unlike Thumb or Thumb 2.
movs r15, r14 copies the return address to the program counter, mov pc, lr, returning from the function like bx lr in modern ARM code.

Alternative version using @Bubbler's trick of XORing the input with itself rotated left one bit, which still works with CMP (but not my original 32-byte TST version, which is why I didn't use that approach at the time). Input is in R0, output is in ZF which is set or R0 which is zero if the input is an invalid constant.

VALID:  EOR R1, R0, R0, ROR#31
        MOV R0, #-16
LOOP:   MOV R1, R1, ROR#2
        CMP R1, #512
        ADDSCC R0, R0, #1     @ Add and Set flags if Carry Clear
        BCC LOOP
        MOV R15, R14          @ return

Answer 6

Retina, 101 bytes

.+
$.(23283064365386962890625**
16{`.+$
$.(4**
)r`(.?)(.{1,32})$
$.($1*)¶$2
A`$
¶

$
$`
0`0{12}|3{12}

Try it online! Link includes test cases. Outputs 1 for valid, 0 for invalid. Explanation:

.+
$.(23283064365386962890625**
16{`.+$
$.(4**
)r`(.?)(.{1,32})$
$.($1*)¶$2
A`$

Convert the input to 16 base 4 digits. (This method is required for very large integers or even for large integers where the traditional method would cause the process to run out of memory.)

¶

$
$`

Join the digits together and then duplicate the string.

0`0{12}|3{12}

Check for 12 repeated 0s or 3s. (If any non-zero output is acceptable, the 0` can be removed to save two bytes.)

Answer 7

JavaScript (Node.js), 43 bytes

f=n=>++i&31&&n>>8==n>>31|f(n>>>2|n<<30);i=0

Try it online!

Note: This function will not be reusable after about 2⁴⁸ invokes. I would argue that should be fine according to the spirit of code-golf though. And fix the limit may cost 2 more bytes.

Answer 8

05AB1E, 17 bytes

4B16°+¦2×30S12×åà

Port of @Neil's Charcoal answer, so make sure to upvote that answer as well.

Input as an integer.

Try it online or verify all test cases.

Explanation:

4B                # Convert the (implicit) input-integer to base-4
  16°             # Push 10**16
     +            # Add it to the base-4 number (as base-10 addition)
      ¦           # Remove the leading 1
       2×         # Repeat this string two times
         30S      # Push [3,0]
            12×   # Repeat both 12 times
               å  # Check if the earlier string contains a substring of 12 3s or 0s
                à # Check if either of the two is truthy
                  # (after which the result is output implicitly)

Answer 9

Ada/GNAT, 152 bytes

type T is mod 2**32;function G(X:T;C:T:=0) return Boolean is (C<30 and then ((((X and 255)=X or (X or not 255)=X) or else G((X mod 4)*2**30+X/4,C+1))));

G is a recursive function that:

1. Takes a type T, which is a mod. Mod types are like Integers, except they wrap around when they overflow and you can do bitwise operations on them.

2. Defaults C to 0 and uses it to check for too many recursions. This was way fewer bytes than writing a loop structure, not just because of the verbose loop syntax in Ada but also because the inline subprogram syntax couldn't be usable with a loop. I picked 30 because it was no more bytes than more sensible values like 15 or 16 that I'd have to do more testing on.

3. Does bitwise logic between the input X and 255/not 255. I honestly didn't expect "not 255" to work, but as it turns out, this does a logical inverse as if it were a variable. These two comparisons basically enforce the rule that all the meaningful data must be within a range of eight contiguous bits. 255 being 00000000000000000000000011111111, and not 255 being 11111111111111111111111100000000.

4. Does the arithmetic equivalent of rotating by 2 and uses this with an incremented C to call its next iteration. There is a builtin for rotations, but using it required a with and a function call, so doing this turned out to be less verbose.

Answer 10

JavaScript (ES6), 47 bytes

Returns 0 or 1.

f=(n,m=~255)=>n&m&&~n&m?m%96&&f(n,m*4|m>>>30):1

Try it online!

Commented

f = (          // f is a recursive function taking:
  n,           //   n = input
  m = ~255     //   m = mask, initialized to ~255 (note that this gives
               //   the signed value -256 rather than 0xFFFFFF00, which
               //   is important for the modulo 96 test)
) =>           //
n & m &&       // if n & m is not 0
~n & m ?       // and ~n & m is not 0:
  m % 96 &&    //   if m is not equal to 0x3FFFFFC0 (the last rotation
               //   which is the only one to be a multiple of 96):
    f(         //     do a recursive call:
      n,       //       pass n unchanged
      m * 4 |  //       rotate m by 2 positions to the left
      m >>> 30 //       (the result is still signed)
    )          //     end of recursive call
:              // else:
  1            //   success: return 1

Answer 11

Jelly, 17 bytes

+Ø%BḊṙ⁴ḶḤ¤;¬$ḄṂ<⁹

Try it online!

A monadic link taking an integer and returning 1 for valid and two for invalid.

Explanation

+Ø%               | Add 2**32
   B              | Convert to binary
    Ḋ             | Remove first digit
     ṙ⁴ḶḤ¤        | Rotate left by each of (0 to 15 doubled)
          ;¬$     | Concatenate to binary not of this
             Ḅ    | Unbinary
              Ṃ   | Max
               <⁹ | < 256

Answer 12

ARMv6M (Cortex-M0), 38 bytes

;@ Pre-UAL syntax
;@ bool isValidARMImm(int _X);
_isValidARMImm:
            TST R0,R0           ;@ test negative
            BPL 1f
                NEG R0,R0       ;@ convert to positive
1:
            TST R0,R0           ;@ test zero
            BEQ 3f              ;@ branch to true if zero
            MOV R1,R0           ;@ copy to work register
            MOV R2,#0x00        ;@ set shifted bit count to 0
2:
                LSR R1,#1       ;@ remove following 0 bits
                BCS 1f          ;@ end if 1 bit shifted in carry flag
                ADD R2,#0x01    ;@ count following 0 bits
                B 2b            ;@ loop
1:
            LSR R0,R2           ;@ shift out 0 bits
            UXTB R1,R0          ;@ unsigned byte extend
            CMP R0,R1           ;@ test (int)R0 == (byte)R1
            BEQ 3f              ;@ branch to true case if equal
                MOV R0,#0x00    ;@ false
                BX LR
3:
            MOV R0,#0x01        ;@ true
            BX LR

8 bytes can be saved by returning the result in the zero flag instead of R0.

_isValidARMImm_ZeroFlag:
            TST R0,R0           ;@ test negative
            BPL 1f
                MVN R0,R0       ;@ convert to positive
1:
            TST R0,R0           ;@ test zero
            BEQ 3f              ;@ branch to true if zero
            MOV R1,R0           ;@ copy to work register
            MOV R2,#0x00        ;@ set shifted bit count to 0
2:
                LSR R1,#1       ;@ remove following 0 bits
                BCS 3f          ;@ end if 1 bit shifted in carry flag
                ADD R2,#0x01    ;@ count following 0 bits
                B 2b            ;@ loop
3:
            LSR R0,R2           ;@ shift out 0 bits
            UXTB R1,R0          ;@ unsigned byte extend
            CMP R0,R1           ;@ test (int)R0 == (byte)R1
            BX LR