2022 Advent Of Code: Cathode-Ray Tube

It suddenly occurred to me that I should document the challenges I found interesting, especially those that can be visualized. If I have extra energy, I’ll write notes for each day’s puzzle. In any case, I found the Advent Of Code Day10 problem quite fun, so I’m writing it down first.

Part 1

The first part of the problem is relatively straightforward. You need to implement a CPU that can only run two instructions (noop and addx). This CPU has a single X register, and you need to calculate the value of the register at specific cycles. Following the instruction specifications and calculating based on the input should yield the answer fairly quickly. The problem description actually mentions a few hardware-related concepts; while they don’t affect solving the puzzle, I found them quite interesting, so I’ll dive deeper into them later.

class CPU {
  x: number;
  cycles: number;

  constructor() {
    this.x = 1;
    this.cycles = 0;
  }

  tick() {
    this.cycles += 1;
  }

  noop() {
    this.tick();
  }

  addx(arg) {
    this.tick();
    this.tick();
    this.x += parseInt(arg);
  }
}

Part 2

The second part is much more interesting. This register actually represents the position of a Sprite, and the cycle count indicates where the screen is currently drawing. The problem description includes a link to – Racing the Beam. Once you add the screen-drawing logic to the code, you’re good to go.

The logic for determining whether to draw a # can also be implemented using bitwise operations—for example, using 0x111000 >> register to represent the sprite’s shifted position, and then ANDing it with the current cycle to get the current screen character. I was a bit lazy here and just compared them directly one by one:

class CPU {
  // ...

  draw() {
    const column = this.cycles % 40;
    if (column === 0 && this.cycles !== 0) {
      this.screen += "\n";
    }

    if (this.x - 1 === column || this.x === column || this.x + 1 === column) {
      this.screen += "#";
      return "#";
    } else {
      this.screen += ".";
      return ".";
    }
  }
}

I built a simple visualization here. Enter instructions in the text box and click “Execute”, and it will draw according to the instructions. (Note: only addx and noop are supported)

After finishing it, I realized that while turning instructions into screen images is easy, doing the reverse is much harder—that is, generating the corresponding instructions given an image. To achieve this, you have to count cycles while shifting the position where the next pixel is generated, and you can’t be too early or too late. Looking at discussions on Reddit, I found that someone had the exact same idea; they wrote a Python script that takes an ASCII image and generates the corresponding instructions.

Atari 2600

Take the Atari 2600 mentioned in the problem: early gaming consoles had no dedicated video frame buffer to use, and the CPU’s memory was tiny (only 128 bytes of RAM)—far from enough to draw an entire screen. Therefore, you had to reuse memory (RAM) as much as possible.

In programs that require graphics computation, a frame buffer is typically used to offload work from the CPU. The CPU only needs to throw pixels into the frame buffer at the corresponding positions, and the GPU handles the rest, such as drawing at the right time, or encoding and decoding into the appropriate output format. However, without the help of a frame buffer, graphics had to be computed in real time, and engineers were left with no choice but to constantly shuffle data around within limited memory.

The problem is that executing CPU instructions also takes time (cycles). Moving memory too early or too late causes dropped frames, so memory had to be updated at precisely the right moment. It was literally like racing against the CRT’s electron beam, hence the name Racing the Beam.

After understanding all these constraints and looking back at Pac-Man on the Atari, I think it’s a sheer miracle that they could write games under such pathetically low memory and excruciatingly slow CPU speeds. Thank goodness I wasn’t an engineer back in that era, or I’d probably be unemployed.

Looking at Wikipedia, the Atari 2600 was developed using the MOS 6507. According to Wikipedia, it was a cost-reduced variant specially made by MOS Technology for the Atari console, costing half as much as the 6502.

Two years ago, after reading about Nintendo’s history, curiosity led me to buy a MOS 6502. But the 6502 has no built-in ROM, and as far as I understand, it requires a Parallel ROM to read data. Nowadays, you can almost only buy Serial EEPROMs, so my project to tinker with the 6502 had been shelved. After reading this story, I’m feeling a bit motivated again. (Though I still don’t know where to buy a Parallel EEPROM.)

Clock Circuit

To keep a CPU running properly, an oscillator is typically required to generate a steady clock frequency. But why is this oscillator necessary in the first place? It wasn’t until I played Turing Complete that I truly understood this.

Inside a CPU, there are many circuits. Some are very simple, such as adders and logic gates; their output depends entirely on the current input, which can be viewed as a function $f(x) = y$. In digital logic, such circuits are called Combinational.

There is another type of circuit that possesses memory, such as registers, which are built using flip-flop circuits under the hood. This type of circuit has memory, meaning its output depends not only on the input, but also on its current state. In digital logic, such circuits are called Sequential. Having memory might sound trivial, but it is one of the necessary conditions for achieving Turing completeness.

Returning to why an oscillator is needed: its primary purpose is to ensure that all aforementioned state changes occur at the exact same point in time, and achieving this requires a unified clock source. For example, suppose I want to execute an instruction that adds the values in register r1 and register r2, and stores the result back in register r1:

add r1, r2

In an actual circuit, the values of r1 and r2 are fetched simultaneously and sent to the adder circuit, and after obtaining the result, it is written into r1—rather than executed sequentially like this:

• Fetch the value of r1
• Fetch the value of r2
• Feed into the adder circuit
• Get the result and write to r1

To ensure that the adder circuit receives the correct inputs, triggering signals via a unified clock is necessary to ensure consistent state transitions across registers.

However, it’s worth emphasizing that aside from low-power or embedded CPUs, modern CPUs (including Intel and AMD) have exceedingly complex architectures. They do a lot of magical things to maximize CPU performance and are nowhere near as simple as what was described above. For example:

1. Instruction Pipeline: CPU instruction execution can be broken down into four major stages: Fetch, Decode, Execute, and Write Back. Under certain conditions, we can begin fetching the next instruction before the previous one has even written back.
2. Out-of-order execution: Instructions can be executed out of order by the CPU depending on circuit availability (rather than following the original instruction sequence).
3. Branch Predictor: Cleverly guessing which branch an instruction will take.

Execution Cycles

For applications that depend on timing, execution cycles are critical, because incorrect timing can easily lead to completely different results. You can find more details on this in two of my previous articles:

• Building an Air Quality Monitoring App with Arduino and ESP32 (Part 2) - Data Communication with UART
• Exploring Raspberry Pi Pico PIO

Generally, applications (or communication protocols) requiring precise timing control will have dedicated hardware to handle them. However, sometimes due to hardware constraints (e.g., limited UART interfaces) or when using a protocol not supported in hardware, implementing it via the CPU introduces the problem of bit banging, putting excessive load on the CPU and hurting performance.