In this project, you will be implementing a (partial) RISCV interpreter in C. Your interpreter will support a subset of the instructions that you implemented in Logisim in P2.
We provide several starter files, which you should also familiarize yourself with before beginning the project. Your job is to implement everything marked as // TODO: in linkedlist.c, hashtable.c, riscv.c.
While it is certainly possible to use the native C compiler on your machine, we highly suggest that you make sure that your implementation works in either the course-provided VM, or SSH on the UGCLinux machines. Our autograder will be grading your assignment using the same environment as the VM/SSH.
What to Submit
A complete implementation of linkedlist.c
A complete implementation of hashtable.c
A complete implementation of riscv.c
In the shared Github repository, you should find starter files. We recommend taking a look at the header files ( *.h ) and the source files ( *.c ).
A Makefile is provided to help with compiling your code. As you progress through each section of this project, there will be a make target that you can use to compile the main function. This will generate an executable that you can run to test your code. If you are interested in reading more about Makefiles, Section F.6 of this chapter
(http://pages.cs.wisc.edu/~remzi/OSTEP/lab-tutorial.pdf) is a good read.
- make hashtable
- make riscv_interpreter
By default, make will create the riscv_interpreter executable to run.
Since you will be supporting memory instructions, you need to have a way to represent memory.
A naive attempt would allocate a large array with 2^31 elements, and directly index into the array for each memory request.
However, this poses certain limitations:
the majority of the array will be unused, leading to waste it may not always be possible to allocate 2^31 bytes of memory for a single process (OS limitation)
Thus, we require you to simulate memory in a specific way, as specified below, which addresses both of the above limitations.
Associative Linked List
You may already be familiar with the notion of an associative linked list. It is one way to represent a dictionary, or a set of key-value mappings. Each node contains a key, a value, and a pointer to the next node. In this case, we are working with mappings from a 32-bit integer (the key, representing a memory address) to another 32-bit integer (the value at the given address).
The associative linked list can be visualized as follows:
For this part of the project, it will be valuable to walk through the ArrayList Lab
(https://canvas.cornell.edu/courses/42905/assignments/381692) and familiarize yourself with pointers and structs.
Begin by implementing an associative linked list in linkedlist.c . The specification of each function can be found in linkedlist.h .
- linkedlist_t *ll_init()
- void ll_free(linkedlist_t* list)
- void ll_add(linkedlist_t *list, int key, int value)
- int ll_get(linkedlist_t *list, int key)
- int ll_size(linkedlist_t *list)
Run make linkedlist to create a linkedlist executable to run. This will run the code found in linkedlist_main.c .
While an associative linked list can certainly simulate memory, it has performance limitations. You may have noticed that as you insert more key-value pairs into the linked list, the time it takes to find the matching key grows linearly. That is, the data structure provides an O(n) lookup. Let’s see if we can use a different data structure to achieve a better performance.
You will now simulate memory in this project using a hash table, which provides much better performance than the associative linked list from the previous section. Once again, you are working with mappings from a 32-bit integer (the key,To implement your hashtable, you MUST use your linked list implementation. That is, you should represent the buckets in your hash table using associative linked lists, which you previously implemented. It can be visualized as follows:
Implement the following functions in hashtable.c . The specification of each function can be found in hashtable.h .
- hashtable_t *ht_init(int num_buckets)
- void ht_free(hashtable_t* table)
- void ht_add(hashtable_t *table, int key, int value)
- int ht_get(hashtable_t *table, int key)
- int ht_size(hashtable_t *table)
You do not need to worry about the resizing case of a traditional hashtable. We intentionally use a fixed number of buckets, and will initialize your hashtable with a high number of buckets when grading the performance of your hashtable. Similarly, feel free to use a high number of buckets to simulate memory in your riscv interpreter, but do keep in mind memory constraints of the system (i.e. you don’t need 2^31 buckets).
Run make hashtable to create a hashtable executable to run. This will run the code found in hashtable_main.c .
For this part of the project, you should implement the init(), end(), step() functions in riscv.c . The specification for these functions can be found in riscv.h .
You will need to convert a string corresponding to a RISCV instruction to something that you can subsequently work with.
Hence, you will have to do some string splitting. You may already be familiar with the tools available for string splitting; if not, it is worth reading up on them
You have probably noticed that RISCV instructions follow a certain format depending on the type of operation. Before you begin implementing anything, we strongly suggest that you take a look at the get_op_type function provided in riscv.c . We recommend that you use this, as it will likely make things simpler for you.
Spaces should not affect the correctness of your interpreter. For example:
- addi x5,x0,12 should be handled the same way as addi x5, x0 , 12
- sw x12,4(x0) should be handled the same way as sw x12 , 4 ( x0 )
- sw x5, 16(x0) should be equivalent to sw x5, 0x10(x0)
Your interpreter must support the following operations in addition to empty strings (i.e. null terminator):
** Note: “Memory-type” is not a formal RISCV instruction type; we group the instructions this way to make parsing easier for you.
Don’t overthink these; most of them can be done quite simply. However, take note of edge cases and check that your interpreter behaves as specified in the RISCV reference manual (https://content.riscv.org/wp-content/uploads/2017/05/riscv-spec-v2.2.pdf) .
Memory is little-endian. We recommend implementing memory as byte-addressed, which will allow each memory address ( 0x00000000 , 0x00000001 , …) to exist as keys in your simulated memory, mapping to a value of a single byte. Other address modes are welcome (such as word-addressed), but discouraged.
Strings passed into your interpreter will either be empty strings or valid RISCV instructions. Valid means that the operation will be in the list of supported operations above, registers will be valid x[0-31] , immediates will be a maximum of 20 bits in either decimal or hexadecimal notation, at least one space follows the operation, and commas are used as the separator between tokens (there can still be any number of spaces).
Formally, all valid instructions satisfy the regex format (https://regex101.com) (though, the set of tokens may not match the format of the operation):
[a-z]+ +x[0-9]+ *, *((x[0-9]+ *, *(x[0-9]+|(0x[0-9a-f]+|-?[0-9]+)))|(0x[0-9a-f]+|-?[0-9]+)( *\( *x[0-9]+ *\))?)
本网站支持淘宝 支付宝 微信支付 paypal等等交易。如果不放心可以用淘宝交易！
E-mail: email@example.com 微信:itcsdx