|
|
c m s c 311
s p r i n g 2 0 0 2 |
Exam Solutions
|
|
|
|
| Exam 1 Solutions | [Postscript] [Solutions] | November 4 |
| Exam 2 Solutions | [Solutions]||
| Summer 2002 Final | NOT POSTED YET |
|
|
c m s c 311
f a l l 2 0 0 2 |
 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Announcements
Exam 2 is Monday, December 9, in CSIC 3117 (classroom) from 5:00-6:15. Closed book, closed notes, closed neighbor exam. Final Exam Information
Final is Tuesday, December 17, in CSIC 3117
(classroom) from 4:00-6:00. Closed book, closed notes, closed neighbor
exam.
If you have a D/F (based on exams), I will submit them after your project grades are computed. However, if you receive an F, project grades may only help you to a D (I think I wrote that in the syllabus somewhere). I will try to get some work done through a bad Internet connection, but will be back in early January to finish the project grades. Note: accounts will disappear by December 30. If you need to save stuff, you should do so before then.
BTW, I haven't been reading email lately.
For a variety of reasons, the current project is now OPTIONAL. In particular, I had to correct the primary output for the last line (I had digits transposed on the "ori" instruction). To compute your final grades, I will total the score from the first 3 projects (0, 1, and 2) and give a grade to the entire class (i.e., A, B, C). This will count 20% to your final grade. Note: doing P2 then helps because it adds more points to your project total (I will accepts P2 up to Friday of exam week). I will also compute your final grades due to exams only. I will take the higher of the grades computed by exams only and by exams plus projects. As long as you submitted P0 and P1, then I take the better of the two grades. However, if you do abysmal on exams only (i.e, get an F average), I reserve the right not to pass. I primarily want students who are just under the C cutoff to move up. If you really need the final exam grade, I would suggest studying for your finals, and trying the projects after the fact.
I should be in AVW 1151 around 1 PM on Saturday and Sunday. On Saturday, I will answer questions about the projects. On Sunday, I will answer questions about the final exam.
I should be in AVW 1152 Sunday at 2 PM, if you have questions
I hope to have primaries up Saturday too. Check announcements later this evening for more info.
Also, you should have bit 0 be the least significant bit, and bit 31 (or whatever the size) be the most significant bit. Bits in registers are numbered right to left, not left to right.
As announced in class, this means the project has 4 more days to be submitted, so you can turn it in by Thursday midnight for regular credit. Yes, I know that there is a 330 project due at the same time. However, this project has been out for at least a month. The ability to do projects without primary inputs and outputs is something you will need for 400-level courses (you can ask questions such as "if this is the input, is this the corresponding output?).
I plan to add one additional function to Convert. which will read in a series of 32 bit values from a binary file, with a given endian-ness. That should be up fairly soon. At this point, barring any inspirations, that should be it for P1.
I will work on a Register class (for C++/Java) and try to have that ready tomorrow. Send email if you see anything that seems odd.
However, expect that there may be a few tiny problems, so read FAQ, etc. regularly. You have two weekends to work on this. It's not all that bad though.
~chf11001/submit p0.tar 0Include a README file. Read HOW_TO_SUBMIT from the posting account: ~chf11001/Proj/P0/
As an additional extra credit, I would like getRightToken() to behave differently. It should look for the first real delimiter from the right, but NOT trim the spaces. Thus, if the string were "***cat***,***dog**", then the rightmost token would be "***dog**", and the rest of the string would be "***cat***". See FAQ.
NOTE: Only the latest submission counts. If you turn in an early and an ontime, then only the ontime will be graded. NOTE: The late policy is pretty generous. Up to 7 days late, at 2 points off a day.
Read about extra credit in project FAQ.
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
c m s c 311
f a l l 2 0 0 2 |
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Announcements
Exam 2 is Monday, December 9, in CSIC 3117 (classroom) from 5:00-6:15. Closed book, closed notes, closed neighbor exam. Final Exam Information
Final is Tuesday, December 17, in CSIC 3117
(classroom) from 4:00-6:00. Closed book, closed notes, closed neighbor
exam.
If you have a D/F (based on exams), I will submit them after your project grades are computed. However, if you receive an F, project grades may only help you to a D (I think I wrote that in the syllabus somewhere). I will try to get some work done through a bad Internet connection, but will be back in early January to finish the project grades. Note: accounts will disappear by December 30. If you need to save stuff, you should do so before then.
BTW, I haven't been reading email lately.
For a variety of reasons, the current project is now OPTIONAL. In particular, I had to correct the primary output for the last line (I had digits transposed on the "ori" instruction). To compute your final grades, I will total the score from the first 3 projects (0, 1, and 2) and give a grade to the entire class (i.e., A, B, C). This will count 20% to your final grade. Note: doing P2 then helps because it adds more points to your project total (I will accepts P2 up to Friday of exam week). I will also compute your final grades due to exams only. I will take the higher of the grades computed by exams only and by exams plus projects. As long as you submitted P0 and P1, then I take the better of the two grades. However, if you do abysmal on exams only (i.e, get an F average), I reserve the right not to pass. I primarily want students who are just under the C cutoff to move up. If you really need the final exam grade, I would suggest studying for your finals, and trying the projects after the fact.
I should be in AVW 1151 around 1 PM on Saturday and Sunday. On Saturday, I will answer questions about the projects. On Sunday, I will answer questions about the final exam.
I should be in AVW 1152 Sunday at 2 PM, if you have questions
I hope to have primaries up Saturday too. Check announcements later this evening for more info.
Also, you should have bit 0 be the least significant bit, and bit 31 (or whatever the size) be the most significant bit. Bits in registers are numbered right to left, not left to right.
As announced in class, this means the project has 4 more days to be submitted, so you can turn it in by Thursday midnight for regular credit. Yes, I know that there is a 330 project due at the same time. However, this project has been out for at least a month. The ability to do projects without primary inputs and outputs is something you will need for 400-level courses (you can ask questions such as "if this is the input, is this the corresponding output?).
I plan to add one additional function to Convert. which will read in a series of 32 bit values from a binary file, with a given endian-ness. That should be up fairly soon. At this point, barring any inspirations, that should be it for P1.
I will work on a Register class (for C++/Java) and try to have that ready tomorrow. Send email if you see anything that seems odd.
However, expect that there may be a few tiny problems, so read FAQ, etc. regularly. You have two weekends to work on this. It's not all that bad though.
~chf11001/submit p0.tar 0Include a README file. Read HOW_TO_SUBMIT from the posting account: ~chf11001/Proj/P0/
As an additional extra credit, I would like getRightToken() to behave differently. It should look for the first real delimiter from the right, but NOT trim the spaces. Thus, if the string were "***cat***,***dog**", then the rightmost token would be "***dog**", and the rest of the string would be "***cat***". See FAQ.
NOTE: Only the latest submission counts. If you turn in an early and an ontime, then only the ontime will be graded. NOTE: The late policy is pretty generous. Up to 7 days late, at 2 points off a day.
Read about extra credit in project FAQ.
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
c m s c 311
f a l l 2 0 0 2 |
Due Wednesday, Sept. 18, 11:59 PM (just before midnight)
Late Due Date Wednesday, Sept. 25, 11:59 PM (just before midnight)
Posted: September 6, 2002
Addendum
Read this section frequently to check for updates/corrections/clarifications to the projects. There will be some, because the project description is rather rough right now. However, the methods should be more or less correct.
- FAQ (9/15/02)
- Clarifications to P0 (9/12/02)
-
Purpose
-
The goals of the project are:
- Change finger information
- Write a (ad-hoc) tokenizer in C++.
-
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
-
Collaboration Policy
-
Should colloboration be permitted, you will need to pick a partner
(groups of 2) or partners (3 or more), depending on the restrictions
of each individual project.
Only one person should submit the project, and have all the names on it. Suppose a project allows teams of 2. The two people can work together on a team, and code on the same project. However, teams are expected not to communicate with other teams. Thus, you should treat each team like an "individual" when it comes with helping other teams.
-
Collaboration on P0
-
You may work in teams of 2. You should inform the instructor
and/or TA who your team members are, and do so in writing, with
both the members having signed a paper. The paper should
say "For project 0, xxx and yyy will work on the same team.
We understand that working with other teams is a violation
of academic integrity."
The project is sufficiently short to be done individually. So, you do not have to work in teams.
Should you work in teams, you should try pair programming. In this case, both of you agree to code side-by-side. One person types, the other person looks it over. After a while, you switch off. By discussing what you will do, you will avoid bugs, and hopefully code quicker.
-
Project 0?
- Why is this called Project 0 instead of Project 1? Traditionally, at Maryland, Project 0 is a simple project meant to get you started. Usually Project 1 is more typical of a project in terms of size and complexity.
-
dce_login: Changing Password/Shells
-
In order to change shells or passwords or finger information,
you must authenticate yourself. If you use "telnet", this isn't
all that important, since it doesn't care. However, using "ssh"
requires authentication, otherwise changing your password,
finger information or default shell fails.
To do this:
- Log into your account using ssh (secure shell).
- Type: dce_login, and hit return
- This will ask for some "Principal" name. Type in your username again.
- Then, it asks for the password. Type in your password again.
- This appears to start a new shell. You can then change your password by typing passwd (NOT password), hitting return, and changing the password.
- Once you are done, type exit. This exits out of the shell, and back into the previous shell.
- Then, type logout to exit your ssh session.
-
Changing Finger Information
-
You should change your finger information. If you use
ssh to login, you must login a second time using
dce_login (it will request your username and password
a second time, and open a new shell). If you use telnet,
you do NOT need to dce_login.
To change your finger information, type:
chfn
You should ONLY change your name. Please have your first and last name as you are registered in the system. For example, if you are registered as "Samir Khuller", please use "Samir Khuller" rather than "Sammy Khuller" or "Biff Khuller", even if you prefer to be called "Biff".Ignore the parts that ask you for your phone number, office, etc. Just hit return, and don't fill anything in.
In addition, you will probably also want to change your password.
passwd
Notice the unusual spelling of "passwd".This will ask for your original password, then your new password, and the new password again. If you use "ssh", it may take a day or so to take effect (it might work right away though). If you use "telnet", the changes should be immediate.
-
Specifications
-
You will be given a file called Tokenizer.h. The
specifications are in the following link.
Tokenizer Specification
Implement the methods. You may add helper methods, if you want.
-
Assumptions
-
You may assume
- Single quotes come in pairs. Double quotes come in pairs.
- No tabs will appear in the input.
-
Restrictions
-
Restrictions.
- You should write the program in C++.
- You must translate \n to the newline character. It will be read in as two characters--a backslash and a newline. This should be converted to a newline character.
You may use STL or any other features you want, provided it compiles and runs under either cxx or g++. A driver will be provided, so you can submit.
-
How to Submit
- A driver will be provided soon to partly test your code. Details will be provided soon.
|
See the class syllabus for policies concerning email Last Modified: Wed Jun 5 10:38:37 EDT 2002 |
|
|
|
|
|
|
|
c m s c 311
f a l l 2 0 0 2 |
Purpose
The overall goal of the project is to write an assembly language interpreter. Thus, it may seem odd to start off with a parsing/tokenizing project.There are two reasons for giving this project. First, I think tokenizing is a useful skill everyone should have. Breaking up a line is just something that you tend to do when working with text.
Second, the rest of the projects require you to manipulate text. Many students probably used all sorts of "cin" tricks to read the input in, and ended up with code that was difficult to read, write, and to fix up.
The idea of these methods is to emulate features of the StringTokenizer in Java. Of course, this isn't the same thing, but it's close enough.
To process a file, you will read in a line at a time, then break the line up using the methods below into tokens. At that point, you will process the tokens.
Location of File
Go to ~chf11001/Proj/P0/, and there should be two files. Use Tokenizer.h and create Tokenizer.cpp.
| Tokenizer |
Static Public Methods
| static string leftTrim( const string & str ) ; |
| Given parameter str, removes any leading blank spaces. For example, if str is " hello, world ", then the string returned should be "hello, world ". Only the leading spaces have been removed. The remaining spaces are unchanged. If there are no leading spaces, just return the string as is (an empty string falls into this category). |
| static string rightTrim( const string & str ) ; |
| Given parameter str, removes any trailing blank spaces. For example, if str is " hello, world ", then the string returned should be " hello, world". Only the trailing spaces have been removed. The remaining spaces are unchanged. If there are no trailing spaces, just return the string as is (an empty string falls into this category). |
| static string trim( const string & str ) ; |
|
Given parameter str, removes any leading AND trailing blank spaces.
For example, if str is " hello, world ", then the
string returned should be "hello, world". Only the leading and trailing
spaces have been removed. The remaining spaces are unchanged.
If there are no trailing spaces, just return the string as is
(an empty string falls into this category).
Use leftTrim and rightTrim to implement this static method. |
| static bool isBlankLine( const std::string & str ) ; |
| Returns true is the line consists of zero or more blanks. Returns false if there is a non-blank character. |
| static std::string stripComment( const std::string & str, const std::string & commentStr ) ; |
|
Finds the leftmost occurrence of commentStr (that's not surrounded
by single or double quotes). Removes the commentStr to
end of string. For example, if the string were "add $r1, $r2, $r3 # adds",
and the comment string were "#", then the retuen value would be:
"add $r1, $r2, $r3 ".
If there is no comment string, just return the string itself. |
| static string getLeftToken( string & str, const string & delimiter ) ; |
|
A delimiter is a separator. Often spaces are used to
separate words. Sometimes commas are used. You might have
colons, slashes, etc. I will also assume you might use
more than one character as a delimiter. For example, you might
use double colons.
The behavior of this method depends on what the delimiter is. If the delimiter is a single space or multiple spaces, then you should get the leftmost token by:
For example, if you have " cat dog ", then once the call is made to getLeftToken(), you should return "cat", and str, the parameter will be " dog ". This behaves very much like "cin" when reading in a string. If the string is empty or contains only blanks, then return the empty string. If the delimiter is anything else, you should search for the first delimiter not enclosed in single or double quotes. You should read up to that delimiter and stop. Should the delimiter not exist, then just return the token. For example, suppose the delimiter is ",". You have " ok "one, two, three" , four". The left (first) token should be "ok "one, two, three" ", and str should be " four". The delimiter is not kept. Also, "escaped" delimiters don't count. For example, if you have the string "paper \, scissors, rock", then the first (left) token is "paper , scissors" and str is "rock". Notice that escaped delimiters are replaced by the actual delimiter. Backslashes can also be delimiters, which means they can also be escaped. |
| static string getRightToken( string & str, const string & delimiter ) ; |
| Similar to getLeftToken() except your get the token from the right side. Basically, process the string right to left, instead of left to right. |
| static int findRealDelimiter( const std::string & str, const std::string & delimiter ) ; |
| This is useful helper function. This returns the index of the first character of a delimiter that is not surrounded by single or double quotes. If there is no such delimiter, return -1. |
| static vector<string> split( const std::string & str, const std::string & delimiter, bool trimToken = true ) ; |
|
Calls firstToken() repeatedly to break a string into tokens.
As each token is pulled out, if trimToken is true, call
trim() on the token to remove leading and trailing blanks.
Be careful. If the string was "h,," you would have 3 tokens. "h", "", and "". For delimiters that are not blanks, the number of tokens should be one more than the number of "real" delimiters. |
| static std::string removeEnd( const std::string & str, char left, char right ) ; |
|
Suppose you had a string like " [ cat ]", and you want to remove
brackets. There may be leading or trailing spaces. So, specify
left as '[' and right as ']'. This returns back
" cat ".
More technically, it removes leading white space and left, should it exist. It removes trailing white space and right should it exist. Should left not exist, then this function does a left trim. Should the right one not exist, then it does a right trim (see the two methods above). Thus, if the string were " cat dog " and left and right were '[' and ']' respectively, then the result would be "cat dog". |
How to Call Static Methods
To call a static method, you need to specify the class, followed by the double colons, followed by the method name and any arguments.
Here's an example:
vector<string> tokens = Tokenizer::split( str ) ;
|
See the class syllabus for policies concerning email Last Modified: Wed Mar 13 20:20:09 EST 2002 |
|
|
|
|
|
|
|
c m s c 311
f a l l 2 0 0 2 |
Some clarifications based on things brought up in class. Plus other stuff...
- To make it easier to grade the projects, let's use
the same compiler. Use g++-3.2 with the -Wall
option. This compiler was just installed a few weeks ago,
and I want to see how it's doing.
This is one of the latest versions of g++, and it now enforces namespaces. If you need to read about that in the CMSC 214 Tutorial located here.
- You should match double quotes with the next occurring double quotes that is not backslashed.
- You should match single quotes with the next occurring single quotes that is not backslashed.
- Process the string left to right. If the first non-backslashed quote is a double quote, then you look for the next matching double quote.
- Do NOT strip off the double quotes, nor the single quotes during a getLeftToken() operation. (The reason is rather technical).
- Handle the following escape sequences: \n, \', \", \\. Also, handle backslash followed by the delimiter. Thus, if the delimiter is : then \: is not meant to be a real delimiter.
- You may assume ',",\n, \ are NOT delimiters (nor their backslashed version).
- Yes, you have to handle spaces as delimiters.
- You need to CONVERT \n to the actual newline character, \\ to a single backslash, \' to single quote, \" to double quote, and backslash followed by a delimiter to a delimiter.
- The easiest way to test for these strings is to create
a text file, and read in a line at a time.
Here's sample code for how to do this.
using namespace std ; int main() { string line ; while ( getline( cin, line ) ) { // split line based on some delimiter, then print out // each token on a separate line, surrounded by slashes. // For example, if the line contained "cat, dog , elk ", // print // (1) /cat/ // (2) /dog/ // (3) /elk/ } }That will give you some indication if your tokenizer is working. - Work on easy stuff first, then worry about complicated stuff later. You don't need to get EVERYTHING to work to submit (though certainly, you get more credit). If you worried about time, get the basics to work (such as splitting by spaces and commas, and handling \n).
|
See the class syllabus for policies concerning email Last Modified: Wed Jun 5 10:38:37 EDT 2002 |
|
|
|
|
|
|
|
c m s c 311
f a l l 2 0 0 2 |
- (9/19) Should I handle backslash followed by the delimiter?
Yes, basically, it should not be considered as a delimiter. It should be considered a literal string. Thus, if comma is a delimiter, then \, is an escaped delimiter. You should not consider it as a delimiter, and get rid of the comma.
When you get a token (using getLeftToken() or getRightToken()), you should take care of all backslashed (escaped) sequences. For all escaped sequences (except \n), you simply remove the backslash. For backslash followed by the character 'n' (which appears as \n, i.e. two separate characters), then replace that with a newline (a single character).
- (9/19) Even more extra credit?
Well, not exactly "more" (a little more perhaps). I noticed from the project description that getLeftToken() left trims the token. So, I am going to follow that. I think I did that to handle white space for space as delimiter.
However, make getRightToken() find the rightmost delimiter and NOT trim the white space.
Thus, if the string were "***cat***,***dog**", then the rightmost token would be "***dog**", and the rest of the string would be "***cat***" (without the comma).
- (9/19) Extra credit? What's that?
Yesterday, someone asked what we should do about escaped delimiters. Here is the part that's the usual stuff (i.e., not extra credit:
- If a backslash followed by an n appears (i.e., two separate characters in the string), replace that by a single newline.
- If \\, \', \" appear, replace that by \, ', and ", respectively.
- If a \ followed by a delimiter appears, then replace that by the delimiter.
You may assume backslashes do not appear for anything else. Thus, \a is not a valid substring, unless "a" is a delimiter.
Extra credit
Suppose you have :: as a delimiter (two colons). Then, you should be able to handle the following: \::: is considerd an escaped delimiter (thus not a true delimiter) followed by a colon. \:::: is treated as an escaped (non-true) delimiter followed by ::, which is a true delimiter.
\\\\\\ is really three escaped backslashes and gets translated to a three real backslashes.
Finally, findRealDelimiter, when looking for 1 or more blank spaces should return the index of the first non-quoted blank that appears after a string of non-blank characters. If such a blank does not appear, it returns -1. Thus, [***cat***], will return 6 (where * is being used to stand for blanks, to make it easier to see in this FAQ and brackets are used to show where the string starts and end, but is not part of the string itself).
If you have "***'cat**'*", then findRealDelimiter() returns 10 since it skips the first three blanks, ignores the item in single quotes, and finds the space at the end.
For any other delimiter, it just looks for the first non-quoted, non-escaped version of that delimiter. Only blanks used as delimiters have this weird feature.
- Is space as a delimiter handled in any unusual way?
Yes. Unfortunately, using space (blank, not TAB or newlines) as a delimiter has to be handled differently. Otherwise, it makes split() awkward to use. If " " is a delimiter, then getLeftToken() should skip over any blank spaces, then over any non-blank spaces, and stop at the next blank space, or the end of string, whichever comes first.
Thus, if the string were "****cat***in*the*hat" where * represents a blank, then, the first token is "cat", and the rest of the string is "**in*the*hat". The tokenizer should skip the first four spaces, read over the non-blank "cat", then stop at the first blank after "cat". It removes that blank, and the rest of the string is "**in*the*hat". Again, blanks with double or single quotes are not to be considered delimiters. You can assume there will be no \* (i.e., backslash followed by a blank), though you can handle it if you want.
Notice that it comes as "cat". If you didn't trim the token, then it would be "****cat".
If the delimiter contains more than one blank (and nothing else) assume it's just one blank space.
For any other delimiter, you simply look for the first "real" occurrence of the delimiter.
- How does stripComment relate to the rest of
the static methods?
Actually, it doesn't. While the rest are useful for tokenizing, this one static method is used for later projects to remove comments from the assembly code.
Therefore, you can assume that comments won't appear in methods dealing with tokenizing. (In any case, without knowing what the comment string is, you can't remove comments withother methods, so you have to make this assumption).
- When should I replace the escaped characters?.
getLeftToken() should get the first token (up to the first delimiter, should it exist), then replace the escaped characters in the token (replacing \' with ', \\ with \, \" with ", and \n with the newline). The rest of the string should remain unchanged (i.e. the substring after the token).
So split() merely calls getLeftToken() over and over, until the string is empty. It doesn't need to do any substitutions of escaped characters.
- Can I use any STL string functions?
You are encouraged to do so. You may find there are many convenient methods available, that will help you avoid doing work. You're always encouraged to read through the set of methods available to you.
Try this link. It's SGI (Silicon Graphics) reference to STL. It's not great, but it should do. There are various "find" and "replace" operations that might be useful.
- Can I write helper functions?
Do you need to ask? Of course, you can! One useful function to write is one that replaces escaped characters.
|
See the class syllabus for policies concerning email Last Modified: Wed Jun 5 10:38:37 EDT 2002 |
|
|
|
|
|
|
|
c m s c 311
f a l l 2 0 0 2 |
- (9/19) Even more extra credit?
Well, not exactly "more" (a little more perhaps). I noticed from the project description that getLeftToken() left trims the token. So, I am going to follow that. I think I did that to handle white space for space as delimiter.
However, make getRightToken() find the rightmost delimiter and NOT trim the white space.
Thus, if the string were "***cat***,***dog**", then the rightmost token would be "***dog**", and the rest of the string would be "***cat***" (without the comma).
- (9/19) Extra credit? What's that?
Yesterday, someone asked what we should do about escaped delimiters. Here is the part that's the usual stuff (i.e., not extra credit:
- If a backslash followed by an n appears (i.e., two separate characters in the string), replace that by a single newline.
- If \\, \', \" appear, replace that by \, ', and ", respectively.
- If a \ followed by a delimiter appears, then replace that by the delimiter.
You may assume backslashes do not appear for anything else. Thus, \a is not a valid substring, unless "a" is a delimiter.
Extra credit
Suppose you have :: as a delimiter (two colons). Then, you should be able to handle the following: \::: is considerd an escaped delimiter (thus not a true delimiter) followed by a colon. \:::: is treated as an escaped (non-true) delimiter followed by ::, which is a true delimiter.
\\\\\\ is really three escaped backslashes and gets translated to a three real backslashes.
Finally, findRealDelimiter, when looking for 1 or more blank spaces should return the index of the first non-quoted blank that appears after a string of non-blank characters. If such a blank does not appear, it returns -1. Thus, [***cat***], will return 6 (where * is being used to stand for blanks, to make it easier to see in this FAQ and brackets are used to show where the string starts and end, but is not part of the string itself).
If you have "***'cat**'*", then findRealDelimiter() returns 10 since it skips the first three blanks, ignores the item in single quotes, and finds the space at the end.
For any other delimiter, it just looks for the first non-quoted, non-escaped version of that delimiter. Only blanks used as delimiters have this weird feature.
- Is space as a delimiter handled in any unusual way?
Yes. Unfortunately, using space (blank, not TAB or newlines) as a delimiter has to be handled differently. Otherwise, it makes split() awkward to use. If " " is a delimiter, then getLeftToken() should skip over any blank spaces, then over any non-blank spaces, and stop at the next blank space, or the end of string, whichever comes first.
Thus, if the string were "****cat***in*the*hat" where * represents a blank, then, the first token is "cat", and the rest of the string is "**in*the*hat". The tokenizer should skip the first four spaces, read over the non-blank "cat", then stop at the first blank after "cat". It removes that blank, and the rest of the string is "**in*the*hat". Again, blanks with double or single quotes are not to be considered delimiters. You can assume there will be no \* (i.e., backslash followed by a blank), though you can handle it if you want.
Notice that it comes as "cat". If you didn't trim the token, then it would be "****cat".
If the delimiter contains more than one blank (and nothing else) assume it's just one blank space.
For any other delimiter, you simply look for the first "real" occurrence of the delimiter.
- How does stripComment relate to the rest of
the static methods?
Actually, it doesn't. While the rest are useful for tokenizing, this one static method is used for later projects to remove comments from the assembly code.
Therefore, you can assume that comments won't appear in methods dealing with tokenizing. (In any case, without knowing what the comment string is, you can't remove comments withother methods, so you have to make this assumption).
- When should I replace the escaped characters?.
getLeftToken() should get the first token (up to the first delimiter, should it exist), then replace the escaped characters in the token (replacing \' with ', \\ with \, \" with ", and \n with the newline). The rest of the string should remain unchanged (i.e. the substring after the token).
So split() merely calls getLeftToken() over and over, until the string is empty. It doesn't need to do any substitutions of escaped characters.
- Can I use any STL string functions?
You are encouraged to do so. You may find there are many convenient methods available, that will help you avoid doing work. You're always encouraged to read through the set of methods available to you.
Try this link. It's SGI (Silicon Graphics) reference to STL. It's not great, but it should do. There are various "find" and "replace" operations that might be useful.
- Can I write helper functions?
Do you need to ask? Of course, you can! One useful function to write is one that replaces escaped characters.
|
See the class syllabus for policies concerning email Last Modified: Wed Jun 5 10:38:37 EDT 2002 |
|
|
|
|
|
|
|
c m s c 311
f a l l 2 0 0 2 |
Due Sunday, Oct. 13, 11:59 PM (just before midnight)
Late Due Date Sunday, Oct. 20, 11:59 PM (just before midnight)
Posted: September 27, 2002
Addendum
Read this section frequently to check for updates/corrections/clarifications to the projects. There will be some, because the project description is rather rough right now. However, the methods should be more or less correct.
-
Purpose
-
The goals of the project are:
- Learn how to write functions to convert from one base to another.
- Learn how to tell if a machine is big or little endian.
- Write a Register class.
- Read from a binary file.
-
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
-
Collaboration Policy
- This project should be done invidividually. You may discuss ideas, but not exchange or view each other's code.
-
Specifications
-
You will be given a file called Convert.h and
Register.h. The specifications are in the following link.
Convert Specification
Register Specification
(10/5 NOW READY)Implement the methods. You may add helper methods, if you want.
-
Assumptions
-
Restrictions
-
Restrictions.
- You should write Convert in C++.
- You should write Register in C++ or Java.
You may use STL or any other features you want, provided it compiles and runs under either cxx or g++. A driver will be provided, so you can submit.
-
How to Submit
- A driver will be provided soon to partly test your code. Details will be provided soon.
|
See the class syllabus for policies concerning email Last Modified: Wed Jun 5 10:38:37 EDT 2002 |
|
|
|
|
|
|
|
c m s c 311
f a l l 2 0 0 2 |
Purpose
The goal of this project is to implement a representation of a register. This is a software emulation of a register. The register supports the following information:
- different number of bits (even though registers typically have 16, 32 or 64 bits).
- bitwise operations such as &, |, ^, etc.
- bitshifting operations
- addition and subtraction
Location of File
Go to ~chf11001/Proj/P1/, and there should be Register.h and RegisterInterface.java for C++ and Java respectively. Create Register.cpp or finish Register.java.
C++ Specifications
| Bit |
Private Instance Variables
Represents a single bit.
| Variable | Description |
| boolean value | Represents a single bit. When value is true, the bit is 1, otherwise it's 0. |
Public Methods
| Bit() ; |
| Default constructor. Sets value to false. |
| int getValue() const ; |
| Returns 0 if value is false, and 1 if value is true. |
| Bit set() ; |
| Sets value to true. Return this . |
| Bit clear() ; |
| Sets value to false. Return this . |
| Bit flip() ; |
| Sets value to its negated value (i.e., flips true to false and vice versa). Return this . |
| Register |
Private Instance Variables
| Variable | Description |
| ??? bit | Pick a reasonably type to store an array of Bit objects (as defined above). The ??? means you get to pick the type for storing an array of bits. (There is a container class that begins with Array...look it up in the Java API at Sun's website). |
Public Methods
| Register( int numBits = 32 ) ; |
| Default constructor. Creates a register with numBits bits. If the number of bits is less than 1, then set numBits to 32 bits. The user can pick an arbitrary size register. |
| Bit getBitAt( int index ) ; |
|
Return the bit (by reference) at index. Assume user will
not go out-of-bounds. If you want to throw an exception, then throw
ArrayIndexOutOfBoundsException (this is already a built-in
exception).
|
| String getSignedDecimal() ; |
| Return the value in the register as a String. Treat the value as signed (thus, it may have a leading minus sign). Use as few digits as needed (minimum of 1). |
| String getUnsignedDecimal() ; |
| Return the value in the register as a String. Treat the value as unsigned. Use as few digits as needed. |
| String getHex() ; |
| Return the value in the register as a String. Treat the value as unsigned. The string should represent the value written in hexadecimal. The result should have a 0x (zero followed by x) prepended (i.e., in front), and use lowercase letters for a, b, c, d, e, f. Use as few hex digits as needed (minimum 1). For example, you might have 0xcafe001 as a result. |
| Register signExtend( int totalBits ) ; |
| Create a copy of this register, but with totalBits bits. The register should be sign-extended if totalBits > numBits. If totalBits <= numBits, return a copy of the register (which has numBits bits). |
| Register zeroExtend( int totalBits ) ; |
| Create a copy of this register, but with totalBits bits. The register should be zero-extended if totalBits > numBits (i.e., the high bits are all 0's, but the low bits are copied). If totalBits <= numBits, return a copy of the register (which has numBits bits). |
| ??? bitwiseNot() ; |
| Bitwise negation. Flip all the bits. Figure out the appropriate return value by determining how the C version of bitwise negation modifies variables. |
| ??? bitwiseAnd( Register other ) ; ??? bitwiseOr( Register other ) ; ??? bitwiseXor( Register other ) ; |
|
Bitwise AND, bitwise OR, and bitwise XOR.
You should determine what return type is appropriate for these bitwise operations. |
| ??? bitwiseAndSelf( Register other ) ; ??? bitwiseOrSelf( Register other ) ; ??? bitwiseXorSelf( Register other ) ; |
|
Bitwise AND, bitwise OR, and bitwise XOR.
You should determine what return type is appropriate for these bitwise operations, by basing it on C's versions of these operators: i.e., &=, |=, ^=. |
| ??? addSigned( Register other ) ; |
|
Do a signed addition. If the size of other register
is smaller than this register's size, then create a SIGN extended
copy of the other register so that the copy has as many bits
as the this register.
If other has more bits than this, and this has N bits, then only use the lowest N bits of other to do the addition. Perform signed addition while ignoring overflow. The result should have numBits bits. This addition should "behave" like addition of int variables, when it comes to determining what (or what NOT to) modify. Thus, you should determine what return type is appropriate for addition. |
| ??? addSignedSelf( Register & other ) ; |
| Do a signed addition that behaves like operator+=. Again, ignore overflow. |
| ??? addUnsigned( Register & other ) ; |
|
Do an unsigned addition. If the size of other register
is smaller than this register's size, then create a ZERO extended
copy of the other register so that the copy has as many bits
as the this register.
If other has more bits than this, and this has N bits, then only use the lowest N bits of other to do the addition. Perform unsigned addition while ignoring overflow. The result should have numBits bits. This addition should "behave" like addition of int variables, when it comes to determining what (or what NOT to) modify. Thus, you should determine what return type is appropriate for addition. |
| ??? addUnsignedSelf( Register other ) ; |
| Do an unsigned addition that behaves like operator+=. Again, ignore overflow. |
| ??? minus( Register other ) ; |
| Do a signed subtraction. Hint: think two's complement. Ignore overflow. |
| ??? minusSelf( Register other ) ; |
| Do a signed subtraction that behaves like operator+=. Hint: think two's complement. Again, ignore overflow. |
| ??? addUnsigned( Register other ) ; |
|
Do an unsigned addition. If the size of other register
is smaller than this register's size, then create a ZERO extended
copy of the other register so that the copy has as many bits
as the this register.
If other has more bits than this, and this has N bits, then only use the lowest N bits of other to do the addition. Perform unsigned addition while ignoring overflow. The result should have numBits bits. This addition should "behave" like addition of int variables, when it comes to determining what (or what NOT to) modify. Thus, you should determine what return type is appropriate for addition. |
| ??? negate() ; |
|
Negates the value in the register treating the binary value as
signed. Hint: how does this differ (if at all) from bitwise negation?
Determine an appropriate return type by thinking about how unary minus affects int variables. |
|
See the class syllabus for policies concerning email Last Modified: Fri Sep 27 19:41:52 EDT 2002 |
|
|
|
|
|
|
|
c m s c 311
f a l l 2 0 0 2 |
Purpose
The goal of this project is to have you implement code to
- convert numbers, represented as strings, from one base to another,
- convert strings from binary to octal and hexadecimal and back
- convert int values to strings that represent signed magnitude, one's complement, two's complement, excess/bias
- determine if a machine is big or little endian
- determine if an int value is big or little endian
Location of File
Go to ~chf11001/Proj/P1/, and there should be Convert.h. Create Convert.cpp.
| Convert |
Static Public Methods
| static std::string baseTenToBaseK( const std::string & num, int dstBase ) ; |
|
Given parameter num, which is a C++ string representing
a base ten number (e.g., "23" ), convert this to another base
(e.g., base 16) as a string (e.g. "17"), using as few digits
as possible in the resulting string (i.e., don't write "0017").
You may assume:
Use lowercase letters "a" to stand for 10, "b" for 11, ..., and "z" to stand for 35. You should convert the string to a base 10 unsigned int value, then divide by k, convert the remainder to a character, and create a string by concatenating onto an empty string. |
| static baseKToBaseTen( const std::string & num, int srcBase ) ; |
|
Given parameter num, which is a C++ string representing
a number (e.g., "1111" ), written in some base k (e.g., base 2), convert
this to a string written in base 10 (e.g., "15"), using as few digits
as possible in the resulting string (i.e., don't write "0015").
You may assume:
To convert, you need to convert each digit (which is a character in the string) to a number, and multiply that number by some power of k, and sum, as shown in class. The resulting value should be converted to a string. Hint: use ostringstream by #include <sstream>.
|
| static std::string srcToDstBase( const std::string & num, int srcBase, int dstBase ) ; |
|
Given parameter str, which represents a number in
srcBase, convert that to a number in dstBase.
Assume both bases are between 2 and 36. The rules that
affect the srcBase are the same as in baseKtoBaseTen.
destBase should produce a string that uses only lowercase
letters.
You can assume:
|
| static std::string octalToBin( const std::string & num ) ; static std::string hexToBin( const std::string & num ) ; static std::string binToOctal( const std::string & num ) ; static std::string binToHex( const std::string & num ) ; |
|
You should convert these strings which represent values in base
2, 8, and 16, efficiently to one another. These strings can
be arbitrarily long (i.e., they may not fit in 32 bit int values).
Use the "quick" technique in class.
You can assume these are unsigned values. Use lowercase to represent "a"..."f" (values 11 through 15). |
| static std::bool isBigEndian() ; static std::bool isLittleEndian() ; |
|
isBigEndian() returns true if the machine the code
is run on is big endian, and false otherwise (i.e., it's little
endian.
isLittleEndian() returns true if the machine the code is run on is little endian, and false otherwise (i.e., it's big endian. This function should return different answers on the OIT cluster and the Sun machines on WAM. They have different endianness. |
| static int endian( unsigned int val, std:: string num ) ; |
|
Assume num represents an unsigned base ten value written
as a string. You will be given an unsigned int value. This value
is really four consecutive bytes in memory. Determine if those
four bytes represent num in big endian (return 1), little
endian (return 0), or neither (return -1).
The idea is this. Suppose someone put 4 bytes into an unsigned int, but did not know how your machine endian was stored. They also sent a string indicating the number they meant to store ("num"), and based on that, you can determine what endian-ness the value is stored. Hint: determine the number you have, then reverse the bytes, and determine that number. See if either one match the value. You know which endian-ness your machine is, so you should be able to figure it out. Another trick is to take each of the four byte, cast it to an int, and shift the number of bits and sum. (Puzzling clue, I realize). |
|
static std::string toOnesComp( int num, int numBits ) ; static std::string toTwosComp( int num, int numBits ) ; static std::string toSignedMag( int num, int numBits ) ; static std::string toExcess( int num, int bias, int numBits ) ; |
|
You are given a signed value called num. Convert num
to a string with numBits characters, if possible. If the
number of bits is too small, then return the string "OVERFLOW".
For example, if you were given num as -7, and written as one's complement, given 4 bits, your answer would be "1000". If it were 5 bits, you would return: "11000". If it were signed magnitude with 4 bits, you would return "1111". If you were asked to write -8 in one's complement, with 4 bits, you would return "OVERFLOW". |
|
static int fromOnesComp( const std::string & num ) ; static int fromTwosComp( const std::string & num ) ; static int fromSignedMag( const std::string & num ) ; static int fromExcess( const std::string & num, int bias ) ; |
| You're given a binary value written as a string, written in one of four representations. Convert that to a signed value. You may assume the value can be stored in a 32 bit signed int. |
| static std::string toIEEE754( std::string num ) ; |
|
This is extra credit. Assume you have a string which may or may
not have a leading - sign. This string represents a number written in
decimal, e.g., "3.625". You should return a 32 character string
representing the IEEE 754 single precision value.
You can assume the string does not generate repeated values, nor does it produce infinity or NaN. The string should have the most significant bit (i.e., the sign bit) to the far left, and the least significant bit to the far right, and be 32 characters long. |
|
See the class syllabus for policies concerning email Last Modified: Fri Sep 27 19:41:52 EDT 2002 |
|
|
|
|
|
|
|
c m s c 311
f a l l 2 0 0 2 |
Purpose
The goal of this project is to implement a representation of a register. This is a software emulation of a register. The register supports the following information:
- different number of bits (even though registers typically have 16, 32 or 64 bits).
- bitwise operations such as &, |, ^, etc.
- bitshifting operations
- addition and subtraction
Location of File
Go to ~chf11001/Proj/P1/, and there should be Register.h and RegisterInterface.java for C++ and Java respectively. Create Register.cpp or finish Register.java.
Java Specifications
| Bit |
Private Instance Variables
Represents a single bit.
| Variable | Description |
| bool value | Represents a single bit. When value is true, the bit is 1, otherwise it's 0. |
Public Methods
| Bit() ; |
| Default constructor. Sets value to false. |
| int getValue() const ; |
| Returns 0 if value is false, and 1 if value is true. |
| Bit & set() ; |
| Sets value to true. Return * this . |
| Bit & clear() ; |
| Sets value to false. Return * this . |
| Bit & flip() ; |
| Sets value to its negated value (i.e., flips true to false and vice versa). Return * this . |
| Bit & operator=( int valueIn ) ; |
| Sets value to false if valueIn is 0, otherwise set it to true. |
| Bit & operator=( bool valueIn ) ; |
| Sets value to valueIn. |
If there is a need to define the copy constructor, assignment operator, and destructor, in order to guarantee the correct behavior of this class, you may do so.
| Register |
Private Instance Variables
| Variable | Description |
| ??? bit | Pick a reasonably type to store an array of Bit objects (as defined above). Hint: don't use an array of bits (although you can). The ??? means you get to pick the type for storing an array of bits. |
| int _size | Stores the number of bits, but only if needed (for example, if you choose an approriate class for the array of Bit, then that class may already keep track of the size), making this instance variable unnecessary. |
Public Methods
| Register( int numBits = 32 ) ; |
| Default constructor. Creates a register with numBits bits. If the number of bits is less than 1, then set numBits to 32 bits. The user can pick an arbitrary size register. |
| Bit & operator[]( int index ) ; |
|
Return the bit (by reference) at index. Assume user will
not go out-of-bounds. If you want to throw an exception, then name
the exception class exactly
ArrayIndexOutOfBoundsException (read up on C++ exceptions if you
wish). Note: this is the same name as the Java exception thrown.
|
| const Bit & operator[]( int index ) const ; |
| Return the bit (by reference) at index. (Same thing as previous, but it will return by const reference). Can also throw exception as above. |
| string getSignedDecimal() const ; |
| Return the value in the register as a string. Treat the value as signed (thus, it may have a leading minus sign). Use as few digits as needed (minimum of 1). |
| string getUnsignedDecimal() const ; |
| Return the value in the register as a string. Treat the value as unsigned. Use as few digits as needed. |
| string getHex() const ; |
| Return the value in the register as a string. Treat the value as unsigned. The string should represent the value written in hexadecimal. The result should have a 0x (zero followed by x) prepended (i.e., in front), and use lowercase letters for a, b, c, d, e, f. Use as few hex digits as needed (minimum 1). For example, you might have 0xcafe001 as a result. |
| Register signExtend( int totalBits ) const ; |
| Create a copy of this register, but with totalBits bits. The register should be sign-extended if totalBits > numBits. If totalBits <= numBits, return a copy of the register (which has numBits bits). |
| Register zeroExtend( int totalBits ) const ; |
| Create a copy of this register, but with totalBits bits. The register should be zero-extended if totalBits > numBits (i.e., the high bits are all 0's, but the low bits are copied). If totalBits <= numBits, return a copy of the register (which has numBits bits). |
| ??? operator~() ; |
| Bitwise negation. Flip all the bits. Figure out the appropriate return value by determining how the C version of bitwise negation modifies variables. |
| ??? operator&( const Register & other ) ; ??? operator|( const Register & other ) ; ??? operator^( const Register & other ) ; |
|
Bitwise AND, bitwise OR, and bitwise XOR.
You should determine what return type is appropriate for these bitwise operations. |
| ??? operator&=( const Register & other ) ; ??? operator|=( const Register & other ) ; ??? operator^=( const Register & other ) ; |
|
Bitwise AND, bitwise OR, and bitwise XOR.
You should determine what return type is appropriate for these bitwise operations, by basing it on C's versions of these operators: i.e., &=, |=, ^= |
| ??? operator+( const Register & other ) const ; |
|
Do a signed addition. If the size of other register
is smaller than this register's size, then create a SIGN extended
copy of the other register so that the copy has as many bits
as the this register.
If other has more bits than this, and this has N bits, then only use the lowest N bits of other to do the addition. Perform signed addition while ignoring overflow. The result should have numBits bits. This addition should "behave" like addition of int variables, when it comes to determining what (or what NOT to) modify. Thus, you should determine what return type is appropriate for addition. |
| ??? operator+=( const Register & other ) ; |
| Do a signed addition that behaves like operator+=. Again, ignore overflow. |
| ??? addUnsigned( const Register & other ) const ; |
|
Do an unsigned addition. If the size of other register
is smaller than this register's size, then create a ZERO extended
copy of the other register so that the copy has as many bits
as the this register.
If other has more bits than this, and this has N bits, then only use the lowest N bits of other to do the addition. Perform unsigned addition while ignoring overflow. The result should have numBits bits. This addition should "behave" like addition of int variables, when it comes to determining what (or what NOT to) modify. Thus, you should determine what return type is appropriate for addition. |
| ??? addUnsignedSelf( const Register & other ) ; |
| Do an unsigned addition that behaves like operator+=. Again, ignore overflow. |
| ??? operator-( const Register & other ) const ; |
| Do a signed subtraction. Hint: think two's complement. Ignore overflow. |
| ??? operator-=( const Register & other ) ; |
| Do a signed subtraction that behaves like operator+=. Hint: think two's complement. Again, ignore overflow. |
| ??? addUnsigned( const Register & other ) const ; |
|
Do an unsigned addition. If the size of other register
is smaller than this register's size, then create a ZERO extended
copy of the other register so that the copy has as many bits
as the this register.
If other has more bits than this, and this has N bits, then only use the lowest N bits of other to do the addition. Perform unsigned addition while ignoring overflow. The result should have numBits bits. This addition should "behave" like addition of int variables, when it comes to determining what (or what NOT to) modify. Thus, you should determine what return type is appropriate for addition. |
| ??? operator-() ; |
|
Overloaded unary minus operator. Negates the value in the
register treating the binary value as signed. Hint: how
does this differ (if at all) from bitwise negation?
Determine an appropriate return type by thinking about how unary minus affects int variables. |
|
See the class syllabus for policies concerning email Last Modified: Fri Sep 27 19:41:52 EDT 2002 |
|
|
|
|
|
|
|
c m s c 311
f a l l 2 0 0 2 |
Due Friday, Dec. 13, 11:59 PM (just before midnight)
Late Due Date Sunday, Dec. 15, 11:59 PM (just before midnight)
Posted: November 27, 2002
-
Purpose
-
The goals of the project are:
- Learn how to read/write a "binary file" in C/C++ (this can be done in Java, but if you're using Java, you have to figure out how to do this).
- To convert a binary MIPS instruction to a string.
- To convert a MIPS instruction given as a string to an unsigned int.
-
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
-
Collaboration Policy
- This project should be done invidividually. You may discuss ideas, but not exchange or view each other's code.
-
Specifications
-
You will be given a file called Translate.h and
Load.h. The specifications are in the following link.
Translate Specification
Load Specification
Implement the methods. You may add helper methods, if you want.
-
Format of instructions
-
Note: || means concatentation
Note: 016 means 16 zeroes.
Note: PC refers to the program counter
Note:- rs stored at B25-21
- rt stored at B20-16
- rd stored at B15-11
Note:
- immed values for addi are written in signed base 10, but stored in 16-bit 2's complement.
- immed values for logical operations (andi, xori, etc.) are written in unsigned base 10, and stored in unsigned binary.
- Labels for jump instructions will be written in hexadecimal with a leading 0x followed by 8 hex digits. Use the low 26 bits, and store there.
- Labels for branch instructions will be written in signed base 10 and stored in 16-bit 2's complement.
Note: Bits are numbered so that B0 is the least signficant bit and B31 is the most significant bit.
Note: Minimum instructions needed to pass primary: add, addi, beq, j, jal, or, ori. You need to translate to and from.
Command Explanation add $rd, $rs, $rt - Reg[ d ] = Reg[ s ] + Reg[ t ]
- R-type instruction
- B31-26 = 000000 (SPECIAL)
- B10-6 = 000000
- B5-0 = 100000 (ADD)
addi $rt, $rs, immed - Reg[ t ] = Reg[ s ] + (immed15)16 || immed15-0
- I-type instruction
- B31-26 = 001000
- Immediate value is sign extended
sub $rd, $rs, $rt - Reg[ d ] = Reg[ s ] - Reg[ t ]
- R-type instruction
- B31-26 = 000000 (SPECIAL)
- B10-6 = 000000
- B5-0 = 100010 (SUB)
and $rd, $rs, $rt - Reg[ d ] = Reg[ s ] & Reg[ t ]
- Bitwise AND
- R-type instruction
- B31-26 = 000000 (SPECIAL)
- B10-6 = 000000
- B5-0 = 100100 (AND)
andi $rt, $rs, immed - Reg[ t ] = Reg[ s ] & 016 || immed15-0
- I-type instruction
- B31-26 = 001100
- Immediate value is zero extended
or $rd, $rs, $rt - Reg[ d ] = Reg[ s ] | Reg[ t ]
- Bitwise OR
- R-type instruction
- B31-26 = 000000 (SPECIAL)
- B10-6 = 000000
- B5-0 = 100101 (OR)
ori $rt, $rs, immed - Reg[ t ] = Reg[ s ] | 016 || immed15-0
- I-type instruction
- B31-26 = 001101
- Immediate value is zero extended
xor $rd, $rs, $rt - Reg[ d ] = Reg[ s ] ^ Reg[ t ]
- Bitwise XOR
- R-type instruction
- B31-26 = 000000 (SPECIAL)
- B10-6 = 000000
- B5-0 = 100110 (XOR)
xori $rt, $rs, immed - Reg[ t ] = Reg[ s ] ^ 016 || immed15-0
- I-type instruction
- B31-26 = 001110
- Immediate value is zero extended
beq $rs, $rt, LABEL - if ( Reg[ s ] == Reg[ t ] ) jump to LABEL else go to next instruction
- I-type instruction
- B31-26 = 000100
- offset is B15-0
- Jump to PC + [ (offset15)14 || offset || 02 ]
- i.e., the offset is shifted to the left by 2, then sign extended.
bne $rs, $rt, LABEL - if ( Reg[ s ] != Reg[ t ] ) jump to LABEL else go to next instruction
- I-type instruction
- B31-26 = 000101
- offset is B15-0
- Jump to PC + [ (offset15)14 || offset || 02 ]
- i.e., the offset is shifted to the left by 2, then sign extended.
slt $rd, $rs, $rt - if ( Reg[ s ] < Reg[ t ] ) Reg[ d ] = 0311 else Reg[ d ] = 032
- R-type instruction
- B31-26 = 000000 (SPECIAL)
- B10-6 = 000000
- B5-0 = 101010 (SLT)
slti $rt, $rs, immed - if ( Reg[ s ] < (immed15)16 || immed15-0) Reg[ d ] = 0311 else Reg[ d ] = 032
- I-type instruction
- B31-26 = 001010
jr $rs - R-type instruction (sort of)
- B31-26 = 000000 (SPECIAL)
- B20-6 = 000 0000 0000 0000
- B5-0 = 000100 (JR)
j LABEL - PC <- PC31-28 || immed || 02
- immed is 26 bit value
- J-type instruction
- B31-26 = 000010
jal LABEL - PC <- PC31-28 || immed || 02
- immed is 26 bit value
- Reg[ 31 ] <- PC + 4 (In the real MIPS, it should be PC + 8, but that's mostly because of pipelining--we use the simpler PC + 4, which is the next instruction).
- J-type instruction
- B31-26 = 000011
lw $rt, offset($rs) - I-type instruction
- offset is sign-extended to 32 bits, and added to Reg[ s ] to produce address. The content of that address (which must be word-aligned), is placed in Reg[ t ]
- B31-26 = 100011
- B15-0 is the offset
lbu $rt, offset($rs) - I-type instruction
- offset is sign-extended to 32 bits, and added to Reg[ s ] to produce address. The content of that address (which does NOT have to be word-aligned), is placed in Reg[ d ]
- B31-26 = 100100 (CORRECTED)
- B15-0 is the offset
sw $rt, offset($rs) - I-type instruction
- offset is sign-extended to 32 bits, and added to Reg[ s ] to produce address. The content of Reg[ t ] is saved at that address (which must be word-aligned)
- B31-26 = 101011
- B15-0 is the offset
sb $rt, offset($rs) - I-type instruction
- offset is sign-extended to 32 bits, and added to Reg[ s ] to produce address. The content of Reg[ t ] is saved at that address (which does NOT have to be word-aligned)
- B31-26 = 101000
- B15-0 is the offset
lui $rt, immed - I-type instruction
- Reg[ t ] = immed || 016
- B31-26 = 001111
- B25-21 = 00000 (normally where rs goes, but leave it all zeroes)
bgtz $rs, LABEL - I-type instruction
- B31-26 = 000111
- B20-16 = 00000
- Let offset = B15-0
- PC-relative addressing. Let target = (offset15)14 || offset || 02
- PC <- PC + target
bgez $rs, LABEL - I-type instruction
- B31-26 = 000001 (REGIMM)
- B20-16 = 00001 (BGEZ)
- Let offset = B15-0
- PC-relative addressing. Let target = (offset15)14 || offset || 02
- PC <- PC + target
bltz $rs, LABEL - I-type instruction
- B31-26 = 000001 (REGIMM)
- B20-16 = 00000 (BLTZ)
- Let offset = B15-0
- PC-relative addressing. Let target = (offset15)14 || offset || 02
- PC <- PC + target
blez $rd, LABEL - I-type instruction
- B31-26 = 000110
- B20-16 = 00000
- Let offset = B15-0
- PC-relative addressing. Let target = (offset15)14 || offset || 02
- PC <- PC + target
sll $rt, $rs, shift_amt - R-type instruction
- Shift left logical
- B10-6 is the shift amount (between 0-31)
- B31-26 = 000000 (SPECIAL)
- B5-0 = 000000 (SLL)
- Shift a copy of Reg[ t ] left by shift_amt bits, inserting zeroes into the low order bits.
srl $rd, $rt, shift_amt - R-type instruction
- Shift right logical
- B10-6 is the shift amount (between 0-31)
- B31-26 = 000000 (SPECIAL)
- B5-0 = 000010 (SRL)
- Shift a copy of Reg[ t ] right by shift_amt bits, inserting zeroes into the high order bits.
sllv $rd, $rs, $rt
(SPRING 2003)- R-type instruction
- Shift left logical variable
- B10-6 = 00000
- B31-26 = 000000 (SPECIAL)
- B5-0 = 000100 (SLLV)
- Shift a copy of Reg[ t ] left by the amount stored in low 5 bits of Reg[ s ], placing shifted result in Reg[ d ].
srlv $rd, $rt
(SPRING 2003)- R-type instruction
- Shift right logical variable
- B10-6 = 00000
- B31-26 = 000000 (SPECIAL)
- B5-0 = 000110 (SRLV)
- Shift a copy of Reg[ t ] right by the amount stored in low 5 bits of Reg[ s ], placing shifted result in Reg[ d ].
|
See the class syllabus for policies concerning email Last Modified: Wed Jun 5 10:38:37 EDT 2002 |
|
|
|
|
|
|
|
c m s c 311
f a l l 2 0 0 2 |
Purpose
The purpose is to load a series of unsigned int (32 bits) from a file. The file will have a 32 bit value (0xdabedabe). As you read it in, it may have been stored in the same endian-ness as your machine or a different endian-ness. (Imagine you have downloaded this file from somewhere on the web, but don't know what endian-ness the machine was).If you read in an unsigned int equal to 0xdabedabe, then this must mean the file is the same as yours. If it's some other value, then it must be a different endian-ness.
Public Methods
| static vector<unsigned int> loadValues( const string & fileName ) ; |
|
If the file exists (in the current directory), read in the first
unsigned int, and determine the endian-ness. If this is the
same as your machine's endian-ness, read the rest of the values
normally. Thus, if there are N * 4 bytes in the file, you will
read in (N - 1) unsigned int values (after the initial 4 byte
header with 0xdabedabe), and store them in a vector of unsigned ints.
If the endian-ness is not the same as your machine, then you still read in the N - 1 values, but then afterwards, you must convert the values so they are the same endian-ness as your machine. (Thus, for each unsigned int, you must swap bytes 0 and 3 and bytes 1 and 2, assuming byte 0 is the least significant byte, and byte 3 is the most significant byte). If the file does not exist, then just return an empty vector. You can assume that there is at least 8 bytes in the file if it does exist (i.e., it has the 4 byte header plus at least one 4 byte integer). |
| static bool writeValues( const string & fileName, vector<unsigned int> values, bool isBigEndian ) ; |
|
In this version, you will write out the values given the endian-ness.
Add the header as needed (0xdabedabe). This may involve swapping bytes.
If you read in the file, then call this function with the same endian-ness
as the file, then print out the file, you should get the equivalent file
(you can run "diff" to see if they result in the same binary).
If the file exists, then return false, and don't do anything. |
Location of File
Go to ~chf11001/Proj/P2/, and there should be Load.h. Those implementing it in Java should make the appropriate conversions.Writing Binary Files
int fd ; // fd is called a file descriptor
ssize_t w1, w2 ;
char header1[ 512 ], header2[ 1024 ] ;
// Opens a file to be written, but only if file does not already exist.
if ( ( fd = open( "newfile", O_WRONLY|O_CREAT|O_EXCL, 0644 ) ) == -1 )
{
cout << "Error opening file" << endl ;
return -1 ;
}
w1 = write( fd, header1, 512 ) ;
w2 = write( fd, header1, 1024 ) ;
// close the file
close( fd ) ;
The write function takes a file descriptor of an opened
file, a pointer to some array (any type) or even just a plain
structure or variable, and the number of bytes that will be
written. The function returns an int-like value telling you
how many bytes were actually written.
To open a file for reading (in C),
int fd ; // fd is called a file descriptor
ssize_t n1, n2 ;
char buf[ 512 ], buf2[ 1024 ] ;
// Opens a file for read only
if ( ( fd = open( "oldfile", O_RDONLY ) ) == -1 )
{
cout << "Error opening file" << endl ;
return -1 ;
}
n1 = read( fd, buf1, 512 ) ;
n2 = read( fd, buf2, 1024 ) ;
// close the file
close( fd ) ;
Nelson Padua-Perez offers the C++ solution.
Note: you should switch "Person" to unsigned int.
#include <iostream.h>
#include <stdlib.h>
#include <fstream.h>
struct Person
{
int id;
float salary;
};
// write takes a char *, and the number of bytes
void create_file(char *filename)
{
int x;
Person p;
ofstream out(filename, ios::out);
if (!out)
{
cerr << "File opening failed!" << endl;
exit(1);
}
for (x = 1; x <= 5; x++)
{
p.id = x;
p.salary = x * 100;
out.write(reinterpret_cast<const char *>(&p), sizeof(Person));
}
}
// read takes a char * pointer, and the number of bytes.
// Notice you can store into any object---endian-ness is an
// issue, however. If the file stores in big-endian, and the machine
// is little-endian, the number will be read in the wrong order.
// There's no information in the file to determine endian-ness.
void read_file(char *filename)
{
int x;
Person p;
ifstream in(filename, ios::in);
if (!in)
{
cerr << "File opening failed!" << endl;
exit(1);
}
for (x = 1; x <= 5; x++)
{
in.read(reinterpret_cast<char *>(&p), sizeof(Person));
cout << "ID: " << p.id << " , SALARY " << p.salary << endl;
}
}
void read_entry(int id, char *filename)
{
Person p;
ifstream in(filename, ios::in);
in.seekg((id - 1) * sizeof(Person));
in.read(reinterpret_cast<char *>(&p), sizeof(Person));
cout << "SID: " << p.id << " , SSALARY " << p.salary << endl;
}
void write_entry(int id, float salary, char *filename)
{
Person p;
ofstream out(filename, ios::out);
p.id = id;
p.salary = salary;
out.seekp((id - 1) * sizeof(Person));
out.write(reinterpret_cast<const char *>(&p), sizeof(Person));
}
int main()
{
create_file("data");
read_file("data"); // sequential reading
cout << "READING ENTRY" << endl;
read_entry(2, "data");
cout << "RANDOM WRITING" << endl;
write_entry(2, 1345, "data");
read_entry(2, "data");
return 0;
}
OUTPUT
% a.out
ID: 1 , SALARY 100
ID: 2 , SALARY 200
ID: 3 , SALARY 300
ID: 4 , SALARY 400
ID: 5 , SALARY 500
READING ENTRY
SID: 2 , SSALARY 200
RANDOM WRITING
SID: 2 , SSALARY 1345
%
|
See the class syllabus for policies concerning email Last Modified: Fri Sep 27 19:41:52 EDT 2002 |
|
|
|
|
|
|
|
c m s c 311
f a l l 2 0 0 2 |
Due Friday, Dec. 13, 11:59 PM (just before midnight)
Late Due Date Sunday, Dec. 15, 11:59 PM (just before midnight)
Posted: November 27, 2002
-
Purpose
-
The goals of the project are:
- Learn how to read/write a "binary file" in C/C++ (this can be done in Java, but if you're using Java, you have to figure out how to do this).
- To convert a binary MIPS instruction to a string.
- To convert a MIPS instruction given as a string to an unsigned int.
-
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
-
Collaboration Policy
- This project should be done invidividually. You may discuss ideas, but not exchange or view each other's code.
-
Specifications
-
You will be given a file called Translate.h and
Load.h. The specifications are in the following link.
Translate Specification
Load Specification
Implement the methods. You may add helper methods, if you want.
-
Format of instructions
-
Note: || means concatentation
Note: 016 means 16 zeroes.
Note: PC refers to the program counter
Note:- rs stored at B25-21
- rt stored at B20-16
- rd stored at B15-11
Note:
- immed values for addi are written in signed base 10, but stored in 16-bit 2's complement.
- immed values for logical operations (andi, xori, etc.) are written in unsigned base 10, and stored in unsigned binary.
- Labels for jump instructions will be written in hexadecimal with a leading 0x followed by 8 hex digits. Use the low 26 bits, and store there.
- Labels for branch instructions will be written in signed base 10 and stored in 16-bit 2's complement.
Note: Bits are numbered so that B0 is the least signficant bit and B31 is the most significant bit.
Note: Minimum instructions needed to pass primary: add, addi, beq, j, jal, or, ori. You need to translate to and from.
Command Explanation add $rd, $rs, $rt - Reg[ d ] = Reg[ s ] + Reg[ t ]
- R-type instruction
- B31-26 = 000000 (SPECIAL)
- B10-6 = 000000
- B5-0 = 100000 (ADD)
addi $rt, $rs, immed - Reg[ t ] = Reg[ s ] + (immed15)16 || immed15-0
- I-type instruction
- B31-26 = 001000
- Immediate value is sign extended
sub $rd, $rs, $rt - Reg[ d ] = Reg[ s ] - Reg[ t ]
- R-type instruction
- B31-26 = 000000 (SPECIAL)
- B10-6 = 000000
- B5-0 = 100010 (SUB)
and $rd, $rs, $rt - Reg[ d ] = Reg[ s ] & Reg[ t ]
- Bitwise AND
- R-type instruction
- B31-26 = 000000 (SPECIAL)
- B10-6 = 000000
- B5-0 = 100100 (AND)
andi $rt, $rs, immed - Reg[ t ] = Reg[ s ] & 016 || immed15-0
- I-type instruction
- B31-26 = 001100
- Immediate value is zero extended
or $rd, $rs, $rt - Reg[ d ] = Reg[ s ] | Reg[ t ]
- Bitwise OR
- R-type instruction
- B31-26 = 000000 (SPECIAL)
- B10-6 = 000000
- B5-0 = 100101 (OR)
ori $rt, $rs, immed - Reg[ t ] = Reg[ s ] | 016 || immed15-0
- I-type instruction
- B31-26 = 001101
- Immediate value is zero extended
xor $rd, $rs, $rt - Reg[ d ] = Reg[ s ] ^ Reg[ t ]
- Bitwise XOR
- R-type instruction
- B31-26 = 000000 (SPECIAL)
- B10-6 = 000000
- B5-0 = 100110 (XOR)
xori $rt, $rs, immed - Reg[ t ] = Reg[ s ] ^ 016 || immed15-0
- I-type instruction
- B31-26 = 001110
- Immediate value is zero extended
beq $rs, $rt, LABEL - if ( Reg[ s ] == Reg[ t ] ) jump to LABEL else go to next instruction
- I-type instruction
- B31-26 = 000100
- offset is B15-0
- Jump to PC + [ (offset15)14 || offset || 02 ]
- i.e., the offset is shifted to the left by 2, then sign extended.
bne $rs, $rt, LABEL - if ( Reg[ s ] != Reg[ t ] ) jump to LABEL else go to next instruction
- I-type instruction
- B31-26 = 000101
- offset is B15-0
- Jump to PC + [ (offset15)14 || offset || 02 ]
- i.e., the offset is shifted to the left by 2, then sign extended.
slt $rd, $rs, $rt - if ( Reg[ s ] < Reg[ t ] ) Reg[ d ] = 0311 else Reg[ d ] = 032
- R-type instruction
- B31-26 = 000000 (SPECIAL)
- B10-6 = 000000
- B5-0 = 101010 (SLT)
slti $rd, $rs, immed - if ( Reg[ s ] < (immed15)16 || immed15-0) Reg[ d ] = 0311 else Reg[ d ] = 032
- I-type instruction
- B31-26 = 001010
jr $rs - R-type instruction (sort of)
- B31-26 = 000000 (SPECIAL)
- B20-6 = 000 0000 0000 0000
- B5-0 = 000100 (JR)
j LABEL - PC <- PC31-28 || immed || 02
- immed is 26 bit value
- J-type instruction
- B31-26 = 000010
jal LABEL - PC <- PC31-28 || immed || 02
- immed is 26 bit value
- Reg[ 31 ] <- PC + 4 (In the real MIPS, it should be PC + 8, but that's mostly because of pipelining--we use the simpler PC + 4, which is the next instruction).
- J-type instruction
- B31-26 = 000011
lw $rt, offset($rs) - I-type instruction
- offset is sign-extended to 32 bits, and added to Reg[ s ] to produce address. The content of that address (which must be word-aligned), is placed in Reg[ t ]
- B31-26 = 100011
- B15-0 is the offset
lbu $rd, offset($rs) - I-type instruction
- offset is sign-extended to 32 bits, and added to Reg[ s ] to produce address. The content of that address (which does NOT have to be word-aligned), is placed in Reg[ d ]
- B31-26 = 100100 (CORRECTED)
- B15-0 is the offset
sw $rt, offset($rs) - I-type instruction
- offset is sign-extended to 32 bits, and added to Reg[ s ] to produce address. The content of Reg[ t ] is saved at that address (which must be word-aligned)
- B31-26 = 101011
- B15-0 is the offset
sb $rt, offset($rs) - I-type instruction
- offset is sign-extended to 32 bits, and added to Reg[ s ] to produce address. The content of Reg[ t ] is saved at that address (which does NOT have to be word-aligned)
- B31-26 = 101000
- B15-0 is the offset
lui $rt, immed - I-type instruction
- Reg[ t ] = immed || 016
- B31-26 = 001111
- B25-21 = 00000 (normally where rs goes, but leave it all zeroes)
bgtz $rs, LABEL - I-type instruction
- B31-26 = 000111
- B20-16 = 00000
- Let offset = B15-0
- PC-relative addressing. Let target = (offset15)14 || offset || 02
- PC <- PC + target
bgez $rd, LABEL - I-type instruction
- B31-26 = 000001 (REGIMM)
- B20-16 = 00001 (BGEZ)
- Let offset = B15-0
- PC-relative addressing. Let target = (offset15)14 || offset || 02
- PC <- PC + target
bltz $rd, LABEL - I-type instruction
- B31-26 = 000001 (REGIMM)
- B20-16 = 00000 (BLTZ)
- Let offset = B15-0
- PC-relative addressing. Let target = (offset15)14 || offset || 02
- PC <- PC + target
blez $rd, LABEL - I-type instruction
- B31-26 = 000110
- B20-16 = 00000
- Let offset = B15-0
- PC-relative addressing. Let target = (offset15)14 || offset || 02
- PC <- PC + target
sll $rt, $rs, shift_amt - R-type instruction
- Shift left logical
- B10-6 is the shift amount (between 0-31)
- B31-26 = 000000 (SPECIAL)
- B5-0 = 000000 (SLL)
- Shift a copy of Reg[ t ] left by shift_amt bits, inserting zeroes into the low order bits.
srl $rd, $rt, shift_amt - R-type instruction
- Shift right logical
- B10-6 is the shift amount (between 0-31)
- B31-26 = 000000 (SPECIAL)
- B5-0 = 000010 (SRL)
- Shift a copy of Reg[ t ] right by shift_amt bits, inserting zeroes into the high order bits.
|
See the class syllabus for policies concerning email Last Modified: Wed Jun 5 10:38:37 EDT 2002 |
|
|
|
|
|
|
|
c m s c 311
f a l l 2 0 0 2 |
Purpose
The goal of this project is to translate instructions to and from a binary representation. A rather useful function for you to use is: write a function which takes an unsigned int and translates it to a 32 character string consisting of 0's and 1's.The only thing you have to be careful about is that C++ strings number the characters from left to right (i.e. index 0 in the MSB), while "real" bitstrings number right to left (index 0 is the LSB).
You will need to implement the following two functions:
Public Methods
| static string binToStringInstr( unsigned int instr ) ; |
| The instruction is represented as a 32 bit unsigned int (thus, it's in "machine language" format). Translate this to the appropriate string (thus, if the instruction means "add $r1, $r2, $r3", that's the string that should be returned. Return the string "UNKNOWN" if you can't tell what instruction it is. |
| static unsigned int stringToBinInstr( string instr ) ; |
|
The instruction is now written as a string. Convert this to
an unsigned int. For example, the string could be
"add $r1, $r2, $r3". You should translate the string to an unsigned
int which is the machine language translation of "add".
You should handle:
|
Location of File
Go to ~chf11001/Proj/P2/, and there should be Translate.h. Those implementing it in Java should make the appropriate conversions.|
See the class syllabus for policies concerning email Last Modified: Fri Sep 27 19:41:52 EDT 2002 |
|
|
|
|
|
|
|
c m s c 311
f a l l 2 0 0 2 |
Purpose
The purpose is to load a series of unsigned int (32 bits) from a file. The file will have a 32 bit value (0xdabedabe). As you read it in, it may have been stored in the same endian-ness as your machine or a different endian-ness. (Imagine you have downloaded this file from somewhere on the web, but don't know what endian-ness the machine was).If you read in an unsigned int equal to 0xdabedabe, then this must mean the file is the same as yours. If it's some other value, then it must be a different endian-ness.
Public Methods
| static vector<unsigned int> loadValues( const string & fileName ) ; |
|
If the file exists (in the current directory), read in the first
unsigned int, and determine the endian-ness. If this is the
same as your machine's endian-ness, read the rest of the values
normally. Thus, if there are N * 4 bytes in the file, you will
read in (N - 1) unsigned int values (after the initial 4 byte
header with 0xdabedabe), and store them in a vector of unsigned ints.
If the endian-ness is not the same as your machine, then you still read in the N - 1 values, but then afterwards, you must convert the values so they are the same endian-ness as your machine. (Thus, for each unsigned int, you must swap bytes 0 and 3 and bytes 1 and 2, assuming byte 0 is the least significant byte, and byte 3 is the most significant byte). If the file does not exist, then just return an empty vector. You can assume that there is at least 8 bytes in the file if it does exist (i.e., it has the 4 byte header plus at least one 4 byte integer). |
| static bool writeValues( const string & fileName, vector<unsigned int> values, bool isBigEndian ) ; |
|
In this version, you will write out the values given the endian-ness.
Add the header as needed (0xdabedabe). This may involve swapping bytes.
If you read in the file, then call this function with the same endian-ness
as the file, then print out the file, you should get the equivalent file
(you can run "diff" to see if they result in the same binary).
If the file exists, then return false, and don't do anything. |
Location of File
Go to ~chf11001/Proj/P2/, and there should be Load.h. Those implementing it in Java should make the appropriate conversions.|
See the class syllabus for policies concerning email Last Modified: Fri Sep 27 19:41:52 EDT 2002 |
|
|
|
|
|
|
|
c m s c 311
f a l l 2 0 0 2 |
TENTATIVE
(as of September 18, 2002)
-
Instructor
-
Name Charles Lin Section 0101 Lecture Time 5:00 PM-6:15 PM Mon/Wed Email clin@umd5.umd.edu Phone 405-2709 Only call the instructor for administrative matters (e.g., you are sick and can't make the exam). You should not call about project debugging/homeworks or extensions. See TAs for that. Email is generally preferable, instead of calling.
-
Office Hours
- W 2:15-3:15, Th 11:15-12:15, F 2:15-4:15
-
Description
-
Prerequisite: CMSC 214 with a grade of C or better and CMSC 250 with a
grade of C or better and permission of department.
Topic Introduction to assembly language. Design of digital logic circuits. Organization of central processors, including instruction sets, register transfer operations, control microprogramming, data representation, and arithmetic algorithms. Memory and input/output organization.
-
Texts
-
- Text:
- Computer Organization & Design: The Hardware/Software
Interface, David Patterson &
John Hennessy, Second Edition, Morgan Kaufmann, 1997.
ISBN: 1558604286
This is the required textbook. Sorry that it is so expensive. You may wish to share textbooks with a friend or buy a used textbook. This is NOT the same textbook as the one used in CMSC 411 (although the authors are the same).
Teaching Assistants
- Kinga Dobolyi (kinga@cs.umd.edu)
- Stuart Fletcher (stuart@cs.umd.edu)
Office Hours
TBAKinga and Stuart hold office hours in AVW 1151, which is the TA room. Kinga's office hours are 12:30-2:30 on Tuesday and Thursdays. Stuart's office hours are 1-3 PM on Mondays and Fridays.
Dr. Preston's TA is Konstantinos Bitsakos, and he holds his hours 10:15-12:15 on Tuesdays and Thursdays.
Dr. Kruskal's TA is Anuradha Penmetcha, and she holds her hours 1-4 on Mondays.
These TAs are available for all courses. However, 311 TAs are better for project questions, which can also be emailed to the instructor.
Webpage
http://www.cs.umd.edu/class/fall2002/cmsc311/
It is your responsibility to read the webpage often.
In addition to this webpage, Dr. Hugue has provided a large number of resources on her main CMSC 311 including old homeworks, exams, etc.
Posting Account
Course Grading Policy
- Midterms: 30% each
- Final: 40%
Your final grade is also based on projects given throughout the semester.
Basically, two grades are computed.
-
Method 1
-
If you pass the primaries of the required projects
(currently, Project 0 through Project 4 are "required"),
plus possibly passing secondaries (this will be decided
during the semester), you will receive a "check" indicating
you have completed the minimum requirements of the projects.
You will have grades computed based on the percentages of exams given above.
-
Method 2
-
You will also be given points on the projects. Your grades
will be based on your relative ranking with other students
in the course. More than likely this means grading on
some 100 point scale (or similar), and then determining
letter grades for projects.
The project grades will then count as 20% of your grade. The scores are combined with exam grades (exams are scaled to 80%), and then your grade with projects are counted.
Also, if you receive an F using Method 1, then no matter what you do on projects, the best you can do is a D.
Homeworks/Readings
Solutions to text problems and additional HW problems are available on Dr. Hugue's CMSC 311 website.
Additional problems may be provided to help you prepare for exams.
In addition, you are expected to read the textbook. While many students find such a task painful (often because English is a second language), it is, nevertheless, an important skill to learn, and it's better to learn now than later.
Projects
- Project 0. Tokenizing project. Mostly to make projects 1 through 3 easier.
- Project 1. Number conversion, reading binary files, etc. Writing simulated registers.
- Project 2. MIPS project 1. Reading in a basic MIPS file, and determining addresses of data segment. Also, translation of some instructions from binary to MIPS.
- Project 3. MIPS project 2. Being able to simulate the actual instructions.
- Project 4. Writing a MIPS assembly language program which will run on the simulator you wrote.
Then, there is the optional projects.
- Project 5. MIPS project 3. Converting the assembly to binary format. Being able to read and write from a file. Loading the binary format into memory. Disassembler.
- Project 6. MIPS project 4. Simulation of hardware. (Unlikely to occur this semester).
The optional projects may make the project grade worth more than the 20%. They are likely to be graded independently of the other projects (for example, if it's worth 10% more, you will get a numeric grade for the 10%). Generally, if you get something working that looks reasonable, you will get a good grade on this section.
Project Late Policy
Exams
Makeups will only be given to students with valid documentation. If you are sick, you must have a doctor state dates of incapacitation. In particular, it must state (1) the date which you were incapacitated, (2) and that you were too sick to attend classes).
You must contact the instructor via email/phone as soon as possible. If the instructor is contacted over a week after the exam has been given, you may receive a 0 on the exam, for failing to contact the instructor in a timely manner.
Requests for regrades on an exam must be made IN WRITING within a week of the exam being handed back. If such a request is not made within a week, the instructor reserves the right not to regrade the exam.
Academic Honesty Statement
Please carefully read and consider the Computer Science Department policy regarding the use of computer systems, and the Office of Information Technology's policy regarding acceptable use of computer accounts provided for instructional use, in the Spring 2002 issue of the departmental newsletter, CS Tid-Bits, handed out with this syllabus. Note in particular the penalties for impermissible cooperation on programming projects, which is a violation of the University's Code of Academic Integrity. Any evidence of unacceptable use of computer accounts or unauthorized cooperation on exams or projects will be submitted to the appropriate authorities or to the Student Honor Council, which could result in an XF for the course, suspension, or expulsion from the University.
NOTE SPECIFICALLY that projects are to be done INDIVIDUALLY, unless otherwise specified by your instructor IN WRITING TO ENTIRE CLASS (verbal assurances don't count). For academic honesty purposes, projects are to be considered comparable to an extended take-home exam. That is, any cooperation or exchange of ideas which would be prohibited on an exam is also prohibited on a project assignment. Working IN ANY WAY with another student will be considered a violation and WILL BE REPORTED to the Honor Council. Students may not discuss pseudocode, design of a program or of individual functions, coding of individual functions, or any high-level code with anyone except the instructors and teaching assistants. Should you have difficulty with a programming assignment you should see your instructor or the teaching assistants in office hours, NOT solicit help from anyone else in violation of these rules. Students are welcome to study together or to receive help in learning the course concepts from any others, but exams and projects are to be solely and entirely each student's own work.
VIOLATIONS OF ACADEMIC HONESTY INCLUDE:
- failing to do all or any of the work on a project by yourself, other than assistance from the instructional staff.
- using any ideas or any part of another student's project, or copying any other individual's work in any way.
- giving any parts or ideas from your project, including test data, to another student.
- having programs on an open account or on a PC that other students can access.
- transferring any part of a project to or from another student or individual by any means, electronic or otherwise.
- publishing any of your code publicly (e.g., via a webpage) which other students can access, even if the project has already been completed.
IT IS THE RESPONSIBILITY, UNDER THE UNIVERSITY'S HONOR POLICY, OF ANY
STUDENT WHO LEARNS OF AN INCIDENT OF ACADEMIC DISHONESTY TO REPORT IT
TO THEIR INSTRUCTOR.
Working in Teams
Also, for your benefit, you should indicate who your team member is early on. Thus, if you are a team member, and you change your mind, and break the team up, and there is similar code between you and a former team member, you will still be considered violating academic integrity.
You may also work individually on projects. For now, working individually does not confer any benefits. However, this may change, depending on the project description.
Course Topics (SUBJECT TO CHANGE)
This list may vary according to the pace of lecture topics.
| Overview (1 lecture) |
- Introduction.
- General Overview of Computer Organization (CPU, Memory, Fetch-Decode-Execute Cycle)
| Number Represenation (5 lectures) |
- What's a bit, byte, bitstring?
- Conversion to and from base 10 from arbitrary base.
- Binary, Octal, Hexadecimal
- Unsigned binary
- Signed decimal: 9's complement, 10's complement
- Signed binary: 1's complement, 2's complement, signed magnitude
- Binary Coded Decimal
- How many bitstrings given N bits?
- Range of numbers given N bits?
- Floating Point Representation
- Simple Addition/Subtraction
| Combinational Logic (5 lectures) |
- Gates and Identities
- Combinational Circuit Parts
- MUX, DeMUX
- Encoder, Decoder
- Half Adder, Full Adder
- Carry Lookahead Adder
- Shifter (Rotator)
- Design of ALU
| Sequential Logic (5-7 lectures) |
- D, JK, and T flip flops
- Sequential Circuit Parts
- Registers
- Synchronous, asynchronous counters
- Register Files
- Design with finite state machines with output (Mealy/Moore)
- PLAs/ROMs used in design
| Assembly Language |
- MIPS assembly language
- Encoding of instructions in binary
- Basic MIPS architecture
- Translation of C program snippets to MIPS
- Addressing modes
| Datapath and Control (4-5 lectures) |
- How an assembly language instruction is executed
- Internal bus
- Control Units
- Register Transfer Language
- Microprogramming
| Memory |
- RAM
- Interleaved memory
- Cache
- Virtual Memory
- Direct Memory Access (DMA)
| Random Topics |
- Interrupts
- Bitwise operators in C
- Shift operators in C
- I/O devices
| Pipelining (2 lectures) |
- Basics of Pipelining
- Amdahl's Law (not really pipelining...)
|
|
c m s c 311
f a l l 2 0 0 2 |
The Memory Hierarchy
-
The following is a ordering of "memory" (i.e., places to store
bits) from fastest to slowest:
- Registers
- RAM (physical memory)
- Disk
The rule of thumb for memory is this: As memory gets quicker and quicker, the cost is more expensive (per byte), and the total number of bytes decreases.
For example, registers are the quickest memory, but typically you have very little of it (for example, MIPS has 32 integer registers). There's typically more RAM (these days, even 1 G of RAM is not too uncommon), but it's much slower than accessing information stored in registers, but it is cheaper per byte than registers.
Finally, there's disk (20 G or more is not uncommon), which is slower than RAM, and there's a lot of it, and it's cheapest of all the memory (per byte).
Thus, if you want faster memory, it's going to cost you, and you can't get too much of it. This is a combination of both economics and physics.
The Need for Cache
-
The goal of computer hardware designers is to make hardware
go as fast as possible. There are two ways to do this. Either
you do a brute force approach: make everything faster (via new
technology), or you make a few observations about the kind of
operations and the kind of data you are working on, and make
hardware faster by being smart about what needs to get
faster.
RISC architectures were proposed and developed in the early 1980s. The ideas behind RISC architecture were:
- Use lots of registers (32 to 128 registers common).
- The only instructions that work with memory should be load/store instructions (i.e., don't add a register to the contents of a memory location).
- Keep instructions simple and few, so the hardware that implements it can be simple (preferably, one instruction per clock cycle).
- Don't have complicated instructions that do a lot, but take many clock cycles.
- Have instructions be equal width (same number of bytes per instruction).
In particular, because each instruction is "simple", the amount of code is expected to increase. Thus, you might have, say, 300 instructions to run instead of 250. As you might guess, running more instructions takes more time than running fewer instructions.
The hope is to execute each of those 300 instructions much faster than the 250 instructions. Some of that comes with making simple instructions, but some of it also comes from placing the instructions in cache.
So, the simple idea is this. Create a fast memory that sits between the physical memory and the registers. This fast memory is a subset of the data that is stored in physical memory. It acts as a middle man.
Here's the analogy. Imagine you are in a large digital library (which represents RAM or physical memory). You sit at a study carrel (a desk with some space for CDs) and have a bunch of CD books. Let's say the carrel can hold up to 20 CDs, each CD being a copy of some "book" in the digital library.
Unfortunately, the technology isn't perfect. When you don't have the CD of the book you want, you must go to the librarian and ask for the book to overwrite the CD you have. So, it's slow if you must go to the librarian to do this.
Thus, when you want to get a book, the first thing you do is to see if you have it in the shelf in the study carrel. If it's there, you access it quickly and begin to read. If it's not there, you have to go the librarian to get the book "burned" on a CD, and that takes time.
This analogy is reasonably close to what happens between cache and RAM, where the study carrel acts as the cache (fast, small subset of the library) and the library itself represents RAM.
Why Cache Works
-
Why does cache increase the speed of programs? Let's go
back to the analogy and see where it might fail.
So there you are in your study carrel, needing to write (or type) a paper on the ancient history of Rome. As you write, you need to read and refer to books. As long as the CDs are sitting in the carrel this is quick.
However, as time passes, you may have to write on the history of China, and because most of your CDs are about the history of Rome, you need to get those new books. Even though they take some time to get the books you needed copied, once you have them, it's pretty speedy.
Now imagine that you don't have a report, and you happen to like to read books rather randomly. One day you read part of one book, then another day, you read another part of another book. You rarely read the same book twice, and you rarely read the entire book.
In this case, having all the CDs in the study carrel doesn't save much time. You're always having to go to the librarian to make new copies.
Yet, for a typical person, this probably doesn't happen very often. You can often leave the books you want in the carrel, and will refer to them quite often. Thus, the study carrel does help you out, because it allows you to get access to frequently needed CDs fast.
It turns out programs also behave in a similar fashion. In particular, programs exhibit the following two properties:
- spatial locality If your program accesses
address X, it is like to access X +/- Delta (where Delta is a small
number). That is, it is likely to access addresses near X.
This property occurs both in data and instructions. For example, most assembly language code is straight-line code. That is, you execute the instructions in order, one after another. Occasionally, you do a branch or a jump instruction. Even so, these often jump or branch to nearby parts of the code.
With data, many programmers commonly program with arrays. Arrays are usually stored contiguous in memory. Thus, all the addresses are quite near each other.
- temporal locality If your program accesses
address X now, it is likely to access address X in the near future.
Again, this property occurs both in data and instructions. For example, in instructions, you are often running loops. Thus, the addresses of the instructions are accessed over and over again.
And these loops are often accessing the same data over and over again (for example doing some complicated processing of data in arrays).
How can caches take advantage of spatial locality? Since you know you are likely to access addresses near X, then fetch the data in a large block near X. Instead of fetching the byte stored at address X, fetch 64 bytes that include address X, which is faster than accessing the 64 bytes one at a time.
How can you take advantage of temporal locality? Place the frequently used data in cache to begin with. Since that data is faster to access than RAM, and since the data is likely to be accessed in the near future, you make the program faster.
Typically, you have two sets of caches: an instruction cache and a data cache. Both have spatial and temporal locality, but don't overlap that much with each other's addresses.
- spatial locality If your program accesses
address X, it is like to access X +/- Delta (where Delta is a small
number). That is, it is likely to access addresses near X.
How Cache Works
-
To begin, let's establish some terminology (some of this is
borrowed from a book by Murdocca).
- A cache consists of 2k slots.
- Each slot consists of:
- A valid bit (referred to as "V"), indicating whether the tag is valid or not.
- A dirty bit (referred to as "D"), indicating whether the data block has been modified.
- The tag which indicates which data block is in a slot.
- The data block which consists of 2m bytes (copied from RAM).
Here's the idea. Suppose a user wants to access address A31-0. This address might be the address of some data in memory, or it might be the address of an instruction to be fetched.
Since the data block contains 2m bytes, we will fetch this many bytes, instead of fetching one (or four) bytes at address A31-0.
For now, let's assume m=8, so each data block consists of 256 bytes.
How do we get those 256 bytes? We need 256 consecutive addresses. The easiest way to accomplish this is follows.
- A31-8 0000 0000
- A31-8 0000 0001
- ....
- A31-8 1111 1111
A31-8 is the upper 24 bits of the original address A31-0 that we want to access. We come up with all 28 = 256 ways of writing an 8 bit value. Combine A31-8 with 8 more bits to get a 32 bit address.
Procedure for accessing data
When an address is generated, the first step is to determine if the data exists in the cache (similar to a person checking to see if the CD is in the study carrel). This is done by searching through the cache (using hardware) to see if it's there.If there, then you have a cache hit. The data is returned to the main CPU. If not, then you have a cache miss (similar to not having the CD in the study carrel, and having to go to the librarian).
This means, you need to fetch the data from RAM (this is done in hardware).
In the process of fetching the data from RAM, you will need to pick a slot to place the data. If all slots are being used, one of the slots must be "evicted", which typically means copying the data back to RAM, and using the slot for the current data being requested.
An entire data block is fetched from RAM, placed in the slot, and the tag updated accordingly.
How this is done depends on the kind of cache you have.
Fully Associative Cache
There are three kinds of cache schemes: fully associative cache, direct mapped cache, and set associative cache.In a fully associative cache, when we fetch a 256 byte data block, it can go into any slot. When the hardware looks to see if the data is one of the slots, it checks to see if the tag of the slot matches the tag of the address.
If the address is B31-0, then B31-8 is the "tag" portion of the address, and B7-0 is the offset. The number of bits in the offset is the log of the number of bytes in the data block. Since the data block has 256 bytes, the number of bits in the offset is 8 (which is log2256).
The hardware checks each slot to see if it has a tag that equals B31-8 (which means the tag is 24 bits).
It also checks to see if V=1 (the valid bit is true). If V=0, this means the tag is meaningless and data block contains garbage bits.
If there is a slot that matches the tag portion of the addres and is valid (there can be at most one such slot), then the offset B7-0 is used as the index into the data block. Since the offset is 8 bits, you can access one of 256 addresses, which is, of course, the number of bytes in the data block.
If there is no such slot, then the data is fetched from memory. In particular, you fetch bytes from address B31-8 0000 0000 all the way up to B31-8 1111 1111 (that's 256 addresses) and place them in a slot.
Which slot should be picked? It depends. If there is a slot that's not valid, then that one should be picked.
If all slots are valid, there's a variety of schemes to use. You can try to pick a slot where D = 0. This would mean the slot is not dirty (i.e., the data block hasn't been modified).
The advantage of picking such a block is that you don't have to write this back to RAM, which saves time. The disadvantage is that this block may be a block that's frequently accessed.
A better strategy may be to determine which slot hasn't been used in a while. In order to do this, you need to keep more information than the slots currently store. In particular, you need to keep something like an "age" counter. An age counter can be, say, a 2 bit counter.
If the slot hasn't been acccessed in a certain time period, the counter is incremented. If the counter reaches 11, it stays at 11. If the slot is accessed, the counter is reset back to 00.
When picking a slot to evict, pick a slot with the largest age counter.
Such schemes (i.e. using age counters) are more likely to be seen when using virtual memory. Virtual memory uses the disk as additional memory. Think of RAM as a kind of cache for disk. When some data doesn't appear in RAM, you look for it on disk. The main difference between RAM and disk vs. cache and RAM is the speed. Disk is very slow to access compared to RAM.
Direct Mapped Cache
To understand fully-associative caches, it's helpful to understand direct mapped caches. In a fully associative cache, any slot can be used to store a data block.In a direct-mapped cache, only a single slot can be used to store a data block.
So, how is that slot determined?
Assume each slot has a slot number. Assume we have 64 slots. The slots are number 0 to 63. With 64 slots, you need 6 bits to identify the slot.
We get these 6 bits from the address. So, if the address is B31-0, then B31-14 is the tag, B13-8 is the slot number (6 bits), and B7-0 is the offset as before.
You might wonder why we picked B13-8 as the slot number. Couldn't we have picked any other 6 bits from bits B31-8? You could have, but usually the further right the bits, the more likely that the values are to vary. You want a lot of variance so that different addresses get mapped to different slots.
If this scheme reminds you of hash tables, it's very similar. If you use the high 6 bits (i.e., B31-26), then you are likely to always pick the same slot, which is like hashing to the same bucket. Picking bits low down tends to make the data spread out more across the different slots.
Thus, B13-8 uniquely determines the slot where the data block must go.
This is similar to having a parking lot with 100 parking spots number 00 through 99 and using the middle two digits of your student ID to select a parking spot. Thus, if your middle 2 digits is 23, then you can only park in spot 23.
The drawback of this scheme is clear. What if many students have 23 as the middle 2 digits, yet, very few have any of the other 2 digits? Then, there may be empty parking spaces, yet you're not allowed to park there (this happens frequently with apartment complexes which assign only one parking spot per apartment---you may have several people living at the apartment, each with their own car, yet only one of you can park in the slot, and others have to park far away---even if other people's parking slots are empty).
The main advantage of this scheme is that it's simpler to implement (uses less hardware) than a fully associative cache.
Set Associate Cache
A set-associative cache is somewhere in between the two schemes. Suppose we have 64 slots. We put each slot in a set. Let's assume there are 8 sets, each containing 8 slots.We break the address up differently.
B31-11 is the tag (23 bits), B10-8 is the set number (3 bits), and B7-0 is the offset as before.
In a set associative scheme, you use B10-8 to identify one of 8 sets (numbered from 000 to 111).
How do you decide which of the 8 slots to pick within the set? At this point, it becomes fully associative within the set. You can pick any of the 8 slots you want.
Again, the parking lot analogy is useful. Assume that there are still 100 parking spots, but you use the last digit of your student ID. There are only 10 possible values using your last digit. However, there are 10 parking spots for each digit (thus 10 assigned to digit 0, 10 assigned to digit 1, etc).
So, now you have a choice of 10 different spots based on the last digit.
As you can see, the set-associative scheme combines ideas from fully associative and direct mapped.