Golf this Thumb-2 Constant!

Question

One thing that is constantly frustrating when golfing ARM Thumb-2 code is generating constants.

Since Thumb only has 16-bit and 32-bit instructions, it is impossible to encode every immediate 32-bit value into a single instruction.

Additionally, since it is a variable length instruction set, some methods of generating a constant are smaller than others.

I hate that. Write a program or function that does this work for me so I don't have to think about it. (*shudder*)

There are four different variants of the mov instruction as well as a pseudo instruction which loads from a constant pool.

They are either 2 bytes, 4 bytes, or 6 bytes long.

These are the following:

1. movs: 2 bytes. Generates any 8-bit unsigned value from 0x00 to 0xFF in the low 8 bits, setting the other bits to 0.
2. mov: 4 bytes. Generates any 8-bit unsigned value bitwise rotated any number of bits,^† filling the rest with 0 bits.
3. mvn: 4 bytes. The same as mov, but generates the one's complement of that rotated 8-bit value, filling the rest with 1 bits.
4. movw: 4 bytes. Can set the low 16 bits to any 16-bit unsigned value from 0x0000-0xFFFF, and the high 16 bits to 0.
5. ldr: 6 bytes. The last resort. Can generate any 32-bit value, but is slow and larger than the other options.

_{†: Note that this is dramatically oversimplified, the real encoding would make this challenge quite frustrating.}

The input will be a 32-bit integer, either by string (base 10 signed/unsigned or hex), stdin, or value.

Every value from 0x00000000 to 0xFFFFFFFF must be handled. It is a critical part of the challenge. Watch out for signed shift issues.

However, you can safely assume all inputs will fit into 32 bits, since ARM is a 32-bit architecture.

The output will be the shortest instruction to encode this constant.

The output format is whatever is easiest, as long as the values are distinct and you indicate which instruction corresponds to each output.

There will be a few cases where multiple answers are correct. You may either output one of the correct answers, or all of them. However, you must only display the shortest answers. So, for example, you must only output ldr when none of the other instructions can generate it.

Test cases (values are in hex to show the bit patterns)

0x00000000 -> movs
0x00000013 -> movs
0x000000ff -> movs
0x12345678 -> ldr
0x02300000 -> mov
0xffffffff -> mvn
0x00ffffff -> mvn
0x00001200 -> mov or movw
0x11800000 -> mov
0x80000000 -> mov
0x00000100 -> mov or movw
0x0000f00d -> movw
0xfff3dfff -> mvn
0x03dc0000 -> mov
0xf000000f -> mov
0x00003dc0 -> mov or movw
0x0021f300 -> ldr
0x00100010 -> ldr
0xffff0000 -> ldr

Standard loopholes apply.

Note that as and objdump will not help; they will use the real encoding which is wrong. 😏

Being code-golf, the smallest answer in bytes per language wins.

Answer 1

JavaScript (ES6), 57 bytes

Returns false for "mov", true for "movs", 2 for "ldr", 3 for "mvn" or 4 for "movw".

f=(n,r)=>n>>8?~n>>8?r>31?n>>16?2:4:f(n>>>31|n*2,-~r):3:!r

Try it online!

Commented

f = (              // f is a recursive function taking:
  n,               //   n = input
  r                //   r = rotation counter, initially undefined
) =>               //
  n >> 8 ?         // if some of the upper 24 bits of n are not 0's:
    ~n >> 8 ?      //   if some of the upper 24 bits of n are not 1's:
      r > 31 ?     //     if the input was rotated 32 times (which means
                   //     that we've tried all possible rotations and we
                   //     are back to the original value):
        n >> 16 ?  //       if some of the upper 16 bits of n are not 0's:
          2        //         return 2 for "ldr"
        :          //       else:
          4        //         return 4 for "movw"
      :            //     else:
        f(         //       do a recursive call:
          n >>> 31 //         rotate n by 1 position to the left
          | n * 2, //
          -~r      //         increment r
        )          //       end of recursive call
    :              //   else:
      3            //     return 3 for "mvn"
  :                // else:
    !r             //   return true for "movs" if r is zero'ish
                   //   or false for "mov" if r is greater than 0

Answer 2

Jelly, 29 bytes

+Ø%BḊ¹¬ƭṙJ$Ḅ<⁹Ẹ
⁹²>;Ç;Ç;<⁹$TṀ

Try it online!

Returns 0, 1, 2, 3, 4 respectively for ldr, movw, mov, mvn and movs. Probably could be improved.

Answer 3

C (gcc), ^{105 \$\cdots\$73} 72 bytes

Saved 15 bytes thanks to EasyasPi!!!
Saved 3 4 bytes thanks to ceilingcat!!!

i;z;f(n){for(i=0;z=n>>8,i++<32&&z&&~z;)n=n*2|n<0;i=z?~z?z>>8?4:3:2:i>1;}

Try it online!

Returns \$0,1,2,3,4\$ for movs, mov, mvn, movw, ldr.

Explanation (before some golfs)

i;f(n){                         // function taking a 32 bit parameter n  
       for(i=0;i++<32           // loop for maximum of 32 times  
               &&n>>8           // while there's set bits in the 24 msb  
               &&~n>>8;)        // and in the 24 msb of n's 1s compliment   
           n=n*2|n<0;           // rotate n 1 bit to the left  
       i=                       // return:  
         n>>8?~n>>8?            // if these are still truth values then we   
                                // must have rotated n 32 times   
                    n>>16?      // does the original n have set bits in the 
                                // 16 msb?   
                          4:    // ldr if it does   
                          3:    // movw if it doesn't.  
                                // the ones below are because we stopped  
                                // looping when we found no/all 1 bits in  
                                // the 24 msb
                          2:    // mvn if all 24 msb are set in the   
                                // current of a rotation of n    
                          i>1;  // mov if there's no set bits in the 24 msb 
                                // of the current rotation of n   
                                // movs if there's no set bit in the 24 msb    
}                               // of n at the start.

Answer 4

MMIX, 96 bytes (24 instrs)

Returns 8 for movs, else is a bitfield (1 for mov, 2 for mvn, 4 for movw). 0 is thus for ldr.

I'm fairly certain that this can never return 6 or 7.

00000000: 3fff0008 4aff0003 e3010008 f8020000  ?”¡®J”¡¤ẉ¢¡®ẏ£¡¡
00000010: 3fffff08 7301ff04 cf040000 e3050000  ?””®s¢”¥Ẇ¥¡¡ẉ¦¡¡
00000020: fe020004 f2030003 f6040002 28010301  “£¡¥ṗ¤¡¤ẇ¥¡£(¢¤¢
00000030: 3b030020 e3020000 e3040020 27040401  ;¤¡ ẉ£¡¡ẉ¥¡ '¥¥¢
00000040: 3fff0338 6302ff01 3bff031f 3f030301  ?”¤8c£”¢;”¤þ?¤¤¢
00000050: c00303ff 5b04fffa c0010102 f8020000  Ċ¤¤”[¥”«Ċ¢¢£ẏ£¡¡

gt2     SRU   $255,$0,8
        BNZ   $255,0F               // if(!(n >> 8))
        SET   $1,8
        POP   2,0                   // return 8; (movs)
0H      SRU   $255,$255,8
        ZSZ   $1,$255,4             // rv = !(n >> 16) << 2
        NXOR  $4,$0,0               // y = ~n
        SET   $5,0
        GET   $2,rJ
        PUSHJ $3,0F                 // q = f(y, 0)
        PUT   rJ,$2
        2ADDU $1,$3,$1              // rv = rv + q * 2
0H      SLU   $3,$0,32              // f(n, rv): y = n << 32
        SET   $2,0                  // q = 0
        SET   $4,32                 // i = 32
0H      SUBU  $4,$4,1               // loop: i--
        SRU   $255,$3,56
        CSZ   $2,$255,1             // if(!(y >> 56)) q = 1
        SLU   $255,$3,31
        SRU   $3,$3,1
        OR    $3,$3,$255            // y = (y >> 1) | (y << 31)
        PBNZ  $4,0B                 // if(i) goto loop
        OR    $1,$1,$2              // rv |= q
        POP   2,0                   // return(rv)

To also support the weird versions of mov and movn, replace SET $2,0 (E3020000, ṭ£¡¡) with the following, at a cost of 40 bytes/10 instructions:

    SRU  $255,$0,16     // ?”¡Ñ t = n >> 16
    XOR  $255,$255,$0   // İ””¡ t ^= n
    SLU  $255,$255,48   // ;””0 t <<= 48
    ZSZ  $4,$255,1      // s¥”¢ i = !t (test for top-equals-bottom)
    SLU  $255,$3,24     // ;”¤ð t = y << 24
    ZSZ  $1,$255,$4     // r¢”¥ q = t? 0 : i (test for low-bytes-zero)
    XOR  $255,$255,$3   // İ””¤ t ^= y
    SRU  $255,$255,56   // ?””8 t >>= 56
    CSZ  $1,$255,$4     // b¢”¥ if(!t) q = i (test for all-bytes-equal)
    SRU  $255,$3,56     // ?”¤8 t = y >> 56
    CSZ  $1,$255,$4     // b¢”¥ if(!t) q = i (test for high-bytes-zero)

Answer 5

Charcoal, 56 bytes

≔⍘×⊕Ｘ²¦³²Ｎ²θ¿‹Ｌθ⁴¹movs¿‹Ｌθ⁴⁹movw¿№θ×0²⁴mov¿№θ×1²⁴mvn¦ldr

Try it online! Link is to verbose version of code. Explanation:

≔⍘×⊕Ｘ²¦³²Ｎ²θ

Input the integer, multiply it by 2³²+1, and convert to binary.

¿‹Ｌθ⁴¹movs

If the length is less than 41, then the original number had 8 bits or fewer, so a movs instruction will work.

¿‹Ｌθ⁴⁹movw

Otherwise if the length is less than 49, then the original number had 16 bits or fewer, so a movw instruction will work.

¿№θ×0²⁴mov

Otherwise if the binary contains a string of 24 0s, then they can be rotated to the beginning of the original number, so a mov instruction will work.

¿№θ×1²⁴mvn

Otherwise if the binary contains a string of 24 1s, then they can be rotated to the beginning of the original number, so a mvn instruction will work.

¦ldr

Otherwise give up and use ldr.

This challenge reminds me of the difficulty of loading immediate values using original ARM instructions, so I wrote a 32-byte program that identifies values that can be loaded into a register via mov or mvn:

≔⍘×⊕Ｘ²¦³²Ｎ⁴θ¿№θ×0¹²mov¿№θ×3¹²mvn

Try it online! Link is to verbose version of code. Outputs mov if the value can be used directly as an immediate operand, or mvn if you can at least load it into a register.

Answer 6

Z80, 59 55 bytes

Input value in dehl. Output in c, 0, 1, 2, 3, 4 for ldr, mvn, mov, movw, movs respectively.
Trashes b and a. This is indeed rather silly.

0E 03 7C B7 20 03 0C 7B
B2 C8 AF 4F 3C F5 7A 2F
57 7B 2F 5F 7C 2F 67 7D
2F 6F 06 20 7A 17 CB 15
CB 14 CB 13 CB 12 7C B3
B2 20 05 F1 4F F5 10 EE
F1 D8 37 3C F5 18 D9

foo:
  ld c,3                // 0E 03    we might want to return 3
  ld a,h                // 7C       is h zero?
  or a                  // B7       the test
  jr nz,hnz             // 20 03    if so,
  inc c                 // 0C       increment c
hnz:                    //          in any case,
  ld a,e                // 7B       load e
  or d                  // B2       or in d
  ret z                 // C8       if both zero return
  xor a                 // AF       clear a and carry
  ld c,a                // 4F       and c
  inc a                 // 3C       actually, set a to 1
  push af               // F5       store a and carry
subr:
  ld a,d                // 7A       complement dehl
  cpl                   // 2F
  ld d,a                // 57
  ld a,e                // 7B
  cpl                   // 2F
  ld e,a                // 5F
  ld a,h                // 7C
  cpl                   // 2F
  ld h,a                // 67
  ld a,l                // 7D
  cpl                   // 2F
  ld l,a                // 6F
  ld b,32               // 06 20    do the following 32 times:
loop:
  ld a,d                // 7A       load D into A
  rla                   // 17       move top bit of A into C flag
  rl l                  // CB 15    do the rest of
  rl h                  // CB 14    the left rotation
  rl e                  // CB 13
  rl d                  // CB 12
  ld a,h                // 7C       or together
  or e                  // B3       the top three
  or d                  // B2       bytes;
  jr nz,nofit           // 20 05    if all zero,
  pop af                // F1       reload old af
  ld c,a                // 4F       load c
  push af               // F5       push it back
nofit:                  //          in any case
  djnz loop             // 10 EE    end loop
  pop af                // F1       reload old af
  ret c                 // D8       return if second time
  scf                   // 37       marker for second time
  inc a                 // 3C       and increment a
  push af               // F5       push those back
  jr subr               // 18 D9    and try again with complement

Bonus: another version that also checks for the weird constants, in 75 bytes. (Inserted region between »German guillemets«, changed byte in *stars*).

0E 03 7C B7 20 03 0C 7B
B2 C8 AF 4F 3C F5 7A 2F
57 7B 2F 5F 7C 2F 67 7D
2F 6F»AB 20 13 7C AA 20
0F AC 28 09 AD 28 06 7D
B7 20 05 F1 4F F5«06 20
7A 17 CB 15 CB 14 CB 13
CB 12 7C B3 B2 20 05 F1
4F F5 10 EE F1 D8 37 3C
F5 18*C5*

foo:
  ld c,3                // 0E 03    we might want to return 3
  ld a,h                // 7C       is h zero?
  or a                  // B7       the test
  jr nz,hnz             // 20 01    if so,
  inc c                 // 0C       increment c
hnz:                    //          in any case,
  ld a,e                // 7B       load e
  or d                  // B2       or in d
  ret z                 // C8       if both zero return
  xor a                 // AF       clear a and carry
  ld c,a                // 4F       and c
  inc a                 // 3C       actually, set a to 1
  push af               // F5       store a and carry
subr:
  ld a,d                // 7A       complement dehl
  cpl                   // 2F
  ld d,a                // 57
  ld a,e                // 7B
  cpl                   // 2F
  ld e,a                // 5F
  ld a,h                // 7C
  cpl                   // 2F
  ld h,a                // 67
  ld a,l                // 7D
  cpl                   // 2F
  ld l,a                // 6F
// begin insert
  xor e                 // AB       check for e=l
  jr nz,stlp            // 20 13    if not, skip to loop
  ld a,h                // 7C
  xor d                 // AA       check for d=h
  jr nz,stlp            // 20 0F    if not, skip to loop
  xor h                 // AC       check for h=0 (a 0 already)
  jr z,succ             // 28 09    if so, skip to succ
  xor l                 // AD       check for h=l
  jr z,succ             // 28 06    if so, skip to succ
  ld a,l                // 7D
  or a                  // B7       check for l=0
  jr nz,stlp            // 20 05    if not, skip to loop
succ:
  pop af                // F1       reload old af
  ld c,a                // 4F       load c
  push af               // F5       push it back
stlp:
// end insert
  ld b,32               // 06 20    do the following 32 times:
loop:
  ld a,d                // 7A       load D into A
  rla                   // 17       move top bit of A into C flag
  rl l                  // CB 15    do the rest of
  rl h                  // CB 14    the left rotation
  rl e                  // CB 13
  rl d                  // CB 12
  ld a,h                // 7C       or together
  or e                  // B3       the top three
  or d                  // B2       bytes;
  jr nz,nofit           // 20 03    if all zero,
  pop af                // F1       reload old af
  ld c,a                // 4F       load c
  push af               // F5       push it back
nofit:                  //          in any case
  djnz loop             // 10 EC    end loop
  pop af                // F1       reload old af
  ret c                 // D8       return if second time
  scf                   // 37       marker for second time
  inc a                 // 3C       and increment a
  push af               // F5       push those back
  jr subr               // 18 C3    and try again with complement