# 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:

 ``` 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 }; ```
 ``` 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:

 ``` 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
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 #include #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; } } ```