creates a working implementation of a Turing universal machine emulator
accepts 14 bytecode instructions
add, divide, multiply, bitNAND, halt, segmented load, segmented store, load value, conditional move, load program, map segment, unmap segment, input, output
later optimized the program to run in 1% of the original time
Skills: C, Object-Oriented Programming, program optimization, unit-testing, bitwise operations
Our process for designing and implementing the universal machine program is described below...
Firstly, we create a visual representation of our overarching architecture plan for the program:
Now, we break down each file/module by describing the general purpose of the module and then describing the functions [function contract; function declaration] each module will need:
In_out_device [click to expand]
In_out_device uses stdin and stdout, performs input and output on unsigned 8-bit chars (1 byte).
It holds two public functions responsible for reading 8-bit characters from stdin and printing 8-bit characters to stdout.
/********** read_byte ********
* Takes a unsigned 8-bit character from stdin and returns it
* Inputs: Nothing
* Returns: unsigned 8 bit character
************************/
char readbyte(FILE *input_stream)
/********** print_byte ********
* prints out given unsigned 8-bit character to stdout
* Inputs:
* int output: the 8-but character to output
* Returns: Nothing
************************/
void printbyte(int output)
Operation [click to expand]
Holds the registers, which is declared as an array of size 8 containing uint32_t words. Contains implementations of all instruction functions. Certain instructions will add to, remove from or otherwise modify the address space.
/********** run_program ********
* Keeps track of the program counter and calls functions to
* run each instruction
* Inputs:
* Seq_t address_space: the virtual address space for the
* program to use
* Returns: Nothing
************************/
void run_program(AddressSpace_T address_space)
Um [click to expand]
Holds the main function responsible for calling all other functions. Initializes the address space. Uses I/O interface to read instructions as 32-bit words and store them in m[0] of address space. Then calls run_program in Operation and sends in the address space.
/********** main ********
* takes in command line arguments, calls appropriate functions to read
* program and subsequently run machine
* Inputs:
* argc: number of inputs to command line
* argv: an array of command line arguments
* Returns: EXIT_FAILURE if command line argument not valid
************************/
int main(argc, *argv[])
/********** read_program ********
* Uses I/O interface to read all instructions in stdin and store them in m[0]
* of a initialized address space
* Inputs: Nothing
* Returns: Struct AddressSpace_T address_space: the address space of the
* memory
************************/
void read_program(*Seq_t Address_Space)
Address_space (warning! this one has many components!) [click to expand]
AddressSpace: A struct of a Hanson Sequence, int seq_capacity and int curr_elems. The sequence will store pointers to UArrays. UArray is the memory segment containing the 32-bit instructions. Each memory segment (Uarray) has a corresponding 32-bit identifier, which corresponds to the index of the segment in the sequence.
The identifiers for previously used and currently unmapped segments are stored in a Hanson Sequence. When a new segment needs to be mapped, the program will first check for a used identifier to reuse, if one is not available the program will create a new identifier.
/********** intialize_space ********
* Initializes the address space which will be used to store addresses made of
* memory segments that hold instructions
* Inputs:
* int file_size: the size of the input file with the instructions
* Returns: the AddressSpace struct
* Expects: the address sequence and UArray of instructions not to be NULL
************************/
S *initialize_space(int file_length)
/********** get_instruction ********
* gets the instruction at segment 0
* Inputs:
* uint32_t prog_count: the program counter,
* tells us where we are in the program
* S as: the AddressSpace struct
* Returns: the instruction at the given index
************************/
uint32_t get_instruction(int prog_count, S as)
/********** put_instruction ********
* puts an instruction at given index in segment 0
* Inputs:
* uint32_t word: the instruction to be put in the segment
* uint32_t index: the index where the instruction is to be put
* S as: the AddressSpace struct
* Returns: -
************************/
void put_instruction(uint32_t word, int prog_count, S as)
/********** get ********
* gets the given instruction at a given offset, in a given segment
* Inputs:
* uint32_t segment: the segment from which the instruction is
* to be retrieved from
* uint32_t offset: the index where the instruction exists
* S as: the AddressSpace struct
* Returns: the desired instruction
* Notes:
* If the memory segment specified is out of bounds or unmapped,
* the program will fail
************************/
get(int segment, int offset, S as)
/********** put ********
* Updates the element at the specified offset in the specified segment of the
* given AddressSpace struct with the provided word.
* Inputs:
* uint32_t segment: The index of the segment in the AddressSpace
* struct
* int offset: The offset within the segment where the word will be
* stored.
* uint32_t word: The word to be stored in the specified location.
* S as: The AddressSpace struct containing the segment to be updated.
* Returns: Nothing
* Notes:
* If the memory segment specified is out of bounds or unmapped,
* the program will fail
************************/
put(int segment, int offset, uint32_t word, S as)
/********** free_address_space ********
* Frees the memory allocated for the AddressSpace structure and all its mapped * elements.
* Inputs:
* S *as: A pointer to the AddressSpace struct to be freed.
* Returns: Nothing
* Notes:
* - Frees the memory associated with each mapped element in the
* AddressSpace struct
* - Frees the memory associated with the sequence of mapped elements and
* available IDs.
* - Frees the memory associated with the AddressSpace struct
************************/
void free_address_space(S *as)
/********** map ********
* Maps a new memory segment in the address space, returning the index at which * the element is mapped. If available, reuses an ID from the sequence of
* available IDs; otherwise, assigns a new ID.
* Inputs:
* int size: The size of the new element to be mapped.
* S as: The AddressSpace struct in which the new element will be
* mapped.
* Returns: uint32_t containing the index/indentfier at which the element is
* mapped.
************************/
uint32_t map(int size, S as)
/********** unmap ********
* Unmaps a memory segment at the specified index in the address space, freeing
* the memory associated with the element.
* Inputs:
* uint32_t index: The index of the element to be unmapped.
* S as: The AddressSpace struct containing the elements to be
* unmapped.
* Returns: Nothing
* Notes: if the memory segment being free'd is m[0] or is already unmapped,
* the program will fail
************************/
void unmap(uint32_t index, S as)
/********** load_program ********
* Loads memory segemnt at index into segment 0
* Inputs:
* uint32_t index: The index of the new program
* S as: The AddressSpace struct where the new program
* will be taken from
* Returns: Nothing
* Note: the memory segment being loaded can be of size 0
************************/
void load_program(uint32_t index, S as)
Next, we describe our implementation and testing plan below: [click to expand]
Create in_out_device.c and in_out_device.h files
link together, read in and then print “Hello World”, compile, test
Create um main
Create read_program function which uses in_out_device to read bytes into a word.
Compare read_program output with original input
Create address space interface
link & test linking
Create intialize_space(int size)
ensure that it creates a Seq_t of appropriate size by outputting length
Create get(int segment, int offset) and put(int segment, int offset, uint32_t word) functions
ensure they are putting and getting correct instructions by comparing their outputs with input file
test get() against put()
Then create get_instruction(int prog_count) and put_instruction(uint32_t word, int prog_count) which will just call the general get and put on segment 0
test get_instruction() against put_instruction()
Create free_address_space(&Seq_t as);
Run with valgrind to ensure memory is freed
**More specific address space tests are described below
Write um main to read in instructions, initialize address space and set m[0] to address space
Test that all 32 bits are properly bitpacked and stored in address space m[0]
Test that it is read big-endian and not in the wrong order
Write instruction functions
Create the registers array and set elems equal to 0.
Create the code that uses get_instruction() and program counter to unpack the current instruction’s opcode and registers.
Test this by using umlabwrite to create UM instructions and then verify that the opcode and registers match
Create the switch statement to call the different instructions
Use the switch statement and umlabwrite to test that all instructions are properly unpacked
Halt
Test program ends w/o memory errors, run with valgrind
Test halting at before and after every other instruction
We also know that all testing functions made in umlab all call halt at well. This can serve as additional testing.l
Math functions
Create the functions Add, subtract, multiply and divide, bitwise Nand
For all of these functions create unit_tests that will test individual cases of addition, subtraction, ect. and assert that the operations were performed correctly.
Use umlabwrite.c to test individual cases for each math operation
Add: should fail if output > 255
Multiply: should fail if output > 255
Divide: should fail if divide by zero or output > 255
Test halting before and after math functions
Memory functions
map_segment, unmap_segment
test against each other, mapping and unmapping a segment
valgrind!
Create segmented_store and segmented load
Segmented_store:
Fail if store in out of bounds or unmapped
testing done in get and put functions of AddressSpace
Test store in the range of a uint_32 to make sure all fit
segmented load:
Fail if load from out of bounds or unmapped
output the value we are loading into register, ensure it is the desired value
Test loading in the range of a uint_32 to make sure all fit
load_program
test that the program_counter is “pointing” to the new program
Test load program in a for-loop where it calls the instructions already in m[0] again
input, output
use output test function made in lab
test input with a value out of bounds (>255 or 0>)
test input and output against each other
test that if input end of input is signaled, r[c] = ~0
load_value
try various values to load and output them to ensure correct values were loaded, we also have loadval from lab which was tested in lab that was already tested in lab
Run with valgrind
Use “UM binaries for COMP 40” collection for final testing
Think deeply about what cases should fail and which should CRE
Ex: opcode>13, register>7
Because the AddressSpace module has so many functions and moving parts, we came up with additional tests for AddressSpace: [click to expand]
AddressSpace testing:
Will create temp helper function: address_size, address_capacity, segment_size(index) for testing purposes
void test_iniatlize()
/* Test creating address space with m[0] of varying sizes & free them */
assert (space_length == length)
of length 1, 0, 50, 1000
free(&every created space)
void map_diff_size()
Map segments of sizes 0-1000
Assert that mapped segments are all filled with 0s
void get_put()
Map segments of address space that will be tested
Using segmented load and segmented store: try storing and retrieving words of sizes 0-1000
Use asserts to ensure what was stored is the same as what was loaded in
Try overwriting the same location with Segmented Store and assert that the word was properly stored
Free immediately and valgrind
void test_segSize()
For index 0 - x: Map x memory segments, use segmented store to fill all x segments.
assert address_size(index) == x *temporary public function
assert address_capacity == x *temporary public function
void all_fail()
try & catch failure
Unmap_non_init - fail allowed
Map_already_init - fail allowed
put segment unmapped - fail allowed
Get segment unmapped - fail allowed
Put & get out of bounds - fail allowed
void re_use_all_IDs()
Map x segments
Unmap x segments
Remap x segments
Assert (address_size == x)
void re_use_one_ID()
Map x segments
unmap 1-x segments
remap 1 segment
assert(address_size == x)
void re_use_some_IDs()
map x segments
unmap x - (x/2) segments
remap x/2 segments
assert address_size == x
void load program()
Load programs of varying lengths (0-1000)
Ensure that previous instructions are free’d
run with valgrind
Ensure a copy of of new program is made, and not moved from its previous location
check previous location after loading new program into m[0] to ensure it hasn’t moved
Ensure new program is loaded into m[0], not any other location
check and output what is at m[0]
Ensure that the whole program is loaded and we are not losing any data
check length before and after loading