Now that I can run the Knuth version of the Insertion sort via MIXAL, I want to convert it to AARCH64 Assembly. What I am going to try to do here is a line by line translation. This is not necessarily how I would write the insertion sort in AARCH64 assembly, but rather a direct translation of the MIXAL version.
I started by defining constants for the output parameters. This is the equivalent to the TERM definition in the MIXAL version.
I print out the completed buffer. You can see some trial and error here; I was trying to calculate N, the length of the buffer, bases on the addreses, just as I had done for Hello World messages, but the fact that I needed to put a blank in the first position made that logic more complex than I wanted. So, while I hand caluclated the leng of the bufffer (26) I add 2 to account for the lead blank and the trailing \n.
IUn MIXAL, Many of the comparisons are done between registers and memory. AARCH64 does not support this. You also cannot add two integers without first loading one of them into a register. Thus, many single commands in MIXAL become multiple. For example,
LDA INPUT+N, 1
This requires four distinct operations.
- load input into a temporary register: ldr x8, =INPUT
- add N to INPUT add x3, x8, N
- add the offset of the X1 register to index the value of INPUT+T: add x3, x3, x1
- load the x0 (used as the accumulator here) with the value stored in memory caluculated from the previous three steps: ldrb w0, [x3]
Here is the completed AARCH64 version. I put a comment with the MIXAL line at the start of each section. For the accumulator, I used X0. I used X10 for the extended register rX. Several other additional registers were used for temporary storage of values.
.global _start .data .equ STDOUT, 1 .equ SYS_WRITE, 64 .equ SYSCALL, 0 INPUT: .ascii " ZYXWVUTSRQPONMLKJIHGFEDCBA\n" N = 26 .text _start: mov x0, STDOUT //output the string before sorting ldr x1, =INPUT ldr x2, =N add x2, x2, 2 mov w8, SYS_WRITE svc SYSCALL insert: ldr x7, =N //START ENT1 2-N mov x9, 2 sub x1, x9, N H2: ldr x8, =INPUT //LDA INPUT+N, 1. x7 = INPUT+N add x3, x8, N add x3, x3, x1 ldrb w0, [x3] sub x2, x7, 1 //ENT2 N-1, 1 add x2, x2, x1 H3: add x3, x8, x2 //x4 will hold the value of INPUT,2 ldrb w4, [x3] cmp w0, w4 B.GT H5 H4: ADD x11, x8, x2 //LDX INPUT,2 ldrb w10, [x11] //w10 is rX add x11, x11, 1 //STX INPUT+1,2 strb w10, [x11] SUB x2, x2, 1 //DEC2 1 cmp x2, 0 //J2P 3b B.GT H3 H5: ldr x11, =INPUT //STA INPUT+1, 2 add x11, x11, 1 add x11, x11, x2 strb w0, [x11] add x1, x1, 1 //INC1 1 cmp x1, 0 //J1NP 2B B.LE H2 mov x0, STDOUT //output the sorted string ldr x1, =INPUT ldr x2, =N add x2, x2, 2 mov w8, SYS_WRITE svc SYSCALL MOV X0, #0 MOV X8, #93 SVC 0
27 Lines of ARCH64 instruction, from 12 lines of MIXAL. I am sure that, using a more AARCH64 focused approach, you could greatly reduce the sort, but even still, I don’t think we’d get it down to 12 lines.
But you could make it much more legible.