Implement a Virtual Machine, which can execute the Test Program outlined below.

Use the following outline for submitting all projects.

Submit your project via canvas.

Your project MUST be packaged in a zip file the name of this .zip is:

YourName_p1.zip

Where YourName is your name p1 is the name of the project

Note: Canvas will allow you to resubmit your project as many times as you want. Only the most current version will be kept my Canvas and graded by me. I highly encourage you to submit early and often. If you wait to the last moment and Canvas, the internet or your computer doesnt work then THIS IS A MISTAKE on your part.

Your project must include:

1. Source Code for your project.

2. Notes put directly in Canvas that tells me how to execute your program and other facts you want me to know. Only needed if your project doesnt work as I would expect ( vm,exe proj1.asm ). If you know you have a bug tell me. I think it is better to know you have a bug than it is to look like I found a bug you have no knowledge of.

3. asm this is your assembly file. This is what I grade. This file must be accepted as a command line argument. I may rename the file just to check that your code really works. Dont misname your project

4. exe this is your compiled executable. You must send an executable if your language doesnt support this then YOU Must build me a script to execute your program (vm.bat). Read if you dont understand what this means.

o Your executable must accept a command-line argument of the assembly file that it uses.

• exe proj1.asm Dont misname your project
• bat proj1.asm Dont misname your project

As long as you leave me explicit instruction on how to run your scripting language in Canvas I will accept it but you really should learn to use the vm.bat file

• Be very careful using Visual Studio to make your program every year students send me executes that will not execute on Windows because they are compiled incorrectly. Always execute your program outside of the development environment before sending it to me (or anyone else).
• Your program must not hang after running. I will execute it at command-line and will expect it to finish when the program is done.

Important Notes:

• Be sure to suppress all debug output in the final asm/vm version you submit.
• Make sure you give me an executable that runs on Windows. You can bring an executable to my office to run.

o THIS DOESNT NEED TO BE YOUR PROJECT o NO, I WILL PRE-GRADE IT THEN LET YOU FIX IT

• Read the assembly file name from the command-line dont hard code it.
• Your vm must NOT hang at the command-line waiting for input after the program has completed!
• You are making an awful assumption if you think you can get a passing grade on a project without completing every element of the project.

o I dont grade source code that doesnt compile and execute o I dont give you credit for programs that crash when run o This class is NOT like peewee soccer you will not be given credit for your effort only your achievements.

• Dont procrastinate this project can be completed by even an average CS student as long as you start today!
  • When Canvas closes it will not be reopened. o Dont send late projects to me via email. Complete them on time.
  • Submit Early Submit Often
• If you have questions about if the language you are using will execute on my machine come by my office and try it out.
  • NO I wont pre-grade your project
  • Remember you only need an example program not a completed project.

You may not change the syntax of the instructions! I will not grade it

You may not change the semantics of the instructions! I will not grade it

You may not add instructions. I will not grade it When in doubt ASK!

Test Program

Write the following assembly program using your assembly language.

Place the following list of integers in memory

• = (1, 2, 3, 4, 5, 6)
• = (300, 150, 50, 20, 10, 5) C = (500, 2, 5, 10)

Place your full name Last Name, First Name in contiguous memory.

Program Output (follow the output formatting exactly. Im very picky on this assignment not so much on the others.)

• Print your name Last Name, First Name on the screen. You dont need the quotes but you do need the comma.
• Print a blank line.
• Add all the elements of list B together; print each result (intermediate and final) on screen. Put 2 spaces between each result. pay attention to this (e.g., 450) pay attention to this
• Print a blank line. pay attention to this
• Multiply all the elements of list A together; print each result (intermediate and final) on screen. Put

2 spaces between each result. (e.g., 2) pay attention to this 6) Print a blank line.

7) Divide the final result from part 3, by each element in list B (the results are not cumulative). Put

2 spaces between each result. (e.g., 1) 8) Print a blank line.

9) Subtract from the final result of part 5 each element of list C (the results are not cumulative). Put

2 spaces between each result. (e.g., 220)

Create a directive for each element of the list and letter of your name.

Example.

A1 .INT 1

A2 .INT 2

A3 .INT 3

C .BYT C u .BYT u r .BYT r

Grading

The project is worth 100 points Systematic Deductions are taken off the top before individual Project Deductions are made. Systematic Deductions are like penalties for doing something a senior shouldnt do because they are just too fundamental and simple.

A basic outline of the grading process but this doesnt necessarily cover every case:

All Project grades in CS 4380 are Performance-based (Mastery Grades) meaning you will only receive credit for elements you complete correctly not things you attempt. You should never expect to receive credit for elements you work on but do nothing.

Systematic Deductions

Late (no excuses; submit early; submit often) -100 Naming executable or asm file incorrectly -10 vm.exe/vm.bat, proj1.asm

Sending an un-executable project -20

Doubles with each offense (most often a VisualStudio issue)

VM hangs when finished -10

VM crashes during execution -50 or greater

Debug Output -10

Failure to send all the elements in your zip -10 Not following instructions which forces me

to regrade your project (e.g., altering instructions) -20

Project Deductions

Each Major element -20 max

Your Name, Add, Multiply, Divide, Subtract, Stop, Modify and Re-run

Projects with a grade of 60 or lower are rare but indicate significant issues in your development skills or time management. While its still possible to pass the class with such a grade on a single project; such a grade generally indicates without a massive effort on your part, youll end up not passing this class as youll continue to have problems on future projects as well.

The issue isnt making one bad mistake and then having to cover for it the rest of the class by making good grades to pass. If you will sit down with Excel or a calculator you can easily see what I mean. The issue is most students who get a poor project grade will have poor grades on subsequent projects and marginal test grades.

Late projects will not be graded. Dont ask. However, if you take the time to bring it to my office and sit down with me, I will talk to you about it. Even a 0 on a single project doesnt mean you will fail the class if your test, homework and other project scores are high.

Hints:

Write the simplest Assembly program you need to complete the test program. You dont need LOOPS or REGISTER INDIRECT ADDRESSING to complete the project. Then write an assembler and a Virtual Machine to execute your program.

Do this as an incremental Development Project not one big problem.

C Implement a Two-Pass Assembler. The instructions you implement are to be taken from the move instructions, arithmetic instructions, trap instructions. Not all instructions are needed for this project, but you will need to implement all these instruction (plus a few more) by the time you turn in the last project.

CCIn the first pass create a Symbol Table (Associative Map)

The key of the Symbol Table is a Label (Code, Data) from an assembly program. The value associated with the key is the location of the Label (Label Address). Compute the address of the Label during the first pass.

Instructions count for N bytes of space

.BYT Variables count for 1 bytes of space

.INT Variables count for K (a min of 4) bytes of space

Pass #1

Read a line of text

Break text on spaces

Find optional label

Find OperatorFind OperandsIncrement counter by instruction

OR

Find DirectiveFind Dataincrement counter by data size

Generate Error Message

Load label to Symbol Table

CC In the second pass create byte code for your program. Using the Symbol Table convert Labels to addresses. Your byte code must be all numeric data: (e.g., ADD is 13, R7 is 7, Label A is 1024, etc.) Pass #2

Read a line of text

Break text on spaces

Find optional label

Find OperatorFind OperandsLookup address for labelsConvert instruction to bytecode Load bytecode to memoryIncrement counter by instruction

OR

Find DirectiveFind DataConvert data to binaryLoad binary data to memoryincrement counter by data size Generate Error Message

To parse instruction in the first and second pass read one (1) line of data at a time from your assembly file.

• Write a Virtual Machine (VM) that can execute your byte code. To make things simpler embed your assembler in your VM. Thus your program will work as:
  • Assembler Pass 1 Parse instruction & Load Symbol Table
  • Assembler Pass 2 Parse instruction, Create Byte & Load Byte Code to Memory
  • Execute Byte code Program

Dont try to skip these steps. It will not work and its not easier!

Separating your Assembler and VM will make completing CS4380 more difficult!! Dont do it!

• You will need the following address modes for this project
  • Direct EA = Address
  • Register EA = Register
  • Immediate may also be very useful

CMemory layout is one of your biggest issues. There are a few major options to consider. IF you have done Project 0 you are finished with this part of the project!

CC Traps 1 and 3 are used for output to the screen. Note there is NO TRAP THAT CAN WRITE OR READ A STRING! Dont create one!

CCCC Strongly consider supporting comments. Just have your assembler discard the comments when they are encountered. Comments will help me grade your projects, even more they will help you write your projects.

MUL R5, R6 ; Multiply A * B

CCCC Dont overlook TESTING. Ive already talked about using TDD along with incremental design, implementation and testing. There are two additional steps you can take to testing that will ensure the quality of your project and the products you built.

1. Dont approach testing as a process to prove your system works always approach testing a process to prove your system doesnt work. Dont run test you know will work runs tests you believe will fail!
   1. If you believe the Earth is flat or the Sun circles the Earth or Apple invented the mouse or Java invented Garbage Collection you can find some evident to support this. However, it is simple to disprove each of these statements.
2. Find two other students taking CS4380 and once you have finish your projects compare the output of your projects. It is virtually impossible for three of you

get the same wrong solution UNLESS youre working too closely in developing your solution. CS4380 is NOT A GROUP Project!

1. Dont share code THIS IS CHEATING.
2. Swapping ideas is OKAY!

How to approach a big project (School or Work):

• Never build something because it is cool or cleaver.
• Only build what is needed to complete the project. o If you finish early you might have free time!
• Focus on what you must accomplish not what you want to do.
• Consider the order in which you must build things to make the best progress.
• Use both top-down and bottom-up design & implementation.

Assembler Pass 1

Read Assembly Source File

Group chars into Tokens (Lexical Analysis)

Regular Expressions

Tokenizer (C strtok)

String Compare

Finite State Machine

Check Syntax of Instructions (Syntax Analysis)

Ensure that all instructions are part of the defined Assembly Language.

[ optional ]

Directives:

[Label] .INT Integer

.ALN

[Label] .BYT Integer

Instructions:

[Label] Operator Operand1 [Operand2]

Operand1 is Register, Label or Immediate

Operand2 is Register, Label or Immediate

Load Defined Labels into a Symbol Table Labels on Directives (Memory allocation) Labels on Instructions (Branch locations) And resolve there address!

Symbol Table

Label Memory Address + other

Check that Defined Labels are unique

Assembler Pass 2

Check that Referenced Labels are defined in the Symbol Table

LDR R1, NUTMEG is label NUTMEG defined (what is its address?) JMP NEXT is label NEXT defined (what is its address?)

Generate Code (Byte Code)

We have a very simple LOADER on this project when you moved bytecode and data to memory youre implementing a LOADER.

Encode Assembly statements to some type of bytecode: Make your instructions fixed length

Op Code Operand 1 Operand 2

I strongly suggest you use an integer for the Op Code, Operand 1 and Operand 2 thus your fixed size instruction will be 12 bytes long. This is NOT optimal but you dont need optimized solutions just a good workable solution.

Directives (Labels) are NOT placed directly into memory. Only the data is placed into memory!!!!!!!

Execute Byte code Program (Virtual Machine)

Register-Register

(Load/Store)

me	mory

Real Memory Layout

Pick one solution or the other Dont Mix them together that is not a solution.

That is a MESS!

• Starting with Code first makes it easy to determine your initial PC (PC=0).
• Starting with Static Data first seems to be more readable than the inverse.

Just make a choice a stick to it! Dont waffle that just wastes time.

Virtual Machine

NOTE: Type Cast as allowed by C can be very helpful here!!!

MemoryType mem[MEM_SIZE];

Static Data (Byte or 4 byte Int)

Bytecode

Heap

Stack

ByteCode IR;

Object or Structure

• opCode is the instruction to execute.
• opd1 is the first operand of the instruction.
• opd2 is the second operand of the instruction.

PC is an index into mem[].

RegisterType reg[REG_SIZE];

Integer

R0 is 0 & R1 is 1

Encoding registers as an index into reg[].

The Big Switch (VM) PC = Beginning_Address;

Running = True;

# this pseudo code is not intended to execute

while(Running) {

IR = mem.fetch(PC); # fetch the current instruction from memory switch(IR.opCode) { case ADD: reg[IR.opd1] = reg[IR.opd1] + reg[IR.opd2];

PC++; break;

case MOV: reg[IR.opd1] = reg[IR.opd2];

PC++; break;

case LDR: reg[IR.opd1] = mem.getInt(IR.opd2);

PC++; break;

}

}