CSSC - EP.3: Instruction Set Analysis

A few days ago, I felt unwell after getting a vaccine, so I paused updates for a while. And finally, the semester is over! Although there will be many decisions influenced by what I made during the finals period, I now have more time to think about more details (´▽｀)

As the project progressed, I realized more and more that designing a computer architecture is not such a simple task… Initially, I just brainstormed and simulated in my head, but later on, I found that Uxn’s basic instruction set alone has 32 instructions, and with 3 mode combinations, there are a total of 256 instructions. Designing a CPU for 256 instructions is truly a challenging endeavor for a university freshman…

Firstly, I have no experience designing a CPU. Therefore, I can only think and analyze using the methods I am most familiar with.

Uxn

• Uxn is a virtual machine designed for all platforms, aiming for a simple design yet enabling diverse possibilities.
• Uxn has built-in Stack, Return Stack, and Device I/O (Varvara), which can be accessed with different instructions.
• You can use Uxntal (assembly language) and bicycle (assembler) to assemble Uxn’s ROM.

Uxn loads from ROM address 0x0100 into RAM address 0x0100; typically, the ROM before 0x0100 is empty.

Uxntal

Uxntal and Uxn are inseparable; Uxntal is the assembly language designed for Uxn. For basic opcodes, Uxn has 32, divided into 4 sections.

• 00~07 are basic stack operations
• 08~0f are logical operations and branch instructions
• 10~17 are direct memory operations
• 18~1f are ALU mathematical operations

You can find the official documentation here: https://wiki.xxiivv.com/site/uxntal.html

Stack: a b c

00 BRK
80 LIT a b c M[PC+1]  08 EQU a b?c
01 INC a b c+1        09 NEQ a b!c
02 POP a b            0a GTH a b>c
03 NIP a c            0b LTH a b<c
04 SWP a c b          0c JMP a b {PC+=c}
05 ROT b c a          0d JCN a {(b8)PC+=c}
06 DUP a b c c        0e JSR a b {rs.PC PC+=c}
07 OVR a b c b        0f STH a b {rs.c}


10 LDZ a b M[c8]      18 ADD a b+c
11 STZ a {M[c8]=b}    19 SUB a b-c
12 LDR a b M[PC+c8]   1a MUL a b*c
13 STR a {M[PC+c8]=b} 1b DIV a b/c
14 LDA a b M[c16]     1c AND a b&c
15 STA a {M[c16]=b}   1d ORA a b|c
16 DEI a b D[c8]      1e EOR a b^c
17 DEO a {D[c8]=b}    1f SFT a b>>c8l<<c8h

Note: This table assumes there are three elements a, b, and c. After each opcode, the result after instruction execution is shown.

The relationship between opcode and mode is as follows:

    MSB < MMMOOOOO > LSB
           |    |
           v    v
         mode  opcode

and:

        M  M  M = [keep, rtrn, shrt]
        |  |  |
        v  |  |
      keep |  |
           |  |
           v  |
       return |
              |
              v
            short

For opcodes:

    MSB  <  o o O O O  >  LSB
            |       |
            v       v
    Feature Area   Opcode-number

Here, ‘opcode number’ refers to the index of an instruction within an instruction block. The Feature Area spans from 0x00 to 0x11.

Instruction Cycle and Stack Operations

However, an instruction from decoding to execution involves more than just identifying what the instruction does. The known CPU instruction cycle is roughly as follows:

1. Fetch
2. Decode
3. Execute

In the Uxn virtual machine, the instruction cycle is abstracted such that each Uxn VM implementation does not necessarily need to adhere to it, or there isn’t a clearly defined constraint. However, based on Uxn’s characteristics, the following structure can be inferred:

1. Lookup to instruction
2. operate stack or store value
3. execute…
4. push or store back to stack

While theoretically, the stack must pop values and then push them back after computation, if we only consider implementing this via a stack pointer, in some cases, it’s only necessary to update the value at the same location with the new result.

Example 1: INC2k

We want to implement the following instruction functionality:

#01 INC         ( 02 )
#0001 INC2      ( 00 02 )
#0001 INC2k     ( 00 01 00 02 )

If the stack must pop and push within the instruction cycle:

#0102 INC2k

operation   step   original stack     register (flexible with 8-bits and 16-bits)
DUP         1      (01 02)            (01)
DUP         2      (01 02)            (01 02)
INC         3      (01 02)            (01 03)
POP         4      (01 02 01)         (03)
POP         5      (01 02 01 03)      ()

The POP operation has high complexity. However, if popping and pushing within the instruction cycle is not required:

#0102 INC2k

operation  step   original stack     counter

*LIT2      1      (01 02)            (??)
DUP2       2      (01 02 01 02)      (??)

DUP        3      (01 02 01 02)      (02)
INC        4      (01 02 01 02)      (03)
SET        5      (01 02 01 03)      (03)

or, if there is an overflow:

#01ff INC2k

operation  step   original stack     counter   description

*LIT2      1      (01 ff)            (??)
DUP2       2      (01 ff 01 ff)      (??)

DUP        3      (01 ff 01 ff)      (ff)
INC        4      (01 ff 01 ff)      (00)      count as overflow, flag on
SET        5      (01 ff 01 00)      (00)

DUP        6      (01 ff 01 00)      (01)
INC        7      (01 ff 01 00)      (02)
SET        8      (01 ff 02 00)      (02)

At this point, you’ll also notice that if an overflow occurs, you only need to invoke the same instruction operations again (i.e., DUP, INC, SET).

This process omits the complex POP operations, instead using a stack pointer to implement an abstract stack and operating directly on stack values. This echoes the initial assessment I mentioned in EP.0: “After confirming that a stack pointer could potentially be implemented with the 74 series, I began…” At the start of the project, I had already planned to use a stack pointer combined with the aforementioned mode to implement abstract stack operations.

Next Post: Instruction Analysis and Instruction Cycle

However, to solve the problem of implementing the instruction set within the Control Unit (CU), the design of the control hub must be considered. In the next article, I will attempt to find methods that can assist me in designing the implementation of the Uxn instruction set. At the same time, I will continue to discuss the initial stack pointer verification and implementation methods that were not mentioned earlier.

Furthermore, due to space constraints, it’s a bit regrettable that this post’s conclusion ended so hastily. I will address the key concepts missing from this post at the beginning of the next one, and I apologize again.

Lastly, I genuinely hoped the CSSC series could present complete thoughts like notes, but I found that in many cases, writing everything out became quite redundant. So, in the end, I heavily edited most of this post’s content and rewrote a more rigorous version, hoping it reads more smoothly.

Next Post 》〉

Appendix: Source Code and Final Result

The source code is now publicly available below. Since it’s just a simple tool, it’s only a few lines:

processing:

import processing.serial.*;

final int SIZE = 11;

Serial device;
byte[] input;
int hi = 100000000;
PGraphics view;
float scaling = 1;
int viewPosX = 0, viewPosY = 0;

void setup() {
  size(800, 600);
  pixelDensity(2);

  view = createGraphics(800, 600);

  print(Serial.list()[1]);

  device = new Serial(this, Serial.list()[1], 115200);
  delay(10);
  device.write('b');

  // avoid nullPointException
  view.beginDraw();
  view.endDraw();
}

void draw() {
  background(255);


  if (hi > width) {
    hi = SIZE;
    device.write('s');
    view.clear();
    view.background(255);
  }

  while (device.available() > 0) {
    view.beginDraw();
    String input = device.readStringUntil('\n');

    if (input == null) continue;
    if (input.length() != 56) continue;

    for (int i = 2; i < 54; i++) {
      if (input.charAt(i) != '0' && input.charAt(i) != '1') continue;

      view.fill(0, input.charAt(i) == '1'? 255: 100, 100);
      view.rect(hi, SIZE*i, SIZE, SIZE);
    }

    //view.line(hi, 0, hi, height);

    hi+=SIZE;

    device.clear();

    view.fill(0);
    view.textSize(SIZE);

    for (int i = 2; i < 54; i++)
      view.text(String.valueOf(i), 0, (i+1)*SIZE);

    view.endDraw();
  }

  image(view, 0 + viewPosX, 0 + viewPosY, 800 * scaling, 600 * scaling);
}

String numBuf = "0";

int toNonZero(int num){
  return num == 0? 1: num;
}

void keyPressed() {
  switch(key) {
  case '+':
    for (int i = 0; i < toNonZero(int(numBuf)); i++)
      scaling += 0.1;
    numBuf = "0";
    break;
  case '-':
    for (int i = 0; i < toNonZero(int(numBuf)); i++)
      scaling -= 0.1;
    numBuf = "0";
    break;
  case 'h':
    for (int i = 0; i < toNonZero(int(numBuf)); i++)
      viewPosX += 10;
    numBuf = "0";
    break;
  case 'l':
    for (int i = 0; i < toNonZero(int(numBuf)); i++)
      viewPosX -= 10;
    numBuf = "0";
    break;
  case 'j':
    for (int i = 0; i < toNonZero(int(numBuf)); i++)
      viewPosY -= 10;
    numBuf = "0";
    break;
  case 'k':
    for (int i = 0; i < toNonZero(int(numBuf)); i++)
      viewPosY += 10;
    numBuf = "0";
    break;
  default:
    if (key <= '9' && key >= '0') {
      numBuf += key;
    }
    break;
  }
}

Arduino:

char input[54];
char readBuf[54];

void setMode(char* modes) {
  for (int i = 2; i < 54; i++)
    pinMode(i, modes[i] == '1' ? OUTPUT : INPUT);
}

void writePin(char* data) {
  for (int i = 2; i < 54; i++)
    digitalWrite(i, data[i] == '1' ? HIGH : LOW);
}

void readPin() {
  readBuf[0] = 1;
  readBuf[1] = 1;
  for (int i = 2; i < 54; i++)
    readBuf[i] = digitalRead(i) == HIGH ? '1' : '0';
}

void setup() {
  // put your setup code here, to run once:
  Serial.begin(115200);
  Serial.println("start");

  for (int i = 2; i < 54; i++) {
    pinMode(i, INPUT_PULLUP);
  }

  attachInterrupt(digitalPinToInterrupt(2), updateInfo, CHANGE);
}

void updateInfo() {
  readPin();
  readBuf[54] = 0;
  Serial.println(readBuf);
}

void loop() {
  // put your main code here, to run repeatedly:
}

The code might not be perfectly complete, but its structure is very simple. Feel free to take a look at what’s inside; I won’t elaborate further here.

The image below shows the final result from Processing

The image below shows the Arduino Mega used for this project