Calculating Jump and Branch Offsets with Byte Shifts

In computer architecture, jump and branch target offsets determine the destination address of an execution redirect relative to the current instruction pointer. This article explains how processors compute these targets in binary using Program Counter (PC) relative addressing, two’s complement signed arithmetic, and binary bit-shifting. You will learn the mathematical mechanics of encoding target locations into instruction fields and how the CPU decodes and shifts these binary offsets at runtime to navigate memory.

The Principle of PC-Relative Addressing

Modern instruction set architectures (such as ARM, MIPS, x86, and RISC-V) typically encode control-flow instructions—like conditional branches and short jumps—using PC-relative addressing. Instead of storing an absolute 32-bit or 64-bit memory address within the instruction, the processor encodes the distance (displacement) between the current Program Counter and the target address:

\[\text{Target Address} = \text{Current PC} + \text{Byte Offset}\]

(Note: Depending on the architecture, the base PC may be the address of the current instruction, or the address of the next sequential instruction, such as \(\text{PC} + 4\) in classic ARM and MIPS pipelines.)

Two’s Complement for Directionality

Branching requires moving both forward and backward in memory. To support bidirectional offsets within a fixed number of binary bits, processors represent the offset as a signed integer using two’s complement:

When the CPU decodes an immediate offset, it sign-extends the value to match the full bit-width of the register architecture (e.g., expanding a 12-bit signed immediate to 32 or 64 bits) before adding it to the PC.

Why Byte Shifts Are Used

Instruction words in RISC architectures are fixed-size and memory-aligned: * In 32-bit aligned architectures (e.g., standard ARM, MIPS, RISC-V), every instruction address is a multiple of 4 bytes. The binary representation of any valid instruction address always ends in 00 (\(2^0\) and \(2^1\) bits are always zero). * In 16-bit aligned architectures (e.g., ARM Thumb, compressed RISC-V), addresses are multiples of 2 bytes, always ending in 0.

Because the lowest bits are consistently zero, storing them in the instruction’s binary format is redundant. By omitting these trailing zeros, the instruction can encode a larger addressing range using fewer bits.

To convert this encoded instruction-count offset back into a raw byte offset, the CPU performs an arithmetic left shift (logical shift left) at execution time: * Left shift by 1 bit (<< 1): Multiplies the immediate value by 2 for 16-bit instruction alignment. * Left shift by 2 bits (<< 2): Multiplies the immediate value by 4 for 32-bit instruction alignment.

Step-by-Step Encoding and Decoding Process

1. Encoding the Branch (Assembler Step)

  1. Calculate the byte distance: Subtract the base PC from the target label address: \[\Delta\text{Bytes} = \text{Target Address} - \text{Base PC}\]
  2. Shift right to discard redundant zeros: Divide by the instruction alignment size: \[\text{Encoded Immediate} = \Delta\text{Bytes} \gg 2 \quad (\text{for 4-byte alignment})\]
  3. Store in instruction: Insert the resulting two’s complement binary value into the immediate field of the machine code.

2. Decoding and Executing the Branch (CPU Step)

  1. Extract immediate: The hardware extracts the immediate bits from the binary opcode.
  2. Sign-extend: The hardware replicates the sign bit across the full processor word length.
  3. Shift left to byte offset: The processor shifts the sign-extended value left by 2 (or 1), appending the missing zero bits: \[\text{Byte Offset} = \text{SignExtended}(\text{Encoded Immediate}) \ll 2\]
  4. Compute final PC: The hardware adder adds the byte offset to the base PC: \[\text{Next PC} = \text{Base PC} + \text{Byte Offset}\]

Concrete Binary Example

Consider a 32-bit aligned system where a branch instruction is executed: * Base PC: 0x00001000 (0001 0000 0000 0000 in binary) * Target Address: 0x00001028 (0001 0000 0010 1000 in binary)

  1. Calculate Byte Difference: \[\text{0x1028} - \text{0x1000} = +\text{0x28} \text{ (40 bytes in decimal, } \texttt{0b00101000}\text{)}\]

  2. Shift Right for Encoding (Divide by 4): \[\texttt{0b00101000} \gg 2 = \texttt{0b00001010} \text{ (10 instructions forward)}\] The assembler places 0b00001010 (decimal 10) into the instruction’s immediate field.

  3. Runtime Decoding (Hardware Left Shift): When the branch condition is met, the CPU sign-extends 0b00001010 and shifts it left by 2 bits: \[\texttt{0b00001010} \ll 2 = \texttt{0b00101000} \text{ (40 bytes)}\]

  4. Target Calculation: \[\text{0x00001000} + \text{0x00000028} = \text{0x00001028}\]

The Program Counter updates to 0x00001028, successfully completing the branch redirect.