18 Feb 2009
I had to manually compile an insertion algorithm from C to Motorola 68K assembly for class. The * symbol denotes a comment in assembly. I kept the C code as comments and wrote the corresponding assembly beneath.
* Compiled by Kanwei Li - 11/29/05
* isort - insertion sort
* This program uses the insertionsort algorithm to sort an array
* of structures containing integer, character and short fields.
* The integer field of each structure is the primary sort key.
* Array elements with equal integer keys are further sorted by
* the character field. The short field is not used for sorting.
* CS255 Assembly Language
* Emory Math/CS
xdef start, end
xdef for_start, for_exit, while_start, while_exit, while_pass
xdef i, j, v, a
*#define N 7
N: equ 7
********************
* TYPE DEFINITIONS *
********************
mys_i_off: equ 0
mys_c_off: equ 4
mys_s_off: equ 6
mys_size: equ 8
*struct mystruct {
* int i;
* char c;
* short s;
*};
********
* CODE *
********
*void main()
*
start:
move.l #1, i
for_start:
nop * nop after non-breakpoint labels as a temporary fix
* for (i=1; i<N; i++) = while(i<N) {
move.l i, d0
cmp.l #N, d0
bge for_exit
* v = a[i];
lea a, a0
muls.w #mys_size, d0
adda.l d0, a0
move.l a0, v
* We store v in registers to prevent clobbering
move.l (mys_i_off, a0), d3 * d3 = v.i
move.b (mys_c_off, a0), d4 * d4 = v.c
move.w (mys_s_off, a0), d5 * d5 = v.s
* j = i-1;
move.l i, d0
sub.l #1, d0
move.l d0, j
while_start:
nop
* while (a && (b || (c && d)))
* while ((j >= 0)
move.l j, d0
cmp.l #0, d0
blt while_exit
* && ((a[j].i > v.i)
lea a, a0
move.l j, d1 *d1 = j offset
muls.w #mys_size, d1
move.l (mys_i_off, a0, d1.l), d0
cmp.l d3, d0 * d3 = v.i
bgt while_pass
* || ((a[j].i == v.i)
bne while_exit
* && (a[j].c > v.c)))) {
move.b (mys_c_off, a0, d1.l), d0
cmp.b d4, d0 * d4 = v.c
ble while_exit
while_pass:
nop
* a[j+1] = a[j];
lea a, a0
move.l j, d1 *d1 = j offset
muls.w #mys_size, d1
move.l d1, d2 *d2 = j+1
add.l #mys_size, d2
move.l (mys_i_off, a0, d1.l), d0
move.l d0, (mys_i_off, a0, d2.l)
move.b (mys_c_off, a0, d1.l), d0
move.b d0, (mys_c_off, a0, d2.l)
move.w (mys_s_off, a0, d1.l), d0
move.w d0, (mys_s_off, a0, d2.l)
* j--;
move.l j, d0
sub.l #1, d0
move.l d0, j
bra while_start
* }
while_exit:
nop
* a[j+1] = v;
lea a, a0
move.l j, d1
muls.w #mys_size, d1
add.l #mys_size, d1
move.l d3, (mys_i_off, a0, d1.l)
move.b d4, (mys_c_off, a0, d1.l)
move.w d5, (mys_s_off, a0, d1.l)
* i++
move.l i, d0
add.l #1, d0
move.l d0, i
bra for_start
* }
for_exit:
end:
nop
nop
org $4000
***************
* GLOBAL DATA *
***************
*struct mystruct a[N] = {
* {100, 'Z', 19},
* {12, 'Z', 7},
* {12, 'Y', 201},
* {-7, 'A', 101},
* {12, 'L', -7},
* {12, 'M', 20},
* {87, 'X', -87}
*};
a:
dc.l 100
dc.w 'Z'
dc.w 19
dc.l 12
dc.w 'Z'
dc.w 7
dc.l 12
dc.w 'Y'
dc.w 201
dc.l -7
dc.w 'A'
dc.w 101
dc.l 12
dc.w 'L'
dc.w -7
dc.l 12
dc.w 'M'
dc.w 20
dc.l 87
dc.w 'X'
dc.w -87
*struct mystruct v;
v: ds.l 2
*int i, j;
i: ds.l 1
j: ds.l 1
end
* This is the expected output.
* i=-7 c='A' s=101 1090519141
* i=12 c='L' s=-7 1275133945
* i=12 c='M' s=20 1291845652
* i=12 c='Y' s=201 1493172425
* i=12 c='Z' s=7 1509949447
* i=87 c='X' s=-87 1476460457
* i=100 c='Z' s=19 1509949459