Step 2: Decode

After we succeed in “fetching” some part of an instruction from memory, we need to verify that it is a valid instruction, and figure out if we need more data from the instruction memory. Decoding is largely just splitting up a binary bit pattern into “fields”, something you played with on the first exam lab.

Before we can actually work on the decoder, we need to explore the instructions we want to simulate. Doing that requires a look at the processor we are working with, in more detain.

Processor Data Sheet

The ATtiny85 is documented in a fairly large PDF file, called a “data sheet”! It is hardly a sheet, and much of what you find in this document is aimed at hardware designers.

For our purposes here, all we need to do is locate the instruction set summary. This is located in Chapter 24.

The table you see looks a bit scary, but after looking at a few processors, it is not so bad. There are only a limited number of unique instructions in this chip, and every instruction is laid out with this information:

:header: Column, Description
Mnemonic the code for this instruction
Operands zero, one or two additional operands
Description what this instruction does
Operation Register Transfer Language showing what happens
Flags these are status bits maintained in a special register
Clocks how many clock ticks does this take. Most work n one tick!

Obviously we need to understand how these instructions work, but for decoding, we are more interested in breaking up a pile of bits to identify what the instruction is, and what else is needed for it to operate.

Exploring the Instructions

The actual encoding of these bits is pretty complex, and is driven by a number of factors involved in laying the chips out for manufacturing. We will not worry about that detail here, but we do need to look at the encoding forms Atmel came up with for this chip.

Note

Although we do not really need to worry about how the real chip is encoded, there is no real reason not to use the scheme the manufacturer came up with. That will let us use the AVR assembler, with a limited instruction set, to program our simulator.

In our work, only a few instructions actually need a second 16-bits to provide the complete instruction. Unfortunately, detecting that second chunk is not as simple as using one bit in the instruction.

Instruction Encoding

The AVR Supports a number of addressing “modes” which group instructions according to how they use SRAM or registers. Here are the modes supported for our attiny85 chip:

  • Direct register addressing, single register
  • Direct register addressing, single register with bit Address Operand
  • Direct register addressing, two 8-bit registers
  • Direct register addressing, Two 16-bit registers
  • Direct I/O addressing (including SREG)
  • Direct SRAM addressing
  • Immediate 8-bit source with register destination (R15 < Rd)
  • Immediate 6-bit constant, 16-bit register (r24:r25,X,Y,Z)
  • Immediate, 4 bit constant
  • Indirect SRAM with displacement
  • Indirect SRAM with pre and post increment
  • Indirect program memory addressing
  • Control transfer direct addressing
  • Control transfer indirect addressing
  • Control transfer relative addressing
  • MCU controls

That is a lot of different ways you can access memory, registers, or constants. We are certainly not going to deal with all of these. In fact, out of all the available instructions in this chip, we will select only 32 of them (for now). Here is a table showing the ones we will initially use (more might be added if we find a need for them).

Mnemonic OP1 OP2 RTL  
IN Rd PORT Rd <- PORT
OUT PORT Rr PORT <- Rr
         
LDI Rd k Rd <- k
LDS Rd k Rd <= [k]
STS k Rr [k] <- Rr
MOV Rd Rr Rd <- Rr
SBI PORT b PORT[b] <- 1
CBI PORT b PORT[b] <- 0
LSL Rd   Rd[n+1] <- Rd[n],Rd[0] <- 0
         
RCALL k   [STACK] <- PC, PC <- PC + k + 1
RET     PC <= [STACK]
PUSH Rr   [STACK] <- Rr
POP Rd   Rd <- [STACK]
         
RJMP k   PC <= PC + k + 1
BRNE K   if (Z == 1) PC <- PC + k + 1
SBRS Rr b if (Rb[b] == 1) PC <= PC + 2 or 3
SBRC Rr b if(Rr[b] == 0) PC <- PC + 2 or 3
         
NOP    
 
DEC Rd   Rd <- Rd + 1
INC Rd   Rd <- Rd - 1
ADD Rd Rr Rd = Rd + Rr
SUB Rd Rr Rd <- Rd - Rr
         
AND Rd Rr Rd <- Rd AND Rr
OR Rd Rr Rd <- Rd OR Rd
EOR Rd Rd Rd <- Rd XOR Rr
COM Rd   Rd <- OxFF - Rd 1(1)
         
SEI     I <- 1
CLI     I <- 0
RETI     PC <- [STACK]

Instruction Encoding

The actual encoding Atmel came up with is detailed in this ref. Note that not all of the instructions in this reference are actually available in the attiny85

N1 N2 N3 N4 MNEM OP1 OP2 W16
1001 010d dddd 0000 com Rd    
1001 010d dddd 0011 inc Rd    
1001 010d dddd 0110 lsr Rd    
1001 010d dddd 1010 dec Rd    
               
1111 111r rrrr 0bbb sbrs Rr b  
               
0000 11rd dddd rrrr add Rd Rr  
0001 01rd dddd rrrr cp Rd Rr  
0001 10rd dddd rrrr sub Rd Rr  
0010 00rd dddd rrrr and Rd Rr  
0010 10rd dddd rrrr or Rd Rr  
0010 11rd dddd rrrr mov Rd Rr  
0010 01rd dddd rrrr eor Rd Rr  
               
1011 0AAd dddd AAAA in Rd A  
1001 1AAr rrrr AAAA out A Rd  
               
1001 1000 AAAA Abbb cbi A b  
1001 1010 AAAA Abbb sbi A b  
               
1001 0100 0111 1000 sei      
1001 0100 1111 1000 cli      
               
1001 000d dddd 0000 lds Rd k k16
1001 001r rrrr 0000 sts k Rr k16
               
0101 kkkk dddd kkkk subi Rd k  
0110 kkkk dddd kkkk ori Rd k  
0111 kkkk dddd kkkk andi Rd k  
               
1001 0101 0000 1000 ret      
1001 0101 0001 1000 reti      
               
1100 kkkk kkkk kkkk rjmp k    
1101 kkkk kkkk kkkk rcall k    
               
1111 00kk kkkk k001 breq k    
1111 01kk kkkk k001 brne k    
               
               
1001 001r rrrr 1111 push Rr    
1001 000d dddd 1111 pop Rd    
               
0000 0000 0000 0000 nop      

This table was created using Microsoft Excel. Here is that spreadsheet for reference:

Register Movement Instructions

Most ALU instructions, and data movement instructions specify two registers as operands. Here is the encoding for those:

Here, the bits colored blue represent the specific instruction opcode. The green bits select the destination register, and the yellow bits the source register.

Decode Logic

After deciding how instructions are to be encoded, we can set up the machinery needed to decode tan instruction. Here is the addion we need for this step:

../_images/decode.png

This is a bit incomplete. We have not shown how the decoded manages to go back and get the constant K from the instruction memory.