Writing an Emulator

**Arthur J. O'Dwyer** · Nov 13 '05, 11:13 PM

Re: Writing an Emulator

[Second try; I don't know what happened to the first one.
Cc'ed to the OP, just in case Usenet eats this one too.
F-up to comp.programmin g.]

On Sun, 23 Nov 2003, Douglas Garstang wrote:[color=blue]
>
> I posted a newsgroup question here a few weeks back, asking some
> questions that related to my 10 year quest (so far) to understand
> pointers.
>
> Someone[/color]

Richard Heathfield. It would be nice if you'd take the time to
look up your quotes. Google Groups might help.
[color=blue]
> suggested I write a simple emulator. Part of his post is
> below. I would have emailed him directly but a valid email wasn't
> included.
>
> I'm sure its quite simple for him, but I don't get it! I understand
> his suggestion conceptually, but don't have a clue where to start. How
> will these 'programs' run? How will the instructions be executed? What
> do I do with the instructions? Just print them on the screen? Jeez,
> maybe if I was a hardware engineer I might have a clue.[/color]

Basically, Richard is suggesting that you create an "imaginary
computer" from scratch -- you can even do this on paper. Once you
have got the basic idea, you can write a C program to emulate the
imaginary machine in software.
Personally, I think this is a bad way to learn pointers, although
it's a nice exercise for general understanding of how computers
work. See below.

[Richard Heathfield wrote:][color=blue]
> If you want to understand pointers, write a computer. Or rather,
> write an emulator for the non-existent computer of your choice.
>
> Start off simple. A 1-bit computer with 2 1-bit "bytes" of memory, a
> 1-bit instruction register (it holds the address in memory of the
> next instruction to be executed), and one 1-bit register. Decide on
> an instruction set for it (it'll have just two different instructions),
> and then write it.[/color]

Okay. Let's make a computer! But first we need to get a few
terms straight. Most modern computers have "registers" and "memory."
Memory is the big open space where data is stored; there's a lot of
it, and it can be addressed sequentially. Memory is where the computer
stores programs and other data. Registers are by comparison very small
areas of storage; there are only a few of them, but most CPU operations,
or "opcodes," operate directly on them, so they're fast and useful.

Computer A is our first attempt at making a computer. It's the
1-bit computer Richard describes above.
Computer A has one 1-bit instruction register, IP ("Instructio n
Pointer"). IP holds the memory address of the next instruction to
be executed by the CPU. After executing each instruction, the CPU
automatically increments IP by 1.

Exercise 0: How many different memory addresses does Computer A
have, in all?
Answer: Notice that IP is only one bit wide. That means that
Computer A can address only 2 memory addresses in all: address 0 and
address 1 ("M0" and "M1", in our notation).

Computer A also has a general-purpose register, R0. It's one bit
long, too.
Note that the registers IP and R0 don't have memory addresses;
M0 and M1 are distinct from the register set.

Notice also that the state of Computer A can be completely described
by only four numbers -- four bits, really. For example, one state of
Computer A is
IP: 0 R0: 1 M0: 1 M0: 0
These four numbers determine absolutely everything about the state
of the machine.

Now let's add some CPU opcodes, so that the computer can actually
start processing programs. First, we are always going to need a
"halt" opcode to terminate the program. Let opcode '0' be HALT.
Whenever IP ends up pointing to a memory address containing a HALT
opcode, the computer will stop executing the program (the program
will "terminate" successfully).
Let opcode '1' be the operation of printing "Hello world" to the
screen. (These imaginary opcodes can do whatever you like, really
-- but this is a nice user-friendly opcode that will make programming
Computer A a little more fun.)

Exercise 1: Suppose the state of the Computer A is
IP: 0 R0: 1 M0: 1 M0: 0
What happens if we let the computer run from this point? Does
the program terminate succesfully? Does anything get printed?
Answer: IP is 0. The instruction at memory address 0 is '1',
so we print "Hello world." IP is incremented by one. Now IP
is 1. The instruction at M1 is '0', HALT, so the program
terminates. So the effect of the total program is to print
"Hello world" and then halt -- the classic beginners' program!

Exercise 2: Suppose the state of the machine is
IP: 1 R0: 0 M0: 1 M0: 1
What happens if we let the computer run from this point?
Assume that all arithmetic on IP is done modulo 2, so that
the value of IP "wraps around" on overflow.
Answer: The opcode at M1 is '1', so we print "Hello world."
IP is incremented; we execute M0, which is '1', and print
"Hello world" again. IP is incremented to 1, and we print
"Hello world" again. And again. And so on. This program,
in short, is an infinite loop that never terminates.

Exercise 3: Draw on a piece of paper the 16 possible states of
Computer A. (16 is two to the fourth power.) Draw one more state,
and label it "Program Terminated."
Draw an arrow from each state to its "successor" state, the state
reached by executing the current instruction. Along each arrow,
write the output of the program at that stage (i.e., either "Hello
world" or nothing). What do you see?
Answer: This state diagram is pretty boring, isn't it? You should
have noticed by now that the R0 register isn't being used for
anything; you also might have noticed that all programs are either
infinite loops, or stop after one or two "instructio n cycles." We'll
remedy this shortly.
[color=blue]
> /Then/ write programs for it. (These are easy: 00, 01, 10, 11. All done.)[/color]

I'm way ahead of you, Richard. ;-)

Exercise 4: Let the program AB (for any values A, B) be the state
IP: 0 R0: 0 M0: A M0: B
Describe the effects of the four programs 00, 01, 10, and 11.

[color=blue]
> This can be done in around 300 lines of C code. Less if you're a terse
> coder, but mine is 300 lines (excluding a few printfs and comments),
> and it even includes a rudimentary disassembler.[/color]

I must be a very terse coder, then. :-)
Cut and paste this C program into another file, compile and run it.
Try out all four of the programs from Exercise 4. Do they do what
you thought they would? (Note that program 11, the infinite loop,
will require you to know how to break out of a program in your [real]
operating system -- try Ctrl-C for Windows or Linux.)

==cut here==

#include <stdio.h>

struct MemoryCell_1bit {
unsigned value: 1;
};

struct ComputerA {
unsigned R0: 1; /* 1 bit register */
unsigned IP: 1; /* 1 bit IP */
struct MemoryCell_1bit M[2]; /* (2 to the 1) memory cells */
};

#define OPCODE_HALT 0 /* stop the program */
#define OPCODE_HELW 1 /* print "Hello world" */

int main()
{
struct ComputerA a;
int t1, t2, t3, t4;
int running;

puts("Please input the initial values of R0, IP, M0 and M1,");
puts("in the following format: (1 1) (0 1) .");
printf("Input now. >");
fflush(stdout);
if (4 != scanf(" (%d%d ) (%d%d )", &t1, &t2, &t3, &t4)) {
puts("Something fouled up -- please run the program again.");
return 0;
}

a.R0 = t1;
a.IP = t2;
a.M[0].value = t3;
a.M[1].value = t4;

for (running = 1; running; a.IP++) {
switch (a.M[a.IP].value)
{
case OPCODE_HALT:
running = 0; /* halt program */
break;
case OPCODE_HELW:
puts("Hello world");
break;
}
}

puts("Program terminated.");
return 0;
}

==cut here==

[color=blue]
> Then write a 2-bit computer. That'll have four 2-bit "bytes" of
> memory, a 2-bit instruction register, and perhaps you can be daring
> and give it two 2-bit registers. The instruction set can have a
> massive FOUR instructions.[/color]

All right, here's where it gets slightly more interesting. Let's
design Computer B, our 2-bit successor to Computer A. This time, I'm
going to describe it only using C, so take a moment to study the
implementation of Computer A before plunging ahead.

struct MemoryCell_2bit {
unsigned value: 2;
};

struct ComputerB {
unsigned R0: 2; /* 2 bit register */
unsigned IP: 2; /* 2 bit IP */
struct MemoryCell_2bit M[4]; /* (2 to the 2) memory cells */
};

#define OPCODE_HALT 0
#define OPCODE_LOAD 1 /* takes a memory address */
#define OPCODE_INCR 2 /* increment R0 */
#define OPCODE_STOR 3 /* takes a memory address */

You can see that Computer B has still only the one register, R0,
but that R0 and IP are now 2-bit registers, and so are the memory
cells (and now there are four of them). OPCODE_HALT still exists,
but I've taken away the HELW opcode and replaced it with three
more cryptic instructions: LOAD, INCR, and STOR.
LOAD takes the "byte" immediately following the opcode in memory
and uses those two bits as an address. It loads the value stored
at that address in memory into R0. (E.g., the two-byte instruction
sequence '1 3' loads the contents of M3 into R0.)
STOR does the reverse, storing the value currently in R0 back
into the specified memory location.
INCR simply increments R0.

Here is the rest of the code for my implementation of Computer B.
Notice that I've added the "print_machine_ state" function, and that
the machine prints its state before executing each instruction.
This way we can keep track of what it's doing with our code.
You should also note that I didn't put any screen-output opcodes
in Computer B, so the "print_machine_ state" output is the only
output we're going to get. While Computer B can do some pretty
neat things by modifying its own programs during execution, it
can't print "Hello world" anymore. (But wait a bit...)

#include <stdio.h>
#define NELEM(x) ((int)(sizeof (x) / sizeof *(x)))
void print_machine_s tate(struct ComputerB *p);

int main()
{
struct ComputerB b;
int t1, t2;
int i;
int running;

puts("Please input the initial values of R0, IP, and M0..M3,");
puts("in the following format: (3 0) (1 2 3 0) .");
printf("Input now. >");
fflush(stdout);
if (2 != scanf(" (%d%d ) (", &t1, &t2)) {
puts("Something fouled up -- please run the program again.");
return 0;
}
b.R0 = t1;
b.IP = t2;

for (i=0; i < NELEM(b.M); ++i) {
if (1 != scanf("%d", &t1)) {
puts("Something fouled up -- please run the program again.");
return 0;
}
b.M[i].value = t1;
}

for (running = 1; running; b.IP++) {
print_machine_s tate(&b);
switch (b.M[b.IP].value)
{
case OPCODE_HALT:
running = 0; /* halt program */
break;
case OPCODE_LOAD:
b.IP++;
b.R0 = b.M[b.M[b.IP].value].value;
break;
case OPCODE_INCR:
b.R0++;
break;
case OPCODE_STOR:
b.IP++;
b.M[b.M[b.IP].value].value = b.R0;
break;
}
}

puts("Program terminated.");

puts("The final state of the machine was:");
print_machine_s tate(&b);

return 0;
}

void print_machine_s tate(struct ComputerB *p)
{
int i;
printf(" IP: %d R0: %d\n", (int)p->IP, (int)p->R0);
for (i=0; i < NELEM(p->M); ++i)
printf(" M%d: %d", i, (int)p->M[i].value);
printf("\n");
}

Exercise 5: Repeat Exercise 3 with a subset of 20 or 30 states
from Computer B. (How many states does Computer B have in total?)
Draw arrows as before. What do you notice?
Answer: Computer B has 4096 (=4**6) states in total. That's much
too many to draw at once. But even with a small subset of the states,
you should see that the diagram is more interesting and complex than
that of Computer A.

[color=blue]
> My version takes about 350 lines. And the 3-bit version is about 400
> lines. It's not difficult, believe me. And by the time you get up
> to 8 bits, you /will/ understand pointers.[/color]

Hmm. In my opinion, Richard speaks the truth, but only because
you won't ever make it to eight bits without an understanding of
pointers -- I don't see the C implementation of these computers
really using too many pointers (and when they do, as in the LOAD
and STOR instructions, we have double indirection).
But try anyway.

Exercise 6: Design and implement Computer C, a 3-bit version of
Computer B. It will have 8 three-bit "bytes" of memory, and eight
opcodes. Add some opcodes at least that do the following: Print
a message to the screen. Print the value of R0. A "jump" opcode
that directly changes the value of IP.

HTH, and please follow up to comp.programmin g with any questions
not directly related to the C implementations ,

-Arthur

**Strangely Placed** · Nov 13 '05, 11:13 PM

Re: Writing an Emulator

[Google's news "editor" isn't thrillingly good. Apologies if the text
flow is munged.]

"Arthur J. O'Dwyer" <ajo@nospam.and rew.cmu.edu> wrote in message news:<Pine.LNX. 4.58-035.03112402220 00.14393@unix46 .andrew.cmu.edu >...
[color=blue]
> On Sun, 23 Nov 2003, Douglas Garstang wrote:[color=green]
> >
> > I posted a newsgroup question here a few weeks back, asking some
> > questions that related to my 10 year quest (so far) to understand
> > pointers.
> >[/color][/color]
<snip>[color=blue]
>
> Basically, Richard is suggesting that you create an "imaginary
> computer" from scratch -- you can even do this on paper.[/color]

Right.

<snip>
[color=blue]
> Personally, I think this is a bad way to learn pointers, although
> it's a nice exercise for general understanding of how computers
> work. See below.[/color]

I have to disagree with you here, Arthur. It is precisely because it's
a nice exercise for understanding how computers work that it is /also/
a good way to learn pointers. Even if the OP chooses to implement the
solution in an unpointery language (Visual Basic springs to mind as a
possible candidate), the very act of implementing a computer will,
effectively, lead him to /invent/ pointers. And I can certainly attest
to the fact that inventing something definitely gives you a much, much
clearer understanding of it than merely reading about it can ever do.

<snip>
[color=blue][color=green]
> > This can be done in around 300 lines of C code. Less if you're a terse
> > coder, but mine is 300 lines (excluding a few printfs and comments),
> > and it even includes a rudimentary disassembler.[/color]
>
> I must be a very terse coder, then. :-)[/color]

Er, yes. Well, tersinosity has never been one of my objectives when
writing C. I tend to set my stall out rather verbosely.

<snip>
[color=blue]
> Hmm. In my opinion, Richard speaks the truth, but only because
> you won't ever make it to eight bits without an understanding of
> pointers[/color]

I venture to suggest that the process of writing the machine is very
likely to produce that understanding.
[color=blue]
> -- I don't see the C implementation of these computers
> really using too many pointers[/color]

No, not particularly, but that's not the point. The point is that the
"machine code interpreter" has to understand about how to read from
and write to the main memory of the simulation, and it is in designing
and writing that interpreter that the student's understanding dawns.

<snip>
[color=blue]
> HTH, and please follow up to comp.programmin g with any questions
> not directly related to the C implementations ,[/color]

Modulo those nits, I take my hat off to you for a superb answer. I
only hope the OP doesn't read it /too/ closely, since the whole idea
is for him to go through the design and development process himself.
It is on that road that he will encounter understanding.

--
Richard Heathfield
(Strangely Placed)

**Arthur J. O'Dwyer** · Nov 13 '05, 11:13 PM

Re: Writing an Emulator

On Mon, 24 Nov 2003, Strangely Placed [Richard Heathfield] wrote:[color=blue]
>
> Arthur J. O'Dwyer wrote...[color=green]
> >
> > Basically, Richard is suggesting that you create an "imaginary
> > computer" from scratch -- you can even do this on paper.[/color][/color]
[color=blue][color=green]
> > Personally, I think this is a bad way to learn pointers, although
> > it's a nice exercise for general understanding of how computers
> > work. See below.[/color]
>
> I have to disagree with you here, Arthur. It is precisely because it's
> a nice exercise for understanding how computers work that it is /also/
> a good way to learn pointers. Even if the OP chooses to implement the
> solution in an unpointery language (Visual Basic springs to mind as a
> possible candidate), the very act of implementing a computer will,
> effectively, lead him to /invent/ pointers. And I can certainly attest
> to the fact that inventing something definitely gives you a much, much
> clearer understanding of it than merely reading about it can ever do.[/color]

True. However, I will say that when I wrote the code for Computer
B, the one that includes the "LOAD" opcode, I was momentarily confused
by the parsing of the address operand to "LOAD"; see in the original
code how it has double indirection

b.R0 = b.M[b.M[b.IP].value].value;

where the "machine code" suggests single indirection

1 3 LOAD [M3]

IMHO that's going to be very confusing for anyone who's not already
confident enough in his pointer knowledge to plough ahead as I did,
trusting what I *knew* to be the right C expression even though it
*looked* kind of funny.
I do absolutely agree with you that the pencil-and-paper exercise
of designing your own computers is a great way to learn pointers
"by doing." But I respectfully submit that if you [meaning newbies]
try to *implement* these computers in C, you'll end up more horribly
confused than you started out. No matter how much more fun it is to
be able to see your imaginary programs executing on real machines.

[color=blue][color=green][color=darkred]
> > > This can be done in around 300 lines of C code. Less if you're a terse
> > > coder, but mine is 300 lines (excluding a few printfs and comments),
> > > and it even includes a rudimentary disassembler.[/color]
> >
> > I must be a very terse coder, then. :-)[/color]
>
> Er, yes. Well, tersinosity has never been one of my objectives when
> writing C. I tend to set my stall out rather verbosely.[/color]

What *did* your code look like? You still have it around anywhere?
Maybe you could post a URL. (And when you write:
[color=blue]
> The point is that the "machine code interpreter" has to understand
> about how to read from and write to the main memory of the simulation,
> and it is in designing and writing that interpreter that the student's
> understanding dawns.[/color]

it makes me think that your code might be horribly long because you
didn't use arrays or bit-fields for your memory cells; but if that's
the case, I want to see how you *did* do it. Morbid fascination,
y'know. ;-)

[color=blue]
> Modulo those nits, I take my hat off to you for a superb answer. [...][/color]

Thank you much!

-Arthur

**seemanta dutta** · Nov 13 '05, 11:14 PM

Re: Writing an Emulator

"Arthur J. O'Dwyer" <ajo@nospam.and rew.cmu.edu> wrote in message news:<Pine.LNX. 4.58-035.03112415475 30.13947@unix43 .andrew.cmu.edu >...[color=blue]
> On Mon, 24 Nov 2003, Strangely Placed [Richard Heathfield] wrote:[color=green]
> >
> > Arthur J. O'Dwyer wrote...[color=darkred]
> > >
> > > Basically, Richard is suggesting that you create an "imaginary
> > > computer" from scratch -- you can even do this on paper.[/color][/color]
>[color=green][color=darkred]
> > > Personally, I think this is a bad way to learn pointers, although
> > > it's a nice exercise for general understanding of how computers
> > > work. See below.[/color]
> >
> > I have to disagree with you here, Arthur. It is precisely because it's
> > a nice exercise for understanding how computers work that it is /also/
> > a good way to learn pointers. Even if the OP chooses to implement the
> > solution in an unpointery language (Visual Basic springs to mind as a
> > possible candidate), the very act of implementing a computer will,
> > effectively, lead him to /invent/ pointers. And I can certainly attest
> > to the fact that inventing something definitely gives you a much, much
> > clearer understanding of it than merely reading about it can ever do.[/color]
>
> True. However, I will say that when I wrote the code for Computer
> B, the one that includes the "LOAD" opcode, I was momentarily confused
> by the parsing of the address operand to "LOAD"; see in the original
> code how it has double indirection
>
> b.R0 = b.M[b.M[b.IP].value].value;
>
> where the "machine code" suggests single indirection
>
> 1 3 LOAD [M3]
>
> IMHO that's going to be very confusing for anyone who's not already
> confident enough in his pointer knowledge to plough ahead as I did,
> trusting what I *knew* to be the right C expression even though it
> *looked* kind of funny.
> I do absolutely agree with you that the pencil-and-paper exercise
> of designing your own computers is a great way to learn pointers
> "by doing." But I respectfully submit that if you [meaning newbies]
> try to *implement* these computers in C, you'll end up more horribly
> confused than you started out. No matter how much more fun it is to
> be able to see your imaginary programs executing on real machines.
>
>[color=green][color=darkred]
> > > > This can be done in around 300 lines of C code. Less if you're a terse
> > > > coder, but mine is 300 lines (excluding a few printfs and comments),
> > > > and it even includes a rudimentary disassembler.
> > >
> > > I must be a very terse coder, then. :-)[/color]
> >
> > Er, yes. Well, tersinosity has never been one of my objectives when
> > writing C. I tend to set my stall out rather verbosely.[/color]
>
> What *did* your code look like? You still have it around anywhere?
> Maybe you could post a URL. (And when you write:
>[color=green]
> > The point is that the "machine code interpreter" has to understand
> > about how to read from and write to the main memory of the simulation,
> > and it is in designing and writing that interpreter that the student's
> > understanding dawns.[/color]
>
> it makes me think that your code might be horribly long because you
> didn't use arrays or bit-fields for your memory cells; but if that's
> the case, I want to see how you *did* do it. Morbid fascination,
> y'know. ;-)
>
>[color=green]
> > Modulo those nits, I take my hat off to you for a superb answer. [...][/color]
>
> Thank you much!
>
> -Arthur[/color]

I personally think it is how you start to code your emulator that
decides whether pointers will be used extensively in the software or
not, which will ultimately determine ur level of understanding of
pointers.No doubt, writing an emulator for an imaginary computer will
lead to ideas like 'memory' and 'adress'. but lets not forget that
these can be implemented using pointers as well as simple arrays in C.

when i created my simulator for 8051 ( http://gsim51.sourceforge.net)
i did use pointers, but hardly for memory addressing etc. for me
pointers came in handy in calling the appropriate function for a
particular opcode( u can also have a look at at the code). although i
could have written every array access line with pointer notation, i
did not do that since i believe that pointers deserve much more
elegant use other than array access.

so ultimately it comes down to the point of individual likeness. i
think K&R would be a good reference for understanding pointers.with 10
years on C expereince u should not have any problems in getting thru
that book.

regards,
Semanta Dutta

**Richard Heathfield** · Nov 13 '05, 11:14 PM

Re: Writing an Emulator

Arthur J. O'Dwyer wrote:
[color=blue]
> What *did* your code look like? You still have it around anywhere?[/color]

I'd prefer not to post it (because I hope to publish it as part of a larger
work), but I will cheerfully email you a copy just as soon as I've finished
the project I'm currently working on (which will actually facilitate
sending the email!). In the meantime, here's a rough breakdown of the code.
just to give you an idea of the "shape" - i.e. how I approached the
problem:

Lines 1-27: Comment.
Lines 28-55: Preprocessor directives.
Lines 56-62: A typedef.
Lines 64-70: PrintBinary()
Lines 71-101: DisplayMachineS tate()
Lines 102-109: Fetch()
Lines 110-134: Execute()
Lines 135-139: GetPRN() - for simulating randomised memory at startup
Lines 140-149: DisplayPrompt()
Lines 150-159: GetENTER()
Lines 160-182: GetYesNo()
Lines 183-204: DoIntro()
Lines 205-217: UserWantsMore() - as in if(UserWantsMor e())
Lines 218-269: GetProgram()
Lines 270-331: RunProgram()
Lines 332-358: main()

Nothing here is terribly non-obvious, of course.

[color=blue][color=green]
>> The point is that the "machine code interpreter" has to understand
>> about how to read from and write to the main memory of the simulation,
>> and it is in designing and writing that interpreter that the student's
>> understanding dawns.[/color]
>
> it makes me think that your code might be horribly long because you
> didn't use arrays or bit-fields for your memory cells; but if that's
> the case, I want to see how you *did* do it. Morbid fascination,
> y'know. ;-)[/color]

Sorry to disappoint you.

typedef struct COMPUTER_
{
int State; /* HALTED or RUNNING */
unsigned char CurrentInstruct ion;
unsigned int CpuRegister[REGISTER_COUNT];
unsigned char Memory[ADDRESS_SPACE];
} COMPUTER;

--
Richard Heathfield : binary@eton.pow ernet.co.uk
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R answers, C books, etc: http://users.powernet.co.uk/eton

**Bill Godfrey** · Nov 13 '05, 11:15 PM

Re: Writing an Emulator

binary@eton.pow ernet.co.uk wrote:[color=blue]
> typedef struct COMPUTER_
> {
> int State; /* HALTED or RUNNING */
> unsigned char CurrentInstruct ion;
> unsigned int CpuRegister[REGISTER_COUNT];
> unsigned char Memory[ADDRESS_SPACE];
> } COMPUTER;[/color]

Hmmm, I'd have made CurrentInstruct ion another register, and called it
NextInstruction . Fits in the way that real-world CPUs work.

Of course, it's only a game as a learning device. Not like any of these
emulators-of-imaginary-hardware will actually see life beyond being just a
game.

Bill, having a horrible vision of how Java may have started.

**Martha H Adams** · Nov 13 '05, 11:56 PM

Re: Writing an Emulator

This is interesting. *This* is why I spend time scouting newsgroups
and coping with the rubbish out there.

There used to be, back in the TRS80 days, a "Tiny Pascal" that ran in
a trsdos environment. I've searched and googled a few times and have
never found it to run in a Freedos, msdos, nor Linux environment. If
anyone knows of a small descendant of that original Tiny Pascal
around, please advise (here) where I could find it. ??

Meanwhile, up this thread is a strong pointer for me to go make one
for myself.

Cheers -- Martha Adams

**Morris Dovey** · Nov 13 '05, 11:57 PM

Re: Writing an Emulator

Bill Godfrey wrote:
[color=blue]
> Of course, it's only a game as a learning device. Not like any
> of these emulators-of-imaginary-hardware will actually see
> life beyond being just a game.[/color]

Hmm. A long time ago (before I started wearing glasses) I wrote
an APL emulator for a small 16-bit CPU with writable control
store (WCS). When it was finally working properly I liked it well
enough to build it on an Augat wire wrap panel. After dealing
with a couple of race conditions, I finally got it working.

'Twas fun. It had an LCS <size>,<addr> (load control store from
RAM) instruction and a BOOL <op>,<r1>,<r2 > instruction that would
perform any of the sixteen possible Boolean <op>erations.

My "big idea" that I didn't ever manage to implement was to have
a compiler work up an optimized instruction set for each compiled
program, then produce the WCS load for that instruction set along
with the TU's object code. Somewhere along the line I got bogged
down in the functional analysis and abandoned the whole project.

It did see light ( But not much light )-:
--
Morris Dovey
West Des Moines, Iowa USA
C links at http://www.iedu.com/c
Read my lips: The apple doesn't fall far from the tree.

**Willem** · Nov 13 '05, 11:57 PM

Re: Writing an Emulator

Morris wrote:
) 'Twas fun. It had an LCS <size>,<addr> (load control store from
) RAM) instruction and a BOOL <op>,<r1>,<r2 > instruction that would
) perform any of the sixteen possible Boolean <op>erations.

<nitpick>
Don't you mean eight possible boolean operations ?
Although I recall the blitter chip in an amiga also having sixteen possible
operations, but that had three inputs and one output.

) My "big idea" that I didn't ever manage to implement was to have
) a compiler work up an optimized instruction set for each compiled
) program, then produce the WCS load for that instruction set along
) with the TU's object code. Somewhere along the line I got bogged
) down in the functional analysis and abandoned the whole project.

I seem to recall reading a doctorate thesis about this idea...

SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

**Morris Dovey** · Nov 13 '05, 11:57 PM

Re: Writing an Emulator [OT]

Willem wrote:
[color=blue]
> Morris wrote:
> ) 'Twas fun. It had an LCS <size>,<addr> (load control store from
> ) RAM) instruction and a BOOL <op>,<r1>,<r2 > instruction that would
> ) perform any of the sixteen possible Boolean <op>erations.
>
> <nitpick>
> Don't you mean eight possible boolean operations ?
> Although I recall the blitter chip in an amiga also having sixteen possible
> operations, but that had three inputs and one output.[/color]

Nope. Imagine a truth table like (AND: <op> == 0x1):

A | 0 0 1 1
B | 0 1 0 1
--+--------
r | 0 0 0 1

Then if the same ordering of A and B values were used for all
sixteen tables, the corresponding r values would range from 0x0
to 0xF - with the first and last being "trivial" (always zero and
always one) operations.
[color=blue]
> ) My "big idea" that I didn't ever manage to implement was to have
> ) a compiler work up an optimized instruction set for each compiled
> ) program, then produce the WCS load for that instruction set along
> ) with the TU's object code. Somewhere along the line I got bogged
> ) down in the functional analysis and abandoned the whole project.
>
> I seem to recall reading a doctorate thesis about this idea...[/color]

Not guilty. But I still like both concepts (the dynamically
writable control store and the optimization).

Did the thesis writer develop the idea into anything
implementable? [If the answer is "yes" I need to track him/her
down and present a bottle of fine champagne!]
--
Morris Dovey
West Des Moines, Iowa USA
C links at http://www.iedu.com/c
Read my lips: The apple doesn't fall far from the tree.

**Willem** · Nov 13 '05, 11:57 PM

Re: Writing an Emulator [OT]

Morris wrote:
) Nope. Imagine a truth table like (AND: <op> == 0x1):
)
) A | 0 0 1 1
) B | 0 1 0 1
) --+--------
) r | 0 0 0 1
)
) Then if the same ordering of A and B values were used for all
) sixteen tables, the corresponding r values would range from 0x0
) to 0xF - with the first and last being "trivial" (always zero and
) always one) operations.

D'oh!

That must mean that the Amiga's blitter chip had 256 possible operations.
Which sounds plausible.

) Did the thesis writer develop the idea into anything
) implementable? [If the answer is "yes" I need to track him/her
) down and present a bottle of fine champagne!]

Err, I think so. But I might be bound by an NDA about that, because he was
my colleague at the time.

SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

**Morris Dovey** · Nov 13 '05, 11:58 PM

Re: Writing an Emulator [OT]

Willem wrote:[color=blue]
> Morris wrote:
> ) Did the thesis writer develop the idea into anything
> ) implementable? [If the answer is "yes" I need to track him/her
> ) down and present a bottle of fine champagne!]
>
> Err, I think so. But I might be bound by an NDA about that, because he was
> my colleague at the time.[/color]

Willem...

Then if/when you see him again please convey my admiration and at
least a /virtual/ magnum. He did a significant piece of work.

<rant>
Hrumph! This NDA thing is getting out of hand. I recall a time
when a thesis was supposed to be an original contribution to the
/common/ body of knowledge - for the betterment of the human
condition and all that.
</rant>
--
Morris Dovey
West Des Moines, Iowa USA
C links at http://www.iedu.com/c
Read my lips: The apple doesn't fall far from the tree.

**Willem** · Nov 14 '05, 12:05 AM

Re: Writing an Emulator [OT]

Morris wrote:
)<rant>
) Hrumph! This NDA thing is getting out of hand. I recall a time
) when a thesis was supposed to be an original contribution to the
) /common/ body of knowledge - for the betterment of the human
) condition and all that.
)</rant>

I *might* be bound. I'm pretty sure I'm not, because it's a thesis paper
that has been published and stuff, but I'd rather not mess with the big
corporations. <Cowers in a corner>

;-)

I found the book, by the way..

"Automatic Synthesis of Reconfigurable Instruction Set Accelerators"
by Bernardo Kastrup, 2001, ISBN 90-74445-50-0

Nice fellow, and a pretty good chess player as well.

SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

**Morris Dovey** · Nov 14 '05, 12:06 AM

Re: Writing an Emulator [OT]

Willem wrote:
[color=blue]
> "Automatic Synthesis of Reconfigurable Instruction Set Accelerators"
> by Bernardo Kastrup, 2001, ISBN 90-74445-50-0
>
> Nice fellow, and a pretty good chess player as well.[/color]

Thanks! I just downloaded a copy from the Design Automation
Section at TU/e. Very nice of them to make it available online.

In case anyone else is interested, this thesis is available (in
English) at http://alexandria.tue.nl/extra2/200101304.pdf
--
Morris Dovey
West Des Moines, Iowa USA
C links at http://www.iedu.com/c
Read my lips: The apple doesn't fall far from the tree.