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.