Perform a permutation on an array in MIPS assembly

Question

I’m currently studying computer science at university and I’d been tasked with writing a MIPS assembly program that performs a permutation on an array. I’m asking here because my code actually worked and I got no feedback beyond that (on the style, comments & form).

Unfortunately the result is likely rather unperformant because I was required to use two predefined functions. Their signatures in C are:

// Swap elements of an array
void swap(char **objects, int k, int l);

// Determine if an element of a permutation array is the start of a cycle
int cycle_head(int *perm, int idx);

Here is C code that emulates the cycle_head function:

int cycle_head(int *perm, int idx) {
    i = perm[idx]
    j = i
    while (1) {
        j = perm[j]
        if (j == i) return 1
        if (j < i) return 0
    }
}

I first wrote equivalent C code for my program:

void permutate(char **objects, int *perm, int perm_len) {
    for (int i = 0; i < perm_len; i++) {
        if (cycle_head(perm, i)) {
            for (
                int j = perm[i], k = perm[j];
                j != i;
                j = k, k = perm[k]
            ) {
                swap(objects, j, k);
            }
        }
    }
}

I then translated this into MIPS assembly:

# void permutate(char **objects, int *perm, int perm_len)
permutate:
    # objects: $a0
    # perm: $a1
    # perm_len: $a2
    # allocate stack
    addi $sp, $sp, -28
    # save $ra, $si, $ai
    sw $ra, 0($sp)
    sw $s0, 4($sp)
    sw $s1, 8($sp)
    sw $s2, 12($sp)
    sw $a0, 16($sp)
    sw $a1, 20($sp)
    sw $a2, 24($sp)
    # for (int i = 0; i < perm_len; i++)
    # i: $s0
    # int i = 0
    li $s0, 0
permutate_for_1_begin:
    # i < perm_len
    bge $s0, $a2, permutate_for_1_end
        # if (cycle_head(perm, i))
        # call cycle_head(perm, i)
        move $a0, $a1
        move $a1, $s0
        jal cycle_head
        # restore $ai
        lw $a0, 16($sp)
        lw $a1, 20($sp)
        lw $a2, 24($sp)
        beq $v0, 0, permutate_if_1_end
            # for (int j = perm[i], k = perm[j];
            # j != i; j = k; k = perm[k])
            # j: $s1
            # int j = perm[i]
            # j = *(perm + (i << 2))
            sll $s1, $s0, 2
            add $s1, $a1, $s1
            lw $s1, 0($s1)
            # k: $s2
            # int k = perm[j]
            # k = *(perm + (j << 2))
            sll $s2, $s1, 2
            add $s2, $a1, $s2
            lw $s2, 0($s2)
        permutate_for_2_begin:
            # j != i
            beq $s1, $s0, permutate_for_2_end
                # call swap(objects, j, k)
                # X move $a0, $a0
                move $a1, $s1
                move $a2, $s2
                jal swap
                # restore $ai
                lw $a0, 16($sp)
                lw $a1, 20($sp)
                lw $a2, 24($sp)
                # j = k
                move $s1, $s2
                # k = perm[k]
                # k = *(perm + (k << 2))
                sll $s2, $s2, 2
                add $s2, $a1, $s2
                lw $s2, 0($s2)
                j permutate_for_2_begin
        permutate_for_2_end:
    permutate_if_1_end:
        # i++
        addi $s0, $s0, 1
        j permutate_for_1_begin
permutate_for_1_end:
    # restore $ra, $si
    lw $ra, 0($sp)
    lw $s0, 4($sp)
    lw $s1, 8($sp)
    lw $s2, 12($sp)
    # free stack
    addi $sp, $sp, 28
    jr $ra

I based my decisions about which registers to use on the register conventions as was communicated in my university course and this document which I found online, which is the reason I don’t use $fp.

I tried to format my code by unindenting all labels except for function labels since they can be considered top-level and cannot be unindented, and indenting all branches until the rejoin point.

I was also told to assume that integers and pointers and registers are all the same width. I am not sure if this is accurate to real hardware.

I tested my code using the MARS MIPS IDE, and it was also tested to be correct by the university.

The code I have listed here differs slightly from the code I submitted, but not functionally, namely in a space character and an asterisk in comments.

Answer 1

General Observations

I don't know MIPS processors or their assembly code so I will make general comments about assembly and the C portion.

In general when you are indexing through an array it is more performant to use indirect addressing (pointers); it requires fewer assembly statements. The optimizing switches in the C compiler do this for you, but when programming in assembly you need to do it yourself.

Some processors have an auto decrement and test assembly instruction. If the processor has this instruction, the following (but less readable) for loop is faster:

    for (size_t i = perm_len + 1; --i; )
    {
        // perform actions on perm[i] or some pointer version of perm[i]
    }

Prefer Unsigned Values for Indexing Arrays

Array indexes should never go negative. Indexing an array with a negative number causes Undefined Behavior because you are indexing other memory rather than the array.

In some cases unsigned integers may be faster than signed integers.

This code is not syntactically correct:

int cycle_head(int *perm, int idx) {
    i = perm[idx]
    j = i
    while (1) {
        j = perm[j]
        if (j == i) return 1
        if (j < i) return 0
    }
}

The variables i and j have not been declared.