Created
May 14, 2013 02:58
-
-
Save anonymous/5573334 to your computer and use it in GitHub Desktop.
Binary Search in Assembly language (Motorola m68000)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
binSearch: EQU $8000 | |
binSrch: | |
link a6,#0 | |
movem.l d1-d7/a0-a5,-(SP) | |
move.l 8(a6),d1 *key | |
move.l 12(a6),a2 *lo | |
move.w 16(a6),a1 *hi | |
recurse: | |
move.w (a1),d2 | |
move.w (a2),d3 | |
cmp.w d3,d2 *compare hi and lo | |
bge skip *skip if hi >= lo | |
move #2,ccr *set v bit | |
bra out *branch because lo > hi | |
skip: | |
move.l a1,d2 *move address of hi to d2 | |
add.l a2,d2 | |
asr.w #1,d2 | |
andi.w #1,d2 *array[mid] | |
move.l d2,a3 | |
cmp.l (a3),d1 *compare key and array[mid] | |
bne else | |
move.l a3,d0 *if key = array[mid], return mid | |
bra out | |
else: | |
cmp.l (a3),d1 *compare key and array[mid] | |
bge right *if key >= array[mid], branch right | |
left: | |
subq.l #2,a3 *array[mid-1] | |
move.l a3,a1 *replace hi with array[mid-1] | |
pea (a1) *load parameters to stack | |
pea (a2) | |
move.w d1,-(SP) | |
jsr binSearch *jump to subroutine | |
adda.l #10,SP *pop parameters off stack | |
bra out | |
right: | |
addq.l #2,a3 | |
move.l a3,a2 | |
pea (a1) | |
pea (a2) | |
move.w d1,-(SP) | |
jsr binSearch | |
adda.l #10,SP | |
out: | |
movem.l (SP)+,d1-d7/a0-a5 | |
unlk a6 | |
rts | |
end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment