Coding the smallest executable, but still doing the job

September 15, 2008
URL:http://www.drdobbs.com/embedded-systems/spew-a-fictitious-processor-with-4k-of-m/210601643

Ben is the owner and software developer for Forever Young Software. He's also a licensed general contractor building homes in the White Mountains of Arizona. Ben can be contacted at [email protected] or [email protected].

The Hugi Compo (short for "competition") was a size coding competition to see who could code the smallest executable, but still complete the task at hand and pass the test suite.

The long-running competition was hosted by a team of programmers who challenged participants with common (and not so common) tasks. I participated in Hugo Compo first as a competitor, and later as a tester and host of the results. It was someone on this team who suggested that we do something different -- create an emulator for a fictious CPU we called the "Spew processor" that 4k of memory accessed with 12 bits, 4 registers, and 18 instructions. The goal of the Spew Compo, Compo #9 was to see who could code the smallest executable to emulate the Spew CPU given a number of Spew image files.

The winner (and usually one of the top scoring competitors) had an executable entry size of 179 bytes. My entry was 15 out of 21, not as good, but still a respectable 261 bytes. In this article, I present my entry to the competition. The source code for my entry, the SPEW assembler, source code, debugger, and detailed information here. The results of this competition and 25 others along with complete rules, examples, test suites, and source code to each competitors entry for each competition are available here.

The Spew CPU only had 4k of RAM, and was set up with specific areas and values; see Table 1.

The first 256 bytes of the 4k image are set to values from 0 to 255 respectively. This is done at boot time. These values aren't used for anything other than to make the emulator more involved for the competition. It has little or no effect on the actual SPEW CPU.

The memory area from 0x100 to 0xEFF is used for code and data. This is the area where the actual binary code and data is loaded to and executed.

The byte at 0xF00 is the accumulator register. This is a byte wide general-purpose register.

The byte at 0xF01 is the status register. It is almost identical to the lower byte of the 80x86 flags register, with a small difference; the overflow flag is moved to bit 3 in the spew status register (see Figure 1).

[Click image to view at full size]

Figure 1

The word at 0xF02 is the stack register.

The word at 0xF04 is the current instruction pointer register.

The memory area from 0xF06 to 0xFFF is the default stack space.

Even though the stack pointer and instruction pointer fields are 16 bits each, only the lower 12 bits are used for memory access. The values in these fields should remain 16-bit values, but when the actual memory access is made, the high nibble should be ignored.

The default stack location is simply that, default. The loader (the host) will only load your data and code to offset 0x100 through 0xEFF. However, the memory from 0x000 to 0x0FF and the memory currently allocated for the default stack can be used however you like. You may place a value in the STACK register to use a different stack.

The stack space, memory from 0xF06 to 0xFFF, is not cleared at load time, so technically, you could place code and data in the image file at this location as long as you changed the stack register to point somewhere else before you used the stack. This process was never discussed enough to rule out using the default stack space as code and data too. Therefore, if you need more memory than the area from 0x100 to 0xEFF allows, simply use the area from 0x100 to 0xFFF making sure you do not overwrite the four system registers. Then as one of the first things you do, point the stack pointer to use the memory area 0x000 to 0x0FF. This frees up about 250 bytes for code and data.

Instruction Set

There are 18 instructions in the Spew CPU. The instructions are always 16-bits wide (see Table 2).

The OSCALL instruction was created so that you could call the host with limited I/O support such as character in/out, terminate application, etc. You simply used the AH value of the corresponding INT 21h service as the second byte of the instruction. Only a limited number of services were allowed.

For example, to print a string of characters to the Host screen, you would use the following example:

@label1    gosub  @writeit
           db 'This is a test program for SPU.COM '
           db #0000

@label3    oscall #0000

@writeit   popb   @Ptr      ; pop pointer
           popb   @Ptr1     ;
@NextChar  rdi    @Ptr      ; get char
           pushb  %A
           lda    #0001     ; move pointer
           addw   @Ptr
           popb   %A
           pushb  #0000     ; test if 0
           popb   %status   ;
           sbba   #0000     ;
           jpz    @Done
           oscall #0006     ; write
           jp     @NextChar
@Done      pushb  @Ptr1     ; push pointer
           pushb  @Ptr      ;
           return

@Ptr       db #0000
@Ptr1      db #0000

Notice that when the code makes it to @writeit, it pops off the return value as the string pointer. It then reads the string, sending a character at a time to the host's screen using OSCALL #0006, until a null character is found. The code then places a new return value back on the stack and does a return. The new position for the return is now the next instruction after the string declaration, which is at @label3.

The code must do two pushes and pops since it can only push and pop a byte at a time, since the stack pointer is 16-bits wide. The ADDW instruction, however, can sign add to a word value, so the two bytes in memory to store the current PC value, PTR and PTR1, must be in consecutive bytes and in the correct order.

The SPEW CPU does not have a CLC instruction like the 80x86 to clear the carry flag, so to clear out the zero flag, it pushes a value of zero into the status register. Since there is no "dangerous" bits in the status register, like the Direction Flag of the 80x86, it is safe to write all zeros to the register. Please note that the JPZ instruction is not "jump if parity zero", it is the "JumP if Zero" instruction.

Another example of one of the instructions is the ability to read the hosts memory from 0x00000 to 0x00FFF. This was added so that a SPU app could read certain parts of the hosts BIOS data for things like the current shift state, master clock count, current screen mode, etc. This instruction, called the RDSYS instruction, is read only and does not allow you to write to this area.

Since an instruction is 16-bits wide and a memory access is only 12-bits wide, most instructions use the high nibble as the instruction and the remaining 12-bits for the memory operand.

The Jump if Condition instruction uses the high nibble for the instruction, the next nibble for the condition, and the lower byte for the signed relative displacement to jump to. This instruction works very similar to the 80x86 instruction, where as a displacement of 0x00 jumps to the next instruction. This can be used as a NOP instruction. The assembler described below allows the NOP mnemonic and simply output a JPZ 0x00 instruction.

The Assembler

To simplify the assembler, it requires all operands to start with a specific character to indicate what type of operand it is. For example, a label must start with the @ character, while an immediate value must start with the # character and be four digits long, and a register to start with the % character.

The assembler does not check for errors. It assumes that all code is valid. It also only allows 255 characters per line, 50 16-byte symbols (labels), and the total source file must be 32k or less.

Math equations are not allowed.

The following line should not be used. Multiple values on a DB line also should not be used.

db #0000+#0001

I am sure that it would be a simple task to expand these limitations, but for simplicity, I have left them as so. If you improve upon the assembler's functionality, please contact me. I would like to see your work.

As with most assemblers, the semicolon is used for comments.

Since the emulator overwrites the first 256 bytes of the SPU image, the assembler writes a comment to these 256 bytes, with the last character being an EOF character (0x1A). The reason is so that you can use the DOS TYPE command and view the comment up to the EOF character. This way, you have 255 bytes to create a specific comment for each of your SPU files. In some cases, the source code to the SPU image fits in this 255-byte area. The assembler is currently hard-coded to a specific comment, but modifying it to ask for the comment, either from stdin or a filename on the command line, shouldn't be difficult.

To use the assembler, the name of the source file must be in the second character position after the SPU on the command line; for instance, the assembler assumes the filename starts at the first byte in the command line, offset 0x82 in the PSP. The assembler also assumes the .SAM extension for the source file and the .SPU extension for the output image file. These extensions should not be used. The assembler's usage is:

SPU demo

This takes demo.sam, assembles it, and produces demo.spu.

The Emulator

One of the members of our team also included DICE, a really nice emulator/debugger that lets you single step through your code. Its usage is:

DICE /s demo.spu

The /s parameter is used to simply emulate the demo.spu image. Remove the /s parameter to use the debugger.

Conclusion

We had a lot of fun coding for this competition. It was exciting to see what we could come up with. To get the results and source code to this competition, visit http://www.hugi.scene.org/compo/compoold.htm#compo9. You can also view other competitions we had on that same page.

And again, you can get the SPEW assembler, source code, the debugger, and detailed information here and at www.frontiernet.net/~fys/spu.htm.

Terms of Service | Privacy Statement | Copyright © 2024 UBM Tech, All rights reserved.