Quick sort implementation in MIPS assembly

MIPS assignment

The program needs to run using QTSpim on the linux system.

quicksort.c

// Demonstration program for Quick Sort of an array of 100 integers

// using recursion

//

#include <stdlib.h>

#include <stdio.h>

#include <stdint.h>

#include “quicksort.h”

// Global values for random number generator.

// Initialize the random number generator with fixed values

// for demonstration purposes.

uint32_t m_w = 50000;

uint32_t m_z = 60000;

int main()

{

uint32_t b, a[100];

for(int i=0; i<100; i++)

{

b = random_in_range(1,100000);

a[i]=b;

}

quickSort(a,0,99);

printf(“\n Sorted array is:\n”);

for (int i=0;i<100;i++)

printf(“a[%d]=%d \n”,i,a[i]);

return 0;

}

//recursive quicksort

void quickSort( uint32_t a[], int l, int r)

{

int j;

if( l < r )

{

// divide and conquer

j = partition( a, l, r);

quickSort( a, l, j-1);

quickSort( a, j+1, r);

}

}

int partition(uint32_t a[], int l, int r) {

int pivot, i, j, t;

pivot = a[l];

i = l; j = r+1;

while( 1)

{

do ++i; while( a[i] <= pivot && i <= r );

do –j; while( a[j] > pivot );

if( i >= j ) break;

t = a[i]; a[i] = a[j]; a[j] = t;

}

t = a[l]; a[l] = a[j]; a[j] = t;

return j;

}

// Generate random number in range [low, high]

// (i.e. including low and high)

uint32_t random_in_range(uint32_t low, uint32_t high)

{

uint32_t range = high-low+1;

uint32_t rand_num = get_random();

return (rand_num % range) + low;

}

// Generate random 32-bit unsigned number

// based on multiply-with-carry method shown

// at http://en.wikipedia.org/wiki/Random_number_generation

uint32_t get_random()

{

uint32_t result;

m_z = 36969 * (m_z & 65535) + (m_z >> 16);

m_w = 18000 * (m_w & 65535) + (m_w >> 16);

result = (m_z << 16) + m_w;  /* 32-bit result */

return result;

}

quicksort.h

#ifndef QUICKSORT_H

#define QUICKSORT_H

#include <stdint.h>

void quickSort(uint32_t a[],int l, int r);

int partition(uint32_t a[],int l, int r);

uint32_t random_in_range(uint32_t, uint32_t);

uint32_t get_random(void);

#endif // QUICKSORT_H

Solutionquicksort.asm

.data

m_w:    .word 50000

m_z:    .word 60000

a:      .space 400      #uint32_t a[100]

msg1:   .asciiz “\n Sorted array is:\n”

msg2p1: .asciiz “a[”

msg2p2: .asciiz “]=”

msg2p3: .asciiz ” \n”

.text

#————————————————–

#  int main()

#————————————————–

main:

li \$s0,0            # \$s0 will be used as i

la \$s1,a            # \$s1 will have the address of a[i]

for1:                   #   for(int i=0; i<100; i++)

bge \$s0,100,endfor1 #    {

li \$a0,1

li \$a1,100000

jal random_in_range #  b = random_in_range(1,100000);

sw \$v0,(\$s1)        # a[i]=b;

b for1              #   }

endfor1:

la \$a0,a            # set first argument to a

move \$a1,\$0         # set second argument to 0

li \$a2,99           # set third argument to 99

jal quicksort       # quickSort(a,0,99);

li \$v0,4            # use syscall number 4, print string

syscall             # printf(“\n Sorted array is:\n”);

li \$s0,0            # \$s0 will be used as i

la \$s1,a            # \$s1 will have the address of a[i]

for2:                   #for (int i=0;i<100;i++)

bge \$s0,100,endfor2 # {

#     printf(“a[%d]=%d \n”,i,a[i]);

li \$v0,4            # use syscall number 4, print string

syscall

move \$a0,\$s0        # load current value of i in a0

li \$v0,1            # use syscall number 1, print number

syscall

li \$v0,4            # use syscall number 4, print string

syscall

lw \$a0,(\$s1)        # load current value of i in a0

li \$v0,1            # use syscall number 1, print number

syscall

li \$v0,4            # use syscall number 4, print string

syscall

b for2              # }

endfor2:

li \$v0,10           # terminate program using syscall 10

syscall

#————————————————–

#void quickSort( uint32_t a[], int l, int r)

# On entry: a0=a[]

#           a1=l

#           a2=r

#————————————————–

quicksort:

addi \$sp,\$sp,-20    # allocate space for saving registers in the stack

sw \$ra,0(\$sp)       # save return address register in the stack

sw \$s0,4(\$sp)       # save \$s0 register in the stack

sw \$s1,8(\$sp)       # save \$s1 register in the stack

sw \$s2,12(\$sp)      # save \$s2 register in the stack

sw \$s3,16(\$sp)      # save \$s3 register in the stack

bge \$a1,\$a2,endif1          #   if( l < r )

# {

# // divide and conquer

move \$s0,\$a0                # save value of \$a0

move \$s1,\$a1                # save value of \$a1

move \$s2,\$a2                # save value of \$a2

jal partition               # j = partition( a, l, r);

move \$s3,\$v0                # save return value in \$s3 (j)

move \$a0,\$s0                # load saved value of \$a0

move \$a1,\$s1                # load saved value of \$a1

jal  quicksort              # quickSort( a, l, j-1);

move \$a0,\$s0                # load saved value of \$a0

move \$a2,\$s2                # load saved value of \$a2

jal  quicksort              # quickSort( a, j+1, r);

endif1:                         # }

lw \$ra,0(\$sp)       # restore contents of \$ra from the stack

lw \$s0,4(\$sp)       # restore \$s0 register from the stack

lw \$s1,8(\$sp)       # restore \$s1 register from the stack

lw \$s2,12(\$sp)      # restore \$s2 register from the stack

lw \$s3,16(\$sp)      # restore \$s3 register from the stack

addi \$sp,\$sp,20     # restore stack pointer

jr \$ra

#————————————————–

# int partition(uint32_t a[], int l, int r) {

# On entry: a0=a[]

#           a1=l

#           a2=r

#————————————————–

partition:

addi \$sp,\$sp,-16    # allocate space for saving registers in the stack

sw \$ra,0(\$sp)       # save return address register in the stack

sw \$s0,4(\$sp)       # save \$s0 register in the stack

sw \$s1,8(\$sp)       # save \$s1 register in the stack

sw \$s2,12(\$sp)      # save \$s2 register in the stack

sll \$t4,\$a1,2       # multiply l by 4 to get offset in array

lw  \$s0,(\$t4)       # pivot = a[l]; \$s0 will be pivot

move \$s1,\$a1        # i = l;  \$s1 will be i

addi \$s2,\$a2,1      # j = r+1;  \$s2 will be j

while1:                 # while( 1)

# {

do1:                    # do

sll \$t1,\$s1,2       # multiply i by 4 to get offset in array

lw  \$t0,(\$t1)       # \$t0 = a[i]

bgt \$t0,\$s0,do2     # while( a[i] <= pivot && i <= r );

bgt \$s1,\$a2,do2

b   do1

do2:                    # do

sll \$t2,\$s2,2       # multiply j by 4 to get offset in array

lw  \$t0,(\$t2)       # \$t0 = a[j]

bgt \$t0,\$s0,do2     # while( a[j] > pivot );

bge \$s1,\$s2,brk1    # if( i >= j ) break;

lw \$t0,(\$t1)        # t = a[i];

lw \$t3,(\$t2)        # a[i] = a[j];

sw \$t3,(\$t1)

sw \$t0,(\$t2)        # a[j] = t;

b while1            # }

brk1:

lw \$t0,(\$t4)        # t = a[l];

lw \$t3,(\$t2)        # a[l] = a[j];

sw \$t3,(\$t4)

sw \$t0,(\$t2)        # a[j] = t;

move \$v0,\$s2        # return j;

lw \$ra,0(\$sp)       # restore contents of \$ra from the stack

lw \$s0,4(\$sp)       # restore \$s0 register from the stack

lw \$s1,8(\$sp)       # restore \$s1 register from the stack

lw \$s2,12(\$sp)      # restore \$s2 register from the stack

addi \$sp,\$sp,16     # restore stack pointer

jr \$ra

#————————————————–

# uint32_t random_in_range(uint32_t low, uint32_t high)

# On entry: a0=low

#           a1=high

# On return: v0 = random integer in the given range

#————————————————–

random_in_range:

addi \$sp,\$sp,-8     # allocate space for saving registers in the stack

sw \$ra,0(\$sp)       # save return address register in the stack

sw \$s0,4(\$sp)       # save \$s0 register in the stack

sub \$s0,\$a1,\$a0     # uint32_t range = high-low+1;

addi \$s0,\$s0,1      # s0 will hold range

jal get_random      # uint32_t rand_num = get_random();

divu \$v0,\$s0         # return (rand_num % range) + low;

mfhi \$v0            # get modulus rand_num % range

lw \$ra,0(\$sp)       # restore contents of \$ra from the stack

lw \$s0,4(\$sp)       # restore \$s0 register from the stack

addi \$sp,\$sp,8     # restore stack pointer

jr \$ra

#————————————————–

# uint32_t get_random()

# On return: \$v0 = random number

#————————————————–

get_random:

# calculate m_z = 36969 * (m_z & 65535) + (m_z >> 16);

li \$t0,36969        # load immediate 36969 in t0

lw \$t2,(\$t1)        # load m_z value in \$t2

andi \$t3,\$t2,65535  # calculate m_z & 65535

multu \$t0,\$t3       # calculate 36969 * (m_z & 65535)

mflo \$t0            # move multiplication result to t0

srl \$t3,\$t2,16      # calculate m_z >> 16

addu \$t0,\$t0,\$t3    # calculate complete expr.: 36969 * (m_z & 65535) + (m_z >> 16);

sw \$t0,(\$t1)        # save result in m_z

# calculate m_w = 18000 * (m_w & 65535) + (m_w >> 16);

li \$t0,18000        # load immediate 18000 in t0

lw \$t2,(\$t1)        # load m_w value in \$t2

andi \$t3,\$t2,65535  # calculate m_w & 65535

multu \$t0,\$t3       # calculate 18000 * (m_w & 65535)

mflo \$t0            # move multiplication resut to t0

srl \$t3,\$t2,16      # calculate m_w >> 16

addu \$t0,\$t0,\$t3    # calculate complete expression: 18000 * (m_w & 65535) + (m_w >> 16);

sw \$t0,(\$t1)        # save result in m_w

la \$t0,m_z          # get address of m_z in t0

lw \$t0,(\$t0)        # t0 = m_z

la \$t1,m_w          # get address of m_w in t1

lw \$t1,(\$t1)        # t1 = m_w

# calculate result = (m_z << 16) + m_w;  /* 32-bit result */

sll \$t0,\$t0,16      # calculate m_z << 16

addu \$t0,\$t0,\$t1    # calculate complete result (m_z << 16) + m_w

move \$v0,\$t0        # return result;

jr \$ra