Simplified Decoding Logic

Read time: 9 minutes (2496 words)

Obviously, the designers of the machine put a lot of thought into how they encoded instructions. They needed to conserve the number of bits needed for an instruction, and not make the decoding logis too complicated. HDL languages like Verilog make the actual construction of a decoder pretty simple, but it ends up looking like a giant switch statement anyway.

We ned to build the decoding logic, and not get overwhelmed by the aountof code it takes, so let’s see if we can come up with somehting reasonably simple.

Instruction Identification

First, looking over the basic encoding we showed earlier, it is apparent that we can use a simple scheme to identify each instruction.

If we create a mask bitset 16-bits wide for each instructuin, we can strip off all bits exceot the bits that actually encode a single instruction. We can then check the resulting value to see if we match a known instruction.

We can do this by creating two arrays of uint16_t data:

mask.h
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
uint16_t mask[] = {
    0b1111111111111111,     // nop
    0b1111110000000000,     // add
    0b1111110000000000,     // cp
    0b1111110000000000,     // sub
    0b1111110000000000,     // and
    0b1111110000000000,     // or
    0b1111110000000000,     // mov
    0b1111110000000000,     // eor
    0b1111000000000000,     // subi
    0b1111000000000000,     // ori
    0b1111000000000000,     // andi
    0b1111111000001111,     // inc
    0b1111111000001111,     // lsr
    0b1111111000001111,     // dec
    0b1111111111111111,     // cli
    0b1111111000001111,     // lds
    0b1111111000001111,     // sts
    0b1111111000001111,     // com
    0b1111111100000000,     // cbi
    0b1111111100000000,     // sbi
    0b1111111111111111,     // sei
    0b1111111111111111,     // ret
    0b1111111111111111,     // reti
    0b1111111000001111,     // push
    0b1111111000001111,     // pop
    0b1111100000000000,     // in
    0b1111100000000000,     // out
    0b1111000000000000,     // rjmp
    0b1111000000000000,     // rcall
    0b1111111000001000,     // sbrs
    0b1111110000000111,     // breq
    0b1111110000000111      // brne
};
mask.h
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
uint16_t val[] = {
    0b0000000000000000,     // nop
    0b0000110000000000,     // add
    0b0001010000000000,     // cp
    0b0001100000000000,     // sub
    0b0010000000000000,     // and
    0b0010100000000000,     // or
    0b0010110000000000,     // mov
    0b0010010000000000,     // eor
    0b0101000000000000,     // subi
    0b0110000000000000,     // ori
    0b0111000000000000,     // andi
    0b1001010000000011,     // inc
    0b1001010000000110,     // lsr
    0b1001010000001010,     // dec
    0b1001010011111000,     // cli
    0b1001000000000000,     // lds
    0b1001001000000000,     // sts
    0b1001010000000000,     // com
    0b1001100000000000,     // cbi
    0b1001101000000000,     // sbi
    0b1001010001111000,     // sei
    0b1001010100001000,     // ret
    0b1001010100011000,     // reti
    0b1001001000001111,     // push
    0b1001000000001111,     // pop
    0b1011000000000000,     // in
    0b1011100000000000,     // out
    0b1100000000000000,     // rjmp
    0b1101000000000000,     // rcall
    0b1111111000000000,     // sbrs
    0b1111000000000001,     // breq
    0b1111010000000001      // brne
};

Finally, here is a table of opcodes matching each bit pattern:

mask.h
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
std::string opcodes[] = {
    "nop",
    "add",
    "cp",
    "sub",
    "and",
    "or",
    "mov",
    "eor",
    "subi",
    "ori",
    "andi",
    "inc",
    "lsr",
    "dec",
    "cli",
    "lds",
    "sts",
    "com",
    "cbi",
    "sbi",
    "sei",
    "ret",
    "reti",
    "push",
    "pop",
    "in",
    "out",
    "rjmp",
    "rcall",
    "sbrs",
    "breq",
    "brne"
};

This is a lot of code. However, the basic decoding logic looks like this:

Operand Identification

With the instructions identified, we still have the problem of extracting the operands. This is a bit of a mess, since the operands are not nicely placed in the instruction. Some are split into two separate fields.

All in all, there are 13 patterns found in the instructions we are considering:

Group Pattern 2nd opc operands
0 xxxxxxxxxxxxxxxx   no operands
1 xxxxxxrdddddrrrr   Rd, Rr
2 xxxxkkkkddddkkkk   Rd, k
3 xxxxxxxdddddxxxx   Rd
4 xxxxxxxdddddxxxx k16 Rd [k16]
5 xxxxxxxrrrrrxxxx k16 [k], Rr
6 xxxxxxxxAAAAAbbb   A,b
7 xxxxxxxrrrrrxxxx   Rr
8 xxxxxAAdddddAAAA   Rd, A
9 xxxxxAArrrrrAAAA   A, Rr
10 xxxxkkkkkkkkkkkk   k
11 xxxxxxxrrrrrxbbb   Rr, b
12 xxxxxxkkkkkkkxxx   k

Note

In this table, we will be checking exact matches on all bits where a “x” is shown, that happens in instruction matching above. Group 0 is an exact match encoding.

Breaking out each of these is a bit messy. Four of these groups are pretty simple, since they contain one operand, and all the bits are grouped together.

Of the remaining, all have two operands, and most have the bit fields split up.

UGH!

Single operand decoding

For each group, we need a mask to clear of the unneeded bits, then a shift value ot move them into the right position to be treated as a simple integer number.

Here is the operand mask table for each group:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
uint16_t oprmask[] = {
    0b1111111111111111,     // group 0  - no operands
    0b0000001111111111,     // group 1  - Rd, Rr
    0b0000111111111111,     // group 2  - Rd, k
    0b0000000111110000,     // group 3  - Rd
    0b0000000111110000,     // group 4  - Rd, [k16]
    0b0000011111111111,     // group 5  - [k16], Rr
    0b0000000011111111,     // group 6  - A, b
    0b0000011111111111,     // group 7  - Rr
    0b0000111111111111,     // group 8  - Rd, A
    0b0000000111110111,     // group 9  - A, Rd
    0b0000001111111000,     // group 10 - k
    0b0000001111111000,     // group 11 - Rr, b
    0b0000001111111000      // group 12 - k
};

We use a simple table to assign a group number of each instruction:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
int groups[] = {
    0,              // nop
    1,              // add
    1,              // cp 
    1,              // sub
    1,              // and
    1,              // or 
    1,              // mov
    1,              // eor
    2,              // subi
    2,              // ori
    2,              // andi
    3,              // inc
    3,              // lsr
    3,              // dec
    0,              // cli
    4,              // lds
    5,              // sts
    3,              // com
    7,              // cbi
    7,              // sbi
    0,              // sei
    0,              // ret
    0,              // reti
    7,              // push
    3,              // pop
    8,              // in 
    9,              // out
    10,             // rjmp
    10,             // rcall
    11,             // sbrs
    12,             // breq
    12              // brne
};

With this data, we can set up the basic switch statement we will use to break out the operands.

Here is the full decoder, minus the operand decode logic.

decode.cpp
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <iostream>
#include <cstdint>

#include "mask.h"

std::string opcode;
int opcode_num;

// operand fields
uint16_t k;
uint8_t d,r;
uint8_t b;
uint8_t A;
int num_operands = 0;

std::string decoder(uint16_t op) {
    for(int i = 0; i<32; i++) { 
        if((op & mask[i]) == val[i]) {
            opcode = opcodes[i];
            opcode_num = i;
            break;
        }
        opcode = "unknown";
    }
    return opcode;
}
    
std::string decode_operands(uint16_t op) {
    uint16_t opr_bits;
    std::string result, opr1, opr2;

    int group = groups[opcode_num];
    opr_bits = op & oprmask[group];

    switch(group) {
        case 0:
            num_operands = 0;
            break;
        case 1:
            num_operands = 2;
            opr1 = "Rd";
            opr2 = "Rr";
            break;
        case 2:
            num_operands = 2;
            opr1 = "Rd";
            opr2 = "k";
            break;
        case 3:
            num_operands = 1;
            opr1 = "Rd";
            break;
        case 4:
            num_operands = 2;
            opr1 = "Rr";
            opr2 = "[k]";
            break;
        case 5:
            num_operands = 2;
            opr1 = "[k]";
            opr2 = "Rr";
            break;
        case 6:
            num_operands = 2;
            opr1 = "A";
            opr2 = "b";
            break;
        case 7:
            num_operands = 1;
            opr1 = "Rr";
            break;
        case 8:
            num_operands = 2;
            opr1 = "Rd";
            opr2 = "A";
            break;
        case 9:
            num_operands = 2;
            opr1 = "A";
            opr2 = "Rr";
            break;
        case 10:
            num_operands = 1;
            opr1 = "k";
            break;
        case 11:
            num_operands = 2;
            opr1 = "Rr";
            opr2 = "b";
            break;
        case 12:
            num_operands = 1;
            opr1 = "k";
            break;
    }
    result = "";
    if(num_operands > 0)
        result += opr1;
    if(num_operands > 1)
        result += " " + opr2;
    return result;
}

int main(void) {
    uint16_t op;
    std::string opcode;
    std::cout << "Decoder test" << std::endl;
    for(int i = 0; i<32; i++) {
        op = val[i];
        opcode = decoder(op);
        std::cout << "Opcode = " << opcode
        << " "
        << decode_operands(op)
        << std::endl;

    }
}