A32 data processing and the barrel shifter

One A32 instruction multiplies a register by 9 with no multiplier: add r12, r2, r2, lsl #3 adds r2 to r2 shifted left three places, so 5 becomes 45. The barrel shifter in front of the ALU does that shift, on the second operand of A32 data processing instructions as they run.

Every number below comes from a Python model of the A32 instruction set that runs what llvm-mc 23.1.2 and ld.lld 21.0.0 built, flag by flag as Arm’s pseudocode specifies, counting instructions, not cycles. Bitwise operations and shifts explains the shifts themselves.

The second operand is shifted on its way into the ALU

In add r1, r2, r3, lsl #3, r2 goes straight to the ALU, while r3 first passes through the barrel shifterbarrel shifter: The circuit in front of a 32-bit Arm ALU that shifts or rotates one operand by any amount in a single step, so an A32 instruction such as add r1, r2, r3, lsl #3 shifts r3 and adds in one go. and moves three places left. This last operand, Operand2 or the flexible second operandflexible second operand: Operand2, the last operand of an A32 data-processing instruction: a rotated 8-bit immediate, or a register that the barrel shifter can shift by a constant or by another register's bottom byte, or rotate with rrx., has five forms:

Step through that add:

shifts.s uses every form on r2 = 5 and r3 = 3:

@ shifts.s: one data-processing instruction per line, each with its second operand shifted on the way in.
@ r2 = 5 and r3 = 3 are the inputs; every other register holds one result.
        .syntax unified
        .text
        .global _start
_start: mov     r2, #5
        mov     r3, #3
        add     r12, r2, r2, lsl #3     @ 5 + (5 << 3): times 9 in one instruction
        add     r1, r2, r3, lsl #3      @ 5 + (3 << 3)
        rsb     r4, r2, r2, lsl #4      @ (5 << 4) - 5: times 15
        mov     r5, r2, ror #1          @ bit 0 of 5 comes back in at bit 31
        mvn     r6, #15                 @ NOT 15, which is -16
        mov     r7, r6, asr #2          @ -16 >> 2, copies of the sign bit fill the top
        mov     r8, r6, lsr #2          @ the same bits, zeros fill the top
        mov     r9, #4
        mov     r10, r2, lsl r9         @ the shift amount comes from a register
        mov     r11, r2, rrx            @ one place right, the C flag enters at bit 31
        mov     r0, #0xFF000000         @ an immediate: 0xFF rotated right by 8
stop:   b       stop

"""Builds shifts.s, lists the words it assembled to, and runs it on the A32 model to read every result register."""
import pathlib
import sys

sys.path.insert(0, str(pathlib.Path(__file__).parent / "sessions"))
import armlab

elf = armlab.build("shifts.s")                       # assemble with llvm-mc, link with ld.lld
armlab.sh(f"llvm-objdump -d --triple=armv7a {elf}")  # each instruction beside the 32-bit word it became
armlab.run(elf, regs=["r12", "r1", "r4", "r5",       # the results, four to a line
                      "r6", "r7", "r8", "r10",
                      "r11", "r0"])

$ llvm-mc --triple=armv7a-none-eabi -filetype=obj -o shifts.o shifts.s
$ ld.lld -T sessions/a32.ld -o shifts.elf shifts.o
$ llvm-objdump -d --triple=armv7a shifts.elf

shifts.elf:	file format elf32-littlearm

Disassembly of section .text:

00000000 <_start>:
       0: e3a02005     	mov	r2, #5
       4: e3a03003     	mov	r3, #3
       8: e082c182     	add	r12, r2, r2, lsl #3
       c: e0821183     	add	r1, r2, r3, lsl #3
      10: e0624202     	rsb	r4, r2, r2, lsl #4
      14: e1a050e2     	ror	r5, r2, #1
      18: e3e0600f     	mvn	r6, #15
      1c: e1a07146     	asr	r7, r6, #2
      20: e1a08126     	lsr	r8, r6, #2
      24: e3a09004     	mov	r9, #4
      28: e1a0a912     	lsl	r10, r2, r9
      2c: e1a0b062     	rrx	r11, r2
      30: e3a004ff     	mov	r0, #-16777216

00000034 <stop>:
      34: eafffffe     	b	0x34 <stop>             @ imm = #-0x8
Model run of shifts.elf: stopped at 0x00000034: b . (a branch to itself); 13 instructions
r12 = 0x0000002D   r1  = 0x0000001D   r4  = 0x0000004B   r5  = 0x80000002
r6  = 0xFFFFFFF0   r7  = 0xFFFFFFFC   r8  = 0x3FFFFFFC   r10 = 0x00000050
r11 = 0x00000002   r0  = 0xFF000000

r12 = 0x2D is 5 × 9 and r4 = 0x4B is 5 × 15, since rsb subtracts the other way round. Two places right, −16 became 0xFFFFFFFC with asrarithmetic shift: A right shift that fills the vacated top bits with copies of the sign bit, so a negative number stays negative; it divides by a power of two rounding towards minus infinity, so -7 shifted right by 1 is -4. More in “Bitwise logic, shifts and rotates” and 0x3FFFFFFC with lsr. ror #1 moved bit 0 of 5 to bit 31. The rotate right extendedrotate right extended: RRX, a 32-bit Arm rotation by one place through the C flag: every bit moves one place right, the old C enters at bit 31, and bit 0 is the bit that leaves., rrx, put C into bit 31; C was 0 because the model starts the flags, UNKNOWN after reset, at 0. The listing spells a shifted mov by its shift, ror r5, r2, #1: one encoding, two names.

An immediate is eight bits and a rotation, not a 12-bit number

An A32 data-processing instruction keeps its constant in 12 bits, yet cannot hold every number up to 4095: the low 8 bits are a value, the top 4 a rotation, and the constant is the value rotated right by twice the rotation. mov r0, #0xFF000000 became 0xE3A004FF: field 0x4FF, 0xFF rotated right by 8. A rotated immediaterotated immediate: The A32 way of storing a constant in 12 bits of an instruction: an 8-bit value and a 4-bit field, the value rotated right by twice the field. 0xFF000000 is 0xFF rotated right by 8; 257 has no such form. holds any constant whose set bits fit in eight neighbouring bits from an even position, even across bit 31, as 0xF000000F does.

shifter.py is the same shifter in Python, with the immediate field decoded too. Change a value in either loop and run it:

"""The A32 barrel shifter in a few lines of Python: the value each shift passes on, and the constant a 12-bit
immediate field stands for. Change the values in the two loops at the bottom and run it again."""

MASK = 0xFFFFFFFF


def shift(value, kind, amount, c=0):
    """The value the shifter passes on to the ALU; c is the C flag, which rrx brings in at bit 31."""
    value &= MASK
    if kind == "rrx":
        return (c << 31) | (value >> 1)
    if amount == 0:
        return value
    if kind == "lsl":
        return (value << amount) & MASK if amount < 32 else 0
    if kind == "lsr":
        return value >> amount if amount < 32 else 0
    if kind == "asr":
        signed = value - (1 << 32) if value >> 31 else value
        return (signed >> min(amount, 31)) & MASK
    amount %= 32                                    # ror: the bits that leave at the bottom re-enter at the top
    return ((value >> amount) | (value << (32 - amount))) & MASK


def expand_imm(imm12):
    """The constant an immediate field stands for: its low 8 bits rotated right by twice its top 4 bits."""
    return shift(imm12 & 0xFF, "ror", 2 * (imm12 >> 8))


for kind, amount in (("lsl", 3), ("lsr", 2), ("asr", 2), ("ror", 1), ("rrx", 1)):
    operation = kind if kind == "rrx" else f"{kind} #{amount}"   # rrx always moves one place
    for value in (5, 0xFFFFFFF0):
        print(f"{value:#010x} {operation} = {shift(value, kind, amount):#010x}")

for imm12 in (0x005, 0x4FF, 0x2FF, 0xF3F):
    print(f"field {imm12:#05x}: {imm12 & 0xFF:#04x} rotated right by {2 * (imm12 >> 8):2} = {expand_imm(imm12):#010x}")

0x00000005 lsl #3 = 0x00000028
0xfffffff0 lsl #3 = 0xffffff80
0x00000005 lsr #2 = 0x00000001
0xfffffff0 lsr #2 = 0x3ffffffc
0x00000005 asr #2 = 0x00000001
0xfffffff0 asr #2 = 0xfffffffc
0x00000005 ror #1 = 0x80000002
0xfffffff0 ror #1 = 0x7ffffff8
0x00000005 rrx = 0x00000002
0xfffffff0 rrx = 0x7ffffff8
field 0x005: 0x05 rotated right by  0 = 0x00000005
field 0x4ff: 0xff rotated right by  8 = 0xff000000
field 0x2ff: 0xff rotated right by  4 = 0xf000000f
field 0xf3f: 0x3f rotated right by 30 = 0x000000fc

For 5 it repeats the model: 0x80000002 after ror #1, 2 after rrx. Field 0xF3F, rotation 15, turns 30 places right, the same as 2 places left: 0x3F becomes 0xFC.

Four groups of instructions take Operand2, and S decides about the flags

A32 data processing comes in four groups, and each of their instructions takes Operand2 as its last operand:

Multiplies are a family of their own: mul r10, r0, r1 keeps the low 32 bits, and its operands never pass through the shifter. groups.s runs one instruction per group on 240 and 60:

@ groups.s: one instruction from each group of A32 data processing, on the same two inputs 240 and 60.
@ The last three lines show what the S suffix changes: only cmp and subs write the flags.
        .syntax unified
        .text
        .global _start
_start: mov     r0, #240
        mov     r1, #60
        add     r2, r0, r1              @ arithmetic: r0 + r1
        sub     r3, r0, r1              @ r0 - r1
        rsb     r4, r0, r1              @ reverse subtract: r1 - r0
        and     r5, r0, r1              @ logical: bits set in both
        orr     r6, r0, r1              @ bits set in either
        eor     r7, r0, r1              @ bits set in one only
        bic     r8, r0, r1              @ r0 with r1's bits cleared
        mvn     r9, r0                  @ move: NOT r0
        mul     r10, r0, r1             @ multiply: the low 32 bits of r0 * r1
        cmp     r0, r1                  @ compare: r0 - r1 for the flags, no register written
        sub     r11, r1, r1             @ no S: the result is 0, the flags stay as cmp left them
        subs    r11, r1, r1             @ S: the same result, and now the flags describe it
stop:   b       stop

"""Runs groups.s on the A32 model and prints, after every instruction, the register it wrote and the N, Z, C, V flags."""
import pathlib
import sys

sys.path.insert(0, str(pathlib.Path(__file__).parent / "sessions"))
import armlab

elf = armlab.build("groups.s")
text = armlab.listing(elf)                      # address -> instruction, as llvm-objdump prints it
COMPARES = ("cmp", "cmn", "tst", "teq")         # these write the flags and no register


def watch(machine):
    def step(m, address, word, executed):
        line = text[address]
        if line.startswith("b "):               # the final b . that ends the run
            return
        flags = "".join(str(m.flag(f)) for f in "NZCV")
        if line.startswith(COMPARES):
            wrote = "flags only"
        else:
            rd = line.split()[1].rstrip(",")    # the first operand is the destination
            wrote = f"{rd} = {armlab.hex32(m.reg(int(rd[1:])))}"
        print(f"  {line:<20} {wrote:<17} NZCV = {flags}")
    machine.on_step = step


armlab.run(elf, setup=watch)

$ llvm-mc --triple=armv7a-none-eabi -filetype=obj -o groups.o groups.s
$ ld.lld -T sessions/a32.ld -o groups.elf groups.o
  mov r0, #240         r0 = 0x000000F0   NZCV = 0000
  mov r1, #60          r1 = 0x0000003C   NZCV = 0000
  add r2, r0, r1       r2 = 0x0000012C   NZCV = 0000
  sub r3, r0, r1       r3 = 0x000000B4   NZCV = 0000
  rsb r4, r0, r1       r4 = 0xFFFFFF4C   NZCV = 0000
  and r5, r0, r1       r5 = 0x00000030   NZCV = 0000
  orr r6, r0, r1       r6 = 0x000000FC   NZCV = 0000
  eor r7, r0, r1       r7 = 0x000000CC   NZCV = 0000
  bic r8, r0, r1       r8 = 0x000000C0   NZCV = 0000
  mvn r9, r0           r9 = 0xFFFFFF0F   NZCV = 0000
  mul r10, r0, r1      r10 = 0x00003840  NZCV = 0000
  cmp r0, r1           flags only        NZCV = 0010
  sub r11, r1, r1      r11 = 0x00000000  NZCV = 0010
  subs r11, r1, r1     r11 = 0x00000000  NZCV = 0110
Model run of groups.elf: stopped at 0x00000038: b . (a branch to itself); 14 instructions

Only two lines changed the flags: without S an instruction leaves N, Z, C and V alone, so sub r11, r1, r1 kept the compare’s 0010. subs wrote the same 0 and set Z = 1 and C = 1, no borrow: 0110. A compare is an S instruction that keeps only the flags.

Three parts follow. The first finds where C comes from after each kind of S instruction, and the 64-bit addition this breaks. The second loads other constants. movw loads 16 bits and movt the top half. The pseudo-instructionpseudo-instruction: A name an assembler accepts where an instruction goes although the instruction set has no instruction of that name: RISC-V li and la become one or more real instructions. The NASM manual also uses the word for its data lines, such as db, equ and times. More in “Assembler syntax: NASM, GNU as, Intel and AT&T” ldr rX, =value lets the assembler choose, using a literal poolWords of data that the assembler puts after the code, within reach of a PC-relative ldr, to hold constants that no single instruction can build. when it must, and adr makes an address from the pc. The third covers mla, the 64-bit long multiplies and 64-bit sums.

Practise

Work each one out on paper from the rules and the runs above; with LLVM installed (toolchain setup), llvm-mc shows whether a changed line assembles:

1. In shifts.s, make the first add use lsl #2 and work out r12.
2. Give r4 the value 5 × 31 with a single rsb.
3. In groups.s, swap the operands of the cmp: which flags does it leave?

The exercise turns the rule for immediates into code.

def encode(value):
    """(imm8, rotation) with value == imm8 rotated right by 2 * rotation, the smallest rotation; None if none fits."""
    return None  # replace with your code


def mov_or_mvn(value):
    """("mov", imm8, rotation) or ("mvn", imm8, rotation) for one instruction that loads value; None if neither fits."""
    return None  # replace with your code

"""Sample tests: constants from the lesson's runs and listings, plus a few edges."""

from immediates import encode, mov_or_mvn


def test_small_values_need_no_rotation():
    assert encode(5) == (5, 0)
    assert encode(0) == (0, 0)
    assert encode(0xFF) == (0xFF, 0)


def test_recorded_mov_of_0xff000000():
    assert encode(0xFF000000) == (0xFF, 4)


def test_values_eight_and_sixteen_places_up():
    assert encode(0x5A00) == (0x5A, 12)
    assert encode(0xFF00) == (0xFF, 12)


def test_a_value_that_wraps_round_bit_31():
    assert encode(0xF000000F) == (0xFF, 2)


def test_rotation_15_shifts_left_by_two():
    assert encode(0x3FC) == (0xFF, 15)
    assert encode(0x104) == (0x41, 15)


def test_the_smallest_rotation_wins():
    assert encode(0x10) == (0x10, 0)
    assert encode(0x40000000) == (0x01, 1)


def test_constants_no_rotated_immediate_holds():
    assert encode(0x101) is None          # bits 0 and 8, nine places apart
    assert encode(0x1004) is None         # bits 12 and 2
    assert encode(0x12345678) is None
    assert encode(0x1FE) is None          # eight bits wide, but it would need an odd rotation


def test_mov_when_the_value_fits():
    assert mov_or_mvn(0xFF000000) == ("mov", 0xFF, 4)


def test_mvn_when_the_complement_fits():
    assert mov_or_mvn(0xFFFFFFF0) == ("mvn", 15, 0)       # mvn r6, #15 in shifts.s
    assert mov_or_mvn(0xFFFFFF00) == ("mvn", 0xFF, 0)
    assert mov_or_mvn(0x7FFFFFFF) == ("mvn", 0x02, 1)     # NOT 0x80000000
    assert mov_or_mvn(0xFFFFFFFF) == ("mvn", 0, 0)


def test_neither_form():
    assert mov_or_mvn(0x101) is None
    assert mov_or_mvn(0x12345678) is None

The questions start from the section your checkpoint answers left weakest.

Where C comes from after an S instruction, and a carry chain it breaks Pro: opens with a Pro, Premium or Ultimate pass

Any 32-bit constant: four ways to load it, and what each one costs Pro: opens with a Pro, Premium or Ultimate pass

Multiplies, multiplying by constants and 64-bit sums, with lab numbers Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

What does the barrel shifter add to an A32 data-processing instruction, and what does it cost?

It shifts or rotates the second operand before the ALU uses it, in the same instruction: add r1, r2, r3, lsl #3 adds r3 × 8 to r2. The amount is a constant or a register’s bottom byte, rrx rotates through C, and an immediate is a byte rotated right by an even amount. The shifted register keeps its value. No extra instruction is needed; the cost is encoding space, which is why immediates are only rotated bytes.

Three harder ones follow: a 64-bit counter that loses counts, constants for two cores, and multiplying with no mul.

Key takeaways

• The barrel shifter shifts or rotates the second operand of A32 data processing instructions on the way into the ALU, so one add multiplies by 9.
• Operand2 is a rotated immediate, a register, or a register shifted by a constant, by another register’s bottom byte, or by rrx.
• An immediate is an 8-bit value rotated right by twice a 4-bit field, so the field 0x4FF stands for 0xFF000000.
• Without S an instruction leaves the flags alone; with S it sets N and Z from its result, and a compare is an S instruction that keeps only the flags.