Is this a narrow Thumb instruction?
ARM Thumb was originally a 16-bit only subset of the 32-bit ARM instruction set.
However, later versions added 32-bit "wide" instructions which were more flexible, and called the original, more restrictive 16-bit instructions "narrow" instructions.
The assembler now chooses between narrow and wide instructions automatically, depending on how the instruction was written. However, this meant that the syntax had to be changed to have specific rules.
Your job is to be this assembler.
However, the programs you parse are not that interesting; they will only ever consist of add and adds.
More specifically:
Your task is to write a function or program that will take an add/adds instruction, and return a truthy value if it is a valid narrow instruction, or a falsey value if it is not.
Syntax rules
- ARM has 16 registers,
r0-r12, r13 (aka sp), r14 (aka lr), and r15 (aka pc). For ease of parsing, we are going to refer to all registers by their number, instead of using the special register names.
- Do note the names when reading the official docs, as there are a lot of special cases for
sp and pc.
- In Thumb mode, these are split into "Lo registers", which are
r0-r7, and "Hi registers" which are r8-r15. Many instructions can only use Lo registers.
- Many instructions use the same source register as the destination register, even if they are written with three operands.
add and adds are distinct instructions. adds affects the condition flags, while add does not. That is the difference, if you were wondering.
The following 6 forms are valid for narrow instructions (adapted from here):
adds x, y, #imm: x and y must both be Lo registers, and imm is a 3-bit constant from 0-7.adds x, y, z: x, y, and z must all be Lo registers.add x, x, y: x and/or y must be Hi registers. Note that x is repeated twice.
- We are ignoring the fact that ARMv6 relaxed this rule to keep it interesting.
adds x, x, #imm: x must be a Lo register. imm is an 8-bit constant from 0-255. Again, note that x is repeated twice.add r13, r13, #imm: imm is a constant multiple of 4 in the range 0-508.add x, y, #imm: x must be a Lo register, and y must either be r13 or r15. imm is a constant multiple of 4 in the range 0-1020.
Everything else is either a wide instruction or not valid.
Other notes
Standard loopholes, everything must be self-contained, and you are only allowed to treat it as text. You can't feed it to an assembler (unless you include the assembler source code in the result, but.. ｗｈｙ).
The input can either be a string argument or text from stdin.
You can assume the format will match the following format (all lowercase, separators being a single space):
{add or adds} reg, reg, {#imm or reg}
Where imm is a non-negative number in base 10 (yes, including zero).
As a regex pattern:
^adds? r([0-9]|1[0-5]), r([0-9]|1[0-5]), (#[0-9]+|r([0-9]|1[0-5]))$
Reference implementation
In case the rules are difficult to follow, here is a reference implementation I made in C. Yes, I deliberately overabstracted it to make you do all the work.
I resisted the urge to post the reference implementation in ARM Thumb assembly, as that would be genuinely evil. 😏
You will not need to do the same error checking I did here. You can always assume the string itself is valid. The error checks in the main function are mostly to show what CAN'T happen.
#include <stdlib.h>
#include <stdint.h>
#include <stdio.h>
#include <stdbool.h>
#include <errno.h>
#include <inttypes.h>
struct thumb_add_insn {
char opcode[5];
uint32_t op1;
uint32_t op2;
char op3_prefix;
uint32_t op3;
};
// Returns whether the opcode ID is adds.
static inline bool is_adds(const char *opcode)
{
return strcmp(opcode, "adds") == 0;
}
// Returns whether this register ID belongs to a Lo register,
// specifically r0-r7.
static inline bool is_lo_reg(uint32_t reg_id)
{
return reg_id <= 7;
}
// Returns whether this register ID belongs to a Hi register,
// specifically r8-r15.
static inline bool is_hi_reg(uint32_t reg_id)
{
return reg_id >= 8;
}
// Returns whether the operand prefix is for an immediate
// value, specifically, '#'.
static inline bool is_imm(char c)
{
return c == '#';
}
// adds x, y, #imm3
static bool is_form_1(const struct thumb_add_insn *insn)
{
return is_adds(insn->opcode)
&& is_lo_reg(insn->op1)
&& is_lo_reg(insn->op2)
&& is_imm(insn->op3_prefix)
&& insn->op3 <= 7;
}
// adds x, y, z
static bool is_form_2(const struct thumb_add_insn *insn)
{
return is_adds(insn->opcode)
&& is_lo_reg(insn->op1)
&& is_lo_reg(insn->op2)
&& !is_imm(insn->op3_prefix)
&& is_lo_reg(insn->op3);
}
// adds x, x, #imm8
static bool is_form_3(const struct thumb_add_insn *insn)
{
return is_adds(insn->opcode)
&& is_lo_reg(insn->op1)
&& insn->op1 == insn->op2
&& is_imm(insn->op3_prefix)
&& insn->op3 < 256;
}
// add x, x, y
static bool is_form_4(const struct thumb_add_insn *insn)
{
return !is_adds(insn->opcode)
&& !is_imm(insn->op3_prefix)
&& (is_hi_reg(insn->op1) || is_hi_reg(insn->op3))
&& insn->op1 == insn->op2;
}
// add r13, r13, #imm
static bool is_form_5(const struct thumb_add_insn *insn)
{
return !is_adds(insn->opcode)
&& insn->op1 == 13
&& insn->op1 == insn->op2
&& is_imm(insn->op3_prefix)
&& insn->op3 <= 508
&& insn->op3 % 4 == 0;
}
// add x, y, #imm, y == r13 or r15
static bool is_form_6(const struct thumb_add_insn *insn)
{
return !is_adds(insn->opcode)
&& is_lo_reg(insn->op1)
&& (insn->op2 == 13 || insn->op2 == 15)
&& is_imm(insn->op3_prefix)
&& insn->op3 <= 1020
&& insn->op3 % 4 == 0;
}
// Parses a Thumb add/adds instruction.
// Returns 1 if it is a narrow instruction, 0 if it is not,
// and -1 on an error.
int is_narrow_add(const char *str)
{
// Note that you do not have to do error checking for the
// competition.
if (str == NULL) {
errno = EINVAL;
return -1;
}
// Allocate a 24 byte struct on the heap for good measure
struct thumb_add_insn *insn = calloc(1, sizeof(*insn));
if (insn == NULL) {
return -1;
}
// Parse the instruction with sscanf.
// {adds} r{0}, r{3}, {#}{3}
if (sscanf(str, "%4s r%"SCNu32", r%"SCNu32", %c%"SCNu32,
insn->opcode,
&insn->op1,
&insn->op2,
&insn->op3_prefix,
&insn->op3) != 5
|| (strcmp(insn->opcode, "add") != 0
&& strcmp(insn->opcode, "adds") != 0)
|| insn->op1 > 15
|| insn->op2 > 15
|| (insn->op3_prefix != 'r' && insn->op3_prefix != '#')
|| (insn->op3_prefix == 'r' && insn->op3 > 15)
) {
errno = EINVAL;
free(insn);
return -1;
}
int ret;
// Test against each of the forms
if (is_form_1(insn)) {
ret = 1;
} else if (is_form_2(insn)) {
ret = 1;
} else if (is_form_3(insn)) {
ret = 1;
} else if (is_form_4(insn)) {
ret = 1;
} else if (is_form_5(insn)) {
ret = 1;
} else if (is_form_6(insn)) {
ret = 1;
} else { // not a match
ret = 0;
}
free(insn);
return ret;
}
Test cases
adds r6, r3, #0 // true, form 1
adds r0, r1, #7 // true, form 1
add r0, r1, #3 // false, must be "adds"
adds r0, r9, #1 // false, r9 is a Hi register
adds r0, r1, #9 // false, must be 0-7
adds r0, r0, r0 // true, form 2
adds r7, r1, r2 // true, form 2
adds r4, r4, r1 // true, form 2
add r7, r1, r2 // false, must be "adds"
adds r13, r14, r6 // false, r13 and r14 are Hi registers (this isn't even valid as a wide instruction)
adds r0, r0, #0 // true, form 3
adds r5, r5, #249 // true, form 3
add r6, r6, #31 // false, must be "adds"
adds r3, r3, #256 // false, must be 0-255
adds r8, r8, #72 // false, r8 is a Hi register
add r4, r4, r11 // true, form 4
add r8, r8, r5 // true, form 4
add r9, r9, r9 // true, form 4
add r14, r14, r12 // true, form 4
add r8, r9, r10 // false, Rd must be the same
add r1, r1, r0 // false, one must be a Hi register (we are ignoring the ARMv6 change)
add r13, r13, #0 // true, form 5
add r13, r13, #48 // true, form 5
adds r13, r13, #64 // false, must be "add"
add r13, r13, #17 // false, not a multiple of 4
add r13, r13, #512 // false, must be 0-508
add r0, r15, #0 // true, form 6
add r4, r13, #1000 // true, form 6
add r11, r13, #32 // false, r11 is a Hi register
add r2, r13, #4000 // false, must be 0-1020
adds r7, r15, #384 // false, must be "add"
add r3, r15, #127 // false, not a multiple of 4
Things you can safely ignore:
// String will never be empty
adds r1, r2 // don't worry about implicit middle operand
adds R4, #12 // same
adds r3, r3, #-3 // adding a negative is not even a thing
add r0, r0, r99 // the only registers are r0 - r15
add r13, r13, #0x32 // it is base 10
subs r1, r1, r2 // only add and adds need to be handled
add r2, r2, lr // you don't need to handle the special names
add r0, sp, #0 // same
add #3, r1, r1 // only the last one will be an immediate
adds r3, r3, 32 // all immediates are prefixed with #
ADDS R0, R0, R1 // everything is lowercase
adds r2, r3 , r4 // only one space
adds r2,r3,r4 // there will always be spaces
addeq r0, r0, r1 // no IT blocks
adds.n r0, r0, r1 // no manual width specifiers
add r1, r2, r3, lsl #8 // no barrel shifting
This is code-golf, so the shortest answer in bytes per language wins.
Proposed tags: code-golfstringparsing and maybe assembly but I think that is for things you must write in assembly, not parsing assembly itself.
