Goals

These are the lessons to learn from this part of the project:

• To understand how to read information in binary format. This is a combination of reading ASCII, and reading numbers stored in binary format.
• How to read binary files.
• Understand basics of a disassembler.

Some of the skills used in the hex dump utility also apply to the this part of the project. This should make this part of the project somewhat easier.

Clarifications and Such

If there are errors and ambiguities, please send email to clin@umd5.umd.edu. I will be checking this description during weekend starting Feb 22., possibly adding corrections if needed.

Background

An assembler is a program that translates programs written in assembly language into machine code. Machine code is essentially the binary equivalent of the assembly language. As assembler behaves functionally like a compiler. That is, its purpose is to convert from one language to another.

However, there's almost a 1-1 correspondence between assembly language programs (at least, the text portion). That means, there's not that much translation to do to get from assembly lanugage to machine code (it's tedious, but not particularly hard).

Assembly language was developed when the first programmers, who wrote their code in machine code, found it too error-prone and slow. So, they wrote "human-readable" code, and then wrote a program (i.e., the assembler) to convert it to machine code.

A disassembler works in reverse. It takes machine code and produces the equivalent assembly language program. At times, the machine code may not have all the information that the assembly language program contains.

In particular, comments are typically removed, and labels may also be removed. We'll explain what label are in the next section.

Structure of MIPS program

A typical assembly language program consists of two parts: the data segment and the text segment. Think of the data segment as a kind of global variable declaration and initialization. This part of the program is not always standardized, and varies from assembler to assembler.

The text segment is the "code" portion, where you write out the instructions to perform a task.

The basic structure of a program looks like:

  .data  # This is a comment
# DATA STUFF GOES HERE

  .text
# PROGRAM GOES HERE

Comments are shown with a #, which behaves like // in C++. Comments are ignored by the assembler.

Assembly lanugage is very line-oriented. In C, each statement usually ends in a semicolon. In assembly language, most statements must appear on a single line.

The keyword .data begins the data segment, and the keyword .text begins the text segment. Each appears in its own line.

All you have to do is write the disassembler for the data segment. I'll be making up the format for the data segment. It will resemble the format given in SPIM (the MIPS simulator, described at the end of your book), but it's not exactly the same. The data segment tends to vary from assembler to assembler.

The specs for the data segment are shown in the next section.

Specifications

Here's the overall picture. I'm describing the data segment of an assembly language program. Then, I'll describe how this segment is encoded to a binary file. You will use the input file, and

I'm doing to define a term called a declaration.

A declaration is going to consist of:

• a label

  Valid C identifiers are also valid identifiers. A valid C identifier are valid names for variables, classes, functions, etc. in C. Those start with an alphabetic character or underscore, followed by zero or more characters from: alphabetic character, underscore, or digits.

  You won't have to check for the validity of the identifiers. You can assume they are "correct". Of course, if you would prefer to check the validity, that's fine too. You can reject programs that don't have valid identifiers.

  Labels appears at the beginning of lines, possibly preceded by one or more blanks.

  We'll assume the labels are case-sensitive.

  Are labels variable names? Not entirely. Think of labels as addresses where data are stored. The reason for thinking of it like this is because labels can also be used with the text segment, too, where they refer to addresses of instructions.

• a colon

  The colon appears immediately after the label. In fact, that's how you're going to tell it's a label. If a label doesn't have a colon, then it's not a label.

• a type

  Assembly language programs support very few types. In particular, you can't create user-defined types (i.e., you can't create structures, classes, etc).

  This is one of the things that makes programs hard to write. It's not that you can't create structures, but that it has to be done in a roundabout way. That is, you have to create large byte arrays, and mentally break it up yourself.

  The valid types we'll support are:

  • int which is a signed int 32 bit value
  • unsigned which is a unsigned int 32 bit value
  • byte which is an 8 bit value (consider it unsigned)
  • ascii which is a string that DOESN'T end in null character
  • asciiz which is a string that DOES end in null character

  The types are case-insensitive. That is, a person can write out int using any combination of upper and lowercase letters.

  The type follows the colon with 0 or more spaces, or could even appear on the bext lines (i.e., after 0 or more blank lines). Most people put the type near the label to make it easier to read.

• an array size

  This is optional, and only appears for types; int, unsigned, and byte. We'll exclude arrays of strings.

  An array size is mostly a convenience to allow you to have many int's or many unsigned, etc.

  The syntax is a left bracket, followed by a positive value, followed by a right bracket, with no spaces between the brackets. This should make it easier to parse.

  This can follow 0 or more spaces after the type, though typically, we'll place with 1 space after the type.

• the data values

  The syntax for the data value depends on the type.

  • int For int values, it will be 1 or more digits, possibly preceded by a negative sign, written in base 10. (Additionally, you could allow someone to write in octal and hexadecimal with a leading 0 (for octal) or 0x, 0X (for hexadecimal)---they could also be preceded by a minus sign).

  • unsigned For int values, it will be 1 or more digits, written in base 10. (Additionally, you could allow someone to write in octal and hexadecimal with a leading 0, 0x, 0X).

  • byte Bytes are written with a leading 0x or 0X in hexadecimal. You can assume there are two digits after the 0x or 0X.

  • ascii is written with a double quote followed by zer oor more characters followed by a close double quote. To handle unusual characters, you need to use backslash. These are so-called escape sequences. For example, \n, \t, \", and \\. There are others, but that's as much as you need to handle.

    The trick is to replace \n with the ASCII code for newline (even though the text file appears as two separate characters, the backslash, and the character n, this is replaced with a single ASCII code for newline). The same applies to the tab.

    The double quotes is a little easier, because you simply ignore the backslash. Same goes with a \\. It's replaced by a single \. The behavior should be the same as it is in C (which is the same as in C++).

    This brings up another point. The second double quotes must not be preceded by a backslash. Most of the times a double quote either starts a string or ends a string. The character has a special significance. However, sometimes you want really want a true double quote to appear in a string. That's when you preceed it by a backslash. In that case, the escaped double quote does not signify the end of a string. It is to be treated as a real double quote.

    You can assume the both pairs of double quotes appear on the same line.

    However, if you want, you can try to handle backslash followed by a true newline character--this is one way that C allows for string that are too lengthy. The other way that C handles long strings is to consider all consecutive strings to be concatenated.

    For example, if you see "cat" and "dog" near each other (could be on the same line or, say, two consecutive lines), then they two are concatenated to "catdog".

    Adding this feature (i.e. "long" strings) is optional.

  • asciiz This has the same syntax as ascii. The only difference is that it's saved in memory differently. ascii does not end in a null character (it may have one or more null characters throughout the string--you don't have to handle this case, but if you do, use '\0' in ascii to represent the null character. Null characters will not appear in asciiz except at the end of the string.). asciiz only has a single null character, which appears at the end. However, both ascii and asciiz strings appear visually the same in the assembly file (except that null characters do not appear in asciiz within the double quotes).

  In an array situation, values are separated by at least one blank space. Values can continue onto the next line as well. There may even be blank lines. You can assume the number of values that appear is less than or equal to the array size.

  If the number of values is less than the array size, the remaining values are filled with 0. Since strings don't occur in array contexts, the user must write a string.

  For a shortcut, multiple values can be typed using a multiply sign. For example, 3*4, means to write the value 3, four times. It's equivalent to writing: 3 3 3 3.

Here are some examples:

num1: int 3
num2: int -3
num3:
  int
 4
arr1: int [5] 3 3 3 -2 -2
arr2: int [5] 3*1 -2*4
arr3: unsigned [5] 3
arr4: unsigned [5] 4*2
b1: byte 0x41
b2: byte 0X41
barr: byte [3] 0x11 0x11 0x11
str: ascii "Hi there"
str2: asciiz "Hi there\n"

The description above may seem unusual. After all, it describes an assembler. You're writing a disassember.

Still, it's useful to have this information, because you need to know the syntax for a program because that's the output of your program.

Now to get to storing this information. The binary file contains the following:

• a magic number

  a "magic number" refers to special string at the beginning of a file to indiciate the kind of file it is. It's called "magic" mostly because there's nothing too special about why that particular value was picked. It just is.

  The magic number we'll use is 0xcafedabe. Be careful. This is a 32 bit value, not 10 ASCII characters. When you read in magic number, you have to check if it has the same endianness as your machine. The way you do that is to read in the magic number into an unsigned int. If that unsigned int is equal to 0xcafedabe, then the file is stored in the same endianness as your machine.

  If the value is 0xbedafeca, then it's the opposite endianness from your machine. In that case, any int value you read in, needs to be "reversed" so you have the correct value.

  If the value isn't either, then you have an invalid file. You can print that it is invalid, if you want, then quit.

• a number of declarations

  This will be stored as an unsigned int using 2 bytes. Again, you need to take into account the endian-ness of the magic number, to determine whether the bytes may have to be reversed.

• the declarations

  We'll describe the syntax of the declarations below.

Syntax of declarations

Each declaration consists of a label, a type, possibly followed by the size of an array (if it's an array), followed by a list of representations. The number of representations will equal the size of the array.

Let's be more specific. Each declaration will have the following information in the binary file. The list of

• The label consists of ASCII characters, ending in a null character. You can, if you want, assume that total length of the label is no longer than 80 characters (which would be quite long), NOT including the NULL terminator.

• The type of the label is stored in one byte. Use the following chart to determine what type you have.

  Bit Pattern (in hex)	Type
  0x01	int
  0x02	unsigned
  0x04	byte
  0x08	ascii
  0x10	asciiz

  If it's an array, then the most significant bit is set to 1, in addition to the bit above being set.

• If the type is an array, then a single byte is used to represent the array. This byte is an unsigned int. Add 1 to the value of this byte (thus, the valid size of an array is from 1-256, rather than 0-255).

  This is, of course, quite small for an array. But for this project, it's fine.

  If the type is NOT an array, then this byte does not exist.

• After the byte, is a list of representations. (see notes on Representations vs. Values, to be posted) of the values in the array. If it's an int or unsigned, each representation uses 4 bytes. There will be as many representations as elements in the array (clearly, this doesn't do much compression, but that's OK for this case). Again, the endian-ness of the values will match the endian-ness of the magic number.

  (2/23) If it's byte, it's straightforward to store a byte (use a char). If it's asciiz, then store the string with the null terminator at the end (endian-ness isn't a factor for strings). If it's ascii, then store a 2 byte size field (represented as an unsigned int), followed by that many ASCII characters. You have to worry about the endian-ness of the size field. Thus, if you have the word "cat" (without the null terminator), you would store 3, in binary, using 2 bytes unsigned, in the appropriate endianness, followed by the ASCII code for 'c', 'a', and 't'.

  Note: only ascii stores the size field. The size for asciiz can be determined by looping until you find the NULL terminator (which has ASCII value 0).

Each declaration (i.e., each label and associated information) will have the information above, concatenated one right after another. This is why it's important to know the number of declarations.

Also, note that we store the labels in the file itself. In general, this may not be necessary. Labels often refer to addresses, and therefore once the address is computed by the assembler, the labels are sometimes not necessary.

Typically, labels for function names are needed, especially for linking. But other labels may not be needed.

However, in our project, we record all the label information in the output.

Coding Strategy

I would consider creating a structure or class that stores the information of each declaration (i.e., the label, the type, and the information). Then store this in, say, a vector or an array of such structures.

This information can be used later on, if necessary.

Sometimes it's a good idea to have a structure/class to store the information, rather than processing it on the fly, and throwing away the information once it's done.

There is clearly a tradeoff. If you process the information as you read it, then you need less space to store the informmation. On the other hand, storing the information allows you to use the information later on.

Outputting Information

Assume the name of the executable is: disassem.

You should allow for two command line switches:

• -i <filename> for an input file. If entire option is missing, it should expect input from standard input.
• -o <filename> for where to write an output file. If entire option is missing, it should expect print to standard output.

You should expect the switches to appear in any order. You may assume input file exists and output file do not.

If there is no command-line argument, write the data portion of the file to standard output.

This is what you should output:

• A comment block at the top. It should look like:

  # -----------------------------
  #   Disassembler
  #     written by: <your-name>
  #      login IDs: <your-login-id>
  #        Section: <your-section>
  #   
  #   Input file name:    <file-name>
  #   Output file name:   <file-name>
  #   Machine-endianness: <endianness>
  #   File-endianness:    <endianness>
  # -----------------------------
  
     .data
   DATA SEGMENT GOES HERE 
  

  where you should put your name (and partner's name, if you have one), and login ID(s), and section number(s).

  The input file name should be the one provided by -i switch, or "standard input", if the -i option does NOT appear.

  The output file name should be the one provided by -o switch, or "standard output", if the -o option does NOT appear.

  You should print "little endian" or "big endian" as appropriate for the <endianness>.

• Print each label at the beginning of a line, followed immediate by a colon, then a space, then the type, then if it's an array, print a space, a left bracket, the size of the array, and a right bracket, then a space.

• When you print the represented values in an array, you need to keep track of repeated represented values. If a represented value repeats, you should print it with a "repeat/multiplication" sign. For example, if you have 3 3 3 3, you should instead print 3*4.

  You should separate the represented values by a single space.

• Put no more than 10 represented value per line (3*4 can be considered a represented value). Continue the values on the next lines, but for each subsequent line, indent in about 5-10 spaces, so that it doesn't line up with the label.

What's a Binary File?

Technically, all files are binary files. They contain bytes of information. However, usually there's a distinction made between text files, which are human readable, and binary files which are often NOT human readable.

Thus, foo.cpp is considered a text or ASCII file, because you enter text in a text editor (in the future, perhaps they will be Unicode files). foo.o is considered a binary file because it's not human-readable (for the most part).

Binary files are often used because they represent information more compactly, and also because they are not human readable (many software products that you may purchase do not provide source code, but only provide binaries).

Since ASCII files are still, technically, binary files, you can run the hex dump utility on them and read them.

Extra Credit

Here are a list of extra credit options. This part of the project is worth 100 points (note: total project points may not add up to 100, but will be scaled to 100 points later on).

• Add error-handling features to the executable. If the user has incorrect syntax (wrong number of arguments), print a "usage" error message and quit.
• Handle output file option more robustly. If the user uses -o option, but no output file name, then if -i is not specified, then write the output to a file called out.asm. If the input file name is specified, then write it to the input file name, with a .asm extesion. For example, if the input file is foo, the output file should be foo.asm.

  However, if the input file has a .bin extension, then the output file should replace .bin with .asm extension. For example, if the input file is foo.bin, the output file should be foo.asm.

  The extra credit for doing this and the previous is worth 10 points.

• Write an assembler for the data portion. Ideally, the assembler would encode what you produced as output back into the same file that was produced. Call the executable assem. It should support options to control the endianness. -endian same and -endian reverse.

  It should be robust enough to handle all sorts of valid data portions. without core dumping.

  Extra credit: 75 points.

  There will be an optional project that includes doing the assembly language portion as well, to be posted at some point.

See the class syllabus for policies concerning email Last Modified: Fri Feb 14 09:13:38 EST 2003

Web Accessibility