CHIP-8 interpreter #2 - interpreter
30/8/2020
(See my other CHIP-8 post focussing on graphics here)
ROMs (programs) are compiled to (or written in) bytecode. Bytecode is a kind of instruction set that is designed for execution by an interpreter. CHIP-8 has 2 byte (octet) instructions and is stored most significant byte first. The first byte of an instruction should be located at an even address, and in the case a program might contain sprite data, that sprite should be padded so the next instruction will be at an even location. CHIP-8 has 36 instructions, however the first is ignored by modern interpreters.
Each opcode (with exception of a few such as draw/return) has various operands that can be one of the following:
- lowest 12 bits
- lowest 4 bits
- lower 4 bits of the high byte
- upper 4 bits of the low byte
- lowest 8 bits
/* * the opcode is a 2 byte value, while our memory is 1 byte * so to get our opcode we need to combine 2 bytes located at PC and PC+1 * we left shift the first byte by 8 (1 byte) to place it in the high byte * and we store the second byte in the lower byte */ opcode = (memory[PC] << 8) | memory[PC+1]; uint16_t nnn = opcode & 0x0FFF; // lowest 12 bits uint8_t n = opcode & 0x000F; // lowest 4 bits uint8_t x = (opcode >> 8) & 0x000F; // lower 4 bits of the high byte, we discard the low byte by right shifting it out uint8_t y = (opcode >> 4) & 0x000F; // upper 4 bits of the low byte, so we need to discard the lower 4 bits uint8_t kk = opcode & 0x00FF; // lowest 8 bitsWith these values known I can continue into the execute stage of the cycle and interpret the correct instruction.
In my interpreter executing an instruction is done within a large, nesting switch statement. Considering the CHIP-8 has 35 used simple instructions, this is a manageable way to do this, however if I were writing an emulator for a real system I would create a function pointer table of handlers which would improve readability vastly.
An example of a few instructions: (note: the memory array is the 4KB of memory the CHIP-8 can access and PC is the program counter pointing to the current instruction)
switch (opcode & 0xF000)
{
/*
* decode highest 4 bits
* the highest 4 bits contains the instruction
*/
case 0x0000:
{
switch (kk)
{
case 0x00E0: /* cls (clear screen) */
memset(video, 0, (WIDTH*HEIGHT) * sizeof(uint32_t));
draw_flag = 1;
break;
case 0x00EE: /* ret (return from subroutine) */
stack[SP] = 0x0;
PC = stack[--SP];
break;
default: unknown_opcode(opcode);
}
break;
}
case 0x1000: /*JP addr (jump to memory address nnn) */
PC = nnn;
break;
case 0x2000: /* CALL addr (call subroutine at addr, increment SP and put current PC on top of stack, set PC to nnn) */
stack[SP++] = PC;
PC = nnn;
break;
...
case 0x05: /* SUB Vx, Vy (subtract Vx from Vy, store in Vx, if Vx > Vy set V[F] 1, otherwise 0 */
V[0xF] = (V[x] > V[y]) ? 1 : 0;
V[x] -= V[y];
break;
case 0x06: /* SHR Vx (if the least significant bit of Vx is 1, V[F] set to 1, otherwise 0, then Vx is divided by 2 */
V[0xF] = V[x] & 0x01;
V[x] >>= 1;
break;
case 0x07: /* SUBN Vx, Vy (if Vy > Vx then set V[F] 1 otherwise 0, then Vx is subtracted from Vy, result stored in Vx */
V[0xF] = (V[y] > V[x]) ? 1 : 0;
V[x] = V[y] - V[x];
break;
case 0x0E: /* SHL Vx (if the most significant bit of Vx is 1, V[F] set to 1, otherwise 0, then Vx is multiplied by 2 */
V[0xF] = (V[x] >> 7) & 0x01;
V[x] <<= 1;
break;
...
}
The instruction is stored within the upper nibble (upper 4 bits) of the opcode's most significant byte. This is enough to decode most instructions, however sometimes multiple instructions use the same upper nibble. In these cases the lowest nibble (variable n) and the lowest byte (variable kk) is used to identify which specific instruction is to be executed. Many instructions use the operands (nnn, n, x, y, kk) as extra information for the instructions, such as memory addresses, register numbers, constants, x/y screen positions etc.
Demonstration of my interpreter playing a breakout game and running a few demos: (the flashing is a byproduct of how the chip-8 is designed - it is intended)
The source code can be found in my git repository.
CHIP-8 interpreter #1 - graphics
17/8/2020
I'm working on an implementation of a CHIP-8 interpreter using SDL2 for graphics and sound, in C. I plan to implement the interpreter in parts and have them accompanied with a website post.
What is CHIP-8
CHIP-8 is an interpreted programming language made in the mid 1970's to allow video games to be easier to create and portable for the incompatible systems of the time.CHIP-8 specs:
- 4KB memory
- 16 general purpose 8-bit registers
- 16-bit I register, used to hold memory addresses
- 8-bit delay timer register
- 8-bit sound timer register
- 64x32 display
- 16-bit PC register, stores the current execution address
- 8-bit SP register, points to the top of the stack
- 16-bit stack consisting of 16 values, allowing upto 16 levels of nested subroutines
- 16 key input, hexadecimal 0-F
- default fontset consisting of 0-F in hexadecimal
- 4KB memory
- 0x0 - 0x1FF reserved for the interpreter, in our case this is where we will put the fontset
- 0x200 - 0XFFF program rom and usable program memory
Graphics
The original CHIP-8 (and the one I'm implementing) uses a 64x32 pixel display. Originally, this would have been viewed on a television of the time, however today we have massive displays - this is just too small. So to fix that we need to implement some scaling, thankfully SDL2 handles this for us.CHIP-8 graphics are drawn using sprites. A sprite is always 8 pixels wide and can be up to 15 pixels tall. Each pixel is a single bit, so each byte has 8 pixels inside it, this equates to a sprite 1 byte wide and up to 15 bytes tall.
As an example, the letter 'E' as a sprite:
| "E" | Binary | Hex |
|
**** * **** * **** |
11110000 10000000 11110000 10000000 11110000 |
0xF0 0x80 0xF0 0x80 0xF0 |
Sprite pixels are not turned off and on as you'd expect, instead they're XOR'd. In my interpreter video memory is an array of 64x32 values. To draw a set pixel of a sprite, the index into video memory is XOR'd with 1 (or in my case 0xFFFFFF). This means if the bit was already turned on, it will be turned off - it's toggling the pixel. In the case of a pixel being turned off because of the XOR, the 0xF register is set to 1 to indicate to the program that a sprite collision has occurred.
If you don't understand the XOR operation see my post detailing how bitwise operations work.
CHIP-8 documentation states that a sprite should wrap around when it is drawn out of bounds. This is achieved with the modulo operator(Modulo is the remained when two numbers are divided, example: 11 modulo 4 = 3, because 11 divides by 4 (twice), with 3 remaining). CHIP-9 has 64x32 display, so imagine the following:
We want to draw a pixel at x coordinate 27. 27 % 32 = 27 - the coordinate stays the same. However, if we try draw a pixel at x coordinate 35 we'll find that 35 % 32 = 3. We've clamped the possible x coordinates to 32, the difference between 35 and 32 is 3, and that is our new X coordinate as it wraps around.
In my interpreter we're treating a 1d array as 2d, so we need to map onto the array (bit is the current bit we're writing, 0-7 for the range of a byte):
destination_in_video_memory = WIDTH*(starty%HEIGHT)+((startx%WIDTH)+bit)
This is the function as it currently stands that draws a sprite to the screen:
void
chip8_draw_sprite(int startx, int starty, uint16_t mem, uint8_t size)
{
/*
* draw sprite located at loc of height size at startx,starty
*/
uint8_t byte = 0;
uint8_t mask = 0x1;
V[0xF] = 0; /* set collision register to 0 */
for (uint8_t byteoffset = 0; byteoffset < size; byteoffset++)
{
/* loop through each byte from mem to mem+size */
byte = memory[mem+byteoffset];
int bit = 0;
for (mask = 0x80; mask != 0; mask >>= 1)
{
if (byte & mask)
{
uint32_t pixel = WIDTH*(starty%HEIGHT)+((startx%WIDTH)+bit);
if (video[pixel] != 0)
{
/* if the video bit is already set, we need to set the collision register */
V[0xF] = 1;
}
video[pixel] ^= 0xFFFFFF;
}
bit++;
}
starty++;
}
}
This is written only for testing purposes, when I get to implementing the CHIP-8 instructions it will be rewritten.The general gist of the function is:
- set the collision register (0xF) to 0
- loop through size bytes in memory starting at the offset mem
- loop through each bit of each byte
- perform our modulo operations to perform screen wrapping
- if the pixel at our selected video memory location is already set, set the collision register to 1
- XOR the selected pixel in video memory with 1 (in my case 0xFFFFFF) to flip its value
More posts should follow eventually detailing the other components.
The source code can be found in my git repository.
Logic gate simulator
24/6/2020
I made a logic gate simulator in C++ using the FOX toolkit.
A working full-adder:
Video of program in action:
Click on an icon and left-click anywhere on the canvas to place that gate (or input/output).
Select a gate by left-clicking on it and press delete to delete that gate and its links.
Hold shift and left-click and drag a link to another gate to connect them.
Click on a gates input to highlight that particular link, press the delete key to delete that link.
Right-click on an input to toggle it on and off.
You can save to an XML file by clicking the save button and selecting a name.
You can also load from an xML file by clicking load.
Some example circuits are provided in the examples/ directory.
To build:
You need the FOX toolkit and pugixml installed. On arch install 'fox' and 'pugixml' packages,
cmake CmakeLists.txt makeThe binary will be in bin/
The source code can be found in my git repository.
Minesweeper in C++ and FOX
15/5/2020
I was recently introduced to the FOX toolkit, so I made a simple minesweeper game using it.
The source code can be found in my git repository.
another x200 and some posters
21/5/2020
I found a cheap ($80 aud) x200 on ebay so I bought it. This brings my x200 count to 3, including one tablet. I'm thinking I might keep it as a backup if I need it one day. I might libreboot it at some point between now and then.
It's condition is excellent - very little scratches on the lid, no scratches on the screen, keyboard has very light wear, it seems like the original part, but I'm not sure yet. Part numbers on it are correct though.
It came with a 9 cell battery, after 2.5 hours the charge went from 90% to 48% before I turned it off. This was in idle - much better than my current main x200, so I will definitely take the battery right away.
I also purchased some new posters - I mainly wanted the k-on and clannad ones, but I liked madoka and kokoro connect was alright till the end. Never seen strikers but it was only a few extra dollars. There is another strikers one that I haven't put up yet.
demo recording and playback
27/4/2020
I decided to try adding demo recording/playback to the silly minesweeper game.
The demo is played back in realtime, meaning it will playback at the same speed as you.
You can record a demo using: ./ncsweeper -record demofille.dem
You can play a demo using: ./ncsweeper -play demofille.dem
This isn't portable, different compilers, endianness and cpu word size will produce incompatible demo files. I know these problems exist but I chose to not tackle them this time around.
The first structure written to file is a header that stores game field data, defined as:
struct demo_header
{
int width;
int height;
int mine_count;
};
Next, a total of header.mine_count mines are written to file simply defined as:
struct demo_mine
{
int x;
int y;
};
Next written to file is the number of actions performed. These actions are then written to file in a structure defined as:
enum DEMO_ACTION_TYPE
{
NONE = 0,
GOUP,
GODOWN,
GOLEFT,
GORIGHT,
FLAG,
REVEAL,
QUIT,
};
struct demo_action
{
double action_pre_delay;
enum DEMO_ACTION_TYPE type;
int start_x;
int start_y;
};
This structure holds the starting position of the cursor for the action, the type of action (see the enum) and the time it took for the player to perform the action. These actions are recorded and loaded from file into a list which the game uses to play the demo back.Here is a demo of my best time on a 50x50 playfield.
You can find the source code in my git repo.
simple grid-based and ncurses minesweeper
8/4/2020
I've been interested in minesweeper lately so I wrote a simple grid version in C as well as one using ncurses.
You can find the source code in my git repo.
Cropped Yuu's face too
23/3/2020
Similar to Chito previously, I cropped out every Yuu face from Bloom Into You totalling 2325 images.
You can find them at https://gnupluslinux.com/yuu/ and download a zip containing every image sorted by chapter and ordered here.
Who cares for the details but, I used xbindkeys to create a shortcut that launches a script. This script uses scrot to take a cropped screenshot into a directory.
During the cropping of all faces I used feh to view images in order using `ls -1 -rt | xargs feh`. This will list the directory, show only file names, reverse the order and order them by modification time.
The file name is randomised, so to order them I needed to use the files modification time. To do this I used a simple bash script: `n=0; ls -tr | while read i; do n=$((n+1)); mv -- "$i" "$(printf %03d "$n").png"; done`. This renames every image in order (001.png, 002.png ...). I took care to use the `preserve` flag in cp (copy) to preserve the modification date when copying around.
Next I had to compress the images, to do this I used pngquant `pngquant --quality=65-80 * --ext .png --force`.
To prevent having to run the script manually in each chapter directory one at a time I ran them in a loop `for d in chapter*; do ( cd "$d" && ../../script.sh ); done`.
After compression the total file size for all images went from 138MB to 52MB.
Then I had to somehow turn these images files into html files. To do this I wrote a simple Python script that iterates through every chapter and image and generates the pages and navigation bars.
The python script:
#!/usr/bin/python
import glob
outputdir = "out/" # directory to output html
templatefile = "template.txt" # template file
imgglob = "*.png" # glob for image files
nochapters = 45; # number of chapters to include
localimgloc = "../" # location of images on filesystem (../chapterx)
dirprefix = "chapter"; # prefix for chapter directories
imgloc = "https://gnupluslinux.com/anime/yuu/"; # location of images
# final will be imgloc+dirprefix+chapternumber
# (https://gnupluslibux.com/anime/yuu/chapterx/001.png)
def getimgno(chapter):
'''
get number of images in chapter
'''
return len(glob.glob1("%s/%s%s" % (localimgloc, dirprefix, str(chapter)), imgglob))
def generatenavbar(chapter):
'''
generate navigation bar for chapter
'''
bar = "Chapter: ";
for p in range(1, nochapters+1):
if p == chapter:
# handle own chapter specially
bar += "<strong>%s</strong> " % (str(p));
else:
bar += "<a href=\"%s%s.html\">%s</a> " % (dirprefix, str(p), str(p));
return bar;
def generateimages(chapter):
imgcount = getimgno(chapter);
images = "";
print(str(imgcount));
for p in range(1, imgcount+1):
images += "<a href=\"%s/%s%s/%03d.png\"> <img src=\"%s/%s%s/%03d.png\" alt=\"Yuu face #%s\"></a>\n" \
% (imgloc, dirprefix, str(chapter), p, imgloc, dirprefix, str(chapter), p, p);
#print(images);
return images;
def generatepages():
'''
call all functions and generate/output final html
'''
for p in range(1, nochapters+1):
navbar = generatenavbar(p);
# read template into memory
templatedata = "";
with open (templatefile, 'r') as template:
templatedata = template.read();
#insert title
templatedata = templatedata.replace("{TITLE}", "Yuu's face in chapter %s" % p);
# insert navbar
templatedata = templatedata.replace("{NAVBAR}", navbar);
#insert images
images = generateimages(p);
templatedata = templatedata.replace("{IMAGES}", images);
# write to output file
with open("%s/%s%s.html" % (outputdir, dirprefix, p), 'w') as out:
out.write(templatedata);
def main():
generatepages();
if __name__ == "__main__":
main();
router and too much free time
26/2/2020
Recently I purchased a netgear wndr3800 router which now runs librecmc. Now my main system (x200 with libre(core)boot) and router run more free software.
I also spent a day taking a screenshot of every Chito face (1505 of them) from the manga Girl's Last Tour because she's really cute. I have them online in a collage like thing at https://gnupluslinux.com/chito/. You can download all 1505 images here.
Simple stack
4/2/2020
I'm exploring data structures and I find I learn best when I put something out, so first with a stack. This is my simple implementation using an array. A linked list would be better but that's more verbose.
/*
* stack using array
*/
#include <stdio.h>
#include <stdlib.h>
struct stack
{
ssize_t size;
ssize_t top;
int *array;
};
struct stack
*createstack(size_t size)
{
struct stack *stack = malloc(sizeof(struct stack));
stack->size = size;
stack->top = -1;
stack->array = malloc(sizeof(int) * stack->size);
return stack;
}
void
destroystack(struct stack *stack)
{
free(stack->array);
free(stack);
}
int
isempty(struct stack *stack)
{
return (stack->top == -1);
}
void
pushstack(struct stack *stack, int val)
{
if (stack->top+1 > stack->size)
{
fprintf(stderr, "stack is full, can't push\n");
return;
}
stack->top++;
stack->array[stack->top] = val;
}
int
popstack(struct stack *stack)
{
if (isempty(stack))
{
fprintf(stderr, "stack is empty, can't pop\n");
/* in the real world we would not be holding ints so -1 will do */
return -1;
}
int popped = stack->array[stack->top];
stack->top--;
return popped;
}
int
peekstack(struct stack *stack)
{
if (isempty(stack))
{
fprintf(stderr, "stack is empty, can't peek\n");
return -1;
}
return stack->array[stack->top];
}
void
printstack(struct stack *stack)
{
if (isempty(stack))
{
fprintf(stderr, "stack is empty\n");
}
for (ssize_t i = 0; i <= stack->top; i++)
{
printf("[%zd] = %d\n", i, stack->array[i]);
}
}
int
main(void)
{
struct stack *stack = createstack(50);
printf("isempty: %d\n", isempty(stack));
pushstack(stack, 5);
pushstack(stack, 10);
pushstack(stack, 15);
printf("peek: %d\n", peekstack(stack));
printf("isempty: %d\n", isempty(stack));
printstack(stack);
puts("popstack()");
printf("popped: %d\n", popstack(stack));
printstack(stack);
printf("popped: %d\n", popstack(stack));
printstack(stack);
printf("popped: %d\n", popstack(stack));
printstack(stack);
destroystack(stack);
return 0;
}
