Monash University > School of Computer Science and Software Engineering > CSE1303 > Part B > Pracs > Prac B6

CSE1303 Computer Science
Semester 2, 2003
Part B
Prac B6

This prac covers material from lectures B01 to B15.

Background

A permutation of a string contains all the same characters as the string, but in a different order. For example, the strings adceb and bdeac are both permutations of abcde.

If a string contains n characters, there are n! (n factorial) different permutations of the string. (Some may be duplicates if the same character appears more than once in the string.)

In this prac you will work with a program which prints all permutations of a string. You don't need to understand the algorithm to be able to do this prac, but there's nothing in it that you haven't seen before.

Assessment

For this prac your answers should address the following criteria. Your demonstrator will consider these items when giving your answers a mark.

Commented C and MIPS code.
Stack diagrams.
Faithfulness of translation.
Correct output for any given input.

Preparation (3 marks)

The marks for Preparation will be awarded only if the preparation is completed before the start of the class.
Even if you do not get the marks for preparation, you will need to complete it before going on with the regular questions, because they will refer to its answers.

Review the question "Pointers and Arrays" in tutorial B5, especially the C and MIPS implementations of the strlen function.
Write C code for Question 1.
Write MIPS code for Question 2.
Type in and run the C code from Question 3. Draw the stack diagrams described in that question.
Make a start on the MIPS code for Questions 1 and 3.

Question 1 (2 marks)

Write your own C implementation of the standard library function int strlen(const char *s). (That is, write a function which does exactly the same thing as the C standard library strlen function. Your function can't simply pass the job on to the C standard library strlen function; it must do everything by itself.)

Write a program to test your function.

Translate your program, including your strlen function, into MIPS assembly language. Try to make your translation as faithful as possible.

Question 2 (2 marks)

Write MIPS code for a function void swap(char *s, char *t) which swaps the character pointed to by s with the character pointed to by t. Although this function must obey the standard MIPS function calling convention, you are allowed to take whatever shortcuts you like in the body of the function, provided the function has the correct behaviour.

Test your function with this test harness:

        .data
str:    .asciiz "Harpy progpamming!\n"

        .text
main:   move $fp, $sp   # No local vars.

        subu $sp, $sp, 8
        la $t0, str+10   # &str[10];
        sw $t0, 0($sp)
        la $t0, str+2    # &str[2];
        sw $t0, 4($sp)
        jal swap
        addu $sp, $sp, 8

        li $v0, 4    # print string
        la $a0, str
        syscall

        li $v0, 10   # exit
        syscall

Question 3 (3 marks)

Type in and run this C program:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char s[10];

/* swap(s,t): swap characters.
 * Swaps characters *s and *t. */
void swap(char *s, char *t)
{
  int c;

  /* Rotate through temp variable c. */
  c = (int) *s; *s = *t; *t = (char) c;
}

/* perm(s,n,l): print permutations.
 * Prints string s for all permutations of characters
 * in positions n through l-1.
 */
void perm(char *s, int n, int l)
{
    int i;

    if (n == l)
    {
        /* No characters to permute . . print string. */
        printf("%s", s);
    }
    else
    {
        /* Work through all characters of string. */
        for (i = n; i < l; i++)
        {
            /* Swap this character with the first one. */
            swap(s + i, s + n);
            /* Permute remainder of string. */
            perm(s, n+1, l);
            /* Swap back again. */
            swap(s + i, s + n);
        }
    }
}

int main()
{
    int length;

    /* Read string from keyboard. */
    printf("Type a string: ");
    fgets(s, 10, stdin);

    /* How long is a string? */
    length = strlen(s);

    /* Permute characters 0 to length - 2
     * (leave last character in place because
     * it is a newline character). */
    perm(s, 0, length - 1);

    exit(0);
}

Draw a stack diagram corresponding to the first entry to the perm function. Assume the string typed by the user is "abcde\n" (the newline character is not stripped by the fgets function).

Draw a stack diagram corresponding to the first entry to the swap function. Make your diagram consistent with your implementation of swap from Question 2.

Draw a stack diagram corresponding to the second time the perm function is entered (i.e., the first occurrence of recursion in the program).

Translate the above program into MIPS assembly language. You should utilize your strlen function from Question 1 and your swap function from Question 2. With the exception of the swap function, try to make your translation as faithful to the original code as possible.

Bonus question (2 bonus marks)

Throughout CSE1303, input and output have been sort of fudged through the use of system calls. When translating C programs into MIPS, the printf function has been turned into so many syscall instructions, rather than a proper function call.

In MIPS assembly language, write a simple version of the printf function that takes an unknown number of (at least 1) parameters, and understands the following format specifiers, specified in the first (string) parameter:

Format Type of parameter Meaning
%d int integer
%s char * string
%c int character
%% none literal % character

Format	Type of parameter	Meaning
`%d`	`int`	integer
`%s`	`char *`	string
`%c`	`int`	character
`%%`	none	literal % character

Your function needs to examine the format string, scanning it and printing it character by character. When a % character is encountered, your function should examine the next character in the string to determine the format, then extract the next function parameter and print it out using appropriate system calls.

(To print a character, the system call code is 11, and the ASCII value of the character to print must be placed in the least significant eight bits of $a0. This system call appeared in SPIM 6.4; you may need to download a recent version of the simulator.)