CST 250 Lab 6 -- Calculating Isqrt

Lab Description

In this lab, we will calculate isqrt -- the integer square root of an unsigned 32 bit number. It will make use of the function you developed to convert a binary number to an ASCII decimal number -- bin_to_asciidec as well as the is_a_digit function. In this lab, as in the last lab, you will be required to set up a C-style stack frame in each function that needs one including main.  True C-style stack frames may have sections for saving registers (ra, fp, s and t registers (as needed)), local variable storage, and parameter space. Remember that each stack section will not be needed in every case.  In particular, note that since you are writing in assembly rather than emulating a C compiler, you can (and should) choose to keep most "local variables" in registers rather than setting them up on the stack (unless we run out of registers).  It is likely that we won't need local variables sections in this lab.  True C-style stack frames would reserve space for a0 -- a3 if the function called any others but you don't need to do this in this lab. You also don't need to align stack frame section addresses to multiples of 8 (as was done in the homework). 
   
Isqrt
The integer square root of a positive integer n is the positive integer m which is the greatest integer less than or equal to the square root of n.  Expressed as a formula it is:
Also, if  m = isqrt(n), then m² <= n and (m+1)² > n.
For example, isqrt(253) = 15 because 15² = 225 and 16² = 256

It can be computed iteratively for values of n > 2 as illustrated in the following pseudo code:

We start out with an intial guess, and then refine out guesses until the new guess and the previous guess are within 1 of each other. Mathematicians say that the guesses will converge to isqrt "quadratically" which basically means we don't have to do the refinement too many times to get our answer.
Notes:

• Because we will be carrying out our calculations purely using integers (no floating point), we may find that the square of the answer obtained using the above process is actually greater than n, in which case we will need to subtract 1 from our answer. (Using only integers in the calculation adds truncation errors that wouldn't otherwise be there.)
• Note that the above only works for n >= 2. With n=0 or n=1, then the first guess is 0 and there is a subsequent divide by 0 in the first pass of the loop. Your code will need to handle n=0 and n=1 as special cases. To determine how to do this, ask yourself what the square root of these values is in each case.

Program Considerations:

The unsigned value n we want to find the isqrt of will be "input" as an .asciiz string in the .data segment. The output, presented through the UART1 Output window (as we did in the last lab) will be as follows (assuming n is 253) :


Note that the debug iteration lines shown above will be produced from within the Isqrt function. But, the final line of output will come from the main routine.
 
Required functions:

Function bin_to_asciidec:
This function was developed in Lab 4 and used in Lab 5 and it will be used again here. It accepts as arguments a 32-bit unsigned decimal value (a0), and a pointer to an 11 byte space in the .data segment (a1) where the ascii string representation of the value in a0 will be placed.

Function asciidec_to_bin:
This will be a new function written for this lab. It converts a value represented by a string of ascii decimal digits to a binary value. The address of the string will be passed through a0 and the 32-bit binary value returned through v0. This function will be needed to convert the input value from an ascii string to an unsigned binary value. You are required to have this function call the is_a_digit function (developed in Lab 3 and used in Lab 5) to check that each of the ascii characters in the string are valid digits (0 through 9 characters) and get each digit's binary value. Then you can use Horner's method (presented in class) to convert the individual digits to the final binary value. There are several possible error cases:

• If the string is empty, or contains more than 10 digits, asciidec_to_bin should set the global value errno to 1 and return.  If, after returning to main from asciidec_to_bin, errno is 1, then isqrt should be skipped.
  
• If the string contains non-digit characters, asciidec_to_bin should ignore these characters and proceed with the conversion. However, if any non-digit characters are encountered in the string, it should set the global value errno to 2.  If errno is 2 after asciidec_to_bin returns to main isqrt should not be skipped. (If the string has skipped non-digit characters, but has more than 10 digits errno should be 1).
  
• I don't require you to handle the error condition that occurs if the string contains 10 digits but the value represented is greater than 4,294,967,295. You can choose to do this if time permits and you want a challenge. Note that it can be done by adding code to detect unsigned overflow in the Horner's method code. Note that there are two places in Horner's method (the add of the next digit and the multiply by 10) where overflow can occur.
  

Note that you should just count the digits as you go through the process of converting the string to binary rather than counting the string length first and then later doing the conversion. 
The main routine should also output appropriate error messages in the case errno is non-zero when asciidec_to_bin returns.  Note that you will have to setup errno in the .data segment, and follow the C convention on errno, which is that main should set errno to 0 before calling any routine that can change its value.

Function isqrt:
This is also a new function written for this lab. It computes the isqrt of the 32 bit unsigned integer value passed through a0 and returns the 32-bit unsigned result through v0.

• Make sure isqrt checks for the fact that sometimes doing integer math causes the algorithm to produce a result that is 1 too high. That is, just before returning, check to see if squaring the final guess produces a value greater than the passed value n. If so, subtract 1 from the final guess. (This will always work so no additional check is needed after subtracting 1.)
  
• Also have the isqrt function output the "debug iteration" lines shown above. (Note that it will be the main routine that emits the last output line shown above.)  Bracket the code (and any data segment elements) required to output these debug lines with .if debug and .endif conditional assembly directives so that this functionality is provided if debug is equated to 1 and not if debug is equated to 0. (This will be tested in lab.) Normally, functions like isqrt should not produce output. This approach gives us a way to observe the isqrt convergence during debugging but later easily remove it.
  
• Note that you will need to use a divide instruction to divide n by the guess, but use an srl instruction to do the divide by two.
  
• In order to produce the "debug iteration" lines will require isqrt to call output_string as a nested function, but only if we are debugging.  While debugging, there will be live values in isqrt that need to be preserved across the output_string call and there are two ways this could be done.  One would be to use s regs for the live values.  That would mean that isqrt would need to use a stack frame and preserve s regs and ra even when we weren't debugging.  Another way would be to use t regs (for what would be live values across the output_string calls) and save and restore them (and ra) in the conditionally compiled section of code that outputs the "debug iteration" lines.  This way, the code compiled when we aren't debugging will not need to save and restore s regs (and ra) making it more efficient.  (Note that in this case, stack space for the saved t regs and ra would also be conditionally allocated and released.)   You can choose either to use s regs or t regs for live values in isqrt this lab, but in either case, it must be done correctly.
  

Function output_string:
This function was defined and the code for it was provided in Lab 4 (also used in Lab 5). Also remember to include the code needed to initialize UART1 in your main routine.

Make sure that all functions (including main) that need stack frames have appropriate stack frames and that they follow the calling convention with respect to preserved and non-preserved registers. 

Procedure:
It is always a good idea to build and test functionality incrementally. so for example, you might write and test the asciidec_to_bin function before writing isqrt (or vice-versa).

Calling Convention
Remember to always follow the calling convention. This is the first lab in which you are writing functions that call other functions.  Only pass parameters to functions using a0 -- a3 and return values using v0 (other than the exception for errno).  Called functions can freely modify call-scratch registers (t0 -- t9, a0 -- a4, v0, v1) without having to save and restore them.  Routines should normally use the call-preserved registers s0 -- s7 for live values that need to be preserved across call(s). (Note that not all values in a routine will need to be preserved across a call, and call-scratch registers are fine for this purpose.)  A subroutine that uses any call-preserved (s) registers needs to save them on the stack at the beginning of the subroutine and restore them at the end. Write functions so that they could be used by someone else who understands the calling convention and what is passed and returned (i.e, the functions could be placed in a library).

Deliverables:

• Demonstrate the working program to the professor.
• Each function should have a comment block at the beginning indicating what is passed in to the function (and in what registers or where on the stack as appropriate) and what is returned. Or if nothing is returned indicate that as well.
  
• Add an accurate representation of the stack frame to each function that has one (including the main routine) in its comment block. Include the frame element offsets (as illustrated in the sample below).
  // Stack Frame
  //===Reg Save area===
  // ra      72
  // old fp  68
  // s0      64
  // s1      60
  //====Local Vars=====
  // total_count 56
  // var_count array 52-16
  //==Parameter space==
  // res a3  12
  .
  .
  .
• Turn in a copy of your commented source program (.S file). Make sure you save the file before submitting it. (Changes to the .S file made in the MPLab editor do not get automatically saved to the file unless you compile the program after you make changes, explicitly save the file, or close MPLab.)
  
• Also turn in a pdf printout of your .S program. When printing code from MPLab, I would ask you to please set the print options to change the default text font size to 12 points monospaced, turn on line wrapping, turn off  the border and set the set the background color to white. The default header and footer settings are fine.
  
• I will actually grade your .S file (after converting it to pdf myself), but I need you to have submitted a pdf file via canvas so that when I return the graded pdf, Canvas will have a place to put it.