Module music was once a staple in video game development but has since been mostly replaced by streamed audio formats like MP3 and OGG.  The reason is straightforward – streamed audio is production environment agnostic whereas module music requires specific production tools and constraints.  However, one of the interesting things about creating games for limited profiles like iOS devices is that many game development practises in use ten to fifteen years ago become relevant again.  There are some big advantages to using mod music for an iOS game.

Milky Tracker is software used to make module music

In a module file each instrument is stored as a single sample while the music is stored as sequenced data. You can think of it as a piano roll, where each notch plays back one of the samples at a specified frequency. Mod’s have many advantages over MP3 audio for games on iOS:

• File size does not scale directly with the play time of the music.  Each instrument in the song is stored once as a sample and that data can be reused over and over as the note sequence is processed.
• Seamless looping and loop points.  Many songs benefit from a loop back to just after the intro or  infinitely looping an ominous ending phrase.
• More control over playback.  If the timer is low, you can increase the speed of playback without affecting pitch to create an organic frenzied feeling.  If Mario gets on a Yoshi you can dynamically mute/un-mute an extra drum channel.
• Fine grained optimisation.  With an MP3 you have to deal with the quality of the entire audio clip as a whole when adjusting for quality.  With a module file you can decrease or increase the fidelity of specific samples to get the best quality for your memory and size constraints.

Unfortunately, many existing and popular solutions for playback on iOS come with licensing fees, but there are alternatives that will do the job. Chibi XMPlay, a lightweight module playback library created by Juan Linietsky and myself, is one of them.

It’s used for playing a type of module file known as XM (eXtended Module) on limited platforms like the iOS or Nintendo DS. Best of all it’s completely open source, licensed under new BSD, and free to use for both commercial and non-commercial applications.

Using ChibiXM Play

Chibi XMPlay was written with portability in mind.  As a client it’s your responsibility to populate memory, file i/o, and mixer function tables for the OS you’re using.  Lucky for you, I’ve done this work already for Trudy’s Mechanicals.  I’ve also added functionality to the wrapper to play sound effects which is possibly useful as a low latency alternative to Apple’s numerous methods.  To use ChibiXM do the following:

1. Make sure you have the “AudioToolbox” framework imported
2. Download the ChibiXM source w/Objective C wrapper and include it
3. The following code will play an XM file (provided ‘song.xm’ is part of your project):

If you just want to see ChibiXM in action here’s a complete XCode project you can compile and deploy that shows some graphics and let’s you switch between some songs with a touch.  Note that the project was created in XCode version 3.13 of the SDK.  To compile under the latest just go to Project Info and change Base SDK to 4.x

Just a few games that used module based music solutions! Ah, memories.

Where To Go From Here?

The wrapper is a simple way to play module music and sound effects, but I encourage you to look further into ChibiXM’s capabilities.  It has functionality to share a pack of samples among many songs and other goodies that allow easy programmability and control over music playback and mixing.  It’s also pretty easy to extend if you wish to add DSP effects to playback.

Here are some links to help you explore this approach to putting music into your game:

Chibi XmPlay – Berlios project page for Chibi XmPlay
Milky Tracker – Multi-platform tracking software that can create XM modules
ModArchive – Massive repository of tracked music
IndieGameMusic.com – Website designed to connect game developers to game musicians

Follow me on twitter! @infey

** UPDATE **
Dave Rempel points out that you may run into an issue if you load many songs into memory at once using xm_song_alloc() as the ChibiXM built-in software mixer (which the iOS code uses) has a statically sized pool of memory for storing samples for all songs currently loaded. The easiest way to avoid running into the issue is to only load the songs into memory you absolutely need for playback. However, if you wish to change the size of this buffer based on the requirements of your app you can modify the size of this buffer in xmplay.c, line 113:

Part 1 | Part 2 | Part 3 | Part 4 | Part 5

Its been a while since I’ve written a post on the simple scripting language.  While steadily working on Trudy’s Mechanicals,  I’ve recorded and released an album with my band Bacchus and integrated the simple scripting language into our internal projects. So without further ado, I’ll be looking at the virtual machine (VM) that the script’s compiled output will run on.

The reason I’ve skipped ahead is that I can’t start outputting assembly until I’ve designed the virtual machine (VM) that it will run on.

In the past I’ve designed stack based VMs exclusively, so this time I decided to try a register based VM.  Register based VMs  are predominantly RISC based, with fixed size instructions and simple addressing modes.  Register based VMs have the advantage that each instruction can do more than a stack based one, but stack-based assembly has the advantage that it  takes up less space.  There are exceptions to both of these cases.

An example of the size/complexity trade-off can be seen in the following arithmetic example.

int x,y;
int z = x*y + 1

Stack-based assembly (JVM inspired) output would be roughly:

1. LOAD X (1 to 2 bytes) – push x on to the top of the stack
2. LOAD Y (1 to 2 bytes) – push y on to the top of the stack
3. MULTIPLY (1 byte) – remove the top two items from the stack, multiply them and push the result
4. INCREMENT (1 byte) – increment the value on the top of the stack
5. STORE Z (1 to 2 bytes) – pop the top value from the stack and place it into the local variable z

Register-based assembly (ARM inspired) output would be roughly:

1. MULTIPLY reg[tmp] = reg[x]*reg[y] (4 bytes)
2. ADD_IMMEDIATE reg[z] = reg[tmp] + 1 (4 bytes)

As you can see stack-based assembly would be 5 instructions, with a size between 5 and 8 bytes.  Register based assembly code would be 2 instructions, with a size of 8 bytes

The Virtual Machine

In physical computers each additional register has a significant manufacturing expense.   The only cost of adding more registers in a VM is decreasing the number of bits used for opcodes or decreasing the number of registers that can be specified in a single instruction.

Like LUA 5, I found that 6 bits (64 opcodes) is more than sufficient for the number of instruction types I wanted my VM to contain. The virtual machine I’ve designed has 256 registers, available to a function at a single time.  Each register can hold either a 32-bit integer or a floating point value.

Each 32 bit instruction falls into one of the following four categories:

In addition to the 256 general purpose registers, two special purpose “registers” are required for the VM to execute:

• PC – program counter.  A pointer to the next instruction in memory to execute
• BP – base pointer.  A pointer to the location in memory, where the 256 registers start at, for the currently executing function.

List of Instructions

Below is a table of op-codes that I’m currently supporting:

Arithmetic

• MOV_IMM -  dst register = 18 bit sign extended immediate
• MOV_CONST – dst register = constant_pool[18 bit immediate]
• ADD – dst register = src register 1  + src register 2
• ADD_IMM – dst register = src register 1 + 10 bit sign extended immediate
• SUB – dst register = src register 1 – src register 2
• MUL – dst register = src register 1 * src register 2
• DIV – dst register = src register 1 / src register 2
• FADD – dst register = src register 1  + src register 2  (treated as floats)
• FSUB – dst register = src register 1  – src register 2 (treated as floats)
• FMUL – dst register = src register 1  * src register 2 (treated as floats)
• FDIV – dst register = src register 1  / src register 2 (treated as floats)

Compares / Jumps

• CMPEQ – dst register = (src register 1 == src register 2) ? 1 : 0
• CMPNE – dst register = (src register 1 != src register 2) ? 1 : 0
• CMPLT – dst register = (src register 1 < src register 2) ? 1 : 0
• CMPLE – dst register = (src register 1 <= src register 2) ? 1 : 0
• FCMPLT – dst register = (src register 1 < src register 2) ? 1 : 0   (treated as floats)
• FCMPLE – dst register = (src register 1 <= src register 2) ? 1 : 0  (treated as floats)
• JNE – if (dst register != 0) {  pc += sign extended 18 bit immediate }
• JEQ – if (dst register == 0) {  pc += sign extended 18 bit immediate }
• J – pc += sign extended 26 bit immediate

Operational

• CALL – call the function [ 18 bit immediate] retrieving parameters starting at  register’s index
• YIELD – interrupt execution
• RETURN – return the value contained in the destination register of the callee, and resume the exection of the caller
• RETURN_I – return an 18 bit immediate, and resume the execution of the caller
  

nb.  this is in no way a final list

Calling Conventions

In stack based languages, the arguments to a  function  are taken from the top of the stack. However, in a register based machine, there is no notion of a “top element of the stack”.  When we CALL a function we need to specify where the arguments should be retrieved from.

The CALL opcode has a register and an 18 bit immediate value as its parameters.

The 18bit value specifies the index  into a table of functions (internal to the VM) to invoke.  The register parameter specifies where in the current register set that the arguments reside.

Would compile to:

The table of functions contains the following information:

• code pointer – code to execute for the function
• number of arguments – the number of arguments that the function requires
• register count – how many registers this function requires (I’ll use this later to check that we don’t exceed memory limits)

When the CALL is executed it shuffles the arguments 2 register indexes up and stores the current BP and PC below them for later use.

?*,?,1 , 2, 3 (inside caller)
?,?,BP,PC, 1* , 2, 3  (inside callee)

* represents where the current BP is pointing at

PC is now set to the code pointer found in the table of functions
BP is set to point to the first argument to the function.  This has the advantage that all arguments start at register indices 0 through N.  This also places the constraint that the caller must not have any useful data placed in registers higher than the ones being passed as arguments as they may be overwritten by the callee.

When a RETURN instruction is encountered within the callee, the old BP and PC are retrieved so that execution can continue from where it left off in the caller.   If a return value is specified, it is place into the position of the first argument inside the caller.

?,?,BP,PC, 1* , 2, 3  (inside callee)
?*,?,return value, ?,? (inside caller)

Implementation

The software implementation of a VM is usually a combination of  a loop and a switch or jump table:

Constant Pools

There are two types of constants contained within the VM:  32 bit constants and string constants.

• 32-bit constants are used when a number (int or float) cannot be represented with the number of bits provided by an immediate value.  To get over this limitation, MOV_CONST moves a 32-bit value from the constant pool into a specified register.
• Since strings are immutable in the language, the string pool is used to store the actual character representation of them.  When strings are placed into registers by the language,under the hood it is not a string pointer copied, but the index of the string within the string constant pool

Wrap Up

You can download the current version of the VM here.   Next time I’ll be bridging the gap between the last two posts and starting to output assembly code to run on this VM.

As always you can follow me on twitter at @igtristan

Part 1 | Part 2 | Part 3 | Part 4 | Part 5

In this post, I’ll be building a two pass Parser for a sub set of the final language.  This subset will be capable of basic variable initialization, and passing values to external and internal methods.  This Parser will be using the Lexer interface from the previous article in the series.

An Example Script

1
2
3
4
5
6
7
8
9
10
11
12
extern void doSomething: (string) str andInt: (int) i;



int doSomethingElse

{

   int x = 0;

   string str = "hi";

   [doSomething: str andInt: x];

   x = [doSomethingAgain: 99];

   return 1;

}



extern int doSomethingAgain: (int) x;

Untill this point, I haven’t posted any examples of what the actual syntax of the language will look like.  As you can see in the above example, it is similar to Objective-C but without objects (although I might add them later).  Similar to C like languages, the extern keyword declares that a user definable piece of code (a callback) will be invoked by the Virtual Machine that the language will be running on.  Also unlike C, but akin to modern languages like Java, there will be no pre-declaration of methods.

In order to allow a method to be called before it is declared, I need to create a multi-pass parser.  On the first pass I’ll read through all of the tokens in the file and create a dictionary of all the method signatures I’ve found and their parameter types.  On the second pass, whenever I encounter a method call, I can look at this dictionary to verify that the method signature exists and the correct types of parameters have been passed.

Passes:

1. Determine all internal and external method signatures.
2. Do everything else

Initially this parser will start out with only these two passes, but I may add additional ones in the future as needed.

Parsing the Language

Traditionally a parser is built from a series of productions written in a Context Free Grammar.   The left side of each production represents the name of the production being defined. The right side represents the Tokens and Productions that it will be composed of.

Here are the logical symbols I’ll be using to construct each Production:

• ‘*’ stands for 0 or more of the token to the left of it
• ‘+’ stands for 1 or more of the token to the left of it
• ‘(‘ and ‘)’ group tokens
• ‘|’ means or
• anything prefixed with ‘Lexer_’ is a token type from the previous post’s Lexer.  (eg.  an identifier, string value, integer value)
• anything in quotes (eg ‘int’) represents a user defined Token.

These are the productions needed to define the example script:

1. File = (ExternalMethod | InternalMethod) *
2. ExternalMethod = ‘extern’ MethodSignature ‘;’
3. InternalMethod = MethodSignature Block
4. MethodSignature =  ReturnType (Lexer_ID  | (Lexer_ID ‘:’ ‘(‘Type’)'  Lexer_ID ) +)
5. ReturnType = ‘int’ | ‘string’ | ‘void’
6. Type = ‘int’ | ‘string’
7. Block = ‘{‘  Statement * ‘}’
8. Statement = StringDeclareStatement | IntDeclareStatement | MethodCallStatement | AssignStatement | ReturnStatement
9. StringDeclareStatement = (‘string’ Lexer_ID ‘=’ Expression ‘;’)| (‘string’ Lexer_ID ‘;’)
10. IntDeclareStatement = (‘int’ Lexer_ID ‘=’ Expression ‘;’ ) | (‘int’ Lexer_ID ‘;’)
11. MethodCallStatement = MethodCallExpression ‘;’
12. AssignStatement = Lexer_ID ‘=’ Expression ‘;’
13. ReturnStatement = (‘return’ Expression ‘;’) | (‘return’ ‘;’)
14. Expression = Lexer_INT | Lexer_STRING | Lexer_ID | MethodCallExpression
15. MethodCallExpression = ‘[' ( Lexer_ID  | (Lexer_ID ':' Expression)+ )  ']‘

Parser building tools often create a tree of nodes representing all the productions found in an entire file, this is known as an Abstract Syntax Tree.  However I’m going to create a Recursive Descent Parser where each of these rules , or group of rules will result in a C function.

Traversing through the Tokens in a File

In order to build a Recursive Decent Parser, I first need to create an interface to iterate through the output of the Lexer;  this is the TokenList.  This TokenList maintains an internal linked list of all the Tokens read from a file using the Lexer.   In addition the TokenList also provides functions for validating input and providing meaningful error messages to the user.  The TokenList interface is listed below:

This function initializes the TokenList with all of the Tokens that can be read from the passed Lexer.  Returns 1 if successful.

This function returns the type of the next Token in the TokenList.  This corresponds to the m_type field in Token struct.

This function returns the next token in a list and if that token does not match the expected type it displays an error and stops compilation.

This function is similar to TokenList_expect but allows for a choice of symbol types to match against.

This function displays an error blaming the token passed to it.  The message is displayed to screen along with the line and column that the Token was found on.  Eventually I’ll put in a user defined function pointer to be called instead, so that the choice of error handling behavior is up to the user.

Example: Using the TokenList to Parse an Integer Declaration Statement

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
Method * m = ...

TokenList * tl = ....



// if the next token is "int" its an Integer Declaration Statement

if (TokenList_peekType(tl) == SYMBOL_INT)

{

   // eat the "int" token

   TokenList_expect(tl, SYMBOL_INT, "");  



   // expect an ID that represents the variable name

   Token * variable_name = TokenList_expect(tl, LEXER_ID, "Expecting a variable name");



   // check that another variable by this name hasn't been declared in this method

   if (Method_addVariable(m, variable_name->m_value, SYMBOL_INT) == 0)

   {

      TokenList_error(tl, variable_name, "A variable by this name already exists");

   }



   // if we find a ";" the statement is over

   // if we find a "=" expect that an expression will follow

   if (TokenList_peekType(tl) == SYMBOL_SEMICOLON) {

      TokenList_expect(tl, SYMBOL_SEMICOLON, "");   // can't fail

   }

   else

   {

      // expect to see a "="

      Token * assign = TokenList_expect(tl, SYMBOL_ASSIGN, "Expecting a =");

      int expression_type;

      // call a function to evaluate the expression on the right hand side

      Pass1_expression(tl, m, &expression_type);



      // verify that the expression type matches the type of the variable

      if (expression_type != SYMBOL_INT) {

         TokenList_error(tl, assign, "Expecting an integer expression on the right side of =");

      }

      // check to see that the statement is terminated by a ";"

      TokenList_expect(tl, SYMBOL_SEMICOLON, "Expecting a ;");

   }

}

Recursive Decent Parser Implementation

In this post’s code you’ll find the following functions within Parser.c.  Listed on the right side of the function name is the list of productions that it handles.

Pass0

• void Parser_pass0 – File
• void Parser_pass0_method – ExternalMethod, InternalMethod
• void Parser_pass0_block – does not directly correspond to a production, just checks that all ‘{‘ s and ‘}’ s come in pairs.

Results:

The first pass, creates a Dictionary of Method objects found in the entire file keyed by the method’s signature.  Each Method contains information about the number and type of parameters and whether the method is internal or external.

Pass 1

• void Parser_pass1 – File
• void Parser_pass1_method – ExternalMethod, InternalMethod
• void Parser_pass1_block – Block
• void Parser_pass1_statement – StringDeclareStatement, IntDeclareStatement, FunctionCallStatement, AssignStatement
• void Parser_pass1_expression – Lexer_INT (integer value), Lexer_STRING (string constant), Lexer_ID (local variable)
• void Parser_pass1_method_call_expression – FunctionCallExpression

Results:

Eventually an array of assembly op-codes.  At this point it just dumps the script to the screen for validation.

Conclusion

Next time I’ll start building the Virtual Machine  and have the Compiler start outputting instructions.  Over further posts I’ll  progressively add features to the language.

Download this weeks code.

As always, you can follow myself or Incubator Games on twitter at @igtristan and @incubatorgames respectively.