[SOLVED] MIPSCSE 220: Systems Fundamentals I Homework #3

CSE 220: Systems Fundamentals I

Homework #3

Fall 2017
Assignment Due: November 10, 2017 by 11:59 pm via Sparky

All test cases MUST execute in 100,000 instructions or less. Efficiency is an important aspect of programming.

Any excess output from your program (debugging notes, etc) may impact your grading. Do not leave erroneous printouts in your code!

Introduction

In this assignment you will be solidifying your understanding of MIPS register conventions and writing more complex functions. We will build upon homework 2 and write a recursive function.

You MUST implement all the functions in the assignment as defined. It is OK to implement addi- tional helper functions of your own in hw3.asm .

CSE 220 Fall 2017 Homework #3 Page 1

You MUST follow the MIPS calling and register conventions appropriately (i.e brute-forcing by saving all registers does not count). If you do not, you WILL lose points.

Getting started Youcanusethefilesyoualreadyhaveforhw2,butyouMUSTcopyallfunctionsfromyour hw2.asm

fileinto hw3.asm.Dontforgettochangethecommentsatthetopofyourasmfileappropriately. You can get additional test files from hw3.zip which is available on Piazza in the homework

section of Resources.

You will only submit your file via Sparky. Make sure that all code required for imple- menting your functions ( and .data ) are included in the hw3.asm file! To make sure that your code is self-contained, try assembling your hw3.asm file by itself in MARS. If you get any errors (such as a missing label), this means that you need to refactor (reorganize) your code, possibly by moving labels you inadvertently defined in a main file to hw3.asm .

Part 1: Correct your HW2 functions

Update the four functions listed below you wrote for the the previous homework so that they follow proper register conventions. Also see the note about an update to

verifyIPv4Checksum that you may need to make in your code. If you didnt complete or get a perfect score in the previous homework, you can use the grading tests to help debug your existing code.

The following functions are needed for Part 2 of this assignment:

replace1st
printStringArray processDatagram

hw3.asm

.text

Make sure to initialize all of your values within your functions! Never assume registers or memory will hold any particular values!

CSE 220 Fall 2017 Homework #3 Page 2

verifyIPv4Checksum
Your implementation MUST work with ANY Header length value in the range of

[5,15].

We will check your register conventions AGAIN! Make sure ALL functions for this home- work follow register conventions. Refer to the lecture notes or ask your TA to review in recitation or office hours if you are still unclear about the conventions.

Part 2: Handling an unordered set of IPv4 packets

Inhomework1,wesetthe Flag and Fragment Offset fieldsofanIPv4packettospecifyif the packet was the first packet, the only packet, or a member of a sequence of packets. In home- work 2, we extracted data from an ordered sequence of packets stored in an array and ignored these fields.

In this homework, we will create a function which will perform similarly to the homework 2s extractData function. It will handle larger packet lengths, perform checks on the array of packets to ensure all packets were received, and account for the packets being out of order in the

array.

The goal is to extract the payloads from an unordered array of generic IPv4 packets to rebuild the correctly transmitted message.

We will assume that:

Each packet has a set maximum size of packetentrysize bytes, instead of 60 bytes as in homework 2. Therefore, the MAXIMUM payload size of a packet is

bytes. the actual paload size of a packet must be computed using the and fields.

Eachpackethasavariablelengthheaderintherangeof[5,15](asindicatedbythe Header length fieldinthepacket).

Implement the following new function: a.

We realize that real IPv4 packets do not have headers of this length, but there is no reason why our checksum verifier cant be generalized to do so.

packetentrysize (4*header length field)

Total Length

(int,int) extractUnorderedData(Packet[] parray, int n, byte[] msg,

Header Length

int packetentrysize)

CSE 220 Fall 2017 Homework #3 Page 3

parray : starting address of the 1D array of unordered IPv4 packet(s). n : number of packets in parray .
msg : starting address of the 1D array of bytes for the msg . packetentrysize : the number of bytes for each parray entry.

returns:(0,M+1)uponsuccess,(-1,k)uponfailure.Allerrorcasesaredescribedbelow.

parray represents the starting address of the Packet array in memory. Each element of thearrayistreatedastypePacket.Therefore,eachelementofthearrayis packetentrysize bytes of memory.

Thisfunctionvalidates parray forthefollowingproperties:

• eachpacketin parray wastransmittedcorrectlyusing verifyIPv4Checksum
• if n>1 , parray contains a SINGLE beginning packet and parray contains a SIN- GLE last fragment packet
• if n==1 , the single packet in parray is not fragmented. A packet is not fragmented if:
  • Flags equals 010, or
  • Flags equals 000 with a Fragment Offset of 0.

    If parray is valid, then the payload of each packet is extracted and placed into the mem- ory space referenced by the argument (using the proper ). The functionusesthe , Flags and fieldofeachpacket header to determine the size and position to copy the packet payload into msg .

    The field specifies the full length of the packet. Note, this is different from which is the max possible value. To determine the length of the packet payload, subtract the size of the header (4* ) from

    this value.

Use Flags to determine how to store each packet payload into msg .

The function is not responsible for checking that the combined payloads build a contiguous data block into msg .

msg

Fragment Offset

Total Length

Total Length

Fragment Offset

packetentrysize

Total Length

Header Length

If Flags equals 100 and packet. Store the payload into

equals 0, the packet is the beginning

Fragment Offset

msg[0]

.

CSE 220 Fall 2017

Homework #3 Page 4

• If Flags equals 100 and
  termediate packet. Store the payload into
• If Flags equals000and
  fragment packet. Store the payload into

  field. Store the payload into msg[0] .

does not equal 0, the packet is an in- .

doesnotequal0,thepacketisthelast .

equals0,thepacketistheONLYpacket. If equals010,thismeansthemessageisnotfragmented.Ignorethe

If Flags equals000and
Store the payload into .

Flags

Fragment Offset

msg[0]

It is guaranteed there is enough space allocated in memory to store the full data- gramattheaddressspecifiedbythe msg argument.

You may assume n packets are provided in the array and all fragment offsets are unique.

Uponsuccessfulextractionofallpayloadsintothe msg array,thefunctionreturns(0, M+1), where M is the index of the last (highest index) byte stored in msg .

The function returns (-1, k ), where k is the array index of the first error, if: Total Length for a packet > packetentrysize for packet k
checksumverificationfailsforpacket k

The function returns (-1, -1) if: n<1

n == 1 andthepacketin parray has Flags equals100
n == 1 andthepacketin parray has Flags equals000and Fragment Offset

does not equal 0
n ! = 1 and any packet in parray has Flags equals 010
n > 1 andthe doesnothaveexactlyonebeginningpacket(Flags equals

parray

100 and
n > 1 and the does not have exactly one last fragment packet ( Flags

equals 000 and CSE 220 Fall 2017

does not equal 0)
Homework #3 Page 5

Fragment Offset

Fragment Offset

equals 0)

msg[Fragment Offset]

Fragment Offset

msg[Fragment Offset]

Fragment Offset

parray

Fragment Offset

You must check for all checksum errors FIRST! Only if there are no checksum er- rors, proceed to verify the flags.

This is not an exhaustive list of errors! If there exists a combination of , , and that is not logically valid return (-1, -1).

Fragment Offset

n

Flags

Examples:
See hw3_examples.asm forpacketarraysandcommentsabouteachexample.

Part 3: Create new printUnorderedDatagram Function Implement the following new function:

b. int printUnorderedDatagram(Packet[] parray, int n, byte[] msg, String[] sarray, int packetentrysize)

This function is identical to from homework 2, except that you replace thecallto extractData with .

In addition, this function takes the packetentrysize as the fifth argument. As dis- cussed in lecture and recitation, this argument is stored on the stack by the caller function and accessed by printUnorderedDatagram from the stack. It is the responsibility of the caller function to return the space to the stack after the function call.

Part 4: Recursive Function
CSE 220 Fall 2017 Homework #3 Page 6

printDatagram

extractUnorderdData

Although most recursive algorithms tend to look simple in a high-level language, they can be tricky to write at an assembly level. In this part you will be given the code for a recursive version of an Edit Distance algorithm in Java and will implement it in MIPS.

The Edit Distance algorithm calculates the minimal number of steps needed to be taken in order to transform one String into another String over a given length for each.

c. int editDistance(String str1, String str2, int m, int n)
This function calculates the edit distance between two Strings str1 and str2 , given

lengths m and n .

• str1 : starting address of the first string.
• str2 : starting address of the second string.
• m:lengthof str1.
• n:lengthof str2.
• returns: the number of edits to transform str1 into str2 . -1 if m or n is less than 0.

  Below is the algorithm that you MUST follow to implement this function:
  int editDistance(String str1 , String str2 , int m ,int n) {

  if(m < 0 || n < 0) return -1;System.out.print("m:" + m + ",n:" + n + "
  ");

  // If first string is empty, just insert nif (m == 0) return n;

  // If second string is empty, just remove mif (n == 0) return m;

  // If last chars of the two strings are the same ignore// the last character of eachif (str1.charAt(m-1) == str2.charAt(n-1))

  return editDistance(str1, str2, m-1, n-1);

  // If last characters are not same, consider all three// operations on last character of first string. Recursively// compute minimum cost for all three operations and take the

CSE 220 Fall 2017 Homework #3 Page 7

// minimum of the three values.int insert = editDistance(str1, str2, m, n-1);int remove = editDistance(str1, str2, m-1, n);int replace = editDistance(str1, str2, m-1, n-1);

//You may implement the min of 3 values in any way you want

return 1 + Math.min(insert, Math.min(remove, replace));}

We will ensure all test can be completed within the stated instruction limit. Examples:
See hw3_example_outputs.txt foroutputsforeachexample.

We know dynamic programming is a more efficient solution. The goal of this exer- cise is to test your register conventions and stack management.

We will grade your recursive output to ensure that you implemented the function recursively.

Hand-in instructions
Do not add any miscellaneous printouts, as this will probably make the grading script give you a

zero. Please print out the text EXACTLY as it is displayed in the provided examples.

See Sparky Submission Instructions on piazza for hand-in instructions. There is no tolerance for homework submission via email. They must be submitted through Sparky. Please do not wait until the last minute to submit your homework. If you are having trouble submitting, stop by office hours prior to the deadline for assistance.

CSE 220 Fall 2017 Homework #3 Page 8