In the Fall of 2001 I wrote a simple (very partial) simulator for the Motorola 6811 microprocessor. My only goal was to give students a feel for object-oriented techniques using a non-trivial example that connected with their previous knowledge. (The students knew what a 6811 microprocessor was and how it behaved.)
After presenting the basic design of the simulation engine, I pointed out that some details had been glossed over. The most obvious limitations were the complete absence of a user interface and the very limited machine language instructions that could be simulated.
Nonetheless, I felt that the basic design worked well and that it would be interesting to pursue it. The result is this project.
It would be disengenuous to claim that "filling in the glossed-over details" was simple. It was not! Nonetheless, the original design has proved to be basically sound. Alas, nurturing the idea from conception through childhood and eventual usability has taken more time than I had anticipated.
This paper describes the basic simulation engine for a processor.
Note: Two important aspects of a useable simulator are not described here:
The goals set for the project are:
There are many possible approaches to designing a microprocessor simulation architecture, but the granularity of the model is one of the first things to consider.
The system could be simulated at the internal model level, the external signal level, the bus-cycle level or the functional level. Let's look at these possiblities.
The maximum granularity would be achieved by simulating the processor using a model of its internal organization. For example, a VHDL description could be used. However, this level of detail is clearly overkill for a simulator of a processor that is already available and known to work. (The internal model simulation would, of course, be appropriate during the design of the processor itself.) Furthermore, not only is the detail unnecessary, it would substantially slow down the speed of the simulation. Even more importantly, it would be a great deal of work to create the model and it is unlikely that the manufacturer would make its model freely available. In short, it is a "no brainer" to reject this level of granularity for the simulator.
The next level of granularity simulates the processor's external connections. For example, simulating the 6811 at this level would involve the crystal clock, signals such as AS and the multiplexed bus. The specifications for these signals are published by the manufacturer and readily available. Such fine-grained simulation would offer the considerable advantage of plugging the simulator into a general purpose circuit simulator thus allowing the complete simulation and debugging of the hardware and software components of a complete system.
However, this level of detail will slow down simulation and is not required when only the software and functionally-defined external hardware is being simulated and debugged. Implementing all aspects of this level including setup and hold times, rise and fall times loading factors and so forth would be onerous.
The coarsest granularity needed for software simulation is the bus cycle. (Yes, assembly language programmers do consider bus cycles.) Each bus cycle (read, write or idle) is simulated. This gives almost as much power as the external signal level, but will run faster and be less tedious to implement. Furthermore, external hardware whose functionality is defined can be simulated at this level.
The coarsest granularity possible for a simulator of machine language would be a functional one. This could offer the fastest performance, but could make the simulation of arbitrary devices unduly complex. (Actaully, I am not sure about this. I think a functional approach is possible with reasonable programming effort; it would offer a considerable performance boost.)
I have chosen to implement the simulator at the bus cycle level of granularity. Frankly, I chose this method at the outset and did not even consider other levels of granularity. It was only after writing this analysis that I became quite interested in examining simulation based on higher and lower levels of granularity.
In the case of the 6811, moving the simulation to the crystal clock level (instead of the bus cycle level) is probably not too difficult. Basically, the bus cycle is split into four phases and the appropriate external signals are set or monitored at each phase. This kind of crystal-clock simulation would degrade speed by a small amount. Alas, taking timing parameters (setup/hold/rise/fall times) and loading factors (resistive and capacitive) would add considerable complexity.
The functional approach is also very interesting and might provide a significant performace boost (maybe a factor of 2 or even an order of magnitude!). With the current approach, every single bus cycle is simulated; this is prudent, but most bus cycles have no side effects (such as setting a status bit waiting for this particular cycle). A clever functional-level simulator could detect instructions (or even groups of instructions) that cannot have side effects related to cycle count. These instructions could be simulated in-line without the overhead of cycle-by-cycle simulation.
The most important design decision was to limit the project to the pure simulation engine and defer questions relating to user interface issues to a separate software development stage. (However, both stages could, and did, procede concurrently.)
The importance of this decision cannot be overemphasized. There were two major consequences:
As a collorary to this decision, there is no code in the engine that communicates directly with the user or reads user-defined files. The engine deals only with Memory Spaces, Cells and CPUs. Some of the things the engine does not deal with are:
The engine has no user-friendly mechanism (such as a configuration file) for defining what addresses are mapped to specific devices (such as RAM, ROM, EEPROM, internal/external devices, etc.) However, the engine does provide mechanisms that a user interface can exploit to accomplish these objectives.
Any user interface must allow for the initialization of memory from (for example) Motorola S19 or Intel Hex records. Once again, the engine has absolutely no code to parse S19 or Intel Hex records; it merely provides an API that a third party can exploit to furnish these important user interface features.
Despite the separation between user interface and basic engine, I was certainly aware of the potential needs of user interfaces as the basic engine was being implemented. Indeed, there are some basic mechanisms built into the engine specifically designed for user interfaces. These include the Warning and CellChange features that will be described later.
I chose the Bus Cycle Simulation model for the simulation engine. This means that every bus cycle (initiated from the core processor) is simulated. Each bus cycle either READs something from somewhere, WRITEs something somewhere, or twiddles its thumbs in an IDLE cycle. (Of course, the IDLE cycle is not totally brain-dead; these cycles are used by the core processor to perform necessary tasks.)
This strategy implies that there is at least one object that can initiate bus cycles and that there are at least one object that can respond to READ and WRITE bus cycles.
I use a single CPU object to initiate bus cycles. The READ/WRITE cycles communicate with a Memory System which is composed of one or more MemorySpaces. Each MemorySpace contains a collection of Cells; it is the individual Cells within a MemorySpace that collaborate with READ/WRITE bus cycles.
To summarize, the bus-cycle design implies three basic classes:
The following sections treat each of these fundamental objects.
The fundamentals of the memory system were designed for any type of processor. In particular, the abstract design does not assume a specific memory space size or the number of bits transferred in a bus cycle.
In addition, no assumptions are made about the number of memory spaces used by a processor. Some processors have only a single memory space (such as the 68hc11 or the 68xxx) that is mapped to RAM, ROM, and devices. Other processors (such as many DSP chips that use a Harvard architecture in which the data and program memory spaces are distinct or the Intel 80x86 family that has separate I/O and ordinary address spaces) have more than one memory space.
The design of the memory space abstraction does not limit the number of memory spaces that a processor may support nor does it define the size of memory space cells or the size of a memory space. (In short, the abstraction allows arbitrary address bus and data bus widths for each memory space.)
A Memory Space is a concept. It is not an implementation. What it does (not how it does it) is important.
A memory space is a collection of cells. Cells are also abstractions; they may be bytes, 16-bit entities or anything else. The Cell abstraction is examined later; the Memory Space abstraction makes no assumptions about how the Cell abstraction works.
In Java, the most general way to describe an abstract conceptual design with no implementation is with an interface. The Memory Space abstraction merely states that a Cell is associated with each possible address. An abridged version of the interface is given here:
public interface MemorySpace {
Cell getCell(int address);
void setCell(int address, Cell cell);
void init();
}
The interface does not describe how methods like
getCell(int) are implemented. If the address space is
big (eg. 32 bits) and (hence) it is likely that it is not fully
populated, then some form of hashed implementation is appropriate.
Our target, however, is a simple processor with a mere 64K (16-bit)
address space. Consequently, the only implementation of a
MemorySpace provided is one for 64K Cells which are
maintained in a simple array. An abridged version of the source code
is:
public class MemorySpace64K implements MemorySpace
{
private Cell[] cells = new Cell[0x10000];
private static final MemorySpace INSTANCE = new MemorySpace64K();
public static MemorySpace getInstance() {return INSTANCE;}
private MemorySpace64K() {} //private to ensure singleton property
public final Cell getCell(int address) {return cells[address];}
public void setCell(int address, Cell cell) {cells[address] = cell;}
}
Note that the tiny 64K addressing space can be easily implemented as a
simple array. Note also that the MemorySpace64K class is
implemented as a singleton. (Refer to GoF for definition
of what a singleton is.) In this case, there is NO
public constructor; the only way to get a MemorySpace64K
object is with MemorySpace64K.getInstance().
A Cell is mapped to an address in a Memory Space. Specific cells are
obtained using the MemorySpace interface. Once a cell
has been obtained, its contents can be examined or modified subject to
constraints based on the specific nature of the cell.
The Cell interface allows the contents to be obtained or modified in two different ways: "get/read" to obtain the contents and "set/write" to change them. Broadly speaking the "get/set" methods allow the direct manipulation of a cell's content; the "read/write" methods simulate read (write) bus cycles.
The distinction between "set/write" is particularly clear when
referring to ROM cells. By definition, you cannot write to ROM.
(Note that a real processor would not blink when a write bus-cycle had
a ROM cell as its destination; the CPU would consume some bus cycles,
but the READ-ONLY memory location would not be changed.) BUT you have
to able to set the contents of ROM locations. In real life, you would
have to burn your desired contents into a ROM. In simulated life,
the set method makes it possible to directly change the
contents of a ROM cell; a write cycle would, of course, have no
effect.
Note that an instruction that modifies memory (such as a
staa instruction) would initiate a Write cycle to modify
the memory; it would not use the set
method. If the destination of the write cycle were in ROM, the
contents would not be changed.
The (abridged) Cell interface is:
public interface Cell {
void write(int contents);
int read();
int get();
void set(int contents);
void reset();
int getAddress();
void addCellChangeListener(CellChangeListener l);
void removeCellChangeListener(CellChangeListener l);
}
Note the addCellChangeListener() and
removeCellChangeListener() methods. The intent is to
give user interface implementors a hook so that they can be informed
of the changes to the contents of a cell.
The implementation of cells is roughly described in the diagram:
interface Cell *-----1 MemorySpace
|
|
|
AbstractByteCell *-----1 CPU
|
|
|
--------------------------------------------------
| | | |
| | | |
RAMByteCell ROMByteCell UnusedByteCell ...various SpecialByteCells
Note that the Cell interface is associated with a MemorySpace. The
parent class for all concete implementations of byte-sized cells is
the AbstractByteCell class. This class is associated
with a CPU class that we will discuss later on.
public class AbstractByteCell implements Cell {
int contents;
int nWrites;
int nReads;
int address;
ArrayList listeners = new ArrayList();
CPU6811 cpu = CPU6811.getInstance();
public AbstractByteCell(int address, int contents) {
this.address = address; this.contents = contents;
nWrites = 0; nReads = 0;
}
public int get() {return contents;}
public int read() {
nReads++;
cpu.incrementReadCycles();
return contents;
}
public void set(int contents) {this.contents = contents;}
public void write(int contents)
{
nWrites++;
cpu.incrementWriteCycles();
set(contents);
}
public int getAddress() {return address;}
public void addCellChangeListener(CellChangeListener l) {}
public void removeCellChangeListener(CellChangeListener l) {}
}
NOTES:
get/set methods) is trivial.The read/write methods keep track of the number of
times the cell is read(written) and inform the CPU of the read/write
cycles. (The CPU maintains a global count of the total number of
cycles, read cycles and write cycles.)
Why keep track of the number of times an individual cell is read or written to? The short answer is: "Why not?" It is very easy to do and the penalty in computation and memory usage is tiny. However, it is also a fact that the user interfaces to the simulation engine currently being developed (Summer 2002) make no use of this information.
The question then becomes: "Why track individual cell read/writes if nothing is being done with the information?" Good question! But the answer is simple: "This information could be used to perform code coverage analysis (by checking how many memory locations that correspond to instructions have been read), profiling and other things". The mere fact that no current user interface (as of mid-September 2002) exploits this mechanism does not mean that these capabilities could not be exploited by future user interface designers.
getAddress() method implies that Cells are aware of
their address. The astute reader may notice a bug here: the address
of a Cell is insufficient to identify it unless the memory space is
known. Fortunately, the only concrete implementation of the simulator
framework is for the 68hc11 which has only one memory space. (The
memory space is implemented as a singleton and, hence, is always
knowable within the package.) If a processor with more than one
address space were to be simulated (e.g. the Intel 80x86 with its
separate memory and I/O address spaces), each Cell would have to know
both its address and its memory space.
The CPU itself is the third major component of the simulation engine.
(The other two major components are the MemorySpace and Cell
interfaces and implementations.) Unlike the the other two majors, the
CPU does not (at present) have a higher level abstraction such as a
Java interface or abstract class. Only the CPU6811 is
implemented.
The CPU6811 class is implemented as a singleton. Clients
obtain a reference to the cpu with code like:
CPU6811 cpu = CPU6811.getInstance();
Thus all clients are guaranteed to be working with the same 6811 cpu engine.
The (abridged) source code in CPU6811.java that ensures this is:
public class Sim6811 {
private static final CPU6811 instance = new CPU6811();
public static CPU6811 getInstance() {return instance;}
private CPU6811() {} //Private constuctor; clients CANNOT create instance
}
The implementation of the CPU6811 class is divided into several components including:
Each of these portions is discussed in greater detail in the following sections.
Each register is declared as a simple primitive data type and given arbitrary initial values as shown in the following code segment. Note that each bit in the Condition Code register is given its own variable.
private int AccA = 0x12;
private int AccB = 0x34;
private int PC = 0x6000; //Standard starting address at RyersonU
private int IX = 0;
private int IY = 0;
private int SP = 0xff; //?Standard BUFFALO monitor stack?
private boolean CC_Z = false;
private boolean CC_N = false;
private boolean CC_C = false;
private boolean CC_V = false;
private boolean CC_H = false;
private boolean CC_I = true;
Each register has its own public get/set methods. For example:
final public int getAccA() {return AccA;}
final public void setAccA(int i) {AccA = i;}
The CPU engine maintains statistics on the total number of reads, writes, number of instructions executed and number of bus cycles simulated with the following variables and initial values:
private int totalWrites = 0;
private int totalReads = 0;
private int totalNInstructions = 0;
private int nCycles = 0;
The CPU is informed when a read, write or idle cycle occurs. For example, if the execution of an instruction performs a read cycle, it must also invoke the following CPU method:
public final void incrementReadCycles()
{
totalReads++;
incrementCycles();
}
Whenever any bus cycle occurs, the CPU must be informed with the
incrementCycles() method: i.e. this method is invoked
for every E-clock cycle. Thus it is invoked often--one
million times per simulated second--and must be efficient. The code
is:
public final void incrementCycles()
{
nCycles++;
TimedEvent event = (TimedEvent) pendingTimedEvents.tickAndRemove();
if (event != null) {
event.doAction();
}
}
Clearly, the incrementCycles() method invokes the method
tickAndRemove() every time. Even
without knowing why we do this and what the method does, it is evident
that it must be fast if the simulation engine is to be fast. It is
indeed an important element in the architecture of the simulator;
however, the details of what it does is deferred until later in this
document.
We have now described most of the scaffolding in the
CPU6811 class and the associated
MemorySpace and Cell classes that allow the
CPU to perform its central job: fetching and executing
instructions stored in its Memory Space.
An abridged (and slightly inaccurate) version of the CPU's
step() method, which fetches and executes a single
insruction, is shown below:
public final InstructionEffects step()
{
Instruction inst = fetchInstruction();
InstructionEffects effects = inst.execute();
totalNInstructions++;
checkInterrupts();
return effects;
}
I hope that the code is (almost) self-explanatory: we fetch an instruction, execute it, update the number of instructions statistic and, when the execution is complete, check if there are any pending interrupts. (Note that, once again, the simulation code mimics what the real processor does; like the code, the real hardware only checks for interrupts after and instruction has finished.)
But how is an instruction fetched and then executed? Let's look at these details. (These are implementation details that are written as private methods.)
Let's start with another private method: fetchOpCode():
private final int fetchOpCode()
{return mem.getCell(CPU6811.PC++).read();}
This simple method (it's only a single line of code) relies on many of
the archtectural features of the simulation engine's design. First,
mem is a private variable in the CPU6811's object that
contains the Memory Space involved in the simulation. We then obtain
the specific Cell (or byte in this case) at the address specified by
the Program Counter (and we also increment the PC just like the real
hardware in the 6811 CPU.) Finally, we invoke the read()
method on that cell and obtain its contents as an int; in
short, we get the first byte of the instruction. (Note that this
also mimics what is going on in the real hardware state machine
implemented in the actual 6811 CPU.)
Let's now look at how an instruction is fetched with the
fetchInstruction() method:
private final Instruction fetchInstruction()
{
int opCode = fetchOpCode();
switch (opCode) {
//pre-byte instruction stuff not shown
default:
Instruction inst = OpCodes.Opcodes[opCode];
}
return inst;
}
The op-code of all 6811 instructions is one or two bytes long. Over 90% of the instructions have the op-code encoded into the first byte of the instruction. The other instructions have their op-code encoded in two bytes: a pre-byte (which must be 0x18, 0xCD or 0x1A) followed by a second byte which completely specifies the instruction and its addressing mode. For simplicity, the abridged code above and the following discussion assume that only instructions with a one-byte op-code are simulated. Note, however, that the op-code is not the whole instruction; most instructions (except for Inherent mode instructions) also require an operand (encoded in machine language) following the op-code. (The truly curious reader is invited to examine the real source code to see how instructions with a pre-byte op-code are handled.)
Once we have an op-code (which will be an integer in the range
0--255), we can retrieve an Instruction from an array of
Instructions indexed by the op-code.
But what is an Instruction?
An Instruction is an interface:
public interface Instruction {
//constants omitted from abridged code
public int execute();
public String toDisassembledString(); //Not discussed here
}
Every Instruction object in the array of instructions (indexed by
op-code) implements this interface. But every one is different! Each
one is a real class (not an interface). In addition, each one extends
an abstract class that implments the interface. This class is
AbstractInstruction.
Let's have a look at this AbstractInstruction class.
Before getting into details, let me first note that it is the biggest class (measured by lines of source code) in the engine package. (It is about 600 lines of code including comments.) The size of this class is enormous because it allows its sub-classes (the real instructions) to inherit (use) its library of useful methods.
There are dozens of such utility methods in the abstract class.
As a simple example, many instructions need to read a byte from some
address; they can use the inherited read8() method shown
below:
int read8(int address) //AbstractInstruction method
{
int data;
data = (int) mem.getCell(address).read();
data &= 0xff;
return data;
}
(Note that the read() method for a cell will increment
the number of cycles so the programmer does have to remember to do this.)
For a more complex example, many instructions need to add two bytes
and set the N, Z, V, C and H bits of the Condition Code register
according to the result. Rather than clutter all of these
instructions with the messy details of how this is done, they can use
the inherited add8() method shown below:
final public int add8(int p, int q) //AbstractInstruction method
{
int result = (p + q)&0xffff;
setNZ8(result);
cpu.CC_C = (result > 0xff);
cpu.CC_V = (result > 0xff) != (((p&0x7f) + (q&0x7f)) > 0x7f);
cpu.CC_H = ((p&0xf) + (q&0xf) > 0xf);
return (result & 0xff);
}
Every actual instruction extends AbstractInstruction (or
another derived abstract class) and
fills in a few details such as what the instruction really does (in
the execute() method.) For example, the
AbaInh class (which implements the aba
inherent mode instruction that adds Accumulator B to Accumulator A) is
shown below:
public class AbaInh extends AbstractInstruction
{
private CPU6811 cpu = CPU6811.getInstance();
final public int execute()
{
cpu.setAccA(add8(cpu.getAccA(), cpu.getAccB()));
cpu.incrementCycles();
return -1;
}
final int getAddressingMode() {return Instruction.INH;}
final protected String getOpSymbolic() {return "ABA";}
}
When a user interacts with the simulation engine to run at full speed, the engine may be busy for a long time. The simulation will stop when a breakpoint or stop instruction is reached or when the user explicitly terminates the run. Since the user input has to be monitored and a possibly infinite number of instructions have to be simultaneously simulated, a separate thread of execution is required for the simulator while the main thread continues to monitor user requests.
The CPU's go() method creates and returns the Thread.
An abridged version of the source code is shown below:
public Thread go(int maxNInstructions)
{
setState(RUNNING);
Thread goThread = new Thread ( new Runnable() {
public void run() {doFastSimulation(); }
} );
return goThread;
}
The doFastSimulation() (code not shown) calls
fastStep() in a tight loop and checks if a breakpoint has
been hit or the user has requested to stop the simulation. The
fastStep() method code is shown below:
public final int fastStep()
{
int rc;
Instruction inst = fetchInstruction();
totalNInstructions++;
rc = inst.execute();
checkInterrupts();
return rc;
}
When I demonstrated my initial very limited version of the 6811 simulator (which simulated a half dozen instructions but did incorporate most of the core ideas described in this document) to my colleague Peter Hiscocks, he commented, "Ken, this looks interesting but, you know, there are over 300 instructions in the 6811." My initial reaction was "So what... the design is architecturally sound...I'll worry about the details later..."
However, I soon encountered the abyss: "Oh... If each instruction requires a separate class of about 15 lines of Java code and there are 300 instructions, I have to write nearly 5000 lines... Oops!"
I decided to write a text file describing each instruction in one line. Some typical lines are:
aba inh 1b f adca imm8 89 t adca dir8 99 t adca ext8 b9 t adca ix8 a9 t
The fields indicate the symbolic assembler, the addressing mode, the
machine language opcode and whether there are more than one addressing
modes. I wrote another program (a Perl script) to read these lines
and translate each one into Java source code for the instruction. The
generated source code had to be completed by hand; this meant
implementing the execute() which was simple to do. (Yes,
it was somewhat tedious, but much less so than writing
these 5000 lines of code by hand!)
The treatment of instructions with more than one address mode was different. In these cases, an abstract version of the instruction was generated and a separate concrete class for each addressing mode was created.
For example, the ldaa instruction generated the following
abstract class:
public abstract class LdaaAbstract extends AbstractInstruction
{
private CPU6811 cpu = CPU6811.getInstance();
final public int execute() //This method was written manually
{
int op = getOperand();
cpu.setAccA(op);
setNZ8(op);
cpu.setCC_V(false);
return -1;
}
final protected String getOpSymbolic() {return "LDAA";}
}
The automatically generated code for the ldaa using the
Extended addressing mode is:
public class LdaaExt extends LdaaAbstract {
private CPU6811 cpu = CPU6811.getInstance();
final public int getOperand() {return getEXT8Operand();}
final int getAddressingMode() {return Instruction.EXT8;}
}
(Notes: the getOperand() concete method is used by the
simulator to obtain the actual operand; the
getAddressingMode() method is only used by the disassembler.)
With this hierarchy of classes, I only had to customize the
execute() method in the abstract class rather than in
each individual addressing mode instance of the LDAA instruction.
Besides reducing typing (or cutting and pasting), any bugs in the
implementation of execute() were conveniently
encapsulated in one place.
To summarize, the architecture for implementing Instructions is broadly described in the following diagram:
interface Instruction
|
|
AbstractInstruction
|
|
-----------------------------------------------------------....
| | |
| | |
ClraInh(custom execute) LdaaAbstract(custom execute) ...and many more...
|
|
--------------------------------------------
| | | | |
LdaaDir LdaaExt LdaaImm LdaaIndX LdaaIndY (no customization)
Testing software is often forgotten or pushed to the background during development. Professors may gripe about this and insist on some sort of testing procedure, but they are sometimes just as guilty in ignoring this essential aspect of software implementation.
I have certainly been guilty of this sin, justifying the poor testing with the standard excuses, "Hey, I have to get this thing out the door! Let's worry about testing later. Indeed, let the users (aka "guinea pigs") do the testing for me."
Recently, however, I have discovered the magic of unit testing and the Junit implementation of this technique. My mastery of this technology is still weak (mastery involves knowing how to use it and, more importantly, practising the discipline of using it), but I have tried to exploit it while the engine code was being developed.
An aphorism that describes unit testing is "Code a little, test a
little". In the past, I often implemented this simple idea by
littering code with println debugging statements.
Unfortunately, the litter had to be removed (or commented out) at some
later stage; furthermore, the litter was sometimes only informative
(eg. a certain block of code has been reached with such and such
conditions) or, at other times, actually did some verification.
Unit testing is as simple as inserting debugging code, but offers the huge advantage of not clutterring the implementation code. You never have to delete debugging code from the implementation and can continue to run the tests no matter how the implementation code evolves. This gives you automated regression testing.
In addition, unit testing forces the programmer to write tests that actually test something (instead of simply providing information.) This tends to focus the mind at the problem at hand and can result in cleaner designs and implementations.
One surprising advantage to unit testing during development involves writing the test code prior to coding the implementation and even writing tests you expect to fail.
DeltaList
Most of the intellectual portion of the design/implementation of the
simulation engine is found in the abstract object-oriented
architecture (the design of its data rather than its
algorithms.) One of the abstractions used in the design
whose algorithmic implementation was a tad more complex than most was
the DeltaList. The steps in its design and
implementation (including the use of unit testing) are summarized here.
Recall that one aspect of the simulation engine's efficiency is the way it can handle bus cycle timed events. My first decision was to use a delta-time list as both the design and implementation of this aspect; indeed, the object implementing the basic idea is called a "DeltaList".
Before implementing code, I realized that the standard implementation
of this idea was not necessarily the best one in all
circumstances. (For example, the idea could be implemented with a
standard Priority Queue algorithm instead of a linked list.)
Consequently, I tried to write the public documentation for the
DeltaList class so that it did not imply any particular
implementation.
Initially, I wrote a test case for a DeltaList object and
implemented it with stubs.
The initial test was:
// Add a single item, check size and delete when expired.
public void testSimpleDelta1() {
DeltaList deltaList = new DeltaList();
assertEquals(deltaList.size(), 0);
//Add an event to fire after 3 ticks
TimedEvent item3 = new TimedEvent(3);
deltaList.add(item3);
assertEquals(deltaList.size(), 1); //List only contains single item
assertEquals(deltaList.tickAndRemove(), null);
assertEquals(deltaList.tickAndRemove(), null);
assertEquals(deltaList.tickAndRemove(), item3);
}
The initial implementation used stubs. An abridged version is:
public class DeltaList {
public DeltaList(){}
public int size() { return 0;}//STUB size is ZERO
public void add(DeltaTimed item){} //STUB does NOTHING
public DeltaTimed tickAndRemove(){return null} //STUB does NOTHING
}
Why, you may ask, go to all the bother of creating test cases that will fail because the implementation itself (only stubs) guarantee failure? The big advantage: the basic code and testing framework can be written, compiled and run. (Note that public documentation should be written at this stage as well.)
Even with this stub implementation, the first test
(assertEquals(deltaList.size(),0);) will actually pass!
The next test (checking that the size of the list is one after adding
an item) is expected to fail. Indeed, this is exactly what happened.
This expected result (including the failure) gives a programmer
confidence that they are doing at least something right and that it is
time to start replacing the stubs with real implementations.
I added implementation and more tests. I concentrated on "boundary condition" tests (where, experience has taught me, bugs often occur). Happily, these tests all worked.
I then implemented a test to mimic the example given in the public
documentation of the class. (The details are described in the public
documentation for the DeltaList class.) An abridged
version of this test is shown here:
// Try out the Moo, Foo Goo example in the public docs
public void testSimpleDelta5() {
DeltaList dl = new DeltaList();
TimedEvent foo5 = new TimedEvent(5); dl.add(foo5);
TimedEvent bar8 = new TimedEvent(8); dl.add(bar8);
//do 3 ticks... assertEquals(dl.tickAndRemove(), null); // 3 times
//now add goo (after 4 additional ticks) and moo(1 tick later)
TimedEvent goo7 = new TimedEvent(4);
TimedEvent moo4 = new TimedEvent(1);
dl.add(moo4); dl.add(goo7);
assertEquals(dl.tickAndRemove(), moo4);
assertEquals(dl.size(), 3);
assertEquals(dl.tickAndRemove(), foo5);
assertEquals(dl.size(), 2);
assertEquals(dl.tickAndRemove(), null);
assertEquals(dl.size(), 2);
assertEquals(dl.tickAndRemove(), null);
assertEquals(dl.tickAndRemove(), null);
assertEquals(dl.tickAndRemove(), goo7);
// assertEquals(dl.tickAndRemove(), goo7);
// assertEquals(dl.tickAndRemove(), bar8);
}
Alas, the test failed...oops. What to do when a test you expect to work does not work?
Some of the choices:
I decided to add information to the test. The (abridged) test now looked like:
public void testSimpleDelta5() {
//...(deleted)...same as before...
//do 3 ticks... assertEquals(dl.tickAndRemove(), null); // 3 times
//now add goo (after 4 additional ticks) and moo(1 tick later)
TimedEvent goo7 = new TimedEvent(4);
TimedEvent moo4 = new TimedEvent(1);
dl.add(moo4); dl.add(goo7);
assertEquals(dl.tickAndRemove(), moo4);
assertEquals(dl.size(), 3);
assertEquals(dl.tickAndRemove(), foo5);
assertEquals(dl.size(), 2);
assertEquals(dl.tickAndRemove(), null);
assertEquals(dl.size(), 2);
assertEquals(dl.tickAndRemove(), null);
assertEquals(dl.tickAndRemove(), null);
assertEquals(dl.tickAndRemove(), goo7);
// assertEquals(dl.tickAndRemove(), goo7);
// assertEquals(dl.tickAndRemove(), bar8);
}
I could now run the test, redirect stdout to a file and
examine it. The output was:
DELTA test moo, foo, bar, goo... New delta list: [] After adding foo5: [Delta: 5] After adding bar8: [Delta: 5, Delta: 3] After 3 ticks: [Delta: 2, Delta: 3] After adding moo4: [Delta: 1, Delta: 1, Delta: 3] After adding goo7: [Delta: 1, Delta: 1, Delta: 4, Delta: 1]
All went well until:
which should have been:After adding goo7: [Delta: 1, Delta: 1, Delta: 4, Delta: 1]
This erroneous list representation caused all subsequent tests to fail.After adding goo7: [Delta: 1, Delta: 1, Delta: 2, Delta: 1] // i.e. 3 ticks already so ^moo4 ^foo5 ^goo7 ^bar8
I now had a fairly detailed view of the internal representation of the delta list and could focus on the "dumb code" I had written. For the mobidly curious, only one line had to be added:
//...and set the delta of the item being added accordingly item.setDelta(itemAddTime);
Colophon: This html rendition is derived from the XML file
com/kclowes/sim11/docs/DesignAndImplementation.xml. It was
translated to html with the XML translation specification
in ./article2html.xsl using a
standard xslt
command written in Java. The source file was written by
Ken Clowes (kclowes@ee.ryerson.ca). The dtd and xsl files
were written by kclowes. Everything was written using
xemacs and maintained using
make and the bash shell under
WindowsME, Solaris and Linux operating systems.