pad.mattdiesel.co.uk

Snippet - MIPS Bubblesort Example

MIPS Bubblesort Example (Text only)

MIPS Example Paper Q5 - Bubblesort
Created 2015-10-16 17:23:30.860860 by Matt.
Modified 2015-10-16 17:23:50.004560 by Matt.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
	j	main


# void sort(int* v, int n)
# {
#	int i,j;
#	for ( i=1; i<n; i++ ) {
#		j = i-1;
#		while ( (j >= 0) && (v[j] > v[j+1]) ) {
#			swap(v[j],v[j+1]);
#			j = j-1;
#		}
#	}
# }

	# $a0 = v
	# $a1 = n
sort:
	addi	$sp,$sp,-16
	sw	$s0,-12($sp)
	sw	$s1,-8($sp)
	sw	$s2,-4($sp)
	sw	$s3,0($sp)
	
	add	$s2,$zero,$a0
	add	$s3,$zero,$a1
	
	xor	$s0,$s0,$s0
sort_for:
	addi	$s0,$s0,1
	slt	$t1,$s0,$s3
	beq	$t1,$zero,sort_forend
	addi	$s1,$s0,-1
	sll	$s1,$s1,2
sort_while:
	slt	$t1,$s1,$zero
	bne	$t1,$zero,sort_for
	
	add	$a0,$s2,$s1
	addi	$a1,$a0,4
	lw	$t4,0($a0)
	lw	$t5,0($a1)
	
	addi	$t5,$t5,1
	slt	$t1,$t4,$t5
	bne	$t1,$zero,sort_for
	
	addi	$sp,$sp,-4
	sw	$ra,0($sp)
	jal	swap
	lw	$ra,0($sp)
	addi	$sp,$sp,4
	
	addi	$s1,$s1,-4
	j	sort_while
sort_forend:
	jr	$ra
	
	
	
swap:
	# a0 = pointer to A
	# a1 = pointer to B
	lw	$t1,0($a0)
	lw	$t2,0($a1)
	sw	$t1,0($a1)
	sw	$t2,0($a0)
	jr	$ra




	# Simple multiply with carry random number generator.
rand:
	# a0 = initializer
	# a1 = initializer
	
	# m_z = 36969 * (m_z & 65535) + (m_z >> 16);
	ori	$t3,$zero,36969
	andi	$t2,$a0,0xFFFF
	srl	$t1,$a0,16
	multu	$t2,$t3
	mflo	$t2
	addu	$a0,$t2,$t1
	
	# m_w = 18000 * (m_w & 65535) + (m_w >> 16);
	ori	$t3,$zero,18000
	andi	$t2,$a1,0xFFFF
	srl	$t1,$a1,16
	multu	$t2,$t3
	mflo	$t2
	addu	$a1,$t2,$t1
	
	sll	$v0,$a0,16
	addu	$v0,$v0,$a1
	jr	$ra





main:
	# Fill values
	lui	$s0,0x1001
	addi	$s0,$s0,0x0000
	
	addi	$s1,$0,30
	addi	$s2,$s0,0
	
	addi	$a0,$zero,0x1234
	addi	$a1,$zero,0x5678
l1:
	jal	rand
	sw	$v0,0($s2)
	addi	$s2,$s2,4
	addi	$s1,$s1,-1
	bne	$s1,$zero,l1
	
	# Sort
	
	or	$a0,$zero,$s0
	ori	$a1,$zero,30
	jal	sort
	
	break