Latest Posting: June 16, 2002 (11 AM)

Posted: June 14, 2002

Addendum

Read this section frequently to check for updates/corrections/clarifications to the projects.

• The text has been extended to make it easier to follow. You may want to reread the whole thing.

Clarifications

Purpose

The goals of the project are:

• To start to write an assembly lanugage interpreter
• To parse an input file which represents the assembly language program
• To use command line arguments for the interpreter

Academic Integrity Statement

Please note that *all* programming projects in this course (including this one) are to be done independently or with the assistance of the instructional staff of this course only, unless otherwise specified IN PRINT by official webpages.

Please review the policies outlined on the class syllabus concerning the use of class computer accounts and concerning the University's Code of Academic Integrity. The instructors of this course will review the programs submitted by students for potential violations of the Code of Academic Integrity and if it is believed that a violation has occurred it will be referred to the Office of Judicial Programs and the Student Honor Council.

Hardcoding is considered a violation of academic integrity

Terminology

A list of terms that might be useful.

• word 32 bits, 4 consecutive bytes
• byte-addressable Each address in memory stores a byte.
• word-aligned To place a word (four consecutive bytes) at an address divisible by 4.
• C-style string A string that ends in a null character. Uses strlen(str) + 1 bytes of memory. The "1" is for the null character.
• label an identifier indicating a specific address (computed by the assembler). An identifier consists of a letter or underscore, followed by zero or more letter, digits, or underscores.

Overview

The goal of the project is to process an assembly language program stored in a file.

This program is divided into two parts: the data segment and the text segment. Think of the data segment as the variable declaration section, and the text segment as the actual code.

Your goal is to determine where in memory the data and the code will be stored, subject to certain restrictions. You won't actually run the program, nor store the data (although, it won't hurt to store the data since you'll actually run the program next time).

The program is expected to run in the following way.

• Run the executable with command line arguments. The command line arguments indicate what address the data segment begins at, what address the code segment begins at, and which file to load. (It can also run without any command line arguments). See section on Command Line Arguments below.
• This will cause the file specified to be loaded and processed. After that occurs, the program accepts commands from the command line. This may cause other files to be loaded and processed, or the user may choose to quit.
• The program ends once the user chooses to quit.

Thus, there are at least two files: the assembly language file, and the command file. The assembly lanugage file is opened using whatever method the language you use opens files (fstream, etc).

The command file is processed by reading from standard input, so this will be redirected to test your code.

In particular, these are the tasks you need to do.

1. Determine which file to load. This may be specified in the command line or in the commands file (sent to your program via input redirection.
2. Determine which address in memory the data and code segment will start (there are two addresses: one for data, and one for the code). This information for these addresses are either provided in the command line and/or in the commands file.
3. Process the commands.

Basic Assembly Language Program Layout

As assembly language program (at least, for the purposes of this class) consists of a data segment and a text segment.

The data segment is essentially where "variables" (actually, labels) are "declared and initialized".

The text segment is the assembly language program.

It's somewhat analagous to C code where all variables must be declared at the beginning, and then the actual code appears afterwards.

Visually, the assembly language file looks like:

   .data

   #  LABELS appears in this section

   .text

   #  assembly language program here

Data Segment

The data segment starts off with the phrase ".data". This is how you know you are in the data segment.

    .data

There may be leading spaces before and after the word. There may be blank lines before and afterwards.

After this line, there are a list of labels. Labels are somewhat like variables. Each label is associated with a memory location, which has to be calculated. The address depends on the type of data that is stored, as well as previous data that's already been computed.

Example and Syntax

Here's an example:

value: word 23

Let's see what this means:

• value is a label, which is an identifier followed by a colon.
  • You may assume that labels always appear at the beginning of a line (although there may be blank spaces before the label).
  • You may assume the colon appears immediate after the label, i.e., there are no spaces between the label and the colon.
• Then, there is at least one or more whitespace (i.e., blank spaces/tabs/newlines) after the label and colon.
• This is followed by the type. The valid types are: word, word array, byte, byte array, and string (although word array and byte array) have special syntax).
• This is followed by one or more whitespace.
• Then, there is an initializer value or an initializer pattern (this may be optional--see below).

When does a label end?

Since the labels may span more than one line, and there may be blank lines, how do you determine when the label ends? There are two ways. Either the next label starts (and the next label is always at the beginning of a line, preceded by possible blank spaces), which indicates the current label is complete.

Or, the ".text" segment begins.

Parsing algorithm

Here's a simple algorithm to help you parse labels.

• Look for the .data line.
• Read in an entire line of text.
• Search for a label (a line with a word, followed by a colon).
• Read in following lines. If those lines don't contain a label and don't contain .text, then concatenate that to the current line.
• If it does contain a laebl or .text, then process the line with the label (split it apart, and process).

Description of "Types"

Here are the possible types:

Type	Explanation	Syntax
word	Stores one word. Must be word aligned.	word <word-value>?
word array	Stores an array of words. Must be word aligned.	word [<digits>] <word-pattern>?
byte	Stores one byte.	byte <byte-value>?
byte array	Stores an array of bytes	byte [<digits>] <byte-pattern>?
string	Stores C-style string	string "<string>"

Let's look at each type more carefully:

• word

  After the label and a colon, there is zero or more spaces (may include newlines), followed by word, followed by one or more spaces (may include newlines), followed by a possible value.

  The value can be written in base 10, hexadecimal, or octal. If written in base 10, assume that it can be either positive or negative, and the value can be stored in 32 bit signed (two's complement) integer. Hexadecimal values start with 0x. Octal will start with 0. Hexadecimal and octal are written as unsigned values. You can assume they can be stored in a 32 bit integer.

  When you process a label with this type, print the following:

  [ label = val, type = word, num bytes = 4, start addr = 100A ]
  100A: 23
  

  where val is replaced by the actual label, and 100A by the start address of the word (written using 4 hexadecimal digits). Note: this address must be word-aligned.

  On the second line, print the start address, followed by a colon, then a space, then the value in memory (in base 10 as a signed value).

  If the value was not specified (thus, left blank), then print:

  [ label = val, type = word, num bytes = 4, start addr = 100A ]
  100A: ?
  

  Put a question mark to indicate an unknown value is stored at the address.

  Here are some examples:

  val_1: word   10
  val_2: word -10
  val_3: 
    word 
  12
  val_4: word 
  val_5: word 0xFF
  val_6:  word    0x2
  val_7:   word 073
  

  You may assume valid values.

  However, for extra credit, handle invalid values.

• byte

  After the label and a colon, there is zero or more spaces (may include newlines), followed by byte, followed by one or more spaces (may include newlines), followed by a possible value.

  The value, if it exists, can be written as a character surrounded by single quotes (as in 't' or 'T'), or it can be a newline, written as '\n', or it can be written as octal (using a leading 0, followed by 3 octal digits), or it can be written in hexadecimal (using a leading 0x, followed by two hexadecimal digits), or it can be written in base 10 (where the value lies between 0 and 127).

  You may assume the values lie between 0 and 127 (the valid range of values for ASCII characters), and, other than the newline character and the null character, the characters are printable (can be seen on screen).

  When you process a label with this type, print the following:

  [ label = val, type = byte, num bytes = 1, start addr = 100A ]
  100A: 't'
  

  where val is replaced by the actual label, and 100A by the start address of the word (written using 4 hexadecimal digits). Note: this address can be any address. There are no restrictions on being word-aligned.

  On the second line, print the start address, followed by a colon, then a space, then the value in memory in single quotes. The exception is that a newline character should be printed as '\n' (a backslash, followed by an 'n').

  If the value was not specified (thus, left blank), then print:

  [ label = val, type = byte, num bytes = 1, start addr = 100A ]
  100A: ?
  

  Put a question mark to indicate an unknown value is stored at the address.

  Here are a few examples of different labels.

    byte_1: byte  'n'
  byte_2: byte  '\n'
  byte_3: byte  65
     byte_4:   byte  0x41
  byte_5:   byte  0101
  byte_6: 
  byte_7: 
    byte  0101
  

• word array

  Think of this as a way of storing values into an array.

  After the label and a colon, there is zero or more spaces (may include newlines), followed by word, followed by one or more spaces (may include newlines), followed by a left bracket, then a positive number, then a right bracket, followed by one or more spaces (may include newlines), followed by a possible value pattern.

  The value within the brackets is the size of the array. If a word array consists of n elements, it occupies 4n elements.

  A value pattern is one of the following:

  • A value (any valid value for a word)

    This is just a value.

  • A value followed immediately by a "*", followed immediately by a positive value (e.g., 10*3, -12*4).

    10*3 means that 10 is repeated 3 times.

  • A value followed immediately by a "**" (two stars).

    10** means that 10 is repeated until the array is filled

  There may be one or more value patterns, which are separated by blanks (possibly newlines).

  Let's consider an example:

  arr1: word [10]  3*5  -9*5
  arr2: word [10]  3*5  -9**
  arr3: word [10]  3*5  
  arr4: word [10]  
  

  arr1 declares memory for an array of 10 consecutive words. This array contains 3, 3, 3, 3, 3, -9, -9, -9, -9, -9. That is, it contains 3 repeated 5 times, followed by -9 repeated 5 times.

  arr2 declares memory for an array of 10 consecutive words. This array contains 3 repeated 5 times, followed by -9 repeated until the rest of the array is filled (9 times).

  arr3 declares memory for an array of 10 consecutive words. However, only the first five elements are filled (with the value 3), the rest are not filled.

  arr4 is uninitialized.

  Notes:

  • You may assume the size of the array is positive. Thus [-10] will not appear.
  • You may assume that the size of the array is in base 10.
  • The value before the * or ** can be base 10, hexadecimal, or octal (as shown earlier for word).
  • You may assume that if some value is followed by **, then that is the last value used.
  • You may assume that the total number of values is less than or equal to the size of the array.
  • The value/value patterns are separated by at least one blank, and may span more than one line (possibly even blank lines).
  • How can you tell when it ends? Three possibilities. First, you see a label (because it ends in a colon), which indicates a new label is declared. Second, you reach the end of file. Third, you see .text on its own line (which indicated that you are starting the text section of the input file).

  Extra Credit: Handle errors when too many values are used in a word array. You should print an error message, and ignore the additional values.

  Suppose you had the following label

  arr1: word [18] 10*5
     -3*5 21  23 
  

  Print the following:

  [ label = arr1, type = word array, num bytes = 72, start addr = 1008 ]
  1008: 10 10 10 10 10 -3 -3 -3 -3 -3 21 23 ? ? ? ?
  1018: ? ?
  

  The first line contains the name of the label, then its type, then the number of bytes (which is 4 times the size of the array), followed by the start address, written as a 4 digit hexadecimal address.

  Then, each line contains an address, followed by a colon, followed by up to 16 values. If an element of an array contains an unintialized value, you should print a "?". The value should be printed as base 10 values. There should be as many values as elements of the array. Thus, if the array has size 18, then it should contain 18 values. Some of those value may be unitialized (thus, a ?).

  You may assume each address takes 4 hex digits.

  word array must be word aligned. That is, the start address must start at an address divisible by 4.

• byte array

  Similar rules apply to byte arrays as word arrays. The differences are the following.

  • The value before the * or ** can be any value used for a byte.
  • The array does not need to be aligned.

  Suppose you had the following label

  arr1: byte [18] 'A'*5
     ' '*5 't'  '\n' 
  

  Print the following:

  [ label = arr1, type = word array, num bytes = 72, start addr = 1008 ]
  1008: 'A' 'A' 'A' 'A' 'A' _ _ _ _ _ t '\n' ? ? ? ?
  1018: ? ?
  

  All character should be printed in single quotes. The exception is space. Print an underscore instead of ' ' to make it a little easier to read. '\n' should be printed if it is encountered.

• string

  A string is the word string followed by a space, followed by double quoted string. You should handle \n, and \". There may be more than one double quoted string (this is when the string is too long). Here are some examples:

  str1: string "cat\n"
  str2:  string "dog" + "house"
    + " fun"
  

  All strings are initialized. The amount of memory taken is the size of the string (as if using strlen) plus one more for the null character.

  For example, if the input is:

  str1: string "cat\n"
  

  Then, print:

  [ label = str1, type = string, num bytes = 5, start addr = 100A ]
  100A: "cat\n"
  

  Note: "\n" takes up one memory location. Print the address of the first character of the string, then a colon, then the string in double quotes. If you have to concatenate two or more strings, then make it into one large string. You can assume the string can fit on one line, when printing.

Text Segment

After the data segment is the text segment. That part of the assembly language file begins with: .text This appears on a line and may have leading or trailing white space. This indicates the first line of the assembly language program.

Each line of text consists of

• a blank line (consists of zero or more blanks/tabs, ending in a newline character).
• a label (similar to the label used in the data segment)
• an instruction
• a label, followed by an instruction

Each instruction lies on one line. Thus, for simplicity, instructions will never span more than one line of input.

You need to determine the following:

• the address of each instruction in memory
• how much to jump forward or backward on instructions that begin with: j, jal, beq, bne. These are essentially "goto" instructions that "jump" to a label.

Each instruction is word-aligned and takes up 4 bytes of memory. In general, you should only worry about lines with instructions when determining which address they are stored in.

Labels have the same address as the instruction immediately after it. It is possible to have several labels in a row as in:

label_1:
label_2:
label_3: add $r1, $r2, $r3

All three label are at the same address as the add instruction.

It is also possible that a label does not have an instruction following it. This only happens if the label is at the very end after the last instruction. In that case, the address of that label should be the address of the last instruction plus 4.

For the time being, don't worry about what each instruction actually does. All you need to worry about are instructions that start with j, jal, beq, bne and determine the location of the label in those instructions.

As you process labels or instructions containing labels, you should do the following:

1. Record the instruction in an array (or vector) of instructions.
2. If it's a label, record the address with the label.
3. If the label is within an instruction, determine whether you've seen the label yet (it may have come earlier). If not, wait until later when you've seen the label, and fix that instruction.

It's a good idea to save the instructions in some format (perhaps make an Instruction class).

Task

For instructions that are branch/jump instructions, add a comment to the end that says

• # jump +N

  # is similar to // in assembly language. It is a comment to the end of the line. jump +N should have N replaced by the number of instructions to jump forward to reach the label. The calculation for this will be shown later.

• # jump -N

  This means to jump backwards N instruction to reach a label

You can assume that the label exists. However, for extra credit, you can indicate there's an error when the label does not exist. This will be discussed later on.

Computing Jump/Branch Instructions

Consider the following instructions:

foo:  add $r1, $r1, $r2
      add $r1, $r1, $r2

      beq $r1, $r2, foo   # jump -3
      jal bar             # jump +1
      add $r1, $r1, $r2
bar:  
      j foo               # jump -6

Let's label each instruction starting at 1. Since there are 6 instructions, the instruction are numbered from 1 to 6.

To determine the jump, find out the instruction of the jump/branch instruction. For example, jal bar is instruction 4. Add 1 to this to get 5. (The computation of the jump is relative to the next instruction).

Find the instruction of the label. In this case, bar is at instruction 6. So, 6 - 5 = 1, so jump +1.

It may seem odd to compute the jump from the next instruction, but there's a reason, which we'll discuss in later project.

Command Line Arguments

Normally, when you run an executable, you run it like:

  p0

or like

  p0 < primary.in

However, you can have arguments to the executable. These are called command line arguments.

  p0 -d 1000 -t 2000 -f in.file

where -d, -t, and -f are called switches or options. Each of these options have a single argument after it.

• -d

  This is the address where you should begin laying out data. You should attempt to place the first label at the address specified by the argument. The address is given in base 10 or hexadecimal (in which case, it starts with 0x).

• -t

  This is the address where you should begin laying out text (the assembly language code). You should attempt to place the first instruction at the address specified by the argument. The address is given in base 10 or hexadecimal (in which case, it starts with 0x).

• -f

  This is the name of the file to open. Assume it's in the current directory.

  The options can be written in any order. Thus, -d, -t, -f are in any order. Either all options are listed, or none are. There won't be any test inputs with two options, but not the third.

How to read command line arguments

If you are programming in C/C++, the command line arguments are read in by modifying main() as follows:

int main( int argc, char *argv[] )

where argc counts the number of arguments and the command itself. So, p0 -d 1000 -t 2000 -f in.file would have argc = 7. argc stands for "argument count". It uses white space to determine how to split the line apart (but groups things in quotes as one argument).

argv is an array of char * (i.e. C-style) strings. The array's size is one larger than argc. For example argv[ 0 ] == "p0", argv[ 1 ] == "-d", argc[ 2 ] == "1000", and so forth. argv[ 7 ] == NULL.

Notice argv[ 0 ] is the name of the executable. Also notice that all commands are C-style strings. Thus "1000" is a C-style string, not an int.

In Java, command line arguments are read in as:

public static void main( String args[] )

where the arguments begin at the actual argument and NOT at the name of the command. Thus, java Foo -d 1000 -t 2000 -f in.file starts the arguments at -d, NOT at Foo.

Removing Comments

You should be able to remove comments. To do so, you should read in one line of text, search for the first occurrence of "#", and find a substring from the beginnning of the line up to but not including "#".

Comments can appear at the end of the line or on its own line.

Example

To make it easier to follow what's going on, let's look at an example.

Suppose the user types in:

p1 -d 999 -t 2001 -f sample.asm < primary.in

What does this mean?

• The data segment should begin at address 999 (in base 10) (this is the -d option)
• The text segment should begin at address 2001 (in base 10). (this is the -t option)
• The assembly language file is "sample.asm" (this is the -f option)
• The command file is redirected in from primary.in. This is input redirected.

Here's a sample assembly language file:

  .data

val:  word -12
arr:  byte [7] 
arr2: word [10] 9**
char: byte '\n'

  .text

BAR:  add $r1, $r2, $r3
      j FOO
      add $r1, $r2, $r3
      jal END
FOO:  add $r1, $r2, $r3
      beq $r1, $r2, BAR
END:   

The file consists of the data segment, then the text segment.

Let's go through the steps to see what to do.

1. First, you recognize find .data and begin to process the data segment.
2. You know the start address for the data segment is 999₁₀ based on the command line argument.
3. You see the label val. It is a word so it must be word-aligned, which means that val must be stored at the next higer address that is divisible by 4. That is address 1000₁₀ (which you need to convert to hexadecimal).

   val takes up 4 consecutive bytes. You print out the appropriate message.

4. Now, you handle arr. This is a byte array. It takes up 7 bytes, and does not have to be word-aligned. So, 1004₁₀ is the first location after word. You can place the byte array there. It occupies address 1004₁₀ through 1010₁₀ (inclusive).

5. Now, you handle arr2. This is a word array. It needs to be word-aligned. 1010₁₀ is not word-aligned (not evenly divisible by 4). So, pick the next available address that's word-aligned: 1012₁₀.

   The array is 10 words long, so that uses 40 bytes. Thus, addresses 1012₁₀ up to 1051₁₀, inclusive.

6. Finally, handle char, which is a single byte. This can go at address 1012.

Note: for simplicity, you don't go back to empty gaps that weren't assigned, (for example, char is not placed at address 999, which wasn't used). You just proceed to the next unused spot in memory.

At this point, you see .text and know it's time to begin processing the assembly language code. This part should be easier.

In particular,

• As you encounter each label that ends in a colon, record the address with that label in some fashion (e.g., using an STL map).
• Record each instruction in some data structure (e.g., using STL vector) or even a simple array.
• Go back through the instructions and figure out which addresses the jump/branch are going to and record the relative jump.
• Print out the information

Instructions need to be word aligned, so they should start at addresses divisible by 4. Since the address starts at 2001, you need to begin the code at 2004 which is divisible by 4.

Which Language?

I would prefer that you choose between C, C++, or Java. If you want to pick any other language, please seek prior approval. In particular, the language should support bitwise operations and arrays, or you should be able to simulate them in some fashion.

What's this for?

In this project, the code isn't run, and it isn't even necessary to store the data in memory locations (they can be processed just enough to print it, and then you can discard them). The goal is merely to determine where to place the data/code once it comes time to do so.

Think of it like planning a wedding banquet. You are trying to figure out which seats each guest should sit (determining who sits near the front, who sits at which table). You're not actually placing the guests there until they arrive. All you're doing is planning it.

Similarly, this project is about planning where to put the data and code in memory.

Commands

In this project, there are two commands.

• quit

  Causes program to quit.

• load -d 1000 -t 2000 -f file.asm

  where the arguments must be specified. Again, -d, -t, and -f can be any order, and the addresses can be specified in base 10 or hexadecimal.

After each command, print:

===> (1) You entered: [quit]
   Exiting program.

or

===> (1) You entered: [load -d 1000 -t 2000 -f file.asm]

The output for load is described below.

Notes on Commands

• You should be able to handle upper or lowercase on the commands. However, you can assume the options are written in lowercase.

• The commands fit on one line
• There may be blank lines.
• You should not process additional commands after quit, even if it exists.
• There will always be a quit command.

In the next project, there will be commands to determine the content of memory, registers, etc.

Output for "load"

Coming soon

Web Accessibility