# Binary instruction decoder tutorial

The objectives of this tutorial are:

- Learn the structure and syntax of the binary format description file.
- Learn how the binary format description matches up with the ISA description.
- Write the binary descriptions for the RiscV RV32I subset of instructions.

*** ** * ** ***

## Overview

### RiscV binary instruction encoding

Binary instruction encoding is the standard way to encode instructions for
execution on a microprocessor. They are normally stored in an executable file,
usually in the ELF format. Instructions can be either fixed width or variable
width.

Typically, instructions use a small set of encoding formats, with each format
customized for the type of instructions encoded. For instance, register-register
instructions may use one format that maximizes the number of available opcodes,
while register-immediate instructions use another that trades off the number of
available opcodes for increasing the size of the immediate that can be encoded.
Branch and jump instructions almost always use formats that maximize the size of
the immediate in order to support branches with larger offsets.

The instruction formats used by the instructions we want to decode in our RiscV
simulator are the following:

R-Type format, used for register-register instructions:

| 31..25 | 24..20 | 19..15 | 14..12 | 11..7 | 6..0 |
|---|---|---|---|---|---|
| 7 | 5 | 5 | 3 | 5 | 7 |
| func7 | rs2 | rs1 | func3 | rd | opcode |

I-Type format, used for register-immediate instructions, load instructions, and
the `jalr` instruction, 12 bit immediate.

| 31..20 | 19..15 | 14..12 | 11..7 | 6..0 |
|---|---|---|---|---|
| 12 | 5 | 3 | 5 | 7 |
| imm12 | rs1 | func3 | rd | opcode |

Specialized I-Type format, used for shift with immediate instructions, 5 bit
immediate:

| 31..25 | 24..20 | 19..15 | 14..12 | 11..7 | 6..0 |
|---|---|---|---|---|---|
| 7 | 5 | 5 | 3 | 5 | 7 |
| func7 | uimm5 | rs1 | func3 | rd | opcode |

U-Type format, used for long immediate instructions (`lui`, `auipc`), 20 bit
immediate:

| 31..12 | 11..7 | 6..0 |
|---|---|---|
| 20 | 5 | 7 |
| uimm20 | rd | opcode |

B-Type format, used for conditional branches, 12-bit immediate.

| 31 | 30..25 | 24..20 | 19..15 | 14..12 | 11..8 | 7 | 6..0 |
|---|---|---|---|---|---|---|---|
| 1 | 6 | 5 | 5 | 3 | 4 | 1 | 7 |
| imm | imm | rs2 | rs1 | func3 | imm | imm | opcode |

J-Type format, used for the `jal` instruction, 20 bit immediate.

| 31 | 30..21 | 20 | 19..12 | 11..7 | 6..0 |
|---|---|---|---|---|---|
| 1 | 10 | 1 | 8 | 5 | 7 |
| imm | imm | imm | imm | rd | opcode |

S-Type format, used for store instructions, 12 bit immediate.

| 31..25 | 24..20 | 19..15 | 14..12 | 11..7 | 6..0 |
|---|---|---|---|---|---|
| 7 | 5 | 5 | 3 | 5 | 7 |
| imm | rs2 | rs1 | func3 | imm | opcode |

As you can see from these formats, all these instructions are 32 bits long, and
the low 7 bits in each format is the opcode field. Also notice that while
several formats have the same size immediates, their bits are taken from
different parts of the instruction. As we will see, the binary decoder
specification format is able to express this.

### Binary encoding description

The binary encoding of the instruction is expressed in the binary format
(`.bin_fmt`) description file. It describes the binary encoding of the
instructions in an ISA so that a binary format instruction decoder can be
generated. The generated decoder determines the opcode, extracts the value of
operand and immediate fields, in order to provide information needed by the ISA
encoding-agnostic decoder described in the previous tutorial.

In this tutorial we will write a binary encoding description file for a subset
of the RiscV32I instructions necessary to simulate the instructions used in a
small "Hello World" program. For more details on the RiscV ISA see
[Risc-V Specifications](https://riscv.org/technical/specifications/){.external}.

> [!NOTE]
> **Note:** Only the instructions that are actually used by the executable will be added in this tutorial. Any other instructions are left as an exercise to the enthusiastic reader.

Start by opening up the file:
`riscv_bin_decoder/riscv32i.bin_fmt`.

The content of the file is broken into several sections.

First, is the `decoder` definition.

    decoder RiscV32I {
      // The namespace in which code will be generated.
      namespace mpact::sim::codelab;
      // The name (including any namespace qualifiers) of the opcode enum type.
      opcode_enum = "OpcodeEnum";
      // Include files specific to this decoder.
      includes {
        #include "riscv_isa_decoder/solution/riscv32i_decoder.h"
      }
      // Instruction groups for which to generate decode functions.
      RiscVInst32;
    };

Our decoder definition specifies the name of our decoder `RiscV32I`, as well as
four additional pieces of information. The first is `namespace`, which defines
the namespace in which the generated code will be placed. Second, the
`opcode_enum`, which names how the opcode enumeration type that is generated
by the ISA decoder should be referenced within the generated code. Third,
`includes {}` specifies include files necessary for the code generated for
this decoder.
In our case, this is the file that is produced by the ISA decoder from the
previous tutorial.
Additional include files can be specified in a globally scoped `includes {}`
definition. This is useful if multiple decoders are defined, and they all need
to include some of the same files. Fourth is a list of names of instruction
groups that make up the instructions for which the decoder is generated. In our
case there is only one: `RiscVInst32`.

> [!NOTE]
> **Note:** The `riscv32i_decoder.h` file is a generated file and therefore not checked into the repository. It is generated during the build.

Next there are three format definitions. These represent different instruction
formats for a 32-bit instruction word used by the instructions already defined
in the file.

    // The generic RiscV 32 bit instruction format.
    format Inst32Format[32] {
      fields:
        unsigned bits[25];
        unsigned opcode[7];
    };

    // RiscV 32 bit instruction format used by a number of instructions
    // needing a 12 bit immediate, including CSR instructions.
    format IType[32] : Inst32Format {
      fields:
        signed imm12[12];
        unsigned rs1[5];
        unsigned func3[3];
        unsigned rd[5];
        unsigned opcode[7];
    };

    // RiscV instruction format used by fence instructions.
    format Fence[32] : Inst32Format {
      fields:
        unsigned fm[4];
        unsigned pred[4];
        unsigned succ[4];
        unsigned rs1[5];
        unsigned func3[3];
        unsigned rd[5];
        unsigned opcode[7];
    };

The first defines a 32 bit wide instruction format named `Inst32Format` that has
two fields: `bits` (25 bits wide) and `opcode` (7 bits wide). Each field is
`unsigned`, meaning that the value will be zero-extended when it is extracted
and placed in a C++ integer type. The sum of the widths of the bitfields must
equal the width of the format. The tool will generate an error if there is a
disagreement. This format does not derive from any other format, so it is
considered a *top level format*.

The second defines a 32 bit wide instruction format named `IType` that derives
from `Inst32Format`, making these two formats *related* . The format contains 5
fields: `imm12`, `rs1`, `func3`, `rd` and `opcode`. The `imm12` field is
`signed`, which means that the value will be sign-extended when the value is
extracted and placed in a C++ integer type. Note that `IType.opcode` both has
the same signed/unsigned attribute and refers to the same instruction word bits
as `Inst32Format.opcode`.

The third format is a custom format that is only used by the `fence`
instruction, which is an instruction that is already specified and we don't have
to worry about in this tutorial.

Key point: Reuse field names in different *related* formats as long as they
represent the same bits and have the same signed/unsigned attribute.

After the format definitions in `riscv32i.bin_fmt` comes an instruction group
definition. All instructions in an instruction group must have the same
bit-length, and use a format that derives (perhaps indirectly) from the same
top level instruction format. When an ISA can have instructions with different
lengths, a different instruction group is used for each length. Additionally,
if the target ISA decoding depends on an execution mode, such as Arm vs. Thumb
instructions, a separate instruction group is required for each mode. The
`bin_fmt` parser generates a binary decoder for each instruction group.

    instruction group RiscV32I[32] "OpcodeEnum" : Inst32Format {
      fence   : Fence  : func3 == 0b000, opcode == 0b000'1111;
      csrs    : IType  : func3 == 0b010, rs1 != 0, opcode == 0b111'0011;
      csrw_nr : IType  : func3 == 0b001, rd == 0,  opcode == 0b111'0011;
      csrs_nw : IType  : func3 == 0b010, rs1 == 0, opcode == 0b111'0011;
    };

The instruction group defines a name `RiscV32I`, a width `[32]`, the name of
the opcode enumeration type to use `"OpcodeEnum"`, and a base instruction
format. The opcode enumeration type should be the same as produced by the
format independent instruction decoder covered in the tutorial on the ISA
decoder.

Each instruction encoding description consists of 3 parts:

- The opcode name, which must be the same as was used in the instruction decoder description for the two to work together.
- The instruction format to use for the opcode. This is the format that is used to satisfy references to bitfields in the final part.
- A comma separated list of bit field constraints, `==`, `!=`, `<`, `<=`, `>`, and `>=` that all must be true for the opcode to successfully *match* the instruction word.

The `.bin_fmt` parser uses all this information to build a decoder that:

- Provides extraction functions (signed/unsigned) as appropriate for each bit field in every format. The extractor functions are placed in namespaces named by the snake-case version of the format name. For instance, the extractor functions for format `IType` are placed in namespace `i_type`. Each extractor function is declared `inline`, takes the narrowest `uint_t` type that holds the width of the format, and returns the narrowest `int_t` (for signed), `uint_t` (for unsigned) type, that holds the extracted field width. E.g.:

    inline uint8_t ExtractOpcode(uint32_t value) {
      return value & 0x7f;
    }

- A decode function for each instruction group. It returns a value of type `OpcodeEnum`, and takes the narrowest `uint_t` type that holds the width of the instruction group format.

*** ** * ** ***

## Perform initial build

Change directory to `riscv_bin_decoder` and build the project using the
following command:

    $ cd riscv_bin_decoder
    $ bazel build :all

Now change your directory back to the repository root, then let's take a look
at the sources that were generated. For that, change directory to
`bazel-out/k8-fastbuild/bin/riscv_bin_decoder` (assuming you are on an x86
host - for other hosts, the k8-fastbuild will be another string).

    $ cd ..
    $ cd bazel-out/k8-fastbuild/bin/riscv_bin_decoder

- `riscv32i_bin_decoder.h`
- `riscv32i_bin_decoder.cc`

### The generated header file (.h)

Open up `riscv32i_bin_decoder.h`. The first part of the file contains standard
boilerplate guards, include files, namespace declarations. Following that
there is a templated helper function in namespace `internal`. This function
is used to extract bit fields from formats too long to fit in a 64-bit C++
integer.

    #ifndef RISCV32I_BIN_DECODER_H
    #define RISCV32I_BIN_DECODER_H

    #include <iostream>
    #include <cstdint>

    #include "third_party/absl/functional/any_invocable.h"


    #include "learning/brain/research/mpact/sim/codelab/riscv_isa_decoder/solution/riscv32i_decoder.h"

    namespace mpact {
    namespace sim {
    namespace codelab {


    namespace internal {

    template <typename T>
    static inline T ExtractBits(const uint8_t *data, int data_size,
                                int bit_index, int width) {
      if (width == 0) return 0;

      int byte_pos = bit_index >> 3;
      int end_byte = (bit_index + width - 1) >> 3;
      int start_bit = bit_index & 0x7;

      // If it is only from one byte, extract and return.
      if (byte_pos == end_byte) {
        uint8_t mask = 0xff >> start_bit;
        return (mask & data[byte_pos]) >> (8 - start_bit - width);
      }

      // Extract from the first byte.
      T val = 0;
      val = data[byte_pos++] & 0xff >> start_bit;
      int remainder = width - (8 - start_bit);
      while (remainder >= 8) {
        val = (val << 8) | data[byte_pos++];
        remainder -= 8;
      }

      // Extract any remaining bits.
      if (remainder > 0) {
        val <<= remainder;
        int shift = 8 - remainder;
        uint8_t mask = 0b1111'1111 << shift;
        val |= (data[byte_pos] & mask) >> shift;
      }
      return val;
    }

    }  // namespace internal

Following the initial section there is a a set of three namespaces, one for each
of the `format` declarations in the `riscv32i.bin_fmt` file:


    namespace fence {

    ...

    }  // namespace fence

    namespace i_type {

    ...

    }  // namespace i_type

    namespace inst32_format {

    ...

    }  // namespace inst32_format

Within each of these namespaces the `inline` bitfield extraction function
for each bit field in that format is defined. Additionally, the base format
duplicates extraction functions from the descendant formats for which
1) the field names only occur in a single field name, or 2) for which the
field names refer to the same type field (signed/unsigned and bit positions)
in each format they occur in. This enables bit fields that describe the same
bits to be extracted using functions in the top level format namespace.

The functions in the `i_type` namespace is shown below:

    namespace i_type {

    inline uint8_t ExtractFunc3(uint32_t value) {
      return  (value >> 12) & 0x7;
    }

    inline int16_t ExtractImm12(uint32_t value) {
      int16_t result = ( (value >> 20) & 0xfff) << 4;
      result = result >> 4;
      return result;
    }

    inline uint8_t ExtractOpcode(uint32_t value) {
      return value & 0x7f;
    }

    inline uint8_t ExtractRd(uint32_t value) {
      return  (value >> 7) & 0x1f;
    }

    inline uint8_t ExtractRs1(uint32_t value) {
      return  (value >> 15) & 0x1f;
    }

    }  // namespace i_type

Lastly, the function declaration of the decoder function for the instruction
group `RiscVInst32` is declared. It takes a 32 bit unsigned as the value of
the instruction word and returns the `OpcodeEnum` enumeration class member
that matches, or `OpcodeEnum::kNone` if there is no match.

    OpcodeEnum DecodeRiscVInst32(uint32_t inst_word);

### The generated Source File (.cc)

Now open up `riscv32i_bin_decoder.cc`. The first part of the file contains
the `#include` and namespace declarations, followed by the decoder function
declarations:

    #include "riscv32i_bin_decoder.h"

    namespace mpact {
    namespace sim {
    namespace codelab {

    OpcodeEnum DecodeRiscVInst32None(uint32_t);
    OpcodeEnum DecodeRiscVInst32_0(uint32_t inst_word);
    OpcodeEnum DecodeRiscVInst32_0_3(uint32_t inst_word);
    OpcodeEnum DecodeRiscVInst32_0_3c(uint32_t inst_word);
    OpcodeEnum DecodeRiscVInst32_0_5c(uint32_t inst_word);

The `DecodeRiscVInst32None` is used for empty decode actions, i.e., the ones
that return `OpcodeEnum::kNone`. The other three functions make up the
generated decoder. The overall decoder works in a hierarchical fashion. A set
of bits in the instruction word is computed to differentiate between
instructions or groups of instructions at the top level. The bits need not
be contiguous. The number of bits determine the size of a lookup table that
is populated with second level decoder functions. This is seen in the next
section of the file:

    absl::AnyInvocable<OpcodeEnum(uint32_t)> parse_group_RiscVInst32_0[kParseGroupRiscVInst32_0_Size] = {
        &DecodeRiscVInst32None, &DecodeRiscVInst32None,
        &DecodeRiscVInst32None, &DecodeRiscVInst32_0_3,
        &DecodeRiscVInst32None, &DecodeRiscVInst32None,

        ...

        &DecodeRiscVInst32None, &DecodeRiscVInst32None,
        &DecodeRiscVInst32None, &DecodeRiscVInst32None,
        &DecodeRiscVInst32_0_3c, &DecodeRiscVInst32None,

        ...
    };

Lastly, the decoder functions are defined:

    OpcodeEnum DecodeRiscVInst32None(uint32_t) {
      return OpcodeEnum::kNone;
    }

    OpcodeEnum DecodeRiscVInst32_0(uint32_t inst_word) {
      if ((inst_word & 0x4003) != 0x3) return OpcodeEnum::kNone;
      uint32_t index;
      index = (inst_word >> 2) & 0x1f;
      index |= (inst_word >> 7) & 0x60;
      return parse_group_RiscVInst32_0[index](inst_word);
    }

    OpcodeEnum DecodeRiscVInst32_0_3(uint32_t inst_word) {
      return OpcodeEnum::kFence;
    }

    OpcodeEnum DecodeRiscVInst32_0_3c(uint32_t inst_word) {
      if ((inst_word & 0xf80) != 0x0) return OpcodeEnum::kNone;
      return OpcodeEnum::kCsrwNr;
    }

    OpcodeEnum DecodeRiscVInst32_0_5c(uint32_t inst_word) {
      uint32_t rs1_value = (inst_word >> 15) & 0x1f;
      if (rs1_value != 0x0)
        return OpcodeEnum::kCsrs;
      if (rs1_value == 0x0)
        return OpcodeEnum::kCsrsNw;
      return OpcodeEnum::kNone;
    }

    OpcodeEnum DecodeRiscVInst32(uint32_t inst_word) {
      OpcodeEnum opcode;
      opcode = DecodeRiscVInst32_0(inst_word);
      return opcode;
    }

In this case, where there are only 4 instructions defined, there is only a
single level of decode and a very sparse lookup table. As instructions are
added, the structure of the decoder will change and the number of levels in the
decoder table hierarchy may increase.

*** ** * ** ***

## Add register-register ALU instructions

Now it's time to add some new instructions to the `riscv32i.bin_fmt` file. The
first group of instructions are register-register ALU instructions such as
`add`, `and`, etc. On RiscV32, these all use the R-type binary instruction
format:

| 31..25 | 24..20 | 19..15 | 14..12 | 11..7 | 6..0 |
|---|---|---|---|---|---|
| 7 | 5 | 5 | 3 | 5 | 7 |
| func7 | rs2 | rs1 | func3 | rd | opcode |

The first thing we need to do is to add the format. Go ahead and open up
`riscv32i.bin_fmt` in your favorite editor. Right after the `Inst32Format` lets
add a format called `RType` which derives from `Inst32Format`. All the bitfields
in `RType` are `unsigned`. Use the names, bit width, and order (left to right)
from the table above to define the format. If you need a hint, or want to see
the full solution,
[click here](https://github.com/google/mpact-sim-codelabs/blob/main/riscv_bin_decoder/solution/riscv32i.bin_fmt).

Next we need to add the instructions. The instructions are:

- `add` - integer add.
- `and` - bitwise and.
- `or` - bitwise or.
- `sll` - shift left logical.
- `sltu` - set less-than, unsigned.
- `sub` - integer subtract.
- `xor` - bitwise xor.

Their encodings are:

| 31..25 | 24..20 | 19..15 | 14..12 | 11..7 | 6..0 | opcode name |
|---|---|---|---|---|---|---|
| 000 0000 | rs2 | rs1 | 000 | rd | 011 0011 | add |
| 000 0000 | rs2 | rs1 | 111 | rd | 011 0011 | and |
| 000 0000 | rs2 | rs1 | 110 | rd | 011 0011 | or |
| 000 0000 | rs2 | rs1 | 001 | rd | 011 0011 | sll |
| 000 0000 | rs2 | rs1 | 011 | rd | 011 0011 | sltu |
| 010 0000 | rs2 | rs1 | 000 | rd | 011 0011 | sub |
| 000 0000 | rs2 | rs1 | 100 | rd | 011 0011 | xor |
| func7 |   |   | func3 |   | opcode |   |

Add these instruction definitions before the other instructions in the
`RiscVInst32` instruction group. Binary strings are specified with a leading
prefix of `0b` (similar to `0x` for hexadecimal numbers). To make it easier to
read long strings of binary digits, you may also insert the single quote `'` as
a digit separator where you see fit.

Each of these instruction definitions will have three constraints, namely on
`func7`, `func3`, and `opcode`. For all but `sub`, the `func7` constraint will
be:

    func7 == 0b000'0000

The `func3` constraint varies across most of the instructions. For `add` and
`sub` it is:

    func3 == 0b000

The `opcode` constraint is the same for each of these instructions:

    opcode == 0b011'0011

Remember to terminate each line with a semicolon `;`.

The finished solution is
[here](https://github.com/google/mpact-sim-codelabs/blob/main/riscv_bin_decoder/solution/riscv32i.bin_fmt).

> [!NOTE]
> **Note:** If you copy files from the solution, remove the `solution/` part of the `#include` file directives in the copied files prior to building in the current directory.

Now go ahead and build your project as previously, and open up the generated
`riscv32i_bin_decoder.cc` file. You will see that additional decoder functions
have been generated to handle the new instructions. For the most part they are
similar to the ones that had been generated before, but look at
`DecodeRiscVInst32_0_c` which is used for `add`/`sub` decode:

    OpcodeEnum DecodeRiscVInst32_0_c(uint32_t inst_word) {
      static constexpr OpcodeEnum opcodes[2] = {
        OpcodeEnum::kAdd,
        OpcodeEnum::kSub,
      };
      if ((inst_word & 0xbe000000) != 0x0) return OpcodeEnum::kNone;
      uint32_t index;
      index = (inst_word >> 30) & 0x1;
      return opcodes[index];
    }

In this function there is a static decode table generated, and a lookup value is
extracted from the instruction word to select the appropriate index. This adds a
second layer in the instruction decoder hierarchy, but since the opcode can be
looked up directly in a table without further comparisons, it is inlined in this
function as opposed to requiring another function call.

*** ** * ** ***

## Add ALU instructions with immediates

The next set of instructions we will add are ALU instructions that use an
immediate value instead of one of the registers. There are three groups of these
instructions (based on the immediate field): the I-Type immediate instructions
with a 12 bit signed immediate, the specialized I-Type immediate instructions
for shifts, and the U-Type immediate, with a 20-bit unsigned immediate value.
The formats are shown below:

The I-Type immediate format:

| 31..20 | 19..15 | 14..12 | 11..7 | 6..0 |
|---|---|---|---|---|
| 12 | 5 | 3 | 5 | 7 |
| imm12 | rs1 | func3 | rd | opcode |

The specialized I-Type immediate format:

| 31..25 | 24..20 | 19..15 | 14..12 | 11..7 | 6..0 |
|---|---|---|---|---|---|
| 7 | 5 | 5 | 3 | 5 | 7 |
| func7 | uimm5 | rs1 | func3 | rd | opcode |

The U-Type immediate format:

| 31..12 | 11..7 | 6..0 |
|---|---|---|
| 20 | 5 | 7 |
| uimm20 | rd | opcode |

The I-Type format already exists in `riscv32i.bin_fmt`, so there is no need to
add that format.

If we compare the specialized I-Type format to the R-Type format we defined in
the previous exercise, we see that the only difference is that the `rs2` fields
is renamed to `uimm5`. Instead of adding a whole new format we can augment the
R-Type format. We can't add another field, as that would increase the width of
the format, but we can add an *overlay* . An *overlay* is an alias for a set of
bits in the format, and can be used to combine multiple subsequences of the
format into a separate named entity. The side-effect is that the generated code
will now also include an extraction function for the overlay, in addition to
those for the fields. In this case, when both `rs2` and `uimm5` are unsigned it
doesn't make much difference except to make it explicit that the field is used
as an immediate. To add an overlay named `uimm5` to the R-Type format, add the
following after the last field:

      overlays:
        unsigned uimm5[5] = rs2;

The only new format we need to add is the U-Type format. Before we add the
format, let's consider the two instructions that use that format: `auipc` and
`lui`. Both of these shift the 20-bit immediate value left by 12 before using it
to either adding the pc to it (`auipc`) or write it directly to a register
(`lui`). Using an overlay we can provide a pre-shifted version of the immediate,
shifting a little bit of computation from instruction execution to instruction
decode. First add the format according to the fields specified in the table
above. Then we can add the following overlay:

      overlays:
        unsigned uimm32[32] = uimm20, 0b0000'0000'0000;

The overlay syntax allows us to concatenate, not only fields, but literals as
well. In this case we concatenate it with 12 zeros, in effect shifting it left
by 12.

The I-Type instructions we need to add are:

- `addi` - Add immediate.
- `andi` - Bitwise and with immediate.
- `ori` - Bitwise or with immediate.
- `xori` - Bitwise xor with immediate.

Their encodings are:

| 31..20 | 19..15 | 14..12 | 11..7 | 6..0 | opcode_name |
|---|---|---|---|---|---|
| imm12 | rs1 | 000 | rd | 001 0011 | addi |
| imm12 | rs1 | 111 | rd | 001 0011 | andi |
| imm12 | rs1 | 110 | rd | 001 0011 | ori |
| imm12 | rs1 | 100 | rd | 001 0011 | xori |
|   |   | func3 |   | opcode |   |

The R-Type (specialized I-Type) instructions we need to add are:

- `slli` - Shift left logical by immediate.
- `srai` - Shift right arithmetic by immediate.
- `srli` - Shift right logical by immediate.

Their encodings are:

| 31..25 | 24..20 | 19..15 | 14..12 | 11..7 | 6..0 | opcode name |
|---|---|---|---|---|---|---|
| 000 0000 | uimm5 | rs1 | 001 | rd | 001 0011 | slli |
| 010 0000 | uimm5 | rs1 | 101 | rd | 001 0011 | srai |
| 000 0000 | uimm5 | rs1 | 101 | rd | 001 0011 | srli |
| func7 |   |   | func3 |   | opcode |   |

The U-Type instructions we need to add are:

- `auipc` - Add upper immediate to pc.
- `lui` - Load upper immediate.

Their encodings are:

| 31..12 | 11..7 | 6..0 | opcode name |
|---|---|---|---|
| uimm20 | rd | 001 0111 | auipc |
| uimm20 | rd | 011 0111 | lui |
|   |   | opcode |   |

Go ahead and make the changes and then build. Check the generated output. Just
as previously, you can check your work against
[riscv32i.bin_fmt](https://github.com/google/mpact-sim-codelabs/blob/main/riscv_bin_decoder/solution/riscv32i.bin_fmt).

> [!NOTE]
> **Note:** If you copy files from the solution, remove the `solution/` part of the `#include` file directives in the copied files prior to building in the current directory.

*** ** * ** ***

## Add branch and jump-and-link instructions

The next set of instructions that need to be defined are the conditional branch
instructions, the jump-and-link instruction, and the jump-and-link register
instruction.

The conditional branches we are adding all use the B-Type encoding.

| 31..25 | 24..20 | 19..15 | 14..12 | 11..7 | 6..0 |
|---|---|---|---|---|---|
| 7 | 5 | 5 | 3 | 5 | 7 |
| imm7 | rs2 | rs1 | func3 | imm5 | opcode |

While the B-Type encoding is identical in layout to the R-Type encoding, we
choose to use a new format type for it to align with the RiscV documentation.
But you could also just have added an overlay to get the appropriate branch
displacement immediate out, using the `func7` and `rd` fields of the R-Type
encoding.

Adding a format `BType` with the fields as specified above is necessary, but not
sufficient. As you can see, the immediate is split over two instruction fields.
Moreover, the branch instructions do not treat this as a simple concatenation of
the two fields. Instead, each field is further partitioned, and these partitions
are concatenated in a different order. Finally, that value is shifted left by
one to obtain a 16-bit aligned offset.

The sequence of bits in the instruction word used to form the immediate are: 31,
7, 30..25, 11..8. This corresponds to the following sub-field references, where
the index or range specify the bits in the field, numbered right to left, i.e.,
`imm7[6]` refers to the msb of `imm7`, and `imm5[0]` refers to the lsb of
`imm5`.

    imm7[6], imm5[0], imm7[5..0], imm5[4..1]

Making this bit manipulation part of the branch instructions themselves have two
big drawbacks. First, it ties the implementation of the semantic function to
details in the binary instruction representation. Second, it adds more run-time
overhead. The answer is to add an overlay to the `BType` format, including a
trailing '0' to account for the left shift.

      overlays:
        signed b_imm[13] = imm7[6], imm5[0], imm7[5..0], imm5[4..1], 0b0;

Notice that the overlay is signed, so it will be automatically sign-extended
when it is extracted from the instruction word.

The jump-and-link (immediate) instruction uses the J-Type encoding:

| 31..12 | 11..7 | 6..0 |
|---|---|---|
| 20 | 5 | 7 |
| imm20 | rd | opcode |

This is also an easy format to add, but again, the immediate that is used by the
instruction is not as straightforward as it seems. The bit sequences used to
form the full immediate are: 31, 19..12, 20, 30..21, and the final immediate is
shifted left by one for half word alignment. The solution is to add another
overlay (21 bits to account for the left shift) to the format:

      overlays:
        signed j_imm[21] = imm20[19, 7..0, 8, 18..9], 0b0;

As you can see, the syntax for overlays support specifying multiple ranges in a
field in a shorthand format. Additionally, if no field name is used, the bit
numbers refer to the instruction word itself, so the above could just as well be
written as:

        signed j_imm[21] = [31, 19..12, 20, 30..21], 0b0;

Finally, the jump-and-link (register) uses the I-type format as used
previously.

The I-Type immediate format:

| 31..20 | 19..15 | 14..12 | 11..7 | 6..0 |
|---|---|---|---|---|
| 12 | 5 | 3 | 5 | 7 |
| imm12 | rs1 | func3 | rd | opcode |

This time, there is no change that has to be made to the format.

The branch instructions we need to add, are:

- `beq` - Branch if equal.
- `bge` - Branch if greater than or equal.
- `bgeu` - Branch if greater than or equal unsigned.
- `blt` - Branch if less than.
- `bltu` - Branch if less than unsigned.
- `bne` - Branch if not equal.

They are encoded as follows:

| 31..25 | 24..20 | 19..15 | 14..12 | 11..7 | 6..0 | opcode name |
|---|---|---|---|---|---|---|
| imm7 | rs2 | rs1 | 000 | imm5 | 110 0011 | beq |
| imm7 | rs2 | rs1 | 101 | imm5 | 110 0011 | bge |
| imm7 | rs2 | rs1 | 111 | imm5 | 110 0011 | bgeu |
| imm7 | rs2 | rs1 | 100 | imm5 | 110 0011 | blt |
| imm7 | rs2 | rs1 | 110 | imm5 | 110 0011 | bltu |
| imm7 | rs2 | rs1 | 001 | imm5 | 110 0011 | bne |
|   |   |   | func3 |   | opcode |   |

The `jal` instruction is encoded as follows:

| 31..12 | 11..7 | 6..0 | opcode name |
|---|---|---|---|
| imm20 | rd | 110 1111 | jal |
|   |   | opcode |   |

The `jalr` instruction is encoded as follows:

| 31..20 | 19..15 | 14..12 | 11..7 | 6..0 | opcode_name |
|---|---|---|---|---|---|
| imm12 | rs1 | 000 | rd | 110 0111 | jalr |
|   |   | func3 |   | opcode |   |

Go ahead and make the changes and then build. Check the generated output. Just
as previously, you can check your work against
[riscv32i.bin_fmt](https://github.com/google/mpact-sim-codelabs/blob/main/riscv_bin_decoder/solution/riscv32i.bin_fmt).

> [!NOTE]
> **Note:** If you copy files from the solution, remove the `solution/` part of the `#include` file directives in the copied files prior to building in the current directory.

*** ** * ** ***

## Add store instructions

The store instructions use the S-Type encoding, which is identical to the B-Type
encoding used by branch instructions, except for the composition of the
immediate. We choose to add the `SType` format to remain aligned with the RiscV
documentation.

| 31..25 | 24..20 | 19..15 | 14..12 | 11..7 | 6..0 |
|---|---|---|---|---|---|
| 7 | 5 | 5 | 3 | 5 | 7 |
| imm7 | rs2 | rs1 | func3 | imm5 | opcode |

In the case of the `SType` format, the immediate is thankfully a straight
forward concatenation of the two immediate fields, so the overlay specification
is simply:

      overlays:
        signed s_imm[12] = imm7, imm5;

Note that no bit range specifiers are required when concatenating whole fields.

The store instructions are encoded as follows:

| 31..25 | 24..20 | 19..15 | 14..12 | 11..7 | 6..0 | opcode name |
|---|---|---|---|---|---|---|
| imm7 | rs2 | rs1 | 000 | imm5 | 010 0011 | sb |
| imm7 | rs2 | rs1 | 001 | imm5 | 010 0011 | sh |
| imm7 | rs2 | rs1 | 010 | imm5 | 010 0011 | sw |
|   |   |   | func3 |   | opcode |   |

Go ahead and make the changes and then build. Check the generated output. Just
as previously, you can check your work against
[riscv32i.bin_fmt](https://github.com/google/mpact-sim-codelabs/blob/main/riscv_bin_decoder/solution/riscv32i.bin_fmt).

> [!NOTE]
> **Note:** If you copy files from the solution, remove the `solution/` part of the `#include` file directives in the copied files prior to building in the current directory.

*** ** * ** ***

## Add load instructions

The load instructions use the I-Type format. No change has to be made there.

The encodings are:

| 31..20 | 19..15 | 14..12 | 11..7 | 6..0 | opcode_name |
|---|---|---|---|---|---|
| imm12 | rs1 | 000 | rd | 000 0011 | lb |
| imm12 | rs1 | 100 | rd | 000 0011 | lbu |
| imm12 | rs1 | 001 | rd | 000 0011 | lh |
| imm12 | rs1 | 101 | rd | 000 0011 | lhu |
| imm12 | rs1 | 010 | rd | 000 0011 | lw |
|   |   | func3 |   | opcode |   |

Go ahead and make the changes and then build. Check the generated output. Just
as previously, you can check your work against
[riscv32i.bin_fmt](https://github.com/google/mpact-sim-codelabs/blob/main/riscv_bin_decoder/solution/riscv32i.bin_fmt).

> [!NOTE]
> **Note:** If you copy files from the solution, remove the `solution/` part of the `#include` file directives in the copied files prior to building in the current directory.

This concludes this tutorial, we hope it has been useful.