Saturday, 31 December 2016

The I76 FSM Processor in (painful) Detail

Long time, no code

So, the real world got in the way for a while, but it's time to look at Interstate 76 yet again to clean up some of the unresolved details from the finite state machine that I left hanging from last time.

The Plan Of Attack

Until now mainly I've been guessing as to how the FSM execution flow works; the kind of instructions that are supported and the way that it hangs together. However there's a limit as to how far we can go with that approach.

It's not that we can't come up with a model that will make the mission bytecode work; it's that there are too many possible working variations and we need to narrow these down into a manageable set to determine a concrete implementation.

The easiest way we have to do that is to look at the actual interpreter assembly and the game code that processes the incoming bytecode, so to go further we have to pick apart the I76 executable itself.


There's a couple of important decompiling tools that I've used to poke around the I76.EXE binary


A "native code to C/C++ decompiler, supporting x86, AMD64, and ARM", Snowman provides a convenient way of extracting out decompiled code flow and matching this to the i386 assembler. The decompiled code is a little "C++ style" verbose, but very useful for top level navigation.

Snowman is available at


A "32-bit assembler-level analyzing debugger" - once we've located and had a pass over the processing we can use OllyDbg to step through the running code and confirm our theories as to how the binary actually works.

Although I have version 2 this has trouble running with I76, so I'm generally using Version 1.1.

When using Olly be sure to go to the Options/Debugging Options menu, select the "Exceptions" pane and tick ignore for "invalid or privileged instruction".

Olly is available at


I'm running I76 on Linux under wine, and the wine debugger offers a neat CLI to set breakpoints, inspect memory, read registers, etc. This provides a slightly more repeatable debugging method than Olly, but Olly is better at interpreting the state of the code and exploring.

Unfortunately I couldn't get the gdb interface to run up I76, so we have instructions for the basic winedbg only.

Finding the relevant piece of the Binary

What To Look For

The things to look for are the target strings that describe FSM operations, and using Snowman's decompiler output to find the case selections that cover the ranges for op-code and action processing.

The action processing is particularly distinctive; the number of actions will result in a large switch. In practice I found the action processor first by looking through the decompiled code for a large case statement and then established the linked functions from there.

Where things actually are

To cut a long story short: For the basic I76 binary then these are the mappings.

The function at 0x0040EBB0 contains the instruction switch handling for the FSM op-code processor. It's a loop around a case statement covering the range of available instructions, and contains the action handler references. Also 0x40ec05 puts out the error string "unknown fsm assembler instruction" when the requested switch fails which helps confirm this is the right code.

The function at 0x0040D0D0 is the switch for the action handler. We can spot this because it's the function with a suitably large case statement, is called by the "right" case handler in the op-code processor and also 0x40d0f9 has a debug string referencing "unknown fsm prototype" in the switch failure handler.

Other Versions

In the (unpatched) Nitro executable then the FSM decoder is at 0x414db0 and the action handler at 0x413420. At first glance the FSM execution code looks largely the same.

The FSM Processor Up Close

Looking at the FSM handler - at the lead in then we load the first argument to the function as:

40ebd2: mov edi, [esp+0x64]

We then use the loaded EDI value to locate the op-code and use it for the switch:

40ebf0: mov ecx, [edi+0x10a8]
40ebf6: mov eax, [ecx]
40ebf8: dec eax
40ebf9: cmp eax, 0xd
40ebfc: ja 0x40ec05

i.e. we use "arg1 + 0x10a8" to locate the opcode, move it into EAX, and then subtract one from it (so our opcode range of 1-14 is a switch value of 0-13). Finally the the cmp/ja is the opening of our switch.

So we can say, with a reasonable degree of confidence that the "edi+0x10a8" is the FSM instruction pointer, and extrapolate from that to say the EDI value provided by argument 1 is the base of memory for this FSM instance.

One other operation we perform in the prologue is clearing the ESI register which we use as a loop counter, so we have

40ebd0: xor esi, esi

And at the tail end of the case operations we have

40ee79: inc esi
40ee7a: cmp esi, 0x3e8
40ee80: jl dword 0x40ebde

Which is the test to loop around and carry on processing the FSM. However some Op-codes (e.g. op-code 10 and 12) can break out and skip this test, so when the FSM runs it actually spins through repeatedly until it hits a return condition.

As a result we have a "pseudo code" loop of...

  if (loopcount > 800)
 ... set global flag ...

 opcode switch
 ...some of which break out...
} while (loopcount++ < 1000);

Interestingly this tells us how the jump op-code "10" may be different from the other jump op-codes, since it breaks out of the counting loop. We'd flagged this as the last op-code we see in microcode blocks and speculated about the side effects, but now we have a clue as to why that might be.



Looking at the assembler for Case 0, which we thought was a push (op-code 1):

40ec17: mov eax, [ecx+0x4]
ECX was referencing the op-code, and therefore it was pointing into the FSM bytecode containing op-code and argument pairs. Since this is an increment then it's likely that this should be the corresponding argument data to our current op-code. It looks like the FSM bytecode has been unpacked into 8 byte fields (4 byte op-code, 4 byte argument).

40ec1a: mov ecx, [edi+0x10b0]
Since EDI is the machine structure base, and we're expecting push, then the chances are this is a reference to the stack pointer address.

40ec20: mov [ecx], eax
The stack pointer referenced address is now set to the argument data value we retrieved from the FSM bytecode pointer.

40ec22: mov ecx, [edi+0x10b0]
40ec28: add ecx, 0x4
The stack pointer value is loaded to ECX and the value incremented by 4 (i.e. a dword)

40ec2b: mov edx, [edi+0x10a8]
40ec31: add edx, 0x8
Update the current opcode/data pointer (move FSM bytecode pointer forward). We move forward by 8 bytes, which is one 4 byte opcode & one 4 byte argument.

40ec34: mov [edi+0x10b0], ecx
40ec3a: mov [edi+0x10a8], edx
Update the actual Stack pointer and FSM bytecode pointer values in memory with the new versions we have in ECX and EDX

40ec40: jmp dword 0x40ee79
And finished. This goes back to the processing loop.

So, yes that's a push. And we've got the following mappings of what's in memory:
EDI + 0x10a8 => Current Pointer in the loaded FSM bytecode (FSM-IPtr)
EDI + 0x10b0 => Stack Pointer


Case 7 (Opcode 8) which we initially felt was a definite jump/call style instruction uses another field:
40ed51: mov eax, [ecx+0x4]
Load argument to EAX again

40ed54: mov ecx, [edi+0x10a4]
Load ECX with the property "+0x10a4". Since we're looking at a JMP style calculation this instantly looks to be the base of the FSM bytecode.

40ed5a: lea eax, [ecx+eax*8]
Calculates the target memory address - since bytecode fields are 8 bytes (4 byte op-code, 4 byte argument) the multiplier is 8 and so the result is the address of the "arg'th" entry from the "+0x10a4" address. This ties up with a jump calculation.

40ed5d: mov [edi+0x10a8], eax
Set the current FSM instruction pointer to the calculated value.

So that's a "goto" style statement with the argument as an absolute address in the FSM code which confirms another piece of the memory layout:
EDI + 0x10a4 => Base of the FSM bytecode.

Confirming That Push

Now we can look at these operations in the debugger to confirm our reading of the op-codes and fields.

Launch The Debugger

Launch it with:

cd .wine/drive_c/Program\ Files/Activision/Interstate76/
winedbg ./I76.EXE

And at the debug console set up the break on the FSM processor and start the application.
Wine-dbg>b *0x40ebd2

This runs up the app, and we can launch a mission. Choosing the training mission we'll see a "Somewhere In The Southwest" and then the debugger will hit the breakpoint.

Look At The Running Program State

We can use the wine debugger to look at the source where we have halted:
0x0040ebd2: movl 0x64(%esp),%edi
0x0040ebd6: movl 0x6c(%esp),%ebx
0x0040ebda: movl 0x70(%esp),%ebp
0x0040ebde: cmpl $0x320,%esi
0x0040ebe4: jle 0x0040ebf0
0x0040ebe6: movl $0x1,0x005054ac
0x0040ebf0: movl 0x10a8(%edi),%ecx
0x0040ebf6: movl 0x0(%ecx),%eax
0x0040ebf8: decl %eax
0x0040ebf9: cmpl $13,%eax

This ties up with the Snowman view of these op-codes, although different mnemonic conventions are in use (AT&T versus Intel).

Now we can use "si" to step forward:
0x0040ebd6: movl 0x6c(%esp),%ebx
0x0040ebda: movl 0x70(%esp),%ebp
0x0040ebde: cmpl $0x320,%esi
0x0040ebe4: jle 0x0040ebf0
Wine-dbg> info regs
Register dump:
CS:0023 SS:002b DS:002b ES:002b FS:0063 GS:006b
EIP:0040ebe4 ESP:0033f474 EBP:0000005f EFLAGS:00000283( - -- I S - - -C)
EAX:00000000 EBX:05f58138 ECX:00000000 EDX:05f6c5b8
ESI:00000000 EDI:05f61da0

At this point we can look at the running FSM pointers referenced through EDI
Wine-dbg>x/16x ($EDI+0x10a4)
0x05f62e44: 05f6c5b8 05f709d8 05f61da8 05f61dac
0x05f62e54: 05f62da0 05f62e68 00000000 000010c0
0x05f62e64: 04455355 05f6c574 05f6c58c 05f6c590
0x05f62e74: 05f6c594 05f6c598 05f6c5a8 00000000

And from our guesses so far, then we think that from this block of data:
0x05f6c5b8 (+0x10a4) is the base of the loaded FSM microcode
0x05f709d8 (+0x10a8) is the current FSM Instruction pointer
0x05f61dac (+0x10b0) is the current FSM Stack Pointer

Also looking at the value in "+10ac" this is one dword below the current stack pointer (0x05f61da8), so there's an immediate suspicion this might actually be a reference to the stack base.

Dumping those memory values (as decimal) then the base of the loaded microcode is
Wine-dbg>x/16d 0x05f6c5b8
0x05f6c5b8: 0006 0001 0008 0002
0x05f6c5c8: 0005 -0004 0005 -0005
0x05f6c5d8: 0001 0275 0004 0002
0x05f6c5e8: 0013 0064 0007 0001

And this ties up with our extraction of the FSM microcode, specifically our initial "Block 3" dump from the A01 mission looks like this:
Block3/0 6:1
Block3/1 8:2
Block3/2 5:-4
Block3/3 5:-5
Block3/4 1:275
Block3/5 4:2
Block3/6 13:64
Block3/7 7:1

which all ties up. Hooray.

Also our current FSM IPtr is referencing:
Wine-dbg>x/16d 0x05f709d8
0x05f709d8: 0001 0000 0001 0000
0x05f709e8: 0001 0001 0006 0001
0x05f709f8: 0008 2185 0013 0052
0x05f70a08: 0009 2191 0004 0004

And this is 17440/8 = 2180 entries into the FSM microcode which we had as:
Block3/2180 1:0
Block3/2181 1:0
Block3/2182 1:1
Block3/2183 6:1
Block3/2184 8:2185
Block3/2185 13:52
Block3/2186 9:2191
Block3/2187 4:4

All of which looks correct

Watching the Push Happen

Walking through the first three operations we should see the stack pointer updating by 12 bytes (from 0x05f61dac to 0x05f61db8) and the stack values "0 0 1" should be pushed onto the stack.

So after stepping through the FSM processing for the first three instructions we see looking at the first three values from the initial Stack Pointer:
Wine-dbg>x/3d 0x05f61dac
0x05f61dac: 0000 0000 0001

And the running FSM pointers are:
0x05f62e44: 05f6c5b8 05f709f0 05f61da8 05f61db8
0x05f62e54: 05f62da0 05f62e68 00000000 000010c0
0x05f62e64: 04455355 05f6c574 05f6c58c 05f6c590
0x05f62e74: 05f6c594 05f6c598 05f6c5a8 00000000

Which is all in line with the changes we believe we should have for the stack & pointer values.

And The Rest

So, this is the basics of how we verify the FSM op-code operation. It takes a lot of verbose detail to go over this for every instruction, so I'll skip over the JMP but it's a similar process to validate. Next time I'll write up the other op-code values we can decipher, and some additional structural details, but this'll do for now. Updated: A couple of minor typo/spelling fixes