Before I get to the topic of this post, I'll tell you where I got the idea for my blog's name. When I was trying to decide on a title, I knew I wanted something which was relevant to my project, but also was reminiscent of Infocom. It didn't take long to find. After I made my choice, I felt it was particularly apt considering my goal is to recreate the Z-machine, which runs quite possibly the most 'classic' games of all, using a modern language and object oriented design principles. So how is it related to Infocom? My favorite Infocom game is 'The Lurking Horror'. In it, you play a college student at G.U.E. Tech who is trying to finish an assignment at the last minute in the campus computer lab during a winter snowstorm. You begin the game in the lab holding an assignment. If you read the assignment (which is not needed to win the game), you'll find the name of the course is "The Classics in the Modern Idiom".
Even if you are an old pro at Infocom's text adventures, sound is not likely to come to mind when thinking about them. That's because few Infocom games actually made sounds at all. Of the thirty or so games Infocom released just two had sound effects: The Lurking Horror and Sherlock. To make matters worse, only selected versions of those two games actually played sound effects. Beyond this there were nine other games which could make simple beeping sounds referred to as 'bleeps' in the Z-machine standards document. Long after the age of Infocom came to a close, the Z-machine was extended to play music as well, but we'll get to that a bit later.
All sound effect manipulation in the Z-machine, including loading, playing, stopping, and unloading is done using the seriously overloaded sound_effect opcode #245. A remark at the bottom of the table of opcodes:
The notation "5/3" for sound_effect is because this plainly Version 5 feature was used also in one solitary Version 3 game, 'The Lurking Horror' (the sound version of which was the last Version 3 release, in September 1987).
I take issue with that statement because several version 4 games also make use of the sound_effect opcode, including 'Trinity', 'A Mind Forever Voyaging', and 'Bureaucracy'. What I think the author of the standard was getting at is only one version 3 game played sampled sound effects. It would be a mistake to fail to include support for the sound_effect opcode in version 4 games.
The sound_effect opcode is rather messy to implement due to the way its operands are handled. It can take 1 to 4 operands. The first operand is the sound effect number. A value of 1 indicates a high pitched beep should be played, while 2 indicates a low pitched one. Values 3 and higher indicate sampled sound effects and require additional operands. A value of zero means all sounds and is allowed only if a second operand is provided and has a value of 3 or 4 which means stop all sounds and unload all sounds respectively (this was clarified in the 1.1 standard). If a sampled sound effect is indicated, a second operand is required. The additional operand has the following meanings: 1:load, 2:play, 3:stop, and 4:unload. Values 1 and 4 are merely hints as to what the game needs at any given time and may be implemented in any convenient way. If the second operand is 2 (play) then a third operand is required. The third operand's lower byte contains the volume to play the sound at. From version 5 onward, the upper byte contains the number of times to play the sound. In the single version 3 game with sampled sounds the sound either played once or looped forever until stopped. This looping information was contained in the sound file itself and not in the game code. Starting with version 5 a fourth operand can be supplied containing the address of a routine to be called when the sound completes but not if it is stopped prematurely by another sound being started.
In addition to the operand madness above, the behavior of playing sampled sounds can be complicated as well. Originally, it was meant to be simple: only one effect can play at a time and starting another will terminate a currently playing one. This becomes more complicated today because 'The Lurking Horror' plays several sounds in sequence. Computers at the time of the game's release would be slow enough to play each sound, but faster computers will cut off the sounds prematurely, so we need a mechanism to prevent this. Another complication is that the 1.1 update to the standard introduced the concept of 'music' as a second sound channel. Sound effects only interrupt other sound effects and music only interrupts music. When we play a sound, the channel is chosen using the file type of the sampled sound itself...yuck. It would have made far more sense to introduce a new opcode at this point, instead of complicating the behavior of sound_effect. The effort required to introduce a new opcode into existing interpreters is far less than the work required to support the new music file types needed and so would not have been an additional hardship on interpreter writers. One could make the argument that the chosen method did not require any updates to Inform to create games supporting music, but if you are going to do something, then I think it is worth doing it right.
In my implementation, I provide the full sound_effect capabilities from version 3 onward***. This includes the fourth operand which is restricted to version 5 and higher in the standard because the version 5 game Sherlock is the only Infocom game ever to use it. It also includes the 1.1 music extension which does not specify supported versions. I felt that the extra work to exclude features from version 3, then restrict them even further in version 4 only to reintroduce them in version 5 to be excessive considering all the existing games are compatible with the notion that these capabilities existed from version 3 onwards. The extra capabilities simply go unused in current version 3 and 4 games.
Next time...we'll see some code.
***Update: I've changed my mind on this (see next post).
Thursday, December 10, 2009
Thursday, November 26, 2009
Happy Thanksgiving
I just wanted to say Happy Thanksgiving.
I haven't posted in a while...The last month has been crazy with family members getting the flu and work demanding much of my time.
I will soon be posting about sound and music in the Z-machine, but for now I'm just going to leave you with this question: Can you guess where I got the title for my blog?
I haven't posted in a while...The last month has been crazy with family members getting the flu and work demanding much of my time.
I will soon be posting about sound and music in the Z-machine, but for now I'm just going to leave you with this question: Can you guess where I got the title for my blog?
Tuesday, October 27, 2009
Variable references and stack fun!
As I mentioned last time, there are some simple opcodes which are easy to get wrong on your first attempt at writing an interpreter. Section 14 of the Z-machine standard lists the complete table of opcodes and among these are seven which are listed as having a single operand marked as (variable). This means the operation uses the value of that operand as a variable number. This has nothing to do with variable operand types discovered while decoding the instruction.
To help us see what the standard means, we'll use the example of the load opcode. The description for load in the standard is "The value of the variable referred to by the operand is stored in the result." This sounds simple enough and we might try a naive implementation using the methods ReadVariable and Store like so:
ushort variable = this.Operands[0];
ushort value = this.ReadVariable(variable);
this.Store(value);
In most cases this will work properly but there is a corner case where it will fail, namely when the operand value is zero. In this case ReadVariable pops a value off the stack. What's wrong with this? Surely it is correct because section 6.3 of the standard says:
Writing to the stack pointer (variable number $00) pushes a value onto the stack; reading from it pulls a value off. Stack entries are 2-byte words as usual.
Unfortunately this case is not mentioned in the 1.0 standard but it is clarified in version 1.1:
Indirect variable references
----------------------------
In the seven opcodes that take indirect variable references (inc, dec,
inc_chk, dec_chk, load, store, pull), an indirect reference to the stack
pointer does not push or pull the top item of the stack - it is read
or written in place.
For these opcodes only, this behavior overrides that defined in the older standard.
Knowing this, a better implementation is:
ushort variable = this.Operands[0];
ushort value = this.ReadVariable(variable);
this.WriteVariable(variable, value);
this.Store(value);
This writes the value back to the variable immediately after reading, which in the above case would push the popped value back onto the stack. In all other cases, the write essentially does nothing since it is writing an identical value back into the variable. The other six opcodes can be implemented similarly by making sure whenever we read a variable we follow it with a write. I think this is a fairly clean way of dealing with the situation. Although it is possible to allow in-place reads/writes to the stack, doing so requires extras methods or extra parameters to the existing ones to change their behavior.
The rest of this post contains some of my random thoughts about stacks.
Typically a stack will have at least three methods, Push, Pop, and Peek. Sometimes Peek is referred to as Top, although I dislike that naming as it seems less descriptive to me. Push puts a value on the stack, Pop removes a value, and Peek let's you see the top element without removing it.
Why do we only allow read-only access to the top element? It is easy to imagine a method called Poke which allows in-place writes to the top element. If a Poke method seems like an abuse of the stack type, it makes me wonder if Peek might also be. Imagine a stack with just Push and Pop methods. No peeking allowed! You couldn't use the stack as a convenient holding area for the current working element. I'm curious as to what pressure for design changes this might exert and whether they would be good or bad.
Working on this reminded me of some comments about stacks on Eric Lippert's blog. Although I don't remember exactly when it was, the discussion involved whether 'Pop' should return a value or merely throw away the top element. I would argue that Pop should return the top element because it is the inverse of Push. One puts an element in, one takes an element out. With this arrangement, Peek is merely a performance optimization for a common set of operations! The equivalent of Peek could be achieved by a Pop followed by a Push of the same element back again. A hypothetical Poke method to allow in-place writes could just as easily be imagined to be a Pop followed by a Push of an altered value. It is interesting to me that this is a far less common case.
If you prefer Pop not to return a value, then it seems fair that Push not take a value, but rather create a default valued element. If you also added our hypothetical Poke method, you could set the new element to the value you want. From this point of view, Push accepting a value is just a performance improvement for a common set of operations!
What do you think?
To help us see what the standard means, we'll use the example of the load opcode. The description for load in the standard is "The value of the variable referred to by the operand is stored in the result." This sounds simple enough and we might try a naive implementation using the methods ReadVariable and Store like so:
ushort variable = this.Operands[0];
ushort value = this.ReadVariable(variable);
this.Store(value);
In most cases this will work properly but there is a corner case where it will fail, namely when the operand value is zero. In this case ReadVariable pops a value off the stack. What's wrong with this? Surely it is correct because section 6.3 of the standard says:
Writing to the stack pointer (variable number $00) pushes a value onto the stack; reading from it pulls a value off. Stack entries are 2-byte words as usual.
Unfortunately this case is not mentioned in the 1.0 standard but it is clarified in version 1.1:
Indirect variable references
----------------------------
In the seven opcodes that take indirect variable references (inc, dec,
inc_chk, dec_chk, load, store, pull), an indirect reference to the stack
pointer does not push or pull the top item of the stack - it is read
or written in place.
For these opcodes only, this behavior overrides that defined in the older standard.
Knowing this, a better implementation is:
ushort variable = this.Operands[0];
ushort value = this.ReadVariable(variable);
this.WriteVariable(variable, value);
this.Store(value);
This writes the value back to the variable immediately after reading, which in the above case would push the popped value back onto the stack. In all other cases, the write essentially does nothing since it is writing an identical value back into the variable. The other six opcodes can be implemented similarly by making sure whenever we read a variable we follow it with a write. I think this is a fairly clean way of dealing with the situation. Although it is possible to allow in-place reads/writes to the stack, doing so requires extras methods or extra parameters to the existing ones to change their behavior.
The rest of this post contains some of my random thoughts about stacks.
Typically a stack will have at least three methods, Push, Pop, and Peek. Sometimes Peek is referred to as Top, although I dislike that naming as it seems less descriptive to me. Push puts a value on the stack, Pop removes a value, and Peek let's you see the top element without removing it.
Why do we only allow read-only access to the top element? It is easy to imagine a method called Poke which allows in-place writes to the top element. If a Poke method seems like an abuse of the stack type, it makes me wonder if Peek might also be. Imagine a stack with just Push and Pop methods. No peeking allowed! You couldn't use the stack as a convenient holding area for the current working element. I'm curious as to what pressure for design changes this might exert and whether they would be good or bad.
Working on this reminded me of some comments about stacks on Eric Lippert's blog. Although I don't remember exactly when it was, the discussion involved whether 'Pop' should return a value or merely throw away the top element. I would argue that Pop should return the top element because it is the inverse of Push. One puts an element in, one takes an element out. With this arrangement, Peek is merely a performance optimization for a common set of operations! The equivalent of Peek could be achieved by a Pop followed by a Push of the same element back again. A hypothetical Poke method to allow in-place writes could just as easily be imagined to be a Pop followed by a Push of an altered value. It is interesting to me that this is a far less common case.
If you prefer Pop not to return a value, then it seems fair that Push not take a value, but rather create a default valued element. If you also added our hypothetical Poke method, you could set the new element to the value you want. From this point of view, Push accepting a value is just a performance improvement for a common set of operations!
What do you think?
Tuesday, October 20, 2009
Basic operations and branches
Now that we have some pieces in place to run operations, let's look at a simple operation for the Z-Machine that is used in all of its versions:
///
/// Operation 20 (ADD).
///
protected override void Operation20()
{
var num1 = (short)this.Operands[0];
var num2 = (short)this.Operands[1];
this.Store((ushort)(num1 + num2));
}
This obviously performs a simple signed addition and stores the result. Math and comparison operations in the Z-machine use signed numbers, but many other operations treat operands and memory values as unsigned.
Here's another:
///
/// Operation 3 (JG).
///
protected override void Operation3()
{
var num1 = (short)this.Operands[0];
var num2 = (short)this.Operands[1];
this.Branch(num1 > num2);
}
This operation compares two operands and branches if the first is greater than the second. I mentioned branch instructions before but now we will see exactly how they work.
protected void Branch(bool condition)
{
byte branchData = this.Memory.ReadByte(this.CallStack.ProgramCounter++);
var offset = (ushort)(branchData & 63);
if ((branchData & 64) != 64)
{
offset = (ushort)((offset << 8) + this.Memory.ReadByte(this.CallStack.ProgramCounter++));
}
if (condition ^ ((branchData & 128) != 128))
{
if (offset > 1)
{
this.Jump((short)(offset > 8191 ? offset - 16384 : offset));
}
else
{
this.Return(offset, this.CallStack.EndRoutine());
}
}
}
We begin by reading a byte pointed to by the program counter. The top two bits are used as flags, while the remaining six bits are the offset value. If the second highest bit is not set, we need to read another byte and combine this byte with the current offset to produce a single 14-bit signed offset. If the top bit is not set, then the branch condition is inverted and we branch on false instead of true. In any case, if the branch is taken, the program counter jumps based on the offset. There is a special case where if the offset is one or zero we return that value from the current routine immediately instead of jumping.
The actual jump is implemented as another method. This is simply because it is identical to the behavior of the unconditional jump operation (opcode #140), so I factored it out into a separate method even though it is just a one-liner:
protected void Jump(short offset)
{
this.CallStack.ProgramCounter += offset - 2;
}
The other math and comparison operators are implemented similarly. They are:
#1 Jump if equal (Sometimes used with more than two operands, in which case the branch is taken if the first operand is equal to any of the others)
#2 Jump if less than
#3 Jump if greater than
#20 Add
#21 Subtract
#22 Multiply
#23 Divide
#24 Modulus
#128 Jump if zero
Next time I'll look at some other seemingly simple operations that can be a source of problems for first time interpreter writers.
///
/// Operation 20 (ADD).
///
protected override void Operation20()
{
var num1 = (short)this.Operands[0];
var num2 = (short)this.Operands[1];
this.Store((ushort)(num1 + num2));
}
This obviously performs a simple signed addition and stores the result. Math and comparison operations in the Z-machine use signed numbers, but many other operations treat operands and memory values as unsigned.
Here's another:
///
/// Operation 3 (JG).
///
protected override void Operation3()
{
var num1 = (short)this.Operands[0];
var num2 = (short)this.Operands[1];
this.Branch(num1 > num2);
}
This operation compares two operands and branches if the first is greater than the second. I mentioned branch instructions before but now we will see exactly how they work.
protected void Branch(bool condition)
{
byte branchData = this.Memory.ReadByte(this.CallStack.ProgramCounter++);
var offset = (ushort)(branchData & 63);
if ((branchData & 64) != 64)
{
offset = (ushort)((offset << 8) + this.Memory.ReadByte(this.CallStack.ProgramCounter++));
}
if (condition ^ ((branchData & 128) != 128))
{
if (offset > 1)
{
this.Jump((short)(offset > 8191 ? offset - 16384 : offset));
}
else
{
this.Return(offset, this.CallStack.EndRoutine());
}
}
}
We begin by reading a byte pointed to by the program counter. The top two bits are used as flags, while the remaining six bits are the offset value. If the second highest bit is not set, we need to read another byte and combine this byte with the current offset to produce a single 14-bit signed offset. If the top bit is not set, then the branch condition is inverted and we branch on false instead of true. In any case, if the branch is taken, the program counter jumps based on the offset. There is a special case where if the offset is one or zero we return that value from the current routine immediately instead of jumping.
The actual jump is implemented as another method. This is simply because it is identical to the behavior of the unconditional jump operation (opcode #140), so I factored it out into a separate method even though it is just a one-liner:
protected void Jump(short offset)
{
this.CallStack.ProgramCounter += offset - 2;
}
The other math and comparison operators are implemented similarly. They are:
#1 Jump if equal (Sometimes used with more than two operands, in which case the branch is taken if the first operand is equal to any of the others)
#2 Jump if less than
#3 Jump if greater than
#20 Add
#21 Subtract
#22 Multiply
#23 Divide
#24 Modulus
#128 Jump if zero
Next time I'll look at some other seemingly simple operations that can be a source of problems for first time interpreter writers.
Wednesday, October 14, 2009
In the beginning...
For anyone interested in the history of the Z-machine, it is very much the history of Zork itself. Zork was inspired by an earlier (non-Infocom) game sometimes called 'Colossal Cave' or 'Adventure', which also has an interesting history and was inspired by a real cave in Kentucky. I've been to the end of the real road where the game Adventure begins. It may sound a bit silly but it was fun just being there.
My fascination with Zork began on a dark and stormy night in 1984. I was visiting a cousin of mine who had just gotten one of the first Macintosh computers and we sat down to play the first game he had gotten for it: Zork I. I was thrilled by the game and quickly become a fan of all things Infocom. Even though this was my introduction to Infocom it was not my first foray into text adventures.
I got my first computer in September of 1983. It was a Commodore Vic-20 and my first game for it was a cartridge of Scott Adams' adventure game 'Pirate's Cove'. I got several more of his cartridges over the next year, including Voodoo Castle, The Count, and Adventureland. The next year I upgraded to a C-64, bought a 1541 floppy disk drive and started getting Infocom games like Zork, Deadline, and The Lurking Horror (my all-time favorite). I also got a very interesting program called 'Adventure Writer' (also known as 'Quill') which allowed you to make your own games and came with two game compilations: The 'Junkyard' series and the 'Thriller' series. These were the first computer games I owned, but even they weren't my first contact with text adventures.
In 1981 I was in fifth grade. Once, I stayed overnight at a classmate's house. He and his brother had a TRS-80 and we made a trip to Radio Shack to pick up a game to play. We picked out Raaka-Tu and played it much of the night. The game was very unforgiving by today's standards, tending to kill you off rather randomly, but nevertheless I was enthralled. This was what first sparked my interest in computers and text adventures especially.
My fascination with Zork began on a dark and stormy night in 1984. I was visiting a cousin of mine who had just gotten one of the first Macintosh computers and we sat down to play the first game he had gotten for it: Zork I. I was thrilled by the game and quickly become a fan of all things Infocom. Even though this was my introduction to Infocom it was not my first foray into text adventures.
I got my first computer in September of 1983. It was a Commodore Vic-20 and my first game for it was a cartridge of Scott Adams' adventure game 'Pirate's Cove'. I got several more of his cartridges over the next year, including Voodoo Castle, The Count, and Adventureland. The next year I upgraded to a C-64, bought a 1541 floppy disk drive and started getting Infocom games like Zork, Deadline, and The Lurking Horror (my all-time favorite). I also got a very interesting program called 'Adventure Writer' (also known as 'Quill') which allowed you to make your own games and came with two game compilations: The 'Junkyard' series and the 'Thriller' series. These were the first computer games I owned, but even they weren't my first contact with text adventures.
In 1981 I was in fifth grade. Once, I stayed overnight at a classmate's house. He and his brother had a TRS-80 and we made a trip to Radio Shack to pick up a game to play. We picked out Raaka-Tu and played it much of the night. The game was very unforgiving by today's standards, tending to kill you off rather randomly, but nevertheless I was enthralled. This was what first sparked my interest in computers and text adventures especially.
Monday, October 5, 2009
Static and Virtual?
A few times while reading developer forums I've come across people asking if it possible to have a class member which is both static and virtual. The obvious answer is 'no'. Imagine a hypothetical static and virtual method named Foo. Because static members belong to no particular instance, when we say BaseClass.Foo() there is no way to determine whether we really meant to invoke DerivedClass.Foo(). Therefore it makes no sense to be both static and virtual.
All very interesting, but how does it apply to the Z-machine? I wanted to be able to invoke a particular operation by using a simple array of delegates and accessing them by index (the opcode number). While the eight different versions of the Z-machine define different operations, all instances of a particular version have identical sets. Because of this and the fact that I implement each version as a class, the array of operations for a given version would logically be a static member of that version's class. This led to the situation of eight different static arrays, each one defined in a different class. This was wasteful because they have more operations in common than they have differences. Additionally it was ugly because it forced me to wrap the call to the delegate in a virtual method to ensure the proper array was accessed. Yuck.
After thinking about the situation a little I thought it would be nice to have a static array of delegates to virtual methods, then I could just use a single array in my base class. After unsuccessfully trying to do just that, I ended up creating a single static array in my base class populated with delegates which take a ZMachine parameter and that call a virtual method on the instance passed to it to ensure the proper operation is invoked. This was ugly too because it involved a wrapper method to call the virtual method for each operation. I was able to use lambda syntax to clean it up quite a bit.
The result in my abstract ZMachine class looks like this:
protected delegate void Operation(ZMachine machine);
private static readonly ImmutableArray<Operation> operations = InitializeOperations();
private static ImmutableArray<Operation> InitializeOperations()
{
var op = new ImmutableArray<Operation>.Builder(256);
op[0] = op[32] = op[64] = op[96] = op[192] = z => z.Op0();
op[1] = op[33] = op[65] = op[97] = op[193] = z => z.Op1();
...
op[254] = z => z.Op254();
op[255] = z => z.Op255();
return op.MakeImmutable();
}
The methods Op1, Op2, etc. are virtual methods in the abstract base class with the default behavior of calling an abstract method called InvalidOperation, allowing derived classes to implement their own handling for any illegal operations as well as override only those operations which they care about.
Overall I'm pleased with the result. I ended up with a single array of delegates to invoke, and virtual operations to override, with the only wart being the extra method call using the lambdas.
All very interesting, but how does it apply to the Z-machine? I wanted to be able to invoke a particular operation by using a simple array of delegates and accessing them by index (the opcode number). While the eight different versions of the Z-machine define different operations, all instances of a particular version have identical sets. Because of this and the fact that I implement each version as a class, the array of operations for a given version would logically be a static member of that version's class. This led to the situation of eight different static arrays, each one defined in a different class. This was wasteful because they have more operations in common than they have differences. Additionally it was ugly because it forced me to wrap the call to the delegate in a virtual method to ensure the proper array was accessed. Yuck.
After thinking about the situation a little I thought it would be nice to have a static array of delegates to virtual methods, then I could just use a single array in my base class. After unsuccessfully trying to do just that, I ended up creating a single static array in my base class populated with delegates which take a ZMachine parameter and that call a virtual method on the instance passed to it to ensure the proper operation is invoked. This was ugly too because it involved a wrapper method to call the virtual method for each operation. I was able to use lambda syntax to clean it up quite a bit.
The result in my abstract ZMachine class looks like this:
protected delegate void Operation(ZMachine machine);
private static readonly ImmutableArray<Operation> operations = InitializeOperations();
private static ImmutableArray<Operation> InitializeOperations()
{
var op = new ImmutableArray<Operation>.Builder(256);
op[0] = op[32] = op[64] = op[96] = op[192] = z => z.Op0();
op[1] = op[33] = op[65] = op[97] = op[193] = z => z.Op1();
...
op[254] = z => z.Op254();
op[255] = z => z.Op255();
return op.MakeImmutable();
}
The methods Op1, Op2, etc. are virtual methods in the abstract base class with the default behavior of calling an abstract method called InvalidOperation, allowing derived classes to implement their own handling for any illegal operations as well as override only those operations which they care about.
Overall I'm pleased with the result. I ended up with a single array of delegates to invoke, and virtual operations to override, with the only wart being the extra method call using the lambdas.
Sunday, September 27, 2009
Limitations of the Z-machine standard
"It is wrong in all cases to believe on insufficient evidence; and where it is presumption to doubt and to investigate, there it is worse than presumption to believe." - The Ethics of Belief, William Kingdon Clifford
When writing an interpreter, despite the very useful Z-machine standard, there are small areas of behavior which are undefined. There are also a very small number of errors in the standard itself. I have to say that overall the 1.0 version standard is very thorough, although I believe the 1.1 standard was not as well conceived in a number of areas. I won't go into the 1.1 standard just yet. Today I am talking about a design decision regarding instruction decoding.
In my last post I described how to decode an instruction and execute it. I deliberately left out one part of the instruction format mentioned in the standard because I don't deal with it at that point, but rather during the execution itself. There are three special types of instructions: branch, store, and text. Branch instructions are followed by one or two bytes which contain information as to whether the branch occurs on true or false and an offset address. Store instructions are followed by a byte containing a variable number in which to store the result of the operation. Text instructions are followed by a string of text to print.
I do not read these extra pieces of the instruction and store them during decoding although many, but not all, interpreters do. Rather I delay the reading of this information until the operation concludes. For example: We read a new instruction from the PC and the byte is 0x14 (20 decimal) which is the 'add' opcode. It is a 2-op instruction with two small constant operands. The next two bytes contain these constants. This is a store instruction therefore it is followed by a byte which contains the variable number to put the result in. We do not read this during decoding, instead we wait until the end of the operation itself. Here is the add operation (which uses signed addition):
protected override void Op20()
{
var num1 = (short)this.Operands[0];
var num2 = (short)this.Operands[1];
this.Store((ushort)(num1 + num2));
}
and the store method:
protected void Store(ushort value)
{
byte variable = this.Memory.ReadByte(this.CallStack.ProgramCounter++);
this.WriteVariable(variable, value);
}
Why is this important? Can't we just read the storage byte ahead of time during decoding and cache it somewhere? After all it is part of the instruction and the standard doesn't say how the instruction should be read. Well, yes, but there really are no compelling reasons to do so, yet there are some not to:
First, caching the result causes complications for the save/restore opcodes. Versions 1-3 of the Z-machine used branch opcodes for save and restore (later versions use store instead). If we read ahead, then when we encounter a save opcode, the PC that is saved will point just past the branching information. When a restore is performed, execution picks up at this point, but cannot know what to do as the save format includes memory and the stack, but no information about the current operation, thus the branch information is lost. Because the branch information can be one or two bytes, backward parsing from the current location is ugly. To fix it, we need to save the PC from the location before we read the branch or store information in order to be able to continue after the restore. When we read these values at the end of the operation, we don't need to do these PC gymnastics and everything 'just works'.
Second and more interestingly, if only from a theoretical point of view, is if the instruction is a 'call' instruction which starts a routine and stores the return value, then reading ahead presupposes the routine will not change the value of the storage byte during execution. We can imagine this routine sits in dynamic memory where it can rewrite itself while running. Read ahead caching of the storage location would break this code! Through testing I found that Infocom's own interpreters do not read the storage location until after a routine returns. Thus the original implementations of the Z-machine have always had this capability and a modern interpreter which does not is unnecessarily limiting possible behavior of the Z-machine. I avoid creating limitations wherever possible.
Wednesday, September 23, 2009
Decoding operations
We know that Z-machine decodes and executes one operation at a time. Let's look at exactly how it does this.
Remember the call stack? One piece of information stored in the call stack is the current program counter (PC). This points to an address in the Z-machine's memory (often beyond the 64k mark, so a 32-bit integer value is recommended). We begin by reading the byte in memory pointed to by the PC. We increment the counter every time we use it. The byte we just read contains the opcode number. After we have the opcode number we need to load the operands to be used during this operation. First we need to determine how many and what type they are.
The Z-machine has three types of operands: small constants (1 byte value), large constants (2 byte value) , and variables (1 byte variable number). It is useful to define them in an enum like this:
public enum OperandType
{
LargeConstant = 0,
Omitted = 3,
SmallConstant = 1,
Variable = 2
}
The enum values correspond to a pair of bits, where a large constant is binary 00, a small constant is 01, a variable is 10, and an omitted operand is 11.
Where do we read these values from? That depends on the opcode number.
If the opcode number is less than 128, the operation uses 'long form'. The operation always has two operands with either small constant or variable operands. Their types are determined by the seventh and sixth bits of the opcode number. Add 1 to the bit value to determine the operand type. Example: The opcode number is 78 which in binary is 01001110. The seventh bit is 1 and the sixth bit is 0. This gives the first operand as 2 (variable) and the second as 1 (small constant).
If the opcode is > 127 and less than 192 then it uses 'short form'. There may be zero or one operands. The type is given by the sixth and fifth bits taken together. It may be any of the three types or omitted.
If the opcode is > 191 (but not 236 or 250, which are special) then it uses 'variable form'. The operand types are specified by an additional byte. We read the byte of memory pointed to by the PC. Each pair of bits in this byte corresponds to one operand, which can be any of the types, including omitted. This gives us 0-4 operands.
If the opcode is 236 or 250 it uses 'double variable form'. The operands are determined by two additional bytes read in the same way as variable form. This gives us 0-7 operands.
Once we have the number and types of operands we can then get their values. Small constants are loaded by reading the next byte pointed to by the PC. Large constants by the next word (two bytes) pointed to by the PC. Variable operands are more complicated. First the variable number is determined by reading the next byte pointed to by the PC. What happens next depends on the variable number: If it is zero, we pop a value off the temporary stack in the call stack. If it is between one and fifteen we read the value of a routine local variable (also stored in the call stack), otherwise we read from a so-called "global" variable, which is really just an offset from a known location in the Z-machine memory. In any of those three cases, the resulting 16-bit value becomes the value of the variable operand.
Now we can execute our operation with the given operands. The following routine decodes and executes a single operation.
private void ExecuteInstruction()
{
this.Operands.Reset();
byte operationCode = this.Memory.ReadByte(this.CallStack.ProgramCounter++);
if (operationCode < 128)
{
this.PopulateOperand((OperandType)((operationCode >> 6 & 1) + 1));
this.PopulateOperand((OperandType)((operationCode >> 5 & 1) + 1));
}
else
{
if (operationCode < 192)
{
this.PopulateOperand((OperandType)(operationCode >> 4 & 3));
}
else
{
byte operandByte1 = this.Memory.ReadByte(this.CallStack.ProgramCounter++);
byte operandByte2 = 255;
if (operationCode == 236 || operationCode == 250)
{
operandByte2 = this.Memory.ReadByte(this.CallStack.ProgramCounter++);
}
this.PopulateOperand((OperandType)(operandByte1 >> 6 & 3));
this.PopulateOperand((OperandType)(operandByte1 >> 4 & 3));
this.PopulateOperand((OperandType)(operandByte1 >> 2 & 3));
this.PopulateOperand((OperandType)(operandByte1 & 3));
this.PopulateOperand((OperandType)(operandByte2 >> 6 & 3));
this.PopulateOperand((OperandType)(operandByte2 >> 4 & 3));
this.PopulateOperand((OperandType)(operandByte2 >> 2 & 3));
this.PopulateOperand((OperandType)(operandByte2 & 3));
}
}
Operations[operationCode](this);
}
We can take advantage of the fact that a byte value of of 255 corresponds to all operands being omitted to combine the variable and double variable case. The final line of the routine executes the operation by invoking a delegate stored in an immutable array called Operations and indexed by the opcode number.
Here's the code for populating the operands:
protected void PopulateOperand(OperandType type)
{
switch (type)
{
case OperandType.SmallConstant:
this.Operands.LoadOperand(this.Memory.ReadByte(this.CallStack.ProgramCounter++));
break;
case OperandType.Variable:
this.Operands.LoadOperand(this.ReadVariable(this.Memory.ReadByte(this.CallStack.ProgramCounter++)));
break;
case OperandType.LargeConstant:
this.Operands.LoadOperand(this.Memory.ReadWord(this.CallStack.ProgramCounter));
this.CallStack.ProgramCounter += 2;
break;
}
}
and finally, here is the code for reading a variable:
protected ushort ReadVariable(ushort variableNumber)
{
if (variableNumber > 15)
{
return this.ReadGlobalVariable((ushort)(variableNumber - 16));
}
return variableNumber > 0 ? this.CallStack.LocalVariableRead((byte)(variableNumber - 1)) : this.CallStack.Pop();
}
CallStack.Pop() pops a value off of the temporary stack within the current frame. It does not remove the entire frame. I use methods called BeginRoutine and EndRoutine for that.
That's it for today.
Remember the call stack? One piece of information stored in the call stack is the current program counter (PC). This points to an address in the Z-machine's memory (often beyond the 64k mark, so a 32-bit integer value is recommended). We begin by reading the byte in memory pointed to by the PC. We increment the counter every time we use it. The byte we just read contains the opcode number. After we have the opcode number we need to load the operands to be used during this operation. First we need to determine how many and what type they are.
The Z-machine has three types of operands: small constants (1 byte value), large constants (2 byte value) , and variables (1 byte variable number). It is useful to define them in an enum like this:
public enum OperandType
{
LargeConstant = 0,
Omitted = 3,
SmallConstant = 1,
Variable = 2
}
The enum values correspond to a pair of bits, where a large constant is binary 00, a small constant is 01, a variable is 10, and an omitted operand is 11.
Where do we read these values from? That depends on the opcode number.
If the opcode number is less than 128, the operation uses 'long form'. The operation always has two operands with either small constant or variable operands. Their types are determined by the seventh and sixth bits of the opcode number. Add 1 to the bit value to determine the operand type. Example: The opcode number is 78 which in binary is 01001110. The seventh bit is 1 and the sixth bit is 0. This gives the first operand as 2 (variable) and the second as 1 (small constant).
If the opcode is > 127 and less than 192 then it uses 'short form'. There may be zero or one operands. The type is given by the sixth and fifth bits taken together. It may be any of the three types or omitted.
If the opcode is > 191 (but not 236 or 250, which are special) then it uses 'variable form'. The operand types are specified by an additional byte. We read the byte of memory pointed to by the PC. Each pair of bits in this byte corresponds to one operand, which can be any of the types, including omitted. This gives us 0-4 operands.
If the opcode is 236 or 250 it uses 'double variable form'. The operands are determined by two additional bytes read in the same way as variable form. This gives us 0-7 operands.
Once we have the number and types of operands we can then get their values. Small constants are loaded by reading the next byte pointed to by the PC. Large constants by the next word (two bytes) pointed to by the PC. Variable operands are more complicated. First the variable number is determined by reading the next byte pointed to by the PC. What happens next depends on the variable number: If it is zero, we pop a value off the temporary stack in the call stack. If it is between one and fifteen we read the value of a routine local variable (also stored in the call stack), otherwise we read from a so-called "global" variable, which is really just an offset from a known location in the Z-machine memory. In any of those three cases, the resulting 16-bit value becomes the value of the variable operand.
Now we can execute our operation with the given operands. The following routine decodes and executes a single operation.
private void ExecuteInstruction()
{
this.Operands.Reset();
byte operationCode = this.Memory.ReadByte(this.CallStack.ProgramCounter++);
if (operationCode < 128)
{
this.PopulateOperand((OperandType)((operationCode >> 6 & 1) + 1));
this.PopulateOperand((OperandType)((operationCode >> 5 & 1) + 1));
}
else
{
if (operationCode < 192)
{
this.PopulateOperand((OperandType)(operationCode >> 4 & 3));
}
else
{
byte operandByte1 = this.Memory.ReadByte(this.CallStack.ProgramCounter++);
byte operandByte2 = 255;
if (operationCode == 236 || operationCode == 250)
{
operandByte2 = this.Memory.ReadByte(this.CallStack.ProgramCounter++);
}
this.PopulateOperand((OperandType)(operandByte1 >> 6 & 3));
this.PopulateOperand((OperandType)(operandByte1 >> 4 & 3));
this.PopulateOperand((OperandType)(operandByte1 >> 2 & 3));
this.PopulateOperand((OperandType)(operandByte1 & 3));
this.PopulateOperand((OperandType)(operandByte2 >> 6 & 3));
this.PopulateOperand((OperandType)(operandByte2 >> 4 & 3));
this.PopulateOperand((OperandType)(operandByte2 >> 2 & 3));
this.PopulateOperand((OperandType)(operandByte2 & 3));
}
}
Operations[operationCode](this);
}
We can take advantage of the fact that a byte value of of 255 corresponds to all operands being omitted to combine the variable and double variable case. The final line of the routine executes the operation by invoking a delegate stored in an immutable array called Operations and indexed by the opcode number.
Here's the code for populating the operands:
protected void PopulateOperand(OperandType type)
{
switch (type)
{
case OperandType.SmallConstant:
this.Operands.LoadOperand(this.Memory.ReadByte(this.CallStack.ProgramCounter++));
break;
case OperandType.Variable:
this.Operands.LoadOperand(this.ReadVariable(this.Memory.ReadByte(this.CallStack.ProgramCounter++)));
break;
case OperandType.LargeConstant:
this.Operands.LoadOperand(this.Memory.ReadWord(this.CallStack.ProgramCounter));
this.CallStack.ProgramCounter += 2;
break;
}
}
and finally, here is the code for reading a variable:
protected ushort ReadVariable(ushort variableNumber)
{
if (variableNumber > 15)
{
return this.ReadGlobalVariable((ushort)(variableNumber - 16));
}
return variableNumber > 0 ? this.CallStack.LocalVariableRead((byte)(variableNumber - 1)) : this.CallStack.Pop();
}
CallStack.Pop() pops a value off of the temporary stack within the current frame. It does not remove the entire frame. I use methods called BeginRoutine and EndRoutine for that.
That's it for today.
Tuesday, September 22, 2009
Interpreter basics
There have been Z-machine interpreters created for most platforms and in most languages. Mine is not the first written in C# but my goals are perhaps a bit different. As I mentioned, my goal is not to create a monolithic interpreter, but rather a class library usable by a host of interpreter front-ends. I currently test my library against several front-ends including: applications using windows console, windows forms, WPF, ASP.Net, and XNA for the Xbox360.
Infocom released almost three dozen Z-machine games which spanned six distinct versions of the Z-machine platform. Hundreds more have been written by other authors since then (many can be found at the IF Archive) and two minor version changes to the Z-machine have been added bringing the total to eight. I wish to support these new games and Infocom's full catalog as well, which includes the version 6 games that had graphics capabilities for the first time. Version 6 is really a different beast from the others (versions 7 and 8 are successors to 5 rather than 6) and requires a lot of extra effort to support.
So what does a Z-machine do? After initializing, it executes code until hitting a read opcode (or additionally read_char in version 4 and up) then waits for input. After receiving input, execution continues with the next instruction. Most of the time is spent waiting for input from the user. Using these simple states we can 'run' one cycle of our machine like this:
public void Run()
{
lock (this.lockObject)
{
switch (this.State)
{
case MachineState.Initializing:
this.Initialize();
break;
case MachineState.Running:
this.ExecuteInstruction();
break;
case MachineState.ReadingInput:
this.ReadInput();
break;
}
}
}
Initialize() seeds the random number generator, places the first routine on the stack, and then sets the state to Running. ExecuteInstruction() decodes and executes a single operation. If that operation is 'read' or 'read_char' it then switches the state to ReadingInput. ReadInput() checks the input buffer. If input has been terminated by a carriage return or a 'terminating character' specified by a table in memory it then switches the state back to Running.
We synchronize on a private object and only run one machine cycle at a time to allow the front-end to determine the nature of the loop between cycles as well as details like how many threads may service the machine.
Next time I'll go into detail about how to decode an operation and execute it.
Infocom released almost three dozen Z-machine games which spanned six distinct versions of the Z-machine platform. Hundreds more have been written by other authors since then (many can be found at the IF Archive) and two minor version changes to the Z-machine have been added bringing the total to eight. I wish to support these new games and Infocom's full catalog as well, which includes the version 6 games that had graphics capabilities for the first time. Version 6 is really a different beast from the others (versions 7 and 8 are successors to 5 rather than 6) and requires a lot of extra effort to support.
So what does a Z-machine do? After initializing, it executes code until hitting a read opcode (or additionally read_char in version 4 and up) then waits for input. After receiving input, execution continues with the next instruction. Most of the time is spent waiting for input from the user. Using these simple states we can 'run' one cycle of our machine like this:
public void Run()
{
lock (this.lockObject)
{
switch (this.State)
{
case MachineState.Initializing:
this.Initialize();
break;
case MachineState.Running:
this.ExecuteInstruction();
break;
case MachineState.ReadingInput:
this.ReadInput();
break;
}
}
}
Initialize() seeds the random number generator, places the first routine on the stack, and then sets the state to Running. ExecuteInstruction() decodes and executes a single operation. If that operation is 'read' or 'read_char' it then switches the state to ReadingInput. ReadInput() checks the input buffer. If input has been terminated by a carriage return or a 'terminating character' specified by a table in memory it then switches the state back to Running.
We synchronize on a private object and only run one machine cycle at a time to allow the front-end to determine the nature of the loop between cycles as well as details like how many threads may service the machine.
Next time I'll go into detail about how to decode an operation and execute it.
Thursday, September 17, 2009
The Troll Room - Randomness in the Z-machine
This is a small room with passages to the east and south and a forbidding hole leading west. Bloodstains and deep scratches (perhaps made by an axe) mar the walls.
A nasty-looking troll, brandishing a bloody axe, blocks all passages out of the room.
Your sword has begun to glow very brightly.
The troll swings his axe, and it nicks your arm as you dodge.
>attack troll with sword
A good slash, but it misses the troll by a mile.The axe crashes against the rock, throwing sparks!
>attack troll with sword
The troll is disarmed by a subtle feint past his guard.The troll, angered and humiliated, recovers his weapon. He appears to have an axe to grind with you.
>attack troll with sword
A quick stroke, but the troll is on guard.The flat of the troll's axe hits you delicately on the head, knocking you out.Conquering his fears, the troll puts you to death.It appears that that last blow was too much for you. I'm afraid you are dead.
**** You have died **** .
A familiar scene to anyone who has played Zork, the troll room is likely a player's first encounter with random (or pseudo-random if we are being pedantic) behavior in the Z-machine. In fact it is possible to die immediately upon entering the room! While this may not be the best possible use of randomness in a game, it serves as a good example of the Z-machine's ability to generate random outcomes. I've chosen the random number generator as the first Z-machine component to look at in detail because it is relatively simple, self-contained and remains constant throughout the different versions of Z-machine design.
The random number generator is invoked through a single opcode which takes a single operand and stores a result, both of which are 16-bit values. The Z-machine specification outlines the expected behavior in two places: Section 2.4 and the details of the random opcode. What we need to do is look at the operand as a signed value, let's call it 'x', and do one of three things: If x is negative, we seed the generator with -x and return zero. If x is zero we seed the generator as randomly as possible and return zero. Finally, if x is positive we generate a random number 'r' such that 1<=r<=x and return it. Additionally, the author of the specification, Graham Nelson, recommends an algorithm where seed values 1 to 999 change the behavior of the generator from producing random numbers to sequential ones mainly to assist game authors with testing. For example: "random -10" would place the generator in 'counting' mode and subsequent calls to random with positive ranges will produce 1,2,3...,9,10,1,2,3... and so on until the generator is seeded with another value. We now have all the behavior we need to implement an abstract base class. An abstract class allows the actual random number generation algorithm to be replaced if need arises without rewriting our class or risk of losing our recommended behavior. Here's our class:
/// <summary>
/// The Z-machine random number generator.
/// </summary>
public abstract class RandomNumberGenerator
{
private short count;
private bool countingMode;
private int seed;
public event EventHandler<GetRandomSeedEventArgs> GetRandomSeed;
protected int Seed
{
get
{
return this.seed;
}
private set
{
this.seed = value;
if (value > 0 && value < 1000)
{
this.countingMode = true;
this.count = 0;
return;
}
if (value == 0)
{
var args = new GetRandomSeedEventArgs();
this.GetRandomSeed(this, args);
this.seed = args.Seed;
}
this.countingMode = false;
this.SeedGenerator();
}
}
/// <summary>
/// Generates a random number within a given range.
/// </summary>
/// <param name="range">
/// The range of possible results.
/// </param>
/// <returns>
/// A random number within the given range.
/// </returns>
public short Generate(short range)
{
if (range < 1)
{
this.Seed = -range;
return 0;
}
if (this.countingMode)
{
int temp = this.count % this.Seed;
this.count = (short)(temp + 1);
return (short)((temp % range) + 1);
}
return (short)(((this.GetNext() & 0x7fff) % range) + 1);
}
/// <summary>
/// Initializes the generator.
/// </summary>
public void Initialize()
{
this.Seed = 0;
}
/// <summary>
/// Gets the next random number.
/// </summary>
/// <returns>
/// The random number.
/// </returns>
protected abstract short GetNext();
/// <summary>
/// Seeds the generator.
/// </summary>
protected abstract void SeedGenerator();
}
Some explanation:
GetRandomSeedEventArgs is a simple class derived from EventArgs which contains a single read-write property of type int called Seed. This allows the generator to raise an event when it needs a randomly valued seed. This occurs whenever Random is called with a zero operand, or the generator is initialized, which happens at machine startup and during a restart.
The reason we do this: this.GetNext() & 0x7fff is to ensure the result is within the expected range because the return value is signed and could possibly be negative if a derived class implements GetNext() badly. This looks a little ugly, but if we use an unsigned return type we lose CLS compliance.
Now that we have a base class, we can implement a real generator. This one is my C# implementation of the Mersenne Twister - mt19937ar:
/// <summary>
/// The Z-machine random number generator using Mersenne Twister algorithm.
/// </summary>
internal sealed class MersenneTwister : RandomNumberGenerator
{
private const uint TemperingMaskB = 0x9d2c5680;
private const uint TemperingMaskC = 0xefc60000;
private const uint InitializationMultipler = 0x6c078965;
private const uint LowerMask = 0x7fffffff;
private const uint M = 397;
private const uint MatrixA = 0x9908b0df;
private const uint N = 624;
private const uint UpperMask = 0x80000000;
private static readonly ImmutableArray<uint> mag01 = InitializeMag01();
private readonly uint[] stateVector = new uint[N];
private uint stateVectorIndex;
/// <summary>
/// Gets the next random number.
/// </summary>
/// <returns>
/// The random number.
/// </returns>
protected override short GetNext()
{
uint result;
if (this.stateVectorIndex >= N)
{
int kk;
for (kk = 0; kk < N - M; kk++)
{
result = (this.stateVector[kk] & UpperMask) (this.stateVector[kk + 1] & LowerMask);
this.stateVector[kk] = this.stateVector[kk + M] ^ (result >> 1) ^ mag01[(int)(result & 1)];
}
for (; kk < N - 1; kk++)
{
result = (this.stateVector[kk] & UpperMask) (this.stateVector[kk + 1] & LowerMask);
this.stateVector[kk] = this.stateVector[kk + M - N] ^ (result >> 1) ^ mag01[(int)(result & 1)];
}
result = (this.stateVector[N - 1] & UpperMask) (this.stateVector[0] & LowerMask);
this.stateVector[N - 1] = this.stateVector[M - 1] ^ (result >> 1) ^ mag01[(int)(result & 1)];
this.stateVectorIndex = 0;
}
result = this.stateVector[this.stateVectorIndex++];
result ^= result >> 11;
result ^= (result << 7) & TemperingMaskB;
result ^= (result << 15) & TemperingMaskC;
result ^= result >> 18;
return (short)result;
}
/// <summary>
/// Seeds the generator.
/// </summary>
protected override void SeedGenerator()
{
this.stateVector[0] = (uint)this.Seed;
for (this.stateVectorIndex = 1; this.stateVectorIndex < N; this.stateVectorIndex++)
{
var previousValue = this.stateVector[this.stateVectorIndex - 1];
this.stateVector[this.stateVectorIndex] = (InitializationMultipler * (previousValue ^ (previousValue >> 30))) + this.stateVectorIndex;
}
}
/// <summary>
/// Initializes the mag01.
/// </summary>
/// <returns>
/// The mag01.
/// </returns>
private static ImmutableArray<uint> InitializeMag01()
{
var mag01Builder = new ImmutableArray<uint>.Builder(2);
mag01Builder[0] = 0;
mag01Builder[1] = MatrixA;
return mag01Builder.MakeImmutable();
}
}
Some explanation:
For those familiar with this algorithm, you may notice I left out a small section in the GetNext method which initializes the generator with a fixed seed value if you forget to seed the generator before calling it. I think this is a bad idea as it hides the error. Failing to seed the generator produces a string of identical results which is much easier to identify and fix.
You might also have noticed this code contains an immutable array class. The immutable array is something I found a need for in other parts of the Z-machine and have gotten into the habit of using it everywhwere. We'll see it again...
There we go! A complete implementation of the Z-machine random number capabilities.
A nasty-looking troll, brandishing a bloody axe, blocks all passages out of the room.
Your sword has begun to glow very brightly.
The troll swings his axe, and it nicks your arm as you dodge.
>attack troll with sword
A good slash, but it misses the troll by a mile.The axe crashes against the rock, throwing sparks!
>attack troll with sword
The troll is disarmed by a subtle feint past his guard.The troll, angered and humiliated, recovers his weapon. He appears to have an axe to grind with you.
>attack troll with sword
A quick stroke, but the troll is on guard.The flat of the troll's axe hits you delicately on the head, knocking you out.Conquering his fears, the troll puts you to death.It appears that that last blow was too much for you. I'm afraid you are dead.
**** You have died **** .
A familiar scene to anyone who has played Zork, the troll room is likely a player's first encounter with random (or pseudo-random if we are being pedantic) behavior in the Z-machine. In fact it is possible to die immediately upon entering the room! While this may not be the best possible use of randomness in a game, it serves as a good example of the Z-machine's ability to generate random outcomes. I've chosen the random number generator as the first Z-machine component to look at in detail because it is relatively simple, self-contained and remains constant throughout the different versions of Z-machine design.
The random number generator is invoked through a single opcode which takes a single operand and stores a result, both of which are 16-bit values. The Z-machine specification outlines the expected behavior in two places: Section 2.4 and the details of the random opcode. What we need to do is look at the operand as a signed value, let's call it 'x', and do one of three things: If x is negative, we seed the generator with -x and return zero. If x is zero we seed the generator as randomly as possible and return zero. Finally, if x is positive we generate a random number 'r' such that 1<=r<=x and return it. Additionally, the author of the specification, Graham Nelson, recommends an algorithm where seed values 1 to 999 change the behavior of the generator from producing random numbers to sequential ones mainly to assist game authors with testing. For example: "random -10" would place the generator in 'counting' mode and subsequent calls to random with positive ranges will produce 1,2,3...,9,10,1,2,3... and so on until the generator is seeded with another value. We now have all the behavior we need to implement an abstract base class. An abstract class allows the actual random number generation algorithm to be replaced if need arises without rewriting our class or risk of losing our recommended behavior. Here's our class:
/// <summary>
/// The Z-machine random number generator.
/// </summary>
public abstract class RandomNumberGenerator
{
private short count;
private bool countingMode;
private int seed;
public event EventHandler<GetRandomSeedEventArgs> GetRandomSeed;
protected int Seed
{
get
{
return this.seed;
}
private set
{
this.seed = value;
if (value > 0 && value < 1000)
{
this.countingMode = true;
this.count = 0;
return;
}
if (value == 0)
{
var args = new GetRandomSeedEventArgs();
this.GetRandomSeed(this, args);
this.seed = args.Seed;
}
this.countingMode = false;
this.SeedGenerator();
}
}
/// <summary>
/// Generates a random number within a given range.
/// </summary>
/// <param name="range">
/// The range of possible results.
/// </param>
/// <returns>
/// A random number within the given range.
/// </returns>
public short Generate(short range)
{
if (range < 1)
{
this.Seed = -range;
return 0;
}
if (this.countingMode)
{
int temp = this.count % this.Seed;
this.count = (short)(temp + 1);
return (short)((temp % range) + 1);
}
return (short)(((this.GetNext() & 0x7fff) % range) + 1);
}
/// <summary>
/// Initializes the generator.
/// </summary>
public void Initialize()
{
this.Seed = 0;
}
/// <summary>
/// Gets the next random number.
/// </summary>
/// <returns>
/// The random number.
/// </returns>
protected abstract short GetNext();
/// <summary>
/// Seeds the generator.
/// </summary>
protected abstract void SeedGenerator();
}
Some explanation:
GetRandomSeedEventArgs is a simple class derived from EventArgs which contains a single read-write property of type int called Seed. This allows the generator to raise an event when it needs a randomly valued seed. This occurs whenever Random is called with a zero operand, or the generator is initialized, which happens at machine startup and during a restart.
The reason we do this: this.GetNext() & 0x7fff is to ensure the result is within the expected range because the return value is signed and could possibly be negative if a derived class implements GetNext() badly. This looks a little ugly, but if we use an unsigned return type we lose CLS compliance.
Now that we have a base class, we can implement a real generator. This one is my C# implementation of the Mersenne Twister - mt19937ar:
/// <summary>
/// The Z-machine random number generator using Mersenne Twister algorithm.
/// </summary>
internal sealed class MersenneTwister : RandomNumberGenerator
{
private const uint TemperingMaskB = 0x9d2c5680;
private const uint TemperingMaskC = 0xefc60000;
private const uint InitializationMultipler = 0x6c078965;
private const uint LowerMask = 0x7fffffff;
private const uint M = 397;
private const uint MatrixA = 0x9908b0df;
private const uint N = 624;
private const uint UpperMask = 0x80000000;
private static readonly ImmutableArray<uint> mag01 = InitializeMag01();
private readonly uint[] stateVector = new uint[N];
private uint stateVectorIndex;
/// <summary>
/// Gets the next random number.
/// </summary>
/// <returns>
/// The random number.
/// </returns>
protected override short GetNext()
{
uint result;
if (this.stateVectorIndex >= N)
{
int kk;
for (kk = 0; kk < N - M; kk++)
{
result = (this.stateVector[kk] & UpperMask) (this.stateVector[kk + 1] & LowerMask);
this.stateVector[kk] = this.stateVector[kk + M] ^ (result >> 1) ^ mag01[(int)(result & 1)];
}
for (; kk < N - 1; kk++)
{
result = (this.stateVector[kk] & UpperMask) (this.stateVector[kk + 1] & LowerMask);
this.stateVector[kk] = this.stateVector[kk + M - N] ^ (result >> 1) ^ mag01[(int)(result & 1)];
}
result = (this.stateVector[N - 1] & UpperMask) (this.stateVector[0] & LowerMask);
this.stateVector[N - 1] = this.stateVector[M - 1] ^ (result >> 1) ^ mag01[(int)(result & 1)];
this.stateVectorIndex = 0;
}
result = this.stateVector[this.stateVectorIndex++];
result ^= result >> 11;
result ^= (result << 7) & TemperingMaskB;
result ^= (result << 15) & TemperingMaskC;
result ^= result >> 18;
return (short)result;
}
/// <summary>
/// Seeds the generator.
/// </summary>
protected override void SeedGenerator()
{
this.stateVector[0] = (uint)this.Seed;
for (this.stateVectorIndex = 1; this.stateVectorIndex < N; this.stateVectorIndex++)
{
var previousValue = this.stateVector[this.stateVectorIndex - 1];
this.stateVector[this.stateVectorIndex] = (InitializationMultipler * (previousValue ^ (previousValue >> 30))) + this.stateVectorIndex;
}
}
/// <summary>
/// Initializes the mag01.
/// </summary>
/// <returns>
/// The mag01.
/// </returns>
private static ImmutableArray<uint> InitializeMag01()
{
var mag01Builder = new ImmutableArray<uint>.Builder(2);
mag01Builder[0] = 0;
mag01Builder[1] = MatrixA;
return mag01Builder.MakeImmutable();
}
}
Some explanation:
For those familiar with this algorithm, you may notice I left out a small section in the GetNext method which initializes the generator with a fixed seed value if you forget to seed the generator before calling it. I think this is a bad idea as it hides the error. Failing to seed the generator produces a string of identical results which is much easier to identify and fix.
You might also have noticed this code contains an immutable array class. The immutable array is something I found a need for in other parts of the Z-machine and have gotten into the habit of using it everywhwere. We'll see it again...
There we go! A complete implementation of the Z-machine random number capabilities.
Monday, September 14, 2009
The Great Underground Empire
A look beneath the surface
The Z-machine is a 16-bit virtual machine using big endian addressing. A cpu, memory, and stack make up the bulk of the machine. The cpu has no registers, but instead relies on global variables in memory, routine specific local variables and temporary values on the stack to read and write data.
Memory is divided into dynamic, static, and high regions. Dynamic memory can be written to whereas static memory is read only. High memory is also read only, but can be swapped out of ram and loaded when needed. This allowed Infocom's games to be larger than the memory size of the computers they ran on (which in the mid-80's was typically around 64k or less). Modern interpreters needn't worry about the high memory distinction unless running on a memory constrained platform. By today's standards that would probably mean running on a wristwatch or toaster.
The stack is interesting and I think a source of confusion for people learning the Z-machine. Technically there are two stacks. The first maintains the state of each routine that has been called, such as local variables and the program counter. Calls to routines and returns from routines push/pop frames from this stack. The second stack holds temporary 16-bit values. Various opcodes can push/pop values from this stack. Because a routine is not allowed to pop values off the second stack that an earlier routine placed there, the second stack can be imagined as a bunch of independent stacks, each one belonging to a corresponding frame on the first stack. The basic structure of the stack can be implemented like this:
class CallStack
{
private Stack<Frame> frames;
...
}
class Frame
{
private Stack<ushort> localStack;
...
}
I'll go over these components in more detail in future posts. Beyond these basic components of the Z-machine, there are smaller but still important pieces, such as the random number generator which I will talk about next time.
The Z-machine is a 16-bit virtual machine using big endian addressing. A cpu, memory, and stack make up the bulk of the machine. The cpu has no registers, but instead relies on global variables in memory, routine specific local variables and temporary values on the stack to read and write data.
Memory is divided into dynamic, static, and high regions. Dynamic memory can be written to whereas static memory is read only. High memory is also read only, but can be swapped out of ram and loaded when needed. This allowed Infocom's games to be larger than the memory size of the computers they ran on (which in the mid-80's was typically around 64k or less). Modern interpreters needn't worry about the high memory distinction unless running on a memory constrained platform. By today's standards that would probably mean running on a wristwatch or toaster.
The stack is interesting and I think a source of confusion for people learning the Z-machine. Technically there are two stacks. The first maintains the state of each routine that has been called, such as local variables and the program counter. Calls to routines and returns from routines push/pop frames from this stack. The second stack holds temporary 16-bit values. Various opcodes can push/pop values from this stack. Because a routine is not allowed to pop values off the second stack that an earlier routine placed there, the second stack can be imagined as a bunch of independent stacks, each one belonging to a corresponding frame on the first stack. The basic structure of the stack can be implemented like this:
class CallStack
{
private Stack<Frame> frames;
...
}
class Frame
{
private Stack<ushort> localStack;
...
}
I'll go over these components in more detail in future posts. Beyond these basic components of the Z-machine, there are smaller but still important pieces, such as the random number generator which I will talk about next time.
Sunday, September 6, 2009
Rebuilding the Z-machine
Hi,
I've created this blog to share my experiences in building a Z-machine interpreter. My name is Mike Greger and I am a C# developer and a gamer. I got started with computers in the early 1980's when I became fascinated by the worlds found within so-called 'text adventures'. Some of my favorites were written by a company called Infocom.
What is a Z-machine?
Infocom created a clever way of making their games available for the many types of computers on the market at that time by designing a virtual machine now known as the Z-machine. Each game only needed to be written once, for the Z-machine. A Z-machine interpreter was then written for each platform to run the games.
Fast forward to 2009: Infocom is long gone. The Z-machine format has been reverse engineered by talented people and the specifications made available. Armed with this information developers have created Z-machine interpreters for platforms big and small.
If it's already been done, then why do it?
The short answer is because of the challenge and learning opportunities it presents. I also like to think I can improve on some things. Some time ago I set out to write my own interpreter and succeeded, sort of. My interpreter played all the infocom games just as I remembered them. However, when I first started my project I did not have a lot of programming experience. Looking back later at what I had written I found the code amateurish and not suitable for easy reuse. I decided to rebuild it and came up with a set of design criteria for a class library written in C# 3.0 which implements the Z-machine:
Why write a blog about it?
In the hope that someone will find something useful, maybe for their own interpreter or other project. While the published specifications contain a lot of useful information, Z-machine behavior can be complex and seeing a working example can be beneficial. Additionally I hope to make clear why I chose certain designs, rather than just publishing source code. Code comments tend to explain how something works, not why it was written that way in the first place.
Next time: Z-machine architecture.
I've created this blog to share my experiences in building a Z-machine interpreter. My name is Mike Greger and I am a C# developer and a gamer. I got started with computers in the early 1980's when I became fascinated by the worlds found within so-called 'text adventures'. Some of my favorites were written by a company called Infocom.
What is a Z-machine?
Infocom created a clever way of making their games available for the many types of computers on the market at that time by designing a virtual machine now known as the Z-machine. Each game only needed to be written once, for the Z-machine. A Z-machine interpreter was then written for each platform to run the games.
Fast forward to 2009: Infocom is long gone. The Z-machine format has been reverse engineered by talented people and the specifications made available. Armed with this information developers have created Z-machine interpreters for platforms big and small.
If it's already been done, then why do it?
The short answer is because of the challenge and learning opportunities it presents. I also like to think I can improve on some things. Some time ago I set out to write my own interpreter and succeeded, sort of. My interpreter played all the infocom games just as I remembered them. However, when I first started my project I did not have a lot of programming experience. Looking back later at what I had written I found the code amateurish and not suitable for easy reuse. I decided to rebuild it and came up with a set of design criteria for a class library written in C# 3.0 which implements the Z-machine:
- Complete. Supports all features and Z-machine versions
- Easy to use and extend
- Decoupled from any particular interface (console, windows forms, WPF, etc.)
- CLS compliant
- Well documented
- Thread-safe
- Memory efficient for multiple instances
- Not overly dependent on framework types
Why write a blog about it?
In the hope that someone will find something useful, maybe for their own interpreter or other project. While the published specifications contain a lot of useful information, Z-machine behavior can be complex and seeing a working example can be beneficial. Additionally I hope to make clear why I chose certain designs, rather than just publishing source code. Code comments tend to explain how something works, not why it was written that way in the first place.
Next time: Z-machine architecture.
Subscribe to:
Posts (Atom)