1

Suppose we have a string representing an integer in a given base, and that very base. The parameters are the address (in $a0) starting from which the string is stored, and the base in $a1.

I should convert the corresponding number into base 10, and save it in $v0. In this case 0 should be loaded into $v1.
If instead the string does not correctly represent an integer in the given base, then in the end $v0 should contain -1 and $v1 should contain 1.

Also, the function that actually performs the conversion should be recursive.

I have written beforehand a Python program in such a way (you'll notice the various s0, s1 etc.) that I could transfer the thinking to MIPS, but it got really confusing when I realised I probably should perform contextually the counting of the characters of the string, the investigation over the string being "in base" or not, and the actual conversion with the gradual summing of quantities to some designated variable - and not separately as in the below program.

How should I go about this and write the function(s)?

Here's the Python code:

digitsDict = dict();

lowerCase = "abcdefghijklmnopqrstuvwxyz"
upperCase = lowerCase.upper();

for i in range(26):
    digitsDict.update({lowerCase[i]:i+10})
    digitsDict.update({upperCase[i]:i+10})

def isInBase(string, base):
    s1 = False; 
    for char in string:
        if (str(char).isdigit()):
            if (int(char) >= base):
                return s1
        else:
            if (char not in digitsDict.keys() or digitsDict[char] >= base):
                return s1
    s1 = True
    return s1

def convert(string, base, k=0):
    s2 = 0
    char = string[k]
    l = len(string) - 1
    if str(char).isdigit(): s2 += int(char)*(base**(l-k))
    else:   s2 += digitsDict[char]*(base**(l-k))
    
    if k == l: return s2;
    return s2 + convert(string, base, k+1)
    

def strToInt(string, base):
    return (convert(string, base, 0), 0)
    
def main(a0String, a1Integer):
    if isInBase(a0String, a1Integer):
        v0, v1 = strToInt(a0String, a1Integer)
    else: v0 = -1; v1 = 1;
    
    print(v0)
    if (v0 == -1): return 22 #MIPS error code for invalid argument
    return 0 #OK
Learner
  • 149
  • 6

1 Answers1

3

First, you have pseudo code, so very good!

Next, as a general rule, make sure your pseudo code actually works (so test it), as debugging design issues in assembly is very difficult, and small changes to the design (in pseudo code) can require large changes in the assembly (e.g. rewriting a lot of code).

You're doing some things in Python that are rather involved in assembly language, so you ought to write your pseudo code in C first, since that will make you address those differences. 

  • in — represents a loop in C or assembly
  • += and + on strings — represents either some simple operations on global buffer, or, some complicated memory management (hint: go for the former)
  • .isDigit() is conditional conjunction or disjunction depending on how you code it
  • .update() will need some alternative translation
  • ** also represents a loop in C or assembly

The next big complication is the calling of functions.  Function calling in MIPS assembly language is probably the most complex topic, due to the requirements register usage and stack handling.

Recursion is a bit of a red herring for assembly language: it appears hard but it is actually no harder and even no different in assembly language than functions calling other functions without involving recursion (this is true assuming the assembly instruction set has a runtime stack for function calling, MIPS does (but if it didn't you'd have to simulate a call stack)).

You'll need to study up on this, it is somewhat involved.  Look for other example, fibonacci, for example.

When translating to MIPS one function that calls another function, we need an analysis of variables and values that are "live across a function call".  These variables need special consideration, since some registers are wiped out by calling another function.  You'll see this in fibonacci, for example.

Part of recursive fib, is fib(n-1)+fib(n-2).  The return value from the first call to fib must be given special handling since it ultimately needed for the addition (+), so it is live across the 2nd call to fib, and without special handling, will be lost by making that 2nd call.  Also, n is live across the first call yet needed again to make the second call, and without some special handling would similarly be wiped out by that first call.

This is a consequence of functions calling functions in MIPS whose instruction set does not automatically stack things and requires the assembly language programmer or compiler to do so manually.  Some or all of this is also needed on other architectures.  This is not a consequence of recursion, so a(n)+b(n) would involve the same requirements for analysis and special handling of variables and values.

When you have a good algorithm (e.g. in C) and it works, your ready for assembly.  Translate your data first: global variables.  Next translate functions, similarly: translate your local variables into MIPS, then translate each structured statement, (e.g. if, for) following its assembly language pattern.  Nested structured statements also nest in assembly language, and it doesn't matter if you translate the inner statements first or outer statements first, as long as you exactly observe the nesting.

In order to translate structured statements into assembly I first use intermediate forms in C, for example:

for ( int i = 0; i < n; i++ ) {
    ..body of for..
}

Note that in the above the "body of the for" could easily contain control structures, like another for or an if.  These then, are nested structure statements — just translate them one at a time, each structured statement following its complete pattern, and make sure the nesting in C is equally observed in assembly.

Translate for to while :

...
int i = 0;
while ( i <n ) {
    ..body of for..
    i++;
}
...

Next, apply "if-goto-label" intermediate form :

    ...
    int i = 0;
loop1:
    if ( i >= n ) goto endLoop1;
    ..body of for..
    i++;
    goto loop1;
endLoop1:
    ...

As you apply patterns, you'll need to create label names; new label names for each application of the pattern.

Then this translates into assembly fairly easily.  If the "body of for" also has control structures make sure their entire translation is embedded and located at the "body of for" section in the above pattern.

Notice how the i < n in assembly sometimes translates into i >= n — here because control flow in if-goto-label form make is say: exit the loop on the logically opposite condition of the while statement in C.

And finally, translate expressions within statements in your C code into assembly.

Erik Eidt
  • 23,049
  • 2
  • 29
  • 53