Writing a Chip 8 Emulator – DRAW command (Part 3)

Previously, I wrote about the Chip 8’s basic execution structure, as well as how to decode and understand its instructions. While many of the commands are used to perform logical operations or fetch data from memory, I think that commands that perform input or output routines are equally important. After all, how can you interact with the emulator if you have no way of seeing what it is doing? In this post, I wanted to talk about one of the most important instructions in the Chip 8 arsenal: the DRAW command.

The Chip 8 Screen

First, a little background. The Chip 8 defines a single screen that is 64 pixels wide by 32 pixels tall. It’s a small screen, but it is a nice size to work with if you are writing an emulator for the first time.

Continuing on with simplicity, the Chip 8 is only capable of drawing pixels in a single color: white. Limited, yes, but easy to work with. If you like, you can have your Chip 8 emulator print the pixel out in any color at all. You just need to know that you can’t write a Chip 8 program that controls the color of the pixels written to the screen.

Writing Pixels with XOR

The Chip 8 has a really simple method of drawing a pixel to the screen. You can only control whether you want to turn a pixel on 1 or turn it off 0. When you turn on a pixel, it appears in the single glorious color that the Chip 8 has.

But writing to the Chip 8 screen isn’t just a simple matter of turning a pixel on and off. All write operations are governed by an XOR (exclusive OR) routine. The reason why the Chip 8 uses an XOR routine is because it makes certain graphics operations easier. However, it is a somewhat tricky concept if you are new to it. Bear with me while I draw out the truth table for an XOR:

0 xor 0 = 0
0 xor 1 = 1
1 xor 0 = 1
1 xor 1 = 0

To break this down, there are four different operations you can perform on the pixels. The first two work as you would expect them to:

  • When you turn off 0 a pixel that is already turned off 0, the pixel remains off 0.
  • When you turn on a pixel 1 that is turned off 0, the pixel turns on 1.

With me so far? Here’s where things get a little trickier:

  • When you turn off 0 a pixel that is turned on 1 the pixel will remain on 1.
  • When you turn on 1 a pixel that is already on 1, you end up turning it off 0.

If the draw operation turns off a pixel that was already on, it will store the value 1 in register VF. This is a really important detail to remember, since it allows you to perform sprite hit detection. Which brings us to the next item of business.

Sprites

Yes, the Chip 8 actually had a concept of a sprite. To those who don’t know, a sprite is a distinct graphical object. Usually, in the realm of computer games, a sprite would be something like a player’s character on the screen.

Everything is a sprite to the Chip 8. This means that you don’t have to turn a pixel off or on individually; instead you control groups of pixels as specified by the sprite. Each sprite can be between 1 and 15 bytes long. The bit patterns within the bytes that you specify correspond to the pixels you want turned on or off. As you would expect, 1 turns on a pixel, and 0 turns off the pixel (subject of course to the above XOR rules). Here’s a simple example of a 7 byte sprite:

         bit 7 6 5 4 3 2 1 0
-------+--------------------
byte 1 |     0 1 1 1 1 1 0 0 
byte 2 |     0 1 0 0 0 0 0 0 
byte 3 |     0 1 0 0 0 0 0 0  
byte 4 |     0 1 1 1 1 1 0 0   
byte 5 |     0 1 0 0 0 0 0 0 
byte 6 |     0 1 0 0 0 0 0 0 
byte 7 |     0 1 1 1 1 1 0 0

Do you see the pattern? The sprite represents a capital E character. In hex, these bytes would be the following values:

         hex
-------+----
byte 1 |  7C
byte 2 |  40
byte 3 |  40
byte 4 |  7C
byte 5 |  40
byte 6 |  40
byte 7 |  7C

These 7 bytes would have to be placed somewhere in the Chip 8’s memory in order to write this sprite pattern to the screen. They also have to be placed in the order that you see them.

Using the Index Register

The index register is used to specify where in memory the sprite resides. This means that before you issue the DRAW command using the Chip 8 instruction set, you must first load the memory location of the sprite into the index register. Continuing our example above, say you stored the 7 byte sprite starting at location 0x300. You would need to first load the index register with that location. In machine code this is A300. The DRAW command would then read byte 1 from 0x300, byte 2 from 0x301, and so on.

The DRAW Command

Okay, with all the background out of the way, we can finally examine the core DRAW instruction. The instruction takes on the form Dxyn. If you recall my earlier post, the D remains the same for all draw commands. The other options are:

  1. x – this specifies the register that stores the X coordinate where you want to draw the sprite. Valid X coordinates range from 0 to 63. Values larger than 63 will cause the sprite to wrap horizontally across the screen.
  2. y – this specifies the register that stores the Y coordinate where you want to draw the sprite. Valid X coordinate range from 0 to 31. Values larger than 31 will cause the sprite to wrap vertically across the screen.
  3. n – this specifies how many bytes the sprite is. Valid number of bytes range from 0 to 15.

Let’s go through a simple program that draws out the capital E at the location 10, 5 (X, Y). Here are the steps you would need to take:

  1. Put the sprite bytes somewhere in memory (say location 0x300).
  2. Load the index with the start of the sprite bytes.
  3. Load a register with the value 10 (say register 0).
  4. Load a register with the value 5 (say register 1).
  5. Issue the DRAW command (becomes D017).

The complete assembly listing for this program would be the following (note that I am using my Chip 8 Assembler to write and compile the assembly code for this example):

# Writes the letter E to the location (10, 5)
start   LOADI  sprite   Load the sprite location into index
        LOAD   r0,$A    Load 10 into register 0
        LOAD   r1,$5    Load 5 into register 1
        DRAW   r0,r1,$7 Draw 7-byte sprite at r0, r1
end     JUMP   end      Loop infinitely
# Data for the program
sprite  FCB    $7C      Capital letter E
        FCB    $40
        FCB    $40
        FCB    $7C
        FCB    $40
        FCB    $40
        FCB    $7C

The assembled statements (with their memory locations and the program listing) are the following:

-- Assembled Statements --
0x0200 A20A  start LOADI   sprite  # Load the sprite location into index
0x0202 600A         LOAD    r0,$A  # Load 10 into register 0
0x0204 6105         LOAD    r1,$5  # Load 5 into register 1
0x0206 D017         DRAW r0,r1,$7  # Draw 7-byte sprite at r0, r1
0x0208 1208    end  JUMP      end  # Loop infinitely
0x020A 007C sprite   FCB      $7C  # Capital letter E
0x020B 0040          FCB      $40  #
0x020C 0040          FCB      $40  #
0x020D 007C          FCB      $7C  #
0x020E 0040          FCB      $40  #
0x020F 0040          FCB      $40  #
0x0210 007C          FCB      $7C  #

For those of you who don’t use my assembler, the second column in the output are the assembled statements. You can punch those into a hex editor manually to create the Chip 8 program. When we run the program, we get the following:

e_program_output

Wrapping Up

It is extremely easy to draw sprites on the screen. All you need to do is load the index register with the memory location of your data, set the X and Y coordinates into two registers, and then issue the DRAW command. In a future post, I’ll look at how you can make writing text in a Chip 8 program easier with the built in font file and the load sprite command (Fs29).

Encrypting a USB Flash Drive

Given how easy it is to lose flash drives, I always make sure to encrypt them if I intend to store any important information on them. In this post, I’m going to go over the steps for creating an encrypted flash drive under Ubuntu. Note that there are a lot of other tutorials out there that pretty much take you through the same thing with some additional information on security and advanced options (for example, this one, or this one). I’m always forgetting the steps, so I wanted to document it for myself!

Finding the Right Device

The first step is to make sure you have the right device selected. This amounts to plugging in the device and checking out how the kernel registers it. Under Ubuntu, a simple command will print out kernel messages for you:

dmesg

That should print out all of the kernel activity that is being logged. You should see near the bottom a lot of output relating to the USB devices:

[5161642.499490] usb 1-1.2: new high-speed USB device number 8 using ehci-pci
[5161642.593412] usb 1-1.2: New USB device found, idVendor=0781, idProduct=5581
[5161642.593423] usb 1-1.2: New USB device strings: Mfr=1, Product=2, SerialNumber=3
[5161642.593429] usb 1-1.2: Product: Ultra
[5161642.593434] usb 1-1.2: Manufacturer: SanDisk
[5161642.593439] usb 1-1.2: SerialNumber: *********************************
[5161642.838071] usb-storage 1-1.2:1.0: USB Mass Storage device detected
[5161642.838160] scsi7 : usb-storage 1-1.2:1.0
[5161642.838357] usbcore: registered new interface driver usb-storage
[5161643.835928] scsi 7:0:0:0: Direct-Access     SanDisk  Ultra            1.00 PQ: 0 ANSI: 6
[5161643.837080] sd 7:0:0:0: Attached scsi generic sg2 type 0
[5161643.837920] sd 7:0:0:0: [sdc] 31266816 512-byte logical blocks: (16.0 GB/14.9 GiB)
[5161643.838987] sd 7:0:0:0: [sdc] Write Protect is off
[5161643.839003] sd 7:0:0:0: [sdc] Mode Sense: 43 00 00 00
[5161643.840239] sd 7:0:0:0: [sdc] Write cache: disabled, read cache: enabled, doesn't support DPO or FUA
[5161643.862424]  sdc: sdc1
[5161643.866058] sd 7:0:0:0: [sdc] Attached SCSI removable disk

In this case, you can see that I plugged in a SanDisk USB flash drive, with 16 GB of storage on it. More importantly, the kernel has told us what device name it has assigned to the drive:

[5161643.862424]  sdc: sdc1

As always, it’s a good idea to double check the drive information. The following command prints out the partitions on /dev/sdc:

sudo fdisk /dev/sdc -l

This will print out information relating to the device:

Disk /dev/sdc: 16.0 GB, 16008609792 bytes
255 heads, 63 sectors/track, 1946 cylinders, total 31266816 sectors
Units = sectors of 1 * 512 = 512 bytes
Sector size (logical/physical): 512 bytes / 512 bytes
I/O size (minimum/optimal): 512 bytes / 512 bytes
Disk identifier: 0x00000000
 
   Device Boot      Start         End      Blocks   Id  System
/dev/sdc1             192    31266815    15633312    c  W95 FAT32 (LBA)

This matches what we expected to see: /dev/sdc is a 16 GB drive, formatted with FAT 32. This is good.

Delete the Existing Partition

The next step is to delete the existing partition, and create a new Linux partition.

WARNING: this will destroy everything on the drive, so be careful! Make sure that the contents of the drive are backed up, and that you check to make sure you are typing the right commands and the right drive letters. As always, make sure you educate yourself if you don’t know what the command is going to do. I am not responsible for any damages that may occur – run any of the following commands at your own risk!

sudo fdisk /dev/sdc

You will now be in the fdisk program. It’s a good idea just to print out the contents of the drive again to confirm this is the correct device:

p

This should give us the same information we saw above:

Disk /dev/sdc: 16.0 GB, 16008609792 bytes
255 heads, 63 sectors/track, 1946 cylinders, total 31266816 sectors
Units = sectors of 1 * 512 = 512 bytes
Sector size (logical/physical): 512 bytes / 512 bytes
I/O size (minimum/optimal): 512 bytes / 512 bytes
Disk identifier: 0x00000000
 
   Device Boot      Start         End      Blocks   Id  System
/dev/sdc1             192    31266815    15633312    c  W95 FAT32 (LBA)

Since this is the only partition, the delete operation will be applied to it:

d

You should see:

Selected partition 1

Create the New Parition

You can now create a new partition that will hold the encrypted container:

n

And, you will be asked for the type of partition:

Partition type:
   p   primary (0 primary, 0 extended, 4 free)
   e   extended
Select (default p):

If this is the only partition that you will be creating on the stick, then you will want to make a primary partition. If you want to make many partitions on the stick, then things get a little trickier. For historical reasons, you can only have 4 partitions on any given disk. However, you can create an extended partition that can hold additional logical drives. But, that discussion is beyond this simple tutorial. In this case, I made a primary partition:

p

Next, you will be asked to choose the partition number:

Partition number (1-4, default 1):

In this case, I want to use the default of 1:

1

As a side note, the partition number is associated with the device that you will then mount when it is created. In this case, by making it 1, when I plug it into any computer, it will become /dev/sdX1 where X will depend on what other devices are already mounted. If I made it 2, then it would be /dev/sdX2.

Next, the we are asked for the first sector, and the last sector. I just used the defaults in order to make the partition span the disk. To accept the default values, you just press enter:

First sector (2048-31266815, default 2048):
Using default value 2048
Last sector, +sectors or +size{K,M,G} (2048-31266815, default 31266815):
Using default value 31266815

With the partition creation complete, I printed out the new partition information with p to see what the new partition looked like:

Command (m for help): p
 
Disk /dev/sdc: 16.0 GB, 16008609792 bytes
64 heads, 32 sectors/track, 15267 cylinders, total 31266816 sectors
Units = sectors of 1 * 512 = 512 bytes
Sector size (logical/physical): 512 bytes / 512 bytes
I/O size (minimum/optimal): 512 bytes / 512 bytes
Disk identifier: 0x805a51a5
 
Device    Boot Start End      Blocks   Id System
/dev/sdc1      2048  31266815 15632384 83 Linux

With the new partition created, I wrote the partition information to the disk with w, which also quits fdisk.

Create the LUKS Container

Usually at this stage of readying a new drive you would format the partition with a filesystem. With encrypted drives however, you need to first create an encrypted container. For this, I used cryptsetup with the luksFormat option. I usually use the default options when it comes to the choice of encryption. For those that are more concerned with choice of encryption and hash options, you can check out the manpages with man cryptsetup.

sudo cryptsetup luksFormat /dev/sdc1

Issuing the command will prompt you with a warning:

WARNING!
========
This will overwrite data on /dev/sdc1 irrevocably.
 
Are you sure? (Type uppercase yes): YES
Enter passphrase:
Verify passphrase:

Make sure you remember the passphrase you type – if you forget it, there is no way to retrieve it. For those interested, the passphrase is stored in a keyslot. Additional passphrases for the same disk can be added to different keyslots. This is useful if more than one person needs to access the disk and you want to have a different passphrase.

Open the Device

Once the container is created, you need to open it. Opening an encrypted container is akin to unlocking it. This is performed with the luksOpen sub-command in cryptsetup:

sudo cryptsetup luksOpen /dev/sdc1 sdc1_crypt

What this does is open the container on /dev/sdc1 and maps it to /dev/mapper/sdc1_crypt. Essentially you write your data as you would normally to the remapped device, which will automatically encrypt and decrypt the data for you as you read and write to the device.

Create the New Filesystem

With the new encrypted container open, you need to create the ext4 filesystem on it:

sudo mke2fs -t ext4 /dev/mapper/sdc1_crypt

This runs through the mke2fs routine:

mke2fs 1.42.9 (4-Feb-2014)
Filesystem label=
OS type: Linux
Block size=4096 (log=2)
Fragment size=4096 (log=2)
Stride=0 blocks, Stripe width=0 blocks
977280 inodes, 3907584 blocks
195379 blocks (5.00%) reserved for the super user
First data block=0
Maximum filesystem blocks=4001366016
120 block groups
32768 blocks per group, 32768 fragments per group
8144 inodes per group
Superblock backups stored on blocks:
32768, 98304, 163840, 229376, 294912, 819200, 884736, 1605632, 2654208
 
Allocating group tables: done
Writing inode tables: done
Creating journal (32768 blocks): done
Writing superblocks and filesystem accounting information: done

With the format complete, the new encrypted stick is ready to use!

Note: some tutorials suggest writing zeros or other random numbers to the device prior to creating the filesystem. Why? Well most drives are zeroed out initially, so even though your data is encrypted on the drive, an attacker would be able to see where you have written data, as well as how much data has been written to disk. The security issue at play is that the attacker could use that information when trying to crack your encryption. But since flash media has a limited number of write cycles, doing this is somewhat costly. It’s up to you to determine how far you want to take your security.

Check that Everything Works

Once everything is complete, I always run a quick test to make sure there are no problems. First, close the container:

sudo cryptsetup luksClose sdc1_crypt

And then open it again to make sure your password works, and that the contents can be decrypted correctly:

sudo cryptsetup luksOpen /dev/sdc1 sdc1_crypt

Then, mount the device to make sure that you can actually read the contents:

sudo mount /dev/mapper/sdc1_crypt /mnt/Backup

Wrapping Up

Encrypting a drive is really easy these days. Simply partition your drive, create the encrypted container in the new partition, and then format the container with the filesystem of your choice. Just remember when you mount the device that you first must use cryptsetup luksOpen to open the container prior to mounting the filesystem!