New game uploaded: Core War

[rje]

I've shortened the call stack to

main() ->repl() -> vm_execute() -> get location(ip)

...but the problem remains unchanged -- and at the border when crossing from one bank to the next.  So now I think maybe it's a blatant bug in the banking code.

 

[rje]

Found it.  It was a relatively trivial problem:  the current instruction was a pointer into banked RAM, and at the boundary that bank switches during the decoding of the full instruction, so the opcode switched as the memory switched out from under it.

The fix is to copy the memory to a temporary variable.

The code now appears to run, but the user interface is still a primitive CLI.

Work checked in to the repo.

Whew.

[svenvandevelde]

15 hours ago, rje said:

I'm working through the implications of moving to multiple banks.



Since I hold _pointers_ to some data, I have to take care that the underlying memory doesn't change out from under them!



Or more correctly, I have to know when to copy out values instead of using pointers.



Yes, I have some pointers into banked RAM.  Not very many, and I'm fixing the places where that's a bad idea.



* * *



The Arena



The arena is (currently) 8191 cells wide.  Bank determination is used with two constants:

#define CELLS_PER_BANK 1000

#define CORE_MEMORY(n) ((Cell *)0xA000)[n % CELLS_PER_BANK]

And setting the bank number is:

unsigned char bank = 10 + (position / CELLS_PER_BANK);

* * *



Cell Size



1000 cells per bank lets the cell size range up to 8 bytes.  But what's a reasonable upper limit?



Assume an arena would never be larger than 16,000 cells -- in other words, assume a cell operand doesn't have to address more than a 14 bit space, ever.



A cell has an opcode, two operands, and each operand has a mode.



The opcode is 4 bits.



Each operand is (as above) 14 bits, and each operand's mode is 2 bits.



That's 4 + 14 + 2 + 14 + 2 = 36 bits = 5 bytes.  4 bits left over for whatever.



So our current usage of each bank is 5,000 bytes.  I could pack in 1,600 cells per bank.



 



 



 

i have a similar problem with my heap manager. I do the same. my headers are 8 bytes. I can store 1000 headers in one bank.

[rje]

OK, now that the VM is working somewhat, and I am able to load and run corewar programs... and they actually run... well usually... OK there is probably another loose pointer in there, and I should track it down.

But I've also started looking up redcode examples, and I've realized that I really ought to support the full ICWS'88 standard.  This is simply because there are a HUGE number of examples available, and they should run without modification. 

This means I need to do this, from "easy" to "hard":

(1) Allow commas separating operands (they're easy to ignore).

(2) Support the predecrement indirect addressing mode.

(3) Support labels.  That's not trivial.

(4) Write an operand expression engine.  THAT will be annoying, but at least I know how to do it.

 

[rje]

The expression engine looks weak. It runs when the program is being "compiled" into memory, right after labels are replaced with address offsets.  An example is:

(jumpd + len + 2) * 5 + 2

First, the labels are grabbed and interpolated.

(1700 + 10 + 2) * 5 + 2

Then subject the above to a linear, left-to-right parser.  In other words, the only precedence rule is parentheses.

I can make it stronger using something like "full parenthesiziation", and I just might try it.  https://en.wikipedia.org/wiki/Operator-precedence_parser

 

[rje]

Ah, I see the bug, and it's related to a pointer left behind during banking.  I just have to track it down now.

Observe the screen shot.  I've run the VM several times with this one redcode program that's just long enough to have part of it on one side of a bank, and part on the next bank, for about ten epochs, as it slowly crawls across the boundary.  It's a great test case actually.

The most interesting suspects died at locations 4500, 6009, and 7500.  I've seen a number of these die on location 6000.

As you might be able to tell, I have 1500 cells per bank.

VERY suspicious.  The process dies on the border, probably because it's reaching ACROSS that border to the other end of the code.  It jumps back and forth, you see, copying itself forward.

So, something is getting hosed.

I can "dissassemble" core memory, and find out which instructions are at those exact addresses (1513, 3010, 4500, 6009, and 7500):

1513

1513 is an invalid address.... actually I think I see the problem.  There is supposed to be valid code at 1513.  But instead, the program copy routine "skipped" seven memory locations when copying its program... from 1512 thru 1518.



And actually, it looks like the MOST RECENT copy was written to location 1522+.  So why is control jumping to 1513?  

3010

3010 is super invalid... but looking backwards slightly, I see that location 2996-2999 is only a fragment of the full program, which is then missing 6 instructions, and then has the final 2 instructions at 3000-3001, but the data appears wrong in 3002-3003.

And so on.

With the 4500 and 7500 entries, the data simply *ends* right at those points, as if there was something stopping the MOV operation.

 

So I suspect the MOV operation is relying on a pointer, when it shouldn't.

 

[rje]

Found the problem:

void arena_setData(int target, int source)

{

Cell *src = arena_getLocation(source);

arena_setLocation(target, src);    <------ RIGHT THERE.  Cell *src is a pointer into banked RAM, right?  Well watch this:

}

 

void arena_setLocation(int target, Cell *copy). <-- watch this space...

{

Cell *tgt = arena_getLocation(target);    <-------- Aiiieeee.  We will occasionally CLOBBER the bank that *copy was "pointing" to!

tgt->opcode = copy->opcode;

tgt->aMode = copy->aMode;

tgt->A = copy->A;

tgt->bMode = copy->bMode;

tgt->B = copy->B;

}

[rje]

(1) Allow commas separating operands. DONE

(2) Support the predecrement indirect addressing mode.  DONE

(3) Allow single-operand on DAT, JMP, and SPL (at least). 

(4) Support labels. 

(5) Write an operand expression engine. 

** ICWS'88 compatability at this point **

 

 

[rje]

Memory usage so far.

Binary: 15K (and it'll grow before it's at a reasonable resting point).

Arena: 40,955 bytes in 6 RAM banks.

It looks to me that the arena could never reasonably fit into main RAM unless

1. 
   the core size remained uncomfortably small
   
   OR
   


2. 
   special RAM-gymnastics were done*
   

 

* for example, dividing memory up into 36-bit chunks.

[rje]

(1) Allow commas separating operands. DONE

(2) Support the predecrement indirect addressing mode.  DONE

(3) Allow single-operand on DAT, JMP, and SPL (at least). DONE

(4) Support labels. 

(5) Write an operand expression engine.