Let’s say you want to make a programming language. The first thing your implementation needs to do is tokenize the input. What does that mean?

Your implementation will be a program that reads an input string and interprets its meaning, analogous to the way we read sentences and interpret their meanings. Consider the following sentence:

The quick brown fox jumps over the lazy dog.

When a human reads this sentence, they look at it and see words. But when a computer reads the same sentence, it just sees a bunch of characters:

'T', 'h', 'e', ' ', 'q', 'u', 'i', 'c', 'k', ' ', 'b', 'r', 'o', 'w', 'n', ' ', 'f', 'o', 'x', ' ', 'j', 'u', 'm', 'p', 's', ' ', 'o', 'v', 'e', 'r', ' ', 't', 'h', 'e', ' ', 'l', 'a', 'z', 'y', ' ', 'd', 'o', 'g', '.'

The process of tokenizing is the process of interpreting a series of characters as a sentence of words.

'The', 'quick', 'brown', 'fox', 'jumps', 'over', 'the', 'lazy', 'dog', '.'

That’s much easier to understand now, but we’re not done yet. A list of words followed by a period does not necessarily make a valid sentence. To know if the sentence is valid and what it might mean, we need to know what part of speech each of the words are. Something like:

{ type: Article, source: 'The' },
{ type: Adjective, source: 'quick' },
{ type: Adjective, source: 'brown' },
{ type: Noun, source: 'fox' },
{ type: Verb, source: 'jumps' },
{ type: Preposition, source: 'over' },
{ type: Article, source: 'the' },
{ type: Adjective, source: 'lazy' },
{ type: Noun, source: 'dog' },
{ type: Period, source: '.' }

Now we have something that a computer program could begin to interpret. Each of those items listed above is called a token. It has a type in addition to its source which is the original string of characters.

Just because we have a list of tokens doesn’t necessarily mean that we have a valid sentence, but we now have enough information to be able to determine if this sentence follows the rules of the grammar of the language.

Of course, we’re making a programming language, so the “sentences” look more like this:

local (text = op.getsuboutline ());

And the tokens look like this:

{ type: Local, source: "local" },
{ type: LeftParen, source: "(" },
{ type: Identifier, source: "texttosearch" },
{ type: Equal, source: "=" },
{ type: Identifier, source: "op" },
{ type: Dot, source: "." },
{ type: Identifier, source: "getsuboutline" },
{ type: LeftParen, source: "(" },
{ type: RightParen, source: ")" },
{ type: RightParen, source: ")" },
{ type: Semicolon, source: ";" }

But the concept is the same. The job of a tokenizer is to scan through the input string and convert it into a list of tokens.

Once we have a tokenizer, we can start building a compiler which takes the list of tokens, interprets it according to the rules of the language’s grammar, and generates instructions for the computer to execute. But that’s for another day.

I need to remember how valuable writing is as a thought tool. The other night I was truly stumped as to how to solve my VGA problem.

As I was finishing writing my previous post, I began to get an idea of where to start debugging my problem. I even said so in the post:

Remember, there’s a break at the end of every line. This means that I need to start loading the character data for the start of the next line at the end of this blank period. There’s also a longer break at the end of each screen. This means that I need to load the data for the first character of the screen at the end of this blank period.

I think this is where the bug is. All the characters in the first column are one half-line (at 320x240) lower than the rest of the screen. My best guess is that I need to start the data load a little sooner during the blank period.

So, I looked for the code that calculates which row of pixels to load, and I found this:

wire [11:0] rom_adr = { pattern_num, vga_vpos[3:1] };

This line says, “the location in ROM is composed of the pattern_num (i.e. the ASCII character) and bits 3, 2, and 1 of the current line”. Apologies to anyone still reading this that isn’t familiar with binary numbers, but those details don’t really matter. What matters is what I put in bold above. We are using the value of the current line to calculate the value of the next character. This works for every character in a row, except for the first character.

When we read the font data for the first character in a row, we are using a value based on the previous row. We need a special case for when we read the first character.

This is what I ended up with

wire [10:0] rom_adr = { pattern_num, (display_on ? vga_vpos[3:1] : next_rom_row) };

Basically this says that if the display is on, use the current line position. If the display is off, (i.e. the blank period at the end of the line) use the next line position.

There was some other work I had to to do calculate that value properly, but it works now!

I’m building an 8-bit computer. I should probably write an overview of the project, why I decided to do it, how I got started, etc, but today I have a problem to solve.

Take a look at the following image:

This shows a VGA monitor displaying text at a resolution of 40 columns x 30 rows. Each character is an 8x8 block, giving an overall screen resolution of 320x240 pixels.

Now, what’s the problem?

Look closely at the first column. Does it look a little off to you? It did do me, which caused me to zoom in.

The first column is one half-line lower than all the following columns.

How can this be?

It’s time to talk about how this is supposed to work.

I have an FPGA that is acting as a video processor (like the VIC II in the Commodore or the ANTIC/GTIA combo in the Atari). I have a character font stored in ROM. There’s also a section of RAM that stores the ASCII values of the characters to display on the screen in order. The first byte in this section of RAM controls the character in the top-left corner of the screen. The last byte controls the character displayed in the bottom-right corner of the screen.

In order to control a VGA monitor, the video processor sends the pixel data (either on or off in my case) for each pixel on the display starting at the top-left, one line at a time, moving left-to-right. This happens at a constant rate, with a fixed-length break at the end of each line, and a slightly longer break at the end of each screen. This process happens 60 times every second.¹

In order to display the expected values on the screen, the video processor must do the following:

1. Load the next character from RAM.
2. Combine the value from RAM with the vertical position on the screen to look up the font data from ROM. (Remember each font is 8 lines tall, so we need to know which line of the font to draw.)
3. Send the font data out one pixel at a time.

As you can imagine, the timing of these operations is critical. We need to load the next character from RAM and the font data from ROM while we are in the process of sending the pixel data to the monitor for the last character.

Oh yeah, one other thing. VGA doesn’t technically support a screen resolution of 320x240, but it does support 640x480. So I’m drawing every pixel twice per line, and drawing every line twice.²

When the processor is outputting the 5th pixel for a character, it starts loading the data for the next character. This seems to work just fine for almost the entire screen, except for the first column.

Remember, there’s a break at the end of every line. This means that I need to start loading the character data for the start of the next line at the end of this blank period. There’s also a longer break at the end of each screen. This means that I need to load the data for the first character of the screen at the end of this blank period.

I think this is where the bug is. All the characters in the first column are one half-line (at 320x240) lower than the rest of the screen. My best guess is that I need to start the data load a little sooner during the blank period.

1. For a much better explanation of how VGA works, I recommend Ben Eater's excellent video.↩︎
2. I want a 320x240 screen size because my 8-bit system doesn't have enough memory to support a 640x480 size screen.↩︎

Cory Doctorow:

The tech worker layoffs are best understood as an all-out war on tech worker morale, because that morale is the source of tech workers' confidence and thus their demands for a larger share of the value generated by their labor. The current tech layoff template is very different from previous tech layoffs: today’s layoffs are taking place over a period of months, long after they are announced, and laid off tech worker is likely to be offered a months of paid post-layoff work, rather than severance. This means that tech workplaces are now haunted by the walking dead, workers who have been laid off but need to come into the office for months, even as the threat of layoffs looms over the heads of the workers who remain. As an old friend, recently laid off from Microsoft after decades of service, wrote to me, this is “a new arrow in the quiver of bringing tech workers to heel and ensuring that we’re properly thankful for the jobs we have (had?).”

Matt Goodman:

That’s the difficulty in this debate. It’s about the city’s future, a generational chance to trade eight elevated lanes of highway for an eventual new neighborhood. The members who added their names to the memo have expressed more interest in analyzing the opportunities removal could present; after all, traffic data cannot account for changes in technology and behavior, both of which inform how frequently people drive. As Councilwoman Willis asked last year, what happens if the city’s economic development plan creates jobs in southern Dallas so residents there no longer have to drive as far to get to work?