The goal of this assignment is to allow you to self-assess whether you are prepared to take this class. As such, even if you do not plan to do the assignment until after the drop deadline, you should look at it and think about it, to make sure you are comfortable with what I am asking you to do.There are a variety of sub-goals to this project, all related to the major goal. You will get some initial experience with Typescript, use a simple data structure common in graphics (a circular buffer), gain experience with the common structure of interactive graphical program (not specific to the web), implement a solution to a small geometric problem, and (not least of which) ensure your development and debugging environments are set up before the first larger assignment.Your assignment is to complete the implementation of app.ts so that the program behaves as demonstrated in class and described here and in the code comments. The result should look like this:## RequirementsHere are some details requirements and guidance for what we expect.1. app.ts contains a starting point for the code for this example, you will complete it. We’ve left in a lot of useful code that we don’t want you to have to implement, and marked two places (with TODO comments) that you will want to add code. You will need to create some new methods as well, to handle things like computing midpoints of lines and recursively drawing triangles. 2. pointset.ts contains the PointSet class that you should use to keep track of a fixed maximum number of mouse points. You do not need to modify this, but should make sure you understand it (as a self-assessment tool). PointSet implements as a circular buffer, as described in the comments in the file. The key feature of a circular buffer is that the contents of the buffer are never moved or copied as new elements are added or removed. Instead, the index markers for the start and end are updated. This is a common data structure in interactive applications, because it gives direct access to each element of the buffer, does not require allocations or copying, or many small allocations of memory that may fragment memory (and trigger the garbage collector in a dynamic language like Javascript). The interface methods of the class hide the implementation details from the programmer: they can simply request the first, second, third, etc. element as desired. 3. your program should create one “point” per animationFrame and store 30 points (1 second worth of data at 30 frames per second, 1/2 a second at 60 fps, and so on). The points should be rendered such that they appear to fade out as the mouse moves, by setting the alpha value of the color being used to increasing levels of transparency based on the number of points. New points should not be created when the mouse is outside of the canvas, but old ones should continue to disappear until they are all gone. 4. when the user clicks and drags, a grey hollow rectangle should be traced out from the start point to the current mouse location as the mouse moves and the button is held. 5. when the user releases the button, a rectangle with a thick black border should be drawn that is the same size and location as the final grey rectangle drawn when dragging the mouse. It should contain two lines that cross the center from the four corners, creating four triangles. 6. information needed to redraw the rectangle should be saved (the corners). A random color should be created and saved with this rectangle. 7. if the user moves the mouse out of the canvas before releasing the button, the rectangle creation should be canceled. 8. inside each of the first 4 triangles, a new triangle of should be drawn using the rectangle’s assigned color. Each new triangle should use the mid-points of each of the sides of the enclosing triangle as it’s corners. 9. additional triangles will be created recursively based on the size of the rectangle (see more details on what should be drawn, below). 10. the canvas should be redrawn each animation frame, with each of the created rectangles being rendered. Nothing should be drawn in the canvas outside of the render function.## RecursionBased on the size of the original rectangle, you will recursively draw more triangles inside the empty triangles created when a triangle is drawn. Each time a triangle is drawn inside another triangle, it subdivides the triangle into 4 equal triangles: the center one being filled (the “drawn” triangle) and 3 empty ones that share a vertex with the enclosing triangle.Based in the size of the rectangle, you will recursively drawn a new triangle inside each of these 3 empty triangles, meaning 3 more triangles are drawn for each triangle in the step above.When a triangle is drawn inside another triangle, it should have a black border (like the enclosing triangle), and be filled with the color that was randomly chosen when the rectangle was created. The color assigned to the rectangle should not change over time, but each time you recursively draw more triangles, their color should be slightly darker than then the triangle containing themThe number of recursion steps based on size of the rectangle the user drew. Consider the “size” to be the smaller of the width and height of the rectangle. If the size is > 128, you should recurse one step after the initial 4 colored triangles. For each power of two above 128, you should recurse one more step (256 = 2 steps, 512 = 3 steps). 0, 1, and 2 recursion steps are shown in the image below.The first column shows rectangles whose width and height are less than 128 each (sized at 163×103, 90×74, 28×25), as does the short rectangle on the bottom of the second column (sized at 265×74). The top of the second column shows 1 recursive step (size 234×180), with each of the original empty triangles containing a slightly darker green triangle. The third column shows 2 recursive steps (size 508×350).Your grade will be based on satisfying each of these requirements, according to the rubric above.# SubmissionYou will check out the project from github classroom, and submit it there. The project folder should contain just the additions to the sample project that are needed to implement the project. Do not add extra files, and do not remove the .gitignore file (we do not want the “node_modules” directory in your repository.)**Do Not Change the names** of the existing files (e.g., index.html, app.ts, etc). The TAs need to be able to test your program as follows:1. cd into the directory and run “`npm install“` 2. run with “`npm run dev“` 3. visit “`http://localhost:3000/index.html“`Please test that your submission meets these requirements. For example, after you check in your final version of the assignment to github, check it out again to a new directory and make sure everything builds and runs correctly.## Development EnvironmentThe sample has already been set up with a complete project for Typescript development.To work with this sample and prepare your submission, you should have Node (and in particular, npm) installed, which you can retrieve from [nodejs.org](http://nodejs.org). (We recommend first installing nvm [[Mac/Linux](https://github.com/nvm-sh/nvm)] [[Windows](https://github.com/coreybutler/nvm-windows)] and using it to install node.)You do not need to install anything else globally, as typescript and all the tools will be installed inside your project.This project uses [Vite](https://vitejs.dev/), a fast, lightweight, modern build-and-dev tool that leverages [Rollup](https://rollupjs.org/guide/en/) as its bundler and supports hot-module-replacement.## Running and DebuggingThe development environment for vite is run using the npm “dev” script in the package.json file, using “`npm run dev“`. This starts the vite server, and should show you something like “` vite v2.4.4 dev server running at:> Local: https://localhost:3000/ > Network: use `–host` to exposeready in 384ms. “` You can then access the server from your web browser at the listed url (“`https://localhost:3000“` in this case).Vite supports hot-module-replacement, so when you edit and save any file in your project, the program will be reloaded in your browser.You can use your browser’s development tools for debugging.
This project is designed to give you experience in writing multi-threaded programs by implementing a simplified MapReduce-style wordcount application. By working on this project: • You will learn to write multi-threaded code that correctly deals with race conditions. • You will carry out a simple performance evaluation to examine the performance impact of (i) the degree of parallelism in the mapper stage and (ii) the size of the shared buffer which the two stages of your application will use to communicate. Figure1: Overview of our Mapreduce-style multi-threaded wordcount application. As covered briefly in Lecture 22, the wordcount application takes as input a text file and produces as output the counts for all uniquely occurring words in the input file arranged in an alphabetically increasing order. We will assume that the words within our input files will only contain letters of the English alphabet and the digits 0-9 (i.e., no punctuation marks or other special characters). Our wordcount will consist of two stages. The 1 first stage, called ”mapper,” reads individual words and produces key-value pairs of the form (word, 1).The second stage, called the ”reducer” consumes these, groups them by key, and sums up the counts in each group to produce the final output. Notice how the first stage can be parallelized. That is, the mapper stage can consist of multiple mapper threads, each working on its own separate portion of the input file. The reducer stage only contains a single thread which runs concurrently with the mapper threads. The communication between the mapper threads and the reducer thread occurs via a shared in-memory FIFO buffer. Figure 1 summarizes these ideas.2 Starter code: unsynchronized word-count We are providing you starter code that implements a preliminary version of wordcount that works correctly in the absence of multi-threading. To appreciate this, you should confirm that this code is able to pass the ”serialize” test in which accesses to the buffer occur in a strictly serial manner (i.e., an operation is issued only upon the completion of the previous operation). However, our implementation is not thread-safe. That is, it has race conditions. You will need to enhance this code to create a thread-safe version of wordcount. 3 What you need to implement Take the time to skim all the starter source code files. All your implementation will be confined to the files helper.c and helper.h. Specifically, you need to consider enhancing the following functions (recall that the provided versions of these functions work correctly in the absence of multi-threding).Though we have implemented the buffer_create function for you, you can enhance it to make any kind of initialization. • state_t* buffer_create(int capacity): creates an in-memory buffer with the specified capacity in bytes). Returns a pointer to state_t, see definition in helper.h. This function will be called once at the beginning, you can do any kind of initialization in it based on your implementation. • enum buffer_status buffer_send(state_t *buffer, void* data): writes data to the buffer. In case the buffer is full, the function waits till the buffer has space to write the new data. Returns BUFFER_SUCCESS for successfully writing data to the buffer, CLOSED_ERROR if the buffer is closed, and BUFFER_ERROR on encountering any other error. The size of data can be found out using the function get_msg_size(data).• enum buffer_status buffer_receive(state_t* buffer, void** data): Reads data from the given buffer and stores it in the function’s input parameter, data (Note that it is a double pointer). This is a blocking call i.e., the function only returns on a successful completion of receive In case the buffer is empty, the function waits till the buffer has some data to read.2 • enum buffer_status buffer_close(state_t* buffer): closes the buffer and informs (you may think of giving signal) all the blocking send/receive calls to return with CLOSED_ERROR. Once the buffer is closed, send/receive operations will return CLOSED_ERROR. Returns BUFFER_SUCCESS if close is successful, CLOSED_ERROR if the buffer is already closed, and BUFFER_ERROR for other errors. • enum buffer_status buffer_destroy(state_t* buffer) Frees all the memory allocated to the buffer , using own version of sem flags The caller is responsible for calling buffer_close and waiting for all threads to finish their tasks before calling buffer_destroy Returns BUFFER_SUCCESS if destroy is successful, DESTROY_ERROR if buffer_destroy is called on an open buffer, and BUFFER_ERROR in any other error case4 Programming rules You are not allowed to take any of the following approaches to complete the assignment: • Spinning in a polling loop to implement blocking calls.• Sleeping instead of using condition-wait. • Trying to change the timing of your code to overcome race conditions. • Using global variables. You are only allowed to use the pthreads library, the standard C library functions (e.g., malloc/free), and the provided starter code. If you think you have a valid reason to use some code outside of these, please contact the course staff to determine its eligibility. 5 Testing your code Your code will be evaluated for correctness, properly handling synchronization, and ensuring it does not violate any of the programming rules from the previous section. We are providing several test cases which are located in test.py—you can find the list of tests at the bottom of the file. Although we are providing you all the tests that are part of our default plan for grading your work, we reserve the right to employ additional tests during the final grading if the need arises. Therefore, you are responsible for ensuring your code is correct, where a large part of correctness is ensuring you don’t have race conditions, deadlocks, or other synchronization bugs.Running the make command in your project will create two executable files: wordcount and wordcount sanitize. • The default executable is wordcount. If you want to run a single test, run the following: ./wordcount [test_case_name] [iters], where [test_case_name] is the test name and [iters] is the number of times to run the test. If you do not provide a test name, all tests will be run. The default number of iterations is 1. 3 • The other executable, wordcount_sanitize, will be used to help detect data races in your code. It can be used with any of the test cases by replacing ./wordcount with ./wordcount_sanitize. Any detected data races will be output to the terminal. You should implement code that does not generate any errors or warnings from the data race detector. • Valgrind is being used to check for memory leaks, report uses of uninitialized values, and detect memory errors such as freeing a memory space more than once. To run a valgrind check by yourself, use the command: valgrind -v –leak-check=full ./wordcount [test case name] [iters].Note that wordcount sanitize should not be run with valgrind as the tools do not behave well together. Only the wordcount executable should be used with valgrind. Valgrind will issue messages about memory errors and leaks that it detects for you to fix them. You should implement code that does not generate any valgrind errors or warnings. To run all the supplied test cases, simply run the following command in the project folder: ./test.py. This runs all of the provided tests to autograde your assignment. 6 Performance evaluation Your performance evaluation will study the impact of two parameters: (i) the number of mapper threads and (ii) the size of the shared memory buffer via which the mapper threads communicate with the reducer thread. For one of the input files provided by us, you will report how execution time varies with (i) and (ii) in the ranges described below. For your performance evaluation, you will be using wordcount in a ”custom” mode (wherein the custom_eval() function is used).You may additionally use this mode for any custom input files you may want to test your code with. Here is the usage of wordcount in this custom mode: ./wordcount custom eval #mapperthreads buffersize infile outfile. For example if you want to run wordcount with 2 mapper threads, a buffer size of 100B, input file perf eval.txt and output file perf out.txt, you will execute: ./wordcount custom eval 2 100 perf eval.txt perf out.txt. To measure the execution time, simply use the time command. For example: time ./wordcount custom eval 2 100 perf eval.txt perf out.txt. You will conduct your performance evaluation on a W204 machine on the input file named perf eval.txt that we are providing you.You are to vary the parameters (i) and (ii) as follows: • number of mapper threads ∈ {1, 2, 4, 8, 16, 32} with size of buffer 1000 B, • size of buffer ∈ {100 B, 1000 B, 10000 B} with 8 mapper threads. You will write your results in a README file. The format of the README file as follows. The README file appears in the root of the repository. You should begin by filling in the name and email of each member of your group on the specified lines at the beginning of the README. The README has several sections for you to fill in. Each section has some text describing what you should write in that section.You should replace that text with your 4 own response for that section. For reporting your experimental results, you will find 9 lines starting with ’@Test:’. Each of these lines has the format: @Test: , , For example: @Test: 1, 100, On each of these lines replace the field with the execution time (in microseconds) you found for this choice of parameters. You are to take the minimum of 5 runs for each such number that you report. Do NOT include units (us). Do NOT edit any other part of this line. For example, if the minimum time value was 20 for the experiment with 1 mapper and buffer size of 100 B: @Test: 1, 100, 20 7 Submission instructions Similar to the last assignment, we will be using GitHub for managing submissions, and you must show your partial work by periodically adding, committing, and pushing your code to GitHub. This helps us see your code if you ask any questions on Piazza (please include your GitHub username) and also helps deter academic integrity violations.Additionally, please input the desired commit number that you would like us to grade in the Canvas assignment that will be created closer to the submission deadline. You can get the commit number from GitHub. In your repository, click on the commits link to the left above your files. Find the commit from the appropriate day/time that you want committed. Click on the clipboard icon to copy the commit number. Note that this is a much longer number than the displayed number. Paste your very long commit number and only your commit number in the assignment submission textbox.8 Grading Your score for the project will consist of two parts: • Part A: 80% of your grade will depend on the various test cases we are providing. • Part B: The remaining 20% will be based on the results of your performance evaluation from Section 6. There are 33 test cases (numbered 0-32) worth a total of 100 points. You only need to score 80 points to meet the entire 80% corresponding to Part A. Anything above 80 will be BONUS. So you can score up to 20 bonus points (i.e., a total score of 120/100) if you are able to pass all the test cases. You will receive zero points if: • You violate the academic integrity policy (sanctions can be greater than just a 0 for the assignment) 5 • You break any of the programming rules • Your code does not compile/build • Your code crashes the grading script • You don’t show your partial work by periodically adding, committing, and pushing your code to GitHub 9 Hints and resources • Make it a habit to ALWAYS do a git pull before starting work on your code. This will help you in both avoiding possible conflicts as well as you will be updated with any possible updates that we may push. We do not expect to make any updates to the source code after our initial release but there is always a chance we may need to.Similalry, there is a chance we may want to add an extra test that we realize is interesting for you to pass. We will always announce any such update on Canvas but your habit of pulling the latest version of the repo will make things easier. • An excellent tutorial on the pthreads library appears at which you may find useful: https://computing.llnl.gov/tutorials/pthreads/. • Carefully read the output from the sanitizer and valgrind tools and think about what they’re trying to say. Usually, they’re printing call stacks to tell you which locations have race conditions, or which locations allocate some memory that was being accessed in the race condition, or which locations allocate some memory that is being leaked, etc. These tools are tremendously useful, which is why we have set them up for you for this assignment.• While these tools are very useful, they are not perfect. Some race conditions are rare and don’t show up all the time. A reasonable approach to debugging these race condition bugs is to try to identify the symptoms of the bug and then read your code to see if you can figure out the sequence of events that caused the bug based on the symptoms. • Debugging with gdb is a useful way of getting information about what is going on in your code. To compile your code in debug mode (to make it easier to debug with gdb), you can simply run: make debug. It is important to realize that when trying to find race conditions, the reproducibility of the race condition often depends on the timing of events. As a result, sometimes, your race condition may only show up in non-debug (i.e., release) mode and may disappear when you run it in debug mode. Bugs may sometimes also disappear when running with gdb or if you add print statements. Bugs that only show up some of the time are still bugs, and you should fix these. Do not try to change the timing to hide bugs.6 • If your bug only shows up outside of gdb, one useful approach is to look at the core dump (if it crashes). Here’s a link to a tutorial on how to get and use core dump files: http://yusufonlinux.blogspot.com/2010/11/debugging-core-using-gdb.html • If your bug only shows up outside of gdb and causes a deadlock (i.e., seems to hang forever), one useful approach is to attach gdb to the program after the fact. To do this, first run your program. Then in another command prompt terminal run: ps aux. This will give you a listing of your running programs. Find the PID for your program. Then within gdb (may require sudo) run: attach PID. This will give you a gdb debugging session just like if you had started the program with gdb. 10 Important reminder To finish the project successfully, you must start early and be proactive about seeking clarifications from the instructors. As with all projects in this class, you are not permitted to: • Use code from outside sources without citing (Internet, previous class projects, etc.) • Share code with other teams or post parts of your code publicly where others could find and use them (e.g., Piazza).You are responsible for protecting your work from falling into the hands of others. • Allow anyone outside your team to write any part of the code for this assignment. If there is any question at all about what is acceptable, ask the instructor. Above all, be honest. This always goes a long way. We will run a code comparison tool on all submitted code to determine if there has been any sharing between teams. Any teams found out to be sharing code will receive a 0 for the lab.
The goals for this project are to help you: 1. Get experience working with a trace-based event-driven simulator 2. Get experience with a basic virtual memory management system (including MMU, TLB, DRAM, DRAM-resident multi-level page tables, page replacement algorithms, and swap device) 3. Get experience with simulation-based performance evaluationYou will implement and experiment with a simple virtual memory manager (VMM) consisting of the following elements: (i) MMU, (ii) TLB, (iii) DRAM, (iv) DRAM-based multi-level page tables, and (iv) disk-based swap device. To do this, you will be given a simulator base code. If you have never worked with a simulator, do not worry. Much of the simulator functionality will be already implemented in the base code allowing you to focus on ideas related to VMM. Additionally, be sure to check out a short video that has been uploaded in canvas announcements – wherein we describe all you need to know to quickly become familiar with the base code.Our base code simulates multiple processes time-sharing a single CPU with the help of the operating system which implements a round-robin CPU scheduler. The code base has been written to work for processes that only execute non-memory instructions. For each simulated process, the simulator reads the instructions from an “input trace file” for that process. You will extend this to simulate the time-sharing of processes that also execute memory instructions (such as loads and stores) that access virtual addresses that need to be translated into their physical counterparts by the MMU.As input, you will receive two types of files: input files and traces. These files are present in the ‘traces’ folder. Where to find the simulator base code The simulator base code is in the simulator.c file. You can compile it using the make command. Then, to run the simulator, you need to write the following command: $ ./simulator input1.txt output1.txt Where input1.txt is the input file and output1.txt will contain the output from running the simulator.Simulator Inputs Our simulator takes two types of inputs for each simulation (henceforth also called “experiment”): (i) system parameters and (ii) a scheduling trace for each process involved in the experiment. These inputs are specified within a file that is passed as a command line argument to the simulator. So for an input file called input1.txt, the simulator would be invoked as follows, where the output will be written to output1.txt. More details on compiling and running the simulator appear under “Using the Simulator” $ ./simulator input1.txt output1.txtThe format of an input file is as follows: # list of system parameters specified as parameter-descriptive-string parameter-value; (all latencies are in units of a “cycle”) # list of parameters that will remain the same across all experiments Non-mem-inst-length 1 Virtual-addr-size-in-bits 32 DRAM-size-in-MB 4 TLB-size-in-entries 16 TLB-latency 1 DRAM-latency 100 Swap-latency 10000000 Page-fault-trap-handling-time 10000 Swap-interrupt-handling-time 10000 TLB-type FullyAssociative TLB-replacement-policy LRU # list of parameters that may vary across experiments P-in-bits 12 Num-pagetable-levels 3 N1-in-bits 8 N2-in-bits 8 N3-in-bits 4 Page-replacement-policy LRU Num-procs 3 # trace-file-name arrival-time-of-process process1 0 process2 3 process3 4 The processes are in order, meaning that each process has a start time later than or equal to the previous start time.Code for parsing this file will be provided with the functions openTrace(), closeTrace(), readNextTrace() and readSysParam() in fileIO.h/c files. The traces are: “input1.txt”, “input2.txt”, …., “input10.txt”. Process trace files contain a list of addresses accessed by a program. The process trace file names will correspond to trace-file-name.txt from input trace files. So in the above example the “input1.txt” points to the 3 process file – “process1.txt”, “process2.txt” and “process3.txt”. ‘Mem’ or ‘NonMem’ is used to define the type of instructions.Here is an example of the first few lines within a process trace file: Total-num-instr 1000000 Mem 0x12f00C00 Mem 0x77f46B77 NonMem Mem 0x7ffde001 Mem 0x12f0015C NonMem Mem 0x77f3c000 Mem 0x12f00C28 NonMem NonMem NonMem NonMem Mem 0x12f00010 Mem 0x12f0CC11 Mem 0x12f00100C Mem 0x77f3CDE1 …Code for parsing this file will be provided with the functions openTrace(), closeTrace(), readNumIns() and readNextMem() in fileIO.h/c files. The process traces are available for each process in the traces: “process1.txt”, “process2..txt”, …., “process44.txt”.We have simulated the Round Robin process scheduler in the schedulingRR() function. This is the only scheduler you need to work with. The base code simulates NonMem instructions ONLY and generates the following upon the completion of an experiment: 1. per-process completion time 2. total number of context switches 3. total amount of time spent in OS vs. total amount of time spent in user mode.The current implementation works with “input1.txt” and “input10.txt” only which has all NONMEM instructions. “input1.txt” has 3 processes: process1, process2 and process3. Each of these processes have 2, 2 and 3 NonMem instructions respectively.Use the following commands to execute the simulator: Make ./simulator input1.txt output1.txt [here input1.txt is the trace parameter you wish to experiment with, output1.txt is the file name where the output will be written] Make clean will delete all object files.The execution order of the processes in “input1” are: process1 → process2 → process3 → process2 → process3; where quanta = 5 and nonMemReadTime = 2. The below diagram shows the execution order of the 3 processes in “input1”:You are required to append to this simulator to take care of all types of instructions and generate the following: [You can use traces 2-9 as reference to test your code] 1. per-process completion time 2. total number of context switches 3. total number of disk interrupts 4. per-process and total number of TLB misses (absolute and ratios) 5. per-process and total number of page faults (absolute and ratios) 6. per-process and total fraction of time in blocked state 7. total amount of time spent in OS vs. total amount of time spent in user mode.To that end, you would have to implement data structures for TLB and page table and include necessary functions and helper data structures. You must assume that the swap device has sufficient capacity to accommodate the active address spaces in their entirety in any experiment. You will assume that the capacity needs of the page tables themselves are accommodated by main memory other than the DRAM that the simulator considers (but that it has similar latency characteristics). You will ignore the main memory needs of the page tables themselves in your simulation of DRAM usage. You will assume that all the memory instructions in the trace files reference valid virtual addresses and, therefore, do not raise traps. All page table entries must be aligned to 4 Bytes. Besides the PPN, you only need to consider the valid bit within a PTE. All of these other PTE entries in a real page table are to be ignored: permissions, user/kernel, dirty, reference.Provided Code Structure ● dataStructures.h file contains the structs used in this project. You can add other structures here. ● fieIO.h/c file contains the helper functions for reading the traces. ● gll.h/c contains a linked list implementation for ease. It has been used in the existing code and you are welcome to use it for your linked list implementation.● simulator.h/c contains the code for the simulator. You are expected to include your implementation in this file. There are //TODO instructions that give you some guidance about adding your implementation specific values in existing functions. You are expected to determine how to include your implementation yourself.○ init() initializes all the data structures and list of processes. processList is the list of all processes. Any process that becomes ready to run is moved to readyProcess list. The process that should run right now is moved to runningProcess list. You should initialize your necessary variables/data structures here.○ simulate() function is the simulator which loops through all the processes until all of them are done. It calls the processSimulator() function in a loop. processSimulator() simulates the running process until one of these things happen- timer interrupt, disk interrupt, page fault, process finishes. processSimulator() calls readIns() function that reads the next instruction for the running process. You have to handle “MEM” instructions in readIns() function.○ diskToMemory() function moves one page from disk to memory. You have to implement it. To implement these functions, you will need to implement TLB and page table along with MMU and swapping logic. You would also need to implement multiple page replacement algorithms(described in next section).● Recommended order of implementation: ○ MMU, DRAM, swap device, Page table only with no TLB ○ Add TLB ○ Performance evaluation.Page Table Implementation (40%) In this part of the assignment you need to implement a multi level page table with the following page replacement policies: ● Optimal: The page that will not be used for the longest period of time in the future is to be removed ● LRU: The least recently accessed page is the one to be removed.● Clock: You should maintain a clock hand that rotates around memory. Each physical page is marked “unused”. Each time a page is needed, the hand advances until it finds a page marked “unused”, at which time that page is chosen for eviction. If it finds a page marked “used” in this process, the page is changed to be “unused”. In addition, on every memory reference, the page accessed should be marked “used”.TLB Integration (20%) In this part of the assignment you need to implement a simulation of the Translation Look-aside Buffer (TLB) that uses the LRU replacement algorithm.Performance Study (40%) After completing and testing your implementation so far, you will conduct two types of experiments. You will describe your findings in a project report (doc or pdf). We first describe these two types of experiments followed by the contents of your project report (large parts of the project report may be a google form where they will simply type in their outputs. If you can do this, it will greatly automate grading).Experiment type 1: In these experiments, you will simply run your simulator with the following inputs and report the outputs 1-7 described under “What you need to do”: ● List of system parameters to use comes here. Choose LRU for page replacement policy. ● List of process mixes to consider comes here. Give them 5-6 mixes of increasing complexity. ● Ideally you would provide them a fixed format (it could even be a google form to automate grading)Experiment type 2: In these experiments, you will vary certain parameters and study the impact on specified quantities. You will plot graphs to convey your findings in your report. You will use the XXX process mix for all of these experiments ● Keeping all other parameters the same as in Experiment type 1, vary p from 12 to 20 and plot the following: (i) average process completion time, (ii) per-process and total number of TLB misses (absolute and ratios), (iii) per-process and total number of page faults (absolute and ratios), and (iv) DRAM internal fragmentation. Choose the number of bits for all 3 page table levels to be as close to equal as possible.● Keeping all other other parameters the same as in Experiment type 1, vary the number of levels in the page table from 1 to 3 and plot the following: (i) average process completion time and (ii) page table size per process. Choose the number of bits for the different levels within multi-level page tables to be as close to equal as possible.● Keeping all other other parameters the same as in Experiment type 1, compare all outputs 1-7 with the page replacement policy being Optimal and Clock vs. LRU. Report: Your report will consist of the graphs described above with a few (at most 5) sentences interpreting your findings for each graph (What trend did you expect based on your understanding from lectures/textbook? Does the trend match your expectation?)Handin Instruction You will upload the commit ID that you want us to grade via canvas. The project report should be pushed to your repository (pdf/ doc format). Programming Rules ● IMPORTANT: You can enhance the PCB data structure. ● IMPORTANT: You need to create the MMU, TLB, DRAM, page tables, swap data structures from scratch. ● IMPORTANT: You must show your partial work on this assignment by periodically committing and submitting (i.e., pushing) your code to git. This will be used both for grading the checkpoints as well as ensuring academic integrity. Hints ● In addition to the usual scanning of provided code to understand how it works, we also encourage you to run it with provided traces (ones without any Mem instructions) as well as traces you construct yourself and use the observed behavior to help understand how it simulates a multi-tasked system. ● We encourage you to use the calculations you have seen in lectures and Exam 1 to create first-order models. You can use the estimates offered by these models to check whether your simulator’s output appears to be in the right range or if it is way off which may be indicative of bugs in your code.
In this lab, you will be writing a dynamic storage allocator for C programs, i.e., your own version of the malloc, free, and realloc functions. You are encouraged to explore the design space creatively and implement an allocator that is correct, space efficient, and fast. The only file you will be modifying is mm.c. Modifications in other files will not be used in the grading. You will be implementing the following functions: • bool mm init(void) • void* malloc(size t size) • void free(void* ptr) • void* realloc(void* oldptr, size t size) • bool mm checkheap(int lineno) You are encouraged to define other (static) helper functions, structures, etc. to better structure your code. • IMPORTANT: You are required to implement a heap checker (see Section 5) that will be graded. The heap checker will help you debug your code. • IMPORTANT:You are required to write commentsfor all of your code including the heap checker. Additionally, you need to write a file comment at the top of the file describing your overall malloc design. See Section 7 for grading details. • IMPORTANT: You must show your partial work on this assignment by periodically committing and submitting (i.e., pushing) your code to git. This will be used both for grading the checkpoints as well as ensuring academic integrity. • You are not allowed to change any of the interfaces inmm.c. • You are not allowed to invoke any memory-management related library calls or system calls. For example, you are not allowed to use sbrk, brk, or the standard library versions of malloc, calloc, free, or realloc. Instead of sbrk, you should use our provided mem sbrk. • Your code is expected to work in 64-bit environments, and you should assume that allocation sizes and offsets will require 8 byte (64-bit) representations. • You are not allowed to use macros as they can be error-prone. The better style is to use static functions and let the compiler inline the simple static functions foryou. • You are limited to 128 bytes of global space for arrays, structs, etc. If you need large amounts of space for storing extra tracking data, you can put it in the heaparea. • IMPORTANT: Failure to abide by these requirements may result in a 0 for the assignment. • mm init: Before calling malloc, realloc, calloc, or free, the application program (i.e., the tracedriven driver program that will evaluate your code) calls your mm init function to perform any necessary initializations, such as allocating the initial heap area. The return value should be true on success and false if there were any problems in performing the initialization. • malloc: The malloc function returns a pointer to an allocated block payload of at least size bytes. The entire allocated block should lie within the heap region and should not overlap with any other allocated chunk. If the requested size is 0 or if mem sbrk is unable to extend the heap, then you should return NULL. Similar to how the standard C library (libc) always returns payload pointers that are aligned to 16 bytes, your malloc implementation should do likewise and always return 16-byte alignedpointers. • free: The free function frees the block pointed to by ptr. It returns nothing. This function is only guaranteed to work when the passed pointer (ptr) was returned by an earlier call to malloc, calloc, or realloc and has not yet been freed. If ptr is NULL, then free should do nothing. • realloc: The realloc function returns a pointer to an allocated region of at least size bytes with the following constraints. – if ptr is NULL, the call is equivalent to malloc(size); – if sizeis equal to zero, the call is equivalent to free(ptr); – if ptr is not NULL, it must have been returned by an earlier call to malloc, calloc, or realloc. The call to realloc changes the size of the memory block pointed to by ptr (the old block) to size bytes and returns the address of the new block. Notice that the address of the new block might be the same as the old block, or it might be different, depending on your implementation, the amount of internal fragmentation in the old block, and the size of the reallocrequest. The contents of the new block are the same as those of the old ptr block, up to the minimum of the old and new sizes. Everything else is uninitialized. For example, if the old block is 8 bytes and the new block is 12 bytes, then the first 8 bytes of the new block are identical to the first 8 bytes of the old block and the last 4 bytes are uninitialized. Similarly, if the old block is 8 bytes and the new block is 4 bytes, then the contents of the new block are identical to the first 4 bytes of the oldblock. These semantics match the the semantics of the corresponding libc malloc, realloc, and free functions. Run man malloc to view complete documentation. The memlib.c package simulates the memory system for your dynamic memory allocator. You can invoke the following functions in memlib.c: • void* mem sbrk(int incr): Expands the heap by incr bytes, where incr is a positive non-zero integer. It returns a generic pointer to the first byte of the newly allocated heap area. The semantics are identicalto the Unix sbrk function, except that mem sbrk accepts only a non-negative integer argument. You must use our version, mem sbrk, for the tests to work. Do not use sbrk. • void* mem heap lo(void): Returns a generic pointer to the first byte in the heap. • void* mem heap hi(void): Returns a generic pointer to the last byte in the heap. • size_t mem heapsize(void): Returns the current size of the heap in bytes. • size_t mem pagesize(void): Returns the system’s page size in bytes (4K on Linux systems). • void* memset(void* ptr, int value, size t n): Sets the first n bytes of memory pointed to by ptr to value. • void* memcpy(void* dst, const void* src, size t n): Copies n bytes from src to dst. Dynamic memory allocators are notoriously tricky beasts to program correctly and efficiently. They are difficult to program correctly because they involve a lot of untyped pointer manipulation and low-level manipulation of bits and bytes. You will find it very helpful to write a heap checker mm checkheap that scans the heap and checks it for consistency. The heap checker will check for invariants which should always be true. Some examples of what a heap checker might check are: • Is every block in the free list marked asfree? • Are there any contiguous free blocks that somehow escapedcoalescing? • Is every free block actually in the free list? • Do the pointers in the free list point to valid free blocks? • Do any allocated blocks overlap? • Do the pointers in a heap block point to valid heapaddresses? You should implement checks for any invariants you consider prudent. It returns true if your heap is in a valid, consistent state and false otherwise. You are not limited to the listed suggestions nor are you required to check all of them. You are encouraged to print out error messages when the check fails. You can use dbg printf to print messages in your code in debug mode. To enable debug mode, uncomment the line #define DEBUG. To call the heap checker, you can use mm checkheap( LINE ), which will pass in the line number of the caller. This can be used to identify which line detected a problem. You are required to implement a heap checker for your code, both for grading and debugging purposes. See Section 7 for details on grading. 6 Testing your code First, you need to compile/build your code by running: make. You need to do this every time you change your code for the tests to utilize your latest changes. To run all the tests after building your code, run: make test. To test a single trace file after building your code, run: ./mdriver -f traces/tracefile.rep. Each trace file contains a sequence of allocate, reallocate, and free commands that instruct the driver to call your malloc, realloc, and freefunctions in some sequence. Other command line options can be found by running: ./mdriver -h To debug your code with gdb, run: gdb mdriver. 7 Evaluation You will receive zero points if: • you break any of the programming rules in Section2 • your code does not compile/build • your code is buggy and crashes the driver Otherwise, your grade will be calculated as follows: 50 pts Checkpoint 1 (Due: Sun., Feb. 28, 11:59:59 PM): This part of the assignment simply tests the correctness of your code. Space utilization and throughput will not be tested in this checkpoint. Your grade will be based on the number of trace files that succeed. 100 pts Checkpoint 2 (Due: Sat., Mar. 06, 11:59:59 PM): This part of the assignment requires that your code is entirely functional and tests the space utilization (60 pts) and throughput (40 pts) of your code. Each metric will have a min and max target (i.e., goal) where if your utilization/throughputis above the max, you get full score and if it is below the min, you get no points. Partial points are assigned proportionally between the min and max. – Space utilization (60 pts): The space utilization is calculated based on the peak ratio between the aggregate amount of memory used by the driver (i.e., allocated via malloc or realloc but not yet freed via free) and the size of the heap used by your allocator. You should design good policiesto minimize fragmentation in order to increase this ratio. – Throughput (40 pts): The throughput is a performance metric that measures the average number of operations completed per second. As the performance of your code can vary between executions and between machines, your score as you’re testing your code is not guaranteed. The performance testing will be performed on the W204 cluster machines to ensure more consistent results. 100 pts Final submission (Due: Fri., Mar.12, 11:59:59 PM): This part of the assignment is graded identically as Checkpoint 2, except that the grading curve has not been significantly reduced as is the case with Checkpoint 2. 50 pts Code demo and comments (Due: Fri., Mar. 12, 11:59:59 PM): As part of the final submission, we will be reviewing your heap checker code and commentsthrough your code. You will need to upload a 4-5 minute demo video describing your design choice, data structures and heap checker code and upload it on canvas (one demo video per team). The TAs can ask you to schedule an appointment to meet them via zoom to answer additional questions about your project after the deadline, if necessary. Your heap checker will be graded based on correctness, completeness, and comments. The comments should be understandable to a TA. The demo will show correctness. Your explanation of the heap checker and your malloc design will determine the degree to which your checker is checking invariants. There will be a balance between space efficiency and speed (throughput),so you should not go to extremes to optimize either the space utilization or the throughput only. To receive a good score, you must achieve a balance between utilization and throughput. Grades will be assigned by running your code on W204 machines. So, please check that your code runs on those machines. 8 Handin Instructions You must show your partial work on this assignment by periodically committing and submitting (i.e., pushing) your code to git. To do this, run: git add mm.c git commit -m “Write a comment here about your code changes” git push We will use the latest submission before each deadline as well as the latest submission before each late deadline for grading purposes. Each checkpoint and final submission can use the late policy, and we will calculate and use the better of the normal score and the late score with the late penalty. Thus, make sure you are committing and submitting to git often. If you want to specify a commit for a specific checkpoint, write it in your readme file. You have to submit your demo video as an assignment (Project 2) on Canvas. Additionally, you must submit your github username that you used for the assignment in Canvas (You should have done this for project 1. No need to re-submit.). 9 Hints • Use the mdriver -f option. During initial development, using tiny trace files will simplify debugging and testing. We have included some trace files ending in -short.rep that you can use for initial debugging. • Write a good heap checker. This will help detect errors much closer to when they occur. This is one of the most useful techniques for debugging data structures like the malloc memory structure. • Use gdb; watchpoints can help with finding corruption. gdb will help you isolate and identify out of bounds memory references as well as where in the code the SEGFAULT occurs. To assist the debugger, you may want to compile with make debug to produce unoptimized code that is easier to debug. To revert to optimized code, run make release for improved performance. Additionally, using watchpoints in gdb can help detect where corruption is occurring if you know the address that is being corrupted. • The textbooks have detailed malloc examples that can help your understanding. You are allowed to reference any code within the textbooks as long as you cite the source (as comment in your code). However, directly copying code from online source is strictly forbidden. • Encapsulate your pointer arithmetic and bit manipulation in static functions. Pointer arithmetic in your implementation can be confusing and error-prone because of all the casting that is necessary. You can reduce the complexity significantly by writing static functions for your pointer operations and bit manipulation. The compiler should inline these simple functions for you. • Use git to track your different versions. git will allow you to track your code changes to help you remember what you’ve done in the past. It can also provide an easy way to revert to prior versions if you made a mistake. • Use the mdriver -v and -V options. These options allow extra debug information to be printed. • Start early! Unless you’ve been writing low-level systems code since you were 5, this will probably be some of the most difficult and sophisticated code you have written so far in your career. So start early, and good luck!
This programming assignment (PA1) has three main goals. First, you will learn in concrete terms what the different segments of a virtual address space (or simply address space) are. Second, you will learn to use three Linux facilities – /proc, strace, and getrusage – to record/measure certain aspects of process resource usage. Finally, we hope that PA1 will serve to refresh your understanding of (or make you learn in case you lack it): (i) logging into a Linux machine (ssh, VPN, 2FA) and using basic Linux shell and commands, (ii) compiling a C program (gcc, make), creating/linking against libraries, (iii) debugging (gdb), (iv) working with a code repository (github), (v) using Linux man pages (the man command), and (vi) plotting experimental data for easy visualization. All of these are good programming and experimental analysis practices that we would like you to follow throughout this course (and beyond it).After accepting the invitational link to the Github Classroom @CMPSC473, you will be given access to your own private repository and another repository named ”PA1” containing all the files needed for completing PA1. When you open this repository, you will find 5 folders, named prog1, …, prog5. These folders contain the files described in Section3. On the web-page of this repository, you will find a link to download it. To download copy the link and type on the command line: $ git clone You will find additional information on using GitHub and other important documents uploaded in a separate document on canvas. As mentioned in class, you may do the bulk of your work on any Linux (virtual) machine of your choosing. However, the results in your report (which will be used for grading your work) must be carried out on CSE department’s Linux-based teaching machines. These machines are named cse-p204instxx.cse.psu.edu (where xx is a machine number). The reason for asking you to report results on these machines is to 1 have relative consistency/uniformity in your measurements – this would help us grade in a consistent manner and identify possible bugs/shortcomings.1. Stack, heap, and system calls: The executable named prog1 contains a function that is recursively called 10 times. This function has a local variable and a dynamically allocated variable. Upon each invocation, the function displays the addresses of the newly allocated variables on the console. After 10 invocations, the program waits for a key to be pressed on the keyboard before concluding. We would like you to observe the addresses displayed by prog1 and answer the following: (a) Which addresses are for the local variables and which ones are for the dynamically allocated variables? How were you able to deduce this? What are the directions in which the stack and the heap grow on your system? (b) What is the size of the process stack when it is waiting for user input? (Hint: Use the contents of /proc/PID/smaps that the /proc file system maintains for this process where we are denoting its process ID by PID. While the program waits for a user input, try running ps -ef | grep prog1. This will give you PID.You can then look at the smaps entry for this process (cat /proc/PID/smaps) to see a description of the current memory allocation to each segment of the process address space. (c) What is the size of the process heap when it is waiting for user input? (d) What are the address limits of the stack and the heap. (Hint: Use the maps entry within the /proc filesystem for this process. This will show all the starting and ending addresses assigned to each segment of virtual memory of a process.) Confirm the variables being allocated lie within these limits. (e) Use the strace command to record the system calls invoked while prog1 executes. For this, simply run strace prog1 on the command line. Look at the man page of strace to learn more about it. Similarly, use man pages to learn basic information about each of these system calls. For each unique system call, write in your own words (just one sentence should do) what purpose this system call serves for this program.2. Debugging refresher: The program prog2.c calls a recursive function which has a local and a dynamically allocated variable. Unlike the last time, however, this program will crash due a bug we have introduced into it. Use the Makefile that we have provided to compile the program. Execute it. The program will exit with an error printed on the console. You are to compile the program with 32 bit and 64 bit options and carry out the following tasks separately for each: (a) Observe and report the differences in the following for the 32 bit and 64 bit executables: (i) size of compiled code, (ii) size of code during run time, (iii) size of linked libraries. 2 (b) Use gdb to find the program statement that caused the error. See some tips on gdb in the Appendix if needed. (c) Explain the cause of this error. Support your claim with address limits found from /proc. (d) Using gdb back trace the stack. Examine individual frames in the stack to find each frame’s size. Combine this with your knowledge (or estimate) of the sizes of other address space components to determine how many invocations of the recursive function should be possible on your system. How many invocations occur when you actually execute the program? (e) What are the contents of a frame in general? Which of these are present in a frame corresponding to an invocation of the recursive function and what are their sizes?3. More debugging: Consider the program prog3.c. It calls a recursive function which has a local and a dynamically allocated variable. Like the last time, this program will crash due to a bug that we have introduced in it. Use the provided Makefile to compile the program. Again, create both a 32 bit and a 64 bit executable. For each of these, execute it. Upon executing, you will see an error on the console before the program terminates. You are to carry out the following tasks: (a) Observe and report the differences in the following for the 32 bit and 64 bit executables: (i) size of compiled code, (ii) size of code during run time, (iii) size of linked libraries. (b) Use valgrind to find the cause of the error including the program statement causing it. For this, simply run valgrind prog3 on the command line. Validate this alleged cause with address space related information gleaned from /proc. (c) How is this error different than the one for prog2?4. And some more: The program prog4.c may seem to be error-free. But when executing under valgrind, you will see many errors. You are to perform the following tasks: (a) Describe the cause and nature of these errors. How would you fix them? (b) Modify the program to use getrusage for measuring the following: (i) user CPU time used, (ii) system CPU time used – what is the difference between (i) and (ii)?, (iii) maximum resident set size – what is this?, (iii) signals received – who may have sent these?, (iv) voluntary context switches, (v) involuntary context switches – what is the difference between (iv) and (v)? Look at the sample code in the Appendix for an example on how to use getrusage().5. Multi-process program that uses fork, exec, wait, kill, exit calls: Compile the multi-process program prog71 using the makefile or using the following commands. $ gcc -g prog72.c -o prog72 $ gcc -g prog71.c -o prog71 Execute prog71 as follows $ ./prog71. a) Compare the following for the parent and child processes (i) PID (ii) address of dynamic variables. b) Compare the address space of the parent and child before and after the ”exec” command. (Hint: Run gdb prog71 and add breakpoints at lines 11, 15, 24, 37 in the file ”prog71” and add additional breakpoints in the file ”prog72” at line numbers 17, 21, 32. Helpful commands: ”set follow-fork-mode child” – In this mode, GDB will switch to the child process if a fork() or vfork() is called. ”set detach-on-fork off” – Both processes will be held under GDB control. One process is debugged, while the other is suspended. ”set detach-on-fork on” – The child process (or parent process, depending on the value of follow-fork-mode) will be detached and allowed to run independently. This is the default. ”x/80x $rsp” – Get HEX dump of stack ”backtrace full” – Display backtrace of the entire stack. c) Compare the stack of prog72 before and after signal handling. (Hint: you may try increasing the sleep time at line 33 in prog71, if that is helpful). Attach screenshots of your findings for questions a, b, and c.4 Submission and Grading You will submit all your source files, Makefiles, and READMEs (the last to convey something non-trivial we may need to know to use your code). You are to submit a report answering all the questions posed above into your github repo. PA1 is worth 15 points (amounting to 15 % of your overall grade). Each of the problems is worth 3 points each. The TAs will evaluate your submission based on (i) the quality and correctness of your report and code, and (ii) examining, compiling, and running code modified by you. Appendix We offer some useful hints here.4 • Quick notes on gdb: 1. To run a program prog1 under gdb, simply execute $ gdb prog1 2. While running under gdb’s control, you can add breakpoints in the program to ease the debugging process. To add a breakpoint, type $ break 3. To run the code type $ r 4. To continue running the program after a breakpoint is hit, type $ c 5. To inspect the stack using gdb, type $ backtrace or $ backtrace full (to display contents of local variables) 6. To get information about individual frames, type $ info frame E.g., if you want to see information about frame 5 (assuming your program has made 6 recursive function calls, since frame number starts from 0), then the command would look like $ info frame 5 7. To get size of a frame, subtract frame addresses of two consecutive frames.• To access virtual address space related information for a process with OS-assigned identifier PID, follow these steps: 1. To find PID of, say, prog2, type, $ ps -ef | grep prog2 or, $ pgrep prog2 2. Inspect the contents of the files /proc/PID/maps and /proc/PID/smaps for a variety of useful information. A simple web search will offer details should you find something unclear (or ask us). • Often a system’s administrator will set an upper bound on the stack size. To find this limit: $ ulimit -s Alternatively, you can use the following command to get both ”soft” and ”hard” limits set for a process: $ cat /proc/PID/limits • To compile the code using 32/64 bit options, add the -m flag to the compile command in the Makefile. E.g., to compile with the 32 bit option: $ gcc -g -m32 prog.c -o prog • To find the size of an executable (including its code vs. data segments), consider using the size command. Look at its man pages. 5 • To find the size of code during run time, type the following while the code is in execution: $ pmap PID | grep “total” To see memory allocated to each section of the process, type $ pmap PID • Sample code for using getrusage() : # in clude # in clude # in clude # in clude i n t main ( ) { s t r u c t rusage usage ; s t r u c t timev al s t a r t , end ; i n t i , j , k = 0 ; ge t ru s age (RUSAGE SELF , &usage ) ; s t a r t = usage . ru s time ; f o r ( i = 0 ; i < 1 0 0 0 0 0; i ++) { f o r ( j = 0 ; j < 1 0 0 0 0 0; j ++) { k += 1 ; } } ge t ru s age (RUSAGE SELF , &usage ) ; end = usage . ru s time ; p r i n t f ( ” S t a r t e d a t : %ld .% ld s ” , s t a r t . t v s e c , s t a r t . t v u s e c ) ; p r i n t f ( ”Ended a t : %ld .% ld s ” , end . t v s e c , end . t v u s e c ) ; r e tu rn 0 ; } 6
1. (3 points) Write a higher-order function dncall that takes three parameters: n, f, x; it returns x when n = 0, returns f(f(x)) when n = 1, returns f(f(f(f(x)))) when n = 2, etc. That is, it returns the result of calling f on x, for 2n times. For instance, invoking dncall with n = 2, the add-one function, and x = 2 should return 6.2. (3 points) Write a Scheme keep-if function. It takes two arguments. The first is a boolean function f, and the second is a list l. The keep-if function returns a new list with all elements x in l such that f(x) = #t being kept, while those elements x such that f(x) = #f being removed. For example, (keep-if (lambda (x) (> x 3)) ’(10 1 7 2)) should return the list (10 7), since both 10 and 7 are greater than 3. Define the keep-if function by using case analysis and recursion.3. (3 points) The least function takes a list of numbers, and returns its least element. For example, (least ’(7 3 6 2)) should return 2. Write the least function in Scheme in two steps: (a) Write a least helper function; it takes a number k and a list of numbers, x, as parameters, and returns the number which is smallest among k and numbers in x. For example, (least helper 5 ’(4 5 6)) should return 4. (b) Write the least function based on least helper.4. (5 points) Write a Scheme function to-words that takes an integer between -99 and 99, inclusive, as a parameter and returns a list of words corresponding to the integers reading in English. Make your function as short as possible; i.e., don’t write a COND statement with 200 tests. Example calls to your function are given below: 1 (to-words 13) ; should return (thirteen) (to-words 42) ; should return (forty two) (to-words -55) ; should return (negative fifty five)Note, in order to simplify things, we are not expecting dashes in the output (i.e., 42 is output as forty two not forty-two). Also, if the input number is outside of the range of [-99,99], your program should output ’error. Hint: You may want to use the built-in integer division functions quotient and remainder.5. (10 points) In this question, we are going to develop a Scheme program that calculates relevant word counts. The input is two lists, the first is a list of words to be counted and the second is a list of irrelevant words; the output should be counts for those relevant words that appear in the first input list. For example, if the first input list is ’(time is long but life is short) and the list of irrelevant words is ’(but)Then the output should be ’((short 1) (is 2) (life 1) (long 1) (time 1)) Note that you are not asked to sort the words in the output. Therefore, the output is correct as long as the counts are correct.Do the following steps to implement the program. In our discussion, we call a word with a count a word-count pair, for example, (short 1) and (is 2) are word-count pairs. We call a list of word-count pairs a word-count list. (a) (2 points) Write a function filterWords that takes a list of words and a list of irrelevant words and returns an output list with irrelevant words filtered out. E.g., if the first input list is ’(time is long but life is short) 2 and the list of irrelevant words is ’(but) Then the output should be ’(time is long life is short)You can use the “member?” function we discussed in class, if you find it helpful. (b) (2 points) Write a function iniWordCountList that takes a list of words and creates a word-count list. The resulting word-count list should have the word count 1 for every word. Use the map function we discussed in class to implement iniWordCountList. For instance, (iniWordCountList ’(time is long life is short)) should generate ((time 1) (is 1) (long 1) (life 1) (is 1) (short 1)) (c) (2 points) Write a function mergeWordCounts. It takes two inputs. The first is a word-count pair and the second is a wordcount list. This function generates a new word-count list. If the input word-count pair has a corresponding pair in the word-count list with the same word, then the counts should be merged; otherwise, the output word-count list should have the input word-count list with the word-count pair at the end of the list. For instance, (mergeWordCounts ’(is 1) ’((time 1) (is 1))) should generate ((time 1) (is 2)) As another example (mergeWordCounts ’(life 1) ’((time 1) (is 2))) 3 should generate ((time 1) (is 2) (life 1)) (d) (2 points) Write a function mergeByWord, which takes a wordcount list and produces a new word-count list; the output wordcount list should have one word-count pair for each word that appears in the input list and the count should be the sum of all counts for that word in the input list. For instance, if the input list is ((time 1) (is 1) (long 1) (but 1) (life 1) (is 1) (short 1)) then the output should be ((short 1) (is 2) (life 1) (but 1) (long 1) (time 1)) Write mergeByWord based on the reduce function we discussed in class and mergeWordCounts. The reduce function is not built-in in Scheme; you can type it in yourself: (define (reduce f l v) (if (null? l) v (f (car l) (reduce f (cdr l) v)))) (e) (2 points) Finally, write a relevantWordCount function that takes in a list of words and a list of relevant words, and outputs the right word-count list. Write this function based on filterWords, iniWordCountList, and mergeByWord.Notes For programming assignments, examples are given only for the purpose of clarification. By no means that our tests will solely be based on those examples. It’s your responsibility to thoroughly test your code by designing your own test cases. Chapter 6 of the Scheme standard http://www.schemers.org/Documents/Standards/R5RS/HTML/ contains a list of standard procedures provided by Scheme (for example, the remainder and the square root functions). You may find them helpful during your programming.Submission format: Put all your code into one DrRacket file and submit your file through Canvas. Please clearly mark your answers using comments so that we can tell the correspondence between your code and questions. Please ensure that your file starts with a comment that includes your name and your Penn State network user id.
Your assignment is to use Python to write a recursive descent parser for a restricted form of SQL, the popular database query language. The lexical syntax is specified by regular expressions: Category Definition digit [0-9] letter [a-zA-Z] int + float +.+ id ( | )* keyword SELECT | FROM | WHERE | AND operator = | < | > comma , The concrete syntax is specified by the following E-BNF grammar, where is the start symbol: -> SELECT FROM [WHERE ] -> {, } -> {AND } -> -> | | Here , , and are token categories defined by the regular expressions above, and the terminal symbols SELECT, FROM, WHERE, and AND are of category keyword, while “,” is a terminal symbol with category comma. Note arbitrary whitespace can appear between tokens, and no space is needed between an operator and its operands, or between the items in a list and the commas that separate them.This project is broken down into the following series of tasks.1. (3 points) Write a class Token that can store the value and category of any token. 1 2. (7 points) Develop a lexical analyzer. You should start by drawing on paper a finite state automaton that can recognize types of tokens and then convert the automaton into code. Name this class Lexer and ensure that it has a method nextToken() which returns a Token. Lexer should have a constructor with the signature “ init (self, s)”, where s is the string representing the query to be parsed. As mentioned before, the code for recognizing an identifier should check to see if the terminal string is a keyword, and if so, then the category of the token should be set to keyword, instead of ID. If nextToken() is called when no input is left, then it should return a token with category EOI (EndOfInput). If the next terminal string is not considered a token by the lexical syntax, then return a token with category Invalid.3. (10 points) Write a syntactic analyzer which parses the tokens given by Lexer using the recursive descent technique. Name this class Parser. Like Lexer, Parser should have a public constructor with the signature “ init (self, s)”. This input string should be used to create a Lexer object. There should also be a method “run(self)” that will start the parse. As the program parses the input, Parser should print out the nonterminal that was matched, surrounded by angle-brackets, e.g. . Whenever it applies a new rule, it should indent by a tab. When it has parsed all tokens that constitute a nonterminal, it should print out the nonterminal’s name, preceded by a slash, and surrounded by angle-brackets, e.g. . When a terminal symbol (token) is matched, it should output the token category, surrounded by anglebrackets, the tokens string, and the token category preceded by a slash and surrounded by angle-brackets (e.g. 42).Whenever the parser comes across a token that does not fit the grammar, it should output a message of the form “Syntax error: expecting expected-tokencategory; saw token” and immediately exit. Note, the input string is expected to contain exactly one sentence of the form Query. In order to test your file, you will have to create a test that creates a Parser object then calls the run() method on the object. For example, the code: parser = Parser (“SELECT C1,C2 FROM T1 WHERE C1=5.23”) parser.run() should have the output given in Figure 1. Although it is not important for completing this assignment, you may be interested to know that this output format is well-formed XML. 2 SELECT C1 , C2 FROM T1 WHERE C1 = 5.23 Figure 1: Sample output. Submission format: The electronic version of your program files must be submitted through Canvas.Make sure that your code can be compiled and run on those Linux machines in the Westgate 204 lab (cse-p204inst01.cse.psu.edu to cse-p204inst38.cse.psu.edu). We will grade your submission on those machines. Make sure your code is well tested. We provided one test for your reference, but you should design your own test cases to test your code. Please ensure that your file has a comment that includes your name, Penn State network user id, and a description of the purpose of the file. Please include comments for each method, as well as any complicated logic within methods.
1. (0 points) Go through a brief tutorial about the DrRacket programming environment at http://docs.racket-lang.org/drracket/index. html. Be sure to change the language to R5RS. 2. (3 points) Code the Ackermann function in DrRacket, which is defined as follows: A(m, n) = n + 1 if m = 0 A(m − 1, 1) if m > 0 and n = 0 A(m − 1, A(m, n − 1)) if m > 0 and n > 0 To check your result, use DrRacket to compute the result of A(3, 5), which should be 253. You only need to submit your Scheme code for the Ackermann function. 3. (3 points) John McCarthy is a famous computer scientist who designed LISP. He once proposed a function called the McCarthy 91 function, defined as follows: Mac(n) = ( n − 10 if n > 100 Mac(Mac(n + 11)) if n ≤ 100 Write this function in Scheme. Try calling the function with a few numbers less than 100 and see what the results are. 4. (3 points) Some credit-card companies pay back a small portion of the charges a customer makes over a year. One company returns (a) 0.5% for the first $1000 of charges, 1 (b) 0.75% for the next $1000 (that is, the portion between $1000 and $2000), (c) 1.0% for the next $1500 (that is, the portion between $2000 and $3500), (d) and 1.5% for everything above $3500. Thus, a customer who charges $400 a year receives $2, which is 0.5% * 400, and one who charges $1,400 a year receives $8, which is 5 = 0.5% * 1000 for the first $1000 and 0.75% * 400 = 3 for the next $400. Define the function payback, which consumes a charge amount and computes the corresponding pay-back amount. 2
1. (6 points) Consider the following function written in C: int x=3, y=2, z=1; void foo(int a, int b) { x = x + b; a = a – b; } In each of the cases below, write down the values of x, y and z after the following calls to foo(). If necessary, assume that output arguments are copied back to parameters in the left-to-right order. (a) foo(y,z) where all parameters are passed by value (b) foo(y,z) where all parameters are passed by reference (c) foo(y,z) where all parameters are passed by value-result (d) foo(x,y) where all parameters are passed by reference (e) foo(x,x) where all parameters are passed by reference (f) foo(x,x) where all parameters are passed by value-result 2. (2 points) Consider the following C++ program, where &i means i is passed by reference: int bar (int &i) { i = i – 2; 1 return 2 * i; } void foo1 () { int x = 3, y = 6, sum; sum = x; sum = sum + bar(x); } void foo2 () { int x = 2, y = 7, sum; sum = bar(x); sum = sum + x; } (a) What is the value of sum at the end of the function foo1? Briefly explain why. (b) What is the value of sum at the end of the function foo2? Briefly explain why. 3. (4 points) Consider the Ada program given below. 1 procedure Main i s 2 A, B, C : I n t e g e r ; 3 procedure Sub1 (C: I n t e g e r ) i s 4 D, E : I n t e g e r ; 5 begin −− o f Sub1 6 . . . 7 end ; −− o f Sub1 8 procedure Sub2 (E: I n t e g e r ) i s 9 procedure Sub3 (F: I n t e g e r ) i s 10 C, D: I n t e g e r ; 11 begin −− o f Sub3 12 Sub1 ( 1 0 0 ) ; 13 end ; −− o f Sub3 14 begin −− o f Sub2 15 Sub3 (E ) ; 16 end ; −− o f Sub2 17 begin −− o f Main 18 Sub2 ( 1 0 ) ; 19 end ; −− o f Main 2 Ada is a statically scoped language. In the above program, the Main function invokes Sub2; Sub2 invokes Sub3; and Sub3 invokes Sub1. Draw the stack of activation records when the program’s execution reaches before line 12 and line 6. For each activation record, include local variables, parameters, the dynamic link, the static link, and the return address.
1. (4 points) In class, we discussed static local variables in C. Answer each question below; if necessary, find and consult a reference on the C language (cite your source in your answer). (a) For a non-static local variable in a C function, what is its scope and what is its lifetime? (b) For a static local variable in a C function, what is its scope and what is its lifetime? (c) For a non-static global variable in C, what is its scope and what is its lifetime? (d) For a static global variable in C, what is its scope and what is its lifetime? 2. (3 points) Find some online material to learn PHP’s namespace mechanism (cite your source). Explain briefly how it works and its benefits. 3. (8 points) Consider the Ada program given below. You will be asked to determine which variables are visible in a number of different situations. In each case, identify each variable by its name and the line number of its declaration. 1 . procedure Main i s 2 . A, B, C : I n t e g e r ; 1 3 . procedure Sub1 i s 4 . D, E : I n t e g e r ; 5 . begin −− o f Sub1 6 . . . . 7 . end ; −− o f Sub1 8 . procedure Sub2 i s 9 . C, D : I n t e g e r ; 1 0. procedure Sub3 i s 1 1. B, D, F: I n t e g e r ; 1 2. begin −− o f Sub3 1 3. . . . 1 4. end ; −− o f Sub3 1 5. begin −− o f Sub2 1 6. . . . 1 7. end ; −− o f Sub2 1 8. begin −− o f Main 1 9. . . . 2 0. end ; −− o f Main (a) Assuming that static scoping is used, say which variables are visible in the bodies of each of the procedures: Main, Sub1, Sub2 and Sub3. (b) Assuming that dynamic scoping is used and the calling sequence is Main calls Sub1; Sub1 calls Sub2; Sub2 calls Sub3, say which variables are visible in Sub3. (c) Assuming that dynamic scoping is used and the calling sequence is Main calls Sub2; Sub2 calls Sub3; Sub3 calls Sub1, say which variables are visible in Sub1. (d) Assuming that dynamic scoping is used and the calling sequence is Main calls Sub2; Sub2 calls Sub1, say which variables are visible in Sub1. 2
1. (5 points) We have the following grammar with the start symbol : -> | + | – -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 (a) Show a leftmost derivation for the expression “7 + 4 – 5”; show every step. (b) Show a rightmost derivation for the above expression; show every step.(c) Show two different parse trees for the above expression. (d) The grammar is ambiguous. Show a new grammar that removes the ambiguity and makes “+” and “-” left-associative. Show the parse tree for “7 + 4 – 5” in your new grammar. Argue why this is the only parse tree in the new grammar. (e) Show a new grammar that removes the ambiguity and makes “+” and “-” right-associative. Show the parse tree for “7 + 4 – 5” in the new grammar.2. (3 points) Show the following BNF grammar (with start symbol ) is ambiguous by giving an example input and drawing its two different parse trees. Give an equivalent unambiguous grammar. -> -> and | -> a | b | c 1 3. (2 points) Consider the language consisting of strings that have n copies of the letter a followed by 2n copies of the letter b where n > 0. For example, the strings abb, aabbbb, and aaabbbbbb are in the language but a, ab, ba and aabbb are not. Give an unambiguous BNF grammar for the language. 4. (4 points) Consider the grammar given bellow: -> = -> x | y | z -> + | -> * | -> () | Give a complete grammar that extends the above grammar to include a binary exponentiation operator ** (i.e., b ** n is used in some languages to mean b raised to the n-th power). In this grammar, make the ** operator right-associative and give it a higher precedence over +, but a lower precedence over *. For example, “x + x ** y ** z” should be parsed the same as “x + (x ** (y ** z))”. 5. (4 points) A simplified email address has (i) an account name starting with a letter and continuing with any number of letters or digits; (ii) an @ character; (iii) a host with two or more sequences of letters or digits separated by periods; the last sequence must be a toplevel domain— either ’edu’, ’org’, or ’com’. Define a context-free grammar to model this language. 6. (4 points) The following E-BNF is the grammar for a simplified version of LISP. Convert it to a BNF grammar. Note in the following “{”, “}”, “[”, “]”, and “|” are meta-symbols of E-BNF, while “(”, “)”, and “.” are terminals. -> | ( . ) | ( ) -> { } -> { | } -> a | b | … | z -> 0 | 1 | … | 9 2
This lab introduces the idea of the pipelining technique for building a fast CPU. The students will obtain experience with the design implementation and testing of the first four stages (Instruction Fetch, Instruction Decode, Instruction Execute, Memory) of the five-stage pipelined CPU using the Xilinx design package for FPGAs. It is assumed that students are familiar with the operation of the Xilinx design package for Field Programmable Gate Arrays (FPGAs) through the Xilinix tutorial available in the class website.1. Pipelining As described in lab 4 2. Circuits of the Instruction Fetch Stage As described in lab 4 3. Circuits of the Instruction Decode Stage As described in lab 4 4. Circuits of the Execution Stage Referring to Figure 1, (8.5) in the third cycle the first instruction entered the EXE stage. The ALU performs addition, and the multiplexer selects the immediate. A letter “e” is prefixed to each control signal in order to distinguish it from that in the ID stage. The second instruction is being decoded in the ID stage and the third instruction is being fetched in the IF stage. All the four pipeline registers are updated at the end of the cycle.5. Circuits of the Memory Access Stage Referring to Figure 2, (8.6) in the fourth cycle of the first instruction entered the MEM stage. The only task in this stage is to read data memory. All the control signals have a prefix “m”. The second instruction entered the EXE stage; the third instruction is being decoded in the ID stage; and the fourth instruction is being fetched in the IF stage. All the five pipeline registers are updated at the end of the cycle.Figure 1 Pipeline execution (EXE) stage Figure 2 Pipeline memory access (MEM) stage6. Table 1 lists the names and usages of the 32 registers in the register file. Table 1 MIPS general purpose register $zero 0 Constant 0 $at 1 Reserved for assembler $v0, $v1 2, 3 Function return values $a0 – $a3 4 – 7 Function argument values $t0 – $t7 8 – 15 Temporary (caller saved) $s0 – $s7 16 – 23 Temporary (callee saved) $t8, $t9 24, 25 Temporary (caller saved) $k0, $k1 26, 27 Reserved for OS Kernel $gp 28 Pointer to Global Area $sp 29 Stack Pointer $fp 30 Frame Pointer $ra 31 Return Address 7. Table 2 lists some MIPS instructions that will be implemented in our CPU Table 2 MIPS integration instruction 8. Initialize the first 10 words of the Data memory with the following HEX values: A00000AA 10000011 20000022 30000033 40000044 5000005560000066 70000077 80000088 90000099 9. Write a Verilog code that implement the following instructions using the design shown in Figure 2. Write a Verilog test bench to verify your code: (You have to show all the signals written into the MEM/WB register and output from EX/MEM register in your simulation outputs) instruction comment lw $2, 00($1) # $2 ß memory[$1+00]; load x[0] lw $3, 04($1) # $3 ß memory[$1+04]; load x[1] lw $4, 08($1) # $4 ß memory[$1+08]; load x[2] lw $5, 12($1) # $5 ß memory[$1+12]; load x[3] Assume that register $1 has the value of 0 10. Write a report that contains the following: a. Your Verilog design code. Use: i. Device: XC7Z010- -1CLG400C b. Your Verilog® Test Bench design code. Add “`timescale 1ns/1ps” as the first line of your test bench file. c. The waveforms resulting from the verification of your design with ModelSim showing all the signals written into the MEM/WB register and output from EX/MEM register. d. The design schematics from the Xilinx synthesis of your design. Do not use any area constraints. e. Snapshot of the I/O Planning and f. Snapshot of the floor planning 11. REPORT FORMAT: Free form, but it must be: g. One report per student. h. Have a cover sheet with identification: Title, Class, Your Name, etc. i. Using Microsoft word and it should be uploaded in word format not PDF. If you know LaTex, you should upload the Tex file in addition to the PDF file. j. Double spaced 12. You have to upload the whole project design file zipped with the word file.
This lab introduces the idea of the pipelining technique for building a fast CPU. The students will obtain experience with the design implementation and testing of the first two stages (Instruction Fetch, Instruction Decode) of the five-stage pipelined CPU using the Xilinx design package for FPGAs. It is assumed that students are familiar with the operation of the Xilinx design package for Field Programmable Gate Arrays (FPGAs) through the Xilinix tutorial available in the class website.Pipelining is an implementation technique in which multiple instructions are overlapped in execution. The fivestage pipelined CPU allows overlapping execution of multiple instructions. Although an instruction takes five clock cycle to pass through the pipeline, a new instruction can enter the pipeline during every clock cycle. Under ideal circumstances, the pipelined CPU can produce a result in every clock cycle. Because in a pipelined CPU there are multiple operations in each clock cycle, we must save the temporary results in each pipeline stage into pipeline registers for use in the follow-up stages. We have five stages: IF, ID, EXE, MEM, and WB. The PC can be considered as the first pipeline register at the beginning of the first stage. We name the other pipeline registers as IF/ID, ID/EXE, EXE/MEM, and MEM/WB in sequence. In order to understand in depth how the pipelined CPU works, we will show the circuits that are required in each pipeline stage of a baseline CPU.The circuit in the IF stage are shown in Figure 2. Also, looking at the first clock cycle in Figure 1(b), the first lw instruction is being fetched. In the IF stage, there is an instruction memory module and an adder between two pipeline registers. The left most pipeline register is the PC; it holds 100. In the end of the first cycle (at the rising edge of clk), the instruction fetched from instruction memory is written into the IF/ID register. Meanwhile, the output of the adder (PC + 4, the next PC) is written into PC.Referring to Figure 3, in the second cycle, the first instruction entered the ID stage. There are two jobs in the second cycle: to decode the first instruction in the ID stage, and to fetch the second instruction in the IF stage. The two instructions are shown on the top of the figures: the first instruction is in the ID stage, and the second instruction is in the IF stage. The first instruction in the ID stage comes from the IF/ID register. Two operands are read from the register file (Regfile in the figure) based on rs and rt, although the lw instruction does not use the operand in the register rt. The immediate (imm) is sign- extended into 32 bits. The regrt signal is used in the ID stage that selects the destination register number; all others must be written into the ID/EXE register for later use. At the end of the second cycle, all the data and control signals, except for regrt, in the ID stage are written into the ID/EXE register. At the same time, the PC and the IF/ID register are also updated.Figure 1 Timing chart comparison between two types of CPUs Figure 2 Pipeline instruction fetch (IF) stageFigure 3 Pipeline instruction decode (ID) stage4. Table 1 lists the names and usages of the 32 registers in the register file. Table 1 MIPS general purpose register $zero 0 Constant 0 $at 1 Reserved for assembler $v0, $v1 2, 3 Function return values $a0 – $a3 4 – 7 Function argument values $t0 – $t7 8 – 15 Temporary (caller saved) $s0 – $s7 16 – 23 Temporary (callee saved) $t8, $t9 24, 25 Temporary (caller saved) $k0, $k1 26, 27 Reserved for OS Kernel $gp 28 Pointer to Global Area $sp 29 Stack Pointer $fp 30 Frame Pointer $ra 31 Return Address 5. Table 2 lists some MIPS instructions that will be implemented in our CPU Table 2 MIPS integration instruction6. Initialize the first 10 words of the Data memory with the following HEX values: A00000AA 10000011 20000022 30000033 40000044 50000055 60000066 70000077 80000088 900000997. Write a Verilog code that implement the following instructions using the design shown in Figure 2 and Figure 3. Write a Verilog test bench to verify your code: (You have to show all the signals written into the IF/ID register and the ID/EXE register in your simulation outputs) # address instruction comment 100: lw $v0, 00($at) # $2 ß memory[$1+00]; load x[0] 104: lw $v1, 04($at) # $3 ß memory[$1+04]; load x[1] Assume that the register $at has the value of 0 8. Write a report that contains the following: a. Your Verilog design code. Use: i. Device: XC7Z010- CLG400 -1 b. Your Verilog® Test Bench design code. Add “`timescale 1ns/1ps” as the first line of your test bench file.c. The waveforms resulting from the verification of your design with simulation showing all the signals written into the IF/ID register and the ID/EXE register. d. The design schematics from the Xilinx synthesis of your design. Do not use any area constraints. e. Snapshot of the I/O Planning and f. Snapshot of the floor planning 9. REPORT FORMAT: Free form, but it must be: g. One report per student. h. Have a cover sheet with identification: Title, Class, Your Name, etc. i. Using Microsoft word and it should be uploaded in word format not PDF. If you know LaTex, you should upload the Tex file in addition to the PDF file. j. Double spaced 10. You have to upload the whole project design file zipped with the word file.
The goal is to learn to use the MARS simulator: You can download the MARS program from http://courses.missouristate.edu/KenVollmar/MARS/. This is version 4.5. It’s a Java program, so it should run anywhere. We will follow the same homework written by Prof. Heller. You can check the following tutorial by Prof. Gary Shute http://www.d.umn.edu/%7Egshute/mips/Mars/Mars.xhtml To start MARS, just double-click on its icon. You should see a window with four parts – some buttons at the top, a section with tabs Edit and Execute, below that a section with tabs Mars Messages and Run I/O, and a section that displays the processor’s Registers. Within the Execute tab, there are panels for the Text Segment (the part of memory where the program’s instructions are placed), the Data Segment (the part of memory where the program’s global data is placed), and Labels (a symbol table, connecting labels in the program with memory locations). If you decide to resize the MARS window and its various sections, be sure that the Registers panel shows all three columns. If you don’t see the Labels panel in the Execute tab, go to the Settings menu, and check the item Show Labels Window. Let’s begin with an absolute minimal program – it starts and ends, and does nothing else. Comments begin with # and go to the end of the line. Assembler directives begin with a dot, and are usually tabindented. Instructions are usually tab-indented, and labels are at the left margin. • Start MARS, then click on the New File button (farthest left, or menu File / New). Now you can type the program into the editor pane under the Edit tab. The default file name is mips1.asm. If you were to click on New File again, you would get a second editor pane for the file mips2.asm. • Don’t take a shortcut by using copy-and-paste — you will miss the helpful information that MARS displays while you type. Copy-and-paste is ok later (well, subject to not cheating, of course). # Version 1, do nothing, then exit # switch to the Text segment .text .globl main main: # the rest of the main program will go here # end the program, no explicit return status li $v0, 10 syscall # switch to the Data segment .data# global data will be defined here • Save the file as version1.asm (fourth button, or menu File / Save as …). The usual filename for an assembly language program would be like version1.s or version1.asm. On Windows, Visual Studio is usually associated with those filename extensions, and it doesn’t like MIPS Assembler, so be careful about double-clicking from a folder display. • QtSPIM only accepts .s or .asm files. MARS will accept any file name; using something like version1.mips will prevent any bad interactions when double-clicking icons, but it makes using the other simulator more difficult. • Assemble the program (thirteenth button, first in the third group, looks like a screwdriver and wrench, or menu Run / Assemble). You should see in the Mars Messages panel below the Edit/Execute section. Of course, your directory names will be different. o Note that you can’t assemble the file until it has been saved. o After the program has been successfully assembled, the display switches to the Execute tab, with machine code in the Text Segment. The Registers information indicates that the program will start at address 0x00400000, which is the content of register pc, the Program Counter; this register always holds the address of the next instruction to be executed. The Text Segment highlights that instruction. o Global variables are displayed in the Data Segment, except that there aren’t any yet. The Labels panel shows global names, which will be needed later when your program uses functions and spans several files. For now, it just says that main is at location 0x00400000. • Run the program (fourteenth button, second in the third group, looks like a rightward triangle, or menu Run / Go). You should see in the Mars Messages panel, and in the Run I/O panel. • Go: running version1.asm • Go: execution completed successfully. • — program is finished running — • You can set breakpoints in the program by checking the Bkpt box at the left of each instruction in the Text Segment panel. More of that later. • Note that the li instruction (load immediate) turned into an addiu instruction (add immediate unsigned). That’s because li is actually a pseudo-instruction. Register $v0 turned into register $2, which is the same thing. Register $0 (or $zero) always contains 0 bits. • The syscall instruction (system call) initiates an operating system action; which one depends on the value in register $v0 when the instruction is executed. Syscall 10 resembles the exit() function in C or C++, while syscall 17, which we will use later, really is the exit() function. • Note that the Program Counter register (pc) started as 0x00400000 and ended as 0x00400008, which is one instruction past the last one in the program. • If you want to rerun the program, you can reset the memory and registers to their default values using the second button from the right, or menu Run / Reset. This returns $v0 to 0x00000000 and pc to 0x00400000. • If you want to run the program one instruction at a time (single-stepping), then reset the memory and registers, and repeatedly use the Run button with the subscript 1, or menu Run / Step. Pay attention to changes in registers $v0 and pc; $v0 is highlighted as it changes, but pc is not. Next, we add some function definitions, which make it easier to deal with system calls. Note the second .text directive, so the new code isn’t treated as data. The program is getting longer, so we use a comment as a dividing line for the different parts of the program.# Version 2, do nothing, then exit # switch to the Text segment .text .globl main main: # the rest of the main program will go here # call function Exit0 jal Exit0 # end the program, default return status # – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – # switch to the Data segment .data# global data will be defined here # – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – # Wrapper functions around some of the system calls # See P&H COD, Fig. A.9.1, for the complete list. # switch to the Text segment .text .globl Print_integer Print_integer: # print the integer in register $a0 li $v0, 1 syscall jr $ra .globl Print_string Print_string: # print the string whose starting address is in register $a0 li $v0, 4 syscall jr $ra .globl Exit Exit: # end the program, no explicit return status li $v0, 10 syscall jr $ra # this instruction is never executed .globl Exit0 Exit0: # end the program, default return statusli $a0, 0 # return status 0 li $v0, 17 syscall jr $ra # this instruction is never executed .globl Exit2 Exit2: # end the program, with return status from register $a0 li $v0, 17 syscall jr $ra # this instruction is never executed # – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – • Repeat the previous steps, with suitable changes. It may help to first clear the Mars Messages and Run I/O panels. • Note that pc finishes with the value 0x00400034, which is the address of the instruction following the syscall instruction in the function Exit0. Work through the Text Segment, Labels and Registers to verify this. Note also that register $ra has the value 0x00400004, which is the address of the instruction following the jal Exit0 instruction. More about this later. It’s essentially a coincidence that the first instruction of the function Print_integer is at address 0x004000004. Next, the third version, the ubiquitous Hello World program. # Version 3, print something, then exit # switch to the Text segment .text .globl main main: # the main program goes here la $a0, hello_string jal Print_stringjal Exit0 # end the program, default return status # – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – # switch to the Data segment .data # global data is defined here hello_string: .asciiz “Hello, world ” # – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – –# Wrapper functions around some of the system calls # See P&H COD, Fig. A.9.1, for the complete list. # switch to the Text segment .text .globl Print_integer Print_integer: # print the integer in register $a0 li $v0, 1 syscall jr $ra .globl Print_string Print_string: # print the string whose starting address is in register $a0 li $v0, 4 syscall jr $ra .globl Exit Exit: # end the program, no explicit return status li $v0, 10 syscall jr $ra # this instruction is never executed .globl Exit0 Exit0: # end the program, default return status li $a0, 0 # return status 0 li $v0, 17 syscall jr $ra # this instruction is never executed .globl Exit2 Exit2: # end the program, with return status from register $a0 li $v0, 17 syscall jr $ra # this instruction is never executed # – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – Repeat the previous steps, with suitable changes. You should see in the Mars Messages panel, and in the Run I/O panel. Assemble: operation completed successfully. Go: running version3.asm Go: execution completed successfully. Hello, world— program is finished running — Note that the label hello_string is not marked (global) in the Labels panel. That’s because we didn’t use the directive .globl hello_string . The label is defined and accessible within the file version3.asm, but it can’t be seen outside the file. Try adding the directive, and see how the Labels panel changes. Finally, here is a program derived from P&H COD, Fig. A.1.4, corrected and adapted for the MARS simulator. There are some differences between MARS and QtSPIM concerning the starting address for main(), and a few other things. This version will work with both simulators. Copy and paste seems completely appropriate at this point. .text # .align 2 # MARS doesn’t like this .globl main main: subu $sp, $sp, 40 # stack push, 40 bytes sw $ra, 20($sp) # save return address register (sw = store word) sd $a0, 32($sp) # save registers $a0, $a1 (sd = store doubleword) sw $0, 24($sp) # sum = 0 sw $0, 28($sp) # i = 0 loop: lw $t6, 28($sp) # i mul $t7, $t6, $t6 # i * i lw $t8, 24($sp) # sum addu $t9, $t8, $t7 # sum + i*i sw $t9, 24($sp) # sum = sum + i*i addu $t0, $t6, 1 # i + 1 sw $t0, 28($sp) # i = i + 1 ble $t0, 100, loop # if (i
In this lab, you will obtain experience with sequential logic design, and study digital design using the Xilinx design package for FPGAs. It is assumed that the students are familiar with the operation of the Xilinx design package for Field Programmable Gate Arrays (FPGAs) through the Xilinix tutorial available in the class website. 1. A finite state machine is a way of modeling system in which the system’s output will depend on not only the current inputs but also the past history of inputs. It defines a finite set of states and behaviors, and how the system transits from one state to another when certain conditions are true. The module of output function is a combinational circuit that generates the outputs based on the current state (Moore model) or the combination of the current state and the current inputs (Mealy model). 2. Suppose we design a radix of six up/down counters as shown in Figure 1. The state of the counter changes on the positive (rising) edge of the clock. If the input u is a 1, the counter value will change in the sequence 0, 1, 2, 3, 4, 5, 0, 1, 2, … . If u is a 0, the counter value will change in the sequence 0, 5, 4, 3, 2, 1, 0, 5, 4, … . There are seven output signals, with each connecting to a segment of LED. A segment of the LED will be on if its control signal is a 0 (active-low). 3. There are six states, the circuit of the counter is shown in Figure 2. The module of dff3 contains three DFFs. The other module is a combinational circuit that generates signals of the next state (ns[2:0]) and LED control signals (a, b, c, d, e, f, and g). The current state (the outputs of dff3) is denoted with q[2:0]. 4. Figure 3 shows the state transition diagram. The arrowed lines indicate the transitions of the states under the condition of the input. Figure 3 also shows that a 3-bit unique code is assigned to a state. Any code can be assigned to any state as long as all the codes are unique. 5. Table 1 is the truth table for the next state. 6. For students who took this class as an (honor option). Figure 4 shows the Karnaugh maps for each of the next state signals. From the Karnaugh maps, you can get the expressions of the next state signals. Figure 5 shows the truth table and Karnaugh maps of the output signals. You can get the expressions of the output signals from the Karnaugh maps. Figure 1 A counter with a seven-segment LEDFigure 2 Block diagram of a counter with a seven segment LED Figure 3 State transition diagram of the counter Table 1 State transition tableFigure 4 Karnaugh map for next state of the counter Figure 5 Karnaugh map for the output function of the counter Figure 6 Test wave form 7. Write a behavioral Verilog code description using the states shown in Figure 1, 2, 3 and Table 1. Compile and simulate your code using the test sequence shown in Figure 6. 8. Write a report that contains the following: a. Your Verilog design code. Use: i. Device: XC7Z010- -1CLG400C b. Your Verilog® Test Bench design code (use the test sequence shown in Figure 6). Add “`timescale 1ns/1ps” as the first line of your test bench file. c. The waveforms resulting from the verification of your design with ModelSim showing all the outputs of the following signals (q, a, b, c, d, e, f, g). d. The design schematics from the Xilinx synthesis of your design. Do not use any area constraints.e. Snapshot of the I/O Planning and f. Snapshot of the floor planning 9. REPORT FORMAT: Free form, but it must be: a. One report per student. b. Have a cover sheet with identification: Title, Class, Your Name, etc. c. Using Microsoft word and it should be uploaded in word format not PDF. If you know LaTex, you should upload the Tex file in addition to the PDF file. d. Double spaced 10. You have to upload the whole project design file zipped with the word file. 11. For students who took this class as an (honor option). In addition to all of the above requirements, you need to get the expressions of the next state and the output signals from Karnaugh maps. Compare the results that you get from Karnaugh map and the results you got from the behavioral model of the Verilog code.
The purpose of this assignment is to introduce you to basic C programming along with the tools you need to succeed as a C programmer. This assignment will familiarize you with C syntax and how to compile, run, and debug C. Furthermore, you will gain exposure to common practices such as man(ual) pages and standard libraries which are utilized in real world C programming.You will become familiar with how to work with strings, arrays, pointers, and structs in C. You will understand the relationship in C between arrays and pointers, including pointer arithmetic (think about how arrays are stored in memory in assembly). You will also become familiar with how to use a Makefile to automate the compilation of your program.You will write your C code in two files: my string.c, pkmn gym.c. See the Detailed Instructions section for more details on the specific requirements for each function. IMPORTANT NOTE: • You need to complete ‘string.c’ before ‘pkmn gym.c’ as you will be using the implemented functions from ‘string.c’ in ‘pkmn gym.c’. In my string.c, you will write your own implementations of common C library functions for working with strings: • my strlen() • my strncmp() • my strncpy() • my strncat() • my memset() • is palindrome ignore case() • caesar shift() • deduplicate str() • swap strings()In pkmn gym.c, you will establish a new Pok´emon gym! Your Pok´emon gym will have the following functions: • catch pokemon() • release pokemon() • count species() • trade pokemon() • register trainer() • unregister trainer() • battle trainer() • find champion() Take a look at the sections on Makefiles and Autograder for more info on how to compile and test your program.1.3 TA Tips While doing the homework, you may find it helpful to draw diagrams of memory locations, as you did with assembly programming. How are arrays represented in memory? How can you use pointers to find the address of array[i]? How are arguments passed to a function and results returned using the stack frame? Remember, C functions are pass by value (copies of the values of arguments are pushed onto the stack), just like subroutines in assembly.1.4 Criteria Your C code must compile without errors or warnings, using the provided Makefile. Your array of structs should be populated correctly at the end of the program. Your helper functions in my string.c must all be implemented correctly, producing the same behavior for test cases as the equivalent library functions from string.h.2.1 my string.c functions The first part of this homework is to implement three very common C string library functions found in string.h. The caveat is that you must implement these functions using only pointer notation. That is, you cannot use array indexing notation, such as str[i] = ‘a’. This restriction only applies in the my string.c file. We recommend implementing these functions first so you are able to use these functions as you move on with the assignment. Make sure to read all the information in this section to ensure you have all the information you need to succeed!For this file, you may assume that all inputs are valid (i.e. not NULL). • size_t my_strlen(const char *s): This function calculates the length of the string pointed to by s, up to and excluding the null terminator (‘’). Consider the following examples: – If char *pet = “otter”, then my_strlen(pet) == 5. Remember, the null terminator is automatically added here. – If char letters[] = {‘a’, ‘b’, ‘c’, ‘’, ‘d’}, then my_strlen(letters) == 3.– If a string with no null terminator is passed into my_strlen, the string standard library defines the output to be undefined behavior. Consider why this might be the case? Therefore, this function should do nothing extra to handle inputs of invalid strings (i.e., unterminated strings) because the programmer is expected to pass in valid strings. • int my_strncmp(const char *s1, const char *s2, size_t n): This function compares two strings, checking a maximum of n characters of both strings. Note that: – Comparisons should be made between each character between the ASCII values of each pair of corresponding characters.– Comparisons should be character by character until one of the following occurs: ∗ There is a difference between the corresponding pair of characters. (This includes if one of the strings terminates before the other one!) ∗ Both strings terminate at the same character. ∗ We have completed n comparisons. This function should return an arbitrary negative integer if the first string is lexicographically less than the second string, zero if equal, and positive if greater. You should also remember to account for null terminators. Some examples of string comparisons are below: – my_strncmp(“bazz”, “bog”, 3) < 0 – my_strncmp(“rainforest”,”rain”, 4) == 0 – my_strncmp(“rainforest”,”rain”, 5) > 0 (recall, ‘f’ > ‘’) – my_strncmp(“aa”, “ab”, 3) == 0 (notice how and where an additional null terminator is placed mid-string!)• char *my_strncpy(char *dest, const char *src, size_t n): This function copies at most n characters from a source string (src) into a destination memory location (dest), returning a pointer to dest. Note that: – If src ends before n characters have been copied to dest, then continue writing null characters to dest until n characters have been written.– If src has not ended after n characters have been copied to dest, a null terminator should not be added to dest. – As an implementor, you can assume dest is sufficiently large enough for n characters to be written into it (note that if you use this function, you have to ensure the dest argument you enter is sufficiently large enough!). Consider the following example. Let us define the following variables: char src[] = “hob”; char dest[] = “ribbit”; Then, – my_strncpy(dest, src, 3) would set dest to {‘h’, ‘o’, ‘b’, ‘b’, ‘i’, ‘t’, ‘’}. – my_strncpy(dest, src, 4) would set dest to {‘h’, ‘o’, ‘b’, ‘’, ‘i’, ‘t’, ‘’}. – my_strncpy(dest, src, 5) would set dest to {‘h’, ‘o’, ‘b’, ‘’, ‘’, ‘t’, ‘’}. • char *my_strncat(char *dest, const char *src, size_t n): This function appends at most n bytes from the src string to the dest string, returning a pointer to dest. This function starts writing characters over dest’s null terminator and stops writing to dest once: – a null terminator is found in src, or – n characters have been written from src. In this case, a null terminator is added to the end of dest.Note that, like my_strncpy, as the implementor of this function, you can assume dest is sufficiently large enough for the result. (If you use this function, you must provide a sufficiently large enough dest to hold the result of this function!) Consider the following example. Let us define the following variables: char src[6] = “defgh”; char dest[100] = “abc”; Then (assuming we set src and dest back to these inputs after every execution), – my_strncpy(dest, src, 3) sets dest to {‘a’, ‘b’, ‘c’, ‘d’, ‘e’, ‘f’, ‘’ } – my_strncpy(dest, src, 5) sets dest to {‘a’, ‘b’, ‘c’, ‘d’, ‘e’, ‘f’, ‘g’, ‘h’, ‘’ } – my_strncpy(dest, src, 6) also sets dest to {‘a’, ‘b’, ‘c’, ‘d’, ‘e’, ‘f’, ‘g’, ‘h’, ‘’ } – my_strncpy(dest, src, 9) also sets dest to {‘a’, ‘b’, ‘c’, ‘d’, ‘e’, ‘f’, ‘g’, ‘h’, ‘’ } • void *my_memset(void *str, int c, size_t n): This function fills the first n bytes of the memory area pointed to by str with the constant int value c. The function returns a pointer to the memory location str. Note that this function does not copy the int value c directly into str, but rather, truncates it to a byte before copying it. As an implementor, you can assume the str buffer has enough space to write n bytes into (If you use this function, you must ensure you provide a str buffer that has enough space to write n bytes into). This function does not add a null terminator at the end. Consider this example. Suppose you had a destination buffer char str[] = “i love aardvarks!”: 5 – my_memset(str, ‘a’, 1) updates str to “a love aardvarks!” – my_memset(str, ‘a’, 7) updates str to “aaaaaaaaardvarks!” – my_memset(str, 0x9961, 16) updates str to “aaaaaaaaaaaaaaaa!”. Note here that 0x9961 truncates to 0x61 which encodes the character ‘a’. • int is_palindrome_ignore_case(const char *str): This function checks whether a string is a palindrome, ignoring differences in case. It should return 1 if the input string str is a palindrome, and it should return 0 if it is not. Consider the following examples of palindromes: racecar, madam, ABBA, Ho-Oh, Eevee, Girafarig. Note that with the last three words, they are only palindromes if you ignore case! • void caesar_shift(char *str, int shift): This function applies a Caesar shift of size shift, updating the input str with the encrypted text. A Caesar shift or Caesar cipher is a type of encryption method where each letter of a message is substituted for a letter that is a fixed distance away in the alphabet. You may assume that the shift is not negative and is not so large that it will cause overflow. For example, with a shift of +2: original A B C D E F . . . U V W X Y Z shifted C D E F G H . . . W X Y Z A B With this table, we could convert the sentence “I love LC-3 assembly!” into “K nqxg NE-3 cuugodna!”. Note that uppercase letters should be transformed into other uppercase letters, lowercase letters should be transformed into other lowercase letters, and other types of characters (e.g., numbers and punctuation) remain unchanged. • void deduplicate_str(char *str): This function removes consecutive duplicate characters in the string. This function is case-sensitive, so characters that are considered “duplicate” must also have the same case. Consider these examples: – if char foo[] = “mississippi”, then calling deduplicate str(foo) should update foo to “misisipi”. – if char bar[] = “bookkeeper”, then calling deduplicate str(bar) should update bar to “bokeper”. – if char baz[] = “Zzyzx”, then calling deduplicate str(bar) should keep baz as “Zzyzx”, as there are no consecutive duplicate characters. • void swap_strings(char **s1, char **s2): This function swaps two string variables. You should not use loops (i.e., for, while, do-while, or goto) to implement this function. Note that you are given pointers to strings (char **). Here is an example of how this function would be used: char *right_opinion = “CS 2110 is a terrible, horrible, no good, very bad class.”; char *wrong_opinion = “CS 2110 is such a fun class!”; swap_strings(&right_opinion, &wrong_opinion); printf(“%s ”, right_opinion); // CS 2110 is such a fun class! printf(“%s ”, wrong_opinion); // CS 2110 is a terrible, horrible, // no good, very bad class. 6 You will notice that many of the arguments in the my string.c and pkmn gym.c files are of type const char *. This is a pointer to a char that is constant. This means that you cannot edit any of the characters to which a const char * points to. If you attempt to do so, using something like *pointer = ‘c’, you will get a compile error. If const does not precede a char * declaration, you can edit the characters to which it points to. In order to understand the functionalities of these library functions, you may also take a look at their man page (i.e. manual page). See the section on Man Pages for more info. What is size t: size t is an unsigned integer datatype in C that is large enough to store the result of sizeof(…). The size t type is used throughout the C standard library (which, of course, includes the string library functions). Some notes: 1. You should complete my string.c before moving on to pkmn gym.c. 2. You are not allowed to use array notation in this file (e.g. s1[0]). All functions should be implemented using pointers and pointer arithmetic only! Think about how arrays and pointers correlate with each other in C. Again, this restriction only applies to this file. If you do use array notation in your code, the makefile will indicate this error: make: *** [Makefile:30: check-array-notation] Error 1 along with the instances of array notation that it encountered. 3. You are not allowed to use any of the standard C string libraries (e.g. #include ). 4. Your string functions should not assume the length of any arguments passed in. 5. For my strncmp, you do not need to return a specific number, as long as it follows the description in the strncmp man page. 6. size t is an unsigned integer datatype typically used to represent the size or length of data, or any other unsigned quantity. 7. For swap strings, you are not allowed to use loops or conditionals. Think back to Homework 1, where you implemented several functions with just one line of code. 2.2 pkmn gym.c The second part of this homework is to implement several C functions within the pkmn gym.c file. You are a Pok´emon gym manager in the region of WeAreTakingSignificantCreativeLibertiesToMakeThisIdeaWorkForTheHomeworkAssignmentia (or Watsia for short)! You need to keep your gym working and functional in case a 10-year-old prodigy with the name of a color wants to battle at your gym! You will primarily be interacting with Trainers in the gym and with the global gym struct to facilitate the operations of your gym. In your gym, you have trainers that are registered to your gym to train! Your struct Gym is defined as such in pkmn gym.h: struct Gym { struct Trainer trainers[MAX_TRAINER_LENGTH]; int num_trainers; }; Your gym keeps track of the following information: • trainers is an array which keeps track of all of the trainers currently registered at the gym, 7 • num trainers is the size of the array, keeping track of how many trainers are currently registered at the gym. The trainers of your gym are represented by the following struct: struct Trainer { char name[MAX_NAME_LENGTH]; struct Pokemon party[MAX_PARTY_LENGTH]; int party_size; int num_wins; }; Each struct Trainer tracks the following information: • name: The name of the trainer, • party: The Pok´emon the trainer has (maximum of 6!), • party size: The number of Pok´emon the trainer has in their party, • num wins: The number of wins they’ve had against other trainers. Finally, each Pok´emon is represented by the following struct: struct Pokemon { char species[MAX_NAME_LENGTH]; int level; }; Each Pok´emon (struct Pokemon) tracks the following information: • species: The name of the species of Pok´emon (e.g., Girafarig, Ho-Oh, Alomomola), • level: The level of the Pok´emon (ranges from 1 to 100 (inclusive)). Useful Macro Definitions in users.h: • SUCCESS is an alias for the integer value to return when a function operation succeeds. • FAILURE is an alias for the integer value to return when a function operation fails. Think of this as an error code. • MAX NAME LENGTH represents the maximum length of the name/species char arrays, including the null terminator. Remember char arrays are one way to represent strings in C. • MAX PARTY LENGTH represents the maximum length of the party array. • MAX TRAINER LENGTH represents the maximum length of the trainers array. Hints: In regards to the functions to be implemented below, here are some common mistakes and reminders for how to go about solving them. • MAX NAME LENGTH represent the maximum lengths of the name char arrays. However, length in this case doesn’t necessarily mean the length from my strlen, which by definition, does not include the null terminator. Think of the maximum lengths from this macros as being the total amount of characters that have been allocated to represent the name. This means that if the maximum length is 10, for example, then the longest name string we could have comprises of 9 non-null characters (letters) and 1 null terminator. These characters all make up the 10 maximum characters that makes up the maximum name. This idea is important for truncating strings that are longer than the maximum lengths! 8 • Remember you can index into strings for reading or writing characters. For example, some string[3] is the 4th character of some string. In this file, you are allowed to use array notation. • When using any of the functions that write to a destination buffer (e.g., my_strncpy, my_strncat, my_memset), ensure that your dest buffer has enough capacity for that function. As examples, – For my_strncpy and my_memset, n should never exceed sizeof(dest) (supposing that dest is a char array). – For my_strncat, n should never exceed sizeof(dest) – strlen(dest) (also supposing that dest is a char array). • When comparing strings to each other, be wary of the n argument you pass in to my strncmp that tells how many characters you will be comparing. • Remember all strings are to be null-terminated! Otherwise, we would not be able to tell what characters are actually part of a string. • Always check the validity of your parameters. Possible things to check for: – NULL values – Strings that are too long – Values that are outside the acceptable range If you have an invalid input, the function should not do anything, and return FAILURE. Functions to Implement: Now that you’ve (hopefully) read all of the gym descriptions, here’s all the functions you must implement for your gym! • int register trainer(const char *name): You need to allow trainers to join your gym. Implement a function that adds a trainer to the trainer array in your gym. – The trainers in the gym’s trainer array should remain contiguous before and after the operation and should start at index 0. – Since this trainer is new to the gym, they should not have any wins or Pok´emon. – If the gym is full (i.e., if there are MAX TRAINER LENGTH trainers in the gym), do not add the new trainer and return FAILURE. – Otherwise, add the trainer and return SUCCESS. • int unregister trainer(const char *name): You also need to allow trainers to leave your gym. Implement a function that finds the trainer with the provided name and removes them from the trainer array in your gym. – The trainers in the gym’s trainer array should remain contiguous before and after the operation and should start at index 0. – If no trainer in the gym has the specified name, do not remove any trainer and return FAILURE. – If only one trainer in the gym has the specified name, remove the trainer and return SUCCESS. – If more than one trainer in the gym has the specified name, remove the first trainer in the array with the specified name and return SUCCESS. • int catch pokemon(struct Trainer *trainer, const char *species, int level): The trainers from your gym really like catching Pok´emon. You must implement a function to add a Pok´emon with the given species and level to the given trainer’s party. 9 – The Pok´emon in the given trainer’s party array should remain contiguous before and after the operation and should start at index 0. – If a trainer’s party is full (i.e., they have MAX PARTY LENGTH Pok´emon in their party), do not add the Pok´emon and return FAILURE. – Remember that the valid range of any Pok´emon’s level is between 1 and 100 (inclusive). If the argument does not match this constraint, return FAILURE. – If the Pok´emon is successfully added, return SUCCESS. • int release_pokemon(struct Trainer *trainer, const char *species): It hurts to say goodbye… and some of your trainers will do it anyway. You must implement a function to remove a Pok´emon with the given species from the given trainer’s party. – The Pok´emon in the given trainer’s party array should remain contiguous before and after the operation and should start at index 0. – If no Pok´emon in the given trainer’s party has the specified species, do not remove any Pok´emon and return FAILURE. – If only one Pok´emon in the trainer’s party has the specified species, remove the Pok´emon and return SUCCESS. – If more than one Pok´emon in the given trainer’s party has the specified species, remove the first Pok´emon in the array with the specified species and return SUCCESS. • int count species(const char *species): You want to compile useful statistics for your gym! Implement a function to count the total number of Pok´emon of a given species in your gym. – This should count and return the total number of Pok´emon of the given species in each trainer’s party. • int trade pokemon(struct Trainer *t0, int party index 0, struct Trainer *t1, int party index 1): Your trainers want to be able to exchange their Pok´emon! Implement a function to swap the Pok´emon in one trainer’s party with the Pok´emon in another trainer’s party. – The first Pok´emon to be traded is the Pok´emon at index party index 0 of trainer t0’s party. If this index is out of bounds for the party array, do not perform a trade and return FAILURE. – The second Pok´emon to be traded is the Pok´emon at index party index 1 of trainer t1’s party. If this index is out of bounds for the party array, do not perform a trade and return FAILURE. – Trainers unfortunately can’t trade with themselves. If t0 and t1 are the same trainer, do not perform a trade and return FAILURE. – After all conditions have been checked and verified, perform the trade and return SUCCESS. For example, suppose t0’s party consisted of: Index 0 1 2 3 4 5 Pok´emon Eevee Ho-Oh Girafarig Alomomola Farigiraf – Level 20 100 25 11 26 – and suppose t1’s party consisted of: Index 0 1 2 3 4 5 Pok´emon Dunsparce Haunter Trubbish Shellos Vulpix Rotom Level 14 22 11 15 17 14 10 If t0 wished to trade their Ho-Oh for t1’s Trubbish, we would call trade_pokemon(t0, 1, t1, 2). • int battle_trainer(struct Trainer *challenger, struct Trainer *opponent): The trainers of your gym LOVE to battle. Implement a function that allows a challenger to initiate a battle with an opponent. In a battle, the two trainers complete a set of “matches” between Pok´emon of the each index of both challenger and opponent’s parties. The trainer with higher-leveled Pok´emon wins the match. The winner of the most Pok´emon matches win the battle! For example, suppose the challenger has this party: Pok´emon Magikarp Magikarp Magikarp Magikarp Magikarp Magikarp Level 100 14 29 75 44 91 and suppose the opponent has this party: Pok´emon Kyogre Ho-Oh Zekrom Dialga Mewtwo Yveltal Level 96 50 34 73 40 80 Then, the battles commence like so: 1. Magikarp (lv. 100) vs. Kyogre (lv. 96) 2. Magikarp (lv. 14) vs. Ho-Oh (lv. 50) 3. Magikarp (lv. 29) vs. Zekrom (lv. 34) 4. Magikarp (lv. 75) vs. Dialga (lv. 73) 5. Magikarp (lv. 44) vs. Mewtwo (lv. 40) 6. Magikarp (lv. 91) vs. Yveltal (lv. 80) Since the challenger won 4 matches and the opponent only won 2 matches, the challenger wins the battle! Some additional notes: – If one trainer has more Pok´emon than another, the trainer with more Pok´emon automatically wins in matches where they do not have competition. For example, if the challenger has 4 Pok´emon and the opponent has 6, the opponent automatically wins the 5th and 6th matches of the battle. – In a match, if the Pok´emon have the same level, treat it as if neither trainer won the match. – If the challenger and the opponent win an equal number of matches, the challenger must swallow their pride and give the win to the opponent (i.e., the opponent wins the battle in case of a tie). – This function should return the winner of the battle (0 if the challenger wins, and 1 if the opponent wins). – This function should also update the respective trainer’s num wins field. • struct Trainer *find champion(void): You, as delusional as you are, believe the next POKEMON LEAGUE CHAMPION ´ of Watsia is in your very gym! Implement a function to find this champion! – Find and return a pointer to the trainer that has the most wins in your gym. – If several trainers have the maximum number of wins, pick the first in the gym trainer array with the maximum wins. – If your gym is empty (oh no!), return NULL. 11 2.3 .h files A header file is a C file (by convention with the extension .h) that contains function prototypes, struct definitions, as well as macros. Header files are useful so that we can separate these declarations and definitions from our main C code and later include them in other files. You can see in the code that pkmn gym.c includes pkmn gym.h, its header file. Before getting started with this homework make sure to get familiar with what’s provided in pkmn gym.h. Here is some of what’s defined in pkmn gym.h: • struct Trainer: This struct definition is how trainers are represented in the gym system. • Prototypes for functions like catch pokemon and release pokemon in pkmn gym.c. By including these at the top of pkmn gym.c, we prevent errors from using a function before it is defined. • Macros for constants such as MAX PARTY LENGTH, which is defined as 6, the maximum number of Pok´emon in a trainer’s party. • UNUSED PARAM(x) and UNUSED FUNC(x): Macros that are used in pkmn gym.c as placeholders so that you can compile the file without needing to complete every function. You may remove these once you’ve completed a function. 3 Useful Tips 3.1 Man Pages The man command in Linux provides “an interface to the on-line reference manuals.” If you are unsure about the specifics of a my string.c function, you should look up the exact details using its man page. This is a great utility for any C and Linux developer for finding out more information about the available functions and libraries. In order to use this, you just need to pass in the function name to this command within a Linux (in our case Docker) terminal. For instance, entering the following command will print the corresponding man page for the strlen function: $ man strlen Additionally, the man pages are accessible online at: http://man.he.net NOTE: You can ignore the subsections after the “RETURN VALUE” (such as ATTRIBUTES, etc) for this homework, however, pay close attention to function descriptions. 3.2 Debugging with GDB and printf We highly recommend getting used to “printf debugging” in C early on. Moreover, If you run into a problem when working on your homework, you can use the debugging tool, GDB, to debug your code! Former TA Adam Suskin made a series of tutorial videos which you can find here. Side Note: Get used to GDB early on as it will come in handy in any C program you will write for the rest of 2110, and even in the future! When running GDB, if you get to a point where user input is needed, you can supply it just like you normally would. When an error happens, you can get a Java-esque stack trace using the backtrace(bt) command which allows you to pinpoint where the error is coming from. For more info on basic GDB commands, search up “GDB Cheat Sheet.” 12 4 Checking Your Solution 4.1 Makefiles Make is a common build tool for abstracting the complexity of working with compilers directly. In fact, the PDF you’re reading now was built with a Makefile! Makefiles let you define a set of desired targets (files you want to compile), their prerequisites (files which are needed to compile the target), and sets of directives (commands such as gcc, gdb, etc.) to build those targets. In all of our C assignments (and also in production level C projects), a Makefile is used to compile C programs with a long list of compiler flags that control things like how much to optimize the code, whether to create debugging information for gdb, and what errors we want to show. We have already provided you a Makefile for this homework, but we highly recommend that you take a look at this file and understand the gcc commands and flags used to understand how to compile C programs. If you’re interested, you can also find more information regarding Makefiles here. Since your program is connected to an autograder with multiple files that need to be compiled using particular settings, it’s a little difficult to compile it by hand. The Makefile allows us to simply type the command make followed by a target such as hw7, tests, run-case, or run-gdb to compile and run your code. 4.2 Autograder To test your code manually, compile your code using make and run the resulting executable file with the command-line arguments of your choice. First, enter into our provided docker container with the following commands: # macOS or Linux ./cs2110docker.sh # Windows cs2110docker.bat If you use your own Linux distribution/VM, make sure you have the check unit test framework installed. However, keep in mind that your code will be tested on Docker. Navigate to your working directory for HW7, then run the autograder locally (without GDB): # To clean your working directory (use this instead of manually deleting .o files) $ make clean # Compile all the required files $ make tests # Run the tester executable $ ./tests The above commands will run all the test cases and print out a percentage, along with details of the failed test cases. If you want to debug a failed test case, see below. Commands to run/debug a specific failing test case: • To run specific tests without gdb: # Run all tests $ make run-case 13 # Run a specific test $ make run-case TEST=testCaseName • To run specific tests with gdb: # Run all tests in gdb $ make run-gdb # Run a specific test in gdb $ make run-gdb TEST=testCaseName Example error message: suites/hw7_suite.c:960:F:test_compareUser_basic_equal: … Example command: make run-caseTEST=test_compareUser_basic_equal TA Tip: Since C autograders can sometimes print out a lot of info, it might be a good idea to pipe the output to a file (./tests > output.txt) and investigate the content of the file instead! Use Gradescope for a cleaner output or run tests individually when debugging as mentioned above. 4.3 Manual Testing If you want to write manual tests of your functions, you are allowed to modify main.c to treat it as your own driver program. For example, you may want to create a new helper method that will print out the contents of the trainers array within pkmn gym.h, implement it in pkmn gym.c, and call it in main.c. However, if you choose to create extraneous helper methods to help debug make sure to remove them when submitting to the autograder. Editing main.c, however, should not interfere with the autograder. Here is how to manually run your main.c code. # Clean up all compiled output $ make clean # Recompile the hw7 executable $ make hw7 # Run the hw7 executable $ ./hw7 Important Notes: 1. The output file will ONLY be graded on Gradescope. 2. All non-compiling homework will receive a zero (with all the flags specified in the Makefile/Syllabus). 3. NOTE: DO NOT MODIFY THE HEADER FILES. Since you are not turning them in, any changes to the .h files will not be reflected when running the Gradescope autograder. Many test cases are randomly generated and your code should work every time we run the autograder on it. However, there’s no need to submit to Gradescope multiple times once you get the desired grade. We reserve the right to update the autograder and the test case weights on Gradescope or the local checker as we see fit when grading your solution. 14 5 Deliverables Please upload the following files to Gradescope: 1. my_string.c 2. pkmn_gym.c Note: Please do not wait until the last minute to run/test your homework; history has proven that last minute turn-ins will result in long queue times for grading on Gradescope. 15 6 Rules and Regulations 1. Please read the assignment in its entirety before asking questions. 2. Please start assignments early, and ask for help early. Do not email us the night the assignment is due with questions. 3. If you find any problems with the assignment, please report them to the TA team. Announcements will be posted if the assignment changes. 4. You are responsible for turning in assignments on time. This includes allowing for unforeseen circumstances. If you have an emergency please reach out to your instructor and the head TAs IN ADVANCE of the due date with documentation (i.e. note from the dean, doctor’s note, etc). 5. You are responsible for ensuring that what you turned in is what you meant to turn in. No excuses if you submit the wrong files, what you turn in is what we grade. In addition, your assignment must be turned in via Gradescope. Email submissions will not be accepted. 6. See the syllabus for information regarding late submissions; any penalties associated with unexcused late submissions are non-negotiable.
Now that you’ve been introduced to assembly, think back to some high level languages you know such as Python or Java. When writing code in Python or Java, you typically use functions or methods. Functions and methods are called subroutines in assembly language. In assembly language, how do we handle jumping around to different parts of memory to execute code from functions or methods? How do we remember where in memory the current function was called from (where to return to)? How do we pass arguments to the subroutine, and then pass the return value back to the caller? The goal of this assignment is to introduce you to the Stack and the Calling Convention in LC-3 Assembly. This will be accomplished by writing your own subroutines, calling subroutines, and even creating subroutines that call themselves (recursion). By the end of this assignment, you should have a strong understanding of the LC-3 Calling Convention and the Stack Frame, and how subroutines are implemented in assembly language.You will implement each of the three subroutines (functions) listed below in LC-3 assembly language. Please see the detailed instructions for each subroutine on the following pages. The autograder checks for certain subroutine calls with arguments pushed in the correct order, so we suggest that you follow the provided algorithms when writing your assembly code. Your subroutines must adhere to the LC-3 calling convention. 1. GCD.asm 2. isPalindrome.asm 3. DFS.asm Later in this document, you can also find some general tips for successfully writing assembly code.1.3 Criteria Your assignment will be graded based on your ability to correctly translate the given pseudocode for subroutines (functions) into LC-3 assembly code, following the LC-3 calling convention. Please use the LC-3 instruction set when writing these programs. Check the deliverables section for deadlines and other related information.You must obtain the correct values for each function. In addition, registers R0-R5 and R7 must be restored from the perspective of the caller, so they contain the same values before and after the caller’s JSR call. Your subroutine must return to the correct point in the caller’s code, and the caller must find the return value on the stack where it is expected to be. If you follow the LC-3 calling convention correctly, each of these things will happen automatically.Your code must assemble with no warnings or errors. (LC3Tools will tell you if there are any). If your code does not assemble, we will not be able to grade that file and you will not receive any points. Good luck and have fun!2.1 Part 1 2.1.1 GCD The GCD of a pair of numbers is the greatest number that is a divisor for both numbers. In GCD.asm, we want you to implement two subroutines: MOD and GCD (see the following pseudocodes for more details). Note that the numbers that we will give you are strictly greater than or equal to 0. As a reminder, please do not change the names of provided subroutines. Otherwise, your submission will not pass the autograder. Remember to get your arguments from the stack! For example: GCD(12, 32) should return 4 GCD(50, 20) should return 10 GCD(2, 1) should return 1 GCD(0, 1) should return 1 2.1.2 Pseudocode Here are the pseudocodes for these subroutines: MOD(int a, int b) { while (a >= b) { a -= b; } return a; } GCD(int a, int b) { if (b == 0) { return a; } while (b != 0) { int temp = b; b = MOD(a, b); a = temp; } return a; } Note: Since there are two loops in the MOD and GCD subroutines, make sure you use different label names for those loops. In general, you should not have two labels with the same name in the same file. 4 2.2 Part 2 2.2.1 isPalindrome For this part of this assignment, you will be checking whether an array of chars is a palindrome in isPalindrome.asm. As a reminder, please do not change the names of provided subroutines. Otherwise, your submission will not pass the autograder. You may be wondering . . . didn’t you already do something like this in HW5? Yes, but this time, you must do it recursively. 2.2.2 Pseudocode Here is the pseudocode for this subroutine: Parameters: – addr string: the starting address of the string – len: the length of the string (not including the null terminator) Returns: 1 if the string is a palindrome, 0 otherwise. IS_PALINDROME(addr string, len) { if (len == 0 || len == 1) { return 1; } else { if (string[0] == string[len – 1]) { return IS_PALINDROME(string + 1, len – 2); } else { return 0; } } } Lets do an example to see how our array looks throughout our above algorithm! isPalindrome([’r’,’o’, ’t’, ’o’, ’r’]) ’r’ ’o’ ’t’ ’o’ ’r’ → isPalindrome([’o’, ’t’, ’o’]) ’o’ ’t’ ’o’ → isPalindrome([’t’]) ’t’ → Return 1 5 2.3 Part 3 2.3.1 DFS For this part of the assignment, you will write a recursive subroutine for a graph in DFS.asm. The parameters of the function are the graph’s root node (provided as an address in memory), and the target node we are searching for (the node’s data, not the address). As a reminder, please do not change the names of provided subroutines or otherwise your submission will not pass the autograder. If you are unfamiliar with DFS and would like more information about it, see https://www.baeldung.com/ cs/depth-first-search-intro. 2.3.2 Graph Data Structure The below figures show us the visual representation of a graph, as well as the memory representation for a node. We are able to implement this abstract graph data structure as a collection of nodes – where each node holds the following information: its data (aka its number/value), and the addresses of its neighboring nodes (nodes that it is connected to via a line or an edge). Thus, each node is really a memory address, representing the start of the chunk of memory where it will store this information. In this example, we can look at the starting node (1) in our graph. At memory address x4000, it stores the node’s data (= 1), at address x4001 it will store the address of its neighboring node (2), at address x4002 the address of its neighboring node (3), and at address x4001 the address of its neighboring node (5). Note: We will know that we have gone through all of the neighboring nodes if the next address has a value of 0. 2.3.3 Visited Set and Visited Vector In the context of graph algorithms, we often make use of a visited set to keep track of all the nodes that have been visited. This allows us to efficiently check in O(1) time whether a node has already been traversed. Considering the constraints of LC-3 assembly and the overhead required to implement such a data structure, we will instead be using a visited vector. This vector is a 16-bit binary number that is going to be stored at a specific address in memory, so that it will persist outside of the scope of a single subroutine. Within the vector, each bit corresponds to a node, i.e. bit 0 corresponds to node 0, bit 5 corresponds to node 5, etc. If a bit is 0, that node is not part of the visited set, and if it is 1, that means the node has already been 6 visited. This leads to the obvious constraint that the visited vector can only represent up to 16 nodes. All test cases will use 16 nodes or less to ensure that a single vector is sufficient. In order to manage the visited vector, you will first implement 2 helper functions: IS VISITED() and SET VISITED(). The pseudocode for these functions can be found below. Let’s see an example of DFS in action on this graph. Our starting node will be 1, and our target node is 5. DFS(Address of Node 1, 5) 7 2.3.4 Pseudocode Here is the pseudocode for these subroutines: SET_VISITED(addr node) { visited = mem[mem[VISITED_VECTOR_ADDR]]; data = mem[node]; mask = 1; while (data > 0) { mask = mask + mask; data–; } mem[mem[VISITED_VECTOR_ADDR]] = (visited | mask); //Hint: Use DeMorgan’s Law! } IS_VISITED(addr node) { visited = mem[mem[VISITED_VECTOR_ADDR]]; data = mem[node]; mask = 1; while (data > 0) { mask = mask + mask; data–; } return (visited & mask) != 0; } DFS(addr node, int target) { SET_VISITED(node); if (mem[node] == target) { return node; } result = 0; for (i = node + 1; mem[i] != 0 && result == 0; i++) { if (! IS_VISITED(mem[i])) { result = DFS(mem[i], target); } } return result; } Note: Since there are multiple loops and conditionals in the all of the subroutines in this file, make sure you use different label names for those loops. In general, you should not have two labels with the same name in the same file. 8 3 Autograder To run the autograder locally, follow the steps below depending on your operating system: • Mac/Linux Users: 1. Navigate to the directory your homework is in (in your terminal on your host machine, not in the Docker container via your browser) 2. Run the command sudo chmod +x grade.sh 3. Now run ./grade.sh • Windows Users: 1. In Git Bash (or Docker Quickstart Terminal for legacy Docker installations) navigate to the directory your homework is in 2. Run chmod +x grade.sh 3. Run ./grade.sh Note: The checker may not reflect your final grade on this assignment. We reserve the right to update the autograder as we see fit when grading. 4 Deliverables Turn in the following files to Gradescope: 1. GCD.asm 2. isPalindrome.asm 3. DFS.asm Make sure that you are submitting .asm files!! The autograder will not grade .obj files. Please do not wait until the last minute to run/test your homework. Last-minute turn-ins will result in long queue times for grading on Gradescope. You have been warned. 5 Demos This homework will be demoed. The demos will be 10 minutes long and will occur IN PERSON. Stay tuned for details as the due date approaches. Please note: Your grade for this assignment is split into 2 parts. 50% of your grade is based upon how well you do with the autograder. The other 50% is determined by how well you do in the demo. Again, more details to come soon. 9 6 Appendix 6.1 Appendix A: LC-3 Instruction Set Architecture 10 6.2 Appendix C: LC-3 Assembly Programming Requirements and Tips 1. Your code must assemble with NO WARNINGS OR ERRORS. To assemble your program, open the file with LC3Tools. It will complain if there are any issues. If your code does not assemble you WILL get a zero for that file. 2. Comment your code! This is especially important in assembly, because it’s much harder to interpret what is happening later, and you’ll be glad you left yourself notes on what certain instructions are contributing to the code. 3. DO NOT assume that ANYTHING in the LC-3 is already zero. Treat the machine as if your program was loaded into a machine with random values stored in the memory and register file. The autograder will do the same. 4. As you step through your assembled code in LC3Tools, registers or memory locations that have updated after one step will be highlighted to you. Use this to your advantage to figure out bugs in your assembly if you are failing a test case. 5. Do NOT execute any data as if it were an instruction (meaning you should put .fills after HALT or RET). All your program does is interpret the values RAM as instructions until it reaches HALT. If you use .fill before your program HALTS, your program might interpret what you filled as an instruction and try to execute it! 6. Test your assembly. Don’t just assume it works and turn it in. 7. When translating pseudocode into assembly, don’t skip over the closing brackets! Even though they’re only one character long, perhaps they also might need to be translated into assembly… 11 7 Rules and Regulations 1. Please read the assignment in its entirety before asking questions. 2. Please start assignments early, and ask for help early. Do not email us the night the assignment is due with questions. 3. If you find any problems with the assignment, please report them to the TA team. Announcements will be posted if the assignment changes. 4. You are responsible for turning in assignments on time. This includes allowing for unforeseen circumstances. If you have an emergency please reach out to your instructor and the head TAs IN ADVANCE of the due date with documentation (i.e. note from the dean, doctor’s note, etc). 5. You are responsible for ensuring that what you turned in is what you meant to turn in. No excuses if you submit the wrong files, what you turn in is what we grade. In addition, your assignment must be turned in via Gradescope. Email submissions will not be accepted. 6. See the syllabus for information regarding late submissions; any penalties associated with unexcused late submissions are non-negotiable.
So far in this class, you have seen how binary or machine code manipulates our circuits to achieve a goal. However, as you have probably figured out, binary can be hard for us to read and debug, so we need an easier way of telling our computers what to do. This is where assembly comes in. Assembly language is symbolic machine code, meaning that we don’t have to write all of the ones and zeros in a program, but rather symbols that translate to ones and zeros. These symbols are translated with something called the assembler. Each assembler is dependent upon the computer architecture on which it was built, so there are many different assembly languages out there. Assembly was widely used before most higher-level languages and is still used today in some cases for direct hardware manipulation.The goal of this assignment is to introduce you to programming in LC-3 assembly code. This will involve writing small programs, translating conditionals and loops into assembly, modifying memory, manipulating strings, and converting high-level programs into assembly code. You will be required to complete the four functions listed below with more in-depth instructions on the following pages: 1. fibonacci.asm 2. uppercaseInRange.asm 3. hexStringToInt.asm 4. palindromeWithSkips.asm1.3 Criteria Your assignment will be graded based on your ability to correctly translate the given pseudocode into LC-3 assembly code. Check the deliverables section for deadlines and other related information. Please use the LC-3 instruction set when writing these programs. More detailed information on each instruction can be found in the Patt/Patel book Appendix A (also on Canvas under “LC-3 Resources”). Please check the rest of this document for some advice on debugging your assembly code, as well some general tips for successfully writing assembly code.You must obtain the correct values for each function. Your code must assemble with no warnings or errors (LC3Tools will tell you if there are any). If your code does not assemble, we will not be able to grade that file and you will not receive any points. Each function is in a separate file, so you will not lose all points if one function does not assemble. Good luck and have fun!2.1 Notes • The provided pseudocode is fully correct and will naturally account for all assumptions and edge cases. It might not be the most efficient solution, and this is OK. • Make sure you conceptually understand what labels are and what using them really means behind the scenes. All problems will revolve around using labels to load inputs and store outputs. • Be careful changing anything outside the first .orig x3000 and HALT lines in every file. Watch out for the instructions in each file to know what you can and cannot change for testing. Your autograder’s functionality will depend on some of the initial code we provided. • Be wary of the differences between instructions like LD and LEA. When you have an answer, make sure you’re storing to the correct address. Trace through your code on LC3Tools if you’re not sure if you’re using the correct instruction.• Debugging via LC3Tools helps tremendously. Eyeballing assembly code can prove to be very difficult. It helps a lot to be able to trace through your code step-by-step, line-by-line, to see if each assembly instruction does what you expected. • You can check if far-away addresses contain expected values in LC3Tools by entering an address in the Jump To Location input and pressing Enter.2.2 Part 1: Fibonacci Given N, calculate and store the first N Fibonacci numbers in an array starting at RESULT. Assumptions: • The first Fibonacci number is 0. • N can be 0 or positive (it will not be negative). Relevant labels: • N: Holds the value of N. • RESULT: Holds the base address of the array that will hold the Fibonacci numbers. Say N = 5. After running your program, memory starting at RESULT should hold 0, 1, 1, 2, 3. Implement your assembly code in fibonacci.asm Suggested Pseudocode: n = mem[N]; resAddr = mem[RESULT] if (n == 1) { mem[resAddr] = 0; } else if (n > 1) { mem[resAddr] = 0; mem[resAddr + 1] = 1; for (i = 2; i < n; i++) { x = mem[resAddr + i – 1]; y = mem[resAddr + i – 2]; mem[resAddr + i] = x + y; } } 4 2.3 Part 2: Uppercase In Range Given a string starting at the address in STRING, convert the characters that are in the range between START and END to uppercase. Assumptions: • Possible characters in the string: lowercase letters, uppercase letters, and spaces • If a character in the range is not lowercase, leave it as it is. • The range should include START and not include END. So, change all the characters to uppercase in range [START, END). • END may be greater than the length of the string. If that is the case, apply the conversion to all of the characters in the string from START onwards. Relevant labels: • STRING: Holds the base address of the array containing the string. • LENGTH: Holds the length of the string. • START: Holds the index of the first character you want to uppercase. • END: Holds the index following that of the last character you want to uppercase. • ASCII A: Holds the ASCII value of lowercase a. Say the string is gOOglE, START is 1, and END is 4. After running your program, the string starting at the address in STRING should be gOOGlE. Implement your assembly code in uppercaseInRange.asm Suggested Pseudocode: String str = “touppERcase”; int start = mem[START]; int end = mem[END]; int length = mem[LENGTH]; if (end > length) { end = length; } for (int x = start; x < end; x++) { if (str[x] >= ’a’) { str[x] = str[x] – 32; } }2.4 Part 3: Hex String to Int Given an hex number encoded as a string, translate it to its numerical value. The value stored at RESULTADDR represents another different address. Store your numerical value result at this different address. Assumptions: • ‘0’ ≤ hexString[i] ≤ ‘9’ and ‘A’ ≤ hexString[i] ≤ ‘F’ • The provided hex string will be nonnegative. • We do not have to worry about overflow. Relevant labels: • HEXSTRING: Holds the starting address of the hex string. • LENGTH: Holds the length of the hex string. This will always be 4. • RESULTADDR: Holds the address of where you will store your numerical value result. • ASCIIDIG: Holds the value 48. • ASCIICHAR: Holds the value 55. • SIXTYFIVE: Holds the value 65. Say the string at HEXSTRING was “211F”. After running your program, mem[mem[RESULTADDR]] should equal 8479 (base 10). If mem[RESULTADDR] = x4000, then this means the value all the way at memory address x4000 should be changed to 8479. The value at RESULTADDR should be unchanged. Recall how we interpret characters using ASCII (ASCII table listed in Appendix). You might find the ASCII label useful. Implement your assembly code in hexStringToInt.asm Suggested Pseudocode: String hexString = “F1ED”; int length = 4; int value = 0; int i = 0; while (i < length) { int leftShifts = mem[LENGTH]; while (leftShifts > 0) { value += value; leftShifts–; } if (hexString[i] >= 65) { value += hexString[i] – 55; } else { value += hexString[i] – 48; } i++; } mem[mem[RESULTADDR]] = value;2.5 Part 4: Palindrome With Skips Given a string, calculate if it’s a palindrome if you don’t consider any instances of the character located at the address in CHARADDR. ANSWERADDR should contain another address. At this address, store true if the string is palindrome and false if it is not. Assumptions: • The characters in the string and the character to remove can be lowercase, uppercase, spaces, numbers, or special characters. • We still consider empty strings as palindromes. • We agree that a 1 in memory represents true and a 0 represents false. Relevant labels: • CHARADDR: Holds the address of the character you don’t consider when deciding if the string is a palindrome. • STRING: Holds the address of the string that you will evaluate. • ANSWERADDR: Holds the address of where you should store the boolean result. Say the provided string is “aibohphooobia” and the given character is “o”. After running your program, mem[mem[ANSWERADDR]] should equal true. Notice we are only given the starting address our string. How do we know which address the string ends? Let’s agree that if we ever read a numerical 0 value, then the string ends. If you take a look at an ASCII table (listed in Appendix), you can see the numerical value 0 is interpreted as NULL, which by convention denotes the end of a string. NOTE: In the pseudocode below, ‘’ means the numerical value 0. It is different from ‘0’, which is the numerical value 48. Implement your assembly code in palindromeWithSkips.asm Suggested Pseudocode: String str = “aibohphobia”; char skipChar = mem[mem[CHARADDR]]; int length = 0; while (str[length] != ’’) { length++; } int left = 0; int right = length – 1; boolean isPalindrome = true; while(left < right) { if (str[left] == skipChar) { left++; continue; } if (str[right] == skipChar) { right–; continue; 7 } if (str[left] != str[right]) { isPalindrome = false; break; } left++; right–; } mem[mem[ANSWERADDR]] = isPalindrome; 3 Deliverables Turn in the following files on Gradescope: 1. fibonacci.asm 2. uppercaseInRange.asm 3. hexStringToInt.asm 4. palindromeWithSkips.asm Note: Try to start homeworks early. It will be easier to get help if you get stuck, and last minute turn-ins will result in long queue times for grading on Gradescope.4 Running the Autograder and Debugging LC-3 Assembly For this homework, there are a variety of test cases associated with each assembly file you implement. Additionally, there are two ways to grade your submission: locally, or through Gradescope. To run the local grader: 1. Ensure that you have Docker running. 2. Navigate to the directory your homework is in. 3. If you are on MacOS or Linux, run the command sudo chmod +x grade.sh 4. Now run ./grade.sh if you are on MacOS/Linux, or .grade.bat on Windows. When you turn in your files on Gradescope for the first time, you may not receive a perfect score. Does this mean you change one line and spam Gradescope until you get a 100? No! Each test case details exactly how we are testing your assembly code (e.g. writing to labels, writing strings, expecting a certain answer, etc.). Here is an example: Writing word “touppercase” at MEM[MEM[WORD]] Writing start argument ’2’ at MEM[START] Writing end argument ’9’ at MEM[END] Running student assembly… –Outputs correct answer: Expected: toUPPERCAse, Got: touppercase You can use this information to replicate such tests yourself locally on LC3Tools. 9 5 Appendix 5.1 Appendix A: ASCII Table Figure 1: ASCII Table — Very Cool and Useful! 10 5.2 Appendix B: LC-3 Instruction Set Architecture 11 5.3 Appendix C: LC-3 Assembly Programming Requirements and Tips 1. Your code must assemble with NO WARNINGS OR ERRORS. To assemble your program, open the file with LC3Tools. It will complain if there are any issues. If your code does not assemble you WILL get a zero for that file. 2. Comment your code! This is especially important in assembly, because it’s much harder to interpret what is happening later, and you’ll be glad you left yourself notes on what certain instructions are contributing to the code. 3. DO NOT assume that ANYTHING in the LC-3 is already zero. Treat the machine as if your program was loaded into a machine with random values stored in the memory and register file. The autograder will do the same. 4. As you step through your assembled code in LC3Tools, registers or memory locations that have updated after one step will be highlighted to you. Use this to your advantage to figure out bugs in your assembly if you are failing a test case. 5. Do NOT execute any data as if it were an instruction (meaning you should put .fills after HALT or RET). All your program does is interpret the values RAM as instructions until it reaches HALT. If you use .fill before your program HALTS, your program might interpret what you filled as an instruction and try to execute it! 6. Test your assembly. Don’t just assume it works and turn it in. 7. When translating pseudocode into assembly, don’t skip over the closing brackets! Even though they’re only one character long, perhaps they also might need to be translated into assembly… 12 6 Rules and Regulations 1. Please read the assignment in its entirety before asking questions. 2. Please start assignments early, and ask for help early. Do not email us the night the assignment is due with questions. 3. If you find any problems with the assignment, please report them to the TA team. Announcements will be posted if the assignment changes. 4. You are responsible for turning in assignments on time. This includes allowing for unforeseen circumstances. If you have an emergency please reach out to your instructor and the head TAs IN ADVANCE of the due date with documentation (i.e. note from the dean, doctor’s note, etc). 5. You are responsible for ensuring that what you turned in is what you meant to turn in. No excuses if you submit the wrong files, what you turn in is what we grade. In addition, your assignment must be turned in via Gradescope. Email submissions will not be accepted. 6. See the syllabus for information regarding late submissions; any penalties associated with unexcused late submissions are non-negotiable.
